Dr. Francisco J. Collazo

TECHNICAL DESCRIPTION OF THE GOLAY CODE:

GOLAY CODE: This code is used in several military digital data communication equipment.

REFERENCE: WEB SITE:http://is1.websearch.com/websrch.bar.inkto/search/inc/results/web/framed.htm?display-url=http%3A%2F%2Fwww.the-art-of-ecc.com%2F2_Short&qkw=Hamming+Algorithm&nextid=di3:1098595064118&frame=http%3A%2F%2Fclickit.go2net.com%2Fsearch%3Fpos%3D12%26ppos%3D4%26plnks%3D4%26uplnks%3D9%26cat%3Dweb%26cid%3D239170%26site%3Dsrch%26area%3Dsrch.noncomm.inktomi%26shape%3Dtextlink%26cp%3Dwebsrch.bar.inkto%26cluster-click%3D0%26pd%3D0%26coll%3D0%26query%3Dhamming%2Balgorithm%26rawto%3Dhttp%3A%2F%2Fwww.the-art-of-ecc.com%2F2_Short

Golay code: The following is a description of the Golay code that can correct up to three errors with a minimum distance of seven:

The binary (23,12,7) Golay code is an example of a perfect code, that is,

// the number of syndromes equals the number of correctable error patterns.

// The minimum distance is 7, so all error patterns of Hamming weight up to

// 3 can be corrected. The total number of these error patterns is:

// Number of errors Number of patterns

// ---------------- ------------------

// 0 1

// 1 23

// 2 253

// 3 1771

// ----

// Total number of error patterns = 2048 = 2^{11} = number of syndromes

// --

// number of redundant bits -------^

// Because of its relatively low length (23), dimension (12) and number of

// redundant bits (11), the binary (23,12,7) Golay code can be encoded and

// decoded simply by using look-up tables. The program below uses a 16K

// encoding table and an 8K decoding table.

// ------------------------------------------------------------------------

// This program is complementary material for the book:

// R.H. Morelos-Zaragoza, The Art of Error Correcting Coding, Wiley, 2002.

// ISBN 0471 49581 6

// This and other programs are available at http://the-art-of-ecc.com

// You may use this program for academic and personal purposes only.

// If this program is used to perform simulations whose results are

// published in a journal or book, please refer to the book above.

// The use of this program in a commercial product requires explicit

// written permission from the author. The author is not responsible or

// liable for damage or loss that may be caused by the use of this program.

// ------------------------------------------------------------------------

#include <stdio.h>

#define X22 0x00400000 /* vector representation of X^{22} */

#define X11 0x00000800 /* vector representation of X^{11} */

#define MASK12 0xfffff800 /* auxiliary vector for testing */

#define GENPOL 0x00000c75 /* generator polinomial, g(x) */

/* Global variables:

* pattern = error pattern, or information, or received vector

* encoding_table[] = encoding table

* decoding_table[] = decoding table

* data = information bits, i(x)

* codeword = code bits = x^{11}i(x) + (x^{11}i(x) mod g(x))

* numerr = number of errors = Hamming weight of error polynomial e(x)

* position[] = error positions in the vector representation of e(x)

* recd = representation of corrupted received polynomial r(x) = c(x) + e(x)

* decerror = number of decoding errors

* a[] = auxiliary array to generate correctable error patterns

long pattern;

long encoding_table[4096], decoding_table[2048];

long data, codeword, recd;

long position[23] = { 0x00000001, 0x00000002, 0x00000004, 0x00000008,

0x00000010, 0x00000020, 0x00000040, 0x00000080,

0x00000100, 0x00000200, 0x00000400, 0x00000800,

0x00001000, 0x00002000, 0x00004000, 0x00008000,

0x00010000, 0x00020000, 0x00040000, 0x00080000,

0x00100000, 0x00200000, 0x00400000 };

long numerr, errpos[23], decerror = 0;

int a[4];

long arr2int(a,r)

* Convert a binary vector of Hamming weight r, and nonzero positions in

* array a[1]...a[r], to a long integer \sum_{i=1}^r 2^{a[i]-1}.

int r;

int *a;

{

int i;

long mul, result = 0, temp;

for (i=1; i<=r; i++) {

mul = 1;

temp = a[i]-1;

while (temp--)

mul = mul << 1;

result += mul;

}

return(result);

}

void nextcomb(n, r, a)

* Calculate next r-combination of an n-set.

int n, r;

int *a;

{

int i, j;

a[r]++;

if (a[r] <= n)

return;

j = r - 1;

while (a[j] == n - r + j)

j--;

for (i = r; i >= j; i--)

a[i] = a[j] + i - j + 1;

return;

}

long get_syndrome(pattern)

* Compute the syndrome corresponding to the given pattern, i.e., the

* remainder after dividing the pattern (when considering it as the vector

* representation of a polynomial) by the generator polynomial, GENPOL.

* In the program this pattern has several meanings: (1) pattern = infomation

* bits, when constructing the encoding table; (2) pattern = error pattern,

* when constructing the decoding table; and (3) pattern = received vector, to

* obtain its syndrome in decoding.

long pattern;

{

long aux = X22, aux2;

if (pattern >= X11)

while (pattern & MASK12) {

while (!(aux & pattern))

aux = aux >> 1;

pattern ^= (aux/X11) * GENPOL;

}

return(pattern);

}

main()

{

long temp;

int seed = 133757;

* ---------------------------------------------------------------------

* Generate ENCODING TABLE

* An entry to the table is an information vector, a 32-bit integer,

* whose 12 least significant positions are the information bits. The

* resulting value is a codeword in the (23,12,7) Golay code: A 32-bit

* integer whose 23 least significant bits are coded bits: Of these, the

* 12 most significant bits are information bits and the 11 least

* significant bits are redundant bits (systematic encoding).

* ---------------------------------------------------------------------

for (pattern = 0; pattern < 4096; pattern++) {

temp = pattern << 11; /* multiply information by X^{11} */

encoding_table[pattern] = temp + get_syndrome(temp);/* add redundancy */

}

* ---------------------------------------------------------------------

* Generate DECODING TABLE

* An entry to the decoding table is a syndrome and the resulting value

* is the most likely error pattern. First an error pattern is generated.

* Then its syndrome is calculated and used as a pointer to the table

* where the error pattern value is stored.

* ---------------------------------------------------------------------

* (1) Error patterns of WEIGHT 1 (SINGLE ERRORS)

decoding_table[0] = 0;

decoding_table[1] = 1;

temp = 1;

for (i=2; i<= 23; i++) {

temp *= 2;