Method and Apparatus for Measuring the Time Delay Between Signals

This invention relates generally to the field of signal processing and more particularly to techniques for discriminating the time delay between two similar signals.

Correlation techniques can be used to determine the time delay between two similar signals which have been corrupted by noise. However, whether the result of the cross-correlation is meaningful depends on the signal-to-noise ratios and other characteristics of the signals. As the power level of the signals decreases, noise at a constant level becomes a more significant portion of each of the signals. This increases the problems of delay determination by correlation techniques and can require substantial increases in correlation time. The time delay between voice information signals is difficult to determine by correlation. Such determinations become especially difficult when the signals are at low power levels in a noisy environment.

The location of a radiation source can be determined by measuring the difference in time of arrival of a signal from that radiation source at three different places. This determination requires measurement of the relative delay between the three received signals. In many situations those signals have low signal-to-noise ratios.

A delay discriminator is needed which can reliably determine that time delay between two signals which have been corrupted by noise. For certain applications it is desirable to have a delay discriminator which does not rely on special characteristics of the signals.

The system of the present invention solves these prior art problems through means for individually characterizing signals and means responsive to corresponding portions of those characterizations for providing a measure of the time delay of one signal relative to another. One embodiment which discriminates the delay of a second signal relative to a first signal includes means for dissecting a time segment of each signal into component frequencies as a means of characterizing that signal. A means for cross characterizing the first and second signals responds to the signals' components at each component frequency (corresponding components) and determines the time delay of each component of the second signal relative to the corresponding component of the first signal. This cross-characterization means also derives a weight for each of these time delay determinations. A means for combining these cross-characterizations is responsive to these time delay determinations and their associated weights and generates a measure of the delay of the second signal relative to the first.

This embodiment also provides an estimate of the uncertainty of that delay measurement. Means for refining the measurement may combine a number of separate delay measurements (each based on a different time segment of the signals) to provide a measurement having a smaller estimate of its uncertainty.

FIG. 1 is a schematic illustration of a delay determination system in accordance with the invention; and

FIG. 2 is a schematic illustration of an alternative system for dissecting and cross-comparing the signals.

One preferred embodiment of a delay discriminator 112 for discriminating the delay between signals A and B in accordance with the present invention is illustrated in a block diagram form in FIG. 1. In this discriminator 112 each of the signals A and B is applied to an associated signal characterizer 120A or 120B, respectively. The signal characterizer 120A is shown in detail whereas the signal characterizer 120B is shown as a block.

Within signal characterizer 120A the signal A is passed through an anti-aliasing filter 121 which in this embodiment is a low pass filter having a sharp cut-off at 4 KHz. Anti-aliasing filter 121 prevents a subsequent sampling operation from translating high frequency signal components so that they appear to be low frequency ones. From anti-aliasing filter 121 the now frequency limited signal is coupled to a sampling analog-to-digital converter 122. This converter samples the amplitude of the signal A at certain times (i.e. at a sampling frequency) determined by timing and control system 118. For audio signals having a bandwidth of up to 3.2 KHz the sampling is preferably at an 8 KHz rate (twice the cut-off frequency of the anti-aliasing filter). Thus one sample is taken every 1/8 millisecond. This sampling rate is high enough to ensure that the samples comprise an accurate representation of the 3.2 KHz input signal. Each of the amplitude samples is analog-to-digital converted to provide a digital value representative of the amplitude of that sample. These digital values are provided in sequence at an output terminal 123 of the converter 122. The remainder of characterizer 120A processes these samples to produce a characterization of signal A which can be used for delay determination purposes.

For signal processing the samples of the signal are handled in groups of 2H samples. In this embodiment 2H is 256. Since the samples are taken every 1/8 millisecond each group of 256 samples represents 32 milliseconds of the input signal. Each group of 256 samples from converter 122, is multiplied in a multiplier 124 by a 256 point window function. In this operation each sample is multiplied by an associated window function value. The window function values are provided to multiplier 124 by a window function unit 126 which may be a recirculating register which is 256 stages long.

The window function is trapezoidal. That is, the initial window function value is small with successive ones increasing until a maximum value is reached after which it remains constant until it begins decreasing to return to the initial small value at the end of its series of 256 values. The window function is synchronized with the operation of the converter 122 and multiplier 124 by timing and control unit 118. In this embodiment the rise and fall of the trapezoid are each 32 steps long for a set of 256 samples. The first window function value is zero. The second is 1/32. The window function value increases in increments of 1/32 until a value of 1 is reached for the thirty-third sample. The window function value remains 1 until the two hundred and twenty-fourth sample where the value reduces to 31/32. The value reduces by 1/32 for each successive sample until the 256th sample where the value is zero. Thus, the first 32 and the last 32 samples in each set of 256 samples have their amplitudes reduced by the multiplication by the window function. This reduction in amplitude for early and late samples smooths the transition between the zero value each sample group has outside its span of 256 samples and the full value middle portion (192 samples) of the sample group. This smoothed transition provides a modififed 16 sample set which, when Fourier transformed, provides lower phase errors than the unmodified set of samples would provide when transformed. A Fourier transformation is subsequently performed on the sample set. Window function unit 126 and multiplier 124 can be omitted from characterizer 120 with a consequent decrease in characterization accuracy.

The output terminal 125 of multiplier 124 is coupled to the input terminal of a double buffer 130. Double buffer 130 temporarily stores each sample-window function product. Double buffer 130 includes first and second registers 131 and 132, respectively which operate independently.

Those values comprising one modified set of 256 samples are stored in the first buffer register 131 as they are received. When the full 256 samples of that modified set have been received, storage of incoming (modified) samples is switched to the second buffer register 132. This switching is synchronized with window function unit 126 by timing and control unit 118. While samples are being placed in storage in the second buffer register 132, the first buffer register 131 is read out through output terminal 133. When the second buffer register becomes full (256 samples) the input to the double buffer 130 is switched again to begin filling the first buffer while the second buffer is read out.

The 256 samples read out of buffer 131 are coupled to a Fourier transform system 140 which includes a means 141 for performing a 256 point complex Fourier transform and a means 142 for extracting a phase spectrum and a power spectrum from the output of the Fourier transform. Means 141 provides 128-point-complex-Fourier-transform data as its output. Because 256 equally-spaced-in-time samples are transformed, the 256 point Fourier transform's output data comprises 256 different frequencies. Half of these frequencies are positive and half are negative. These 256 values contain the information required to compute the power and phase of 128 frequency components of the signal. The number of frequency components is always half the number of samples transformed. Thus, if 2H samples are transformed there are H powers and phases. The power, phase and frequency values from means 141 are provided to the means 142 for extracting the phase (.phi.) and the power spectrum (S) of this Fourier transform data.

The phase (.phi.)for a given positive frequency .vertline.f.sub.i .vertline. (of these 128 positive frequencies) is ##EQU1## This phase is calculated in radians. The power (S) for that given positive frequency .vertline.f.sub.i .vertline. is

where "amp. of (+.vertline.f.sub.i .vertline.) freq." is the amplitude of the component having the freq. +.vertline.f.sub.i .vertline.. Means 142 provides 128 phases (one for each frequency magnitude) and 128 power levels (one for each frequency magnitude) as its output. Each of these frequencies is treated as positive. This is the 128 point transform output from means 142. Each of these frequencies is referred to as a component of the input signal A.

Thus, the Fourier transform system 140 dissects the signal A into a set of 128 component frequencies whose phase and power characterize signal A during the corresponding 32 millisecond portion of signal A. The frequency component at DC (frequency=0) has no meaningful phase information and is discarded. This characterization of signal A is coupled to and stored in a memory 150 for use in determining the delay of signal B with respect to signal A. This stored characterization has three values associated with each component i, 1.ltoreq.i.ltoreq.127--its frequency f.sub.i, its phase .phi..sub.i and its power S.sub.i. In a system in which the sampling rate is fixed, the f.sub.i 's are fixed and therefore may be stored separately from the phases and powers which change from sample set to sample set.

Depending on the Fourier transformation procedure utilized, Fourier transform system 140 may comprise a single transformation means which provides its Fourier transform data in the form of 128 positive frequencies each having a phase and a power level. The Fourier transform system 140 (means 141 and 142) operates under the control of timing and control unit 118 and completes its processing of one set of modified data samples while the subsequent set of samples is being taken, modified and placed in storage in the double buffer 130.

At the same time that the signal characterizer 120A has been frequency dissecting a set of samples from signal A to provide a characterization of signal A, the signal characterizer 120B has been performing a similar dissection on a time related sample set from the signal B to provide a characterization of input signal B. Normally sampling analog-to-digital converters 122A and 122B operate simultaneously and the switching of the buffers in each of the characterizers occurs at the same time. Under these conditions the sample sets from signals A and B are in synchronism. If the Fourier transform system is fast enough, a single such system can perform the Fourier transformation for both signals A and B.

The Fourier transform data for signals A and B are provided from the memories 150 of the respective characterizers 120A and 120B to an A vs. B Signal Delay Measurement Generator 170AB. The generator 170AB includes two major units--a signal cross characterizer 178 and a cross characterization combiner 210. In this embodiment the cross characterizer 178 includes a component delay determiner 180 and a component weight deriver 190.

The phase and the associated frequency of each of the components of the signals A and B is provided to the component delay determiner 180. Determiner 180 determines the time delay of each component of signal B relative to the same component of signal A. These determinations may preferably be made in sequence one component at a time. The phases of the components of signals A and B, .phi..sub.Ai and .phi..sub.Bi, respectively, for a given frequency f.sub.i are applied to the two input terminals 182 and 183, respectively, of a combiner 181 where the two signals are subtracted. These phases are in units of radians. Input terminal 182 has a positive sense and input terminal 183 has a negative sense. The difference (.phi..sub.Bi -.phi..sub.Ai) of these two phases is provided at the output terminal 184. This difference is taken modulo 2.pi.. That is if the difference D is less than -.pi., then 2.pi. is added to it successively until the difference D is in the range -.pi..ltoreq.D.ltoreq..pi. and if D>.pi., then 2.pi. is subtracted successively until -.pi..ltoreq.D.ltoreq..pi.. If there is no time delay between a pair of corresponding components their phases are equal and this difference is zero. If component B is delayed with respect to component A, the phase of component B is greater than that of component A and the difference is positive. If component B is advanced with respect to component A, then the difference is negative. This difference is the phase difference of the two components at frequency f.sub.i. To convert this phase difference (in units of radians) at a frequency f.sub.i to a time difference it is necessary to divide this phase difference by the 2.pi. times the frequency (2.pi.f.sub.i). This is done in a divider 185.

The phase difference is coupled to the dividend input terminal 186 of divider 185. The frequency f.sub.i times 2.pi. is applied by multiplier 187 to the divisor input terminal of divider 185. The quotient of these two factors is the delay .DELTA.t.sub.i of the component of signal B at frequency f.sub.i relative to the component of signal A at frequency f.sub.i. This delay .DELTA.t.sub.i is in seconds and is positive when component B is delayed relative to component A. This time delay value is provided at the output terminal 188 of divider 185 and at the output terminal 189 of time delay determiner 180.

The time delays .DELTA.t.sub.i for all 127 components could be added together and divided by 127 to provide an average time delay .DELTA.t.sub.AB as the estimate of the delay of signal B relative to signal A: ##EQU2## However, this does not take full advantage of all of the information about signals A and B which is provided by the characterizers 120. A much more accurate time delay measurement which has a much smaller uncertainty may be provided if a weighted average of the time delays .DELTA.t.sub.i is taken in which each of the time delays .DELTA.t.sub.i is weighted in accordance with its relative reliability.

The higher power level components provide more reliable delay determinations than lower power-level components. Also, higher frequency components provide better estimates of the time delay than lower frequency components. The relative merit is a function of the frequency squared. For this reason each of the time delays .DELTA.t.sub.i is weighted by a factor W.sub.i /W.sub.T in combining them to provide a signal delay measurement. The term W.sub.i is referred to as the weight for the time delay .DELTA.t.sub.i. The denominator W.sub.T is the sum of the W.sub.i 's. Thus, ##EQU3##

The estimate of the delay .DELTA.t.sub.AB of the signal B relative to signal A is: ##EQU4## Since W.sub.T is a constant for a given pair of signal A and signal B characterizations this is the same as: ##EQU5## Thus in the general case where there are H dissection frequencies: ##EQU6## This latter form is employed in this system because it allows each term (.DELTA.t.sub.i) (W.sub.i) to be accumulated as it becomes available and because it replaces (H-1) divisions by (H-1) additions and one division. This speeds the signal processing and minimizes storage requirements.

The weights W.sub.i are provided by weight deriver 190 in response to the frequency f.sub.i and the powers S.sub.Ai and S.sub.Bi of the signals A and B at frequency f.sub.i, respectively. These values are provided as first, second and third inputs to the component weight deriver 190. A series of four two-input multipliers 191-194 receives these power levels and this frequency and produces the product 2S.sub.Ai S.sub.Bi f.sub.i.sup.2. The power levels S.sub.Ai and S.sub.Bi are also applied to the input terminals of a two-input adder 195. Both of these input terminals have a positive sense. The sum S.sub.Ai +S.sub.Bi from adder 195 is applied to the divisor input of a divider 196. The product 2S.sub.Ai S.sub.Bi f.sub.i.sup.2 from multiplier 194 is applied to the dividend input of divider 196. The quotient at the output terminal of divider 196 is (2S.sub.Ai S.sub.Bi f.sub.i.sup.2)/(S.sub.Ai +S.sub.Bi. This value is provided at the output terminals 197 of weight deriver 190 as the weight W.sub.i. The factor ##EQU7## is an estimate of the effective signal-to-noise ratio of the signal A and the signal B components at frequency f.sub.i (relative to the other frequency components) for time delay measurement purposes, assuming a uniform noise distribution over frequency. This factor must be multiplied by the frequency squared to provide a frequency adjusted weight (W.sub.i) at each of the various frequencies f.sub.i. This frequency adjusted weight is directly proportional to the merit of the time delay estimate at that frequency f.sub.i and is in a form which can be added directly to determine W.sub.T and which provides time-delay-weight products (.DELTA.t.sub.i)(W.sub.i) which can be added directly.

The timing and control unit 118 regulates the operation of the memories 150, determiner 180 and deriver 190 to produce the time delay and weight values .DELTA.t.sub.i and W.sub.i for a given f.sub.i component simultaneously. These values for a given i are provided as inputs to a multiplier 201. The output from multiplier 201 (the product (W.sub.i)(.DELTA.t.sub.i)) is a weighted time delay determination for the i.sup.th frequency. The weighted time delay determinations (W.sub.i)(.DELTA.t.sub.i) and the weights W.sub.i (for all i) comprise a cross-characterization of signals A and B and are provided as inputs to the cross-characterization combiner 210. Alternatively, multiplier 201 can be considered part of combiner 210 which then receives the inputs .DELTA.t.sub.i and W.sub.i.

Within combiner 210 the product (.DELTA.t.sub.i)(W.sub.i) is provided as an input to an accumulating adder 212 and the weight value W.sub.i is provided as an input to an accumulating adder 213. Once the data for each of the component frequencies has been processed, the accumulating adders 212 and 213 provide as outputs the sums ##EQU8## respectively. The sum of the (W.sub.i) (.DELTA.t.sub.i)'s is the sum of the weighted time delays and is applied to the dividend terminal of a divider 214. The sum W.sub.T of the W.sub.i 's is applied to the divisor terminal of the divider 214. The quotient from the divider 214 is the measure .DELTA.t.sub.AB of the delay of the signal B with respect to the signal A. This signal is provided at the output terminal 215 of combiner 210. If the signal B is retarded relative to signal A, then the delay of the signal B is positive (greater than zero). If signal B is advanced relative to signal A, then the delay is negative (less than zero).

The value W.sub.T from adder 213 is also applied to the divisor input of a divider 216 which has a dividend input of one. The quotient from divider 216 is provided at an output terminal 217 of the combiner 210. The value at the terminal 217 is the uncertainty .sigma..sup.2.sub.AB of the time delay estimate .DELTA.t.sub.AB. This uncertainty is a result of distortion of the signals and their components in a random way by the noise. The value W.sub.T from adder 213 is also provided at an output terminal 218. This value is equal to 1/.sigma..sup.2.sub.AB.

So long as the delay between the signals A and B is less than one half the period of the highest frequency in the Fourier data, there is no ambiguity as to the phase of any component since all phases (.phi.) will be in the range -180.degree.<.phi.<180.degree.. If the time delay exceeds the above limit, then ambiguities in the phase of the high frequency components can be resolved by reference to the lower frequency components for which no phase ambiguity exists.

When the uncertainty .sigma..sup.2.sub.AB is greater than desired and the delay between the signals is expected to remain substantially constant over the period of time in which a number of delay measuelay between the signals is expected to remain substantially constant over the period of time in which a number of delay measurements .DELTA.t.sub.AB are generated, a signal delay measurement refiner 220 may be provided to reduce the uncertainty. Refiner 220 receives a succession of delay measurements .DELTA.t.sub.ABj, 1.ltoreq.j.ltoreq.J where J is the number of such measurements. Each measurement .DELTA.t.sub.ABj has an associated uncertainty .sigma..sup.2.sub.ABj. These measurements are based on samples of the signals A and B which were taken from a succession of 32 millisecond portions of signals A and B. Therefore, in general the delay measurements and their uncertainties will vary. Within refiner 220, as each of the .DELTA.t.sub.ABj and .sigma..sup.2.sub.ABj values is received, the .DELTA.t.sub.ABj value is divided by the .sigma..sup.2.sub.ABj value in a divider 221. The quotient of this division is provided as an input to an accumulating adder 222. The value .sup.1 /.sigma..sup.2.sub.ABj from output terminal 218 of generator 170.sub.AB is provided as an input to an accumulating adder 224. The output of accumulating adder 222 is divided by the output of accumulating adder 224 in a divider 225 whose quotient is provided at an output terminal 226 of refiner 220. This output signal is a refined measurement .DELTA.t.sub.AB of the delay between the signals A and B, where the indicates that this is a more refined estimate of the actual value of .DELTA.t.sub.AB. The output of the accumulating adder 224 is divided into one in a divider 227. The quotient of this division is provided at an output terminal 228 of the refiner 220. The signal at the output terminal 228 is a value .sigma..sup.2.sub.AB. If the actual delay between signals A and B is fixed, then the uncertainty .sigma..sup.2.sub.AB decreases with each successive sample .DELTA.t.sub.ABj which is provided to the refiner 220. When a desired uncertainty level .sigma..sup.2.sub.AB has been obtained or a desired number J of delay estimates .DELTA.t.sub.ABj have been combined, refiner 220 may be reset to begin calculating new values of .DELTA.t.sub.AB and .sigma..sup.2.sub.AB.

It is preferred to use a signal processing digital computer to perform the operations of delay discriminator 112 because the computer's high speed enables the delay measurements to be provided in substantially real time. Such near real time delay measurements are necessary in many position location systems.

A wide variety of Fourier transform programs for digital computers are available which can perform the Fourier transform function. Any computer which can implement such programs can be used in the practice of the present invention. However, if the delay data is needed in "real time" a computer must be selected which is fast enough to perform the calculations in "real time". A signal processor which is fast enough to provide such real time data is described in a paper entitled, "A signal Processor For Communications Signal Analysis" by S. J. Nossen et al., which was published in the NAECON proceedings for May 1980 at pages 233-236. This signal processor is representative of one processor implementation which is easily adapted to implement the discrimination technique of this invention. This processor has been built and operated in a number of different systems.

As has been described, the delay discrimination process of this invention gives greater weight to the higher power and the higher frequency components of the signal--those portions of the signal which provide the more reliable delay determinations. In contrast, the prior art cross correlation method gives equal weight to all portions of the signals and thus lacks the gain which this invention provides by emphasizing the more meritorious portions of the signals. The differences between these techniques are particularly significant when the signal-to-noise ratio is small. Because of the improvement in the signal-to-noise ratio provided by the Fourier transform, the inventive technique can determine delays even when the signal-to-noise ratio is so low that delay determinations can not be made in reasonable times or in some cases not at all using cross-correlation techniques. The ability of the present invention to discriminate small delays is limited mainly by the resolution of any given implementation of the system, i.e. how noisy the signals are and how much time is available for making the determination.

This system is useful with any signal waveform. In a limiting case where the transmitted signal is an unmodulated pure sine wave, the method of this invention becomes equivalent to a cross-correlation delay determination. In the more general case where modulation is present on the signal, the inventive technique provides a more accurate delay estimate than cross-correlation does.

Computer simulations of the system of FIG. 1 were run. With voice communication input signals the performance of that system was consistently better by a wide margin compared to a known cross-correlation based system. One of the reasons for this superior performance is the dissection of the signal followed by production of individual weighted time delay determinations (.DELTA.t.sub.i)(W.sub.i) which are combined and divided by W.sub.T to generate the measure of the delay of signal B relative to signal A. This weighting technique ensures that the signal delay measurement is more certain than any individual delay determination.

The system 112 of FIG. 1 generates the signal time delay measurement .DELTA.t.sub.AB by a process comprising the steps of (1) characterizing each signal by dissecting it into separate frequency components, (2) determining the delay .DELTA.t.sub.i between the same frequency (corresponding) components of two signals, (3) deriving a weight W.sub.i for each delay determination (.DELTA.t.sub.i) from the power in those components and (4) combining the determined time delays and weights to form the weighted sum .DELTA.t.sub.AB. By providing .sigma..sup.2.sub.AB as an additional output, the system is able to provide a refined measurement of the delay. This is done by forming a weighted sum of a time sequence of delay measurements .DELTA..sup.t.sub.AB, where the .sigma..sup.2.sub.AB 's are the weights.

In system 112 of FIG. 1 the dissection is done by Fourier transformation of a set of samples of the signal. The component delay is obtained by subtracting the phases and dividing by the frequency of the same frequency components of the two signals.

FIG. 2 illustrates an alternative structure 312 for a portion of the delay discriminati.on system. In this embodiment, each signal characterizer is in the form of a frequency dissector 320A (or 320B) which comprises a plurality of bandpass filters 322.sub.i, each centered at a different frequency. Rather than being a single frequency as in the Fourier transform embodiment of FIG. 1, each of these dissection frequencies includes a range of frequencies. Each filter defines one of these dissection frequency ranges which may be referred to as a primary frequency range. The single frequencies of the Fourier embodiment may also be referred to as primary frequency ranges since they are spaced apart in frequency. Each of these frequency ranges may be identified by and referred to by the center frequency f.sub.i of the bandpass filter i which dissects it from the signal. If each filter has a pass band shape which is the Fourier transform of the trapezoidal window function (of unit 126 in FIG. 1) and is centered at a different one of the f.sub.i 's, then this dissection is equivalent to the sample and Fourier transform implementation 120 of FIG. 1. In this embodiment a cross characterizer 378 comprises a plurality of correlators 380.sub.i, one for each of the component frequencies. Each correlator is coupled to receive and correlate the signal A component and the signal B component in a given frequency range f.sub.i. The output of the correlators are time delay determinations based on the portion of each input signal which is within the pass band of the corresponding A and B filters. A weight for this time delay determination is proportional to the power in those components. The time delays and the weights are coupled to a cross-characterization combiner which may be like combiner 210 of system 112 of FIG. 1.

This delay discriminator is particularly useful in a data transmission system in which data is encoded as a controllable delay between two signals. Such a system may transmit the two signals as the upper and lower sidebands of a suppressed carrier signal. A delay discriminator in accordance with this invention can recover encoded data from signals having a data rate which makes their signal-to-noise ratios too low to allow delay determinations to be accurately made using correlation techniques. As a result, the signals may be transmitted at lower power levels than would be required if a prior art correlation delay determiner were used. These lower power levels render the signals more difficult to intercept.