# An Improved Low-Density Parity-Check Decoder and Its Field-Programmable Fate Array Implementation
## 3 Improved Decoding Algorithm
### TNMS Decoding Algorithm  
Quantization essentially amplifies the channel information of all codewords to be decoded by a consistent factor. Subsequent information derived from the channel data is similarly amplified. Consequently, both the initial channel information \(L(Q_{i})\) and the variable node edge information \(\sum\limits_{j\in N(i)}L^{(l)}(c_{ii})\) in the final codeword decision formula are amplified by the same factor, ensuring that the final decision information \(L^{(l)}(q_{i})\) remains accurate when determining whether the decoded bit is 0 or 1. Drawing on this concept, the traditional NMS decoding algorithm has been improved. After the traditional NMS algorithm initializes the channel information as the variable node information (Formula (9)), a self-update step is added using the correction factor \(\beta\), following Formula (17):  
\[L(Q_{i})^{\prime}=\beta\times L(Q_{i}) \tag{17}\]  
The correction factor \(\alpha\) used in the check node update step is removed, replacing Formula (10) with Formula (18):  
\[L^{(l)}(c_{ij})=\prod_{i^{\prime}\in M(j)\smallsetminus i}\text{sgn}(L^{(l-1)}(v _{i^{\prime}j}))\times\text{min}_{i^{\prime}\in M(j)\smallsetminus i}(|L^{(l-1)}( v_{i^{\prime}j})|) \tag{18}\]  
In the decision step, \(L(Q_{i})\) in Formula (11) is replaced with \(L(Q_{i})^{\prime}\) in Formula (19), and consequently, Formula (11) is replaced with Formula (19):  
\[L^{(l)}(v_{ij})=L(Q_{i})^{\prime}+\sum_{j^{\prime}\in N(i)/j}L^{(l)}(c_{j^{ \prime}i}) \tag{19}\]  
In the decision step, \(L(Q_{i})\) in Formula (12) is replaced with \(L(Q_{i})^{\prime}\) in Formula (20), and consequently, Formula (12) is replaced with Formula (20):  
\[L^{(l)}(q_{i})=L(Q_{i})^{\prime}+\sum_{j\in N(i)}L^{(l)}(c_{ji}) \tag{20}\]  
In the original NMS algorithm, the optimal correction factor for the check node formula is \(\alpha\). In the improved decoding algorithm, the optimal correction factor \(\beta\) is set to \(1/\alpha\), which yields decoding performance equivalent to using the correction factor \(\alpha\) in the original NMS algorithm. For the NMS algorithm, the optimal correction factor selection is influenced by factors like code length, code rate, and signal-to-noise ratio (SNR). Generally, the value ranges from 0.7 to 0.85. In certain cases, approximating \(\alpha\) using shift-add operations may require numerous addition steps, while switching to the correction factor in the improved algorithm can reduce the number of additions required, lowering computation overhead and minimizing logic resource usage. For example, consider LDPC decoding for a code with length n, check bit length m, and a code rate R = (n - m)/n. In the original NMS algorithm (Formula (10)), if the optimal correction factor \(\alpha\) is 0.8, it can be approximated by \(L^{(l)}(c_{ji})^{\prime}=L^{(l)}(c_{ji})\times(1/2+1/4+1/32+1/64)\). During each iteration, the second minimum and minimum values among the m check nodes are corrected once each, requiring m \(\times\) 2 \(\times\) 3 additions and m \(\times\) 4 \(\times\) 2 shifts. With the improved decoding algorithm, in Formula (17), if \(\beta\) is set to \(1/\alpha\), i.e., 1.25, it can be approximated using \(L(Q_{i})^{\prime}=L(Q_{i})\times(1+0.25)\). In each iteration, this requires correcting the n channel information values once, which involves n additions and n shifts. Additionally, due to the quantization bit-width limitation in hardware implementation, the channel information cannot be indefinitely expanded. Therefore, after every three iterations, both the channel information and check node information need to be right-shifted by one bit. This results in an average of (n + 2 \(\times\) m)/3 shifts per iteration. This process keeps the channel information stable within the quantization range while converting the data loss from correction factors in each iteration of the original NMS algorithm into a single bit-shift of both channel and check node information after every three iterations.