# Flexible 5G New Radio LDPC Encoder Optimized for High Hardware Usage Efficiency
## 2 Encoding of LDPC Codes
### Richardson-Urbanke LDPC Encoding Method  
[PERSON] and [PERSON] [20] proposed an LDPC encoding method that provides an approximately linear computational complexity. The proposed method consists of two steps: (1) offline preprocessing and (2) encoding. During the preprocessing step, the PCM is transformed to the approximate lower triangular (ALT) form in such a way that codewords can be represented in a systematic form as follows:  
\[\mathbf{x}=\left[\begin{array}{cc}\mathbf{i}&\mathbf{p}_{1}&\mathbf{p}_{2} \end{array}\right], \tag{8}\]  
where \(\mathbf{p}_{1}\) represents a vector of \(g\) parity bits, whereas \(\mathbf{p}_{2}\) represents a vector of remaining (\(m-g\)) parity bits.  
After the preprocessing step, the PCM has the following form:  
\[\mathbf{H}=\left[\begin{array}{cc}\mathbf{A}&\mathbf{B}&\mathbf{T}\\ \mathbf{C}&\mathbf{D}&\mathbf{E}\end{array}\right], \tag{9}\]  
where submatrices \(\mathbf{A}\) (of size \((m-g)\times(n-m)\)), \(\mathbf{B}\) (of size \((m-g)\times g\))), \(\mathbf{C}\) (of size \(g\times(n-m)\)), \(\mathbf{D}\) (of size \(g\times g\)), and \(\mathbf{E}\) (of size \(g\times(m-g)\)) are sparse matrices, whereas the submatrix \(\mathbf{T}\) (of size \((m-g)\times(m-g)\)) is a sparse lower triangular matrix. The preprocessing transformation is performed by permuting rows and columns inside the PCM. Appropriate permutations can be obtained by greedy algorithms described in [20], which provide \(g\) to be as small as possible. In addition, it is required that the matrix \(-\mathbf{E}\mathbf{T}^{-1}\mathbf{B}+\mathbf{D}\) stays nonsingular in the Galois field GF(2).  
If the PCM transformation is successfully completed, parity bits can be calculated using the following equations:  
\[\mathbf{p}_{1}^{\mathrm{T}}=\left(-\mathbf{E}\mathbf{T}^{-1}\mathbf{B}+ \mathbf{D}\right)^{-1}\left(-\mathbf{E}\mathbf{T}^{-1}\mathbf{A}+\mathbf{C} \right)\mathbf{i}^{\mathrm{T}}, \tag{10}\]  
\[\mathbf{p}_{2}^{\mathrm{T}}=-\mathbf{T}^{-1}\Big{(}\mathbf{A}\mathbf{i}^{ \mathrm{T}}+\mathbf{B}\mathbf{p}_{1}^{\mathrm{T}}\Big{)}. \tag{11}\]Multiplications with **A**, **B**, **C**, and **E** are multiplications with sparse matrices, whose computational complexity is linear (\(O(n)\)). Additions also have linear complexity. Since **T** is a lower triangular matrix, all multiplications with \(\textbf{T}^{-1}\) can be replaced with a forward substitution, given that \(\textbf{T}^{-1}\textbf{a}=\textbf{b}\) is equivalent to the system \(\textbf{a}=\textbf{T}\textbf{b}\). Since **T** is also sparse, the performed forward substitution is a process of linear complexity. The only quadratic complexity calculation is multiplication by dense matrix \(\left(-\textbf{ET}^{-1}\textbf{B}+\textbf{D}\right)^{-1}\left(O\left(g^{2} \right)\right)\), which is why the transformation algorithm searches for permutations that will provide small \(g\), preferably \(g\sim\sqrt{n}\). Such approximately linear encoding complexity is the main reason why many LDPC encoders are essentially based on the RU method [20; 21; 22; 23; 24; 25; 26; 27]. The reported weaknesses of this method are the necessity for multiple consequent operations, which generally leads to long critical paths in hardware implementations [28], and low potential for encoding flexibility [14].