This invention relates to fast transform based offset determination.
In a number of applications, it is necessary to estimate an offset, for example a time delay, between a two signals, x=(x0, . . . , xN−1) and y=(y0, . . . , yN−1), which may represent two noisy instances of a common signal with different delays. A well-known approach to determining the relative delay of the signals is to form a cross-correlation of the signals as the convolution of time-reversed version of one of the signals x−N=(xN−1, . . . , x0) and the other signal to find z=x−Ny=(z0, . . . , zN−1) and determine the index i of the value zi that is largest. It is also well known that the signal z can be determined using a Fourier Transform approach as z=−1((x)*(y)) where ( ) is the N point Discrete Fourier Transform (DFT), recognizing that the DFT approach computes a circular convolution, and therefore the signals x and y should be suitably padded with zeros.
Although presented above with a one-dimensional signal, essentially the same approach may be used for multidimensional data (e.g., images) in which an offset for each dimension is determined.
One application in which such delays are computed in a Global Positioning System (GPS) receiver, in which the signals represent a pseudo-noise reference signal and a reception of the same pseudo-noise signal transmitted from a satellite.
There is a need to reduce the computation required to determine a time offset, for example, to reduce the computation resources (e.g., processor speed, power, time) needed to implement the computation.