#include <stdio.h>#include <math.h>#include "bytes.h"#include "bits.h"#include "bch.h"#include "input.h"Go to the source code of this file.
Functions | |
| void | generate_gf () |
| void | gen_poly () |
| void | mencode_bch () |
| int | mdecode_bch (int correction) |
| void | bch_init (bch_type type) |
| void | encode_bch (unsigned long bits, byte *block, bch_type type) |
| int | decode_bch (unsigned long *bits, byte *block, bch_type type, int correction) |
| bch_type | strtobch_type (char *str) |
| char * | bch_type_str (bch_type type) |
| int | code_length (bch_type b) |
| int | info_length (bch_type b) |
Variables | |
| int | m |
| int | n |
| int | length |
| int | k |
| int | t |
| int | d |
| int | p [21] |
| int | alpha_to [1048576] |
| int | index_of [1048576] |
| int | g [548576] |
| int | recd [1048576] |
| int | data [1048576] |
| int | bb [548576] |
| int | debug |
|
|
Definition at line 441 of file bch.c. References BCH15_11, BCH15_5, BCH15_7, BCH31_11, BCH31_6, BCH63_10, BCH63_7, bch_type, gen_poly(), generate_gf(), k, length, m, n, p, and t. Referenced by decode_bch(), and encode_bch(). 00442 {
00443 static bch_type old_type=-1;
00444 int i,j;
00445
00446 /*
00447 * let's only initialize stuff if the parameters have changed.
00448 * that should speed this up a lot.
00449 */
00450
00451 if (old_type != type) {
00452 /*
00453 * initial stuff. set p[] = 0's.
00454 */
00455 for (i=0;i<21;i++)
00456 p[i] = 0;
00457
00458 /*
00459 * setup code specific params.
00460 */
00461 switch(type) {
00462 case BCH15_5:
00463 /* (15,5,7) BCH Code */
00464 k=5; t=3; m = 4; length = 15;
00465 break;
00466 case BCH15_7:
00467 /* (15,7,5) BCH code */
00468 k=7; t=2; m = 4; length = 15;
00469 break;
00470 case BCH15_11:
00471 /* (15,11,3) BCH code */
00472 k=11; t=1; m = 4; length = 15;
00473 break;
00474 case BCH31_6:
00475 /* (31,6,15) BCH code */
00476 k=6; t=7; m = 5; length = 31;
00477 break;
00478 case BCH31_11:
00479 /* (31,11,11) BCH code */
00480 k=11; t=5; m = 5; length = 31;
00481 break;
00482 case BCH63_7:
00483 /* (63,7,31) BCH code */
00484 k=7; t=15; m = 6; length = 63;
00485 break;
00486 case BCH63_10:
00487 /* (63,10,37) BCH code */
00488 k=10; t=13; m = 6; length = 63;
00489 break;
00490 }
00491
00492 /*
00493 * next set n = 2^m-1.
00494 */
00495 n=1;
00496 for (i=0;i<m;i++)
00497 n*=2;
00498 n-=1;
00499
00500 /*
00501 * Set length specific params.
00502 */
00503 switch(type) {
00504 case BCH15_5:
00505 case BCH15_7:
00506 case BCH15_11:
00507 /* p(x) = 11001 */
00508 p[0]=1; p[1]=1; p[4]=1;
00509 break;
00510 case BCH31_6:
00511 case BCH31_11:
00512 /* p(x) = 101001 */
00513 p[0]=1; p[2]=1; p[5]=1;
00514 break;
00515 case BCH63_7:
00516 case BCH63_10:
00517 /* p(x) = 1100001 */
00518 p[0]=1; p[1]=1; p[6]=1;
00519 break;
00520 }
00521 generate_gf();
00522 gen_poly();
00523 }
00524 }
|
|
|
Definition at line 682 of file bch.c. References BCH15_11, BCH15_5, BCH15_7, BCH31_11, BCH31_6, BCH63_10, BCH63_7, and BCHNONE. Referenced by decode_bch(), and encode_bch(). 00683 {
00684 switch(type) {
00685 case BCHNONE: return "None";
00686 case BCH15_5: return "(15,5)";
00687 case BCH15_7: return "(15,7)";
00688 case BCH15_11: return "(15,11)";
00689 case BCH31_6: return "(31,6)";
00690 case BCH31_11: return "(31,11)";
00691 case BCH63_7: return "(63,7)";
00692 case BCH63_10: return "(63,10)";
00693 }
00694 }
|
|
|
Definition at line 697 of file bch.c. References BCH15_11, BCH15_5, BCH15_7, BCH31_11, BCH31_6, BCH63_10, BCH63_7, BCHNONE, and GOLAY23_12. Referenced by demultiplex(), and shift_in(). 00698 {
00699 switch(b)
00700 {
00701 case BCHNONE:
00702 return 7;
00703 case BCH15_5:
00704 case BCH15_7:
00705 case BCH15_11:
00706 return 15;
00707 case BCH31_6:
00708 case BCH31_11:
00709 return 31;
00710 case BCH63_7:
00711 case BCH63_10:
00712 return 63;
00713 case GOLAY23_12:
00714 return 23;
00715 }
00716 return 0;
00717 }
|
|
||||||||||||||||||||
|
Definition at line 580 of file bch.c. References bch_init(), bch_type_str(), debug, error(), getbit(), length, m, mdecode_bch(), and recd. Referenced by deconstruct_header(), and deconstruct_mpl(). 00593 {
00594 int i, j;
00595 unsigned int r=0;
00596 int returnval=0;
00597
00598
00599 if ((correction!=0)&&(correction!=1))
00600 error("decode_bch","incorrect correction mode");
00601
00602 /*
00603 * begin the decoding process
00604 */
00605 if (debug >= 3) {
00606 printf("BCH: decode_bch() - bch_code = %s\n", bch_type_str(type));
00607 }
00608
00609 if (type == BCHNONE) {
00610 *bits = block[0];
00611 return 1;
00612 }
00613
00614 /*
00615 * init codec if necessary
00616 */
00617 bch_init(type);
00618
00619
00620 /*
00621 * copy input to decoder to recd[]
00622 */
00623
00624 for (i=0;i<m-1;i++)
00625 for (j=1;j<8;j++)
00626 recd[(8*i)+j-1] = getbit(block[i],j);
00627
00628 /*
00629 * run the BCH decoding algorithm
00630 */
00631 returnval = mdecode_bch(correction);
00632
00633 /*
00634 * put output of bch coder into *bits;
00635 */
00636
00637 j=1;
00638 r = 0;
00639 for (i=length-k;i<length;i++) {
00640 r += j*recd[i];
00641 j*=2;
00642 }
00643 *bits = r;
00644
00645 if (debug >= 3) {
00646 printf("BCH: decode_bch() bits = %d\n", *bits);
00647 }
00648
00649 return (returnval);
00650 }
|
|
||||||||||||||||
|
Definition at line 529 of file bch.c. References bb, bch_init(), bch_type_str(), data, debug, getbitint(), length, mencode_bch(), recd, and setbit(). Referenced by construct_mpl(), make_backward_control(), and make_forward_control(). 00533 {
00534 int i,j;
00535
00536 if (debug >= 3) {
00537 printf("BCH: encode_bch() type = %s\n", bch_type_str(type));
00538 }
00539
00540 if (type == BCHNONE) {
00541 block[0] = bits & 0xFF;
00542 return;
00543 }
00544
00545 /*
00546 * init codec if necessary
00547 */
00548 bch_init(type);
00549
00550 /*
00551 * put input into encoder.
00552 */
00553
00554 for (i=0;i<k;i++)
00555 data[i] = getbitint(bits,(16-i)); /* data stores the field in REVERSE */
00556
00557 /*
00558 * Run the encoder.
00559 */
00560 mencode_bch();
00561
00562 /*
00563 * Put the redundancy + data into recd[]
00564 */
00565 for (i = 0; i < length - k; i++)
00566 recd[i] = bb[i];
00567 for (i = 0; i < k; i++)
00568 recd[i + length - k] = data[i];
00569
00570 /*
00571 * recd[] now contains the code. put this into Block and return
00572 */
00573 for (i=0;i<=(length/8);i++)
00574 for(j=1;j<=8;j++)
00575 setbit(&(block[i]),j,recd[(8*i)+j-1]);
00576
00577 }
|
|
|
Definition at line 95 of file bch.c. References alpha_to, d, debug, g, index_of, k, length, m, n, and t. Referenced by bch_init(). 00100 {1..(d-1)}. The generator polynomial is calculated
00101 * as the product of linear factors of the form (x+alpha^i), for every i in
00102 * the above cycle sets.
00103 */
00104 {
00105 register int ii, jj, ll, kaux;
00106 register int test, aux, nocycles, root, noterms, rdncy;
00107 int cycle[1024][21], size[1024], min[1024], zeros[1024];
00108
00109 /* Generate cycle sets modulo n, n = 2**m - 1 */
00110 cycle[0][0] = 0;
00111 size[0] = 1;
00112 cycle[1][0] = 1;
00113 size[1] = 1;
00114 jj = 1; /* cycle set index */
00115 if (m > 9) {
00116 printf("BCH: gen_poly() - Computing cycle sets modulo %d\n", n);
00117 }
00118 do {
00119 /* Generate the jj-th cycle set */
00120 ii = 0;
00121 do {
00122 ii++;
00123 cycle[jj][ii] = (cycle[jj][ii - 1] * 2) % n;
00124 size[jj]++;
00125 aux = (cycle[jj][ii] * 2) % n;
00126 } while (aux != cycle[jj][0]);
00127 /* Next cycle set representative */
00128 ll = 0;
00129 do {
00130 ll++;
00131 test = 0;
00132 for (ii = 1; ((ii <= jj) && (!test)); ii++)
00133 /* Examine previous cycle sets */
00134 for (kaux = 0; ((kaux < size[ii]) && (!test)); kaux++)
00135 if (ll == cycle[ii][kaux])
00136 test = 1;
00137 } while ((test) && (ll < (n - 1)));
00138 if (!(test)) {
00139 jj++; /* next cycle set index */
00140 cycle[jj][0] = ll;
00141 size[jj] = 1;
00142 }
00143 } while (ll < (n - 1));
00144 nocycles = jj; /* number of cycle sets modulo n */
00145
00146 d = 2 * t + 1;
00147 /* Search for roots 1, 2, ..., d-1 in cycle sets */
00148 kaux = 0;
00149 rdncy = 0;
00150 for (ii = 1; ii <= nocycles; ii++) {
00151 min[kaux] = 0;
00152 test = 0;
00153 for (jj = 0; ((jj < size[ii]) && (!test)); jj++)
00154 for (root = 1; ((root < d) && (!test)); root++)
00155 if (root == cycle[ii][jj]) {
00156 test = 1;
00157 min[kaux] = ii;
00158 }
00159 if (min[kaux]) {
00160 rdncy += size[min[kaux]];
00161 kaux++;
00162 }
00163 }
00164 noterms = kaux;
00165 kaux = 1;
00166 for (ii = 0; ii < noterms; ii++)
00167 for (jj = 0; jj < size[min[ii]]; jj++) {
00168 zeros[kaux] = cycle[min[ii]][jj];
00169 kaux++;
00170 }
00171 k = length - rdncy;
00172
00173 /* Compute the generator polynomial */
00174 g[0] = alpha_to[zeros[1]];
00175 g[1] = 1; /* g(x) = (X + zeros[1]) initially */
00176 for (ii = 2; ii <= rdncy; ii++) {
00177 g[ii] = 1;
00178 for (jj = ii - 1; jj > 0; jj--)
00179 if (g[jj] != 0)
00180 g[jj] = g[jj - 1] ^ alpha_to[(index_of[g[jj]] + zeros[ii]) % n];
00181 else
00182 g[jj] = g[jj - 1];
00183 g[0] = alpha_to[(index_of[g[0]] + zeros[ii]) % n];
00184 }
00185
00186 if (debug >= 5) {
00187 printf("BCH: gen_poly() - g(x) = ");
00188 for (ii = 0; ii <= rdncy; ii++) {
00189 printf("%d", g[ii]);
00190 if (ii && ((ii % 50) == 0))
00191 printf("\n");
00192 }
00193 printf("\n");
00194 }
00195 }
|
|
|
Definition at line 59 of file bch.c. References alpha_to, index_of, m, and p. Referenced by bch_init(). 00064 : 00065 * index->polynomial form: alpha_to[] contains j=alpha^i; 00066 * polynomial form -> index form: index_of[j=alpha^i] = i 00067 * 00068 * alpha=2 is the primitive element of GF(2**m) 00069 */ 00070 { 00071 register int i, mask; 00072 00073 mask = 1; 00074 alpha_to[m] = 0; 00075 for (i = 0; i < m; i++) { 00076 alpha_to[i] = mask; 00077 index_of[alpha_to[i]] = i; 00078 if (p[i] != 0) 00079 alpha_to[m] ^= mask; 00080 mask <<= 1; 00081 } 00082 index_of[alpha_to[m]] = m; 00083 mask >>= 1; 00084 for (i = m + 1; i < n; i++) { 00085 if (alpha_to[i - 1] >= mask) 00086 alpha_to[i] = alpha_to[m] ^ ((alpha_to[i - 1] ^ mask) << 1); 00087 else 00088 alpha_to[i] = alpha_to[i - 1] << 1; 00089 index_of[alpha_to[i]] = i; 00090 } 00091 index_of[0] = -1; 00092 }
|
|
|
Definition at line 720 of file bch.c. References BCH15_11, BCH15_5, BCH15_7, BCH31_11, BCH31_6, BCH63_10, BCH63_7, and BCHNONE. 00721 {
00722 switch(b)
00723 {
00724 case BCHNONE: return 8;
00725 case BCH15_5: return 5;
00726 case BCH15_7: return 7;
00727 case BCH15_11: return 11;
00728 case BCH31_6: return 6;
00729 case BCH31_11: return 11;
00730 case BCH63_7: return 7;
00731 case BCH63_10: return 10;
00732 }
00733 return 0;
00734 }
|
|
|
Definition at line 229 of file bch.c. References alpha_to, d, debug, index_of, n, and recd. Referenced by decode_bch(). 00252 {
00253 register int i, j, u, q, t2, count = 0, syn_error = 0;
00254 int elp[1026][1024], d[1026], l[1026], u_lu[1026], s[1025];
00255 int root[200], loc[200], err[1024], reg[201];
00256 int returnval = 1;
00257
00258 t2 = 2 * t;
00259
00260 /* first form the syndromes */
00261 if (debug >= 3) {
00262 printf("BCH: mdecode_bch() - S(x) = ");
00263 }
00264
00265 for (i = 1; i <= t2; i++) {
00266 s[i] = 0;
00267 for (j = 0; j < length; j++)
00268 if (recd[j] != 0)
00269 s[i] ^= alpha_to[(i * j) % n];
00270 if (s[i] != 0) {
00271 syn_error = 1; /* set error flag if non-zero syndrome */
00272 /* if we are only detecting, bail out */
00273 if (!correction)
00274 return 0;
00275 }
00276 /*
00277 * Note: If the code is used only for ERROR DETECTION, then
00278 * exit program here indicating the presence of errors.
00279 */
00280 /* convert syndrome from polynomial form to index form */
00281 s[i] = index_of[s[i]];
00282 if (debug >= 3) {
00283 printf("%3d ", s[i]);
00284 }
00285 }
00286 if (debug >= 3) {
00287 printf("\n");
00288 }
00289
00290 if (syn_error) { /* if there are errors, try to correct them */
00291 /*
00292 * Compute the error location polynomial via the Berlekamp
00293 * iterative algorithm. Following the terminology of Lin and
00294 * Costello's book : d[u] is the 'mu'th discrepancy, where
00295 * u='mu'+1 and 'mu' (the Greek letter!) is the step number
00296 * ranging from -1 to 2*t (see L&C), l[u] is the degree of
00297 * the elp at that step, and u_l[u] is the difference between
00298 * the step number and the degree of the elp.
00299 */
00300 /* initialise table entries */
00301 d[0] = 0; /* index form */
00302 d[1] = s[1]; /* index form */
00303 elp[0][0] = 0; /* index form */
00304 elp[1][0] = 1; /* polynomial form */
00305 for (i = 1; i < t2; i++) {
00306 elp[0][i] = -1; /* index form */
00307 elp[1][i] = 0; /* polynomial form */
00308 }
00309 l[0] = 0;
00310 l[1] = 0;
00311 u_lu[0] = -1;
00312 u_lu[1] = 0;
00313 u = 0;
00314
00315 do {
00316 u++;
00317 if (d[u] == -1) {
00318 l[u + 1] = l[u];
00319 for (i = 0; i <= l[u]; i++) {
00320 elp[u + 1][i] = elp[u][i];
00321 elp[u][i] = index_of[elp[u][i]];
00322 }
00323 } else
00324 /*
00325 * search for words with greatest u_lu[q] for
00326 * which d[q]!=0
00327 */
00328 {
00329 q = u - 1;
00330 while ((d[q] == -1) && (q > 0))
00331 q--;
00332 /* have found first non-zero d[q] */
00333 if (q > 0) {
00334 j = q;
00335 do {
00336 j--;
00337 if ((d[j] != -1) && (u_lu[q] < u_lu[j]))
00338 q = j;
00339 } while (j > 0);
00340 }
00341
00342 /*
00343 * have now found q such that d[u]!=0 and
00344 * u_lu[q] is maximum
00345 */
00346 /* store degree of new elp polynomial */
00347 if (l[u] > l[q] + u - q)
00348 l[u + 1] = l[u];
00349 else
00350 l[u + 1] = l[q] + u - q;
00351
00352 /* form new elp(x) */
00353 for (i = 0; i < t2; i++)
00354 elp[u + 1][i] = 0;
00355 for (i = 0; i <= l[q]; i++)
00356 if (elp[q][i] != -1)
00357 elp[u + 1][i + u - q] =
00358 alpha_to[(d[u] + n - d[q] + elp[q][i]) % n];
00359 for (i = 0; i <= l[u]; i++) {
00360 elp[u + 1][i] ^= elp[u][i];
00361 elp[u][i] = index_of[elp[u][i]];
00362 }
00363 }
00364 u_lu[u + 1] = u - l[u + 1];
00365
00366 /* form (u+1)th discrepancy */
00367 if (u < t2) {
00368 /* no discrepancy computed on last iteration */
00369 if (s[u + 1] != -1)
00370 d[u + 1] = alpha_to[s[u + 1]];
00371 else
00372 d[u + 1] = 0;
00373 for (i = 1; i <= l[u + 1]; i++)
00374 if ((s[u + 1 - i] != -1) && (elp[u + 1][i] != 0))
00375 d[u + 1] ^= alpha_to[(s[u + 1 - i]
00376 + index_of[elp[u + 1][i]]) % n];
00377 /* put d[u+1] into index form */
00378 d[u + 1] = index_of[d[u + 1]];
00379 }
00380 } while ((u < t2) && (l[u + 1] <= t));
00381
00382 u++;
00383 if (l[u] <= t) {/* Can correct errors */
00384 /* put elp into index form */
00385 for (i = 0; i <= l[u]; i++)
00386 elp[u][i] = index_of[elp[u][i]];
00387
00388 if (debug >= 5) {
00389 printf("BCH: mencode_bch() - sigma(x) = ");
00390 for (i = 0; i <= l[u]; i++)
00391 printf("%3d ", elp[u][i]);
00392 printf("\n");
00393 }
00394
00395 if (debug >= 3) {
00396 printf("BCH: mencode_bch() - Roots: ");
00397 }
00398 /* Chien search: find roots of the error location polynomial */
00399 for (i = 1; i <= l[u]; i++)
00400 reg[i] = elp[u][i];
00401 count = 0;
00402 for (i = 1; i <= n; i++) {
00403 q = 1;
00404 for (j = 1; j <= l[u]; j++)
00405 if (reg[j] != -1) {
00406 reg[j] = (reg[j] + j) % n;
00407 q ^= alpha_to[reg[j]];
00408 }
00409 if (!q) { /* store root and error
00410 * location number indices */
00411 root[count] = i;
00412 loc[count] = n - i;
00413 count++;
00414 if (debug >=3 )
00415 printf("%3d ", n - i);
00416 }
00417 }
00418 if (debug >= 3)
00419 printf("\n");
00420 if (count == l[u]) {
00421 /* no. roots = degree of elp hence <= t errors */
00422 for (i = 0; i < l[u]; i++)
00423 recd[loc[i]] ^= 1;
00424 }
00425 else{ /* elp has degree >t hence cannot solve */
00426 if (debug >=3)
00427 printf("mdecode_bch() - Incomplete decoding: errors detected\n");
00428 }
00429 }
00430 }
00431 return returnval;
00432 }
|
|
|
Definition at line 199 of file bch.c. References bb, data, g, k, and length. Referenced by encode_bch(). 00205 {
00206 register int i, j;
00207 register int feedback;
00208
00209 for (i = 0; i < length - k; i++)
00210 bb[i] = 0;
00211 for (i = k - 1; i >= 0; i--) {
00212 feedback = data[i] ^ bb[length - k - 1];
00213 if (feedback != 0) {
00214 for (j = length - k - 1; j > 0; j--)
00215 if (g[j] != 0)
00216 bb[j] = bb[j - 1] ^ feedback;
00217 else
00218 bb[j] = bb[j - 1];
00219 bb[0] = g[0] && feedback;
00220 } else {
00221 for (j = length - k - 1; j > 0; j--)
00222 bb[j] = bb[j - 1];
00223 bb[0] = 0;
00224 }
00225 }
00226 }
|
|
|
Definition at line 655 of file bch.c. References bch_type, and equals(). Referenced by mux_config(). 00656 {
00657 int i;
00658 i=strlen(str)-1;
00659 while (i > 0 && (str[i]==' ' || str[i]=='\t'))
00660 str[i]=0;
00661
00662 if (equals(str, "BCH15_5"))
00663 return BCH15_5;
00664 else if (equals(str, "BCH15_7"))
00665 return BCH15_7;
00666 else if (equals(str, "BCH15_11"))
00667 return BCH15_11;
00668 else if (equals(str, "BCH31_6"))
00669 return BCH31_6;
00670 else if (equals(str, "BCH31_11"))
00671 return BCH31_11;
00672 else if (equals(str, "BCH63_7"))
00673 return BCH63_7;
00674 else if (equals(str, "BCH63_10"))
00675 return BCH63_10;
00676 else if (equals(str, "GOLAY23_12"))
00677 return GOLAY23_12;
00678 else
00679 return BCHNONE;
00680 }
|
|
|
Definition at line 50 of file bch.c. Referenced by gen_poly(), generate_gf(), and mdecode_bch(). |
|
|
Definition at line 51 of file bch.c. Referenced by encode_bch(), and mencode_bch(). |
|
|
Definition at line 48 of file bch.c. Referenced by gen_poly(), and mdecode_bch(). |
|
|
Definition at line 51 of file bch.c. Referenced by encode_bch(), and mencode_bch(). |
|
|
|
|
|
Definition at line 50 of file bch.c. Referenced by gen_poly(), and mencode_bch(). |
|
|
Definition at line 50 of file bch.c. Referenced by gen_poly(), generate_gf(), and mdecode_bch(). |
|
|
Definition at line 48 of file bch.c. Referenced by bch_init(), gen_poly(), and mencode_bch(). |
|
|
Definition at line 48 of file bch.c. Referenced by bch_init(), decode_bch(), encode_bch(), gen_poly(), and mencode_bch(). |
|
|
Definition at line 48 of file bch.c. Referenced by bch_init(), decode_bch(), gen_poly(), and generate_gf(). |
|
|
Definition at line 48 of file bch.c. Referenced by bch_init(), gen_poly(), and mdecode_bch(). |
|
|
Definition at line 49 of file bch.c. Referenced by bch_init(), and generate_gf(). |
|
|
Definition at line 51 of file bch.c. Referenced by decode_bch(), encode_bch(), and mdecode_bch(). |
|
|
Definition at line 48 of file bch.c. Referenced by bch_init(), and gen_poly(). |
1.3.9.1