epan/golay.c

   1 /* $Id$
   2  *
   3  * Provides routines for encoding and decoding the extended Golay
   4  * (24,12,8) code.
   5  *
   6  * This implementation will detect up to 4 errors in a codeword (without
   7  * being able to correct them); it will correct up to 3 errors.
   8  *
   9  * Wireshark - Network traffic analyzer
  10  * By Gerald Combs <gerald@wireshark.org>
  11  * Copyright 1998 Gerald Combs
  12  *
  13  * This program is free software; you can redistribute it and/or
  14  * modify it under the terms of the GNU General Public License
  15  * as published by the Free Software Foundation; either version 2
  16  * of the License, or (at your option) any later version.
  17  *
  18  * This program is distributed in the hope that it will be useful,
  19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21  * GNU General Public License for more details.
  22  *
  23  * You should have received a copy of the GNU General Public License
  24  * along with this program; if not, write to the Free Software
  25  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  26  */
  27
  28 #include <glib.h>
  29 #include "golay.h"
  30
  31
  32 /* Encoding matrix, H
  33
  34    These entries are formed from the matrix specified in H.223/B.3.2.1.3;
  35    it's first transposed so we have:
  36
  37    [P1 ]   [111110010010]  [MC1 ]
  38    [P2 ]   [011111001001]  [MC2 ]
  39    [P3 ]   [110001110110]  [MC3 ]
  40    [P4 ]   [011000111011]  [MC4 ]
  41    [P5 ]   [110010001111]  [MPL1]
  42    [P6 ] = [100111010101]  [MPL2]
  43    [P7 ]   [101101111000]  [MPL3]
  44    [P8 ]   [010110111100]  [MPL4]
  45    [P9 ]   [001011011110]  [MPL5]
  46    [P10]   [000101101111]  [MPL6]
  47    [P11]   [111100100101]  [MPL7]
  48    [P12]   [101011100011]  [MPL8]
  49
  50    So according to the equation, P1 = MC1+MC2+MC3+MC4+MPL1+MPL4+MPL7
  51
  52    Looking down the first column, we see that if MC1 is set, we toggle bits
  53    1,3,5,6,7,11,12 of the parity: in binary, 110001110101 = 0xE3A
  54
  55    Similarly, to calculate the inverse, we read across the top of the table and
  56    see that P1 is affected by bits MC1,MC2,MC3,MC4,MPL1,MPL4,MPL7: in binary,
  57    111110010010 = 0x49F.
  58
  59    I've seen cunning implementations of this which only use one table. That
  60    technique doesn't seem to work with these numbers though.
  61 */
  62
  63 static const guint golay_encode_matrix[12] = {
  64     0xC75,
  65     0x49F,
  66     0xD4B,
  67     0x6E3,
  68     0x9B3,
  69     0xB66,
  70     0xECC,
  71     0x1ED,
  72     0x3DA,
  73     0x7B4,
  74     0xB1D,
  75     0xE3A,
  76 };
  77
  78 static const guint golay_decode_matrix[12] = {
  79    0x49F,
  80    0x93E,
  81    0x6E3,
  82    0xDC6,
  83    0xF13,
  84    0xAB9,
  85    0x1ED,
  86    0x3DA,
  87    0x7B4,
  88    0xF68,
  89    0xA4F,
  90    0xC75,
  91 };
  92
  93
  94
  95 /* Function to compute the Hamming weight of a 12-bit integer */
  96 static guint weight12(guint vector)
  97 {
  98     guint w=0;
  99     guint i;
 100     for( i=0; i<12; i++ )
 101         if( vector & 1<<i )
 102             w++;
 103     return w;
 104 }
 105
 106 /* returns the golay coding of the given 12-bit word */
 107 static guint golay_coding(guint w)
 108 {
 109     guint out=0;
 110     guint i;
 111
 112     for( i = 0; i<12; i++ ) {
 113         if( w & 1<<i )
 114             out ^= golay_encode_matrix[i];
 115     }
 116     return out;
 117 }
 118
 119 /* encodes a 12-bit word to a 24-bit codeword */
 120 guint32 golay_encode(guint w)
 121 {
 122     return ((guint32)w) | ((guint32)golay_coding(w))<<12;
 123 }
 124
 125
 126
 127 /* returns the golay coding of the given 12-bit word */
 128 static guint golay_decoding(guint w)
 129 {
 130     guint out=0;
 131     guint i;
 132
 133     for( i = 0; i<12; i++ ) {
 134         if( w & 1<<(i) )
 135             out ^= golay_decode_matrix[i];
 136     }
 137     return out;
 138 }
 139
 140
 141 /* return a mask showing the bits which are in error in a received
 142  * 24-bit codeword, or -1 if 4 errors were detected.
 143  */
 144 gint32 golay_errors(guint32 codeword)
 145 {
 146     guint received_data, received_parity;
 147     guint syndrome;
 148     guint w,i;
 149     guint inv_syndrome = 0;
 150
 151     received_parity = (guint)(codeword>>12);
 152     received_data   = (guint)codeword & 0xfff;
 153
 154     /* We use the C notation ^ for XOR to represent addition modulo 2.
 155      *
 156      * Model the received codeword (r) as the transmitted codeword (u)
 157      * plus an error vector (e).
 158      *
 159      *   r = e ^ u
 160      *
 161      * Then we calculate a syndrome (s):
 162      *
 163      *   s = r * H, where H = [ P   ], where I12 is the identity matrix
 164      *                        [ I12 ]
 165      *
 166      * (In other words, we calculate the parity check for the received
 167      * data bits, and add them to the received parity bits)
 168      */
 169
 170     syndrome = received_parity ^ (golay_coding(received_data));
 171     w = weight12(syndrome);
 172
 173     /*
 174      * The properties of the golay code are such that the Hamming distance (ie,
 175      * the minimum distance between codewords) is 8; that means that one bit of
 176      * error in the data bits will cause 7 errors in the parity bits.
 177      *
 178      * In particular, if we find 3 or fewer errors in the parity bits, either:
 179      *  - there are no errors in the data bits, or
 180      *  - there are at least 5 errors in the data bits
 181      * we hope for the former (we don't profess to deal with the
 182      * latter).
 183      */
 184     if( w <= 3 ) {
 185         return ((gint32) syndrome)<<12;
 186     }
 187
 188     /* the next thing to try is one error in the data bits.
 189      * we try each bit in turn and see if an error in that bit would have given
 190      * us anything like the parity bits we got. At this point, we tolerate two
 191      * errors in the parity bits, but three or more errors would give a total
 192      * error weight of 4 or more, which means it's actually uncorrectable or
 193      * closer to another codeword. */
 194
 195     for( i = 0; i<12; i++ ) {
 196         guint error = 1<<i;
 197         guint coding_error = golay_encode_matrix[i];
 198         if( weight12(syndrome^coding_error) <= 2 ) {
 199             return (gint32)((((guint32)(syndrome^coding_error))<<12) | (guint32)error) ;
 200         }
 201     }
 202
 203     /* okay then, let's see whether the parity bits are error free, and all the
 204      * errors are in the data bits. model this as follows:
 205      *
 206      * [r | pr] = [u | pu] + [e | 0]
 207      *
 208      * pr = pu
 209      * pu = H * u => u = H' * pu = H' * pr , where H' is inverse of H
 210      *
 211      * we already have s = H*r + pr, so pr = s - H*r = s ^ H*r
 212      * e = u ^ r
 213      *   = (H' * ( s ^ H*r )) ^ r
 214      *   = H'*s ^ r ^ r
 215      *   = H'*s
 216      *
 217      * Once again, we accept up to three error bits...
 218      */
 219
 220     inv_syndrome = golay_decoding(syndrome);
 221     w = weight12(inv_syndrome);
 222     if( w <=3 ) {
 223         return (gint32)inv_syndrome;
 224     }
 225
 226     /* Final shot: try with 2 errors in the data bits, and 1 in the parity
 227      * bits; as before we try each of the bits in the parity in turn */
 228     for( i = 0; i<12; i++ ) {
 229         guint error = 1<<i;
 230         guint coding_error = golay_decode_matrix[i];
 231         if( weight12(inv_syndrome^coding_error) <= 2 ) {
 232             guint32 error_word = ((guint32)(inv_syndrome^coding_error)) | ((guint32)error)<<12;
 233             return (gint32)error_word;
 234         }
 235     }
 236
 237     /* uncorrectable error */
 238     return -1;
 239 }
 240
 241
 242
 243 /* decode a received codeword. Up to 3 errors are corrected for; 4
 244    errors are detected as uncorrectable (return -1); 5 or more errors
 245    cause an incorrect correction.
 246 */
 247 gint golay_decode(guint32 w)
 248 {
 249     guint data = (guint)w & 0xfff;
 250     gint32 errors = golay_errors(w);
 251     guint data_errors;
 252
 253     if( errors == -1 )
 254         return -1;
 255     data_errors = (guint)errors & 0xfff;
 256     return (gint)(data ^ data_errors);
 257 }