Reed Solomon error correction question

I am normally a speech/audio processing engineer, so this is somewhat out
of my primary expertise area.
I have recently implemented the Reed Solomon error correction algorithm
and have gotten it to work for the following case: the roots of the
generator polynomial are in positions 1 through 2t, where t is the number
of errors.  However, I implemented the case where the roots of the
generator polynomial start at n, where n > 1.  I looked through many
library books and found a formula for finding the error values in only a
couple of books.  The problem is that it does not work. I found errors in
several books concerning Reed Solomon, and there are a lot of details not
explained in most texts.  
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.  
When I implemented the case where the generator polynomial roots start in
position 1, you have the omega polynomial in the numerator and the
derivative of the sigma polynomial in the denominator.  The coefficient
becomes 1.  This works fine.
The forumla for the case of n > 1, is the same except the coefficient is
given as:
    - alpha^(j(1-n))
where n is the index for the first root of the generator polynomial.
This doesn't work, as I am stress testing the algorithm over thousands of
randomly generated messages.
Thank you for any information, either formulas or books and articles or
code that clearly explain this.
I also have another question: we were asked to implement am (n,k) code,
but the particular values of n and K are not listed in any table of valid
BCH codes.  The textbooks, however, refer to R-S as a type of BCH code. 
Does this mean that R-S cannot work with these values of n and h?  I have a
specification in front of me with these values of n and k, and also the AHA
website seems to have an implementation of it running online (without the
equations or source available).  Is it possible to have an R-S decoder for
values of (n,k) that are not listed in the tables of BCH codes?

Linda Seltzer

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


> I also have another question: we were asked to implement an (n,k) code,
> but the particular values of n and k are not listed in any table of valid
> BCH codes. &#4294967295;The textbooks, however, refer to R-S as a type of BCH code.
> Does this mean that R-S cannot work with these values of n and k? &#4294967295;I have a
> specification in front of me with these values of n and k, and also the AHA
> website seems to have an implementation of it running online (without the
> equations or source available). &#4294967295;Is it possible to have an R-S decoder for
> values of (n,k) that are not listed in the tables of BCH codes?

Yes, Reed-Solomon decoders can have values of n and k other than
those listed in tables.  The number of errors that can be corrected
is (n-k)/2, and if n-k happens to be an odd number, then (n-k-1)/2
errors can be corrected and (n-k+1)/2 errors can be detected but
not corrected. The values in published tables are usually for binary
BCH codes, i.e. code symbols are bits, whereas the code symbols
in Reed-Solomon codes are bytes (or bit vectors).

--Dilip Sarwate

Hi There,

> > 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.
> > 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) athttp://www.ifp.uiuc.edu/~sarwate/decoder.ps


I have implemented the algorithm in "http://www.ifp.uiuc.edu/~sarwate/
decoder.ps" using Matlab (a while ago, +/- 3 years), and according to
my knowledge it is working great. I used it in several simulations.

Thank you Prof Sarwate for sharing the link with us.
Jaco

_______________
Jaco Versfeld

http://dept.ee.wits.ac.za/~versfeld

"It is not the best team that wins, but the team that gets along best
that wins" John C. Maxwell

Thank you, Prof. Sarwate.
Is there also a paper on the encoder?
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.
Other texts define the generator polynomial as the Galois product of 
(X - alpha^m) .... (X - alpha^(m+2t-1))
where t is the number of errors and m is the starting location for the
generator roots.
If you take m = 2, the Galois product
(X - alpha^2) ... (X - alpha^7),
you will not get a 1 as the coefficient of the X^0 term.
So the statement by Sklar and the definition in some books seem to differ,
and information is needed on how to resolve this.
Is there anything different about the encoder when the generator
polynomial is defined to start at a location > 1?

> If you take m = 2, ...
> you will not get a 1 as the coefficient of the X^0 term.
> ... information is needed on how to resolve this.

The number is chosen to simplify the decoder.
"1" and "0" are magic for Forney.
With "1" the factor "x" following the division disappears.
With "0" the factor changes to "1/x" and compensates
a shift.
Other magic numbers like in the NASA CCSDS were chosen
for very special decoder-architectures ( Berlekamps
bit-serial, dual-basis ... ).

 > the definition in some books seem to differ,
Good books that cover RS very well are:

Blahut "Theory and practice of error control codes"
       Addison Wesley 1983
Clark Cain "Error-Correction Coding for digital
       Communications" Plenum 1981
Wicker "Error Control Systems" Prentice Hall 1995

Perhaps available at the local library.

MfG JRD

On Oct 9, 11:55&#4294967295;am, "lindasel" <lselt...@alumni.caltech.edu> wrote:

> Is there also a paper on the encoder?

There are lots of papers on encoders, though I have
not been fortunate enough to write any of them.

> 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.

I don't know which paper this is, but the requirement that
"the coefficients of X^(n-k) and X^0 mnust be 1" is not
applicable to Reed-Solomon codes.

> Other texts define the generator polynomial as the Galois product of
> (X - alpha^m) .... (X - alpha^(m+2t-1))
> where t is the number of errors and m is the starting location for the
> generator roots.

This is correct.

> If you take m = 2, the Galois product
> (X - alpha^2) ... (X - alpha^7),
> you will not get a 1 as the coefficient of the X^0 term.
> So the statement by Sklar and the definition in some books seem to differ,
> and information is needed on how to resolve this.

You will not get 1 as the coefficient of the X^0 term even
when m = 1.  If Sklar did make the statement that you
attribute to him, then that statement is wrong.  Eq. (22)
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.

> Is there anything different about the encoder when the generator
> polynomial is defined to start at a location > 1?

The answer can be implementation-dependent but there is not
anything significantly different.  In the *decoder*, as Rafael
Deliano points out in another message in  this thread, choosing
m = 0 or 1 does have some advantages.

--Dilip Sarwate

>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
>--Dilip Sarwate
To Professor Sarwate: Thank you for posting your paper on your website.  I
would appreciate it if you could answer a question about the iBM algorithm.
 The main iteration loop is
for r=0 step 1 until (2t-1) do
Question 1: Is the "until" inclusive or noninclusive.
Question 2: If the subscript of s can be r-0, r-1, ... r-t, then there
would be cases in which the subscript of s is a negative number.  Also,
wouldn't there be a different number of terms for each iteration of r?  Can
you provide another formulation of this? 
Also do you have a worked example, particularly of the iBM algorithm?  I
would like to check my code at each step.
If someone else has this working, your information would be appreciated.

>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.

 > iBM
I can´t help you with the inversionless BM
only with the old fashioned one.

 > I would like to check my code at each step.
   For that you will have to code the subroutines
to do the galois-field and polynomial math.
   Most textbooks start out with a simple 4 bit
field ( g = x^4 + x + 1 ) that
will be sufficient for BCH(15,7) BCH(15,5)
RS(15,9) RS(15,11). Assuming that works
one can scale up to 8 bit.

   My description is in german, but probably
clear enough if you have any book to help you.
The calculation for the "digits":
http://www.embeddedforth.de/temp/gal.pdf
   Ignore pictures 2,3,6,7: they are for
implementation in hardware. The Lin Costello
book has a good description of that.
   Ignore Zech: not necessary.
View the result as a closed
"galois-field-coprocessor"
( lower half of page ):
http://www.embeddedforth.de/temp/fr.pdf
Note that tables for squarer, cuber, inversion
are handy.
The upper half of the pages shows the BCH-decoder:
somewhat simpler because binary and therefore
no need for Forney.

   The next layer is polynomials ( "strings of
digits" ). View the result as a closed
"polynomial-processor". Skip division
you do not need it for BM.
http://www.embeddedforth.de/temp/pr.pdf
Ignore the half page Euclid.

   Ignore the first 2 pages on Euclid:
http://www.embeddedforth.de/temp/bm.pdf
   But note at picture 14,15 that two
notations for S(z) are common:
either you have a dummy "1" as first
digit or not.

   Many flowcharts for BM on page 3,4.
They are all slightly different improvements
on Massey, they all worked for me.
I prefer Blahut ( he has the best description
on BM in his book ).
Table 4 has detailed runs,
Table 5 only I/O-data.
   Stuff like "L(z)-d*z*B(z)" is
in the "polynomial-processor":
shift ( picture 9 )
multiplication of constant ( picture 3 )
addition ( picture 2 )
"L(z)/d" is:
division by constant ( picture 4 )
   Most foulups in coding are in calculating
discrepancy d due to the different notations
for S(z)

   The simple BS will work for BCH but needs
for RS an external Omega-calculator ( page 5 ):
http://www.embeddedforth.de/temp/rs.pdf
Its a multiplication of polynomials,
result chopped to the right length.

   My code probably won´t help you as it
is in FORTH.
   You can buy the first edition of
Morelos-Zaragoza "The Art of Error Correcting Coding"
at ebay from the UK very cheaply at the moment:
http://cgi.ebay.de/The-Art-of-Error-Correcting-Coding-Book_W0QQitemZ370094882240QQcmdZViewItem?hash=item370094882240
For this book he has C code on his homepage.
The book ( and that seems to go for the 2. edition too )
only has 220 pages and tries to cover a lot of subjects.
Not much explaining there, but worked examples and at
that price its worth having.

MfG  JRD

On Oct 15, 2:40&#4294967295;am, "lindasel" <lselt...@alumni.caltech.edu> wrote:

> >(www.informit.com/content/images/art_sklar7_reed-solomon/elementLinks/
> >art_sklar7_reed-solomon.pdf)

>
> This link gave me an error message. &#4294967295;The site seems to have restricted
> access.

The URL is very long, and Google Groups
broke it into two lines.  The URL that I posted
(as opposed to what Google shows) continues
past "...Links/" with the file name which ends
in "solomon.pdf"