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 // (39,32) code test (SEC-DED)
25 //
26
27 #include <stdio.h>
28 #include <stdlib.h>
29 #include <string.h>
30 #include <assert.h>
31
32 #include "liquid.internal.h"
33
34 #define DEBUG_FEC_SECDED 1
35
36 // P matrix [7 x 32 bits], [7 x 4 bytes]
37 // 1000 1010 1000 0010 0000 1111 0001 1011
38 // 0001 0000 0001 1111 0111 0001 0110 0001
39 // 0001 0110 1111 0000 1001 0010 1010 0110
40 // 1111 1111 0000 0001 1010 0100 0100 0100
41 // 0110 1100 1111 1111 0000 1000 0000 1000
42 // 0010 0001 0010 0100 1111 1111 1001 0000
43 // 1100 0001 0100 1000 0100 0000 1111 1111
44 unsigned char P[28] = {
45 0x8a, 0x82, 0x0f, 0x1b,
46 0x10, 0x1f, 0x71, 0x61,
47 0x16, 0xf0, 0x92, 0xa6,
48 0xff, 0x01, 0xa4, 0x44,
49 0x6c, 0xff, 0x08, 0x08,
50 0x21, 0x24, 0xff, 0x90,
51 0xc1, 0x48, 0x40, 0xff};
52
53
print_bitstring_short(unsigned char _x,unsigned char _n)54 void print_bitstring_short(unsigned char _x,
55 unsigned char _n)
56 {
57 unsigned int i;
58 for (i=0; i<_n; i++)
59 printf("%1u", (_x >> (_n-i-1)) & 1);
60 }
61
print_bitstring(unsigned char * _x,unsigned char _n)62 void print_bitstring(unsigned char * _x,
63 unsigned char _n)
64 {
65 unsigned int i;
66 // compute number of elements in _x
67 div_t d = div(_n, 8);
68 unsigned int N = d.quot + (d.rem ? 1 : 0);
69
70 // print leader
71 printf(" ");
72 if (d.rem == 0) printf(" ");
73 for (i=0; i<8-d.rem-1; i++)
74 printf(" ");
75
76 // print bitstring
77 for (i=0; i<N; i++) {
78 if (i==0 && d.rem)
79 print_bitstring_short(_x[i], d.rem);
80 else
81 print_bitstring_short(_x[i], 8);
82
83 printf(" ");
84
85 }
86 printf("\n");
87 }
88
main(int argc,char * argv[])89 int main(int argc, char*argv[])
90 {
91 unsigned int i;
92
93 // error vector [22 x 1]
94 unsigned char err[5] = {0,0,0,0,2};
95
96 // original message [16 x 1]
97 unsigned char m[4] = {0,0,0,1};
98 //m[0] = rand() & 0xffff;
99 //m[1] = rand() & 0xffff;
100
101 // derived values
102 unsigned char v[5]; // encoded/transmitted message
103 unsigned char e[5]; // error vector
104 unsigned char r[5]; // received vector
105 unsigned char s; // syndrome vector
106 unsigned char e_hat[5] = {0,0,0,0,0}; // estimated error vector
107 unsigned char v_hat[5]; // estimated transmitted message
108 unsigned char m_hat[4]; // estimated original message
109
110 #if 0
111 // print P matrix
112 printf("P : \n");
113 print_bitstring(&P[ 0],32);
114 print_bitstring(&P[ 4],32);
115 print_bitstring(&P[ 8],32);
116 print_bitstring(&P[12],32);
117 print_bitstring(&P[16],32);
118 print_bitstring(&P[20],32);
119 print_bitstring(&P[24],32);
120 #endif
121
122 // original message
123 printf("m (original message): ");
124 print_bitstring(m,32);
125
126 // compute encoded/transmitted message: v = m*G
127 v[0] = 0;
128 for (i=0; i<7; i++) {
129 v[0] <<= 1;
130
131 unsigned int p = liquid_c_ones[P[4*i+0] & m[0]] +
132 liquid_c_ones[P[4*i+1] & m[1]] +
133 liquid_c_ones[P[4*i+2] & m[2]] +
134 liquid_c_ones[P[4*i+3] & m[3]];
135 //printf("p = %u\n", p);
136 v[0] |= p & 0x01;
137 }
138 v[1] = m[0];
139 v[2] = m[1];
140 v[3] = m[2];
141 v[4] = m[3];
142 printf("v (encoded message): ");
143 print_bitstring(v,39);
144
145 // use pre-determined error vector
146 e[0] = err[0];
147 e[1] = err[1];
148 e[2] = err[2];
149 e[3] = err[3];
150 e[4] = err[4];
151 printf("e (error vector): ");
152 print_bitstring(e,39);
153
154 // compute received vector: r = v + e
155 r[0] = v[0] ^ e[0];
156 r[1] = v[1] ^ e[1];
157 r[2] = v[2] ^ e[2];
158 r[3] = v[3] ^ e[3];
159 r[4] = v[4] ^ e[4];
160 printf("r (received vector): ");
161 print_bitstring(r,39);
162
163 // compute syndrome vector, s = r*H^T = ( H*r^T )^T
164 s = 0;
165 for (i=0; i<7; i++) {
166 s <<= 1;
167
168 unsigned int p =
169 ( (r[0] & (1<<(7-i-1))) ? 1 : 0 )+
170 liquid_count_ones(P[4*i+0] & r[1]) +
171 liquid_count_ones(P[4*i+1] & r[2]) +
172 liquid_count_ones(P[4*i+2] & r[3]) +
173 liquid_count_ones(P[4*i+3] & r[4]);
174 //printf("p = %u\n", p);
175
176 s |= p & 0x01;
177 }
178 printf("s (syndrome vector): ");
179 print_bitstring(&s,7);
180
181 // compute weight of s
182 unsigned int ws = liquid_count_ones(s);
183 printf("weight(s) = %u\n", ws);
184
185 if (ws == 0) {
186 printf("no errors detected\n");
187 } else {
188 // estimate error location
189 int syndrome_match = 0;
190
191 // TODO : these can be pre-computed
192 unsigned int n;
193 for (n=0; n<39; n++) {
194 // compute syndrome
195 unsigned int s_test = 0;
196 unsigned char e_test[5] = {0,0,0,0,0};
197
198 div_t d = div(n,8);
199 e_test[5-d.quot-1] = 1 << d.rem;
200
201 for (i=0; i<7; i++) {
202 s_test <<= 1;
203 unsigned int p =
204 ( (e_test[0] & (1<<(7-i-1))) ? 1 : 0 )+
205 liquid_count_ones(P[4*i+0] & e_test[1]) +
206 liquid_count_ones(P[4*i+1] & e_test[2]) +
207 liquid_count_ones(P[4*i+2] & e_test[3]) +
208 liquid_count_ones(P[4*i+3] & e_test[4]);
209
210 s_test |= p & 0x01;
211 }
212
213 #if 1
214 // print results
215 //printf("e_test:"); print_bitstring(e_test, 72);
216 printf("%3u : e = ", n);
217 print_bitstring_short(e_test[0],7); printf(" ");
218 print_bitstring_short(e_test[1],8); printf(" ");
219 print_bitstring_short(e_test[2],8); printf(" ");
220 print_bitstring_short(e_test[3],8); printf(" ");
221 print_bitstring_short(e_test[4],8); printf(" ");
222 printf(", s = ");
223 print_bitstring_short(s_test,7);
224 if (s == s_test) printf(" *");
225 printf("\n");
226 #else
227 // print output array (secded2216_syndrome_w1[])
228 printf("0x%.2x\n", s_test);
229 #endif
230
231 if (s == s_test) {
232 memmove(e_hat, e_test, sizeof(e_test));
233 syndrome_match = 1;
234 }
235 }
236
237 if (syndrome_match) {
238 printf("syndrome match!\n");
239 } else {
240 printf("no syndrome match; expected multiple errors\n");
241 }
242 }
243
244 // compute estimated transmitted message: v_hat = r + e_hat
245 printf("e-hat (estimated error):");
246 print_bitstring(e_hat,39);
247
248 printf("v-hat (estimated tx): ");
249 v_hat[0] = r[0] ^ e_hat[0];
250 v_hat[1] = r[1] ^ e_hat[1];
251 v_hat[2] = r[2] ^ e_hat[2];
252 v_hat[3] = r[3] ^ e_hat[3];
253 v_hat[4] = r[4] ^ e_hat[4];
254 print_bitstring(v_hat,39);
255
256 // compute estimated original message: (last 16 bits of encoded message)
257 m_hat[0] = v_hat[1];
258 m_hat[1] = v_hat[2];
259 m_hat[2] = v_hat[3];
260 m_hat[3] = v_hat[4];
261 printf("m-hat (estimated orig.):");
262 print_bitstring(m_hat,32);
263
264 // compute errors between v, v_hat
265 unsigned int num_errors_encoded = count_bit_errors_array(v, v_hat, 5);
266 printf("decoding errors (encoded) : %2u / 39\n", num_errors_encoded);
267
268 // compute errors between m, m_hat
269 unsigned int num_errors_decoded = count_bit_errors_array(m, m_hat, 4);
270 printf("decoding errors (original) : %2u / 32\n", num_errors_decoded);
271
272 return 0;
273 }
274
275