% This program constructs coumn-weight three girth six quasi-cyclic LDPC codes given
% k( row weight, j(column-weight) is fixed at 3) 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: malemag@mopipi.ub.bw

% divides rows into j groups. shift and connect rows
% k times.
j=3; % column  weight is fixed
k=6;% row-weight is variable
m=7;%(k*k+k)/2; %67
M=j*m; % total number of rows
shift=zeros(k,j);
rows = struct('connect',0,'counter',0,'con',0);
emptyset = [];
for y = 1:M
    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];
group2 = [m+1:2*m];
group3 = [2*m+1:3*m];
% create list of neighbors at a distance of 6 or less.
%g= 1; % determines the girth of the code.
found_code = 1; % true is algorithm does not fail.

for kk = 1:k
    
     r1=ceil(rand*length(group1));
     i = group1(r1);
     
     mem=rows(i).con;
   
    A = intersect(mem,group2);
    A = setxor(A,group2);
    if (isempty(A)~=1)
        r1 = ceil(rand*length(A));
        row1 = A(r1);
    else
        disp('Row one not found');
        found_code = 0;
        break;
    end
    
    % create list of neighbors at a distance of 6 or less for row1.
    mem3 = rows(row1).con;
    
    
    % 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));
                x1 = check3(r2);
                                             
            else
                disp('Row two 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 == x1);
    
    p1 =circshift(group1,[1 -u+1]);
    p2 =circshift(group2,[1 -y+1]);
    p3 =circshift(group3,[1 -x+1]);
    
     shift(kk,1)=u;
     shift(kk,2)=y;
     shift(kk,3)=x;
    
     a = kk;
     for b=1:m
        
        g1=p1(b);g2=p2(b);g3=p3(b);
        rows(g1).connect(a,1)=g2;
        rows(g1).connect(a,2)=g3;
                
        rows(g2).connect(a,1) = g1;
        rows(g2).connect(a,2) = g3;
           
        rows(g3).connect(a,1) = g1;
        rows(g3).connect(a,2) = g2;
        
        set1 = [g1 g2];
        set2 = [g1 g3];
        set3 = [g2 g3];
        
        rows(g1).con = union(rows(g1).con, set3);
        rows(g2).con = union(rows(g2).con, set2);
        rows(g3).con = union(rows(g3).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             
 
 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);
         H(z,counter)=1;
         H(x1,counter)=1;
         H(x2,counter)=1;
         counter = counter + 1;
     end
 end
 else
     disp('Algorithm failed to get the code. Try again or increase row-group size m.');
 end