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