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 // (72,64) 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 [8 x 64]
37 // 11111111 00001111 00001111 00001100 01101000 10001000 10001000 10000000 :
38 // 11110000 11111111 00000000 11110011 01100100 01000100 01000100 01000000 :
39 // 00110000 11110000 11111111 00001111 00000010 00100010 00100010 00100110 :
40 // 11001111 00000000 11110000 11111111 00000001 00010001 00010001 00010110 :
41 // 01101000 10001000 10001000 10000000 11111111 00001111 00000000 11110011 :
42 // 01100100 01000100 01000100 01000000 11110000 11111111 00001111 00001100 :
43 // 00000010 00100010 00100010 00100110 11001111 00000000 11111111 00001111 :
44 // 00000001 00010001 00010001 00010110 00110000 11110000 11110000 11111111 :
45 unsigned char P[64] = {
46 0xFF, 0x0F, 0x0F, 0x0C, 0x68, 0x88, 0x88, 0x80,
47 0xF0, 0xFF, 0x00, 0xF3, 0x64, 0x44, 0x44, 0x40,
48 0x30, 0xF0, 0xFF, 0x0F, 0x02, 0x22, 0x22, 0x26,
49 0xCF, 0x00, 0xF0, 0xFF, 0x01, 0x11, 0x11, 0x16,
50 0x68, 0x88, 0x88, 0x80, 0xFF, 0x0F, 0x00, 0xF3,
51 0x64, 0x44, 0x44, 0x40, 0xF0, 0xFF, 0x0F, 0x0C,
52 0x02, 0x22, 0x22, 0x26, 0xCF, 0x00, 0xFF, 0x0F,
53 0x01, 0x11, 0x11, 0x16, 0x30, 0xF0, 0xF0, 0xFF};
54
print_bitstring_short(unsigned char _x,unsigned char _n)55 void print_bitstring_short(unsigned char _x,
56 unsigned char _n)
57 {
58 unsigned int i;
59 for (i=0; i<_n; i++)
60 printf("%1u", (_x >> (_n-i-1)) & 1);
61 }
62
print_bitstring(unsigned char * _x,unsigned char _n)63 void print_bitstring(unsigned char * _x,
64 unsigned char _n)
65 {
66 unsigned int i;
67 // compute number of elements in _x
68 div_t d = div(_n, 8);
69 unsigned int N = d.quot + (d.rem ? 1 : 0);
70
71 // print leader
72 printf(" ");
73 if (d.rem == 0) printf(" ");
74 for (i=0; i<8-d.rem-1; i++)
75 printf(" ");
76
77 // print bitstring
78 for (i=0; i<N; i++) {
79 if (i==0 && d.rem)
80 print_bitstring_short(_x[i], d.rem);
81 else
82 print_bitstring_short(_x[i], 8);
83
84 printf(" ");
85
86 }
87 printf("\n");
88 }
89
90
main(int argc,char * argv[])91 int main(int argc, char*argv[])
92 {
93 unsigned int i;
94
95 // error vector [72 x 1]
96 unsigned char e[9] = {0,0,0,0,0,0,0,0,2};
97
98 // original message [64 x 1]
99 unsigned char m[8] = {0,0,0,0,0,0,0,1};
100
101 // derived values
102 unsigned char v[9]; // encoded/transmitted message
103 unsigned char r[9]; // received vector
104 unsigned char s; // syndrome vector
105 unsigned char v_hat[9]; // estimated transmitted message
106 unsigned char m_hat[8]; // estimated original message
107
108 // original message
109 printf("m (original message):\n ");
110 print_bitstring(m,64);
111
112 // compute encoded/transmitted message: v = m*G
113 v[0] = 0;
114 for (i=0; i<8; i++) {
115 v[0] <<= 1;
116
117 unsigned int p = liquid_c_ones[ P[8*i+0] & m[0] ] +
118 liquid_c_ones[ P[8*i+1] & m[1] ] +
119 liquid_c_ones[ P[8*i+2] & m[2] ] +
120 liquid_c_ones[ P[8*i+3] & m[3] ] +
121 liquid_c_ones[ P[8*i+4] & m[4] ] +
122 liquid_c_ones[ P[8*i+5] & m[5] ] +
123 liquid_c_ones[ P[8*i+6] & m[6] ] +
124 liquid_c_ones[ P[8*i+7] & m[7] ];
125 //printf("p = %u\n", p);
126 v[0] |= p & 0x01;
127 }
128 for (i=0; i<8; i++)
129 v[i+1] = m[i];
130 printf("v (encoded/transmitted message):\n");
131 print_bitstring(v,72);
132
133 // use pre-determined error vector
134 printf("e (error vector):\n");
135 print_bitstring(e,72);
136
137 // compute received vector: r = v + e
138 for (i=0; i<9; i++)
139 r[i] = v[i] ^ e[i];
140 printf("r (received vector):\n");
141 print_bitstring(r,72);
142
143 // compute syndrome vector, s = r*H^T = ( H*r^T )^T
144 s = 0;
145 for (i=0; i<8; i++) {
146 s <<= 1;
147 unsigned int p =
148 ( (r[0] & (1<<(8-i-1))) ? 1 : 0 )+
149 liquid_c_ones[ P[8*i+0] & r[1] ] +
150 liquid_c_ones[ P[8*i+1] & r[2] ] +
151 liquid_c_ones[ P[8*i+2] & r[3] ] +
152 liquid_c_ones[ P[8*i+3] & r[4] ] +
153 liquid_c_ones[ P[8*i+4] & r[5] ] +
154 liquid_c_ones[ P[8*i+5] & r[6] ] +
155 liquid_c_ones[ P[8*i+6] & r[7] ] +
156 liquid_c_ones[ P[8*i+7] & r[8] ];
157
158 printf("p = %u\n", p);
159
160 s |= p & 0x01;
161 }
162 printf("s (syndrome vector):\n");
163 print_bitstring(&s,8);
164
165 // compute weight of s
166 unsigned int ws = liquid_count_ones(s);
167 printf("w(s) = %u\n", ws);
168
169 // estimated error vector
170 unsigned char e_hat[9] = {0,0,0,0,0,0,0,0,0};
171
172 if (ws == 0) {
173 printf("no errors detected\n");
174 } else {
175 // estimate error location
176 int syndrome_match = 0;
177
178 // TODO : these can be pre-computed
179 unsigned int n;
180 for (n=0; n<72; n++) {
181 // compute syndrome
182 unsigned char e_test[9] = {0,0,0,0,0,0,0,0,0};
183 unsigned char s_hat = 0;
184
185 div_t d = div(n,8);
186 e_test[9-d.quot-1] = 1 << d.rem;
187
188 for (i=0; i<8; i++) {
189 s_hat <<= 1;
190 unsigned int p =
191 ( (e_test[0] & (1<<(8-i-1))) ? 1 : 0 )+
192 liquid_c_ones[ P[8*i+0] & e_test[1] ] +
193 liquid_c_ones[ P[8*i+1] & e_test[2] ] +
194 liquid_c_ones[ P[8*i+2] & e_test[3] ] +
195 liquid_c_ones[ P[8*i+3] & e_test[4] ] +
196 liquid_c_ones[ P[8*i+4] & e_test[5] ] +
197 liquid_c_ones[ P[8*i+5] & e_test[6] ] +
198 liquid_c_ones[ P[8*i+6] & e_test[7] ] +
199 liquid_c_ones[ P[8*i+7] & e_test[8] ];
200
201 s_hat |= p & 0x01;
202 }
203
204 // print results
205 //printf("e_test:"); print_bitstring(e_test, 72);
206 printf("%2u e=", n);
207 for (i=0; i<9; i++) {
208 print_bitstring_short(e_test[i],8);
209 printf(" ");
210 }
211 printf("s=");
212 print_bitstring_short(s_hat,8);
213 if (s == s_hat) printf("*");
214 printf("\n");
215
216 if (s == s_hat) {
217 memmove(e_hat, e_test, 9*sizeof(unsigned char));
218 syndrome_match = 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 vector):\n");
231 print_bitstring(e_hat,72);
232
233 printf("v-hat (estimated transmitted vector):\n");
234 for (i=0; i<9; i++)
235 v_hat[i] = r[i] ^ e_hat[i];
236 print_bitstring(v_hat,72);
237 //print_bitstring(v, 72);
238
239 // compute errors between v, v_hat
240 unsigned int num_errors_encoded = count_bit_errors_array(v, v_hat, 9);
241 printf("decoding errors (encoded) : %2u / 72\n", num_errors_encoded);
242
243 // compute estimated original message: (last 64 bits of encoded message)
244 for (i=0; i<8; i++)
245 m_hat[i] = v_hat[i+1];
246 printf("m-hat (estimated original vector):\n ");
247 print_bitstring(m_hat,64);
248 //print_bitstring(m, 64);
249
250 // compute errors between m, m_hat
251 unsigned int num_errors_decoded = count_bit_errors_array(m, m_hat, 8);
252 printf("decoding errors (original) : %2u / 64\n", num_errors_decoded);
253
254 return 0;
255 }
256
257