1 /* K=15 r=1/6 Viterbi decoder in portable C 2 * Copyright Mar 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 <limits.h> 9 #include "fec.h" 10 11 typedef union { unsigned long w[512]; unsigned char c[2048];} decision_t; 12 typedef union { unsigned long w[16384]; } metric_t; 13 14 static union branchtab615 { unsigned long w[8192]; } Branchtab615[6] __attribute__ ((aligned(16))); 15 static int Init = 0; 16 17 /* State info for instance of Viterbi decoder */ 18 struct v615 { 19 metric_t metrics1; /* path metric buffer 1 */ 20 metric_t metrics2; /* path metric buffer 2 */ 21 decision_t *dp; /* Pointer to current decision */ 22 metric_t *old_metrics,*new_metrics; /* Pointers to path metrics, swapped on every bit */ 23 decision_t *decisions; /* Beginning of decisions for block */ 24 }; 25 26 /* Create a new instance of a Viterbi decoder */ 27 void *create_viterbi615_port(int len){ 28 struct v615 *vp; 29 30 if(!Init){ 31 int polys[6] = { V615POLYA,V615POLYB,V615POLYC,V615POLYD,V615POLYE,V615POLYF }; 32 set_viterbi615_polynomial_port(polys); 33 } 34 if((vp = (struct v615 *)malloc(sizeof(struct v615))) == NULL) 35 return NULL; 36 if((vp->decisions = malloc((len+14)*sizeof(decision_t))) == NULL){ 37 free(vp); 38 return NULL; 39 } 40 init_viterbi615(vp,0); 41 return vp; 42 } 43 44 void set_viterbi615_polynomial_port(int polys[6]){ 45 int state; 46 int i; 47 48 for(state=0;state < 8192;state++){ 49 for(i=0;i<6;i++) 50 Branchtab615[i].w[state] = (polys[i] < 0) ^ parity((2*state) & abs(polys[i])) ? 255 : 0; 51 } 52 Init++; 53 } 54 55 /* Initialize Viterbi decoder for start of new frame */ 56 int init_viterbi615_port(void *p,int starting_state){ 57 struct v615 *vp = p; 58 int i; 59 60 if(p == NULL) 61 return -1; 62 for(i=0;i<16384;i++) 63 vp->metrics1.w[i] = 1000; 64 65 vp->old_metrics = &vp->metrics1; 66 vp->new_metrics = &vp->metrics2; 67 vp->dp = vp->decisions; 68 vp->old_metrics->w[starting_state & 16383] = 0; /* Bias known start state */ 69 return 0; 70 } 71 72 /* Viterbi chainback */ 73 int chainback_viterbi615_port( 74 void *p, 75 unsigned char *data, /* Decoded output data */ 76 unsigned int nbits, /* Number of data bits */ 77 unsigned int endstate){ /* Terminal encoder state */ 78 struct v615 *vp = p; 79 decision_t *d; 80 81 if(p == NULL) 82 return -1; 83 d = (decision_t *)vp->decisions; 84 endstate %= 16384; 85 86 /* The store into data[] only needs to be done every 8 bits. 87 * But this avoids a conditional branch, and the writes will 88 * combine in the cache anyway 89 */ 90 d += 14; /* Look past tail */ 91 while(nbits-- != 0){ 92 int k; 93 94 k = (d[nbits].c[endstate/8] >> (endstate%8)) & 1; 95 endstate = (k << 13) | (endstate >> 1); 96 data[nbits>>3] = endstate >> 6; 97 } 98 return 0; 99 } 100 101 /* Delete instance of a Viterbi decoder */ 102 void delete_viterbi615_port(void *p){ 103 struct v615 *vp = p; 104 105 if(vp != NULL){ 106 free(vp->decisions); 107 free(vp); 108 } 109 } 110 111 /* C-language butterfly */ 112 #define BFLY(i) {\ 113 unsigned long metric,m0,m1,m2,m3,decision0,decision1;\ 114 metric = ((Branchtab615[0].w[i] ^ syms[0]) + (Branchtab615[1].w[i] ^ syms[1])\ 115 +(Branchtab615[2].w[i] ^ syms[2]) + (Branchtab615[3].w[i] ^ syms[3])\ 116 +(Branchtab615[4].w[i] ^ syms[4]) + (Branchtab615[5].w[i] ^ syms[5]));\ 117 m0 = vp->old_metrics->w[i] + metric;\ 118 m1 = vp->old_metrics->w[i+8192] + (1530 - metric);\ 119 m2 = vp->old_metrics->w[i] + (1530-metric);\ 120 m3 = vp->old_metrics->w[i+8192] + metric;\ 121 decision0 = (signed long)(m0-m1) >= 0;\ 122 decision1 = (signed long)(m2-m3) >= 0;\ 123 vp->new_metrics->w[2*i] = decision0 ? m1 : m0;\ 124 vp->new_metrics->w[2*i+1] = decision1 ? m3 : m2;\ 125 d->c[i/4] |= ((decision0|(decision1<<1)) << ((2*i)&7));\ 126 } 127 /* Update decoder with a block of demodulated symbols 128 * Note that nbits is the number of decoded data bits, not the number 129 * of symbols! 130 */ 131 132 int update_viterbi615_blk_port(void *p,unsigned char *syms,int nbits){ 133 struct v615 *vp = p; 134 void *tmp; 135 decision_t *d; 136 int i; 137 138 if(p == NULL) 139 return -1; 140 d = (decision_t *)vp->dp; 141 while(nbits--){ 142 memset(d,0,sizeof(decision_t)); 143 for(i=0;i<8192;i++) 144 BFLY(i); 145 146 syms += 6; 147 d++; 148 /* Swap pointers to old and new metrics */ 149 tmp = vp->old_metrics; 150 vp->old_metrics = vp->new_metrics; 151 vp->new_metrics = tmp; 152 } 153 vp->dp = d; 154 return 0; 155 } 156 157
