/* File:    golay23.c * Title:   Encoder/decoder for a binary (23,12,7) Golay code * Author:  Robert Morelos-Zaragoza (robert@spectra.eng.hawaii.edu) * Date:    August 1994 * * 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. *  * For more information, suggestions, or other ideas on implementing error * correcting codes, please contact me at (I'm temporarily in Japan, but * below is my U.S. address): * *                    Robert Morelos-Zaragoza *                    770 S. Post Oak Ln. #200 *                      Houston, Texas 77056 * *             email: robert@spectra.eng.hawaii.edu * *       Homework: Add an overall parity-check bit to get the (24,12,8) *                 extended Golay code. * * COPYRIGHT NOTICE: This computer program is free for non-commercial purposes. * You may implement this program for any non-commercial application. You may  * also implement this program for commercial purposes, provided that you * obtain my written permission. Any modification of this program is covered * by this copyright. * * ==   Copyright (c) 1994  Robert Morelos-Zaragoza. All rights reserved.   == */#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(){   register int i,j;   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;        decoding_table[get_syndrome(temp)] = temp;        }   /*                * (2) Error patterns of WEIGHT 2 (DOUBLE ERRORS)    */    a[1] = 1; a[2] = 2;    temp = arr2int(a,2);    decoding_table[get_syndrome(temp)] = temp;    for (i=1; i<253; i++) {        nextcomb(23,2,a);        temp = arr2int(a,2);        decoding_table[get_syndrome(temp)] = temp;        }   /*                * (3) Error patterns of WEIGHT 3 (TRIPLE ERRORS)    */    a[1] = 1; a[2] = 2; a[3] = 3;    temp = arr2int(a,3);    decoding_table[get_syndrome(temp)] = temp;    for (i=1; i<1771; i++) {        nextcomb(23,3,a);        temp = arr2int(a,3);        decoding_table[get_syndrome(temp)] = temp;        }   /* ---------------------------------------------------------------------    *                        Generate DATA    * ---------------------------------------------------------------------    */    srandom(seed);    /*     * data = 12 information bits, an information polynomial i(x)     */    data = random() & 0x00000fff;    printf("data =            %#012x\n", data);   /*    * ---------------------------------------------------------------------    *                         ENCODING    * ---------------------------------------------------------------------    */    codeword = encoding_table[data];    printf("codeword =        %#012x\n", codeword);   /*    * ---------------------------------------------------------------------    *                          ERRORS    * ---------------------------------------------------------------------    */    printf("Enter the number of errors and their positions (0...22): ");    scanf("%d", &numerr);    for (i = 0; i < numerr; i++)        scanf("%d", &errpos[i]);   /*    * ---------------------------------------------------------------------    *                      RECEIVED VECTOR    * ---------------------------------------------------------------------    */    recd = codeword;    if (numerr)        for (i = 0; i < numerr; i++)            recd ^= position[errpos[i]];    printf("received vector = %#012x\n", recd);   /*    * ---------------------------------------------------------------------    *                         DECODING    * ---------------------------------------------------------------------    */    printf("syndrome =        %#012x\n", get_syndrome(recd));    printf("error pattern =   %#012x\n", decoding_table[get_syndrome(recd)]);   /*    * Calculate the syndrome, look up the corresponding error pattern and    * add it to the received vector.    */    recd ^= decoding_table[get_syndrome(recd)];    printf("decoded vector =  %#012x\n", recd);    printf("recovered data =  %#012x\n", (recd>>11));    printf("original data  =  %#012x\n", data);   /*    * DECODING ERRORS? Only the data portion is compared. Note that this    * is only possible in a simulation!    */    pattern = (recd ^ codeword) >> 11;    for (i=0; i<12; i++)       if (pattern&position[i])          decerror++;    printf("there were %d decoding errors\n", decerror);}