Efficient algorithm for processing GPS signals

• US 6,750,814 B1
• Filed: 06/16/2003
• Issued: 06/15/2004
• Est. Priority Date: 09/18/2000
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: CellGuide Ltd. (Alphabet Inc.)
• Inventors: Dochovni, Eran, Nir, Joseph, Cohen, Hanoch, Shayevits, Baruch
• Primary Examiner(s): Phan, Dao
• Application Number:
  US10/363,777
• Time in Patent Office: 365 Days
• Field of Search: 342/357.01, 342/357.05, 342/357.06, 342/357.12, 342/352, 701/213, 701/215, 701/207
• US Class Current: 342/357.77
• CPC Class Codes: G01S 19/29 carrier including Doppler, related G01S19/246 takes precedence
• CPC Class Codes: G01S 19/30 code related G01S19/246 takes precedence

Abstract

A disclosed algorithm enables fast and efficient location of a mobile unit by obtaining and processing a snapshot of signals from all satellites in view of a constellation such as the Global Positioning System. The method is capable of dealing with weak signals and requires minimal use of processing time and use of communications resources. Each satellite transmits a signal that consists of a series of frames of a pseudo-noise sequence whereupon is superimposed a satellite data message. The total signal received from the satellite network by the mobile unit is arranged as columns of a matrix and is processed coherently to provide estimated pseudo-ranges and estimated rates of change of pseudo-ranges for in-view satellites. The coherent processing includes performing an initial orthogonal transform on the rows of the matrix and, uses prior knowledge to select that portion of the matrix containing a particular satellite signal for further processing. A reference vector, containing the respective pseudo-noise sequence, is prepared for each satellite in view by cyclically transposing the elements thereof to match the phase of the same sequence in the received signal from the satellite and multiplying the elements of the vector by Doppler compensation factors. Then, for each satellite in view, the columns of the selected matrix portion are convolved with the prepared reference vector for that satellite. Prior knowledge is again used to refine the selection and the satellite data message is demodulated to enable precise location of the start of a pseudo-noise sequence frame and the Doppler shift of the received signal. The process is repeated for at east four satellites in view to determine location and velocity of the receiving station by methods well known in the art.

Claims

1. A method for fast processing of electronic signals for determining a location of a mobile receiver comprising the steps of:

a) Providing a satellite-based positioning system including a plurality of satellites, each satellite transmitting a signal including a plurality of blocks, each block including a plurality of frames of a known pseudo-noise sequence unique to each satellite, each block being multiplied by a bit of a data sequence, the signal being frequency-shifted relative to a nominal frequency;

b) Receiving, by the mobile receiver, a snapshot of said signals of all said satellites in view and arranging said snapshot in a two-dimensional matrix; and

c) Mathematically windowing and transforming said matrix into a frequency domain.

2. The method of claim 1, further comprising, for each said satellite in view, the steps of:

i) Selecting a portion of said mathematically windowed and transformed matrix containing a preponderance of said signal of said each satellite according to an expected Doppler shift of said signal, said portion being a matrix having as many rows as said mathematically windowed and transformed matrix and, at most, as many columns as said mathematically windowed and transformed matrix;

ii) Preparing a reference vector corresponding to said each satellite, said vector being a mathematically transformed copy of a said frame of said known pseudo-noise sequence of said each satellite and having a number of elements equal to a number of elements of said number of rows of said mathematically windowed and transformed matrix;

iii) Multiplying respective elements in each said column of said selected portion of said mathematically windowed and transformed matrix by respective said elements of said reference vector, thereby producing an adjusted matrix; and

iv) Performing an inverse discrete orthogonal transform on each row of said adjusted matrix.

3. The method of claim 2, further comprising the steps of:

v) Isolating a desired signal event by demodulating said data sequence of said each satellite; and

vi) Deducing a time of arrival of said signal event and a Doppler shift of the signal of said each satellite.

4. The method of claim 2, wherein the number of said satellites in view is at least four.

5. The method of claim 3, comprising the further step of providing said deduced times of arrival and said Doppler shifts for all said satellites in view for calculation of a location and a velocity of said mobile receiver.

6. The method of claim 5, comprising the further step of providing an ancillary communications network wherewith the mobile receiver communicates, said ancillary communications network transmitting a synchronization signal at a respective transmission frequency.

7. The method of claim 1, wherein said arranging of said snapshot in a two-dimensional matrix includes the steps of:

i) digitizing said snapshot thereby producing a digitized signal including a plurality of digitized elements; and

ii) arranging said digitized elements consecutively by column in said two-dimensional matrix, each said column;

A) containing a sub-plurality of elements; and

B) corresponding to an integral number of frames of said pseudo-noise sequence.

8. The method of claim 7, wherein said sub-plurality of elements includes a number of said elements equal to a power of two.

9. The method of claim 7, wherein said integral number is one.

10. The method of claim 7, wherein said elements are complex numbers.

11. The method of claim 10, wherein components of said complex numbers are stored as two-bit numbers.

12. The method of claim 10, wherein components of said complex numbers are stored as one-bit number.

13. The method of claim 1, wherein said mathematical windowing and transformation includes the steps of:

i) applying a window function to each row of said matrix;

ii) performing a two-dimensional discrete orthogonal transform on said matrix; and

iii) overwriting original said matrix by said transformed said matrix.

14. The method of claim 13, wherein said window function is a Hamming window.

15. The method of claim 13, wherein said orthogonal transform is a Fourier transform.

16. The method of claim 2, wherein said selecting of said portion of said mathematically transformed matrix containing a preponderance of said signal of said each satellite is based on:

i) information related to said data sequence including;

A) a satellite transmission schedule; and

B) trajectory parameters of said each satellite; and

ii) an approximate location of the mobile receiver.

17. The method of claim 16, wherein said data sequence is obtained from a transmission by a corresponding said each satellite.

18. The method of claim 16, wherein said trajectory parameters are stored in and retrieved from a data bank.

19. The method of claim 18, wherein said data bank is located with the mobile receiver.

20. The method of claim 18, wherein said data bank is located at an area server and said retrieval is on-demand therefrom via said ancillary communications network.

21. The method of claim 2, wherein said mathematical transformation of said frame of said pseudo-noise sequence includes the steps of:

A) mathematically resampling said frame to consist of a number of elements equal to a number of said sub-plurality of elements in a said column of said adjusted matrix;

B) cyclically shifting said elements of said resampled frame to be in phase with said pseudo-noise sequence received from said each satellite in accordance with;

I) an estimate of an expected time of arrival of said pseudo-noise sequence; and

II) a drift of a local clock in the mobile receiver;

C) multiplying each said element of said cyclically shifted frame by a respective Doppler compensation factor;

D) transforming said Doppler-compensated frame by means of a discrete orthogonal transform; and

E) replacing each element of said transformed frame by a complex conjugate thereof.

22. The method of claim 21, wherein said time of arrival is estimated from:

a) Information related to said data sequence including;

i) a satellite transmission schedule; and

ii) trajectory parameters of said each satellite; and

b) Knowledge of an approximate location of the mobile receiver.

23. The method of claim 21, wherein said drift of said local clock is measured by the steps of:

a) Providing an ancillary communications network wherewith the mobile receiver communicates, said ancillary communications network transmitting a synchronization signal at a respective transmission frequency, and

b) Calibrating said local clock against said synchronization signal.

24. The method of claim 21, wherein said drift of said local clock is measured by the steps of:

a) Providing an ancillary communications network wherewith the mobile receiver communicates, said ancillary communications network transmitting a synchronization signal at a respective transmission frequency, and

b) Calibrating said local clock against said transmission frequency.

25. The method of claim 21, wherein said drift of said local clock is measured by comparison with said transmission frequency of said each satellite.

26. The method of claim 21, wherein said Doppler compensation factors are based on a likely frequency shift of said signal of said each satellite due to a Doppler effect arising from relative motion of said satellite with respect to the mobile receiver.

27. The method of claim 26, wherein said likely frequency shift is estimated from:

a) Information related to said data sequence including;

i) a satellite transmission schedule; and

ii) trajectory parameters of said each satellite; and

b) An approximate location and velocity of the mobile receiver.

28. The method of claim 21, wherein said orthogonal transform is a Fourier transform.

29. The method of claim 3, wherein said isolating of said desired signal event includes the steps of:

i) selecting a contiguous sub-set of said rows of said inverse-transformed adjusted matrix in accordance with an estimate of a likely presence therein of a preponderance of said signal event, thereby providing a reduced matrix having, at most, as many rows as said inverse-transformed adjusted matrix and as many columns as said inverse-transformed adjusted matrix;

ii) performing an inverse discrete orthogonal transform on each column of said reduced matrix;

iii) multiplying elements of columns of said inverted, reduced matrix by respective expected said data sequence bits; and

iv) performing a discrete orthogonal transform on each column of said multiplied, inverted, reduced matrix, resulting in a transformed, reduced matrix.

30. The method of claim 29, wherein said estimate is derived from:

a) Knowledge of said data sequence;

b) A satellite transmission schedule for said data sequence;

c) Trajectory parameters of said each satellite; and

d) An approximate location of the mobile receiver.

31. The method of claim 29, wherein said signal event is a start of a said frame of a said pseudo-noise sequence.

32. The method of claim 29, wherein said expected data sequence bits are inferred from:

a) Knowledge of said data sequence;

b) A satellite transmission schedule for said data sequence;

c) Trajectory parameters of said each satellite; and

d) An approximate location of the mobile receiver.

33. The method of claim 29, wherein said expected data sequence bits are hypothesized.

34. The method of claim 29, wherein said orthogonal transform is a Fourier transform.

35. The method of claim 3, wherein said deducing of said time of arrival of said signal event and said Doppler shift of said signal of said each satellite is effected by steps including:

i) identifying at least one peak in said transformed, reduced matrix, each said at least one peak having a row coordinate and a column coordinate and an absolute magnitude, said row coordinate of said local maximum corresponding to a pseudo-range of said each satellite and said column coordinate of said local maximum corresponding to the rate of change thereof; and

ii) if a plurality of said peaks are identified, interpolating among said peaks to refine said identification of said row coordinate and said column coordinate of said local maximum.

36. The method of claim 35, wherein said interpolation is effected by two-dimensional curve fitting.

37. The method of claim 35, wherein said interpolation is effected by one-dimensional curve-fitting in each of a row and a column direction.