# Hard SyDR: A Benchmarking Environment for Global Navigation Satellite System Algorithms +
## 2 Background and Motivation
### GNSS Processing Stages and Computational Complexity  
A processing chain embedded in GNSS receiver can be simplified into the following four main processing stages, which are summarized in Figure 1 and as follows [5]:  
1. **Acquisition:** Any new signal scheduled for tracking must first pass through an acquisition stage, which identifies the visible satellites in the sky and searches for the initial Doppler and code shifts of each of the satellites visible in the sky at the location of interest. The size of the acquisition search space depends on the current status of the GNSS receiver (i.e., cold/warm/hot start), and of the possible access to Assisted-GNSS data (e.g., cellular radio, internet). If this stage fails due to the signal not being present or being suppressed by noise, the receiver will not proceed to the next stage. 2. **Tracking:** Once the coarse parameters for the Doppler and code shifts have been found, their values must be fine-tuned and continuously tracked to precisely align the signal replica with the incoming signal to retrieve the navigation message (i.e., data bits). If the tracking is lost, the receiver reverts to the acquisition stage, though a very limited search space is needed in most cases. Otherwise, the receiver remains in this stage until shutdown. 3. **Decoding:** Recovery of the navigation data bits becomes possible when the replica perfectly aligns with the incoming signal. These bits encode the timestamp necessary to compute the measurements used for user positioning. 4. **Positioning:** Using the tracking measurements and the decoded navigation data from multiple satellites, the receiver can recompose the _pseudoranges_ and compute a position (e.g., Standard Point Positioning (SPP), Differential GNSS (DGNSS), Precise Point Positioning (PPP)). Steps 1, 2, and 3 should be performed concurrently for tracking each signal. In this paper, we encapsulate these functions within the concept of _channels_, where each channel is responsible for tracking the signal from one satellite. The acquisition is often highlighted as the most computationally complex part [1] as it might involve a significant number of arithmetic operations for performing convolutions. While the use of the FFT in modern receivers dramatically reduces this complexity, from \(O(n^{2})\) (Serial Search) to \(O(n\log n)\) (Parallel Code Phase Search (PCPS)) [1], the acquisition stage still requires more operations than the tracking stage. Moreover, using the FFT in hardware has proven challenging, as discovered in our experiments reviewed in Section 5. As tracking \"only\" requires a few correlation operations, its computational complexity will in any case be lower than the one in the acquisition stage. The actual complexities of the DSP operations of a GNSS receiver are highly dependent on the scenario assumptions (e.g., algorithms used, environment, Assisted-GNSS, user dynamics, etc.) [1]. Nevertheless, using the SyDR platform, it is possible to list these assumptions and have a better idea of the actual complexity in processing time. Absolute processing times are irrelevant, as they are affected by many factors (e.g., hardware technology, operating system, programming language). However, relative processing times can enable comparison between different algorithms of the same processing stage or between processing stages. The former allows for identifying an optimal algorithm based on predefined KPIs (e.g., complexity, quality, reliability); the latter helps us expose critical points of the processing chain with high computational complexity. Optimizing these points can lead to large energy savings with minimal negative impact on the results. In Figure 2, we review the processing time needed for the different functions of SyDR. The processing is based on real data recorded in our lab and replayed in post-processing within SyDR.