BCH Codes and Reed-Solomon Codes

Does any one know of any research which attempts to analytically determine
the the binary codeword subspace (BCH code) of a Reed-Solomon code, that is
the binary vector subspace of a subspace of GF(2^m - 1)^n?
-- 
%  Randy Yates                  % "My Shangri-la has gone away, fading like 
%% Fuquay-Varina, NC            %  the Beatles on 'Hey Jude'" 
%%% 919-577-9882                %  
%%%% <yates@ieee.org>           % 'Shangri-La', *A New World Record*, ELO
http://home.earthlink.net/~yatescr

Every Reed-Solomon code contains a binary BCH code as
a subspace.  Recall that the codeword polynomials of
a t-error-correcting Reed-Solomon code have 2t
consecutive powers of alpha as roots.  The codeword
polynomials from a binary t-error-correcting BCH code
(defined in terms of these same consecutive powers)
also have all these 2t roots (and their conjugates
as well!).  So the answer to Randy's question is
striaghtforward.  But perhaps he meant to ask about
the codewords that one would get by looking at, say,
the first bit of each m-bit symbol in a Reed-Solomon
codeword?  That's a much more complicated problem since
the answer depends in part on the basis used to represent
the field.  The book by MacWilliams and Sloane has some
discussion of this problem.  More recent work is by
C. T. Retter published in the IEEE Transactions on
Information Theory.

Hope this helps

--Dilip Sarwate

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? 

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)?

> Recall that the codeword polynomials of
> a t-error-correcting Reed-Solomon code have 2t
> consecutive powers of alpha as roots.  The codeword
> polynomials from a binary t-error-correcting BCH code
> (defined in terms of these same consecutive powers)
> also have all these 2t roots (and their conjugates
> as well!).  So the answer to Randy's question is
> striaghtforward.  

> But perhaps he meant to ask about
> the codewords that one would get by looking at, say,
> the first bit of each m-bit symbol in a Reed-Solomon
> codeword?  

I'm not sure why there's confusion here. As I understand it, BCH codes
are the subclass of Reed-Solomon codes constructed from GF(2^m) in
which every codeword is binary, i.e., consists only of vectors with
elements from the subfield GF(2). That seems to be what you say above,
but that's true by definition for a BCH code.

> That's a much more complicated problem since
> the answer depends in part on the basis used to represent
> the field.  The book by MacWilliams and Sloane has some
> discussion of this problem.  More recent work is by
> C. T. Retter published in the IEEE Transactions on
> Information Theory.

Retter - thanks Dilip.
-- 
%  Randy Yates                  % "Midnight, on the water... 
%% Fuquay-Varina, NC            %  I saw...  the ocean's daughter." 
%%% 919-577-9882                % 'Can't Get It Out Of My Head' 
%%%% <yates@ieee.org>           % *El Dorado*, Electric Light Orchestra
http://home.earthlink.net/~yatescr

Randy Yates <yates@ieee.org> writes:
> [...]
> Hmm. Well, how about the (26, 21) Reed Solomon code
> constructed from GF(3^3) with minimum distance 5? 

Wups! That should be the (26, 22) RS code.
-- 
%  Randy Yates                  % "...the answer lies within your soul
%% Fuquay-Varina, NC            %       'cause no one knows which side
%%% 919-577-9882                %                   the coin will fall."
%%%% <yates@ieee.org>           %  'Big Wheels', *Out of the Blue*, ELO
http://home.earthlink.net/~yatescr

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!  Your original question was about
binary subcodes of a Reed-Solomon code over GF(2^m),
which is the question that I answered.  A more general
statement would have been "Every Reed-Solomon code
over GF(p^m) contains a BCH code over GF(p)."


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

--Dilip Sarwate

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.

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.
-- 
Randy Yates
Sony Ericsson Mobile Communications
Research Triangle Park, NC, USA
randy.yates@sonyericsson.com, 919-472-1124

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

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" == 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

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