Julius, Ray, Clay,

Thank you.

--Randy

Julius Kusuma <kusuma@mit.edu> writes:

> On Wed, 31 Mar 2004, Raymond Toy wrote:
> 
> > Add Michelson and Levesque to the list.  This is what I used to learn
> > about block codes.
> >
> > Ray
> >
> 
> for algebraic block codes, i highly recommend MacWilliams and Sloane's
> "the theory of error-correcting codes" as your second book.  it's a bit
> dense, but if you are mathematically inclined, it's a very thorough
> treatment of the subject matter.
> 
> this book defines Reed-Solomon codes as:
> 
> "A Reed-Solomon code over GF(q) is a BCH code of length N=q-1.  Of course
> q is never 2.  Thus the length is the number of nonzero elements in the
> ground field."
> 
> cyclic codes tend to work better over larger finite fields;  in fact, if i
> recall correctly, this is one motivation for Forney's thesis on
> concatenated codes:  if we wish to use these powerful cyclic codes, how do
> we map it to the channel?  of course, this is among other things
> contributed in the said thesis.
> 
> julius
> 
> -- 
> The most rigorous proofs will be shown by vigorous handwaving.
> http://www.mit.edu/~kusuma
> 
> opinion of author is not necessarily of the institute

-- 
Randy Yates
Sony Ericsson Mobile Communications
Research Triangle Park, NC, USA
randy.yates@sonyericsson.com, 919-472-1124

On Wed, 31 Mar 2004, Raymond Toy wrote:

> Add Michelson and Levesque to the list.  This is what I used to learn
> about block codes.
>
> Ray
>

for algebraic block codes, i highly recommend MacWilliams and Sloane's
"the theory of error-correcting codes" as your second book.  it's a bit
dense, but if you are mathematically inclined, it's a very thorough
treatment of the subject matter.

this book defines Reed-Solomon codes as:

"A Reed-Solomon code over GF(q) is a BCH code of length N=q-1.  Of course
q is never 2.  Thus the length is the number of nonzero elements in the
ground field."

cyclic codes tend to work better over larger finite fields;  in fact, if i
recall correctly, this is one motivation for Forney's thesis on
concatenated codes:  if we wish to use these powerful cyclic codes, how do
we map it to the channel?  of course, this is among other things
contributed in the said thesis.

julius

-- 
The most rigorous proofs will be shown by vigorous handwaving.
http://www.mit.edu/~kusuma

opinion of author is not necessarily of the institute

>>>>> "Clay" == Clay S Turner <CSTurner@WSE.Biz> writes:

    Clay> Hello Randy,

    Clay> One classic that describes the RS codes as a special case of the BCH codes
    Clay> is "Error Correcting Codes" by Peterson and Weldon, section 9.2. Another
    Clay> reference that makes this same claim is "Coding and Information Theory" by
    Clay> Roman, section 4.3.

Add Michelson and Levesque to the list.  This is what I used to learn
about block codes.

Ray

"Randy Yates" <yates@ieee.org> wrote in message
news:u105iohz.fsf@ieee.org...
> >>
> >>I had learned that a Reed-Solomon code was a special type of
> >>(non-binary) BCH code.  So I guess it depends on the book you are
> >>using as your reference.  I always take BCH to be the non-binary one,
> >>unless it's clear from context that some other BCH code is being
> >>discussed.
> >>
> >>Ray
> >
> > That's my understanding as well, RS codes are a subset of BCH, not the
> > other way around.  I've seen this classification and description in
> > multiple places, so I tend to think of them that way.  Makes sense to
> > me as well.
>
> Hi Eric/Ray,
>
> Could you please give me a reference or two on where RS codes are defined
> this way?

Hello Randy,

One classic that describes the RS codes as a special case of the BCH codes
is "Error Correcting Codes" by Peterson and Weldon, section 9.2. Another
reference that makes this same claim is "Coding and Information Theory" by
Roman, section 4.3.

I hope this helps.

-- 
Clay S. Turner, V.P.
Wireless Systems Engineering, Inc.
Satellite Beach, Florida 32937
(321) 777-7889
www.wse.biz
csturner@wse.biz





>
> RS codes were defined to us in terms of the Vandermonde matrix over GF(q)
> of dimension 2*t by n, where t is the number of correctable errors and
> 2t <= q-1. Here q can be any p^m. Then it was narrowed to BCH codes by
> the codewords that only have elements over GF(p).
> -- 
> %  Randy Yates                  % "Ticket to the moon, flight leaves here
today
> %% Fuquay-Varina, NC            %  from Satellite 2"
> %%% 919-577-9882                % 'Ticket To The Moon'
> %%%% <yates@ieee.org>           % *Time*, Electric Light Orchestra
> http://home.earthlink.net/~yatescr

Randy Yates <yates@ieee.org> writes:
> [...]
> Then it was narrowed to BCH codes by
> the codewords that only have elements over GF(p).

I should have added "where p = 2". 
-- 
%  Randy Yates                  % "So now it's getting late,
%% Fuquay-Varina, NC            %    and those who hesitate
%%% 919-577-9882                %    got no one..."
%%%% <yates@ieee.org>           % 'Waterfall', *Face The Music*, ELO
http://home.earthlink.net/~yatescr

eric.jacobsen@delete.ieee.org (Eric Jacobsen) writes:

> On Tue, 30 Mar 2004 11:52:17 -0500, Raymond Toy <toy@rtp.ericsson.se>
> wrote:
>
>>>>>>> "Randy" == Randy Yates <randy.yates@sonyericsson.com> writes:
>>
>>    Randy> "A BCH code over GF(p)" is a contradiction according to the way it has
>>    Randy> been presented to me. A BCH code is, BY DEFINITION, a BINARY code, 
>>    Randy> according to my notes.
>>
>>I had learned that a Reed-Solomon code was a special type of
>>(non-binary) BCH code.  So I guess it depends on the book you are
>>using as your reference.  I always take BCH to be the non-binary one,
>>unless it's clear from context that some other BCH code is being
>>discussed. 
>>
>>Ray
>
> That's my understanding as well, RS codes are a subset of BCH, not the
> other way around.  I've seen this classification and description in
> multiple places, so I tend to think of them that way.  Makes sense to
> me as well.

Hi Eric/Ray, 

Could you please give me a reference or two on where RS codes are defined
this way?

RS codes were defined to us in terms of the Vandermonde matrix over GF(q) 
of dimension 2*t by n, where t is the number of correctable errors and 
2t <= q-1. Here q can be any p^m. Then it was narrowed to BCH codes by
the codewords that only have elements over GF(p).
-- 
%  Randy Yates                  % "Ticket to the moon, flight leaves here today 
%% Fuquay-Varina, NC            %  from Satellite 2"
%%% 919-577-9882                % 'Ticket To The Moon' 
%%%% <yates@ieee.org>           % *Time*, Electric Light Orchestra
http://home.earthlink.net/~yatescr

On Tue, 30 Mar 2004 11:52:17 -0500, Raymond Toy <toy@rtp.ericsson.se>
wrote:

>>>>>> "Randy" == Randy Yates <randy.yates@sonyericsson.com> writes:
>
>    Randy> "A BCH code over GF(p)" is a contradiction according to the way it has
>    Randy> been presented to me. A BCH code is, BY DEFINITION, a BINARY code, 
>    Randy> according to my notes.
>
>I had learned that a Reed-Solomon code was a special type of
>(non-binary) BCH code.  So I guess it depends on the book you are
>using as your reference.  I always take BCH to be the non-binary one,
>unless it's clear from context that some other BCH code is being
>discussed. 
>
>Ray

That's my understanding as well, RS codes are a subset of BCH, not the
other way around.  I've seen this classification and description in
multiple places, so I tend to think of them that way.  Makes sense to
me as well.

I've learned that getting a community to absolutely agree on
definitions is a futile exercise.  The best one can do is try to
ensure a common understanding of definitions and issues in each
context.   A pain, to be sure, but functionally it appears to be the
only practical way to do things.

Eric Jacobsen
Minister of Algorithms, Intel Corp.
My opinions may not be Intel's opinions.
http://www.ericjacobsen.org

>>>>> "Randy" == Randy Yates <randy.yates@sonyericsson.com> writes:

    Randy> "A BCH code over GF(p)" is a contradiction according to the way it has
    Randy> been presented to me. A BCH code is, BY DEFINITION, a BINARY code, 
    Randy> according to my notes.

I had learned that a Reed-Solomon code was a special type of
(non-binary) BCH code.  So I guess it depends on the book you are
using as your reference.  I always take BCH to be the non-binary one,
unless it's clear from context that some other BCH code is being
discussed. 

Ray

rge11x@netscape.net (robert egri) writes:
> [...]
> Randy Yates <randy.yates@sonyericsson.com> wrote in message news:<xxpy8pj9t1g.fsf@usrts005.corpusers.net>...
>> "A BCH code over GF(p)" is a contradiction according to the way it has
>> been presented to me. A BCH code is, BY DEFINITION, a BINARY code, 
>> according to my notes.
>
> That is not a contradiction. There can be many definitions, some may
> be more general than others. 

As long as there are many definitions, it is impossible to identify
a BCH code unambiguously. 

> Professor Sarwate has not only the right attitude he has also given
> you the RIGHT answer; 

So to belittle someone seeking information by referring to them in a demeaning
manner is the right attitude? Interesting viewpoint.
-- 
%  Randy Yates                  % "She's sweet on Wagner-I think she'd die for Beethoven.
%% Fuquay-Varina, NC            %  She love the way Puccini lays down a tune, and
%%% 919-577-9882                %  Verdi's always creepin' from her room." 
%%%% <yates@ieee.org>           % "Rockaria", *A New World Record*, ELO   
http://home.earthlink.net/~yatescr

Randy Yates <randy.yates@sonyericsson.com> wrote in message news:<xxpy8pj9t1g.fsf@usrts005.corpusers.net>...
> Dilip Sarwate <sarwate@uiuc.edu> writes:
> 
> > Randy Yates wrote:
> > > 
> > > Dilip Sarwate <sarwate@uiuc.edu> writes:
> > > 
> > > > Every Reed-Solomon code contains a binary BCH code as
> > > > a subspace.
> > > 
> > > Hmm. Well, how about the (26, 21) Reed Solomon code
> > > constructed from GF(3^3) with minimum distance 5?
> > 
> > Randy:
> > 
> > Stop nitpicking!  
> 
> Dilip:
> 
> I can see how this would be viewed as nitpicking to someone who has
> studied the subject for decades and is comfortable with the
> terminology and theory. However, I am a beginner and, having only
> discussed it thus far within the confines of my classmates and
> professor, am still a bit unsure of the lingo and common assumptions.
> Please try to keep that in mind before criticizing me.
> 
> > A more general
> > statement would have been "Every Reed-Solomon code
> > over GF(p^m) contains a BCH code over GF(p)."
> 
> "A BCH code over GF(p)" is a contradiction according to the way it has
> been presented to me. A BCH code is, BY DEFINITION, a BINARY code, 
> according to my notes.

That is not a contradiction. There can be many definitions, some may
be more general than others. There are binary BCH codes and indeed
these are the most common ones but there are also nonbinary BCH codes,
as well.
A binary BCH code is built over a binary extension field; a non-binary
BCH code is built over a non-binary extension field. If you have a
prime number p and an extension field GF(p^m) over GF(p) then you can
build a Reed-SOlomon code over the extension field. A subcode of said
RS code such that all the symbols are in the sub-field GF(p^s) of
GF(p^m) for some s is a BCH code. When s=1 you always get the subfield
GF(p). For other s>1, you may or may not get one. If p=2 and s=1 you
have the binary BCH codes. (Question: When is GF(p^s) < GF(p^m)?)
Whatever decodes the RS code will by force will also decode its BCH
subfield/subcode using the same extension field GF(p^m) where the
error locator polynomial lives.

> 
> Further, I thought the key reason we are interested in BCH codes is
> that, due to their binary nature, the decoder can be implemented by
> finding the error-locator polynomial alone (e.g., using the 
> Berlekamp-Massey algorithm) without requiring the error magnitudes
> (e.g., via the Forney algorithm) to be computed. This, combined with
> the maximum-distance separable and easily-specified minimum distance 
> properties, makes them practically interesting, I thought. 
> 
> > > Further, even if you construct it from GF(2^m), how
> > > are you guaranteed that there are ANY binary codewords
> > > (other than the trivial codeword)?
> > 
> > If the generator polynomial of Reed-Solomon code does
> > not have 1 as a root, then we are guaranteed that the
> > all-ones vector is a codeword in the Reed-Solomon code
> > as well as the BCH subcode.  
> 
> That is something we hadn't been shown. 
> 
> > More generally, if the
> > rate is low enough, the BCH subcode might be just the
> > repetition code consisting of the all-zero and all-one
> > vectors.  Nitpickers are reminded that in the case of
> > GF(p), p > 2, the repetition code will have p codewords:
> > the all-zero, all-one, all-two, .... , all-(p-1).
> 
> Please note that this attitude contributes absolutely zero to
> encouraging discussion and learning on the subject. The fact
> that you're an expert in it is great. However, try to give
> a little room to those who aren't.


Professor Sarwate has not only the right attitude he has also given
you the RIGHT answer; therefore, he contributed the best that any one
could to the discussion...

cheers