Make your own free website on Tripod.com
GENERATING THE PARITY CHECK MATRIX

Low Density Parity Check codes can be specified by a Non-Systematic Sparse Parity-Check Matrix, H, having a uniform column weight, (³3)and a uniform row weight. H is constructed at random subject to these constraints. An (n,j,k) LDPC code is specified by a partiy check matrix,H having n-k rows, n columns and j 1's per column.  In this software k=3 i.e., all the parity check matrices will have 3 ones per column. The code formed form such a parity check matrix is known as a regular Gallagher code.
The function gen_ldpc(rows,cols) generates the parity check matrix H.
 
Function Usage Example:
 H=gen_ldpc(1000,2000) % generates the parity check matrix for a (2000,1000,3)LDPC code
 
The function follows the steps for creating a parity check matrix used by Radford Neal in his software.(ftp://ftp.cs.utoronto.ca/pub/radford/LDPC-2001-05-04/pchk.html).
The function takes 2parameters: the number of rows and the number of columns of the parity check matrix and outputs the variance in the number of ones per row along with the parity check matrix.
IMPLEMENTATION:
1.An all zero matrix H of dimension (rows x cols) is created.
2.For each column inH , three 1's are placed in rows chosen at random, subject only to the constraint
that the ones be placed in distinct rows.
3.The software then runs through the matrix searching for a row with zero 1's or just one 1. If a row has no
1ís in it then it is a redundant row. So the software chooses 2 columns in the same row at randomand places 1ís
 in those columns. If a row just has one 1 in a row it means that the codeword bit in thatcolumn is
alwayszero. So whenever the software finds a row with just one 1 in it, it randomly picksanother   column in the same row andplaces a 1 there.
4.The software then calculates the number of 1's per row.
  Number of 1's per row = (cols x bits_per_col )/rows.If this is not an integer, the software roundsthe value
to the next higher integer.
If the number of 1's per row, calculated in step 4 is not an integer, it is not possible to have a uniform number of ones in each row.
5.The software then runs through the matrix trying to make the number of 1's per row as uniform as possible. For
any row (row i, say) containing more number of ones than the value calculated in Step 4, the software picks a column containing a 1 at random and tries to move that 1 to a different row (randomly chosen such that has it a lesser number of ones than the value calculated in step 4) in the same column. The software makes  sure that the row so chosen does not have a 1 in that particular column. If the software is not able to find such a row, it just tries with a different column containing a 1 in  row i.
6.A good parity check matrix for LDPC codes generates a factor graph with no cycles in it. The software runs through the graph trying to eliminate cycles of length 4 i.e., situations where pairs of rows share1ís in a particular pair of columns as shown below. Shown below is the parity check matrix of a (20,10,3) LDPC code.
 No matter how uniform the preliminary parity check matrix created in steps 1 and 2 is, Step 6 can make the number of 1ís in the rows be uneven.
Such parity-check matrices generate Irregular Gallagher (IG) codes.This parity check matrix formed by using the gen_ldpc( ) function will be referred to as IG parity check matrix.



LDPC software index                                                                                                               Encoding Message Blocks