Speeding-up acquisition time in modern GNSS receivers by exploiting an FPGA hardware accelerator: analysis, design and implementation in a proof-of-concept prototype

This thesis was carried out in collaboration with SITAEL, the largest privately-owned Space Company in Italy leading the development of the Small Satellites sector. A core feature for an artificial satellite is the Positioning System, that allows it to independently know its position in space. The implementation of this functionality involves the design of a GNSS (Global Navigation Satellite Systems) receiver. It lets the user to acquire, decode and elaborate the navigation messages provided by the GNSS satellite constellations deployed around the world. This field is one of the most actual themes in the research, as new satellite constellations for GNSS are actually being deployed and new GNSS signals are planned to be available from 2020 (L5, L2C) to 2030 (L1C). The aim of this thesis is to study and implement methods to speed-up the acquisition of GNSS signals with FPGA hardware accelerators, focusing on GPS (Global Positioning System). An environment is set up for the development of GNSS receivers. It consists primarily of an SDR (Software Defined Radio) reference receiver and an original set of Scilab simulations to functionally validate the studied algorithms. Then an hardware environment is set up to design, test and load the proposed algorithms on FPGA. It consists in a Universal Software Radio Peripheral (USRP) that performs signal acquisition. Data is then is routed in its internal FPGA. That FPGA is chosen to host the designed acquisition correlators and to send the results to a personal computer via the ethernet port. The software GPS-SDR-SIM is chosen to generate a valid GPS test data stream. The environment permit to build and validate the so-called Acquisition Block of a GNSS receiver, whose function is to detect the presence/absence of data from a given satellite in the incoming signal, accounting for problems as the Doppler frequency shift due to the relative satellite/receiver speed. Such a block has been designed with the most advanced theory of Frequency Domain Parallel Correlation. It uses FFTs to perform a parallel test of all the code displacements between the incoming signal and the code replica. It gives an output vector that contains the correlation between signal and code for all the code bins. It is shown how the so-called Parallel Code Phase Search (PCPS) algorithm can be implemented on FPGAs to acquire the currently in-use GPS L1 C/A signals. The advantage of its use is the speed gain given by the its intrinsic parallelism, at the cost of larger area consumption compared to non-parallel algorithms. We were able to implement a single branch of the algorithm in the target device and it is shown how many enhancement can improve timing and area results (like pipelining the architecture, performing FFT Splitting and using fixed point streaming FFT cores). The achieved results are presented both for on-earth and space executions. Modern GNSS systems are then presented, focusing on the design optimizations that can lead to an FPGA implementation of their acquisition stages. In fact these next-generation signals have a structure that is similar to the current ones but they uses longer primary codes that are made longer by the use of secondary codes. We used many algorithms discussed in literature (Correlation Splitting, FFT splitting, Hypercodes etc) to show how the acquisition process of modern GNSS signals can be splitted to reduce the problem to a succession of modified L1 C/A acquisition blocks (like the designed one) with great results. In particular it has been shown how the acquisition of L5, L2C and L1C signals can be reduced to the problem of performing a 40920-point correlation using radix-2 FFTs. This operation can lead to the design of a multi-signal receiver that is based on a single, optimized, computational core