4 * Generic convolutional encoding / decoding
6 * Copyright (C) 2011 Sylvain Munaut <tnt@246tNt.com>
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.
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.
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.
30 #include <osmocom/core/bits.h>
31 #include <osmocom/core/conv.h>
34 /* ------------------------------------------------------------------------ */
36 /* ------------------------------------------------------------------------ */
39 osmo_conv_encode_init(struct osmo_conv_encoder *encoder,
40 const struct osmo_conv_code *code)
42 memset(encoder, 0x00, sizeof(struct osmo_conv_encoder));
47 _conv_encode_do_output(struct osmo_conv_encoder *encoder,
48 uint8_t out, ubit_t *output)
50 const struct osmo_conv_code *code = encoder->code;
55 for (j=0; j<code->N; j++)
57 int bit_no = code->N - j - 1;
58 int r_idx = encoder->i_idx * code->N + j;
60 if (code->puncture[encoder->p_idx] == r_idx)
63 output[o_idx++] = (out >> bit_no) & 1;
66 for (j=0; j<code->N; j++)
68 int bit_no = code->N - j - 1;
69 output[o_idx++] = (out >> bit_no) & 1;
77 osmo_conv_encode_raw(struct osmo_conv_encoder *encoder,
78 const ubit_t *input, ubit_t *output, int n)
80 const struct osmo_conv_code *code = encoder->code;
86 state = encoder->state;
92 out = code->next_output[state][bit];
93 state = code->next_state[state][bit];
95 o_idx += _conv_encode_do_output(encoder, out, &output[o_idx]);
100 encoder->state = state;
106 osmo_conv_encode_finish(struct osmo_conv_encoder *encoder,
109 const struct osmo_conv_code *code = encoder->code;
118 state = encoder->state;
120 for (i=0; i<n; i++) {
123 if (code->next_term_output) {
124 out = code->next_term_output[state];
125 state = code->next_term_state[state];
127 out = code->next_output[state][0];
128 state = code->next_state[state][0];
131 o_idx += _conv_encode_do_output(encoder, out, &output[o_idx]);
136 encoder->state = state;
142 osmo_conv_encode(const struct osmo_conv_code *code,
143 const ubit_t *input, ubit_t *output)
145 struct osmo_conv_encoder encoder;
148 osmo_conv_encode_init(&encoder, code);
149 l = osmo_conv_encode_raw(&encoder, input, output, code->len);
150 l += osmo_conv_encode_finish(&encoder, &output[l]);
156 /* ------------------------------------------------------------------------ */
157 /* Decoding (viterbi) */
158 /* ------------------------------------------------------------------------ */
160 #define MAX_AE 0x00ffffff
163 osmo_conv_decode_init(struct osmo_conv_decoder *decoder,
164 const struct osmo_conv_code *code, int len)
172 n_states = 1 << (code->K - 1);
174 memset(decoder, 0x00, sizeof(struct osmo_conv_decoder));
176 decoder->code = code;
177 decoder->n_states = n_states;
180 /* Allocate arrays */
181 decoder->ae = malloc(sizeof(unsigned int) * n_states);
182 decoder->ae_next = malloc(sizeof(unsigned int) * n_states);
184 decoder->state_history = malloc(sizeof(uint8_t) * n_states * (len + decoder->code->K - 1));
187 osmo_conv_decode_reset(decoder);
191 osmo_conv_decode_reset(struct osmo_conv_decoder *decoder)
199 /* Initial error (only state 0 is valid) */
201 for (i=1; i<decoder->n_states; i++) {
202 decoder->ae[i] = MAX_AE;
207 osmo_conv_decode_deinit(struct osmo_conv_decoder *decoder)
210 free(decoder->ae_next);
211 free(decoder->state_history);
213 memset(decoder, 0x00, sizeof(struct osmo_conv_decoder));
217 osmo_conv_decode_scan(struct osmo_conv_decoder *decoder,
218 const sbit_t *input, int n)
220 const struct osmo_conv_code *code = decoder->code;
226 unsigned int *ae_next;
227 uint8_t *state_history;
233 n_states = decoder->n_states;
236 ae_next = decoder->ae_next;
237 state_history = &decoder->state_history[n_states * decoder->o_idx];
239 in_sym = alloca(sizeof(sbit_t) * code->N);
242 p_idx = decoder->p_idx;
244 /* Scan the treillis */
247 /* Reset next accumulated error */
248 for (s=0; s<n_states; s++) {
253 if (code->puncture) {
255 for (j=0; j<code->N; j++) {
256 int idx = ((decoder->o_idx + i) * code->N) + j;
257 if (idx == code->puncture[p_idx]) {
258 in_sym[j] = 0; /* Undefined */
261 in_sym[j] = input[i_idx];
266 /* Easy, just copy N bits */
267 memcpy(in_sym, &input[i_idx], code->N);
272 for (s=0; s<n_states; s++)
274 /* Scan possible input bits */
280 /* Next output and state */
281 uint8_t out = code->next_output[s][b];
282 uint8_t state = code->next_state[s][b];
284 /* New error for this path */
285 nae = ae[s]; /* start from last error */
286 m = 1 << (code->N - 1); /* mask for 'out' bit selection */
288 for (j=0; j<code->N; j++) {
289 ov = (out & m) ? -127 : 127; /* sbit_t value for it */
290 e = ((int)in_sym[j]) - ov; /* raw error for this bit */
291 nae += (e * e) >> 9; /* acc the squared/scaled value */
292 m >>= 1; /* next mask bit */
295 /* Is it survivor ? */
296 if (ae_next[state] > nae) {
297 ae_next[state] = nae;
298 state_history[(n_states * i) + state] = s;
303 /* Copy accumulated error */
304 memcpy(ae, ae_next, sizeof(unsigned int) * n_states);
307 /* Update decoder state */
308 decoder->p_idx = p_idx;
315 osmo_conv_decode_finish(struct osmo_conv_decoder *decoder,
318 const struct osmo_conv_code *code = decoder->code;
324 unsigned int *ae_next;
325 uint8_t *state_history;
331 n_states = decoder->n_states;
334 ae_next = decoder->ae_next;
335 state_history = &decoder->state_history[n_states * decoder->o_idx];
337 in_sym = alloca(sizeof(sbit_t) * code->N);
340 p_idx = decoder->p_idx;
342 /* Scan the treillis */
343 for (i=0; i<code->K-1; i++)
345 /* Reset next accumulated error */
346 for (s=0; s<n_states; s++) {
351 if (code->puncture) {
353 for (j=0; j<code->N; j++) {
354 int idx = ((decoder->o_idx + i) * code->N) + j;
355 if (idx == code->puncture[p_idx]) {
356 in_sym[j] = 0; /* Undefined */
359 in_sym[j] = input[i_idx];
364 /* Easy, just copy N bits */
365 memcpy(in_sym, &input[i_idx], code->N);
370 for (s=0; s<n_states; s++)
375 /* Next output and state */
379 if (code->next_term_output) {
380 out = code->next_term_output[s];
381 state = code->next_term_state[s];
383 out = code->next_output[s][0];
384 state = code->next_state[s][0];
387 /* New error for this path */
388 nae = ae[s]; /* start from last error */
389 m = 1 << (code->N - 1); /* mask for 'out' bit selection */
391 for (j=0; j<code->N; j++) {
392 int is = (int)in_sym[j];
394 ov = (out & m) ? -127 : 127; /* sbit_t value for it */
395 e = is - ov; /* raw error for this bit */
396 nae += (e * e) >> 9; /* acc the squared/scaled value */
398 m >>= 1; /* next mask bit */
401 /* Is it survivor ? */
402 if (ae_next[state] > nae) {
403 ae_next[state] = nae;
404 state_history[(n_states * i) + state] = s;
408 /* Copy accumulated error */
409 memcpy(ae, ae_next, sizeof(unsigned int) * n_states);
412 /* Update decoder state */
413 decoder->p_idx = p_idx;
414 decoder->o_idx += code->K - 1;
420 osmo_conv_decode_get_output(struct osmo_conv_decoder *decoder,
421 ubit_t *output, int has_finish)
423 const struct osmo_conv_code *code = decoder->code;
426 uint8_t min_state, cur_state;
431 /* Find state with least error */
435 for (s=0; s<decoder->n_states; s++)
437 if (decoder->ae[s] < min_ae) {
438 min_ae = decoder->ae[s];
443 if (min_state == 0xff)
447 cur_state = min_state;
451 sh_ptr = &decoder->state_history[decoder->n_states * (n-1)];
453 /* No output for the K-1 termination input bits */
455 for (i=0; i<code->K-1; i++) {
456 cur_state = sh_ptr[cur_state];
457 sh_ptr -= decoder->n_states;
462 /* Generate output backward */
463 for (i=n-1; i>=0; i--)
465 min_state = cur_state;
466 cur_state = sh_ptr[cur_state];
468 sh_ptr -= decoder->n_states;
470 if (code->next_state[cur_state][0] == min_state)
480 osmo_conv_decode(const struct osmo_conv_code *code,
481 const sbit_t *input, ubit_t *output)
483 struct osmo_conv_decoder decoder;
486 osmo_conv_decode_init(&decoder, code, 0);
488 l = osmo_conv_decode_scan(&decoder, input, code->len);
489 l = osmo_conv_decode_finish(&decoder, &input[l]);
491 rv = osmo_conv_decode_get_output(&decoder, output, 1);
493 osmo_conv_decode_deinit(&decoder);