TWI870481B - Modernized global navigation satellite system receivers - Google Patents

Abstract

GNSS receivers and systems within such receivers use improvements to reduce memory usage while providing sufficient processing resources to receive and acquire and track E5 band GNSS signals directly (without attempting in one embodiment to receive L1 GNSS signals). Other aspects are also described.

Description

Modern global navigation satellite system receiver

The present invention relates to the field of global navigation satellite systems (GNSS), and more specifically to a GNSS receiver using a modern L5 signal in the L5 band in one embodiment. There are many GNSS systems available, including the US GPS (Global Positioning System), GLONASS, Galileo, BeiDou, and regional systems that are currently or may be deployed in the future. The US GPS system was originally available only in the L1 band. Now, the US GPS system includes GNSS signals in the L5 band, and the Galileo system includes modern GNSS signals (such as E5A and E5B) in the L5 band centered at 1191.79 MHz. Modern GNSS signals in the L5 band have some advantages over GNSS signals in the L1 band, and some of these advantages are explained below. However, it has been considered too difficult to directly acquire L5 band GNSS signals in a GNSS receiver without pre-acquiring L1 GNSS signals in the GNSS receiver, and therefore conventional GNSS receivers employ a technique of first acquiring L1 GNSS signals, and this acquisition provides information (e.g., time information and Doppler estimates) for acquiring GNSS signals in the E5 band. Therefore, conventional GNSS receivers that support GNSS L5 signals use an RF front end that receives both L5 signals and L1 signals; this means that there are multiple RF components in these GNSS receivers. In addition, the conventional receiver must store and use the PRN codes of both L1 GNSS signals and L5 GNSS signals.

The various aspects described herein provide improvements that may allow a GNSS receiver to directly receive, acquire, process and use only L5 band GNSS signals in the GNSS receiver with greater sensitivity and reliability than achieved in the narrow band L1, but in some embodiments such improvements may be used in conventional receivers to receive and process L5 band GNSS signals as well as one or more additional GNSS bands (e.g., the L1 GPS band). These aspects may be implemented in various embodiments, which may include a GNSS receiver or portions of a GNSS receiver or a data processing system (e.g., a smart phone) containing such a receiver or portions of such a receiver, and may include methods implemented by such a device (e.g., a GNSS receiver, etc.) and may include a non-transitory machine-readable medium storing computer program instructions, which, when executed by a data processing system, causes the data processing system to implement one or more of the methods described herein.

One aspect of the present invention is directed to directly acquiring L5 band GNSS signals. In other words, in this aspect, a GNSS receiver directly acquires L5 band GNSS signals without attempting to acquire time and frequency information from L1 band GNSS signals. The terms "direct acquisition" and "directly acquiring" are intended to mean that a GNSS receiver receives L5 band GNSS signals and acquires the signals to obtain time and frequency information derived from the signals, rather than acquiring time and frequency information from L1 band GNSS signals. Although cellular phone aiding data (time or frequency phase lock as described in the prior rapid tracking patent) can be used in a GNSS receiver, one GNSS receiver does not acquire L1 band GNSS signals and does not use the L1 band GNSS signals to directly acquire L5 band GNSS signals. Therefore, when the GNSS receiver directly acquires L5 band GNSS signals, the GNSS receiver acquires the L5 band GNSS signals to obtain time and frequency information from the signals without the benefit of previously acquiring the L1 band GNSS signals and without the benefit of obtaining time or frequency information from the L1 band GNSS signals.

Another aspect of the invention relates to sharing a cache memory between a set of one or more application processors (APs) and a GNSS processing system (or sharing other memory between the GNSS processing system and other processors on a SOC or integrated circuit). This aspect provides a solution to the typically excessive memory requirements when acquiring L5 GNSS signals, specifically by using a discrete Fourier transform (DFT) calculation method. The one or more application processors (or other processors) and the GNSS processing system can be implemented together in a single monolithic integrated circuit (IC) on a single semiconductor substrate and the cache memory can also be located on the same integrated circuit. The single monolithic integrated circuit (IC) on the single semiconductor substrate can be referred to as a system on a chip (SOC). In this aspect, an application processor (or other processor) shares its cache memory (or other memory) with at least one acquisition engine (AE) of a GNSS processing system. In one embodiment, this sharing may be limited to those situations in which the acquisition engine initially acquires GNSS signals (e.g., at the beginning with or without auxiliary data from a cellular telephone network). A portion of cache memory (which may be L1 (level 1) or L2 (level 2) SRAM cache memory of the one or more application processors or other memory used by other processing systems) may be allocated to the acquisition engine during the acquisition phase in response to a request for location data (such as a latitude and longitude) from an application (e.g., a map application or other application). The allocation may be prioritized based on the location request or not by an operating system (OS) of the system or firmware on an IC; if the location request is from a low priority background resident application, the allocation may be temporarily deferred until sufficient free memory is available in the cache memory. On the other hand, if the location request comes from a map application that is the foreground application (and therefore the device's display is a user interface showing the map application to a user), then the allocation is prioritized. In one embodiment, the portion to be allocated can be identified by determining which pages in the cache are undisturbed and stored in a backup memory (e.g., main DRAM or, more preferably, non-volatile memory (e.g., flash memory)). Such pages (e.g., uninterrupted and stored in a backup memory) may be immediately cleared/deleted from the cache (or other memory) and then allocated to the AE for use in storing one or more of, for example, hypothetical data or generated GNSS PRN codes and/or code spectrum of GNSS PRN codes generated from a DFT.

A method according to this common aspect may include the following operations implemented in a GNSS receiver: receiving a request from one or more application processors on an integrated circuit to generate position data by using a GNSS processing system on the integrated circuit, the GNSS processing system including an acquisition engine (AE), the acquisition engine (AE) being configured to acquire a plurality of GNSS signals, each of the GNSS signals being transmitted from one of a GNSS cluster space vehicle (SV); identifying the integrated circuit; A portion of a cache memory (or other memory) on the road is allocated to the acquisition engine for use in response to the request to generate location data, and a remaining portion of the cache memory (or other memory) is allocated to the one or more application processors (or other processors), the allocation being performed by an operating system executing on the one or more application processors or by firmware on the IC; and the acquisition engine or the one or more application processors storing data related to GNSS signal acquisition processing in the allocated portion. In one embodiment, the method may use static random access memory (SRAM) as a cache memory (or other memory) on the integrated circuit, and the acquisition engine may include ASIC (application specific integrated circuit) hardware logic for implementing a fast Fourier transform (FFT) operation (e.g., a discrete Fourier transform (DFT) operation) using a time decimation method and also using a frequency decimation method. In one embodiment, the method may further include the following operations: de-allocating the allocated portion after the GNSS processing system begins tracking GNSS signals that have been acquired from at least three (3) GNSS SVs, the de-allocation occurring in response to acquiring GNSS signals from the at least three GNSS SVs before a tracking phase. In one embodiment, the GNSS processing system includes a dedicated memory that is separate from the cache memory (or other memory) and dedicated to the GNSS processing system. In one embodiment, a memory controller coupled to the cache memory (or other memory) may include: a first port controller that controls access to the portion allocated to the acquisition engine; and a second port controller that controls access to the remaining portion of the cache memory (or other memory). In one embodiment, the acquisition engine implements acquisition of GNSS signals from a GNSS SV and the acquisition includes determining a primary code phase and frequency of a received GNSS signal containing a virtual random noise (PRN) code to enable tracking of the GNSS signal to generate a virtual range to the GNSS SV as a result of the tracking. In one embodiment of the method, a portion is allocated to store one or more of: (1) a virtual random noise code of the GNSS SV or (2) a hypothesis of an identifier of a possible acquired GNSS signal and a hypothesis of a frequency of the possible acquired GNSS signal. In one embodiment of this method, the one or more application processors may generate GNSS PRN codes and/or code spectra of GNSS PRN codes from DFT for at least the GNSS SVs in the system's field of view before the start of an acquisition phase; in one implementation scheme of this embodiment, such PRN codes and/or their code spectra obtained from DFT may be generated and used immediately but not stored, or alternatively, such PRN codes and/or their code spectra obtained from DFT may be generated and temporarily stored for use during the acquisition and tracking phases. In an alternative embodiment, the one or more application processors may generate GNSS PRN codes and store them in the system's DRAM memory, and then copy them to cache (or other memory) before starting the acquisition phase or in response to a position request. In one embodiment, to save memory, the system may generate GNSS PRN codes and/or derive their code spectra from DFT only for GNSS SVs that are operating well in view.

In one embodiment, a system according to this sharing mode may include the following components: a set of one or more application processors configured to execute an operating system (OS) and one or more applications, the set of one or more application processors implemented in an integrated circuit (IC); a set of one or more buses coupled to the set of one or more application processors, the one or more buses being located on the integrated circuit; a cache (or Other memory) located on the integrated circuit and coupled to the set of one or more buses and coupled to the set of one or more application processors to store for use by the operating system or for the one or more applications and other memory (e.g., high-bandwidth modem memory or other memory used by one or more processors that are not in the set of one or more application processors and may also be located on the IC and coupled to the one or more buses a bus interface coupled to the set of one or more buses, the bus interface coupling the set of one or more application processors to a dynamic random access memory (DRAM) outside the integrated circuit; a GNSS processing system implemented on the integrated circuit, the GNSS processing system including an acquisition engine (AE) and a tracking engine (TE), the GNSS processing system through the one or more buses A bus is coupled to the cache memory (or other memory); and a memory controller is coupled to the cache memory (or other memory) and the set of one or more application processors and the GNSS processing system, the memory controller is responsive to one or more instructions from the operating system (or other software component) to allocate a portion of the cache memory (or other memory) for use by the AE to allow acquisition of GNSS signals. In one embodiment, the cache memory may include static random access memory (SRAM), and the AE may include ASIC hardware logic to perform discrete Fourier transform operations using both a time sampling method and a frequency sampling method. In one embodiment, the memory controller may include: a first port controller for controlling reading and writing of the portion used for the AE; and a second port controller for controlling reading and writing of a remaining portion of the cache memory (or other memory). In one embodiment, the memory controller may de-allocate the portion of the cache memory (or other memory) used by the AE before the GNSS processing system begins tracking GNSS signals acquired from at least three GNSS SVs (but before determining a position data (e.g., a latitude and a longitude)).

Another aspect that can help reduce memory usage in an L5 band GNSS receiver is to generate code spectra of GNSS PRN codes and/or GNSS PRN codes from DFT for association to received GNSS signals on demand during the acquisition phase. In one embodiment, the on-demand generation can generate code spectra of GNSS PRN codes and/or GNSS PRN codes from DFT during the acquisition and tracking phases. For example, in one embodiment, such codes can be generated but not stored during both the acquisition and tracking phases; in an alternative embodiment, codes can be generated temporarily and on demand and stored during both the acquisition and tracking phases, and such codes are no longer stored once a position is determined.

Another aspect of the invention relates to an acquisition correlator using array processing. The array processing architecture may first arrange the digitized GNSS sample data, for example, in rows in an array, where the rows are arranged in time in a baseband sample memory. A DFT operation performed on the data may generate an output, which may then be processed by an inverse DFT operation without rotating or reformatting or re-arranging or transposing the data in the array prior to the inverse DFT operation. The data may be arranged so that each ALU in a set of multiple ALUs processes a column or row in the array, thereby dividing the processing into discrete segments that may be processed by each of the DFT ALUs, so that a single DFT ALU may compute each column or row in one or more processing clock cycles as an atomic processing operation, and in one embodiment the single DFT ALU performs multiple DFT operations once it is instructed to do so. The baseband sample memory may be implemented as a loop buffer containing an array of sorted data. In one embodiment, the processing operation may be a DFT in-place computation such that a row (or column) of input data is retrieved from memory and processed (using a DFT), and the output from this processing is then stored back into the same memory locations as the input data (thus overwriting the input data in those memory locations).

In one embodiment in which an array processing architecture may be used, a system for processing GNSS signals may include the following components: an RF analog-to-digital converter (ADC) for generating a digital representation of a received GNSS signal; a baseband sample memory for storing the digital representation of the received GNSS signal as digitized GNSS sample data in N2 rows (e.g., 1024 rows) and N1 rows (e.g., 20 rows), the array being stored in a row order in the baseband sample memory; The baseband sample memory is a memory for storing digitized GNSS sample data received in a time period (including a first time period and a second time period) in a row sequence, such that a first row in the row sequence contains digitized GNSS sample data received during the first time period, and a second row in the row sequence that is located after the first row contains digitized GNSS sample data received during a second time period that is located after the first time period in time, wherein the baseband sample memory is coupled to an RF ADC; and an arithmetic logic unit (ALU) configured to perform discrete Fourier transform (DFT) operations, the ALU being coupled to the baseband sample memory and configured to perform N1 DFTs in parallel and simultaneously, wherein each of the N1 DFTs contains N2 points in the DFT and the outputs of the N1 DFTs are stored in a portion of the sample array, and wherein the ALU is configured to then perform N2 DFTs, each of the N2 DFTs contains N1 points from the portion of the sample array, the N2 DFTs providing an output that is stored in a DFT result array arranged in row order. In one embodiment, the baseband sample memory is configured as a cyclic memory buffer storing digitized GNSS sample data. In one embodiment, the N1 DFTs use the same operation and the same program control instructions to cause the set of ALUs to operate on different data. In one embodiment, the N2 DFTs are performed continuously over time. In one embodiment, the cyclic sample memory buffer stores more than one frame of a virtual random GNSS signal over one millisecond. In one embodiment, the N1 DFTs and the N2 DFTs use a time decimation method, and N1 is one of integer values 5, 10, 20, or 40. In another embodiment, N2 is set so that N1×N2=20480 (or N1×N2 is greater than 20480). In one embodiment, a change from column order to row order avoids a reordering or transposition algorithm, and the change is produced by a combination of N1 DFTs followed by N2 DFTs configured to produce the change. In one embodiment, a GNSS code generator is configured to produce a GNSS code spectrum, and the set of ALUs performs a set of DFTs on the GNSS PRN code to provide a code spectrum result data, which is stored in a code spectrum memory in a row order. In one embodiment, the ALU may be configured to multiply the code spectrum result data by the sample output stored in the DFT result array to generate a product array. In one embodiment, the ALU may be configured to perform an inverse DFT on the product array using a frequency decimation method. In one embodiment, the inverse DFT may include: (1) in a first stage, N2 DFTs using conjugate inputs, each of the N2 DFTs containing N1 points; and (2) in a second stage subsequent to the first stage, N1 DFTs, each of the N1 DFTs containing N2 points. In one embodiment, the baseband sample memory may be a dual-port memory that allows different processors or programs to access different portions of the baseband sample memory simultaneously. In one embodiment, the GNSS code generator may repeatedly generate a virtual random noise code for each GNSS SV in view every millisecond when a virtual random noise code is needed during an acquisition phase, and does not store a generated virtual random noise code (and/or its code spectrum obtained from DFT) after use, and the generated virtual random noise code may be used to generate a GNSS code spectrum. In one embodiment, the GNSS code spectrum is aligned in both frequency and phase to the appropriate location in memory to match the code phase and frequency shift assumptions associated with the received GNSS signal. In one embodiment, this alignment can be performed by CORDIC hardware.

One or more embodiments of a GNSS receiver described herein may implement one of the following methods using a series of DFTs. In one embodiment, a method may include the following operations: Receive a GNSS signal; Digitize the received GNSS signal and provide an output of GNSS sample data from an analog-to-digital converter (ADC), the GNSS sample data including at least one of (1) GNSS sideband A sample data of a received GNSS signal and (2) GNSS sideband B sample data of the received GNSS signal; Perform at least one of the following: (1) calculate a first set of DFTs on the GNSS sideband A sample data to provide a first set of results; and (2) 2) Calculate a second set of DFTs on the GNSS sideband B sample data to provide a second set of results; Perform at least one of the following two items: (1) Calculate a third set of DFTs on the GNSS sideband A main PRN code data, before the third set of DFTs, the GNSS sideband A main PRN code data is adjusted due to code Doppler and carrier Doppler, and the GNSS sideband A main PRN code data includes at least one of the two components in GNSS sideband A, and the third set of DFTs provides a third set of results; and (2) Calculate a fourth set of DFTs on the GNSS sideband B main PRN code data DFT, before the fourth set of DFT, the GNSS sideband B main PRN code data is adjusted due to code Doppler and carrier Doppler, the GNSS sideband B main PRN code data includes at least one of the two components in GNSS sideband B, and the fourth set of DFT provides a fourth set of results; Perform at least one of the following two items: (1) use the complex conjugate of the product of the first set of results and the complex conjugate of the third set of results to calculate the first set of correlations to provide a fifth set of results; and (2) use the complex conjugate of the product of the second set of results and the complex conjugate of the fourth set of results to calculate the first set of correlations to provide a fifth set of results. A conjugate DFT is calculated to compute a second set of associations to provide a sixth set of results; and integrating at least one of the following: (1) integrating the fifth set of results using at least one previous sum of the GNSS sideband A; and (2) integrating the sixth set of results using at least one previous sum of the GNSS sideband B, wherein the integration includes at least one of the following: (1) storing at least one new sum of the GNSS sideband A components in a single hypothetical memory and (2) storing at least one new sum of the GNSS sideband B components in the single hypothetical memory.

One implementation of this method can be summarized as ("Case 1"): 1.      Calculate the FFT of a sideband A sample; 2.      Calculate the FFT of a sideband B sample; 3.      Calculate the FFT of at least one sideband A component main code adjusted by code Doppler and carrier Doppler (e.g., a range of potential Dopplers to be searched); 4.      Calculate the FFT of at least one sideband B component main code adjusted by code Doppler and carrier Doppler; 5.      Calculate the correlation by performing an inverse FFT (IFFT) on the product of (a) the FFT calculated from 1 (FFT of sideband A samples) and (b) the FFT calculated from 3 (FFT of sideband A components); 6.     The correlation is computed by taking an IFFT of the product of (a) the FFT computed from 2 and (b) the FFT computed from 4.

This implementation may provide several advantages. For example, this implementation may require very few FFTs on the received sideband samples and may reduce or eliminate the large data transfers typically required to move pre-computed GNSS sample spectra from memory (e.g., DRAM or non-volatile memory) to the frequency domain correlation engine. The frequency domain correlation engine may be very efficient by reusing the engine at a reasonable clock rate while requiring a low or small memory footprint. For example, the frequency domain correlation engine may calculate the master code and its spectrum in situ within the engine (e.g., in operations 3 and 4 in the summation "Case 1" above) according to a pipeline architecture described herein. Additionally, applying code Doppler and carrier Doppler to the field generated code (e.g., in operations 3 and 4 in the summation "Case 1" above) can reduce the input (received) sample FFT and also improve the code Doppler accuracy.

There are many combinations and permutations of this implementation for acquiring (for example) L5 GNSS signals. However, these combinations and permutations may not be as efficient as "Case 1" above because they require faster processing clocks and/or more memory (relative to "Case 1") or because they have less acquisition sensitivity or require a longer time to acquire signals to reach a given signal strength. The use of the six (6) operations in "Case 1" may be retained, but the arrangement is based on one or more of the following: (1) where and how code compensation and carrier compensation are implemented, for example: (a) carrier Doppler compensation may be performed by "erasing" the received GNSS samples or multiplying the locally generated (or pre-calculated) PRN code samples; or (b) code Doppler adjustment may be applied to the received GNSS samples ("input samples") or locally generated (or pre-calculated) PRN code samples by performing a complex multiplication of the code spectrum (for example, see Appendix 3) or by correlating the result after compensation and integrating it in memory (see Appendix 1); (2) is it based on the GNSS in view? SV instead of generating the code spectrum locally in the acquisition engine (AE), or pre-calculating the code spectrum and loading it into the AE; or (3) alternative hardware architectures (rather than performing the time extraction FFT and frequency extraction FFT sequentially), such as parallel FFT kernels or higher radix kernels to reduce the number of processing clocks per FFT. The following 6 arrangements are examples of possible arrangements.

Case 2 (Switch code and carrier Doppler to samples: more input sample FFTs are needed) 1.      FFT of sideband A adjusted for code Doppler and carrier Doppler 2.      FFT of sideband B adjusted for code Doppler and carrier Doppler 3.      FFT of at least one A component main code 4.      FFT of at least one B component main code 5.      Correlate by IFFT of 1 and 3 products combined into a single hypothetical memory 6.      Correlate by IFFT of 2 and 4 products combined into a single hypothetical memory

Case 2B (same as 2, pre-calculated code spectrum: requires more memory and data bandwidth) 1.      FFT of sideband A adjusted for code Doppler and carrier Doppler 2.      FFT of sideband B adjusted for code Doppler and carrier Doppler 3.      Get at least one pre-calculated FFT of the A component master code 4.      Get at least one pre-calculated FFT of the B component master code 5.      IFFT and correlate 1 product and 3 products combined into a single hypothetical memory 6.      IFFT and correlate 2 products and 4 products combined into a single hypothetical memory

Case 3 (same as 2, correlated after code Doppler compensation) 1.      FFT of sideband A adjusted for carrier Doppler 2.      FFT of sideband B adjusted for carrier Doppler 3.      FFT of at least one A component main code 4.      FFT of at least one B component main code 5.      IFFT of 1 product and 3 products combined into a single hypothetical memory and adjusted for code Doppler and correlate 6.      IFFT of 2 products and 4 products combined into a single hypothetical memory and adjusted for code Doppler and correlate

Case 3B (same as 3, but with pre-calculated code spectrum) 1.      Perform FFT on sideband A adjusted for carrier Doppler 2.      Perform FFT on sideband B adjusted for carrier Doppler 3.      Obtain pre-calculated FFT of at least one A-component main code 4.      Obtain pre-calculated FFT of at least one B-component main code 5.      Perform IFFT on 1 and 3 products combined into a single hypothetical memory and adjusted for code Doppler and correlate 6.      Perform IFFT on 2 and 4 products combined into a single hypothetical memory and adjusted for code Doppler and correlate

The following set of cases uses the method described in Appendix 1 which computes the FFT of the input sample sideband samples every millisecond at several frequencies (0, 200, 400, 600, 800) and then roughly estimates the sample sideband A or B spectrum by selecting the closest sub-kHz FFT and then shifting by +/-N samples to get an over-kHz offset. For example, 2450 Hz uses a 400Hz FFT and shifts this FFT by +2 samples to get a combined 400Hz + 2kHz Doppler offset.

Case 4 (similar to the method described in Appendix 1) 1.      Select at least one FFT from a set of sideband A sample FFTs adjusted for carrier Doppler at a set of frequencies covering a 1 kHz range, the one FFT shifted by N samples to generate an approximate carrier Doppler 2.      Select at least one FFT from a set of sideband B sample FFTs adjusted for carrier Doppler at a set of frequencies covering a 1 kHz range, the one FFT shifted by N samples to generate an approximate carrier Doppler 3.      Perform FFT on at least one A component main code adjusted for code Doppler 4.      Perform FFT on at least one B component main code adjusted for code Doppler 5.     IFFT of 1 product and 3 products integrated into a single hypothetical memory to make a correlation 6.      IFFT of 2 products and 4 products integrated into a single hypothetical memory to make a correlation

Case 4A (similar to method 4, but with pre-calculated code spectrum and code Doppler post-correlation) 1.      Select at least one FFT from a set of sideband A sample FFTs adjusted for carrier Doppler at a set of frequencies covering a 1 kHz range, the one FFT shifted by N samples to generate an approximate carrier Doppler 2.      Select at least one FFT from a set of sideband B sample FFTs adjusted for carrier Doppler at a set of frequencies covering a 1 kHz range, the one FFT shifted by N samples to generate an approximate carrier Doppler 3.      Obtain at least one pre-calculated FFT of the A component main code 4.      Obtain at least one pre-calculated FFT of the B component main code 5.     IFFT of 1 and 3 products integrated into a single hypothetical memory and adjusted for code Doppler is correlated 6. IFFT of 2 and 4 products integrated into a single hypothetical memory and adjusted for code Doppler is correlated

In some of the embodiments described herein, adjustments or compensations are made for one or both of Code Doppler and Carrier Doppler. As described herein, these adjustments may be performed independently and at different stages. Code Doppler adjustment is an adjustment made to a locally generated code (or a pre-calculated code) or to a received GNSS sample code to adjust for the Doppler effect of a code (e.g., a primary GNSS PRN code); for example, during a search or acquisition phase, multiple possible Code Doppler adjustments may be made to the locally generated code or to the received GNSS sample code to search for and acquire a GNSS signal affected by the Doppler effect. Carrier Doppler adjustment is an adjustment made to adjust for the Doppler effect on a carrier frequency of a signal. Carrier Doppler is the observed frequency deviation from the transmitted frequency due to relative motion between the satellite and the receiver and is the deviation from the nominal values of the satellite and receiver oscillators. Code Doppler is the shift in the received code phase over time and is coherent with the carrier Doppler. At L5, there are 115 carrier cycles per code chip. Therefore, the code Doppler in chips/second is the carrier Doppler divided by 115. So at a carrier Doppler of 4321 Hz, the received code phase will move 37.57 chips in one second. In order to be able to receive weak signals, the received signal must be correlated to the receiver's replica for multiple master code frames. This requires shifting each incoming code phase assumption based on the carrier Doppler assumption. This shift is called a Doppler shift.

Another aspect of the present invention involves using the primary code and/or secondary code in the E5 GNSS signals from one GNSS SV to derive code phase data or time data based on those GNSS signals, and then using that information to estimate the code phases of other GNSS signals from other GNSS SVs to obtain the code phases of those other GNSS signals from those other GNSS SVs. In this aspect, a GNSS receiver may employ a processing period that may be less than and may be offset from a 1 ms GNSS PRN code period, and the GNSS receiver may use the processing to attempt to coherently integrate before acquiring the code phase of other GNSS signals; for example, a GNSS processing system in a GNSS receiver may retrieve a full 1 millisecond (ms) of digitized GNSS sample data from a cyclic memory buffer every 0.25 milliseconds and perform a set of DFTs and inverse DFTs on the retrieved data to coherently integrate for each frequency band, and then repeat this VFFDC procedure at the next processing period, where each processing period is 0.25 milliseconds or some other fraction of a code period (i.e., 1 ms long in one embodiment). This may allow a GNSS receiver to repeatedly use 1 millisecond of data from a recurring buffer over multiple processing periods in an attempt to coherently integrate other GNSS signals using information obtained by pre-acquiring the primary or secondary code phase of at least one of the GNSS signals. In this example, satellite codes are searched based on an approximate time grid at which they are expected to be received so as to reduce sub-millisecond coherence pair loss due to phase reversals associated with the secondary codes. In another embodiment, the receiver clock may already be accurate enough (much less than 1 ms error) and a priority position may be known enough to allow all GNSS signals to be processed in this precise time acquisition mode.

Another aspect of the invention involves using only a subset (a selected component) of the two or four components of the GNSS signal to first acquire the subset (e.g., only one of the four components) during coarse time acquisition, and then acquire the remaining components. In one embodiment, this selected component is selected based on a lowest probability of a signal change due to a sign or phase reversal due to a coding scheme used in the selected component. In the case of Galileo's E5 GNSS signals, the E5BI component has the lowest probability of signal change due to sign or phase reversal and can therefore be used as the selected component to perform a coarse time acquisition or fine time acquisition before attempting to acquire and/or track the remaining components of the Galileo GNSS signal. This use of only a subset of the components may be done initially at the beginning of an acquisition (e.g., a coarse time acquisition), or as a fallback mode of operation after a practiced acquisition failure, or as a method to acquire a stronger satellite more quickly as the number of associations decreases, to allow a portion of a GNSS acquisition engine to search a large frequency space of many SVs more quickly and with lower power than if more GNSS signal components were employed.

Another aspect of the invention relates to reducing the effects of interference from some known strong interference sources, such as aeronautical radio navigation (ARN) signals that are typically present around, for example, airports or military bases. ARN signals, such as signals from a tactical air navigation system (DME/TACAN), are typically strong pulse signals that are well above a noise floor, while GNSS signals are typically below the noise floor. In addition, ARN signals can cause interference to GNSS in the L5 band. In one embodiment, the interference can be attenuated by detecting a signal source above the noise floor (for example, detecting a signal above a predetermined threshold that may be several dB above a noise floor) and then removing the signal in the frequency domain. The interference signal can be identified during the signal acquisition phase using the DFT array processing described herein, and then the interference signal can be processed through a FIR (finite impulse response) filter to remove the interference signal before time domain correlation processing. Alternatively, since the input sample spectrum is performed every millisecond and at each of the upper and lower sidebands, frequencies with strong interference may be observed in the input data spectrum.

Another aspect of the invention is a method for reducing memory usage by calculating outputs from some DFT calculations but not storing the outputs. This method can reduce the size of the integration or assumption memory by not storing selected outputs from the DFT calculations. In one embodiment, the outputs are evaluated to determine whether to save the outputs. This approach can be used when using the DFT method to perform correlation. In this case, the DFT generates correlation results with all code assumptions within one millisecond. If the time segment position uncertainty is much less than one millisecond (i.e., the full range), only a portion around the estimated position needs to be integrated and saved.

The aspects and embodiments described herein may include a non-transitory machine-readable medium storing executable computer program instructions that, when executed by the one or more data processing systems, cause the one or more data processing systems to perform the methods described herein. The instructions may be stored in non-volatile memory (e.g., flash memory) or volatile dynamic random access memory or other forms of memory.

The above invention content does not include an exhaustive list of all embodiments of the present invention. All systems and methods can be implemented according to all suitable combinations of the various aspects and embodiments summarized above and also according to the aspects and embodiments disclosed in the following detailed description.

Various embodiments and aspects will be described with reference to the details discussed below, and the accompanying drawings will illustrate various embodiments. The following description and drawings are illustrative and should not be construed as limiting. Numerous specific details are set forth to provide a thorough understanding of various embodiments. However, in some instances, well-known or commonly used details are not set forth to provide a concise description of an embodiment.

Mentioning "one embodiment" or "an embodiment" in the specification means that a specific feature, structure, and characteristic described in conjunction with the embodiment may be included in at least one embodiment. The phrase "in one embodiment" appearing in various places in the specification does not necessarily refer to the same embodiment. The processing logic including hardware (such as circuit systems, dedicated logic, etc.), software, or a combination of hardware and software implements the procedures shown in the figure below. Although the following describes the procedures according to certain sequential operations, it should be understood that some of the operations described may be performed in a different order. In addition, some operations may be performed in parallel rather than sequentially.

One aspect of the embodiments described herein relates to sharing cache memory between one or more application processors and a GNSS processing system. Before describing these sharing embodiments, an illustration of a prior architecture in the prior art will be provided with reference to FIG. 1 . FIG. 1 shows a system 10 including one or more application processors 12 and a GNSS processor 20 coupled via a bus 14, which is also coupled to system main memory, which is dynamic random access memory (DRAM) 24. The system 10 includes one or more input/output (I/O) devices 26 (e.g., one or more touch screens, speakers, microphones) and one or more sensors (e.g., cameras, facial detection sensors, etc.). The system 10 also includes a cellular modem and processor 16, which may include its own cache memory, which may be SRAM 16A. The cellular modem and processor 16 are coupled to a cellular phone RF component 17 to receive cellular phone signals via an antenna 18. The GNSS processor 20 is configured to receive and process GNSS signals in both the L1 band and the L5 band. In addition, the GNSS radio frequency (RF) component 21 is configured to receive GNSS signals in the L1 band and the L5 band via antenna 22A and antenna 22B, and the GNSS RF component 21 includes one or more RF mixers and RF to intermediate frequency down-converters and includes an RF local oscillator. These GNSS signals are processed by the GNSS processor 20, which includes its own dedicated processor memory as part of the GNSS processor 20. The GNSS processor does not use the cache 12A or shares the cache 12A used by one or more application processors 12, which utilize a cache using techniques known in the art. The GNSS processor receives and processes the GNSS signals and provides position outputs (e.g., latitude and longitude outputs) to one or more application processors 12 via bus 14. The GNSS processor receives and processes the GNSS signals without utilizing cache memory 12A and requires two separate GNSS antennas 22A and 22B and two separate GNSS RF paths starting at the two GNSS antennas 22A and 22B.

FIG2 shows an example of a system in which cache memory is shared between one or more application processors and a GNSS processing system. The system 50 shown in FIG2 includes a system-on-chip (SOC) 52 including one or more application processors 66 and a cache memory 70 and a GNSS processing system 68. In one embodiment, the SOC 52 may be a single monolithic semiconductor device pre-positioned in a substrate of an integrated circuit that includes all of the components shown within the perimeter of the SOC 52 shown in FIG2. The SOC 52 may include a memory controller 72 that controls access to a cache 70 (or other memory) that is coupled to the one or more application processors 66 and to the GNSS processing system 68. Thus, the memory controller 72 may arbitrate use of the cache 70 to allow both the GNSS processing system 68 and the one or more application processors 66 to use the cache, which may be implemented as SRAM memory in one embodiment. In one embodiment, the memory controller 72 may allocate a portion of the cache 70 for use by the GNSS processing system and allow the one or more application processors 66 to use the remainder of the cache 70. In one embodiment, cache memory 70 may be used to store program code or program instructions and data operated by the processing system. As further described below, when an acquisition engine of GNSS processing system 68 acquires GNSS signals, the acquisition engine may use cache memory to store, for example, assumptions in an assumption memory used during the acquisition phase, or may use cache memory 70 to store PRN codes (and/or their code spectra from DFT) generated for the GNSS signals. GNSS processing system 68 may be coupled to the one or more application processors 66 via bus 74. The one or more application processors 66 and the GNSS processing system 68 may also be coupled to a cellular modem and processor 76 via a bus 74. In one embodiment, the bus 74 is a set of buses on the SOC 52. The SOC 52 also includes a bus interface 78 that allows the SOC 52 to be coupled to a system bus 54 that is external to the SOC 52. There are several other components external to the SOC 52, and they include the GNSS RF component 63, which in the example shown in FIG. 2 is configured to operate only in the L5 wideband (WB) band to receive and process only L5 wideband (WB) GNSS signals in the embodiment shown in FIG. 2 . The term or phrase L5 WB band or L5 WB signal or L5 WB GNSS is meant to include or refer to modern GNSS signals and modern GNSS systems (e.g., SVs and receiver clusters) operating in a modern frequency band centered at 1191.795 MHz and having a chip rate of 10.23 MHz or having a chip rate significantly higher than the original chip rate or GPS L1 of 1.023 MHz, and these modern GNSS systems include, for example, the U.S. L5 GPS system, the European E5 Galileo system, the Chinese Beidou/Guanzhi B2 system, GLONASS K2, and QZSS. The cellular phone modem and processor 76 are coupled to a cellular phone RF assembly 64 to receive cellular phone signals and transmit cellular phone signals. DRAM 56 is coupled to bus 54 and can store user data and applications as well as an operating system. In addition, in addition to DRAM 56, system 50 may also include non-volatile memory 57, such as flash memory. Non-volatile memory 57 can store user data and applications as well as an operating system for system 50. System 50 may also include various input/output devices, which can interface with the rest of the system through one or more I/O controllers 58. The input/output devices may include one or more sensors 62 and other input/output devices 60. For example, the sensor may include one or more of the following: a 3-axis accelerometer, a 3-axis gyroscope, an ambient light sensor (ALS), a barometric pressure sensor, a magnetometer, one or more cameras, etc. In addition, the system 50 may include other RF components 62, such as Bluetooth, Wi-Fi, etc. A method for operating the system 50 will now be provided with reference to FIG. 3 .

The system 50 may receive a request from an application to determine a location in operation 101 (shown in FIG. 3 ). The request may come from a foreground application or from a background application. For example, a map application in a user interface that is in the foreground and therefore displays a map to the user requests a location, and this request may cause the GNSS processing system 68 to be activated. Alternatively, a resident background process may make a request for a location. The nature of the request may determine a priority for the memory controller 72 to determine how and when to allocate a portion of the cache 70 for use by the GNSS processing system 68. For example, in some embodiments, a request for a location by a foreground application may cause "allocating a portion of cache memory 70 for use by the GNSS processing system 68" to be a high priority task, so that the portion is allocated as quickly as possible. Alternatively, a request for a location by a background application may cause "allocating a portion of cache memory 70 by the memory controller 72" to be a deferred process or task, thereby giving the memory controller 72 more time to allocate a portion of cache memory 70.

In operation 103, the GNSS processing system 68 may receive auxiliary data from, for example, a cellular modem and processor 76. In one embodiment, a satellite almanac or other data source regarding satellites in view over a period of time may be received by the system 50 and stored for later use by the GNSS processing system 68. In operation 105, based on the satellites or space vehicles (SVs) in view (e.g., from a received satellite almanac), the GNSS processing system 68 may generate virtual random noise (PRN) codes for the GNSS SVs in view and/or generate code spectra of the virtual random noise codes from DFT (e.g., see code spectrum memory 263 in FIG. 6 ). In one embodiment, the GNSS processing system 68 may generate such codes as needed and use such codes without storing such codes during the acquisition and tracking phases of processing GNSS signals. In another embodiment, during the acquisition and tracking phase of processing GNSS signals, the GNSS processing system 68 may generate such codes and/or code spectra of such codes from DFT as needed (e.g., see code spectrum memory 263 in FIG. 6 ) and use such codes and/or code spectra of such codes from DFT (e.g., see code spectrum memory 263 in FIG. 6 ) but also store such codes and/or their code spectra, but once the tracking phase is completed, such codes are no longer stored. In one embodiment, a code spectrum may be generated (generated from the GNSS PRN codes of the GNSS SVs in view) but not stored (for more than about 1 ms), and the code spectrum may be repeatedly generated every millisecond (ms) of the GNSS sample data received and stored (e.g., in a circular memory buffer); thus, in a first ms, a code spectrum is generated by applying a code Doppler (e.g., time shift) and a carrier frequency Doppler adjustment (e.g., see FIGS. 6 and 9D ) to the generated GNSS master PRN code, then performing a DFT (e.g., by DFT ALU 261), and then a new code spectrum is generated in a second ms (the next ms after the first ms). One benefit of applying code Doppler and carrier frequency adjustments prior to generating the code spectrum (e.g., by the DFT ALU 261 in FIG. 6 ) is that, because the code Doppler rate of the E5 GNSS signal is high, the code spectrum cannot be pre-computed or even used in subsequent milliseconds, and therefore the code should be Doppler shifted every millisecond interval to maintain high correlation. In one embodiment, if memory is available, the Doppler shifted code spectrum can be stored for a short period of time to reduce the use of computational resources. Generating these codes on demand (which continues until a position data is determined) without long-term storage or without any storage can reduce the amount of memory used by the GNSS processing system 68. Similarly, sharing cache memory 70 with one or more application processors 66 may also reduce memory usage by the GNSS processing system 68. In operation 107, a portion of cache memory (e.g., SRAM memory) on an integrated circuit containing the GNSS processing system and one or more application processors may be allocated, for example, by the memory controller 72. This may then allow an acquisition engine in the GNSS processing system 68 to use the allocated portion, at least during the acquisition phase.

The acquisition phase typically involves determining the frequency and master code phase of the acquired PRN code and the identifier of the satellite that has transmitted the acquired PRN code. When a correlation operation indicates a match between a locally generated PRN code and a received PRN code, the PRN code is acquired. In one embodiment, in operation 109, an acquisition engine in the GNSS processing system uses the allocated portion to store hypothetical data and/or GNSS PRN codes. Then in operation 111, the acquisition engine acquires one or more GNSS signals to allow a tracking engine in the GNSS processing system to track the acquired GNSS signals, thereby determining the virtual distance from the GNSS SV that has transmitted the GNSS signal acquired by the acquisition engine. In one embodiment, portions of the cache memory may be de-allocated after the tracking phase begins in operation 113. For example, the memory controller 72 may de-allocate portions that already contain hypothetical data, but if GNSS PRN codes and/or code spectra thereof from DFT (e.g., see the description of code spectrum memory 263 below) are already stored in the cache memory, the GNSS PRN codes and/or code spectra of the GNSS PRN codes from DFT are retained for tracking. In an embodiment where the PRN code and/or its code spectrum from the DFT is not stored but is generated on the fly during use (e.g., see the description of the code spectrum memory 263 below), then the de-allocation of the portion of the cache used by the acquisition engine may be a complete de-allocation, thereby freeing the cache 70 for use by one or more application processors 66. Then in operation 115, the GNSS processing system 68 may derive the virtual range and may use the virtual range and the ephemeris data in the GNSS SV to determine the position data of the system (e.g., system 50).

In one embodiment, the GNSS processing system 68 may include a dedicated memory that is separate from the cache memory 70 and dedicated to the GNSS processing system. In one embodiment, the memory controller 72 may include: a first port controller for controlling the reading and writing of the portion of the cache memory 70 used for the acquisition engine; and a second port controller for controlling the reading and writing of the remaining portion of the cache memory 70. In one embodiment, when requesting position data (e.g., based on information about the health of the SV and information about the SVs in view), the generation of GNSS PRN codes and/or the generation of code spectra of GNSS PRN codes based on DFT may be performed only for healthy GNSS SVs in view. This selective generation of GNSS PRN codes and/or code spectra of GNSS PRN codes from DFT without storing such codes (except for registers and buffers in pipeline processing logic) after the tracking phase or during the acquisition and tracking phase can reduce the memory usage of the GNSS processing system. The pipeline processing logic can include registers and buffers that temporarily store codes and code spectra during one or several clock cycles. In one embodiment, the GNSS processing system 68 may use the array processing architecture described below (e.g., the architectures shown in FIGS. 6 , 7 , 8 , and 9 ) to additionally reduce GNSS processing system memory usage by, for example, using an in-situ DFT algorithm.

In one embodiment, the operating system (or processor firmware) may implement the allocation of portions of cache memory to the GNSS processing system based on information about the data stored in the cache memory, which may be referred to as metadata. For example, this metadata may indicate whether the data stored in the cache memory was "interfered with" (e.g., changed while stored in the cache memory) before a portion of the cache memory was allocated for use by the acquisition engine, or whether it was stored in a backing store (e.g., non-volatile storage (e.g., flash memory) or even DRAM memory). For example, if a portion of the cache memory is storing computer program instructions or code that has been stored in non-volatile storage before the portion is allocated for use by the acquisition engine, and the computer program instructions have not been modified while in the cache memory, the portion of the cache memory can be allocated to the acquisition engine without having to write the data in the portion out to DRAM memory or out to non-volatile storage. This can allow the operating system (or processor firmware) to quickly clear a portion of the cache memory so that it can be quickly allocated for use by the acquisition engine of the GNSS processing system. In the example shown in FIG. 2 , the GNSS processing system shares a memory (e.g., cache memory 70) with one or more application processors (APs); in an alternative embodiment, the GNSS processing system may share other memory with other processing systems on the IC (e.g., one or more other processors). In this alternative embodiment, the GNSS processing system shares another memory and does not use or share the cache memory of one or more APs. The other memory and the GNSS processing system and other processing systems may all be located on the same IC (e.g., a SOC that also includes one or more APs and the cache memory of one or more APs). The other processing system may be one or more modem processors or graphics processors or code that uses other memory separate from the cache memory used by one or more APs, and this separate (on the same chip) other memory may also be a two-port ("dual-port") type memory that supports high-frequency data access (read and write). As described herein, the memory controller may arbitrate access to the other memory when both the GNSS processing system and the other processing system attempt to access the other memory simultaneously. In one implementation of this alternative embodiment, the other memory may be a processor local memory of one or more of the other processing systems, and the one or more of the other processing systems uses its processor local memory exclusively except when the GNSS processing system needs to use the processor local memory.

Another aspect of the invention involves using an array processing architecture with DFT to acquire and track GNSS signals, such as from an E5 GNSS SV. This aspect is shown in FIGS. 4, 5A, 5B, 6, 7, 8, 9A-9D, and 10 and will now be described with reference thereto. FIG. 4 shows an example of a portion 150 of a GNSS receiver that receives GNSS signals and stores the GNSS signals in a two-dimensional (2D) baseband sample array after performing an analog-to-digital conversion. The GNSS receiver may include a GNSS radio frequency (RF) front end 153 that receives GNSS signals via an antenna 151 coupled to the GNSS RF front end 153. In one embodiment, the GNSS RF front end 153 only receives L5 WB GNSS signals.

FIG12 shows an example of components and architecture that may be used in an embodiment of the GNSS RF front end 153. As shown in FIG12, the GNSS receiver includes an RF front end module 701 and a digital front end 703 located on an ASIC (which may be part of the SOC 52); the RF front end module 701 may be separate from the ASIC containing the digital front end 703. The RF front end module 701 may be implemented in an RF integrated circuit (IC) coupled to a GNSS antenna 707 tuned to receive L5 WB GNSS signals; the GNSS antenna 707 is typically off-chip and therefore not located on the RF IC. GNSS antenna 707 receives GNSS signals and provides them to a bandpass filter 709, which is configured to pass signals centered at 1192 MHz and having a bandpass bandwidth of 51 MHz, and thus GNSS signals between approximately 1166.5 MHz and 1217.5 MHz pass through bandpass filter 709. The output of bandpass filter 709 is coupled to LNA 711 to provide the bandpass filtered GNSS signals to LNA 711. In one embodiment, GNSS antenna 707 is tuned to receive only L5 WB GNSS frequency signals. The RF front end module may include a low noise amplifier (LNA) 711 that is tuned for and therefore optimized to receive the L5 WB band only, and no other LNA that receives other GNSS signals (e.g., L1 GPS) is present in the GNSS receiver shown in Figure 12. The output of the LNA 711 may be filtered by a band pass filter 713 and the output from the filter 713 is amplified on an amplifier 715 on the ASIC containing the digital front end 703, and then an ADC 717 converter produces digitized GNSS sample data, which is then processed in one embodiment to produce two streams of digitized GNSS sample data: one is GNSS sideband A, and the other is GNSS sideband B. The clock generation phase locked loop 719 and the clock dividers 723 and 725 generate clock signals which are used by the ADC 717 and the CIC extractors 721 and 729 to generate digitized GNSS sample data having up to four GNSS signal components (e.g., E5AI, E5AQ, E5BI, and E5BQ). The downconverter 727 separates the I signal from the Q signal, and the sideband splitting downconverter 731 separates the upper sideband from the lower sideband to provide GNSS sample data for storage in a baseband sample memory (e.g., baseband sample memory 253 in FIG. 6 ). In one embodiment of the GNSS receiver shown in FIG12 , the GNSS receiver has a direct connection from an LNA (e.g., LNA 711) through one or more filters (e.g., bandpass filter 713) and/or one or more gain stages (e.g., amplifier 715) to an analog-to-digital converter (ADC 717), and this GNSS receiver does not have an RF mixer, and thus no RF mixer is present in the RF front end module 701 and no RF mixer is present in the digital front end 703. In addition, this GNSS receiver does not have an RF reference local oscillator (e.g., does not have a phase-locked loop) and no down-conversion (frequency) is performed in the RF signal path before the ADC (e.g., ADC 717). In conventional GNSS receivers, an RF reference local oscillator and one or more RF mixers are used to implement RF down-conversion in the RF signal path before the ADC.

Referring back to FIG. 4 , the output from the GNSS RF front end 153 may be provided to a radio frequency (RF) analog-to-digital converter (ADC) 155, which may generate digitized GNSS sample data from the digitized GNSS signal. In one embodiment, the output from the RF ADC 155 may be stored in a baseband sample array, such as the baseband sample array 157 shown in FIG. 4 . In one embodiment, the baseband sample array 157 may have N2 rows or more and N1 rows to provide an N2×N1 array (N2×N1). The number of samples in the array may be configured so that it satisfies the Nyquist criterion to provide a sufficient number of samples. If, in one embodiment, N1 = 20 and N2 = 1024, there are 20,480 samples over time (e.g., 1 millisecond or slightly more than 1 ms (e.g., 1.05 ms)), which may satisfy the Nyquist criterion. The RF ADC 155 is configured to repeatedly receive analog samples from the GNSS RF front end 153 over time and convert the analog samples into digitized GNSS samples for storage in the array 157. For example, the RF ADC may repeatedly convert samples of the GNSS signal and store them in the array 157. In one embodiment, array 157 may be implemented as a loop memory buffer that stores digitized samples; as is known in the art, a loop memory buffer may use a write pointer to indicate the next write location in the array and a read pointer to indicate the next read location. The write pointer is used when ADC 155 provides an output to be stored in the loop buffer, and the read pointer is used when the ALU reads the next set of inputs for processing. The array 157 may provide data to an arithmetic logic unit (ALU) 159 which is configured to perform DFT and inverse DFT to acquire and in one embodiment track GNSS signals, and FIGS. 6 , 7 , 8 , and 9 show an embodiment of the ALU 159. Before describing these ALUs 159, a method of using this array processing architecture will now be provided with reference to FIGS. 5A and 5B . The method shown in FIGS. 5A and 5B may use the array processing architecture shown in FIG. 6 .

In operation 201 shown in FIG. 5A , digitized GNSS sample data is stored in a two-dimensional memory array, which may be a circular buffer (e.g., memory 253 in FIG. 6 ) containing GNSS signal data slightly larger than a 1 millisecond frame (e.g., 1.05 or 1.25 milliseconds of GNSS signal data). The length of a frame of E5 GNSS PRN code data in a GNSS signal is 1.0 milliseconds. The additional memory beyond 1 millisecond may be determined based on the time required to calculate the spectrum of the data (via DFT) before the input data is overwritten. Therefore, a faster DFT means that a shorter additional time beyond 1 millisecond is sufficient. In one embodiment, the data in the memory array is formatted so that consecutive rows contain consecutive time samples. For example, the first row may contain samples from time period t1 to t20 and the second row may contain samples from time period t21 to t40. The array 157 shown in FIG4 shows an example of such an array, which in one embodiment may be stored in the baseband sample memory 253 in FIG6. In one embodiment, the purpose of these optimizations is to minimize the number of clock cycles required to perform a correlation procedure that is performed using frequency domain operations: i.e., the inverse DFT of the product of the DFT of the input samples multiplied by the complex conjugate of the code samples adjusted for the carrier frequency produces a correlation of the input samples under all possible code hypotheses under the carrier frequency hypothesis. This single step defined herein is referred to as Very Fast Frequency Domain Correlation (VFFDC) as a form of Frequency Domain Correlation (FDC). Optimizing the data stream through these operations can reduce the number of clock cycles required to perform the correlation. The advantage is that for a given system clock, the number of carrier frequency estimates or hypotheses that can be checked within 1 millisecond is increased. Additionally, reducing the clock means that system timing requirements can be relaxed, allowing a chip design to be more reliable or a design to operate at a lower voltage to reduce power consumption or clock faster to achieve greater throughput. Alternatively, a method of implementing FDC that requires more clocks but requires a higher clock frequency can be used. The clock required to implement FDC can be reduced using a matrix configuration (such as array 157), whereby the output of the sample and code spectrum is ordered so that the clock required to implement the IDFT of the complex conjugate of the product can be reduced. Then, in operation 203, a GNSS processing system (e.g., the GNSS processing system shown in FIG. 6 or the GNSS processing system 68 shown in FIG. 2 ) may retrieve the GNSS baseband data from the two-dimensional memory array and load the retrieved GNSS baseband data into a set of DFT ALUs. For example, the set of DFT ALUs may be a set of four ASIC hardware DFT ALUs in an acquisition engine, wherein each of the DFT ALUs may respond to a single program instruction and implement 20 parallel DFT operations in each DFT ALU. In one embodiment, the set of DFT ALUs may be the DFT ALU 255 shown in FIG. 6 . In operation 205, the GNSS processing system may generate PRN code data (or alternatively retrieve such PRN code data from memory) and/or generate a code spectrum of the PRN code data from the DFT for each expected GNSS signal source (e.g., each set of E5 or L5 or B2 GNSS SVs known to be in view). Once the PRN code data is generated, the PRN code data may be time shifted and frequency shifted, and sample interpolation may also be added (e.g., by adding a zero to fill the last bit in the code) to generate code data, which is operated on by a set of DFTs (e.g., using the DFT ALU 261 in FIG. 6 ) to generate code spectrum data, which may be stored in a code spectrum array (e.g., the code spectrum memory 263 shown in FIG. 6 ). In one embodiment, the code generator 259 may perform operation 205 to generate code array data, and then the DFT ALU 261 shown in FIG. 6 may process the code array data to generate a code spectrum array (in row order), which is temporarily stored in the code spectrum memory 263.

It should be noted that the code Doppler on the E5 band signal is much faster than the code Doppler in the L1 band. This code Doppler is a carrier Doppler scaled by the ratio of carrier cycles to chips. Under L1, there are 1540 carrier cycles per chip. Under L5, for example, there are 116 carrier cycles per chip. Therefore, the number of chips under L5 is 13.28 times faster, which means that the correlation in the E5 band needs to update the code phase faster to accommodate consistent correlations within consecutive frames of the PRN code. This means that it is generally impossible to pre-calculate this effect. An alternative solution is to apply the code Doppler effect to the correlation results first and then add the assumption memory. The storage locations can be shifted to counteract the code Doppler, but this results in some loss when the shift is quantized into a number of hypotheses, typically about 2 hypotheses/chip. Therefore, it is better to apply the code Doppler to the generated code before generating the code spectrum. Another optimization scheme is to multiply the carrier Doppler onto the generated code to match the carrier information in the input samples. In this way, the DFT of the input samples only needs to be performed once per millisecond for each sideband and/or centerband, and the same input spectrum can be used for all correlations performed within that millisecond.

In operation 207, a set of DFT ALUs (e.g., DFT ALU 255 shown in FIG. 6) may perform multiple DFTs on the loaded GNSS baseband data simultaneously using a time extraction method and store the results in a frequency domain result memory (e.g., memory 257 shown in FIG. 6). In the example shown in FIG. 6, operation 207 performed by DFT ALU 255 generates an array, which is arranged in a row order and stored in memory 257, and the data in this memory 257 may be retrieved to provide an output 258 shown in FIG. 6. The output 258 in operation 209 may be multiplied by the code spectrum stored in a code spectrum memory (e.g., code spectrum memory 263); in the example shown in FIG6 , multiplier 265 performs this multiplication of operation 209 and generates a product array of data. Then in operation 211 , a set of inverse DFTs may be performed on the data in the product array using a frequency decimation method, and these DFTs may use conjugate inputs to generate inverse DFTs. In one embodiment, the inverse DFT ALU 267 shown in FIG. 6 may perform operation 211, and the output from the inverse DFT ALU 267 may be processed in an associated post-processing operator 269 shown in FIG. 6, and then stored in a memory, which may be referred to as an integration memory (e.g., memory 271 shown in FIG. 6), in operation 213. In one embodiment, the integration memory may store hypothetical data during the acquisition phase. In one embodiment, this integrated memory may be in a portion of a cache (e.g., cache 70) allocated for use by an acquisition engine of a GNSS processing system including the array correlator of FIG. 6. The GNSS processing system may then perform operation 215 by determining the frequency of acquired PRN codes that identify the GNSS SV that transmitted the acquired PRN codes. Once it is determined that GNSS signals have been acquired from a particular GNSS SV, operation 217 may then be performed for each GNSS SV's signal that has been acquired by entering a tracking mode for the acquired GNSS signals. In one embodiment, the tracking mode may use a conventional correlator or other techniques such as DFT to determine the virtual distance to the acquired and tracked GNSS SV. This is shown as operation 219 in Figure 5B. The GNSS processing system may then use the determined virtual distance to derive a position of the GNSS receiver, i.e., by using the virtual distance of the tracked GNSS SV (with ephemeris data) to derive the position (e.g., a latitude and a longitude of the GNSS receiver), as is known in the art.

FIG6 shows an example of a fast frequency domain correlator architecture that can implement the method shown in FIG5A and FIG5B. Memory 253 can be a cyclic buffer memory that stores N2×N1 samples of digitized GNSS signals. In one embodiment, memory 253 can be two cyclic memory buffers that store 1.05 or 1.25 ms of GNSS sample data; one of these cyclic memory buffers can store GNSS sideband A sample data and the other can store GNSS sideband B sample data. The following method can be used to separate the two different sidebands and then store them. To obtain the upper sideband (e.g. E5B or B2B), the GNSS sample data is digitally ground-shifted down (for a sampler centered at 1191.795 MHz) by, for example, 15.345 MHz (and so will now represent information in sample data that was originally at 1207.14 MHz), and then filtered by a low-pass filter to capture a data bandwidth of +/- 10.23 MHz, and then the filtered sample data is dropped from a wideband sample to a lower sampling rate for processing in the pipeline shown in FIG6 . To obtain the lower sideband (e.g., E5A or B2A or L5 or QZSS), the GNSS sample data is digitally ground shifted up (for samples centered at 1191.795 MHz) by, for example, 15.345 MHz (and so will now represent information in sample data that was originally at 1176.45 MHz), and then the shifted data is filtered by a low pass filter (LPF) to capture a data bandwidth of +/-10.23 Hz, and then the filtered data is downsampled from a wideband sample to a lower sampling rate for processing in the pipeline shown in FIG. 6 . DFT ALU 255 retrieves data from memory 253 and performs a set of DFTs in DFT ALU 255; FIG. 7 shows an example of components within DFT ALU 255. In the example shown in FIG. 7, there are two DFT stages. The first stage uses N1 DTFs, each of which operates on 1024 points based on inputs including a phase factor input from array 301 and data from memory 253, which may be similar to the data shown in array 157 in FIG. 4. The input to the array is input 251, which may be provided, for example, by an analog-to-digital converter (e.g., RF ADC 155 shown in FIG. 4). FIG7 shows a set of 20 DFT operations, three of which are shown as operations 303, 304, and 306. The results of these operations may be stored in a portion of a result sample array 308, which in turn provides an output that is used as an input to a second stage in which there are N2 DFTs; these N2 DFT operations include the two operations 313 and 315 shown in FIG7. One of the inputs to these N2 DFTs is a set of phase factors from an array 311. The output from these DFT operations in the second stage shown in Figure 7 is stored in an FFT result array 257, and the data is stored in a row order that is the reverse of the column order in which the data is stored in memory 253. This reversal allows the data to be prepared for inverse DFT operations, such as those performed by inverse DFT ALU 267, without having to transpose or otherwise reformat the data.

FIG8 shows one embodiment of an inverse DFT ALU 267. In the example shown in FIG8, the inverse DFT ALU may include two stages of DFT operations that receive data from the product array from multiplier 265. The first stage may include N2 DFT operations that use data from the product array produced by multiplier 265 (with conjugate inputs) and also use phase factors from a phase factor array 351 to produce outputs that may be stored in a first stage sample array 361. Each of the N2 DFT operations in FIG8 is performed for 20 data points. FIG8 shows two of the total N2 DFT operations: DFT operations 355 and 357. In the example shown in FIG8 , the second stage of the DFT operation uses N1 DFT operations, each of which operates on N2 points; FIG8 shows three of these operations 363, 365, and 367, each of which receives a row of data from the first stage sample array 361. These DFT operations in the second stage also receive a phase factor input from the phase factor array 353, and these DFT operations in the second stage generate 20 outputs that can be post-processed in the post-processor 371 shown in FIG8 . The results of the post-processing can be stored in the integration array 373, which can be the same as the integration memory 271 shown in FIG6 . The phase factors from arrays 301 and 311 (in FIG. 7 ) and arrays 351 and 353 (in FIG. 8 ) specify the phase shift required for each basis (20/16/8 DFT at each stage of the FFT). In one embodiment, these phase shifts are used to decompose a 20480 point DFT into multiple basis stages - 20/16/8 DFT, which is an FFT implementation based on a DFT. Phase factors are also called "rotation factors" of an FFT.

9A, 9B, 9C and 9D show an example of a spectrum code generator (and portions thereof) that can generate spectrum codes that are stored in a code spectrum memory (e.g., code spectrum memory 263 in FIGS. 6 and 8). In one embodiment, when the GNSS processing system acquires and tracks GNSS SVs in view, the generator 259 and DFT ALU 261 shown in Figure 9D may generate PRN codes and/or code spectra of PRN codes from DFT on-demand and temporarily only for such GNSS SVs, but do not store (except temporarily stored in registers and buffers in the processing pipeline for a few clock cycles) the generated PRN codes and/or their code spectra from DFT; this can increase the memory used by the GNSS processing system by reducing the amount of memory required to operate the GNSS processing system. In an alternative embodiment, the code spectrum generator may generate PRN codes and/or code spectra of PRN codes from DFT only on demand for GNSS SVs in view, but store the codes during the acquisition and tracking phase until one or more positions (e.g., one or more longitude and latitude values) are determined. Thereafter, the PRN codes and/or their code spectra from DFT may be deleted from memory to allow the memory to be used for other purposes. In one embodiment, as shown in FIG. 9D , the code spectrum generator 259 may use a polynomial type generator 402 (shown in FIG. 9A ) to generate PRN codes from a code seed 401 for each GNSS SV in view. The generated PRN code may then be time shifted in time shifter 404 using a set of programmable coefficients (based on the coefficients), and the generated and time shifted PRN code may then be frequency shifted by a frequency shifter that may use CORDIC phase rotations, three of which are shown as CORDIC phase rotations 408, 410, and 412. The phase rotations may be based on a programmable phase division input 406. Another set of CORDIC phase rotations (including phase rotations 417, 419, and 421) may then generate an output that is then processed by the same DFT operation (implemented by DFT ALU 261 in FIG. 6 in one embodiment) as that performed on the digitized GNSS sample data. Then, in one embodiment, the result of the DFT operation (in one embodiment, performed by the DFT ALU 261 in FIG. 6 ) is stored in a code spectrum memory, such as the code spectrum memory 263 shown in FIG. 6 .

One embodiment of a polynomial type generator 402 is shown in FIG. 9A . This embodiment may be used to implement the methods shown in FIG. 9B and FIG. 9C . This generator 402 includes two calculated (or pre-calculated) code advance matrices 501 and 502 retrieved, for example, from a lookup table, if pre-calculated. For example, for each of the four components of the Galileo E5A and E5B signals, there is a corresponding code type and master code polynomial data; this information is well known in the art and published in the ICD of the source of the GNSS constellation. The generator 402 may generate more than 2 of the master PRN code bits within a single clock cycle by using the calculated code advance matrices 501 and 502; see operations 955 and 957 in FIG. 9B . As shown in FIG. 9A , the calculated code-forwarding matrix 501 includes a first input that receives a generator polynomial 503 that can be used as master code polynomial data for a given GNSS cluster and a given GNSS signal component; and includes a second input that receives a value fed back from a register 515; and includes an output that is a first input to a multiplexer (MUX) 511. A second input 507 to MUX 511 is a constant initial value, all 1s (14 bits, each of the 14 bits is set to a value of 1 in one embodiment); this second input 507 is only used for the initial output from register 515, and thereafter MUX 511 selects the first input (to MUX 511) as the output from MUX 511, and stores the output in register 515 (which can be a clock-controlled register) so that on the next clock cycle the final output from MUX 511 is fed back to the second input of the code advance matrix 501 and is also provided as a first input of the XOR logic gate 519. The output from MUX 511 fed back to the second input (of code-forward matrix 501) is multiplied by the constant value in code-forward matrix 501 (derived from generator polynomial 503) to generate the next output from code-forward matrix 501 and is passed through MUX The next output is passed to 511 and stored in register 515; this process of feeding back the output from register 515 and performing a matrix multiplication of the output with a constant value in code advance matrix 501 is repeated on each clock cycle (or alternatively in a group of several clock cycles) to generate N bits of the main PRN code for a given GNSS cluster (e.g., Galileo E5) and a given GNSS signal component (e.g., E5AI) in each clock cycle. In one embodiment, N may be greater than 2, such as 10 or 14 bits. Thus, generator 402 can quickly generate multiple (e.g., N) bits of the primary GNSS PRN code within one clock cycle or a few clock cycles. In the example shown in FIG. 9A , 14 bits are generated from the output of register 515 , but XOR logic gate 519 (which implements an exclusive or logic operation) only uses the last 10 bits. The use of code forward matrix 502 is similar to the use of code forward matrix 501 . Code forward matrices 501 and 502 are (in one embodiment) pre-calculated to generate (at the output of XOR logic gate 519) N bits below the primary GNSS PRN code of the GNSS signal component from the GNSS SV in the given cluster for a given GNSS cluster and GNSS signal component and a given seed of a GNSS SV in the given cluster (a "shift" of N bits) based on the values in the matrices and the previous outputs from registers 515 and 517. The Matlab Appendix contains an example of a code generator 402 that can form and use these pre-calculated code forward matrices, in the form of well-known Matlab codes. In one embodiment, a pre-calculated code shift matrix may be pre-calculated (or calculated on the fly) by multiplying an original matrix containing the principal polynomial data N times to provide N shifted bits in the PRN code within each clock cycle. For example, if a shift of N=3 is desired, the original matrix ("A") is multiplied 3 times (A*A*A) to provide a code shift matrix of N=3 bits for the output of the next 3 bits in the PRN code. 9A , the calculated code forward matrix 502 includes a first input that receives the generator polynomial 505, which may be the master code polynomial data for a given GNSS cluster and a given GNSS signal component, and includes a second input that receives a value fed back from register 517, and includes an output that is a first input to MUX 513. A second input 509 to MUX 513 is a seed value for a corresponding GNSS SV in the given GNSS cluster. This seed value is only used for the initial output from multiplexer 513 and from register 517 and thereafter MUX 513 selects the first input (going to MUX 513) as the output of MUX 513 and the output is stored in register 517 (which may be a clock-controlled register) so that on the next clock cycle the final output from MUX 513 is fed back to the second input of the code advance matrix 502 and is also provided as a second input to the XOR logic gate 519. The output from MUX 513 fed back to the second input (of code advance matrix 502) is multiplied (in a matrix multiplication operation) by the pre-calculated value in code advance matrix 502 to produce the next output from the code advance matrix 502, and the next output is passed through MUX 513 and stored in register 517. On each clock cycle, the outputs from registers 515 and 517 are mutually exclusive-ORed by XOR logic gate 519 to give 10 new bits (i.e., 10-bit advance of the PRN code); the 14-bit output is truncated within the current clock cycle to give 10 new bits. Code advance by ten 524 can be truncated optionally. XOR logic gate 521 then performs an exclusive OR operation on the output from XOR logic gate 519 and the secondary code bits 523 from a given GNSS signal component of a given GNSS SV to "erase" or "remove" the secondary code from the code generated at the output of XOR logic gate 519. Left shift logic 527, increase sampling logic block 529 and left shift logic 533 along with registers 526 and 531 further process the generated primary PRN code to provide code samples that can be "aligned" with the received GNSS samples at a specific sampling rate so that the sampling rates match and can be aligned. Shift logic can be used to shift or move to different parts of the PRN code. The output from the left shift logic 533 is provided to the time shifter 404 in the code spectrum processing pipeline shown in Figure 9D.

9B and 9C show a method for the opcode generator 402. In operation 951, a GNSS processing system determines the GNSS SVs in view, for example based on learned auxiliary data (e.g., a recently downloaded version of a GNSS satellite almanac) or based on almanac data in the form of equations. In one embodiment, the GNSS SVs in view may be limited to L5 WB GNSS SVs, such as one or more of the Galileo E5 GNSS cluster, the US L5 GNSS cluster, and the Chinese Beidou/Compass B2 cluster. Then in operation 953, the GNSS processing system may determine a code type and a code generator polynomial (which may be a set of known coefficients for the signal component) for each GNSS signal component from a GNSS SV in view (e.g., E5AI and E5BI of a Galileo E5 GNSS SV) to generate a primary PRN code for the GNSS signal component. Then in operation 955, a G1 code forward matrix is calculated (or pre-calculated and retrieved from a lookup table in non-volatile memory), and in operation 957, a G2 code forward matrix is calculated (or pre-calculated and retrieved from a lookup table in non-volatile memory). In one embodiment, each of the G1 code shift matrix and the G2 code shift matrix is pre-calculated by multiplying an original matrix of the main code polynomial data N times, where N represents a desired number of code bits to be generated. For example, if the code "shift" amount is 10 bits of the main PRN code data, the original matrix is multiplied (squared) ten times to form a 10-bit code shift matrix. In one embodiment, the code "shift" amount is the number of bits of the main PRN code data generated in one clock cycle, so if N = 10, the code generator generates 10 new bits of main PRN code data every clock cycle. After retrieving (if pre-calculated) or calculating the G1 code forward matrix and the G2 code forward matrix, the method can then continue in operation 959. In operation 959, the system uses the initial vector (all 1s) to provide a first G1 output (so the first G1 output is the initial vector of all 1s) and the system uses the code seed to provide a first G2 output (so the first G2 output is the code seed); in operation 961, the system performs an exclusive or operation on the first G1 output and the first G2 output to provide the first set of N-bit PRN code data. After operation 961, the first set of N-bit PRN code data is processed in operations 969, 971, and 973 (as processing continues through 9X (from operation 961 to operation 969 shown in Figures 9B and 9C)) and all subsequent sets of N-bit PRN code shifts are generated in the loop of operations 963, 965, 967, 969, 971, 973, and 975. In operation 963, the G1 output (e.g., from register 515 in Figure 9A) is fed back to the G1 code shift matrix and the G2 output (e.g., from register 517 in Figure 9A) is fed back to the G2 code shift matrix. Then in operation 965, the last G1 output (e.g., from register 515) is multiplied with the G1 code forward matrix to produce the next G1 output, and the last G2 output (e.g., from register 517) is multiplied with the G2 code forward matrix to produce the next G2 output. In operation 967, the G1 output and the G2 output are mutually exclusive or operated (e.g., in XOR logic gate 519 in FIG. 9A). In operation 969, the code output from XOR logic gate 519 (e.g., in XOR logic gate 521) and the expected secondary code bit (e.g., secondary code bit 523) are mutually exclusive or operated to erase or remove the secondary code from the code output. Then in operations 971 and 973, code samples are generated and provided to the residual code spectrum processing pipeline. These operations prepare the code samples so that their sampling rate can match the sampling rate of the received GNSS sample data. Operation 975 determines whether to continue to generate GNSS main PRN code data. In one embodiment, when tracking of all required GNSS signals is completed, the generation of PRN code data can be terminated, but if such tracking is required, the process continues in the loop from operation 963 to operation 975.

FIG. 10 shows an example of a GNSS processing system that may be used to implement the methods described herein or may be used to implement the systems described herein. The GNSS processing system 450 may be implemented on its own integrated circuit (e.g., a navigation chip 451) or may be part of a system on a chip architecture that is part of a larger system such as a smart phone or tablet computer. The GNSS processing system 450 may include processing logic such as an ARM processor 466 that uses ARM programs and data memory 467 to control the operation of the GNSS processing system 450. In addition, the GNSS processing system 450 may include an RF ADC 465 that may be similar to the RF ADC 155 shown in FIG. 4. The GNSS processing system 450 may also include a clock phase-locked loop generation and gating circuitry 464 to use the phase-locked loop and generate clocks for other operations in the GNSS processing system 450. The GNSS processing system 450 may include both logic modules and memory to implement the acquisition and tracking procedures described herein. For example, the logic module 457 may include an acquisition engine 458, which may include a set of DFT and inverse DFT processors or ALUs to implement the DFT operations described herein. In addition, the logic module 457 may include a digital front end 460, which may be located in all digital E5 GNSS front ends to provide processing before and after the RF ADC 465. The logic module 457 may also include a plurality of satellite signal generators (such as satellite signal generator 459) that generate GNSS PRN codes for GNSS satellites (SVs) in view based on auxiliary data that may be received, for example, from a cellular data communication network. The logic module 457 may also include a timing and control module 461 and a memory interface and bus control module 462 to allow the GNSS processing system to be coupled to one or more application processors. The logic module 457 may be coupled to one or more memories for storing various data in various data structures, for example, the one or more memories include a baseband sample memory 468, an acquisition engine command memory 469, an FFT program memory 470, an FFT constant memory 471, an FFT variable memory 472, an FFT result memory 473, a code spectrum generation memory 474, a coherent integral memory 475, an IFFT memory 476, an IFFT memory 477, an IFFT variable memory 478, and an incoherent integral memory 479. Such memories may be used with logic module 457 to perform the operations described herein. It will be appreciated that alternative architectures may use different processor and memory configurations than shown in FIG. 10 .

In another embodiment, the clocks required to perform the DFT operation are reduced by performing multiple core operations in parallel. For example, if the sampling rate is chosen to be 2^N (e.g., N=14), a radix-4 core with 7 stages can be used to implement the DFT. Each step of each stage processes 4 samples in real time. Assuming only dual-port memory, with one read and write per cycle, the clocks required for the stage are 4*4096, and 7 stages require 114,688 clocks. The VFFDC shown in Figure 6 can achieve a DFT in approximately 4096 clocks. To achieve similar performance, 32 cores could be implemented in parallel so that one stage could be completed in 512 clocks, and 7 stages would be completed in 3584 clocks. However, this approach would require being able to reach 32 input samples in parallel. Thus, the advantage of VFFDC is that a low clock rate can be achieved while only reading 10 memories in parallel. Another embodiment uses a 4 times higher clock rate, and then only requires 8 cores in parallel, which reduces the parallel memory read requirement to 8 inputs/outputs per clock. The advantage of VFFDC is that both a low clock rate and a low parallel memory read/write configuration can be maintained. This optimization should allow low power consumption since the system can operate at a low clock speed and achieve reliable timing at low voltage.

In one embodiment, VFFDC implements a processing chain with minimal memory requirements. Every millisecond, two DFTs are performed on the input samples, one for each of the upper and lower sidebands of E5. Then for each component of each satellite signal (4 for E5, 2 for L5, and 4 for B2 in the future), a DFT is performed that includes code Doppler and carrier frequency effects so that a different DFT does not have to be applied to the input samples to remove the carrier frequency assumption. Then, another DFT is performed to perform an inverse DFT on the product of the input and code spectrum. Therefore, the total number of DFTs per millisecond is 2 + 2*N channels*M components, where the first 2 are the original input DFTs and the second 2 are the IDFTs that make the code spectrum and the spectral product. Up to 22 channels with 4 components per channel, this is 2 + 2*(22*4) = 178 DFTs/ms. If the code spectrum DFT is calculated in advance, the input samples must be unique for each frequency of each PRN. In this case, the number of DFTs is (2*M*N) = 176, where M=4 and N=22. However, this requires a memory to store the code spectrum. Such a system will also need a method to generate the code Doppler after each IFFT and before updating the assumption memory. Therefore, even if the alternative is almost the same number of DFTs, it still requires additional memory and may have higher power consumption per millisecond to move the code spectrum DFT to the AE. For example, with 20480 assumptions per millisecond, a required bus rate would be 22 channels * 4 components * 2 bytes of I, Q of the code spectrum * 20480 assumptions * 8 bits/byte 28Mbit/millisecond = 28Gbit/second. This configuration would be almost impossible to implement. Therefore, on-site computing power makes the system feasible.

Another optimization to reduce system memory is to allow all four components of the E5 band signal (such as Galileo E5) and future B2 to be processed into a single hypothetical memory for long-term integration to overcome weak signals due to high system losses in cellular phones and/or high losses due to attenuation of the signal by foliage or the user's body. The public domain interface control files for B2 only describe the lower sideband, but other technical papers suggest that the upper sideband signal structure will be available by the end of 2019 or later. Therefore, GPS L5, which has only one sideband, will have only two components, while E5 and B2 will have 4 components: two on each of the upper and lower sidebands.

The main challenge of coherently integrating the sum of each millisecond code correlation is to reduce the cancellation loss due to phase reversal at 1 ms time segments. If the primary code phase of the received signal can be estimated to be approximately 0.5 ms or less, the received signal spectrum can be at least partially aligned in time with the estimated code phase so that sub-millisecond cancellation is avoided. FIG. 11 shows an embodiment that can provide accurate time coherent integration.

In one embodiment, estimating the expected partial primary (ms long) code phase of the candidate signal requires knowledge of both precise time and initial position. As is known in the art, precise time can be derived from the secondary code phase of a first received signal or can be derived from a precise time source. This estimation can be operation 601 in FIG. 11 .

Once the primary code phase uncertainty is reduced to well below 1 ms, the sub-millisecond cancellation problem can be solved by at least partially aligning the time segments of the received 1 ms signal with the time at which the code is expected to be received from each SV. This means that multiple received signal spectra must be calculated every millisecond, staggered in time to match the primary code spectrum and thus reduce the extent of sub-ms coherence cancellation.

The search order can determine which SVs, their signal components, and Dopplers will be searched at each partial phase offset. This is shown as operation 603 in Figure 11. Since the long coherent integration generates greater sensitivity, the E5Aq and E5Bq pilot signals can be used preferentially because the E5Aq and E5Bq pilot signals have 100 ms long secondary codes and no data bit inversion. In one embodiment, if the navigation message symbol is predicted and removed, E5Ai and E5Bi can also be used, thereby eliminating or reducing their respective coherent pair consumption losses. It should be noted that although the main code phase of all signals is expected to be unevenly distributed across one millisecond, it may be possible that the processing slot that can be used for only a given signal is suboptimal. Regardless, the worst case scenario where the first ½ ms of the signal cancels out the second ½ ms in a subcode bit inversion situation will always be avoided.

In one embodiment of the invention, M 1ms signal spectra are calculated every millisecond, each spectrum offset by 1/M ms. For example, if M=4, then every 0.25 ms, a full 1 ms (or more than 1 ms) of received and digitized GNSS sample data is processed by FFT correlation (e.g., using the VFFDC architecture shown in FIG. 6 ), so in this case the processing time periods are separated and offset (one from the next) by 0.25 ms and the received GNSS sample data are also offset by 0.25 ms. In this example, a first processing time period at relative time 0.0 ms will process the FFT correlation on the 1 ms of GNSS sample data generated in operation 605. These correlations are shown as operation 607 in FIG. 11 . A second processing period at 0.25 ms relative time will process the FFT correlation (operation 607) using 1 ms of GNSS sample data ending at 0.25 ms relative time (operation 605) and offset from the previous 1 ms by 0.25 ms. A third processing period at 0.5 ms relative time will process the FFT correlation (607) using 1 ms of GNSS sample data ending at 0.5 ms relative time (operation 605) and offset from the previous 1 ms by 0.25 ms. Thus operations 605, 607 and 609 are repeated four times during a 1 ms time interval. In an alternative more sensitive embodiment, the signal spectrum is calculated to align as closely as possible with each expected satellite code phase.

In the case of coarse time mode, candidate signal codes (received GNSS sample data) and their associated spectra must be generated and aligned every millisecond and correlated with the signal spectrum using VFFDC or similar FFT-based methods.

When these resulting correlations are generated, they must be summed in a coherence hypothesis memory dedicated to each SV band and segment, with the phase reversals associated with the secondary code removed. This is shown as operation 607. This procedure requires the calculation of full 1 ms correlations, but the code phase uncertainty is much less than 1 ms. However, only the portion of the full PN code that may contain a correlation peak must be stored in the hypothesis memory.

At the sub-code period boundary, or more often in some cases, the coherent hypothesis memory must be summed incoherently into a non-coherent hypothesis memory that is a mirror image of the coherent hypothesis memory but contains only magnitude information and may therefore reserve half of the memory. This is shown as operation 611.

The process in FIG. 11 continues in operation 613 (by returning to operation 605) until a correlation peak rises above the noise floor. Once the correlation peak rises above the noise floor with sufficient confidence, the search result is reported and the acquisition search for the particular SV of interest may be terminated, toward the next SV in the search order to obtain its partial code phase. The search may also time out after a preset time interval and a search failure may be reported.

FIG. 11 shows an example of a method of how a satellite code may be searched in alignment with an approximate time grid in which the satellite codes are expected to be received so that sub-millisecond coherence pair loss due to phase reversal may be reduced. This search may be performed based on an initial set of information, which in one embodiment may include at least two of the following: (1) a code phase of a primary or secondary code signal received from at least one GNSS SV; (2) a GNSS time estimated based on one or more time sources, the estimated GNSS time uncertainty being estimated (e.g., based on the known accuracy of the sources) or known to be within +/- 0.5 milliseconds of the actual GNSS time; and (3) an approximate position of the GNSS receiver. Using this initial set, operation 601 in FIG. 11 may be performed. In effect, this initial set gives the system an estimate of GNSS time to enable acquisition using GNSS time.

A machine-readable medium includes any mechanism for storing information in a form that can be read by a machine (e.g., a computer). For example, a machine-readable medium includes read-only memory ("ROM"), random access memory ("RAM"), disk storage media, optical storage media, flash memory devices, etc.

An article of manufacture may be used to store program code. An article of manufacture storing program code may be embodied in, but not limited to, one or more memories (e.g., one or more flash memories, random access memory (static random access memory, dynamic random access memory, or other random access memory)), optical disks, CD-ROMs, DVD ROMs, EPROMs, EEPROMs, magnetic or optical cards, or other types of machine-readable media suitable for storing electronic instructions. Program code may also be downloaded from a remote computer (e.g., a server) to a requesting computer (e.g., a client) by data signals embodied in a transmission medium (e.g., via a communication link (e.g., a network connection)).

In the foregoing specification, specific exemplary embodiments have been described. It is apparent that various modifications may be made to these embodiments without departing from the broader spirit and scope set forth in the scope of the following patent application. Therefore, this specification and drawings should be regarded as having an illustrative rather than a restrictive meaning.Appendix The following appendix provides further information regarding some embodiments. These embodiments are non-limiting examples of GNSS receivers, portions of GNSS receivers, methods for operating such receivers or portions, and non-transitory machine-readable media that can enable the performance of such methods. A "Matlab" code appendix is also attached and provides examples of implementations of various components described herein in the form of well-known Matlab code. Appendix 1 Appendix This appendix provides further information regarding various embodiments and aspects of the present invention, but is not intended to limit the scope of any claim in the subject matter of the accompanying application. An all-digital receiver architecture for commercially viable modern GNSS signal tracking Inventors: Paul Conflitti, Paul McBurney, Mark Moeglein, and Greg Turetzkybackground SnapTrack's development of Assisted GPS between 1995 and 1999 (see, e.g., U.S. Patents 5,663,734 and 5,812,087) brought GNSS tracking to mobile phones worldwide. At the time, GPS was the only GNSS constellation in operation, and the L1 C/A signal was the only signal open to civilian use. The simplicity of the L1 C/A signal (with a 1 MHz chip rate and a 50 BPS navigation message) and the nature of the CDMA2000 cellular system formed a combination of two receiver strategies suitable for a mobile phone, where they shared a common oscillator, and the synchronous nature of the network allowed time and frequency to be communicated from the base station to the mobile device with great accuracy. It also enables the provision of auxiliary data to mobile devices so that they do not need to read it directly from satellites, thus saving a lot of time and processing power and greatly improving sensitivity. > These same factors also enable Advanced Forward Link Trilateration (AFLT), effectively forming a virtual satellite network from the base stations of a synchronized CDMA2000 cellular network. The complexity of modern cellular networks (including 4G and 5G) and modern GNSS systems has continued to grow with the proliferation of a GNSS cluster including Galileo (Europe), BeiDou/Compass (China) and a modern GPS. All three clusters interleave in the L5 band and share the spectrum. GPS L5 is a 10.23 MHz extended bandwidth signal centered at 1176.45 MHz. Both Galileo and BeiDou use an altBOC code to spread the signal energy into two sidebands. The two sidebands of Galileo (A-Sideband and B-Sideband) are centered at 1176.45 MHz and 1207.14 MHz, +/-15.345 MHz from its center frequency (1191.795 MHZ). They are similarly modulated using a 10.23 MHz code. Finally, BeiDou has a signal at virtually the same frequency as Galileo, with the same length extended code. India and Japan also have regional systems developed and transmitting in this band. The Japanese system, QZSS, uses a signal very similar to GPS. The Indian system has BOC modulation and a regular center frequency, but it also has a narrowband signal centered at 1176.45 MHz. Thus, GPS, BeiDou, Galileo, QZSS, and IRNSS all have signals in the 1176.45 MHz L5A band. In addition, Galileo and BeiDou have similar signals centered at 1207.14 MHz, which will be called the L5B band. GLONASS also has similar proposed signals at 1176.45 MHz and 1202.025 MHz. In practice, there are two sets of modern signals that have certain common properties, some of which are at L1, such as E1B and E1C; and these are at L5, such as E5 and B2. Their main differences are in the chip rate and code length. Here are some of the key advantages of these modern wideband GNSS signals at L5 over legacy signals or signals in other frequency bands: 1. The code length has been increased 10 times compared to GPS L1 C/A to further mitigate cross-correlation and up to 4 different signals broadcast by each SV are designed to be orthogonal to each other. Unfortunately, most of these signals use the same 10,230 chip code length and 10.23MHz chip rate, so there is still the possibility of cross-correlation between signals where one signal is directly received and another is relatively weak/indirect. 2. All signals are in the same frequency band, allowing a single RF front end to track all signals. 3. Pilot codes allow for enhanced sensitivity for tracking in blocked signal environments. 4. Galileo and BeiDou’s AltBOC (15,10) signals provide transmit diversity for improved fading resistance and improved multipath resistance. 5. Data and pilot channels are orthogonal. This yields the following advantages: a. Improved SNR when combining signals (specifically, when combining signals incoherently). b. Ability to coherently track pilot channels that are primarily limited by oscillator stability and user dynamics. c. Can be tracked using a pure PLL rather than a Costas loop. This avoids the square loss of removing data bit inversions and allows the use of a full discriminator range of +/-180 degrees. 6. Advanced coding of data on the data channel to reduce the bit error rate. This allows data to be extracted at a lower SNR, thereby improving the ability to determine precise time with weak signals. 7. The secondary code with overlapping codes changes the primary code frame. This reduces the cross-correlation between codes by removing the constant phase sequence. The secondary coding also allows the GNSS time to be accurately determined from the secondary code phase, and the clock can be set with great absolute accuracy when the receiver clock uncertainty is less than the duration of the secondary code. 8. High chip rate. Higher chip rates narrow the correlation peak to reduce multipath and cross-correlation. 9. Codes that complete in 1 millisecond. This allows a faster acquisition and achieves a feasible FFT method using cyclic convolution. This achieves a commercially viable modern-only GNSS receiver (COVIMOGR). The longer the code, the more expensive it is to acquire. Modern codes at L1 are typically longer and therefore more difficult to acquire directly. The key benefit of these modern GNSS signals (extended codes and higher chip rates) also makes them more challenging than previous receivers, but modern correlator hardware can easily handle these challenges, as will be explained in another embodiment of this article. Receiver manufacturers plan to acquire L1 band signals first (GPS C/A codes, Galileo E1, BeiDou B1 or B1C or GLONASS FDMA) and then move to L5 tracking because the computational load of tracking longer codes when the timing uncertainty is about 1 ms can be daunting. Frequency domain correlation has been proposed by some to solve this problem of directly acquiring the wideband 10.23 MHz signal. However, strategies for doing so rely on substantial FFT hardware, including much more memory than is commercially viable for consumer applications such as cell phones, wristbands, or even vehicle navigation. Cell Phone Network Synchronization  While the embodiments described herein are suitable for standalone GNSS receivers, it is recognized that the most important market for GNSS receivers is actually as components of larger mobile devices such as cellular phones. The complexity and data carrying capacity of mobile networks have increased substantially, but the time and even frequency synchronization that was reliably available for these networks associated with Qualcomm's 2G and 3G technology, while still supported, is no longer guaranteed for 4G and 5G systems. As a result, Qualcomm's AFLT technology for cell-station ranging is generally no longer supported, and multi-cluster GNSS tracking has replaced it to some extent. Moreover, at the time of this writing, fine timing aids to help synchronize these networks are not yet commonly available. Therefore, any commercially viable direct L5 acquisition strategy (i.e., without using L1 GPS) must allow for significant time uncertainty and even frequency uncertainty, and also allow for the possibility that fine time and frequency aids will not be available. Where cellular data (e.g., the Internet) is available, time transport protocols (e.g., NTP and SNTP) typically limit this time uncertainty. The limiting frequency uncertainty is the cellular carrier frequency, which is itself subject to availability and variations in network type and network implementation. Therefore, any design with modern AGNSS capabilities must allow for different initial time and frequency uncertainties. Benefits of Direct L5A  Some key benefits of just tracking L5 over transitioning from L1 to L5 include: 1. Eliminate one RF front end, including expensive antenna, LNA, and SAW filter. This also substantially reduces integration difficulty. 2. Signals with improved sensitivity and robustness to fading are available. 3. Near-field correlation acquisition problems are substantially reduced. 4. Susceptibility to congestion and jamming is reduced. Some disadvantages include: 1. Currently, there are relatively few SVs that support modern signals. This gap is expected to narrow rapidly in the next few years. 2. Increased complexity, especially in acquisition.decline Pf_L1 It is defined as the probability of a carrier tracking loss at L1 frequency that is large enough. Similarly, Pf_L5 Defined as the probability of a carrier tracking loss on L5. Pf_L1 and Pf_L5 Through the signal path related, but independent of the different expected C/No. Typically, when the data and pilot energy at L5 are combined synchronously, the L5 signal is expected to be enhanced by 3dB, making P_fL ＜P_fL . Acquiring a signal at L1 in a fading environment is inherently unreliable, so if the receiver antenna is in a local null, then it is impossible to acquire a signal at L5, not to mention impossible to track. At any given moment, P_acq Becomes 1-P_fL . Ptrack is then used to initially reacquire (1-P_fL )*(1-P_fL ). In the direct acquisition case, P_acq Only (1-P_fL ). However, direct acquisition is about an order of magnitude more complex in terms of both signal processing and memory, and it is also likely to be more difficult to maintain carrier tracking without the assistance of an L1 carrier. Therefore, direct acquisition reliability is significantly greater in all Rician and Rayleigh fading scenarios, especially for consumer applications with substantial subject blockage, linear antennas, and cluttered environments. However, tracking L1 and L5 signals in the worst environments yields transmit diversity gain. However, given the relative inaccuracy of code tracking at L5 and the weakness of the L1 signal, the loss is not noticeable, especially after full operability of the L5 band signal of the main GNSS constellation is achieved. The diversity gain associated with tracking multiple separable signals under L5 also makes L1 tracking less important. Although some performance gain is obtained from the additional carrier, it is substantially less than the gain obtained from the additional carrier under L5. Take the Galileo E5 altBoc signal with multiple separable lobes. If a receiver only tracks the E5_A and E5_B , but only one or the other is needed to maintain the continuity of its carrier smoothing and incremental position solution, then P_slipE5AB Defined as P_slipE5A *P_slipE5B . In example P_slipE5A=P_slipE5B=0.001, P_slipE5AB will be 0.000001. While tracking E1 does provide greater carrier tracking reliability, that gain is negated somewhat by limiting acquisition and reacquisition to E1 and the weaker signals and lower accuracy codes at E1. The E5 signal includes 3 additional lobes approximately 10 dB below the two main lobes, providing an additional form of diversity that further eliminates the need to acquire or track E1. Obviously, for the L5-I and L5-Q signals, less transmit diversity is available, and so L1 and L2C tracking may still be of great interest, especially until the constellation of satellites supporting L5 is expanded. This may also allow better local measurement of ionospheric TEC along the ray path. In the long run, BeiDou with its expected available B2B signals is more like Galileo. Description of Embodiments of the Invention  The following figure illustrates a possible digital signal processing front end according to an embodiment of an aspect of the invention as described herein. Antenna -> Filter -> LNA -> RF Downconverter (from 1189MHz to DC with +/-54 MHz BW). Sampling at 108Mhz generates in-phase (realC = cosine) and quadrature (imagC – sine) samples. Bandwidth extends from +/-54Mhz at L5 center frequency 1191.795MHz. GNSS Receiver Front-End Signal Processing Flowchart Sideband A is centered down 15*1.023 Mhz, and sideband B is centered up 15*1.023 Mhz. Thus a 15*1.023 Mhz digital local oscillator is created. Call it sideband SB. Sideband A below -15*1.023MHz is shifted to DC by performing a frequency shift: Ai = real * cos(SB) – imag * sin(SB) Aq = imag * cos(SB) + real * sin (SB) The signal is then low pass filtered and decimates from 100 Mhz to 16.384 Mz using a clock divider. Similarly, the 15*1.023MHz upper sideband B is shifted to DC by a frequency shift: Bi = real * cos(SB) + imag * sin(SB) Bq = imag * cos(SB) - real * sin (SB) The signal is then low-pass filtered and decimated from 108Mhz to 20.46MHz using a clock divider. The decimator is simply a clock divider that generates 20,460 clocks from 108,000 samples in one millisecond. Acquisition and Tracking Modes  A commercially available direct acquisition broadband GNSS receiver should use its limited resources efficiently based on the state of the acquisition and tracking process. Applications without minimal data connectivity may necessarily use the "air search" mode, but the more interesting case is when aiding data is available and does not need to be derived from satellite signals. These pieces of aiding information can be roughly categorized into receiver clock settings (time), oscillator training (frequency), initial position, satellite position, and satellite clock information (almanac). Depending on the quality of all these forms of aiding, in one embodiment, the commercially available modern unique GNSS receiver (COVIMOGR) described herein should be able to acquire the signal and derive the aiding information it needs as quickly as possible. To this end, three different acquisition modes are described: 1. Air search: One of the key auxiliary components described above is effectively missing and therefore the receiver must "air search" for all signals of all known clusters. This is the least attractive scenario, as its use cases have been reduced in a connected world. In this sense, it is a slowed-down version of Mode 2. 2. Coarse time: The receiver clock time is known to be within a few seconds, but not to 0.5 ms (the more accurate the better) and a reasonably accurate initial position is available. In this mode, direct acquisition is challenging, as most signals under L5 are wideband signals with millisecond codes that are an order of magnitude longer than L1-C/A. For COVIMOGR, attempts to correlate directly with these signals using a time domain correlator library are not computationally feasible, especially for receivers that must acquire in obstructed environments and have non-optimal antennas, which are typically commercially available. 3. Precise Time: Once a first satellite signal is acquired or precise time aid is received, the uncertainty of the millisecond code phase for each satellite can typically be reduced to about 100 microseconds or less, provided that sufficiently accurate aid information is available. In this case, signal processing is specified in a precise time mode to achieve maximum sensitivity and minimum resource allocation. The precise time source can be the initial signal or signals that have been acquired and/or tracked, or it can be based on network aids, or a combination thereof. Once the signal is acquired from each SV, it is passed to a tracking engine which is responsible for reading the navigation message data and providing ongoing virtual range, Doppler and carrier phase measurements. In addition, it can read the phase of the secondary code, allowing the millisecond code phase to be extended to the virtual range of all SVs, which is a key benefit for the precise time acquisition mode. Signal Processing in Coarse Time Mode  For the most complex case, this article will explain the acquisition of the Galileo E5 double-sideband altBOC code. Alternative solutions for processing single-band Beidou and GPS signals will also be described. Each SV supporting altBOC now has 20460 samples per millisecond, I and Q for each A and B sideband. With E5 (a 1PPM oscillator) and obtaining auxiliary information, it is hoped to cover 1PPM = 1191Hz, e.g. 1200Hz oscillator frequency uncertainty. Due to modern signal re-decoding on both data and pilot channels, in one embodiment only non-coherent integration is used with coarse timing. A longer coherent integration will observe phase reversals that cancel the integrated energy for more than one millisecond. For a 1 millisecond integration, a frequency step of 500 Hz will result in a 2dB sinX/X loss. In addition, the codes on the A-band and B-band are not aligned by 116.5 carrier cycles per chip after shifting to low IF. Therefore, this misalignment should be corrected for long-term correlation. Typically, the integration time is limited by the time it takes to integrate 1/2 time/frequency search units, where the frequency error is half the frequency search step size. Integrating longer than this means that energy is dragged from one code search grid to the next, limiting the integration effectiveness. Code ambiguity = carrier frequency error/carrier cycles per chip/cells per chip * dt (seconds) Solving for the frequency error required to recover a certain number of dB for a given dt and limiting smear to ½ cell gives 250 ms, Frequency error = ½ *carrier cycles per chip/20460 cells/10230 chips/dt = ½*116.5*10230/20460/0.25 = 116.5Hz [Note: math reworked to old 16384 assumption using 20460 cells] The frequency step size is then programmed to be twice the frequency error, so the frequency step size is about 233 Hz. To cover +/-1PPM = 1191*2 = 2383Hz with a step size of ~233 Hz, about 10 bins are needed. For the purpose of this example, the frequency uncertainties associated with unknown user motion, user position, or user clock are assumed to be negligible. Note: The term mixer is used to denote a channel that effectively performs a time domain correlation of the input signal, with up to four codes per modern satellite being searched. The correlation is performed using FFT. Correlation = inverse FFT (complex conjugate of sample FFT * code FFT). The amplitudes of each correlation hypothesis are integrated in the hypothesis memory. These are mixed to cover the entire frequency uncertainty range. To search all SVs in the field of view in 1 second means ~24*10 frequencies, each with an integration time of 0.25 seconds. This would require 60 discrete mixers. This number is considered too high for at least some embodiments. Therefore, in one embodiment the integration time can be reduced to 0.1 seconds. This requires only 24 mixers. However, each mixer must mix each of the four components of the E5 signal. This means that 96 FFTs are performed in parallel in one embodiment. Each FFT must nominally have 20480 (cells) * 16 bits (I or Q word size) * 2 (for each I, Q) = 0.625 million bits. Multiply by 96 to get 60 million bits = 7.5 million bytes. In addition to the FFT memory, each mixer requires a memory to integrate the incoherent or coherent code hypothesis memory. In one embodiment, a very compact representation of one of 8 bits/cell is assumed. In one embodiment, this requires a method to shift out the linearly increasing noise floor average associated with the incoherent integration of the amplitude every millisecond. Conveniently, the power integration of all 4 codes for the 20460 cell hypothesis at each mixer can be integrated into the same memory to perform the incoherent integration. Therefore each mixer requires 20460 bytes, and a total assumed memory would be: Assumed Memory = 20460 cells/mixer * 24 mixers * 8 bits/cell = 3.74 million bytes = 0.468 million bytes. In one embodiment, which will be referred to as a double buffer, sampled data is copied to each mixer every millisecond and processed in two stages, as shown below Top Timing Image In another embodiment, a loop buffer can be used to reduce the signal buffer memory by nearly a factor of two. However, substantially faster signal processing will be required than can be accomplished in just 1MS. The preferred embodiment of the present invention utilizes FFT to perform the correlation, where correlation = inverse FFT (complex conjugate of sample FFT * code FFT). The amplitude of each correlation hypothesis is integrated in the hypothesis memory. In stage 1 of the first embodiment described above, the FFT of the samples is calculated. These FFTs can be used in all mixers. Power can be saved in stage 1 because a reduced number of FFTs are being run at this time. In practice, the channel is inactive in Phase 1, although some of the channel's FFT resources are borrowed to generate the sample FFT. Typically 8 FFTs are performed in Phase 1: one for each of the 0Hz, 250Hz, 500Hz, and 750Hz carrier-erased versions of the input samples for both Channel A and Channel B. In Phase 2, the sample FFT (FFT of the received GNSS sample data) is complex multiplied with the code FFFT (FFT of the locally generated GNSS SV PRN code) and then an inverse FFT (IFFT) is performed. The IFFT is actually equivalent to an FFT. The code FFT is either temporarily calculated during the setup cycle, or pre-calculated and stored in non-volatile RAM or ROM. To minimize computation, the following improvements may be used in some embodiments. 1) Carrier erase is first performed on samples at three ramping frequencies of 250 Hz, 500 Hz, and 750 Hz to generate 4 sets of samples including the original sample at 0 Hz. FFT is then performed on this sequence of 4 samples to generate 4 FFTs. In stage 2, when a specific Doppler must be applied to the sample sequence to erase the Doppler, an FFT trick is applied. That is, another ramping frequency shift of +/-N*1 kHz is obtained by shifting the FFT by +/-N grids. For example, to achieve a search frequency of 4321 Hz, two ramping frequency methods are combined to approximate the total desired Doppler. The 250 Hz FFT is selected first because it is closest to the sub-kHz part. This FFT is then shifted by 4 bins to get a total shift of 4250 Hz. A negative frequency of -4321 will be constructed using a 750 Hz shift of -5 bins: -5000+750=-4250. Thus, in stage 1, all mixers do not need to compute the FFT of a particular Doppler at the frequency mix. Since the number of mixers is high, this reduces the total number of FFTs by almost half. a. In another approach, the FFTs of 250 Hz and 750 Hz Doppler are interpolated from the FFTs of 0 Hz and 500 Hz. 2) Precompute the code FFTs before the long integration or from memory. Such codes can be used throughout the long incoherent integration procedure. The code is generated by starting with a zero code phase offset. A divisor is generated to produce 10230 code clocks in 20360 sample clocks. The sample code remains constant between changes in the code clock. To cancel a code Doppler rate equal to the carrier Doppler divided by 116.5 cycles (when sideband A and sideband B are shifted to center at 1191.795 Hz), there are several options: a. The simplest is a code cell integrator that is related to the number of chips moved multiplied by the ratio of the number of code hypotheses to chips per millisecond. (For example, 20460/10230=2). This way, the target hypothesis memory address is shifted every millisecond according to the rate integration. For example, if the Doppler is 4321Hz, the number of cells in 100ms is (4321/116.5)*(20460/10230)*0.1 = 7.418 cells. This means that the offset between correlation and integration for one millisecond will vary from zero to almost 7.5 cells, evenly distributed over 100ms. In addition, the same code zero-phase FFT is used each time. b. The worst case is to re-do the 20360 code sequence every millisecond, where the starting code phase of the 20360 to 10230 code clock divider has a steadily increasing phase. Then update the code FFT every millisecond. c. Another relatively simple method is to use another FFT property, where a time shift T in the time domain is equivalent to subtracting a zero-phase FFT from the complex exponential e^(-jwT) Multiply by , where w is the frequency at each grid and T is the time shift converted to chips per second by dividing by the number of chips per second. This complex multiplication can be reduced to a multiplication step of the complex conjugate of the sample FFT by the code FFT. d. Another approach is to use the fractional code offsets of the first approach to interpolate adjacent amplitudes to cancel out the code offsets between code offset times that change by integer values. Even with these improvements, the number of clocks required to implement a 16384 or 20480 sample FFT is still high. Even with dual-port memory, an efficient implementation may still require about 115,000 clocks, which is more than the approximately 100,000 clocks in 1 millisecond for a 100 MHz original sampling clock. Without acceleration, this means 96 FFTs need to be run in parallel, and the memory required is huge and may be unmanageable for COVIMOGR. In general, the instruction is lowered by the number of clocks per stage multiplied by the number of stages. For a radix-N FFT, the number of clocks per stage is the sample size divided by N. The number of stages is the logarithm of the sample size to the base N. For example, for radix 2 and sample size 16384, the clocks per stage is 8192 and the number of stages is 14. Therefore, the minimum clock is 14*8182 = 114666. For radix 4, the number of clocks per stage is 4096 and the number of stages is 7, for a total of 28672. This lower bound also assumes that the radix operation itself (including multiplying a complex combination of memory elements by a set of complex rotation factors) can be cascaded into a single instruction. This is a reasonable assumption, since integrated circuits can perform several operations in a single clock cycle due to the speed of transistors and the predictability of propagation at certain voltages and clock rates. Therefore, increasing the radix can reduce the clock cycle. However, the limitation is the ability of the memory addressing circuitry to fetch and write. For a fairly common dual-port memory, a radix-4 implementation cannot fetch 4 complex elements in parallel, but rather takes 4 clock cycles. In a sense, the advantage of higher radix is lost. To achieve an implementable design where only modernized acquisition of the modernized signal is competitive with previous acquisition methods, some embodiments may use the following breakthroughs: 1) Implementation of FFT-based methods is memory intensive, a. Consideration should be given to the ability to use system memory rather than dedicated memory. In this way, memory is no longer a sunk cost because it can be allocated for acquisition and then reused for other purposes when acquisition is complete or when the GNSS receiver is not in operation. Therefore, a memory is shared between a GNSS processing system and another system that may be located on the same integrated circuit (IC) so that the shared memory and the GNSS receiver and the other system are all located on the same IC, which may be a system-on-chip (SOC). b. Consideration should be given to methods of efficiently pipeline processing FFT data to reduce memory usage. This embodiment is described below in the Very Fast Frequency Domain Correlation (VFFDC) section. 2) In one embodiment, recognizing that a high number of effective FFTs are required to achieve a fast acquisition in a mass market GNSS receiver with high system loss (due to high NF, high antenna loss, signal fading or blocking), a fast FFT engine may be reused many times in a millisecond, and general system memory may be used so that only a low number of physical FFT engines are used, thereby minimizing the need for memory. This fast FFT is restructured from a general FFT architecture so that the FFT can be further parallelized and each parallel sub-FFT can be updated using its own memory. a. Alternatively, a custom memory design can be used that can extract a high number of words in parallel. This way, several radixes can be performed in parallel. For example, assume that 32 sets of I,Q can be extracted in a single clock cycle. This allows the 8 radix-4 calculations to be parallelized. In this way, the clock per stage is divided by 8. So in total, 20460 FFTs can be performed in 4096 (clocks/stage)/8 (parallel radix-4)*7 (stages) = 3584 clocks. With a system clock of 100Mhz, there are 100,000 clocks per millisecond, and this allows the FFT to be reused 27 times in one millisecond. If a mixer requires 88 FFTs, only 4 physical FFTs will be needed. Note that this low clock rate allows for a low power system since the maximum memory and DSP clocks are quite low by today's standards. b. Alternatively, a higher clock can be used. A 4x higher clock will result in a reduction to a single FFT. This comes with the disadvantage of mixing clocking rates in the design and thus adding the extra burden of buffering and staging. c. Finally, a pipelined VFFDC design can be used (which is the preferred embodiment) which minimizes the need for replication and maximizes parallel operations at each stage. 3) Although FFT memory can be reduced and reused, the rest of the assumption memory dominates the rest of the design. a. Although the full E5 signal is more than 6dB stronger than the previous L1 CA signal, non-coherent integration is the most effective way to improve SNR without resorting to multiple assumptions about secondary decoding and data bits, which generate random phase reversals every millisecond. In contrast, L1 C/A has similar random phase reversals due to data bits, but the intervals are significantly longer (20 milliseconds). This feature is a feature that achieves a faster SNR improvement by coherent integration of L1 C/A. For some mass market devices, simply integrating the signal incoherently is not enough because it is not practical to integrate long enough. i. Consider a target device that needs to improve SNR by 16dB to overcome system impairments. 1. Using E5, the 4 components of the combined signal: A-data (Ai), A-pilot (Aq), B-data (Bi) and B-pilot (Bq) are almost 6.5dB stronger than L1 C/A in 1ms. Integrating non-coherently over 100ms with a 1ms integration yields (over 1MS C/A) a gain of 6.5dB + 1.5dB*log(100,base2) = 6.5+(1.5*6.64)=10dB + 6.5=16.5dB. Taking into account some phase reversals in the 1ms sample buffer which are a loss of about 1dB, this gives a gain of 16.5dB-1dB = 15.5dB over the 1ms GPS L1-C/A. [(There is some loss associated with σ phase and <2dB phase reversals within the 1ms sample buffer)]. Combining means maintaining a separate sample buffer for the A and B sidebands, since adding them together would double the noise and erase the 3dB gain associated with each sideband. This calculation does not take into account the benefit of transmit diversity provided by dual sideband signals. In typical Rayleigh fading environments found indoors and in urban canyons, this transmit diversity can improve fading resistance by approximately 10dB or more, especially for the direct signal path, making signal acquisition, tracking, and reading of the navigation data symbol stream substantially more reliable. 2. For L1 C/A, general case acquisition using coarse timing means the longest coherence interval is close to 10ms (which is half the 20ms data bit interval). In this case, a 10ms sample will completely avoid phase reversal, while the adjacent 10ms sample may have phase alignment almost lost in the worst case. a. With 10ms coherence, now reduce the frequency step size to almost 50Hz. To reduce the frequency loss to the same level as described for the E5 method, use 25Hz steps. This means that the number of frequencies required to cover the same +/-1PPM is 2 *1575/25 + 1 = 127 per SV. Note that E5 only needs 9 (the difference is 10 times the integration time, i.e. 10 = 10ms/1ms and there is a factor of 1.3 = 1575/1192, which makes E5 lower frequency). b. To achieve the same sensitivity of 16dB after impairments, the sensitivity gain model for the L1 C/A search with a 10ms coherence window is 10dB for the first 10ms, then the sensitivity increases by 1.5 for each doubling with non-coherent integration of these 10ms integrations. Keeping the integration time at 100ms means that the integration time will double to 20, 40, 80, and then 20/160 = .125. The number of doublings is 5.56, and the non-coherent gain is 1.5 * 3.125 = 4.69dB, so the total SNR gain is 10dB + 4.49 – 1.5dB (average loss of 2dB for phase reversal loss in one of the 10ms windows) = 13.2 dB, similar to but less than the E5 case. c. This shows that the perception that L1 C/A is more sensitive to coherent integration is incorrect, as simpler non-coherent methods and acquiring the entire signal can have the same or better sensitivity. d. Now let's examine the size of the assumed memory and how it compares between E5 and L1 C/A. With E5, there are 24 channels running in parallel. Therefore, the size of the assumed memory at two samples per chip is 20*20460*8 bits = 3.12M bits. Note that all 4 components of E5 fit into the same assumed memory, since they all have the same code phase assumption. i.  Note: As the signal travels through space, there is phase dispersion between sideband A and sideband B due to the fact that the number of carrier cycles per chip is different (115 cycles at A, 118 cycles at B, and 116.5 cycles at the center corresponding to 1191.795MHz). The relative phase difference of the code chips is 1. delChips = codeDoppler B – codeDoppler A = (Satellite Doppler) *dt * [1/115 – 1/118] = Doppler * dt * (118 – 115) / (115*118) = 3*Doppler*dt / 13570. Note that there is also a small relative ionospheric dispersion, which is about one carrier cycle. 2. Since the travel time averages about 80 ms and the maximum Doppler due to satellite motion is 5kHz, the delta chip is: delChips = 3*5000*0.08/13570=0.088 chips 3. Therefore, when A has a codeDoppler greater than B, assuming a code mapping in memory from 1 ms amplitude to sum of amplitudes, a special offset of 14 cells is imposed on the A channel (assuming 16384 cells per 10230 chips). 4. Since both sidebands are shifted to the center, they have the same code rate in dt, which represents the processing time. 5. Note: If the oscillator offset is very high, the Doppler can be larger. In this case, the difference between the two sidebands in the travel time is larger and needs to be compensated. a. One solution is to compensate the oscillator in HW. Maintain a SW table where the offset the receiver is learning is fixed over temperature and can measure the error in velocity fix, just like how the time offset is learned in position fix. In this case, the frequency offset can be removed using a hardware based frequency shift to remove the frequency error from the sample data. This way only the satellite Doppler is observable in the code Doppler difference between the two sidebands. 6. Note: If the two sidebands are generated using separate IFs, the code Doppler difference is not common for time integration for SNR improvement. In this case, compensation for the code Doppler difference is required. ii. Now to the assumed memory for L1 C/A: If the same search power is achieved, this means 127 frequencies per SV, and with the same 24 satellites in one second, this means 3048 frequencies per second. Assuming each frequency is also searched for 100 milliseconds, this means 305 concurrent frequencies are being searched. Assume typical sampling is close to twice the chip rate, and therefore about 2046 samples per millisecond. Therefore, the assumed total is 2046*305, and 8 bits = 4.875 million bits, which is actually higher than the E5 case. This number can be reduced in several ways. First consider the same code cell to chip ratio. This puts the sample clock at 1.6384 MHz instead of 2.046 Mhz. This reduces the assumed memory to 3.904 million bits, which is still large. The next step is to reduce the frequency step size from 25Hz to 50Hz, and accept another 1.5dB frequency step loss to 13.2-1.5 = 11.7dB. This cuts the memory in half. Using the original 2.046Mhz sampling clock at 50Hz yields half the frequency and therefore 2.4375 million bits, which is now a bit less than the E5's 2.816 million bits, and the L1 C/A is almost 5dB less sensitive. (16.5-11.7=4.8dB). This does not take into account the additional advantage of Galileo signal transmit diversity, resulting in signals acquired using E5 A+B being substantially more resistant to fading. If this improvement is conservatively estimated to be 6dB, COVIMOGR has at least an 11dB advantage over L1 coarse acquisition code in coarse acquisition mode. The advantage of COVIMOGR is extended in the precise time acquisition mode, where coherent integration further improves modern signal tracking sensitivity. iii.     This example shows that even in the coarse time acquisition case, the E5 with its very efficient FFT engine can have higher sensitivity than a L1 C/A based receiver with similar assumed memory. Preferred Embodiment – VFFDC   Coarse Time Acquisition Processing Timeline Accurate time to obtain processing timeline The pipeline-oriented architecture illustrated in the figure above enables significantly faster FFT throughput and reduced memory usage in both working memory and signal memory, making the hypothetical memory the single largest memory usage. In reality, the flow will differ slightly between coarse-time mode and fine-time acquisition mode, as illustrated in the figure above. The VFFDC performance speedup and memory reduction compared to typical FFT techniques comes from a combination of proper staging, attention to memory management details, and application of recent "decimation in time" (DIT) FFT and "decimation in frequency" (DIF) FFT. The figure below shows a high-level view of the Very Fast Frequency Domain Correlator (VFFDC) architecture. Several of the blocks in this diagram will be described in more detail. Very Fast Frequency Domain Correlator (VFFDC) Architecture Diagram FFT processor architecture (four parallel IVFFT operations) Inverse FFT processor architecture (four parallel IVFFT operations) The following diagram provides a detailed end-to-end timeline view of the Get Correlator process. Get Correlator Array Processing Diagram VFFDC process The following figure further illustrates the GNSS code generator. The preferred embodiment generates each code from its underlying polynomial representation, shifts and shapes it appropriately, and then transforms it to the frequency domain every millisecond. However, there are several possible implementations that can achieve many of the memory reduction goals without completely regenerating the code spectrum every millisecond. For example, the time domain codes may be generated only once per tracking session. In another example, the code spectrum memory may be stored and slightly adjusted as needed. In another embodiment, such caching methods may be used when storage resources are available, but not otherwise necessary. FFT processor architecture (four parallel FFT operations) Note: To generate the code spectrum, four GNSS code generators are used to replace the baseband sample memory. VFFT N2×N1 program flow Inverse FFT processor architecture Note: During the detailed design process, the interconnect network and the algorithms mapped to the hardware and the instruction set definition for each block will be defined simultaneously. Inverse VFFT N2×N1 Algorithm Note that in this embodiment, the FFT is performed temporarily on both signal data and code data in two working memory buffers that are reused by all mixers. The signal data is stored in a loop buffer that lasts longer than 1 ms so that the FFT process can be performed before the buffer's write pointer catches up with the FFT's read pointer, thereby saving almost twice the baseband sample memory over the previously described dual buffer embodiment. In addition, in this embodiment, the GNSS codes are generated temporarily, thus saving about 100 times on the pre-stored GNSS code spectrum memory. These 10,230 bit codes can be stored compactly in the time domain as 10,230 bits, but once converted to the frequency domain, their size expands to encompass a complex non-binary representation. Note that there are actually four codes per SV. Some of these codes can be stored simply, but they are most simply stored as their polynomial representation. This is therefore the preferred embodiment for memory efficiency considerations. Although each code required to transform per millisecond essentially increases the FFT processing workload by a factor of two (only the in-phase branch of the code spectrum goes through the first stage of FFT processing), it is worth doing so in this embodiment to reduce inherent memory and I/O. Further gain is generated when the DIF conjugate FFT is used for the inverse FFT, so that the inverse DIF process is performed in column order (time domain data is stored in column order and frequency domain data is stored in row order) using the same buffer that stores the results of the multiplication process. Note that according to the Nyquist criterion, it is proposed to perform these FFTs for N = 20,460 samples, which breaks down into a set of N1 = 20 first-stage DFTs. (10 or 40 could also be used for N1. The choice of 20 was a design decision.) This leaves the next stage of the N2 = 1024-point DIT/DIF FFT, which can be implemented at high speed in another three stages using integer arithmetic (two radix 8 and one final radix 16). Because of the pipelined nature of this processing, it can easily be done in 50 microseconds for all SVs in view at a 100 MHz band with a processing clock just slightly faster than the sampling clock, which means that the loop buffer only needs to be about 1.05 milliseconds long (21483 samples, stored as 4 bits of I and 4 bits of q), saving power and most importantly, on-chip RAM. VFFT Details of One Embodiment  a. Decompose an N-point DFT into an N₁ Point DFT and N₂ Point N₁ Parallel FFTs  i. The total number of FFT points is N = N₁ *N₂ , where N₁ ＜＜ N₂ ii. By decomposing the FFT processing into N₂ N of points₁ The N-point VFFT-DIT algorithm architecture is optimized for speed by performing N parallel FFTs followed by a combination of N1-point DFTs.₁ Parallel FFTs to speed up FFT processing time by N₁ times.   iii. By decomposing the FFT processing into N₁ The first stage of the point DFT, followed by N₂ Point N₁ Parallel FFTs can be used to optimize the speed of the N-point VFFT-DIF algorithm architecture. Using array processing methods to execute N₁ Parallel FFTs to speed up FFT processing time by up to N₁ times.   iv. An inverse VFFT-DIF operation can be performed by conjugating the input array before the VFFT and conjugating the output array after the VFFT.   b. Use array processing methods to process N₁ parallel FFTs. All FFTs perform the same processing, using the same program control instructions but using a different data set (a vector) from the array.   c. A DFT can be performed on any number of points in the repack/depack phase.   N FFTs can be used in one instruction loop₁ N parallel constant cross multipliers and adders are used to perform this DFT. Therefore, N₂ cycles to complete the first/last phase of the VFFT.   d. Use 3 phases to implement N₂ point FFT where radix-8 in 2 stages and radix-16 in first/last stage.   i. Radix-16 stage does not require W_N Phase shift, which reduces complexity and evens out the time of pre/post VFFT operations.   ii. Phase shift factor is only required for radix-8 levels. Since the firmware selects only 1 element from memory per instruction cycle,₂ Point FFT requires only one phase shifter hardware. Since there are N₁ There are N parallel FFTs being calculated, so N hardware is required₁ phase shifters and all share the same phase shift amount.   iii.     Each stage of FFT needs to complete N₂ cycles, so 3 stages need to complete 3*N₂ cycles.   iv. The processing rate on each stage is limited by the read and write accesses to the dual-port variable memory. Each processing cycle includes a read and write access, which allows firmware cycles of 8 or 16 instructions for the radix-8 stage or radix-16 stage, respectively. This design utilizes almost 100% of the available read and write memory bandwidth and is therefore likely to be the most efficient given the actual hardware limitations.   v. Dual-port memory is typically available in ASIC libraries, but higher-port memory is not. Therefore, for design portability, this embodiment uses single-port and dual-port memories, and does not currently require byte access capabilities (which are not always supported in every ASIC library). e. Associative post-processing operations are performed on the fly, without storage, and may be pipelined in a few extra processing cycles, but there are no extra cycles within the firmware loop. These operations are performed on the full column vector in 1 instruction cycle. f. Variant memory may reduce precision at the end of the VFFT. The associative post-processing operations can then be performed at higher precision in the processor's registers. The results can be reduced back to lower precision before being stored in hypothetical memory. Therefore, variable memory does not need to be high precision (the target is 8-bit/I/Q-component). g. Block floating point may be used for the integral value to reduce the accuracy to unsigned 8 bits. Magnitude compression may also include subtracting the minimum value in the block before applying the block floating point conversion. h. In at least some embodiments, Cordic-based phase shifters may be used throughout the design instead of complex multipliers and sin/cos tables. i. Cordic hardware is approximately 1/4 the area (cost) of a complex multiplier, and the accuracy of a Cordic phase table is typically lower than that of a sin/cos table. ii. The Cordic algorithm produces several small phase modulation spurs (PM) near the noise floor, rather than using 1 or 2 major amplitude modulation harmonic spurs (AM) as with the quantized sin/cos table approach. The spurious-free dynamic range of Cordic is greatly increased, which allows for reduced signal accuracy but the same performance.   iii.     The only drawback of Cordic hardware is the long propagation delays through the serial stages. Due to the conditional logic within each stage, the arithmetic logic cannot be optimized across the stages. Excessive delays that exceed the timing budget may need to be handled by register pipeline stages, and any additional group delays must be incorporated into the signal processing algorithm.   It should be noted that although the description of this design assumes that the data is read in column order to optimize addressing, the data can easily be read in row order with similar results.   Lower power for stronger signals is achieved through reduced complexity correlators. Although using two components of the two sidebands of E5 allows for an SNR increase of up to 6dB compared to a single sideband component (I or Q), in some cases it is better to use a lower power configuration that is able to obtain a stronger signal in a reasonable amount of time. In another case, the receiver may need to read some information from a navigation message that is only available from a subset of the signal components. This information could be, for example, a week timestamp or a specific phase change interpreted as a timestamp of fractional synchronization. Or it could be integrity information. For example, it could be calendar or almanac information or differential correction information. In situations where a piece of information needs to be read to speed up further acquisition and tracking, those signals that are likely to provide this information the fastest are prioritized. Consider the following acquisition scenario: When a receiver is turned on while inside a parking garage, all signals are blocked. The receiver has no knowledge of the garage and will likely initiate a search strategy based on the very weak signals. This strategy requires integrating all components of the signal for a longer time and provides maximum sensitivity. While this method is good for acquiring weak signals, when the receiver eventually leaves the garage, it is slower to recover stronger signals because it spends more time on each search frequency. In such cases, it may be beneficial to have a second parallel search engine, or to allocate some search resources to look for stronger signals using a shorter integration period so that each frequency band can be searched faster, allowing the receiver to cover more frequencies in a shorter period of time. In addition, consider the unknown one of time acquisition. Typical Network Time Protocol (NTP) accuracy on the Internet is in the range of about 5 ms to 100 ms. In some cases, frame synchronization of only a selected GNSS signal component may provide precise time. In such a case, searching for that signal component will be the highest initial priority until the signal is tracked and the clock is confidently set. Once the clock is confidently set, the signal may be de-prioritized in favor of a signal component that contains less data and therefore has higher tracking sensitivity. A flexible association method can be used to acquire strong signals as quickly as possible. First, the association resources can be configurable so that a channel can search from one to four signal components. If a single channel cannot release unused resources, the resources will be idle and the acquisition time will be extended. For example, if a channel is configured to be able to search four components and only a single component is used, the other three resources will not be available. Therefore, the first part of this embodiment is to identify the association of the basic search unit as a signal component, such as E5BI. For frequency domain methods this means performing an FFT of the samples, an FFT of the code, a multiplication of the sample spectrum with the complex conjugate of the code spectrum, and an IFFT of the product. The total number of correlations is the number of times the VFFDC resources can be reused in the code frame length (nominally 1MS). The channel concept then includes the ability to choose from one to four components to match the E5 and B2 signals which have four components. In this case, the number of channels should match the hardware's ability to perform the number of correlations in one frame (1ms in this case). For example, if there is the ability to perform 88 full correlations in one ms, the maximum number of channels should be 88 when only one component is used per channel. For example, if only 22 channels are defined with up to 4 components, then only a single component is used and 3 components are idle. The second part of one of the embodiments is to select the component with the minimum search loss. In the case of a modern signal with a frame length of 1 millisecond and a 4 to 100 millisecond overlapping code or sub-code whose bit changes are synchronized with the frame, each frame can have a positive or negative sign change from 1 to -1 or from -1 to 1. Generally speaking, these overlapping codes form phase reversals at a rate close to 50%. On two consecutive frames where no phase reversal occurs, when the frame point or time period or the frame restarts, the process of performing a one millisecond period of non-coherent integration synchronized with the phase of a random millisecond input sample is lossless. In contrast, if the frame period is located at the center of a millisecond and a phase reversal occurs, cancellation will occur, resulting in a very small correlation for that millisecond. Using FFT-based correlation, it is not possible to split the millisecond correlation into two parts, the part before the potential phase reversal period element and the part after the period. The receiver operates on a full millisecond of received signals with an arbitrarily selected start time. At this stage of the acquisition process, each satellite signal has a significantly different and unknown phase. This is because the millisecond samples are correlated with a full millisecond code sample starting at zero phase, and it is not possible to apply a separation based on the other phases. In contrast, using traditional time domain correlation methods, a different combination of input samples can be selected for different code phase estimates so that the period occurs at the edge of the millisecond buffer. This way, during integration, the in-phase and quadratic sums have the same phase. However, for modern signals, this approach of correlating each code phase hypothesis individually is not commercially viable because it either requires too much hardware, increasing power consumption and size, or is too slow to reduce hardware. Therefore, the price of the incoherent integration of a millisecond correlation is that there is a loss in the millisecond sample associated with the time segment phase. The loss is small when the phase is close to the edge of the millisecond or the overlapping code has no phase reversal. The loss is higher when the phase is close to the center of the millisecond and a phase reversal occurs. In the latter case, the loss is effectively infinite. In the former case, the loss is small. In general, the worst case loss is less than 3dB when integrated over the duration of the overlay code, since with a probability of about 50% for a phase reversal, half of the correlations are lost, but the remaining correlations have no such phase loss. Losing half the power means losing 3dB. It has been found that data channel E5BI has an overlay code of 0001. The subcode is repeated every 4 frames of 4 milliseconds. The data symbols form additional phase reversals at the boundaries of the overlay code. Therefore, consider a 5-bit alternating data symbol sequence 0, 1, 0, 1, 0. The combination of the overlay code and the data symbols will generate the following overlay code phase sequence, where 0 represents phase 0 and 1 represents phase 180 degrees. 0001 1110 0001 1110 0001 Now focus on the phase reversals, the derivative of the sequence: 0001 0001 0001 0001 0001 There are only 5 phase reversals over 20 symbols, so the probability of a phase reversal is 25%. In contrast, consider the data channel B2AI on BeiDou. Its overlay code is 00010. Or perhaps a diagram is provided where the phase transitions are specified by 00010]. Now consider the same 5 data bits 01010. The resulting combination of overlapping code and data symbols generates this sequence: 00010 11101 00010 11101 00010 Now look at the phase reversals, i.e. the derivative 00011 10011 10011 10011 10011 There are 15 phase reversals in 25 bits. The probability of this change is 15/25 = 60%. Therefore, the maximum loss in dB for B2AI is 3dB & 0.6 = 1.8dB, whereas, the maximum loss in dB for E5BI is 3db * 0.25 = 0.75dB, which limits the loss to 1.05dB by comparison. Therefore, to improve the actual acquisition time with a fixed amount of search resources, one embodiment may implement a single component search (searching only the single component by trying to acquire only the single component at a time) and select the component with the lowest phase reversal probability on each system. For Galileo E5, the best component is E5BI.Shared Memory COVIMOGR = Commercially Viable Modern GNSS Only Receiver Another approach that can be used to implement a Commercially Viable Modern GNSS Only Receiver (COVIMOGR) is to reduce dedicated memory by reusing system memory. Consider the case of integrating COVIMOGR in a System-on-Chip (SOC) where large SRAM and DRAM are already available along with other processing systems. The COVIMOGR SOC components include but are not limited to Digital Front End (DFE), Acquisition Engine (AE) using frequency domain correlation, Tracking Engine (TE) using time domain, Reacquisition Engine (RE) using time domain, and minimal CPU/RAM/ROM required to control AE, TE, RE. The amount of memory required for the AE depends on its efficiency relative to the frame period, which is typically 1 ms for modern signals in the L5 band: for example, if 88 full frequencies (mixers) are required and if the correlation engine requires 4500 clock cycles, and 108000 clock cycles are available per millisecond, then each correlation engine can be used 24 times per millisecond. This means that at least 4 correlation engines are needed in the AE. In this case, memory for 4 engines is needed. Generally speaking, this memory must be dedicated to the AE, as it must be available every clock cycle and is slowed down by any memory arbitration. The SOC architecture may include the following items: 1. A set of application processors (APs), such as four. These are typically of variable speed. 2. A general purpose IO, input and output interfaces to off-chip systems, and IO for on-chip communication. 3. A hardware abstraction layer that contains hardware controls, operating system (OS), and arbitrated communication buses so that all blocks can be configured and communicate through the OS. This block contains its own CPU or runs on an AP in the system 4. A set of functions that are placed on the SOC and each of these functions can be implemented by a processing system that includes a local processing memory that can be shared with a GNSS processing system. 5. A GNSS processing system (e.g., COVIMOGR), which is itself another function. It can have an acquisition engine, a tracking engine, a re-acquisition engine, a digital front end, a minimal CPU, a minimal SRAM, and a minimal NV-ROM. 6. A large SRAM block which is available to the system via the communication bus and also used for one or more other functions, in this case it is connected to the COVIMOGR. 7. A DRAM which is a general purpose non-volatile memory. Consider the system on a chip (SOC) shown below. It can be a single monolithic die or a system of multiple dies. Here consider that all components except the DRAM are on the same die and the DRAM is a second die connected via the communication bus. In order to reduce the size of the COVIMOGR and especially the size of the SRAM of the AE, a combination of dedicated memory in the AE and the SOC SRAM can be used. In a preferred embodiment, the hypothetical memory for non-coherent integration and/or coherent integration is shared with the SOC via a direct bus so that the COVIMOGR can address certain parts of the SOC SRAM without slowing down. 1. The AP gets a request from an application to determine a GNSS position. 2. The HAL identifies a setup portion of the SRAM and allocates it to the COVIMOGR. The allocated memory must have a read/write controller that can operate independently of the other memory slices to be able to be used by the AE but without frequent contention/arbitration. 3. When the GNSS receiver is active, COVIMOGR uses memory located in the AE. 4. The application requesting GNSS is terminated or idled 5. The OS signals the HAL to shut down GNSS. 6. The HAL notifies COVIMOGR to shut down. 7. The slice (e.g., page) of SRAM allocated to COVIMOGR is returned to the system. In this way, the total SRAM required by COVIMOGR can be reduced because the memory required in the AE is shared rather than dedicated to the AE for use only by the AE. To further reduce the memory in the AE, at least some of the memory in the AE or in the GNSS processing system can be shared with other processing systems on the SOC. Another option is when the GNSS code spectrum is stored in the SOC DRAM as a set of pre-calculated tables that are programmed into the DRAM when the system is updated. Another option is that a program on the AP or even COVIMOGR can calculate the codes and/or code spectrum in the background or even at the start of a GNSS session. For reference, the number of codes for L5 is 63, E5 is 50, and B2 is 63. QZSS contains 2 and EGNOS contains 2. This is 180 PRNs. However, L5 has two codes/PRNs, E5 has 4 codes/PRNs, and B2 has 4 codes/PRNs. Therefore, the total number of codes is 586. Each code is 10230 bits. Storing all the codes requires 5,994,780 bits, which is about 734k bytes. In the case where the code spectrum is stored as a real code, the storage depends on the sampling rate used by the AE. Since each component is searched independently, the code is real for each component. The DFT of this code is a symmetric complex conjugate. This means that the complex number pairs reflected near the midpoint of the DFT have the same real value, but are negative if they are imaginary values. The total value required after reading the memory is 2N, but N/2 is a symmetric complex conjugate. Therefore, N unique values are required, and the HW can construct all values from N unique values. It is assumed that the number of bits required is further reduced, while the loss is minimized. In a preferred embodiment, 8 bits or 1 byte are used to store the real part and 8 bits are used to store the imaginary part. For a sampling rate of 20,480,000 (at 10,230,000 chips per millisecond, with only two samples per chip), the number of bytes used to store all pre-computed code spectra is approximately twice the number of code bits. Therefore, 586 codes * 20480 bytes/code = 11,632,640 bytes = 11.360 Megabytes. This amount can be reduced in several ways: An application can periodically assess which codes are currently active in the well-behaved satellites in space. Then, a significant reduction in one of the stored codes or code spectra can be achieved. For example, there are more than 50 valid PRNs per satellite per system. However, there are typically no more than 30, and more likely only 24 allocated PRNs in the space at a time. This would allow the memory to be reduced by more than half. In another approach, the pre-calculated code spectrum is moved to a sector of SRAM when the GNSS is active, such that: 1. The AP gets a request from an application to determine a GNSS position. 2. The HAL identifies a setup portion of SRAM to store the code spectrum and allocates it to the COVIMOGR. The allocated memory must have a read/write controller that can operate independently of the other memory slices to be able to be used by the AE without frequent contention/arbitration. 3. The HAL copies the code into the SRAM allocated for the code spectrum and gives COVIMOGR the base address of the pre-calculated code spectrum as well as the system, PRN and components of each code. 4. When the GNSS receiver is active, COVIMOGR extracts the code spectrum from the AE and uses the code spectrum in the step of complex conjugation of the sample spectrum multiplied by the code spectrum. 5. The application requesting GNSS is terminated 6. The OS signals the HAL to turn off GNSS. 7. The HAL notifies COVIMOGR to shut down. 8. The SRAM slice allocated to COVIMOGR is returned to the system. In another embodiment, a background application running on the SOC AP is used to calculate the effective code spectrum based on the current PRN in space. 1. A background application periodically calculates the effective PRN for all systems and stores it in DRAM. 2. The AP gets a request from an application to determine a GNSS position. 3. The HAL identifies a set portion of the SRAM used to store the code spectrum and allocates that portion to the COVIMOGR. 4. The HAL copies the code to the SRAM allocated to the code spectrum and gives the COVIMOGR the base address of the pre-calculated code spectrum and the system, PRN and components of each code. 5. When the GNSS receiver is active the COVIMOGR extracts the code spectrum from the SRAM in the AE and uses it in the step of multiplying the sample spectrum by the complex conjugate of the code spectrum. 6. Application requesting GNSS terminates 7. OS signals HAL to shut down GNSS. 8. HAL notifies COVIMOGR to shut down. 9. Return the slice of SRAM allocated to COVIMOGR to the system. In one embodiment, one way to further reduce the cost of COVIMOGR is to compute as many GNSS functions as possible on the AP. The CPU/RAM/ROM allocated to COVIMOGR can be minimally configured to allow full control of the various HW engines/components: AE, TE, RE, DFE. These systems will need a reliable method to send control settings, request services, and read results. For example, the AE will have an interface to request a search for a specific PRN in the system. Results are available as fast as every millisecond. However, the system is designed to buffer its results internally to allow a lower interrupt rate, such as once per block in 20 milliseconds. The tracking engine can operate at a similar update rate: periodic writing and reading, approximately once per satellite every 20 milliseconds. In this embodiment, it is the job of COVIMOGR to service these interrupts, write the next update and then format the data and send it to the assigned AP. In one embodiment the process may be: 1. The AP gets a request from an application to determine a GNSS position. 2. The HAL identifies an AP to run COVIMOGR's high-level software. 3. The COVIMOGR's GNSS application code is copied from DRAM to an executable memory block, which may be SRAM. 4. HAL identifies other SRAM slices for AE 5. HAL identifies code spectrum and copies code spectrum to SRAM slice for AE 6. Application enables COVIMOGR and indicates memory information for AE. 7. Application informs COVIMOGR CPU which satellites to search for. 8. COVIMOGR controls AE to start searching. 9. COVIMOGR CPU services AE search results. 10. Found signal starts tracking TE. 11. Found signal lost in TE is retrieved in TE or RE based on the time since the last tracking. Recently lost confidential data is re-searched in RE. 12. COVIMOGR detects a confidence track and aggregates code and frequency information within a configurable measurement interval (e.g., one second) to enable accurate measurements to be sent to the COVIMOGR SW running on the AP. 13. COVIMOGR erases data bits to track data, buffers the data with a configurable buffer size of 50 to 100 bits, and then sends the data to the COVIMOGR SW running on the AP. 14. Accurate time is obtained from the decoded symbols that are converted into timestamps and ephemeris data. 15. Position/velocity clock offsets and drifts are determined by the COVIMOGR SW on the AP. 16. Refine the search data and update the observable PRNs and their expected code phases and frequencies. Send data to CPU on COVIMGR. 17. SW on COVIMOGR removes satellite from AE and changes to search in TE for a low power maintenance mode. 18. If COVIMOGR loses satellite due to signal blocking condition, reacquisition or initial acquisition is repeated to find satellite immediately after any blocking condition is removed. 19. Terminate application requesting GNSS 20. OS signals HAL to shut down GNSS. 21. HAL notifies COVIMOGR to shut down. 22. Return SRAM slice allocated to COVIMOGR to the system. It should be noted that in another embodiment to save power and SRAM, the COVIMOGR can also release a portion of the SOC SRAM back to the SOC if it is not required for continued operation after the initial acquisition and clock setting. In this case, if the signal is lost and the clock setting decreases by approximately 100 microseconds, the COVIMOGR can request to reacquire the required SRAM block, up to the full amount initially acquired. Carrier and Code Generation Options: In one embodiment, the following elements can be used to increase the sensitivity of a COVIMOGR 1. Combine all components of a modern signal in a way that achieves the best SNR. a. Sideband A and Sideband B should be processed from separate channels, not combined. It is tempting to try to combine the sidebands together to increase the FFT number of input samples. But consider a PRN on one sideband with a received SNR. If it is combined with another sideband, the SNR will drop by almost 3dB, thus losing the benefit of using all components. b. The data of a particular sideband can be correlated with the pilot channel from the same channel in two different ways: individually or coherently. Correlating separately means multiplying the real-valued (i.e. not composite) code with the in-phase and quadrature signal input components, and searching for the pilot and data codes in parallel in this way. Coherently correlating means multiplying the composite code with the data channel code in the real part and the pilot channel code in the imaginary part. However, due to the unknown relative phase of the pilot and data channels, a second hypothesis must be tested when the two codes are in different phases. This can be done by changing the sign of one of the components. There are actually four possibilities, but if the result of correlating a frame is squared, there are only two. In practice, either the strongest power (or amplitude) is chosen in each code hypothesis, or the two are added together. For stronger signals, the coherent method has some benefit, but it requires that both hypotheses be computed simultaneously and compared before integrating into the hypothesis memory. For weaker signals, the advantage is smaller because it is difficult to choose the correct hypothesis and the procedure increases noise by choosing a larger estimate. c. The coherent method is more expensive when the code is precomputed because coherent codes are not complex symmetric like real codes and therefore require double the storage. d. A preferred embodiment is to mix the data and pilot codes as real codes for two sidebands and combine them after squaring one frame. 2. Use coherent integration up to the frame length of the main code sequence and then integrate the power (or amplitude) non-coherently over multiple frames so that the SNR grows almost linearly under each code assumption. a. This procedure can use an accurate treatment of code conversion due to carrier frequency alignment, which will be referred to as code Doppler in this article. During propagation from the satellite to the receiver, the code Doppler is different for each sideband depending on the relationship between the carrier frequency and the chip rate. For the sidebands below 1176.45Mhz, there are 16 cycles per chip. For the sidebands above 1207.14Mhz, there are 118 cycles per chip. The preferred embodiment shifts each sideband to a common center frequency of 1191.795MHz. A Sideband A channel is found by shifting a baseband signal centered at this original center frequency by 15*1.023MHz of the BOC frequency = 14.345Mhz, applying a low filter, and then decimating to a bandwidth of approximately 20.48Mhz, which contains the main lobe of Sideband A. A Sideband B channel is found in a similar procedure, but shifted down 15.345Mhz. b. By shifting the sidebands to a common frequency, the individual codes switch relative to each other at a rate of 116.5 carrier cycles/chip. c. The effect of the code Doppler placed during transmission and during integration separately. An estimate of the transmission time (about 75 ms on average) (determined by calculating the true transmission time from the satellite to the known receiver position after fix) is multiplied by the code Doppler (which is the negative of the carrier Doppler divided by the carrier cycles/chip) to approximate the transmitted portion. There will be a difference in the arriving code phases of the two channels due to the different cycles/chip. However the effect is small and negligible when searching with large step sizes (e.g., ½ chip). With a Doppler of 5 kHz based on satellite motion and a transmission time of 80 ms, the worst case difference is about 0.08 chip. In many cases, a fairly accurate range estimate for each SV can be pre-computed based on an approximate receiver time and position, making this compensation more accurate. d. In the case of using 116.5 carrier cycles/chip for both sidebands, the code Doppler effect during the integration period can be calculated exactly as the Doppler estimate multiplied by the integration time. e. This compensation can be done in several ways: i. The code samples can be time shifted before the DFT so that the integrated amplitude at the start of the integration period corresponds to the code hypothesis. The shift is calculated as dt*carrierDoppler/116.5. The shift is decomposed into integer and fractional chips. This shift becomes the initial phase for the code generator, which generates a code estimate at a sample time of one millisecond for the input samples. This method is called the shifted code sample method. This method is only possible when the code spectrum is calculated every millisecond. ii. Generate code samples with an initial phase of zero, and then modify the code spectrum by multiplying the spectrum with a frequency-dependent complex sequence. This method uses the following property: the FFT of the time-shifted sequence is equal to the FFT of the unshifted sequence multiplied by a frequency-dependent complex exponential and an independent variable of e^(jwT), where w is the angular frequency at each element of the FFT and T is a fixed amount of time shift. This is called the modified zero-phase spectrum method. This method works well for both pre-computed and ad hoc calculated code spectra based on a zero initial phase code sequence. iii. Code Doppler shifts can be compensated after correlation. The correlation destination hypothesis generated at a zero initial phase code spectrum is shifted to compensate. A coarse method and a fine method can be used. 1. In the coarse method, the code Doppler shift of the chip is converted to a code hypothesis by multiplying the input samples in one millisecond divided by the code chips in one millisecond. For example, at a sample/second of 20480, a code shift of 1.5 chips is converted to a hypothesis shift of 1.5*20480/1020 = 3.0 cells. Therefore, the current correlation result at zero phase is added to the third code hypothesis when the carrier Doppler is negative, or the current correlation result is added to the final hypothesis minus 3 cells when the Doppler is positive. 2. In a refined method, the same method above is used to identify the integer code hypothesis offset. Fractional shifts are then used to scale two adjacent results of zero initial phase correlation. For example, if the fractional phase is 0.5 code chips, the correlation value added to the hypothesis memory under hypothesis zero is half the value of the zero initial phase correlation at cells 3 and 4. The other updates will be shifted equally. f. As a method to minimize the hypothesis memory, all components are integrated into a single memory. A simple shift (such as code Doppler applied to the correlation result) can be used to compensate for the offset between the sidebands that occurred during transmission before adding to the assumption memory. g. Since the two sidebands are shifted to a common center frequency, each sideband sees the code Doppler effect during integration. 3. Carrier Doppler is applied with minimum frequency offset. The scenario here is that the correlation will be performed using a frequency domain method using three DFT steps to generate Correlation = IFFT [FFTsamples*FFTcode’], where FFTsamples is the DFT of the input samples, FFTcode’ is the complex conjugate of the DFT of the code samples, and IFFT is the inverse DFT of the product of two FFTs. The IFFT is actually an FFT that is then divided by the number of samples in the IFFT. FFT stands for Fast Fourier Transform as an efficient method to implement Discrete Fourier Transform (DFT). The VFFDC method combines three FFTs in a way that exploits the symmetry of the FFT and IFFT processes by performing multiplication and complex conjugation. VFFDC can also cancel the effect of the sideband process on the individual carrier frequencies by processing the sidebands of the signal input samples or code samples, this effect is called carrier Doppler. Choose the total number of DFT operations that affect. a. The range of the received frequency deviation from the nominal for each satellite due to the motion of the satellite relative to the receiver is approximately +/- 5Khz plus the frequency offset of the oscillator. If the curve of a frequency offset of the oscillator versus temperature is known, a frequency shift can be applied to the input samples before correlation to eliminate most of its effects. However, even if the remaining satellite motion dependent frequency offsets can generally be pre-calculated, all satellites still do not have a common value and a specific range of values must be searched for each satellite based on the receiver time and position uncertainties. b. This satellite-specific Doppler can be handled in essentially one of two ways i. Remove the Doppler from the input samples using a frequency difference operation so that the resulting samples have a zero frequency offset. These modified samples are then correlated with code samples that also have a zero frequency offset. This method is called the Down-Shifted Input Sample Method (DISM). A down-frequency shift of the complex sequence A is performed by frequency source B using the triangulation function: sin(a-b) = sinA cosB - cosA sinB, and cos(a-b) = cosA cosB + sinA sinB, where A represents the frequency of the input samples and B represents the carrier frequency to be removed. sin and cos represent the imaginary part and the real part, respectively. a. This method requires a unique set of input samples for each frequency to be searched. This increases the number of FFTs by the number of unique frequencies. When two sideband components are used, two DFTs of the sideband input samples must be formed, which also doubles the number of FFTs. Some optimization can be performed here. i. Perform the DFT of the two sidebands with a set of discrete frequencies with equivalent step size and integration time. A longer integration time requires a smaller step size, while a shorter time allows a larger step size. For a longer integration time, set the step size where the maximum frequency error between two steps equals the Doppler error of half the sample clock. For example, if the integration time is 100 ms to get the desired SNR to achieve a weak signal improvement of 10 dB, the frequency error of a sample clock of 20480000 is ½ = df / 116.5 * 0.1 * 20480 / 10230. Df = 0.5*116.5 / 0.1 * 10230/20480 = 291 Hz. Therefore, the search step size can be twice this amount since the maximum error between a step of 582 Hz is 291 Hz. For a short integration time, the step size is chosen to minimize the loss associated with the sinX/X error of the maximum frequency error between two steps. For a 1 ms integration, sinX/X is 0.63 at a loss of 4 dB at X=500 Hz and 0.9 at a loss of 0.9 dB at X=250 Hz. ii. To reduce the number of sample FFTs, a set of down-converted input samples is generated with a frequency step size related to the integration time. 1. For a 10 ms integration time for fast searches for strong satellites, sinX/X sets the step size. In this case, two frequencies of 0 and 500 Hz are chosen to limit the frequency error to 250 Hz. There are then 4 sample FFTs: 2 for A and 2 for B. For example, if a channel requires a Doppler of 2200 Hz, an FFT of 0 Hz is chosen and the resulting FFT is shifted by 2 grids to generate a frequency shift of 2 kHz. The frequency error is limited to 200 Hz, which has a loss of less than 0.9 dB. This is because a 1 ms integration has an impairment at 0 Hz, 200 Hz, 400 Hz, 600 Hz and 800 Hz. 2. For an integration time of 250 ms which yields 11.5 dB, the df of the maximum code Doppler error for a ½ sample clock is 116 Hz. Therefore, the step size is rounded up to almost double, 250 Hz. A down-shifted input sample method is used to generate input samples with 0, 250 Hz, 500 Hz and 750 Hz removed. In this case, there are now 8 sample FFTs, 4 for A and 4 for B. For a channel where a 2200 Hz carrier frequency is desired, the 250 Hz FFT is selected and shifted by 2 grids to generate a carrier erasure of 2250 Hz. ii. Add the Doppler and code samples using a frequency addition operation so that the resulting code samples have the same frequency as the expected satellite Doppler frequency. This method is called the Up-Conversion Shifted Code Sample Method (UCSM). It uses the triangulation function to perform an up-conversion frequency shift on the complex sequence A by the frequency generator B: sin(a+b) = sinA cosB + cosA sinB, cos(a+b) = cosA cosB - sinA sinB, where A represents the frequency of the code sample and B represents the carrier frequency to be added. Sin and cos represent the imaginary part and the real part, respectively. Note that the code samples can start at zero phase in the case of code Doppler being addressed by shifting the resulting code spectrum, or can start at a non-zero initial phase in the case of code Doppler being addressed in the time domain. Sum the possibilities of performing frequency domain correlation using 22 channels, where each channel can process 4 components: 2 for sideband A and 2 for sideband B: Option 1: Apply carrier Doppler to the input samples and code Doppler to the code samples using a down-shifting approach: Correlation = IFFT [FFT (samples*Doppler) * FFT (code samples with non-zero phase)’]. When all components are used, each channel has 2 sample FFTs, one for A and B 4 code FFTs, one for each code 4 IFFTs, one for each code Total = 10/frequency For all channels: 22 * 10 = 220 FFTs/ms Option 2: Apply carrier Doppler using up-shifting method and apply code Doppler to code samples with non-zero initial condition: Correlation = IFFT [ FFT (samples) * FFT (code samples with non-zero phase due to carrier Doppler up-shifting)’]. Now the sample FFT is common to all channels. So put this in a separate pool. When all components are used, there are 4 code FFTs per channel, one for each code 4 IFFTs, one for each code total = 8/frequency For all channels: 22 * 8 + 2 sample FFTs for A and B = 178 FFTs/ms Option 3: Apply carrier Doppler to a set of input samples at a preset carrier Doppler using a down-shift method, and use a pre-calculated code spectrum and apply the frequency domain code Doppler method. Correlation = IFFT [ FFT (samples*Doppler) * FFT (code samples with zero phase)*e^(jwT)]. Assume a maximum integration time of 200 Hz Doppler step size is required. So there are 10 sample FFTs for A and B with steps of 0 Hz, 200 Hz, 400 Hz, 600 Hz, 800 Hz. When all components are used, each channel has to read 4 pre-computed code spectra, 4 IFFTs per code, one per code total = 4/frequency for all channels: 22*4 + 10 = 98 FFTs/ms The difficulty with option 3 is that the correlation engine should access the pre-computed code spectra very quickly. It has to read 22*4*20480 bytes/ms = 1.76 million bytes/ms. This is the motivation for using option 2, where a trade-off is made between the computation of the code spectrum power and the system complexity to retrieve the pre-computed code spectrum at a speed close to 2Gbytes/sec. Real-time Code Spectrum Generator (Preferred Embodiment, Option 2) 3. Real-time Code Spectrum Generator a. Perform VFFT on each code sequence in real-time before each acquisition correlator channel during the previous processing cycle (note that VFFT can be performed on the code sequence in ~40 us with a 108 MHz clock) b. Code generator generates 10 chips/cycle based on the 14-bit code of the GNSS satellite of interest. i. Code generator has 10 pairs of polynomials. ii. Code generator polynomials are programmable to allow for changes in future GNSS signals. c. A polyphase pulse filter is applied to the code sequence to achieve an adjustable time shift with resolution in a fraction of a chip period. i. Due to the bipolar (+|- 1) modulation code sequence, higher pulse shape accuracy can be achieved with a simple implementation. In addition, the bipolar modulation code sequence is noise-free, the pulse shaping filter coefficients can have higher accuracy and more terms, and the coefficients can be programmed to allow the pulse to respond to any changes in the digital front end. ii. Higher interpolation accuracy can be achieved with a simple implementation. Increasing the sampling rate (N_u ) can achieve higher precision in effective time shift. For example, in N_u=8, there is a 1/8 chip resolution with 2 samples/chip; this is achieved with a 4-phase filter. N_u higher values of are easily implemented. iii.     The pulse shaper implements time shifting of an integer number of chips in hardware iv. The time advance for each millisecond is calculated and applied in hardware based on the Doppler time shift assumption of the channel. v. An alternative approach is to apply the time shift in the frequency domain at the VFFT output with a phase shift across the frequency band before storing in the code spectrum memory. This approach may require an additional 20-point complex phase shifter in hardware as an additional processing pipeline stage after the VFFT 20-point phase shifter and the 20-point DFT; thus, there are a total of 3 processing pipeline operations in the last firmware loop. vi. Since the code spectra for the upper and lower sidebands of the BOC (15,10) signal are generated separately and independently in real time, a different time shift can be applied to each code spectrum every millisecond within the dwell duration (the dwell duration is the integration time). This design capability allows correction of different time shifts on the upper and lower sidebands due to unequal Doppler time shifts, ionosphere divergence, and antenna phase instability. These time shift differences can be more aligned when the code spectra are generated, which then allows constructive combining during the coherent addition of the upper and lower sidebands in post-correlation processing. d. Apply frequency shift to the shaped code sequence before VFFT i. The frequency shifter provides a wider frequency range and any frequency step size without the need to rotate and interpolate the bin values post-FFT. This provides maximum flexibility for satellite search strategies ii. The input from the pulse shaping filter is noise-free and relatively low-precision; hence, an ideal location for a frequency shifter. iii.     The frequency shifter has a Cordic-based phase rotator and a common phase accumulator for 20 samples/cycle in parallel; each of the 20 phase rotators applies a different phase offset iv. It should be possible to combine the phase shift value of the frequency shifter with the phase shift value of the first stage of the VFFT-DIT. This will allow a Cordic phase shifter to perform phase shift summing. v. Calculate and apply the phase advance per millisecond in hardware to maintain phase continuity over a dwell time of a few milliseconds. e. Perform a 20480 point VFFT-DIT on the time and frequency shifted code sequence i. Performed by the same processor as the baseband sample VFFT. ii. The resulting N=20480 bands of the code spectrum and baseband spectrum can be truncated to a smaller amount band-symmetrically to achieve the final "brick wall" filtering of the code spectrum (1 kHz transition band without spurious signal distortion). 1. One of 20k, 18k, 16K, 14k programmable options is available, enabling different options for samples/chip, associated pulse width, and assumed memory word size. iii.     The digital front end and baseband sample memory can be designed to achieve 20,480 kHz sampling rate and full main load processing, making it simpler and more accurate to process GNSS signals. No brick-and-mortar all nonlinear filters are required. iv. Only 25% more VFFT variable memory is required, which is a small portion of the total core area. The coarse time acquisition mode shown above is intended for situations where the code phase uncertainty for each SV to be acquired is > +/= 0.5ms. The final reporting step can report code phase and Doppler instead of code phase and carrier phase. CORDIC (Coordinated Rotation Digital Computer) Algorithm  The figure below shows the Cordic phase rotation that will occur in the code spectrum generation process to align the code spectrum with a continuous 1ms sample buffer over time. Secondary Code Phase Determination  Once the primary and secondary millisecond code phases are known, the acquisition process can be made more sensitive by determining the secondary code phase and shifting to coherent integration. However, this can be done in the tracking loop using techniques generally known in the art and is beyond the scope of this invention. However, it should be noted that in this case, the secondary code phase boundaries of all tracked SVs are fed back into the acquisition engine to assist in the acquisition of subsequent satellites in precise time mode.   PAUL MCBURNEY 8 Coherent Integration in Precise Time Acquisition Mode Assumed Memory Organization:  The following table shows the lengths of known secondary codes on all signal components for GPS, BeiDou and Galileo at L5. Generally speaking, sensitivity can be improved by 3dB per doubling with coherent integration and 1.5dB per doubling with non-coherent integration. Therefore, the table below shows the theoretical gain associated with coherent integration that is synchronized to the secondary code of each individual signal component, relative to non-synchronous integration. Cluster Signal Sub-code length Theoretical coherence gain within the main code period (5log10( length )) Galileo E5A 20 6.5dB Galileo E5 100 10dB Galileo E5 4 3dB Galileo E5 100 10dB GPS I5 10 5dB GPS Q5 20 6.5dB BeiDou B2a Information 5 3.5dB BeiDou B2a Introduction 100 10dB Once the receiver clock is effectively synchronized to the 100 ms Galileo E5 and BeiDou B2a secondary pilot codes, the coherent integration of these signal components can be extended up to 100 ms if the phase stability in the oscillator permits. (This does not mean that the absolute GNSS time is known, but that the sub-100 ms secondary code phase is known.) Although the navigation data for each channel can be predicted and estimated, in this embodiment it is assumed that such prediction is not available. In the precise time acquisition mode, these theoretical gains are therefore the gains to be approximated in a COVIMOGR. It should also be understood that oscillator phase stability will affect the theoretical coherent integration gain. In practice, L1 C/A receivers typically use 40 to 80 ms of coherent integration when, for example, navigation messages are modeled and predicted in advance, since further coherent integration will significantly narrow the effective Doppler grid and result in degraded returns due to oscillator phase instabilities. Direct acquisition of wideband GNSS signals faces similar concerns here. In an alternative embodiment, in the case where the expected primary ms code phase of a signal being searched is well defined but the secondary code phase is unknown, multiple coherent integration buffers are formed, one for each millisecond of ambiguity of the secondary code of the respective signal component. Note that if the secondary code phase is unknown, the average of the three clusters comprising the 100 ms secondary code pilot channel will be approximately 45 1 ms time ambiguity grids. Therefore, this may not be practical for the Galileo and BeiDou 100 ms secondary codes, but for the case where the code phase uncertainty is limited to approximately 10 microseconds, this integration may be feasible. In any case, only a portion of the complete PN cycle associated with the narrowed code phase window of each SV is stored in the hypothetical memory. In this case, the I and Q must be stored, and the A and B sidebands can be combined or integrated separately for later optimal gain combining. Note that all 100 1-ms ambiguities must generally be considered to reliably integrate the Galileo and BeiDou pilot channels coherently. The GPS pilot channel, while not as high in potential coherence gain, will assume only 1/5 the memory usage of the BeiDou and Galileo pilot channels due to its shorter secondary code. Given the level of time and Doppler uncertainty, full 1 ms PN rolling coherent integration of all SVs during coarse time acquisition is not commercially feasible. However, once a first SV is found, the first SV signal can be used to help estimate the code phase of the successive signals, limiting the timing error to twice the position uncertainty on either side and typically less, given that the initial position uncertainty is relatively low. The typical average code uncertainty associated with the position uncertainty will be only the position uncertainty on either side. In one embodiment (shown in FIG. 11 of the present invention), the sub-code phase is estimated in the time domain tracking engine and fed back to the acquisition engine for accurate time coherent integration of the signals not yet acquired in the acquisition engine. If, for example, the initial position uncertainty of the receiver is 1500 meters, the associated time uncertainty will average about 3000 meters/speed of light = 10 microseconds or less, <= 1% of the full 1MS PN roll. Given that the average total time ambiguity is about 45 ms, it can be seen that CIM can be balanced with NIM, perhaps larger in cases where dynamic Doppler uncertainty is high, and smaller in static cases. Once a reference signal is known, the actual two-sided SV specific time uncertainty window size can be set using a simple equation.,in𝜎 _p It is a unilateral initial position uncertainty andandare the individual unit pointing vectors from the estimated position to the nth SV and the reference SV, respectively. Similarly, the expected ms code phase of the i-th SV (at the center of the window) will be_ei=𝜑_γ + 1000 ∗m 𝑜𝑑(R_i – R_γ , 𝐶/1000)/𝐶, where 𝜑_γ is the known fractional phase (0 to 1) of the reference channel master code, R is the calculated range between an initial position and the satellite and C is the speed of light. In this case the modulus will be positive or negative, +/-0.5 ms. Similarly, when a subcode phase is known, the appropriate subcode fractional phase can be determined for each signal component that is less than or equal to the length of the maximum known subcode. In most cases, it will be easy to determine the 100ms code phase, so the equation will be shown here: 𝜑′_ei=𝜑′_γ + 10 ∗m 𝑜𝑑(𝑅_i - 𝑅_γ , 𝐶/10)/𝐶, where 𝜑′ is the secondary code phase. Note that in the case where a longer coherent integration is applied to both the pilot and data channels, which have shorter secondary codes, each with different Doppler widths and expected sensitivities. In this case, in a practical E5 coherent integration method for acquisition, the preferred embodiment uses only the E5 AQ and BQ pilot signals and discards AI and AQ when in precise time acquisition mode. Given that its coherent integration is limited to the length of its relatively short secondary code, this method maintains the robustness of tracking the A and B sidebands at the expense of the relatively small sensitivity of the data channel. Some gain can still be added by using the data channel, especially if its navigation messages are well predicted and erased, but for simplicity, tracking the pilot channel in this mode is the preferred embodiment. In another embodiment, all four codes can be coherently integrated up to the length of their respective subcodes. In this case, their respective VFFDC outputs will be appropriately summed in view of the pilot channel with a greater weight. It should be noted that in this case the effective Doppler grid widths of the data and pilot components will differ in size by a factor of up to 25. The wider Doppler grid size of the data channel can be simply mapped onto the richer Doppler grid of the pilot channel when summing to each of the coherent integration memory cells associated with the pilot channel. In another embodiment, the navigation message data prediction of the data channel may be used to remove its respective bit transitions and thereby extend the coherent integral of the data channel to match the coherent integral of the pilot channel. Top: Precise time coherent and non-coherent integration processing. Note that the reporting block can report code phase and Doppler instead of code and carrier phase for transfer to the tracking engine. Assumption Memory  The figure below shows an example implementation of a shared general purpose non-coherent assumption (integrate/accumulate) memory, organized into ~20KB size buffers. The non-coherent buffers each contain a single mixer result, based on the code phase uncertainty window for each SV of interest, and the coherent memory map (on the same reusable buffer) contains a mix of in-phase and quadrature, multiple Doppler bins, and multiple SVs per bin. Assume memory is configured for non-coherent integration in coarse time mode (initial configuration is 100 ms seek) – organized into 24 – 20460 byte buffers The figure below shows an exemplary implementation of a shared hypothetical memory in an exact time coherent integration mode during a first integration period. Note that in this case, complex data must be stored but with narrowed code phase uncertainty, and each Doppler must only save a portion of the full PN cycle. In this embodiment, the two pilot signal components are saved in separate buffers. In another embodiment, they can be merged. In yet another embodiment, the shorter coherent integration times of the data channels can be integrated with appropriate weighting into their respective pilot counterparts (AI becomes AQ and BI becomes BQ), or the data can be erased across subcode boundaries before coherent integration using predicted navigation message data. This approach would require additional buffering of the I component so that it can be added to the Q component at the end of its respective subcode period. This would not have a significant impact on memory usage in the hybrid approach, given that there are multiple pilot Dopplers per data Doppler and that data and pilot components can be combined in the case of prediction and erasure of navigation message data. Assume memory is configured for coherent integration in exact time mode (configurable time slots) Summation can improve acquisition sensitivity (in one or more embodiments) by one or more of the following: 1. Direct wideband signal acquisition. 2. Separating the sidebands to avoid raising the noise level from the original level of each sideband. 3. Mixing all components in coarse time acquisition for maximum fading-resistant SNR. 4. Determining at least one pilot channel subcode phase in the tracking engine and feeding it back to the acquisition engine when transitioning to fine time acquisition mode. 5. When in fine time acquisition mode, mixing all frequency diversity pilot channels for maximum fading-resistant SNR. 6. Integrate the correlation results into a single hypothetical memory where each ms result is compensated for code Doppler 7. Handle code Doppler using one of the three methods described above so that the strongest signal power grows only at the hypothetical memory location, rather than smearing the signal at multiple locations if code Doppler is not properly accounted for. 8. FFT-based 20,360 chip code correlation. 9. In precise time acquisition mode, coherent integration is at least partially aligned with the expected main code phase. To keep the cost (memory, power, silicon area, RF link) reasonable, one or more embodiments may use: 1. Direct wideband signal acquisition of L5 wideband signal only. 2. VFFDC architecture achieves working memory reuse and minimum signal input buffer size. 3. Temporary code spectrum generation minimizes code spectrum storage and I/O. Incorporating and carefully managing non-coherent and coherent assumption memory buffers also reduces memory usage. Matlab Appendix This Matlab Appendix contains copyrighted material. The owner, oneNav, hereby reserves all rights, including copyright, in the material. The copyright owner has no objection to the facsimile reproduction by any person of the patent file or patent disclosure as it appears in the U.S. Patent and Trademark Office file or records, but otherwise the copyright owner reserves all copyright rights. Copyright oneNav. Part 1 The following Matlab code provides an implementation of a GNSS code generator in Matlab using the implementation shown in Figures 9A to 9D. function [code_array] = gnss_code_gen(code_bits_per_row, code_gen_poly_set, code_gen_seed) % Generates an array of code bits for all wideband GNSS signals % % Component State Var Length Shorten Code Gen Poly Exponents % L5I|Q 13 x1=＞8190 [9,10,12,13] % x2=＞full [1,3,4,6,7,8,12,13] % E5AI|Q 14 x1=＞full [1,6,8,14] % x2=＞full [4,5,7,8,12,14] % E5BI|Q 14 x1=＞full [4,11,13,14] % x2=＞full [2,5,8,9,12,14] % B2AI (data) 13 x1=＞8190 [1,5,11,13] % x2=＞full [3,5,9,11,12,13] % B2AQ (pilot) 13 x1=＞8190 [3,6,7,13] % x2=＞full [1,5,7,8,12,13] % Code generator seed must be length 14, even for L5 & B2 with poly order 13. % Append an extra zero bit if needed, and transpose into a column vector. if (length(code_gen_seed) == 13), code_gen_seed = [code_gen_seed 0]'; elseif (length(code_gen_seed) == 14), code_gen_seed = code_gen_seed'; end % Code generation polynomials in vector format g1_L5IQ = [0 0 0 0 0 0 0 0 1 1 0 1 1]; % [9,10,12,13] g2_L5IQ = [1 0 1 1 0 1 1 1 0 0 0 1 1]; % [1,3,4,6,7,8,12,13] g1_E5AIQ = [1 0 0 0 0 1 0 1 0 0 0 0 0 1]; % [1,6,8,14] g2_E5AIQ = [0 0 0 1 1 0 1 1 0 0 0 1 0 1]; % [4,5,7,8,12,14] g1_E5BIQ = [0 0 0 1 0 0 0 0 0 0 1 0 1 1]; % [4,11,13,14] g2_E5BIQ = [0 1 0 0 1 0 0 1 1 0 0 1 0 1]; % [2,5,8,9,12,14] g1_B2AI = [1 0 0 0 1 0 0 0 0 0 1 0 1]; % [1,5,11,13] g2_B2AI = [0 0 1 0 1 0 0 0 1 0 1 1 1]; % [3,5,9,11,12,13] g1_B2AQ = [0 0 1 0 0 1 1 0 0 0 0 0 1]; % [3,6,7,13] g2_B2AQ = [1 0 0 0 1 0 1 1 0 0 0 1 1]; % [1,5,7,8,12,13] % Add B2B and Glonass when available. Offer 3 programmable options for future % Select the configuration parameters for the code generator switch (code_gen_poly_set) case 'L5IQ' g1_poly = g1_L5IQ; g2_poly = g2_L5IQ; poly_order = 13; x1_code_length = 8190; case 'E5AIQ' g1_poly = g1_E5AIQ; g2_poly = g2_E5AIQ; poly_order = 14; x1_code_length = 10230; case 'E5BIQ' g1_poly = g1_E5BIQ; g2_poly = g2_E5BIQ; poly_order = 14; x1_code_length = 10230; case 'B2AI' g1_poly = g1_B2AI; g2_poly = g2_B2AI; poly_order = 13; x1_code_length = 8190; case 'B2AQ' g1_poly = g1_B2AQ; g2_poly = g2_B2AQ; poly_order = 13; x1_code_length = 8190; otherwise disp('Unsupported Code Generator Mode') end% switch % Form the generator polynomial vector into a 14 by 14 state transition matrix with an identity sub-matrix % The identity matrix behaves like a shift register. if (poly_order == 14) G1 = [g1_poly ; eye(13,14)]; G2 = [g2_poly ; eye(13,14)]; elseif (poly_order == 13) % Append 1 zero row and column to fill 14x14 array G1 = [g1_poly; eye(12,13); zeros(1,13)]; G2 = [g2_poly; eye(12,13); zeros(1,13)]; G1 = [G1 zeros(14,1)]; G2 = [G2 zeros(14,1)]; end % if % Set the iteration where the G1*X1 code generator state must be re-initialized to all ones. x1_state_init_k = x1_code_length/code_bits_per_row; % Initialize the X1 and X2 state variable vectors and the output array X1 = ones(14,1); X2 = code_gen_seed; code_array = zeros(10230/code_bits_per_row, code_bits_per_row); % Code generation with one code bit per iteration if (code_bits_per_row == 1) for k = 1:10230 code_array(k) = xor(X1(poly_order), X2(poly_order)); X2 = mod(G2 * X2, 2); if (k == x1_state_init_k), X1 = ones(14,1); else, X1 = mod(G1 * X1, 2); end end % for % Code generation with ten code bits per iteration elseif (code_bits_per_row == 10) % Multiple the state transition matrix by 10 times to form a new matrix % that advances the state by 10 code bits on each iteration. G1_10 = mod(G1^10, 2); G2_10 = mod(G2^10, 2); % Define generator output range for state variable bits in reverse order out_index = uint8(poly_order:-1:(poly_order-9)); for k = 1:1023 code_array(k,:) = xor(X1(out_index), X2(out_index)); X2 = mod(G2_10 * X2, 2); if (k == x1_state_init_k), X1 = ones(14,1); else, X1 = mod(G1_10 * X1, 2); end end % for end % if % Print state transition matrix % G1 = uint8(G1) % G2 = uint8(G2) % G1_10 = uint8(G1_10) % G2_10 = uint8(G2_10) end % function % Example of code seed values for first 2 SVs in each constellation % Seed value vector order =>[s21, s22, s23, ... s2r], where r is state variable size % First code bits output are ordered as c1, c2, c3 .., with c1 as MSB % Because g1 is initialized to all 1s, the first code bit vector is inverted and bit-reversed from the seed vector % % Component Initial State Seed First code bits output % L5I sv1,I = 1010100011011 0010011101010 % L5Q sv1,Q = 0110100110011 0011001101001 % L5I sv2,I = 0011111001010 1010110000011 % LqCy sv2,Q = 1011100001001 0110111100010 % E5AI sv1,AI= 10100011000011 3CEA9D % E5A sv1,AQ= 01010101110101 515537 % E5B sv1,BI= 00001001011100 C5BEA1 % E5B sv1,BQ= 10011011011000 E49AF0 % E5AI sv2,AI= 00111001000110 9D8CF1 % E5A sv2,AQ= 01000110010100 D67539 % E5B sv2,BI= 11100100001101 4F6248 % E5B sv2,BQ= 11000110001100 CE701F % B2AI sv1,I = 1000000100101 26771056 % B2A sv1,Q = 1000000100101 26772435 % B2AI sv2,I = 1000000110100 64771737 % B2A sv2,Q = 1000000110100 64771100 % Notes: % L5 seed values are inverted, and first code bits are bit-reversed from ICD % E5 seed values are bit reversed from ICD % B2 is correct in ICD % secondary code - pilot % L5 at 1 kHz rate => nh20(t) = 0 0 0 0 0 1 0 0 1 1 0 1 0 1 0 0 1 1 1 0 Part 2 The following Matlab code provides an implementation in Matlab of the GNSS code sample generation script using the embodiments shown in FIGS. 9A to 9D. clear sc_cmd.code_gen_poly_set = 'E5AIQ'; sc_cmd.code_gen_seed = [1 0 1 0 0 0 1 1 0 0 0 0 1 1]; sc_cmd.freq_shift = -20480; sc_cmd.freq_shift_phase = 0; sc_cmd.code_advance = 11.125; sc_cmd.code_phase_step = 0.01; sc_cmd.second_code_length = 20; sc_cmd.second_code_seq = ones(sc_cmd.second_code_length, 1); sc_cmd.second_code_phase = 0; ms_nr = 1; % function [code_sample_array, csg_state_var] = code_sample_gen(ms_nr, sc_cmd, csg_state_var) % Code Sample Generator - Generate GNSS code, secondary code, shift code phase, upsample, filter and shift frequency % First unpack the command and state variable structures % and translate values for the hardware operations % --- Commands that are fixed for dwell duration --- % Frequency shift is specified in Hz and converted to a signed fraction of the sample rate. freq_gen_shift = sc_cmd.freq_shift / 20480000; % Code generator polynomial set selection and initial state variable (seed) code_gen_poly_set = sc_cmd.code_gen_poly_set; code_gen_seed = sc_cmd.code_gen_seed; % Frequency shifter phase step per ms is defined as signed fraction of cycles advanced/declined per ms. freq_gen_phase_step_ms = rem(sc_cmd.freq_shift / 1000, 1); % Code phase step per ms is defined as signed fraction of the code- bit period advanced/declined per ms. code_gen_phase_step_ms = sc_cmd.code_phase_step; % --- Variables set to command values on first ms, and updated every ms over dwell duration --- if (ms_nr == 1) % Initial phase of freq gen is specified in degrees and converted to positive fraction of a cycle freq_gen_phase = mod(sc_cmd.freq_shift_phase, 360) / 360; % Initial phase of code gen is specified in positive code-bit periods with 0.125 resolution, 0 to 63.875 range code_gen_phase = sc_cmd.code_advance; else % When not first ms, load state variables from last ms freq_gen_phase = csg_state_var.freq_gen_phase; code_gen_phase = csg_state_var.code_gen_phase; end % Update and save state variables for the next ms time when this function is called again csg_state_var.freq_gen_phase = freq_gen_phase + freq_gen_phase_step_ms; csg_state_var.code_gen_phase = code_gen_phase + code_gen_phase_step_ms; % Factor the code phase advance into tens, ones and 1/8th fractions of code bits. % Hardware will apply these in 3 separate stages of cycle advancing and shifting. code_advance_rnd = round(8*code_gen_phase)/8; % round to 1/8 resolution code_advance_tens = uint32(floor(code_advance_rnd/10)); code_advance_ones = uint32(floor(code_advance_rnd/1)) - 10*code_advance_tens; code_advance_frac = uint32(8*rem(code_advance_rnd,1)); % Secondary Code-bit Selection second_code_bit = sc_cmd.second_code_seq( mod((sc_cmd.second_code_phase+ms_nr-1), sc_cmd.second_code_length) +1); % --- Now generate 20480 samples for the code sequence % Generate a length 10230 code sequence for a GNSS satellite signal component. % Reshape into a column vector for easier math in subsequent lines, % although hardware will process 10 bits in parallel per cycle code_array = gnss_code_gen(10, code_gen_poly_set, code_gen_seed); code_vector = reshape(code_array', [10230 1]); % Apply the secondary code to the primary code sequence second_code_vector = xor(code_vector, second_code_bit*ones(10230,1)); % not exactly right! another secondary code bit is needed on extension % Extend the code sequence by 20 code bits by appending the first 20 code bits to the end of the sequence. % Advance the code phase in increments of 10 code bits % (like the hardware will do in multiple clock cycles) code_ext_adv10 = [second_code_vector((10*code_advance_tens+1) : 10230) ; second_code_vector(1 : (10*code_advance_tens+20))]; % Advance the code phase by 0 to 9 code bits. Append NaN to fill vector to same size code_adv1 = [code_ext_adv10(code_advance_ones+1 : length(code_ext_adv10)) ; NaN(code_advance_ones, 1)]; % Upsample 8x by stretching each code-bit value over 8 consecutive samples code_sample_8x = reshape([code_adv1 code_adv1 code_adv1 code_adv1 code_adv1 code_adv1 code_adv1 code_adv1]', [8*length(code_adv1), 1]); % Further advance the code phase with 1/8 th chip resolution. Append NaN to fill vector to same size code_adv_frac = [code_sample_8x(code_advance_frac+1 : length(code_sample_8x)) ; NaN(code_advance_frac, 1)]; % Reshape into array of 1025 rows by 80 columns in column-order (just for easy sample insertion) % Insert repeated sample at the Nr row index in each of the 80 columns. % Reshape back into 1 column vector code_sample_array = reshape(code_adv_frac, [1025 80]); [code_sample_array(1:Nr, 1:80); code_sample_array(Nr, 1:80); code_sample_array((Nr+1):1025, 1:80)]; code_upsample = reshape(code_insert_array, [80*1026, 1]); % Lowpass filter and decimating by 4 to 80*1024 sample vector h_aa = 1/64 * [5 -2 -4 -3 -1 5 9 15 16 15 9 5 -1 -3 -4 -2 5]; % plot(h_aa) Ni = length(h_aa) - 1; lpf = zeros(20480, 1); for n = 1:20480 lpf(n) = sum(h_aa' .* code_upsample(4*n-3 : 4*n-3+Ni)); end % Frequency shifter (typical range less than +/- 10 kHz). Complex output % Set phase accumulator to initial phase command, then advance by frequency shift command % Limit to 1024 phase shifts/cycle to match with capabilites of the CORDIC in 1st stage of 20 by 1024-point FFTs freq_gen_phase_accum = zeros(20480, 1); freq_gen_phase_accum(1) = freq_gen_phase; for n = 2:20480 freq_gen_phase_accum(n) = rem((freq_gen_phase_accum(n-1) + freq_gen_shift), 1); end freq_gen_phase_1024 = round(freq_gen_phase_accum * 1024) / 1024; code_sample_vector = lpf .* exp(1j*2*pi * freq_gen_phase_1024); % Reshape sample vector into array of 1024 rows by 20 columns in row order. code_sample_array = reshape(code_sample_vector, [20 1024])'; % end % Alt method % Lowpass filter and decimating by 4 % Sum 8 consecutive 1-bit code values and step 4 samples every iteration. % Equivalent to h = [1 1 1 1 1 1 1 1] with post decimation by 4 % y1 = zeros(20480+2, 1); % for k = 1:(20480+2) % y1(k) = sum(code_upsample(4*k-3 : 4*k+4)) - 4; % end % Equalization filter for sinc shape LPF spectrum (try 3-tap or may need 5-tap) % Note, LPF+EQ combined filtering has an effective group delay of 8 samples => 1024/1023 chip periods % c = 0.3;                 h_eq = [1-c 1 1-c];       % Just place holder!!!! % y2 = zeros(20480, 1); % for k = 1:20480 % y2(k) = sum(h_eq' .* y1(k : k+2)); % end Part 3 The following Matlab code provides an implementation of the GNSS signal acquisition engine in Matlab using the implementation shown in FIG6. % Acquisition Engine Signal Processing % Frequency Plan fs_adc = 432000; % Plan A rf_upsample_rate = 8; fs_rf = rf_upsample_rate * fs_adc; fs_if = fs_adc/4; % Satellite Parameters ssg_param.sample_rate = 432000; % kHz ssg_param.sv_type = 'E5'; ssg_param.sv_number = 1; ssg_param.doppler_freq = 200; % Hz time shift per ms = -freq_shift /116500 ssg_param.snr = 0; % dB ssg_param.chip_code_phase = 0; % apply as decline ssg_param.pilot_code_phase = 0; % % Digital Front End Commands dfe_cmd.first_if_upconv = 1; % Upconv neg IF, downconv pos IF dfe_cmd.gain_step = 1; % - 3dB steps dfe_cmd.ifd2_init_phase = 0; dfe_cmd.ifd2_freq_shift = -3795/fs_if; dfe_cmd.ab_init_phase = 0; dfe_cmd.ab_freq_shift = 15345/fs_if; dfe_cmd.int_dec_rate = floor(fs_if/20480); dfe_cmd.frd_init_phase = 0; dfe_cmd.frac_dec_phase_step = fs_if / (dfe_cmd.int_dec_rate*20480) - 1; % AE Channel Commands for 4 sub-channels, 1 channel only dwell_duration = 10; % ms integration_mode = 'Non_Coh'; comp_combining_mode = [2 2]; % 4 [2 2] [1 1 1 1] sc1_cmd.sideband_select = 'ASB'; % ASB or BSB sc2_cmd.sideband_select = 'ASB'; sc3_cmd.sideband_select = 'BSB'; sc4_cmd.sideband_select = 'BSB'; sc1_cmd.freq_shift = 200; % Hz sc2_cmd.freq_shift = 200; sc3_cmd.freq_shift = 200; sc4_cmd.freq_shift = 200; sc1_cmd.freq_shift_phase = 0; % Degrees sc2_cmd.freq_shift_phase = 90; sc3_cmd.freq_shift_phase = 0; sc4_cmd.freq_shift_phase = 90; sc1_cmd.code_advance = 11.125; % Code sequence start position (1/8 chip resolution) sc2_cmd.code_advance = 11.125; sc3_cmd.code_advance = 11.125; sc4_cmd.code_advance = 11.125; sc1_cmd.code_phase_step = 0.01; % added/subtracted from code phase every ms sc2_cmd.code_phase_step = 0.01; % set to -freq_shift / 116500 sc3_cmd.code_phase_step = 0.01; sc4_cmd.code_phase_step = 0.01; sc1_cmd.code_gen_poly_set = 'E5AIQ'; sc2_cmd.code_gen_poly_set = 'E5AIQ'; sc3_cmd.code_gen_poly_set = 'E5BIQ'; sc4_cmd.code_gen_poly_set = 'E5BIQ'; sc1_cmd.code_gen_seed = [1 0 1 0 0 0 1 1 0 0 0 0 1 1]; % for Galileo SV #1 sc2_cmd.code_gen_seed = [0 1 0 1 0 1 0 1 1 1 0 1 0 1]; sc3_cmd.code_gen_seed = [0 0 0 0 1 0 0 1 0 1 1 1 0 0]; sc4_cmd.code_gen_seed = [1 0 0 1 1 0 1 1 0 1 1 0 0 0]; sc1_cmd.second_code_length = 20; % L5 => 10,20; E5 => 4,20,100; B2 => 5, 100 sc2_cmd.second_code_length = 100; sc3_cmd.second_code_length = 4; sc4_cmd.second_code_length = 100; sc1_cmd.second_code_seq = zeros(sc1_cmd.second_code_length, 1); based on SV number and type sc2_cmd.second_code_seq = zeros(sc2_cmd.second_code_length, 1); just write down first 2 SV of each GNSS sc3_cmd.second_code_seq = zeros(sc3_cmd.second_code_length, 1); sc4_cmd.second_code_seq = zeros(sc4_cmd.second_code_length, 1); sc1_cmd.second_code_phase = 0; % Index offset advance of first code bit within sequence at start of dwell. sc2_cmd.second_code_phase = 0; % All secondary codes have 1 ms bit period sc3_cmd.second_code_phase = 0; sc4_cmd.second_code_phase = 0; % Dwell Loop for 1 channel with up to 4 sub-channels for ms_nr = 1 : dwell_duration % GNSS Satellite Signal Generator => Length 432,000 column vector, Load/save state variables every ms [ssg_signal, ssg_state_var] = gnss_signal_gen(ms_nr, ssg_param, ssg_state_var); % Digital Front End => 1024 by 20 in row order, Load/save state variables every ms [ASB_sample, BSB_sample, dfe_state_var] = dig_front_end(ms_nr, ssg_signal, dfe_cmd, dfe_state_var); % GNSS Code Sample Generators => 1024 by 20 in row order [code_sample_1, csg1_state_var] = code_sample_gen(ms_nr, sc1_cmd, csg1_state_var); [code_sample_2, csg2_state_var] = code_sample_gen(ms_nr, sc2_cmd, csg2_state_var); [code_sample_3, csg3_state_var] = code_sample_gen(ms_nr, sc3_cmd, csg3_state_var); [code_sample_4, csg4_state_var] = code_sample_gen(ms_nr, sc4_cmd, csg4_state_var); % Sideband Signal Spectrum Transform => 1024 by 20 in column order ASB_spec = vfft_dit(ASB_sample); BSB_spec = vfft_dit(BSB_sample); % Select Sideband Spectrum for each Sub-channel if (sc1_cmd.sideband_select == 'ASB'), sc1_SB = ASB_spec; else, sc1_SB = BSB_spec; end if (sc2_cmd.sideband_select == 'ASB'), sc2_SB = ASB_spec; else, sc2_SB = BSB_spec; end if (sc3_cmd.sideband_select == 'ASB'), sc3_SB = ASB_spec; else, sc3_SB = BSB_spec; end if (sc4_cmd.sideband_select == 'ASB'), sc4_SB = ASB_spec; else, sc4_SB = BSB_spec; end % Code Spectrum Transform => 1024 by 20 in column order code_spec_1 = vfft_dit(code_sample_1); code_spec_2 = vfft_dit(code_sample_2); code_spec_3 = vfft_dit(code_sample_3); code_spec_4 = vfft_dit(code_sample_4); % Signal and Code Spectrum Multiple =＞ Conjugate the code spectrum and result before IFFT mult_spec_1 = conj(sc1_SB .* conj(code_spec_1)); mult_spec_2 = conj(sc2_SB .* conj(code_spec_2)); mult_spec_3 = conj(sc3_SB .* conj(code_spec_3)); mult_spec_4 = conj(sc4_SB .* conj(code_spec_4)); % Correlation (Inverse) Fourier Transform => 1024 by 20 in row order corr_result_1 = vfft_dif(mult_spec_1); corr_result_2 = vfft_dif(mult_spec_2); corr_result_3 = vfft_dif(mult_spec_3); corr_result_4 = vfft_dif(mult_spec_4); %Correlation Post Processing % Integration % Correlation Plot - update every ms % Print out status % Save results to file end % ms_nr loop Part 4 The following Matlab code provides an implementation of a GNSS signal acquisition engine in Matlab. In the implementation shown in Figure 6, the GNSS signal acquisition engine uses DFT and time extraction. function [Y] = vfft_dit(X) % Very Fast Fourier Transform by Decimation in Time Algorithm % % X is the time domain input array of N2 rows by N1 columns with array % elements in row order. % % Y is the frequency domain output array of N2 rows by N1 columns with array % elements in column order. % % The N-point VFFT-DIT algorithm-architecture is speed optimized by decomposing % the FFT processing into N1 parallel FFTs of N2-points, followed by a % combining stage with N1-point DFTs. The N1 parallel FFTs are performed % concurrently using array processing to speed up FFT processing time by a % factor of N1 times. % The total number of FFT points is N = N1 * N2, with N1 ＜＜ N2 % An inverse VFFT-DIT can be done by conjugating the input and output arrays. % Find the dimensions for the X array input [N2, N1] = size(X); % Total number of FFT points N = N1 * N2; % Calculate N2-point FFTs for all columns of X array H = fft(X, N2, 1); % Define an N2 by N1 array of n2*k1 exponent values for the WN phase shift factors P = [0:1:(N2-1)]' * [0:1:(N1-1)]; % Define the N2 by N1 array of WN phase shift factors WN = exp(-1j*2*pi/N * P); % Array element multiply of the N2-point FFT results and the WN phase shift factors H_WN = H .* WN; % Calculate N1-point DFTs on all rows Y = fft(H_WN, N1, 2); end Part 5 The following Matlab code provides an example of an implementation of a GNSS signal acquisition engine in Matlab. In the implementation shown in FIG6 , the GNSS signal acquisition engine uses a DFT of frequency extraction method. function [Y] = vfft_dif(X) % Very Fast Fourier Transform by Decimation in Frequency Algorithm % % X is the time domain input array of N2 rows by N1 columns with array % elements in column order. % % Y is the frequency domain output array of N2 rows by N1 columns with array % elements in row order. % % The N-point VFFT-DIF algorithm-architecture is speed optimized by decomposing % the FFT processing into a first stage with N1-point DFTs, followed by % N1 parallel FFTs of N2-points. The N1 parallel FFTs are performed concurrently % using array processing to speed up FFT processing time by a factor of N1 times. % The total number of FFT points is N = N1 * N2, with N1 ＜＜ N2 % An inverse VFFT-DIF can be done by conjugating the input and output arrays. % Find the dimensions for the X array input [N2, N1] = size(X); % Total number of FFT points N = N1 * N2; % Calculate N1-point DFTs on all rows of X G = fft(X, N1, 2); % Define an N2 by N1 array of n2*k1 exponent values for the WN phase shift factors P = [0:1:(N2-1)]' * [0:1:(N1-1)]; % Define the N2 by N1 array of WN phase shift factors WN = exp(-1j*2*pi/N * P); % Array element multiply of the first stage DFT results and the WN phase shift factors G_WN = G .* WN; % Calculate N2-point FFTs for all columns of G .* WN Y = fft(G_WN, N2, 1); End Appendix 3Using frequency domain Doppler compensation background GNSS Signal acquisition: GNSS (Global Navigation Satellite System) signals are usually incorporated into a Pseudo Randomly Modulated (PRN) waveform to achieve accurate arrival time measurement at the receiving terminal. Usually a PRN waveform is incorporated into a repetitive code, the duration of which is called the frame length. The received waveform is processed using a signal processing structure (e.g., a set of correlators, matched filters, etc.). The present invention focuses on obtaining GNSS signals based on the use of a Fast Fourier Transform (FFT) method, which effectively implements a matched filter corresponding to a received signal. This method is particularly attractive when the spread ratio (SR) of the PRN waveform is large (i.e., the ratio of signal bandwidth to frame length is large). In many modern GNSS systems, this expansion ratio can exceed 10,000. FFT is a very efficient algorithm for computing a discrete Fourier transform (DFT), and even though the term "FFT" is used throughout, by FFT is meant any means for computing a DFT, including various FFT algorithms, including Cooley-Tukey algorithm, prime factor algorithm, frequency modulation z-transform algorithm, etc. Acquiring a GNSS signal with high SR is difficult because the signal arrival times must be within a large set of time instances (e.g., over 10,000 in the above example) and furthermore tested over a large set of potential frequency offsets from a nominal assumed carrier frequency, the potential frequency offsets being due to Doppler effects and local clock errors. Additionally, a set of possible satellite signals must be tested. A set of times, a set of frequency offsets, and a set of satellite signal numbers are called "hypotheses." As can be seen above, acquiring GNSS signals requires searching a large three-dimensional hypothesis space. The time hypothesis search can be performed very efficiently using the FFT method because each possible time hypothesis can be processed in parallel within the frame length. The FFT method performs a matched filtering operation on a set of incoming time samples by: (1) performing a forward FFT on the set of incoming time samples to generate a set of "signal frequency samples," (2) multiplying the signal frequency samples by frequency samples of a PRN reference signal (called "reference frequency samples"), and (3) performing an inverse FFT on the result. This set of output samples is then further accumulated with several previous sets of outputs to perform "coherent processing", or the output samples are detected (usually by magnitude or magnitude square operations) and accumulated with the previous data sets that were similarly processed. The accumulated sets of processed data are observed to determine whether a large peak appears above the background noise samples, where the peak indicates the arrival time of the incoming signal. As indicated above, in the acquisition process, the incoming signal may have a carrier frequency offset associated with it, which is also determined. A conventional method for making this determination involves assuming a Doppler frequency, compensating for the Doppler in the time domain by multiplying the set of incoming samples by a complex cosine to remove the Doppler component and then continuing with the above three steps. This procedure is performed for each of a set of assumed Doppler frequencies. The problem with this method using an FFT implementation is that a forward FFT and an inverse FFT are required for each Doppler assumed frequency. In many cases, a set of 20 or more such assumed frequencies must be searched. The present invention reduces the number of such FFTs to approximately half of the number required in the above prior art methods, thereby reducing the overall processing time by nearly half.Invention In the following discussion, the frequency uncertainty is referred to as "Doppler" but the frequency uncertainty may also be due to local oscillator frequency errors. For simplicity of discussion the frequency uncertainty is referred to as "Doppler" but when doing so it actually means any source of frequency uncertainty, perhaps including errors on the part of a GNSS transmitter. Also, in the following discussion, for simplicity the multiplication of the forward FFT data with the frequency reference (discussed above) is ignored but this is performed normally. After a forward FFT, if the FFT output is considered as a vector, if the vector is rotated m positions then this is equivalent to a frequency shift equal to m x grid spacing, where the grid spacing equals the sampling rate divided by the number of samples/FFT. Here, m is an integer which may be positive for positive shifts and negative for negative shifts. If the input signal is positively Doppler shifted, the vector will usually be rotated negatively to compensate, and vice versa. This has the effect of converting the signal to near zero frequency or some other desired frequency. An advantage of this method is that after a forward FFT, a multiplicity of Doppler shifts can be tested by a series of inverse FFTs, each of which is followed by a rotation.¹ The operation is performed with a frequency shift. For example, if 20 Doppler frequencies are tested in this way, only one forward FFT will be required and 20 inverse FFTs will be required, one for each Doppler to be tested. In this example, only 21 FFT operations need to be performed, while 40 are required in the standard method. In many cases, checking the Doppler uncertainty region with integer grid spacing increments is coarse, resulting in a worst-case loss of (0.5) or 3.9 dB. To reduce this loss, it is desirable to perform a rotation of the above vector by ½ grid spacing, i.e., it is desirable to test for a Doppler frequency shift equal to m+1/2 grids. This rotation can be performed in one of three ways. In the first method, two forward FFTs are performed, one without modification and the second with a frequency shift equal to half the grid spacing, ie, a frequency offset of the sampling rate/(2Xno_FFT_samples). This frequency shift will be done in the time domain by multiplying by a complex cosine in the usual way (or using an equivalent algorithm such as CORDIC rotation). Each of these forward FFTs is stored. To test for Doppler error of an integer number of grids, the first forward FFT vector is rotated by the required number of grids. To test for Doppler error incorporated into half grid spacing, the second forward FFT vector is selected and rotated by an appropriate integer number of grids. For example, if one wants to test for Doppler error of m+1/2 grids (m and integer), i.e., one wants an overall compensation shift of -m-1/2 grids, one would rotate the second forward FFT vector = -m-1 positions. Note here that the second FFT data set incorporates a shift of +1/2 grid (assumed) so that the total shift is -m-1+1/2=-m-1/2. Of course, the above technique also works if the data used is first frequency shifted by -1/2 grid, or indeed 1/2 grid plus a positive or negative integer multiple of grids, before the second forward FFT. In that case, the data vector will need to be rotated by an appropriate integer amount after the second forward FFT is performed to achieve the overall desired Doppler compensation. The first method above is very accurate but of course the number of forward FFT operations plus times. In the previous example, a total of 22 forward FFTs were required, while the standard method requires 40 FFTs, still a good savings. However, another disadvantage is that twice as many forward FFT vectors need to be maintained, which can be a high price to pay, especially if several parallel FFTs are required to achieve an overall acquisition time. A second method to achieve an offset that incorporates ½ grid spacing is to use an interpolation technique on the forward FFT samples in the frequency domain to determine the middle sample at ½ grid spacing from each of the original frequency samples. The vector of middle samples then replaces the second forward FFT vector discussed above. FFT. This vector of intermediate samples is then rotated the required number of positions to implement a Doppler shift of ½ the grid spacing plus the requisite number of integer divisions. A number of different interpolation functions may be used to determine the intermediate samples depending on the complexity and accuracy required. For example, a sinc interpolator may be used, i.e., sin(2πf)/(2πf), where f is in units of the grid spacing. Alternatives include polynomial interpolators, spline functions, etc. In general, the most appropriate interpolator can be determined empirically since it depends on the frequency response of the time samples and the maximum complexity of the interpolator. In the case of ½ the grid spacing achieved by either method, the maximum complexity of the interpolator is 0. With a grid spacing of 1/4, the worst case loss due to Doppler error is -0.91 dB. This does not include any additional implementation errors (such as interpolation errors). In yet a third method, an interpolation is performed but rather than performing the interpolation in the frequency domain, the input data sample set is appended with additional frequency samples having the value zero, which are appended at the beginning or end of the sample set. If the set of zero-valued samples is equal to the value of the original sample set, then the resulting FFT of the appended sample set has an FFT with a grid spacing of ½ now relative to the FFT of the non-appended set. Thus a simple rotation of the FFT vector now provides a frequency translation in the positive or negative direction in a manner similar to that discussed above. Spacing less than ½ grid can be achieved by appending the original set with more zero-valued samples (e.g., adding twice as many zero-valued samples gives 1/3 grid spacing, etc.). Whether to choose the first or second method for testing Doppler with m+1/2 grid spacing depends on the storage requirements of the first method due to the complexity of the interpolation. In terms of computational speed, the interpolator method is expected to use fewer operations/frequency samples than the FFT. Although it seems that an interpolation process may be more computationally efficient, some further examination shows that this is not the case. In terms of operations/data samples, the FFT operation is very efficient. An FFT of length N requires only about 2 log2(N) real multiplications per data sample. For example, an FFT of size 1024 requires only about 20 real multiplications per data sample. An equivalent complexity interpolator would have an interpolation filter of length (number of taps) equal to 10, since two real multiplications are required per frequency sample. Since frequency data tends to be very noisy, it is not clear whether such a short length will be sufficient to achieve the required accuracy. The above method can be further generalized to offsets other than m+1/2 grid spacing to m+e grid spacing, where e is any number between 0 and 1. An additional forward FFT of the input data can be calculated after frequency conversion by a vector corresponding to e grids and this is stored for later use, where this vector is used with an appropriate number of vector position shifts. Alternatively, the interpolation method can be used to determine the middle sample from any of the pre-computed FFT data sets (e.g., sets with 0 frequency offset and ½ grid offset). Furthermore, there is a trade-off between the need for more forward FFTs and increased indirect storage and the computational complexity of an acceptable interpolation method. The third method discussed above has the disadvantage of requiring an FFT of twice the size or larger and twice the storage to achieve the performance of this process. This may not be as efficient as methods 1 and 2, but may be competitive in some cases, especially for relatively small FFT sizes. It should be clear from the above discussion that the three methods discussed above can be combined in various ways, for example the third method can be combined with the second method to achieve very small grid spacing without requiring a larger FFT size. In another aspect of the invention, a set of Doppler frequencies can be tested for more than one PRN corresponding to more than one received GNSS satellite signal without performing additional forward FFTs. That is, in the previous discussion, a forward FFT or several forward FFTs are performed on the data and then a set of inverse FFTs are performed to test various Doppler shifts and these all correspond to one specific satellite signal, i.e., one specific PRN. As indicated above, as part of the overall processing, the frequency samples are multiplied with the frequency samples of a PRN reference signal. This will occur after the Doppler shift operation explained above. This is because the PRN frequency samples are assumed to have zero frequency offset. A similar set of inverse FFTs can be performed on other PRNs using their corresponding frequency samples, and additional Doppler frequencies can again be tested, but another forward FFT corresponding to these additional PRNs need not be performed. In yet another aspect of the invention, instead of rotating or shifting the vector of frequency samples provided by performing a forward FFT on the signal samples, a similar operation can be performed on the frequency samples of the PRN reference signal. That is, a Doppler compensation is performed on the PRN frequency samples rather than on the signal frequency samples. One problem with this approach is that the product of the signal frequency samples and the Doppler compensated PRN samples will no longer be zero frequency even when assuming that the Doppler is exactly associated with the signal. Therefore, the inverse FFT will contain a frequency offset. However, taking the magnitude of the inverse FFT will remove the frequency component. Therefore, this approach is effective for applications that only perform incoherent summation of such inverse FFT vectors. One advantage of this approach is that the Doppler shifted PRN frequency samples can be pre-computed, so there is no need to perform any additional forward FFT on the signal data, as the previously mentioned approach would indicate (using Doppler shifted signal frequency samples).

10: System 12: Application processor 12A: Cache memory 14: Bus 16: Processor 16A: Static random access memory 17: Cell phone RF module 18: Antenna 20: Global navigation satellite system processor 21: Global navigation satellite system RF module 22A: Antenna/Global navigation satellite System antenna 22B: Antenna/GNSS system antenna 24: Dynamic random access memory 26: Input/output device 50: System/operating system 52: System on chip 54: System bus/bus 56: Dynamic random access memory 57: Non-volatile memory 58: Input/output control = 60: Input/output device 62: Sensor/RF component 63: Global navigation satellite system RF component 64: Cell phone RF component 66: Application processor 68: Global navigation satellite system processing system 70: Cache memory 72: Memory controller 74: Bus 76: Processor 78: Bus interface 101: Operation 103: Operation 105: Operation 107: Operation 109: Operation 111: Operation 113: Operation 115: Operation 150: Part 151: Antenna 153: Global navigation satellite system RF front end 155: RF analog-to-digital converter 157: Baseband sample This array/array 159: Arithmetic logic unit 201: Operation 203: Operation 205: Operation 207: Operation 209: Operation 211: Operation 213: Operation 215: Operation 217: Operation 219: Operation 251: Input 253: Baseband sample memory/memory 255: Discrete Fourier Transform Arithmetic Logic Unit 257: Memory/FFT Result Array 258: Output 259: Code Generator 261: Discrete Fourier Transform Arithmetic Logic Unit 263: Code Spectrum Memory 265: Multiplier 267: Inverse Discrete Fourier Transform Arithmetic Logic Unit 269: Correlation Post-Processing Operator 271: Memory/Integral Memory 301: Array 303: Operation 304: Operation 306: Operation 308: Partial Result Sample Array 311: Array 313: Operation 315: Operation 351: Phase Factor Array 353: Phase Factor Array/Array 355: Discrete Fourier Transform =Transformation operation 357: Discrete Fourier transform operation 361: First stage sample array 363: Operation 365: Operation 367: Operation 371: Postprocessor 373: Integral array 401: Code type 402: Polynomial type generator 404: Time shifter 406: Programmable phase division input 408 :CORDIC phase rotation 410:CORDIC phase rotation 412:CORDIC phase rotation 415:CORDIC phase diagram 417:Phase rotation 419:Phase rotation 421:Phase rotation 450:Global navigation satellite system processing system 451:Navigation chip 453:Global navigation satellite system receiver code 457:Logic module 458:Acquisition engine 459:Satellite signal generator 460:Digital front end 461:Timing and control module 462:Bus control module 463:Tracking engine 464:Clock phase-locked loop generation and gate control circuit system 465:RF analog-to-digital conversion Converter 466: ARM processor 467: ARM program and data memory 468: Baseband sample memory 469: Acquisition engine command memory 470: Fast Fourier transform program memory 471: Fast Fourier transform constant memory 472: Fast Fourier transform variable memory 473: Fast Fourier transform 474: Code spectrum generation memory 475: Coherent integral memory 476: IFFT memory 477: IFFT memory 478: IFFT variable memory 479: Non-coherent integral memory 501: Code forward matrix 502: Code forward matrix Array 503: Generator polynomial 505: Generator polynomial 507: Second input 509: Second input 511: Multiplexer 515: Register 517: Register 519: XOR logic gate 521: XOR logic gate 523: Secondary code bit 524: Code shifted forward by ten bits 526: Register 527: Left shift logic 529: Add sampling logic block 531: Register 533: Left shift logic 601: Operation 603: Operation 605: Operation 607: Operation 609: Operation 611: Operation 613: Operation 701: RF front end module 703: Digital front end 707: Full GNSS antenna 709: Bandpass filter 711: Low noise amplifier 713: Bandpass filter 715: Amplifier 717: Analog-to-digital converter 719: Clock generation phase-locked loop 721: CIC decimator 723: Clock divider 725: Clock divider 727: Down converter 729: CIC decimator 731: Sideband splitting down converter 951: Operation 953: Operation 955: Operation 957: Operation 959: Operation 961: Operation 963: Operation 965: Operation 967: Operation 969: Operation 971: Operation 973: Operation 975: Operation

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.

FIG. 1 is a block diagram showing an example of a data processing system including a GNSS processor and one or more application processors.

FIG. 2 is a block diagram showing an example of an embodiment including a GNSS processing system and one or more application processors and a cache memory.

FIG. 3 is a flow chart illustrating a method for sharing a cache memory between one or more application processors and a GNSS processor according to an embodiment.

FIG. 4 shows an example of a front end of a GNSS receiver that digitizes received GNSS signals according to an embodiment.

5A and 5B show an example of a method using array processing with several DFTs according to an embodiment.

FIG6 is a block diagram illustrating a frequency domain correlator architecture using array processing according to an embodiment.

FIG. 7 illustrates, in block diagram form, an example of a processing component for performing array processing according to one embodiment.

FIG8 illustrates, in block diagram form, an example of other processing components for performing array processing according to one embodiment.

9A, 9B, 9C and 9D show an example of processing components and a method that may be used to generate a PRN code spectrum for use with the array processing architecture shown in FIGS. 6, 7 and 8.

FIG. 10 shows an example of components that may be used in an embodiment of a GNSS receiver.

FIG. 11 is a flow chart showing a method according to an embodiment.

FIG. 12 shows an example of a GNSS receiver with only L5 WB band in block diagram form.

50: System/Operating System

52: System on Chip

54: System bus/bus

56: Dynamic random access memory

57: Non-volatile memory

58: Input/output controller

60: Input/output device

62: Sensor/RF components

63: Global Navigation Satellite System Radio Frequency Components

64: Cellular phone RF components

66: Application Processor

68: Global Navigation Satellite System Processing System

70: Cache memory

72:Memory controller

74:Bus

76: Processor

78: Bus interface

Claims (67)

A GNSS processing system includes: an antenna input for receiving a GNSS signal in an E5 frequency band; a low noise amplifier (LNA) coupled to the antenna input to amplify the GNSS signals; a radio frequency (RF) analog-to-digital converter (ADC) coupled to an output of the LNA, the RF ADC and the LNA being used to receive and process the GNSS signal in the E5 frequency band; a circular memory buffer coupled to an output of the RF ADC to receive and store digitized GNSS sample data, the circular memory buffer storing digitized GNSS sample data greater than 1 millisecond and digitized GNSS sample data less than 2 milliseconds. A GNSS processing system as claimed in claim 1, wherein the cyclic memory buffer stores the digitized GNSS sample data in an array of rows and columns, and the sample data is presented in an order of columns, that is, in a time order, wherein 1 millisecond is the frame duration of a main code of a modern GNSS signal, and the modern GNSS signals are further covered by a subcode at a 1 KHz rate. A GNSS processing system as claimed in claim 2, further comprising: a GNSS processor comprising an acquisition engine and a tracking engine, the acquisition engine comprising a set of DFT ALUs, the set of DFT ALUs processing the digitized GNSS sample data in the array and generating an intermediate output that does not require transposing the data in the array. A GNSS processing system as claimed in claim 3, wherein a first group of DFT ALUs in the group of DFT ALUs uses a time extraction method to generate the intermediate output stored in a variable memory, and a second group of DFT ALUs in the group of DFT ALUs uses the intermediate output to generate an output stored in an FFT result memory. A GNSS processing system as claimed in claim 4, wherein the cyclic memory buffer includes a first cyclic memory buffer for storing an A sideband in an E5 frequency band and a second cyclic memory buffer for storing a B sideband in the E5 frequency band. A GNSS processing system as claimed in claim 1, wherein the cyclic memory buffer is a dual-port memory. A GNSS processing system as claimed in claim 6, wherein the additional memory used to store data exceeding 1 millisecond in the loop memory buffer is based on the processing time of the discrete Fourier transform of the digitized GNSS sample data. A method for processing GNSS signals, the method comprising: receiving GNSS signals; digitizing the received GNSS signals and providing an output of GNSS sample data from an analog-to-digital converter (ADC), the GNSS sample data comprising at least one of (1) GNSS sideband A sample data of a received GNSS signal and (2) GNSS sideband B sample data of the received GNSS signal; performing at least one of the following two items: (1) calculating a first set of DFT of the GNSS sideband A sample data to provide a first set of results, and (2) calculating a second set of DFTs of the GNSS sideband B sample data to provide a second set of results; performing at least one of the following two items: (1) calculating a third set of DFTs of the GNSS sideband A primary PRN code data, the GNSS sideband A primary PRN code data being adjusted due to code Doppler and carrier Doppler before the third set of DFTs, the GNSS sideband A primary PRN code data comprising at least one of the two components in the GNSS sideband A, the third set of DFTs providing a third set of results; and (2) calculating the GNSS sideband B primary PRN code data a fourth set of DFTs, prior to which the GNSS sideband B primary PRN code data is adjusted due to code Doppler and carrier Doppler, the GNSS sideband B primary PRN code data comprising at least one of two components in the GNSS sideband B, the fourth set of DFTs providing a fourth set of results; performing at least one of the following two items: (1) using a DFT to calculate a first set of correlations on a complex conjugate of a product of the first set of results and a complex conjugate of the third set of results to provide a fifth set of results; and (2) using a DFT to calculate a first set of correlations on a complex conjugate of a product of the second set of results and a complex conjugate of the fourth set of results. The complex conjugate of the set of results uses a DFT to calculate a second set of correlations to provide a sixth set of results; performing at least one of the following two items: (1) integrating the fifth set of results with at least one previous sum of the GNSS sideband A; and (2) integrating the sixth set of results with at least one previous sum of the GNSS sideband B, wherein the integration includes at least one of the following two items: (1) storing at least one new sum of the GNSS sideband A components in a single hypothetical memory and (2) storing at least one new sum of the GNSS sideband B components in the single hypothetical memory. The method of claim 8, wherein the fourth set of results includes IDFT results of two components of the GNSS sideband A, and the sixth set of results includes IDFT results of two components of the GNSS sideband B. The method of claim 9, wherein the GNSS sideband A sample data is stored in a first circular memory buffer, and the GNSS sideband B sample data is stored in a second circular memory buffer. The method of claim 10, wherein the GNSS sideband A sample data is stored in the first circular memory buffer in a format of an array of rows and columns, and the GNSS sideband B sample data is stored in the second circular memory buffer in the format of the array of rows and columns. The method of claim 11, wherein the GNSS sample data is processed in the following manner to separate the GNSS sideband A sample data from the GNSS sideband B sample data: (1) for the GNSS sideband A, the samples centered at a first frequency are shifted up to a first offset frequency and a low-pass filter is applied to capture a first bandwidth of data and the output of the low-pass filter is decimated to a lower sampling rate; and (2) for the GNSS sideband B, the samples centered at the first frequency are shifted down to the first offset frequency and a low-pass filter is applied to capture a second bandwidth of data and the output of the low-pass filter is decimated to a lower sampling rate. The method of claim 11, wherein the computational operation does not require a separate operation to transpose or reconfigure the sample data or the generated code spectrum data when input to the first set of associations and the second set of associations. The method of claim 11, wherein a code generator performs at least one of the following two items: (1) generating the GNSS sideband A main PRN code data every millisecond when acquiring and tracking GNSS signals, and not storing the GNSS sideband A main PRN code data after completing Fourier transform; and (2) generating the GNSS sideband B main PRN code data every millisecond when acquiring and tracking the GNSS signals, and not storing the GNSS sideband B main PRN code data after completing Fourier transform. The method of claim 14, wherein when receiving the GNSS signals, the integration is non-coherent during at least a portion of an acquisition phase. A system for processing GNSS signals, the system comprising: an RF analog-to-digital converter (ADC) for generating a digital representation of received GNSS signals; a baseband sample memory for storing the digital representation of the received GNSS signals as digitized GNSS sample data, the baseband sample memory being configured to store an array of the digitized GNSS sample data in N2 rows and N1 The digitized GNSS sample data in the array are stored in the baseband sample memory in a row order and N2 is greater than N1, the row order contains the digitized GNSS sample data received in a time period including a first time period and a second time period, so that a first row in the row order contains the digitized GNSS sample data received during the first time period and a second row in the row order contains the digitized GNSS sample data received during the first time period. a second row after the first time period containing digitized GNSS sample data received during the second time period, the second time period being subsequent in time to the first time period, the baseband sample memory being coupled to the RF ADC; an arithmetic logic unit (ALU) configured to perform a discrete Fourier transform (DFT) operation, the ALU being coupled to the baseband sample memory, the ALU being configured to perform a discrete Fourier transform (DFT) operation in parallel and simultaneously in time. Performing N1 DFTs, wherein each of the N1 DFTs contains N2 points in the DFT and the output of the N1 DFTs is stored in a portion of a result sample array, and wherein the set of ALUs is configured to then perform N2 DFTs, wherein each of the N2 DFTs contains N1 points from the portion of the result sample array, and the N2 DFTs provide an output stored in a DFT result array arranged in row order. A system as claimed in claim 16, wherein the baseband sample memory is configured as a loop memory buffer for storing the array. A system as claimed in claim 17, wherein the N1 DFTs use the same operation and the same program control instructions to enable the group of ALUs to operate on different data. A system as claimed in claim 18, wherein the N2 DFTs are performed continuously over time, and wherein the cyclic memory buffer stores more than one frame of a virtual random GNSS code, the frame being greater than 1 millisecond. A system as claimed in claim 18, wherein the N1 DFTs and the N2 DFTs use a time decimation method, and wherein N1 is an integer value of one of 5, 10, 20, or 40. A system as claimed in claim 18, wherein a change from column order to row order avoids a reordering algorithm, the change being caused by a combination of the N1 DFTs followed by the N2 DFTs. A system as claimed in claim 18, wherein a GNSS code generator is configured to generate a GNSS code, and the ALU performs a DFT on the GNSS code to provide a code spectrum result data, the code spectrum result data is stored in a code spectrum memory in a row order, and the code spectrum result data includes GNSS PRN code data with frequency shift and/or time shift. A system as claimed in claim 22, wherein the set of ALUs is configured to multiply the code spectrum result data by the output stored in the DFT result array to generate a product array. The system of claim 23, wherein the set of ALUs is configured to perform an inverse DFT on the product array using a frequency decimation method. The system of claim 24, wherein the inverse DFT comprises: (1) in a first phase, N2 DFTs with conjugate inputs, each of the N2 DFTs containing N1 points; and (2) in a second phase after the first phase, N1 DFTs, each of the N1 DFTs containing N2 points. A system as claimed in claim 17, wherein the baseband sample memory is a dual-port memory. A system as claimed in claim 22, wherein the GNSS code generator generates a virtual random code for each GNSS SV in view every millisecond when a virtual random code is needed during an acquisition phase, and does not store the generated virtual random code after using the generated virtual random code, and the generated virtual random code is used to generate the GNSS code spectrum. The system of claim 27, wherein the GNSS code spectrum is aligned in both frequency and phase to appropriate locations in memory so that code phase and frequency shift hypotheses associated with the received GNSS signals match. A system as claimed in claim 28, wherein the alignment is performed by CORDIC hardware. A system as claimed in claim 16, wherein the digitized GNSS sample data is stored in row order rather than column order. A system for processing GNSS L5 band signals, the system comprising: an RF analog-to-digital converter (ADC) for generating a digital representation of received GNSS signals; a baseband sample memory for storing the digital representation of the received GNSS signals, the baseband sample memory coupled to the ADC; a GNSS processing system coupled to the baseband sample memory for processing the received GNSS signals; The digital representation of the received GNSS signal, the GNSS processing system is configured to process four GNSS signal components of a GNSS signal to non-coherently integrate all four GNSS signal components to generate non-coherent integration data for each of the four GNSS signal components and store the non-coherent integration data in a single hypothetical memory to obtain the GNSS signal. A system as claimed in claim 31, wherein the single hypothetical memory is less than 2 million memory bytes, and wherein the four GNSS signal components include a Galileo E5AI signal component, a Galileo E5BI signal component, a Galileo E5BQ signal component and a Galileo E5AQ signal component, or include four GNSS signal components used in a Beidou/Compass B2 system, or include both the Galileo E5 signal component and the Beidou/Compass B2 signal component. The system of claim 32, wherein the GNSS processing system processes GNSS signals received from at least two GNSS clusters, the at least two GNSS clusters comprising: a Galileo E5 cluster of GNSS SVs, a L5 GP cluster of GNSS SVs, a GLONASS K2 cluster of GNSS SVs, a QZSS cluster of GNSS SVs, and a BeiDou B2 cluster of GNSS SVs. The system of claim 31 further comprises: a code generator for generating GNSS PRN codes during the acquisition and tracking of GNSS signals, but not storing such GNSS PRN codes after the tracking is completed. A system as claimed in claim 34, wherein the code generator generates more than two primary PRN code bits in a clock cycle during the acquisition and tracking period. A system as claimed in claim 35, wherein the code generator generates more than two main PRN code bits in a clock cycle by a calculation using a calculated code forward matrix, the calculated code forward matrix being derived from an N-fold multiplication of a code polynomial matrix for a given GNSS cluster and GNSS signal components in that GNSS cluster, N representing a number of main PRN code bits generated in a clock cycle. A system as claimed in claim 36, wherein the GNSS processing system shares a memory with one or more processors, and the GNSS processing system, cache memory and one or more application processors are all disposed on the same single integrated circuit. The system of claim 37, wherein the GNSS processing system includes an acquisition engine and a tracking engine, and the acquisition engine includes processing logic to receive a GNSS sample data array arranged in a row order or a column order according to a reception time, and the processing logic is used to perform a DFT on the GNSS sample data array using a time decimation algorithm to generate frequency domain results, the frequency domain results are multiplied by a code spectrum of a GNSS PRN code of a GNSS SV in view, and then in the processing logic, the products of the frequency domain results and the code spectrum are processed by an IDFT using a frequency decimation algorithm to generate hypotheses of possible acquired GNSS signals that are incoherently accumulated in the single hypothesis memory. A system as claimed in claim 38, wherein the GNSS sample data array is stored in two cyclic memory buffers, the two cyclic memory buffers comprising a first cyclic memory buffer for storing A-band GNSS sample data and a second cyclic memory buffer for storing B-band GNSS sample data, wherein a plurality of GNSS clusters can be received in at least one of the frequency bands. A system as claimed in claim 36, wherein a GNSS master PRN code from an output of the code generator is frequency shifted and time shifted to produce a code spectrum prior to applying a set of DFTs using a time decimation algorithm, the code spectrum being multiplied by a frequency domain result obtained from applying a set of DFTs to a received GNSS signal using a time decimation algorithm. A system as claimed in claim 39, wherein a GNSS master PRN code from an output of the code generator is frequency shifted and time shifted to generate the code spectrum. A system as claimed in claim 38, wherein an order in the array is changed by a series of said DFTs such that no transposition or reconfiguration of the data is required when performing said IDFTs. A system as claimed in claim 42, wherein the series of DFTs avoids the use of memory or processing resources that would otherwise be used for the transposition or reconfiguration. A system as claimed in claim 31, wherein the GNSS processing system does not receive and acquire L1 GNSS signals. A system for processing GNSS signals; the system includes: an analog-to-digital converter (ADC) for generating a digital representation of a received GNSS signal; a baseband sample memory for storing the digital representation of the received GNSS signals, the baseband memory coupled to the ADC; a GNSS processing system coupled to the baseband sample memory for processing the digital representation of the received GNSS signals, the GNSS The processing system obtains up to four GNSS signal components by non-coherently integrating up to four GNSS signal components of a GNSS signal in an array processing system within a time period, the array processing system being located in an acquisition engine in the GNSS processing system and the array processing system receiving GNSS sample data from the baseband memory, and the GNSS sample data being formatted into a row and column array having a plurality of rows and a plurality of columns. A system as claimed in claim 45, wherein the array processing system includes processing logic that performs a set of DFTs using a time decimation algorithm followed by performing a set of inverse DFTs using a frequency decimation algorithm. A system as claimed in claim 46, wherein an output from the array processing system provides a frequency and a GNSS SV identifier stored in a hypothesis memory for integrating a hypothesis of a GNSS signal. The system of claim 45, wherein the array processing system receives the GNSS sample data in a first order and generates an output in a second order different from the first order, and wherein the first order is one of a row order or a column order in the row and column array, and the second order is one of the column order or the row order, and wherein the first order and the second order are based on the time at which the GNSS sample data is received. A system as claimed in claim 48, wherein the GNSS sample data is stored in two cyclic memory buffers in the row and column arrays, the two cyclic memory buffers including a first cyclic memory buffer for storing a first GNSS signal component from a GNSS SV sample data and a second cyclic memory buffer for storing a second GNSS signal component from the GNSS SV sample data, the first cyclic memory buffer and the second cyclic memory buffer being coupled to the array processing system. A system as claimed in claim 45, wherein the GNSS processing system does not receive and acquire L1 GNSS signals. A GNSS receiver, comprising: a radio frequency (RF) receiver, comprising at least a first RF filter and a low noise amplifier (LNA), wherein the low noise amplifier is tuned to only a L5 WB band to receive L5 WB GNSS signal; an analog-to-digital converter (ADC) coupled to the LNA to generate GNSS sample data, the GNSS sample data stored in a baseband sample memory, wherein the RF receiver is the only GNSS receiver in the GNSS receiver; and wherein the baseband sample memory includes a cyclic memory buffer coupled to an output of the ADC to receive and store the GNSS sample data, the cyclic memory buffer storing digitized GNSS sample data greater than 1 millisecond and digitized GNSS sample data less than 2 milliseconds. A GNSS receiver as claimed in claim 51, wherein the RF receiver does not include an amplifier for other GNSS signals outside the L5 WB band, and wherein the RF receiver includes the first RF filter coupled to a GNSS antenna, and an output of the first RF filter is coupled to an input of the LNA and an output of the LNA is coupled to a second RF filter. A GNSS receiver as claimed in claim 52, wherein an input of a first amplifier is coupled to an output of the second RF filter, and an output of the first amplifier is coupled to the ADC, and wherein the LNA and the first RF filter are disposed on a first IC, and the ADC and the first amplifier are disposed on a second IC. A GNSS receiver as claimed in claim 53, wherein the GNSS receiver further comprises: a sideband splitting downconverter that separates a GNSS sideband A sample data from a GNSS sideband B sample data; and wherein the second RF filter is disposed in the first IC. A GNSS receiver as claimed in claim 54, wherein the cyclic memory buffer comprises: a first cyclic memory buffer for storing the GNSS sideband A sample data; and a second cyclic memory buffer for storing the GNSS sideband B sample data, and wherein the cyclic memory buffer is a dual port memory. A GNSS receiver as claimed in claim 55, wherein the RF receiver does not include an RF mixer. A GNSS receiver as claimed in claim 56, wherein the RF receiver does not include an RF reference local oscillator, and wherein the GNSS antenna is tuned only to the L5 WB band. A GNSS receiver as claimed in claim 56, wherein the sideband splitting downconverter generates the GNSS sideband A sample data configured as a first row and column array, and generates the GNSS sideband B sample data configured as a second row and column array. A GNSS receiver as claimed in claim 56, wherein the RF receiver is tuned to receive GNSS signals centered at 1191.795 MHz, and the L5 WB GNSS signals have a chip rate of 10.23 MHz. A GNSS receiver as claimed in claim 58, wherein the GNSS antenna is the only GNSS antenna in the GNSS receiver, and wherein the RF receiver is tuned to receive GNSS signals centered at 1191.795 MHz and the L5 WB GNSS signals have a chip rate of 10.23 MHz. A system for processing GNSS signals, the system comprising: an analog-to-digital converter (ADC) for generating a digital representation of a received GNSS signal in an L5 WB GNSS band; a baseband sample memory for storing the digital representation of the received GNSS signals, the baseband sample memory coupled to the ADC; a GNSS processing system coupled to the baseband sample memory to process the digital representation of the received GNSS signals, the GNSS processing system being configured to receive and process at least one of four GNSS signal components of an L5 WB band GNSS signal without using an L1 GNSS signal. The system of claim 61, wherein the system comprises only a single GNSS antenna tuned to the L5 WB band centered at 1191.795 MHz, and the received GNSS signals have a chip rate of 10.23 MHz or a chip rate significantly higher (e.g., by a factor of 2) than the L1 GPS chip rate of 1.023 MHz. A system as claimed in claim 62, wherein the baseband sample memory stores the digital representation in a row and column array, wherein the row and column array is arranged in columns according to a reception time. A system as claimed in claim 62, wherein the baseband sample memory stores the digital representation in a row and column array, wherein the row and column array is arranged in rows according to a reception time. A system as claimed in claim 63, wherein the GNSS processing system processes the received GNSS signals without transposing or reconfiguring the data in an array containing the data by a series of DFTs, the series of DFTs comprising a first set of DFTs performed using a decimation in time method and then comprising a second set of DFTs performed using a decimation in frequency method. A system as claimed in claim 61, wherein an initial signal is acquired in a coarse time acquisition mode, other signals are acquired in a precise time acquisition mode, and all signals are tracked in a tracking mode. A system as claimed in claim 66, wherein the use of dedicated hardware is reduced when in a coherent tracking mode.