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.
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) |
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 .
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
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.
Cyclic codewords are conveniently represented as polynomials modulo . In fact, if then let
Denote by the ring of polynomials with coefficients in modulo :
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.
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 .
More generally we have the following result
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 .
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.
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:
First we show that an interpolating polynomial always exists.
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 .
Input: is a list of points in , is an integer.
Output: A codeword in close to or ``fail''.
Let and . Property (1) above gives equations
Compute using the previous step .
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 .
Input: is a cyclic code with generator polynomial of length over and a received word in .
Output: A codeword in close to or ``fail''.
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);
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])); Add(B0,row); 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; add_col_mat:=function(M,N) #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 Add(col,NT[j]); od; return MutableTransposedMat(col); end; add_row_mat:=function(M,N) #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 Add(row,N[j]); 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 A:=add_row_mat(A,L[i][1]); 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 A[j]:=add_col_mat(A[j],L[j][i]); od; od; B:=A[1]; for j in [2..m] do B:= add_row_mat(B,A[j]); 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 # r=[r1,...,rn] is received vector #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;
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 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.)
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.
If this works, it's a polynomial time algorithm for estimating the minimum distance of a cyclic code.
The command line arguments were:
latex2html -t 'J. McGowan Math Honors Thesis 2004-2005' -split 0 mcgowan_mathhonors2004-2005.tex
The translation was initiated by David Joyner on 2005-04-06