ldpcDecode

The implementation of the belief propagation algorithm is based on the decoding algorithm presented by Gallager [2].

For transmitted LDPC-encoded codeword c = c₀, c₁, …, c_n-1, the input to the LDPC decoder is the log-likelihood ratio (LLR) value $$L(c_i)=\log \left(\frac{\mathrm{Pr}(c_i=0|\text{channel output for }{c}_i)}{\mathrm{Pr}(c_i=1|\text{channel output for }{c}_i)}\right)$$.

In each iteration, the key components of the algorithm are updated based on these equations:

$$L(r_{ji})=2\text{atanh}\left({\displaystyle \prod _{i^{\prime }\in V_j\backslash i}\tanh \left(\frac{1}{2}L(q_{i^{\prime }j})\right)}\right)$$,

$$L(q_{ij})=L(c_i)+{\displaystyle \sum _{j^{\prime }\in C_i\backslash j}L(r_{j^{\prime }i})}$$, initialized as $$L(q_{ij})=L(c_i)$$ before the first iteration, and

$$L(Q_i)=L(c_i)+{\displaystyle \sum _{j^{\prime }\in C_i}L(r_{j^{\prime }i})}$$.

At the end of each iteration, L(Q_i) contains the updated estimate of the LLR value for transmitted bit c_i. The value L(Q_i) is the soft-decision output for c_i. If L(Q_i) ≤ 0, the hard-decision output for c_i is 1. Otherwise, the hard-decision output for c_i is 0.

If decoding is configured to stop when all of the parity checks are satisfied, the algorithm verifies the parity-check equation (H c' = 0) at the end of each iteration. When all of the parity checks are satisfied, or if the maximum number of iterations is reached, decoding stops.

Index sets $$C_i\backslash j$$ and $$V_j\backslash i$$ are based on the parity-check matrix (PCM). Index sets C_i and V_j correspond to all nonzero elements in column i and row j of the PCM, respectively.

This figure shows the computation of these index sets in a given PCM for i = 5 and j = 3.

To avoid infinite numbers in the algorithm equations, atanh(1) and atanh(–1) are set to 19.07 and –19.07, respectively. Due to finite precision, MATLAB returns 1 for tanh(19.07) and –1 for tanh(-19.07).

The implementation of the layered belief propagation algorithm is based on the decoding algorithm presented in Hocevar [3], Section II.A. The decoding loop iterates over subsets of rows (layers) of the PCM. For each row, m, in a layer and each bit index, j, the implementation updates the key components of the algorithm based on these equations:

(1) $$L(q_{mj})=L(q_j)-R_{mj}$$,

(2) $$A_{mj}={\displaystyle \sum _{\begin{array}{c}n \in N\left(m\right)\\ n\ne j\end{array}}\text{ψ}(L(q_{mn}))}$$,

(3) $$s_{mj}={\displaystyle \prod _{\begin{array}{c}n \in N\left(m\right)\\ n\ne j\end{array}}\text{sign}(L(q_{mn}))}$$,

(4) $$R_{mj}=-s_{mj}\text{ψ}(A_{mj})$$, and

(5) $$L(q_j)=L(q_{mj})+R_{mj}$$.

For each layer, the decoding equation (5) works on the combined input obtained from the current LLR inputs $$L(q_{mj})$$ and the previous layer updates $$R_{mj}$$.

Because only a subset of the nodes is updated in a layer, the layered belief propagation algorithm is faster compared to the belief propagation algorithm. To achieve the same error rate as attained with belief propagation decoding, use half the number of decoding iterations when you use the layered belief propagation algorithm.

The implementation of the normalized min-sum decoding algorithm follows the layered belief propagation algorithm with equation (2) replaced by

$$A_{mj}=\underset{\begin{array}{c}n \in N\left(m\right)\\ n\ne j\end{array}}{\min }(\left|L(q_{mn}) \right|\cdot \alpha )$$,

where α is in the range (0, 1] and is the scaling factor specified by the MinSumScalingFactor input argument to the ldpcDecode function. This equation is an adaptation of equation (4) presented in Chen [4].

The implementation of the offset min-sum decoding algorithm follows the layered belief propagation algorithm with equation (2) replaced by

$$A_{mj} = \max (\underset{\begin{array}{c}n \in N\left(m\right)\\ n\ne j\end{array}}{\min } (\left|L\left(q_{mn}\right)\right|- \beta ), 0)$$,

where β ≥ 0 and is the offset specified by the MinSumOffset input argument to the ldpcDecode function. This equation is an adaptation of equation (5) presented in Chen [4].