Problem: Erasure correction with Universal reed solomon decoder

[Marcus]

hello,
i want to implement an algorithm for an universal reed solomon decoder as
described in "A Universal Reed-Solomon Decoder" by R.E. Blahut, IBM J. Res.
Develop. Vol.28 No.2 March 1984. (free download)[1]
This is a time domain implementation of the berlekamp algorithm and the
forney algorithm.
the berlekamp algorithm computes the error locator polynomial, its formal
derivative and the error evaluator polynomial in the time domain.
after that, the errors are corrected using the forney algorithm.

the used RS-code is described IEEE Std. 802.16 section 8.4.3.2.1. its
generator polynomial is: (x+a^0)*(x+a^1)...(x+a^15) in GF(256).

i had to make some modification for this code to the described[1] decoder:
computation of the dicrepancy: the exponent of omega is (r-1)*i not r*i
forney algorithm: a factor of omega^(2*i) has to be multiplied to gamma(i)
for the correction
the remainder of the algorithm is as described by r. e. blahut at page
155(figure 3).


Everything works fine with my decoder as long as i only correct errors. the
decoder corrects up to 8 errors as it should be.
but when i want to correct erasures the decoder fails.

lets say the last four symbols are set to zero in the recieved codeword, the
others are correct.
if i set rho to zero (no erasures, errors only) everything is fine.
if i set rho(the number of erasures) to 4 the decoder fails( erasure
location ir=(0,1,2,3) for r=1 to 4).
i think the error locator polynomial and its derivative are ok because they
are the same as if i set rho to zero.
so i think there is something wrong with the initialisation/computation of
the error evaluator polynomial if i have erasures.
i hope somebode can tell me where i have made a mistake


thanks,
marcus

 

[Ian Stirling]

hello,
i want to implement an algorithm for an universal reed solomon decoder as
described in "A Universal Reed-Solomon Decoder" by R.E. Blahut, IBM J. Res.
Develop. Vol.28 No.2 March 1984. (free download)[1]
This is a time domain implementation of the berlekamp algorithm and the
forney algorithm.
the berlekamp algorithm computes the error locator polynomial, its formal
derivative and the error evaluator polynomial in the time domain.
after that, the errors are corrected using the forney algorithm.

Everything works fine with my decoder as long as i only correct errors. the
decoder corrects up to 8 errors as it should be.
but when i want to correct erasures the decoder fails.

By erasure, do you mean that you take a bit out of a longer sequence,
shortening it?
I'm almost certain that RS will not correct tat.

 

[Marcus]

hello,
i want to implement an algorithm for an universal reed solomon decoder as
described in "A Universal Reed-Solomon Decoder" by R.E. Blahut, IBM J.
Res.
Develop. Vol.28 No.2 March 1984. (free download)[1]
This is a time domain implementation of the berlekamp algorithm and the
forney algorithm.
the berlekamp algorithm computes the error locator polynomial, its formal
derivative and the error evaluator polynomial in the time domain.
after that, the errors are corrected using the forney algorithm.

Everything works fine with my decoder as long as i only correct errors.
the
decoder corrects up to 8 errors as it should be.
but when i want to correct erasures the decoder fails.

By erasure, do you mean that you take a bit out of a longer sequence,
shortening it?
I'm almost certain that RS will not correct tat.

difference between errors and erasures:
error: somewhere in the recieved codeword a symbol at an unknown position
was changed to an unknown value during transmission
erasure: at a known position an error occured or you even recieved nothing
at all.

RS can correct (2t-e)/2 errors and/or erasures where 2t is the number of
parity symbols and e is the number of erasures.
so you can for example correct 12 erasures and 2 errors or up to 8 errors if
there are no erasures or 16 erasures if there are no errors if you have
a(n=255,k=239,2t=8)RS-code