From: Dan Kotlow Subject: Re: I need some clarification: RS codes Date: Mon, 01 May 2000 06:19:30 GMT Newsgroups: sci.math,sci.math.num-analysis,sci.math.research Summary: [missing] On Thu, 27 Apr 2000 08:31:28 -0400, ian wrote: > >Hello all, > > I am looking into Reed-Solomon codes and I am confused at what >appears to be (though I'm sure it isn't) an inconsistency in the >literature. I've read the original paper by Reed and Solomon, >"Polynomial Codes over Certain Finite Fields", which says that the code >maps vectors of length m (the information) onto vectors of length 2^n >(the transmitted message), where m < 2^n. Very well, but in all the >practical references I've found, on the internet or otherwise, where a >Reed-Solomon code is actually implemented, the length of the transmitted >message is always >2^n - 1. For instance, the RS(255, 249) code takes a message of length >249 and extends it to 255, which is 2^8 - 1, not 2^8 as the original >paper indicates would be the case. Could someone please tell me what >I'm overlooking here? Has the code been optimized since its original >conception by not sending the P(0) term? Please help me... > >Confused, >ian > > Adding the P(0) component to the code formed by evaluating all polynomials of degree <= k-1 on the multiplicative group of a finite field GF(q) is the same as extending that code by adding a parity symbol. This is because the values of any polynomial on all the elements of GF(q) add up to zero. The unextended code is used in practice because it is a cyclic, BCH code, for which there are powerful decoding techniques available. Reed-Solomon codes did not become popular until this not-too-obvious equivalence was observed and said powerful decoding methods were developed. The equivalence of the two definitions is not addressed in any of the coding theory books on my shelf, but it can be pieced together from the results usually covered. Here is a condensed proof. Let b be a primitive element in GF(q) (generator of the multiplicative group), a = b^(-1), n = q - 1. Associate with any n-tuple c = (c_0,...,c_(n-1)) the polynomial P(x) which has c_i as the coefficient of x^i. The linear map F: c -> n (P(a),...,P(a^(n-1)) on n-tuples has the inverse c -> (P(b),...,P(b^(n-1)) and is therefore bijective on n-tuples (written out, these are the "Finite Field Fourier Transform" and its inverse transform). The code RS(n,k) with distance d = 2t + 1 is (by the usual definition) the k-dimensional subspace of n-tuples such that P(b) = ... = P(b^(2t)) = 0. F carries this subspace into the k-dimensional subspace of n-tuples whose last 2t components vanish, and is therefore an isomorphism of these subspaces. The inverse map exhibits RS(n,k) as an (unextended) Reed-Solomon code by the original definition. The original definition was generalized by Goppa to construct "algebraic geometry codes".