14e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi/* Reed-Solomon decoder 24e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi * Copyright 2002 Phil Karn, KA9Q 34e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi * May be used under the terms of the GNU Lesser General Public License (LGPL) 44e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi */ 54e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 64e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi#ifdef DEBUG 74e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi#include <stdio.h> 84e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi#endif 94e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 104e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi#include <string.h> 114e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 124e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi#define NULL ((void *)0) 134e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi#define min(a,b) ((a) < (b) ? (a) : (b)) 144e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 154e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi#ifdef FIXED 164e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi#include "fixed.h" 174e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi#elif defined(BIGSYM) 184e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi#include "int.h" 194e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi#else 204e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi#include "char.h" 214e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi#endif 224e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 234e213d510f437769f8a28578dd4f786fb7d16c4Bill Yiint DECODE_RS( 244e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi#ifdef FIXED 254e213d510f437769f8a28578dd4f786fb7d16c4Bill Yidata_t *data, int *eras_pos, int no_eras,int pad){ 264e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi#else 274e213d510f437769f8a28578dd4f786fb7d16c4Bill Yivoid *p,data_t *data, int *eras_pos, int no_eras){ 284e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi struct rs *rs = (struct rs *)p; 294e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi#endif 304e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi int deg_lambda, el, deg_omega; 314e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi int i, j, r,k; 324e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi data_t u,q,tmp,num1,num2,den,discr_r; 334e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi data_t lambda[NROOTS+1], s[NROOTS]; /* Err+Eras Locator poly 344e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi * and syndrome poly */ 354e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi data_t b[NROOTS+1], t[NROOTS+1], omega[NROOTS+1]; 364e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi data_t root[NROOTS], reg[NROOTS+1], loc[NROOTS]; 374e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi int syn_error, count; 384e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 394e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi#ifdef FIXED 404e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi /* Check pad parameter for validity */ 414e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if(pad < 0 || pad >= NN) 424e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi return -1; 434e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi#endif 444e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 454e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi /* form the syndromes; i.e., evaluate data(x) at roots of g(x) */ 464e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi for(i=0;i<NROOTS;i++) 474e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi s[i] = data[0]; 484e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 494e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi for(j=1;j<NN-PAD;j++){ 504e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi for(i=0;i<NROOTS;i++){ 514e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if(s[i] == 0){ 524e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi s[i] = data[j]; 534e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } else { 544e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi s[i] = data[j] ^ ALPHA_TO[MODNN(INDEX_OF[s[i]] + (FCR+i)*PRIM)]; 554e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 564e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 574e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 584e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 594e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi /* Convert syndromes to index form, checking for nonzero condition */ 604e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi syn_error = 0; 614e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi for(i=0;i<NROOTS;i++){ 624e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi syn_error |= s[i]; 634e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi s[i] = INDEX_OF[s[i]]; 644e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 654e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 664e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if (!syn_error) { 674e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi /* if syndrome is zero, data[] is a codeword and there are no 684e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi * errors to correct. So return data[] unmodified 694e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi */ 704e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi count = 0; 714e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi goto finish; 724e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 734e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi memset(&lambda[1],0,NROOTS*sizeof(lambda[0])); 744e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi lambda[0] = 1; 754e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 764e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if (no_eras > 0) { 774e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi /* Init lambda to be the erasure locator polynomial */ 784e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi lambda[1] = ALPHA_TO[MODNN(PRIM*(NN-1-eras_pos[0]))]; 794e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi for (i = 1; i < no_eras; i++) { 804e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi u = MODNN(PRIM*(NN-1-eras_pos[i])); 814e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi for (j = i+1; j > 0; j--) { 824e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi tmp = INDEX_OF[lambda[j - 1]]; 834e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if(tmp != A0) 844e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi lambda[j] ^= ALPHA_TO[MODNN(u + tmp)]; 854e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 864e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 874e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 884e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi#if DEBUG >= 1 894e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi /* Test code that verifies the erasure locator polynomial just constructed 904e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi Needed only for decoder debugging. */ 914e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 924e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi /* find roots of the erasure location polynomial */ 934e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi for(i=1;i<=no_eras;i++) 944e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi reg[i] = INDEX_OF[lambda[i]]; 954e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 964e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi count = 0; 974e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi for (i = 1,k=IPRIM-1; i <= NN; i++,k = MODNN(k+IPRIM)) { 984e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi q = 1; 994e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi for (j = 1; j <= no_eras; j++) 1004e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if (reg[j] != A0) { 1014e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi reg[j] = MODNN(reg[j] + j); 1024e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi q ^= ALPHA_TO[reg[j]]; 1034e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 1044e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if (q != 0) 1054e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi continue; 1064e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi /* store root and error location number indices */ 1074e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi root[count] = i; 1084e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi loc[count] = k; 1094e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi count++; 1104e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 1114e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if (count != no_eras) { 1124e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi printf("count = %d no_eras = %d\n lambda(x) is WRONG\n",count,no_eras); 1134e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi count = -1; 1144e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi goto finish; 1154e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 1164e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi#if DEBUG >= 2 1174e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi printf("\n Erasure positions as determined by roots of Eras Loc Poly:\n"); 1184e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi for (i = 0; i < count; i++) 1194e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi printf("%d ", loc[i]); 1204e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi printf("\n"); 1214e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi#endif 1224e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi#endif 1234e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 1244e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi for(i=0;i<NROOTS+1;i++) 1254e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi b[i] = INDEX_OF[lambda[i]]; 1264e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 1274e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi /* 1284e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi * Begin Berlekamp-Massey algorithm to determine error+erasure 1294e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi * locator polynomial 1304e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi */ 1314e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi r = no_eras; 1324e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi el = no_eras; 1334e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi while (++r <= NROOTS) { /* r is the step number */ 1344e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi /* Compute discrepancy at the r-th step in poly-form */ 1354e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi discr_r = 0; 1364e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi for (i = 0; i < r; i++){ 1374e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if ((lambda[i] != 0) && (s[r-i-1] != A0)) { 1384e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi discr_r ^= ALPHA_TO[MODNN(INDEX_OF[lambda[i]] + s[r-i-1])]; 1394e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 1404e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 1414e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi discr_r = INDEX_OF[discr_r]; /* Index form */ 1424e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if (discr_r == A0) { 1434e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi /* 2 lines below: B(x) <-- x*B(x) */ 1444e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi memmove(&b[1],b,NROOTS*sizeof(b[0])); 1454e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi b[0] = A0; 1464e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } else { 1474e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi /* 7 lines below: T(x) <-- lambda(x) - discr_r*x*b(x) */ 1484e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi t[0] = lambda[0]; 1494e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi for (i = 0 ; i < NROOTS; i++) { 1504e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if(b[i] != A0) 1514e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi t[i+1] = lambda[i+1] ^ ALPHA_TO[MODNN(discr_r + b[i])]; 1524e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi else 1534e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi t[i+1] = lambda[i+1]; 1544e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 1554e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if (2 * el <= r + no_eras - 1) { 1564e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi el = r + no_eras - el; 1574e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi /* 1584e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi * 2 lines below: B(x) <-- inv(discr_r) * 1594e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi * lambda(x) 1604e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi */ 1614e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi for (i = 0; i <= NROOTS; i++) 1624e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi b[i] = (lambda[i] == 0) ? A0 : MODNN(INDEX_OF[lambda[i]] - discr_r + NN); 1634e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } else { 1644e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi /* 2 lines below: B(x) <-- x*B(x) */ 1654e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi memmove(&b[1],b,NROOTS*sizeof(b[0])); 1664e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi b[0] = A0; 1674e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 1684e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi memcpy(lambda,t,(NROOTS+1)*sizeof(t[0])); 1694e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 1704e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 1714e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 1724e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi /* Convert lambda to index form and compute deg(lambda(x)) */ 1734e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi deg_lambda = 0; 1744e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi for(i=0;i<NROOTS+1;i++){ 1754e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi lambda[i] = INDEX_OF[lambda[i]]; 1764e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if(lambda[i] != A0) 1774e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi deg_lambda = i; 1784e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 1794e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi /* Find roots of the error+erasure locator polynomial by Chien search */ 1804e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi memcpy(®[1],&lambda[1],NROOTS*sizeof(reg[0])); 1814e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi count = 0; /* Number of roots of lambda(x) */ 1824e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi for (i = 1,k=IPRIM-1; i <= NN; i++,k = MODNN(k+IPRIM)) { 1834e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi q = 1; /* lambda[0] is always 0 */ 1844e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi for (j = deg_lambda; j > 0; j--){ 1854e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if (reg[j] != A0) { 1864e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi reg[j] = MODNN(reg[j] + j); 1874e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi q ^= ALPHA_TO[reg[j]]; 1884e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 1894e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 1904e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if (q != 0) 1914e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi continue; /* Not a root */ 1924e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi /* store root (index-form) and error location number */ 1934e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi#if DEBUG>=2 1944e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi printf("count %d root %d loc %d\n",count,i,k); 1954e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi#endif 1964e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi root[count] = i; 1974e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi loc[count] = k; 1984e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi /* If we've already found max possible roots, 1994e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi * abort the search to save time 2004e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi */ 2014e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if(++count == deg_lambda) 2024e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi break; 2034e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 2044e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if (deg_lambda != count) { 2054e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi /* 2064e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi * deg(lambda) unequal to number of roots => uncorrectable 2074e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi * error detected 2084e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi */ 2094e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi count = -1; 2104e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi goto finish; 2114e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 2124e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi /* 2134e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi * Compute err+eras evaluator poly omega(x) = s(x)*lambda(x) (modulo 2144e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi * x**NROOTS). in index form. Also find deg(omega). 2154e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi */ 2164e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi deg_omega = deg_lambda-1; 2174e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi for (i = 0; i <= deg_omega;i++){ 2184e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi tmp = 0; 2194e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi for(j=i;j >= 0; j--){ 2204e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if ((s[i - j] != A0) && (lambda[j] != A0)) 2214e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi tmp ^= ALPHA_TO[MODNN(s[i - j] + lambda[j])]; 2224e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 2234e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi omega[i] = INDEX_OF[tmp]; 2244e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 2254e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 2264e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi /* 2274e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi * Compute error values in poly-form. num1 = omega(inv(X(l))), num2 = 2284e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi * inv(X(l))**(FCR-1) and den = lambda_pr(inv(X(l))) all in poly-form 2294e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi */ 2304e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi for (j = count-1; j >=0; j--) { 2314e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi num1 = 0; 2324e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi for (i = deg_omega; i >= 0; i--) { 2334e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if (omega[i] != A0) 2344e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi num1 ^= ALPHA_TO[MODNN(omega[i] + i * root[j])]; 2354e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 2364e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi num2 = ALPHA_TO[MODNN(root[j] * (FCR - 1) + NN)]; 2374e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi den = 0; 2384e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi 2394e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi /* lambda[i+1] for i even is the formal derivative lambda_pr of lambda[i] */ 2404e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi for (i = min(deg_lambda,NROOTS-1) & ~1; i >= 0; i -=2) { 2414e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if(lambda[i+1] != A0) 2424e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi den ^= ALPHA_TO[MODNN(lambda[i+1] + i * root[j])]; 2434e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 2444e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi#if DEBUG >= 1 2454e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if (den == 0) { 2464e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi printf("\n ERROR: denominator = 0\n"); 2474e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi count = -1; 2484e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi goto finish; 2494e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 2504e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi#endif 2514e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi /* Apply error to data */ 2524e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if (num1 != 0 && loc[j] >= PAD) { 2534e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi data[loc[j]-PAD] ^= ALPHA_TO[MODNN(INDEX_OF[num1] + INDEX_OF[num2] + NN - INDEX_OF[den])]; 2544e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 2554e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 2564e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi finish: 2574e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi if(eras_pos != NULL){ 2584e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi for(i=0;i<count;i++) 2594e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi eras_pos[i] = loc[i]; 2604e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi } 2614e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi return count; 2624e213d510f437769f8a28578dd4f786fb7d16c4Bill Yi} 263