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)
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)
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 i
thcolumn
indicates that column i was not swapped with any other column during the
Gauss-Jordan reduction. An entry ‘j’ in the i
th 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