Patent Publication Number: US-7898475-B2

Title: GNSS receiver with reduced storage requirements

Description:
RELATED APPLICATIONS 
     The present application claims the benefit of the following two co-pending India provisional applications, both of which are incorporated in their entirety herewith: 
     Serial number: 439/CHE/2008, entitled: “Area &amp; Performance Optimized Architecture for GPS Acquisition/Tracking correlator Channel”, filed on 21 Feb. 2008, naming Texas Instruments Inc. (the intended assignee) as the Applicant, and naming Jasbir Singh Nayyar as inventor. 
     Serial number: 487/CHE/2008, entitled: “Area &amp; Performance Optimized Architecture for GNSS Acquisition/Tracking Channel”, filed on 27 Feb. 2008, naming Texas Instruments Inc. (the intended assignee) as the Applicant, and naming Jasbir Singh Nayyar as inventor. 
     BACKGROUND OF THE INVENTION 
     1. Technical Field 
     Embodiments of the present disclosure relate generally to navigation system receivers, and more specifically to a Global Navigation Satellite System (GNSS) receiver with reduced storage requirements. 
     2. Related Art 
     GNSS generally refers to any of the satellite-based navigation systems, which broadcast GNSS signals carrying data (e.g., satellite position, time-of-transmission, various correction parameters, etc.) used by corresponding receivers to determine their respective positions based on the received broadcast data. Global Positioning System (GPS) and Galileo based Systems are some examples of GNSS. 
     It is generally desirable that a GNSS receiver be designed with reduced storage requirements, at least for reasons such as lower implementation cost and area, lower power consumption, etc. 
     SUMMARY 
     This Summary is provided to comply with 37 C.F.R. §1.73, requiring a summary of the invention briefly indicating the nature and substance of the invention. It is submitted with the understanding that it will not be used to interpret or limit the scope or meaning of the claims. 
     A Global Navigation Satellite System (GNSS) receiver provided according to an aspect of the present invention contains a buffer to store fewer than a number of samples spanning a code period of a received GNSS signal, with the samples being used by a correlator and a processor to perform various searches in the receiver. Due to the use of such smaller memory space in the buffer, the overall size of receivers may be reduced. 
     According to another aspect of the present invention, the amount of storage provided for storing local code and carrier samples (used during correlation) is also reduced by dynamically generating the partial values of the local code and carrier sample as required for generating partial correlation results. The overall size of receivers may be reduced due to such a feature also. 
     Several aspects of the invention are described below with reference to examples for illustration. It should be understood that numerous specific details, relationships, and methods are set forth to provide a full understanding of the invention. One skilled in the relevant art, however, will readily recognize that the invention can be practiced without one or more of the specific details, or with other methods, etc. In other instances, well-known structures or operations are not shown in detail to avoid obscuring the features of the invention. 
    
    
     
       BRIEF DESCRIPTION OF THE VIEWS OF DRAWINGS 
       Example embodiments of the present invention will be described with reference to the accompanying drawings briefly described below. 
         FIG. 1  is a block diagram of an example environment in which several aspects of the present invention can be implemented. 
         FIG. 2  is a diagram illustrating an example signal structure of an example GNSS signal. 
         FIG. 3  is a block diagram of a GNSS receiver in an embodiment of the present invention. 
         FIG. 4  is a block diagram of a baseband processing block in an embodiment. 
         FIG. 5A  is a diagram illustrating the manner in which correlation operations are performed by a channel in an embodiment. 
         FIG. 5B  is a timing diagram illustrating the operation of a channel in an embodiment. 
         FIG. 6  is a diagram of a table containing partial sums generated in a channel in an embodiment. 
         FIG. 7  is a block diagram of a baseband processing block in an alternative embodiment. 
         FIG. 8  is a diagram illustrating the manner in which correlation operations are performed by a channel in an alternative embodiment. 
         FIG. 9  is a timing diagram illustrating the operation of a channel in an alternative embodiment. 
     
    
    
     The drawing in which an element first appears is indicated by the leftmost digit(s) in the corresponding reference number. 
     DETAILED DESCRIPTION 
     Various embodiments are described below with several examples for illustration. 
     1. Example Environment 
       FIG. 1  is a block diagram of an example environment in which several aspects of the present invention can be implemented. The diagram is shown containing GNSS receiver  110 , and GNSS transmitters  120 ,  130 ,  140  and  150 . Merely for illustration, the components of  FIG. 1  are assumed to correspond to a satellite-based navigation system such as GPS, Galileo, and GLONASS systems. However, several of the features can be implemented in other GNSS environments, as well as in environments in which multiple GNSS systems are used in combination (e.g., GPS plus Galileo), as will be apparent to one skilled in the relevant arts by reading the disclosure provided herein. Similarly, merely for illustration, the environment is chosen to contain fewer transmitters, etc., though several real-world environments contain many more devices, both in type and number. 
     Assuming a satellite-based navigation system environment, each of GNSS transmitters  120 ,  130 ,  140  and  150  corresponds to a satellite transmitting a corresponding GNSS signal containing information (data values) that enables GNSS receiver  110  to determine its position. Only four GNSS transmitters and one receiver are shown for simplicity. However, typically many more transmitters and receivers may be present in corresponding environments. GNSS transmitters  120 ,  130 ,  140  and  150  respectively transmit GNSS signals  121 ,  131 ,  141 , and  151 . 
     GNSS receiver  110  receives signals  121 ,  131 ,  141  and  151  (via antenna  111 ), and determines its position (typically in a Cartesian coordinate system, or as latitude, longitude and height with respect to the earth&#39;s surface) in a manner well known in the relevant arts, once the data values from the received signals are recovered. For ease of description signals  121 ,  131 ,  141  and  151  are together referred to as signal  111 . 
     Several features of the present invention enable GNSS receiver  110  to be implemented with smaller area and resource requirements (e.g., smaller buffer memory). The features can be better appreciated based on an understanding of the structure of the signal received at antenna  111 . Accordingly, the description is continued with respect to an example signal structure of a transmitted GNSS signal (e.g., any of  121 ,  131 ,  141  and  151 ). 
     2. Example Signal Structure 
       FIG. 2  is a diagram illustrating an example signal structure of a GNSS signal (either transmitted by transmitter  120  or received at antenna  111 ). It may be noted that the specific details of the signal may be different from that shown in  FIG. 2 , based on the specific type of GNSS signal. The diagram shows details of signal  121  though the description is applicable to other signals  131 ,  141 , and  151  as well. It should be appreciated that waveform  240  is shown on an ‘expanded’ time scale (for clarity) and the inter-relation of specific portions is illustrated by arrows. 
     Waveform  210  represents a spreading code used to spread the bandwidth occupied by the data ( 220 ) to a much wider bandwidth according to direct sequence spread spectrum technology. As is well known, each transmitter  120 / 130 / 140 / 150  uses a corresponding different code. Waveform  210  is shown containing multiple code bits in each code period T, and may be a pseudo random binary (PRN) sequence. The code is shown as the sequence 10010100100 merely for illustration. 
     Waveform  220  contains data values (with each value containing potentially several bits) representing information that enables GNSS receiver  110  to determine its (receiver&#39;s) position, and may include the position of satellite  120 , orbital information of satellite  120 , clock information, various correction parameters, etc., as is well known in the relevant arts. A single data bit of a GNSS signal can span one or more code periods, and the corresponding duration is referred to as a data bit period. The time-relationship between a data-bit period and code period may be different for different GNSS systems. 
     Data  220  and code  210  are combined to generate waveform  230 . In the context of GPS GNSS system, data  220  and code  210  are combined using an exclusive-OR (XOR) operation to generate waveform  230 , as shown with example code and data portions in  FIG. 2 . Each bit (or symbol, in general) of waveforms  210  and  230  is also referred to as a chip. Chip  290  is marked in  FIG. 2  as an illustration. However, alternative combining techniques can be used to generate the combined value, as will be apparent to one skilled in the relevant arts by reading the disclosure provided herein. Further, in non-GPS contexts such as Galileo System, such combination may be performed in a different manner. 
     Waveform  230  modulates a carrier of a predetermined frequency, and an example modulated carrier (GNSS signal) is represented by waveform  240 . With respect to GNSS signal  240 , it is assumed that BPSK modulation is used (though other techniques can be used, without departing from the scope and spirit of various aspects of the present invention) to modulate the carrier, as may be observed from waveform  240 , only a portion of which is shown. It is noted that in  FIG. 2 , only three carrier cycles are shown corresponding to one code bit period. However, typically the number of carrier cycles in one code bit period is much larger. 
     As is well known in the relevant arts, GNSS signals  121 ,  131 ,  141  and  151  may each represent a different code, but on a same carrier frequency for a same GNSS system. Thus, all transmitters of GPS would transmit on one frequency, while all transmitters of Galileo system would transmit on some other frequency. GNSS receiver  110  extracts data  220  from a GNSS signal  121  by generating a local signal (which is formed by combining a replica of code  210  and the carrier in a similar manner as in GNSS transmitter  120 ), and performing correlation operations with the generated local signal with signal  121  (or a down-converted baseband signal corresponding to signal  121 ). GNSS receiver  110  extracts data from signals  131 ,  141  and  151  in a correspondingly similar manner. 
     3. Example Receiver 
       FIG. 3  is a block diagram illustrating the details of a GNSS receiver in an embodiment. GNSS receiver  110  is shown containing antenna  111 , front-end processing block  310 , analog to digital converter (ADC)  320 , decimation and filtering block  330 , baseband processing block  340 , processor  350 , and memory  360 . The details of the diagram are provided merely by way of illustration, and other embodiments may contain fewer or more components, and corresponding interconnections. 
     Antenna  111  receives GNSS signals  121 ,  131 ,  141  and  151 , and provides the signals on path  311  to front-end processing block  310 . The combination of all the GNSS signals provided by antenna  111  to front-end processing block  310  is also referred to in this application as “received GNSS signal”. Thus, “received GNSS signal” at antenna  111  may contain multiple types of GNSS signals (GPS, Galileo, etc), as well as multiple numbers of each type from corresponding transmitters. 
     Front-end processing block  310  may perform various front-end analog signal processing operations, such as band-pass filtering, amplification using a low-noise amplifier etc., on the received GNSS signal. Front end processing block  310  may also perform one or more levels of down-conversion to lower the carrier frequency to a lower frequency (e.g., intermediate frequency/IF). Front end processing block  310  provides the processed signal (e.g., IF signal) to ADC  320  via path  312 . The operations as well as components within front-end processing block  310  may be designed to operate with CDMA (code division multiple access, e.g., GPS, Galileo) as well as FDM (Frequency division multiplexed, E.g., GLONASS) type of GNSS signals. 
     ADC  320  samples signal  312  to generate corresponding digital codes/samples. The sampling rate may be selected to be sufficiently high such that code and data information in the IF signal is preserved. ADC  320  provides the samples to decimation and filtering block  330  on path  323 . In some embodiments, decimation and filtering block  330  may not be implemented, and ADC  320  may provide the samples directly to baseband processing block  340 . 
     Decimation and filtering block  330  performs various operations on the samples received on path  323  to further reduce (down-convert) the IF frequency to baseband. Thus, decimation and filtering block  330  provides the final down-converted signal at baseband to baseband processing block  340 . In some embodiments, decimation and filtering block  330  may also operate to remove a common carrier Doppler component (common to all transmitted GNSS signals caused, for example, by a frequency offset/variation in a master clock used to generate local signals in receiver  110 , for example, in baseband processing block  340 ). Decimation and filtering block  330  provides samples corresponding to the final down-converted signal (referred to also as the baseband GNSS signal) to baseband processing block  340  on path  334 . 
     Decimation and filtering block  330  may be implemented to provide different decimation rates for different types of GNSS signals (GPS, Galileo System, etc), and may correspondingly provide samples at different desired rates on path  334  (which may thus contain multiple paths). As an illustration, ADC  320  may sample signal  312  at a frequency of ‘S’ samples per second. Based on the specific type of GNSS signal to be processed, as well as the specific type of processing (whether a GNSS signal is being acquired or tracked), decimation and filtering block may be implemented to cause only a fraction of the samples (e.g., every other sample) to be forwarded on path  334 . ADC  320  and decimation and filtering block  330  may (optionally) receive control signals via path  353  from processor  350  to set various parameters (e.g., decimation rate, sampling rate, etc.) related to their operations. 
     Baseband processing block  340  generates local signals corresponding to each transmitted GNSS signal, and correlates the received GNSS signal with each of the local signals to acquire (lock onto) and track (to maintain lock) the transmitted GNSS signals. Each local signal is a carrier signal modulated by a corresponding spreading code. The frequency of the locally generated carrier may be at baseband (approximately equal to the carrier frequency of a signal on path  334 ). Baseband processing block  340  provides results (typically a number representing the degree of similarity of the corresponding local and transmitted GNSS signal) of correlation operations to processor  350  via path  345 . Baseband processing block  340  may receive operational commands, initialization commands and data, clocks, etc., from processor  350  via path  345 . 
     As is well known, acquisition of a GNSS signal typically involves various searches/operations such as code phase searches and carrier Doppler searches. A code phase search implies aligning the spreading code of a GNSS signal with a locally generated replica code in receiver  110 . A Doppler search is directed to (precise) determination of the carrier frequency of a baseband GNSS signal accounting for frequency changes due to Doppler effects. While the applicable standards specify a nominal carrier frequency, the actual frequency with which a GNSS signal is received can deviate from the nominal due to Doppler effect caused by relative motion between a GNSS receiver and a satellite. Once a signal is acquired, tracking may also require adjustments to local code and carrier phases and/or frequencies. 
     Hence, baseband processing block  340  performs code phase searches and carrier Doppler searches corresponding to each GNSS signal (e.g., for each of signals  121 ,  131 ,  141  and  151  shown in  FIG. 1 ). The local signal corresponding to each iteration may potentially contain a different carrier frequency and/or code phase, and is generated to correspond to a desired GNSS signal that is to be acquired and tracked. A detailed description of signal acquisition and tracking is not provided here in the interest of conciseness, and any of several well known techniques may be employed. 
     Processor  350  processes the correlation results received via path  345  from baseband processing block  340  to control the various acquisition/tracking operations, to extract the data transmitted by the satellites, to estimate the time taken for the signal to reach receiver  110 , among various other operations, to determine the position of GNSS receiver  110  according to any of several known techniques. Processor  350  may correspond to a general purpose processor or to an application specific processor such as a digital signal processor (DSP). 
     Several features of the present invention enable baseband processing block  340  to be implemented with smaller storage requirements, and hence with smaller area. An embodiment is described in detail next. 
     4. Baseband Processing Block with Smaller Storage Area 
       FIG. 4  is a block diagram of a baseband processing block in an embodiment. Baseband processing block  340  is shown containing buffers  410 A,  410 B,  410 C,  410 D and  410 E, and N-channel correlation block ( 490 ) containing channels  490 - 1  through  490 -N, and bus  402 . The internal details of only channel  490 - 1  is shown, and channels  490 - 2  through  490 -N may be implemented in a similar manner. GNSS samples stored in the buffers is available for processing (by selection in the corresponding multiplexer) to each of the channels. Thus, each of the buffers  410 A through  410 E may be viewed as being ‘common’ to all the channels. Each channel may be selected to acquire/track a different GNSS signal (e.g., a GPS signal with specific code, Galileo signal), though multiple channels can be operated to process a same GNSS signal. 
     Channel  490 - 1  is shown containing multiplexer (MUX)  420 , local carrier generator  430 , coefficients storage  435 , correlator  440 , code forming block  450 , code storage  452 , code interpolator and integrator  460 , coherent sum storage  470  and non-coherent sum storage  480 . The operations of the various blocks of baseband processing block  340  may be controlled by (synchronized with) clock  345 Clk, provided by processor  350 . While shown in  FIG. 4  as containing five buffers ( 410 A,  410 B,  410 C,  410 D and  410 E), baseband processing block  340  can be implemented with fewer or more buffers. 
     Paths  334 A,  334 B,  334 C,  334 D, and  334 E are deemed to be contained in path  334  of  FIG. 3 . Buffers  410 A,  410 B,  410 C,  410 D and  410 E receive a respective sequence of samples representing received GNSS signal  111  (being the combination of signals  121 ,  131 ,  141  and  151 ) on respective paths  334 A,  334 B,  334 C,  334 D and  334 E. The sequences on the paths may correspond to samples at different rates. In an embodiment, buffer  410 A receives samples with a sampling rate of 2 samples per symbol (sps), and the samples may be used by one or more channels ( 490 - 1  through  490 -N) during acquisition phase of corresponding GPS signals. 
     Buffer  410 B receives samples with a sampling rate of 4 sps, and the samples may be used by one or more channels ( 490 - 1  through  490 -N) during tracking phase of corresponding GPS signals. Buffers  410 C,  410 D and  410 E respectively receive samples with sampling rates of 1 sps, 1 sps and 4 sps, and used respectively for acquisition of upper side band of Galileo signal, acquisition of lower side band of Galileo signals, and for tracking of Galileo signals. Samples in each of buffers  410 A,  410 B,  410 C,  410 D and  410 E are provided to multiplexers in channels  490 - 1  through  490 -N via bus  402 . The paths from each of the buffers to bus  402  may be serial or parallel (multiple paths from each storage location of the buffers to bus  402 ). 
     Each of channels  490 - 1  through  490 -N operates to acquire and track a corresponding GNSS signal, as specified, for example by processor  350 . For example, channel  490 - 1  may be used to acquire and track signal  121  transmitted by satellite  120  (by using the same code as that used by satellite  120  and a local carrier), while channel  490 - 2  may be used in relation to signal  131  (by using the code used by satellite  130  and a local carrier), etc. Channels  490 - 3  through  490 -N may similarly be used to acquire and track other GNSS signals (of other navigational systems). Alternatively, multiple correlators may be used for correlation with a same GNSS signal at least for small durations of operation. In general, the specific code (spreading code) and local carrier frequency used in a channel determines the specific transmitted GNSS signal that is searched for or tracked. 
     MUX  420  receives a control signal on path  421  (contained in path  345  of  FIG. 3 ), for example, from processor  350  ( FIG. 3 ), and forwards samples on path  424  from a selected one of buffers  410 A,  410 B,  410 C,  410 D and  410 E to correlator  440 . Thus, processor  350  may control the specific combination of mode (for example, acquisition vs. tracking)-navigational system (for example, GPS vs. Galileo) by controlling MUX-control-input  421  for the corresponding channel. The specific GNSS signal ( 121  vs.  131  vs.  141 , etc., of  FIG. 1 ) being searched for, may be controlled by controlling the appropriate values in code forming block  450 . 
     Local carrier generator  430  stores (via path  433 ) digital samples (termed Doppler coefficients) representing a local carrier signal in coefficients storage  435 . The Doppler coefficients may be generated using well-known techniques, such as for example, using phase accumulator techniques. The local carrier signal approximately equals the carrier frequency of the baseband GNSS signal that channel  490 - 1  is selected for acquiring/tracking. As is well known in the relevant arts, the difference in the carrier frequencies between the locally generated carrier and the carrier of a baseband GNSS signal may be due to Doppler effects caused by relative motion between receiver  110  and the transmitting satellites ( FIG. 1 ), ignoring offsets and drifts in the time-base generators (master clocks) in the satellites and receiver  110 . 
     Code forming block  450  provides, on path  455 , a local code (in the form of corresponding digital samples) corresponding to the specific GNSS signal that is desired to be processed. Code forming block  450  contains circuitry for generating the code samples (e.g., using Linear Feedback Shift Registers), as well as storage elements for storing the generated local code chip samples. Code storage  452  stores the code chips/bits received on path  455 . In an embodiment, all code bits and all Doppler coefficients required for processing are generated and stored (in code storage  452  and coefficients storage  435  respectively) prior to commencement of processing of the GNSS signal, for example, at the time of initialization of a channel, to process a specific GNSS signal. 
     Correlator  440  combines the local code and local carrier samples received on paths  454  and  434  respectively to generate a local signal. Correlator  440  correlates the local signal with the baseband GNSS signal received on path  424 , for example, by multiplying corresponding samples of the baseband GNSS signal and the local signal. Correlator  440  provides the product on path  446 . 
     Code interpolator and integrator  460  performs coherent and/or non-coherent addition (digital integration) of the correlation products received on path  446  to generate a sum, which is forwarded for storage either on path  467  to coherent sum storage  470  or on path  468  to non-coherent sum storage  480  based on whether coherent integrations or non-coherent integrations are performed in channel  490 - 1 . Code interpolator and integrator  460  also removes code Doppler (Doppler effects on code samples of the GNSS signal). Coherent sum storage  470  and non-coherent sum storage  480  are storage components such as, for example, random access memory (RAM), flash memory, etc. Processor  350  retrieves the multiplied-and-accumulated sums in coherent sum storage  470  and/or non-coherent sum storage  480  (via path  345 A), and partial sums from storage elements in the other channels (channel  490 -N and retrieval path  345 N are shown), and processes the sums to determine the position of receiver  110 , universal coordinated time (UTC), etc., using techniques well known in the relevant arts. 
     In an approach described in co-pending application entitled, “Doppler And Code Phase Searches In A GNSS Receiver”, naming Jasbir Singh Nayyar as inventor, Ser. No. 12/045,047, filed on: 10 Mar. 2008, which is incorporated in its entirety into the present application, buffers to store GNSS samples are implemented with a storage size of at least one code period worth of samples of the corresponding type of GNSS signal. However, such an approach may not be efficient in terms of implementation area and cost. Further, with such an approach, larger buffer sizes may be required when the code period is longer (more number of symbols/chips in a code period). Hence, the storage area may increase proportionately with respect to code period length. Another potential drawback with the above-noted approach is that for higher sampling rates (generally required for more precise determination of position, such as during a tracking phase), the buffer sizes further increase. Also, for better performance (accuracy, sensitivity and TTFF—time to first fix), the GNSS samples may need to be represented using multiple bits, which further increases the storage requirements The buffer size/area requirement may become even larger if such buffers need to be replicated for each channel. 
     According to an aspect of the present invention, each of buffers  410 A,  410 B,  410 C,  410 D and  410 E is implemented to have a storage size less than the number of samples generated corresponding to one code period of corresponding GNSS signal, and are thus designed to store fewer than a number of samples spanning one code period of a GNSS signal. To illustrate and clarify, assuming buffer  410 A is implemented to store samples of GPS type of GNSS signal (one code period of a GPS L1 C/A signal containing 1023 chips), its storage size is less than the number of samples generated corresponding to 1023 chips. 
     In an embodiment, two samples are generated (by decimation and filtering block  330 ) per chip of a GPS signal, and hence 2046 samples would be generated corresponding to one code period. The storage size of buffer  410 A is implemented with a memory capacity to store less than 2046 samples in this example. 
     New ‘incoming’ samples of a GPS signal are sequentially (serially) stored in buffer  410 A, overwriting the ‘old’ samples. Buffer  410 A may thus be viewed as a shift register with ‘new’ incoming samples being ‘shifted-in’, while older (in time) samples are shifted out (and discarded). All of channels  4901 - 1  through  4901 -N selected to process the samples in buffer  410 A receive the samples stored in buffer  410 A. Thus, in addition to a storage size less than ‘one code period worth’, the same buffer ( 410 A) provides samples to all channels that are selected to process the samples. 
     Each of the other buffers ( 410 B,  410 C,  410 D and  410 E) is implemented similarly with a size less than “one code period worth samples” of the corresponding GNSS signals to be stored in the buffers, and also provide the stored samples to all the channels selected to process the corresponding samples. 
     Thus, in the embodiment illustrated with respect to  FIG. 4 , buffer  410 B has a storage size less than 4096 samples (corresponding to GPS signal sampled at 4 sps). Buffer  410 C has a storage size less than 4096 samples (corresponding to USB of Galileo signal sampled at 1 sps). Buffer  410 D has a storage size less than 4096 samples (corresponding to LSB of Galileo signal sampled at 1 sps). Buffer  410 E has a storage size less than 16384 samples (corresponding to Galileo signal, USB plus LSB, sampled at 4 sps). It may, therefore, be appreciated that the buffer implementation described above reduces overall storage requirements in baseband processing block  340  (receiver  110  in general), and thus the implementation area. In addition, processing of GNSS signals with large code period lengths, as well as sample-generation of GNSS samples with higher sampling rates may be efficiently accommodated without substantial increase in implementation area. Further, since the data in the buffers are available to all the channels, implementation area is further reduced. An example description of the operation of a channel using a storage buffer implemented as described above is provided next. 
     5. Operation 
       FIG. 5A  is a block diagram illustrating the manner in which correlation operations are performed by a channel in an embodiment. Correlator  440 , code forming block  450 , and local carrier generator  430  contained in channel  490 - 1  ( FIG. 4 ), and buffer  410 A ( FIG. 4 ) are shown in  FIG. 5A . For ease of description, it is assumed that the GNSS signal which channel  490 - 1  is configured by processor  350  to acquire and track, contains a code with a period of eight chips (bits), and is sampled at a rate of 1 sps. It is assumed, again to simplify description that only two carrier phases (two carrier Doppler hypotheses) are searched for. 
     Buffer  410 A contains memory elements (each with a hardware support, e.g., in the form of transistors) which may be implemented as a shift register. The size (memory space) in buffer  410 A equals two GNSS samples corresponding to ¼ of the period. It is noted that while a sample of a GNSS signal may, in general, contain multiple bits, it is assumed that each sample is represented by a single bit (i.e., either logic 0 or logic 1) to simplify the following description. 
     Samples representing a baseband GNSS signal (with a code period of 8chips) are received by buffer  410 A via path  334 A, with two samples (also equal to two bits in the example) being stored in buffer  410 A at a time. Representing C 1 -C 8  as the 8 samples (or 8 bits) obtained corresponding to one code period duration,  FIG. 5A  is shown with the first two samples C 1  and C 2  stored in buffer  410 A (newer/later successive samples C 3 -C 8  shown in dashed boxes in  FIG. 5A , for clarity in the description below). 
     Buffer  410 A provides the two stored samples on paths  424 A and  424 B (deemed to be contained in path  424 ) to multipliers  510 A and  510 B respectively. Hence, path  412 A of  FIG. 4  contains two separate paths, each providing the two samples stored in buffer  410 A to bus  402 , which in turn provides the two bits (in parallel) to MUX  420 . MUX  420  provides the two chips on path  424 . In  FIG. 5A , buffer  410 A is shown as directly providing the two stored samples directly on path  424  merely as an illustration. 
     Code forming block  450  is shown containing storage register(s)  580 , with the register  580  having a size equal to and storing 8 chips/bits, I 1 -I 8 , representing the eight code chips of the GNSS signal to be acquired/tracked. Local carrier generator  430  is shown containing Doppler coefficients F 11 -F 18  (labeled as  540 ) for one carrier phase to be searched for, and Doppler coefficients F 21 -F 28  (labeled as  550 ) for the second carrier phase to be searched for. The labels  540  and  550  are also referred to in the description below as Doppler hypotheses. 
     Correlator  440  is shown containing multipliers  510 A and  510 B, summing block  520 , and MUX  560 . MUX  560  receives local carrier samples on paths  545 A,  545 B,  555 A and  555 B, and based on the value of control input  562 , forwards either the carrier sample-pairs on paths  545 A and  545 B, or on paths  555 A and  545 B, onto paths  561 A and  561 B respectively. 
     Multiplier  510 A receives a GNSS sample on path  424 A, and multiplies the GNSS sample with a sample (local sample) representing a combination of a local code chip and a local carrier sample, received respectively on paths  531 A and  561 A. The combination of the local code chip and local carrier sample may be performed based on the specific type of GNSS signal sought to be processed (e.g., using XOR operation in the case of GPS). The combination operation and corresponding circuitry are not shown in  FIG. 5A , but can be implemented using well known techniques. 
     Multiplier  510 A provides the product of the GNSS sample and local sample on path  512 A. Multiplier  510 B provides, on path  512 B, a product of a GNSS sample received on path  424 B and a local sample representing the combination of a local code chip and carrier sample received respectively on paths  531 B and  561 B. Summing block  520  adds the products received on paths  512 A and  512 B to form a partial sum, and forwards the partial sum on path  446 . 
     The operations of the blocks of  FIG. 5A  in performing code phase and carrier phase searches are described with combined reference to the timing diagram of  FIG. 5B  and the correlation results table shown in  FIG. 6 . It is first noted that for the example of  FIGS. 5A ,  5 B and  6 , one complete (over one code period) correlation results for one code phase and one carrier phase (one Doppler hypothesis) search contains four partial sums (provided on path  446 ). Example correlation results for code phase C 1  and Doppler hypothesis  540 , as well as for code phase C 8  and Doppler hypothesis  550  are respectively represented by equations 1 and 2 below:
 
Phase C 1−Doppler540=[ I 1. C 1. F 11+ I 2. C 2. F 12]+[ I 3. C 3. F 13+ I 4. C 4. F 14]+[ I 5. C 5. F 15+ I 6. C 6. F 16]+[ I 7. C 7. F 17+ I 8. C 8. F 18]  Equation 1
 
Phase C 4−Doppler550=[ I 1. C 4. F 21+ I 2. C 5. F 22]+[ I 3. C 6. F 23+ I 4. C 7. F 24]+[ I 5. C 8. F 25+ I 6. C 1. F 26]+[ I 7. C 2. F 27+ I 8. C 3. F 28]  Equation 2
 
     In Equations 1 and 2, the terms within brackets, such as [I 1 .C 1 .F 11 +I 2 .C 2 .F 12 ], represent partial sums provided on path  446 . Each term contains two partial correlations, with each partial correlation result being obtained as noted above. For example, the partial correlation I 1 .C 1 .F 11  of partial sum [I 1 .C 1 .F 11 +I 2 .C 2 .F 12 ] is generated by multiplier  510 A, by multiplying GNSS sample bit C 1  (received on path  424 A) with the local sample represented by the combination (I 1 .F 11 ). 
     In the table of  FIG. 6 , column labeled “SHIFT” represents the number of GNSS sample-shifts that occur in buffer  410 . SHIFT  0  represents a state (or time interval) when GNSS samples C 1  and C 2  are stored, SHIFT  1  represents a state when GNSS samples C 2  and C 3  are stored, with C 1  having been shifted out (leftwards in  FIG. 5A ) and discarded, SHIFT  2  represents a state when GNSS samples C 3  and C 4  are stored, with C 2  having been shifted out and discarded, and so on. Time intervals T 0  through T 7  represent intervals in which correlator  440  generates the partial sums corresponding to a SHIFT state, and shown in the corresponding columns T 0 -T 7 . 
     It may be appreciated that although time is shown in  FIG. 5B  only along the X axis, T 0  through T 7  of SHIFT  0  occur in forward chronological order, followed by T 0  through T 7  of SHIFT  1  (represented by arrow  590 ), then by T 0  through T 7  of SHIFT  2  (represented by  591 ), and so on. In the timing diagram of  FIG. 5B , only the partial sums generated for SHIFT  0 , SHIFT  1 , SHIFT  2  and SHIFT  5  are shown, for conciseness. 
     Assuming that correlation operation start with samples C 1  and C 2  stored in buffer  410 A (SHIFT  0  state), correlator  440  generates, in time interval T 0  (of SHIFT  0 ), partial sumT 0 _ 0  ([I 1 .C 1 .F 11 +I 2 .C 2 .F 12 ]) for code phase C 1  and Doppler hypothesis  540 , and partial sumT 1 _ 0 , ([I 1 .C 1 .F 21 +I 2 .C 2 .F 22 ]) for code phase C 1  and Doppler hypothesis  550 . The two partial sums are shown along row SHIFT  0 , and under columns T 0  and T 1  respectively. The other partial sums shown in  FIGS. 5B and 6  are generated in the corresponding time intervals of the corresponding SHIFT state, as may be verified. 
     The table of  FIG. 6  shows the partial sums for one complete code phase search (for all possible eight code phases) and covering two Doppler hypotheses, with partial sum [I 7 .C 6 .F 27 +I 8 .C 7 .F 28 ] being the last partial sum generated. In general, all the partial sums of  FIG. 6  are provided to processor  350  (via storages  470  and  480 ), which processes the sums in a known way for locking, tracking and/or data recovery purposes. As noted above, the position can be determined in a known way (typically based on data from 3 or more satellites) once the data is recovered from the corresponding satellites. 
     Thus, assuming the GNSS signal searched for is received and has a sufficiently high signal-to-noise ratio, the sum of a corresponding sequence of four of the partial sums (e.g., as given in equation 1 or 2, the corresponding partial sums being shown circled in  FIG. 6 ) may indicate that the GNSS signal has been locked onto (acquired). Otherwise, correlator  440  may repeat the correlations described above till signal lock is achieved, or a command from processor  350  to search for a different GNSS signal is received. 
     Assuming a lock is obtained, channel  490 - 1  may be provided with samples from buffer  410 B (4-samples-wide storage) to continue to track the acquired GNSS signal. Other channels may be configured to perform correlations to acquire/track GNSS signals in a similar manner to that described above. 
     The description above is provided assuming code period of 8 chips, and only two Doppler hypotheses merely to serve as an illustration. It may be appreciated that the technique may be extended for real world GNSS signals. For example, to acquire and track a GPS C/A L1 type GNSS signal, code forming block  450  may internally store 1023 local code chips, and local carrier generator  430  may store more than two sets of Doppler coefficients. In general, the number of sets of Doppler coefficients may be selected depending on whether estimates of the position of receiver  110  and the local time are available a priori (e.g., whether receiver  110  is in cold start, warm start, hot start modes, etc.). 
     It may be observed from the description above that a complete correlation is obtained by accumulating partial results (which may be stored in coherent sum storage  470  or non-coherent sum storage  480 ) that are ‘spread across’ a code period. 
     Further, it may also be observed that all possible (or desired) partial correlation sums may be generated (e.g., for all code phases plus desired Doppler hypotheses) with the samples stored in buffer  410 A (or the other buffers) before partial sums are generated with a next set of GNSS samples. As an illustration, partial sums corresponding to all eight local codes and both Doppler hypotheses  540  and  550  are generated in cycles T 0 -T 8  of SHIFT  5  (row  5  in  FIG. 6 ), using samples C 6  and C 7  in buffer  410 A. 
     Subsequently, partial sums corresponding to all eight local codes and both Doppler hypotheses  540  and  550  are generated in cycles T 0 -T 8  of SHIFT  6  (row  6  in  FIG. 6 ), using samples C 7  and C 8  in buffer  410 A. As a result, multiple code phase searches as well as Doppler hypotheses may be performed to obtain at least partial results (which may at a later time instance be combined) in a time-efficient manner. 
     As another benefit of the techniques illustrated with respect to  FIG. 5A ,  5 B and  6 , degradations in correlation sums resulting potentially due to bit-flips occurring in the received GNSS samples are minimized or eliminated. 
     The frequency of operation (frequency of clock  345 Clk) required is expressed by the following formula:
 
 f =( M*L*S/W )* Cf   Equation 3
 
     wherein, 
     f is the required frequency for clock  345 Clk, 
     M is the number of Doppler hypotheses, 
     L is the number of symbols or chips in one code period of a GNSS signal desired to be acquired/tracked, 
     W is the number of correlation products generated in one clock cycle of clock  345 Clk, and also corresponds to the number of multipliers similar to  510 A and  510 B provided in hardware (along with corresponding input connections), 
     S is the number of samples of the GNSS signal generated per chip or symbol, and 
     Cf is the chipping or symbol frequency of the GNSS signal. 
     Thus, for acquisition/tracking of GPS C/A signals at L1 band, with S (of equation 3) equal to 2 sps, one Doppler hypothesis (M=1), and W equaling 66, a required frequency for  345 Clk is (1023*2/66*1.023) Mega Hertz), i.e., 31.71 MHz. The storage size of buffer  410 A for such a scenario is 132 samples (S*W), rather than 2046 samples (1023*2) if the entire code period worth of samples were instead stored. It may be appreciated that by reducing the code phase uncertainty or by increasing the operational frequency, multiple Doppler searches may be performed as well. 
     For example, employing the same 31.71 MHz operational frequency, two Doppler searches and approximately 512 chip code uncertainty can be searched for. The example numbers provided above are intended merely to be illustrative, and other values can be used depending on the specific requirements and implementation scenarios. 
     It is further noted that the number of Doppler coefficients can be reduced. As an illustration, for a Doppler uncertainty of +6 KHz, carrier phase may be assumed to remain constant for a predetermined number of GNSS samples, with a corresponding acceptable signal-to-noise ratio loss. For example, a 6 KHz Doppler changes carrier phase by less than 23 degrees for 11 chip period. Therefore, storage for Doppler coefficients can be reduced by quantizing the phase values to 45 degrees. For W equaling 66, as in the example above, such quantization necessitates only six coefficients per 66-chip duration for one Doppler hypothesis. Therefore, storage for only (2×6×M) Doppler coefficients is needed instead of 1023/11×M coefficients. 
     The approach described above requires storage elements to store all local samples, (local code samples within code forming block  450  and Doppler coefficients within local carrier generator  430 ). Since one set of local samples needs to be stored for each of channels  490 - 1  through  490 -N, total storage area for the local samples may be unacceptably high, in some implementation scenarios. According to another aspect of the present invention, in addition to reduced storage area for storing GNSS samples, the storage area for storing local samples is also reduced. An embodiment illustrating such features is described next. 
     6. Reducing Storage Area for Local Samples 
       FIG. 7  is a block diagram of a baseband processing block in an embodiment. As described below, the approaches implemented operate to reduce storage size for local samples as well as received GNSS samples. Baseband processing block  700 , which can be implemented in place of baseband processing block  340  of  FIG. 3 , is shown containing shadow buffer  710 , buffer  720 , and N-channel correlation block ( 790 ) containing channels  790 - 1  through  790 -N, and bus  702 . The internal details of only channel  790 - 1  is shown, and channels  790 - 2  through  790 -N may be implemented in a similar manner. 
     Channel  790 - 1  is shown containing correlator  730 , code storage  740 , code forming block  745 , coefficients storage  750 , coefficients shadow register  755 , code interpolator and integrator  760 , local carrier generator  770 , coherent sum storage  780  and non-coherent sum storage  785 . The operations of the various blocks of baseband processing block  700  may be controlled by clock  345 Clk. 
     Code forming block  745 , local carrier generator  770 , code interpolator and integrator  760 , coherent sum storage  780  and non-coherent sum storage  480  operate similar to code forming block  450 , local carrier generator  430 , code interpolator and integrator  460 , coherent sum storage  470  and non-coherent sum storage  480  of  FIG. 4  respectively, and the description of their operation is not repeated in the interest of conciseness. 
     Each of shadow buffer  710  and buffer  720  is implemented to have a storage size less than one code period worth of samples corresponding to the type of GNSS signal desired to be acquired/tracked. It may be observed that the combination of  710 / 720  corresponds to one of the buffers  410 A- 410 E. 
     Shadow buffer  710  stores GNSS samples received on path  334  (for example, in serial form). When shadow buffer  710  is full, control circuitry (not shown) causes the stored samples (which may be viewed as one window of GNSS samples (‘window samples’) with respect to a complete code period) to be transferred to buffer  720 . Shadow buffer  710  receives newer/later GNSS samples, while channels  790 - 1  through  790 -N operate to process the samples stored in buffer  720  (and received via path  721  and bus  702 ), till shadow buffer  710  is filled again, and the newer samples transferred to buffer  720 . 
     Correlator  730  combines local code samples with corresponding local carrier samples received on paths  743  and  753  respectively to generate a local signal, and correlates the local signal with the baseband GNSS signal (samples) received on bus  702 . Correlator  730  provides the product on path  736 . 
     Code forming block  745  provides local code samples on path  744 . Code storage  740  is implemented with a size less than one code period worth of local code samples. Local carrier generator  770  provides carrier samples (Doppler coefficients) on path  775 . Coefficients shadow register  755  stores the samples received on path  775 . When coefficients shadow register  755  is full, control circuitry (not shown) causes the stored carrier samples to be transferred to coefficients storage  750  via path  756 . Each of coefficients shadow register  755  and coefficients storage  750  is implemented with a storage size less than a size required to store a complete set of coefficients required for one Doppler hypothesis covering one code period. Coefficients shadow register  755  receives a next set of carrier samples from local carrier generator  770  while correlator  730  operates using the samples stored in coefficients storage  750 . 
     Due to the reduced storage size required for storing code samples and carrier samples, in addition to the reduced size of buffer  720 , overall storage area in baseband processing block  700  is reduced. An example implementation illustrating the structure and techniques described above with respect to  FIG. 7  is provided next with reference to  FIG. 8 . 
     The details of the blocks shown in  FIG. 8  are provided assuming that a GPS signal is to be acquired/tracked in channel  790 - 1 . It is assumed that each of shadow buffer  710  and buffer  720  are implemented with a storage size equal to sixty six samples (one window in this example) of a GPS signal sampled at 2 sps. The sixty six storage locations in shadow buffer  710  are labeled C 1 -C 66 , while those in buffer  720  are labeled  1 - 66 . It is noted that one code period of a GPS C/A L1 signal sampled at 2 sps contains 2046 samples. Incoming sets of sixty six samples to be stored in shadow buffer  710  are shown in dashed boxes in  FIG. 8 , to lend clarity in the description below. 
     In the embodiment of  FIG. 8 , code storage  740  is implemented with a size equal to store thirty three chips (bits) of a local GPS code, and each of coefficients shadow register  755  and coefficients storage  750  is implemented to store 3 carrier samples. The number of bits used to represent each sample is based, generally, on the level of accuracy desired. Each of multipliers  820  and  830  in correlator  730  is assumed to be implemented to perform thirty three multiply operations simultaneously, and may each contain thirty three multipliers internally. 
     Multiplier  820  receives in parallel (simultaneously), samples stored in thirty three odd-numbered storage locations ( 1 ,  3 ,  5 , etc. in  FIG. 8 ) of buffer  720 , and multiplier  830  receives in parallel, thirty three samples from even-numbered locations of buffer  720 . Although shown as separate inputs to multipliers  820  and  830 , it is assumed that correlator  730  contains corresponding circuitry (not shown) to combine code samples on path  743  with corresponding carrier samples on path  753 , and to provide the combined result to the corresponding portions of multipliers  820  and  830 . 
     In operation, code storage  740  provides thirty three code bits ‘currently’ stored in it on path  743 . The thirty three code bits are combined using XOR operation with corresponding ones of carrier samples provided by coefficients storage  750  on path  753 . Thus, the first carrier sample is combined with each of the first 11 code bits, the second carrier sample is combined with each of the next 11 code bits, and the third sample with the last 11 code bits. The thirty three local samples thus obtained are provided to the corresponding ones of the thirty three multipliers in each of multiplier  820  and  830 . Multipliers  820  and  830  provide the results of the multiplication (sixty six products corresponding to thirty three local code period duration) to summing block  810 . Summing block  810  adds the sixty six products to provide a partial sum on path  736 . 
     The operations noted above are repeated with a next code bit shifted into code storage  740  (e.g., code bits  2  through  34 , corresponding to a second partial sum), till the last (1023 rd ) code bit is shifted into code storage  740 , i.e., a total of 990 ( 1023 - 33 ) iterations, each of which may be viewed as an ‘iteration window’. It is noted that for every successive iteration, a new set of generated carrier samples is provided to coefficients storage  750  from coefficients shadow register  755  (which in turn is provided that carrier samples by local carrier generator  770 . 
     Each of the partial 990 partial sums is stored in either coherent sum storage  780  or non-coherent sum storage  785 , and the generation of one set of 990 partial sums represents one partial code phase search and one partial Doppler hypothesis performed with the available ‘current’ sixty six GNSS samples in buffer  720 . The above operations may be repeated with further sets of sixty six GNSS samples till one complete code phase search and one complete Doppler hypothesis is over. 
     A next set of iterations may then be performed for a next Doppler hypothesis, and the operations maybe continued throughout the acquire and track phases of operations. It is noted that processor  350  ( FIG. 3 ) may perform one complete correlation covering one code phase and one Doppler hypothesis (1023*2=2046 correlation products in the example) by adding the corresponding partial correlation results (partial sums) from corresponding iteration windows. 
     It may be appreciated that, in addition to the “less than one code period worth of samples” storage size in buffer  710 , the storage size for local code and carrier samples is less than that in the implementation described with respect to  FIGS. 4 and 5A . For example, while in the implementation of  FIGS. 4 and 5A  code storage  450  is required to be large enough to store 1023 code bits (for GPS) and eight carrier samples for each Doppler hypothesis, in the embodiment described with respect to of  FIGS. 7 and 8 , the total storage requirement for code as well as carrier samples is only thirty three bits for code storage  740  and three samples for coefficients storage  750  (ignoring the storage area due to coefficients shadow register  755 ). 
     The savings in area may be particularly significant when the total number of channels is large, and/or when the code period length is large. 
       FIG. 9  is a timing diagram illustrating the operations noted above. Time interval P 0  represents a duration in which partial sums for all 1023 local code phases and one (partial) Doppler hypothesis are generated using a set of sixty six GPS samples stored in buffer  720 . In an immediately subsequent interval P 1 , partial sums for all 1023 local code phases and a next partial portion of the same Doppler hypothesis (as in P 1 ) are generated using a next set of sixty six GPS samples received and stored in buffer  720 . Further sets of partial sums corresponding to further sets of sixty six GPS samples are similarly generated. 
     It may be appreciated that availability of GNSS samples in buffer  720  for the duration of thirty three code chips of a GPS signal (in the example) provides sufficient time for generation (in code forming block  745  and local carrier generator  770  respectively) of local code and carrier samples dynamically (‘on the fly’). Hence, all the code and carrier samples do not need to be generated and stored before commencement of processing of a GNSS signal, thereby reducing storage size of code storage  740  as well as coefficients storage  750 . The respective storage sizes of buffer  720 , shadow buffer  710 , code storage  740 , coefficients storage  750 , coefficients shadow register  755  and the combinational logic required to be implemented in correlator  730  are inversely proportional to the size of a ‘window’ of stored GNSS samples (sixty six in the example). The sizes may be implemented to be larger or smaller than in the example described above based on implementation or environment-specific requirements. 
     It is also noted that by increasing the frequency of clock  345 Clk multiple (partial) Doppler hypotheses may be performed with a same set of ‘window samples’ in other embodiments. Increasing the frequency of clock  345 Clk can also enable a same channel to be used for acquiring/tracking more than one GNSS signal in a time multiplexed manner. In some other embodiments, fewer than a complete local code phase set (less than 1023 in the example) may be used for correlations with each set ‘window samples’. 
     Thus, several aspects of the present invention enable a GNSS receiver to be implemented with reduced storage requirements for storing GNSS samples as well as for storing local code and carrier samples. 
     References throughout this specification to “one embodiment”, “an embodiment”, or similar language means that a particular feature, structure, or characteristic described in connection with the embodiment is included in at least one embodiment of the present invention. Thus, appearances of the phrases “in one embodiment”, “in an embodiment” and similar language throughout this specification may, but do not necessarily, all refer to the same embodiment. 
     While various embodiments of the present invention have been described above, it should be understood that they have been presented by way of example only, and not limitation. Thus, the breadth and scope of the present invention should not be limited by any of the above-described embodiments, but should be defined only in accordance with the following claims and their equivalents.