Reed Solomon error correction question

lindasel wrote:
>> of his paper titled Reed-Solomon Codes
>> (www.informit.com/content/images/art_sklar7_reed-solomon/elementLinks/
>> art_sklar7_reed-solomon.pdf)
>> shows a generator polynomial with the coefficient of X^0
>> not being 1.
> This link gave me an error message.  The site seems to have restricted
> access.

Try this: 
(www.informit.com/content/images/art_sklar7_reed-solomon/elementLinks/art_sklar7_reed-solomon.pdf)

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������
** Posted from http://www.teranews.com **

>>http://www.ifp.uiuc.edu/~sarwate/decoder.ps
I would be most appreciative of any information on a question I have on
this paper.  I am looking at Step 4 of the iBM algorithm, in which omega is
calculated.  Omega (subscript i) at Step (2t) of the Berlkamp-Massey
algorithm is computed for i = 0, 1, ... t-1.  But in equation 6, the lambda
polynomial multiplied by the syndrome polynomial ("convolution" of the two
polynomials) = omega mod (2t).  
I am not clear what exactly is the procedure for obtaining omega from the
lambda and syndrome polynomials.  Other books suggest that one should
convolve the two polynomials and remove any terms of powers >= 2t.  So
omega would have the order (2t-1).
Step 4 seems to indicate that 
omega[0] = s[0]lambda[0]
omega[1] = s[1]lambda[0] + s[0]lambda[1]
omega[2] = s[2]lambda[0] + s[1]lambda[1] + s[0]lambda[2] 
and you stop there.  
In this case omega would have the order t-1.
Thank you for any information.

Another question about Step 4 in the iBM algorithm in Prof. Sarwate's
paper:
By Step 6 of the Berlekamp-Massey algorithm, if a shift register is being
used for the syndrome, syndrome[5] (the higest order syndrome byte) would
be in the s[0] position of the shift register.  Does that mean that
omega[0] = s[0]lamda[0] = syndrome[5]lamda[0]
omega[1] = syndrome[4]lamda[0] ^ ... etc

(all "+" signs actually being XOR)

dvsarwate@yahoo.com <dvsarwate@gmail.com> wrote:

>On Oct 7, 1:59&#4294967295;pm, "lindasel" <lselt...@alumni.caltech.edu> wrote:

>> I am looking for reliable and accurate equations for finding the error
>> values when the generator polynomial roots start in a position greater than
>> 1. &#4294967295;
>> Thank you for any information, either formulas or books and articles or
>> code that clearly explain this.

>I won't vouch for the reliability or accuracy of the information
>but you might want to look at the paper High-Speed Architectures for
>Reed-Solomon Decoders, IEEE Transactions on VLSI Systems, vol. 9,
>no. 5, Oct 2001 which is available (in Postscript format) at
>http://www.ifp.uiuc.edu/~sarwate/decoder.ps

Another source is Berlekamp et. al.'s chapter in Wicker and
Bhargava, _Reed Solomon Codes and their Applications_.
The code generator is define in Section 2.1, equation (1)
as having its first root at alpha ^ L.  The error value
is defined by equation (15) in Section 2.2 and has a
factor of X ^ (L-1), where X is the error location.
Note that this factor is one for the common case of L = 1.

The same formulation is used in McCliece, "The Theory
of Information and Coding" (Cambridge University Press).
Both of these books are well worth having in your library.

Steve

lindasel <lseltzer@alumni.caltech.edu> wrote:

>I have the following question about the encoder.
>In Bernard Sklar's paper on what communications engineers should know
>about Reed-Solomon, he states that a generator polynomial must be minimal,
>and that the coefficients of X^(n-k) and X^0 mnust be 1.

Doesn't seem right to me, at least as just stated.  Trivial 
counterexample-- a generator polynomial with one root.   The only 
requirement for a cyclic RS code is that the roots of the code 
generator be consecutive powers of some field generator.

The leading coefficient must be one, if you want to construct
a systematic code in the usual way, but even if not you
still get an RS code.

Steve

dvsarwate@yahoo.com <dvsarwate@gmail.com> wrote:

>On Oct 7, 1:59&#4294967295;pm, "lindasel" <lselt...@alumni.caltech.edu> wrote:

>> I am looking for reliable and accurate equations for finding the error
>> values when the generator polynomial roots start in a position greater than
>> 1. &#4294967295;
>> Thank you for any information, either formulas or books and articles or
>> code that clearly explain this.

>I won't vouch for the reliability or accuracy of the information
>but you might want to look at the paper High-Speed Architectures for
>Reed-Solomon Decoders, IEEE Transactions on VLSI Systems, vol. 9,
>no. 5, Oct 2001 which is available (in Postscript format) at
>http://www.ifp.uiuc.edu/~sarwate/decoder.ps

Another source is Berlekamp et. al.'s chapter in Wicker and
Bhargava, _Reed Solomon Codes and their Applications_.
The code generator is define in Section 2.1, equation (1)
as having its first root at alpha ^ L.  The error value
is defined by equation (15) in Section 2.2 and has a
factor of X ^ (L-1), where X is the error location.
Note that this factor is one for the common case of L = 1.

The same formulation is used in McEliece, "The Theory
of Information and Coding" (Cambridge University Press).
Both of these books are well worth having in your library.

Steve