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 (39,32) 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_SECDED3932 0
39
40 // P matrix [7 x 32 bits], [7 x 4 bytes]
41 // 1000 1010 1000 0010 0000 1111 0001 1011
42 // 0001 0000 0001 1111 0111 0001 0110 0001
43 // 0001 0110 1111 0000 1001 0010 1010 0110
44 // 1111 1111 0000 0001 1010 0100 0100 0100
45 // 0110 1100 1111 1111 0000 1000 0000 1000
46 // 0010 0001 0010 0100 1111 1111 1001 0000
47 // 1100 0001 0100 1000 0100 0000 1111 1111
48 unsigned char secded3932_P[28] = {
49 0x8a, 0x82, 0x0f, 0x1b,
50 0x10, 0x1f, 0x71, 0x61,
51 0x16, 0xf0, 0x92, 0xa6,
52 0xff, 0x01, 0xa4, 0x44,
53 0x6c, 0xff, 0x08, 0x08,
54 0x21, 0x24, 0xff, 0x90,
55 0xc1, 0x48, 0x40, 0xff};
56
57
58 // syndrome vectors for errors of weight 1
59 unsigned char secded3932_syndrome_w1[39] = {
60 0x61, 0x51, 0x19, 0x45,
61 0x43, 0x31, 0x29, 0x13,
62 0x62, 0x52, 0x4a, 0x46,
63 0x32, 0x2a, 0x23, 0x1a,
64 0x2c, 0x64, 0x26, 0x25,
65 0x34, 0x16, 0x15, 0x54,
66 0x0b, 0x58, 0x1c, 0x4c,
67 0x38, 0x0e, 0x0d, 0x49,
68 0x01, 0x02, 0x04, 0x08,
69 0x10, 0x20, 0x40};
70
71 // compute parity on 32-bit input
fec_secded3932_compute_parity(unsigned char * _m)72 unsigned char fec_secded3932_compute_parity(unsigned char * _m)
73 {
74 // compute encoded/transmitted message: v = m*G
75 unsigned char parity = 0x00;
76
77 // TODO : unwrap this loop
78 unsigned int i;
79 for (i=0; i<7; i++) {
80 parity <<= 1;
81
82 unsigned int p = liquid_c_ones[ secded3932_P[4*i+0] & _m[0] ] +
83 liquid_c_ones[ secded3932_P[4*i+1] & _m[1] ] +
84 liquid_c_ones[ secded3932_P[4*i+2] & _m[2] ] +
85 liquid_c_ones[ secded3932_P[4*i+3] & _m[3] ];
86
87 parity |= p & 0x01;
88 }
89
90 return parity;
91 }
92
93 // compute syndrome on 39-bit input
fec_secded3932_compute_syndrome(unsigned char * _v)94 unsigned char fec_secded3932_compute_syndrome(unsigned char * _v)
95 {
96 // TODO : unwrap this loop
97 unsigned int i;
98 unsigned char syndrome = 0x00;
99 for (i=0; i<7; i++) {
100 syndrome <<= 1;
101
102 unsigned int p =
103 ( (_v[0] & (1<<(7-i-1))) ? 1 : 0 )+
104 liquid_c_ones[ secded3932_P[4*i+0] & _v[1] ] +
105 liquid_c_ones[ secded3932_P[4*i+1] & _v[2] ] +
106 liquid_c_ones[ secded3932_P[4*i+2] & _v[3] ] +
107 liquid_c_ones[ secded3932_P[4*i+3] & _v[4] ];
108
109 syndrome |= p & 0x01;
110 }
111
112 return syndrome;
113 }
114
115 // encode symbol
116 // _sym_dec : decoded symbol [size: 4 x 1]
117 // _sym_enc : encoded symbol [size: 5 x 1], _sym_enc[0] has only 7 bits
fec_secded3932_encode_symbol(unsigned char * _sym_dec,unsigned char * _sym_enc)118 void fec_secded3932_encode_symbol(unsigned char * _sym_dec,
119 unsigned char * _sym_enc)
120 {
121 // first six bits is parity block
122 _sym_enc[0] = fec_secded3932_compute_parity(_sym_dec);
123
124 // concatenate original message
125 _sym_enc[1] = _sym_dec[0];
126 _sym_enc[2] = _sym_dec[1];
127 _sym_enc[3] = _sym_dec[2];
128 _sym_enc[4] = _sym_dec[3];
129 }
130
131 // decode symbol, returning 0/1/2 for zero/one/multiple errors detected
132 // _sym_enc : encoded symbol [size: 5 x 1], _sym_enc[0] has only 7 bits
133 // _sym_dec : decoded symbol [size: 4 x 1]
fec_secded3932_decode_symbol(unsigned char * _sym_enc,unsigned char * _sym_dec)134 int fec_secded3932_decode_symbol(unsigned char * _sym_enc,
135 unsigned char * _sym_dec)
136 {
137 #if 0
138 // validate input
139 if (_sym_enc[0] >= (1<<7)) {
140 fprintf(stderr,"warning, fec_secded3932_decode_symbol(), input symbol too large\n");
141 }
142 #endif
143
144 // estimate error vector
145 unsigned char e_hat[5] = {0,0,0,0,0}; // estimated error vector
146 int syndrome_flag = fec_secded3932_estimate_ehat(_sym_enc, e_hat);
147
148 // compute estimated transmit vector (last 64 bits of encoded message)
149 // NOTE: indices take into account first element in _sym_enc and e_hat
150 // arrays holds the parity bits
151 _sym_dec[0] = _sym_enc[1] ^ e_hat[1];
152 _sym_dec[1] = _sym_enc[2] ^ e_hat[2];
153 _sym_dec[2] = _sym_enc[3] ^ e_hat[3];
154 _sym_dec[3] = _sym_enc[4] ^ e_hat[4];
155
156 #if DEBUG_FEC_SECDED3932
157 if (syndrome_flag == 1) {
158 printf("secded3932_decode_symbol(): single error detected!\n");
159 } else if (syndrome_flag == 2) {
160 printf("secded3932_decode_symbol(): no match found (multiple errors detected)\n");
161 }
162 #endif
163
164 // return syndrome flag
165 return syndrome_flag;
166 }
167
168 // estimate error vector, returning 0/1/2 for zero/one/multiple errors
169 // detected, respectively
170 // _sym_enc : encoded symbol [size: 5 x 1], _sym_enc[0] has only 6 bits
171 // _e_hat : estimated error vector [size: 5 x 1]
fec_secded3932_estimate_ehat(unsigned char * _sym_enc,unsigned char * _e_hat)172 int fec_secded3932_estimate_ehat(unsigned char * _sym_enc,
173 unsigned char * _e_hat)
174 {
175 // clear output array
176 _e_hat[0] = 0x00;
177 _e_hat[1] = 0x00;
178 _e_hat[2] = 0x00;
179 _e_hat[3] = 0x00;
180 _e_hat[4] = 0x00;
181
182 // compute syndrome vector, s = r*H^T = ( H*r^T )^T
183 unsigned char s = fec_secded3932_compute_syndrome(_sym_enc);
184
185 // compute weight of s
186 unsigned int ws = liquid_c_ones[s];
187
188 if (ws == 0) {
189 // no errors detected
190 return 0;
191 } else {
192 // estimate error location; search for syndrome with error
193 // vector of weight one
194
195 unsigned int n;
196 // estimate error location
197 for (n=0; n<39; n++) {
198 if (s == secded3932_syndrome_w1[n]) {
199 // single error detected at location 'n'
200 div_t d = div(n,8);
201 _e_hat[5-d.quot-1] = 1 << d.rem;
202
203 return 1;
204 }
205 }
206
207 }
208
209 // no syndrome match; multiple errors detected
210 return 2;
211 }
212
213 // create SEC-DED (39,32) codec object
fec_secded3932_create(void * _opts)214 fec fec_secded3932_create(void * _opts)
215 {
216 fec q = (fec) malloc(sizeof(struct fec_s));
217
218 // set scheme
219 q->scheme = LIQUID_FEC_SECDED3932;
220 q->rate = fec_get_rate(q->scheme);
221
222 // set internal function pointers
223 q->encode_func = &fec_secded3932_encode;
224 q->decode_func = &fec_secded3932_decode;
225 q->decode_soft_func = NULL;
226
227 return q;
228 }
229
230 // destroy SEC-DEC (39,32) object
fec_secded3932_destroy(fec _q)231 void fec_secded3932_destroy(fec _q)
232 {
233 free(_q);
234 }
235
236 // encode block of data using SEC-DEC (39,32) encoder
237 //
238 // _q : encoder/decoder object
239 // _dec_msg_len : decoded message length (number of bytes)
240 // _msg_dec : decoded message [size: 1 x _dec_msg_len]
241 // _msg_enc : encoded message [size: 1 x 2*_dec_msg_len]
fec_secded3932_encode(fec _q,unsigned int _dec_msg_len,unsigned char * _msg_dec,unsigned char * _msg_enc)242 void fec_secded3932_encode(fec _q,
243 unsigned int _dec_msg_len,
244 unsigned char *_msg_dec,
245 unsigned char *_msg_enc)
246 {
247 unsigned int i=0; // decoded byte counter
248 unsigned int j=0; // encoded byte counter
249
250 // determine remainder of input length / 4
251 unsigned int r = _dec_msg_len % 4;
252
253 // for now simply encode as 4/5-rate codec (eat
254 // last parity bit)
255 // TODO : make more efficient
256
257 for (i=0; i<_dec_msg_len-r; i+=4) {
258 // compute parity (7 bits) on two input bytes (32 bits)
259 _msg_enc[j+0] = fec_secded3932_compute_parity(&_msg_dec[i]);
260
261 // copy remaining two input bytes (32 bits)
262 _msg_enc[j+1] = _msg_dec[i+0];
263 _msg_enc[j+2] = _msg_dec[i+1];
264 _msg_enc[j+3] = _msg_dec[i+2];
265 _msg_enc[j+4] = _msg_dec[i+3];
266
267 // increment output counter
268 j += 5;
269 }
270
271 // if input length isn't divisible by 4, encode last few bytes
272 if (r) {
273 // one 32-bit symbol (decoded)
274 unsigned char m[4] = {0,0,0,0};
275 unsigned int n;
276 for (n=0; n<r; n++)
277 m[n] = _msg_dec[i+n];
278
279 // one 39-bit symbol (encoded)
280 unsigned char v[5];
281
282 // encode
283 fec_secded3932_encode_symbol(m, v);
284
285 // there is no need to actually send all five bytes;
286 // the last few bytes are zero and can be artificially
287 // inserted at the decoder
288 _msg_enc[j+0] = v[0];
289 for (n=0; n<r; n++)
290 _msg_enc[j+n+1] = v[n+1];
291
292 i += r;
293 j += r+1;
294 }
295
296 assert( j == fec_get_enc_msg_length(LIQUID_FEC_SECDED3932,_dec_msg_len) );
297 assert( i == _dec_msg_len);
298 }
299
300 // decode block of data using SEC-DEC (39,32) decoder
301 //
302 // _q : encoder/decoder object
303 // _dec_msg_len : decoded message length (number of bytes)
304 // _msg_enc : encoded message [size: 1 x 2*_dec_msg_len]
305 // _msg_dec : decoded message [size: 1 x _dec_msg_len]
306 //
307 //unsigned int
fec_secded3932_decode(fec _q,unsigned int _dec_msg_len,unsigned char * _msg_enc,unsigned char * _msg_dec)308 void fec_secded3932_decode(fec _q,
309 unsigned int _dec_msg_len,
310 unsigned char *_msg_enc,
311 unsigned char *_msg_dec)
312 {
313 unsigned int i=0; // decoded byte counter
314 unsigned int j=0; // encoded byte counter
315
316 // determine remainder of input length / 4
317 unsigned int r = _dec_msg_len % 4;
318
319 for (i=0; i<_dec_msg_len-r; i+=4) {
320 // decode straight to output
321 fec_secded3932_decode_symbol(&_msg_enc[j], &_msg_dec[i]);
322
323 j += 5;
324 }
325
326 // if input length isn't divisible by 4, decode last several bytes
327 if (r) {
328 // one 39-bit symbol
329 unsigned char v[5] = {_msg_enc[j+0], 0, 0, 0, 0};
330 unsigned int n;
331 for (n=0; n<r; n++)
332 v[n+1] = _msg_enc[j+n+1];
333
334 // one 32-bit symbol (decoded)
335 unsigned char m_hat[4];
336
337 // decode symbol
338 fec_secded3932_decode_symbol(v, m_hat);
339
340 // copy non-zero bytes to output (ignore zeros artifically
341 // inserted at receiver)
342 for (n=0; n<r; n++)
343 _msg_dec[i+n] = m_hat[n];
344
345 i += r;
346 j += r+1;
347 }
348
349 assert( j == fec_get_enc_msg_length(LIQUID_FEC_SECDED3932,_dec_msg_len) );
350 assert( i == _dec_msg_len);
351
352 //return num_errors;
353 }
354