[GF (q) + LDPC] regular LDPC coding and decoding design and MATLAB simulation based on the GF (q) field of binary graph

1. Software version

matlab2017b

2. System principle

        First assume the ring length l, If the rank of binary matrix is full rank , Then this ring is not included in the binary minimum distance , hypothesis g=lmin Is the ring length of the check matrix . So every binary matrix （ Its ring length is lmin and lmax） Between , Then the bit error rate can be reduced , Improve performance . The full rank condition given in this paper FRC The description of is as follows ：

        Give a block matrix Cd, Its ring length is d=l/2; Through row and column transformation , We can get the following formula ：

    

  Then its full rank condition is det(Cd) It's not equal to 0. This is equivalent to the following condition ：

         therefore , When we are doing ring elimination , We will adopt the method of circulation , Through continuous row and column transformation , Meet the above conditions , So as to get the ring elimination effect .

Then introduce stop set ：

         System performance , In addition to being related to rings , Also related to stop sets , In practice, , There is no specific way to eliminate the impact of stop sets , The usual way is ：

          hypothesis ds Is the weight of a given stop set , Then the corresponding regular graph （ matrix ） The weight of its smallest stop set is dsmin=3g/4., here g For the ring length . In practice, , In order to provide the performance of the system , You need to maximize the minimum distance of the stop set .

Then use the four steps given at the end of the paper to optimize the cycle .

         The general steps of the whole binary image algorithm are ：

        First step ： initialization , The initialization step is from the initial H Randomly selected rows in the check matrix , These rows mainly come from row sets R And their permutations . Pass step 1 , We will get several different permutations R The matrix constructed by row data H.

        The second step ： The main purpose of this step is to delete the ring length in g and LM Between the rings . Including set S Stop set in , So as to obtain better performance of the ring and stop set state . Set up the matrix H A set of row labels I, Then start iterative calculation , The maximum ring length of the direct matrix is greater than LM. That is, the small rings in the whole matrix are eliminated .

         The specific steps are: ：

        2.1： Initialize random selection I, here I yes H The subset or complete set of the set of all row labels in the matrix , Here we choose all row labels as the optimized target .

        2.2： from I Select a row label randomly in .

        2.3： From matrix R One at random n A random set  

        2.4： choice A combination , Make sure that some small rings and long rings are deleted as much as possible , For each cycle l, Search by l Small girth , Then delete .

        2.5： Set I Remove the label of the line of the ring deleted in this cycle , Then recycle , direct I Become an empty set .

         The third step ： Ring elimination and stop set processing ：

        This step , Mainly for some girth greater than LM The situation of , To delete , And right S The selection of the stop set in satisfies the maximization of the minimum distance .

       Step four ： If there is no ring that can be eliminated or there is no S The selection of the stop set in satisfies the condition that the maximization processing of the minimum distance changes , Then complete the optimization process of these four steps , Otherwise, continue to start the cycle of the above four steps .

About 2,4 Analysis with good performance

This can only be analyzed from a relative perspective , Because the line weight is 2 When , If there is one in the system 4 Ring , Then the two points of this rectangle are respectively the two non 0 Elements , The other two points are two non-zero elements in another column , When the column weight is 4 When , appear 4 The probability of a ring is less than 2,6,28,210 The probability of four rings ,

       Of course , Since we can construct H matrix , Generally, there are no four rings , This is the time , We need to consider the structure of six rings , Six rings exist in the following situations ：

In the same way , Appear on the column when the column weight is 4 When , The probability of six rings is far less than the column weight is greater than 4 The situation of . If there are no six rings , Then consider the situation of the eighth ring . One analogy .

         however 2,4 The performance will be better than 2,3 Poor performance .

        From the perspective of simulation , You can produce different line weights , Matrix of column weight , Make a simulation comparison . The above is analyzed from a theoretical point of view .

3. Core source code  

function H = func_good_Hgf32(H0,N);

H  = zeros(size(H0));
H  = func_randomly(H0,N);
H0 = H;
%%
%Initialization
%The rows values in H are chosen at random from the rows in R and their random permutations
% produce random permutations Composed of H matrix 
R     = H0;
% To arrange and combine randomly 
[M,N] = size(H0);
indcol= randperm(M);% Random arrangement of rows 
indrow= randperm(N);% Random arrangement of columns 
% Row arrangement 
for i = 1:M
    H(i,:) = R(indcol(i),:);
end
for i = 1:N
    H(:,i) = R(:,indrow(i));
end

% Produce different permutations R
NUM = N;% Set up a collection 
for j = 1:NUM
    indcol= randperm(M);% Random arrangement of rows 
    indrow= randperm(N);% Random arrangement of columns 
    % Row arrangement 
    for i = 1:M
        Hj(i,:) = R(indcol(i),:);
    end
    for i = 1:N
        Hj(:,i) = R(:,indrow(i));
    end
    RR{j} = Hj;
end


%%
%Initial cycle cancellation:
ROW_SET = [1:M];
I       = ROW_SET;
n       = floor(M/2);
g       = 1;
LM      = 6;
l       = g;
MM      = length(I);
while(MM > 0)% When it comes to 1 When , Then for 1, Stop the cycle 
    for l = g:1:LM
        %2.2: from I Select a row label randomly in .
        tmps   = randperm(M);
        Index  = tmps(1);
        %2.3： from R Choose... At random n A combination of ;
        for i = 1:n
            R_tmps{i} = RR{Index+i-1};
        end
        %2.4： Maximize girth value , Then delete this set 
        for i = 1:n
            R_tmps{i} = RR{Index+i-1};
            if rank(R_tmps{i}) == M
               R_tmps{i} = []; 
               RR{Index+i-1} = zeros(size(RR{Index+i-1}));
            end
        end
    end
    %2.5： The end of this cycle , Remove random Index
    MM = MM-1;    
end
% Remove the excluded combination method 
Index2 = 0;
for i = 1:NUM
    if sum(RR{i}) > 0;
       Index2 = Index2 + 1;
       RR2{Index2} = RR{i};
    end
end

%%
%Cycle cancellation and stopping set mitigation
% First, eliminate the ring 
Index3 = 0;
RR3    = RR2;
for i = 1:Index2
    % Detect whether there is greater than LM Ring length of , If there is , Delete , Otherwise, it will not be deleted 
    cycle4num = check4cycle(RR3{i});
    cycle6num = check6cycle(RR3{i});
    cycle8num = check8cycle(RR3{i});
    if cycle4num == 0 & cycle6num == 0 & cycle8num == 0  
       Index3 = Index3 + 1;  
       RR3{Index3} = RR2{Index3}; 
    elseif cycle4num == 0 & cycle6num == 0 & cycle8num > 0  
       RR3{Index3} = zeros(size(RR2{Index3}));
    end   
end
% Remove the excluded combination method 
Index4 = 0;
for i = 1:Index3
    if sum(RR3{i}) > 0;
       Index4 = Index4 + 1;
       RR4{Index4} = RR3{i};
    end
end
% In the rest of the set , Choose any one .
SEL = randperm(Index4);
H   = RR4{SEL(1)};

4. test result

5. reference

[1] Poulliat C ,  Fossorier M ,  Declercq D . Design of regular (2,dc)-LDPC codes over GF(q) using their binary images[J]. IEEE Transactions on Communications, 2008, 56(10):1626-1635.A14-14(error)