5G NR QC-LDPC Encoding Algorithm

3GPP 5G has been focused on structured LDPC codes known as quasi-cyclic low-density parity-check (QC-LDPC) codes, which exhibit advantages over other types of LDPC codes with respect to the hardware implementations of encoding and decoding using simple shift registers and logic circuits.

5G NR QC-LDPC

Circulant Permutation Matrix

A circular permutation matrix ${\bf I}(P_{i,j})$ of size $Z_c \times Z_c$ is obtained by circularly shifting the identity matrix $\bf I$ of size $Z_c \times Z_c$ to the right $P_{i,j}$ times. We denoted this binary circulant permutation matrixas by $Q(P_{i,j})$, considering $Q(1)$ as an example,

$Q(1) = \begin{bmatrix} 0 & 1 & 0 & \ldots & 0\\ 0 & 0 & 1 & \ldots & 0\\ \vdots & \vdots & \ddots & \vdots \\0 & 0 & 0 & \ldots & 1\\1 & 0 & 0 & \ldots & 0\\ \end{bmatrix}$

For simple notation, $Q(−1)$ denotes the null matrix.

All possible lifting sizes $Z_c$ are grouped into 8 sets, listed as $\text{follow}^{[1]}$:

The parity-check matrix $\bf H$ of QC-LDPC code expressed by the following $m_b \times n_b$ array of $Z \times Z$ circulants over $GF(2)$:

$H = \begin{bmatrix}Q(P_{1,1}) & Q(P_{1,2}) & \ldots & Q(P_{1,n_b})\cr Q(P_{2,1}) & Q(P_{2,2}) & \ldots & Q(P_{2,n_b})\cr \vdots & \vdots & \ddots & \vdots \cr Q(P_{m_b,1}) & Q(P_{m_b,2}) & \ldots & Q(P_{m_b,n_b})\cr \end{bmatrix}$

Base Graphs Characteristics

There are two rate-compatible base graphs with similar structures in 5G NR, denoted by BG1 and BG2.

BG1 is targeted for larger block lengths$(500 \le K \le 8448)$ and higher rates $(1/3 ≤ R ≤ 8/9)$.

BG2 is targeted for smaller block lengths$(40 \le K \le 2560)$ and lower rates $(1/5 \le R \le 2/3)$.

For BG1, a matrix of $H_{BG1}$ with a size of $m_b \times n_b(m_b = 46, n_b = 68, k_b = n_b - m_b = 22)$.

For BG2, a matrix of $H_{BG2}$ with a size of $m_b \times n_b(m_b = 42, n_b = 52, k_b = n_b - m_b = 10)$.

The information bit columns are $k_b \times Z$.

The $H \in \{H_{BG1},H_{BG2}\}$ can be partitioned into six matrices:

$H = \begin{bmatrix}A & B & 0\cr C_1 & C_2 & I\cr \end{bmatrix}$

There are 8 different $i_{LS}$ for BG1 and 8 different $i_{LS}$ for BG2, that corresponding to 16 different $A, C_1, C_2$.

$A = \begin{bmatrix}a_{1,1} & a_{1,2} & \ldots & a_{1,k_b}\cr a_{2,1} & a_{2,2} & \ldots & a_{2,k_b}\cr a_{3,1} & a_{3,2} & \ldots & a_{3,k_b}\cr a_{4,1} & a_{4,2} & \ldots & a_{4,k_b}\cr \end{bmatrix} C_1 = \begin{bmatrix} c_{1,1} & c_{1,2} & \ldots & c_{1,k_b}\cr c_{2,1} & c_{2,2} & \ldots & c_{2,k_b}\cr \vdots & \vdots & \ddots & \vdots \cr c_{m_b-4,1} & c_{m_b-4,2} & \ldots & c_{m_b-4,k_b}\cr \end{bmatrix} C_2 = \begin{bmatrix} c_{1,k_b+1} & c_{1,k_b+2} & c_{1,k_b+3} & c_{1,k_b+4}\cr c_{2,k_b+1} & c_{2,k_b+2} & c_{1,k_b+3} & c_{2,k_b+4}\cr \vdots & \vdots & \vdots & \vdots \cr c_{m_b-4,k_b+1} & c_{m_b-4,k_b+2} & c_{m_b-4,k_b+3} & c_{m_b-4,k_b+4}\cr \end{bmatrix}$

For simple notation, $\{-1, 0, 1, ...\}$ denotes the $\{Q(-1), Q(0), Q(1)...\}$.

There are 2 types of $B \in \{H_{BG1\_B1}, H_{BG1\_B2}, H_{BG2\_B1}, H_{BG2\_B2}\}$ in both BG1 and BG2.

$H_{BG1\_B1} = \begin{bmatrix} 1 & 0 & -1 & -1\cr 0 & 0 & 0 & -1\cr -1 & -1 & 0 & 0\cr 1 & -1 & -1 & 0\cr \end{bmatrix} ~~ H_{BG1\_B2} = \begin{bmatrix} 0 & 0 & -1 & -1\cr 105 & 0 & 0 & -1\cr -1 & -1 & 0 & 0\cr 0 & -1 & -1 & 0\cr \end{bmatrix}$

$H_{BG1\_B1}$ is for $Z$ set index $i_{LS} = (0, 1, 2, 3, 4, 5, 7)$, $H_{BG2\_B1}$ is for $i_{LS} = (6)$.

$H_{BG2\_B1} = \begin{bmatrix} 0 & 0 & -1 & -1\cr -1 & 0 & 0 & -1\cr 1 & -1 & 0 & 0\cr 0 & -1 & -1 & 0\cr \end{bmatrix} ~~ H_{BG2\_B2} = \begin{bmatrix} 1 & 0 & -1 & -1\cr -1 & 0 & 0 & -1\cr 0 & -1 & 0 & 0\cr 1 & -1 & -1 & 0\cr \end{bmatrix}$

$H_{BG1\_B2}$ is for $Z$ set index $i_{LS} = (0, 1, 2, 4, 5, 6)$, $H_{BG2\_B2}$ is for $i_{LS} = (3, 7)$.

Encoding Algorithm

Let the codeword

$C = [s \; p_b \; p_c] = [s_1, s_2, \ldots, s_{k_b}, p_{b_1}, p_{b_2}, p_{b_3}, p_{b_4}, p_{c_1}, p_{c_2}, \ldots, p_{c_{m_b-4}}]$

where each element of $C$ is a vector of length $Z$.

The encoding of LDPC codes is carried out as follow:

$HC^T = \begin{bmatrix} A & B & 0\\ C_1 & C_2 & I\\ \end{bmatrix} \begin{bmatrix} s^T\\ p_b^T\\ p_c^T\\ \end{bmatrix} = 0^T$

that is,

\begin{align} A s^T + B p_b^T &= 0^T \tag{1} \\ C_1 s^T + C_2 p_b^T + p_c^T &= 0^T \tag{2} \end{align}

Computation of $p_b$

First we determinate the $p_b$ part from equation (1):

\begin{align} H_{BG1\_B1} &: \begin{cases} \sum\limits_{j=1}^{k_b}a_{1,j}s_j + p_{b_1}^{(1)} + p_{b_2} = 0\\ \sum\limits_{j=1}^{k_b}a_{2,j}s_j + p_{b_1} + p_{b_2} + p_{b_3} = 0\\ \sum\limits_{j=1}^{k_b}a_{3,j}s_j + p_{b_3} + p_{b_4} = 0 \\ \sum\limits_{j=1}^{k_b}a_{4,j}s_j + p_{b_1}^{(1)} + p_{b_4} = 0 \end{cases};~~~~~~ H_{BG1\_B2} : \begin{cases} \sum\limits_{j=1}^{k_b}a_{1,j}s_j + p_{b_1} + p_{b_2} = 0\\ \sum\limits_{j=1}^{k_b}a_{2,j}s_j + p_{b_1}^{(105~mod~Z)} + p_{b_2} + p_{b_3} = 0\\ \sum\limits_{j=1}^{k_b}a_{3,j}s_j + p_{b_3} + p_{b_4} = 0\\ \sum\limits_{j=1}^{k_b}a_{4,j}s_j + p_{b_1} + p_{b_4} = 0 \end{cases};\\ \\ H_{BG2\_B1} &: \begin{cases} \sum\limits_{j=1}^{k_b}a_{1,j}s_j + p_{b_1} + p_{b_2} = 0\\ \sum\limits_{j=1}^{k_b}a_{2,j}s_j + p_{b_2} + p_{b_3} = 0\\ \sum\limits_{j=1}^{k_b}a_{3,j}s_j + p_{b_1}^{(1)} + p_{b_3} + p_{b_4} = 0\\ \sum\limits_{j=1}^{k_b}a_{4,j}s_j + p_{b_1} + p_{b_4} = 0 \end{cases};~~~~~~ H_{BG2\_B2} : \begin{cases} \sum\limits_{j=1}^{k_b}a_{1,j}s_j + p_{b_1}^{(1)} + p_{b_2} = 0\\ \sum\limits_{j=1}^{k_b}a_{2,j}s_j + p_{b_2} + p_{b_3} = 0\\ \sum\limits_{j=1}^{k_b}a_{3,j}s_j + p_{b_1} + p_{b_3} + p_{b_4} = 0\\\sum\limits_{j=1}^{k_b}a_{4,j}s_j + p_{b_1}^{(1)} + p_{b_4} = 0 \end{cases}.\end{align}

where $p_{b_1}^{(\alpha)}$ denotes the $\alpha^{th}$ right cyclic shifted version of $p_{b_1}$ for $0 ≤ \alpha ≤ Z$.

Based on the definition below,

$\lambda_i = \sum\limits_{j=1}^{k_b}a_{i,j}s_j; ~~ i = 1, 2, 3, 4$.

the following can be obtained:

\begin{align}H_{BG1\_B1} &: \begin{cases} p_{b_1} = \sum\limits_{i=1}^{4} \lambda_i\\ p_{b_2} = \lambda_1 + p_{b_1}^{(1)}\\p_{b_4} = \lambda_4 + p_{b_1}^{(1)}\\p_{b_3} = \lambda_3 + p_{b_4}\end{cases};~~~~~~H_{BG1\_B2} : \begin{cases}p_{b_1}^{(105~mod~Z)} = \sum\limits_{i=1}^{4} \lambda_i \to p_{b_1}\\p_{b_2} = \lambda_1 + p_{b_1}\\p_{b_4} = \lambda_4 + p_{b_1}\\p_{b_3} = \lambda_3 + p_{b_4}\end{cases};\\ \\H_{BG2\_B1} &: \begin{cases} p_{b_1}^{(1)} = \sum\limits_{i=1}^{4} \lambda_i \to p_{b_1}\\p_{b_2} = \lambda_1 + p_{b_1}\\p_{b_3} = \lambda_2 + p_{b_2}\\p_{b_4} = \lambda_4 + p_{b_1}\end{cases};~~~~~~H_{BG2\_B2} : \begin{cases}p_{b_1} = \sum\limits_{i=1}^{4} \lambda_i\\p_{b_2} = \lambda_1 + p_{b_1}^{(1)}\\p_{b_3} = \lambda_2 + p_{b_2}\\p_{b_4} = \lambda_3 + p_{b_1}^{(1)}\end{cases}.\end{align}

Computation of $p_c$

Secondly, the $p_c$ can be easily determined based on equation (2):

$p_{c_i} = \sum\limits_{j=1}^{k_b}c_{i,j}s_j + \sum\limits_{j=1}^4 c_{i,k_b+j}p_{b_j},~~i=1,2,\ldots, m_b-4$.

Systematic Bit Puncturing

5G NR directly delete the first $2 \times Z$ systematic bits. Here ignore the procedures of CRC, rate-matching, HARQ and so on which included in a complete channel coding link.

Reference:

1. 3GPP TS 38.212. NR; Multiplexing and channel coding. 3rd Generation Partnership Project. www.3gpp.org.

2. Tram Thi Bao Nguyen, Tuy Nguyen Tan, Hanho Lee. Efficient QC-LDPC Encoder for 5G New Radio. www.mdpi.com.

Previous post by Lyons Zhang:
Polar Coding Notes: A Simple Proof

[ - ]
Comment by September 14, 2019

Hi Lynos,

I will be glad if you can help me information regarding, how to "Simulate a BPSK environment with Rayleigh (AWGN) for full-duplex" in Matlab.

Thanks

[ - ]
Comment by September 16, 2019

Newhuf,

1. Dent, P., G. E. Bottomley, and T. Croft. “Jakes Fading Model Revisited.” Electronics Letters. Vol. 29, Number 13, 1993, pp. 1162–1163.

2. Pätzold, Matthias, Cheng-Xiang Wang, and Bjørn Olav Hogstad. “Two New Sum-of-Sinusoids-Based Methods for the Efficient Generation of Multiple Uncorrelated Rayleigh Fading Waveforms.” IEEE Transactions on Wireless Communications. Vol. 8, Number 6, 2009, pp. 3122–3131.

To post reply to a comment, click on the 'reply' button attached to each comment. To post a new comment (not a reply to a comment) check out the 'Write a Comment' tab at the top of the comments.