Forums

Can reed-solomon code applied in CCSDS be decoded through Berlekamp-Massey algorithm?

Started by tonylzez September 21, 2006
In CCSDS,RS(255,223)code,the roots of the generator polynomial are not
consecutive,which follows as
                G(x)=(x-a^(11*112))*(x-a^(11*113))...*(x-a^(11*143)) 
I applied a kind of modified Berlekamp-Massy algorithm to resolve key
equation
                S(x)*delta(x)=omega(x)(mod x^d) (s(x)=s0+s1*x+...+sd*x^d,
   d is minimum code distance,delta(x) is error location polynomial and
omega(x) is error value polynomial)
But I get false results.
For example,
if error polynomial is E(x)=a*x(which means a error value "a" is added in
position 1),the resolved error polynomial is E(x)=a^202*x^11 ; 
if error polynomial is E(x)=a*x^2(which means a error value
"a" is added in position 2),the resolved error polynomial is 
E(x)=a^153*x^22; 
In fact,you can see that resolved error locations is equal to ((actual
location)*11 mod 255).
I think that maybe in CCSDS,the key equation need be modified,if it is not

the truth ,why the resolved results are not correct?
By the way,if the roots of generator polynomias are not consecutive,the
resolved results are correct.
Does whether the roots of the generator polynomial are consecutive makes
difference in reed-solomon decoding algorithm? 
Could somebody help me?



"tonylzez" <tonylzez@yahoo.com> wrote in message 
news:_KKdnaWjYZr9FY_YnZ2dnUVZ_rOdnZ2d@giganews.com...
> In CCSDS,RS(255,223)code,the roots of the generator polynomial are not > consecutive,which follows as > G(x)=(x-a^(11*112))*(x-a^(11*113))...*(x-a^(11*143))
The roots of the polynomial are consecutive powers of a^11, not of a.
> But I get false results. > For example, > if error polynomial is E(x)=a*x(which means a error value "a" is added in > position 1),the resolved error polynomial is E(x)=a^202*x^11 ; > if error polynomial is E(x)=a*x^2(which means a error value > "a" is added in position 2),the resolved error polynomial is > E(x)=a^153*x^22; > In fact,you can see that resolved error locations is equal to ((actual > location)*11 mod 255).
The error locations are defined in terms of powers of a^11. If the i-th symbol is in error, the error-locator has (a^11)^i as an inverse root. So, the locations found by your calculations are indeed correct except that you are interpreting them as powers of a, not as powers of a^11. If you interpret them as powers of a^11, you will get x and x^2 as the error locations in your examples above. With regard to the error value computation, you need to account for the fact that you are starting from the 112th power. Thus, the error-value computation (Forney's formula) needs to include a factor (see http://www.ifp.uiuc.edu/~sarwate/pubs/decoder.ps for details) which should fix up the error value as well.
> By the way,if the roots of generator polynomias are not consecutive,the > resolved results are correct.
??
> Does whether the roots of the generator polynomial are consecutive makes > difference in reed-solomon decoding algorithm?
Yes, we do need consecutive powers as roots for the decoding to work.... --Dilip Sarwate
yes,I have simulated the Forney algorithm based on next expression:
      Yi=(A^i)^111*omega(x=A^i)/(A*lambda'(x=A^i)),
where A=a^11,omega(x) is error value polynomial,lambda(x) is error locator
polynomial,and A^i is the root of the equation
       lambda(x)=0;
But I have another question:
   If the roots of generator polynomial are not consecutive,for example
,they are arbitrary  powers as a^3,a^7,...a^200,must we apply a new decode
method?I think the key equtation should be correct all the same,but the
error value polynomial and error locator polynomial may be interpreted as
some new meanings!Am I right?
>Yes, we do need consecutive powers as roots for the decoding to work.... > > >--Dilip Sarwate > > >
"tonylzez" <tonylzez@yahoo.com> wrote in message 
news:KJCdndOgY--vMo7YnZ2dnUVZ_qSdnZ2d@giganews.com...


> But I have another question: > If the roots of generator polynomial are not consecutive,for example > ,they are arbitrary powers as a^3,a^7,...a^200,must we apply a new decode > method?I think the key equtation should be correct all the same,but the > error value polynomial and error locator polynomial may be interpreted as > some new meanings!Am I right?
I think that consecutive powers are needed, but since you think the key equation is still correct, why don't you try a simulation and report on the results?
Ok,I will go on with my simulation and report the results before long.
>I think that consecutive powers are needed, but since you think the >key equation is still correct, why don't you try a simulation and report >on the results? > > >
tonylzez wrote:

> If the roots of generator polynomial are not consecutive,for example > ,they are arbitrary powers as a^3,a^7,...a^200,must we apply a new decode > method?I think the key equtation should be correct all the same,but the > error value polynomial and error locator polynomial may be interpreted as > some new meanings!Am I right? >> Yes, we do need consecutive powers as roots for the decoding to work.... >> >> >> --Dilip Sarwate
This is correct. If you don't use consecutive powers, the minimum distance of the resulting code is usually less, so you cannot necessarily decode the same number of errors. Certainly you can modify the key equation to match your zeros, but the LFSR thinking underlying Berlekamp-Massey goes out of the window. May be something can be done? Feel free to experiment. Cheers, Jyrki Lahtonen
In Reed-Solomon code,the inconsecutive roots of generator polynomial are
not allowed based on cyclic code theory.The generator polynomial follows
as
  g(x)=(x-A^(m0)*(x-A^(m0+1))*...*(x-A^(m0+d-1))
where d is the minimum code distance,which is equal to 33 in ccsds
standard,and
  A=a^i 
where a is primitive element of GF(255),i is a arbitrary ingeger.
so if the roots are inconsecutive,the encode method is not Reed-Solomon
code at all.
In fact,I think the minimum code distance will decrease if the roots are
inconsecutive,so the errors that can be corrected will also decrease.

>This is correct. If you don't use consecutive powers, the minimum >distance of the resulting code is usually less, so you cannot >necessarily decode the same number of errors. Certainly you can modify >the key equation to match your zeros, but the LFSR thinking underlying >Berlekamp-Massey goes out of the window. May be something can be done? >Feel free to experiment. > >Cheers, > >Jyrki Lahtonen >