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 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.
