|
Software Patent Abstract
A real-time software receiver that executes on a general purpose
processor. The software receiver includes data acquisition and correlator
modules that perform, in place of hardware correlation, baseband
mixing and PRN code correlation using bit-wise parallelism.
Software Patent Claims
What is claimed is:
1. A method for computing prompt and early-minus-late in-phase
and quadrature summed accumulations for a plurality of signals from
a plurality of channels comprising the steps of: representing a
carrier replica signal from the at least one channel from the plurality
of channels as a carrier replica sign and a carrier replica magnitude;
representing signal data from the at least one channel of the plurality
of channels as at least one signal word; computing a baseband mixed
sign as a function of the carrier replica sign and the at least
one signal word; computing a baseband mixed magnitude as a function
of the carrier replica magnitude; selecting a pseudo-random number
(PRN) code having a prompt PRN code and an early-minus-late PRN
code; representing the prompt PRN code as a prompt PRN code sign;
computing a fully mixed prompt integrand sign as a function of the
baseband mixed sign and the prompt PRN code sign; representing the
early-minus-late PRN code as an early-minus-late PRN code sign and
an early-minus-late PRN code zero mask; computing a fully mixed
early-minus-late integrand sign as a function of the baseband mixed
sign and the early-minus-late PRN code sign; computing at least
one set of prompt integrand value words as a function of the fully
mixed prompt integrand sign and the baseband mixed magnitude; computing
at least one set of early-minus-late integrand value words as a
function of the fully mixed early-minus-late integrand sign, the
baseband mixed magnitude, and early-minus-late PRN code zero mask;
computing prompt in-phase and quadrature summed accumulations for
the plurality of channels for an accumulation interval as functions
of the number of significant bits in the at least one set of prompt
integrand value words and as functions of the values associated
with the at least one set of prompt integrand value words; and computing
early-minus-late in-phase and quadrature summed accumulations for
the plurality of channels as functions of the number of significant
bits in the at least one set of early-minus-late integrand value
words and as functions of the values associated with the at least
one set of early-minus-late integrand value words; and supplying
the prompt and early-minus-late in-phase and quadrature summed accumulations
to a software receiver to compute navigation data.
2. The method as in claim 1 further comprising the step of: retrieving
the carrier replica signal from a carrier replica table, the carrier
replica table representing a coarse grid of frequencies.
3. The method as in claim 1 further comprising the steps of: representing
the signal word from the at least one channel as a signal sign and
a signal magnitude; and computing at least one baseband mixed magnitude
as a function of the carrier replica magnitude and the signal magnitude.
4. The method as in claim 3 further comprising the step of: retrieving
the carrier replica signal from a carrier replica table, the carrier
replica table representing a coarse grid of frequencies.
5. The method as in claim 1 further comprising the steps of: receiving
at least one radio frequency (RE) signal from the at least one channel
from the plurality of channels; digitizing the at least one RE signal;
and mixing the at least one RE signal to form signal data using
bit-wise parallelism.
6. The method as in claim 5 wherein the at least one RE signal
is a multi-bit signal.
7. The method as in claim 5 further comprising the steps of: down-convening
the at least one RE signal to an intermediate frequency; and digitizing
the intermediate frequency.
8. The method as in claim 5 further comprising the step of: receiving
the at least one RE signal from a global positional source.
9. The method as in claim 1 wherein said step of computing a fully
mixed prompt integrand sign is performed using bit-wise parallelism.
10. The method as in claim 1 wherein said step of computing fully
mixed early-minus-late integrand sign and is performed using bit-wise
parallelism.
11. The method as in claim 1 further comprising the step of: rotating
the in-phase and quadrature summed accumulations to correct for
effects of frequency and phase granularity of the signal data.
12. The method as in claim 1 further comprising the step of: computing
navigation data using the prompt in-phase and quadrature summed
accumulations and the early-minus-late in-phase and quadrature summed
accumulations.
13. The method as in claim 1 further comprising the step of retrieving
the carrier replica signal from a carrier replica table, the carrier
replica table representing a coarse grid of frequencies.
14. The method as in claim 1 wherein said step of computing a baseband
mixed magnitude comprises the steps of: representing the at least
one signal word as a signal sign and a signal magnitude; and computing
the basehand mixed magnitude as a function of the carrier replica
magnitude and the signal magnitude.
15. The method as in claim 1 further comprising the step of: generating
the PRN code using the bit-wise parallelism according to the steps
of: formulating a tabulated function for use in translating code
chip and timing values into PRN code using the bit-wise parallelism;
generating at least one prompt PRN code in real-time; choosing at
least one chip value from the at least one prompt PRN code, the
at least one chip value corresponding to at least one data interval
that contains at least one sample of a data word, the at least one
chip value having a known timing relative to the at least one data
interval; transforming the known timing into a time grid index;
and translating the at least one chip value and the time grid index
during the at least one data interval into the PRN code using the
bit-wise parallelism for the at least one data interval, said step
of translating resulting from the use of the tabulated function.
16. The method as in claim 15 further comprising the step of: computing
the time grid index as a function of a time offset index and an
auxiliary table index.
17. The method as in claim 15 further comprising the step of: computing
the time grid index iteratively as a function of a previously-computed
time grid index, the at least one prompt PRN code, and the timing
values associated with the at least one prompt PRN code.
18. A node in a computer network capable of carrying out the method
according to claim 1.
19. A communications network comprising at least one node for carrying
out the method according to claim 1.
20. The method of claim 1 wherein said computing prompt and early-minus-late
in-phase and quadrature summed accumulations for a plurality of
signals from a plurality of channels is performed by a computer
system receiving electromagnetic signals traveling over a computer
network carrying information capable of causing a computer system
in the network to perform said computing of prompt and earl-minus-late
in-phase and quadrature summed accumulations for a plurality of
signals from a plurality of channels.
21. A computer readable medium having instructions embodied therein
for the practice of the method of claim 1.
22. A method for generating over-sampled prompt and early-minus-late
pseudo-random number (PRN) codes in a bit-wise parallel format comprising
the steps of: formulating a tabulated function for use in translating
code chip and timing information into over-sampled prompt and early-minus-late
PRN code in the bit-wise parallel format; generating at least one
prompt PRN code in real-time; choosing at least one chip value from
the at least one prompt PRN code, the at least one chip value corresponding
to at least one data interval that contains at least one sample
of a data word, the at least one chip value having a known timing
relative to the at least one data interval; transforming the relative
timing into a time grid index; and translating the at least one
chip value and the time grid index during the at least one data
interval into the over-sampled prompt and early-minus-late PRN codes
in bit-wise parallel format for the at least one data interval,
said step of translating resulting from the use of the tabulated
function; and distinguishing a signal and computing its PRN code
phase by correlating the signal with the over-sampled prompt and
early-minus-late PRN codes in bit-wise parallel format.
23. The method as in claim 22 further comprising the step of: computing
the time grid index as a function of a time offset index and an
auxiliary table index.
24. The method as in claim 22 further comprising the step of: computing
the time grid index iteratively as a function of a previously-computed
time grid index, the at least one prompt PRN code, and timing values
associated with the at least one prompt PRN code.
25. A method for using over-sampled prompt and early-minus-late
pseudo-random number (PRN) code replica data words that are stored
in a bit-wise parallel representation in a pre-computed table consisting
of the steps of: selecting the over-sampled prompt and early-minus-late
PRN code based on over-sampled prompt and early-minus-late PRN code
start time as measured relative to an RF data sample time, said
step of selecting substantially matching the midpoint of the over-sampled
prompt and early-minus-late PRN code with a desired PRN code midpoint;
and bit-shifting the over-sampled prompt and early-minus-late PRN
code data words, said step of bit-shifting insuring that the over-sampled
prompt and early-minus-late PRN code start time corresponds with
a pre-selected sample interval; and distinguishing a signal associated
with the RF data and computing its PRN code phase based on a correlation
between the signal and the over-sampled prompt and early-minus-late
PRN code.
26. The method of claim 1 further comprising the step of: tracking
the phase of the PRN code to track the timing of its chips including
the steps of: latching PRN code phase, carrier phase, epoch counters,
and carrier frequencies at a pre-specified time; computing a pseudo
range using the PRN code phase and the epoch counters; tracking
and updating the PRN code phase and the carrier phase by estimating
code chipping rate and carrier Doppler shift inputs; and computing
the PRN code phase at the pre-specified time as a function of the
updated code chipping rate and the pre-specified time.
Mobile Phone Patent Description
BACKGROUND OF THE INVENTION
This invention relates generally to software radio receivers, and
more specifically to a software receiver for positioning systems.
A typical positioning system receiver, such as is used in the Global
Positioning System (GPS), includes an antenna, a radio frequency
(RF) section, a correlator, a signal tracking and demodulation component,
and a component to compute the navigation solution. The antenna,
which is possibly followed by a pre-amplifier, receives L-band GPS
signals. The RF section filters and down converts the GHz GPS signal
to an intermediate frequency in the MHz range. The RF section also
digitizes the signal. The correlator separates the down-converted
signal into different channels (ten or more in modern receivers)
allocated to each satellite. For each satellite, the correlator
mixes the Doppler-shifted intermediate frequency signal to baseband
by correlating it with a local copy of the carrier replica signal
and it distinguishes the particular satellite by correlating the
signal with a pseudo-random number (PRN) code. Software routines
cause the carrier replica and PRN replica signals to track the actual
received signal, extract the navigation message, and compute the
navigation solution.
Baseband mixing is a multiplication of an input signal by a complex
exponential where the frequency of the complex exponential approximately
matches that of the input signal. The resultant signal is centered
at baseband. A complex signal can be broken down into cosine and
sine signal components, resulting in separate in-phase and quadrature
components. The frequency of the baseband mixed signal must be controllable
to within a few millihertz in the case of a phase-locked loop for
use in a precision navigation system, and the baseband mixed signal
must have a continuously varying phase. In a hardware correlator,
local oscillators generate cosine and sine signal components that
have precise frequency control and a continuous phase. Generating
cosine and sine signal components on the fly with the correct frequency
and phase is too time consuming to be feasible for a software correlator.
Instead, the software correlator generates cosine and sine signal
components on a grid of frequencies off-line. These signal components
must be stored on a time grid of points sampled at the RF front-end
sampling frequency, for example, at 5.714 MHz for one particular
RF front-end hardware configuration, and the signals must last for
a typical accumulation period, e.g., for a 0.001 second coarse/acquisition
(C/A) PRN code period when working with GPS L1 civilian signals.
It takes tens of gigabytes of memory or more in order to brute-force
store all frequencies on a one mHz grid ranging from -10 KHz to
+10 KHz, which is the needed frequency range when tracking GPS satellites
from a terrestrial receiver, and additional storage is required
to store a grid of possible starting phases at each frequency point.
PRN code mixing is a multiplication of a baseband mixed signal
by a prompt +1/-1 PRN code or by a +2/0/-2 early-minus-late PRN
code, where the code timing and frequency approximately match that
of the input signal. The resultant signal is a constant in the case
of prompt PRN code mixing, and an approximately linear function
of the code timing error in the case of early-minus-late mixing.
A receiver accumulates both of these correlation outputs. The magnitude
of the prompt accumulation indicates signal strength and whether
a signal has been detected, and its in-phase (real) and quadrature
(imaginary) components are used to measure carrier phase and Doppler
shift. The magnitude of the early-minus-late accumulation measures
the code timing error; it will be zero when the timing error is
zero.
The code phase of the baseband mixing signal must be controllable
to within a percent or less of a PRN code chip for use in a precision
navigation system. In a hardware correlator, local oscillators generate
the prompt and early-minus-late PRN code replicas. A software correlator
can either compute and store PRN code replicas, or compute them
in real-time.
The current Global Positioning System is slated to realize expanded
capabilities that include new civilian codes on the L2 frequency,
a new L5 frequency, and new codes (M-code, CL and CM codes) on the
L2 frequency. Some of these upgrades are slated to start within
one to three years. A hardware correlator requires hardware modifications
in order to use these new signals. In the near term, a receiver
designer will be faced with a complex trade-off in order to decide
whether the extra complexity is worth the improved performance that
will accrue only very slowly as new GPS satellites replace older
models. One way to avoid the complex trade-off is to use a software
receiver that can receive and process new signals without the need
for a new correlator chip set.
A software receiver is flexible because its software components
can be easily modified. One application of a software receiver is
to merge together numerous devices that use wireless digital communication
protocols to form a single device. For example, a cell phone, GPS
receiver, and Personal Data Assistant (PDA) could become a single
device that plays the role of all three. Another use of a software
receiver is to shorten development and to-market times for new wireless
devices. For example, as new frequencies and codes are added to
GPS, a software receiver having a software correlator simply needs
to be reprogrammed, while a hardware approach would require a brand
new correlator chip design. New PRN codes can be used simply by
making software changes. Thus, software receiver technology lessens
the risks involved for designers during the period of transition
to the new signals. Furthermore, a software receiver could be reprogrammed
to use the Galileo system (European GPS) or GLONASS (Russian GPS).
In the recent past, GPS software receivers have been developed
that either post-process stored signals or operate in real-time.
Previous real-time software receivers function with a limited number
of channels (4-6) or require high-end computer speeds or digital
signal processor (DSP) chips such as are disclosed in Real-Time
GPS Software Radio Receiver, Akos et al., ION NTM 2001, 22-24 Jan.
2001, Long Beach, Calif., pp. 809-816 (Akos 2001a), and Global Positioning
System Software Receiver (gpSrx) Implementation in Low Cost/Power
Programmable Processors, Akos et al., ION GPS 2001, 11-14 Sep. 2001,
Salt Lake City, Utah, pp. 2851-2858, both incorporated herein in
their entireties by reference.
Therefore, it is an object of the present invention to create a
software receiver that operates in real-time and is not restricted
to a severely limited number of channels or to a very fast processor.
Another object of the present invention is to minimize the number
of sine and cosine signal components that must be stored.
A further object of the present invention is to process incoming
signals through bit-wise parallelism.
A still further object of the present invention is to process over-sampled
signals by use of bit-wise parallelism.
A still further object of the present invention is to use very
long over-sampled PRN codes efficiently in a bit-wise parallel software
receiver.
SUMMARY OF THE INVENTION
The objects set forth above as well as further and other objects
are addressed by the present invention. The solutions and advantages
of the present invention are achieved by the illustrative embodiment
described herein below.
The software receiver system and method of the present invention
enable the efficient execution of a set of algorithms, that perform
software correlation on data sampled from incoming channels, on
a general purpose processor. The system and method of the present
invention provide for either PRN code storage or computation of
PRN codes in real-time. PRN code storage is appropriate for PRN
codes that have short periods, such as the GPS coarse/acquisition
codes, which are 1023 chips long. In this case, the system and method
of the present invention pre-compute over-sampled replicas of entire
PRN code periods and store them for orderly and efficient retrieval,
such as in a table. This table can include a selection of code start
times as measured relative to the sample times at which RF data
are available from the receiver front end. There is a separate table
for each unique PRN code.
The system and method of the present invention can also generate
over-sampled versions of the prompt and early-minus-late PRN codes
in real-time through use of an over-sampling function described
herein. The values of the over-sampling function can be located
in a specially designed table that can be generic across PRN codes.
The length of the specially designed table can be independent of
the length of the PRN code whose replica is being used to process
a given received signal. The system and method of the present invention
include techniques for efficiently calculating indices into the
specially designed table that enable rapid, real-time table look-up.
The system of the present invention includes a software correlator
that can mix the received signal to baseband, compute baseband/PRN
correlations through bit-wise parallelism and look-up tables using
either the tabulated or real-time-generated PRN codes, and compute
accumulations through bit-wise parallelism and processor instructions
or look-up tables. Bit-wise parallelism allows the processing of
multiple data samples simultaneously as the multiple bits of a given
word of computer data. For example, for 32-bit words, the software
correlator can process up to 32 samples at a time. Bit-wise parallelism
can optimally operate when each signal in question can be represented
by only a few bits, which is normally the case in RF digital signal
processing of navigation signals.
The bit-wise parallel operations of the present invention can save
computation time in comparison to integer mathematical correlation
operations. If, for example, four accumulations are required per
sample, integer mathematics requires six multiplications and four
additions per sample (except for the last sample). At a sampling
rate of, for example, 5.714 MHz this translates into 57,140 integer
operations per PRN code period. In the illustrative embodiment,
33,500 bit-wise parallel operations are necessary per PRN code period
when the RF signal has a 2-bit representation. This operation count
is further reduced to approximately 16,750 bit-wise parallel operations
per PRN code period when the RF signal has a 1-bit representation.
Thus, there can be a savings of almost a factor of two to almost
a factor of four in the operation count.
The system and method of the present invention also include a table
of pre-computed baseband mixing sine waves, algorithms that can
produce correlation accumulation outputs that are equivalent to
what would be produced by a continuously variable sine wave, and
a method of use of the table and algorithms. Thus, in the present
invention, a relatively small set of sine wave values need to be
pre-computed and saved, which can conserve computer memory and processing
time.
The present invention also includes a system and method for tracking
the phase of PRN code replicas in software in order to track the
timing of any given "chip" of the PRN code replica as
measured with respect to a pre-specified set of sample times at
which the basic raw data comes out of the RF front end (a chip is
an element of a PRN code). The PRN code phase is kept track of via
a variable for each channel, that indicates the PRN code start time
with respect to the RF sample times. The system and method of the
present invention allow for the synchronization of the measurements
of PRN code phase, carrier phase, and carrier frequency for each
satellite relative to these sample times.
The method for tracking the phase of each PRN code replica and
the phase of each carrier replica includes the steps of latching
all the C/A code phases, carrier phases, epoch counters, and carrier
frequencies for each satellite at a pre-specified time, and computing
the pseudo range to each satellite using the C/A code phase and
epoch counters. The method also includes the step of tracking and
updating code and carrier phases by estimating code chipping rate
and carrier Doppler shift inputs. The method further includes the
step of computing the code phase at the pre-specified time for each
satellite as a function of the updated code chipping rate and the
pre-specified time. The method further includes the step of computing
the carrier phase at the pre-specified time as a function of the
updated carrier phase, the Doppler shift, and the pre-specified
time. The timing of the PRN code phase (or chip location) is the
most fundamental of GPS measurements for use in navigation data
processing. The monitoring of these times in software allows complete
control of the precision with which they can be measured, and it
allows precise synchronization of these times with the measurement
times of data from other sensors, such as inertial measurement units.
This feature gives an enhanced ability to develop what are known
as deeply coupled systems that must fuse GPS data with data from
other types of sensor systems.
The software correlator of the present invention can advantageously
be easily adapted to accept signals at any frequency, new PRN codes,
or even signals for different types of devices. Thus, the same processing
hardware could use the software correlator to implement such devices
as a GPS receiver, a cell phone, or both. To allow for new codes,
new frequencies, and new types of functionality, small changes can
be made in the software correlator, or different versions of the
software correlator can be run on the same processor. Hardware-correlator-based
receivers of the prior art can deal only with frequencies and PRN
codes that are hard-wired into their designs. Also, the system and
method of the present invention could be implemented within systems
such as GLONASS receivers, cell phones and cell base stations, pagers,
wireless Ethernet (e.g. 802.11.times. standards), Bluetooth.TM.,
Blackberry.RTM. wireless internet devices, and satellite radio/phones
(e.g. INMARSAT.RTM.). In fact, the system and method of the present
invention are applicable to any sort of telecommunication system/device
that uses spread spectrum, code division multiple access (CDMA)
PRN codes for the transmission of information, either wired or wireless.
For a better understanding of the present invention, together with
other and further objects thereof, reference is made to the accompanying
drawings and detailed description. The scope of the present invention
is pointed out in the appended claims.
DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWING
FIG. 1 is a schematic block diagram of the hardware environment
of a typical software receiver;
FIGS. 2A and 2B are schematic diagrams of bit-wise mappings of
signal and carrier replica sign and magnitude bits to computer data
words;
FIG. 2C is a graphic representation of a plot of bit-wise parallel
radio frequency signal and PRN code replica storage and mixing;
FIG. 2D is a graphic representation of a plot of sections of prompt,
early, late, and early-minus-late PRN code signals and 16-bit word
representations of their over-sampled equivalents;
FIGS. 3A and 3B are data flow diagrams illustrating the bit-wise
parallelism process (replicated twice, once for the in-phase carrier
replica and once for the quadrature carrier replica) of the present
invention;
FIG. 3C is a graphic representation of a plot of a prior art optimal
2-bit representation of a sine wave presented to enhance the reader's
understanding of the present invention;
FIGS. 4A and 4B are flowcharts of the method for computing correlation
accumulations through bit-wise parallel computations of the present
invention;
FIG. 5 is a schematic diagram of a look-up table layout as a function
of code time offset and chip bit pattern;
FIG. 6 is a graphic representation of a plot illustrating the timing
relationship between data sample words and the sequence of prompt
code chips that defines an accumulation interval;
FIG. 7 is a flowchart of the method for computing bit-wise parallel
representations of the over-sampled prompt PRN code replica and
the over-sampled early-minus-late PRN code replica for an entire
accumulation interval using the real-time over-sampled PRN code
generation algorithm.
FIG. 8 is a graphic representation of a plot that illustrates the
location in time at which the code phase of each signal is computed;
and
FIGS. 9A and 9B are graphic representations of plots of correlations
of the true sampled code with prompt (FIG. 9A) and early-minus-late
(FIG. 9B) versions of the true and table look-up codes, the latter
being generated by the new real-time over-sampled PRN code generator.
DETAILED DESCRIPTION OF THE INVENTION
The present invention is now described more fully hereinafter with
reference to the accompanying drawings, in which the illustrative
embodiment of the present invention is shown. The following configuration
description is presented for illustrative purposes only. Any computer
configuration satisfying the speed and interface requirements herein
described may be suitable for implementing the system of the present
invention. The equations herein are stated in general terms, but
have parameters that are specific to the GPS L1 C/A signal for illustrative
purposes only. For example, the 0.001 sec. accumulation interval
seen in many of the equations is the nominal C/A code period. Also,
the C/A PRN code of the illustrative embodiment can be replaced
by the PRN code of any other CDMA signaling system.
By way of introductory explanation, RF signal processing equations
and terms are herein provided. The time-domain L1 C/A signal received
from, for example, a satellite, is represented by:
.function..times..times..times..function..times..tau..tau..tau..times..fun-
ction..omega..times..PHI..function. ##EQU00001## where t.sub.i is
the sample time, A.sub.j is the amplitude, D.sub.jk is the navigation
data bit, C.sub.j[t] is the C/A code, .tau..sub.jk and .tau..sub.jk+1
are the start times of the received k.sup.th and k+1.sup.st C/A
code periods, .omega..sub.IF is the intermediate frequency corresponding
to the L1 carrier frequency, .phi..sub.j (t.sub.i) is the carrier
phase perturbation due to accumulated delta range, n.sub.j is the
receiver noise, and the subscript j refers to a particular GPS satellite.
The summation is over all visible GPS satellites. The negative sign
in front of .phi.(t.sub.i) comes from the high-side mixing that
occurs in the RF front-end that has been used in the illustrative
embodiment. The signal in equation (1) is the output of a typical
RF front end.
A GPS receiver works with correlations between the received signal
and a replica of it. The correlations are used to acquire and track
the signal. The replica is composed of two parts, the carrier replica
and the C/A PRN code replica. Two carrier replica signals are used,
an in-phase signal and a quadrature signal. When mixed with the
received signal from the RF front end they form the in-phase and
quadrature baseband mixed signals represented by:
.function..function..times..tau..tau..tau..times..times..omega..times..PHI-
..omega..function..tau..function..function..times..tau..tau..tau..times..t-
imes..omega..times..PHI..omega..function..tau. ##EQU00002## where
equations (2) and (3) apply during the k.sup.th C/A code period.
In these equations {circumflex over (.tau.)}.sub.jk and {circumflex
over (.tau.)}.sub.jk+1 are the receiver's estimates of the start
times of the k.sup.th and k+1.sup.st code periods, {circumflex over
(.phi.)}.sub.jk is the estimated carrier phase at time {circumflex
over (.tau.)}.sub.jk, and {circumflex over (.omega.)}.sub.Doppjk
is the estimated carrier Doppler shift during the k.sup.th code
period.
A typical receiver computes the estimates {circumflex over (.tau.)}.sub.jk,
{circumflex over (.tau.)}.sub.jk+1, {circumflex over (.phi.)}.sub.jk,
and {circumflex over (.omega.)}.sub.Doppjk by various conventional
means that are described in GPS Receivers, A. J. Van Dierendonck,
Global Positioning System: Theory and Applications, B. W. Parkinson
and J. J. Spilker, Jr., Eds., vol. I, American Institute of Aeronautics
and Astronautics, 1996, Chapter 8, pp. 329-406 (Dierendonck), incorporated
herein in its entirety by reference. These include open-loop acquisition
methods and closed-loop signal tracking methods such as a delay-locked
loop to compute {circumflex over (.tau.)}.sub.jk and {circumflex
over (.tau.)}.sub.jk+1 and a phase-locked loop or a frequency-locked
loop to compute {circumflex over (.phi.)}.sub.jk and {circumflex
over (.omega.)}.sub.Dppjk. The software receiver developed herein
uses conventional techniques for forming these estimates.
Both prompt and early-minus-late correlations are needed to track
the carrier frequency, carrier phase, and code phase in a GPS receiver.
A typical receiver uses the PRN code and carrier replicas to compute
the following in-phase and quadrature correlation accumulations:
.function..DELTA..times..function..times..times..times..times..DELTA..tau.-
.tau..tau..times..times..times..times..omega..times. .times. .PHI..omega..function..tau..function..DELTA.
.times..function..times..times..times..times..times..DELTA..tau..tau..tau-
..times..times..times..times..omega..times. .function..PHI..omega..function..tau.
##EQU00003## where i.sub.k is the index of the first RF front-end
sample time that obeys {circumflex over (.tau.)}.sub.jk.ltoreq.t.sub.i.sub.k
and N.sub.k+1 is the total number of samples that obey {circumflex
over (.tau.)}.sub.jk.ltoreq.t.sub.i<{circumflex over (.tau.)}.sub.jk+1.
The time offset .DELTA. causes the replica PRN code to play back
early if it is positive and late if .DELTA. is negative. The prompt
correlations are defined by equations (4) and (5) with .DELTA.=0.
The early-minus-late correlations are I.sub.jk(.DELTA..sub.eml/2)-I.sub.jk(-.DELTA..sub.eml/2)
and Q.sub.jk(.DELTA..sub.eml/2)-Q.sub.jk(-.DELTA..sub.eml/2) where
.DELTA..sub.eml is the spacing between the early and late PRN carrier
replicas. The present invention described herein is an efficient
technique for the receiver to accumulate I.sub.jk and Q.sub.jk in
software.
Referring now to FIG. 1, the operational platform of the software
receiver 10 of the present invention includes an antenna 11, conventional
RF front-end 13, a data acquisition (DAQ) system 17, a microprocessor
16, a software correlator 19, and application-specific code 15.
Conventional RF front-end 13 interfaces with antenna 11 and with
(DAQ) system 17. DAQ system 17 includes a system of shift registers
and a data buffer. Microprocessor 16 executes software correlator
19, which includes a set of specially developed bit-wise parallel
algorithms, and application-specific code 15, such as the GPS navigation
and tracking functions. In the illustrative embodiment, conventional
GPS software functions (signal tracking, data extraction, navigation
solution, etc.) are provided by the MITEL.RTM. GPSArchitect software
ported to RTLINUX.RTM. (see A Coming of Age for GPS: A RTLINUX BASED
GPS RECEIVER, Ledvina et al., Proceedings of the Workshop on Real
Time Operating Systems and Applications and Second Real Time Linux
Workshop (in conjunction with IEEE RTSS 2000) Nov. 27-28, 2000),
but can be provided by any equivalent configuration.
Continuing to refer to FIG. 1, conventional RF front-end 13 can,
for example, be a MITEL.RTM. GP2015 RF front-end, which down converts
the nominal 1.57542 GHz GPS signal 12 to an intermediate frequency
of (88.54/63).times.10.sup.6 Hz.apprxeq.1.4053968254 MHz and then
performs analog-to-digital conversion. The resultant, digitized
signal data 21 has a pre-determined number of bits/sample, such
as two binary bits/sample, a sign bit and a magnitude bit, or one
bit/sample. The shift registers in the DAQ system 17 parallelize
the magnitude and sign data bit streams into separate words, which
the DAQ system 17 reads into the memory of microprocessor 16 using
DMA. To make the process of reading data into the microprocessor
16 more efficient and to prepare for efficient correlation calculations,
DAQ system 17 can read a pre-specified number of bits of buffered
samples, such as thirty-two bits, at a time. The exemplary thirty-two
bits include sixteen sign bits and sixteen magnitude bits.
Referring now to FIGS. 1 and 2A, the shift registers in DAQ system
17 (FIG. 1) buffer signal data 21 (FIGS. 1 and 2A) and pack signal
sign 21A (FIG. 2A) and signal magnitude 21B (FIG. 2A) into separate
words, that represent the integer values .+-.1 and .+-.3 as is shown
in Table 1. In the case of a 1-bit signal, the bit stream representing
the samples is packed into successive words to prepare the signal
for bit-wise parallel processing. DAQ system 17 also provides for
accurate timing by, for example, synchronizing signal sign 21A and
signal magnitude 21B to a (40/7).times.10.sup.6 Hz.apprxeq.5.714
MHz clock signal, which can be, for example, a third output from
conventional RF front-end 13 (FIG. 1). DAQ system 17 can convert
the 5.71424 MHz clock signal down to 357.14 KHz by use of, for example,
a divide-by-16 counter for a 16-bit word, which can provide a signal
indicating when the buffer is full. DAQ system 17 can use any method
for providing a buffer full indication.
TABLE-US-00001 TABLE 1 The sign and magnitude combinations of the
sample RF output of the conventional RF front-end and their corresponding
values. Signal Sign 21A Signal Magnitude 21B RF Signal Value 0 0
-1 0 1 -3 1 0 +1 1 1 +3
With further reference to FIG. 1, in the illustrative embodiment,
the DAQ system 17 can consist of an interface card and driver software
that can be compatible with, for example, a 1.73 GHz AMD ATHLON.RTM.
processor running RTLINUX.RTM., but could be compatible with any
operating system and any processor that can accommodate real-time
operations. The interface card can, for example, be a NATIONAL INSTRUMENTS.RTM.
PCI-DIO-32HS digital I/O card. Pertinent features of this card are
the thirty-two digital input lines, DMA, and availability of a driver
for RTLINUX.RTM., perhaps gotten from the suite of open source drivers
and application interface software for interface cards known as
COMEDI (COntrol and MEasurement and Device Interface). Modifications
to the conventional COMEDI driver for the PCI-DIO-32HS card include
increasing the number of input bits from sixteen to thirty-two,
enabling DMA, and modifying the driver to support continuous interrupt-driven
acquisition.
With still further reference to FIG. 1, microprocessor 16 can be,
for example, a 1.73 GHz AMD ATHLON.TM. processor running the RTLINUX.RTM.
operating system, but any operating system and processor that can
accommodate real-time operations can be used. Low latency interrupt
responsiveness, the ability to execute threads at regular intervals,
with the kernel having a possibility of being the lowest priority
thread, and reliable execution of time-critical code are among features
of an operating system that could enhance the performance of the
system of the present invention. The use of RTLINUX.RTM. is presented
herein for illustrative purposes only.
Continuing to refer to FIG. 1, analogous to a hardware correlator
that takes input directly from the RF front end in serial fashion,
software correlator 19 reads from a shared memory buffer that both
software correlator 19 and DAQ system 17 can access, the former
to read data, and the latter to write data. The shared memory buffer
can be implemented as a DMA memory space and a circular buffer.
In the illustrative embodiment in which the system and method of
the present invention are used in a GPS (or similar) environment,
microprocessor 16 can store the most recent twenty-one milliseconds
of signal data 21 (FIGS. 1 and 2A) in the circular buffer, but could
store more or less. The present invention does not fix the size
of the circular buffer, nor the amount of RF data that can be stored
there. The circular buffer allows the processing of code periods
that start and stop at different times for different satellites
during different iterations of a regularly scheduled program thread.
DMA memory space can be written to directly by DAQ system 17 using
a DAQ software driver, which fills the circular buffer. Communication
between software correlator 19 and application-specific code 15
can be performed using operating system-provided shared memory capability.
For example, the mbuff driver, included with RTLINUX.RTM., can be
used to create and manage this shared memory space. Any memory management
system that accommodates real-time processing can be used. If the
mbuff driver is used, kernel modules can share memory and the kernel
can be restricted from swapping the shared memory space to long-term
storage.
Continuing with the analogy to hardware correlation, and still
referring primarily to FIG. 1, in hardware correlation, the correlator
receives frequency and phase information from tracking and acquisition
loops that are part of application code, and Numerically Controlled
Oscillators (NCOs) generate signals that correspond to the written
frequencies and phases. In contrast, software correlator 19 includes
simulated carrier and code NCOs that receive their frequency commands
from application-specific code 15. Software correlator 19 uses these
frequency commands to reconstruct carrier replica signal 25 (FIG.
3A) and prompt PRN code 29 and early-minus-late PRN code 35 (FIG.
3A) which it mixes with the signal data 21 (FIG. 2A) resulting in
fully mixed prompt integrand 31 and fully mixed early-minus-late
integrand 33 (FIG. 3A).
To further continue the analogy, a hardware correlator generates
in real-time a particular C/A code replica at the correct Doppler
shifted frequency and phase. In contrast, software correlator 19
can generate C/A codes off-line and store them in a memory table,
the pre-computed over-sampled PRN code table 28 (FIG. 3A). The pre-computed
over-sampled PRN code table 28 is used to select PRN codes with
the correct timing relationship to the sample times of signal data
21 (FIG. 3A). The codes are then used to form correlations with
baseband mixed signals 23 (FIG. 3A), the result from which is summed
to produce the standard in-phase and quadrature, summed prompt accumulation
45 (FIG. 3B) and summed early-minus-late accumulation 47 (FIG. 3B)
that are equivalent to what would be produced by a continuously
variable sine wave. These are provided to application-specific code
15, such as conventional GPS software that executes signal tracking
and navigation functions. In a second approach, software correlator
19 can generate the PRN carrier replicas on-line at the code chipping
rate and can use tabulated functions to re-sample the code at the
sample rate of the RF front-end for purposes of calculating accumulations.
Real-time over-sampled PRN code generator 30A (FIG. 3A) is used
in place of pre-computed over-sampled PRN code table 28 (FIG. 3A)
in this latter approach. This latter method can be used with longer
PRN codes, such as the new civilian GPS L2 CL codes.
With still further reference to FIG. 1, since the received L1 raw
signal 12 can have an uncertain carrier phase, software correlator
19 computes both in-phase (I) and quadrature (Q) accumulations,
as defined in equations (4) and (5). Software correlator 19 begins
the accumulation process by using carrier replica signal 25 (FIG.
3A), which it gets from pre-stored carrier replica table 30 (FIG.
3A). The carrier replicas in this table fall on a rough frequency
grid, and they all start with a particular phase, for example a
phase of zero. The baseband mixing process involves selecting a
carrier replica signal 25 (FIG. 3A) from carrier replica table 30
(FIG. 3A) that is at the frequency that is as close to "ideal"
as possible. In the case of a 175 Hz grid spacing, the baseband
mixing process selects a signal that is maximally within .+-.87.5
Hz of the ideal signal. The rough frequency grid can have a spacing
of, for example, 175 Hz but could be larger or smaller depending
on (a) the frequency range needed to cover, for example, .+-.10
Khz, (b) the amount of space available for storing pre-computed
signals, and (c) other design decisions. The pre-computed signals
in carrier replica table 30 (FIG. 3A) each may occupy 180 32-bit
words in order to be guaranteed to cover the full 5,714 RF front-end
samples that occur in one PRN code period for any possible code
period start time within the thirty-two samples of the initial word.
Thus, 180*4=720 bytes could be required for each bit of each pre-computed
carrier replica signal 25 that is stored in the table. The sine
and cosine waves of carrier replica signals 25 (FIG. 3A) each have
2-bit representations, which translates into a storage requirement
of 2880 bytes for the carrier replica signals 25 at a given Doppler
shift. There are 115 Doppler shifts that may be stored in order
to cover the -10 KHz to +10 KHz range with a 175 Hz grid spacing.
This translates into 323 Kbytes of storage for all of the carrier
replica signals 25. This approach avoids the need to pre-compute
sine waves with a prohibitively large number of possible frequencies
and phase offsets and it avoids the need to compute sine waves in
real-time. Instead, the errors created by using pre-defined sine
wave replicas are compensated for by post-processing calculations,
as described below.
In any case, and continuing to refer to FIG. 1, the resulting accumulations
are
.function..DELTA..times..function..times..function..times..DELTA..tau..tau-
..tau..times..function..omega..omega..times..times..function..DELTA..times-
..function..times..function..times..DELTA..tau..tau..tau..times..function.-
.omega..omega..times..times. ##EQU00004## where .omega..sub.gjk
is the grid frequency that is closest to the estimated frequency
{circumflex over (.omega.)}.sub.Doppjk and where t.sub.0gjk is the
time at which this carrier replica signal 25 (FIG. 3A) has zero
carrier phase. Software correlator 19 rotates these accumulations
in order to create accurate approximations of what would have been
computed had the estimated carrier phase time history in equations
(4) and (5) been used: I.sub.jk(.DELTA.)=I.sub.gjk(.DELTA.)cos(.DELTA..phi..sub.avgjk)+Q.sub.gjk-
(.DELTA.)sin(.DELTA..phi..sub.avgjk) (8) Q.sub.jk(.DELTA.)=-I.sub.gjk(.DELTA.)sin(.DELTA..phi..sub.avgjk)+Q.sub.gj-
k(.DELTA.)cos(.DELTA..phi..sub.avgjk) (9) where .DELTA..phi..sub.avgjk
is the average phase difference between the grid carrier phase and
the estimated carrier phase averaged over the accumulation interval:
.DELTA..PHI..omega..function..tau..tau..times..PHI..omega..function..tau..-
tau..omega..times..times. ##EQU00005## Note that equations (8),
(9), and (10) are an illustrative example of how software correlator
(19) can rotate its I and Q accumulations in order to correct for
phase and frequency errors in its table of pre-computed carrier
replica signals. There exist other formulas that yield equivalent
results, and this patent disclosure covers all such techniques.
The validity of equations (8) and (9) is dependent on the assumption
that
.function..times..omega..omega..times..tau..tau..times.<<
##EQU00006## For example, a 175 Hz grid spacing and a nominal C/A
PRN code period of 0.001 sec yields a value on the left-hand side
of inequality (11) of 0.04, which respects the assumed limit.
Note that equations (8) and (9) can be derived from equations (4)
and (5) as follows. First, the carrier phase of the grid signal
in the arguments of the cosine and sine terms of equations (6) and
(7) are added to and subtracted from the arguments of the cosine
and sine terms in equations (4) and (5). Next, trigonometric identities
are used to split the resulting cosine and sine terms into sums
of products of cosine and sine functions. In each product, one of
the terms involves an argument like the arguments in the trigonometric
terms in equations (6) and (7). The other trigonometr terms are
then approximated by either cos(.DELTA..phi..sub.avgjk) or sin(.DELTA..phi..sub.avgjk).
These approximations are valid because of the inequality in equation
(11) and because the average of
.times..omega..omega..function..times..tau..tau. ##EQU00007## over
the accumulation interval is zero.
A decrease in the carrier to noise ratio C/N.sub.0, which characterizes
the receiver's sensitivity, is caused by the use of an inexact baseband
mixing frequency. The worst-case decrease is expressed as a function
of the frequency grid spacing .DELTA.f and is given by
.DELTA..times..times..times..function..function..pi..DELTA..times..times..-
pi..DELTA..times..times. ##EQU00008## where .DELTA.f is in units
of Hz, and T is the integration period. Thus, a .DELTA.f of 175
Hz causes a worst-case C/N.sub.0 loss of 0.11 dB for T=0.001 sec.
Referring now to FIGS. 2A, 2B, and 3A, PRN codes (composed of prompt
PRN codes 29 (FIG. 3A) and early-minus-late PRN codes 35 (FIG. 3A))
are either pre-computed or generated in real-time. Pre-computing
involves, for each satellite, computing an entire PRN code, storing
the PRN code appropriately for easy retrieval, and referencing the
PRN code, possibly by means of indices that are computed based on,
for example, the incoming RF signal data 21 (FIGS. 2A and 3A). Pre-computing
can be most advantageously used when the PRN code is not very long.
Generating PRN codes in real-time can be a more appropriate solution
when the PRN codes are very long (and thus would require an unacceptable
amount of storage), or perhaps when too many PRN codes are required
for the amount of storage available, or for any other reason, but
real-time PRN code generation can entail an additional computational
cost. Both pre-computing and real-time determination of PRN codes
are described herein with respect to a bit-wise parallel implementation.
Continuing to refer primarily to FIGS. 2A, 2B, and 3A, in order
to perform bit-wise parallel operations, software correlator 19
(FIG. 1) stores pre-computed carrier replica sign 25A (FIGS. 2B
and 3A) and carrier replica magnitude 25B (FIGS. 2B and 3A) in data
words. Simple representations of signal data 21 (FIGS. 2A and 3A)
and carrier replica signal 25 (FIGS. 2B and 3A) in terms of one,
two, or more bits are suitable for using bit-wise parallelism to
perform the calculations described herein. Bit-wise parallel operations
work with representations of the data that store successive samples
in successive bits of a word. For example, thirty-two samples (bits)
of the RF front-end output are stored in two N=32-bit words, signal
sign 21A (FIGS. 2A and 3A) and signal magnitude 21B (FIGS. 2A and
3A), or simply a single 32-bit word if signal data 21 consists of
a single data bit. Carrier replica sign 25A (FIGS. 2B and 3A) and
carrier replica magnitude 25B (FIGS. 2B and 3A) are stored, for
example in tables, in separate words, with each 32-bit word storing
thirty-two sign or magnitude bits that tabulate to thirty-two successive
samples of the corresponding cosine or sine wave. Similarly, tables
can store prompt PRN code 29 (FIG. 3A) and early-minus-late PRN
code 35 (FIG. 3A), which are composed of prompt PRN code sign 29A
(FIG. 3A), early-minus-late PRN code sign 35A (FIG. 3A), and early-minus-late
PRN code zero mask 35B (FIG. 3A). The data words that comprise the
bit-wise parallel representations of these three signal types, the
original RF signal data 21 (FIGS. 2A and 3A), the carrier replica
signal 25 (FIG. 2B and FIG. 3A), and the de-spreading prompt PRN
code 29 (FIG. 3A) and early-minus-late PRN code 35 (FIG. 3A), are
the inputs to the calculations of software correlator 19 (FIG. 1).
Further continuing primarily to refer to FIGS. 2A, 2B, and 3A,
many intermediate calculated quantities and at least three types
of intermediate signals are also stored in bit-wise parallel format.
First there are the in-phase and quadrature baseband mixed signals
23 (FIG. 3A), whose 3-bit representations for the illustrative embodiment
are stored as baseband mixed sign 23A (FIG. 3A), baseband mixed
high magnitude 23B (FIG. 3A), and baseband mixed low magnitude 23C
(FIG. 3A). The second bit-wise parallel signal type is the fully
mixed integrand, of which there are four signals: in-phase and quadrature
fully mixed prompt integrand 31 (FIG. 3A) and in-phase and quadrature
fully mixed early-minus-late integrand 33 (FIG. 3A). The former
are stored as 3-bit representations in the illustrative embodiment
as fully mixed prompt integrand sign 31A (FIG. 3A), fully mixed
prompt integrand high magnitude 31B (FIG. 3A), and fully mixed prompt
integrand low magnitude 31C (FIG. 3A). The latter are stored as
3.5-bit representations in the illustrative embodiment as fully
mixed early-minus-late integrand sign 33A (FIG. 3A), fully mixed
early-minus-late integrand high magnitude 33B (FIG. 3A), fully mixed
early-minus-late integrand low magnitude 33C (FIG. 3A), and fully
mixed early-minus-late integrand zero mask 33D (FIG. 3A). This representation
is called a 3.5-bit representation because the sign, high-magnitude,
and low-magnitude bits are ignored if the corresponding zero mask
bit has the value zero. The third bit-wise parallel signal type
is a value word, of which there are two types: prompt integrand
value words 27 (FIG. 3B) and early-minus-late integrand value words
37 (FIG. 3B). Each fully mixed integrand is used to construct value
words, one word for each possible value that the integer integrand
can take on. There are eight possible values for the integrands
of the illustrative embodiment: -1, -2, -3, -6, 1, 2, 3, and 6 for
the in-phase and quadrature fully mixed prompt integrands 31 (FIG.
3A) and -2, -4, -6, -12, 2, 4, 6, and 12 for the in-phase and quadrature
fully mixed early-minus-late integrands 33 (FIG. 3A). Each bit-wise
parallel value word contains a one bit for each sample time when
the integrand value equals the value of the value word, but it contains
a zero bit for all other sample times. The storage of raw data and
intermediate results in bit-wise parallel format allows the EXCLUSIVE
OR operations that are involved in mixing to operate on thirty-two
samples at a time if microprocessor 16 (FIG. 1) has a bit-wise EXCLUSIVE
OR command. Other bit-wise commands are used to perform additional
software correlation operations in parallel on sets of two thirty-two
samples.
At this point, the problem of over-sampling is introduced. Referring
now to FIGS. 2C and 2D, the problem of over-sampling is illustrated
with respect to bit-wise parallelism as follows. There is normally
more than one RF data sample per PRN code chip. The three successive
-1 values 73 (FIG. 2C) at sample times t.sub.1 to t.sub.3 all occur
during the same PRN code chip as do the four successive +1 values
75 (FIG. 2C) at times t.sub.4 through t.sub.7. The difference in
the number of samples for the two code chips arises because the
PRN code chip period is not an integer multiple of the sample period.
Analogously, referring to FIG. 2D, where sample interval .DELTA.t.sub.s
63 is less than actual PRN code chip length .DELTA.t.sub.c 65, over-sampling
is indicated because the RF sampling frequency f.sub.s=1/.DELTA.t.sub.s
is greater than the PRN code chipping frequency f.sub.c=1/.DELTA.t.sub.c.
PRN codes for CDMA signaling are sequences of +1 and -1 values,
the elements of which are chips. Over the time intervals of interest,
a carrier replica progresses through its chips at a constant chipping
rate of f.sub.c=1/.DELTA.t.sub.c chips/second. The time interval
.DELTA.t.sub.c is the actual PRN code chip length 65 (FIG. 2D).
Software correlator 19 (FIG. 1) normally receives PRN code, and
attempts to align it with the prompt replica version of the code,
prompt PRN code 29 (FIG. 2D). It makes use of the signal's correlation
with prompt PRN code 29 (FIG. 2D) and with early-minus-late PRN
code 35 (FIG. 2D) in order to determine a chipping rate f.sub.c
that tends to align prompt PRN code 29 (FIG. 2D) as desired. Conventional
methods for determining f.sub.c are well-known in the art. Chips
of early code 69B (FIG. 2D) start and stop 0.5.DELTA.t.sub.eml seconds
before the corresponding chips of prompt PRN code 29 (FIG. 2D),
and the chips of late code 69C (FIG. 2D) start and stop 0.5.DELTA.t.sub.eml
seconds after prompt PRN code 29 (FIG. 2D). Early-minus-late PRN
code 35 (FIG. 2D) is the difference between early code 69B (FIG.
2D) and late code 69C (FIG. 2D). Example segments of these four
types of replica codes are depicted in FIG. 2D.
Referring to FIGS. 1, 2A, 2C, and 2D software correlator 19 (FIG.
1) receives, through conventional RF front end 13 and DAQ system
17, signal data 21 (FIG. 1), the raw data 12 (FIG. 1) source of
which is sampled at the rate f.sub.s=1/.DELTA.t.sub.s Hz. In order
to process the resulting RF signal data 21, software correlator
19 (FIG. 1) needs prompt PRN code 29 (FIG. 2D) and early-minus-late
PRN code 35 (FIG. 2D) replicas sampled at the same times as raw
signal 12 (FIG. 1). FIG. 2D depicts sixteen sample times as vertical
dash-dotted lines. Referring to FIG. 2D, prompt PRN code 29 (FIG.
2D) can be represented by its prompt PRN code sign 29A (FIG. 2D)
at the sample times. The bit value one represents +1, and the bit
value zero represents -1. Prompt PRN code sign 29A (FIG. 2D), shown
at the sixteen sample times--starting with three 1s, continuing
with ten 0s, and finishing with another three 1s--is a 16-bit word
stored as the integer 2.sup.15+2.sup.14+2.sup.13+2.sup.2+2.sup.1+2.sup.0=57351.
Early-minus-late PRN code 35 (FIG. 2D) requires a 1.5-bit representation.
A zero mask bit is set to zero if early-minus-late PRN code 35 takes
on the value zero, and it is set to one if early-minus-late PRN
code 35 equals +2 or -2. Early-minus-late PRN code zero mask 35B
(FIG. 2D) at sixteen sample times shown in FIG. 2D is equivalent
to 2.sup.13+2.sup.12+2.sup.2=12292. A 2's sign bit is set to one
if early-minus-late PRN code 35 (FIG. 2D) equals +2 at the sample
time, and it is set to zero if the code equals -2. The 2's sign
bit is irrelevant if the corresponding early-minus-late PRN code
zero mask 35B (FIG. 2D) bit equals zero. Early-minus-late PRN code
sign 35A (FIG. 2D) for sixteen sample times contains X values that
indicate bits whose values are irrelevant because the corresponding
early-minus-late PRN code zero mask 35B (FIG. 2D) bits are zero.
In an illustrative embodiment, all the X values become zero, thus
the equivalent integer for early-minus-late PRN code sign 35A (FIG.
2D) is 2.sup.2=4.
Continuing to refer to FIG. 3A, an alternative to taking the prompt
PRN code 29 and early-minus-late PRN code 35 from pre-computed over-sampled
PRN code table 28 is to generate prompt PRN code sign 29A, early-minus-late
PRN code sign 35A, and early-minus-late PRN code zero mask 35B using
real-time over-sampled PRN code generator 30A (FIG. 3A). Shown in
FIG. 3A are two circles and a loose arrow with a quarter circle
pointer. These are the symbols for a switch and indicate the ability
of the system to choose possible alternate sources of PRN code.
Using the real-time over-sampled PRN code generator 30A includes
a step of generating the PRN code chips in real-time by conventional
means. For example, the GPS civilian L2 CL and CM codes are generated
by a 27-bit feedback shift register (see The New L2 Civil Signal,
R. D. Fontana et al., Proceedings of the ION GPS 2001, Sep. 11-14,
2001, Salt Lake City, Utah, pp. 617-631). The method further includes
the steps of choosing chip values from the PRN code, where the chip
values correspond to a data interval that contains the samples of
a data word and where the chips have a known timing relative to
the data interval, transforming the relative timing into a time
grid index, and translating the PRN code chip values and the time
grid index for the data interval into the PRN code's over-sampled
bit-wise parallel format. These latter steps can be carried out
efficiently by using a table look up function. One table each for
prompt PRN code sign 29A, early-minus-late PRN code sign 35A, and
early-minus-late PRN code zero mask 35B can include integer values
that constitute the bit-wise parallel representation of the PRN
code for the sample times associated with the data word in question.
Indices into each 1-dimensional table are functions of (a) the time
offset between the first PRN code chip and the first sample time
of the given data word, and (b) the bit pattern of the PRN code
chips that span the sample times of the data word. The sizes of
the tables are independent of the period of the PRN code that is
being over-sampled. The tables can be re-used for multiple PRN codes
in a multi-channel receiver. The computation and use of the tables
are discussed in more detail later.
Continuing with the description of bit-wise parallelism with respect
to the operations of software correlator 19 (FIG. 1), and continuing
to refer to FIG. 3A, the specially-developed algorithms described
herein make use of bit-wise parallelism so that a single programming
language statement, such as a C code command, can partially process
up to thirty-two samples at a time. Previously referred-to carrier
replica signal 25 in the form of cosine and sine signals are stored
as binary carrier replica sign 25A and carrier replica magnitude
25B. The format of this representation is defined in Table 2 and
illustrated in FIG. 3C which is a reconstructed carrier and carrier
replica in the form of representative sine signal 51 (FIG. 3C) shown
in optimal 2-bit representation 53 (FIG. 3C) that has the minimum
square error. The format of Table 2 assumes that the cosine and
sine signals have an amplitude of approximately 2.4. Note that other
representations, beyond 2-bit representation, are possible. In general,
more bits yield a better SNR, but can also require a larger number
of computations for the correlation operations.
TABLE-US-00002 TABLE 2 Sign and magnitude combinations of the stored
intermediate-frequency baseband mixing carrier sine wave replicas
and the values that they represent Carrier Replica Sign Carrier
Replica 25A Magnitude 25B Carrier Replica Value 0 0 -1 0 1 -2 1
0 +1 1 1 +2
Continuing to refer to FIG. 3A, multiplication of the RF front-end
output representation, the signal sign 21A and signal magnitude
21B, of Table 1 by the sine wave representation, carrier replica
sign 25A and carrier replica magnitude 25B, of Table 2 yields baseband
mixed signals 23, consisting of baseband mixed sign 23A, baseband
mixed high magnitude 23B, and baseband mixed low magnitude 23C,
that can take on the values -6, -3, -2, -1, +1, +2, +3, and +6,
as shown in Table 3. Baseband mixed high magnitude 23B is simply
signal magnitude 21B, and baseband mixed low magnitude 23C is carrier
replica magnitude 25B. Thus, these two magnitude bits are available
without the need for computation. Baseband mixed sign 23A is the
result of an EXCLUSIVE OR operation between signal sign 21A and
carrier replica sign 25A. Notice how the relationship of the sign
bit value with the actual sign gets reversed from that of Tables
1 and 2.
TABLE-US-00003 TABLE 3 Sign, high-magnitude, and low-magnitude
combinations of the baseband-mixed signal and their corresponding
signal values. Baseband Baseband Mixed Baseband Mixed Mixed Sign
High Magnitude Low Magnitude Baseband Mixed 23A 23B 23C Value 0
0 0 +1 0 0 1 +2 0 1 0 +3 0 1 1 +6 1 0 0 -1 1 0 1 -2 1 1 0 -3 1 1
1 -6
Continuing to refer to FIG. 3A, and continuing to describe the
bit-wise parallel algorithms, the required amount of storage for
tables of pre-computed prompt PRN code 29 and early-minus-late PRN
code 35 can be greatly reduced by making two simplifications. First,
the prompt PRN code 29 is stored as prompt PRN code sign 29A. This
representation is shown in Table 4. The early-minus-late PRN code
35, on the other hand, is stored in a two-bit representation (actually
a 1.5 bit representation): early-minus-late PRN code sign 35A and
early-minus-late PRN code zero mask 35B, as denoted in Table 5.
Note that the X in the first column of Table 5 indicates that zero
or one can be placed in this location without affecting the corresponding
code value. The X signifies a lack of effect of the sign bit on
the code value when the zero mask bit equals zero. This is why the
early-minus-late PRN code 35 representation is referred to as a
1.5-bit representation. This X value will affect the corresponding
fully mixed early-minus-late integrand sign 33A, but it will not
affect any of the early-minus-late value words because the zero
value in the corresponding zero mask location will null out the
corresponding bit of all early-minus-late value words.
TABLE-US-00004 TABLE 4 Sign bits of the prompt C/A code and the
corresponding prompt signal values. Prompt PRN Code Sign 29A Prompt
Code Value 1 +1 0 -1
TABLE-US-00005 TABLE 5 Sign and zero mask bit combinations of the
early-minus-late PRN code 35 and the corresponding signal values.
Early-minus-late PRN Early-minus-late PRN Early-Minus-Late Code
Code Sign 35A Code Zero Mask 35B Value X 0 0 0 1 -2 1 1 +2
Another simplification in the pre-computed over-sampled PRN code
table 28, and continuing to refer to FIG. 3A, can be to ignore code
Doppler shift variations. All signals in the table are assumed to
have zero Doppler shift; i.e., all C/A codes in the table assume
that {circumflex over (.tau.)}.sub.jk+1-{circumflex over (.tau.)}.sub.jk=0.001
sec. Note that the period of 0.001 is applicable for accumulations
that use the full 1023 chips of the C/A code only. Any other type
of code or accumulation interval may have a different period. The
code phase errors due to this assumption can be eliminated by choosing
a replica code from the pre-computed over-sampled PRN code table
28 whose midpoint occurs at the desired midpoint time ({circumflex
over (.tau.)}.sub.jk+{circumflex over (.tau.)}.sub.jk+1)/2. The
only other effect of this assumption can be a small correlation
power loss, which is no more than 0.014 dB if the magnitude of the
Doppler shift is less than 10 KHz. The pre-computed over-sampled
PRN code table 28 should include a selection of different phases,
for example fourteen, as measured relative to a signal sample spacing
of, for example, 175 nsec. This translates into a code phase spacing
of, for example, 12.5 nsec, which equals a pseudo range measurement
digitization level of 3.8 m, or a maximum measurement error of 1.9
m. The number of phases in the pre-computed over-sampled PRN code
table 28 is dependent upon the design of the system and no set number
of phases is required by the present invention. Referring to FIG.
6, suppose that pre-computed over-sampled PRN code table 28 stores
over-sampled bit-wise parallel representations of chips C(1) through
C(M). The table must allow for the retrieval of over-sampled bit-wise
parallel code replicas for a range of start times of code chip C(1)
that span the entire first data sample word in the accumulation
interval W.sub.1 95 (FIG. 6). The table may contain code replicas
whose different phases yield start times that span only a single
sample interval of data word W.sub.1 95 (FIG. 6), which is only
1/n.sub.s of the required number of start times. In this case the
software correlator may apply bit shift operations to a tabulated
PRN code replica from that sample interval in order to generate
the over-sampled bit-wise parallel PRN code replica that applies
when chip C(1) starts in a different sample interval of data word
W.sub.1 95 (FIG. 6).
Continuing to refer to FIG. 3A, and further continuing to describe
the bit-wise parallel algorithms, prompt PRN code 29 and early-minus-late
PRN code 35 replicas can be mixed with the baseband mixed signals
23 to form fully mixed prompt integrand 31 by an EXCLUSIVE OR operation
and bit re-definitions. An EXCLUSIVE OR between prompt PRN code
sign 29A and baseband mixed sign 23A produces fully mixed prompt
integrand sign 31A given in Table 6. The fully mixed prompt integrand
high magnitude 31B and fully mixed prompt integrand low magnitude
31C are baseband mixed high magnitude 23B and baseband mixed low
magnitude 23C, also given in Table 6. Note that the Table 6 representation
is identical to that of Table 3 except for the inversion in the
meaning of the sign bits. The number of magnitude bits is dependent
upon the design of the system and no set number of magnitude bits
is required by the present invention. A change in the number of
magnitude bits will cause a change in the number of entries of the
equivalent of Table 6 and it will affect the possible values of
the integrand.
TABLE-US-00006 TABLE 6 Sign, high-magnitude, and low-magnitude
bit combinations of the fully mixed prompt integrand 31 and its
corresponding values. Fully Mixed Fully Mixed Fully Mixed Prompt
Fully Mixed Prompt Prompt Prompt Integrand Sign Integrand High Integrand
Low Integrand 31A Magnitude 31B Magnitude 31C Value 0 0 0 -1 0 0
1 -2 0 1 0 -3 0 1 1 -6 1 0 0 +1 1 0 1 +2 1 1 0 +3 1 1 1 +6
Still continuing to refer to FIG. 3A, the mixing of the early-minus-late
PRN code 35 with the baseband mixed signals 23 forms fully mixed
early-minus-late integrands 33. Fully mixed early-minus-late integrand
sign 33A is an EXCLUSIVE OR between early-minus-late PRN code sign
35A and baseband mixed sign 23A. Fully mixed early-minus-late integrand
high magnitude 33B and fully mixed early-minus-late integrand low
magnitude 33C are, as above, baseband mixed high magnitude 23B and
baseband mixed low magnitude 23C. Fully mixed early-minus-late integrand
zero mask 33D is early-minus-late PRN code zero mask 35B. The resulting
representation is given in Table 7. As in Table 5, each X entry
in the table indicates that the corresponding bit can be either
zero or one without affecting the corresponding integrand value.
TABLE-US-00007 TABLE 7 Sign, high-magnitude, low-magnitude, and
zero mask bit combinations of the fully mixed early-minus-late integrands
33 and their corresponding values. EML EML Early-Minus- Integrand
Integrand EML Early- Late (EML) High Low Integrand Minus-Late Integrand
Magnitude Magnitude Zero Mask Integrand Sign 33A 33B 33C 33D Value
X X X 0 0 0 0 0 1 -2 0 0 1 1 -4 0 1 0 1 -6 0 1 1 1 -12 1 0 0 1 +2
1 0 1 1 +4 1 1 0 1 +6 1 1 1 1 +12
Referring now to FIGS. 3A, 3B, 4A, and 4B, the method for computing
in-phase and quadrature accumulations for every accumulation period,
for example every millisecond for GPS C/A code, by use of bit-wise
parallelism includes the steps of selecting carrier replica signal
25 (FIG. 3A) according to the proximity of its frequency to the
desired frequency, and representing sample signal data 21 (FIG.
3A) and carrier replica signal 25 (FIG. 3A) from at least one channel
as bits in signal sign 21A (FIG. 3A) and, if present, signal magnitude
21B (FIG. 3A) and carrier replica sign 25A (FIG. 3A) and carrier
replica magnitude 25B (FIG. 3A) (method step 101, FIG. 4A). Note
that carrier replica signal 25 (FIG. 3A) is chosen so that its frequency
is close to the correct signal frequency. The method also includes
the step of mixing signal data 21 (FIG. 3A) to baseband by computing
in-phase and quadrature baseband mixed sign 23A (FIG. 3A) and in-phase
and quadrature baseband mixed high and low magnitude 23B/C (FIG.
3A) (method step 103, FIG. 4A). The method further includes the
steps of selecting PRN code from pre-computed over-sampled PRN code
table 28 (FIG. 3A) or of computing it using real-time over-sampled
PRN code generator 30A (FIG. 3A), representing prompt PRN code 29
(FIG. 3A) as prompt PRN code sign 29A (FIG. 3A), and representing
early-minus-late PRN code 35 (FIG. 3A) from as early-minus-late
PRN code sign 35A (FIG. 3A) and early-minus-late PRN code zero mask
35B (FIG. 3A) (method step 105, FIG. 4A). The method further includes
the step of de-spreading in-phase and quadrature baseband mixed
signal 23 (FIG. 3A) by mixing it with prompt PRN code 29 (FIG. 3A)
and early-minus-late PRN code 35 (FIG. 3A), resulting in in-phase
and quadrature fully mixed prompt integrands 31 (FIG. 3A), and fully
mixed early-minus-late integrands 33 (FIG. 3A) (method step 107,
FIG. 4A). The method further includes the step of using prompt value
word logic 27A (FIG. 3B) to compute prompt integrand value words
27 (FIG. 3B) from the in-phase and quadrature fully mixed prompt
integrands 31 (FIG. 3A). The method further includes the step of
using early-minus-late value word logic 37A (FIG. 3B) to compute
early-minus-late integrand value words 37 (FIG. 3B) from the fully
mixed early-minus-late integrands 33 (FIG. 3B) (method step 109,
FIG. 4A). The method further includes the steps of summing over
each prompt integrand value word 27 and early-minus-late integrand
value word 37 (FIG. 3B) the number of one bits (or zero bits) using
one bits summation table 38 (FIG. 3B) or using a processor command
if available (method step 111, FIG. 4B), and summing, over the accumulation
interval, the number of one bits (or zero bits) in each prompt integrand
value word 27 and early-minus-late integrand value word 37 to produce
prompt accumulations 41 (FIG. 3B) and early-minus-late accumulations
49 (FIG. 3B) (method step 113, FIG. 4B). The method further includes
the step of multiplying prompt accumulations 41 (FIG. 3B) and early-minus-late
accumulations 49 (FIG. 3B) by corresponding values 41A and summing
the results over the value words of each signal for an entire accumulation
interval to yield in-phase and quadrature summed prompt accumulations
45 (FIG. 3B) and summed early-minus-late accumulations 47 (FIG.
3B) (method step 115, FIG. 4B) that are stored for use by acquisition
techniques or tracking loops. The method further includes the step
of rotating the in-phase and quadrature summed prompt accumulations
45 (FIG. 3B) and summed early-minus-late accumulations 47 (FIG.
3B) (method step 117, FIG. 4B) to simulate a condition in which
baseband mixing had been performed using cosine and sine signal
replicas with the correct frequency and phase. If there are more
channels to process (decision step 119, FIG. 4B), the method includes
the step of repeating the previous steps beginning at method step
101, FIG. 4A. If there are no more channels to process (decision
step 119, FIG. 4B), the method includes the step of setting parameters
for the next accumulation period, including storing current C/A
code phases, epoch counters, carrier phases, and carrier Doppler
shifts (method step 121, FIG. 4B). If the time period to wait until
the next accumulations need to be calculated has not expired (decision
step 123, FIG. 4B), the method includes the step of sleeping until
the expiration of the time period (method step 125, FIG. 4B). If
the time period has expired (decision step 123, FIG. 4B), the method
includes the step of repeating the previous steps beginning at method
step 101, FIG. 4A. The length of the time period depends on the
nominal accumulation period. It is set to be less than this period,
normally between 50% to 90% of this period, to reduce the possibility
that accumulations are missed for any channels.
Referring again to FIGS. 3B and 4A, method step 109 (FIG. 4A) calls
for computing value words. This computation starts by performing
bit-wise parallel Boolean logic for each of the possible values
in the right-hand column of the prompt integrand representation
in Table 6. A 32-bit prompt integrand value word 27 (FIG. 3B) is
computed for each thirty-two samples and each row of Table 6. The
prompt integrand value word 27 (FIG. 3B) contains ones for the sample
times when the actual integrand equals the corresponding value in
the right-hand column of Table 6, and zeros for the remaining times
when the actual integrand does not equal this value. The prompt
integrand value words 27 (FIG. 3B) corresponding to the possible
Table 6 values are formed by method step 109 (FIG. 4A) as follows:
MINUSONE=NOT(SIGN) AND [NOT(HIGHMAG) AND NOT(LOWMAG)] (13) MINUSTWO=NOT(SIGN)
AND [NOT(HIGHMAG) AND LOWMAG] (14) MINUSTHREE=NOT(SIGN) AND [HIGHMAG
AND NOT(LOWMAG)] (15) MINUSSIX=NOT(SIGN) AND [HIGHMAG AND LOWMAG]
(16) PLUSONE=SIGN AND [NOT(HIGHMAG) AND NOT(LOWMAG)] (17) PLUSTWO=SIGN
AND [NOT(HIGHMAG) AND LOWMAG] (18) PLUSTHREE=SIGN AND [HIGHMAG AND
NOT(LOWMAG)] (19) PLUSSIX=SIGN AND [HIGHMAG AND LOWMAG] (20)
Continuing to refer to FIGS. 3A, 3B, 4A, and 4B, method steps 109
(FIG. 4A), 111 (FIG. 4B), and 113 (FIG. 4B) call for operations
for the fully mixed early-minus-late integrands 33 (FIG. 3A) that
are similar to those for the fully mixed prompt integrands 31 (FIG.
3A). Early-minus-late integrand value words 37 (FIG. 3B) correspond
to values that are double those of the prompt integrand value words
27 (FIG. 3B), i.e., the MINUSSIX word becomes the MINUSTWELVE word.
Also, an additional AND operation must be performed with the zero
mask bits of Table 7 in order to mask out sample times when the
early and late PRN codes cancel each other. Possible formulas for
the method step 109 (FIG. 4A) computation of these early-minus-late
integrand value words 37 (FIG. 3B) are as follows: MINUSTWO=[ZEROMASK
AND NOT(SIGN)] AND [NOT(HIGHMAG) AND NOT(LOWMAG)] (21) MINUSFOUR=[ZEROMASK
AND NOT(SIGN)] AND [NOT(HIGHMAG) AND LOWMAG] (22) MINUSSIX=[ZEROMASK
AND NOT(SIGN)] AND [HIGHMAG AND NOT(LOWMAG)] (23) MINUSTWELVE=[ZEROMASK
AND NOT(SIGN)] AND [HIGHMAG AND LOWMAG] (24) PLUSTWO=[ZEROMASK AND
SIGN] AND [NOT(HIGHMAG) AND NOT(LOWMAG)] (25) PLUSFOUR=[ZEROMASK
AND SIGN] AND [NOT(HIGHMAG) AND LOWMAG] (26) PLUSSIX=[ZEROMASK AND
SIGN] AND [HIGHMAG AND NOT(LOWMAG)] (27) PLUSTWELVE=[ZEROMASK AND
SIGN] AND [HIGHMAG AND LOWMAG] (28) Additional zero masking can
occur in the first and last words of an accumulation interval. This
is true because the start and stop times of an accumulation interval
do not normally fall at the boundaries of data words. Therefore,
the bits in the first word that precede the accumulation interval
may need to get zero masked as might the bits in the last word that
come after the end of the accumulation interval.
Referring primarily to FIGS. 3B and 4B, the one bits counting operations
of method step 111 (FIG. 4B) form the count of the number of one
bits in each of the eight value words. If there are no such counting
operations in the instruction set of microprocessor 16 (FIG. 1),
the counting can be accomplished using a table look-up. In the case
of a table look-up, prompt integrand value words 27 and early-minus-late
integrand value words 37 (FIG. 3B) can be used as addresses in one
bits summation table 38 (FIG. 3B), and one bits summation table
38 (FIG. 3B) can output the number of one values (or zeros) in the
address. For example, if the table look-up operation is called BITSUM,
the following computations can be performed to compute one-bits
counts: ONESCOUNT=BITSUM(VALUEWORD) (29) where the output of the
table ONESCOUNT is the number of one bits in the word VALUEWORD.
This operation is repeated for each of the prompt integrand value
words 27 (FIG. 3B) and early-minus-late integrand value words 37
(FIG. 3B) in order to accomplish method step 111 (FIG. 4B). Selection
of table width, for example 16-bit or 32-bit, depends on the amount
of memory available and other design decisions. If the table width
is smaller than the number of bits in a value word, then multiple
calls of the table are used in order to sum up the total number
of one values in a given value word. Each call takes as input only
a portion of the bits in the value word.
Continuing to refer primarily to FIGS. 3B and 4B, the accumulation
operations of method steps 113 (FIG. 4B) and 115 (FIG. 4B) sum the
one bit counts for each prompt integrand value word 27 (FIG. 3B)
and for each early-minus-late integrand value word 37 (FIG. 3B)
over the entire accumulation interval, multiply each result by the
value 41A (FIG. 3B) that is associated with the value word, and
sum all of these scaled value accumulations to form the accumulations
of equations (6) and (7), summed prompt accumulation 45 (FIG. 3B)
and summed early-minus-late accumulation 47 (FIG. 3B). For example,
the following computations can be performed to compute the in-phase
summed prompt accumulation 45 in equation (6) as follows:
.function..times..function..times..times..function..times..times..function-
..times..times..function..times..function..times..times..function..times..-
times..function..times..times..function. ##EQU00009## where l is
the index of successive bit-wise parallel data words in the accumulation
interval, N.sub.w is the total number of data words in the interval,
and ONESCOUNT(k).sub.Ipl is the ones count for the corresponding
value word 41 (FIG. 3B) associated with value k 41A (FIG. 3B) for
the lth data word interval and the in-phase summed prompt accumulation
45 (FIG. 3B). The quadrature summed prompt accumulations 45 (FIG.
3B) and the in-phase and quadrature summed early-minus-late accumulations
47 (FIG. 3B) are calculated in a similar manner. The only difference
is in the actual ONESCOUNT values used and, for the case of early-minus-late
signals, the set of k values 41A (FIG. 3B).
Continuing to refer primarily to FIGS. 4A and 4B, the method of
the present invention can be adapted to work with a different number
of bits in the representation of the RF front-end output and of
the baseband mixed signals. An increase above two bits can make
the logic more complex and may decrease the time savings over straight
integer arithmetic. A decrease to a 1-bit representation can have
the opposite effect. For example, if the RF front-end uses 1-bit
digitization rather than 2-bit digitization while carrier replica
signal 25 (FIG. 2B) retains its 2-bit digitization, then the operation
count can decrease by a factor of almost two for the 1-bit method,
which can make the logic execute about 4.2 times faster than straight
integer arithmetic.
Returning to the discussion of determining PRN code, and now referring
again FIGS. 2C, 2D, and 3A, the real-time generation of bit-wise
parallel over-sampled prompt PRN code sign 29A (FIGS. 2D and 3A),
early-minus-late PRN code sign 35A (FIGS. 2D and 3A), and early-minus-late
PRN code zero mask 35B (FIGS. 2D and 3A) can be carried out by real-time
over-sampled PRN code generator 30A (FIG. 3A). The inputs to this
calculation are the actual PRN code chip length 65 (FIG. 2D), .DELTA.t.sub.c,
the sample interval 63 (FIG. 2D), .DELTA.t.sub.s, the nominal early-to-late
code delay 61 (FIG. 2D), .DELTA.t.sub.eml, the end time of the first
code chip relative to the first sample time, or put another way,
the time lag .DELTA.t.sub.0, 67 (FIG. 2D) from the first RF sample
time to the end time of the first prompt PRN code chip, and prompt
code chips 91 (FIGS. 2D and 6). The outputs are the three integers
that store the prompt PRN code sign 29A (FIGS. 2D and 3A), early-minus-late
PRN code zero mask 35B (FIGS. 2D and 3A), and early-minus-late PRN
code sign 35A (FIGS. 2D and 3A), which are all in bit-wise parallel
format.
Referring again to FIGS. 2C and 2D, table look-ups can be used
to translate a PRN code and its timing information to bit-wise parallel
representations of its over-sampled prompt and early-minus-late
versions. The required table look-ups can be simplified by recognizing
that the following parameters are substantially constant, for the
purposes of this calculation: sampling interval 63 (FIG. 2D), .DELTA.t.sub.s,
the nominal chip length, .DELTA.t.sub.cnom, the early-minus-late
code delay 61 (FIG. 2D), .DELTA.t.sub.eml, used by software correlator
19 (FIG. 1), and the maximum number of chips that span a data word
of microprocessor 16 (FIG. 1). The difference between the actual
chipping rate .DELTA.f.sub.c, (reciprocal of .DELTA.t.sub.c) and
the nominal chipping rate .DELTA.f.sub.cnom (reciprocal of .DELTA.t.sub.cnom)
that is used for the above simplification can be accommodated by
correcting time lag 67 (FIG. 2D), .DELTA.t.sub.0, for the average
effects of Doppler shift, a procedure discussed later. Using the
simplification, each look-up table has two variable inputs: the
actual set of prompt code chips 91 (FIGS. 2D and 6) and time lag
67 (FIG. 2D), .DELTA.t.sub.0. A table look-up procedure for each
signal component yields a single integer result for prompt PRN code
sign 29A (FIGS. 2D and 3A), another single integer result for early-minus-late
PRN code zero mask 35B (FIGS. 2D and 3A), and yet another single
integer result for early-minus-late PRN code sign 35A (FIGS. 2D
and 3A).
Time lag 67 (FIG. 2D), .DELTA.t.sub.0, can take on an infinite
number of values in the continuous range:
.times..DELTA..times..times.<.DELTA..times..times..ltoreq..DELTA..times-
..times..times..DELTA..times..times. ##EQU00010## This range's lower
limit guarantees that the end time of the first late chip occurs
no earlier than the first sample time. A lower time lag 67 (FIG.
2D) .DELTA.t.sub.0 value would make the first chip irrelevant to
the prompt PRN code 29 (FIG. 2D), early code 69B (FIG. 2D), and
late code 69C (FIG. 2D) at all of the sample times. The upper limit
in equation (31) guarantees that the start time of the first late
chip occurs no later than the first sample. A larger value of .DELTA.t.sub.0
would leave the late code 69C (FIG. 2D) at the first sample time
undefined based on the available code chips.
Referring now to FIG. 5, to create an electronically processable
table, the continuous range of .DELTA.t.sub.0 values can be replaced
with a discrete grid having m equally spaced points per sample interval
63 (FIG. 2D), .DELTA.t.sub.s. The integer m is chosen to be large
enough so that the granularity .DELTA.t.sub.s/m gives sufficient
PRN code timing resolution. In GPS applications m is usually chosen
to be large enough so that (c.DELTA.t.sub.s/m) is on the order of
several meters or less, where c is the speed of light, but reasonably
sized because the table sizes are usually proportional to m. Given
a choice of m, the grid of relative end times of the first prompt
code period is:
.DELTA..times..times..times..times..times..DELTA..times..times..times..tim-
es..times..times..times. ##EQU00011## where the limits
.times..times..times..times..DELTA..times..times..times..DELTA..times..tim-
es..times..times..function..DELTA..times..times..times..DELTA..times..time-
s..DELTA..times..times..times. ##EQU00012## provide full coverage
of the interval defined in equation (31). The floor ( ) function
rounds to the nearest integer in the direction of -.infin.. This
k.sub.min value can cause the minimum .DELTA.t.sub.0k to fall slightly
below the lower limit in equation (31), which can cause memory inefficiency,
but this value is advantageous because it may simplify some further
computations.
The size for each table can be a function of the maximum number
of code chips that may fall within a data word's sample range. Given
.DELTA.t.sub.0, bit information for the following number of code
chips is required in order for the prompt PRN code 29 (FIG. 2D),
early code 69B (FIG. 2D), and late code 69C (FIG. 2D) to be fully
specified at all of the data word's sample times:
.function..DELTA..times..times..times..times..DELTA..times..times..DELTA..-
times..times..times..DELTA..times..times..DELTA..times..times. ##EQU00013##
where n.sub.s is the number of data samples that can be stored in
bit-wise parallel format in each word. It is clear from equation
(34) that l(.DELTA.t.sub.0) is a non-increasing function of .DELTA.t.sub.0.
Therefore, the maximum number of required chips occurs at the minimum
value of .DELTA.t.sub.0: L=l(.DELTA.t.sub.0k min) (35) The size
of each table can be determined from the parameters k.sub.min, k.sub.max,
and L. The grid contains k.sub.tot=(k.sub.max-k.sub.min+1) different
time offsets of the first code chip. At each of these grid points
there are 2.sup.L possible combinations of the code chips. Thus,
each table optimally contains k.sub.tot.times.2.sup.L entries, and
each entry is optimally an unsigned integer in the range from 0
to 2.sup.n.sup.s-1.
Continuing to refer to FIG. 5, each table can be stored as an array
with a single index. The first 2.sup.L entries correspond to the
2.sup.L different possible chip sequences that can occur at .DELTA.t.sub.0=.DELTA.t.sub.0k
min, the next 2.sup.L entries correspond to .DELTA.t.sub.0=.DELTA.t.sub.0(kmin+1),
and so forth. The tabulated bit sequences for a fixed .DELTA.t.sub.0
are ordered by interpreting the sequence as a binary index counter
with the first chip being the most significant counter bit and the
L.sup.th chip being the least significant bit. The integer elements
of the table can be the x(i) table elements 81 with corresponding
code time offset 83 .DELTA.t.sub.0k, and corresponding bit sequence
85 of the chips. The array index of a given x(i) table element 81
can be computed based on its code time offset 83 .DELTA.t.sub.0k
grid index k and its corresponding bit sequence 85. The corresponding
bit sequence 85 associated with the array index consists of the
chip values C(1), C(2), C(3), . . . C(L). The C(j) chip values are
either zero or one, with zero representing a -1 PRN code value and
one representing a +1 PRN code value, and they are listed in order
of increasing time. The corresponding array index of the x(i) table
element 81 is:
.function..function..function..function..times..function..times..times..ti-
mes..times..times..times..function..times..times..times..times.
##EQU00014## This equation can be inverted to give the code time
offset 83 grid index k and the corresponding bit sequence 85 as
functions of the x(i) table element 81 index i: k(i)=k.sub.min+floor[(i-1)/2.sup.L]
(37a)
.function..function..times..function..times..times..times..times..times..t-
imes. ##EQU00015## where mod(y,z)=y-z.times.floor(y/z) is the usual
remainder function.
Continuing to refer to FIG. 5, the following computations generate
the x(i) table elements 81 entries of the three tables. Given i,
the corresponding code time offset 83 grid index k(i) is computed
from equation (37a) and is used to generate three sequences of chip
indices:
.function..times..times..function..function..DELTA..times..times..DELTA..t-
imes..times..times..times..times..times..times..times..times..function..ti-
mes..times..function..function..DELTA..times..times..DELTA..times..times..-
DELTA..times..times..times..DELTA..times..times..times..times..times..time-
s..times..times..times..function..times..times..function..function..DELTA.-
.times..times..DELTA..times..times..DELTA..times..times..times..DELTA..tim-
es..times..times..times..times..times..times..times..times..times.
##EQU00016## where n is the index of the sample time within the
over-sampled data word. The integer j.sub.p(n,i) is the index of
the PRN code chip that applies at sample n for the prompt PRN code
29 (FIG. 2D). The integers j.sub.e(n,i) and j.sub.l(n,i) are defined
similarly for the early code 69B (FIG. 2D) and late code 69C (FIG.
2D), respectively. The formulas in equations (38a)-(38c) amount
to time measurements of each sample given in units of chip lengths
past the first chip. These indices, in turn, can be used to determine
the chip values that apply at the sample times: C.sub.p(n,i)=C[j.sub.p(n,i);i]
for n=1,2,3, . . . ,n.sub.s (39a) C.sub.e(n,i)=C[j.sub.e(n,i);i]
for n=1,2,3, . . . ,n.sub.s (39b) C.sub.1(n,i)=C[j.sub.l(n,i);i]
for n=1,2,3, . . . ,n.sub.s (39c) where C.sub.p(n,i) is the over-sampled
prompt PRN code 29 (FIG. 2D), and C.sub.e(n,i) and C.sub.l(n,i)
are, respectively, the early code 69B (FIG. 2D) and late code 69C
(FIG. 2D). Each of these code bit values is either zero or one,
as dictated by the outer mod(,2) operation in equation (37b). These
over-sampled chip values can, in turn, be used to formulate tabulated
functions x.sub.p(i), x.sub.emlzm(i), and x.sub.eml2s(i) that generate
the unsigned integers that constitute the bit-wise parallel code
representations of the three tables:
.function..times..function..times..times..function..times..times..function-
..function..times..times..times..times..times..function..times..times..fun-
ction..function..times..function..times..times. ##EQU00017## where
x.sub.p(i) is the entry of the prompt sign table, x.sub.emlzm(i)
is the entry of the early-minus-late zero mask table, and x.sub.eml2s(i)
is the entry of the early-minus-late 2's sign table. Note that the
formula used in equation (40c) is only an example illustrative embodiment
of the early-minus-late 2's sign table calculation. It places zeros
in all of the X entries of early-minus-late PRN code sign 35A (FIG.
2D). There exist alternate formulas that are equally correct but
that do not place zeros in the X entries.
The table layout in FIG. 5 is only an illustrative embodiment of
how one can construct a table that can be used to translate PRN
code chip values and timing information into data words that store
the bit-wise parallel representations of the over-sampled prompt
PRN code sign 29A (FIG. 2D), early-minus-late PRN code zero mask
35B (FIG. 2D), and early-minus-late PRN code sign 35A (FIG. 2D).
Other table layouts are also possible. Possible illustrative index
calculations are described below for indexing into the tables for
PRN code retrieval during accumulation calculations If another table
layout is used, then different indexing calculations might be needed.
Furthermore, different indexing calculations can be used even for
the illustrative table layout shown in FIG. 5.
Referring now primarily to FIG. 6, accumulation calculations, as
have been previously outlined herein and elsewhere, work with a
fixed sequence of code chips. The prompt version of this sequence
has a specified timing relationship to the incoming RF signal data
21 (FIG. 2A). This relationship can be pre-determined by a code
search algorithm if software receiver 10 (FIG. 1) is in acquisition
mode or by its delay-locked loop if it is in tracking mode. Software
correlator 19 (FIG. 1) can calculate an accumulation using prompt
code chips 91 (FIG. 6) C(1) through C(M). The timing of the prompt
replicas of prompt code chips 91 (FIG. 6) can define the accumulation
interval. The chip sequence starts at start lag 93 (FIG. 6) .DELTA.t.sub.start
seconds past the first sample of data word W.sub.1 95 (FIG. 6),
it chips at the constant chipping rate f.sub.c=1/.DELTA.t.sub.c,
and it ends at end time 97 (FIG. 6), which occurs .DELTA.t.sup.start+M.DELTA.t.sub.c
seconds after the first sample of data word W.sub.1 95 (FIG. 6).
The end of the M.sup.th prompt code chip can occur during data word
W.sub.N 99 (FIG. 6), which implies that
.function..DELTA..times..times..times..times..DELTA..times..times..times..-
DELTA..times..times. ##EQU00018## where the ceil( ) function rounds
to the nearest integer towards +.infin.. Some of the initial bits
of data word W.sub.1 95 (FIG. 6) and some of the final bits of data
word W.sub.N 99 (FIG. 6) may not be included in the accumulation.
Let n.sub.ex0 be the number of initial bits of data word W.sub.1
95 (FIG. 6) that are excluded, and let n.sub.exf be the number of
final bits of data word W.sub.N 99 (FIG. 6) that are excluded. The
timing relationship in FIG. 6 implies that these numbers are:
.times..times..function..DELTA..times..times..DELTA..times..times..times..-
times..function..DELTA..times..times..times..times..DELTA..times..times..D-
ELTA..times..times..times. ##EQU00019##
These sample counts can be used to develop additional zero mask
words that software correlator 19 (FIG. 1) uses to properly process
the first and last data words during its bit-wise parallel accumulation
calculations, as defined in A 12-Channel Real-Time GPS L1 Software
Receiver, B. M. Ledvina et al., Proceedings of the ION National
Technical Meeting, Jan. 22-24, 2003, Anaheim, Calif. and Bit-Wise
Parallel Algorithms for Efficient Software Correlation Applied to
a GPS Software Receiver, B. M. Ledvina et al., to appear in the
IEEE Transactions on Wireless Communications, 2003, both incorporated
herein in their entirety by reference. Note that equations (41)-(42b)
and all related timing considerations herein use the following code
chip start/stop convention: a sample is correlated with a particular
code chip if the start time of the code chip coincides exactly with
the sample time, but it will not get correlated with that chip if
its sample time coincides exactly with the end time of the code
chip.
Continuing to refer to FIG. 6, efficiently determining the correct
x.sub.p(i), X.sub.emlzm(i), and x.sub.eml2s(i) bit-wise parallel
code representations for the N data words W.sub.1 95 (FIG. 6) through
data word W.sub.N 99 (FIG. 6) involves making an efficient determination
of the correct table index i.sub.v that corresponds to data word
W.sub.v .sub.for v=1, . . . , N, where the table index i.sub.v is
a function of start lag .DELTA.t.sub.start 93 (FIG. 6), actual PRN
code chip length .DELTA.t.sub.c 65 (FIG. 6), v, and prompt code
chips C(0), C(1), C(2), . . . , C(M+1) 91 (FIG. 6). The chip value
C(0) 94 (FIG. 6) is needed in order to specify the late code 69C
(FIG. 2D) at the initial few samples of the accumulation, and the
chip value C(M+1) 96 (FIG. 6) is needed to specify the early code
69B (FIG. 2D) at the final few samples. Additional constants that
can be used in order to determine the i.sub.v indices are .DELTA.t.sub.s,
n.sub.s, m, L, k.sub.min, k.sub.max, and nominal chip length .DELTA.t.sub.cnom,
which has been used to generate the three x(i) tables.
The first step of the index calculation procedure pre-computes
and stores a table of candidate integers for the final summation
term that appears on the right-hand side of equation (36). This
table takes the form:
.DELTA..times..times..function..mu..times..function..mu..times..times..tim-
es..times..times..mu..times. ##EQU00020## This computation requires
the undefined chip values C(-L+1), C(-L+2), C(-L+3), . . . , C(-1),
and C(M+2), C(M+3), C(M+4), . . . , C(M+L). The value zero can be
used for each of these undefined chips because they can affect the
over-sampled codes only for the first n.sub.ex0 samples of data
word W.sub.1 95 (FIG. 6) or for the last n.sub.exf samples of data
word W.sub.N 99 (FIG. 6), none of which are part of the accumulation.
The table of equation (43) can be constructed by using the following
iterative procedure: .DELTA.i(1)=C(0) (44a) .DELTA.i(.mu.)=mod[2.DELTA.i(.mu.-1),2.sup.L]+C(.mu.-1)
for .mu.=2,3,4, . . . , (M+2) (44b) .DELTA.i(.mu.)=mod[2.DELTA.i(.mu.-1),2.sup.L]
for .mu.=(M+3), (M+4), . . . , (M+L+1) (44c) Note that the mod(2.times.,2.sup.L)
operation in the latter two equations can be replaced by a single
truncated leftward bit shift.
In many cases prompt code chips 91 (FIG. 6) C(0), C(1), C(2), .
. . can be generated as the output of a feedback shift register
or a system of such registers. For example, the new GPS civilian
L2 signals can be generated this way. In this case, each iteration
of equation (44b) can be interleaved with an iteration of the shift
register calculations. Shift-register generation of PRN codes is
well-known in the art.
An alternative to building up the previously-described table is
to calculate the index component only for one data word at a time.
Suppose that .DELTA.i.sub.v is the correct index component for data
word W.sub.v, and that .mu..sub.v is the auxiliary index that would
have been used to determine .DELTA.i.sub.v from the .DELTA.i(.mu.)
table had the table existed. In order to calculate .DELTA.i.sub.v+1
for data word W.sub.v+1, .mu..sub.v+1 is computed (procedure defined
herein), feedback shift register calculations that generate C(.mu..sub.v),
C(.mu..sub.v+1), C(.mu..sub.v+2), . . . , C(.mu..sub.v+1-1) are
iterated, and the resulting chip values are used to perform (.mu..sub.v+1-.mu..sub.v)
iterations of equations (44b) or (44c).
Determination of the correct index into the x.sub.p(i), x.sub.emlzm(i),
and x.sub.eml2s(i) tables for data word W.sub.v can be reduced to
the determination of two quantities. One is the time offset index
k.sub.v that causes .DELTA.t.sub.0kv from equation (32) to match
the true time offset for data word W.sub.v as closely as possible.
The other quantity is the auxiliary table index .mu..sub.v. It constitutes
an index for the sequence of actual code chips that are associated
with data word W.sub.v. Given these two quantities, the correct
index for the three x(i) tables is i.sub.v=1+(k.sub.v-k.sub.min).times.2.sup.L+.DELTA.i(.mu..sub.v)
for v=1,2,3 . . . , N (45)
The auxiliary index .mu..sub.v is determined by the position of
the W.sub.v data word relative to the PRN code chip sequence. Once
that position has been ascertained, the index k.sub.v can be calculated
from the position relative to the W.sub.v samples of the L code
chips that are associated with the index .mu..sub.v.
A time integer can keep track of the number of fine-scale time
units in a given interval. The fine-scale time unit is a small fraction
of the sample interval 63 (FIG. 2D), .DELTA.t.sub.s:
.DELTA..times..times..DELTA..times..times. ##EQU00021## where m.sub.f
is the integer number of fine-scale time intervals per sample interval
63 (FIG. 2D), .DELTA.t.sub.s. This number is chosen large enough,
for example m.sub.f>2mN, to preclude any significant build-up
of timing errors during an accumulation interval due to the finite
time resolution .DELTA.t.sub.f. N is the number of data words in
the accumulation interval. The calculation of the k.sub.v values
over one accumulation interval involves approximately N iterative
time increments, each of which has a resolution of .DELTA.t.sub.f.
If m.sub.f obeys the inequality given above, then the cumulative
timing errors due to the finite precision .DELTA.t.sub.f will be
less than the timing error caused by the finite timing precision
of the x(i) tables. Normally it is possible to make m.sub.f much
larger than 2mN and still keep all of the relevant calculations
within the size limits of a 32-bit signed integer. If m.sub.f is
a power of two, a rightward bit shift operation can be used to implement
integer division by m.sub.f. Time unit .DELTA.t.sub.f can be used
to define an integer that approximately keeps track of the code/sample
time offset .DELTA.t.sub.0v for data word W.sub.v:
.apprxeq..times..times..DELTA..times..times..times..DELTA..times..times..t-
imes..times..times..DELTA..times..times..times..DELTA..times..times.
##EQU00022## where the round( ) function rounds up or down to the
nearest integer. The time lag 67 (FIG. 2D), .DELTA.t.sub.0v, is
the amount by which the end time of PRN code chip C(.mu..sub.v-L)
lags the first sample time of data word W.sub.v. The algorithm that
iteratively determines k.sub.fv tries to keep the relationship in
equation (47) exact, but using only integer operations can allow
small errors to build up. Note that k.sub.fvlm.sub.f.apprxeq.k.sub.vlm,
as implied by a comparison of equations (32) and (47). This relationship
can be used to determine k.sub.v from an iteratively determined
k.sub.fv. Several constants are required by the iterative procedure
that determines k.sub.fv, k.sub.v and .mu..sub.v. The first five
constants are used to account for the difference between the nominal
chip length .DELTA.t.sub.cnom, used to generate the x(i) tables,
and the actual chip length 65 (FIG. 2D), .DELTA.t.sub.c used in
the accumulation: k.sub.fmid=round[(n.sub.s-1)m.sub.f/2] (48a)
.lamda..DELTA..times..times..DELTA..times..times..DELTA..times..times..tim-
es..times..times..function..times..times..lamda..times..times..times..time-
s..lamda..times..times..times..DELTA..times..times..DELTA..times..times..f-
unction..function..times..times..lamda..function..times..times..DELTA..tim-
es..times..noteq..DELTA..times..times..times. ##EQU00023## a.sub.fix=round(.lamda.b.sub.fix)
(48e) where the sign( ) function returns +1 if its input argument
is positive, zero if the argument is zero, and -1 if the argument
is negative. The index k.sub.fmid is approximately half the length
of a data word as measured in units of .DELTA.t.sub.f seconds. During
an accumulation, the rational factor a.sub.fix/b.sub.fix gets multiplied
by the time offset between the end time of the first code chip a |