Check Nodes

This web page describes the logic inside the Check Node function.

First consider a LDPC decoder as illustrated below which inputs probability values.




A block diagram of the Check Node function is shown below...



Gallager very cleverly derived the formula for the probability that the number of 1's in a set of probabilites is even on page 41 of his 1963 paper on LDPC codes.

p(# 1's is even) = 1/2 + 1/2[(1-2p1)(1-2p2)(1-2p3)...]

p(# 1's is odd) = 1 - p(# 1's is even) = -1/2 + 1/2[(1-2p1)(1-2p2)(1-2p3)...]

In the above example,
 p1out = 1/2(1-2p2in)(1-2p3in) -1/2
p2out = 1/2(1-2p1in)(1-2p3in) -1/2
p3out = 1/2(1-2p1in)(1-2p2in) -1/2

The Check Node function could be implemented in a number of different ways...
  •  It might make sense for the Check Node function to simply average the values it receives.  [For the above example the value outputted by the Check Node would be pout = (p1in+p2in+p3in)/3.]
  •  If one input value deviates more than some fixed amount from the other values, that value could be ignored similar to what the bit-flipping decoder does and the average of the others used as output.
  •  One input value could be ignored and the output could be declared to be 1 or 0 if the other values are above or below predetermined thresholds.
Simulations may tell which method is the most effective.

Comments?  To post comments, e-mail me, and I will reply with instructions.

Comments