Forums

Decoding

Started by shereen.ahmed April 8, 2006
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