girth-eightqc-ldpc.m

The algorith divides rows in to four equal groups. The rows are then used to from a distance graph w

% This program constructs coumn-weight four girth 8 quasi-cyclic LDPC codes given
% k( row weight, j(column weight) is fixed at 4) and m (size of each sub-matrix). The
% program constructs a distance graph first then converts it into a matrix.
% For details of the algorithm see PhD thesis by G.Malema, LDPC codes: Construction and Implementation
%(University of Adelaide 2007) and other publications.
% Author : Dr. Gabofetswe Alafang Malema,University of Botswana  
% Department of Computer science. e-mail: [e-mail]

j=4; % column-weight should be fixed at 4.
k=8; % row-weight is variable.
m=130; % size of each sub-matrix.is variable.
M=j*m; % total number of rows.
shift=zeros(k,j); % stores shift values for each sub-matrix.
rows = struct('connect',0,'counter',0,'con',0); % structure used for storing connections.
emptyset = [];
for y = 1:M       % connections and number of connections for rows and columns are initialized.
    rows(y).counter = 0;
    rows(y).con = intersect(emptyset,rows(y).con);
    rows(y).connect = intersect(emptyset,rows(y).connect);
    %rows(y).mem = intersect(emptyset,rows(y).mem);
end
group1 = [1:m];  %row group one
group2 = [m+1:2*m];  % row group two,
group3 = [2*m+1:3*m]; % row group three, these groups are connected to group one.
group4 = [3*m+1:4*m];

g= 1; % determines the girth of the code, in these case 8.
found_code = 1; % true if algorithm does not fail.

% the for loop finds a rows(from groups 1,2,3) that are apart at atleast a distance
% of 8. They are then connected. The rest of the groups are connected
% according to this first connection. The process is repeated k times which
% is the number of connections for each row.
for kk = 1:k
    r1 = ceil(rand*length(group1)); % randomly choose a row from group1
    i = group1(r1);
    %while rows(i).counter < k
        mem=[]; mem1 = rows(i).con;
        mem2 = [];
        for y = 1:g
            %mem2 = [];
            for x = 1:length(mem1)
                x1 = mem1(x);
                mem2 = union(mem2,rows(x1).con);
            end
            mem = union(mem1,mem2);
            mem1=mem;
        end
        
    % find row not in mem in the given range.
    
    A = intersect(mem,group2);
    A = setxor(A,group2);
    if (isempty(A)~=1)
        r1 = ceil(rand*length(A));
        row1 = A(r1);
    else
        disp('Row two not found');
        found_code = 0;
        break;
    end
    
    % create list of neighbors at a distance of 6 or less for row1.
    mem3 = []; mem1=rows(row1).con;
    mem2 = [];
    for b = 1:g
        %mem2 = [];
        for x = 1:length(mem1)
            x1 = mem1(x);
            mem2 = union(mem2,rows(x1).con);
        end
        mem3 = union(mem1,mem2);
        mem1 = mem3;
    end
    mem3 = union(mem3,row1);
    
    % Find row 2 not in mem or mem3 at a distance of atleast 7.
    
            check1 = intersect(mem,group3);
            check1 = setxor(check1,group3);
            check2 = intersect(mem3,group3);
            check2 = setxor(check2,group3);
            check3 = intersect(check1,check2);
            
            if isempty(check3)~=1
                r2 = ceil(rand*length(check3));
                row2 = check3(r2);
               
              
            else
                disp('Row three not found');
                found_code = 0;
                break;
            end
    
           % create list of neighbors at a distance of 6 or less for row1.
    mem4 = []; mem1=rows(row2).con;
    mem2 = [];
    for b = 1:g
        %mem2 = [];
        for x = 1:length(mem1)
            x1 = mem1(x);
            mem2 = union(mem2,rows(x1).con);
        end
        mem4 = union(mem1,mem2);
        mem1 = mem4;
    end
    mem4 = union(mem4,row2);
    % Find last 4th row.
        
    check1 = intersect(mem,group4);
    check1 = setxor(check1,group4);
    check2 = intersect(mem3,group4);
    check2 = setxor(check2,group4);
    check3 = intersect(mem4,group4);
    check3 = setxor(check3,group4);
    check4 = intersect(check1,check2);
    check4 = intersect(check4,check3);
    
    if (isempty(check4)~=1)
        r3 = ceil(rand*length(check4));
        row3 = check4(r3);
    else        
        disp('Row four not found');
        found_code = 0;
        break;
    end  
    % connect all the rows by using a shift.
    u = find(group1 == i);
    y = find(group2 == row1);
    x = find(group3 == row2);
    z = find(group4 == row3);
    
    p1 =circshift(group1,[1 -u+1]);
    p2 =circshift(group2,[1 -y+1]);
    p3 =circshift(group3,[1 -x+1]);
    p4 =circshift(group4,[1 -z+1]);
    
   
     shift(kk,1)=u; % stores shift values of the sub-matrices.
     shift(kk,2)=y;
     shift(kk,3)=x;
     shift(kk,4)=z;
     
    a = kk;
    
    for b=1:m
        
        g1=p1(b);g2=p2(b);g3=p3(b);g4=p4(b);
        rows(g1).connect(a,1)=g2;
        rows(g1).connect(a,2)=g3;
        rows(g1).connect(a,3)=g4;
                
        rows(g2).connect(a,1) = g1;
        rows(g2).connect(a,2) = g3;
        rows(g2).connect(a,3) = g4;
        
        rows(g3).connect(a,1) = g1;
        rows(g3).connect(a,2) = g2;
        rows(g3).connect(a,3) = g4;
        
        rows(g4).connect(a,1) = g1;
        rows(g4).connect(a,2) = g2;
        rows(g4).connect(a,3) = g3;
        
        set1 = [g1 g2 g3];
        set2 = [g1 g2 g4];
        set3 = [g1 g3 g4];
        set4 = [g2 g3 g4];
        
        rows(g1).con = union(rows(g1).con, set4);
        rows(g2).con = union(rows(g2).con, set3);
        rows(g3).con = union(rows(g3).con, set2);
        rows(g4).con = union(rows(g4).con, set1);
    end
        
    %end % while loop. 
end % for kk =1:k
 count = zeros(1,M);
 for z = 1:M
     count(z)= rows(z).counter;
 end             
 
 %create a sparse matrix H from the row connections above.
 counter = 1; 
 H = zeros(M,5);

 if found_code == 1
 for i = 1:k
     for z = 1:m
         x1 = rows(z).connect(i,1);
         x2 = rows(z).connect(i,2);
         x3 = rows(z).connect(i,3);
         H(z,counter)=1;
         H(x1,counter)=1;
         H(x2,counter)=1;
         H(x3,counter)=1;
         counter = counter + 1;
     end
 end
 else
     disp('Algorithm failed to find code. Try again or increase group size m.');
 end