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