Golay Code Implementation – Detecting Errors » History » Version 3
Version 2 (ABDALLAH, Hussein, 03/13/2016 12:30 PM) → Version 3/14 (ABDALLAH, Hussein, 03/13/2016 12:31 PM)
h1. 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 zero
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.
AE3h _555h checkbits
101011100011 )10101010101001100001011 10101010101001100001011
101011100011 (checkbits)
------------ <---------- Exclusive-OR
100100101100
101011100011
------------
111100111100
101011100011
------------
101110111111
101011100011
------------
101011100011
101011100011
------------
000000000000 <-- syndrome = 0
The 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.
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 zero
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.
AE3h _555h checkbits
101011100011 )10101010101001100001011 10101010101001100001011
101011100011 (checkbits)
------------ <---------- Exclusive-OR
100100101100
101011100011
------------
111100111100
101011100011
------------
101110111111
101011100011
------------
101011100011
101011100011
------------
000000000000 <-- syndrome = 0
The 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.