CCS

Decoding LDPC Codes - The Bit-Flipping Algorithm

The bit-flipping algorithm is a hard-decision decoding algorithm with low complexity.

A modified, and much simpler, version of the bit-flipping algorithm is obtained by
flipping only those bits in y for which the number of unsatisfied parity check equations
has the largest value and then repeating the syndrome computation.

This process is continued until either the syndrome is zero or a predetermined number of iterations is reached.

Matlab Coding

 1 function [c check] = bitflipping(H,y,max_it)
 2 %BITFLIPPING Bit-flipping algorithm for decoding LDPC codes
 3 %   [c check] = bitflipping(H,y,max_it)
 4 %    H: parity-check matrix of the code
 5 %    y: channel outputs, binary-valued
 6 %    max_it: maximum number of iterations
 7 %    c: decoder output
 8 %    check: is 0 if c is a codeword and is 1 if c is not a codeword
 9         
10 s = mod(y*H',2);              %Syndrome computation
11 it=1;                         %Iteration counter
12 while ((it<=max_it) && (nnz(s)~= 0)) 
13   f = s*H;
14   ind = find(f-max(f) == 0);
15   y(ind) = mod(y(ind)+1,2);
16   it = it+1;
17   s = mod(y*H',2);
18 end
19 c = y;
20 check = nnz(s);
21 if (check > 0)
22     check = 1;
23 end

>> y = [0 0 0 1 0 0 1]

y =

0 0 0 1 0 0 1

>> H = [1 0 0 1 0 0 1]

H =

1 0 0 1 0 0 1

>> [c, Pcheck] = bitflipping(H,y,6)

c =

0 0 0 1 0 0 1

Pcheck =

Reference,

　　1. <<Contemporary Communication System using MATLAB>> - John G. Proakis