Implementing Generalized Reed-Solomon Codes and a Cyclic Code Decoder in GUAVA
Jason McGowan
4-4-2005

# Problem

1. Implement evaluation codes. (Algorithm 1)

2. Write a decoding algorithm for Generalized Reed-Solomon codes. (Algorithm 2)

3. Write a decoding algorithm for cyclic codes. (Algorithm 3)

Background Information: GAP is a computer algebra program whose open source kernel is written in the C programming language. GUAVA is a package for error-correcting block codes in GAP. Neither GAP nor GUAVA contains a program for decoding Generalized Reed-Solomon codes or cyclic codes, two very popular families of codes. Our work will greatly speed the decoding algorithms for several types of codes in the next release of the GUAVA package.

# Introduction

A linear code of length is a subspace of for some prime power and some . Let be a linear code of length over . If then the code is called binary. We assume that has been given the standard basis , , ..., . The dimension of is denoted , so the number of elements of is equal to .

Another important parameter associated to the code is the number of errors which it can, in principle, correct. For this notion, we need to introduce the Hamming metric. For any two , let denote the number of coordinates where these two vectors differ:

 (1)

This is called the Hamming distance or Hamming metric. Define the weight of to be the number of non-zero entries of . Note, because the vector has non-zero entries only at locations where and differ. The smallest distance between distinct codewords in a linear code is the minimum distance of :

 (2)

(for details see [HILL] Theorem 5.2).

A linear code of length and dimension over has a basis of vectors of length . If those vectors are arranged as rows of a matrix , then we call the matrix a generator matrix for .

Example 1   The following matrix is a generator matrix for a code of length 11, dimension 8, and minimum distance 4 over .

Now we define a general class of codes which, as part of this project, were implemented in GUAVA. Let denote the polynomial ring in variables through . Let denote the field of rational functions in these variables. Let be a finite dimensional subspace of and choose a subset of points of disjoint from the poles of the functions in (so all the functions are defined at the points ). Construct a linear code by evaluating basis vectors of at the points of as follows. Choose which are basis vectors for and pick as above. Denote by

the evaluation map . Define the associated evaluation code by means of the generator matrix,

This is the code spanned by the vectors , .

Example 2   Let be greater than . Let denote the polynomial ring in . Let denote the vector space of polynomials with coefficients in of degree less than . Let denote a subset of elements of (since this makes sense). Choose as a vector space basis of the powers of . In this case the evaluation code has generator matrix,

This is a generalized Reed-Solomon code of length and dimension over .

Lemma 3   Let denote a generalized Reed-Solomon code as in above example. has minimum distance .

Proof Suppose a codeword has weight less than . Associated to is a polynomial of degree less than with the property that . If the weight of is less than then must have greater than zeros. Therefore has greater than zeros. This contradicts the fact that has at most zeros.

Therefore all generalized Reed-Solomon codes are minimum distance separable.

Definition 4   A linear code of length is a cyclic code if whenever is a codeword then so is its cyclic shift .

Example 5   Consider the binary code with generator matrix

Clearly these four rows , , , are obtained from the previous by a shift to the right. Also notes the shift of to the right is equal to . The shift of to the right is . And the shift of is . The shift of is . Therefore, the linear code generated by is invariate under shifts to the right. Therefore is a cyclic code.

Cyclic codewords are conveniently represented as polynomials modulo . In fact, if then let

denote the associated codeword polynomial. In this notation the cyclic shift of corresponds to the polynomial . In other words cyclic shifts correspond to multiplication by . Since cyclic shifts leave cyclic codes invariant, multiplication by any power of modulo corresponds to a codeword in . Since is a linear code, the sum of any two such codeword polynomials is another codeword polynomial. Therefore, in fact, the product of any codeword polynomial times any polynomial in modulo is another codeword polynomial.

Denote by the ring of polynomials with coefficients in modulo :

 (3)

Define an ideal of to be any subset of closed under addition and multiplication by an arbitrary element of :
• If then , and
• If and then .
In other words an ideal in is simply a subset closed under addition and multiplication by an arbitrary polynomial modulo . In particular, the collection of codeword polynomials associated to a cyclic code is an ideal of .

Lemma 6   There is natural one-to-one correspondence between cyclic codes of length over and ideals of .

This can be found in any book on coding theory, for example MacWilliams and Sloane [MS].

In fact GUAVA allows you to easily pass back and forth between codewords as vectors and codewords as polynomials.

In order to define the generator polynomial of a cyclic code we need the following mathematical fact.

Lemma 7   Every ideal of is of the form . In other words every element of is a multiple of for some polynomial in .

Ideals which are of the form are called principal ideals and is called a generator of the ideal .

Proof Suppose not. Let be a non-zero element in of smallest degree. Pick an arbitrary non-zero element in . By the division algorithm, we can write where and are polynomials and the degree of is strictly less than the degree of . Notice that belongs to by definition. This contradicts the assumption that has smallest degree unless . Therefore every element of is a multiple of . Take .

Definition 8   Let be a cyclic code of length . Let be the ideal corresponding to by Lemma 6. We call a generator polynomial of if it is a generator of .

Example 9   We continue with Example 5. Let . This is the codeword polynomial associated to the top row of the generator matrix. is the generator polynomial of the cyclic code . Note that .

More generally we have the following result

Lemma 10   The generator polynomial always divides .

Proof By the division algorithm for some quotient and some remainder of degree less than . In this means that . So corresponds to a codeword since is the generator polynomial. This is impossible since has minimal degree of any codeword in unless .

# Algorithms

Recall .

One common method of constructing a linear code is by constructing its generator matrix from the values of certain functions at certain points. Sometimes this construction adds extra structure to the code which aids in implementing fast decoding algorithms. The algorithm below assumes that you have a list of rational functions in variables and a list of points in .

Algorithm 1 (Evaluation Code)

1. Input: is a list of points in , is a list of rational functions in variables. is the ring of multivariate polynomials in variables of which is a subset.

2. For and let , where and . Let be the code with generator matrix . This is a code over .

The decoding of generalized Reed-Solomon codes relies on the algebraic structure of the code. Codewords are values of a polynomial of degree less than . The rough idea is that if enough values are known, then the polynomial can be reconstructed (think of the Lagrange interpolation formula).

Let be a received word where is a codeword and the weight of is less than , where denotes the integer part. The interpolating polynomial is defined to be a polynomial of two variables having the following three properties:

1. , for all with ,
2. ,

First we show that an interpolating polynomial always exists.

Lemma 11   There always exists a non-zero polynomial satisfying the conditions above.

Proof By condition 2 we can write

and by condition 3 we can write

So we have degrees of freedom in choosing the coefficients for . Condition 1 imposes constraints on these coefficients, therefore giving rise to a linear system of equations in unknowns. By Lemma 3, . So . Therefore, this system has a solution.

Why is it that computing will help us to find the polynomial that gave rise to the codeword that we're looking for? Here's the intuitive explanation. Since there aren't too many errors in the received word, it follows that usually'' . Therefore, by Property (1) above, is usually'' 0. But notice that Properties (2) and (3) above, is a polynomial in of degree at most . So if the number which are roots of exceeds , then must be equal to 0 identically. But if , then it is easy to solve for : implies .

Algorithm 2 (Generalized Reed-Solomon Decoder)

1. Input: is a list of points in , is an integer.

Output: A codeword in close to or fail''.

2. Let and . Property (1) above gives equations

in unknowns . Solve these equations for these unknowns.

3. Compute using the previous step .

4. Let . Return .

Consider a cyclic code with generator polynomial of length over and a received word in . Let denote the polynomial associated to the received word . Consider the syndrome polynomial'' . If the degree of is less than then a) the polynomial is within Hamming distance of the received polynomial , and b) is associated to a codeword in . Therefore is the codeword that the minimum distance algorithm would return for decoding .

Algorithm 3 (Cyclic Decoder)

1. Input: is a cyclic code with generator polynomial of length over and a received word in .

Output: A codeword in close to or fail''.

2. Compute the polynomial associated to the received word .

3. For each from to , compute the syndrome polynomials . Let denote the degree of .

4. Find the first which is less than . Let . Let .

5. Convert to a codeword and return .

The algorithm will never return fail if the number of errors is less than [(d-1)/2].

# Examples

In the following two examples we consider a cyclic code of length 10 over the field with three elements . Let denote a random codeword. We create an error in the first coordinate of and use the method of Algorithm 3 to decode this incorrect received word.

#### example - stays in 1st loop

CCs:=CyclicCodes(10,GF(3));;
C:=CCs[2];
c:=Random(C);
e:=Codeword(Z(3)*[1,0,0,0,0,0,0,0,0,0,0],GF(3));
CyclicDecodeword(c+e,C);

gap> CCs:=CyclicCodes(10,GF(3));;
gap> C:=CCs[2];
a cyclic [10,9,1..2]1 enumerated code over GF(3)
gap> c:=Random(C);
[ 2 1 0 1 1 1 1 2 0 2 ]
gap> e:=Codeword(Z(3)*[1,0,0,0,0,0,0,0,0,0,0],GF(3));
[ 2 0 0 0 0 0 0 0 0 0 0 ]
gap> CyclicDecodeword(c+e,C);
[ 2 1 0 1 1 1 1 2 0 2 ]

######## example - goes into 2nd loop

CCs:=CyclicCodes(15,GF(3));;
C:=CCs[6];
MinimimDistance(C);
c:=Random(C);
e:=Codeword(Z(3)*[1,0,0,0,0,0,0,0,0,0,0,0,0,0,1],GF(3));
CyclicDecodeword(c+e,C);


# GAP Code

ValueExtended:=function(f,vars,P)
return Value(NumeratorOfRationalFunction(f)*vars[1]^0,vars,P)\
*Value(DenominatorOfRationalFunction(f)*vars[1]^0,vars,P)^(-1);
end;

# P is a list of n points in F^r
# L is a list of rational functions in r variables
# EvaluationCode returns the image of the evaluation map f->[f(P1),...,f(Pn)]
# The output is the code whose generator matrix has rows (f(P1)...f(Pn)) where
# f is in L and P={P1,..,Pn}
EvaluationCode:=function(P,L,R)
local i, G, n, C, j, k, varsn,varsd, vars, F;
vars:=IndeterminatesOfPolynomialRing(R);
F:=CoefficientsRing(R);
n:=Length(P);
k:=Length(L);
G:=ShallowCopy(NullMat(k,n,F));
for i in [1..k] do
for j in [1..n] do
G[i][j]:=ValueExtended(L[i],vars,P[j]);
od;
od;
C:=GeneratorMatCode(G,F);
C!.GeneratorMat:=ShallowCopy(G);
return C;
end;

GeneralizedReedSolomonCode:=function(P,k,R)
local p, L, vars, i, F, f, x, C, R0, P0, G, j, n;
n:=Length(P);
F:=CoefficientsRing(R);
G:=NullMat(k,n,F);
vars:=IndeterminatesOfPolynomialRing(R);
x:=vars[1];
L:=List([0..(k-1)],i->(x^i));
for i in [1..k] do
for j in [1..n] do
G[i][j]:=Value(L[i],vars,[P[j]]);
od;
od;
C:=GeneratorMatCode(G,F);
C!.GeneratorMat:=ShallowCopy(G);
return C;
end;

GeneralizedReedMullerCode:=function(Pts,r,F)
## Pts are points in F^d
## for usual GRM code, take
##     pts:=Cartesian(List([1..d],i->Elements(F)));
## for some d>1.
## r is the degree of the polys in x1, ..., xd
##
local q, n, pts, row, B0, L, exps, Ld, i, x, e, d;
q:=Size(F);
d:=Length(Pts[1]);
L:=[0..Minimum(q-1,r)];
Ld:=Cartesian(List([1..d],i->L));
exps:=Filtered(Ld,x->Sum(x)<=r);
n:=Size(pts);
B0:=[];
for e in exps do
row:=List(Pts,t->Product([1..d],i->t[i]^e[i]));
od;
B:=AsList(B0);
C:=GeneratorMatCode(One(F)*B,F);
return C;
end;

CyclicDecodeword:=function(w,C)
local d, g, wpol, s, ds, cpol, cc, c, i, m, e, x, n, ccc, r;
if not(IsCyclicCode(C)) then
Error("\n\n Code must be cyclic");
fi;
n:=WordLength(C);
d:=MinimumDistance(C);
g:=GeneratorPol(C);
x:=IndeterminateOfUnivariateRationalFunction(g);
wpol:=PolyCodeword(w);
s:=wpol mod g;
ds:=DegreeOfLaurentPolynomial(s);
if ds<=Int((d-1)/2) then
cpol:=wpol-s;
cc:=CoefficientsOfUnivariatePolynomial(cpol);
r:=Length(cc);
ccc:=Concatenation(cc,List([1..(n-r)],i->0*cc[1]));
c:=Codeword(ccc);
return c;
fi;
for i in [1..(n-1)] do
s:=x^i*wpol mod g;
ds:=DegreeOfLaurentPolynomial(s);
if ds<=Int((d-1)/2) then
m:=i;
e:=x^(n-m)*s mod (x^n-1);
cpol:=wpol-e;
cc:=CoefficientsOfUnivariatePolynomial(cpol);
r:=Length(cc);
ccc:=Concatenation(cc,List([1..(n-r)],i->0*cc[1]));
c:=Codeword(ccc);
return c;
fi;
od;
return "fail";
end;

#N is a matrix with same rowdim as M
#the fcn adjoins N to the end of M
local i,j,S,col,NT;
col:=MutableTransposedMat(M);  #preserves M
NT:=MutableTransposedMat(N);   #preserves N
for j in [1..DimensionsMat(N)[2]] do
od;
return MutableTransposedMat(col);
end;

#N is a matrix with same coldim as M
#the fcn adjoins N to the bottom of M
local i,j,S,row;
row:=ShallowCopy(M);#to preserve M;
for j in [1..DimensionsMat(N)[1]] do
od;
return row;
end;

block_matrix:=function(L)
#L is an array of matrices of the form
#[[M1,...,Ma],[N1,...,Na],...,[P1,...,Pa]]
#returns the associated block matrix
local A,B,i,j,m,n;
n:=Length(L[1]);
m:=Length(L);
A:=[];
if n=1 then
if m=1 then return L[1][1]; fi;
A:=L[1][1];
for i in [2..m] do
od;
return A;
fi;
for j in [1..m] do
A[j]:=L[j][1];
od;
for j in [1..m] do
for i in [2..n] do
od;
od;
B:=A[1];
for j in [2..m] do
od;
return B;
end;

DiagonalPower:=function(r,j)
local R,n,i;
n:=Length(r);
R:=DiagonalMat(List([1..n],i->r[i]^j));
return R;
end;

#
#Input: Xlist=[x1,..,xn], l = highest power
#Output: Vandermonde matrix (xi^j)
#
VandermondeMat:=function(Xlist,x)
local V,n,i,j;
n:=Length(Xlist);
V:=List([1..(x+1)],j->List([1..n],i->Xlist[i]^(j-1)));
return TransposedMat(V);
end;

#
#Input: Xlist=[x1,..,xn], l = highest power,
#       L=[h_1,...,h_ell] is list of powers
#Output: Computes matrix described in Algor. 12.1.1 in [JH]
#
LocatorMat:=function(r,Xlist,L)
local a,j,b,ell;
ell:=Length(L);
a:=List([1..ell],j->DiagonalPower(r,(j-1))*VandermondeMat(Xlist,L[j]));
b:=List([1..ell],j->[1,j,a[j]]);
# return BlockMatrix(b,1,ell);
return (block_matrix([a]));
end;

#
# Compute kernel of matrix in alg 12.1.1 in [JH].
# Choose a basis vector in kernel.
# Construct the polynomial Q(x,y) in alg 12.1.1.
#
ErrorLocatorPair:=function(r,Xlist,L)
local a,j,b,q,e,Q,i,lengths,ker,ell;
ell:=Length(L);
e:=LocatorMat(r,Xlist,L);
ker:=NullspaceMat(TransposedMat(e));
if ker=[] then Print("Decoding fails.\n"); return []; fi;
q:=ker[1];
Q:=[];
lengths:=List([1..Length(L)],i->Sum(List([1..i],j->1+L[j])));
Q[1]:=List([1..lengths[1]],j->q[j]);
for i in [2..Length(L)] do
Q[i]:=List([(lengths[i-1]+1)..lengths[i]],j->q[j]);
od;
return Q;
end;

#
#Input: List coeffs of coefficients, R = F[x]
#Output: polynomial L[0]+L[1]x+...+L[d]x^d
#
CoefficientToPolynomial:=function(coeffs,R)
local p,i,j, lengths, F,xx;
xx:=IndeterminatesOfPolynomialRing(R)[1];
F:=Field(coeffs);
p:=Zero(F);
lengths:=List([1..Length(coeffs)],i->Sum(List([1..i],j->1+coeffs[j])));
for i in [1..Length(coeffs)] do
p:=p+coeffs[i]*xx^(i-1);
od;
return p;
end;

#
#Input: List L of coefficients ell, R = F[x]
#       Xlist=[x1,..,xn],
#Output: list of polynomials Qi as in Algor. 12.1.1 in [JH]
#
ErrorLocatorPolynomials:=function(r,Xlist,L,R)
local q,p,i,ell;
ell:=Length(L);
q:=ErrorLocatorPair(r,Xlist,L);
if q=[] then Print("Decoding fails.\n"); return []; fi;
p:=[];
for i in [1..Length(q)] do
p:=Concatenation([CoefficientToPolynomial(q[i],R)],p);
od;
return p;
end;

DecodewordGRS:=function(r,P,k,R)
local z,F,f,s,t,L,n,Qpolys,vars,x,c,y;
F:=CoefficientsRing(R);
vars:=IndeterminatesOfPolynomialRing(R);
x:=vars[1];y:=vars[2];
n:=Length(r);
t:=Int((n-k)/2);
L:=[n-1-t,n-t-k];
Qpolys:=ErrorLocatorPolynomials(r,P,L,R);
f:=-Qpolys[2]/Qpolys[1];
c:=List(Xlist,s->Int(Value(f,[x],[s])));
return Codeword(c,n,F);
end;


# Conjecture

There is a simiple relationship between finding the minimum weight codeword of a linear code and decoding a received word. Here is an illustration: Let denote a generator matrix of a linear code . Let denote a received word with error vector and codeword . Create the new code with generator matrix

The minimum weight codeword of this code is the error vector provided has less than non-zero coordinates. Therefore if you can compute the minimum weight codeword of then you can decode any received word for .

The following conjecture tries to reverse this idea and ask if the decoding algorithm for a cyclic code can help one determine the weight of a minimum weight codeword. If one could reverse this idea, this would have the advantage of speeding up the algorithm for determining the minimum weight codeword. (The decoding algorithm for the cyclic code is relatively fast compared to the algorithm for finding the minimum weight codeword.)

Conjecture 1

1. Input: is a cyclic code with generator polynomial of length over and a received word in . Assume we do not know the minimum distance of . Let denote an upper bound for the minimum distance.

Output: A good estimate for the minimum distance.

2. Let denote a small'' set of random codewords in . Let denote a corresponding set of received words, with each corresponding vectore having errors from the corresponding codeword. Compute the polynomials associated to the received words .

3. Apply algorithm 3 to try to correct the errors in the 's. If any failure occurs, replace by and go to step 2. If all are correct, then stop and return .

If this works, it's a polynomial time algorithm for estimating the minimum distance of a cyclic code.

## Bibliography

[GUA] GUAVA web page,

[HILL] R. Hill, A First Course In Coding Theory, Oxford University Press, 1986.

[HJ] T. Høholdt and J. Justesen, A Course In Error-Correcting Codes, European Math Society Publishing, 2004.

[LX] S. Ling and C. Xing, Coding Theory: A First Course, Cambridge University Press, 2004.

[MS] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-correcting Codes, North-Holland, 1983.