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"]);

B := matrix([[1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1], ...

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

I12 := matrix([[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]...

> G:=augment(I12,B);

G := matrix([[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1...

> 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];

w := [1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, ...

> DecodeEGolay(w);

original word

101111101111,010010010010

 decoded word

001111101110,010010010010

 error pattern

100000000001,000000000000

Example 3.6.3

> w:="001001001101101000101000";

w :=

> DecodeEGolay(w);

original word

001001001101,101000101000

 decoded word

001001011111,101010101000

 error pattern

000000010010,000010000000

Example 3.6.4

> w:="000111000111011011010000";

w :=

> 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);

v := vector([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,...

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

w1 := vector([1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0...

> DecodeEGolay(w1);

The word 111100000000000000000000 cannot be decoded

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

w2 := vector([0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0...

> 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);

G2 := matrix([[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...

> 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";

w :=

> 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);

v := vector([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,...

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

w3 := vector([1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0...

> DecodeGolay(w3);

original word

111000000000,00000000000

 decoded word

000000000000,00000000000

 error pattern

111000000000,00000000000

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

w4 := vector([0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0...

> 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]);

w5 := vector([1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0...

> DecodeGolay(w5);

original word

111100000000,00000000000

 decoded word

111100000100,01000000010

 error pattern

000000000100,01000000010

>

>