Efficient algorithm for processing GPS signals

Details Efficient algorithm for processing GPS signals Efficient algorithm for processing GPS signals

2003-06-16

2004-06-15

Phan, Dao (Department: 3662)

Communications: directive radio wave systems and devices (e.g.,

Directive

Including a satellite

C342S357490, C701S213000

Reexamination Certificate

active

06750814

ABSTRACT:

FIELD AND BACKGROUND OF THE INVENTION
The present invention relates to the fast processing of electronic signals and, more particularly, to the fast processing of signals in a positioning system based on a satellite network such as the Global Positioning System (GPS).
The Global Positioning System is a constellation of Earth-orbiting satellites that transmit standard signals that can be used to establish the location and velocity of a user equipped with a suitable GPS receiver. For civilian applications, the basic signals are “C/A codes” or Gold Codes, pseudo-random noise (PN) sequences, transmitted as repeated frames of 1023 chips at a chip rate of 1023 chips/ms (≡one frame per millisecond). Each satellite is assigned a unique PN sequence, the PN sequences of the various satellites being mutually orthogonal.
Superimposed on the PN sequence of each GPS satellite is a continuously repeating Satellite Data Message (SDM), of 30 seconds duration, transmitted at a rate of 50 bits per second. The complete SDM is therefore 1500 bits long. Each bit (+1 or −1) of the SDM is modulated onto the satellite's signal by multiplying 20 consecutive frames of the PN sequence by that bit. The first 900 bits of the SDM include the satellite ephemeris and time model for the respective satellite. The remaining 600 bits of the SDM include a portion of the GPS almanac, which is a 15,000 bit block of coarse ephemeris and time model data for the entire GPS system. In addition, bits
1
-
8
, bits
301
-
308
, bits
601
-
608
, bits
901
-
908
and bits
1201
-
1208
of every SDM are identical 8-bit (160 millisecond) headers that are invariant in time and that are identical in all the GPS satellites. Bits
31
-
60
, bits
331
-
360
, bits
631
-
660
, bits
931
-
960
and bits
1231
-
1260
of every SDM are 30-bit (600 millisecond) hand-over words that are time-variant (these hand-over words include representations of the time of the week), but are, like the headers, identical in all the GPS satellites.
A GPS mobile unit receives a signal as a function of time, t, of the form:
G
⁡
(
t
)
=
∑
j
⁢
G
j
⁡
(
t
)
where:
G
j
(
t
)=
K
j
D
j
(
t−&tgr;
j
)
g
j
(
t−&tgr;
j
) exp [
i
&ohgr;(
t−&tgr;
j
)],
is the signal received from satellite j,j being an index that denotes a single satellite of those that are visible; i is the square root of −1; &tgr;
j
is the true one-way propagation time of radio waves from satellite j to the mobile unit; K
j
is an amplitude factor that depends on the true range R
j
=c&tgr;
j
to satellite j at time t, and on the GPS antenna-gain pattern; D
j
(t−&tgr;
j
) is the SDM of satellite j at time (t−&tgr;
j
); g
j
(t−&tgr;
j
) is the PN sequence of satellite j at time (t−&tgr;
j
); and exp [i&ohgr;
j
(t−&tgr;
j
)] is a frequency factor whose Doppler shift depends on the radial component of the velocity of satellite j relative to the mobile unit, on the bias of the mobile unit's internal clock, and on other imperfections in the mobile unit.
Conventionally, a GPS receiver acquires and tracks the signals from at least four GPS satellites by correlating the received signal with the satellites' respective PN sequences and locking on to the correlation peaks. Once a satellite is acquired and tracked, the GPS receiver decodes the ephemeris and time model thereof, from the respective SDM. This is repeated for each required satellite: These models include sufficient ephemeris data to enable the GPS receiver to compute the satellites′ positions. The correlation peaks obtained during the continued tracking of the satellites provide measured times of arrival of these PN sequence frames. The differences between an arbitrary reference time and measured times of arrival, multiplied by the speed of light, are pseudo-ranges &rgr;
j
from the satellites to the GPS receiver. Typically, the reference time is the time at which the satellites commenced transmission of their respective PN sequences, as measured by the GPS receiver clock, which in general is offset from the GPS system clock by an unknown time offset. A pseudo-range, &rgr;, is related to the true range, R, of the respective satellite by &rgr;=R+c
b
, where the range offset c
b
is the time offset, T
0
, of the GPS receiver relative to GPS system time, multiplied by the speed of light c: c
b
=T
0
c. From these pseudo-ranges, and from the known positions of the satellites as functions of time, the position of the GPS receiver is calculated by triangulation. Pseudo-ranges to at least four satellites are needed to solve at least four simultaneous equations of the form:
 |
{right arrow over (s)}−{right arrow over (r)}|=&rgr;−c
b
where {right arrow over (s)} is the position vector of a satellite and {right arrow over (r)}=(x,y,z) is the position vector of the GPS receiver, for the three unknown Cartesian coordinates x, y, z of the GPS receiver and for c
b
. The satellites are sufficiently far from the GPS receiver that these equations can be linearized in x, y, and z with no loss of accuracy.
In similar fashion, measurement of the Doppler shifts of the received satellite signals enables calculation of the velocity of the GPS receiver. At least four simultaneous equations of the form:
({right arrow over (&ngr;)}
s
−{right arrow over (&ngr;)})·
LOS
=&ngr;
r
−c
d
where {right arrow over (&ngr;)}
s
is actual satellite velocity, {right arrow over (&ngr;)} is velocity of the mobile unit,
LOS
is a unit vector denoting the line of sight to an observed GPS satellite, and c
d
is a clock drift correction. Relative speed with respect to a satellite is calculated from a measurement of the respective Doppler shift in the signal from that satellite.
A number of patents (e.g. U.S. Pat. No. 5,781,156) describe GPS receivers operating in a snapshot method. Such receivers record a sample of the signal from GPS satellites and process the recording later, off-line. This enables high reception sensitivity, as well as low consumption of battery power and small physical size. Signal processing must, however, be highly efficient in order to save processing time. Some of these receivers achieve a significant saving in processing time by transferring ancillary data for processing elsewhere through a communications network (cellular or other), in which case it is still important to reduce the amount of ancillary data sent, in order to save on communications resources.
Several prior art methods are known for increasing the efficiency with which a GPS receiver establishes its position and for reducing the power requirements of a GPS receiver. The SDM is 30 seconds long so, even under ideal reception conditions with parallel processing of the signals from all the satellites in view, it necessarily takes more than 30 seconds to get a GPS position fix. Prior knowledge of the SDM can reduce this time to less than 10 seconds. Schuchman et al., in U.S. Pat. No. 5,365,450, which is incorporated by reference for all purposes as if fully set forth herein, teach the transmitting of the SDMs to a GPS receiver integrated into a mobile unit, such as a cellular telephone or other wireless communications network receiver, by a base station of the network via the control channel of the network.
Krasner, in U.S. Pat. No. 5,663,734, which is incorporated by reference for all purposes as if fully set forth herein, teaches a GPS receiver for a mobile unit in which, as in the GPS receiver of Schuchman et al., the SDM is obtained via a wireless link to a base station, but then, instead of processing GPS signals in real time, the GPS receiver stores up to one second's worth of signals (1000 PN sequence frames per satellite), along with the initial time of arrival (TOA) of the signals, and processes the stored signals. Groups of 5 to 10 frames each are summed and correlated with the PN sequences of satellites expected to be in view, and the resulting correlation functions

Affiliated with

Also associated with

Rating

Efficient algorithm for processing GPS signals does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Efficient algorithm for processing GPS signals, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient algorithm for processing GPS signals will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3352179