1 /*
2 * Copyright (c) 2007 - 2015 Joseph Gaeddert
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a copy
5 * of this software and associated documentation files (the "Software"), to deal
6 * in the Software without restriction, including without limitation the rights
7 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8 * copies of the Software, and to permit persons to whom the Software is
9 * furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice shall be included in
12 * all copies or substantial portions of the Software.
13 *
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
20 * THE SOFTWARE.
21 */
22
23 //
24 // 2/3-rate (12,8) Hamming code
25 //
26 // bit position 1 2 3 4 5 6 7 8 9 10 11 12
27 // encoded bits P1 P2 1 P4 2 3 4 P8 5 6 7 8
28 //
29 // parity bit P1 x . x . x . x . x . x .
30 // coveratge P2 . x x . . x x . . x x .
31 // P4 . . . x x x x . . . . x
32 // P8 . . . . . . . x x x x x
33
34 #include <stdio.h>
35 #include <stdlib.h>
36 #include <assert.h>
37
38 #include "liquid.internal.h"
39
40 #define DEBUG_FEC_HAMMING128 0 // debugging flag
41 #define FEC_HAMMING128_ENC_GENTAB 1 // use look-up table for encoding?
42
43 // parity bit coverage mask for encoder (collapsed version of figure
44 // above, stripping out parity bits P1, P2, P4, P8 and only including
45 // data bits 1:8)
46 //
47 // bit position 3 5 6 7 9 10 11 12
48 //
49 // parity bit P1 x x . x x . x . = 1101 1010
50 // coverage P2 x . x x . x x . = 1011 0110
51 // P4 . x x x . . . x = 0111 0001
52 // P8 . . . . x x x x = 0000 1111
53 #define HAMMING128_M1 0xda // 1101 1010
54 #define HAMMING128_M2 0xb6 // 1011 0110
55 #define HAMMING128_M4 0x71 // 0111 0001
56 #define HAMMING128_M8 0x0f // 0000 1111
57
58 // parity bit coverage mask for decoder; used to compute syndromes
59 // for decoding a received message (see first figure, above).
60 #define HAMMING128_S1 0x0aaa // .... 1010 1010 1010
61 #define HAMMING128_S2 0x0666 // .... 0110 0110 0110
62 #define HAMMING128_S4 0x01e1 // .... 0001 1110 0001
63 #define HAMMING128_S8 0x001f // .... 0000 0001 1111
64
fec_hamming128_encode_symbol(unsigned int _sym_dec)65 unsigned int fec_hamming128_encode_symbol(unsigned int _sym_dec)
66 {
67 // validate input
68 if (_sym_dec >= (1<<8)) {
69 fprintf(stderr,"error, fec_hamming128_encode(), input symbol too large\n");
70 exit(1);
71 }
72
73 // compute parity bits
74 unsigned int p1 = liquid_bdotprod_uint16(_sym_dec, HAMMING128_M1);
75 unsigned int p2 = liquid_bdotprod_uint16(_sym_dec, HAMMING128_M2);
76 unsigned int p4 = liquid_bdotprod_uint16(_sym_dec, HAMMING128_M4);
77 unsigned int p8 = liquid_bdotprod_uint16(_sym_dec, HAMMING128_M8);
78
79 #if DEBUG_FEC_HAMMING128
80 printf("parity bits (p1,p2,p4,p8) : (%1u,%1u,%1u,%1u)\n", p1, p2, p4, p8);
81 #endif
82
83 // encode symbol by inserting parity bits with data bits to
84 // make a 12-bit symbol
85 unsigned int sym_enc = ((_sym_dec & 0x000f) << 0) |
86 ((_sym_dec & 0x0070) << 1) |
87 ((_sym_dec & 0x0080) << 2) |
88 ( p1 << 11 ) |
89 ( p2 << 10 ) |
90 ( p4 << 8 ) |
91 ( p8 << 4 );
92
93 return sym_enc;
94 }
95
fec_hamming128_decode_symbol(unsigned int _sym_enc)96 unsigned int fec_hamming128_decode_symbol(unsigned int _sym_enc)
97 {
98 // validate input
99 if (_sym_enc >= (1<<12)) {
100 fprintf(stderr,"error, fec_hamming128_decode(), input symbol too large\n");
101 exit(1);
102 }
103
104 // compute syndrome bits
105 unsigned int s1 = liquid_bdotprod_uint16(_sym_enc, HAMMING128_S1);
106 unsigned int s2 = liquid_bdotprod_uint16(_sym_enc, HAMMING128_S2);
107 unsigned int s4 = liquid_bdotprod_uint16(_sym_enc, HAMMING128_S4);
108 unsigned int s8 = liquid_bdotprod_uint16(_sym_enc, HAMMING128_S8);
109
110 // index
111 unsigned int z = (s8<<3) | (s4<<2) | (s2<<1) | s1;
112
113 #if DEBUG_FEC_HAMMING128
114 printf("syndrome bits (s1,s2,s4,s8) : (%1u,%1u,%1u,%1u)\n", s1, s2, s4, s8);
115 printf("syndrome z : %u\n", z);
116 #endif
117
118 // flip bit at this position
119 if (z) {
120 if (z > 12) {
121 // if this happens there are likely too many errors
122 // to correct; just pass without trying to do anything
123 //fprintf(stderr,"warning, fec_hamming128_decode_symbol(), syndrome index exceeds 12\n");
124 } else {
125 //printf("error detected!\n");
126 _sym_enc ^= 1 << (12-z);
127 }
128 }
129
130 // strip data bits (x) from encoded symbol with parity bits (.)
131 // symbol: [..x. xxx. xxxx]
132 // 0000 0000 1111 > 0x000f
133 // 0000 1110 0000 > 0x00e0
134 // 0010 0000 0000 > 0x0200
135 unsigned int sym_dec = ((_sym_enc & 0x000f) ) |
136 ((_sym_enc & 0x00e0) >> 1) |
137 ((_sym_enc & 0x0200) >> 2);
138
139
140 return sym_dec;
141 }
142
143 // create Hamming(12,8) codec object
fec_hamming128_create(void * _opts)144 fec fec_hamming128_create(void * _opts)
145 {
146 fec q = (fec) malloc(sizeof(struct fec_s));
147
148 // set scheme
149 q->scheme = LIQUID_FEC_HAMMING128;
150 q->rate = fec_get_rate(q->scheme);
151
152 // set internal function pointers
153 q->encode_func = &fec_hamming128_encode;
154 q->decode_func = &fec_hamming128_decode;
155 q->decode_soft_func = &fec_hamming128_decode_soft;
156
157 return q;
158 }
159
160 // destroy Hamming(12,8) object
fec_hamming128_destroy(fec _q)161 void fec_hamming128_destroy(fec _q)
162 {
163 free(_q);
164 }
165
166 // encode block of data using Hamming(12,8) encoder
167 //
168 // _q : encoder/decoder object
169 // _dec_msg_len : decoded message length (number of bytes)
170 // _msg_dec : decoded message [size: 1 x _dec_msg_len]
171 // _msg_enc : encoded message [size: 1 x 2*_dec_msg_len]
fec_hamming128_encode(fec _q,unsigned int _dec_msg_len,unsigned char * _msg_dec,unsigned char * _msg_enc)172 void fec_hamming128_encode(fec _q,
173 unsigned int _dec_msg_len,
174 unsigned char *_msg_dec,
175 unsigned char *_msg_enc)
176 {
177 unsigned int i, j=0; // input/output symbol counters
178 unsigned char s0, s1; // input 8-bit symbols
179 unsigned int m0, m1; // output 12-bit symbols
180
181 // determine if input length is odd
182 unsigned int r = _dec_msg_len % 2;
183
184 for (i=0; i<_dec_msg_len-r; i+=2) {
185 // strip two input bytes
186 s0 = _msg_dec[i+0];
187 s1 = _msg_dec[i+1];
188
189 // encode each byte into 12-bit symbols
190 #if FEC_HAMMING128_ENC_GENTAB
191 m0 = hamming128_enc_gentab[s0];
192 m1 = hamming128_enc_gentab[s1];
193 #else
194 m0 = fec_hamming128_encode_symbol(s0);
195 m1 = fec_hamming128_encode_symbol(s1);
196 #endif
197
198 // append both 12-bit symbols to output (three 8-bit bytes),
199 // retaining order of bits in output
200 _msg_enc[j+0] = (m0 >> 4) & 0xff;
201 _msg_enc[j+1] = ((m0 << 4) & 0xf0) | ((m1 >> 8) & 0x0f);
202 _msg_enc[j+2] = (m1 ) & 0xff;
203
204 j += 3;
205 }
206
207 // if input length is even, encode last symbol by itself
208 if (r) {
209 // strip last input symbol
210 s0 = _msg_dec[_dec_msg_len-1];
211
212 // encode into 12-bit symbol
213 #if FEC_HAMMING128_ENC_GENTAB
214 m0 = hamming128_enc_gentab[s0];
215 #else
216 m0 = fec_hamming128_encode_symbol(s0);
217 #endif
218
219 // append to output
220 _msg_enc[j+0] = ( m0 & 0x0ff0 ) >> 4;
221 _msg_enc[j+1] = ( m0 & 0x000f ) << 4;
222
223 j += 2;
224 }
225
226 assert(j== fec_get_enc_msg_length(LIQUID_FEC_HAMMING128,_dec_msg_len));
227 }
228
229 // decode block of data using Hamming(12,8) decoder
230 //
231 // _q : encoder/decoder object
232 // _dec_msg_len : decoded message length (number of bytes)
233 // _msg_enc : encoded message [size: 1 x 2*_dec_msg_len]
234 // _msg_dec : decoded message [size: 1 x _dec_msg_len]
235 //
236 //unsigned int
fec_hamming128_decode(fec _q,unsigned int _dec_msg_len,unsigned char * _msg_enc,unsigned char * _msg_dec)237 void fec_hamming128_decode(fec _q,
238 unsigned int _dec_msg_len,
239 unsigned char *_msg_enc,
240 unsigned char *_msg_dec)
241 {
242 unsigned int i=0,j=0;
243 unsigned int r = _dec_msg_len % 2;
244 unsigned char r0, r1, r2;
245 unsigned int m0, m1;
246
247 for (i=0; i<_dec_msg_len-r; i+=2) {
248 // strip three input symbols
249 r0 = _msg_enc[j+0];
250 r1 = _msg_enc[j+1];
251 r2 = _msg_enc[j+2];
252
253 // combine three 8-bit symbols into two 12-bit symbols
254 m0 = ((r0 << 4) & 0x0ff0) | ((r1 >> 4) & 0x000f);
255 m1 = ((r1 << 8) & 0x0f00) | ((r2 ) & 0x00ff);
256
257 // decode each symbol into an 8-bit byte
258 _msg_dec[i+0] = fec_hamming128_decode_symbol(m0);
259 _msg_dec[i+1] = fec_hamming128_decode_symbol(m1);
260
261 j += 3;
262 }
263
264 // if input length is even, decode last symbol by itself
265 if (r) {
266 // strip last two input bytes (last byte should only contain
267 // for bits)
268 r0 = _msg_enc[j+0];
269 r1 = _msg_enc[j+1];
270
271 // pack into 12-bit symbol
272 m0 = ((r0 << 4) & 0x0ff0) | ((r1 >> 4) & 0x000f);
273
274 // decode symbol into an 8-bit byte
275 _msg_dec[i++] = fec_hamming128_decode_symbol(m0);
276
277 j += 2;
278 }
279
280 assert(j== fec_get_enc_msg_length(LIQUID_FEC_HAMMING128,_dec_msg_len));
281
282 //return num_errors;
283 }
284
285
286 // decode block of data using Hamming(12,8) soft decoder
287 //
288 // _q : encoder/decoder object
289 // _dec_msg_len : decoded message length (number of bytes)
290 // _msg_enc : encoded message [size: 8*_enc_msg_len x 1]
291 // _msg_dec : decoded message [size: _dec_msg_len x 1]
292 //
293 //unsigned int
fec_hamming128_decode_soft(fec _q,unsigned int _dec_msg_len,unsigned char * _msg_enc,unsigned char * _msg_dec)294 void fec_hamming128_decode_soft(fec _q,
295 unsigned int _dec_msg_len,
296 unsigned char *_msg_enc,
297 unsigned char *_msg_dec)
298 {
299 unsigned int i;
300 unsigned int k=0; // array bit index
301 unsigned int r = _dec_msg_len % 2;
302
303 // compute encoded message length
304 unsigned int enc_msg_len = (3*_dec_msg_len)/2 + r;
305
306 unsigned char s; // decoded 8-bit symbol
307
308 //unsigned char num_errors=0;
309 for (i=0; i<_dec_msg_len; i++) {
310 #if 0
311 // use true ML soft decoding: about 1.45 dB improvement in Eb/N_0 for a BER of 10^-5
312 // with a decoding complexity of 1.43M cycles/trial (64-byte block)
313 s = fecsoft_hamming128_decode(&_msg_enc[k]);
314 #else
315 // use n-3 nearest neighbors: about 0.54 dB improvement in Eb/N_0 for a BER of 10^-5
316 // with a decoding complexity of 124k cycles/trial (64-byte block)
317 s = fecsoft_hamming128_decode_n3(&_msg_enc[k]);
318 #endif
319 k += 12;
320
321 _msg_dec[i] = (unsigned char)(s & 0xff);
322
323 //printf(" %3u : 0x%.2x > 0x%.2x, 0x%.2x > 0x%.2x (k=%u)\n", i, r0, s0, r1, s1, k);
324 }
325 k += r*4; // for assert method
326 assert(k == 8*enc_msg_len);
327 //return num_errors;
328 }
329
330 //
331 // internal methods
332 //
333
334 // soft decoding of one symbol
335 // NOTE : because this method compares the received symbol to every
336 // possible (256) encoded symbols, it is painfully slow to
337 // run.
fecsoft_hamming128_decode(unsigned char * _soft_bits)338 unsigned int fecsoft_hamming128_decode(unsigned char * _soft_bits)
339 {
340 // find symbol with minimum distance from all 2^8 possible
341 unsigned int d; // distance metric
342 unsigned int dmin = 0; // minimum distance
343 unsigned int s_hat = 0; // estimated transmitted symbol
344 unsigned int c; // encoded symbol
345
346 unsigned int s;
347 for (s=0; s<256; s++) {
348 // encode symbol
349 #if FEC_HAMMING128_ENC_GENTAB
350 c = hamming128_enc_gentab[s];
351 #else
352 c = fec_hamming128_encode_symbol(s);
353 #endif
354
355 // compute distance metric
356 d = 0;
357 d += (c & 0x0800) ? 255 - _soft_bits[ 0] : _soft_bits[ 0];
358 d += (c & 0x0400) ? 255 - _soft_bits[ 1] : _soft_bits[ 1];
359 d += (c & 0x0200) ? 255 - _soft_bits[ 2] : _soft_bits[ 2];
360 d += (c & 0x0100) ? 255 - _soft_bits[ 3] : _soft_bits[ 3];
361 d += (c & 0x0080) ? 255 - _soft_bits[ 4] : _soft_bits[ 4];
362 d += (c & 0x0040) ? 255 - _soft_bits[ 5] : _soft_bits[ 5];
363 d += (c & 0x0020) ? 255 - _soft_bits[ 6] : _soft_bits[ 6];
364 d += (c & 0x0010) ? 255 - _soft_bits[ 7] : _soft_bits[ 7];
365 d += (c & 0x0008) ? 255 - _soft_bits[ 8] : _soft_bits[ 8];
366 d += (c & 0x0004) ? 255 - _soft_bits[ 9] : _soft_bits[ 9];
367 d += (c & 0x0002) ? 255 - _soft_bits[10] : _soft_bits[10];
368 d += (c & 0x0001) ? 255 - _soft_bits[11] : _soft_bits[11];
369
370 if (d < dmin || s==0) {
371 s_hat = s;
372 dmin = d;
373 }
374 }
375 return s_hat;
376 }
377
378 // soft decoding of one symbol using nearest neighbors
fecsoft_hamming128_decode_n3(unsigned char * _soft_bits)379 unsigned int fecsoft_hamming128_decode_n3(unsigned char * _soft_bits)
380 {
381 // find symbol with minimum distance from 17 nearest neighbors
382 unsigned int d; // distance metric
383 unsigned int dmin = 0; // minimum distance
384 unsigned int s_hat = 0; // estimated transmitted symbol
385 unsigned int c; // encoded symbol
386
387 // compute hard-decoded symbol
388 c = 0x0000;
389 c |= (_soft_bits[ 0] > 127) ? 0x0800 : 0;
390 c |= (_soft_bits[ 1] > 127) ? 0x0400 : 0;
391 c |= (_soft_bits[ 2] > 127) ? 0x0200 : 0;
392 c |= (_soft_bits[ 3] > 127) ? 0x0100 : 0;
393 c |= (_soft_bits[ 4] > 127) ? 0x0080 : 0;
394 c |= (_soft_bits[ 5] > 127) ? 0x0040 : 0;
395 c |= (_soft_bits[ 6] > 127) ? 0x0020 : 0;
396 c |= (_soft_bits[ 7] > 127) ? 0x0010 : 0;
397 c |= (_soft_bits[ 8] > 127) ? 0x0008 : 0;
398 c |= (_soft_bits[ 9] > 127) ? 0x0004 : 0;
399 c |= (_soft_bits[10] > 127) ? 0x0002 : 0;
400 c |= (_soft_bits[11] > 127) ? 0x0001 : 0;
401
402 // decode symbol
403 s_hat = fec_hamming128_decode_symbol(c);
404
405 // re-encode and compute distance
406 #if FEC_HAMMING128_ENC_GENTAB
407 c = hamming128_enc_gentab[s_hat];
408 #else
409 c = fec_hamming128_encode_symbol(s_hat);
410 #endif
411
412 // compute distance metric
413 d = 0;
414 d += (c & 0x0800) ? 255 - _soft_bits[ 0] : _soft_bits[ 0];
415 d += (c & 0x0400) ? 255 - _soft_bits[ 1] : _soft_bits[ 1];
416 d += (c & 0x0200) ? 255 - _soft_bits[ 2] : _soft_bits[ 2];
417 d += (c & 0x0100) ? 255 - _soft_bits[ 3] : _soft_bits[ 3];
418 d += (c & 0x0080) ? 255 - _soft_bits[ 4] : _soft_bits[ 4];
419 d += (c & 0x0040) ? 255 - _soft_bits[ 5] : _soft_bits[ 5];
420 d += (c & 0x0020) ? 255 - _soft_bits[ 6] : _soft_bits[ 6];
421 d += (c & 0x0010) ? 255 - _soft_bits[ 7] : _soft_bits[ 7];
422 d += (c & 0x0008) ? 255 - _soft_bits[ 8] : _soft_bits[ 8];
423 d += (c & 0x0004) ? 255 - _soft_bits[ 9] : _soft_bits[ 9];
424 d += (c & 0x0002) ? 255 - _soft_bits[10] : _soft_bits[10];
425 d += (c & 0x0001) ? 255 - _soft_bits[11] : _soft_bits[11];
426
427 dmin = d;
428
429 // search over 17 nearest neighbors
430 unsigned int s;
431 unsigned int i;
432 for (i=0; i<17; i++) {
433 // use look-up table for nearest neighbors
434 s = fecsoft_hamming128_n3[s_hat][i];
435
436 // encode symbol
437 #if FEC_HAMMING128_ENC_GENTAB
438 c = hamming128_enc_gentab[s];
439 #else
440 c = fec_hamming128_encode_symbol(s);
441 #endif
442
443 // compute distance metric
444 d = 0;
445 d += (c & 0x0800) ? 255 - _soft_bits[ 0] : _soft_bits[ 0];
446 d += (c & 0x0400) ? 255 - _soft_bits[ 1] : _soft_bits[ 1];
447 d += (c & 0x0200) ? 255 - _soft_bits[ 2] : _soft_bits[ 2];
448 d += (c & 0x0100) ? 255 - _soft_bits[ 3] : _soft_bits[ 3];
449 d += (c & 0x0080) ? 255 - _soft_bits[ 4] : _soft_bits[ 4];
450 d += (c & 0x0040) ? 255 - _soft_bits[ 5] : _soft_bits[ 5];
451 d += (c & 0x0020) ? 255 - _soft_bits[ 6] : _soft_bits[ 6];
452 d += (c & 0x0010) ? 255 - _soft_bits[ 7] : _soft_bits[ 7];
453 d += (c & 0x0008) ? 255 - _soft_bits[ 8] : _soft_bits[ 8];
454 d += (c & 0x0004) ? 255 - _soft_bits[ 9] : _soft_bits[ 9];
455 d += (c & 0x0002) ? 255 - _soft_bits[10] : _soft_bits[10];
456 d += (c & 0x0001) ? 255 - _soft_bits[11] : _soft_bits[11];
457
458 if (d < dmin) {
459 s_hat = s;
460 dmin = d;
461 }
462 }
463
464 return s_hat;
465 }
466
467