%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function girth = CalcGirth(checkMatrix_H,start_node)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% @author   Andreas Waadt, 13. November 2005
% @param     checkMatrix_H : the parity check matrix of the code
%           start_node : start search for cycles from this vertex
% @return   girth : the shortest cycle through checkMatrix_H
%               from the vertex with number 'start_node'
% This function calculates the length of the shortest cyclic way 
% through the tanner graph of checkMatrix_H;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% disp('----------------------------------------------------------------');
% disp('   Calculate the girth of');
% checkMatrix_H = checkMatrix_H
% disp('----------------------------------------------------------------');


sizeOfMatrix = size(checkMatrix_H);
% number of rows (check sums, check nodes)
j_rows = sizeOfMatrix(1);
% number of columns (bits per codeword, variable nodes)
n_columns = sizeOfMatrix(2);

% define a starting point (variable node),
% to start the search for a cycle from
start_node = 1;

% distance from variable node to the starting point
d_bit = -1 .* ones(1,n_columns);
% source (last check node) of this variable node
s_bit = -1 .* ones(1,n_columns);

% init start point
d_bit(start_node) = 0;

% loop
for loop_cnt = 1 : 1 : n_columns
    
    % distance from check node to the starting point
    d_check = -1 .* ones(1,j_rows);
    % source (last variable node) of this check node
    s_check = -1 .* ones(1,j_rows);
    
    % go from variable nodes to check nodes
    for bit_cnt = 1:1:n_columns
        if( d_bit(bit_cnt) >= 0 )
            for check_cnt = 1:1:j_rows
                if( (checkMatrix_H(check_cnt,bit_cnt) > 0) && (s_bit(bit_cnt) ~= check_cnt) )
                    d_check(check_cnt) = d_bit(bit_cnt)+1;
                    s_check(check_cnt) = bit_cnt;
                end;
            end;
        end;
    end;
    
    % distance from variable node to the starting point
    d_bit = -1 .* ones(1,n_columns);
    % source (last check node) of this variable node
    s_bit = -1 .* ones(1,n_columns);
    
    % go from check nodes to variable nodes
    for check_cnt = 1:1:j_rows
        if( d_check(check_cnt) >= 0 )
            for bit_cnt = 1:1:n_columns
                if( (checkMatrix_H(check_cnt,bit_cnt) > 0) && (s_check(check_cnt) ~= bit_cnt) )
                    d_bit(bit_cnt) = d_check(check_cnt)+1;
                    s_bit(bit_cnt) = check_cnt;
                    
                    if( bit_cnt == start_node )
                        % cycle found. Hurra, geschafft!!!
                        girth = d_bit(start_node);
                        return;
                    end;
                end;
            end;
        end;
    end;
    
end;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%