# An Improved Low-Density Parity-Check Decoder and Its Field-Programmable Fate Array Implementation
## 2 LDPC Code Structure and Decoding Algorithm  
### LDPC Decoding Algorithm  
The LDPC decoding methods can be broadly categorized into two classes: hard-decision algorithms based on bit-flipping decoding and soft-decision algorithms. Hard-decision decoding algorithms, due to their low complexity, are suitable for hardware implementation but cannot achieve optimal decoding performance. Soft-decision algorithms, while more complex to implement in hardware, can theoretically achieve performance close to the Shannon limit. To reduce the difficulty of hardware implementation, a simplified version of the Min-Sum (MS) algorithm was proposed, giving rise to a series of improved MS algorithms, such as the Normalized Min-Sum (NMS) and Offset Min-Sum (OMS) algorithms, which retain low implementation complexity. As a type of linear block code, an LDPC code is defined by a parity-check matrix H consisting of m rows and n columns. It is represented by a Tanner graph that includes n variable nodes and m check nodes. Here, the \(i\)-th variable node, denoted as \(v_{i}\), represents the \(i\)-th bit of the transmitted codeword. The \(j\)-th check node, referred to as \(c_{j}\), corresponds to the \(j\)-th parity-check equation. A connection between the \(i\)-th variable node \(v_{i}\) and the \(j\)-th check node \(c_{j}\) is established when \(H_{ij}=1\). Taking the Formula (1) matrix as an example, the corresponding set of parity-check equations is given by equation Formula (2), and the associated Tanner graph is denoted as Figure 1. Tanner graph corresponding to Matrix H, which visually demonstrates the encoding and decoding process of the LDPC code. \[H= \begin{bmatrix}1&0&1&1&0&0&0&1&0&1&1&0\\ 0&0&1&0&1&1&0&1&1&0&0&1\\ 1&1&0&1&0&1&0&0&1&1&0&0\\ 1&1&0&1&0&0&1&0&0&0&1&1\\ 0&0&1&0&1&1&1&0&1&1&0&0\\ 0&1&0&0&1&0&1&1&0&0&1&1\end{bmatrix}  \tag{1}\]\[\left\{ \begin{array}{l}c_{1}+c_{3}+c_{4}+c_{8}+c_{10}+c_{11}=0\\ c_{3}+c_{5}+c_{6}+c_{8}+c_{9}+c_{12}=0\\ c_{1}+c_{2}+c_{4}+c_{6}+c_{9}+c_{10}=0\\ c_{1}+c_{2}+c_{4}+c_{7}+c_{11}+c_{12}=0\\ c_{3}+c_{5}+c_{6}+c_{7}+c_{9}+c_{10}=0\\ c_{2}+c_{5}+c_{7}+c_{8}+c_{11}+c_{12}=0\\ \end{array} \right. \tag{2}\]  
Initially, implementing the Belief Propagation (BP) algorithm in the probability domain required extensive use of multiplication, division, and logarithmic operations, making it not only challenging to implement on hardware but also prone to numerical instability with longer code lengths. The introduction of the Log-Likelihood Ratio Belief Propagation (LLR-BP) algorithm, which transforms multiplication operations into addition operations through the use of log-likelihood ratios, significantly reduced the complexity of hardware implementation. The log-likelihood ratio is first defined as Formula (3). \[L(Q_{i})=\log(\Pr(x_{i}=0\mid y_{i})/\Pr(x_{i}=1\mid y_{i})) \tag{3}\]  
Under the condition of Gaussian white noise with a variance of \(\sigma^{2}\), Formula (4) can be simplified to the following:  
\[L(Q_{i})=\log(\frac{\Pr(x_{i}=1\mid y_{i})}{\Pr(x_{i}=-1\mid y_{i})})=\log( \frac{1+e^{2y_{i}/\sigma^{2}}}{1+e^{-2y_{i}/\sigma^{2}}})=2y_{i}/\sigma^{2} \tag{4}\]  
The update for the check nodes is as follows:  
\[L(c_{ji})=\prod_{i\in M(j)\smallsetminus i}sign(Lv_{ij})\phi(\sum_{i\in M(j) \smallsetminus i}\phi(\left|Lv_{ij}\right|)) \tag{5}\]  
In Formula (5), \(\phi(x)=-\log(\tanh(x/2))=\log\left(\frac{c_{i}+1}{\sigma^{2}-1}\right)\)  
For the update of variable nodes  
\[L(v_{ij})=L(Q_{i})+\sum_{j\in N(i)/j}L^{(l)}(c_{ji}) \tag{6}\]  
Regarding the posterior probability  
\[L(q_{i})=L(Q_{i})+\sum_{j\in N(i)}L^{(l)}(c_{ji}) \tag{7}\]  
In the LLRBP algorithm, the hyperbolic tangent operations within the check nodes remain overly complex for hardware implementation. Taking advantage of the property that the slope of the hyperbolic tangent function decreases as the input x increases, the Min-Sum decoding algorithm was proposed.