Decoding

Dear  all

Can any one help me to understand  LDPC code

1) If LDPC code decode using viterbi algorithm and sum product
algorithm , which one will be  performance better ?

2) What are the different decoding algorithms for LDPC ?

3) What is the advantage of itterative decoding  over non itterative ?

4) Why the sum product algorithm is the best decoding algorithm  for
LDPC ?

thanks

Why don't you try this link:
http://wol.ra.phy.cam.ac.uk/mackay/codes/

shereen.ahmed wrote:
> Dear  all
>
> Can any one help me to understand  LDPC code
>

Google. And  the above link is a good one.

> 1) If LDPC code decode using viterbi algorithm and sum product
> algorithm , which one will be  performance better ?

You can hardly discern any difference in performance. But keep in mind
that you canNOT do Viterbi for large LDPC codes. We don't have enough
computational power to do that.

Sum-Product algorithm is iterative. And as we have learnt over the past
decade, iterative algorithms perform much much better without
increasing the decoding complexity.

> 2) What are the different decoding algorithms for LDPC ?

There is only one. And that comes from the idea of belief propogation.
And that algorithm is inherently iterative.

Ofcourse, you can do ML decoding. But you hardly gain anything by doing
that instead of the sum product algorithm. You can try that for a small
LDPC matrix.

> 3) What is the advantage of itterative decoding  over non itterative ?

Oh well. Before I start, it is *iterative* with a single 't'.

Let us say that you transmit a symbol over a continous channel, where
the noise is continous. What you receive is a symbol that is also
continous. Now, algorithms of the past have been doing some hard
decision over this received symbol and then passing the resulting
symbol to the decoder.

A couple of decades before, people realized that they are loosing a lot
of information by doing this hard decision before decoding. Now, if
only they can use the entire information to decode whatever they
receive...

Having said that, let us look at the two algorithms that you are so
interested in. Viterbi and Sum-Product. Viterbi algorithm also uses the
"soft" information for decoding. And so does Sum-Product algorithm. But
the Sum-Product algorithm also produces a "soft" output which it feeds
back as the "a-priori" information and uses this extra information to
decode the received vector again. This process is repeated a many
times, each time "refining" the soft information.

Keep in mind that this sort of iteration is possible for the
Sum-Product algorithm only because it works on the graph structure of
the LDPC code. While Viterbi works on the trellis structure.
Theoritically Viterbi should be able to produce optimum decoding since
it is ML. But then, Viterbi is just not possible for a large LDPC code.

But does this answer your question of why iterative algorithm performs
better? Well, the answer for that is that the mutual information
between the received vector and the decoded code word keeps increasing
with each iteration. You can actually visualize it by plotting it on an
EXtrinsic Information Transfer (EXIT) chart.

> 4) Why the sum product algorithm is the best decoding algorithm  for
> LDPC ?

Because it is iterative.

> thanks

Again, the MacKay's link is a good one. Do take some time to go through
it Shereen.

On 9 Apr 2006 23:28:56 -0700, "PraZ" <prasanna.sethuraman@patni.com>
wrote:

>
>Why don't you try this link:
>http://wol.ra.phy.cam.ac.uk/mackay/codes/
>
>shereen.ahmed wrote:
>> Dear  all
>>
>> Can any one help me to understand  LDPC code
>>
>
>Google. And  the above link is a good one.
>
>> 1) If LDPC code decode using viterbi algorithm and sum product
>> algorithm , which one will be  performance better ?
>
>You can hardly discern any difference in performance. But keep in mind
>that you canNOT do Viterbi for large LDPC codes. We don't have enough
>computational power to do that.
>
>Sum-Product algorithm is iterative. And as we have learnt over the past
>decade, iterative algorithms perform much much better without
>increasing the decoding complexity.
>
>> 2) What are the different decoding algorithms for LDPC ?
>
>There is only one. And that comes from the idea of belief propogation.
>And that algorithm is inherently iterative.
>
>Ofcourse, you can do ML decoding. But you hardly gain anything by doing
>that instead of the sum product algorithm. You can try that for a small
>LDPC matrix.

There are a number of decoding algorithms, but how distinct they are
is often a matter of opinion.   e.g., there are many different ways to
do the kernal computations, min-sum being the easiest example.
Scheduling can vary from full serial to full parallel and anything in
between.   "Layered" decoding with suitably structured codes is also
getting popular.


>> 3) What is the advantage of itterative decoding  over non itterative ?
>
>Oh well. Before I start, it is *iterative* with a single 't'.
>
>Let us say that you transmit a symbol over a continous channel, where
>the noise is continous. What you receive is a symbol that is also
>continous. Now, algorithms of the past have been doing some hard
>decision over this received symbol and then passing the resulting
>symbol to the decoder.
>
>A couple of decades before, people realized that they are loosing a lot
>of information by doing this hard decision before decoding. Now, if
>only they can use the entire information to decode whatever they
>receive...
>
>Having said that, let us look at the two algorithms that you are so
>interested in. Viterbi and Sum-Product. Viterbi algorithm also uses the
>"soft" information for decoding. And so does Sum-Product algorithm. But
>the Sum-Product algorithm also produces a "soft" output which it feeds
>back as the "a-priori" information and uses this extra information to
>decode the received vector again. This process is repeated a many
>times, each time "refining" the soft information.
>
>Keep in mind that this sort of iteration is possible for the
>Sum-Product algorithm only because it works on the graph structure of
>the LDPC code. While Viterbi works on the trellis structure.
>Theoritically Viterbi should be able to produce optimum decoding since
>it is ML. But then, Viterbi is just not possible for a large LDPC code.
>
>But does this answer your question of why iterative algorithm performs
>better? Well, the answer for that is that the mutual information
>between the received vector and the decoded code word keeps increasing
>with each iteration. You can actually visualize it by plotting it on an
>EXtrinsic Information Transfer (EXIT) chart.
>
>> 4) Why the sum product algorithm is the best decoding algorithm  for
>> LDPC ?
>
>Because it is iterative.
>
>> thanks
>
>Again, the MacKay's link is a good one. Do take some time to go through
>it Shereen.
Eric Jacobsen
Minister of Algorithms, Intel Corp.
My opinions may not be Intel's opinions.
http://www.ericjacobsen.org