golay.mws

Decoding with the Golay Codes

In this worksheet we program the decoding algorithm for the Golay and extended Golay codes. The extended Golay code is the linear code whose generator matrix is the 12 by 24 matrix [I | B], where B is the 12 by 12 matrix defined below. This code has distance 8, and so it will correct up to three errors. We verify this with the Distance command; this will take some time, so be patient. The Golay code has distance 7, which we also verify with the Distance command.

The procedure
FindErrorPattern programs Algorithm 3.6.1. The procedure DecodeEGolay then uses it to decode with the extended Golay code. To use it, enter DecodeEGolay(v) , where v is either a string or a list. To decode with the Golay code, enter DecodeGolay(v) . This procedure encodes Algorithm 3.7.1 with the help of FindErrorPattern.

To help work examples with this code, we define a procedure called change . This procedure allows you to take a list and change any of its entries. For example, if you want to change the 2nd, 5th, and 7th entries of the vector v = [1,0,0,0,1,1,0,1,1] , you would enter

change(v,[2,5,7]);

at a Maple prompt, provided v is defined in memory. The second input of the command is a list of which components to change.

To use this worksheet, you must first open and load into memory the commands in the worksheet CodingProcedures.mws .

> B:=mat(["110111000101","101110001011","011100010111","111000101101","110001011011","100010110111","000101101111","001011011101","010110111001","101101110001","011011100011","111111111110"]);

> I12:=matrix(12,12,(i,j)->1-ceil(abs(i-j)/12));

> G:=augment(I12,B);

> H:=evalm(G):

> Distance(H);

`The Hamming distance of the code is 8`

cut

> cut := proc(ww) local w:
if type(ww,string) = false then w := ww else w := MakeList(ww): fi:
ShortPrint(ShrinkVector([op(1..12,w)])):
printf(","):
ShortPrint(ShrinkVector([op(13..nops(w),w)])):
end:

change

> change := proc(v,l) local i,m,n,w,II:
w := convert(v,list):
m := nops(w):
n := nops(convert(l,list)):
II := matrix(m,m,(i,j)->1-ceil(abs(i-j)/m)):
for i from 1 to n do
w := evalm(w + row(II,l[i])):
od:
map(`mod`,w,2):
end:

FindErrorPattern

> FindErrorPattern := proc(ww) local i,s,s2,t,u,v,w,zero,test:
if type(ww,string) = true then
w := MakeList(ww)
else
w := convert(ww,list)
fi:
zero := vector(12,0):
test := 0:
s := convert(map(`mod`,evalm(H&*w),2),list):
if wt(s) <= 3 then
u := MakeList(cat(ShrinkVector(s),ShrinkVector(zero))):
test := 1:
else
for i from 1 to 12 do
t := convert(map(`mod`,evalm(s+col(B,i)),2),list):
if wt(t) <= 2 then
u:= MakeList(cat(ShrinkVector(t),ShrinkVector(row(I12,i)))):
test := 1:
break:
fi:
od:
fi:
if test = 0 then
s2 := convert(map(`mod`,evalm(B&*s),2),list):
if wt(s2) <= 3 then
u :=MakeList(cat(ShrinkVector(zero),ShrinkVector(s2))):
test := 1:
fi:
for i from 1 to 12 do
t := convert(map(`mod`,evalm(s2+col(B,i)),2),list):
if wt(t) <= 2 then
u:= MakeList(cat(ShrinkVector(row(I12,i)),ShrinkVector(t))):
test := 1:
break:
fi:
od:
fi:
if test = 0 then
u:=999:
else
u:
fi:
end:

DecodeEGolay

> DecodeEGolay := proc(ww) local u,v,w:
if type(ww,string) = true then
w := MakeList(ww)
else
w := convert(ww,list)
fi:
u := FindErrorPattern(w):
if u = 999 then
printf("The word %A cannot be decoded",ShrinkVector(w)):
else
v:=map(`mod`,w+u,2):
printf("original word\n"):
cut(w):
printf("\n decoded word\n"):
#cut([op(1..23,v)]):
cut(v):
printf("\n error pattern\n"):
#cut([op(1..23,u)]):
cut(u):
fi:
end:

DecodeGolay

> DecodeGolay := proc(ww) local u,v,w:
if type(ww,string) = true then
w := MakeList(ww)
else
w := convert(ww,list)
fi:
if wt(w) mod 2 = 1 then w:=[op(w),0] else w:=[op(w),1] fi:
u := FindErrorPattern(w):
if u = 999 then
printf("The word %A cannot be decoded",ShrinkVector([op(1..23,w)])):
else
v:=map(`mod`,w+u,2):
printf("original word\n"):
cut([op(1..23,w)]):
printf("\n decoded word\n"):
cut([op(1..23,v)]):
printf("\n error pattern\n"):
cut([op(1..23,u)]):
fi:
end:

Example 3.6.2

> w:=[1,0,1,1,1,1,1,0,1,1,1,1,0,1,0,0,1,0,0,1,0,0,1,0];

> DecodeEGolay(w);

`original word`

`101111101111,010010010010`

` decoded word`

`001111101110,010010010010`

` error pattern`

`100000000001,000000000000`

Example 3.6.3

> w:="001001001101101000101000";

> DecodeEGolay(w);

`original word`

`001001001101,101000101000`

` decoded word`

`001001011111,101010101000`

` error pattern`

`000000010010,000010000000`

Example 3.6.4

> w:="000111000111011011010000";

> DecodeEGolay(w);

`original word`

`000111000111,011011010000`

` decoded word`

`000011000111,011010000000`

` error pattern`

`000100000000,000001010000`

If you make more than three errors, then the decoding algorithm will either give you the incorrect codeword or will not return any codeword. In the next two examples we start with the zero vector and make 4 and 5 changes, respectively, to get w1 and w2. The word w1 does not get decoded, while the word w2 gets decoded, but incorrectly.

> v := vector(24,0);

> w1 := change(v,[1,2,3,4]);

> DecodeEGolay(w1);

`The word 111100000000000000000000 cannot be decoded`

> w2 := change(v,[2,8,7,5,4]);

> DecodeEGolay(w2);

`original word`

`010110110000,000000000000`

` decoded word`

`010110111001,000000001000`

` error pattern`

`000000001001,000000001000`

The Golay code is obtained from the extended Golay code by removing the last column of G and using the resulting 12 x 23 matrix as a generator matrix. This code has distance 7.

> G2 := delcols(G,24..24);

> H2 := ParityCheck(G2):

> Distance(H2);

`The Hamming distance of the code is 7`

We now give some examples of decoding with the Golay code. The first is the word from Example 3.7.2.

> w := "00100100100111111110000";

> DecodeGolay(w);

`original word`

`001001001001,11111110000`

` decoded word`

`001001000000,11111010000`

` error pattern`

`000000001001,00000100000`

> DecodeGolay("01100100100101101101111");

`original word`

`011001001001,01101101111`

` decoded word`

`011000001001,01101101101`

` error pattern`

`000001000000,00000000010`

> v:=vector(23,0);

> w3:=change(v,[1,2,3]);

> DecodeGolay(w3);

`original word`

`111000000000,00000000000`

` decoded word`

`000000000000,00000000000`

` error pattern`

`111000000000,00000000000`

> w4:=change(v,[3,7,18]);

> DecodeGolay(w4);

`original word`

`001000100000,00000100000`

` decoded word`

`000000000000,00000000000`

` error pattern`

`001000100000,00000100000`

The Golay code corrects 3 errors, and is "perfect", meaning that every word is within a distance 3 of a codeword. Thus, given any received word, the Golay code will return a decoded codeword. This is different than the extended Golay code, which may not return anything.

> w5:=change(v,[1,2,3,4]);

> DecodeGolay(w5);

`original word`

`111100000000,00000000000`

` decoded word`

`111100000100,01000000010`

` error pattern`

`000000000100,01000000010`

>

>