Error Correcting Codes

Mike May, S. J., 1998

When we say that an (m, n) cyclic code generated by is t-error correcting,

we mean that we have a polynomial of degree (m-n) over ,

such that the map taking to , where is the remainder

obtained after dividing by , takes distinct polynomials to polynomials that

differ in at least coefficients. (Note that to , is divisible by , since the characteristic is 2.) This is equivalent to claiming that

multiplication by is a map from polynomials of degree less than n

to polynomials of degree less than m, with the added property that any two

distinct polynomials and are taken to polynomials

and that differ in at least coefficients.

>

Verifying error correction

Since an (m, n) code has message, we could check that a code is t-error correcting

by checking the pairs of messages to see that the two members

of each pair differ from each other in at least coefficients.

The alternative is to note that this is

equivalent to checking that has at least

nonzero coefficeints for all polynomials of degree less than n.

We list three well chosen polynomials to explore with.

> p1 := x^3+x+1;
p2 := sort(expand((x^4+x+1)*(x^4+x^3+x^2+x+1)));
p3 := sort(expand((x^4+x+1)*(x^4+x^3+x^2+x+1)*(x^2+x+1)));

p1 is the generator of a single error correcting (7,4) code.

p2 is the generator of a double error correcting (15, 8) code.
p3 is the generator of a triple error correcting (15, 5) code.

We want some procedures for turning the binary representation of a number

into a polynomial over Z2.

> makepoly := proc(n,m)
# n should be less than 2^m
local i, tempn, tempp:
tempp := 0: tempn := n:
for i from 0 to m-1 do
tempp := tempp + irem(tempn,2)*x^i:
tempn:= iquo(tempn,2):
od:
sort(tempp):
end:

> makepoly(62,6);

For an t-error correcting (m,n) code generated by p, we need to check

that for any nonzero polynomial over Z2 of degree < (m-n),

the polynomial has at least 2t+1 nonzero terms.

> minlength := 7:
for i from 1 to 15 do
tpoly := makepoly(i,4):
q1 := sort(expand((p1*tpoly)) mod 2):
print(tpoly,q1,`length = `,subs(x=1,q1));
minlength := min(minlength,subs(x=1,q1)):
od:
minlength;

We would like a procedure that checks the minimum length of a

nonzero codeword.

> minlengthcheck := proc(m,n,p,x)
#This checks the minimal distance of an (m,n) code
#generated by p, a polynomial in x.
local minlength, tpoly, q,len1, i:
minlength := 2^n-1;
for i from 1 to (2^(n)-1) do
tpoly := makepoly(i,n):
q := sort(expand((p*tpoly)) mod 2):
len1 := subs(x=1,q):
if len1 < minlength then minlength := len1 fi:
od:
minlength;
end:

We can now verify the lengths of the codes generated by the three polynomials

given earlier.

> minlengthcheck(7,4,p1,x);
minlengthcheck(15,7,p2,x);
minlengthcheck(15,5,p3,x);

Cyclic generators.

It has been noted that we often want to list the nonzero elements of a field

in terms of a primitive element. If the generating polynomial is minp, an

nth degree polynomial in alpha, we want the remainder of divided by

minp, for i from 1 to .

> lister := proc(minp, alpha)
local i,n;
n := degree(minp, alpha):
for i from 1 to 2^n-1 do
print(alpha^i = Rem(alpha^i,minp,alpha) mod 2) od:
end:

> minp := alpha^3 + alpha^1 + 1;
lister(minp,alpha);

Producing the polynomials in error correcting codes

We also want to produce the polynomials used in error correcting codes. We first want to find an irreducible polynomial for an odd power of the primitive element we have described the field in terms of.

> fsubbeta := proc(d,minp, alpha)
local n, i, solset, sollist,f1, t1, t2:
n := degree(minp, alpha):
solset := {}:
for i from 0 to n-1 do
t1 := Rem(alpha^(d*2^i), minp, alpha) mod 2:
solset := solset union {t1}:
sollist[i+1] := t1:
od:
f1 := 1:
for i from 1 to nops(solset) do
f1 := f1*(x-sollist[i]) od:
sort(rem(f1,minp,alpha) mod 2);
end:

> minp := alpha^4+alpha+1:
for i from 1 to 3 do print(2*i-1, fsubbeta(2*i-1, minp, alpha)) od:
f1 := 1:
for i from 1 to 3 do f1 := f1*fsubbeta(2*i-1, minp, alpha) mod 2 od:
sort(expand(f1) mod 2);

>

Note that the polynomial for is only quadratic, thus we only need a 10th degree

polynomial for triple error correction.

Consider now the case for (31,x) codes.

> minp := alpha^5+alpha^2+1:
for i from 1 to 6 do print(2*i-1, listells(2*i-1, minp, alpha)) od:

Note that the polynomial for is the same as the polynomial for . Thus

the 20th degree polynomial obtained by taking the product of the first 4 polynomials

given produces a (31,11) code that is 5-error correcting rather than 4-error

correcting as we would suspect.

> minp := alpha^9+alpha+1: s1 := {}:
for i from 1 to 17 do
t1 := fsubbeta(2*i-1, minp, alpha):
print(2*i-1, degree(t1), t1):
s1 := s1 union {t1}:
od:
s1; nops(s1);
#for i from 1 to 3 do f1 := f1*fsubbeta(2*i-1, minp, alpha) mod 2 od:
#sort(expand(f1) mod 2);

>