## 2 LDPC Codes
### LDPC Decoding Algorithm  
Based on the low-density characteristics of the LDPC check matrix, despite the belief that propagation-based iterative decoding algorithms is suboptimal, the result can still be obtained close to the optimal decoding criterion. The sum product algorithm (SPA) is a classical iterative decoding algorithm that accomplishes iterative decoding by passing messages between nodes. The log-likelihood ratio sum product algorithm (LLR-SPA) replaces probability domain calculations with likelihood domain calculations, reducing the algorithm complexity without changing the decoding performance.  
In addition to matrix representation, LDPC codes can also be represented by Tanner graphs, which can be used to better illustrate the decoding algorithm. Tanner graphs are bipartite graphs, where nodes on the graph are classified into two categories: variable nodes (VNs) and check nodes (CNs), and lines connecting the two categories of nodes are called edges. Their equivalent Tanner graph can be obtained based on the check matrix \(H\). According to this rule, the VN can correspond to the coded bits in the check equation, while the CN corresponds to the set of check equations. Tanner graphs are often used to describe sum-product decoding algorithms. An example of a Tanner graph is given in Figure 1. Let the \(j\)th variable node (VN) be \(VN_{j}\) and the \(i\)th check node (CN) be \(CN_{i}\). In the check matrix, element \(h_{ij}=1\) indicates the existence of an edge between \(CN_{i}\) and \(VN_{j}\) on the Tanner graph. The specific LLR-SPA algorithm is as follows.  
Step 1. Initialize the variable nodes according to Equation (7), where \(L_{j}\) denotes the result of the channel message after initialization, \(y_{j}\) denotes the actual value received by the channel and \(v_{j}\) denotes the estimated value of the code word. According to the Tanner diagram, for \(h_{ij}=1\), let \(L_{j\to i}=L_{j}\):\[L_{j}=L\big{(}v_{j}|y_{j}\big{)}=\log\Bigg{(}\frac{Pr\big{(}v_{j}=0|y_{j}\big{)}}{ Pr\big{(}v_{j}=1|y_{j}\big{)}}\Bigg{)} \tag{7}\]  
Step 2. The CN is updated to calculate the extrinsic information passed according to Equation (8), where \(L_{i\to j}\) denotes the extrinsic information passed from \(CN_{i}\) to \(VN_{j}\), \(N(i)\) denotes the set of nodes connected to \(CN_{i}\) and \(j^{\prime}\) denotes any variable node connected to \(CN_{i}\) except \(VN_{j}\):  
\[L_{i\to j}=2\text{tanh}^{-1}\left(\prod_{j^{\prime}\in N(i)-\{j\}}\text{ tanh}\bigg{(}\frac{1}{2}L_{j\to i}\bigg{)}\right) \tag{8}\]  
Step 3. The VN is updated and the extrinsic information passed is calculated according to Equation (9), where \(L_{j\to i}\) denotes the extrinsic information passed from \(VN_{j}\) to \(CN_{i}\), \(N(j)\) denotes the set of nodes connected to \(VN_{j}\) and \(i^{\prime}\) denotes any check node connected to \(VN_{j}\) except \(CN_{i}\).  
\[L_{j\to i}=L_{j}+\sum_{j^{\prime}\in N(j)-\{i\}}L_{i^{\prime}\to j} \tag{9}\]  
Step 4. Sum the LLR according to  
\[L_{j}^{\text{ }total}=L_{j}+\sum_{i\in N(j)}L_{i\to j} \tag{10}\]  
Step 5. Termination criterion: for \(j\in[0,n-1]\), judge the code bits according to Equation (11). If the check condition \(\overset{\cdot}{v}H^{T}=O\) is satisfied, terminate the decoding. Otherwise, the decoding has failed; return to step 2 and repeat the process until the decoding succeeds or the maximum number of iterations is reached.  
\[\overset{\cdot}{v}_{j}=\left\{\begin{aligned} & 1,\ L_{j}^{\text{ }total}<0\\ & 0,\ else\end{aligned}\right. \tag{11}\]