Forums

BCH Codes and Reed-Solomon Codes

Started by Randy Yates March 26, 2004
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