Documentation

This is machine translation

Translated by
Mouseover text to see original. Click the button below to return to the English verison of the page.

LDPC Decoder

Decode binary low-density parity-check code specified by parity-check matrix

Library

Block sublibrary of Error Detection and Correction

Description

This block implements the message-passing algorithm for decoding low-density parity-check (LDPC) codes, which are linear error control codes with sparse parity-check matrices and long block lengths that can attain performance near the Shannon limit.

The LDPC Decoder block is designed to:

• Decode generic binary LDPC codes where no patterns in the parity-check matrix are assumed.

• Execute a number of iterations you specify or run until all parity-checks are satisfied.

• Output hard decisions or soft decisions (log-likelihood ratios) for decoded bits.

(nk) and n are the number of rows and columns, respectively, in the parity-check matrix.

This block accepts a real-valued, $n×1$ column vector input signal of type double. Each element is the log-likelihood ratio for a received bit (more likely to be 0 if the log-likelihood ratio is positive). The first k elements correspond to the information part of a codeword.

Both the input and the output are discrete-time signals. The ratio of the output sample time to the input sample time is $n/k$ if only the information part is decoded, and 1 if the entire codeword is decoded.

Decoding Algorithm

The input to the LDPC decoder is the log-likelihood ratio (LLR), $L\left({c}_{i}\right)$, which is defined by the following equation

where ${c}_{i}$ is the ith bit of the transmitted codeword, c. There are three key variables in the algorithm: $L\left({r}_{ji}\right)$, $L\left({q}_{ij}\right)$, and $L\left({Q}_{i}\right)$. $L\left({q}_{ij}\right)$ is initialized as $L\left({q}_{ij}\right)=L\left({c}_{i}\right)$. For each iteration, update $L\left({r}_{ji}\right)$, $L\left({q}_{ij}\right)$, and $L\left({Q}_{i}\right)$ using the following equations

`$L\left({r}_{ji}\right)=2\text{\hspace{0.17em}}\text{atanh}\text{\hspace{0.17em}}\left(\prod _{{i}^{\prime }\in {V}_{j}\i}\mathrm{tanh}\left(\frac{1}{2}L\left({q}_{{i}^{\prime }j}\right)\right)\right)$`
`$L\left({q}_{ij}\right)=L\left({c}_{i}\right)+\sum _{{j}^{\prime }\in {C}_{i}\j}L\left({r}_{{j}^{\prime }i}\right)$`
`$L\left({Q}_{i}\right)=L\left({c}_{i}\right)+\sum _{{j}^{\prime }\in {C}_{i}}L\left({r}_{{j}^{\prime }i}\right)$`

where the index sets, ${C}_{i}\j$ and ${V}_{j}\i$, are chosen as shown in the following example.

Suppose you have the following parity-check matrix H:

`$H=\left(\begin{array}{cccccccccc}1& 1& 1& 1& 0& 0& 0& 0& 0& 0\\ 1& 0& 0& 0& 1& 1& 1& 0& 0& 0\\ 0& 1& 0& 0& 1& 0& 0& 1& 1& 0\\ 0& 0& 1& 0& 0& 1& 0& 1& 0& 1\\ 0& 0& 0& 1& 0& 0& 1& 0& 1& 1\end{array}\right)$`

For $i=5$ and $j=3$, the index sets would be

At the end of each iteration, $L\left({Q}_{i}\right)$ provides an updated estimate of the a posteriori log-likelihood ratio for the transmitted bit ${c}_{i}$.

The soft-decision output for ${c}_{i}$ is $L\left({Q}_{i}\right)$. The hard-decision output for ${c}_{i}$ is 1 if $L\left({Q}_{i}\right)<0$, and 0 otherwise.

If the property `DoParityCheck` is set to `'no'`, the algorithm iterates as many times as specified by the Number of iterations parameter.

If the property `DoParityCheck` is set to `'yes'`, then at the end of each iteration the algorithm verifies the parity check equation ($H{c}^{\text{T}}=0$) and stops if it is satisfied.

In this algorithm, atanh(1) and atanh(-1) are set to be 19.07 and -19.07 respectively to avoid infinite numbers from being used in the algorithm's equations. These numbers were chosen because MATLAB returns 1 for tanh(19.07) and -1 for tanh(-19.07), due to finite precision.

Parameters

Parity-check matrix

This parameter accepts a sparse matrix with dimension n -k by n (where n >k > 0) of real numbers. All nonzero elements must be equal to 1. The upper bound limit for the value of n is 231-1

Output format

The output is a real-valued column vector signal. The options are `Information part` and ```Whole codeword```.

• When you this parameter to `Information part`, the output contains k elements.

• When you set this parameter to `whole codeword`, the output contains n elements

Decision type

The options are `Hard decision` and ```Soft decision```.

• When you set this parameter to `Hard decision`, the output is decoded bits (of type double or boolean).

• When you set this parameter to `Soft decision`, the output is log-likelihood ratios (of type double).

Output data type

This parameter appears only when Decision type is set to `Hard decision`.

The options are `boolean` and `double`.

Number of iterations

This can be any positive integer.

Stop iterating when all parity checks are satisfied

If checked, the block will determine whether the parity checks are satisfied after each iteration and stop if all are satisfied.

Output number of iterations executed

Creates an output port on the block when selected.

Output final parity checks

Creates an output port on the block when selected.

Supported Data Type

PortSupported Data Types
In
• Double-precision floating point

Out
• Double-precision floating point

• Boolean when Decision type is ```Hard decision```

Examples

Enter `commdvbs2` at the command line to see an example that uses this block.

References

[1] Gallager, Robert G., Low-Density Parity-Check Codes, Cambridge, MA, MIT Press, 1963.