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