# Efficient LDPC Encoder Design for IoT-Type Devices
## 5 LDPC Encoder Design for a Microcontroller Implementation
### Elementary Computations  
In this section, we present how the encoding process can be decomposed into elementary operations that are suitable for a typical microcontroller CPU, as well as how the code specification, i.e., the structured parity-check matrix, can be efficiently memorized. An efficient sparse matrix representation of \(\mathbf{H}\) can utilize indexes of nonzero elements, \(\text{ind}(\mathbf{H})\), which is a matrix with the same number of rows as \(\mathbf{H}\), but only a few columns with indexes of nonzero elements in every row of \(\mathbf{H}\). For regular codes, with every row of \(\mathbf{H}\) that has weight \(d_{c}\), this representation requires the storage of \(M\times d_{c}\) index values. However, for the QC-LDPC codes applied in our research, an even more efficient representation is possible, similar to hardware implementation of, for example, [32], in which \(\mathbf{H}\) is represented by the following:  
* Indexes of nonzero submatrices \(\mathbf{P}^{i_{ij}}\) in (1);
* Circular shift values \(s_{i,j}\) in (1) gathered in matrix representation \(\mathbf{S}\). This way, the storage is reduced to \((M/P)\times d_{c}\) indexes plus \((M/P)\times d_{c}\) circular shift values, which gives, in total, \(2(M/P)\times d_{c}\) integer values, which can often fit into an 8-bit (uint8_t) representation if \(P<256\) and \(N/P<256\). In our implementation, the Richardson-Urbanke algorithm, according to expressions (6) and (7), is partitioned into steps that are realized sequentially in a CPU, as we illustrate in Figure 2.  
The first step is the preparation of the input information vector \(\mathbf{u}^{T}\), that is, buffering the incoming data into a vector \(\mathbf{u}^{T}\) of length \(K\). Then, in the following steps, intermediate-result vectors denoted by \(\mathbf{a},\mathbf{b},\ldots,\mathbf{h}\), as well as final parity bit vectors \(\mathbf{p}_{1},\mathbf{p}_{2}\) are calculated sequentially. The required partial operations can be categorized into three types:  
* Sparsely structured matrix by vector multiplication over \(\mathrm{GF}(2)\), e.g., \(\mathbf{a}:=\mathbf{A}\mathbf{u}^{T}\);
* Inverse of a lower-triangular sparse matrix by vector multiplication over \(\mathrm{GF}(2)\), e.g., \(\mathbf{b}:=\mathbf{T}^{-1}\mathbf{a}^{T}\);
* Addition over \(\mathrm{GF}(2)\), e.g., \(\mathbf{e}:=\mathbf{c}+\mathbf{d}\). Let us discuss these types of operations, beginning with the sparsely structured matrix by vector multiplication. The expression is  
\[\mathbf{a}:=\mathbf{A}\mathbf{u}^{\mathbf{T}} \tag{8}\]  
For the QC-LDPC codes with a structured parity-check matrix, as in (1), this can be formulated as follows:  
Figure 2: Block diagram presenting consecutive steps in the efficient encoding algorithm. \[ \begin{bmatrix}\mathbf{a}_{1}^{T}\\ \mathbf{a}_{2}^{T}\\ \vdots\\ \mathbf{a}_{I-L}^{T}\end{bmatrix} := \begin{bmatrix}\mathbf{P}^{s_{1,1}}&\ldots& \mathbf{P}^{s_{1,l}}\\ \mathbf{P}^{s_{2,1}}&\ldots&\mathbf{P}^{s_{2,l}}\\ \vdots&\ddots&\vdots\\ \mathbf{P}^{s_{I-1,1}}&\ldots&\mathbf{P}^{s_{I-1,l}}\end{bmatrix} \cdot \begin{bmatrix} \mathbf{u}_{1}^{T}\\ \mathbf{u}_{2}^{T}\\ \vdots\\ \mathbf{u}_{I-L}^{T}\end{bmatrix} \\ = \begin{bmatrix}\mathbf{P}^{s_{1,1}}\mathbf{u}_{1}^{T}&\ldots& \mathbf{P}^{s_{1,l}}\mathbf{u}_{I-L}^{T}\\ \mathbf{P}^{s_{2,1}}\mathbf{u}_{1}^{T}&\ldots&\mathbf{P}^{s_{2,l}}\mathbf{u}_ {I-L}^{T}\\ \vdots&\ddots&\vdots\\ \mathbf{P}^{s_{I-1,l}}\mathbf{u}_{1}^{T}&\ldots&\mathbf{P}^{s_{I-l,l}}\mathbf{ u}_{I-L}^{T}\end{bmatrix}  \tag{9}\]  
where \(\mathbf{u}_{1}\), \(\mathbf{u}_{2},\ldots\) and \(\mathbf{a}_{1}\), \(\mathbf{a}_{2},\ldots\) are the subvectors of, respectively, \(\mathbf{u}\) and \(\mathbf{a}\) of size \(1\times P\). In (9), every subvector calculation of  
\[\mathbf{a}_{i}^{T}:=\mathbf{P}^{s_{i,1}}\mathbf{u}_{1}^{T}+\mathbf{P}^{s_{i,2} }\mathbf{u}_{2}^{T}+\ldots+\mathbf{P}^{s_{i,j-l}}\mathbf{u}_{J-I}^{T} \tag{10}\]  
requires the performance of elementary operations of the type \(\mathbf{P}^{s_{i}/\mathbf{u}}\mathbf{u}_{j}^{T}\), as well as additions over GF(2).