git.gag.com Git - debian/gnuradio/blob - gnuradio-core/src/lib/reed-solomon/decode_rs.c

   1 /* Reed-Solomon decoder
   2  * Copyright 2002 Phil Karn, KA9Q
   3  * May be used under the terms of the GNU General Public License (GPL)
   4  */
   5
   6 #ifdef DEBUG
   7 #include <stdio.h>
   8 #endif
   9
  10 #include <string.h>
  11
  12 #define NULL ((void *)0)
  13 #define min(a,b)        ((a) < (b) ? (a) : (b))
  14
  15 #ifdef FIXED
  16 #include "fixed.h"
  17 #elif defined(BIGSYM)
  18 #include "int.h"
  19 #else
  20 #include "char.h"
  21 #endif
  22
  23 int DECODE_RS(
  24 #ifndef FIXED
  25 void *p,
  26 #endif
  27 DTYPE *data, int *eras_pos, int no_eras){
  28
  29 #ifndef FIXED
  30   struct rs *rs = (struct rs *)p;
  31 #endif
  32   int deg_lambda, el, deg_omega;
  33   int i, j, r,k;
  34   DTYPE u,q,tmp,num1,num2,den,discr_r;
  35   DTYPE lambda[NROOTS+1], s[NROOTS];    /* Err+Eras Locator poly
  36                                          * and syndrome poly */
  37   DTYPE b[NROOTS+1], t[NROOTS+1], omega[NROOTS+1];
  38   DTYPE root[NROOTS], reg[NROOTS+1], loc[NROOTS];
  39   int syn_error, count;
  40
  41   /* form the syndromes; i.e., evaluate data(x) at roots of g(x) */
  42   for(i=0;i<NROOTS;i++)
  43     s[i] = data[0];
  44
  45   for(j=1;j<NN;j++){
  46     for(i=0;i<NROOTS;i++){
  47       if(s[i] == 0){
  48         s[i] = data[j];
  49       } else {
  50         s[i] = data[j] ^ ALPHA_TO[MODNN(INDEX_OF[s[i]] + (FCR+i)*PRIM)];
  51       }
  52     }
  53   }
  54
  55   /* Convert syndromes to index form, checking for nonzero condition */
  56   syn_error = 0;
  57   for(i=0;i<NROOTS;i++){
  58     syn_error |= s[i];
  59     s[i] = INDEX_OF[s[i]];
  60   }
  61
  62   if (!syn_error) {
  63     /* if syndrome is zero, data[] is a codeword and there are no
  64      * errors to correct. So return data[] unmodified
  65      */
  66     count = 0;
  67     goto finish;
  68   }
  69   memset(&lambda[1],0,NROOTS*sizeof(lambda[0]));
  70   lambda[0] = 1;
  71
  72   if (no_eras > 0) {
  73     /* Init lambda to be the erasure locator polynomial */
  74     lambda[1] = ALPHA_TO[MODNN(PRIM*(NN-1-eras_pos[0]))];
  75     for (i = 1; i < no_eras; i++) {
  76       u = MODNN(PRIM*(NN-1-eras_pos[i]));
  77       for (j = i+1; j > 0; j--) {
  78         tmp = INDEX_OF[lambda[j - 1]];
  79         if(tmp != A0)
  80           lambda[j] ^= ALPHA_TO[MODNN(u + tmp)];
  81       }
  82     }
  83
  84 #if DEBUG >= 1
  85     /* Test code that verifies the erasure locator polynomial just constructed
  86        Needed only for decoder debugging. */
  87
  88     /* find roots of the erasure location polynomial */
  89     for(i=1;i<=no_eras;i++)
  90       reg[i] = INDEX_OF[lambda[i]];
  91
  92     count = 0;
  93     for (i = 1,k=IPRIM-1; i <= NN; i++,k = MODNN(k+IPRIM)) {
  94       q = 1;
  95       for (j = 1; j <= no_eras; j++)
  96         if (reg[j] != A0) {
  97           reg[j] = MODNN(reg[j] + j);
  98           q ^= ALPHA_TO[reg[j]];
  99         }
 100       if (q != 0)
 101         continue;
 102       /* store root and error location number indices */
 103       root[count] = i;
 104       loc[count] = k;
 105       count++;
 106     }
 107     if (count != no_eras) {
 108       printf("count = %d no_eras = %d\n lambda(x) is WRONG\n",count,no_eras);
 109       count = -1;
 110       goto finish;
 111     }
 112 #if DEBUG >= 2
 113     printf("\n Erasure positions as determined by roots of Eras Loc Poly:\n");
 114     for (i = 0; i < count; i++)
 115       printf("%d ", loc[i]);
 116     printf("\n");
 117 #endif
 118 #endif
 119   }
 120   for(i=0;i<NROOTS+1;i++)
 121     b[i] = INDEX_OF[lambda[i]];
 122
 123   /*
 124    * Begin Berlekamp-Massey algorithm to determine error+erasure
 125    * locator polynomial
 126    */
 127   r = no_eras;
 128   el = no_eras;
 129   while (++r <= NROOTS) {       /* r is the step number */
 130     /* Compute discrepancy at the r-th step in poly-form */
 131     discr_r = 0;
 132     for (i = 0; i < r; i++){
 133       if ((lambda[i] != 0) && (s[r-i-1] != A0)) {
 134         discr_r ^= ALPHA_TO[MODNN(INDEX_OF[lambda[i]] + s[r-i-1])];
 135       }
 136     }
 137     discr_r = INDEX_OF[discr_r];        /* Index form */
 138     if (discr_r == A0) {
 139       /* 2 lines below: B(x) <-- x*B(x) */
 140       memmove(&b[1],b,NROOTS*sizeof(b[0]));
 141       b[0] = A0;
 142     } else {
 143       /* 7 lines below: T(x) <-- lambda(x) - discr_r*x*b(x) */
 144       t[0] = lambda[0];
 145       for (i = 0 ; i < NROOTS; i++) {
 146         if(b[i] != A0)
 147           t[i+1] = lambda[i+1] ^ ALPHA_TO[MODNN(discr_r + b[i])];
 148         else
 149           t[i+1] = lambda[i+1];
 150       }
 151       if (2 * el <= r + no_eras - 1) {
 152         el = r + no_eras - el;
 153         /*
 154          * 2 lines below: B(x) <-- inv(discr_r) *
 155          * lambda(x)
 156          */
 157         for (i = 0; i <= NROOTS; i++)
 158           b[i] = (lambda[i] == 0) ? A0 : MODNN(INDEX_OF[lambda[i]] - discr_r + NN);
 159       } else {
 160         /* 2 lines below: B(x) <-- x*B(x) */
 161         memmove(&b[1],b,NROOTS*sizeof(b[0]));
 162         b[0] = A0;
 163       }
 164       memcpy(lambda,t,(NROOTS+1)*sizeof(t[0]));
 165     }
 166   }
 167
 168   /* Convert lambda to index form and compute deg(lambda(x)) */
 169   deg_lambda = 0;
 170   for(i=0;i<NROOTS+1;i++){
 171     lambda[i] = INDEX_OF[lambda[i]];
 172     if(lambda[i] != A0)
 173       deg_lambda = i;
 174   }
 175   /* Find roots of the error+erasure locator polynomial by Chien search */
 176   memcpy(&reg[1],&lambda[1],NROOTS*sizeof(reg[0]));
 177   count = 0;            /* Number of roots of lambda(x) */
 178   for (i = 1,k=IPRIM-1; i <= NN; i++,k = MODNN(k+IPRIM)) {
 179     q = 1; /* lambda[0] is always 0 */
 180     for (j = deg_lambda; j > 0; j--){
 181       if (reg[j] != A0) {
 182         reg[j] = MODNN(reg[j] + j);
 183         q ^= ALPHA_TO[reg[j]];
 184       }
 185     }
 186     if (q != 0)
 187       continue; /* Not a root */
 188     /* store root (index-form) and error location number */
 189 #if DEBUG>=2
 190     printf("count %d root %d loc %d\n",count,i,k);
 191 #endif
 192     root[count] = i;
 193     loc[count] = k;
 194     /* If we've already found max possible roots,
 195      * abort the search to save time
 196      */
 197     if(++count == deg_lambda)
 198       break;
 199   }
 200   if (deg_lambda != count) {
 201     /*
 202      * deg(lambda) unequal to number of roots => uncorrectable
 203      * error detected
 204      */
 205     count = -1;
 206     goto finish;
 207   }
 208   /*
 209    * Compute err+eras evaluator poly omega(x) = s(x)*lambda(x) (modulo
 210    * x**NROOTS). in index form. Also find deg(omega).
 211    */
 212   deg_omega = 0;
 213   for (i = 0; i < NROOTS;i++){
 214     tmp = 0;
 215     j = (deg_lambda < i) ? deg_lambda : i;
 216     for(;j >= 0; j--){
 217       if ((s[i - j] != A0) && (lambda[j] != A0))
 218         tmp ^= ALPHA_TO[MODNN(s[i - j] + lambda[j])];
 219     }
 220     if(tmp != 0)
 221       deg_omega = i;
 222     omega[i] = INDEX_OF[tmp];
 223   }
 224   omega[NROOTS] = A0;
 225
 226   /*
 227    * Compute error values in poly-form. num1 = omega(inv(X(l))), num2 =
 228    * inv(X(l))**(FCR-1) and den = lambda_pr(inv(X(l))) all in poly-form
 229    */
 230   for (j = count-1; j >=0; j--) {
 231     num1 = 0;
 232     for (i = deg_omega; i >= 0; i--) {
 233       if (omega[i] != A0)
 234         num1  ^= ALPHA_TO[MODNN(omega[i] + i * root[j])];
 235     }
 236     num2 = ALPHA_TO[MODNN(root[j] * (FCR - 1) + NN)];
 237     den = 0;
 238
 239     /* lambda[i+1] for i even is the formal derivative lambda_pr of lambda[i] */
 240     for (i = min(deg_lambda,NROOTS-1) & ~1; i >= 0; i -=2) {
 241       if(lambda[i+1] != A0)
 242         den ^= ALPHA_TO[MODNN(lambda[i+1] + i * root[j])];
 243     }
 244     if (den == 0) {
 245 #if DEBUG >= 1
 246       printf("\n ERROR: denominator = 0\n");
 247 #endif
 248       count = -1;
 249       goto finish;
 250     }
 251     /* Apply error to data */
 252     if (num1 != 0) {
 253       data[loc[j]] ^= ALPHA_TO[MODNN(INDEX_OF[num1] + INDEX_OF[num2] + NN - INDEX_OF[den])];
 254     }
 255   }
 256  finish:
 257   if(eras_pos != NULL){
 258     for(i=0;i<count;i++)
 259       eras_pos[i] = loc[i];
 260   }
 261   return count;
 262 }