Decoding LDPC Codes with Belief Propagation

Belief propagation is widely used as a message-passing algorithm for inference on graphical models. Key features are:

• Its ability to perform ML estimation in some cases for a-cyclic graphs.
• Its ability to make estimations with complexity that grows only linearly with graph size for sparse graphs (generally speaking, ML estimation has exponential complexity).

This post aims to give an overview of belief propagation as an algorithm to decode LDPC codes and present an example implementation in Python for it. My implementation is available on a dedicated GitHub repo. However, it is aimed to be educational and was written for fun. Better, more optimized (though not necessarily easy to read) implementations exist. A more thorough explanation of the presented algorithm appears on my GitHub pages website.

LDPC Codes and Tanner Graphs

LDPC codes are a class of linear block error correction codes. Originally invented by Gallager in the 1960s, yet has become into wide use only in recent decades. They are used in cellular communications, Wi-Fi, video broadcasts, and more today.

The codes are based on sparse parity check matrices, denoted by H. Those matrices are binary matrices. The number of columns equals the block size, and the number of rows equals the number of check equations (some sources define it using the transpose). Typical matrices used in actual codes are much larger than the example matrix below.

Example of parity check matrix, image by author.

The matrix may be considered as a bi-adjacency matrix representing a bipartite graph. These graphs are termed Tanner graphs after Tanner, who perceived this representation for the code. In this case, the two sets of nodes forming the graph are termed:

• Check nodes (or c-nodes) with one node per row (or parity check equation).
• Variable nodes (or v-nodes) with one node per column (one bit received from the channel).

Below you can see the graph corresponding to the above matrix:

Tanner graph corresponding to the matrix H, image by author.

For a more detailed presentation of LDPC codes, you can look up any of the great sources online, for instance, this medium post or my GitHub pages website dedicated to LDPC codes.

Belief Propagation

Message Passing

The basic concept of the algorithm involves message passing. Messages are passed iteratively between adjacent nodes (c-nods to v-nodes and vice versa) until convergence or an apriori dictated maximal number of iterations. The nature of the messages involves probabilities or log-likelihoods of probabilities. As nodes receive messages from their nearest neighbors, they improve their estimate regarding received bits. Since Tanner graphs for LDPC codes typically include cycles, the algorithm may not converge to the ML estimate. However, for sufficiently long blocks (large graphs), with sufficiently long cycles, the algorithm has been shown empirically to perform well.

Another key feature is the passing of extrinsic information. Namely, when a node passes a message to another, it uses information from all other neighbors to compose the message, but not information provided by the message recipient.

Since our graph contains two types of nodes, they will pass fundamentally different kinds of information in their messages.

• Variable nodes pass messages that involve the log-likelihood of some bit being 0 or 1 by processing information obtained from other check nodes and the channel.
• Check nodes pass messages which involve the log-likelihood of a parity equation is satisfied by processing information obtained from other variable nodes.

Probability and Likelihoods

I do not wish to go into too many details here (and medium isn’t very math-friendly), so more information appears here. We define:

as the probability of some bit cᵢ being equal to b=0,1, conditioned on:

1. The event that parity check equations involving node cᵢ are satisfied.
2. The value received from the channel yᵢ.
3. Messages obtained from neighboring check nodes, except for node j.

We also define:

as the probability of the j-th check equation to be satisfied conditioned on bit value and the messages received from all variable nodes except node i.

Lastly, we define four log-likelihoods:

as the log-likelihood ratio of channel symbols, note that this value will depend on the model assumed for the channel.

as the log-likelihood ratio of validity of parity equation j given bit value using information extrinsic to v-node i.

as the log-likelihood ratio of bit value (v-node i) using information extrinsic to c-node j.

as the log-likelihood of bit value (v-node i), which is used to perform hard estimates regarding bit values.

Our messages use these values. Specifically, the log-likelihood ratio of “q” is used as the messages sent from v-nodes to c-nodes, and the log-likelihood ratio of “r” is used as the messages passed from c-nodes to v-nodes.

Update Rules

As said before, the algorithm involves passing messages back and forth between nodes, and therefore it will be beneficial if we can express the update rules for each message type in terms of the other. Without going into details, the update rules are:

where the sum and product run over all adjacent v-nodes except for node i, and we use

and

The second update rule is:

where the sum is over all adjacent c-nodes except for node j.

The third update rule is:

where the sum is over all adjacent c-nodes.

The Algorithm

After all the hard work, the algorithm reduces to six simple steps:

1. For all n bits initialize for all adjacent i, j:

2. Update:

3. Update:

4. Update:

5. For all n bits, decode by:

6. If

or exceeded maximal iterations limit, stop, else go to step 2.

Implementation

The following implementation is available as a GitHub repo. I also uploaded it to PyPI to play with if you wish. To install:

pip install belief-propagation-ldpc

Nodes

To begin describing the implementation, I will start by describing the Node class. It is defined as an “abstract base class” as we subclass from it the two types of nodes, CNode and VNode. It also lists two abstract methods, initialize to initialize node and message which returns the message it should pass. Here’s the Node code:

Each node has an automatically incremented unique id uid solely for bookkeeping purposes. The ordering_key is optional (but is a must for VNode as shown below) and used to order nodes. It also has a name (which is optional but is best for clarity when debugging or viewing a graph). neighbors is a dictionary of neighbors, and the received_messages dictionary holds messages received from each neighbor and is updated each iteration. The receive_messages method requests messages from each neighbor by invoking the message method and updates received_messages.

Deriving from the Node class, we have VNode and CNode shown below:

A CNode implements the initialize method with zero messages, and implements the message method according to the update rule discussed before for messages from c-nodes to v-nodes (step 2 of the algorithm).

A VNode implements the initialize method which initializes received_messages, but also receives some channel_symbol (a value of 0 or 1 assuming hard demodulation) and computes its llr according to the channel_model provided to the constructor (step 1 of the algorithm). Only a binary symmetric channel (BSC) was implemented in the provided code. If other channels are needed, it can easily be achieved by cloning the repo and adding channels to the channel_models.py file. The constructor also requires an ordering_key so that the algorithm can later supply each node the correct channel symbol per the ordering of the parity check matrix. The message method implements the update rule discussed before for messages from v-nodes to c-nodes (step 3 of the algorithm). The estimate method computes the log-likelihood ratio (step 4 of the algorithm) required to obtain ĉ.

Graph

A TannerGraph doesn’t do much. All it does is create the graph. To avoid the fuss of constructing edges one by one, it can also receive a bi-adjacency (parity check) matrix and build from it the graph. Here is the code:

The TannerGraph holds dictionaries for VNodes and CNodes (keys are uid’s), and a set of edges. It also implements methods for adding nodes, edges, and a classmethod named from_adjacency_matrix for constructing a graph from a matrix. The ordered_v_nodes method returns a list of nodes ordered by the ordering_key discussed before.

Algorithm Implementation

By now, almost all of the work is done. All that is left is writing a for loop. Here is the code:

The constructor requires specifying the graph object, the parity check matrix, and the maximal number of iterations. Then, to decode, call the decode method with a received channel_word to run the algorithm. Iterations end after the maximal amount of iterations or upon successful decoding. The method returns the estimated codeword, the final likelihoods, and a boolean flag indicating the returned estimate is a valid codeword.

Running an Example

The repo includes the source code for this example. First, either clone the repo or install the package from PyPI. Then, create a parity check matrix (the same one used in the example on the top of the page):

from belief_propagation import BeliefPropagation, TannerGraph, bsc_llrimport numpy as np

# consider a parity check matrix
H = np.array([[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]])

Create also a channel model (we assume a BSC channel with 10% for bit flips):

model = bsc_llr(0.1)

With the model and parity in hand, construct a graph:

tg = TannerGraph.from_biadjacency_matrix(H, channel_model=model)

Let us assume an invalid word received from the channel. Note that the channel flipped the last bit.

# let us assume the codeword [1,1,0,0,1,0,0,0,0,0] was sent, but due to a channel error the last bit got flipped
c = np.array([1, 1, 0, 0, 1, 0, 0, 0, 0, 1])

Running the algorithm by:

bp = BeliefPropagation(tg, H, max_iter=10)
estimate, llr, decode_success = bp.decode(c)

You will see that the estimate is the original word transmitted, i.e., only the last bit gets flipped.