Power savings technique for a positioning system receiver

[0002] This is a continuation-in-part of application Ser. No. 09/040,521, filed on Mar. 16, 1998.

[0003] The present invention pertains to power management in a signal receiver. More particularly, the present invention relates to reducing power consumption in a Global Positioning System (GPS) receiver.

[0004] Signal acquisition in a Global Positioning System (GPS) receiver generally requires searching for a modulation code in a carrier signal that is received from a GPS satellite. GPS generally makes use of two spread-spectrum modulation codes known as the “C/A code” and the “P code”, which are multiplexed in quadrature onto a single carrier. The C/A code is a Gold code with a chipping rate of 1.023 Mbits/sec and is used for making course position determinations. The P code is a pseudo-random code with a chipping rate of 10.23 Mbits/sec and is used for more precise position determinations. The P code is more resistant to jamming than the C/A code and has a secure, “antispoof” version known as the Y code. The Y code is available only to authorized users, such as the military. The P code and the Y code are sometimes referred to collectively as the P(Y) code.

[0005] Code acquisition in a GPS receiver may be accomplished by comparing the received code with a reference code generated locally within the receiver in order to synchronize the two codes. The time required to acquire the signal is generally dependent upon frequency and phase uncertainties between the received code and the reference code. Consequently, acquisition of the received code generally involves searching a two-dimensional search region defined by a number of code offset values in one dimension and a number of frequency offset values, sometimes referred to as Doppler offset values, in the other dimension. The code offsets represent different values of phase offset between the received code and the reference code, while the frequency offsets represent different values of frequency offset between the received code and carrier and the reference code and carrier. The code and frequency offset values which define the search region are sometimes referred to as “bins”.

[0006] Thus, referring to FIG. 1, the acquisition of a P(Y) code received from a GPS satellite is performed by searching for a signal 20 within a search region 21. The search region 21 is defined in terms of a number of code offset bins along one axis and a number of frequency offset bins along a second axis. Element 22 in FIG. 1 represents a bin. The signal acquisition time is the time from the start of the search until a bin is determined to be occupied or “hit”.

[0007] The process of synchronizing the locally-generated code to the received code in a GPS receiver often involves computing the correlation between the two codes at various points in time. Referring to FIG. 2A, two correlation curves 31 and 32 are associated with two adjacent code offset bins. In the direction of code offset, the shape of the correlation function may be a series of overlapping triangles, the peaks of which are centered at the midpoint of each code offset bin, and the troughs of which fall halfway between each bin. The width of each bin is the width of each triangle at the code offset axis. Although the bins overlap, the midpoints of the bins are spaced apart by C chips; hence, the bins are said to be spaced apart by C chips. The rate at which a search region may be covered generally depends upon the number of parallel search bins and the degree of overlap of adjacent bins. The most adverse condition in terms of signal correlation is for the received signal to be located exactly midway between the center points of adjacent bins. For example, FIG. 2A illustrates that signal correlation is strongest when the actual code offset corresponds to the center of a bin and weakest when the offset corresponds to the trough 33 between two bins. Signal acquisition time, therefore, depends partially upon the “depth” of the trough 33. The depth of the trough 33, in turn, is directly dependent upon the spacing of the bins. If the bins are spaced farther apart, the total number of bins to be searched within a given search region may be reduced; however, the overall acquisition time may increase due to the increased trough depth. These principles, therefore, give rise to a design trade-off between bin spacing and signal acquisition speed.

[0008] FIG. 2B shows a relationship between frequency offset and signal correlation. In the direction of frequency offset, the shape of the correlation function is a series of overlapping sinc(x) curves, the peaks of which are centered at the midpoint of each frequency offset bin and the troughs of which fall halfway between each bin. Curves 34 and 35 represent the correlation curves associated with two adjacent frequency offset bins. The bins associated with curves 34 and 35 overlap but are spaced apart by F Hz. The width of the frequency offset bins is the width between the nulls of each sinc(x) curve at the frequency offset axis. As with code offset, the depth of the trough 36 depends partially upon the spacing of the bins.

[0009] A problem that is associated with many GPS receivers is power consumption. Random access memory (RAM) in the receiver can be a significant source of power consumption. A GPS receiver may include RAM for providing accumulators to store correlation data used during signal acquisition. Conventional dynamic RAM (DRAM) based on Complementary Metal-Oxide-Semiconductor (CMOS) process draws power each time it is accessed during a read or write cycle. Thus, it is desirable to reduce power consumption in a GPS receiver and, in particular, to reduce power consumption associated with RAM accumulators in a GPS receiver.

[0010] One aspect of the present invention is a method and apparatus for reducing power consumption in a receiver that includes multiple correlation segments that are operable in parallel. Each of the correlation segments has a separate set of storage locations associated with it. In each of the correlation segments, correlation data associated with multiple signals are generated. The correlation data are stored during each of multiple time intervals by accessing the storage locations of less than all of the correlation segments during each time interval.

[0011] In another aspect of the invention, correlation data generated in a given correlation segment are combined with correlation data generated in each other correlation segment to form data to be stored in the storage locations of the given correlation segment.

[0012] In particular embodiments, the multiple correlation segments may be cross-coupled, so that correlation data generated in any given correlation segment are added to correlation data generated in each other correlation segment, and the combined correlation data are stored in a set of accumulators for that correlation segment. The accumulators of only one correlation segment are accessed at a time to reduce power consumption in the receiver.

[0013] Other features of the present invention will be apparent from the accompanying drawings and from the detailed description which follows.

[0014] The present invention is illustrated by way of example and not limitation in the figures of the accompanying drawings, in which like references indicate similar elements and in which:

[0015] FIG. 1 illustrates a search region defined in terms of a number of frequency offset bins and a number of code offset bins.

[0016] FIG. 2A illustrates a correlation function for two adjacent code offset bins.

[0017] FIG. 2B illustrates a correlation function for two adjacent frequency offset bins.

[0018] FIG. 3 is a block diagram of a GPS receiver.

[0019] FIGS. 4A and 4B illustrate varying the spacing of code offset bins in terms of correlation.

[0020] FIGS. 5A and 5B illustrate varying the spacing of frequency offset bins in terms of correlation.

[0021] FIG. 6 illustrates a search stage of a GPS receiver including two correlation segments operable in parallel.

[0022] FIG. 7A is a flow diagram illustrating a routine for dynamically varying bin spacing.

[0023] FIG. 7B illustrates the relationship between quantities N_NCOH, T_COH and T_NCOH.

[0024] FIG. 7C illustrates the relationship between quantities N_COH, T_COH and m.

[0025] FIG. 7D is a flow diagram illustrating a routine for determining Doppler offset bin spacing according to a first embodiment.

[0026] FIG. 7E is a flow diagram illustrating a routine for determining Doppler offset bin spacing according to a second embodiment.

[0027] FIG. 8 is a block diagram of one of the correlation segments of FIG. 6.

[0028] FIG. 9A is a signal diagram illustrating the combining of samples of a received code.

[0029] FIG. 9B is a flow diagram illustrating a routine for determining code offset bin spacing according to a first embodiment.

[0030] FIG. 9C is a flow diagram illustrating a routine for determining code offset bin spacing according to a second embodiment.

[0031] FIG. 10A is a block diagram of the code offset bin spacing stage (COBSS) of FIG. 8.

[0032] Figure 10B is a block diagram of the combiner control circuit of FIG. 10A.

[0033] FIG. 11 is a block diagram of the correlation stage of FIG. 8.

[0034] FIG. 12 is a block diagram of the accumulation stage of FIG. 8.

[0035] FIG. 13 is a block diagram of the accumulator control block of FIG. 12.

[0036] FIG. 14 illustrates two correlation segments cross-coupled to reduce power consumption.

[0037] FIG. 15 is a flow diagram illustrating a power savings technique usable with the embodiment of FIG. 14.

[0038] A method and apparatus are described for reducing power consumption resulting from accessing memory in a GPS receiver. The present invention is particularly suited for use in a massively parallel GPS receiver for fast acquisition of P(Y) or C/A codes. For purposes of the present invention, the term “P(Y) code” is used to collectively refer to either a P code or a Y code associated with GPS. It will be recognized that the present invention can be used in many other applications. Hence, the present invention is not limited to use in acquiring the aforementioned codes, nor is the present invention limited to use in a positioning system. Also, certain aspects of the present invention are described herein in the form of particular hardware or software components. Note, however, that such components generally may be embodied in either hardware or software, or in a combination of hardware and software, within the scope of the present invention.

[0039] As will be described in greater detail below, a GPS receiver includes multiple correlation segments that can operate in parallel. Each correlation segment has a separate set of accumulators associated with it, embodied in RAM. In each of the correlation segments, correlation data associated with an input code and a reference code are generated. The multiple correlation segments are cross-coupled, so that correlation data generated in each correlation segment are added to correlation data generated in each other correlation segment. The correlation data combined in each correlation segment are stored in the accumulators of each corresponding correlation segment, so that the accumulators of only one correlation segment are accessed at a time, reducing power consumption that results from accessing RAM.

[0040] Refer now to FIG. 3, which illustrates an example of a GPS receiver 1 in which the present invention can be implemented. The receiver 1 includes an antenna 2, a radio frequency (RF) input stage 3, a search stage 4, a tracking stage 5, a central processing unit (CPU) 6, a memory 7, an input/output (I/O) subsystem 8, and an analog-to-digital (A/D) converter 9. A modulated L1 or L2 GPS carrier signal is received by the receiver 1 at antenna 2 and input to the RF input stage 3. The RF input stage 3 amplifies and filters the received signal, down converts the frequency of the received signal to one that is more manageable, and outputs the resulting signal to the A/D converter 9. The A/D converter 9 samples the signal received at its input and outputs the samples SI to both the search stage 4 and the tracking stage 5. Note that in other embodiments, separate A/D samplers may be used for the search stage 4 and the tracking stage 5. The search stage 4 is responsible for locating the C/A code and P(Y) code within a given search region, while the signal tracking stage 5 is responsible for locking onto these signals, i.e., maintaining alignment of the received signal with a locally-generated reference signal. Search stage 4 can search multiple Doppler bins and multiple code offset bins in parallel. As will be described below, the present invention is directed to the search stage 4.

[0041] The search stage 4 and the tracking stage 5 each provide an output to, and receive control inputs from, the CPU 6. The CPU 6 has a bi-directional connection to memory 7 and to I/O subsystem 8. The memory 7 may be used to store software instructions executable by the CPU 6, various types of data, or both. The I/O subsystem 8 includes a display device (not shown) for presenting navigation and positional information to the user and various user controls (not shown) for receiving user inputs.

[0042] In general, GPS receivers often use a common clock signal to provide timing for sampling, searching, and tracking functions. In contrast, the receiver 1 uses a separate clock signal for purposes of signal acquisition (searching) from that used for sampling and signal tracking. It is advantageous to use two separate clock signals, because the acquisition circuitry can tolerate a significantly higher phase noise in its clock signal than the sampling and tracking stages can, even though they require the same frequency stability. In the receiver 1, clock signal CLK1 drives the A/D converter 9 and the tracking stage 5 for purposes of sampling and tracking, respectively. A second clock signal CLK2 is provided to the search stage 4 for purposes of signal acquisition. Clock signal CLK1 is preferably from a very stable oscillator, the specific stability parameters of which are application dependent. The stability requirements of the clock signal CLK2 are less stringent than those of clock signal CLK1, however, because the phase error of clock signal CLK2 can be as large as half a bin for purposes of signal acquisition.

[0043] In accordance with the present invention, the spacing of Doppler offset bins, code offset bins, or both may be varied to best suit a particular receiver or signal environment. Refer to FIGS. 4A and 4B, which illustrate the effect of varying the code offset bin spacing on the signal correlation function. The manner in which the bin spacing is varied is described in detail below. FIG. 4A shows correlation curves 41 and 42 corresponding to two adjacent code offset bins. The bins are spaced apart by C code chips. FIG. 4B illustrates the same curves when the bin spacing has been increased to (C+ΔC) chips. It can be seen that increasing the spacing between the adjacent bins causes a deepening of the trough 43 between the two bins. The depth of the trough represents losses or attenuation of the correlated signal. Hence, a wider spacing might be used to accelerate a search where a strong signal is present, while a narrower spacing might be used to reduce losses where a weak signal is present or when the signal is being jammed. In addition, the variable bin spacing allows the size and shape of the search region to be tailored as desired without altering the number of bins that are searched.

[0044] Similarly, as shown in FIGS. 5A and 5B, which illustrate the effect of varying the spacing between Doppler offset bins on correlation. The two correlation curves 51 and 52 are spaced apart by F Hz in FIG. 5A. As with code offset, a deepening of the trough 53 between the two bins also results when the Doppler offset bin spacing is increased to (F+ΔF) Hz. Thus, the varying of bin spacing can be used to control the depth of the trough between adjacent Doppler offset bins, code offset bins, or both.

[0045] One problem associated with code acquisition in a GPS receiver is “code smearing” loss, or loss which results when, as a result of code Doppler, the received code is not synchronized with the reference code over the entire correlation interval. The use of a single, shared reference code generator for all Doppler bins may result in divergence of the code and carrier frequencies. Code smearing tends to be worse in the outer Doppler bins and often results from a Doppler bin offset that is too wide. An advantage of the present invention is that bin spacing can be varied to reduce code smearing.

[0046] As noted above, the present invention relates to the search stage 4 (see FIG. 3). FIG. 6 shows the search stage 4 in greater detail, according to one embodiment of the present invention. In the illustrated embodiment, the search stage 4 includes two essentially identical correlation segments 61A and 61B. Each of correlation segments 61A and 61B receives the sampled input signal SI and is coupled to the CPU 6 for bi-directional communication of commands, addresses, and data. Such communication is provided using techniques that are well-known in the art. Each correlation segment can search a region comprising some number of code offset bins by some number of Doppler offset bins. In one embodiment, the correlation segments 61A and 61B can operate in parallel. That is, the correlation segments 61A and 61B can each search a different set of 512 code offset bins by the same seven Doppler offset bins to cover an effective search region of 1,024 code offset bins by seven Doppler offset bins. An advantage of such an embodiment is that computations can be limited to only a few Doppler channels that are of interest. Note, however, that the present invention is not limited to any particular number of correlation segments, Doppler offset channels or bins, or code offset channels or bins, or to any particular size of search region.

[0047] The varying of the spacing of code offset bin spacing or Doppler offset bin spacing, or both may be implemented, in part, in each of the correlation segments 61A and 61B. FIG. 7A illustrates a routine 700 by which the spacing of either the code offset bins or the Doppler offset bins may be varied. At 701, the receiver 1 determines the size of the search region and the desired signal strength. At 702, the receiver 1 selects the bin spacing and integration times. The initial selection of bin spacing may be a default value. At 703, the receiver 1 attempts to locate a received signal, such as a P(Y) code, within a first set of bins. If the signal has been located within the total non-coherent integration period T_NCOH at 704, then the routine ends. If not, then the routine proceeds to 709, where it is determined whether the code or frequency uncertainties or the signal characteristics have changed. A change in uncertainty might result, for example, from a change in the dynamics of the receiver's platform, such as a high acceleration if the platform is a vehicle. If either the code or frequency uncertainty or signal characteristics have changed, then the routine repeats from 701 with an appropriate modification to the size of the search region and/or desired signal strength based on the current uncertainties and/or signal characteristics.

[0048] If there has been no change in the uncertainties or signal characteristics at 709, then the routine proceeds from 705. If not all bins of the search region have been covered at 705, then at 707 the next part of the search region is determined, and the routine proceeds to 708. At 708 it is determined whether the signal environment has changed. If not, the routine repeats from 702 by reselecting the bin spacing and integration times; otherwise the routine repeats from 703 by attempting to locate the signal.

[0049] If all bins of the search region have been covered at 705, then at 706 the bin search region is modified, and the routine repeats from 702. For example, the bin spacing may be reduced in order to reduce the depth of the troughs between bins and thereby increase the likelihood that a signal will be located. The amount by which the spacing is adjusted can be a default value, or it can be based on any of various dynamically computed parameters, such as satellite signal strength, jamming levels, code uncertainty, frequency uncertainty, desired probability of detection, etc. Note that numerous variations on the routine of FIG. 7A are possible within the scope of the present invention.

[0050] The algorithm used to select the bin spacings and integration time at 702 is based on minimizing the expected acquisition search time for the desired probability of detection of the signal. The algorithm generally combines parameters of the search region and search device capabilities with an empirical or statistical model to connect the probability of success or failure (to detect the signal) with a chosen combination of bin spacings and integration time.

[0051] FIGS. 7D and 7E illustrate examples of routines for selecting bin spacing, as performed in 702 above. Before discussing those routines, however, it may be useful to define certain terms. As indicated in the routine of FIG. 7A, the search stage 4 of receiver 1 attempts to locate a signal during a total non-coherent integration period T_NCOH (FIG. 7A, 703 and 704). Each non-coherent integration period T_NCOH comprises a number N_NCOH of non-coherent integrations, each of which has a coherent integration time T_COH. The relationship between the quantities T_COH and N_NCOH is illustrated in FIG. 7B. Each coherent integration time T_COH comprises a number N_COH of coherent integration cycles of a correlation segment. The relationship between the quantities T_COH and N_COH is illustrated in FIG. 7C. As will be discussed below, each of the N_COH coherent integration cycles comprises m subcycles, where m is equal to the number of code offset bins per correlation segment.

[0052] Referring now to FIG. 7D, a routine 750 for varying bin spacing is shown. Adjustment of bin spacings at 702 may involve varying the spacing of either Doppler offset bins, code bins, or both. In one embodiment, Doppler and code bin spacings are adjusted at 702 by testing candidate bin spacings according to a nested loop approach. More specifically, for each selected Doppler bin spacing, multiple code bin spacings are tested, one at a time, until all candidate bin spacings have been tested.

[0053] The routine 750 of FIG. 7D is for determining the spacing of Doppler offset bins, however, a similar routine can be used to determine the spacing of code offset bins, as will be discussed below. The Doppler offset bin spacing is determined by the number of coherent integration cycles N_COH used. Thus, at 751, the position uncertainty and frequency uncertainty are calculated. Next, at 752 the effective signal-to-noise ratio S/N is computed for the signal level S, ambient noise N, and jamming-to-signal ratio J/S. At 753, one of multiple candidate N_COH values is selected, and the following sequence is then performed for each candidate N_COH value. At 754 the bin width and resulting bin spacing is calculated to cover the frequency uncertainty previously computed (at 751). Next, at 755 the correlation losses L are calculated for current bin spacing and desired probability of detection Pd. At 756 the required number of non-coherent integrations N_NCOH needed to detect the presence of a satellite is calculated at the effective signal-to-noise ratio S/N, with the correlation losses L and currently selected N_COH, for the desired probability of detection Pd, is computed. In one embodiment, the computation of the number of non-coherent integrations at 756 is performed using a statistical model, as described in S. Mahmood et al., “An Analytical Study of Fast Acquisition Issues in GPS Exploitation for Electronic Combat”, Proceedings, 7^thInternational Technical Meeting of the Institute of Navigation, pp. 863-70, Sep. 20-23, 1994, Salt Lake City, Utah. As an alternative, this calculation might be performed as a linear best-fit computation. Next, at 757 it is determined whether the resulting total integration time T_NCOH is the shortest computed thus far. If not, the routine continues from 758. If so, then at 760 the current bin spacing and N_COH are saved as the “best” bin spacing and N_COH, and the routine continues from 758. If there are more candidate N_COH values to consider at 758, then at 759 the next N_COH value is selected, and the routine repeats from 754. Otherwise, the routine ends. The final “best” N_COH value is then used to control the Doppler bin spacing, in a manner which will be described below.

[0054] FIG. 7E illustrates an alternative routine for varying the Doppler offset bin spacing. Again, the Doppler offset bin spacing is determined by the number N_COH of coherent integration cycles used. This alternative routine uses a weighted sum of parameters to calculate the N_COH value needed to provide the shortest total non-coherent integration time T_NCOH. For example, the weighted sum might be computed as follows:

[0055] N_COH=A+B·Pd+C·S/Nj+D·(Uhz/NDop)  (1)

[0056] where:

[0057] Pd is the desired probability of detection;

[0058] S/Nj is the effective signal-to-noise ratio corrected for jamming and other noise sensors, in dB;

[0059] Uhz is the frequency uncertainty in Hz; and

[0060] NDop is the number of Doppler bins.

[0061] For a specific implementation, the coefficients A, B, C and D may be calculated from a least squares fit covering the range of variation of the above parameters. For purposes of generating the data for fitting, the routine of FIG. 7B or experimental data can be used.

[0062] Thus, the weighted sum N_COH might be computed according to the routine 780 of FIG. 7E. At 781, the position uncertainty and frequency uncertainty are calculated. Next, at 782 the effective signal-to-noise ratio S/N is computed for the signal level S, ambient noise N and jamming-to-signal ratio J/S. Next, at 783, N_COH is computed according to equation (1) above. At 784 the required number of non-coherent integrations N_NCOH needed to detect the presence of a satellite is calculated at the effective signal-to-noise ratio S/N, with the correlation losses L and N_COH, for the desired probability of detection Pd, is computed. The method described by Mahmood et al. may be used for this computation. At 785, if the resulting N_NCOH is less than one, then at 786 the number of coherent integration cycles N_COH is recomputed such that N_NCOH equals one, and the routine ends. If N_NCOH is equal to or greater than one at 785, then the routine ends.

[0063] FIG. 8 illustrates the segment 61A in greater detail. As noted above, segment 61B is essentially identical to segment 61A. Segment 61A includes a programmable-rate mixing stage 78, a code offset bin spacing stage (COBSS) 72, a correlation stage 73, a Doppler bin generation and accumulation stage 74, a threshold detection and buffer circuit (TDBC) 75, a mean and peak detection circuit (MPDC) 76, and a reference code generator 77.

[0064] The mixing stage 78 includes a register 79, a programmable-rate number-controlled oscillator (NCO) 102, sine/cosine look-up tables (not shown), and a mixer 71. The input signal SI includes a number of digital samples of the signal from A/D converter 9. The mixer 71 mixes the signal SI with signal 80 generated by NCO 102. Signal 80 includes both in-phase and quadrature (i.e., sine and cosine) components. The frequency of signal 80 output by NCO 102 is determined by the value that is stored in register 79, which is set by the CPU 6. The resulting mixed signal DSI includes both in-phase and quadrature components and is output by the mixer 71 to the COBSS 72.

[0065] The COBSS 72 receives the clock signal CLK2 and the output DSI of the mixer 71 and selectively combines samples of the mixed input signal DSI to vary the spacing between code offset bins. Note that the combining function is optional and can be bypassed, if appropriate. The combining of samples, which is described in greater detail below, is based on the clock signal CLK2 received by the COBSS 72 as well as a control input CCTRL received by the COBSS 72 from the CPU 6. The combined samples are output by the COBSS 72 as signal CDSI, which is provided to the correlation stage 73 as input. The COBSS also outputs a control signal READY to both the correlation stage 73 and the accumulation stage 74. The purpose of the READY signal is described below.

[0066] The reference code REF_CODE is generated locally by the reference code generator 77 and is provided as inputs to both the COBSS 72 and the correlation stage 73. Reference code generator 77 receives clock signal CLK1 as input.

[0067] REF_CODE includes indications of the epoch.

[0068] The correlation stage 73 receives signal CDSI from the COBSS 72 and REF_CODE and outputs to the accumulation stage (separately) both in-phase and quadrature values of correlation between REF_CODE and the P(Y) code in the received signal at various points in time. The in-phase and quadrature correlation values are represented collectively as signal I,Q output from correlation stage 73. The correlation stage also receives clock signal CLK2. The accumulation stage 74 also receives clock signal CLK2 as well as control signals READY and N_NORM from the COBSS 72 and control signal FCTRL from the CPU 6, the purposes of which are described below.

[0069] The accumulation stage 74 is described in greater detail below. Generally, however, the accumulation stage 74 mixes correlation values in signal I,Q with signals of various different frequencies to create the desired Doppler offset bins and collects values over the period of a coherent integration interval. In addition, the accumulation stage includes components for dynamically varying the spacing of the Doppler offset bins, as necessary. The mixed results are accumulated, both coherently and non-coherently, and then output to both the TDBC 75 and the MPDC 76.

[0070] TDBC 75 applies a threshold function to the signal received at its input to provide a “hit” (signal found) indication to the CPU 6 and in which bin the hit occurred. MPDC 76 detects and outputs to the CPU 6 the mean and peak values of the signal received at its input. The mean and peak values are combined with other information available to the CPU 6 to determine the threshold values in the TDBC 75. TDBC 75 and MPDC 76 both are clocked by clock signal CLK2.

[0071] Refer now to FIG. 9A, which illustrates how samples of the input signal may be combined by the COBSS 72 to vary the spacing of code offset bins. In a GPS receiver, the minimum achievable spacing of code offset bins is generally the A/D sample period of the received signal. In accordance with the present invention, therefore, the code offset bin spacing can be increased by combining samples of the input signal. In one embodiment, the code offset bin spacing can be increased up to a maximum of one code chip. For example, if sampled at 20.46 MHz, up to two samples could be combined for the P(Y) code, or up to 20 samples could be combined for the C/A code. In FIG. 9A, waveform 91 represents the P(Y) code or C/A code in a received signal, while waveform 92 represents the locally-generated P(Y) or C/A reference code. For purposes of illustration only, the reference code is shown offset from the received code by one code chip. The received waveform 91 consists of a series of digital samples 93. In accordance with the present invention, samples 93 are combined (e.g., averaged together) by the COBSS 72 to form a number of combined samples available at times 95. The combining of the samples 93 effectively increases the spacing between code offset bins. Thus, the COBSS 72 is used to synthesize artificial sampling rates. The COBSS 72 is synchronized to the code chip rate to avoid combining samples across chip boundaries 96.

[0072] The combining of samples is done dynamically based on the current signal environment, i.e., satellite signal strength, noise and/or jamming levels, code uncertainty, frequency uncertainty, etc. The particular algorithm and/or criteria by which samples are combined (e.g., the frequency at which samples are combined, the number of consecutive samples that are combined into one sample, etc.) are determined by the CPU 6, which controls the COBSS via the control signal CCTRL.

[0073] FIG. 9B illustrates an example of a relatively simple routine 900 for determining code bin spacing for a given coherent integration interval N_COH. At 901, the position and frequency uncertainties are calculated. At 902 the effective signal-to-noise ratio S/N is computed for the signal level S, ambient noise N, and jamming level J/S. At 903, one of multiple candidate code bin spacings is selected, and the following sequence is then performed for each candidate code bin spacing. At 904 the correlation losses L are calculated for the selected bin spacing and desired probability of detection Pd. At 905 the required number of non-coherent integrations N_NCOH needed to detect the presence of a satellite is calculated at the effective signal-to-noise ratio S/N, with the correlation losses L and currently selected N_COH, for the desired probability of detection Pd. The computation of the number of non-coherent integrations N_NCOH performed at 905 may be based on, for example, the method described by S. Mahmood et al., as noted above, or as a linear best-fit computation. Next, at 906 it is determined whether the resulting total integration time T_NCOH is the shortest computed thus far. If not, the routine continues from 907. If so, then at 908 the current bin spacing is saved as the “best” bin spacing, and the routine continues from 907. If there are more candidate bin spacings to consider at 907, then at 909 the next candidate bin spacing is selected, and the routine repeats from 904. Otherwise, the routine ends.

[0074] As with the determination of Doppler bin spacing, other methods of determining code bin spacing might also be used. For example, the code offset bin spacing may be computed as a weighted sum designed to provide the shortest total non-coherent integration time T_NCOH. The weighted sum might be computed as follows:

[0075] Code offset bin spacing=E+F·Pd+G·S/Nj+H·Fsc  (2)

[0076] where:

[0077] Pd is the desired probability of detection;

[0078] S/Nj is the effective signal-to-noise ratio corrected for jamming and other noise sensors, in dB;

[0079] Fsc is the ratio of the A/D sampling frequency to the code frequency.

[0080] For a specific implementation, the coefficients E, F, G and H may be calculated from a least squares fit for code bin spacing covering the range of variation of the above parameters. For purposes of generating the data for fitting, the routine of FIG. 9B or experimental data can be used.

[0081] Thus, the weighted sum for code offset bin spacing might be computed according to the routine 930 of FIG. 9C. At 931, the position uncertainty and frequency uncertainty are calculated. Next, at 931 the effective signal-to-noise ratio S/N is computed for the signal level S, ambient noise N, and jamming-to-signal ratio J/S. Next, at 933, the code offset bin spacing is computed according to equation (2) above. At 934 N_COH is computed from equation (1) above. At 935 the required number of non-coherent integrations N_NCOH needed to detect the presence of a satellite is calculated at the effective signal-to-noise ratio S/N, with the correlation losses L and N_COH, for the desired probability of detection Pd, is computed. The method described by Mahmood et al. may be used for this computation. At 936, if the resulting N_NCOH is less than one, then at 937 N_COH is recomputed such that N_NCOH equals one, and the routine ends. If N_NCOH is equal to or greater than one at 936, then the routine ends.

[0082] FIG. 10A illustrates the COBSS 72 in greater detail. In the illustrated embodiment, the COBSS 72 includes a sample combiner 81, a combiner control circuit 83, a normalizer 82, and a register 84. The combiner 81 combines successive samples (within signal DSI) when commanded to do so by the control circuit 83. The combiner control circuit provides signals LOADC and ACCUMC to the combiner to load samples the combiner and to command accumulation of loaded samples, respectively. Specifically, while LOADC is asserted, any samples appearing at the DSI input of combiner 81 will be loaded into the combiner 81. Loaded samples will be combined when ACCUMC is subsequently asserted. Combined samples are output by the combiner 81 as signal DSI′, which is provided to the normalizer 82.

[0083] Generally, the combiner control circuit 83 selectively asserts LOADC or ACCUMC based on a value N_COMB stored in and received from register 84, which indicates the average number of successive samples to be combined. If the average number of successive samples does not divide evenly into the number of code bins, the control circuit 83 does so subject to the restriction that samples on opposite sides of a chip boundary are not combined, as noted above in connection with FIG. 9A. The value N_COMB in register 84 is set by the CPU 6 using control signal CCTRL. The control circuit 83 also receives a code clock signal CODE_CLK as input and outputs a signal, READY. In one embodiment, CODE_CLK is a 10.23 MHz clock signal for purposes of acquiring the P(Y) code or a 1.023 MHz signal for purposes of acquiring the C/A code. The READY signal is provided to the correlation stage 73 and the accumulation stage 74.

[0084] The READY signal is essentially an enable signal which, when asserted, causes the accumulation stage 74 to input the output of the correlation stage 73 in response to CLK2. The correlation stage 73 is described below in greater detail. For example, referring again to FIG. 9A, if the combiner 81 is active (not bypassed), then READY is asserted at times 95. If the combiner 81 is bypassed, however, then READY is always asserted.

[0085] The normalizer 82 generally scales the output DSI′ from the combiner 81 as necessary and provides the scaled output CDSI to correlation stage 73. More specifically, the scaling operation may include either or both of two separate scaling functions. First, the normalizer 82 scales the sampled input signal DSI′ down, if necessary, so that the signal can be represented using a constant, predetermined number of bits (e.g., four bits). Second, the normalizer 82 scales the sampled input signal to evenly weight the results at each successive stage of the correlation shift register 105, which is discussed below in connection with FIG. 11, to adjust for any combining of samples done by the combiner 72. More specifically, the scaling stage 104 will divide the combined value by the number of samples that were combined to form the value. The number of samples combined is indicated in a signal N_NORM provided to the normalizer 82 from the combiner control circuit 83.

[0086] FIG. 10B illustrates the logic of the combiner control circuit 83 according to one embodiment. Control circuit 83 includes an edge detector 90, a standard S-R flip-flop 91, an OR gate 92, a binary up counter 94, a logic circuit 97, and an inverter 98. Edge detector 90 receives signal CODE_CLK as input and provides an out put to the set (S) input of flip-flop 91. The output of edge detector 90 is asserted in response to each rising edge of CODE_CLK. Clock signal CLK2 is applied to the reset (R) input of flip-flop 91. The Q output of flip-flop 91 is applied to one input of two-input OR gate 92. The other input of OR gate 92 is coupled to the “A=B” output of logic circuit 97. The output of OR gate 92 is provided to the CLEAR input of counter 94, which is clocked by CLK2. The output of counter 94 is applied to the “A” input of logic circuit 97. Logic circuit 97 also has a “B” input, which is coupled to receive the value N_COMB. Logic circuit 97 asserts its “A=0” output when the output of counter 94 is zero and asserts its “A=B” output when the output of counter 94 equals N_COMB. The “A=0” output of logic circuit 97 forms signals READY and LOADC. The “A=0” output is also passed through an inverter 98, the output of which forms signal ACCUMC.

[0087] FIG. 11 illustrates the correlation stage 73 in greater detail. In the illustrated embodiment, the correlation stage 73 includes a correlator/shift register (CSR) 105 and a fractal adder circuit 106, which comprises an adder tree. The CSR 105 is a serial-in/parallel-out device which receives the signal CDSI from the normalizer 82 as well as the reference code REF_CODE and the READY signal. The CSR 105 outputs m multi-bit outputs COR in parallel to the CFA 106. Each of the m outputs is a measure of the correlation of samples of the received P(Y) or C/A code and one bit of the reference code REF_CODE. As noted above, the number m is equal to the number of code offset bins per correlation segment.

[0088] The CSR 105 contains an m-bit shift register for shifting in the sampled, scaled input signal CDSI at the clock frequency and an m-bit latch for latching m bits of the local reference code REF_CODE at a time while the input signal CDSI is shifted. At each clock cycle, the input signal CDSI is shifted in the CSR 105 by one bit, and the CSR 105 provides a number of parallel outputs COR to the fractal adder 106. Each output COR value is a multi-bit value representing the exclusive-OR (XOR) of one bit of the input signal CDSI and one corresponding bit of the latched m-bit sequence of the reference code REF_CODE. After every m clock cycles, the next sequence of m bits of the REF_CODE is parallel loaded into the m-bit latch, and the input signal CDSI continues to be shifted into the shift register.

[0089] The fractal adder 106 provides a summation of the COR values received at its inputs, which also results in wideband filtering. The output I,Q of the fractal adder 106 is applied to the accumulation stage 74. As noted above, signal I,Q represents both in-phase and quadrature signals.

[0090] FIG. 12 illustrates the accumulation stage 74 in greater detail. Generally, the accumulation stage 74 creates multiple Doppler offset bins by simultaneously mixing the output I,Q of the correlation stage 72 with a number (2n) of mixing signals MS to generate a number of discrete Doppler channels. The number 2n depends upon the number of Doppler offset bins that are desired to be searched and is therefore application specific. All processing on signal I,Q and signals derived therefrom in the accumulation stage 74 is performed separately and in parallel on both the in-phase and quadrature components, until the magnitude accumulation function (MNCAs 117) described below. Hence, each of the mixing signals MS includes both sine and cosine components at an integer multiple of the basic Doppler offset Δf.

[0091] The accumulation stage 74 includes a number (2n) of mixers 110; the same number (2n) of cosine/sine generators 111; a number (2n+1) of coherent accumulators 114; a Doppler bin NCO 112; a register 113; an accumulator control circuit 115; registers 116 and 118; and a number (2n+1) of magnitude/non-coherent accumulation circuits (MNCAs) 117.

[0092] In accordance with the present invention, the spacing of the Doppler offset bins is determined by appropriately selecting the frequencies of the mixing signals MS, and the spacing can varied dynamically by altering these frequencies. Thus, signal I,Q is applied to each of mixers 110, and each of the mixing signals MS is generated by a different one of the cosine/sine generators 111 at a different integer multiple of the basic Doppler offset Af in either the positive or negative direction (i.e., ±Δf, ±2Δf, . . . , ±nΔf). Each mixing signal MS includes both in-phase and quadrature (i.e., sine and cosine) components. The output of each cosine/sine generator 110 is applied to a different one of the mixers 111. The resulting output of each mixer 111 is applied to a different one of the coherent accumulators 114. The signal I,Q is also applied directly to one of the coherent accumulators 114 without being mixed; the unmixed signal I,Q, therefore, corresponds to zero Doppler offset (0Δf).

[0093] A signal PHASE is input to each of the cosine/sine generators 111 from the Doppler bin NCO 112. The rate of change in the signal PHASE represents the basic Doppler offset Δf and, therefore, the spacing of the Doppler offset bins. Each of the cosine/sine generators 111 generates its output mixing signal MS at a predetermined multiple of Δf, based on PHASE. The function of the cosine/sine generators 111 may be provided as a look-up in a look-up table using the value of PHASE. Register 113 stores a value N_SPACE, which is provided to the Doppler bin NCO 112 to control the rate of change of signal PHASE. The value N_SPACE, which is set by the CPU 6 using control signal FCTRL, may be determined dynamically based on various different parameters, such as current signals conditions, etc. See the discussion above with reference to FIG. 7A, for example.

[0094] Signal I,Q and the output of each mixer 110 is applied to a different one of the coherent accumulators 114. Accumulators 114 are digital integrator cells, which accumulate signals at their respective inputs over the coherent integration interval N_COH (separately for the in-phase and quadrature signals). Each coherent accumulator 114 includes m storage locations (where m is 512 in one embodiment), each capable of storing a multi-bit value for both in-phase and quadrature components.

[0095] The coherent integration interval N_COH is determined by the CPU 6 and is stored in register 116. The required number of non-coherent integrations N_NCOH is stored in register 118, which is also set by the CPU 6. The accumulator control circuit 115 receives the values N_COH and N_NCOH from registers 116 and 118, respectively, and receives the READY signal from the COBSS 72. In response, the accumulator control circuit 115 generates signals LOADA, ACCUMA, and ADDRA, each of which is simultaneously provided (e.g., via a bus) to each of the coherent accumulators 114. When asserted, signals LOADA and ACCUMA cause a particular one of the registers in each of the accumulators 114, as specified by address signal ADDRA, to load or accumulate the values at its input (for both in-phase and quadrature components), respectively. As noted above, the data transfer functions of the accumulations stage 74 are clocked by CLK2 and enabled by the READY signal. Thus, if READY is not asserted, then neither LOADA nor ACCUMA can be asserted.

[0096] The accumulator control circuit 115 also generates signals LOADB and ACCUMB, which are simultaneously provided to each of the MNCAs 117. The signals LOADB and ACCUMB are activated by the accumulator control circuit 115 to update each MNCA 117 with the coherently integrated values at the completion of N_COH coherent cycles. When asserted, LOADB and ACCUMB cause a particular one of the accumulators in each MNCA 117, as specified by address signal ADDRA, to load or accumulate, respectively, the values at its input.

[0097] Each of the coherent accumulators 114 outputs m multi-bit parallel outputs to a corresponding one of the MNCAs 117 for both the in-phase and quadrature components. Each MNCA 117 receives address signal ADDRA and, based on the specified address, selects a particular one of its parallel inputs (both in-phase and quadrature) from the corresponding accumulator 114. The MNCA 117 performs non-coherent accumulation of the magnitude values at its selected input. Once the MNCA 117 performs this function on a given set of inputs, the in-phase and quadrature components in those inputs are no longer processed separately. Thus, accumulated magnitude values are output by the MNCA 117 to both the TDBC 75 and the MPDC 76, the functions of which were discussed above.

[0098] FIG. 13 illustrates the accumulator control circuit 115 in greater detail. In the illustrated embodiment, the circuit 115 includes binary up counters 121, 122 and 123; AND gates 124, 125, 126, 127, 128 and 129; inverters 130 and 131; logic blocks 132 and 133; and comparators 134 and 135. Note that FIGS. 7B and 7C show the relationships between the outputs of counters 121, 122, and 123 and the quantities, N_COH, T_COH, N_NCOH, and T_NCOH, discussed above.

[0099] The elements of accumulator control circuit 115 are connected as follows. AND gate 124 receives as input the READY signal and CLK2. The output of AND gate 124 is applied to the clock input of a free-running, binary up counter 121. Counter 121 counts from zero to m−1, where m is the number of code offset bins per correlation segment, as noted above. The count output of counter 121 forms signal ADDRA. The overflow output of counter 121 is applied to the clock input of binary up counter 122. Counter 122 is used in generating signals ACCUMA and LOADA to the coherent accumulators 114 and is therefore referred to as “coherent” counter 122. The count output of coherent counter 122 is applied as input to logic block 133. Logic block 133 outputs a logic one (asserted) when the count output from coherent counter 122 is zero, and a logic zero (not asserted) otherwise. The output of logic block 133 is applied as one input of AND gate 129, which receives a second input from the output of AND gate 124. The output of AND gate 129 is signal LOADA.

[0100] Comparator 134 receives as input the value N_COH from register 116 (FIG. 12) and the count value output from coherent counter 122 and outputs a logic one when these two values are equal. The output of comparator 134 is applied to one input of AND gate 125. A second input of AND gate 125 is the output of AND gate 124. The count output of non-coherent counter 123 is applied as an input to logic block 132 and to comparator 135. Counter 123 is used in generating signals ACCUMB and LOADB to the MNCAs 117 and is therefore referred to as “non-coherent” counter 123. Logic block 132 outputs a logic one when the count output from non-coherent counter 123 is zero, and a logic zero otherwise. Comparator 135 also receives the value N_NCOH as input and outputs a signal DONE to the CPU 6. The signal DONE is logic one when the count of non-coherent counter 123 equals N_NCOH, indicating that the total integration time has elapsed (see FIGS. 7A, 703 and 704).

[0101] The output of logic block 132 is applied as an input to inverter 130 and to AND gate 127. The output of inverter 130 is applied to one input of AND gate 126. The other input of AND gate 126 is the signal LOADA. The output of AND gate 126 is signal ACCUMB. A second input of AND gate is signal LOADA. The output of AND gate 127 is signal LOADB.

[0102] The output of logic block 133 is also applied to the input of inverter 131. The output of inverter 131 is applied to one input of AND gate 128. AND gate 128 receives a second input from the output of AND gate 124. The output of AND gate 128 is signal ACCUMA.

[0103] It is generally desirable to limit power consumption in a GPS receiver. Memory in the receiver can be a significant source of power consumption, such as the memory used to provide the coherent accumulators 114 and/or non-coherent accumulators (MNCAs) 117 (FIG. 12). In one embodiment, at least the coherent accumulators 114 in each correlation segment are embodied as conventional, CMOS-based, synchronous DRAM, as is henceforth assumed in this description. Accordingly, power is consumed each time an accumulator is accessed, as a result of the well-known power characteristics of this type of memory. In one embodiment, the accumulators of each correlation segment are accessed every clock cycle, which can result in high power consumption.

[0104] As indicated above in connection with FIG. 6, two or more correlation segments (e.g., segments 61A and 61B) can be configured to operate in parallel. Each correlation segment includes 2n+1 coherent accumulators 114, as determined by the number of Doppler offset bins. Further, each coherent accumulator 114 includes m storage locations, where m is the number of code offset bins (which is 512 in one embodiment). Each storage location can store a multi-bit value. Summers 119 are coupled between the outputs and inputs of the accumulators 114 to enable the contents of each storage location to be accumulated.

[0105] Two or more correlation segments may be concatenated to improve the speed of signal acquisition. Concatenation is accomplished by coupling the outputs of the code and data shift registers in the CSR 105 (FIG. 11) of one correlation segment to the inputs of the code and data shift registers (respectively) of the CSR 105 in another correlation segment. Thus, if each correlation segment is capable of latching m-bit long code sequences, then the concatenation allows code sequences 2m (e.g., 1,024) bits in length to be latched, to effectively create 2m code offset bins. In such an embodiment, the timing of the concatenated correlation segments is coupled for synchronized control. As described above, the timing is controlled by the CPU via accumulator control circuit 115 (FIG. 12) in each correlation segment. Despite the concatenation, the segments continue to act as independent accumulators working on adjacent code phases, and the RAM in each correlation segment is still accessed during each clock cycle.

[0106] To reduce power consumption, a configuration such as shown in FIG. 14 may be used. As shown, summers 120 are provided with cross-connections 136 between correlation segments 61A and 61B. More specifically, in each correlation segment, a summer 120 is coupled between the I,Q output of the fractal adder 106 and the input of summer 119. Each summer 120 is also coupled to receive the I,Q output from the other correlation segment via cross-connection 136. The cross-coupling between the two correlation segments 61A and 61B allows the summation of the outputs of the fractal adders 106 of the two segments. Such summation allows the RAM (i.e., accumulators 114) in each correlation segment to be accessed less frequently than it would otherwise need to be accessed. Specifically, the coherent accumulators 114 in each segment can be active during only m of every 2m code phases. Hence, lower power consumption is achieved. The accessing of the accumulators is controlled by the CPU via accumulator control circuit 115 (FIG. 12) in each correlation segment. Further power savings can be achieved by performing single clock cycle read/modify/writes on all accumulators, since power consumption resulting from these operations tends to be non-cumulative or cumulative to a limited point.

[0107] Refer now to FIG. 15, which is a flow diagram illustrating the power savings technique associated with the configuration of FIG. 14. During the signal acquisition process, at 1501 data is stored in consecutive locations of the coherent accumulators 114 in segment 61A. During this period, the coherent accumulators 114 of segment 61B are not accessed. Thus, assuming for example that the two segments 61A and 61B each contain m correlators, then only the accumulators 114 in segment 61A are accessed for a period of m consecutive clock cycles, during which the accumulators 114 of segment 61B are not accessed. If all (m) locations in each of the accumulators 114 of segment 61A have been accessed at 1502, then the routine proceeds to 1503. At 1503 data is stored in the coherent accumulators 114 of segment 61B for m consecutive clock cycles, during which the accumulators 114 of segment 61A are not accessed. If all m locations of all accumulators in segment 61B are determined to have been accessed at block 1504, then the routine repeats from block 1501. The routine repeats until a signal is acquired.

[0108] Note that the above-described power savings technique can be implemented in a receiver that has more than two correlation segments operable in parallel. For example, a receiver might include four parallel correlation segments, which are cross-linked to form a 2,048-bit correlator. The power savings can be achieved by summing, in each correlation segment, the output of the fractal adder 106 of the correlation segment with the output of the fractal adders 106 of all other correlation segments, and accessing the accumulators 114 of that correlation segment only one-fourth the time. It will be recognized that this power savings technique can also be applied to receivers with different numbers of parallel correlation segments in a similar manner.

[0109] Thus, a method and apparatus have been described for reducing power consumption resulting from accessing memory in a GPS receiver. Although the present invention has been described with reference to specific exemplary embodiments, it will be evident that various modifications and changes may be made to these embodiments without departing from the broader spirit and scope of the invention as set forth in the claims. Accordingly, the specification and drawings are to be regarded in an illustrative rather than a restrictive sense.