soft-decision decoding - koetter-vardy algorithm

[eltonjohn]

koetter-vardy algorithm

Any body has any experience with soft decoding ?
I'm trying to implement a "Reliability Matrix" for later use with a Koetter Vardy algorithm to be used as a front end of a Guruswami-Sudan Reed Solomon Decoder .

 

[Moshu95]

soft decision reliability matrix

Hi,
I've done it last year when i worked on the KV algorithm so I can help you if you still need...

 

[eltonjohn]

Re: soft-decision decoding

Hi i have gone through a lot of the papers .I'm doing algebraic soft decoding .I'm trying to implement VLSI techniques in DSP .I have a project and i been imposed analog devices DSP which are very slow 50 mips only .So any way that i can reduce the algorithm overhead is welcome .I'm in the process of using reencoding and also multiplicity assigment using BGMD . I wrote a reliability matrix program .using a gaussian PDF .but i think that a LLR (log likelihood ratio) function will work much easier .Have you done any of that . I'm planning to probably use Nielsen interoplation algorithm .
Any suggestions is welcomed..
regards

 

[Moshu95]

Re: soft-decision decoding

Hi,
with such DSP, the Koetter-Vardy algorithm is a real challenge!
When I work on it I implement the reliability Matrix with gaussian PDF as it is done by the authors. After, I used Koetter Algorithm for Interpolation and Roth Ruckenstein algorithm for factorisation.
Just for being sure, are you obliged to used the KV algorithm?
There is another soft decision decoding for RS codes which is better in terms of performances. It the algorithm proposed by Jiang and Narayanan.
They have proposed to use a Belief Propagation with and adaptation of the parity matrix of RS codes. It is much better than the KV algorithm. The complexity is still important, but I think it is more easier to reduce it than using the KV.
BR.

 

[eltonjohn]

Re: soft-decision decoding

HI again

Thanks for the reply ..I have finished the reencoding part by using a erasures only decoder and the scaling .I found that there is way to accelarate Galois arithmetic by using Zach logarithms . I wrote the Koetter interpolator . But i think that i will try to implement the Nielsen interpolator . The paper that you suggested i think i have it .But i need to implement techniques that have been out at least a couple of years .There are a lot of suggested new approaches but i don't know how feasable these are. Some papers are too short in explanations.

I will like to know if there is a way to calculate the relaibility of the received symbols with LLRs (log likelihood ratios) .Reliability for received bits is proportional to the value of the received bit. But how to calculate the reliability of a symbol from these ??

 

[Moshu95]

Re: soft-decision decoding

Assume that the modulation is a BPSK and the transmission over an AWGN,
yhe LLR on GF(2^q) are then defined by :

\sum_{i=1}^{q}

 2*y_i/sigma^

2.
You can find this formula reading a paper on non binary LDPC codes, whose decoder needs LLR over GF(2^q).

Hope this will help.

Added after 6 minutes:

Sorry for precedent message, the presentation was not expected to be that one...

So I rewrite the formula I was talking about:

\[LLR(Y) = \sum_{i=1}^{q}\frac{2*y_i}{\sigma^2}\]