Let’s discuss an application of cyclostationary signal processing (CSP): time-delay estimation. The idea is that sampled data is available from two antennas (sensors), and there is a common signal component in each data set. The signal component in one data set is the time-delayed or time-advanced version of the component in the other set. This can happen when a plane-wave radio frequency (RF) signal propagates and impinges on the two antennas. In such a case, the RF signal arrives at the sensors with a time difference proportional to the distance between the sensors along the direction of propagation, and so the time-delay estimation is also commonly referred to as time-difference-of-arrival (TDOA) estimation.
Consider the diagram shown in Figure 1. A distant transmitter emits a signal that is well-modeled as a plane wave once it reaches our two receivers. An individual wavefront of the signal arrives at the two sensors at different times.
The line segment AB is perpendicular to the direction of propagation for the RF signal. The angle is called the angle of arrival (AOA). If we could estimate the AOA, we can tell the direction from which the signal arrives, which could be useful in a variety of settings. Since the triangle ABC is a right triangle, we have
When , the wavefronts first strike receiver 2, then must propagate over meters before striking receiver 1. On the other hand, when , each wavefront strikes the two receivers simultaneously. In the former case, the TDOA is maximum, and in the latter it is zero. The TDOA can be negative too, so that azimuthal degrees can be determined by estimating the TDOA.
In general, the wavefront must traverse meters between striking receiver 2 and striking receiver 1,
Assuming the speed of propagation is meters/sec, the TDOA is given by
In this post I’ll review several methods of TDOA estimation, some of which employ CSP and some of which do not. We’ll see some of the advantages and disadvantages of the various classes of methods through inspection, simulation, and application to captured data. Consider this post as a starting point to a study or development effort rather than as a definitive performance characterization.
Throughout this post, the data models of interest correspond to the following physical situation:
where and are the observed data from two physically separated sensors (antennas and their receivers), is the time difference of arrival (TDOA), and and are independent receiver noises for the two sensors. The two receivers are assumed to employ a common timing reference so that the only contribution to is the propagation delay.
This model neglects several potentially important aspects of real-world captured data sets, such as the Doppler effect, time variation of , cochannel interference, and phase mismatch between the signal components ( components) in each data set. That is, a more complete model might look like
where and are complex scalars (numbers), and are the Doppler shifts for the two sensors, and and are one or more cochannel interferers, each of which has its own TDOA, Doppler shift, etc.
The noises and are assumed to be stationary, or at least do not possess any of the cycle frequencies of that we wish to exploit. They are also assumed to be statistically independent and have mean values of zero.
We have developed multiple TDOA estimation algorithms using the simpler model, as have others, and then we end up applying them to data adhering to the more complex signal models. This is due to the generally high degree of difficulty with mathematically deriving algorithms using the more complex models.
A simple, and often effective, approach to estimating is to estimate the cross correlation between and , and find the location of its maximum. That location is then the TDOA estimate .
The cross correlation method works because the autocorrelation for any signal achieves its maximum at a delay (correlation lag) of zero. (It may achieve this same maximum at other delays as well, but will definitely achieve it at . Consider .)
The cross correlation between and is
The expectation can be distributed to the four terms. The final three terms are all zero. The cross correlations between the signal and noise are zero because they are independent, and the noises have zero mean values. The final term, “noise times noise,” is zero because the two noises are independent, and have zero mean values. So we end up with
Now, we’d like to express this cross correlation in terms of a function that we know how to maximize, such as the autocorrelation for . But the form isn’t yet familiar; we have defined our functions with symmetrical lag variables and ,
We can force our desired form in the following way. Consider the autocorrelation for two arbitrary time instants and :
Let’s define two new variables that are the difference and the average value of the two time instants and ,
Then and can be expressed in terms of and as follows
Therefore the generic autocorrelation for is re-expressed as
as desired. For our cross-correlation problem, we identify
This leads to
So we have
For the cross-correlation method, let’s focus on the term here, or
Since the autocorrelation function for peaks at , the cross correlation with between and peaks at . (Don’t worry about the sign of here, it is just an artifact of which receiver we associate with and which with .)
In practice, we simply form an estimate of the cross correlation and find the location of its maximum.
Generalized Cross Correlation (GCC)
The cross correlation can be expressed as the inverse Fourier transform of the cross spectrum between and , which is denoted by ,
Notice that if there are frequency bands for which the cross spectrum is small relative to the noise power, the contribution to the inverse transform can be harmful and cause TDOA estimation error. Thus, we may wish to weight the cross spectrum prior to inverse transformation, such as with a general weighting function ,
This form can also be derived by modifying our problem statement to include arbitrary linear time-invariant filtering applied to each of and prior to cross-correlation-based TDOA estimation. A variety of weighting factors, and their motivations and properties, are discussed in Knapp/Carter’s paper on Generalized Cross Correlation (GCC) (The Literature [R52]).
In this post, we will use , which we will approximate as . This is essentially the Eckhart filter ([R52]) when the receiver noises are white and possess the same variances. Other helpful references on the GCC class of estimators were published by Knapp, Carter, Hero, and Kirlin [R53]-[R60].
Cyclic Cross Correlation (CCC)
Recall from our development for the cross-correlation method that the time-varying cross correlation between and is given by
An individual cyclic cross correlation term in this cross correlation is given by
If the underlying cyclic autocorrelation achieves its maximum at , then the magnitude of the cyclic cross correlation will achieve its maximum at . Therefore, the cyclic cross correlation can be used to form an estimate of the delay in a manner similar to the conventional cross correlation,
For some signals (textbook rectangular-pulse!), the cyclic autocorrelation does not peak at , but may exhibit a pair of peaks whose center is indeed at . For such signals, the search for a single peak can be replaced by a search for a pair of peaks. The TDOA estimate is then the midpoint of the locations of the two peaks.
Spectral Coherence Alignment (SPECCOA)
The SPECCOA method arises from a least-squares fitting problem involving the relationship between the cyclic cross correlation and the cyclic autocorrelation. Recall that this relation is given by
If we perform a least-squares minimization over the error given by the absolute value of the differences between the left and right sides of that equation, we end up with the following estimator
The SPECCOA estimator is derived in The Literature [R48]-[R49].
Spectral Correlation Ratio (SPECCORR)
By taking a system-identification approach, Gardner and Chen (The Literature [R51]) derive yet another cyclostationarity-exploiting TDOA estimator that inverse transforms the ratio of the cyclic cross spectral correlation function and the cyclic spectral correlation function,
Spectral Coherence Nulling (SPECCON)
Consider the signal , where and are our usual noisy CS signals (4)-(5). If the delay/advance parameter is equal to , then the spectral correlation at cycle frequency for will be zero, because the spectral correlation for the components in and will be identical. So we can consider minimizing the spectral correlation for over the parameter . This leads to the SPECCON method (The Literature [R48]).
SPECCON is given by
Generalized SPECCOA (GSPECCOA)
GSPECCOA arises from considering all auto- and cross-SCF functions for the two sensor time-series, and jointly fitting them to an ideal SCF for the signal of interest (The Literature [R50]). The resultant algorithm can be expressed as
Approximate Maximum Likelihood (AML)
I have attempted to derive the weak-signal maximum-likelihood TDOA estimator for the signal model involving gain-and-phase mismatched receivers ((6)-(7) with ). The mathematics is rather complex, and tedious, so I’m just going to say that I’m including two approximations to the ML estimator that I call AML1 and AML5. They are similar to GSPECCOA.
The Case of No Interference
Let’s consider a simulated textbook BPSK signal with square-root raised-cosine pulses. The excess bandwidth parameter (roll-off) is 1.0, the bit rate is (10 samples per signalling interval), and the carrier frequency is . So this signal has five cycle frequencies that we can exploit: the two non-conjugate cycle frequencies of 0 and 1/10, and the three conjugate cycle frequencies of , , and . A small amount of noise is added so that the inband SNR is approximately 20 dB. The TDOA is set at 10 samples.
In all cases shown here, 65536 samples are processed. All spectral correlation functions are estimated using the frequency-smoothing method. All cross spectral correlations are not smoothed (more on that below), and all auto spectral correlation functions are smoothed with a rectangular smoothing window with width equal to 500 frequency bins. This means the smoothing window width is equal to 500/65536 = 0.0076 (normalized) Hz.
For each simulated algorithm, we plot the TDOA objective function. That is, we plot the function of delay that is either maximized or minimized by the algorithm to find the TDOA estimate. First, consider the conventional case of a non-conjugate cycle frequency of zero (no CSP):
(Here SPECCORR is coincident with Cross Correlation.) All the algorithms’ objective functions peak at the correct delay of 10 samples (the true signal TDOA value). The next graph shows the objective functions for the case of the non-conjugate cycle frequency of :
Once again, all the objective functions peak at the correct TDOA. The shapes of the functions are different from each other, and are also different from those for . Each algorithm provides a slightly different trade-off between the width near the true TDOA and the height at points distant from the TDOA. This is akin to a resolution/sidelobe type of trade-off that is common in spectral analysis and other signal-processing settings.
Here are the objective functions for the three conjugate cycle frequencies:
Several of the algorithms have multi-cycle extensions, where multiple cycle frequencies are exploited simultaneously. Here are the objective functions for those multi-cycle algorithms when they exploit all five cycle frequencies:
The Case of Cochannel Interference
Now let’s add a cochannel interferer to our BPSK signal. The interferer will also be a BPSK signal, with slightly different parameters, but will completely overlap the original BPSK signal in both time and frequency–it cannot be removed by any sort of linear time-invariant filtering or time-gating operation. If it could, we could identify each signal’s band, filter them to isolate them, and then apply the cross-correlation (non-CSP) methods and we’d be doing very well indeed.
The interferer has the same pulse function as the BPSK signal of interest, a bit rate of and a carrier frequency of . These choices imply that the two signals do not share any cycle frequencies except for the (trivial) non-conjugate cycle frequency of zero. The interferer power and the original signal power are the same. This all results in the PSDs shown here:
The interferer’s TDOA is 17 samples. Let’s go through the same sequence of plots that we went through for the case of an interference-free signal. First, the conventional methods and the CSP methods that use only the non-conjugate cycle frequency of zero (stationary-signal processing):
Several of the methods still peak at the TDOA of the BPSK signal, but each also peaks for the TDOA of the interferer. However, methods such as GSPECCOA peak at neither TDOA, but somewhere between the two TDOAs.
Without some further prior information, it would be impossible to reliably associate any of the local maxima with the TDOA for the signal–which peak belongs to which signal?
The next example corresponds to the non-conjugate cycle frequency of 0.1, which is the bit rate for the BPSK signal of interest, but is not a cycle frequency for the BPSK interferer:
Here are the objective functions for the conjugate cycle frequencies for the BPSK signal of interest:
And here are the objective functions for the case of combining the information in all five cycle frequencies:
All of the methods peak at the correct TDOA, although they also show significant values near the TDOA of the interferer. This is largely due to the inclusion of the non-conjugate cycle frequency of zero, which is sensitive to the presence of all signals. If we eliminate this cycle frequency, we obtain the following objective functions:
Here the SPECCOA and AML5 algorithms do not appear to reflect the presence of the interferer at all.
Finally, if we reverse the roles of the two modulated signals, and use the four cycle frequencies for the interferer instead of those for the original BPSK signal, we obtain the following set of objective functions:
Now the functions peak at the TDOA of the interferer, as expected. This is another illustration of the signal selectivity property of cyclostationary parameters.
To reassure us that the various CS-exploiting methods actually work on real-world data, let’s apply them to a captured CDMA-EVDO signal. We process seconds of a downlink EVDO signal sampled at MHz. This signal possesses non-conjugate cycle frequencies that are harmonics of MHz. We induce a TDOA of samples by applying a Fourier-based delay operation to the captured data. The -second data record is processed by extracting successive blocks with length ms and applying GSPECCOA for various cycle-frequency selections.
Here are the histograms of the obtained TDOA estimates:
In the histogram plot, the histogram-bin locations are constrained to lie within samples, so all TDOA estimates less than samples are lumped into the bin at , and similarly for . Clearly the cycle-frequency set that uses all five harmonics provides nearly perfect performance, producing the nearest estimate to samples (that is, samples) that it can for almost all trials.
I’ve presented the algorithms’ objective functions in terms of samples, and I used a simulated example where the true TDOA is equal to an integer number of samples (). In practice, the actual TDOA is simply a function of the propagation speed and angle of arrival, and so is a continuous-valued variable, not a discrete one. But we want to work with sampled data, so we are stuck with discrete-valued TDOA estimates.
The discrete nature of the TDOA estimate in digital signal processing leads to unavoidable errors when applied to actual captured data. Perhaps even more importantly, it leads to the possibility of erroneous performance analyses when Monte Carlo simulations are used. In particular, if the TDOA is selected to be an integer number of samples, the various algorithms can yield perfect estimates (zero errors) over many many Monte Carlo trials. (My algorithm is perfect! Let’s publish!)
One way of avoiding this misleading result is to interpolate the data prior to applying the TDOA estimate. It could be interpolated such that the minimum non-zero error is small relative to the desired error in some application. At least in this case, the relevant performance can be captured, and the algorithms correctly ranked.
When interpolation is applied to the EVDO example above, we obtain the following histograms:
As the level of interpolation increases, the TDOA estimates inch closer to the true value of (which does not lie on any interpolated point, since the interpolation factors are multiples of two).
It is tempting to apply lots of smoothing to the auto and cross spectral correlation functions in a given CSP algorithm, so as to decrease the variance of the estimate, and thereby improve the variability of the TDOA estimates. But there is a catch. We can apply plenty of smoothing to any auto spectral correlation estimate, but the ideal cross spectral correlation functions contain a sinusoidal factor whose period in the frequency variable depends on the unknown TDOA . Thus, these functions can easily be oversmoothed, causing the destructive interference between periods of the sinusoidal factor. I typically smooth the auto estimates and do not smooth the cross estimates at all.
I’ll leave it to you, dear reader, to calculate the cross spectral correlation between and in order to see the problematic complex sinusoidal term.