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 // Hamming code parity check matrix
25 //
26 // bit position 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
27 // encoded bits P1 P2 1 P4 2 3 4 P8 5 6 7 8 9 10 11 P16 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 P32 27 28 29 30 31 32
28 //
29 // parity bit P1 x . x . x . x . x . x . x . x . x . x . x . x . x . x . x . x .
30 // coverage P2 . x x . . x x . . x x . . x x . . x x . . x x . . x x . . x x .
31 // P4 . . . x x x x . . . . x x x x . . . . x x x x . . . . x x x x .
32 // P8 . . . . . . . x x x x x x x x . . . . . . . . x x x x x x x x .
33 // P16 . . . . . . . . . . . . . . . x x x x x x x x x x x x x x x x .
34 // P32 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x
35
36 #include <stdio.h>
37 #include <stdlib.h>
38 #include <assert.h>
39
40 #include "liquid.internal.h"
41
42 #define DEBUG_FEC_HAMMING 1
43
44 #if 0
45
46 //
47 // (12,8) Hamming code
48 //
49 // parity bit coverage mask for encoder (collapsed version of figure
50 // above, stripping out parity bits P1, P2, P4, P8 and only including
51 // data bits 1:8)
52 //
53 // bit position 3 5 6 7 9 10 11 12
54 //
55 // parity bit P1 x x . x x . x . = 1101 1010
56 // coverage P2 x . x x . x x . = 1011 0110
57 // P4 . x x x . . . x = 0111 0001
58 // P8 . . . . x x x x = 0000 1111
59 #define HAMMING_M1 0xda // 1101 1010
60 #define HAMMING_M2 0xb6 // 1011 0110
61 #define HAMMING_M4 0x71 // 0111 0001
62 #define HAMMING_M8 0x0f // 0000 1111
63
64 // parity bit coverage mask for decoder; used to compute syndromes
65 // for decoding a received message (see first figure, above).
66 #define HAMMING_S1 0x0aaa // .... 1010 1010 1010
67 #define HAMMING_S2 0x0666 // .... 0110 0110 0110
68 #define HAMMING_S4 0x01e1 // .... 0001 1110 0001
69 #define HAMMING_S8 0x001f // .... 0000 0001 1111
70
71 #endif
72
73
74 #if 0
75 //
76 // (15,11) Hamming code
77 //
78 // parity bit coverage mask for encoder (collapsed version of figure
79 // above, stripping out parity bits P1, P2, P4, P8 and only including
80 // data bits 1:11)
81 //
82 // parity bit P1 x x . x x . x . x . x = .110 1101 0101
83 // coverage P2 x . x x . x x . . x x = .101 1011 0011
84 // P4 . x x x . . . x x x x = .011 1000 1111
85 // P8 . . . . x x x x x x x = .000 0111 1111
86
87 #define HAMMING_M1 0x0d65 // .110 1101 0101
88 #define HAMMING_M2 0x05b3 // .101 1011 0011
89 #define HAMMING_M4 0x038f // .011 1000 1111
90 #define HAMMING_M8 0x007f // .000 0111 1111
91
92 // parity bit coverage mask for decoder; used to compute syndromes
93 // for decoding a received message (see first figure, above).
94 #define HAMMING_S1 0x5555 // .101 0101 0101 0101
95 #define HAMMING_S2 0x3333 // .011 0011 0011 0011
96 #define HAMMING_S4 0x0f0f // .000 1111 0000 1111
97 #define HAMMING_S8 0x00ff // .000 0000 1111 1111
98 #endif
99
100 //
101 // (31,26) Hamming code
102 //
103 // parity bit coverage mask for encoder (collapsed version of figure
104 // above, stripping out parity bits P1, P2, P4, P8, P16 and only including
105 // data bits 1:26)
106 //
107 // bit position 3 5 6 7 8 9 10 11 12 13 14 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
108 // * * * * * *
109 // parity bit P1 x x . x x . x . x . x x . x . x . x . x . x . x . x = ..11 0110 1010 1101 0101 0101 0101
110 // coverage P2 x . x x . x x . . x x . x x . . x x . . x x . . x x = ..10 1101 1001 1011 0011 0011 0011
111 // P4 . x x x . . . x x x x . . . x x x x . . . . x x x x = ..01 1100 0111 1000 1111 0000 1111
112 // P8 . . . . x x x x x x x . . . . . . . x x x x x x x x = ..00 0011 1111 1000 0000 1111 1111
113 // P16 . . . . . . . . . . . x x x x x x x x x x x x x x x = ..00 0000 0000 0111 1111 1111 1111
114
115 #define HAMMING_M1 0x036AD555 // ..11 0110 1010 1101 0101 0101 0101
116 #define HAMMING_M2 0x02D9B333 // ..10 1101 1001 1011 0011 0011 0011
117 #define HAMMING_M4 0x01C78F0F // ..01 1100 0111 1000 1111 0000 1111
118 #define HAMMING_M8 0x003F80FF // ..00 0011 1111 1000 0000 1111 1111
119 #define HAMMING_M16 0x00007FFF // ..00 0000 0000 0111 1111 1111 1111
120
121 // bit position 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
122 // * * * * * * *
123 // parity bit P1 x . x . x . x . x . x . x . x . x . x . x . x . x . x . x . x = .101 0101 0101 0101 0101 0101 0101 0101
124 // coverage P2 . x x . . x x . . x x . . x x . . x x . . x x . . x x . . x x = .011 0011 0011 0011 0011 0011 0011 0011
125 // P4 . . . x x x x . . . . x x x x . . . . x x x x . . . . x x x x = .000 1111 0000 1111 0000 1111 0000 1111
126 // P8 . . . . . . . x x x x x x x x . . . . . . . . x x x x x x x x = .000 0000 1111 1111 0000 0000 1111 1111
127 // P16 . . . . . . . . . . . . . . . x x x x x x x x x x x x x x x x = .000 0000 0000 0000 1111 1111 1111 1111
128 //
129 // parity bit coverage mask for decoder; used to compute syndromes
130 // for decoding a received message (see figure, above).
131 #define HAMMING_S1 0x55555555 // .101 0101 0101 0101 0101 0101 0101 0101
132 #define HAMMING_S2 0x33333333 // .011 0011 0011 0011 0011 0011 0011 0011
133 #define HAMMING_S4 0x0f0f0f0f // .000 1111 0000 1111 0000 1111 0000 1111
134 #define HAMMING_S8 0x00ff00ff // .000 0000 1111 1111 0000 0000 1111 1111
135 #define HAMMING_S16 0x0000ffff // .000 0000 0000 0000 1111 1111 1111 1111
136
137
138
fec_hamming_encode_symbol(unsigned int _sym_dec)139 unsigned int fec_hamming_encode_symbol(unsigned int _sym_dec)
140 {
141 // validate input
142 if (_sym_dec >= (1<<26)) {
143 fprintf(stderr,"error, fec_hamming_encode(), input symbol too large\n");
144 exit(1);
145 }
146
147 // compute parity bits
148 unsigned int p1 = liquid_bdotprod_uint32(_sym_dec, HAMMING_M1);
149 unsigned int p2 = liquid_bdotprod_uint32(_sym_dec, HAMMING_M2);
150 unsigned int p4 = liquid_bdotprod_uint32(_sym_dec, HAMMING_M4);
151 unsigned int p8 = liquid_bdotprod_uint32(_sym_dec, HAMMING_M8);
152 unsigned int p16 = liquid_bdotprod_uint32(_sym_dec, HAMMING_M16);
153
154 #if DEBUG_FEC_HAMMING
155 printf("parity bits (p1,p2,p4,p8,p16) : (%1u,%1u,%1u,%1u,%1u)\n", p1, p2, p4, p8, p16);
156 #endif
157
158 // encode symbol by inserting parity bits with data bits to
159 // make a 31-bit symbol
160 unsigned int sym_enc = ((_sym_dec & 0x00007fff) << 0) | // ..00 0000 0000 0111 1111 1111 1111
161 ((_sym_dec & 0x003F8000) << 1) | // ..00 0011 1111 1000 0000 0000 0000
162 ((_sym_dec & 0x01C00000) << 2) | // ..01 1100 0000 0000 0000 0000 0000
163 ((_sym_dec & 0x02000000) << 3) | // ..10 0000 0000 0000 0000 0000 0000
164 ( p1 << 30 ) | // 30 = 31 - 1 (position of P1)
165 ( p2 << 29 ) | // 29 = 31 - 2 (position of P2)
166 ( p4 << 27 ) | // 27 = 31 - 4 (position of P4)
167 ( p8 << 23 ) | // 23 = 31 - 8 (position of P8)
168 ( p16 << 15 ); // 15 = 31 - 16 (position of P16)
169
170 return sym_enc;
171 }
172
fec_hamming_decode_symbol(unsigned int _sym_enc)173 unsigned int fec_hamming_decode_symbol(unsigned int _sym_enc)
174 {
175 // validate input
176 if (_sym_enc >= (1<<31)) {
177 fprintf(stderr,"error, fec_hamming_decode(), input symbol too large\n");
178 exit(1);
179 }
180
181 // compute syndrome bits
182 unsigned int s1 = liquid_bdotprod_uint32(_sym_enc, HAMMING_S1);
183 unsigned int s2 = liquid_bdotprod_uint32(_sym_enc, HAMMING_S2);
184 unsigned int s4 = liquid_bdotprod_uint32(_sym_enc, HAMMING_S4);
185 unsigned int s8 = liquid_bdotprod_uint32(_sym_enc, HAMMING_S8);
186 unsigned int s16 = liquid_bdotprod_uint32(_sym_enc, HAMMING_S16);
187
188 // index
189 unsigned int z = (s16<<4) | (s8<<3) | (s4<<2) | (s2<<1) | s1;
190
191 #if DEBUG_FEC_HAMMING
192 printf("syndrome bits (s1,s2,s4,s8,16) : (%1u,%1u,%1u,%1u,%1u)\n", s1, s2, s4, s8, s16);
193 printf("syndrome z : %u\n", z);
194 #endif
195
196 // flip bit at this position
197 if (z) {
198 if (z > 31) {
199 // if this happens there are likely too many errors
200 // to correct; just pass without trying to do anything
201 fprintf(stderr,"warning, fec_hamming_decode_symbol(), syndrome index exceeds maximum\n");
202 } else {
203 //printf("error detected!\n");
204 _sym_enc ^= 1 << (31-z);
205 }
206 }
207
208 // strip data bits from encoded symbol with parity bits
209 unsigned int sym_dec = ((_sym_enc & 0x00007fff) ) | // .000 0000 0000 0000 0111 1111 1111 1111
210 ((_sym_enc & 0x007f0000) >> 1) | // .000 0000 0111 1111 0000 0000 0000 0000
211 ((_sym_enc & 0x07000000) >> 2) | // .000 0111 0000 0000 0000 0000 0000 0000
212 ((_sym_enc & 0x10000000) >> 3); // .001 0000 0000 0000 0000 0000 0000 0000
213 return sym_dec;
214 }
215
216 //
217 // Hamming(31,26) example
218 //
219
print_bitstring(unsigned int _x,unsigned int _n)220 void print_bitstring(unsigned int _x,
221 unsigned int _n)
222 {
223 unsigned int i;
224 for (i=0; i<_n; i++)
225 printf("%1u", (_x >> (_n-i-1)) & 1);
226 }
227
main(int argc,char * argv[])228 int main(int argc, char*argv[])
229 {
230 // original symbol
231 unsigned int sym_org = 28236851; // ..01 1010 1110 1101 1100 0011 0011
232
233 // encoded symbol
234 unsigned int sym_enc = fec_hamming_encode_symbol(sym_org);
235
236 // received symbol
237 unsigned int n=7; // index of bit to corrupt
238 unsigned int sym_rec = sym_enc ^ (1<<(31-n));
239
240 // decoded symbol
241 unsigned int sym_dec = fec_hamming_decode_symbol(sym_rec);
242
243 // print results
244 printf(" sym org : "); print_bitstring(sym_org, 26); printf("\n");
245 printf(" sym enc : "); print_bitstring(sym_enc, 31); printf("\n");
246 printf(" sym rec : "); print_bitstring(sym_rec, 31); printf("\n");
247 printf(" sym dec : "); print_bitstring(sym_dec, 26); printf("\n");
248
249 // print number of bit errors
250 printf(" bit errors : %u\n", count_bit_errors(sym_org, sym_dec));
251
252 return 0;
253 }
254
255