# Low Power QC-LDPC Decoder Based on Token Ring Architecture
## LDPC Codes and Their Decoding--Preliminaries
### LDPC Decoding Algorithm  
The classical LDPC decoding algorithms belong to the class of iterative belief propagation (BP) algorithms, as recalled by MacKay [5]. In BP, beliefs are propagated between nodes in a Tanner graph [36] representation of an LDPC code. This graph is a bipartite graph with so-called control nodes representing rows of \(\mathbf{H}\), bit nodes representing columns of \(\mathbf{H}\) and edges representing nonzero positions in \(\mathbf{H}\). The commonly used simplified method for determining the beliefs (messages propagated between nodes in the algorithm) is known as the Min-Sum algorithm [37; 38; 39]. The decoding process is an estimation process of the transmitted code vector \(\mathbf{x}=[x_{1},x_{2},...,x_{N}]\) from input data (received \"soft\" values \(\mathbf{y}=[y_{1},y_{2},...,y_{N}]\)). The following denotations are used in the algorithm presentation:  
\(:=\) symbol means \"becomes\",  
\(\mathbf{c}=[c_{1},c_{2},\ldots,c_{N}]\)--code vector,  
\(\mathbf{y}=[y_{1},y_{2},\ldots,y_{N}]\)--received vector,  
\(Q_{nm}\)--belief LLR value from the \(n\)-th bit vertex to the \(m\)-th Tanner graph control vertex,  
\(L(x_{n}|y_{n})\)--LLR a priori probabilities for the \(n\)-th bit,  
\((1,N)\)--set of integers between 1 and \(N\),  
\(\mathcal{N}(m)\)--a set of column indexes in the parity check matrix \(\mathbf{H}\) containing one in the \(m\)-th row,  
Figure 1: An example of a check matrix \(\mathbf{H}\) of the Quasi-Cyclic Low-Density Parity-Check (QC-LDPC) code and simplified notation in the form of an offset matrix. Figure 2: Shifts of the submatrixes matrix \(P\) by 0, 1, 2 and 3 positions. \(\mathcal{M}(n)\)--a set of row indexes in the parity check matrix \(\mathbf{H}\) containing one in the \(n\)-th column, \(R_{mn}\)--message from the \(m\)-th control vertex to the \(n\)-th bit vertex of Tanner graph, \(X_{n}\)--the \(n\)-th value of the decoded vector. The Min-Sum decoding algorithm can be presented in consecutive steps as follows:  
1. _Initialization of the decoder based on \"soft\" decisions_: Based on the vector of data \(\mathbf{y}\) received from the demodulator, the probability values are determined, which can be written as \(P(c_{n}=0|y_{n})\) and \(P(c_{n}=1|y_{n})\) for \(n=1,...,N\), which are the probabilities that the \(c_{n}\) bit was originally transmitted if the \(y_{n}\) value has been received. From values \(P(c_{n}=0|y_{n})\) and \(P(c_{n}=1|y_{n})\), Log-Likelihood Ratios (LLR) are determined, which are the actual algorithm input. For every \(m\in\mathcal{M}(n)\) and \(n\in(1,N)\). Initialization of \(Q_{nm}\) beliefs (messages) can be expressed as: \[Q_{nm}:=L(c_{n}|y_{n})=\ln\left(\frac{P(c_{n}=0|y_{n})}{P(c_{n}=1|y_{n})}\right)\] (1)
2. _Control nodes processing_: Calculation of \(R_{mn}\), messages from \(m\)th control node to \(n\)th bit node. For every \(n\in\mathcal{N}(m)\) and \(m\in(1,M)\): \[R_{mn}:=\left[\prod_{k\in\mathcal{N}(m)\backslash n}\text{sgn}(Q_{km})\right] \min_{k\in\mathcal{N}(m)\backslash n}|Q_{km}|\] (2)
3. _Bit nodes processing_: Recalculation of \(Q_{nm}\), messages from \(n\)th bit node to \(m\)th control node. For every \(m\in\mathcal{M}(n)\) and \(n\in(1,N)\): \[Q_{nm}:=L(c_{n}|y_{n})+\sum_{k\in\mathcal{M}(n)\backslash m}R_{kn}\] (3)
4. _Total beliefs update_: Calculation of the current beliefs about all bits in \(\mathbf{c}\). For every \(n\in(1,N)\): \[Q_{n}:=L(c_{n}|y_{n})+\sum_{k\in\mathcal{M}(n)}R_{kn}\] (4)
5. _Hard decisions update_: Making trial hard decisions. For every \(n\in(1,N)\): \[X_{n}:=\left\{ \begin{array}{ll}1&\text{gdy }Q_{n}<0\\ 0&\text{gdy }Q_{n}\geq 0\end{array} \right.\] (5)
6. _Verification of control equations_: \[\mathbf{H}X^{T}=0\] (6)
7. _Another iteration_: If the parity check Equation (6) is satisfied or the maximum number of iterations is reached, the computations are terminated. Otherwise, the next iteration starts from point (2). The hardware implementation of the QC-LDPC decoder is closely related to the content of the parity check matrix \(\mathbf{H}\).