Utah State University
ECE 7670
Error Control Coding Theory

Program # 5
BCH and Reed-Solomon Decoding
Due Friday, April 6, 2001

We are now ready to do the thing that we have been building up to all quarter: BCH and Reed-Solomon decoding. This will use what you know about polynomial arithmetic, which you will need to generalize to polynomials with coefficients from Galois fields. It will rely on your Galois field routines, as well as some new material.

1. Write a program to systematically encode a BCH code. The code we will use is the (15,5) BCH code over the field $GF(2^4)$ with zeros at $\alpha, \alpha^2, \alpha^3, \alpha^4, \alpha^5, \alpha^6$, where $\alpha$ is the primitive element: $\alpha^4 + \alpha + 1 = 0$. The minimal polynomials of $\alpha, \alpha^3$ and $\alpha^5$ are (do we need the other minimal polynomials?)
   
   $$f_1(x) = 1+x+x^4$$
   
   
   
   
   $$f_3(x) = 1+x+x^2+x^3+x^4$$
   
   
   
   
   $$f_5(x) = 1+x+x^2.$$
   
   
   The generator for the three-error correcting code is
   $$\begin{eqnarray*} g(x) &=& \mbox{LCM}[f_1(x)f_3(x)f_5(x)] \\ &=& 1+x+x^2+x^4+x^5+x^8+x^{10} \end{eqnarray*}$$
   
   
   
   
   
   Observe that since the weight of the generator is 7, the minimum distance of this code is exactly 7; the code can correct up to three errors.

   You should write a stand-alone program that takes as a command-line parameters the name of the file to encode and the name of the encoded file.

   If you understand the structure of what you did for the CRC code, you are most of the way there already.

2. Write another program which decodes the code of part 1 using the Berlekamp-Massey algorithm to decode up to three errors. Test your program in two ways:
   1. First, take a lengthy file, encode it, then decode it, and make sure that the decoded file is identical to the original file. For this test, you should create a stand-alone program which accepts two command-line arguments, the name of the encoded file and the name of the decoded file.
   2. Second, generate all possible patterns of up to three bits, and show that the decoder is able to correct them all. (This will probably need to be a separate program from the previous one.) This task will be easier if you write your decoder as a subroutine, say bchdecode(char *instream, char *outstream), which takes the input stream and returns a decoded output stream.

      Since the code is linear, go ahead and assume that the all-zero code word is sent, and simply generate the error pattern. To generate all patterns of up to three bits, you may want to use a piece of code like the following. Even though it produces some error patterns more than once, it is thorough and easy.

      
      ...
      char bit[15];
      char decodedbit[15];
      /* generate patterns of three bits */
      for(b1 = 0; b1 < 15; b1++) {            /* first error bit */
         for(b2 = 0; b2 < 15; b2++) {         /* second error bit */
            for(b3 = 0; b3 < 15; b3++) {      /* third error bit */
               for(i = 0; i < 15; i++)        /* set all prior bits to zero */
                  bit[i] = 0;
               /* now assign the error bits */
               bit[b1] = 1;
               bit[b2] = 1;
               bit[b3] = 1;
      
               bchdecode(bit,decodedbit);  /* <--- this is the subroutine you write */
      
               /* see if any errors left */
               for(i = 0; i < 15; i++) {
                  if(decodedbit[i]) {
                    printf("error on bitstream: ");
                    for(j = 0; j < 15; j++) {
                       printf("%d",decodedbit[j]);
                    }
                    printf("\n");
                    break;
                  }
               }
            }
         }
      }
      

   You should provide a list of all the patterns of three errors that your program was not able to correct. There should be none! Don't give me a list of the errors it was able to correct - it would be pages long.
3. Write a stand-alone program that systematically encodes a (255,249) Reed-Solomon decoder capable of correcting up to three errors. Use
   
   $$p(x) = 1+x+x^2+x^7+x^8.$$
   
   
   as the primitive polynomial to generate the field, and use a narrow-sense Reed-Solomon code. This program should accept command-line arguments, as in

   
   rsencode inputfile codedfile
   

4. Write a stand-alone program that decodes the Reed-Solomon code from the last step. The program should accept command-line arguments, as in

   
   rsdecode codedfile decodedfile
   

   Use the Berlekamp-Massey decoding algorithm.

   Test your decoder by generating at least 1000 random patterns of up to three nonzero digits out of the 255, with the other digits equal to zero, and verify that your decoder is able to correct them all. (This may require a separate program, or a separate mode of operation.

5. Also, test your program by passing a very large encoded file through the channel model program you developed for Program 4. Count the number of errors before decoding, and after decoding.

6. Extra credit: Provide another implementation of the Reed-Solomon decoder using Euclidean algorithm decoding.

Turn in your program listings, errors not corrected (if any!), and a discussion of items learned, issues, problems, etc.