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