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