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?
Can reed-solomon code applied in CCSDS be decoded through Berlekamp-Massey algorithm?
Started by ●September 21, 2006
Reply by ●September 21, 20062006-09-21
"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
Reply by ●September 22, 20062006-09-22
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 > > >
Reply by ●September 22, 20062006-09-22
"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?
Reply by ●September 24, 20062006-09-24
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? > > >
Reply by ●September 27, 20062006-09-27
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 SarwateThis 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
Reply by ●October 7, 20062006-10-07
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 >