# Patent

## Title
Signal receiver having signal acquisition at low signal strength using interleaved time segments

## Abstract

A GPS receiver and method using alternating “A” and “B” integration time segments. The polarities of certain GPS data bits are known beforehand and their expected reception times are known. The GPS signal in 10 millisecond “A” time segments and “B” time segments is depolarized according to the known polarities. The depolarized GPS signal during an “A” time period made up of all the “A” time segments is integrated for providing an “A” time period magnitude for each code phase. Likewise, the depolarized GPS signal during a “B” time period made up of all the “B” time segments is integrated for providing a “B” time period magnitude for each potential GPS code phase. The strongest of the time period magnitudes is compared to a correlation threshold for selecting a code phase for signal acquisition.

## Background
CROSS REFERENCE TO RELATED APPLICATIONS
This application is a continuation of application Ser. No. 09/860,125 filed May 17, 2001, now U.S. Pat. 6,990,140 by the same inventor and assigned to the same assignee.


BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates generally to a global positioning system (GPS) receiver and more particularly for a GPS receiver integrating a GPS signal for an “A” time period having “A” time segments and integrating the GPS signal for a “B” time period having “B” time segments, where the “A” time segments and the “B” time segments alternate, for signal acquisition at a low signal strength.
2. Description of the Prior Art
The global positioning system (GPS) is a system using GPS satellites for broadcasting GPS signals having information for determining location and time. Each GPS satellite broadcasts a GPS signal having 20 milliseconds (ms) GPS data bits modulated by a 1 ms pseudorandom noise (PRN) code having 1023 bits or chips. The PRN code for each GPS satellite is distinct, thereby enabling a GPS receiver to distinguish the GPS signal from one GPS satellite from the GPS signal from another GPS satellite. The 20 ms GPS data bits are organized into a frames of fifteen hundred bits. Each frame is subdivided into five subframes of three hundred bits each.
Typically, when the GPS receiver is first turned on, it knows its own approximate location, an approximate clock time, and almanac or ephemeris information for the locations-in-space of the GPS satellites as a function of clock time. The GPS receiver processes the approximate time, its approximate location, and the almanac or ephemeris information to determine which of the GPS satellites should be in-view and generates one or more GPS replica signals having carrier frequencies and a pseudorandom noise (PRN) codes matching the estimated Doppler frequencies and the PRN codes of one or more of the in-view GPS satellites. The GPS receiver correlates the carrier frequency, the PRN code, and the PRN code phase of the incoming GPS signal to the replica signals and then accumulates a correlation level. The process of correlation and accumulation may need to be repeated many times until a correlation level is found that exceeds a correlation threshold, thereby indicating GPS signal acquisition for the frequency, code, and code phase of the replica signals.
The incoming GPS signal has a low signal-to-noise ratio because of the spreading effect of the PRN code. The effect of the correlation and accumulation process for despreading 1 ms or an epoch of the spread GPS signal is to increase the signal-to-noise in order to be able to recognize the GPS data bits. This increase in signal-to-noise that results from the despreading is termed processing gain. Additional processing gain can sometimes be achieved by correlating and accumulating several epochs of the PRN code.
When signal acquisition is achieved the GPS receiver monitors the GPS data bits until a hand over word (HOW) at the start of the subframe is recognized. When the HOW is recognized, the GPS receiver reads time of week (TOW) in the GPS data bits in the HOW to learn a GPS-based clock time. A current precise location-in-space of the GPS satellite is then calculated from the GPS-based clock time and the ephemeris information. The code phase of the GPS replica signal is then used to calculate a pseudorange between the location of the GPS receiver and the location-in-space of the GPS satellite. Typically, the ephemeris information is retained in memory in the GPS receiver from a previous operational mode or is determined by reading additional GPS data bits. The geographical location fix is derived by linearizing the pseudorange about the range between the location-in-space of the GPS satellite and the approximate location of the GPS receiver and then solving four or more simultaneous equations having the locations-in-space and the linearized pseudoranges for four or more GPS satellites.
The global positioning system is commonly used for determining geographical location and/or time in commercial applications including navigation, timing, mapping, surveying, machine and agricultural control, vehicle tracking, and marking locations and time of events. Given such wide commercial application, it is clear that GPS receivers provide a good value for many users. However, the global positioning system has been limited in several potential applications because existing GPS receivers are unable to acquire a GPS signal unless the GPS signal has a relatively clear line of sight to the GPS satellites ensuring strong GPS signals. Typically, this is not a problem where the GPS receiver is mounted on a platform such as a ship, airplane, farm tractor, or a vehicle traveling on an open highway. However, the signal strength requirements of GPS receivers make it difficult to use GPS indoors or where the GPS signal may be weak due to the attenuation of passing through buildings or trees.
In order to increase the strength of the GPS signal within the GPS receiver, workers in the art use techniques for increasing the processing gain above the standard processing gain that occurs by despreading a single epoch of the 1 ms PRN code. For example, the additional processing gain for integrating (correlating and accumulating) ten coherent epochs is 10 log1010=10 decibels (dB) and the increased processing gain for one-hundred coherent epochs is 10 log10100=20 decibels (dB). It would seem that one should increase the number of despread epochs indefinitely until enough processing gain is achieved for overcoming the GPS signal attenuation caused by buildings and trees. Unfortunately, every 20 ms the C/A PRN code may be inverted with a new GPS data bit, thereby nullifying the processing gain for integration times beyond 20 ms. Accordingly, there continues to be a need for improvements in GPS receivers and methods for acquisition of weak GPS signals.
SUMMARY OF THE INVENTION
Briefly, an object of the present invention is to acquire a signal having data bits spread by a spreading code even when the spread spectrum signal is weak by integrating the signal in separate interleaved time periods termed “A” and “B” time periods where the “A” time period includes “A” time segments and the “B” time period includes “B” time segments that alternate with the “A” time segments. Known polarities of expected data bits having a known expected reception time period are used to invert or not invert (depolarize) the signal separately for each time segment. By constructing the time segments to be one-half a data bit period, at least one of the “A” and “B” time segments avoids transitions in the GPS data bits, thereby enabling a continuous integration without the nullifying effect of inversions of the data bits. A preferred embodiment of the present invention is described in terms of a spread spectrum global positioning system (GPS) signal. In order to more easily follow the summaries of embodiments, the reader may first want to refer to FIGS. 6A–E.
In a preferred embodiment of the present invention, the polarities of certain 20 millisecond (ms) GPS data bits are known beforehand and their expected reception times are known to within ±10 ms. “A” time segments of 10 ms and “B” time segments of 10 ms alternate. The GPS signal in each of the 10 ms “A” time segments is depolarized according to the known polarities of the expected GPS data bits. Likewise, the GPS signal each of the 10 ms “B” time segments is depolarized according to the known polarities of the same GPS data bits. After accounting for polarities of the expected data bits, the GPS signal during an “A” time period including all the 10 ms “A” time segments is coherently integrated (accumulated) for providing an “A” time period magnitude for each potential code phase of a pseudorandom (PRN) spreading code of the GPS signal. Likewise, the GPS signal during a “B” time period including all the 10 ms “B” time segments is coherently integrated for providing a “B” time period magnitude for each potential GPS code phase. The strongest of the time period magnitudes is detected and then compared to a correlation threshold. When the threshold is exceeded, the GPS code phase that yielded the strongest time period magnitude is used for GPS signal acquisition.
The “A” time period may also include “A” augmentation time segments corresponding to certain “B” time segments when consecutive data bits have no change in polarity. Likewise, the “B” time period may also include certain “B” augmentation time segments corresponding to certain “A” time segments when consecutive data bits have no change in polarity.
In a time domain version of the embodiment, the GPS signal is integrated by accumulating correlation levels for the “A” time period and the “B” time period at each potential code phase for providing the “A” time period magnitudes and the “B” time period magnitudes, respectively. In a frequency domain version of the embodiment, the “A” time period magnitudes and the “B” time period magnitudes are integrated for each potential code phase using fast Fourier transform (convolution) techniques.
Each of the 10 ms “A” and “B” time segments includes 10 epochs for the 1 ms GPS spreading code. An advantage of the present invention is that a large signal processing gain is achieved due to the length of time of the “A” time period (or the “B” time period), thereby improving the probability of rapid acquisition of a weak signal.
The present invention can be extended to a number N of types of alternating time segments, where the “A” and “B” alternating time segments represents an embodiment for N=2. For example for N=4 (FIG. 6F), “A”, “B”, “C”, and “D” time segments, each time segment having one-half a data bit time period, alternate for an expected reception time period for a sequence of known data bits. Increasing the number N of types of time segments allows a tradeoff that increases the tolerance for time error at the expense of reducing the processing gain.
These and other objects and advantages of the present invention will no doubt become obvious to those of ordinary skill in the art after having read the following detailed description of the preferred embodiments which are illustrated in the various figures.



IN THE DRAWINGS
FIGS. 1A and 1B are flow charts of alternative methods of the present invention for acquiring spread spectrum signals using “A” and “B” time periods;
FIG. 2 is a block diagram of a GPS receiver of the present invention using “A” and “B” time periods;
FIG. 3 is a block diagram of a time domain correlation machine for a GPS receiver of the present invention;
FIG. 4 is a block diagram of a frequency domain correlation machine for a GPS receiver of the present invention;
FIG. 5 is a block diagram of an AB processor of the present invention for the correlation machines of FIGS. 3 and 4;
FIGS. 6A and 6B are time charts showing “A” and “B” time segments for a continuous expected reception time period and a discontinuous expected reception time period, respectively, for the present invention;
FIG. 6C is a time chart showing “A” and “B” augmentation time segments for the present invention;
FIGS. 6D and 6E are time charts for time errors of 5 and 10 milliseconds, respectively, showing “A” and “B” time period magnitudes for the present invention;
FIG. 6F is a time chart showing “A”, “B”, “C”, and “D” time segments for the present invention;
FIGS. 7A–I are flow charts showing first through ninth embodiments, respectively, having first through ninth arrangements, respectively, for depolarizing, separating, and integrating an incoming signal for the present invention;
FIG. 8 is a block diagram of an N processor of the present invention for N types of time periods; and
FIG. 9 is a block diagram of a GPS receiver of the present invention using N types of time periods.



DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS
The FIGS. 1A and 1B are flow charts illustrating variations of the present invention for fast acquisition of weak global positioning system (GPS) signals. At the start, GPS-based time is known beforehand to within one-half the time periods of the GPS data bits; the polarities of a sequence of GPS data bits are known beforehand (stored sequence 122, FIG. 2); and ephemeris information is known or obtained. A method of the present invention is used for acquiring the GPS signal for a first GPS satellite. Then, the method of the present invention or conventional methods may be used for acquiring the GPS signal from other GPS satellites for determining a location fix.
Referring to FIG. 1A, in a step 52 the incoming GPS signal is received. In a step 54 the GPS signal is downconverted. In a step 56 the start of an expected reception time period for an incoming sequence of certain expected GPS data bits is detected. The expected reception time period may be wider than the time period for the incoming sequence in order to accommodate the time delays for differing distances to GPS satellites. In a step 58, the downconverted GPS signal is sampled and a representation of the GPS signal is stored during the expected reception time period. In a step 62 the expected reception time period associated with the stored signal representation is organized into alternating “A” time segments and “B” time segments as shown in FIGS. 6A–E and described in the accompanying detailed descriptions below.
The stored signal representation is depolarized in a step 64 for the polarities of the stored sequence (122, FIG. 2). In a step 66 an appropriate Doppler frequency is chosen and the depolarized signal representation is integrated (coherently accumulated) for each potential GPS code phase for an “A” time period including all the “A” time segments. Similarly, in a step 68 the depolarized signal representation is integrated (coherently accumulated) using the Doppler frequency for each potential GPS code phase for the “B” time period including all the “B” time segments. The signal integrations for the “A” time period provide “A” time period magnitudes corresponding to the potential code phases, respectively, and the signal integrations for the “B” time period provide “B” time period magnitudes corresponding to the same potential code phases, respectively. Then, in a step 70 the code phase increment that results in the strongest of the “A” time period magnitudes, the “B” time period magnitudes, or combination of the “A”: and “B” time period magnitudes at the same code phase increment is tested against a correlation threshold and used for signal acquisition when the correlation threshold is exceeded. In order to find a time period magnitude that exceeds the correlation threshold the steps 66, 68, and 70 may be iterated using different assumptions for carrier frequency.
Referring to FIG. 1B, the steps 52–62 are described above in the detailed description of FIG. 1A. Then, in a step 72 the stored signal representation is integrated for the “A” time segments for providing “A” time segment integrations. Similarly, in a step 74 the stored signal representation is integrated for the “B” time segments for providing “B” time segment integrations.
The “A” time segment integrations are depolarized in a step 76 for the polarities of a stored sequence (122 in FIG. 2) representing the incoming sequence of certain expected GPS data bits for the “A” time segments of the expected reception time period. Similarly, in a step 78 the “B” time segment integrations are depolarized for the polarities of the stored sequence (122 in FIG. 2) for the “B” time segments of the expected reception time period.
The “A” depolarized integrations are integrated (coherently accumulated) in a step 82 for the “A” time period including all the “A” time segments for providing the “A” time period magnitudes. Similarly, in a step 84 the “B” depolarized integrations are integrated (coherently accumulated) for the “B” time period including all the “A” time segments for providing the “B” time period magnitudes. The signal integrations for the “A” time period provide “A” time period magnitudes corresponding to the potential code phases, respectively, and the signal integrations for the “B” time period provide “B” time period magnitudes corresponding to the same potential code phases, respectively. Then, in the step 70 described above, the code phase increment that results in the strongest of the “A” time period magnitudes, the “B” time period magnitudes, or a combination of the “A” and “B” time period magnitudes is tested against a correlation threshold and used for signal acquisition and/or tracking when a correlation threshold is exceeded. In order to find a time period magnitude that exceeds the correlation threshold the steps 72–84 and 70 may be iterated using different assumptions for carrier frequency.
The FIGS. 1A and 1B and the accompanying descriptions illustrate and describe variations according to the present invention in the order of the steps for depolarizing and integrating the representations of the GPS signal. For the present invention, the GPS signal is integrated in one or more steps for the 10 ms “A” and the 10 ms “B” time segments and then the “A” and “B” time segment integrations are integrated (coherently accumulated) for the “A” and “B” time periods. The step of depolarizing may be applied to a representation of the GPS signal before the 10 ms integrations, within stages of the 10 ms integrations of the individual “A” and “B” time segments, to a GPS replica signal used in the 10 ms integrations, or to the “A” and “B” time segments before the 10 ms integrations are integrated (coherently accumulated) for the “A” and “B” time periods. Also in variations of the present invention, the separation of the processing for the “A” and “B” time segments may be made at any point before or after the depolarization up to the integration of the “A” time segments into the “A” time period and the integration of the “B” time segments into the “B” time period.
FIG. 2 is a block diagram of a signal receiver of the present invention referred to by a general reference number 100. The receiver 100 is described in terms of a global positioning system (GPS) receiver for receiving incoming coarse/acquisition (C/A) GPS signals. However, those of ordinary skill the art of spread spectrum radio receivers will see that the block diagram illustrated in FIG. 2 and described below can be applied for receiving other types of signals, especially for receiving other types of direct fast sequence spread spectrum signals including precision P or P(Y) code GPS signals.
The GPS receiver 100 includes a GPS antenna 102, a frequency downconverter 104, a sampler 106, a stored signal memory 108, a correlation machine 112, a microprocessor 114, and a program memory 116. The GPS antenna 102 converts incoming airwave GPS signals from GPS satellites or pseudolites to conducted GPS signals and passes the conducted GPS signals to the frequency downconverter 104. The frequency downconverter 104 includes a reference generator 105, local oscillators deriving their frequencies from the reference generator 105, and mixers for downconverting the GPS signals to a lower frequency and passing the lower frequency GPS signals to the sampler 106. The sampler 106 samples the downconverted GPS signals for providing in-phase (I) and quadrature phase (Q) samples. The signal memory 108 stores the I and Q samples for a selected time period as a stored signal representation for later use by the correlation machine 112. In an alternative embodiment the correlation machine 112 processes a representation of the incoming signal in real time as it arrives.
The correlation machine 112 integrates the signal representation for providing correlation magnitudes corresponding to code phases, respectively, of the pseudorandom noise (PRN) spreading code in the GPS signal. Typically, the correlation machine 112 has several independent channels where each channel processes the stored signal representation the GPS signal for one GPS satellite at a time. For example, a 12 channel correlation machine 112 could be aligned for acquiring and/or tracking GPS signals from 12 GPS satellites, respectively, or each channel of the correlation machine 112 could be aligned for sharing the task of acquiring and/or tracking the GPS signal from one GPS satellite or several channels could be aligned for acquiring the GPS signal from several GPS satellites while several channels are aligned for acquiring and/or tracking the GPS signal from one GPS satellite. The expected reception time period for the stored signal representation for each GPS satellite is offset in time several milliseconds depending upon the location of the GPS satellite transmitting the signal.
The microprocessor 114 reads programmed instructions in the program memory 116 for controlling the elements of the GPS receiver 100. The program memory 116 includes a stored sequence 122, an acquisition detector 124, and a signal and navigation program 126. The stored sequence 122 includes data for known polarities of certain expected GPS data bits having respective expected reception times. In a preferred embodiment, the stored sequence 122 includes expected GPS data bits forming a continuous sequence for a continuous expected reception time period. However, the stored sequence 122 can be any two GPS data bits, either contiguous or separated, having known polarities and expected reception times. The acquisition detector 124 includes instructions for using the correlation magnitudes from the correlation machine 112 for determining the code phase of the PRN spreading code to use for GPS signal acquisition. The signal and navigation program 126 includes instructions for directing the microprocessor 114 for signal acquisition, signal tracking, location and time fixes, and control for the functions of the GPS receiver 100.
The GPS receiver 100 also includes an expected sequence timer 132, and an AB timer 134. The sequence timer 132 uses the reference generator 105 for maintaining GPS time to within ±10 ms for gating the sampler 106 and/or the signal memory 108 for storing the sampled downconverted GPS signal during the expected reception time period. There are several ways in which GPS time can be maintained to within ±10 ms. For relatively short periods of time, for example a few hours to a few days, an accurate GPS-based time can be maintained with an accurate temperature controlled clock. For longer periods of time, an accurate GPS-time can be received in a time signal transmitted from a time source. The sequence timer 132 also triggers the AB timer 134 for generating AB time segment signals for organizing the expected reception time period into alternating 10 ms “A” time segments and 10 ms “B” time segments as illustrated in FIGS. 6A–E and described in the accompanying detailed description below. Typically, the “A” and “B” time segments for one GPS satellite are offset in time from the “A” and “B” time segments for another GPS satellite in order to accommodate different distances to the satellites.
The correlation machine 112 includes an AB processor 136. The AB processor 136 provides “A” time period magnitudes for an “A” time period having accumulated integrations for the “A” time segments (and “A” augmentation time segments described below) and provides “B” time period magnitudes for a “B” time period having accumulated integrations for the “B” time segments (and “B” augmentation time segments described below). The correlation machine 112 including the AB processor 136 integrates the stored signal representation of the GPS signal during the “A” time period for providing an “A” time period magnitude for each potential GPS code phase and during the “B” time period for providing a “B” time period magnitude for each potential GPS code phase.
A replica generator 138 preferably included in the correlation machine 112 generates GPS replica signals for the carrier frequency and the spreading code of the GPS signals as represented by the stored signal representation of the GPS signals. The C/A code of the GPS signal has a 1023 bit or chip spreading code. The replica generator 138 issues a replica signal for all 1023 chips either in the time or frequency domain for both I and Q in one-half chip or smaller increments of code phase. The correlation machine 112 in a preferred embodiment provides I and Q correlation levels in increments that are slightly less than one-half chip. Preferably about 2048 code phase increments are provided for 1 and about 2048 code phase increments are provided for Q to the AB processor 136. During the “A” time period, the AB processor 136 accumulates and combines the I and Q levels for providing the “A” time period magnitudes; and during the “B” time period, the AB processor 136 accumulates and combines the I and Q levels for providing the “B” time period magnitudes. The correlation machine 112 and integration process are illustrated and described in greater detail in FIGS. 3–4 and the accompanying descriptions below.
The “A” time period magnitudes and the “B” time period magnitudes from the correlation machine 112 are processed by the microprocessor 114 using instructions in the acquisition detector 124 for determining the increment of code phase for the replica code that appears to match the code phase of the incoming GPS signal. This replica code phase is then processed for GPS signal acquisition by the microprocessor 114 according to instructions in the signal and navigation program 126.
There are several embodiments for the acquisition detector 124 that can process the “A” and “B” time period magnitudes in order to find the code phase for acquisition. In a preferred embodiment, the strongest of the time period magnitudes, whether one of the “A” time period magnitudes or the “B” time period magnitudes, is tested against a correlation threshold. In another preferred embodiment, the “A” time period magnitude and the “B” time period magnitude for a code phase are combined (incoherently) or their squares are added to form an AB time period magnitude for that code phase. When the strongest combined time period magnitude exceeds the correlation threshold, the code phase that resulted in that combined time period magnitude is used for signal acquisition and tracking. Once the code phase for acquisition of the GPS signal from a single GPS satellite is determined, conventional methods can be used for acquiring the GPS signal from other GPS satellites. When the strongest magnitude does not exceed the required correlation threshold, then a different Doppler frequency, a different PRN code, a different GPS time, or the like is tried and the process is repeated; or the GPS receiver 100 may go into a standby mode to conserve power.
The stored sequence 122 may be a fixed sequence stored in the program memory 116. However, typically the stored sequence 122 is calculated depending upon recent information and then stored in the program memory 116 after calculation. One sequence of GPS data bits that can be used for the stored sequence 122 is the time-of-week (TOW) in the hand-over-word (HOW) that is broadcast in each subframe of the GPS signal. The TOW is the 17 most significant bits (MSB)s corresponding to a TOW-count at the epoch which occurs at the leading edge of the next following subframe. The polarities of this sequence of 17 bits are known by knowing the GPS-based time which is maintained by the GPS receiver 100 to within ±10 ms for use by the expected sequence timer 132. The 17 bits of the TOW result in a total expected reception time period of about 340 ms. Extra time may be required time error or to account for early and late edges times. Those skilled in the art will be able to determine other sequences within the GPS subframes that can be used. A more complete understanding of the HOW and TOW and other sequences within the GPS signal is available in published form from Navtech Seminars & Navtech Bookstore and Software Store, of Arlington, Va., under title of GPS Interface Control Document ICD-GPS-200 which is incorporated herein by reference.
The expected GPS data bits do not need to be continuous or consecutive. For non-consecutive data bits, the sequence timer 132 provides triggers to the AB timer 134 for the expected reception time period for each section of the stored sequence 122. However, it should be understood that a wider separation between the beginning of the first time segment and the end of the last time segment results in a narrower carrier frequency range of the GPS signal for the correlation process. When the carrier frequency range is narrow, the integration process may need to be iterated for many carrier center frequencies before a satisfactory code phase is found for signal acquisition. Preferably, the reference generator 105 generates a reference signal having a stable frequency and a capability of being updated or stabilized further with a frequency standard signal transmitted from a frequency standard source.
Using more than two types for sequential 10 ms time segments reduces the requirement for accurate time but also reduces the signal processing gain. Doubling the number of types of time segments halves the time accuracy requirement. For example, four types of alternating 10 ms time segments (“A” then “B” then “C” then “D” then “A” again and so on) could be used for reducing the time accuracy requirement to ±20 ms but also reduces the total time for any one of the “A”, “B”, “C”, and “D” time periods by a factor of two, thereby reducing the signal processing gain. A time chart illustrating “A”, “B”, “C”, and “D” alternating time segments is shown in FIG. 6F and described in the accompanying detailed description.
FIG. 3 is a block diagram showing the signal memory 108 and a time domain correlation machine 112A that is an embodiment of the correlation machine 112 described above. The block diagram of the correlation machine 112A shows depolarizers 143–149 in optional placements within the correlation machine 112A. One of the depolarizers 143–149 depolarizes a representation of the GPS signal by inverting the GPS signal representation for one polarity for a GPS data bit in the stored sequence 122 and not inverting the GPS signal representation for the other polarity. Only one of the depolarizers 143–149 at only one of the placements is used in any one embodiment.
The block diagram of the correlation machine 112A illustrates a single channel for determining “A” and “B” time period magnitudes for respective code phases. However, a preferred embodiment of the GPS receiver 100 will include several such channels in the correlation machine 112A where each channel operates effectively in parallel.
The correlation machine 112A includes a replica generator 138A that is a version of the replica generator 138 described above. The replica generator 138A includes a carrier numerically controlled oscillator (NCO) 152, a code numerically controlled oscillator (NCO) 154, a pseudorandom (PRN) coder 156, and a code phase shifter 158. The carrier NCO 152, code NCO 154, PRN coder 156, and code phase shifter 158 are controlled by the microprocessor 114. The carrier NCO 154 issues I and Q replica carrier signals for the expected carrier frequency of the downconverted GPS signal. The code NCO 154 issues a code rate signal for the expected code rate of the GPS signal to the PRN coder 156. The PRN coder 156 generates a selected PRN code at the repetition rate of the code rate signal. The selected PRN code may be selected to be different or the same for each of the channels of the correlation machine 112A depending upon the status of the GPS receiver 100. The code phase shifter 158 issues I and Q replica versions of the PRN code in sample increments of code phase of preferably one-half chip at a controlled code phase. In order to determine the correct code phase for signal acquisition, the code phase shifter 158 shifts the PRN code in shift increments of code phase that are one-half chip or smaller, preferably one-half chip. Alternatively, the code phase shifter 158 is not required if the PRN coder 156 issues I and Q replica code signals for incremental code phase shifts in parallel.
The correlator machine 112A also includes I and Q carrier multipliers 162, and I and Q code multipliers 164. Although only one set of carrier multipliers 162 and one set of code multipliers 164 are shown, several sets may be included for faster parallel processing. Multiple code multipliers 164 are required where the replica code signal includes the code phase shifts in parallel. The correlation machine 112A also includes I and Q accumulators 166 and the AB processor 136 (or an N processor 800, FIGS. 8–9). The processing of the I samples from the signal memory 108 will now be described with the understanding that the Q samples are processed in the same way. The I carrier multiplier 162 correlates I samples from the signal memory 108 with the I samples of the replica carrier signal from the carrier NCO 152 for providing an I baseband (or pseudo-band) representation of the GPS signal. The I code multiplier 164 correlates the I baseband signal with the I replica PRN code from the code phase shifter 158 for providing I code correlations to the I accumulator 166 for each increment of code phase at the current increment of replica code phase shift.
The I accumulator 166 despreads the GPS signal by accumulating (integrating) the I code correlations for the current increment of replica code phase shift for a selected time period, preferably either one complete code time period at 1 ms for ten times or ten complete code periods at 10 ms for one time. For the example of slightly less than one-half chip incremental code phase shift for the 1023 chip C/A PRN code, for either 1 ms or 10 ms correlation time periods, the I accumulator provides preferably about 2048 I integrations. The accumulated I integrations are then passed to the AB processor 136 (or an N processor 800, FIGS. 8–9). The same process is followed for the Q GPS signal representations for providing accumulated Q integrations to the AB processor 136 (or N processor 800, FIGS. 8–9).
The depolarized replica signal is used within the correlation machine 112A for depolarizing a representation of the incoming signal. The placement of the depolarizer 143 shows an optional placement for depolarizing the I and Q replica carrier signal from the carrier NCO 152 for providing a depolarized replica signal. The placement of the depolarizer 144 shows an optional placement for depolarizing the PRN code from the PRN coder 156 for providing a depolarized replica signal. The placement of the depolarizer 145 shows an optional placement for depolarizing the I and Q PRN codes from the code phase shifter 158 for providing a depolarized replica signal. The placement of the depolarizer 146 shows an optional placement for depolarizing the I and Q stored signal representation from the signal memory 108. The placement of the depolarizer 147 shows an optional placement for depolarizing the I and Q baseband GPS signal from the carrier multipliers 162. The placement of the depolarizer 148 shows an optional placement for depolarizing the I and Q correlations from the code multipliers 164. The placement of the depolarizer 149 shows an optional placement for depolarizing the I and Q integrations from the accumulator 168.
FIG. 4 is a block diagram showing the signal memory 108 and a frequency domain correlation machine 112B that is an embodiment of the correlation machine 112 described above. The block diagram of the correlation machine 112B shows the depolarizers 143–144 and 146–147 described above, and a depolarizer 172 in optional placements within the correlation machine 112B. One of the depolarizers 143–144, 146–147, or 172 depolarizes a representation of the GPS signal by inverting the GPS signal representation for one polarity for a GPS data bit in the stored sequence 122 and not inverting the GPS signal representation for the other polarity. Only one of the depolarizers 143–144, 146–147, and 172 at only one of the placements is used in any one embodiment.
The block diagram of the correlation machine 112B illustrates a single channel for determining “A” and “B” time period magnitudes for respective code phases. However, a preferred embodiment of the GPS receiver 100 will include several such channels in the correlation machine 112B where each channel operates effectively in parallel.
The correlation machine 112B includes a replica generator 138B that is a version of the replica generator 138 described above. The replica generator 138B includes the carrier NCO 152, the code NCO 154, and the PRN coder 156 as described above, and a replica fast Fourier transformer 174. The replica fast Fourier transformer (FFT) 178 performs a complex fast frequency transform on the PRN code from the PRN coder 156 for providing frequency domain I and Q replica code signals corresponding to increments of code phase of preferably one-half chip.
The correlator machine 112B also includes the I and Q carrier multipliers 162 described above, a signal fast Fourier transformer (FFT) 176, I and Q code multipliers 178, an inverse fast Fourier transformer (IFFT) 180, and the AB processor 136 (or N processor 800, FIGS. 8–9). The signal FFT 176 performs a complex fast Fourier transform on the I and Q baseband signals from the I and Q carrier multipliers 162 for providing frequency domain I and Q baseband signals. The I code multiplier 178 multiplies the frequency domain I baseband signal by the frequency domain I replica code signal for providing a frequency domain I despread GPS signal to the IFFT 180. Similarly, the Q code multiplier 178 multiplies the frequency domain Q baseband signal by the frequency domain Q replica code signal for providing a frequency domain Q despread GPS signal to the IFFT 180. The IFFT 180 performs a complex inverse fast Fourier transform on the frequency domain I and Q despread GPS signals for providing I and Q correlation levels for all potential code phase increments in parallel for a selected time period of preferably 10 ms. For an example of slightly less than one-half chip increments of replica code, for the 1023 chip C/A PRN code, the IFFT 180 preferably provides about 2048 I integrations and about 2048 Q integrations. The I and Q correlation levels are then passed to the AB processor 136 (or N processor 800, FIGS. 8–9).
The placement of the depolarizer 172 shows an optional placement for depolarizing the I and Q integrations after the IFFT 180. The depolarizers 143–144 and 146–147 are optionally placed within the correlation machine 112B as described above in the detailed description accompanying FIG. 3 for the correlation machine 112A.
FIG. 5 is a block diagram of the AB processor 136 of the present invention for receiving I and Q integrations from the I and Q accumulators 166 of the time domain correlation machine 112A or the IFFT 180 of the frequency domain correlation machine 112B. One of the depolarizers 143–149 or 172 is in place so that the I and Q integrations, are depolarized according to the polarities in the stored sequence 122.
The AB processor 136 includes an AB switch 202, accumulators 206–209, an “A” combiner 212, and a “B” combiner 214. The AB switch 202 separates a representation of the incoming signal into the “A” time period and the “B” time period. The “A” time period includes “A” time segments and “A” augmentation time segments (FIG. 6A–E). The “B” time period includes “B” time segments and “B” augmentation time segments (FIG. 6A–E). There are several variations (FIGS. 7A–I) of the present invention regarding the placement of the AB switch 202 within the GPS receiver 100 for separating the incoming signal according to the “A” and “B” time periods. In one variation the AB switch 202 separates the stored signal representation where the stored signal representation enters the correlation machine 112 from the signal memory 108. In this variation the correlation machine 112 integrates the stored signal representation for the “A” time period separately from the stored signal representation for the “B” time period. In another variation the AB switch 202 is disposed within the correlation machine 112 so that signal can be processed in time periods of up to the 10 ms time periods of the “A” and “B” time segments before the AB switch 202.
In a preferred embodiment, the AB switch 202 includes an I AB switch 202I and a Q AB switch 202Q. The I AB switch 202I receives the depolarized I integrations from the I accumulator 166 for the time domain correlation machine 112A or the IFFT 180 for the frequency domain correlation machine 112B. Similarly, the Q AB switch 202Q receives the depolarized Q integrations from the Q accumulator 166 for the time domain correlation machine 112A or the IFFT 180 for the frequency domain correlation machine 112B. In FIG. 5, the I AB switch 202I and the Q AB switch 202Q are shown for the “A” time period.
For the “A” time period, the I AB switch 202I passes the depolarized I integrations to the accumulator 206. For the “B” time period, the I AB switch 202I passes the depolarized I integrations to the accumulator 207. The accumulator 206 accumulates the depolarized I integrations for the “A” time period for providing an “A” I magnitude accumulation for each code phase. The accumulator 207 accumulates the depolarized I integrations for the “B” time period for providing a “B” I magnitude accumulation for each code phase.
The Q AB switch 202Q for the “A” time period passes the depolarized Q integrations to the accumulator 208. For the “B” time period the Q AB switch 202Q passes the depolarized Q integrations to the accumulator 209. The accumulator 208 accumulates the depolarized Q integrations for the “A” time period for providing an “A” Q magnitude accumulation for each code phase. The accumulator 209 accumulates the depolarized Q integrations for the “B” time period for providing a “B” Q magnitude accumulation for each code phase.
The A combiner 212 adds the square of the “A” I magnitude accumulation from the accumulator 206 to the square of the “A” Q magnitude accumulation from the accumulator 208 for each code phase increment for providing the “A” time period magnitudes. The B combiner 214 adds the square of the “B” I magnitude accumulation from the accumulator 207 to the square of the “B” Q magnitude accumulation from the accumulator 209 for each code phase increment for providing the “B” time period magnitudes. At this point for code phase increments of slightly less than one–half chip there will be preferably about 2048 “A” time period magnitudes and about 2048 “B” time period magnitudes. As described above, the code phase increment that results in the strongest of the “A” time period magnitudes, the “B” time period magnitudes, or combination of the “A” and “B” time period magnitudes is tested against a correlation threshold and used for signal acquisition when the correlation threshold is exceeded.
As described above the “A” I and Q magnitude accumulations and “B” I and Q magnitude accumulations are preferably linear functions proportional to the levels for the I and Q integrations of the GPS signal, whereas the “A” and “B” time period magnitudes are preferably proportional to the sum of the squares the I and Q magnitude accumulations (I2+Q2). However, it should be noted that the “A” and “B” time period magnitudes can be some other convenient non-decreasing function of the “A” and “B” I and Q magnitude accumulations, such as the sum (I+Q) or square root of the sum of the squares (√(I2+Q2)).
The “A” and “B” time segments can be processed separately through the correlation machines 112A and 112B. In a variation of the correlation machine 112A, the I carrier multiplier 162, the I code multiplier 164, and the I accumulator 166 integrate representations of the GPS signal for “A” time segments and separately for “B” time segments for providing depolarized I integrations for “A” time segments and depolarized I integrations for “B” time segments, respectively, and likewise for Q. The AB processor 136 then uses the accumulators 206–209 and the combiners 212 and 214 as described above. Similarly, for the correlation machine 112B, the carrier multipliers 162, the signal FFT 176, the code multipliers 178, and the IFFT 180 integrate representations of the GPS signal for “A” time segments and separately for “B” time segments for providing depolarized I integrations for “A” time segments and depolarized I integrations for “B” time segments, respectively, and likewise for Q.
FIGS. 6A–B illustrate the “A” and “B” time segments with respect to exemplary sequences of GPS data bits. Each of the “A” time segments and each of the “B” time segments is preferably about one-half the time length of a data bit. For the exemplary case of C/A GPS, the data bits have a time period of 20 ms, thereby the “A” and “B” time segments preferably have periods of about 10 ms. The “A” time segments start at the start of expected reception time period of the first bit of a known sequence of expected GPS data bits (t=0 ms) for a case where GPS-based time is accurate to within a small portion of a millisecond within the GPS receiver 100. The “A” time segments and then repeat each 20 ms thereafter for the expected reception time period. The “B” time segments start 10 ms later (t=10 ms) and repeat 20 ms thereafter for the expected reception time period in order to alternate with the “A” time segments. FIG. 6A shows the expected reception time period for a continuous sequence of expected GPS data bits. FIG. 6B shows the expected reception time period for a discontinuous sequence of expected GPS data bits. The “A” time period includes only those “A” time segments for the expected GPS data bits while leaving a gap for the time period between the expected GPS data bits and likewise the “B” time period includes only those “B” time segments for the expected GPS data bits while leaving a gap for the time period between the expected GPS data bits.
FIG. 6C shows the “A” and “B” time segments numbered A1–11 and B1–11, respectively, in positions with respect to the sequence of expected data bits for a locally maintained GPS-based time that is exactly accurate. For an error in the GPS-based time of up to plus or minus 10 ms, it can be seen that the B4, the B8, and the B9 time segments denoted with asterisks (*), termed herein “A” augmentation time segments, correspond to the same polarity in the sequence as they have for the exactly correct time. Accordingly, in order to increase processing gain of the “A” time period magnitudes, the “A” time period can be constructed to include not only the A1–A11 time segments but also the “A” augmentation time segments B4*, B8*, and B9*. Similarly, for an error in the GPS-based time of up to plus or minus 10 ms, it can be seen that the A5, the A9, and the A10 time segments denoted with asterisks (*), termed herein “B” augmentation time segments, correspond to the same polarity in the sequence as they have for the exactly correct time. Accordingly, in order to increase processing gain of the “B” time period magnitudes, the “B” time period can be constructed to include not only the B1–B11 time segments but also the “B” augmentation time segments A5*, A9*, and A10*.
FIGS. 6D and 6E show the effect of a locally maintained GPS-based time that is late by 5 and 10 milliseconds, respectively, with respect to the sequence of expected data bits. Referring to FIG. 6D the start of the A1 time segment (t=0 ms) is 5 milliseconds after the start of the exemplary sequence. Even though the local time has a time error of 5 milliseconds, all of the “A” time segments A1–11 and the “A” augmentation time segments B4*, B8*, and B9* fall entirely within a data bit having the polarity of the expected data bit for that time segment. The depolarized incoming signal is integrated and when the correct code phase is used, the integration in the “A” time period is shown by a line referred to as “A” integration. The “A” integration increases monotonically during the “A” time segments A1–11 and “A” augmentation time segments B4*, B8*, and B9* to form the “A” time period magnitude. For example, during the A1 time segment the “A” integration increases, during the B1 time segment the “A” integration is flat, during the A2 time segment the “A” integration increases, and so on until the “A” time period magnitude is reached. Note that the “A” integration increases during the “B” time segments that are used as “A” augmentation time segments B4*, B8*, and B9*.
The B1 time segment in FIG. 6D starts 10 ms after (t=10 ms) after the A1 time segment. The local time error of 5 milliseconds causes all of the “B” time segments B1–11 to straddle the transitions in the 20 ms data bits. When the depolarized incoming signal is integrated and the correct code phase is used, the integration in the “B” time period is shown by a line referred to as “B” integration. The “B” integration increases during the “B” augmentation time segments A5*, A9*, and A10* but has no net increase during the “A” and “B” time segments (except for the “A” time segments that are used as “B” augmentation time segments) to form the “B” time period magnitude. For example, during the A1 time segment the “B” integration is flat, during the B1 time segment the “B” integration increases and then decreases for a net of zero, during the A2 time segment the “B” integration is flat, and so on until the “B” time period magnitude is reached. Note that the “B” integration increases during the “A” time segments that are used as “B” augmentation time segments A5*, A9*, and A10* and the “B” time segments that are used as “A” augmentation time segments B4*, B8*, and B9*.
Referring to FIG. 6E the start of the A1 time segment (t=0 ms) is 10 milliseconds after the start of the exemplary sequence. Even though the local time has a time error of 10 milliseconds, all of the “A” time segments A1–11 and the “A” augmentation time segments B4*, B8*, and B9* fall entirely within a data bit having the polarity of the expected data bit for that time segment. The depolarized incoming signal is integrated and when the correct code phase is used, the integration in the “A” time period is shown by a line referred to as “A” integration. The “A” integration increases monotonically during the “A” time segments A1–11 and “A” augmentation time segments B4*, B8*, and B9* to form the “A” time period magnitude. For example, during the A1 time segment the “A” integration increases, during the B1 time segment the “A” integration is flat, during the A2 time segment the “A” integration increases, and so on until the “A” time period magnitude is reached. Note that the “A” integration increases during the “B” time segments that are used as “A” augmentation time segments B4*, B8*, and B9*.
The B1 time segment in FIG. 6E starts 10 ms after (t=10 ms) after the A1 time segment. The local time error of 10 milliseconds causes all of the “B” time segments B1–11 to fall in the next 20 data bit. When the depolarized incoming signal is integrated and the correct code phase is used, the integration in the “B” time period is shown by a line referred to as “B” integration. The “B” integration increases during the “B” augmentation time segments A5*, A9*, and A10*, is flat during the “A” time segments (except for the “A” time segments that are used for “B” augmentation time segments) but decreases during the “B” time segments (except for the “B” time segments that are also used as “A” augmentation time segments) to form the “B” time period magnitude. For example, during the A1 time segment the “B” integration is flat, during the B1 time segment the “B” integration decreases, during the A2 time segment the “B” integration is flat, and so on until the “B” time period magnitude is reached. Note that the “B” integration increases during the “A” time segments that are used as “B” augmentation time segments A5*, A9*, and A10* and the “B” time segments that are used as “A” augmentation time segments B4*, B8*, and B9*.
For the local GPS-based time that is late with respect to the correct GPS-based time as shown in FIGS. 6D and 6E the “A” time period magnitude is greater than the “B” time period magnitude for 5 and 10 millisecond time errors, respectively. For a local GPS time that is early with respect to GPS-based time the time period magnitudes for “A” and “B” would be reversed and the “B” time period magnitude would be greater than the “A” time period magnitude.
FIG. 6F shows four types of time segments, termed “A”, “B”, “C”, and “D”, for an expected reception time period including the time period for the expected sequence and early and late edge times before and after, respectively, the expected sequence. The “A” time segments are shown as A1, A3, A5, A7, A9, and A11; the “B” time segments are shown as B1, B3, B5, B7, B9, and B11; and so on for “C” and “D” time segments. The first bit of the expected sequence is shown as bit 1; the third bit of the expected sequence is shown as bit 3; and so on with every other bit to bit 11. The time segments A1–11 odd, B1–11 odd, C1–11 odd, and D1–11 odd are shown in time with respect to the expected sequence for a time error of 0 ms. For a time error of 20 ms, the time segments A1–11 odd, B1–11 odd, C1–11 odd, and D1–11 odd shift 20 ms right or left with respect to the expected sequence depending upon the sign of the time error.
The A1, B1, C1, and D1 time segments are depolarized according to the sense of the known polarity for the expected bit 1; the A3, B3, C3, and D3 time segments are depolarized according to the sense of the known polarity for the expected bit 3; and so on to the A11, B11, C11, and D11 time segments depolarized according to the sense of the known polarity for the expected bit 11. The “A” time period magnitudes are the coherent integrations corresponding to code phases, respectively, for the A1, A3, A5, A7, A9, and A11 time segments; the “B” time period magnitudes are the coherent integrations corresponding to code phases, respectively, for the B1, B3, B5, B7, B9, and B11 time segments; and so on for “C” and “D” time period magnitudes.
The four types of time segments (“A”, “B”, “C”, “D”) shown in FIG. 6F can be extended to N time segment types where the time segments of each of the N time segment types alternates or follows one another as shown in FIG. 6F for N =4. Time periods for each of the N time segment types are separately integrated. Any one of the N types of time segments can be known as an Mth type of time segment. An Mth one of the time periods includes the integrations for the Mth type of time segments and may include Mth augmentation time segments.
For N=8 having “A”, “B”, “C”, “D”, “E”, “F”, “G” and “H” time segments, there would be A1, A5, and A9 time segments; B1, B5, and B9 time segments and so on to H1, H5, and H9 time segments. For N=8, the A1 through H1 time segments are arranged symmetrically about and depolarized for the first bit (bit 1) in a sequence, the A5 through H5 time segments are arranged symmetrically about and depolarized for the fifth bit (bit 5) in a sequence, and the A9 through H9 time segments are arranged symmetrically about and depolarized for the ninth bit (bit 9).
It should be seen by inspection that the time segments for at least one of the “A”, “B”, “C”, and “D” time periods coincides with the expected data bits for up to a ±20 ms time error between the time segments based upon the local estimate of GPS-based time and the sequence of expected GPS data bits shown for actual GPS-based time. In addition, the sense of the known polarity of the data bits of the expected sequence does not change for a time error of up to ±20 ms for the B9 and the C9 time segments corresponding to the three consecutive data bits of bit 8, bit 9, and bit 10. Therefore, the B9 and C9 time segments are noted with an asterisk (*) to show that they can be used as “A” augmentation time segments and “D” augmentation time segments for determining the “A” and “D” time period magnitudes as described above for two types of time segments (“A” and “B”). For N=2, “A” and “B” augmentation time segments result from the “B” and “A” time segments corresponding to two consecutive data bits having the same sense; for N=4, “A” and “D” augmentation time segments result from the “B” and “C” time segments corresponding to three consecutive data bits having the same sense; for N=8 (“A”, “B”, “C”, “D”, “E”, “F”, “G” and “H”), “A”, “B”, “C”, “F”, “G” and “H” augmentation time segments result from the “D” and “E” time segments corresponding five consecutive data bits having the same sense; and so on for N, N/2+1 consecutive data bits having the same sense resulting in augmentation time segments for the first N/2−1 and the last N/2−1 types of time segments.
Doubling the number of time segment types halves the time accuracy requirement. For example, the use of four types of time segments (“A”, “B”, “C”, “D”) instead of two types or time segment (“A”, “B”) reduces the requirement for time accuracy from ±10 ms to ±20 ms; and the use of eight types (N=8) reduces the requirement for time accuracy to ±40 ms. However, doubling the number of time segment types also reduces the processing gain by 3 dB. For example, the use of four time segment types (“A”, “B”, “C”, “D”) instead of two time segment types (“A”, “B”) reduces the processing gain by 3 dB.
FIGS. 7A–I are flow charts showing several arrangements for the order in which representations of the incoming GPS signal are depolarized, separated for “A” and “B” time segments, and integrated for providing the “A” and “B” time period magnitudes for the potential code phases of the spreading code of the incoming signal. Although separations of “A” and “B” time segments are shown, it should be recognized that N types of time segments can be separated, for example N=4 for “A”, “B”, “C”, and “D” time segment can be separated in the same way as for N=2 for “A” and “B” time segments. Several of the blocks in FIGS. 7A–I perform integrations of representations of the GPS signal. Those of ordinary skill in the art will appreciate that such integrations can be performed as a single period of time or can be performed in separate periods of time and then coherently accumulated.
In a first embodiment shown in FIG. 7A, a block 702 depolarizes a representation of the incoming signal for the known polarities of the expected GPS data bits for providing a depolarized signal. A block 704 integrates the depolarized signal for time lengths not greater than the time segments for providing depolarized integrations. A block 706 separates the “A” time segments and the “B” time segments for the depolarized integrated signal for providing “A” and “B” depolarized integrations, respectively. Then, a block 708 further integrates (accumulates) the “A” depolarized integrations over the entire “A” time period for providing the “A” time period magnitudes and further integrates (accumulates) the “B” depolarized integrations over the entire “B” time period for providing the “B” time period magnitudes.
In a second embodiment shown in FIG. 7B, a block 710 depolarizes a representation of the incoming signal for the known polarities of the expected GPS data bits for providing a depolarized signal. A block 712 separates the “A” time segments and the “B” time segments for the depolarized signal for providing an “A” depolarized signal and a “B” depolarized signal, respectively. Then, a block 714 integrates the “A” depolarized signal over entire “A” time period for providing the “A” time period magnitudes and integrates the “B” depolarized signal over the entire “B” time period for providing the “B” time period magnitudes.
In a third embodiment shown in FIG. 7C, a block 720 integrates a representation of the incoming signal for time lengths not greater than the time segments for providing first integrations of the signal. A block 722 depolarizes the first integrations for the known polarities of the expected GPS data bits for providing depolarized integrations. A block 724 separates the depolarized integrations according to the “A” and “B” time segments for providing “A” and “B” depolarized integrations, respectively. Then, a block 726 further integrates the “A” depolarized integrations over the entire “A” time period for providing the “A” time period magnitudes and further integrates the “B” depolarized integrations over the entire “B” time period for providing the “B” time period magnitudes.
In a fourth embodiment shown FIG. 7D, a block 730 integrates a representation of the incoming signal for time lengths not greater than the time segments for providing first integrations of the signal. A block 732 separates the first integrations according to the “A” and “B” time segments for providing “A” and “B” depolarized integrations, respectively. A block 734 depolarizes the “A” and “B” integrations for the known polarities of the expected GPS data bits for providing “A” and “B” depolarized integrations, respectively. Then, a block 736 further integrates the “A” depolarized integrations over the entire “A” time period for providing the “A” time period magnitudes and further integrates the “B” depolarized integrations over the entire “B” time period for providing the “B” time period magnitudes.
In a fifth embodiment shown in FIG. 7E, a block 740 separates a representation of the incoming signal according to “A” and “B” time segments for providing “A” and “B” time segment signals, respectively. A block 742 depolarizes the “A” and “B” time segment signals for the known polarities of the expected GPS data bits for providing “A” and “B” depolarized time segment signals, respectively. Then, a block 744 integrates the “A” depolarized time segment signal over the entire “A” time period for providing the “A” time period magnitudes and integrates the “B” depolarized time segment signal over the entire “B” time period for providing the “B” time period magnitudes.
A sixth embodiment shown in FIG. 7F, a block 750 separates a representation of the incoming signal according to “A” and “B” time segments for providing “A” and “B” time segment signals, respectively. A block 752 integrates the “A” and “B” time segment signals for time lengths not greater then time segments for providing “A” and “B” integrations, respectively. A block 754 depolarizes the “A” and “B” integrations for the known polarities of the expected GPS data bits for providing “A” and “B” depolarized integrations, respectively. Then, a block 756 further integrates the “A” depolarized integrations over the entire “A” time period for providing the “A” time period magnitudes and further integrates the “B” depolarized integrations over the entire “B” time period for providing the “B” time period magnitudes.
In a seventh embodiment shown in FIG. 7G, a block 760 integrates a representation of the incoming signal for time lengths less than the time segments for providing first integrations, for example one epoch (1 ms for GPS C/A code). A block 762 depolarizes the first integrations for the known polarities of the expected GPS data bits for providing depolarized first integrations. A block 764 further integrates the depolarized first integrations for time lengths not greater than the time segments, preferably equal to a time segment (10 ms for GPS C/A code), for providing depolarized second integrations of the signal. A block 766 separates the depolarized second integrations according to “A” and “B” time segments for providing “A” and “B” depolarized second integrations, respectively. Then, a block 768 further integrates the “A” depolarized second integrations over the entire “A” time period for providing the “A” time period magnitudes and further integrates the “B” depolarized second integrations over the entire “B” time period for providing the “B” time period magnitudes. The embodiment of FIG. 7G differs from the embodiments of FIGS. 7A, 7C, 7D, 7H, and 7I in that a representation of the GPS signal is depolarized between integration blocks for performing time segment integrations. Those of ordinary skill in the art will note that the embodiment of 7G effectively reduces to one of the embodiments illustrated in FIGS. 7A, 7C, 7D, 7H, and 7I when the depolarization block 762 is placed elsewhere than between the integrations blocks 760 and 764. For example, when the block 762 is moved to a position before the block 760, the embodiment of FIG. 7G reduces to the embodiment illustrated in FIG. 7A.
In an eight embodiment shown in FIG. 7H, a block 770 integrates a representation of the incoming signal for time lengths less than the time segments for providing first integrations, for example one epoch (1 ms for GPS C/A code). A block 772 separates the first integrations according to “A” and “B” time segments for providing “A” and “B” first integrations, respectively. A block 774 depolarizes the “A” and “B” first integrations for the known polarities of the expected GPS data bits for providing “A” and “B” depolarized integrations, respectively. Then, a block 776 further integrates the “A” depolarized integrations over the entire “A” time period for providing the “A” time period magnitudes and further integrates the “B” depolarized integrations over the entire “B” time period for providing the “B” time period magnitudes.
In a ninth embodiment shown in FIG. 7I, a block 780 integrates a representation of the incoming signal for time lengths less than the time segments for providing first integrations, for example one epoch (1 ms for GPS C/A code). A block 782 depolarizes the first integrations for providing depolarized integrations. A block 784 separates the depolarized integrations according to “A” and “B” time segments for providing “A” and “B” depolarized integrations, respectively. Then, a block 786 further integrates the “A” depolarized integrations over the entire “A” time period for providing the “A” time period magnitudes and further integrates the “B” depolarized integrations over the entire “B” time period for providing the “B” time period magnitudes.
FIG. 8 is a block diagram of an N processor of the present invention referred to by a reference number 800 for processing N types of time segments. The N processor 800 for a special case of N=2 is described above as the AB processor 136. FIG. 8 illustrates the N processor 800 for N=4 for processing “A”, “B”, “C”, and “D” types of time segments. The “A”, “B”, “C”, and “D” types of time segments are illustrated in FIG. 6F and described in the accompanying detailed description. The N processor 800 receives I and Q integrations from the I and Q accumulators 166 of the time domain correlation machine 112A or the IFFT 180 of the frequency domain correlation machine 112B. One of the depolarizers 143–149 or 172 is in place for depolarizing the representation of the incoming signal each of the N types of time segments.
The N processor 800 includes an N switch 802, I accumulators 804, Q accumulators 805, and combiners 806. The N switch 802 separates the I and Q integrations for each of the N types of time segments into N types of time periods denoted for N=4 as “A”, “B”, “C”, and “D” time periods. The “A” time period includes “A” time segments and “A” augmentation time segments (FIG. 6F); the “B” time period includes “B” time segments and “B” augmentation time segments; and so on for the “C” and “D” time segments and augmentation time segments. There are several variations (FIGS. 7A–I) of the present invention regarding the placement of the N switch 802 within the GPS receiver 100 for separating the incoming signal. In one variation the N switch 802 separates the stored signal representation where the stored signal representation enters the correlation machine 112 from the signal memory 108. In this variation the correlation machine 112 integrates the stored signal representation for each of the N types of time segments and augmentation time segments separately from each of the other of the N types of time segments and augmentation time segments. In another variation the N switch 802 is disposed within the correlation machine 112 so that signal can be processed in time periods of up to the 10 ms time periods of the time segments before the N switch 802.
In a preferred embodiment, the N switch 802 includes an I N switch 802I and a Q N switch 802Q. In FIG. 8, the I N switch 802I and the Q N switch 802Q are shown for the “B” time period. The I N switch 802I receives the depolarized I integrations from the I accumulator 166 for the time domain correlation machine 112A or the IFFT 180 for the frequency domain correlation machine 112B. Similarly, the Q N switch 802Q receives the depolarized Q integrations from the Q accumulator 166 for the time domain correlation machine 112A or the IFFT 180 for the frequency domain correlation machine 112B.
For N=4, the I accumulators 804 include four I accumulators denoted as an “A” I accumulator 804A, a “B” I accumulator 804B, a “C” I accumulator 804C, and a “D” I accumulator 804D. Similarly, the Q accumulators 805 include four Q accumulators denoted as an “A” Q accumulator 805A, a “B” Q accumulator 805B, a “C” Q accumulator 805C, and a “D” Q accumulator 805D. For the “A” time period, the I N switch 802I passes the depolarized I integrations to the “A” I accumulator 804A; for the “B” time period, the I N switch 802I passes the depolarized I integrations to the “B” I accumulator 804B; for the “C” time period, the I N switch 802I passes the depolarized I integrations to the “C” I accumulator 804C; and for the “D” time period, the I N switch 802I passes the depolarized I integrations to the “D” I accumulator 804D. Similarly, for the “A” time period, the Q N switch 802Q passes the depolarized Q integrations to the “A” Q accumulator 805A; for the “B” time period, the Q N switch 802Q passes the depolarized Q integrations to the “B” Q accumulator 805B; for the “C” time period, the Q N switch 802Q passes the depolarized Q integrations to the “C” Q accumulator 805C; and for the “D” time period, the Q N switch 802Q passes the depolarized Q integrations to the “D” Q accumulator 805D. The accumulators 804A–D accumulate the depolarized I integrations for providing I magnitude accumulations for each code phase. Similarly, the accumulators 805A–D accumulate the depolarized Q integrations for providing Q magnitude accumulation for each code phase.
For N=4, the N combiner 806 includes an “A” combiner 806A, a “B” combiner 806B, a C combiner 806C, and a “D” combiner 806D. The “A” combiner 806A adds the square of the “A” time period I accumulation from the “A” I accumulator 804A to the square of the “A” time period Q accumulation from the “A” Q accumulator 805A for each code phase increment for providing the “A” time period magnitudes; the “B” combiner 806B adds the square of the “B” time period I accumulation from the “B” I accumulator 804B to the square of the “B” time period Q accumulation from the “B” Q accumulator 805B; and so on for the “C” combiner 806C and the “D” combiner 806D. At this point using code phase increments of slightly less than one-half chip there will be preferably about 2048 “A” time period magnitudes, about 2048 “B” time period magnitudes, about 2048 “C” time period magnitudes, and about 2048 “D” time period magnitudes. As described above, the code phase increment that results in the strongest of the “A”, “B”, “C”, or “D” time period magnitudes, or combination of the “A”, “B”, “C”, and “D” time period magnitudes for a code phase is tested against a correlation threshold and used for signal acquisition when the correlation threshold is exceeded.
As described above the time period I and Q accumulations are preferably proportional to the levels for the I and Q integrations of the GPS signal, whereas the “A”, “B”, “C”, and “D” time period magnitudes are preferably proportional to the sum of the squares the I and Q magnitude accumulations (I2+Q2). However, it should be noted that the “A”, “B”, “C”, and “D” time period magnitudes can be some other convenient non-decreasing functions of the time period I and Q accumulations, such as the sum (I+Q) or the square root of the sum of the squares (√(I2+Q2)
FIG. 9 is a block diagram of a signal receiver of the present invention referred to by the general reference number 810. The receiver 810 is described in terms of a global positioning system (GPS) receiver for receiving incoming coarse/acquisition (C/A) GPS signals. However, those of ordinary skill the art of spread spectrum radio receivers will see that the block diagram illustrated in FIG. 9 and described below can be applied for receiving other types of signals, especially for receiving other types of direct fast sequence spread spectrum signals including precision P or P(Y) code GPS signals. The GPS receiver 810 includes the GPS antenna 102, the frequency downconverter 104, the reference generator 105, the sampler 106, the stored signal memory 108, the correlation machine 112, the microprocessor 114, the replica generator 138, and the program memory 116 including the stored sequence 122, the acquisition detector 811, and the signal and navigation program 126 as described above.
The GPS receiver 810 also includes an expected sequence timer 812, and an N timer 814. The sequence timer 812 uses the reference generator 105 for maintaining GPS time to within ±20/N ms for gating the sampler 106 and/or the signal memory 108 for storing the sampled downconverted GPS signal during the expected reception time period including the early and late edge times as shown in FIG. 6F. The sequence timer 812 also triggers the N timer 814 for generating N time segment signals for organizing the expected reception time period into N types of alternating 10 ms time segments as illustrated in FIGS. 6A–E for N=2 and FIG. 6F for N=4 and described in the accompanying detailed descriptions above.
The correlation machine 112 includes the N processor 800 illustrated in FIG. 8 and described above for the case of N=4. The correlation machine 112 including the N processor 800 integrates the stored signal representation of the GPS signal during the “A” time segments and “A1” augmentation time segments for providing “A” time period magnitudes for each code phase, respectively; during the “B” time segments and “B” augmentation time segments for providing “B” time period magnitudes for each code phase, respectively; during the “C” time segments and “C” augmentation time segments for providing “C” time period magnitudes for each code phase, respectively; and during the “D” time segments and “B” augmentation time segments for providing for “D” time period magnitudes each code phase, respectively. The correlation machine 112 and integration process are illustrated and described in greater detail in FIGS. 3–4 and the accompanying descriptions above with the provision that the AB processor 136 is replaced by the N processor 800.
The N types of time period magnitudes, represented for N=4 by the “A” time period magnitudes, the “B” time period magnitudes, “C” time period magnitudes and the “D” time period magnitudes, from the correlation machine 112 are processed by the microprocessor 114 using instructions in the acquisition detector 811 for determining the increment of code phase for the replica code that appears to match the code phase of the incoming GPS signal. This replica code phase is then processed for GPS signal acquisition by the microprocessor 114 according to instructions in the signal and navigation program 126.
There are several embodiments for the acquisition detector 811 that can process the N types of time period magnitudes in order to find the code phase for acquisition. In a preferred embodiment, the strongest of the time period magnitudes is tested against a correlation threshold. In another preferred embodiment, the N types of time period magnitudes for a code phase are combined (incoherently) or their squares are added to form an N combined time period magnitude for that code phase. The code phase that resulted in the strongest of the time period magnitudes is tested against a correlation threshold. When the strongest time period magnitude exceeds the correlation threshold, the code phase that resulted in that combined time period magnitude is used for signal acquisition and tracking. Once the code phase for acquisition of the GPS signal from a single GPS satellite is determined, conventional methods can be used for acquiring the GPS signal from other GPS satellites. When the strongest magnitude does not exceed the required correlation threshold, then a different Doppler frequency, a different PRN code, a different GPS time, or the like is tried and the process is repeated; or the GPS receiver 810 may go into a standby mode to conserve power.
Although the present invention has been described in terms of the presently preferred embodiments, it is to be understood that such disclosure is not to be interpreted as limiting. Various alterations and modifications will no doubt become apparent to those skilled in the art after having read the above disclosure. Accordingly, it is intended that the broadest reading of the appended claims define the true idea and scope of the invention.

## Claims

1. A method for fast acquisition of a global navigation satellite system (GNSS) signal having data bits modulated by a spreading code, comprising:
organizing integration of said GNSS signal into “A” time periods having “A” time segments, each of said “A” time segments having a plurality of chips of said spreading code, and “B” time periods having “B” time segments, each of said “B” time segments having a plurality of chips of said spreading code, said “A” time segments alternating with said “B” time segments;
correlating said spreading code chips with replica code chips for determining spreading code chip correlations;
integrating said GNSS signal by accumulating said spreading code chip correlations during N said “A” time segments, said N at least two, for determining a set of “A” time period integrations corresponding to code phases, respectively, for said spreading code;
integrating said GNSS signal by accumulating said spreading code chip correlations during M said “B” time segments, said M at least two, for determining a set of “B” time period integrations corresponding to said code phases, respectively; and
using said “A” and “B” time period integrations for determining a correct one of said code phases for acquiring said GNSS signal.

2. The method of claim 1, wherein:
said “A” time segments and said “B” time segments have time durations about one-half the time durations of said data bits.

3. The method of claim 1, wherein:
organizing said integration includes constructing said “A” and said “B” time segments so that all of said “A” time segments or all of said “B” time segments avoid transition times between said data bits.

4. The method of claim 1, wherein:
integrating said GNSS signal during said N “A” time segments includes:
correlating said GNSS signal against a GNSS replica during each one of said “A” time segments for providing “A” time segment integrations for said respective code phases; and
combining said “A” time segment integrations for like ones of said code phases for providing said “A” time period integrations.

5. The method of claim 1, wherein:
integrating said GNSS signal during said N “A” time segments includes:
depolarizing said GNSS signal according to expected polarities of said data bits for providing a depolarized GNSS signal; and
integrating said depolarized GNSS signal during said N “A” time segments for determining said “A” time period integrations.

6. The method of claim 5, wherein:
integrating said depolarized GNSS signal during said N “A” time segments includes:
determining said N of phase sets of depolarized integrations, said depolarized integrations corresponding respectively to said code phases; and
determining said “A” time period integrations by combining said depolarized integrations for like ones of said code phases.

7. The method of claim 6, wherein:
determining said “A” time period integrations includes combining linear representations of said depolarized integrations.

8. The method of claim 6, wherein:
determining said “A” time period integrations includes combining squared representations of said depolarized integrations.

9. The method of claim 1, wherein:
integrating said GNSS signal during said N “A” time segments includes:
integrating said GNSS signal during a first of said N “A” time segments for providing first integration levels corresponding respectively to said code phases; and
resuming integrating said GNSS signal during a second of said N “A” time segments for providing second integration levels corresponding respectively to said code phases, and so on for each of said N “A” time segments for providing said “A” time period integrations.

10. The method of claim 9, wherein:
resuming integrating said GNSS signal during said second “A” time segment includes:
retaining said first integration levels through a first of said M “B” time segments; and
resuming integrating during said second “A” time segment starting from said first integration levels for providing said second integration levels.

11. The method of claim 9, further comprising:
determining a certain one of said “B” time segments where expected polarities are the same for consecutive said data bits; and wherein:
resuming integrating said GNSS signal during said second “A” time segment includes:
resuming integrating during said certain “B” time segment starting from said first integration levels for providing augmented first integration levels; and
resuming integrating during said second “A” time segment starting from said augmented first integration levels for providing said second “A” integration levels.

12. The method of claim 1, wherein:
integrating said GNSS signal during said N “A” time segments includes;
integrating said GNSS signal during said N “A” time segments for providing said N of phase sets of polarized integrations, said polarized integrations corresponding respectively to said code phases;
depolarizing said polarized integrations according to expected polarities of said data bits for providing depolarized integration components; and
determining said “A” time period integrations by combining said depolarized integrations for like ones of said code phases.

13. An apparatus for fast acquisition of a global navigation satellite system (GNSS) signal having data bits modulated by a spreading code, comprising:
an AB timer for segmenting a time of said GNSS signal into “A” time periods having “A” time segments, each of said “A” time segments having a plurality of chips of said spreading code, and “B” time periods having “B” time segments, each of said “B” time segments having a plurality of chips of said spreading code, said “A” time segments alternating with said “B” time segments;
a correlation machine including code multipliers for correlating said spreading code chips with replica code chips for determining spreading code chip correlations, the correlation machine coupled to the AB timer for integrating said spreading code chip correlations during N said “A” time segments, said N at least two, for determining a set of “A” time period integrations corresponding to code phases, respectively, for said spreading code; and integrating said spreading code chip correlations during M said “B” time segments, said M at least two, for determining a set of “B” time period integrations corresponding to said code phases, respectively; and
an acquisition detector for using said “A” and “B” time period integrations for determining a correct one of said code phases for acquiring said GNSS signal.

14. The apparatus of claim 13, wherein:
said “A” time segments and said “B” time segments have time durations about one-half the time durations of said data bits.

15. The apparatus of claim 13, wherein:
the AB timer constructs said “A” and said “B” time segments so that all of said “A” time segments or all of said “B” time segments avoid transition times between said data bits.

16. The apparatus of claim 13, wherein:
the correlation machine correlates said GNSS signal against a GNSS replica during each one of said “A” time segments for providing “A” time segment integrations for said respective code phases; and includes an AB processor for combining said “A” time segment integrations for like ones of said code phases for providing said “A” time period integrations.

17. The apparatus of claim 13, wherein:
the correlation machine includes a depolarizer for depolarizing said GNSS signal according to expected polarities of said data bits for providing a depolarized GNSS signal; and an AB processor for accumulating said depolarized GNSS signal during said N “A” time segments for determining said “A” time period integrations.

18. The apparatus of claim 13, wherein:
the correlation machine determines said N of phase sets of depolarized integrations, said depolarized integrations corresponding respectively to said code phases; and determines said “A” time period integrations by combining said depolarized integrations for like ones of said code phases.

19. The apparatus of claim 18, wherein:
the correlation machine determines said “A” time period integrations by combining linear representations of said depolarized integrations.

20. The apparatus of claim 18, wherein:
the correlation machine determines said “A” time period integrations by combining squared representations of said depolarized integrations.

21. The apparatus of claim 13, wherein:
the correlation machine includes an AB processor for integrating said GNSS signal during a first of said N “A” time segments for providing first integration levels corresponding respectively to said code phases; and resuming integrating said GNSS signal during a second of said N “A” time segments for providing second integration levels corresponding respectively to said code phases, and so on for each of said N “A” time segments for accumulating said “A” time period integrations.

22. The apparatus of claim 21, wherein:
said AB processor retains said first integration levels through a first of said M “B” time segments; and resumes integrating during said second “A” time segment starting from said first integration levels for providing said second integration levels.

23. The apparatus of claim 21, further comprising:
an expected sequence timer for determining a certain one of said “B” time segments where expected polarities are the same for consecutive said data bits; and wherein:
said AB processor resumes integrating during said certain “B” time segment starting from said first integration levels for providing augmented first integration levels; and resumes integrating during said second “A” time segment starting from said augmented first integration levels for providing said second integration levels.

24. The apparatus of claim 13, wherein:
the correlation machine is constructed for integrating said GNSS signal during said N “A” time segments for providing said N of phase sets of polarized integrations, said polarized integrations corresponding respectively to said code phases; a depolarizer for depolarizing said polarized integrations according to expected polarities of said data bits for providing depolarized integration components; and an AB processor for determining said “A” time period integrations by combining said depolarized integrations for like ones of said code phases.