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  *
13  */
15 #include <glib.h>
16 #include "golay.h"
19 /* Encoding matrix, H
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:
24    [P1 ]     [MC1 ]
25    [P2 ]     [MC2 ]
26    [P3 ]     [MC3 ]
27    [P4 ]     [MC4 ]
28    [P5 ]     [MPL1]
29    [P6 ] =   [MPL2]
30    [P7 ]     [MPL3]
31    [P8 ]     [MPL4]
32    [P9 ]     [MPL5]
33    [P10]     [MPL6]
34    [P11]     [MPL7]
35    [P12]     [MPL8]
37    So according to the equation, P1 = MC1+MC2+MC3+MC4+MPL1+MPL4+MPL7
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
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.
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 */
50 static const guint golay_encode_matrix = {
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 };
65 static const guint golay_decode_matrix = {
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 };
82 /* Function to compute the Hamming weight of a 12-bit integer */
83 static guint weight12(guint vector)
84 {
85     guint w=0;
86     guint i;
87     for( i=0; i<12; i++ )
88         if( vector & 1<<i )
89             w++;
90     return w;
91 }
93 /* returns the golay coding of the given 12-bit word */
94 static guint golay_coding(guint w)
95 {
96     guint out=0;
97     guint i;
99     for( i = 0; i<12; i++ ) {
100         if( w & 1<<i )
101             out ^= golay_encode_matrix[i];
102     }
103     return out;
104 }
106 /* encodes a 12-bit word to a 24-bit codeword */
107 guint32 golay_encode(guint w)
108 {
109     return ((guint32)w) | ((guint32)golay_coding(w))<<12;
110 }
114 /* returns the golay coding of the given 12-bit word */
115 static guint golay_decoding(guint w)
116 {
117     guint out=0;
118     guint i;
120     for( i = 0; i<12; i++ ) {
121         if( w & 1<<(i) )
122             out ^= golay_decode_matrix[i];
123     }
124     return out;
125 }
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 gint32 golay_errors(guint32 codeword)
132 {
134     guint syndrome;
135     guint w,i;
136     guint inv_syndrome = 0;
139     received_data   = (guint)codeword & 0xfff;
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      */
158     w = weight12(syndrome);
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 ((gint32) syndrome)<<12;
173     }
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. */
182     for( i = 0; i<12; i++ ) {
183         guint error = 1<<i;
184         guint coding_error = golay_encode_matrix[i];
185         if( weight12(syndrome^coding_error) <= 2 ) {
186             return (gint32)((((guint32)(syndrome^coding_error))<<12) | (guint32)error) ;
187         }
188     }
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      */
207     inv_syndrome = golay_decoding(syndrome);
208     w = weight12(inv_syndrome);
209     if( w <=3 ) {
210         return (gint32)inv_syndrome;
211     }
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         guint error = 1<<i;
217         guint coding_error = golay_decode_matrix[i];
218         if( weight12(inv_syndrome^coding_error) <= 2 ) {
219             guint32 error_word = ((guint32)(inv_syndrome^coding_error)) | ((guint32)error)<<12;
220             return (gint32)error_word;
221         }
222     }
224     /* uncorrectable error */
225     return -1;
226 }
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 gint golay_decode(guint32 w)
235 {
236     guint data = (guint)w & 0xfff;
237     gint32 errors = golay_errors(w);
238     guint data_errors;
240     if( errors == -1 )
241         return -1;
242     data_errors = (guint)errors & 0xfff;
243     return (gint)(data ^ data_errors);
244 }
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  */