# Efficient LDPC Encoder Design for IoT-Type Devices
## 4 Richardson-Urbanke Encoding Algorithm  
A basic encoding method for any linear block codes can be based on a generator matrix. However, in general, the generator matrix of an LDPC code is a dense \(N\times K\) matrix, which in itself is a great amount of data for storing in limited memory, and it requires dense matrix operations. Therefore, it is desirable to employ a more efficient LDPC encoding method, as introduced by [PERSON] and [PERSON] [43], who directly utilized the parity-check matrix \(\mathbf{H}\), which is sparse by definition. This method requires an \(\mathbf{H}\) matrix in an ALT form. Let us shortly introduce the Richardson-Urbanke method in the context of QC-LDPC codes. We assume that by making use of some of the known methods [20; 24], the parity-check matrix is constructed in (or converted into) an ALT form, with \(P\times P\) submatrices of the QC-LDPC structure. Let the \(\mathbf{H}\) in ALT form be partitioned as follows:  
\[\mathbf{H}= \begin{bmatrix}\mathbf{A}&\mathbf{B}&\mathbf{T}\\ \mathbf{C}&\mathbf{D}&\mathbf{E}\\ \end{bmatrix} , \tag{2}\]  
where \(\mathbf{A}\) is of size \((I-g)P\times(J-I)P\), \(\mathbf{B}\) is \((I-g)P\times gP\), \(\mathbf{T}\) is \((I-g)P\times(I-g)P\), \(\mathbf{C}\) is \(gP\times(J-I)P\), \(\mathbf{D}\) is \(gP\times gP\), and \(\mathbf{E}\) is \(gP\times(I-g)P\), where \(g\) is the gap size, that is, the size of the non-triangular part. The structure of the \(\mathbf{T}\) matrix is essential, which should be lower triangular, that is,  
\[\mathbf{T}= \begin{bmatrix}\mathbf{P}^{0}&\mathbf{0}&\mathbf{0}&\cdots& \mathbf{0}\\ \mathbf{P}^{s_{2},(J-I+g+1)}&\mathbf{P}^{0}&\mathbf{0}&\cdots&\mathbf{0}\\ \mathbf{P}^{s_{3},(J-I+g+1)}&\mathbf{P}^{s_{3},(J-I+g+2)}&\mathbf{P}^{0}&& \mathbf{0}\\ \vdots&&\ddots&&\vdots\\ \mathbf{P}^{s(I-g),(J-I+g+1)}&\mathbf{P}^{s(I-g),(J-I+g+2)}&\cdots&\mathbf{P}^ {s(I-g),(J-1)}&\mathbf{P}^{0}\\ \end{bmatrix}  \tag{3}\]  
where \(\mathbf{P}^{0}\) is an identity matrix of size \(P\times P\). An important feature is that \(\mathbf{T}^{-1}\) multiplication by any vector can be performed with linear complexity through a back-substitution operation [43]. The systematic encoding process of an information vector \(\mathbf{u}=\{u_{1},u_{2},\dots,u_{K}\}\) is based on determining two parity sub-vectors \(\mathbf{p}_{1}\) and \(\mathbf{p}_{2}\) with lengths \(gP\) and \((I-g)P\), respectively, such that the obtained code vector is \(\mathbf{c}=[\mathbf{u},\mathbf{p}_{1},\mathbf{p}_{2}]\). Considering (2), the parity-check equation \(\mathbf{H}\mathbf{c}^{T}=\mathbf{0}\) can be divided into two parts:\[\mathbf{Au}^{T}+\mathbf{B}\mathbf{p}_{1}^{T}+\mathbf{T}\mathbf{p}_{2}^{T} =\mathbf{0}, \tag{4}\] \[\mathbf{Cu}^{T}+\mathbf{D}\mathbf{p}_{1}^{T}+\mathbf{E}\mathbf{p}_{2 }^{T} =\mathbf{0}. \tag{5}\]  
After simple algebraic transformations with GF(2) arithmetic, the expressions for calculating \(\mathbf{p}_{1}\) and \(\mathbf{p}_{2}\) are obtained:  
\[\mathbf{p}_{1}^{T} =\mathbf{\Phi}^{-1}(\mathbf{ET}^{-1}\mathbf{Au}^{T}+\mathbf{Cu}^ {T}), \tag{6}\] \[\mathbf{p}_{2}^{T} =\mathbf{T}^{-1}(\mathbf{Au}^{T}+\mathbf{B}\mathbf{p}_{1}^{T}), \tag{7}\]  
where \(\mathbf{\Phi}=\mathbf{ET}^{-1}\mathbf{B}+\mathbf{D}\). The multiplication by the sparse sub-matrices \(\mathbf{A}\), \(\mathbf{B}\), \(\mathbf{C}\), \(\mathbf{E}\), and \(\mathbf{T}^{-1}\), which is realized through back-substitution, is an operation with complexity that is linearly dependent on the code length \(N\). More importantly, as will be presented below, for QC-LDPC matrices, as in (1), the encoding can be implemented with just two elementary operations: the GF(2) addition and circular shifting of sub-vectors. However, straightforward multiplication by \(\mathbf{\Phi}^{-1}\) can be problematic. The first reason is that \(\mathbf{\Phi}\) is not guaranteed to be an invertible matrix. In such a case, in order to use the Richardson-Urbanke encoding method, \(\mathbf{H}\) must be rearranged by row and column permutations such that an invertible \(\mathbf{\Phi}\) is achieved.