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 // 1/2-rate (7,4) Hamming code
25 //
26
27 #include <stdio.h>
28 #include <stdlib.h>
29 #include <assert.h>
30
31 #include "liquid.internal.h"
32
33 // encoder look-up table
34 unsigned char hamming74_enc_gentab[16] = {
35 0x00, 0x69, 0x2a, 0x43, 0x4c, 0x25, 0x66, 0x0f,
36 0x70, 0x19, 0x5a, 0x33, 0x3c, 0x55, 0x16, 0x7f};
37
38 // decoder look-up table
39 unsigned char hamming74_dec_gentab[128] = {
40 0x00, 0x00, 0x00, 0x03, 0x00, 0x05, 0x0e, 0x07,
41 0x00, 0x09, 0x02, 0x07, 0x04, 0x07, 0x07, 0x07,
42 0x00, 0x09, 0x0e, 0x0b, 0x0e, 0x0d, 0x0e, 0x0e,
43 0x09, 0x09, 0x0a, 0x09, 0x0c, 0x09, 0x0e, 0x07,
44 0x00, 0x05, 0x02, 0x0b, 0x05, 0x05, 0x06, 0x05,
45 0x02, 0x01, 0x02, 0x02, 0x0c, 0x05, 0x02, 0x07,
46 0x08, 0x0b, 0x0b, 0x0b, 0x0c, 0x05, 0x0e, 0x0b,
47 0x0c, 0x09, 0x02, 0x0b, 0x0c, 0x0c, 0x0c, 0x0f,
48 0x00, 0x03, 0x03, 0x03, 0x04, 0x0d, 0x06, 0x03,
49 0x04, 0x01, 0x0a, 0x03, 0x04, 0x04, 0x04, 0x07,
50 0x08, 0x0d, 0x0a, 0x03, 0x0d, 0x0d, 0x0e, 0x0d,
51 0x0a, 0x09, 0x0a, 0x0a, 0x04, 0x0d, 0x0a, 0x0f,
52 0x08, 0x01, 0x06, 0x03, 0x06, 0x05, 0x06, 0x06,
53 0x01, 0x01, 0x02, 0x01, 0x04, 0x01, 0x06, 0x0f,
54 0x08, 0x08, 0x08, 0x0b, 0x08, 0x0d, 0x06, 0x0f,
55 0x08, 0x01, 0x0a, 0x0f, 0x0c, 0x0f, 0x0f, 0x0f};
56
57 // create Hamming(7,4) codec object
fec_hamming74_create(void * _opts)58 fec fec_hamming74_create(void * _opts)
59 {
60 fec q = (fec) malloc(sizeof(struct fec_s));
61
62 // set scheme
63 q->scheme = LIQUID_FEC_HAMMING74;
64 q->rate = fec_get_rate(q->scheme);
65
66 // set internal function pointers
67 q->encode_func = &fec_hamming74_encode;
68 q->decode_func = &fec_hamming74_decode;
69 q->decode_soft_func = &fec_hamming74_decode_soft;
70
71 return q;
72 }
73
74 // destroy Hamming(7,4) object
fec_hamming74_destroy(fec _q)75 void fec_hamming74_destroy(fec _q)
76 {
77 free(_q);
78 }
79
80 // encode block of data using Hamming(7,4) encoder
81 //
82 // _q : encoder/decoder object
83 // _dec_msg_len : decoded message length (number of bytes)
84 // _msg_dec : decoded message [size: _dec_msg_len x 1]
85 // _msg_enc : encoded message [size: ...]
fec_hamming74_encode(fec _q,unsigned int _dec_msg_len,unsigned char * _msg_dec,unsigned char * _msg_enc)86 void fec_hamming74_encode(fec _q,
87 unsigned int _dec_msg_len,
88 unsigned char *_msg_dec,
89 unsigned char *_msg_enc)
90 {
91 unsigned int i; // input byte counter
92 unsigned int k=0; // array bit index
93
94 // compute encoded message length
95 unsigned int enc_msg_len = fec_block_get_enc_msg_len(_dec_msg_len,4,7);
96
97 unsigned char s0, s1; // decoded symbols
98 unsigned char m0, m1; // encoded symbols
99
100 for (i=0; i<_dec_msg_len; i++) {
101 // strip two 4-bit symbols from input byte
102 s0 = (_msg_dec[i] >> 4) & 0x0f;
103 s1 = (_msg_dec[i] >> 0) & 0x0f;
104
105 // encode two 7-bit symbols
106 m0 = hamming74_enc_gentab[s0];
107 m1 = hamming74_enc_gentab[s1];
108
109 // pack encoded symbols into output array
110 liquid_pack_array(_msg_enc, enc_msg_len, k, 7, m0);
111 k += 7;
112 liquid_pack_array(_msg_enc, enc_msg_len, k, 7, m1);
113 k += 7;
114
115 //printf(" %3u : 0x%.2x > 0x%.2x, 0x%.2x > 0x%.2x (k=%u)\n", i, s0, m0, s1, m1, k);
116 }
117 }
118
119 // decode block of data using Hamming(7,4) decoder
120 //
121 // _q : encoder/decoder object
122 // _dec_msg_len : decoded message length (number of bytes)
123 // _msg_enc : encoded message [size: ...]
124 // _msg_dec : decoded message [size: _dec_msg_len x 1]
125 //
126 //unsigned int
fec_hamming74_decode(fec _q,unsigned int _dec_msg_len,unsigned char * _msg_enc,unsigned char * _msg_dec)127 void fec_hamming74_decode(fec _q,
128 unsigned int _dec_msg_len,
129 unsigned char *_msg_enc,
130 unsigned char *_msg_dec)
131 {
132 unsigned int i;
133 unsigned int k=0; // array bit index
134
135 // compute encoded message length
136 unsigned int enc_msg_len = fec_block_get_enc_msg_len(_dec_msg_len,4,7);
137
138 unsigned char r0, r1; // received 7-bit symbols
139 unsigned char s0, s1; // decoded 4-bit symbols
140
141 //unsigned char num_errors=0;
142 for (i=0; i<_dec_msg_len; i++) {
143 // strip two 7-bit symbols from
144 liquid_unpack_array(_msg_enc, enc_msg_len, k, 7, &r0);
145 k += 7;
146 liquid_unpack_array(_msg_enc, enc_msg_len, k, 7, &r1);
147 k += 7;
148
149 s0 = hamming74_dec_gentab[r0];
150 s1 = hamming74_dec_gentab[r1];
151
152 _msg_dec[i] = (s0 << 4) | s1;
153
154 //printf(" %3u : 0x%.2x > 0x%.2x, 0x%.2x > 0x%.2x (k=%u)\n", i, r0, s0, r1, s1, k);
155 }
156 //return num_errors;
157 }
158
159 // decode block of data using Hamming(7,4) soft decoder
160 //
161 // _q : encoder/decoder object
162 // _dec_msg_len : decoded message length (number of bytes)
163 // _msg_enc : encoded message [size: 8*_enc_msg_len x 1]
164 // _msg_dec : decoded message [size: _dec_msg_len x 1]
165 //
166 //unsigned int
fec_hamming74_decode_soft(fec _q,unsigned int _dec_msg_len,unsigned char * _msg_enc,unsigned char * _msg_dec)167 void fec_hamming74_decode_soft(fec _q,
168 unsigned int _dec_msg_len,
169 unsigned char *_msg_enc,
170 unsigned char *_msg_dec)
171 {
172 unsigned int i;
173 unsigned int k=0; // array bit index
174
175 // compute encoded message length
176 unsigned int enc_msg_len = fec_block_get_enc_msg_len(_dec_msg_len,4,7);
177
178 // decoded 4-bit symbols
179 unsigned char s0;
180 unsigned char s1;
181
182 //unsigned char num_errors=0;
183 for (i=0; i<_dec_msg_len; i++) {
184 s0 = fecsoft_hamming74_decode(&_msg_enc[k ]);
185 s1 = fecsoft_hamming74_decode(&_msg_enc[k+7]);
186 k += 14;
187
188 // pack two 4-bit symbols into one 8-bit byte
189 _msg_dec[i] = (s0 << 4) | s1;
190
191 //printf(" %3u : 0x%.2x > 0x%.2x, 0x%.2x > 0x%.2x (k=%u)\n", i, r0, s0, r1, s1, k);
192 }
193 assert(k == 8*enc_msg_len);
194 //return num_errors;
195 }
196
197 //
198 // internal methods
199 //
200
201 // soft decoding of one symbol
fecsoft_hamming74_decode(unsigned char * _soft_bits)202 unsigned char fecsoft_hamming74_decode(unsigned char * _soft_bits)
203 {
204 // find symbol with minimum distance from all 2^4 possible
205 unsigned int d; // distance metric
206 unsigned int dmin = 0; // minimum distance
207 unsigned char s_hat = 0; // estimated transmitted symbol
208 unsigned char c; // encoded symbol
209
210 unsigned char s;
211 for (s=0; s<16; s++) {
212 // encode symbol
213 c = hamming74_enc_gentab[s];
214
215 // compute distance metric
216 d = 0;
217 d += (c & 0x40) ? 255 - _soft_bits[0] : _soft_bits[0];
218 d += (c & 0x20) ? 255 - _soft_bits[1] : _soft_bits[1];
219 d += (c & 0x10) ? 255 - _soft_bits[2] : _soft_bits[2];
220 d += (c & 0x08) ? 255 - _soft_bits[3] : _soft_bits[3];
221 d += (c & 0x04) ? 255 - _soft_bits[4] : _soft_bits[4];
222 d += (c & 0x02) ? 255 - _soft_bits[5] : _soft_bits[5];
223 d += (c & 0x01) ? 255 - _soft_bits[6] : _soft_bits[6];
224
225 if (d < dmin || s==0) {
226 s_hat = s;
227 dmin = d;
228 }
229 }
230 return s_hat;
231 }
232