blob: 7a8be8cae25f12878d3c5f640680915f471ea865 [file] [log] [blame]
Sylvain Munaut19dc5c92011-04-23 16:09:19 +02001/*
2 * conv.c
3 *
4 * Generic convolutional encoding / decoding
5 *
6 * Copyright (C) 2011 Sylvain Munaut <tnt@246tNt.com>
7 *
8 * All Rights Reserved
9 *
10 * This program is free software; you can redistribute it and/or modify
11 * it under the terms of the GNU General Public License as published by
12 * the Free Software Foundation; either version 2 of the License, or
13 * (at your option) any later version.
14 *
15 * This program is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 * GNU General Public License for more details.
19 *
20 * You should have received a copy of the GNU General Public License along
21 * with this program; if not, write to the Free Software Foundation, Inc.,
22 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
23 */
24
Harald Welteba6988b2011-08-17 12:46:48 +020025/*! \addtogroup conv
26 * @{
27 */
28
29/*! \file conv.c
30 * \file Osmocom convolutional encoder and decoder
31 */
Holger Hans Peter Freyther47723482011-11-09 11:26:15 +010032#include "config.h"
33#ifdef HAVE_ALLOCA_H
Sylvain Munaut19dc5c92011-04-23 16:09:19 +020034#include <alloca.h>
Holger Hans Peter Freyther47723482011-11-09 11:26:15 +010035#endif
Sylvain Munaut19dc5c92011-04-23 16:09:19 +020036#include <stdint.h>
37#include <stdlib.h>
38#include <string.h>
39
40#include <osmocom/core/bits.h>
41#include <osmocom/core/conv.h>
42
43
44/* ------------------------------------------------------------------------ */
45/* Encoding */
46/* ------------------------------------------------------------------------ */
47
Harald Welteba6988b2011-08-17 12:46:48 +020048/*! \brief Initialize a convolutional encoder
49 * \param[in,out] encoder Encoder state to initialize
50 * \param[in] code Description of convolutional code
51 */
Sylvain Munaut19dc5c92011-04-23 16:09:19 +020052void
53osmo_conv_encode_init(struct osmo_conv_encoder *encoder,
54 const struct osmo_conv_code *code)
55{
56 memset(encoder, 0x00, sizeof(struct osmo_conv_encoder));
57 encoder->code = code;
58}
59
60static inline int
61_conv_encode_do_output(struct osmo_conv_encoder *encoder,
62 uint8_t out, ubit_t *output)
63{
64 const struct osmo_conv_code *code = encoder->code;
65 int o_idx = 0;
66 int j;
67
68 if (code->puncture) {
69 for (j=0; j<code->N; j++)
70 {
71 int bit_no = code->N - j - 1;
72 int r_idx = encoder->i_idx * code->N + j;
73
74 if (code->puncture[encoder->p_idx] == r_idx)
75 encoder->p_idx++;
76 else
77 output[o_idx++] = (out >> bit_no) & 1;
78 }
79 } else {
80 for (j=0; j<code->N; j++)
81 {
82 int bit_no = code->N - j - 1;
83 output[o_idx++] = (out >> bit_no) & 1;
84 }
85 }
86
87 return o_idx;
88}
89
90int
91osmo_conv_encode_raw(struct osmo_conv_encoder *encoder,
92 const ubit_t *input, ubit_t *output, int n)
93{
94 const struct osmo_conv_code *code = encoder->code;
95 uint8_t state;
96 int i;
97 int o_idx;
98
99 o_idx = 0;
100 state = encoder->state;
101
102 for (i=0; i<n; i++) {
103 int bit = input[i];
104 uint8_t out;
105
106 out = code->next_output[state][bit];
107 state = code->next_state[state][bit];
108
109 o_idx += _conv_encode_do_output(encoder, out, &output[o_idx]);
110
111 encoder->i_idx++;
112 }
113
114 encoder->state = state;
115
116 return o_idx;
117}
118
119int
120osmo_conv_encode_finish(struct osmo_conv_encoder *encoder,
121 ubit_t *output)
122{
123 const struct osmo_conv_code *code = encoder->code;
124 uint8_t state;
125 int n;
126 int i;
127 int o_idx;
128
129 n = code->K - 1;
130
131 o_idx = 0;
132 state = encoder->state;
133
134 for (i=0; i<n; i++) {
135 uint8_t out;
136
137 if (code->next_term_output) {
138 out = code->next_term_output[state];
139 state = code->next_term_state[state];
140 } else {
141 out = code->next_output[state][0];
142 state = code->next_state[state][0];
143 }
144
145 o_idx += _conv_encode_do_output(encoder, out, &output[o_idx]);
146
147 encoder->i_idx++;
148 }
149
150 encoder->state = state;
151
152 return o_idx;
153}
154
Harald Welteba6988b2011-08-17 12:46:48 +0200155/*! \brief All-in-one convolutional encoding function
156 * \param[in] code description of convolutional code to be used
157 * \param[in] input array of unpacked bits (uncoded)
158 * \param[out] output array of unpacked bits (encoded)
Sylvain Munaut03d2c892011-11-24 11:53:49 +0100159 * \return Number of produced output bits
Harald Welteba6988b2011-08-17 12:46:48 +0200160 *
161 * This is an all-in-one function, taking care of
162 * \ref osmo_conv_init, \ref osmo_conv_encode_raw and
163 * \ref osmo_conv_encode_finish.
164 */
Sylvain Munaut19dc5c92011-04-23 16:09:19 +0200165int
166osmo_conv_encode(const struct osmo_conv_code *code,
167 const ubit_t *input, ubit_t *output)
168{
169 struct osmo_conv_encoder encoder;
170 int l;
171
172 osmo_conv_encode_init(&encoder, code);
173 l = osmo_conv_encode_raw(&encoder, input, output, code->len);
174 l += osmo_conv_encode_finish(&encoder, &output[l]);
175
176 return l;
177}
178
179
180/* ------------------------------------------------------------------------ */
181/* Decoding (viterbi) */
182/* ------------------------------------------------------------------------ */
183
184#define MAX_AE 0x00ffffff
185
186void
187osmo_conv_decode_init(struct osmo_conv_decoder *decoder,
188 const struct osmo_conv_code *code, int len)
189{
190 int n_states;
191
192 /* Init */
193 if (len <= 0)
194 len = code->len;
195
196 n_states = 1 << (code->K - 1);
197
198 memset(decoder, 0x00, sizeof(struct osmo_conv_decoder));
199
200 decoder->code = code;
201 decoder->n_states = n_states;
202 decoder->len = len;
203
204 /* Allocate arrays */
205 decoder->ae = malloc(sizeof(unsigned int) * n_states);
206 decoder->ae_next = malloc(sizeof(unsigned int) * n_states);
207
208 decoder->state_history = malloc(sizeof(uint8_t) * n_states * (len + decoder->code->K - 1));
209
210 /* Classic reset */
211 osmo_conv_decode_reset(decoder);
212}
213
214void
215osmo_conv_decode_reset(struct osmo_conv_decoder *decoder)
216{
217 int i;
218
219 /* Reset indexes */
220 decoder->o_idx = 0;
221 decoder->p_idx = 0;
222
223 /* Initial error (only state 0 is valid) */
224 decoder->ae[0] = 0;
225 for (i=1; i<decoder->n_states; i++) {
226 decoder->ae[i] = MAX_AE;
227 }
228}
229
230void
231osmo_conv_decode_deinit(struct osmo_conv_decoder *decoder)
232{
233 free(decoder->ae);
234 free(decoder->ae_next);
235 free(decoder->state_history);
236
237 memset(decoder, 0x00, sizeof(struct osmo_conv_decoder));
238}
239
240int
241osmo_conv_decode_scan(struct osmo_conv_decoder *decoder,
242 const sbit_t *input, int n)
243{
244 const struct osmo_conv_code *code = decoder->code;
245
246 int i, s, b, j;
247
248 int n_states;
249 unsigned int *ae;
250 unsigned int *ae_next;
251 uint8_t *state_history;
252 sbit_t *in_sym;
253
254 int i_idx, p_idx;
255
256 /* Prepare */
257 n_states = decoder->n_states;
258
259 ae = decoder->ae;
260 ae_next = decoder->ae_next;
261 state_history = &decoder->state_history[n_states * decoder->o_idx];
262
263 in_sym = alloca(sizeof(sbit_t) * code->N);
264
265 i_idx = 0;
266 p_idx = decoder->p_idx;
267
268 /* Scan the treillis */
269 for (i=0; i<n; i++)
270 {
271 /* Reset next accumulated error */
272 for (s=0; s<n_states; s++) {
273 ae_next[s] = MAX_AE;
274 }
275
276 /* Get input */
277 if (code->puncture) {
278 /* Hard way ... */
279 for (j=0; j<code->N; j++) {
280 int idx = ((decoder->o_idx + i) * code->N) + j;
281 if (idx == code->puncture[p_idx]) {
282 in_sym[j] = 0; /* Undefined */
283 p_idx++;
284 } else {
285 in_sym[j] = input[i_idx];
286 i_idx++;
287 }
288 }
289 } else {
290 /* Easy, just copy N bits */
291 memcpy(in_sym, &input[i_idx], code->N);
292 i_idx += code->N;
293 }
294
295 /* Scan all state */
296 for (s=0; s<n_states; s++)
297 {
298 /* Scan possible input bits */
299 for (b=0; b<2; b++)
300 {
301 int nae, ov, e;
302 uint8_t m;
303
304 /* Next output and state */
305 uint8_t out = code->next_output[s][b];
306 uint8_t state = code->next_state[s][b];
307
308 /* New error for this path */
309 nae = ae[s]; /* start from last error */
310 m = 1 << (code->N - 1); /* mask for 'out' bit selection */
311
312 for (j=0; j<code->N; j++) {
Sylvain Munautd4440d42011-11-24 16:04:58 +0100313 int is = (int)in_sym[j];
314 if (is) {
315 ov = (out & m) ? -127 : 127; /* sbit_t value for it */
316 e = is - ov; /* raw error for this bit */
317 nae += (e * e) >> 9; /* acc the squared/scaled value */
318 }
Sylvain Munaut19dc5c92011-04-23 16:09:19 +0200319 m >>= 1; /* next mask bit */
320 }
321
322 /* Is it survivor ? */
323 if (ae_next[state] > nae) {
324 ae_next[state] = nae;
325 state_history[(n_states * i) + state] = s;
326 }
327 }
328 }
329
330 /* Copy accumulated error */
331 memcpy(ae, ae_next, sizeof(unsigned int) * n_states);
332 }
333
334 /* Update decoder state */
335 decoder->p_idx = p_idx;
336 decoder->o_idx += n;
337
338 return i_idx;
339}
340
341int
342osmo_conv_decode_finish(struct osmo_conv_decoder *decoder,
343 const sbit_t *input)
344{
345 const struct osmo_conv_code *code = decoder->code;
346
347 int i, s, j;
348
349 int n_states;
350 unsigned int *ae;
351 unsigned int *ae_next;
352 uint8_t *state_history;
353 sbit_t *in_sym;
354
355 int i_idx, p_idx;
356
357 /* Prepare */
358 n_states = decoder->n_states;
359
360 ae = decoder->ae;
361 ae_next = decoder->ae_next;
362 state_history = &decoder->state_history[n_states * decoder->o_idx];
363
364 in_sym = alloca(sizeof(sbit_t) * code->N);
365
366 i_idx = 0;
367 p_idx = decoder->p_idx;
368
369 /* Scan the treillis */
370 for (i=0; i<code->K-1; i++)
371 {
372 /* Reset next accumulated error */
373 for (s=0; s<n_states; s++) {
374 ae_next[s] = MAX_AE;
375 }
376
377 /* Get input */
378 if (code->puncture) {
379 /* Hard way ... */
380 for (j=0; j<code->N; j++) {
381 int idx = ((decoder->o_idx + i) * code->N) + j;
382 if (idx == code->puncture[p_idx]) {
383 in_sym[j] = 0; /* Undefined */
384 p_idx++;
385 } else {
386 in_sym[j] = input[i_idx];
387 i_idx++;
388 }
389 }
390 } else {
391 /* Easy, just copy N bits */
392 memcpy(in_sym, &input[i_idx], code->N);
393 i_idx += code->N;
394 }
395
396 /* Scan all state */
397 for (s=0; s<n_states; s++)
398 {
399 int nae, ov, e;
400 uint8_t m;
401
402 /* Next output and state */
403 uint8_t out;
404 uint8_t state;
405
406 if (code->next_term_output) {
407 out = code->next_term_output[s];
408 state = code->next_term_state[s];
409 } else {
410 out = code->next_output[s][0];
411 state = code->next_state[s][0];
412 }
413
414 /* New error for this path */
415 nae = ae[s]; /* start from last error */
416 m = 1 << (code->N - 1); /* mask for 'out' bit selection */
417
418 for (j=0; j<code->N; j++) {
Sylvain Munaut1dd7c842011-04-28 22:30:30 +0200419 int is = (int)in_sym[j];
420 if (is) {
421 ov = (out & m) ? -127 : 127; /* sbit_t value for it */
422 e = is - ov; /* raw error for this bit */
423 nae += (e * e) >> 9; /* acc the squared/scaled value */
424 }
Sylvain Munaut19dc5c92011-04-23 16:09:19 +0200425 m >>= 1; /* next mask bit */
426 }
427
428 /* Is it survivor ? */
429 if (ae_next[state] > nae) {
430 ae_next[state] = nae;
431 state_history[(n_states * i) + state] = s;
432 }
433 }
434
435 /* Copy accumulated error */
436 memcpy(ae, ae_next, sizeof(unsigned int) * n_states);
437 }
438
439 /* Update decoder state */
440 decoder->p_idx = p_idx;
441 decoder->o_idx += code->K - 1;
442
443 return i_idx;
444}
445
446int
447osmo_conv_decode_get_output(struct osmo_conv_decoder *decoder,
448 ubit_t *output, int has_finish)
449{
450 const struct osmo_conv_code *code = decoder->code;
451
452 int min_ae;
453 uint8_t min_state, cur_state;
454 int i, s, n;
455
456 uint8_t *sh_ptr;
457
458 /* Find state with least error */
459 min_ae = MAX_AE;
460 min_state = 0xff;
461
462 for (s=0; s<decoder->n_states; s++)
463 {
464 if (decoder->ae[s] < min_ae) {
465 min_ae = decoder->ae[s];
466 min_state = s;
467 }
468 }
469
470 if (min_state == 0xff)
471 return -1;
472
473 /* Traceback */
474 cur_state = min_state;
475
476 n = decoder->o_idx;
477
478 sh_ptr = &decoder->state_history[decoder->n_states * (n-1)];
479
480 /* No output for the K-1 termination input bits */
481 if (has_finish) {
482 for (i=0; i<code->K-1; i++) {
483 cur_state = sh_ptr[cur_state];
484 sh_ptr -= decoder->n_states;
485 }
486 n -= code->K - 1;
487 }
488
489 /* Generate output backward */
490 for (i=n-1; i>=0; i--)
491 {
492 min_state = cur_state;
493 cur_state = sh_ptr[cur_state];
494
495 sh_ptr -= decoder->n_states;
496
497 if (code->next_state[cur_state][0] == min_state)
498 output[i] = 0;
499 else
500 output[i] = 1;
501 }
502
503 return min_ae;
504}
505
Harald Welteba6988b2011-08-17 12:46:48 +0200506/*! \brief All-in-one convolutional decoding function
507 * \param[in] code description of convolutional code to be used
508 * \param[in] input array of soft bits (coded)
509 * \param[out] output array of unpacked bits (decoded)
510 *
511 * This is an all-in-one function, taking care of
512 * \ref osmo_conv_decode_init, \ref osmo_conv_decode_scan,
513 * \ref osmo_conv_decode_finish, \ref osmo_conv_decode_get_output and
514 * \ref osmo_conv_decode_deinit.
515 */
Sylvain Munaut19dc5c92011-04-23 16:09:19 +0200516int
517osmo_conv_decode(const struct osmo_conv_code *code,
518 const sbit_t *input, ubit_t *output)
519{
520 struct osmo_conv_decoder decoder;
521 int rv, l;
522
523 osmo_conv_decode_init(&decoder, code, 0);
524
525 l = osmo_conv_decode_scan(&decoder, input, code->len);
526 l = osmo_conv_decode_finish(&decoder, &input[l]);
527
528 rv = osmo_conv_decode_get_output(&decoder, output, 1);
529
530 osmo_conv_decode_deinit(&decoder);
531
532 return rv;
533}
Harald Welteba6988b2011-08-17 12:46:48 +0200534
535/*! }@ */