LowDensity Parity Check (LDPC) Encoding
Lowdensity parity check (LDPC) is a linear errorcorrecting coding scheme that uses a parity check matrix that provides only a few ones with respect to a much larger number of zeros.
The main advantage of the parity check matrix is that it provides a performance that is almost equal to the capacity of many different channels and linear time complex algorithms for decoding. Furthermore, parity check matrices are suited for implementations that make heavy use of parallelism.
An LDPC code is a block code that has a parity check matrix H, every row and column of which is sparse. A Regular Gallager Code is an LDPC code in which every column of H has a weight, j, and every row has a weight, k. Regular Gallager codes are constructed at random, subject to these constraints.
For example, if

the number of ones in each column (j) = 3

the number of ones in each row (k) = 6

the number of columns (n) = 12

the number of rows (m) = 6 (because
$m=\text{\hspace{0.17em}}n\times j\xf7k$)

the rate of (n,j,k) LDPC Code is
$R\ge 1(j\xf7k)$
Then
$H=\left(\begin{array}{cccccccccccc}1& 1& 1& 0& 0& 1& 1& 0& 0& 0& 1& 0\\ 1& 1& 1& 1& 1& 0& 0& 0& 0& 0& 0& 1\\ 0& 0& 0& 0& 0& 1& 1& 1& 0& 1& 1& 1\\ 1& 0& 0& 1& 0& 0& 0& 1& 1& 1& 0& 1\\ 0& 1& 0& 1& 1& 0& 1& 1& 1& 0& 0& 0\\ 0& 0& 1& 0& 1& 1& 0& 0& 1& 1& 1& 0\end{array}\right)$
If the number of ones per column or row is not constant, the code is an irregular LDPC code. Usually, irregular LDPC codes outperform regular LDPC codes.
Parity Bits
The decoder assumes that the parity bits are placed at the end of the code word. Hence, it returns the first part of the code word, which are the message bits.
Likelihood Calculation
Belief Propagation algorithm is a subclass of messagepassing algorithms. The messages passed along the edges in this algorithm are probabilities, or beliefs. It is advantageous to work with likelihoods, or loglikelihoods instead of probabilities. For a binary random variable x, let
$L\left(x\right)=\mathrm{Pr}[x=0]\xf7\mathrm{Pr}[x=1]$ be the likelihood of x, where Pr denotes probability.
Given another random variable y, the conditional likelihood of x denoted L(x/y) is defined as
$\mathrm{Pr}[x=1y]\xf7\mathrm{Pr}[x=0y]$.
The likelihood ratio is defined as
$L=\mathrm{Pr}[x=1y]\xf7\mathrm{Pr}[x=0y]$.
For example, for a BSC channel, if the probability of error = p and the probability of no error =
$1p$, then the likelihood ratio =
$(1p)\xf7p$.
The likelihood calculation depends upon the specific choice of the symbol map used in the modulation scheme. An example of likelihood calculation for a BPSK additive white Gaussian noise (AWGN) channel, if bit 0 is mapped to symbol point 1 and bit 1 is mapped to symbol point 1, is
$P(x=0)={P}_{y}(x=0y)=\frac{1}{1+{e}^{\frac{2y}{{\sigma}^{2}}}}P(x=0)={P}_{y}(x=0y)=\frac{1}{1+{e}^{\frac{2y}{{\sigma}^{2}}}}L={e}^{\frac{2y}{{\sigma}^{2}}}$
where x and y are binary random variables.