Golay Code Implementation – Encoding » History » Version 13

ABDALLAH, Hussein, 03/17/2016 09:42 PM

1 1 ABDALLAH, Hussein
h1. Golay Code Implementation – Encoding
2 1 ABDALLAH, Hussein
3 1 ABDALLAH, Hussein
The Golay code is encoded using modulo-2 division. Taking into account that the information bits are 12 per codeword, we must encode each 12-bit as one codeword.
4 1 ABDALLAH, Hussein
 The characteristic polynomials for the Golay code are:
5 1 ABDALLAH, Hussein
6 1 ABDALLAH, Hussein
•	X11 + X9 + X7 + X6 + X5 + X + 1, coefficients AE3h.
7 1 ABDALLAH, Hussein
•	X11 + X10 + X6 + X5 + X4 + X2 + 1, coefficients C75h.
8 1 ABDALLAH, Hussein
9 1 ABDALLAH, Hussein
These polynomials generate different checkbits. For our encoding algorithm we will use the first polynomial AE3h.
10 1 ABDALLAH, Hussein
Below, there is an example illustrating by hand the module-2 division process using exclusive-OR (XOR). The data is 555h. To generate 11 check-bit, we append 11 zero onto the bit-reversed data (LSB first). 
11 3 ABDALLAH, Hussein
                                               
12 3 ABDALLAH, Hussein
      Golay polynomial    info bits   zero fill                        
13 4 ABDALLAH, Hussein
          |----------|  |----------||---------|                       
14 2 ABDALLAH, Hussein
      AE3h            _555h(reversed)                      
15 5 ABDALLAH, Hussein
     101011100011  10101010101000000000000   (11 zeros)                    
16 1 ABDALLAH, Hussein
                   101011100011  (AE3h)                                
17 1 ABDALLAH, Hussein
                   ------------ <---------- Exclusive-OR         
18 1 ABDALLAH, Hussein
                        100100100000                             
19 1 ABDALLAH, Hussein
                        101011100011                             
20 1 ABDALLAH, Hussein
                        ------------                             
21 1 ABDALLAH, Hussein
                          111100001100                           
22 1 ABDALLAH, Hussein
                          101011100011                           
23 1 ABDALLAH, Hussein
                          ------------                           
24 1 ABDALLAH, Hussein
                           101111011110                          
25 1 ABDALLAH, Hussein
                           101011100011                          
26 1 ABDALLAH, Hussein
                           ------------                          
27 1 ABDALLAH, Hussein
                              100111101000                       
28 1 ABDALLAH, Hussein
                              101011100011                       
29 1 ABDALLAH, Hussein
                              ------------                       
30 1 ABDALLAH, Hussein
                               01100001011 <-- checkbits   
31 1 ABDALLAH, Hussein
      
32 1 ABDALLAH, Hussein
So we have the 11-checkbits 01100001011, and then the bit-reversed remainder from the division 11010000110=686h. 
33 12 ABDALLAH, Hussein
After that, we put the codeword together for the transmission and we get 686555h which is called Systematic encoding (we can add a parity bit to the codeword to obtain an extended Golay).
34 9 ABDALLAH, Hussein
35 1 ABDALLAH, Hussein
The encoding algorithm is shown below. Long integers are used to conveniently store one codeword.
36 9 ABDALLAH, Hussein
37 1 ABDALLAH, Hussein
#define POLY  0xAE3  /* or use the other polynomial, 0xC75 */
38 1 ABDALLAH, Hussein
39 1 ABDALLAH, Hussein
unsigned long golay(unsigned long cw) 
40 1 ABDALLAH, Hussein
41 6 ABDALLAH, Hussein
  /* This function calculates [23,12] Golay codewords. 
42 6 ABDALLAH, Hussein
     The format of the returned longint is 
43 6 ABDALLAH, Hussein
     [checkbits(11),data(12)]. */ 
44 1 ABDALLAH, Hussein
45 8 ABDALLAH, Hussein
{ 
46 8 ABDALLAH, Hussein
  int i; 
47 8 ABDALLAH, Hussein
  unsigned long c; 
48 8 ABDALLAH, Hussein
  cw&=0xfffl; 
49 8 ABDALLAH, Hussein
  c=cw; /* save original codeword */ 
50 8 ABDALLAH, Hussein
  for (i=1; i<=12; i++)  /* examine each data bit */ 
51 8 ABDALLAH, Hussein
    { 
52 8 ABDALLAH, Hussein
      if (cw & 1)        /* test data bit */ 
53 8 ABDALLAH, Hussein
        cw^=POLY;        /* XOR polynomial */ 
54 8 ABDALLAH, Hussein
      cw>>=1;            /* shift intermediate result */
55 8 ABDALLAH, Hussein
    } 
56 8 ABDALLAH, Hussein
  return((cw<<12)|c);    /* assemble codeword */ 
57 8 ABDALLAH, Hussein
} 
58 10 ABDALLAH, Hussein
59 1 ABDALLAH, Hussein
The routine parity() adds the parity bit to complete the extended codeword. It is shown below.
60 10 ABDALLAH, Hussein
61 1 ABDALLAH, Hussein
int parity(unsigned long cw) 
62 11 ABDALLAH, Hussein
  /* This function checks the overall parity of codeword cw.
63 1 ABDALLAH, Hussein
   If parity is even, 0 is returned, else 1. */ 
64 11 ABDALLAH, Hussein
65 1 ABDALLAH, Hussein
{ 
66 1 ABDALLAH, Hussein
  unsigned char p; 
67 1 ABDALLAH, Hussein
68 1 ABDALLAH, Hussein
  /* XOR the bytes of the codeword */ 
69 1 ABDALLAH, Hussein
  p=*(unsigned char*)&cw; 
70 1 ABDALLAH, Hussein
  p^=*((unsigned char*)&cw+1); 
71 1 ABDALLAH, Hussein
  p^=*((unsigned char*)&cw+2); 
72 1 ABDALLAH, Hussein
73 1 ABDALLAH, Hussein
  /* XOR the halves of the intermediate result */ 
74 1 ABDALLAH, Hussein
  p=p ^ (p>>4); 
75 1 ABDALLAH, Hussein
  p=p ^ (p>>2); 
76 1 ABDALLAH, Hussein
  p=p ^ (p>>1); 
77 1 ABDALLAH, Hussein
78 1 ABDALLAH, Hussein
  /* return the parity result */ 
79 1 ABDALLAH, Hussein
  return(p & 1); 
80 1 ABDALLAH, Hussein
} 
81 13 ABDALLAH, Hussein
82 13 ABDALLAH, Hussein
83 13 ABDALLAH, Hussein
*References*
84 13 ABDALLAH, Hussein
85 13 ABDALLAH, Hussein
http://aqdi.com/articles/using-the-golay-error-detection-and-correction-code-3/