epan/golay.c

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