# Efficient LDPC Encoder Design for IoT-Type Devices
## 5 LDPC Encoder Design for a Microcontroller Implementation
### Elementary Computations
Every \(\mathbf{P}^{s_{i,j}}\) for the QC-LDPC code is one of the following:  
* A zero matrix (\(s_{i,j}=\infty\)); then, \(\mathbf{P}^{s_{i,j}}\mathbf{u}_{j}^{T}=\mathbf{0}\). * A circular shift of an identity matrix by \(s_{i,j}\); then it can easily be verified that \(\mathbf{P}^{s_{i,j}}\mathbf{u}_{j}^{T}\) is a circular shift of \(\mathbf{u}_{j}^{T}\) by \(s_{i,j}\) positions. Therefore, computing (10) for QC-LDPC codes requires elementary operations of circular shifts of subvectors of \(\mathbf{u}^{T}\) of length \(P\), as well as modulo-2 additions of subvectors of length \(P\), which are equivalent to additions over GF(2). Similar elementary operations can be indicated for the other sparsely structured matrices by vector multiplications in Figure 2.  
The \(\mathbf{T}^{-1}\) by vector multiplication, e.g., \(\mathbf{b}^{T}:=\mathbf{T}^{-1}\mathbf{a}^{T}\), can be realized due to the equivalency:  
\[\mathbf{b}^{T}=\mathbf{T}^{-1}\mathbf{a}^{T}\Leftrightarrow\mathbf{Tb}^{T}= \mathbf{a}^{T} \tag{11}\]  
which, in the matrix form, is expressed as  
\[ \begin{bmatrix}\mathbf{P}^{0}&\mathbf{0}&\mathbf{0}&\cdots&\mathbf{0}\\ \mathbf{P}^{s_{2,(J-1+g+1)}}&\mathbf{P}^{0}&\mathbf{0}&\cdots&0\\ \vdots&&\ddots&\vdots\\ \mathbf{P}^{s_{(I-g),(J-1+g+1)}}&\mathbf{P}^{s_{(I-g),(J-1+g+2)}}&\mathbf{P}^{ s_{(I-g),(J-1+g+3)}}&\cdots&\mathbf{P}^{0}\end{bmatrix} \cdot \begin{bmatrix} \mathbf{b}_{1}^{T}\\ \mathbf{b}_{2}^{T}\\ \vdots\\ \mathbf{b}_{I-L}^{T}\end{bmatrix} = \begin{bmatrix}\mathbf{a}_{1}^{T}\\ \mathbf{a}_{2}^{T}\\ \vdots\\ \mathbf{a}_{I-L}^{T}\end{bmatrix}  \tag{12}\]  
Examining (12), it can be noticed that subvectors \(\mathbf{b}_{1},\mathbf{b}_{2},\ldots\) can be subsequently computed. First, \(\mathbf{b}_{1}\) is computed according to:  
\[\mathbf{P}^{0}\mathbf{b}_{1}^{T}=\mathbf{a}_{1}^{T}\ \Rightarrow\ \mathbf{b}_{1}^{T}=\mathbf{a}_{1}^{T} \tag{13}\]  
Then, \(\mathbf{b_{2}}\) is computed according to:  
\[\mathbf{P}^{s_{2,(J-1+g+1)}}\mathbf{b}_{1}^{T}+\mathbf{P}^{0}\mathbf{b}_{2}^{T} =\mathbf{a}_{2}^{T}\ \Rightarrow\ \mathbf{b}_{2}^{T}=(\mathbf{P}^{s_{2,(J-1+g+1)}})\mathbf{b}_{1}^{T}+ \mathbf{a}_{2}^{T} \tag{14}\]  
and then every subsequent \(i\)th subvector \(\mathbf{b}_{i}^{T}\) is computed according to the following expression:  
\[ \begin{gathered}\mathbf{P}^{s_{i,(J-1+g+1)}}\mathbf{b}_{1}^{T}+ \mathbf{P}^{s_{i,(J-1+g+2)}}\mathbf{b}_{2}^{T}+\cdots+\mathbf{P}^{0}\mathbf{b}_ {i}^{T}=\mathbf{a}_{i}^{T}\ \Rightarrow\\ \mathbf{b}_{i}^{T}=\mathbf{P}^{s_{i,(J-1+g+1)}}\mathbf{b}_{1}^{T}+ \mathbf{P}^{s_{i,(J-1+g+2)}}\mathbf{b}_{2}^{T}+\cdots+\mathbf{P}^{s_{i,(J-1+g+ 1)}}\mathbf{b}_{I-1}^{T}+\mathbf{a}_{i}^{T}\end{gathered} \end{gathered} \tag{15}\]  
This last expression shows that computing every subsequent subvector \(\mathbf{b}_{i}^{T}\) requires only circular shift operations of previously calculated subvectors \(\mathbf{b}_{1}^{T},\ldots,\mathbf{b}_{(i-1)}^{T}\) and additions over GF(2). The subvector additions over GF(2) are equivalent to the vector-wise binary exclusive- or (XOR) operations. The last step of encoding, as shown in Figure 2, is assembling a code vector \(\mathbf{c}\) as follows:  
\[\mathbf{c}= \begin{bmatrix}\mathbf{u}&\mathbf{p_{1}}&\mathbf{p_{2}}\end{bmatrix}  \tag{16}\]  
We can conclude that the whole encoding process can be partitioned into the following elementary operations:  
* Circular shift operations of subvectors of length \(P\);
* Subvector additions over GF(2) realized with XOR operations. We remark that a classic encoding that employs a generator matrix can also be realized with just GF(2) additions, but the generator matrix representation is not sparse. Meanwhile, the presented formulation operates directly on a sparse parity-check matrix; therefore, many of the submatrices are all-zero, thus significantly reducing the computational complexity.