MT LDPC Decoder (Flooding Schedule)

Download PDF

Updated2023-02-17
6 minute(s) read

Decodes LDPC code based on the standard message-passing schedule, which is a version of the flooding schedule. According to the flooding schedule, all the symbol nodes, and subsequently all the check nodes, pass new messages to their neighbors in each iteration.

The message that is sent from message node (v) to the check node (c) must not take into account the message sent in the previous iteration from c to v. The same is true for messages passed from check nodes to message nodes.

Inputs/Outputs

parity check matrix

The sparse parity check matrix generated by MT LDPC Generate Regular Parity Check Matrix or MT LDPC Generate Irregular Parity Check Matrix. You can also set a parity check matrix that is not rank deficient in this parameter.

likelihoods

The likelihoods of the received symbols.

maximum number of iterations

The maximum number of iterations for the iterative decoding process. The decoder stops iterating after the number of iterations exceeds the value of the maximum number of iterations or if the decoder satisfies other conditions.

Default value: 100

error in

Error conditions that occur before this node runs.

The node responds to this input according to standard error behavior.

Standard Error Behavior

Default value: No error

reset?

A Boolean that determines whether the internal state of the decoder is cleared.

TRUE	Clears any buffered bits from previous iterations.
FALSE	Continues decoding from the previous iteration. Any buffered bits from the previous iteration are added to the beginning of the input bit stream prior to decoding.

Default value: TRUE

output bit stream

Bit sequence decoded by this node.

error out

Error information.

The node produces this output according to standard error behavior.

Standard Error Behavior

Low-Density Parity Check (LDPC) Encoding

Low-density parity check (LDPC) is a linear error-correcting 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 = n \times j \div k$
)
the rate of (n,j,k) LDPC Code is
$R \geq 1 - (j \div k)$

Then

H = (\begin{matrix} 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{matrix})

H = (\begin{matrix} 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{matrix})

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 sub-class of message-passing algorithms. The messages passed along the edges in this algorithm are probabilities, or beliefs. It is advantageous to work with likelihoods, or log-likelihoods instead of probabilities. For a binary random variable x, let

L (x) = \Pr [x = 0] \div \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

\Pr [x = 1 | y] \div \Pr [x = 0 | y]

The likelihood ratio is defined as

L = \Pr [x = 1 | y] \div \Pr [x = 0 | y]

For example, for a BSC channel, if the probability of error = p and the probability of no error =

1 - p

, then the likelihood ratio =

(1 - p) \div p

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 = 0 | y) = \frac{1}{1 + e^{\frac{2 y}{σ^{2}}}} P (x = 0) = P_{y} (x = 0 | y) = \frac{1}{1 + e^{\frac{- 2 y}{σ^{2}}}} L = e^{\frac{2 y}{σ^{2}}}

P (x = 0) = P_{y} (x = 0 | y) = \frac{1}{1 + e^{\frac{2 y}{σ^{2}}}} P (x = 0) = P_{y} (x = 0 | y) = \frac{1}{1 + e^{\frac{- 2 y}{σ^{2}}}} L = e^{\frac{2 y}{σ^{2}}}

where x and y are binary random variables.

LabVIEW Modulation Toolkit

Table of Contents

MT LDPC Decoder (Flooding Schedule)

Inputs/Outputs

parity check matrix

likelihoods

maximum number of iterations

error in

reset?

output bit stream

error out

Low-Density Parity Check (LDPC) Encoding

Parity Bits

Likelihood Calculation

Log in to get a better experience