Introduction

This post reviews the check node operation of belief propagation on LDPC decoding. For the binary LDPC code, each check node represents a constraint such that the modulo-2 sum of the bits corresponed to the variable nodes conneceted to this check node equals to 0.

For a check node message with degree \(d_c\), the output message of each edge from this check nodes is calculated using the other \(d_c-1\) extrinsic messages. For example, one can caulate the probablity of 0 and 1 of variable node 0, i.e., \(P(X=0/1;0)\) using the probabilities of the other \(d_c - 1\) “extrinsic” variable nodes, i.e., \(P(X=0/1;i)\), where \(i=1,\ldots,d_c-1\). This is the so-called “sum-product” algorithm.

This post illustrates that how to derive the belief propagation on check nodes from sum-product algorithm.

Reference

1. T. J. Richardson and R. L. Urbanke, “The capacity of low-density parity-check codes under message-passing decoding,” in IEEE Transactions on Information Theory, vol. 47, no. 2, pp. 599-618, Feb 2001, doi: 10.1109/18.910577. link