Extended (24, 12) Binary Golay Code: Encoding and Decoding Procedures 

© Czeslaw Koscielny 2006

Academy of Management in Legnica, Legnica, Poland,
Faculty of Computer Science,
Wroclaw University of Applied Informatics, Wroclaw, Poland 

e mail: c.koscielny@wsm.edu.pl
              
 

Abstract 

It has been shown in the worksheet how to implement encoding and decoding of triple error correcting (24, 12) binary Golay code. The worksheet proves that Maple is an excellent (but underestimated)  tool for teaching error-correcting codes. 

 

1. Introduction 

    The extended (24, 12) binary Golay code [1] considered in this submission can correct three or fewer errors. Due to the 11 x 11 matrix Bc,  having a cyclic structure and being a component of both the generator and the parity check matrices of this code, its decoding procedure is very simple. Therefore, the discussed (24, 12) code was used about 25 years ago in the spacecraft Voyager. As it is known, this spacecraft delivered to the Earth many perfect photographs of Jupiter and Saturn. 

 

2. Generator and Parity Check Matrices of (24, 12) Golay Code 

    Let 

 

be the 11 x 11 matrix over GF(2), where 

 

, 

 

 

 

. 

 

The (24, 12) Golay code has the following generator and parity check matrices, correspondingly: 

 

,   ,  

where I - identity matrix 12 x 12,  

 

 

 

and  

 

.  

Therefore 

 

 

 

 

 

 

 

 

It can be seen that ,  ,  

 

3. Encoding and Decoding of (24, 12) Golay Code 

    As in the case of any linear code, to generate a code vector it suffices to multiply the vector i, containing 12 information symbols  

 

i = [ 

by the G matrix: 

 

 

wherefrom 

 

 

 

The decoding algorithm of the extended Golay code, shown below, consists in determining the error pattern u = v + w, where w denotes the vector received and v  the nearest to w code vector. In the content of the algorithm  wt(x)  denotes the weight of the vector x, (i.e. the number of "ones" contained in x), i-th row of the matrix B, the word of length 12   with 1 in the i-th  position  and 0 elsewhere. After determining u we assume that the corrected received vector will be v = w + u.  Here are the steps of the algorithm [1]: 

 

           Step 1. Compute the syndrome  

           Step 2. If u = [s, 000000000000]. 

           Step 3. If  then u = []. 

           Step 4. Compute the second syndrome  

           Step 5. If then u = [000000000000, ].
           Step 6. If    then u = [].
           Step 7. If u is not yet determined then request retransmission. 

4. Maple Approach to the Extended Golay Code 

   The Maple implementation of encoding and decoding procedures of the discussed code, i.e. C24E and C24D together with matrices B, G, H and are contained in the file golay.m. The next section presents how to make use of this file. 

 

5. Example 

    The worksheet allow the user to experiment with (24, 12) Golay code. To do it one ought to read the file golay.m: 

>	read "golay.m";

 

 

We can now see the matrices B, G, H and and the Maple code of procedures  C24E and C24D:  

 

>	B := evalm(B); G := evalm(G); H := evalm(H); Ht := evalm(Ht);

 

>	showstat(C24E);

 

>	showstat(C24D);

 

 

Let the information symbols be: 

 

>	i := [1,0,1,0,1,0,0,1,1,0,0,0]:

 

 

then the code vector containing these information bits is the following: 

 

>	v := C24E(i);

 

 

Assuming the error vector 

 

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

 

 

we can compute the received vector  in the considered case. 

 

>	w := [seq(0, i = 1 .. 24)]: for i to 24 do w[i] := (v[i] + u[i]) mod 2 end do: w;

 

 

Here is the result of decoding of the received vector: 

 

>	vc := C24D(w);

 

 

The result is quite correct. If error pattern contains five (or any odd number) errors 

 

>	u := [1,0,1,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,1,0,0,0]: w := [seq(0, i = 1 .. 24)]: for i to 24 do w[i] := (v[i] + u[i]) mod 2 end do: w;

 

 

then the received vector is transformed into the code vector and errors are not detected: 

 

>	vc := C24D(w);

 

 

In the case if error vector contains six (or any even number) errors 

 

>	u := [1,0,1,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,1,0,0,1]: w := [seq(0, i = 1 .. 24)]: for i to 24 do w[i] := (v[i] + u[i]) mod 2 end do: w;

 

 

then decoding procedure can be able to detect errors: 

 

>	vc := C24D(w);

 

Bibliography 

[1] D. R. Hankerson, D. G. Hoffman, D. A. Leonard, C. C. Lindner: CODING THEORY AND CRYPTOGRAPHY -THE ESSENTIALS, Second Editiion, Revised and Expanded, Marcel Dekker Inc., 2000 

 

Legal Notice: The copyright for this application is owned by the author(s). Neither Maplesoft nor the author are responsible for any errors contained within and are not liable for any damages resulting from the use of this material. This application is intended for non-commercial, non-profit use only. Contact the author for permission if you wish to use this application in for-profit activities.