Forums

2t error correction-Reed solomon

Started by nezhate August 13, 2006
Hi all,
can any one tell why the Reed solomon codes can correct only 2t = n-k
errors ? how to prove it
Thanks

"nezhate" <mazouz.nezhate@gmail.com> asked in message 
news:1155463562.628660.246080@h48g2000cwc.googlegroups.com...

> can any one tell why the Reed solomon codes can correct only 2t = n-k > errors ?
No one can tell why because Reed-Solomon codes cannot correct 2t = n-k errors; they can only correct t = (n-k)/2 errors.
Hi
sorry for error typing ! I wanted to say t = (n-k)/2.
how to prove that it corrects only t errors ?

nezhate said the following on 23/08/2006 15:10:
> Hi > sorry for error typing ! I wanted to say t = (n-k)/2. > how to prove that it corrects only t errors ? >
This is the maximum that any class of code can correct, not just Reed-Solomon. If there are more than (n-k)/2 errors, the received codeword is closer (Hamming distance) to an incorrect codeword than the correct codeword. -- Oli
I m in the process to implement the RS decoder. I implemented syndrome
calculation, berlekamp massey algorithm, chien search and forney
algorithms.
However, in my code the number of error locations from the chien search is
always less than the degree of the berlekamp massey algorithm. They are
never equal. I found a method of testing the berlekamp massey algorithm.
It is available in IEEE transactions on consumer electronics. The title of
the paper is 'architecture of a high speed reed solomon decoder by tetsuo
lwaki. 
According to the method in this paper, the output of the berlekamp massey
algorithm is the same as the output from the paper. From this comparison I
assumed that the berlekamp massey is working fine. However, the degree of
the error locator polynomial is always greater than the number of error
locations obtained by chien search. Please guide me whether this is
normal. If not then what should I do. I am using chien search for
(204,188,8) rs decoder with generator polynomial
(x+lambda^0)(x+lambda^1).......(x+lambda^15) and primitive poynomial x^8 +
x^4 +x^3 +x^2 +1

Regards,
Zahid



z.khan@ed.ac.uk wrote:
> I m in the process to implement the RS decoder. I implemented syndrome > calculation, berlekamp massey algorithm, chien search and forney > algorithms. > However, in my code the number of error locations from the chien search is > always less than the degree of the berlekamp massey algorithm. They are > never equal. I found a method of testing the berlekamp massey algorithm. > It is available in IEEE transactions on consumer electronics. The title of > the paper is 'architecture of a high speed reed solomon decoder by tetsuo > lwaki. > According to the method in this paper, the output of the berlekamp massey > algorithm is the same as the output from the paper. From this comparison I > assumed that the berlekamp massey is working fine. However, the degree of > the error locator polynomial is always greater than the number of error > locations obtained by chien search. Please guide me whether this is > normal. If not then what should I do. I am using chien search for > (204,188,8) rs decoder with generator polynomial > (x+lambda^0)(x+lambda^1).......(x+lambda^15) and primitive poynomial x^8 + > x^4 +x^3 +x^2 +1 > > Regards, > Zahid
Hi Zahid , perhaps your chien search did not evaluate the error locator at each element in GF(2^8). If you are interested I can give you some files to compare them with your result. cheers