Real-time GNSS software receivers

	Challenges, status, and perspectives

The idea of a software receiver is to sample the analog input signal as close to the antenna as possible and to implement the complete the data processing in software. Thus, the hardware is reduced to the minimum while all the digital signal processing is done by the mean of a microprocessor.

One advantage of a software receiver lies clearly in the low cost opportunity as the system resources are already available. Another benefit resides in the flexibility for adapting to new signals and frequencies.

In this paper, we will first give a very short overview of the history of software receivers. Then, the term ‘software receiver’ will be explained and the different classes of software receivers presented. The third section is dedicated to some of the challenges that the development of software receivers is confronted with. The next section provides an overview and a short description of the current status related to the algorithms of code and carrier generation, acquisition, tracking, and baseband processing for software receivers. Finally, the last section provides some concluding remarks and a research outlook. This article is a short version of the paper presented at the ENCGNSS 2009 conference in Naples [1].

History

During the 1990’s, a U.S. Department of Defense (DoD) project named Speakeasy was undertaken with the objective of showing and proving the concept of a programmable waveform, multiband and multimode radio [2]. The Speakeasy project demonstrated the approach that underlies most software receivers: the analog to digital converter (ADC) is placed as close as possible to the antenna and all baseband functions are processed in a programmable microprocessor using software techniques. The software implementation of all baseband functions offers a great flexibility that allows rapid changes and modifications. This property is an advantage in the fast changing environment of GNSS receivers as new radio frequency (RF) bands, modulation types, bandwidths, and spreading/dispreading and baseband algorithms are regularly introduced.

Software receiver: definition and types

The definition of a software receiver (SR) always brings some confusion among researchers and engineers in the field of communications and GNSS. In this paper we will consider the widely accepted SR definition in the field of GNSS, that is, a receiver in which all the base-band signal processing is performed in software by a programmable microprocessor. Nowadays, software receivers can be grouped in three main categories as shown in Figure 1.

The first category regroups the receivers that are based on Field Programmable Gate Arrays (FPGAs), which are sometimes also referred to the domain of SR. These receivers can be reconfigured in the field by software or a dedicated microcontroller can be implemented into the FPGA[3] ADDIN ZOTERO_ITEM {“sort”:true ,”citationItems”:[{“uri”:[“http://zotero. org/users/local/nU9p5ORW/items/ I4TT3WA4”]}]} [3]. The second category, post-processing receivers, includes, among others, the countless software tools or lines of code for testing new algorithms and for analyzing the GNSS signal. Finally, the third category is the real-time capable software receivers group that will be further considered in this paper.

Challenges

The following chapter highlights some of the main challenges related to software receivers. This includes the problem of the high data rate when working with a nearly ideal implementation and also talks about the high processing power requirements for the base-band processing algorithms.

Data rate

The ideal software receiver places the ADC as close as possible to the antenna in order to reduce the hardware parts to the minimum (see Figure 2). In that sense, the most straightforward approach consists in digitizing the data directly at the antenna. But as the Nyquist theorem must be fulfilled, this translates into a data rate that is, for the time being, too high to be processed by a microcontroller.

Considering the GPS L1 signal and assuming 2 quantization bit per sample, this leads to the following values:

In order to reduce the data throughput, a solution such as a low intermediate frequency (low-IF) or a sub-sampling analog front-end can be chosen. In a low-IF front-end, the incoming signal is down-converted to an intermediate frequency of several megahertz. This allows obtaining a data rate that can be more easily handled by a microcontroller.

The sub-sampling technique exploits the fact that the effective signal bandwidth in a GNSS signal is much lower than the carrier frequency. Therefore, not the carrier frequency but the signal bandwidth must be respected by the Nyquist theorem. In this case, the modulated signal is undersampled to achieve frequency translation via intentional aliasing. But this solution is difficult to implement due to current hardware and resources limitations. Again, if the GPS L1 signal is taken as an example with 2 quantization bit per sample, this leads to the following values:

Bandwidth GPS L1 = 2 MHz

Bandwidth = 4 MHz
Data rate ≥ 8 MBit/s = 1 MByte/s

Complexity of baseband operations

Considering a low- IF based architecture, the ADC provides a data stream that is first down-converted to base-band to remove the remaining Doppler frequency offset. The signal is then multiplied with several code replicas (generally Early, Prompt, and Late) and finally accumulated. An example of a real data IF architecture is shown in Figure 3.

Former studies [4] demonstrated that, assuming that an integer operation and a multiplication take respectively 1 and 14 CPU cycles for an Intel Pentium 4 processor, the base-band operations (without carrier and code generation) would require at least a 3 GHz Intel Pentium 4 processor at 100% CPU load. Therefore, such an architecture is not suitable as a real-time software solution.

Current implementations

A major problem of the software architecture is the important amount of CPU cycles needed for executing the base-band operations. In order to reduce this number, two alternate strategies can be found: the first one applies Single Instruction Multiple Data (SIMD) operations while the second one utilizes the bitwise representation of the signal.

Single Instruction Multiple Data (SIMD)

In 1995, Intel introduced Single Instruction Multiple Data (SIMD) operations under the name of Multi Media Extension (MMX). The SIMD are mathematical instructions that operate on vectors of data and perform integer arithmetic on eight 8-bit, four 16- bit, or two 32-bit integers packed into a MMX register (see Figure 4). Later SIMD extensions, SSE, SSE2, and SSE3 include SIMD floating point operations and expand the type of integer operations.

SIMD operations are well fitted to execute the same mathematical operation on several sets of data. In particular, they can be used to perform the PRN code mixing and the accumulation concurrently for all code replicas. With the help of further optimizations, such as instruction pipelining, more than 600% performance improvement with the SIMD operations compared to the standard integer operations can be observed [5]. For this reason, most of the implementations of software receivers with real-time processing capabilities are using SIMD operations.

Bitwise Operations

Bitwise operation (or vector processing) exploits the bit representation of the incoming signal. Figure 5 shows a typical data storage scheme for vector processing. The sign information is stored in the sign word while the remaining bit(s) representing the magnitude is (are) stored in the magn word(s). The objective is to take advantage of the high parallelism and speed of the bitwise operations for which a single integer addition or multiplication is translated into simple parallel logical operations. The carrier mixing stage is reduced to one or a few simple logical operations that can be performed concurrently on several bits. In the same way, the PRN code removal only affects the sign word

The inherent drawback of this approach is the lack of flexibility: the complexity of the process becomes bit-depth dependent and the signal quantification cannot be easily changed without important modification of the software code. To overcome this limitation, a combination of bitwise processing and distributed arithmetic was proposed, as described in [6].

Code generation

The real-time generation of the pseudorandom noise (PRN) code is too power consuming to be implemented in a software receiver. The most efficient way (in terms of processing load) is to pre-generate the codes, assuming a zero Doppler shift,. and store them in memory.

As the incoming signal code phase is random, the beginning of the first code chip is in general not aligned with the beginning of stored code and may occur at any position. To overcome this issue, either all the possible phases can be stored in memory or the code can be shifted appropriately during the tracking phase. While the first approach increases the memory requirements, the second requires further data processing. This approach is very popular in the domain of software receiver and can be found in several solutions: [4], [7], [8], [9], [10].

Carrier generation

The generation of a local carrier frequency is necessary to perform the Doppler removal for every channel. Several techniques exist to reduce the computational load for the carrier generation: the values for the carrier can be pre-generated and then stored in lookup tables. As it would require several gigabytes of memory to store all the possible frequencies, the values are recorded on a coarse frequency grid with no phase offset. This method is very popular in the domain of software receivers and many solutions take advantage of it to avoid the power hungry real-time carrier generation [8], [11], [12].

Outlook

Software receivers have found their place in the field of algorithm prototyping and testing for a long time. Nowadays they also play a key role for certain special applications. What remains unclear today is if they will enter and change drastically the embedded market or succeed as generic high-end receivers.

A software GNSS receiver offers different advantages including design flexibility, faster adaptability, faster time-to-market, higher portability and easy optimization at any algorithm stage. However, a major drawback persists in the high CPU load.

Many different companies and universities have projects running that aim at optimizing and developing new algorithms and methods for a software implementation. The development not only includes the software level, but also enlarges in the direction of using additional hardware that is already available on a standard PC (for example, using the high performance graphic processing unit (GPU) for calculating the local carrier [13]).

References

M. Baracchi-Frei, G. Waelchli, C. Botteron, and P. Farine, “Real-Time GNSS Software Receiver: Challenges, Status, and Perspectives,” ENCGNSS 2009, Naples: 2009.

R. Lackey and D. Upmal, “Speakeasy: The Military Software Radio,” IEEE Communications Magazine, May. 1995, pp. 56-61..

“Altera NIOS II Processor” Available: http://www.altera.com/products/ip/ processors/nios2/ni2-index.html..

G.W. Heckler and J.L. Garrison, “Architecture of a Reconfigurable Software Receiver,” ION GNSS ITM, 2004..

G.W. Heckler and J.L. Garrison, “SIMD correlator library for GNSS software receiver,” GPS Solutions, Oct. 2006, pp. 269-276..

G. Waelchli, M. Baracchi-Frei, C. Botteron, and P. Farine, “Distributed Arithmetic for Efficient Base-Band Processing in Real-Time GNSS Software Receivers,” Journal of Electrical and Computer Engineering, vol. 2010..

Y. Chen and J. Juang, “A GNSS Software Receiver Approach for the Processing of Intermittent Data,” 2007..

A. Fridmann and S. Semenov, “Architectures of Software GPS Receivers,” GPS Solutions, vol. 3, 2000, pp. 58-64..

M.L. Psiaki, “Real-Time Generation of Bit-Wise Parallel Representation of Over-Sampled PRN Code,” IEEE Trans. on Wireless Communication, vol. 5, Mar. 2006..

J. Tian, Q. HongLei, Z. JunJie, and L. Yang, “Real-time GPS Software Receiver Correlator Design,” 2007..

T. Pany, S.W. Moon, M. Irsigler, B. Eissfeller, and K. Fürlinger, “Performance assessment of an under sampling SWC receiver for simulated high bandwidth GPS/Galileo signals and real signals,” ION GPS/GNSS: 2003..

S. Charkhandeh, M. Petovello, R. Watson, and G. Lachapelle, “Implemenation and Testing of a Real- Time Software-Based GPS Receiver for x86 Processors,” ION NTM: 2006..

M. Petovello, C. O’Driscoll, G. Lachapelle, D. Borio, and H. Murtaza, “Architecture and Benefits of an Advanced GNSS Software Receiver,” International Symposium on GPS/GNSS: 2008.

		Marcel Baracchi University of Neuchâtel, Switzerland marcel.baracchi@unine.ch

Grégoire Waelchli Ecole Polytechnique Fédérale de Lausanne(EPFL), Electronic and Signal Processing Laboratory, Neuchâtel, Switzerland gregoire.waelchli@epfl.ch

Cyril Botteron Ecole Polytechnique Fédérale de Lausanne (EPFL), Electronic and Signal Processing Laboratory, Neuchâtel, Switzerland cyril.botteron@epfl.ch

Pierre-André Farine Professor,Ecole Polytechnique Fédérale de Lausanne(EPFL), Electronic and Signal Processing Laboratory, Neuchâtel, Switzerland pierre-andre.farine@epfl.ch

	My Coordinates	EDITORIAL
	His Coordinates	Orhan Altan, President, ISPRS
	News	INDUSTRY | GPS | GALILEO UPDATE | LBS | GIS | REMOTE SENSING
	Mark your calendar	MAY 2010 TO NOVEMBER 2010