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 // SEC-DED (72,64) 8/9-rate forward error-correction block code
25 //
26 // References:
27 // [Lin:2004] Lin, Shu and Costello, Daniel L. Jr., "Error Control
28 // Coding," Prentice Hall, New Jersey, 2nd edition, 2004.
29 //
30
31 #include <stdio.h>
32 #include <stdlib.h>
33 #include <string.h>
34 #include <assert.h>
35
36 #include "liquid.internal.h"
37
38 #define DEBUG_FEC_SECDED7264 0
39
40 // P matrix [8 x 64]
41 // 11111111 00001111 00001111 00001100 01101000 10001000 10001000 10000000 :
42 // 11110000 11111111 00000000 11110011 01100100 01000100 01000100 01000000 :
43 // 00110000 11110000 11111111 00001111 00000010 00100010 00100010 00100110 :
44 // 11001111 00000000 11110000 11111111 00000001 00010001 00010001 00010110 :
45 // 01101000 10001000 10001000 10000000 11111111 00001111 00000000 11110011 :
46 // 01100100 01000100 01000100 01000000 11110000 11111111 00001111 00001100 :
47 // 00000010 00100010 00100010 00100110 11001111 00000000 11111111 00001111 :
48 // 00000001 00010001 00010001 00010110 00110000 11110000 11110000 11111111 :
49 unsigned char secded7264_P[64] = {
50 0xFF, 0x0F, 0x0F, 0x0C, 0x68, 0x88, 0x88, 0x80,
51 0xF0, 0xFF, 0x00, 0xF3, 0x64, 0x44, 0x44, 0x40,
52 0x30, 0xF0, 0xFF, 0x0F, 0x02, 0x22, 0x22, 0x26,
53 0xCF, 0x00, 0xF0, 0xFF, 0x01, 0x11, 0x11, 0x16,
54 0x68, 0x88, 0x88, 0x80, 0xFF, 0x0F, 0x00, 0xF3,
55 0x64, 0x44, 0x44, 0x40, 0xF0, 0xFF, 0x0F, 0x0C,
56 0x02, 0x22, 0x22, 0x26, 0xCF, 0x00, 0xFF, 0x0F,
57 0x01, 0x11, 0x11, 0x16, 0x30, 0xF0, 0xF0, 0xFF};
58
59 // syndrome vectors for errors of weight 1
60 unsigned char secded7264_syndrome_w1[72] = {
61 0x0b, 0x3b, 0x37, 0x07, 0x19, 0x29, 0x49, 0x89,
62 0x16, 0x26, 0x46, 0x86, 0x13, 0x23, 0x43, 0x83,
63 0x1c, 0x2c, 0x4c, 0x8c, 0x15, 0x25, 0x45, 0x85,
64 0x1a, 0x2a, 0x4a, 0x8a, 0x0d, 0xcd, 0xce, 0x0e,
65 0x70, 0x73, 0xb3, 0xb0, 0x51, 0x52, 0x54, 0x58,
66 0xa1, 0xa2, 0xa4, 0xa8, 0x31, 0x32, 0x34, 0x38,
67 0xc1, 0xc2, 0xc4, 0xc8, 0x61, 0x62, 0x64, 0x68,
68 0x91, 0x92, 0x94, 0x98, 0xe0, 0xec, 0xdc, 0xd0,
69 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80};
70
71
72 // compute parity byte on 64-byte input
fec_secded7264_compute_parity(unsigned char * _v)73 unsigned char fec_secded7264_compute_parity(unsigned char * _v)
74 {
75 // compute parity byte on message
76 unsigned int i;
77 unsigned char parity = 0x00;
78 for (i=0; i<8; i++) {
79 parity <<= 1;
80
81 unsigned int p = liquid_c_ones[ secded7264_P[8*i+0] & _v[0] ] +
82 liquid_c_ones[ secded7264_P[8*i+1] & _v[1] ] +
83 liquid_c_ones[ secded7264_P[8*i+2] & _v[2] ] +
84 liquid_c_ones[ secded7264_P[8*i+3] & _v[3] ] +
85 liquid_c_ones[ secded7264_P[8*i+4] & _v[4] ] +
86 liquid_c_ones[ secded7264_P[8*i+5] & _v[5] ] +
87 liquid_c_ones[ secded7264_P[8*i+6] & _v[6] ] +
88 liquid_c_ones[ secded7264_P[8*i+7] & _v[7] ];
89
90 parity |= p & 0x01;
91 }
92
93 // return parity byte
94 return parity;
95 }
96
97 // compute syndrome on 72-bit input
fec_secded7264_compute_syndrome(unsigned char * _v)98 unsigned char fec_secded7264_compute_syndrome(unsigned char * _v)
99 {
100 // TODO : unwrap this loop
101 unsigned int i;
102 unsigned char syndrome = 0x00;
103 for (i=0; i<8; i++) {
104 syndrome <<= 1;
105
106 // compute parity bit
107 unsigned int p =
108 ( (_v[0] & (1<<(8-i-1))) ? 1 : 0 ) +
109 liquid_c_ones[ secded7264_P[8*i+0] & _v[1] ] +
110 liquid_c_ones[ secded7264_P[8*i+1] & _v[2] ] +
111 liquid_c_ones[ secded7264_P[8*i+2] & _v[3] ] +
112 liquid_c_ones[ secded7264_P[8*i+3] & _v[4] ] +
113 liquid_c_ones[ secded7264_P[8*i+4] & _v[5] ] +
114 liquid_c_ones[ secded7264_P[8*i+5] & _v[6] ] +
115 liquid_c_ones[ secded7264_P[8*i+6] & _v[7] ] +
116 liquid_c_ones[ secded7264_P[8*i+7] & _v[8] ];
117
118 syndrome |= p & 0x01;
119 }
120
121 return syndrome;
122 }
123
fec_secded7264_encode_symbol(unsigned char * _sym_dec,unsigned char * _sym_enc)124 void fec_secded7264_encode_symbol(unsigned char * _sym_dec,
125 unsigned char * _sym_enc)
126 {
127 // compute parity on input
128 _sym_enc[0] = fec_secded7264_compute_parity(_sym_dec);
129
130 // copy input to output
131 _sym_enc[1] = _sym_dec[0];
132 _sym_enc[2] = _sym_dec[1];
133 _sym_enc[3] = _sym_dec[2];
134 _sym_enc[4] = _sym_dec[3];
135 _sym_enc[5] = _sym_dec[4];
136 _sym_enc[6] = _sym_dec[5];
137 _sym_enc[7] = _sym_dec[6];
138 _sym_enc[8] = _sym_dec[7];
139 }
140
141 // decode symbol, returning 0/1/2 for zero/one/multiple errors detected
142 // _sym_enc : encoded symbol [size: 9 x 1]
143 // _sym_dec : decoded symbol [size: 8 x 1]
fec_secded7264_decode_symbol(unsigned char * _sym_enc,unsigned char * _sym_dec)144 int fec_secded7264_decode_symbol(unsigned char * _sym_enc,
145 unsigned char * _sym_dec)
146 {
147 // estimate error vector
148 unsigned char e_hat[9] = {0,0,0,0,0,0,0,0,0};
149 int syndrome_flag = fec_secded7264_estimate_ehat(_sym_enc, e_hat);
150
151 // compute estimated transmit vector (last 64 bits of encoded message)
152 // NOTE: indices take into account first element in _sym_enc and e_hat
153 // arrays holds the parity bits
154 _sym_dec[0] = _sym_enc[1] ^ e_hat[1];
155 _sym_dec[1] = _sym_enc[2] ^ e_hat[2];
156 _sym_dec[2] = _sym_enc[3] ^ e_hat[3];
157 _sym_dec[3] = _sym_enc[4] ^ e_hat[4];
158 _sym_dec[4] = _sym_enc[5] ^ e_hat[5];
159 _sym_dec[5] = _sym_enc[6] ^ e_hat[6];
160 _sym_dec[6] = _sym_enc[7] ^ e_hat[7];
161 _sym_dec[7] = _sym_enc[8] ^ e_hat[8];
162
163 #if DEBUG_FEC_SECDED7264
164 if (syndrome_flag == 1) {
165 printf("secded7264_decode_symbol(): single error detected!\n");
166 } else if (syndrome_flag == 2) {
167 printf("secded7264_decode_symbol(): no match found (multiple errors detected)\n");
168 }
169 #endif
170
171 // return syndrome flag
172 return syndrome_flag;
173 }
174
175 // estimate error vector, returning 0/1/2 for zero/one/multiple errors
176 // detected, respectively
177 // _sym_enc : encoded symbol [size: 9 x 1],
178 // _e_hat : estimated error vector [size: 9 x 1]
fec_secded7264_estimate_ehat(unsigned char * _sym_enc,unsigned char * _e_hat)179 int fec_secded7264_estimate_ehat(unsigned char * _sym_enc,
180 unsigned char * _e_hat)
181 {
182 // clear output array
183 memset(_e_hat, 0x00, 9*sizeof(unsigned char));
184
185 // compute syndrome vector, s = r*H^T = ( H*r^T )^T
186 unsigned char s = fec_secded7264_compute_syndrome(_sym_enc);
187
188 // compute weight of s
189 unsigned int ws = liquid_c_ones[s];
190
191 if (ws == 0) {
192 // no errors detected
193 return 0;
194 } else {
195 // estimate error location; search for syndrome with error
196 // vector of weight one
197
198 unsigned int n;
199 // estimate error location
200 for (n=0; n<72; n++) {
201 if (s == secded7264_syndrome_w1[n]) {
202 // single error detected at location 'n'
203 div_t d = div(n,8);
204 _e_hat[9-d.quot-1] = 1 << d.rem;
205
206 return 1;
207 }
208 }
209
210 }
211
212 // no syndrome match; multiple errors detected
213 return 2;
214 }
215
216 // create SEC-DED (72,64) codec object
fec_secded7264_create(void * _opts)217 fec fec_secded7264_create(void * _opts)
218 {
219 fec q = (fec) malloc(sizeof(struct fec_s));
220
221 // set scheme
222 q->scheme = LIQUID_FEC_SECDED7264;
223 q->rate = fec_get_rate(q->scheme);
224
225 // set internal function pointers
226 q->encode_func = &fec_secded7264_encode;
227 q->decode_func = &fec_secded7264_decode;
228 q->decode_soft_func = NULL;
229
230 return q;
231 }
232
233 // destroy SEC-DEC (72,64) object
fec_secded7264_destroy(fec _q)234 void fec_secded7264_destroy(fec _q)
235 {
236 free(_q);
237 }
238
239 // encode block of data using SEC-DEC (72,64) encoder
240 //
241 // _q : encoder/decoder object
242 // _dec_msg_len : decoded message length (number of bytes)
243 // _msg_dec : decoded message [size: 1 x _dec_msg_len]
244 // _msg_enc : encoded message [size: 1 x 2*_dec_msg_len]
fec_secded7264_encode(fec _q,unsigned int _dec_msg_len,unsigned char * _msg_dec,unsigned char * _msg_enc)245 void fec_secded7264_encode(fec _q,
246 unsigned int _dec_msg_len,
247 unsigned char *_msg_dec,
248 unsigned char *_msg_enc)
249 {
250 unsigned int i=0; // decoded byte counter
251 unsigned int j=0; // encoded byte counter
252 unsigned char parity; // parity byte
253
254 // determine remainder of input length / 8
255 unsigned int r = _dec_msg_len % 8;
256
257 // TODO : devise more efficient way of doing this
258 for (i=0; i<_dec_msg_len-r; i+=8) {
259 // encode directly to output
260 fec_secded7264_encode_symbol(&_msg_dec[i], &_msg_enc[j]);
261
262 j += 9;
263 }
264
265 // if input length isn't divisible by 8, encode last few bytes
266 if (r) {
267 unsigned char v[8] = {0,0,0,0,0,0,0,0};
268 unsigned int n;
269 for (n=0; n<r; n++)
270 v[n] = _msg_dec[i+n];
271
272 // compute parity
273 parity = fec_secded7264_compute_parity(v);
274
275 // there is no need to actually send all the bytes; the
276 // last 8-r bytes are zeros and can be added at the
277 // decoder
278 _msg_enc[j+0] = parity;
279 for (n=0; n<r; n++)
280 _msg_enc[j+n+1] = _msg_dec[i+n];
281
282 i += r;
283 j += r+1;
284 }
285
286 assert( j == fec_get_enc_msg_length(LIQUID_FEC_SECDED7264,_dec_msg_len) );
287 assert( i == _dec_msg_len);
288 }
289
290 // decode block of data using SEC-DEC (72,64) decoder
291 //
292 // _q : encoder/decoder object
293 // _dec_msg_len : decoded message length (number of bytes)
294 // _msg_enc : encoded message [size: 1 x 2*_dec_msg_len]
295 // _msg_dec : decoded message [size: 1 x _dec_msg_len]
296 //
297 //unsigned int
fec_secded7264_decode(fec _q,unsigned int _dec_msg_len,unsigned char * _msg_enc,unsigned char * _msg_dec)298 void fec_secded7264_decode(fec _q,
299 unsigned int _dec_msg_len,
300 unsigned char *_msg_enc,
301 unsigned char *_msg_dec)
302 {
303 unsigned int i=0; // decoded byte counter
304 unsigned int j=0; // encoded byte counter
305
306 // determine remainder of input length / 8
307 unsigned int r = _dec_msg_len % 8;
308
309 for (i=0; i<_dec_msg_len-r; i+=8) {
310 // decode nine input bytes
311 fec_secded7264_decode_symbol(&_msg_enc[j], &_msg_dec[i]);
312
313 j += 9;
314 }
315
316
317 // if input length isn't divisible by 8, decode last several bytes
318 if (r) {
319 unsigned char v[9] = {0,0,0,0,0,0,0,0,0}; // received message
320 unsigned char c[8] = {0,0,0,0,0,0,0,0}; // decoded message
321
322 unsigned int n;
323 // output length is input + 1 (parity byte)
324 for (n=0; n<r+1; n++)
325 v[n] = _msg_enc[j+n];
326
327 // decode symbol
328 fec_secded7264_decode_symbol(v,c);
329
330 // store only relevant bytes
331 for (n=0; n<r; n++)
332 _msg_dec[i+n] = c[n];
333
334 i += r;
335 j += r+1;
336 }
337
338 assert( j == fec_get_enc_msg_length(LIQUID_FEC_SECDED7264,_dec_msg_len) );
339 assert( i == _dec_msg_len);
340
341 //return num_errors;
342 }
343