# Concatenated Coding for GNSS Signals in Urban Environments
## 3 Concatenated Coding Scheme for GNSS Messages
### Complexity Evaluation  
Since the decoding process is more computationally complex than the encoding process, only decoding complexity was considered in this work for simplicity. The complexity comparison results of the proposed RS-LDPC concatenation code and the non-binary LDPC code are provided in terms of the number of addition, multiplication, and comparison operations.  
For the RS-LDPC concatenation code, the complexity was evaluated by two main operations, as is shown in Table 1: (1) Operations involved in the check node update (CNU) and variable node update (VNU) processes of the inner LLR-BP algorithm per iteration, and (2) the maximum number of additions and multiplications in the step of error-locator polynomial computation for outer B-M algorithm. For the non-binary LDPC code, complexity was provided by the operations in the CNU and VNU processes of the extended min-sum (EMS) decoding algorithm, as is shown in Table 2[29].  
\begin{table}
\begin{tabular}{c c c c} \hline \hline  & \multicolumn{2}{c}{**LLR-BP**} & \multicolumn{2}{c}{**B–M**} \\ \cline{2-4}  & **Check Node Update** & **Variable Node Update** & **Error-Locator** \\  & **(CNU)** & **(VNU)** & **Polynomial Computation** \\ \hline \multirow{2}{*}{
\begin{tabular}{c} Additions \\ Comparisons \\ Multiplications \\ \end{tabular} } & 2M(3\(d_{c}\) – 4) & \(N\)\(d_{p}\)\({}^{2}\) & \((n-k)\)\({}^{2}+2(n-k)\) \\  & 2M(3\(d_{c}\) – 4) & – & – \\  & – & – & \(3(n-k)\)\({}^{2}\)/2 + \(7(n-k)\)/2 \\ \hline \hline \end{tabular}
\end{table}
Table 1: Decoding complexity of RS-LDPC with the log-likelihood ratio belief propagation (LLR-BP) algorithm for the inner binary LDPC code, and the Berlekamp–Massey (B–M) algorithm for the outer RS code.  
\begin{table}
\begin{tabular}{c c c} \hline \hline  & **CNU** & **VNU** \\ \hline \multicolumn{2}{c}{Additions \(6 Mn_{m}(d_{c}-2)\)} & \multicolumn{1}{c}{\(4N\)\(n\)\(d_{m}\)(2\(d_{v}-3\))} \\ \hline \multicolumn{2}{c}{Comparisons \(6 Mn_{m}(d_{c}-2)\)log\({}_{2}n_{m}\)} & \multicolumn{1}{c}{\(2N\)\(n\)\(m\)(2\(d_{v}-3)\)log\({}_{2}\)(2\(n\)\(m\))} \\ \hline \hline \end{tabular}
\end{table}
Table 2: Decoding complexity of the non-binary LDPC code with the extended min-sum (EMS) algorithm.  
It can be seen from Tables 1 and 2 that the complexity is a function of the code parameters, where \(d_{c}\) and \(d_{v}\) represent the average check node degree and average variable node degree of the binary and non-binary LDPC codes, \(N\) and \(M\) represent the codeword length and the number of check nodes of the binary and non-binary LDPC codes, \(n_{m}\) represents the truncated message size in the EMS algorithm, and \(n\) and \(k\) are the codeword and information lengths of the RS code, respectively.  
It can be observed from Table 1 that the complexity of the LLR-BP algorithm for the binary LDPC code is linear per codeword per iteration, and the overall complexity of the B-M algorithm for the RS code is \(\mathcal{O}((n-k)^{2})\). The complexity of the EMS algorithm for the non-binary LDPC code is \(\mathcal{O}(Mn_{m}{\rm log}_{2}n_{m})\) per codeword per iteration, as shown in Table 2. The numerical computational complexity results associated with the code parameters employed in this work will be given in the next section.