1 /* K=9 r=1/2 Viterbi decoder in portable C 2 * Copyright Feb 2004, Phil Karn, KA9Q 3 * May be used under the terms of the GNU Lesser General Public License (LGPL) 4 */ 5 #include <stdio.h> 6 #include <stdlib.h> 7 #include <memory.h> 8 #include "fec.h" 9 10 typedef union { unsigned int w[256]; } metric_t; 11 typedef union { unsigned long w[8];} decision_t; 12 13 static union { unsigned char c[128]; } Branchtab29[2]; 14 static int Init = 0; 15 16 /* State info for instance of Viterbi decoder */ 17 struct v29 { 18 metric_t metrics1; /* path metric buffer 1 */ 19 metric_t metrics2; /* path metric buffer 2 */ 20 decision_t *dp; /* Pointer to current decision */ 21 metric_t *old_metrics,*new_metrics; /* Pointers to path metrics, swapped on every bit */ 22 decision_t *decisions; /* Beginning of decisions for block */ 23 }; 24 25 /* Initialize Viterbi decoder for start of new frame */ 26 int init_viterbi29_port(void *p,int starting_state){ 27 struct v29 *vp = p; 28 int i; 29 30 if(p == NULL) 31 return -1; 32 for(i=0;i<256;i++) 33 vp->metrics1.w[i] = 63; 34 35 vp->old_metrics = &vp->metrics1; 36 vp->new_metrics = &vp->metrics2; 37 vp->dp = vp->decisions; 38 vp->old_metrics->w[starting_state & 255] = 0; /* Bias known start state */ 39 return 0; 40 } 41 42 void set_viterbi29_polynomial_port(int polys[2]){ 43 int state; 44 45 for(state=0;state < 128;state++){ 46 Branchtab29[0].c[state] = (polys[0] < 0) ^ parity((2*state) & abs(polys[0])) ? 255 : 0; 47 Branchtab29[1].c[state] = (polys[1] < 0) ^ parity((2*state) & abs(polys[1])) ? 255 : 0; 48 } 49 Init++; 50 } 51 52 53 /* Create a new instance of a Viterbi decoder */ 54 void *create_viterbi29_port(int len){ 55 struct v29 *vp; 56 57 if(!Init){ 58 int polys[2] = {V29POLYA,V29POLYB}; 59 set_viterbi29_polynomial_port(polys); 60 } 61 if((vp = (struct v29 *)malloc(sizeof(struct v29))) == NULL) 62 return NULL; 63 64 if((vp->decisions = (decision_t *)malloc((len+8)*sizeof(decision_t))) == NULL){ 65 free(vp); 66 return NULL; 67 } 68 init_viterbi29_port(vp,0); 69 70 return vp; 71 } 72 73 74 /* Viterbi chainback */ 75 int chainback_viterbi29_port( 76 void *p, 77 unsigned char *data, /* Decoded output data */ 78 unsigned int nbits, /* Number of data bits */ 79 unsigned int endstate){ /* Terminal encoder state */ 80 struct v29 *vp = p; 81 decision_t *d; 82 83 if(p == NULL) 84 return -1; 85 86 d = vp->decisions; 87 /* Make room beyond the end of the encoder register so we can 88 * accumulate a full byte of decoded data 89 */ 90 endstate %= 256; 91 92 /* The store into data[] only needs to be done every 8 bits. 93 * But this avoids a conditional branch, and the writes will 94 * combine in the cache anyway 95 */ 96 d += 8; /* Look past tail */ 97 while(nbits-- != 0){ 98 int k; 99 100 k = (d[nbits].w[(endstate)/32] >> (endstate%32)) & 1; 101 data[nbits>>3] = endstate = (endstate >> 1) | (k << 7); 102 } 103 return 0; 104 } 105 106 107 /* Delete instance of a Viterbi decoder */ 108 void delete_viterbi29_port(void *p){ 109 struct v29 *vp = p; 110 111 if(vp != NULL){ 112 free(vp->decisions); 113 free(vp); 114 } 115 } 116 117 /* C-language butterfly */ 118 #define BFLY(i) {\ 119 unsigned int metric,m0,m1,decision;\ 120 metric = (Branchtab29[0].c[i] ^ sym0) + (Branchtab29[1].c[i] ^ sym1);\ 121 m0 = vp->old_metrics->w[i] + metric;\ 122 m1 = vp->old_metrics->w[i+128] + (510 - metric);\ 123 decision = (signed int)(m0-m1) > 0;\ 124 vp->new_metrics->w[2*i] = decision ? m1 : m0;\ 125 d->w[i/16] |= decision << ((2*i)&31);\ 126 m0 -= (metric+metric-510);\ 127 m1 += (metric+metric-510);\ 128 decision = (signed int)(m0-m1) > 0;\ 129 vp->new_metrics->w[2*i+1] = decision ? m1 : m0;\ 130 d->w[i/16] |= decision << ((2*i+1)&31);\ 131 } 132 133 /* Update decoder with a block of demodulated symbols 134 * Note that nbits is the number of decoded data bits, not the number 135 * of symbols! 136 */ 137 138 int update_viterbi29_blk_port(void *p,unsigned char *syms,int nbits){ 139 struct v29 *vp = p; 140 decision_t *d; 141 142 if(p == NULL) 143 return -1; 144 145 d = (decision_t *)vp->dp; 146 while(nbits--){ 147 void *tmp; 148 unsigned char sym0,sym1; 149 int i; 150 151 for(i=0;i<8;i++) 152 d->w[i] = 0; 153 sym0 = *syms++; 154 sym1 = *syms++; 155 156 for(i=0;i<128;i++) 157 BFLY(i); 158 159 d++; 160 tmp = vp->old_metrics; 161 vp->old_metrics = vp->new_metrics; 162 vp->new_metrics = tmp; 163 } 164 vp->dp = d; 165 return 0; 166 } 167
