Bill Yi | 4e213d5 | 2015-06-23 13:53:11 -0700 | [diff] [blame] | 1 | /* The guts of the Reed-Solomon decoder, meant to be #included |
| 2 | * into a function body with the following typedefs, macros and variables supplied |
| 3 | * according to the code parameters: |
| 4 | |
| 5 | * data_t - a typedef for the data symbol |
| 6 | * data_t data[] - array of NN data and parity symbols to be corrected in place |
| 7 | * retval - an integer lvalue into which the decoder's return code is written |
| 8 | * NROOTS - the number of roots in the RS code generator polynomial, |
| 9 | * which is the same as the number of parity symbols in a block. |
| 10 | Integer variable or literal. |
| 11 | * NN - the total number of symbols in a RS block. Integer variable or literal. |
| 12 | * PAD - the number of pad symbols in a block. Integer variable or literal. |
| 13 | * ALPHA_TO - The address of an array of NN elements to convert Galois field |
| 14 | * elements in index (log) form to polynomial form. Read only. |
| 15 | * INDEX_OF - The address of an array of NN elements to convert Galois field |
| 16 | * elements in polynomial form to index (log) form. Read only. |
| 17 | * MODNN - a function to reduce its argument modulo NN. May be inline or a macro. |
| 18 | * FCR - An integer literal or variable specifying the first consecutive root of the |
| 19 | * Reed-Solomon generator polynomial. Integer variable or literal. |
| 20 | * PRIM - The primitive root of the generator poly. Integer variable or literal. |
| 21 | * DEBUG - If set to 1 or more, do various internal consistency checking. Leave this |
| 22 | * undefined for production code |
| 23 | |
| 24 | * The memset(), memmove(), and memcpy() functions are used. The appropriate header |
| 25 | * file declaring these functions (usually <string.h>) must be included by the calling |
| 26 | * program. |
| 27 | */ |
| 28 | |
| 29 | |
| 30 | #if !defined(NROOTS) |
| 31 | #error "NROOTS not defined" |
| 32 | #endif |
| 33 | |
| 34 | #if !defined(NN) |
| 35 | #error "NN not defined" |
| 36 | #endif |
| 37 | |
| 38 | #if !defined(PAD) |
| 39 | #error "PAD not defined" |
| 40 | #endif |
| 41 | |
| 42 | #if !defined(ALPHA_TO) |
| 43 | #error "ALPHA_TO not defined" |
| 44 | #endif |
| 45 | |
| 46 | #if !defined(INDEX_OF) |
| 47 | #error "INDEX_OF not defined" |
| 48 | #endif |
| 49 | |
| 50 | #if !defined(MODNN) |
| 51 | #error "MODNN not defined" |
| 52 | #endif |
| 53 | |
| 54 | #if !defined(FCR) |
| 55 | #error "FCR not defined" |
| 56 | #endif |
| 57 | |
| 58 | #if !defined(PRIM) |
| 59 | #error "PRIM not defined" |
| 60 | #endif |
| 61 | |
| 62 | #if !defined(NULL) |
| 63 | #define NULL ((void *)0) |
| 64 | #endif |
| 65 | |
| 66 | #undef MIN |
| 67 | #define MIN(a,b) ((a) < (b) ? (a) : (b)) |
| 68 | #undef A0 |
| 69 | #define A0 (NN) |
| 70 | |
| 71 | { |
| 72 | int deg_lambda, el, deg_omega; |
| 73 | int i, j, r,k; |
| 74 | data_t u,q,tmp,num1,num2,den,discr_r; |
| 75 | data_t lambda[NROOTS+1], s[NROOTS]; /* Err+Eras Locator poly |
| 76 | * and syndrome poly */ |
| 77 | data_t b[NROOTS+1], t[NROOTS+1], omega[NROOTS+1]; |
| 78 | data_t root[NROOTS], reg[NROOTS+1], loc[NROOTS]; |
| 79 | int syn_error, count; |
| 80 | |
| 81 | /* form the syndromes; i.e., evaluate data(x) at roots of g(x) */ |
| 82 | for(i=0;i<NROOTS;i++) |
| 83 | s[i] = data[0]; |
| 84 | |
| 85 | for(j=1;j<NN-PAD;j++){ |
| 86 | for(i=0;i<NROOTS;i++){ |
| 87 | if(s[i] == 0){ |
| 88 | s[i] = data[j]; |
| 89 | } else { |
| 90 | s[i] = data[j] ^ ALPHA_TO[MODNN(INDEX_OF[s[i]] + (FCR+i)*PRIM)]; |
| 91 | } |
| 92 | } |
| 93 | } |
| 94 | |
| 95 | /* Convert syndromes to index form, checking for nonzero condition */ |
| 96 | syn_error = 0; |
| 97 | for(i=0;i<NROOTS;i++){ |
| 98 | syn_error |= s[i]; |
| 99 | s[i] = INDEX_OF[s[i]]; |
| 100 | } |
| 101 | |
| 102 | if (!syn_error) { |
| 103 | /* if syndrome is zero, data[] is a codeword and there are no |
| 104 | * errors to correct. So return data[] unmodified |
| 105 | */ |
| 106 | count = 0; |
| 107 | goto finish; |
| 108 | } |
| 109 | memset(&lambda[1],0,NROOTS*sizeof(lambda[0])); |
| 110 | lambda[0] = 1; |
| 111 | |
| 112 | if (no_eras > 0) { |
| 113 | /* Init lambda to be the erasure locator polynomial */ |
| 114 | lambda[1] = ALPHA_TO[MODNN(PRIM*(NN-1-eras_pos[0]))]; |
| 115 | for (i = 1; i < no_eras; i++) { |
| 116 | u = MODNN(PRIM*(NN-1-eras_pos[i])); |
| 117 | for (j = i+1; j > 0; j--) { |
| 118 | tmp = INDEX_OF[lambda[j - 1]]; |
| 119 | if(tmp != A0) |
| 120 | lambda[j] ^= ALPHA_TO[MODNN(u + tmp)]; |
| 121 | } |
| 122 | } |
| 123 | |
| 124 | #if DEBUG >= 1 |
| 125 | /* Test code that verifies the erasure locator polynomial just constructed |
| 126 | Needed only for decoder debugging. */ |
| 127 | |
| 128 | /* find roots of the erasure location polynomial */ |
| 129 | for(i=1;i<=no_eras;i++) |
| 130 | reg[i] = INDEX_OF[lambda[i]]; |
| 131 | |
| 132 | count = 0; |
| 133 | for (i = 1,k=IPRIM-1; i <= NN; i++,k = MODNN(k+IPRIM)) { |
| 134 | q = 1; |
| 135 | for (j = 1; j <= no_eras; j++) |
| 136 | if (reg[j] != A0) { |
| 137 | reg[j] = MODNN(reg[j] + j); |
| 138 | q ^= ALPHA_TO[reg[j]]; |
| 139 | } |
| 140 | if (q != 0) |
| 141 | continue; |
| 142 | /* store root and error location number indices */ |
| 143 | root[count] = i; |
| 144 | loc[count] = k; |
| 145 | count++; |
| 146 | } |
| 147 | if (count != no_eras) { |
| 148 | printf("count = %d no_eras = %d\n lambda(x) is WRONG\n",count,no_eras); |
| 149 | count = -1; |
| 150 | goto finish; |
| 151 | } |
| 152 | #if DEBUG >= 2 |
| 153 | printf("\n Erasure positions as determined by roots of Eras Loc Poly:\n"); |
| 154 | for (i = 0; i < count; i++) |
| 155 | printf("%d ", loc[i]); |
| 156 | printf("\n"); |
| 157 | #endif |
| 158 | #endif |
| 159 | } |
| 160 | for(i=0;i<NROOTS+1;i++) |
| 161 | b[i] = INDEX_OF[lambda[i]]; |
| 162 | |
| 163 | /* |
| 164 | * Begin Berlekamp-Massey algorithm to determine error+erasure |
| 165 | * locator polynomial |
| 166 | */ |
| 167 | r = no_eras; |
| 168 | el = no_eras; |
| 169 | while (++r <= NROOTS) { /* r is the step number */ |
| 170 | /* Compute discrepancy at the r-th step in poly-form */ |
| 171 | discr_r = 0; |
| 172 | for (i = 0; i < r; i++){ |
| 173 | if ((lambda[i] != 0) && (s[r-i-1] != A0)) { |
| 174 | discr_r ^= ALPHA_TO[MODNN(INDEX_OF[lambda[i]] + s[r-i-1])]; |
| 175 | } |
| 176 | } |
| 177 | discr_r = INDEX_OF[discr_r]; /* Index form */ |
| 178 | if (discr_r == A0) { |
| 179 | /* 2 lines below: B(x) <-- x*B(x) */ |
| 180 | memmove(&b[1],b,NROOTS*sizeof(b[0])); |
| 181 | b[0] = A0; |
| 182 | } else { |
| 183 | /* 7 lines below: T(x) <-- lambda(x) - discr_r*x*b(x) */ |
| 184 | t[0] = lambda[0]; |
| 185 | for (i = 0 ; i < NROOTS; i++) { |
| 186 | if(b[i] != A0) |
| 187 | t[i+1] = lambda[i+1] ^ ALPHA_TO[MODNN(discr_r + b[i])]; |
| 188 | else |
| 189 | t[i+1] = lambda[i+1]; |
| 190 | } |
| 191 | if (2 * el <= r + no_eras - 1) { |
| 192 | el = r + no_eras - el; |
| 193 | /* |
| 194 | * 2 lines below: B(x) <-- inv(discr_r) * |
| 195 | * lambda(x) |
| 196 | */ |
| 197 | for (i = 0; i <= NROOTS; i++) |
| 198 | b[i] = (lambda[i] == 0) ? A0 : MODNN(INDEX_OF[lambda[i]] - discr_r + NN); |
| 199 | } else { |
| 200 | /* 2 lines below: B(x) <-- x*B(x) */ |
| 201 | memmove(&b[1],b,NROOTS*sizeof(b[0])); |
| 202 | b[0] = A0; |
| 203 | } |
| 204 | memcpy(lambda,t,(NROOTS+1)*sizeof(t[0])); |
| 205 | } |
| 206 | } |
| 207 | |
| 208 | /* Convert lambda to index form and compute deg(lambda(x)) */ |
| 209 | deg_lambda = 0; |
| 210 | for(i=0;i<NROOTS+1;i++){ |
| 211 | lambda[i] = INDEX_OF[lambda[i]]; |
| 212 | if(lambda[i] != A0) |
| 213 | deg_lambda = i; |
| 214 | } |
| 215 | /* Find roots of the error+erasure locator polynomial by Chien search */ |
| 216 | memcpy(®[1],&lambda[1],NROOTS*sizeof(reg[0])); |
| 217 | count = 0; /* Number of roots of lambda(x) */ |
| 218 | for (i = 1,k=IPRIM-1; i <= NN; i++,k = MODNN(k+IPRIM)) { |
| 219 | q = 1; /* lambda[0] is always 0 */ |
| 220 | for (j = deg_lambda; j > 0; j--){ |
| 221 | if (reg[j] != A0) { |
| 222 | reg[j] = MODNN(reg[j] + j); |
| 223 | q ^= ALPHA_TO[reg[j]]; |
| 224 | } |
| 225 | } |
| 226 | if (q != 0) |
| 227 | continue; /* Not a root */ |
| 228 | /* store root (index-form) and error location number */ |
| 229 | #if DEBUG>=2 |
| 230 | printf("count %d root %d loc %d\n",count,i,k); |
| 231 | #endif |
| 232 | root[count] = i; |
| 233 | loc[count] = k; |
| 234 | /* If we've already found max possible roots, |
| 235 | * abort the search to save time |
| 236 | */ |
| 237 | if(++count == deg_lambda) |
| 238 | break; |
| 239 | } |
| 240 | if (deg_lambda != count) { |
| 241 | /* |
| 242 | * deg(lambda) unequal to number of roots => uncorrectable |
| 243 | * error detected |
| 244 | */ |
| 245 | count = -1; |
| 246 | goto finish; |
| 247 | } |
| 248 | /* |
| 249 | * Compute err+eras evaluator poly omega(x) = s(x)*lambda(x) (modulo |
| 250 | * x**NROOTS). in index form. Also find deg(omega). |
| 251 | */ |
| 252 | deg_omega = deg_lambda-1; |
| 253 | for (i = 0; i <= deg_omega;i++){ |
| 254 | tmp = 0; |
| 255 | for(j=i;j >= 0; j--){ |
| 256 | if ((s[i - j] != A0) && (lambda[j] != A0)) |
| 257 | tmp ^= ALPHA_TO[MODNN(s[i - j] + lambda[j])]; |
| 258 | } |
| 259 | omega[i] = INDEX_OF[tmp]; |
| 260 | } |
| 261 | |
| 262 | /* |
| 263 | * Compute error values in poly-form. num1 = omega(inv(X(l))), num2 = |
| 264 | * inv(X(l))**(FCR-1) and den = lambda_pr(inv(X(l))) all in poly-form |
| 265 | */ |
| 266 | for (j = count-1; j >=0; j--) { |
| 267 | num1 = 0; |
| 268 | for (i = deg_omega; i >= 0; i--) { |
| 269 | if (omega[i] != A0) |
| 270 | num1 ^= ALPHA_TO[MODNN(omega[i] + i * root[j])]; |
| 271 | } |
| 272 | num2 = ALPHA_TO[MODNN(root[j] * (FCR - 1) + NN)]; |
| 273 | den = 0; |
| 274 | |
| 275 | /* lambda[i+1] for i even is the formal derivative lambda_pr of lambda[i] */ |
| 276 | for (i = MIN(deg_lambda,NROOTS-1) & ~1; i >= 0; i -=2) { |
| 277 | if(lambda[i+1] != A0) |
| 278 | den ^= ALPHA_TO[MODNN(lambda[i+1] + i * root[j])]; |
| 279 | } |
| 280 | #if DEBUG >= 1 |
| 281 | if (den == 0) { |
| 282 | printf("\n ERROR: denominator = 0\n"); |
| 283 | count = -1; |
| 284 | goto finish; |
| 285 | } |
| 286 | #endif |
| 287 | /* Apply error to data */ |
| 288 | if (num1 != 0 && loc[j] >= PAD) { |
| 289 | data[loc[j]-PAD] ^= ALPHA_TO[MODNN(INDEX_OF[num1] + INDEX_OF[num2] + NN - INDEX_OF[den])]; |
| 290 | } |
| 291 | } |
| 292 | finish: |
| 293 | if(eras_pos != NULL){ |
| 294 | for(i=0;i<count;i++) |
| 295 | eras_pos[i] = loc[i]; |
| 296 | } |
| 297 | retval = count; |
| 298 | } |