Make your own free website on Tripod.com
ENCODING MESSAGE BLOCKS

Given a codeword uand an M by N IG parity check matrix H, we have
                                        u.HT=0                                                                                  (1)
Let us assume that the message bits, s , are located at the end of the codeword and the check bits, c, occupy the beginning of the codeword i.e.,
                                        u=[c|s]                                                                                   (2)
Also let,
                                       H=[A|B]                                                                                 (3)
where A is an M by M matrix and B is an M by N-M matrix
If the message bits s are located at the end of the codeword ,
Þthe first part of H is an identity matrix, i.e., A is an identity matrix
Using (2) and (3) in (1) we have
                                    Ac + Bs = 0                                                                            (4)
Þ                                 c=A-1 Bs                                                                                (5)
Eqn. (5) can be used to compute the check bits as long as A is non-singular and not only when A is an identity matrix (H in systematic form) .The function rref_GF2(parity-check)  helps reduce a binary matrix to the reduced row echelon form over GF2.The function takes the IG parity check matrix obtained by using the gen_ldpc( ) function and reduces it to the systematic form using Gauss-Jordan reduction.
 
Function Usage Example:
systematicH=rref_GF2(H) ;%reduces the parity check matrix  H to systematic form

The disadvantage of using the systematic parity check matrix is that the sparseness of the matrix maybe lost due to the row operations involved in the Gauss-Jordan reduction.Decoding is faster if the matrix is sparse. If we use the systematic form of H for encoding, we will have to use the systematic H for decoding and if the matrix is not sparse, decoding takes longer.

 
If the IG parity check matrix has to be used for encoding , the first M byM part of the matrix(A) has to be non singular.But it is not necessary that the IG parity check matrix obtained by the gen_ldpc(  ) function  always has a non-singular A.
The function rearrange cols(parity_check) rearranges the columns of the IG parity check matrix such that A is non singular. The function does only the column operations of the Gauss-Jordan reduction that can be used to reduce the IG parity check matrix to the systematic form. Since no row operations are done the sparseness of the matrix is not affected.
 
Function Usage Example:
[newh,rearranged_cols]=rearrange_cols(H) ;% makes the first M by M part of H non-singular without row operations
 
The function returns two matrices.  The first matrix, newH, is the IG parity check matrix,H, with its columns rearranged as in the Gauss-Jordan reduction. This column re-ordering ensures a non-singular A matrix. The second matrix,
rearranged_cols,  is a one dimensional matrix (array) with elements representing the rearrangement of columns that was performed.A 0 in the ithcolumn indicates that column i was not swapped with any other column during the Gauss-Jordan reduction. An entry j in the ith column indicates that columns i and j in H were swapped during the Gauss-Jordan elimination.
For Example, consider the following rearraged_cols array
column #-  1         2        3        4        5       6       7       8          9       10
               [0     0     0     0     6     7     0    17     0    16]


This array means that columns 5 and 6 of H were swapped,
                          then columns 6 and 7  of H were swapped,
                          then columns 8 and 17 of H were swapped and
                          then columns 10 and 16 of H were swapped to get a matrix with a non-singular A
 

Once we have the rearranged IG matrix, we can get the check bits by using Eqn. (5).
The function inv_GF2(A) can be used to find the inverse of binary matrix A over GF2.
 
Function Usage Example:
Ainverse=inv_GF2(A); %gets the inverse of A over GF2
The function mul_GF2(A,B) can be used to multiply two binary matrices A and B over GF2.
 
Function Usage Example:
product=mul_GF2(A,B) ;% A x B over GF2
 
Once the check bits c are obtained, the preliminary codeword can be obtained as u¢=[c|s].
If u¢is to be used as the codeword, then we have to use the rearranged IG parity check matrix for decoding.
We cannot use the IG parity check matrix, H, to decode  u¢ since u¢will not satisfy the checks defined by H.
We could use the rearranged version of H because the sparseness of the rearranged matrix is not changed, however the rearrangement of columns may introduce cycles in the factor graph defined by the rearranged parity check matrix. So in order to use the original IG parity check matrix H for decoding , we need to take u¢and rearrange the columns so that it represents the codeword formed using H i.e., we need to undo the rearrangement done by the rearrange_cols ( ) function to accomplish this. The rearranged_cols array output by the rearrange_cols( ) function can be used to do this. The function reorder_bits(u¢,rearrange_cols) can be used for this rearrangement. The function outputs the codeword u generated by the IG parity check matrix H.
Function Usage Example:
u=reorder_bits(u1,rearranged_cols) ; %outputs the codeword generated using the IG parity check matrix, H.
 
Here is the MATLAB code to do the encoding using the functions in the software :


clear all;
clc;
%%%%%%%%%%%%define dimension of the parity check matrix%%%%%%%%
rows=100;
cols=200;
H=gen_ldpc(rows,cols);%generates a 100 x 200 H matrix( the IG parity
                      %check matrix)
[newh,rearranged_cols]=rearrange_cols(h);
% newh holds the rearranged version of H and rearranged_cols holds
%the rearrangement order of columns

%%%%%%%%%%%%Get A and B matrices %%%%%%%%%%%%%%%%
for i=1:rows
    for j=1:rows
        A(i,j)=newh(i,j);
    end
end
for i=1:rows
    for j=rows+1:cols
        B(i,j-rows)=newh(i,j);
    end
end

%%%%%%%%%%%%%%message bits%%%%%%%%%%%%%%%%%%%%%

%generate message bits randomly
for i=1:cols-rows
    s(i)=round(rand);
end
s=s.;% make it a row vector
%%%%%%% or load s from file %%%%type "help load" at matlab prompt for details

%%%%%%%%%%%%%%get check bits( Eqn.5)%%%%%%%%%%%%%%%%

d=mul_GF2(gfinv(a),b);
c=mul_GF2(d,s);
%%%%%%%%%%%%%%%%%form u'%%%%%%%%%%%%%
u1=c;
for i=rows+1:cols
    u1(i)=s(i-rows);
end
%%%%%%%%%%%%%%% reorder u¢to get the CW u %%%%%%%%%%%%%%%%%%%
u=reorder_bits(u1,rearranged_cols);
%%%%%%%%%%%%%%% u is the codeword to be transmitted %%%%%%%%%%%%%%%%%%%



LDPC Software Index                                                                                              Modulation and Channel Simulations