Golay Code Implementation – Detecting Errors » History » Version 13
ABDALLAH, Hussein, 03/13/2016 12:35 PM
| 1 | 1 | ABDALLAH, Hussein | h1. Golay Code Implementation – Detecting Errors |
|---|---|---|---|
| 2 | 10 | ABDALLAH, Hussein | |
| 3 | 9 | ABDALLAH, Hussein | It is easy to detect errors in a codeword. |
| 4 | 9 | ABDALLAH, Hussein | • Using the parity bit to check for odd numbers of errors |
| 5 | 9 | ABDALLAH, Hussein | If parity is correct |
| 6 | 9 | ABDALLAH, Hussein | • Computing the 23-bit syndrome of the codeword and check for zero |
| 7 | 9 | ABDALLAH, Hussein | 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. |
| 8 | 9 | ABDALLAH, Hussein | A hand computation example is shown below using the previous 686555h, bit reversed for the division process. |
| 9 | 1 | ABDALLAH, Hussein | |
| 10 | 8 | ABDALLAH, Hussein | |
| 11 | 8 | ABDALLAH, Hussein | 101011100011 10101010101001100001011 ( AE3h then 555h then checkbits) |
| 12 | 1 | ABDALLAH, Hussein | 101011100011 (checkbits) |
| 13 | 1 | ABDALLAH, Hussein | ------------ <---------- Exclusive-OR |
| 14 | 1 | ABDALLAH, Hussein | 100100101100 |
| 15 | 1 | ABDALLAH, Hussein | 101011100011 |
| 16 | 1 | ABDALLAH, Hussein | ------------ |
| 17 | 1 | ABDALLAH, Hussein | 111100111100 |
| 18 | 1 | ABDALLAH, Hussein | 101011100011 |
| 19 | 1 | ABDALLAH, Hussein | ------------ |
| 20 | 1 | ABDALLAH, Hussein | 101110111111 |
| 21 | 1 | ABDALLAH, Hussein | 101011100011 |
| 22 | 1 | ABDALLAH, Hussein | ------------ |
| 23 | 1 | ABDALLAH, Hussein | 101011100011 |
| 24 | 1 | ABDALLAH, Hussein | 101011100011 |
| 25 | 1 | ABDALLAH, Hussein | ------------ |
| 26 | 3 | ABDALLAH, Hussein | 000000000000 <-- syndrome = 0 |
| 27 | 11 | ABDALLAH, Hussein | |
| 28 | 11 | ABDALLAH, Hussein | The routine in the next listing does the same sort of calculation. |
| 29 | 11 | ABDALLAH, Hussein | unsigned long syndrome(unsigned long cw) |
| 30 | 12 | ABDALLAH, Hussein | |
| 31 | 12 | ABDALLAH, Hussein | /* This function calculates and returns the syndrome |
| 32 | 12 | ABDALLAH, Hussein | of a [23,12] Golay codeword. */ |
| 33 | 13 | ABDALLAH, Hussein | |
| 34 | 13 | ABDALLAH, Hussein | { |
| 35 | 13 | ABDALLAH, Hussein | int i; |
| 36 | 13 | ABDALLAH, Hussein | cw&=0x7fffffl; |
| 37 | 13 | ABDALLAH, Hussein | for (i=1; i<=12; i++) /* examine each data bit */ |
| 38 | 13 | ABDALLAH, Hussein | { |
| 39 | 13 | ABDALLAH, Hussein | if (cw & 1) /* test data bit */ |
| 40 | 13 | ABDALLAH, Hussein | cw^=POLY; /* XOR polynomial */ |
| 41 | 13 | ABDALLAH, Hussein | cw>>=1; /* shift intermediate result */ |
| 42 | 13 | ABDALLAH, Hussein | } |
| 43 | 13 | ABDALLAH, Hussein | return(cw<<12); /* value pairs with upper bits of cw */ |
| 44 | 13 | ABDALLAH, Hussein | } |
| 45 | 13 | ABDALLAH, Hussein | 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. |