Golay Code Implementation – Encoding » History » Version 1
Version 1/13
-
Next » -
Current version
ABDALLAH, Hussein, 03/13/2016 12:13 PM
Golay Code Implementation – Encoding¶
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.
The characteristic polynomials for the Golay code are:
• X11 + X9 + X7 + X6 + X5 + X + 1, coefficients AE3h.
• X11 + X10 + X6 + X5 + X4 + X2 + 1, coefficients C75h.
These polynomials generate different checkbits. For our encoding algorithm we will use the first polynomial AE3h.
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).
Golay
polynomial info bits zero fill
|----------| |----------||---------|
AE3h 555h(reversed)______________________
101011100011 )10101010101000000000000 (11 zeros)
101011100011 (AE3h)
------------ <---------- Exclusive-OR
100100100000
101011100011
------------
111100001100
101011100011
------------
101111011110
101011100011
------------
100111101000
101011100011
------------
01100001011 <-- checkbits
So we have the 11-checkbits 01100001011, and then the bit-reversed remainder from the division 11010000110=686h.
After that, we put the codeword together for the transmission and we get 686555h which is called Systematic encodein (we can add a parity bit to the codeword to obtain an extended Golay).
The encoding algorithm is shown below. Long integers are used to conveniently store one codeword.
#define POLY 0xAE3 /* or use the other polynomial, 0xC75 */
unsigned long golay(unsigned long cw)
/* This function calculates [23,12] Golay codewords.
The format of the returned longint is
[checkbits(11),data(12)]. */
{
int i;
unsigned long c;
cw&=0xfffl;
c=cw; /* save original codeword /
for (i=1; i<=12; i++) / examine each data bit */
{
if (cw & 1) /* test data bit /
cw^=POLY; / XOR polynomial /
cw>>=1; / shift intermediate result /
}
return((cw<<12)|c); / assemble codeword /
}
The routine parity() adds the parity bit to complete the extended codeword. It is shown below.
int parity(unsigned long cw)
/ This function checks the overall parity of codeword cw.
If parity is even, 0 is returned, else 1. */
{
unsigned char p;
/* XOR the bytes of the codeword /
p=(unsigned char*)&cw;
p^=*((unsigned char*)&cw+1);
p^=*((unsigned char*)&cw+2);
/* XOR the halves of the intermediate result */
p=p ^ (p>>4);
p=p ^ (p>>2);
p=p ^ (p>>1);
/* return the parity result */
return(p & 1);
}