求BCH码的编译码程序

summersun512

这是我的毕业设计题目，难度太高了，我是从头学起的，希望高人帮帮忙，什么语言实现的编译码都可以，我会自行用C进行改写，拜托大家了~

summersun512

难道真的没有高人会吗？[em03]

abc3xyz

，呵呵，要不要干脆把论文发给你。。。xdu的？用那本厚厚的纠错码？
附    录
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
int             m, n, length, k, t, d;
int             p[21];
int             alpha_to[1048576], index_of[1048576], g[548576];
int             recd[1048576], data[1048576], bb[548576];
int             seed;
int             numerr, errpos[1024], decerror = 0;
void
read_p()
{
        int                        i, ninf;
        printf("\nEnter a value of m such that the code length is\n");
        printf("2**(m-1) - 1 < length <= 2**m - 1\n\n");
    do {
           printf("Enter m (between 2 and 20): ");
           scanf("%d", &m);
    } while ( !(m>1) || !(m<21) );
        for (i=1; i<m; i++)
                p = 0;
        p[0] = p[m] = 1;
        if (m == 2)                        p[1] = 1;
        else if (m == 3)        p[1] = 1;
        else if (m == 4)        p[1] = 1;
        else if (m == 5)        p[2] = 1;
        else if (m == 6)        p[1] = 1;
        else if (m == 7)        p[1] = 1;
        else if (m == 8)        p[4] = p[5] = p[6] = 1;
        else if (m == 9)        p[4] = 1;
        else if (m == 10)        p[3] = 1;
        else if (m == 11)        p[2] = 1;
        else if (m == 12)        p[3] = p[4] = p[7] = 1;
        else if (m == 13)        p[1] = p[3] = p[4] = 1;
        else if (m == 14)        p[1] = p[11] = p[12] = 1;
        else if (m == 15)        p[1] = 1;
        else if (m == 16)        p[2] = p[3] = p[5] = 1;
        else if (m == 17)        p[3] = 1;
        else if (m == 18)        p[7] = 1;
        else if (m == 19)        p[1] = p[5] = p[6] = 1;
        else if (m == 20)        p[3] = 1;
        printf("p(x) = ");
    n = 1;
        for (i = 0; i <= m; i++) {
        n *= 2;
                printf("%1d", p);
        }
        printf("\n");
        n = n / 2 - 1;
        ninf = (n + 1) / 2 - 1;
        do  {
                printf("Enter code length (%d < length <= %d): ", ninf, n);
                scanf("%d", &length);
        } while ( !((length <= n)&&(length>ninf)) );
}

void
generate_gf()

{
        register int    i, mask;

        mask = 1;
        alpha_to[m] = 0;
        for (i = 0; i < m; i++) {
                alpha_to = mask;
                index_of[alpha_to] = i;
                if (p != 0)
                        alpha_to[m] ^= mask;
                mask <<= 1;
        }
        index_of[alpha_to[m]] = m;
        mask >>= 1;
        for (i = m + 1; i < n; i++) {
                if (alpha_to[i - 1] >= mask)
                  alpha_to = alpha_to[m] ^ ((alpha_to[i - 1] ^ mask) << 1);
                else
                  alpha_to = alpha_to[i - 1] << 1;
                index_of[alpha_to] = i;
        }
        index_of[0] = -1;
}


void
gen_poly()

{
        register int        ii, jj, ll, kaux;
        register int        test, aux, nocycles, root, noterms, rdncy;
        int             cycle[1024][21], size[1024], min[1024], zeros[1024];

       
        cycle[0][0] = 0;
        size[0] = 1;
        cycle[1][0] = 1;
        size[1] = 1;
        jj = 1;                       
        if (m > 9)  {
                printf("Computing cycle sets modulo %d\n", n);
                printf("(This may take some time)...\n");
        }
        do {
               
                ii = 0;
                do {
                        ii++;
                        cycle[jj][ii] = (cycle[jj][ii - 1] * 2) % n;
                        size[jj]++;
                        aux = (cycle[jj][ii] * 2) % n;
                } while (aux != cycle[jj][0]);
               
                ll = 0;
                do {
                        ll++;
                        test = 0;
                        for (ii = 1; ((ii <= jj) && (!test)); ii++)       
                       
                          for (kaux = 0; ((kaux < size[ii]) && (!test)); kaux++)
                             if (ll == cycle[ii][kaux])
                                test = 1;
                } while ((test) && (ll < (n - 1)));
                if (!(test)) {
                        jj++;       
                        cycle[jj][0] = ll;
                        size[jj] = 1;
                }
        } while (ll < (n - 1));
        nocycles = jj;               

        printf("Enter the error correcting capability, t: ");
        scanf("%d", &t);

        d = 2 * t + 1;

       
        kaux = 0;
        rdncy = 0;
        for (ii = 1; ii <= nocycles; ii++) {
                min[kaux] = 0;
                test = 0;
                for (jj = 0; ((jj < size[ii]) && (!test)); jj++)
                        for (root = 1; ((root < d) && (!test)); root++)
                                if (root == cycle[ii][jj])  {
                                        test = 1;
                                        min[kaux] = ii;
                                }
                if (min[kaux]) {
                        rdncy += size[min[kaux]];
                        kaux++;
                }
        }
        noterms = kaux;
        kaux = 1;
        for (ii = 0; ii < noterms; ii++)
                for (jj = 0; jj < size[min[ii]]; jj++) {
                        zeros[kaux] = cycle[min[ii]][jj];
                        kaux++;
                }

        k = length - rdncy;

    if (k<0)
      {
         printf("Parameters invalid!\n");
         exit(0);
      }

        printf("This is a (%d, %d, %d) binary BCH code\n", length, k, d);

       
        g[0] = alpha_to[zeros[1]];
        g[1] = 1;               
        for (ii = 2; ii <= rdncy; ii++) {
          g[ii] = 1;
          for (jj = ii - 1; jj > 0; jj--)
            if (g[jj] != 0)
              g[jj] = g[jj - 1] ^ alpha_to[(index_of[g[jj]] + zeros[ii]) % n];
            else
              g[jj] = g[jj - 1];
          g[0] = alpha_to[(index_of[g[0]] + zeros[ii]) % n];
        }
        printf("Generator polynomial:\ng(x) = ");
        for (ii = 0; ii <= rdncy; ii++) {
          printf("%d", g[ii]);
          if (ii && ((ii % 50) == 0))
            printf("\n");
        }
        printf("\n");
}


void
encode_bch()

{
        register int    i, j;
        register int    feedback;

        for (i = 0; i < length - k; i++)
                bb = 0;
        for (i = k - 1; i >= 0; i--) {
                feedback = data ^ bb[length - k - 1];
                if (feedback != 0) {
                        for (j = length - k - 1; j > 0; j--)
                                if (g[j] != 0)
                                        bb[j] = bb[j - 1] ^ feedback;
                                else
                                        bb[j] = bb[j - 1];
                        bb[0] = g[0] && feedback;
                } else {
                        for (j = length - k - 1; j > 0; j--)
                                bb[j] = bb[j - 1];
                        bb[0] = 0;
                }
        }
}


void
decode_bch()

{
        register int    i, j, u, q, t2, count = 0, syn_error = 0;
        int             elp[1026][1024], d[1026], l[1026], u_lu[1026], s[1025];
        int             root[200], loc[200], err[1024], reg[201];

        t2 = 2 * t;

        /* first form the syndromes */
        printf("S(x) = ");
        for (i = 1; i <= t2; i++) {
                s = 0;
                for (j = 0; j < length; j++)
                        if (recd[j] != 0)
                                s ^= alpha_to[(i * j) % n];
                if (s != 0)
                        syn_error = 1;
                s = index_of[s];
                printf("%3d ", s);
        }
        printf("\n");

        if (syn_error) {       
                d[0] = 0;                       
                d[1] = s[1];               
                elp[0][0] = 0;               
                elp[1][0] = 1;               
                for (i = 1; i < t2; i++) {
                        elp[0] = -1;       
                        elp[1] = 0;       
                }
                l[0] = 0;
                l[1] = 0;
                u_lu[0] = -1;
                u_lu[1] = 0;
                u = 0;

                do {
                        u++;
                        if (d == -1) {
                                l[u + 1] = l;
                                for (i = 0; i <= l; i++) {
                                        elp[u + 1] = elp;
                                        elp = index_of[elp];
                                }
                        } else
                               
                        {
                                q = u - 1;
                                while ((d[q] == -1) && (q > 0))
                                        q--;
                               
                                if (q > 0) {
                                  j = q;
                                  do {
                                    j--;
                                    if ((d[j] != -1) && (u_lu[q] < u_lu[j]))
                                      q = j;
                                  } while (j > 0);
                                }

                               
                                if (l > l[q] + u - q)
                                        l[u + 1] = l;
                                else
                                        l[u + 1] = l[q] + u - q;

                               
                                for (i = 0; i < t2; i++)
                                        elp[u + 1] = 0;
                                for (i = 0; i <= l[q]; i++)
                                        if (elp[q] != -1)
                                                elp[u + 1][i + u - q] =
                                   alpha_to[(d + n - d[q] + elp[q]) % n];
                                for (i = 0; i <= l; i++) {
                                        elp[u + 1] ^= elp;
                                        elp = index_of[elp];
                                }
                        }
                        u_lu[u + 1] = u - l[u + 1];

                       
                        if (u < t2) {       
                       
                          if (s[u + 1] != -1)
                            d[u + 1] = alpha_to[s[u + 1]];
                          else
                            d[u + 1] = 0;
                            for (i = 1; i <= l[u + 1]; i++)
                              if ((s[u + 1 - i] != -1) && (elp[u + 1] != 0))
                                d[u + 1] ^= alpha_to[(s[u + 1 - i]
                                              + index_of[elp[u + 1]]) % n];
                          
                          d[u + 1] = index_of[d[u + 1]];       
                        }
                } while ((u < t2) && (l[u + 1] <= t));

                u++;
                if (l <= t) {
                        for (i = 0; i <= l; i++)
                                elp = index_of[elp];

                        printf("sigma(x) = ");
                        for (i = 0; i <= l; i++)
                                printf("%3d ", elp);
                        printf("\n");
                        printf("Roots: ");

                        for (i = 1; i <= l; i++)
                                reg = elp;
                        count = 0;
                        for (i = 1; i <= n; i++) {
                                q = 1;
                                for (j = 1; j <= l; j++)
                                        if (reg[j] != -1) {
                                                reg[j] = (reg[j] + j) % n;
                                                q ^= alpha_to[reg[j]];
                                        }
                                if (!q) {       
                                        root[count] = i;
                                        loc[count] = n - i;
                                        count++;
                                        printf("%3d ", n - i);
                                }
                        }
                        printf("\n");
                        if (count == l)       
                       
                                for (i = 0; i < l; i++)
                                        recd[loc] ^= 1;
                        else       
                                printf("Incomplete decoding: errors detected\n");
                }
        }
}



main()
{
        int             i;

        read_p();               
        generate_gf();         
        gen_poly();            

       
        seed = 131073;
        srandom(seed);
        for (i = 0; i < k; i++)
                data = ( random() & 65536 ) >> 16;

        encode_bch();           

       
        for (i = 0; i < length - k; i++)
                recd = bb;
        for (i = 0; i < k; i++)
                recd[i + length - k] = data;
        printf("Code polynomial:\nc(x) = ");
        for (i = 0; i < length; i++) {
                printf("%1d", recd);
                if (i && ((i % 50) == 0))
                        printf("\n");
        }
        printf("\n");

        printf("Enter the number of errors:\n");
        scanf("%d", &numerr);       
    printf("Enter error locations (integers between");
    printf(" 0 and %d): ", length-1);
       
        for (i = 0; i < numerr; i++)
                scanf("%d", &errpos);
        if (numerr)
                for (i = 0; i < numerr; i++)
                        recd[errpos] ^= 1;
        printf("r(x) = ");
        for (i = 0; i < length; i++) {
                printf("%1d", recd);
                if (i && ((i % 50) == 0))
                        printf("\n");
        }
        printf("\n");

        decode_bch();            
        printf("Results:\n");
        printf("original data  = ");
        for (i = 0; i < k; i++) {
                printf("%1d", data);
                if (i && ((i % 50) == 0))
                        printf("\n");
        }
        printf("\nrecovered data = ");
        for (i = length - k; i < length; i++) {
                printf("%1d", recd);
                if ((i-length+k) && (((i-length+k) % 50) == 0))
                        printf("\n");
        }
        printf("\n");

       
        for (i = length - k; i < length; i++)
                if (data[i - length + k] != recd)
                        decerror++;
        if (decerror)
           printf("There were %d decoding errors in message positions\n", decerror);
        else
           printf("Succesful decoding\n");
}