Notation:

**r** should satisfy the conditions given by **r.H ^{T }=
0**

i.e.,

Hence, each column of **H ^{T }**(each row of H )defines
a Check. There are a total of M checks.

Bits of

Since each check verifies

The decoding is done by the method of Probability Propogation or the Sum-Product Algorithm.[3] gives an excellent tutorial

on this topic.

More Notation: (This notation is the same as the notation used by the authors in [2],[3] )

N (m)º{l
: **H _{mn}**=1} --- This is the set of bits
participating in check m i.e., the columns which have 1's in row m of

belong to this set. For each m, there are

M(n)º{m:
**H _{mn}**=1}
--- This is the set of checks bit n of

belong to this set. For each n, there are

N (m)\n
--- The set of (*t _{r}*-1)
elements participating in check m apart from bit n

q^{x}_{mn}
---The probability that bit l of ** r **has a value x given
the information obtained via the M-1 checks apart from check m

r^{x}_{mn }
---Probability of check m being satisfied by bit n of **r**, if r_{n}
is considered fixed at the value xÎ
{0,1} and the

other N-1 bits have a seperable distribution given by {q^{x}_{mn'}
: n'ÎL(m)\n}

__DECODING ALGORITHM__

__Step 1.__ Initialization

Initialize q^{0}_{mn }and
q^{1}_{mn }to the likelyhoods of x_{n}, f_{n}^{0
}and
f_{n}^{1 }.

For the AWGN channel,

f_{n}^{1} = 1/(1+exp(-2ay_{n}/s^{2})

and
f_{n}^{0
}=1- f_{n}^{1 }where,

the input to the Gaussian channel
is ±a, s^{2 }=N_{0}/2
is the variance of the additive noise and y_{n} is the soft output
of the

Gaussian Channel.

__Step 2.__ Horizontal Step

For each row/check m and every nÎN(m),
the 2 probabilities r^{0}_{mn
}and r^{1}_{mn
}are
computed.

For example , say we are looking
at a check m where the 2nd , 3rd and 5th columns are 1(here *t _{r}*=3).

i.e., the check is r

Suppose we wanted to calculate r

r^{0}_{m2 }= Prob{ r_{2}År_{3}År_{5}=0|
r_{2}=0,r_{3}=0,r_{5}=0}
x q^{0}_{m3 }x q^{0}_{m5}
_{
}+ Prob{ r_{2}År_{3}År_{5}=0|
r_{2}=0,r_{3}=0,r_{5}=1}
x q^{0}_{m3 }x q^{1}_{m5}
_{
}+ Prob{ r_{2}År_{3}År_{5}=0|
r_{2}=0,r_{3}=1,r_{5}=0}
x q^{1}_{m3 }x q^{0}_{m5}

+ Prob{ r_{2}År_{3}År_{5}=0|
r_{2}=0,r_{3}=1,r_{5}=1}
x q^{1}_{m3 }x q^{1}_{m5}

_{
}|||^{ly}_{ } r^{0}_{m2
}can
be calculated.

Therefore, generalizing the above equations we have,

The conditional probabilities in the above equations are 0 or 1 depending
on whether check m is satisfied by the

corresponding values of x_{n} and x_{n'}.

Using the above equations to calculate the r^{0}_{mn
}and
r^{1}_{mn }will require the enumeration of
all possible combinations

of x_{n' }which may be computationally intensive. The
authors in [2] suggest a couple of different methods to compute

the above probabilities and one of the effecient schemes they suggest
is as follows:

compute d_{qmn}=
q^{0}_{mn}-q^{1}_{mn}

then compute
d_{rmn}=
r^{0}_{mn}-r^{1}_{mn}=
**P**d_{qmn'}
: n'ÎL(m)\n

and then we get
r^{0}_{mn}=(1+d_{rmn})/2
and r^{1}_{mn}=(1-d_{rmn})/2

__Step 3.__ Vertical Step

In this step we update the values
of q^{0}_{mn}and q^{1}_{mn}using the r's
obtained in step 3.

q^{0}_{mn}=
a_{mn
}f_{n}^{0
}**P**r^{0}_{m'n
}:m'ÎM(n)\m

q^{1}_{mn}=
a_{mn
}f_{n}^{1
}**P**r^{1}_{m'n
}:m'ÎM(n)\m

where a_{mn
}is
chosen such that q^{0}_{mn} +q^{1}_{mn}=1

The pseudoposterior probabilities
are then obtained.

q^{0}_{n}=
a_{n
}f_{n}^{0
}**P**r^{0}_{mn
}:mÎM(n)

q^{1}_{n}=
a_{n
}f_{n}^{1
}**P**r^{1}_{mn
}:mÎM(n)

__Step 4.__ Tentative Decoding

set r_{n} =1 if q^{1}_{n
}>0.5

and r_{n}=0 otherwise.

If **r.H ^{T }=
**0
stop

Else go to step 2.

In the software implementation the algorithm iterates 1000 times.

The function **decode_ldpc(rx_waveform,No,amp,h)** does the decoding.

The function takes 4 parameters

(i) rx_waveform : The soft output of the gaussian channel

(ii) No: Twice the magnitude of PSD of the AWGN (No/2)

(iii)amp: the amplitude of the bpsk waveform (amp representing the voltage
for 1and -amp

representing the voltage for 0)

(iv)h: the parity check matrix to be used for decoding.

The function returns the decoded codeword and not the message bits.

The function can be used along with the modulation and channel transmission
functions as shown below:

Function Usage Example:

% assume the codeword c, the parity check
matrix H and No are already loaded into the MATLAB memory

tx_waveform=bpsk(c,1); %amp= 1

rx_waveform=awgn(tx_waveform,No);

vhat=decode_ldpc(rx_waveform,No,1,h) %since
amp=1;

Once the decoding is done ( the termination condition is satisfied or
the maximum number of iterations are performed), the message bits need
to be extracted. At the last step of encoding the message blocks,
the reordering done to get a non-

singular A was undone. If this reordering was done again, the message
bits would be located at the end of the decoded codeword and can be extracted
easily. The rearranged_cols array (output by the rearrange_cols( ) function)
that holds the

reordering information is used to do the reordering. The extract_mesg(vhat,rearranged_cols)
works in this manner.

Function Usage Example:

% assume we have the rearranged_cols array
output by the rearrange_cols( ) function already loaded into MATLAB memory

uhat = extract_mesg(vhat,rearranged_cols);

LDPC Software Index