Golay Code Implementation – Detecting Errors¶
It is easy to detect errors in a codeword.
• Using the parity bit to check for odd numbers of errors
If parity is correct
• Computing the 23-bit syndrome of the codeword and check for zeros.
The syndrome is the reminder left after the codeword is divided by the polynomial, modulo-2. It is equal to zero if the Golay code is valid, else non-zero.
A hand computation example is shown below using the previous 686555h, bit reversed for the division process.
101011100011 10101010101001100001011 ( AE3h then 555h then checkbits)
101011100011 (checkbits)
------------ <---------- Exclusive-OR
100100101100
101011100011
------------
111100111100
101011100011
------------
101110111111
101011100011
------------
101011100011
101011100011
------------
000000000000 <-- syndrome = 0The routine in the next listing does the same sort of calculation.
unsigned long syndrome(unsigned long cw)
/* This function calculates and returns the syndrome
of a [23,12] Golay codeword. */
{
int i;
cw&=0x7fffffl;
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); / value pairs with upper bits of cw */
}
These routines are all you need to implement a Golay error detection scheme. As above, you can detect up to 6 bit errors per codeword and, with the parity bit, all odd numbers of errors.