# Efficient QC-LDPC Encoder for 5G New Radio
## 3 LDPC Encoding Algorithms
### LDPC Encoding with the RU Method  
Instead of determining a generator matrix for \(H\), an LDPC code can be directly encoded using the parity check matrix by transforming it into a lower triangular form and applying back substitution. The RU encoding method, which was proposed by [PERSON] and [PERSON] [13], is a linear time encoding method for sparse parity check matrices. The underlying principle is transformation using only row and column permutations, to reformulate a parity check matrix \(H\) into a sparse matrix. Therefore, this approach can reduce the complexity more than the \(G\) matrix multiplication method. The RU algorithm consists of two steps: a pre-processing step and actual encoding step.  
First, in the pre-processing step, the parity check matrix \(H\) is converted into the approximate lower triangular (ALT) form, as shown in Figure 3. The parity check matrix \(H\) is given by the \(M\times N\) matrix, where \(N\) is the block length of the code and \(M\) is the number of parity check equations. Given that the matrix transformation is realized solely by row and column permutations, the \(H\) matrix remains a sparse matrix:  
\[H_{T}=\begin{bmatrix}A&B&T\\ C&D&E\end{bmatrix}. \tag{9}\]  
Here, the matrix \(T\) has a lower triangular form with 1s along the diagonal, and all the entries above the diagonal are 0s. By multiplying \(H\) from the left by  
\[\begin{bmatrix}I&0\\ -ET^{-1}&I\end{bmatrix}, \tag{10}\]the following is obtained:  
\[\bar{H}=\begin{bmatrix}A&B&T\\ \tilde{C}&\tilde{D}&0\end{bmatrix}, \tag{11}\]  
where  
\[\begin{array}{l}\tilde{C}=-ET^{-1}A+C,\\ \tilde{D}=-ET^{-1}B+D,\\ \tilde{E}=-ET^{-1}T+E=0.\end{array} \tag{12}\]  
The actual encoding step is performed by matrix-multiplication, forward-substitution and vector addition operations. Let the codeword \(C=[s\quad p_{1}\quad p_{2}]\) where \(s\) represents the information bits, \(p_{1}\) denotes the first \(G\) parity check bits, and \(p_{2}\) contains the remaining \((M-G)\) parity check bits. The codeword \(C\) must satisfy the parity check equation \(HC^{T}=0^{T}\). The two equations are then expressed by:  
\[\begin{array}{l}As^{T}+Bp_{1}^{T}+Tp_{2}^{T}=0^{T},\\ \tilde{C}s^{T}+\tilde{D}p_{1}^{T}+0p_{2}^{T}=0^{T}.\end{array} \tag{13}\]  
Using the RU method, the calculation of the parity bits in the first parity portion \(p_{1}\) is only dependent on the information bits, given that \(E\) was cleared. Hence, it can be calculated independently of the parity bits in \(p_{2}\). If \(\tilde{D}\) is non singular, then \(p_{1}^{T}\) can be obtained from Equation (13):  
\[p_{1}^{T}=\tilde{D}^{-1}\tilde{C}s^{T}. \tag{14}\]  
If \(\tilde{D}\) is singular in GF(2), then it is necessary to further permute the columns of \(\tilde{H}\) to eliminate this singularity. Once \(p_{1}\) is known, \(p_{2}\) can be determined using Equation (13):  
\[p_{2}^{T}=-T^{-1}(As^{T}+Bp_{1}^{T}). \tag{15}\]  
Given that \(T\) is the lower triangular form, \(p_{2}\) can be found using back substitution. The complexity of this encoding procedure can be kept low since \(A\), \(B\) and \(T\) are sparse. Tables 3 and 4 present the complexity of calculation of \(p_{1}^{T}\) and \(p_{2}^{T}\), respectively. The complexity of the RU algorithm is given by \(O(N+G^{2})\), where \(N\) is the block length and \(G\) is the gap to linear encoding. The gap is actually the  
Figure 3: The parity check matrix \(H\) in approximate lower triangular form.  
number of rows of the parity check matrix that cannot be set into a triangular form using only row and column permutations. With a small gap \(G\), the lower encoding complexity for the code is achieved.  
The disadvantage of encoding using the RU method is that there is no exact programmable step-by-step algorithm. The multiple matrix calculations in this algorithm significantly limit the development of a rapid flexible encoder [28]. In addition, the RU method is subjected to a long critical path and odd constraints, which could render the LDPC encoder non-systematic [19].