HARD DECISION DECODING ALGORITHM FOR LDPC(LOW DENSITY PARITY CHECK) CODES

Example:

ENCODING:

Let the parity check matrix be as shown below. It corresponds to a (n,k)=(6,2) LDPC code. where n is total number of bits in each code word and k is number data bits in each code word.

The generator matrix for the above parity check matrix is as shown below.

Since the order of G is (k x n)=(2 x 6) it corresponds to a code word of length 6 having 2 data bits. Thus there are 2^2 = 4 ,valid code words possible. Encoding of LDPC codes is similar to that of any linear block code but the difference lies in the formation of [H]. Let us consider the data bits [1 0], the corresponding code word is found out as shown below.

DECODING:

STEP 1

Multiply the transpose,[Y'] of received code word,[Y] with the parity check matrix,[H]  i.e [s]=[H][Y'] (mod 2 for each bit). If the result is 0,then the code word is correct so go to step 4.

STEP 2

Multiply [s] with each column of the [H] while adding result in each column to form a n (code word length) bit row vector,[e].

STEP 3

Flip the bits of [Y] having highest corresponding values in [e] and go to step 1. 

STEP 4

Display [Y] as the corrected code word.

NOTE: The above steps are carried out for a fixed number of iterations and if [H][Y']=[0] can't be satisfied then the received  code word cannot be decoded.

For the above mentioned example let the erroneously received code word be [Y]=[1 0 1 1 1 0] corresponding to the sent code word [c]=[1 0 0 1 1 0] i.e error at 3rd bit.

1st Iteration:

Step 1:

[s]=[H][Y']=[1 0 0 0]'

Step 2:

[e]=[0 1 1 0 0 0]

Step 3:

Since 2nd and 3rd bits in [e] have highest value (1 in this case) flip the corresponding bits in [Y].

Thus [Y]=[1 1 0 1 1 0]

2nd Iteration:

Step 1:

[s]=[H][Y']=[1 1 0 1]'

Step 2:

[e]=[1 3 1 1 0 1]

Step 3:

Since only 2nd bit in [e] has highest value (3 in this case) flip the 2nd bit in [Y].

Thus [Y]=[1 0 0 1 1 0]

3rd Iteration:

Step 1:

[s]=[H][Y']=[0 0 0 0]'

Step 4:

Thus [Y]=[1 0 0 1 1 0] is the corrected code word.

CONCLUSION:

In the above example I was lucky enough to get the result in 3 iterations(just for a single bit error) but usually Hard Decision Decoding is not used especially when there are burst errors, instead Soft Decision Decoding is used for such errors.