Linear Block Code

A very simple linear block code can be represented with a Generator Matrix G, for example:

If c is the uncoded bits:

The encoded bits d can be obtained via matrix G:

H is defined as the Parity Matrix, where:

In this example, H is:

where each row represents one of the there parity check equations below:

LDPC

LDPC code is simply one kind of linear block code where the dimension of H is big (e.g. 1944*972) but the percentage of 1’s in the Parity Matrix is very low (e.g. only 8 1’s per row in the matrix, resulting a percentage of 8/1944).

Graphic Representation (Tanner Graph) of LDPC

The Parity Matrix of LDPC can be described with a graph of Check Nodes(CN) and Variable Nodes(VN). Each CN represents a parity bit in the matrix and each VN represents one bit of the codeword. CN_i is connected to VN_j if the element h_ij of H is a 1. Below is the Tanner Graph of the H matrix in this example:

Message Passing Algorithm

The Message Passing algorithm is based on the Tanner Graph.

Step 1: VN uses the received LLR as the message and pass them to the CN

Step 2: CN calculate the new message and send them back to VN

Step 3: VN calculate the new LLR based on the received message from CN

Step 4: repeat Step 1 to Step 3 using the new LLR

The Standard TPMP Decoding Algorithm[2]

The nature of LDPC decoding algorithms is mainly iterative. Most of these algorithms are derived from the well-known belief propagation (BP) algorithm [3]. The aim of BP algorithm is to compute the a posteriori probability (APP) that a given bit in the transmitted codeword c = [c_0,, c₁, … , c_N−1] equals 1, given the received word y = [y₀, y₁, … , y_N−1]. For binary phase shift keying (BPSK) modulation over an additive white Gaussian noise (AWGN) channel with mean 1 and variance σ², the reliability messages represented as logarithmic likelihood ratio (LLR) are computed in two steps: (1) check node update and (2) variable node update. This is also referred to as twophase message passing (TPMP).

For n^th iteration, let αⁿ_j represents the LLR of VN_j, αⁿ_i,j represent the message sent from variable node VN_j to check node CN_i, βⁿ_i,j represent the message sent from CN_i to VN_j; M(j) = {i : H_ij = 1} is the set of parity checks in which VN_j participates, N(i) = {j : H_ij = 1} the set of variable nodes that participate in parity check i, M(j) \ i the set M(j) with CN_i excluded, and N(i) \ j the set N(i) with VN_j excluded.

The standard TPMP algorithm is described as below:

For different decoding schemes, the calculation of βⁿ_i,j is different. The Sum Product (SP) algorithm [4] gives near-optimal results; however, the implementation of the transcendental function Φ(x) requires dedicated LUTs, leading to significant hardware complexity [5]. Min-Sum (MS) algorithm [6] is a simple approximation of the SP: its easy implementation suffers an 0.2 dB performance loss compared to SP decoding [7]. Normalized Min-Sum (NMS) algorithm [8] gives better performance than MS by multiplying the MS check node update by a positive constant λ_k, smaller than 1. Offset Min-Sum (OMS) is another improvement of standard MS algorithm which reduces the reliability values βⁿ_i,j by a positive value β. All the four schemes are summarised in the below table:

Layered Decoding Algorithm[2]

Modify the VN update rule as:

Then step(2)(3)(4) in TPMP can be merged into one operation. This technique is called layered decoding which considers the matrix H as a concatenation of layers of constituent sub-matrices, where the dimension of each sub-matrices is 1 * M. The layered decoding algorithm is described as below (NMS is used here with normalisation factor λ):

QC-LDPC and Parallelism in Layered Decoding Algorithm[9,10]

Quasi-Cyclic LDPC (QC-LDPC) codes have been widely used in many practical systems, such as IEEE 802.11n WLAN, IEEE 802.16e WiMAX, also in Verizon 5G. The parity check matrix for a QC-LDPC code can be represented as an array of square sub-matrices, where each sub-matrix is either a Z * Z zero matrix or a Z * Z circulant matrix. As an example, Below shows the parity check matrix for the block length 1944 bits, code rate 1/2, sub-matrix size Z = 81 LDPC code. In this matrix representation, each square box with a label I_x represents an 81 * 81 cyclicly-shifted identity matrix with a shifted value of x, and each empty box represents an 81 * 81 zero matrix.

Base graph (BG)1 defined by 5G NR standard for length N = 3808 bits, code rate R = 1/3, and Z = 56:

One advantage of QC-LDPC code is allowing parallelization of the layered decoding algorithm. Because each square sub-matrices is either a zero matrix or a circulant matrix, all the Z layers within a square sub-matrices can be processed simultaneously.

References

[1] Low-density parity-check code Wikipedia (https://en.wikipedia.org/wiki/Low-density_parity-check_code)
[2] Awais, Muhammad, and Carlo Condo. “Flexible LDPC decoder architectures.” VLSI Design 2012 (2012): 5.
[3] R. Gallager, “Low-density parity-check codes,” IEEE Transactions on Information Theory, vol. 8, no. 1, pp. 21–28, 1962.
[4] F. R. Kschischang, B. J. Frey, and H. A. Loeliger, “Factor graphs and the sum-product algorithm,” IEEE Transactions on Information Theory, vol. 47, no. 2, pp. 498–519, 2001.
[5] G. Masera, F. Quaglio, and F. Vacca, “Finite precision implementation of LDPC decoders,” IEE Proceedings on Communications, vol. 152, no. 6, pp. 1098–1102, 2005.
[6] N. Wiberg, Codes and decoding on general graphs, Ph.D. dissertation, Linkoping University, Linkoping, Sweden, 1996.
[7] M. Daud, A. Suksmono,Hendrawan, and Sugihartono, “Comparison of decoding algorithms for LDPC codes of IEEE 802.16e standard,,” in Proceedings of the 6th International Conference on Telecommunication Systems, Services, and Applications (TSSA ’11), pp. 280–283, October 2011.
[8] J. Chen andM. P. C. Fossorier, “Near optimumuniversal belief propagation based decoding of LDPC codes and extension to turbo decoding,” in Proceedings of the IEEE International Symposium on Information Theory (ISIT ’01), p. 189, June 2001.
[9] Sun, Yang, Guohui Wang, and Joseph R. Cavallaro. “Multi-layer parallel decoding algorithm and VLSI architecture for quasi-cyclic LDPC codes.” Circuits and Systems (ISCAS), 2011 IEEE International Symposium on. IEEE, 2011.
[10] Thi Bao Nguyen, Tram, Tuy Nguyen Tan, and Hanho Lee. “Low-Complexity High-Throughput QC-LDPC Decoder for 5G New Radio Wireless Communication.” Electronics 10.4 (2021): 516.