System and method of time of flight detection
A position-determining apparatus, such as a GPS receiver, determines the position of the mobile device based on the time of flight of a transmitted probe signal using a method in which sections of the received signal is classified into two or more categories and accumulated according to categories before being used to compute the convolutions familiar in the context of a matched filter. Using the method of the present invention to compute the convolutions, and optionally applying additional time-saving techniques described herein, a position determination is achieved using a number of arithmetic operations that is significantly reduced from that required in prior art methods to compute the convolutions. The reduced number of arithmetic operations can reduce significantly the power consumption required of a device carrying out a method of the present invention, and thereby realizing a significant advantage.
1. An apparatus for determining a distance based on a transmitted signal, comprising:
a storage device providing a first set of signal values representing time-ordered noise-less signal values of the transmitted signal, the first set of signal values being divided into sections, each section being associated according to a predetermined criterion with one of a plurality of categories, and each section having a predetermined number of signal values with each signal value being associated with a sample index representing a temporal position of the signal value in time;
a signal interface for receiving a second set of signal values representing digitized demodulated samples of a received signal, each of the signal values in the second set of signal values being assigned a category and a sample index based on a predetermined alignment in time with the signal values of the first set of signal values, wherein each signal value in the second set of signal value is assigned the same category and sample index as the corresponding signal value in the first set of signal values to which the signal value in the second set of signal values is aligned;
a set of accumulators each being associated with a corresponding one of the categories and a corresponding sample index, each accumulator being configured to sum a subset of signal values selected from the second set of signal values, the subset of signal values being signal values that are assigned to corresponding category and sample index; and
an arithmetic unit configured to compute one or more convolution of the transmitted signal and the received signal using the first set of signal values and the sums in the accumulators under one or more predetermined offsets in time relative to the predetermined alignment.
2. The apparatus of claim 1 , wherein the predetermined criterion determined the associated category of a section based on signal transitions within the section.
3. The apparatus of claim 1 , wherein the predetermined criterion determines the associated category of a section based on signal transitions in one or more sections previous in time or following in time relative to the section.
4. The apparatus of claim 1 , wherein the transmitted signal comprises a plurality of chips, and wherein each section is bounded in time along boundaries of two selected chips.
5. The apparatus of claim 1 , wherein the transmitted signal comprises a plurality of chips, and wherein each section is bounded in time along mid-points of two selected chips.
6. The apparatus of claim 1 , wherein the signal interface is configured to receive the second set of signal values from an RF front end circuit.
7. The apparatus of claim 1 , wherein each signal sample in the second set of signal samples is represented by a complex number, representing in-phase sampling and quadrature sampling of the received signal.
8. The apparatus of claim 1 , wherein the predetermined alignment results from a coarse estimation step.
9. The apparatus of claim 1 , wherein the predetermined alignment is provided by a server in communication with the apparatus over a telecommunication network.
10. The apparatus of claim 1 , wherein the arithmetic unit computes the convolutions after applying a masking function on both the sums in the accumulators and the first set of signal values.
11. The apparatus of claim 10 , wherein multiplying the masking function with itself is unity.
12. The apparatus of claim 1 wherein, using the largest one of the computed convolutions, the apparatus computes one of: a power of the received signal, an expected gain of a communication channel, a standard deviation of an additive noise, and a signal-to-noise ratio.
13. The apparatus of claim 1 , wherein each accumulator keep tracks of the number of signal values summed.
14. The apparatus of claim 1 , further comprising memory elements for maintaining a plurality of statistical states based on the convolutions.
15. The apparatus of claim 14 , wherein the statistical states relate to a probability distribution.
16. The apparatus of claim 15 , wherein the statistical states are represented by logarithms of probabilities computed from the probability distribution.
17. The apparatus of claim 16 , wherein the probabilities are calculated from the correlations based on an additive Gaussian noise model.
18. The apparatus of claim 15 , wherein the probability distribution relate to probabilities of the received signal is aligned in time with the transmitted signal under the predetermined alignment modified by predetermined offsets.
19. The apparatus of claim 18 , wherein a portion of the second set of signal values assigned to a predetermined category is excluded from being summed in the accumulators, the predetermined category encompassing signal values of the first set of signal values in sections in which no signal transition occurs.
20. The apparatus of claim 18 wherein a signal value in the second set of signal values is summed in one of the accumulators only when the corresponding signal value in the first set of signal values to which the signal value in the second set of signal values immediately precedes or immediately follows a signal transition.
21. The apparatus of claim 18 , wherein a portion of the second set of signal values are excluded from being summed in the accumulators, the portion of the second set of signal values corresponding to signal values at predetermined offsets corresponding to probabilities that are less than a predetermined threshold.
22. The apparatus of claim 15 , using the computed convolutions and the probability distribution, the apparatus computes an expected offset relative to the predetermined alignment.
23. The apparatus of claim 22 , wherein the apparatus operates in a sleep mode during which the arithmetic unit ceases computation of the convolutions, the apparatus enters into the sleep mode of operation for a predetermined time period after computing the expected offset.
24. The apparatus of claim 15 , wherein the probability distribution is updated over time.
25. The apparatus of claim 24 , wherein each convolution is computed based on earlier computed convolutions, the earlier computed convolutions being weighted by a factor that decays over time.
26. The apparatus of claim 1 , further comprising a demodulator coupled to the signal interface, the demodulator providing the second set of signal samples after demodulating the received signal; and a numerically controlled oscillator that provides a timing signal to the demodulator.
27. The apparatus of claim 26 , wherein the numerical oscillator adaptively updates a frequency and a phase of the timing signal.
28. The apparatus of claim 27 , wherein the phase of the timing signal is updated based on an estimate of a phase of the received signal, the estimate of the phase of the received signal being derived from by the largest one of the computed convolutions.
29. The apparatus of claim 27 , wherein the numerical oscillator updates the frequency and the phase of the timing signal at predetermined intervals, each predetermined interval having a duration based on a frequency resolution and a phase resolution of a frequency estimate and a phase estimate, respectively.
30. The apparatus of claim 27 , wherein the frequency and the phase of the timing signal is updated according to a Kalman filter.
31. The apparatus of claim 13 wherein the apparatus determines that a signal of a predetermined offset is detected in the received signal when a predetermined parameter has a value exceeding a threshold, wherein the predetermined parameter is based on a difference in the accumulated values in two of the accumulators, and wherein the threshold is based in part on a sum of the signal values summed in the accumulators.
32. The apparatus of claim 31 wherein, when the apparatus determines two or more signal of different predetermined offsets are detected, the received signal is deemed to have the earliest of the predetermined offsets.