Lines Matching +full:- +full:i
2 * ECC algorithm for M-systems disk on chip. We use the excellent Reed
22 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
42 #define KK (1023-4) /* Number of data symbols per block */
45 #define NN ((1 << MM) - 1)
66 /* Compute x % NN, where NN is 2**MM - 1,
73 x -= NN; in modnn()
81 for(ci=(n)-1;ci >=0;ci--)\
87 for(ci=(n)-1;ci >=0;ci--)\
93 for(ci=(n)-1;ci >=0;ci--)\
100 lookup tables: index->polynomial form alpha_to[] contains j=alpha**i;
101 polynomial form -> index form index_of[j=alpha**i] = i
106 0 <= i <= 2^m-2,
107 @^i = a(0) + a(1) @ + a(2) @^2 + ... + a(m-1) @^(m-1)
108 where the binary vector (a(0),a(1),a(2),...,a(m-1)) is the representation
109 of the integer "alpha_to[i]" with a(0) being the LSB and a(m-1) the MSB. Thus for
116 a(0) + a(1) @ + a(2) @^2 + ... + a(m-1) @^(m-1)
117 we consider the integer "i" whose binary representation with a(0) being LSB
118 and a(m-1) MSB is (a(0),a(1),...,a(m-1)) and locate the entry
119 "index_of[i]". Now, @^index_of[i] is that element whose polynomial
120 representation is (a(0),a(1),a(2),...,a(m-1)).
122 The element alpha_to[2^m-1] = 0 always signifying that the
133 register int i, mask; in generate_gf() local
137 for (i = 0; i < MM; i++) { in generate_gf()
138 Alpha_to[i] = mask; in generate_gf()
139 Index_of[Alpha_to[i]] = i; in generate_gf()
140 /* If Pp[i] == 1 then, term @^i occurs in poly-repr of @^MM */ in generate_gf()
141 if (Pp[i] != 0) in generate_gf()
142 Alpha_to[MM] ^= mask; /* Bit-wise EXOR operation */ in generate_gf()
143 mask <<= 1; /* single left-shift */ in generate_gf()
147 * Have obtained poly-repr of @^MM. Poly-repr of @^(i+1) is given by in generate_gf()
148 * poly-repr of @^i shifted left one-bit and accounting for any @^MM in generate_gf()
149 * term that may occur when poly-repr of @^i is shifted. in generate_gf()
152 for (i = MM + 1; i < NN; i++) { in generate_gf()
153 if (Alpha_to[i - 1] >= mask) in generate_gf()
154 Alpha_to[i] = Alpha_to[MM] ^ ((Alpha_to[i - 1] ^ mask) << 1); in generate_gf()
156 Alpha_to[i] = Alpha_to[i - 1] << 1; in generate_gf()
157 Index_of[Alpha_to[i]] = i; in generate_gf()
168 * Return number of symbols corrected, or -1 if codeword is illegal
169 * or uncorrectable. If eras_pos is non-null, the detected error locations
170 * are written back. NOTE! This array must be at least NN-KK elements long.
172 * to retrieve the correct data : data[erase_pos[i]] ^= erase_val[i] .
175 * maximum # of errors correctable is t_after_eras = floor((NN-KK-no_eras)/2).
178 * in R. Blahut's "Theory ... of Error-Correcting Codes".
186 gf bb[NN - KK + 1], gf eras_val[NN-KK], int eras_pos[NN-KK], in eras_dec_rs()
190 int i, j, r,k; in eras_dec_rs() local
192 gf lambda[NN-KK + 1], s[NN-KK + 1]; /* Err+Eras Locator poly in eras_dec_rs()
194 gf b[NN-KK + 1], t[NN-KK + 1], omega[NN-KK + 1]; in eras_dec_rs()
195 gf root[NN-KK], reg[NN-KK + 1], loc[NN-KK]; in eras_dec_rs()
199 for(i=0;i<NN-KK;i++) in eras_dec_rs()
200 syn_error |= bb[i]; in eras_dec_rs()
210 for(i=1;i<=NN-KK;i++){ in eras_dec_rs()
211 s[i] = bb[0]; in eras_dec_rs()
213 for(j=1;j<NN-KK;j++){ in eras_dec_rs()
218 for(i=1;i<=NN-KK;i++) in eras_dec_rs()
219 s[i] ^= Alpha_to[modnn(tmp + (B0+i-1)*PRIM*j)]; in eras_dec_rs()
225 for(i=1;i<=NN-KK;i++) { in eras_dec_rs()
226 tmp = Index_of[s[i]]; in eras_dec_rs()
228 tmp = modnn(tmp + 2 * KK * (B0+i-1)*PRIM); in eras_dec_rs()
229 s[i] = tmp; in eras_dec_rs()
232 CLEAR(&lambda[1],NN-KK); in eras_dec_rs()
238 for (i = 1; i < no_eras; i++) { in eras_dec_rs()
239 u = modnn(PRIM*eras_pos[i]); in eras_dec_rs()
240 for (j = i+1; j > 0; j--) { in eras_dec_rs()
241 tmp = Index_of[lambda[j - 1]]; in eras_dec_rs()
251 for(i=1;i<=no_eras;i++) in eras_dec_rs()
252 reg[i] = Index_of[lambda[i]]; in eras_dec_rs()
254 for (i = 1,k=NN-Ldec; i <= NN; i++,k = modnn(NN+k-Ldec)) { in eras_dec_rs()
264 root[count] = i; in eras_dec_rs()
270 count = -1; in eras_dec_rs()
275 for (i = 0; i < count; i++) in eras_dec_rs()
276 printf("%d ", loc[i]); in eras_dec_rs()
281 for(i=0;i<NN-KK+1;i++) in eras_dec_rs()
282 b[i] = Index_of[lambda[i]]; in eras_dec_rs()
285 * Begin Berlekamp-Massey algorithm to determine error+erasure in eras_dec_rs()
290 while (++r <= NN-KK) { /* r is the step number */ in eras_dec_rs()
291 /* Compute discrepancy at the r-th step in poly-form */ in eras_dec_rs()
293 for (i = 0; i < r; i++){ in eras_dec_rs()
294 if ((lambda[i] != 0) && (s[r - i] != A0)) { in eras_dec_rs()
295 discr_r ^= Alpha_to[modnn(Index_of[lambda[i]] + s[r - i])]; in eras_dec_rs()
300 /* 2 lines below: B(x) <-- x*B(x) */ in eras_dec_rs()
301 COPYDOWN(&b[1],b,NN-KK); in eras_dec_rs()
304 /* 7 lines below: T(x) <-- lambda(x) - discr_r*x*b(x) */ in eras_dec_rs()
306 for (i = 0 ; i < NN-KK; i++) { in eras_dec_rs()
307 if(b[i] != A0) in eras_dec_rs()
308 t[i+1] = lambda[i+1] ^ Alpha_to[modnn(discr_r + b[i])]; in eras_dec_rs()
310 t[i+1] = lambda[i+1]; in eras_dec_rs()
312 if (2 * el <= r + no_eras - 1) { in eras_dec_rs()
313 el = r + no_eras - el; in eras_dec_rs()
315 * 2 lines below: B(x) <-- inv(discr_r) * in eras_dec_rs()
318 for (i = 0; i <= NN-KK; i++) in eras_dec_rs()
319 b[i] = (lambda[i] == 0) ? A0 : modnn(Index_of[lambda[i]] - discr_r + NN); in eras_dec_rs()
321 /* 2 lines below: B(x) <-- x*B(x) */ in eras_dec_rs()
322 COPYDOWN(&b[1],b,NN-KK); in eras_dec_rs()
325 COPY(lambda,t,NN-KK+1); in eras_dec_rs()
331 for(i=0;i<NN-KK+1;i++){ in eras_dec_rs()
332 lambda[i] = Index_of[lambda[i]]; in eras_dec_rs()
333 if(lambda[i] != A0) in eras_dec_rs()
334 deg_lambda = i; in eras_dec_rs()
340 COPY(®[1],&lambda[1],NN-KK); in eras_dec_rs()
342 for (i = 1,k=NN-Ldec; i <= NN; i++,k = modnn(NN+k-Ldec)) { in eras_dec_rs()
344 for (j = deg_lambda; j > 0; j--){ in eras_dec_rs()
352 /* store root (index-form) and error location number */ in eras_dec_rs()
353 root[count] = i; in eras_dec_rs()
366 count = -1; in eras_dec_rs()
371 * x**(NN-KK)). in index form. Also find deg(omega). in eras_dec_rs()
374 for (i = 0; i < NN-KK;i++){ in eras_dec_rs()
376 j = (deg_lambda < i) ? deg_lambda : i; in eras_dec_rs()
377 for(;j >= 0; j--){ in eras_dec_rs()
378 if ((s[i + 1 - j] != A0) && (lambda[j] != A0)) in eras_dec_rs()
379 tmp ^= Alpha_to[modnn(s[i + 1 - j] + lambda[j])]; in eras_dec_rs()
382 deg_omega = i; in eras_dec_rs()
383 omega[i] = Index_of[tmp]; in eras_dec_rs()
385 omega[NN-KK] = A0; in eras_dec_rs()
388 * Compute error values in poly-form. num1 = omega(inv(X(l))), num2 = in eras_dec_rs()
389 * inv(X(l))**(B0-1) and den = lambda_pr(inv(X(l))) all in poly-form in eras_dec_rs()
391 for (j = count-1; j >=0; j--) { in eras_dec_rs()
393 for (i = deg_omega; i >= 0; i--) { in eras_dec_rs()
394 if (omega[i] != A0) in eras_dec_rs()
395 num1 ^= Alpha_to[modnn(omega[i] + i * root[j])]; in eras_dec_rs()
397 num2 = Alpha_to[modnn(root[j] * (B0 - 1) + NN)]; in eras_dec_rs()
400 /* lambda[i+1] for i even is the formal derivative lambda_pr of lambda[i] */ in eras_dec_rs()
401 for (i = min(deg_lambda,NN-KK-1) & ~1; i >= 0; i -=2) { in eras_dec_rs()
402 if(lambda[i+1] != A0) in eras_dec_rs()
403 den ^= Alpha_to[modnn(lambda[i+1] + i * root[j])]; in eras_dec_rs()
409 /* Convert to dual- basis */ in eras_dec_rs()
410 count = -1; in eras_dec_rs()
415 eras_val[j] = Alpha_to[modnn(Index_of[num1] + Index_of[num2] + NN - Index_of[den])]; in eras_dec_rs()
421 for(i=0;i<count;i++) in eras_dec_rs()
422 eras_pos[i] = loc[i]; in eras_dec_rs()
437 * sector), or -1 if error
441 int parity, i, nb_errors; in doc_decode_ecc() local
442 gf bb[NN - KK + 1]; in doc_decode_ecc()
443 gf error_val[NN-KK]; in doc_decode_ecc()
444 int error_pos[NN-KK], pos, bitpos, index, val; in doc_decode_ecc()
450 return -1; in doc_decode_ecc()
455 return -1; in doc_decode_ecc()
473 for(i=0;i<nb_errors;i++) { in doc_decode_ecc()
474 pos = error_pos[i]; in doc_decode_ecc()
476 nb_errors = -1; in doc_decode_ecc()
481 pos = 10 * (NB_DATA - 1 - pos) - 6; in doc_decode_ecc()
488 val = error_val[i] >> (2 + bitpos); in doc_decode_ecc()
499 val = error_val[i] << (8 - bitpos); in doc_decode_ecc()
509 nb_errors = -1; in doc_decode_ecc()