summaryrefslogtreecommitdiffstats
path: root/epan/golay.c
blob: 0751a12fcd30a7212c7aa7eb0a6376e6fe129507 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
/*
 * Provides routines for encoding and decoding the extended Golay
 * (24,12,8) code.
 *
 * This implementation will detect up to 4 errors in a codeword (without
 * being able to correct them); it will correct up to 3 errors.
 *
 * Wireshark - Network traffic analyzer
 * By Gerald Combs <gerald@wireshark.org>
 * Copyright 1998 Gerald Combs
 *
 * SPDX-License-Identifier: GPL-2.0-or-later
 */

#include <glib.h>
#include "golay.h"


/* Encoding matrix, H

   These entries are formed from the matrix specified in H.223/B.3.2.1.3;
   it's first transposed so we have:

   [P1 ]   [111110010010]  [MC1 ]
   [P2 ]   [011111001001]  [MC2 ]
   [P3 ]   [110001110110]  [MC3 ]
   [P4 ]   [011000111011]  [MC4 ]
   [P5 ]   [110010001111]  [MPL1]
   [P6 ] = [100111010101]  [MPL2]
   [P7 ]   [101101111000]  [MPL3]
   [P8 ]   [010110111100]  [MPL4]
   [P9 ]   [001011011110]  [MPL5]
   [P10]   [000101101111]  [MPL6]
   [P11]   [111100100101]  [MPL7]
   [P12]   [101011100011]  [MPL8]

   So according to the equation, P1 = MC1+MC2+MC3+MC4+MPL1+MPL4+MPL7

   Looking down the first column, we see that if MC1 is set, we toggle bits
   1,3,5,6,7,11,12 of the parity: in binary, 110001110101 = 0xE3A

   Similarly, to calculate the inverse, we read across the top of the table and
   see that P1 is affected by bits MC1,MC2,MC3,MC4,MPL1,MPL4,MPL7: in binary,
   111110010010 = 0x49F.

   I've seen cunning implementations of this which only use one table. That
   technique doesn't seem to work with these numbers though.
*/

static const guint golay_encode_matrix[12] = {
    0xC75,
    0x49F,
    0xD4B,
    0x6E3,
    0x9B3,
    0xB66,
    0xECC,
    0x1ED,
    0x3DA,
    0x7B4,
    0xB1D,
    0xE3A,
};

static const guint golay_decode_matrix[12] = {
    0x49F,
    0x93E,
    0x6E3,
    0xDC6,
    0xF13,
    0xAB9,
    0x1ED,
    0x3DA,
    0x7B4,
    0xF68,
    0xA4F,
    0xC75,
};



/* Function to compute the Hamming weight of a 12-bit integer */
static guint weight12(guint vector)
{
    guint w=0;
    guint i;
    for( i=0; i<12; i++ )
        if( vector & 1<<i )
            w++;
    return w;
}

/* returns the golay coding of the given 12-bit word */
static guint golay_coding(guint w)
{
    guint out=0;
    guint i;

    for( i = 0; i<12; i++ ) {
        if( w & 1<<i )
            out ^= golay_encode_matrix[i];
    }
    return out;
}

/* encodes a 12-bit word to a 24-bit codeword */
guint32 golay_encode(guint w)
{
    return ((guint32)w) | ((guint32)golay_coding(w))<<12;
}



/* returns the golay coding of the given 12-bit word */
static guint golay_decoding(guint w)
{
    guint out=0;
    guint i;

    for( i = 0; i<12; i++ ) {
        if( w & 1<<(i) )
            out ^= golay_decode_matrix[i];
    }
    return out;
}


/* return a mask showing the bits which are in error in a received
 * 24-bit codeword, or -1 if 4 errors were detected.
 */
gint32 golay_errors(guint32 codeword)
{
    guint received_data, received_parity;
    guint syndrome;
    guint w,i;
    guint inv_syndrome = 0;

    received_parity = (guint)(codeword>>12);
    received_data   = (guint)codeword & 0xfff;

    /* We use the C notation ^ for XOR to represent addition modulo 2.
     *
     * Model the received codeword (r) as the transmitted codeword (u)
     * plus an error vector (e).
     *
     *   r = e ^ u
     *
     * Then we calculate a syndrome (s):
     *
     *   s = r * H, where H = [ P   ], where I12 is the identity matrix
     *                        [ I12 ]
     *
     * (In other words, we calculate the parity check for the received
     * data bits, and add them to the received parity bits)
     */

    syndrome = received_parity ^ (golay_coding(received_data));
    w = weight12(syndrome);

    /*
     * The properties of the golay code are such that the Hamming distance (ie,
     * the minimum distance between codewords) is 8; that means that one bit of
     * error in the data bits will cause 7 errors in the parity bits.
     *
     * In particular, if we find 3 or fewer errors in the parity bits, either:
     *  - there are no errors in the data bits, or
     *  - there are at least 5 errors in the data bits
     * we hope for the former (we don't profess to deal with the
     * latter).
     */
    if( w <= 3 ) {
        return ((gint32) syndrome)<<12;
    }

    /* the next thing to try is one error in the data bits.
     * we try each bit in turn and see if an error in that bit would have given
     * us anything like the parity bits we got. At this point, we tolerate two
     * errors in the parity bits, but three or more errors would give a total
     * error weight of 4 or more, which means it's actually uncorrectable or
     * closer to another codeword. */

    for( i = 0; i<12; i++ ) {
        guint error = 1<<i;
        guint coding_error = golay_encode_matrix[i];
        if( weight12(syndrome^coding_error) <= 2 ) {
            return (gint32)((((guint32)(syndrome^coding_error))<<12) | (guint32)error) ;
        }
    }

    /* okay then, let's see whether the parity bits are error free, and all the
     * errors are in the data bits. model this as follows:
     *
     * [r | pr] = [u | pu] + [e | 0]
     *
     * pr = pu
     * pu = H * u => u = H' * pu = H' * pr , where H' is inverse of H
     *
     * we already have s = H*r + pr, so pr = s - H*r = s ^ H*r
     * e = u ^ r
     *   = (H' * ( s ^ H*r )) ^ r
     *   = H'*s ^ r ^ r
     *   = H'*s
     *
     * Once again, we accept up to three error bits...
     */

    inv_syndrome = golay_decoding(syndrome);
    w = weight12(inv_syndrome);
    if( w <=3 ) {
        return (gint32)inv_syndrome;
    }

    /* Final shot: try with 2 errors in the data bits, and 1 in the parity
     * bits; as before we try each of the bits in the parity in turn */
    for( i = 0; i<12; i++ ) {
        guint error = 1<<i;
        guint coding_error = golay_decode_matrix[i];
        if( weight12(inv_syndrome^coding_error) <= 2 ) {
            guint32 error_word = ((guint32)(inv_syndrome^coding_error)) | ((guint32)error)<<12;
            return (gint32)error_word;
        }
    }

    /* uncorrectable error */
    return -1;
}



/* decode a received codeword. Up to 3 errors are corrected for; 4
   errors are detected as uncorrectable (return -1); 5 or more errors
   cause an incorrect correction.
*/
gint golay_decode(guint32 w)
{
    guint data = (guint)w & 0xfff;
    gint32 errors = golay_errors(w);
    guint data_errors;

    if( errors == -1 )
        return -1;
    data_errors = (guint)errors & 0xfff;
    return (gint)(data ^ data_errors);
}

/*
 * Editor modelines
 *
 * Local Variables:
 * c-basic-offset: 4
 * tab-width: 8
 * indent-tabs-mode: nil
 * End:
 *
 * ex: set shiftwidth=4 tabstop=8 expandtab:
 * :indentSize=4:tabSize=8:noTabs=true:
 */