>On Oct 7, 1:59�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. �
>> 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
Reply by Steve Pope●October 22, 20082008-10-22
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
Reply by Steve Pope●October 22, 20082008-10-22
dvsarwate@yahoo.com <dvsarwate@gmail.com> wrote:
>On Oct 7, 1:59�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. �
>> 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
Reply by lindasel●October 20, 20082008-10-20
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)
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.
Reply by Jerry Avins●October 15, 20082008-10-15
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 **
Reply by dvsa...@yahoo.com●October 15, 20082008-10-15
On Oct 15, 2:40�am, "lindasel" <lselt...@alumni.caltech.edu> wrote:
>
> This link gave me an error message. �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"
Reply by Rafael Deliano●October 15, 20082008-10-15
> 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
Reply by lindasel●October 15, 20082008-10-15
>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.
Reply by lindasel●October 13, 20082008-10-13
>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.