Math 422: Coding Theory

Final Exam

The final exam will take place on Wednesday, April 23, 9:00 AM in the regular classroom. It will take 2 hours.

Notice this is a closed book exam. No sheets, no calculators, no books are allowed.

The material covered will be the entire class.

In particular you should be familiar with the definitions and theorems (and their meaning). More precisely, the following is a list of topics you should be very fluent in:

• definition of codes
• computations in finite fields (mainly mod p)
• minimum distance, nearest neighbour decoding, error detection and correction
• word error probability
• definition of A_q(n,d), some obvious values for A_q(n,d) (e.g. A_q(n,n) = q; also A₂(n,d) = A₂(n+1,d+1) if d is odd)
• Hamming distance, spheres in F_qⁿ, Hamming bound, perfect codes
• balanced block designs (and how to construct a code from one)
• linear codes
• minimum weight
• encoding with linear codes, standard array decoding, syndrome decoding
• generator and parity check matrices (def. and how to find them)
• dual code
• Hamming codes
• Golay codes, and the methods we used for computing their minimum distance (e.g. what it means if a code is self-dual).
• Cyclic codes; definition; generator and check polynomials; generator matrix, PCM;
• Field Theory; irreducible polynomials; minimal polynomial; order of a field; order of an element; Lagrange's Theorem for fields (the order of a nonzero element in F_q divides q-1); computation in finite fields; primitive elements; construction of finite fields as quotient rings of polynomial rings; the equation x^q - x.
• BCH Codes; Reed-Solomon Codes; decoding a BCH code

There will be simple proof questions on the exam.

The above list is not exhaustive.

You are not, for example, expected to know the Plotkin bound by heart. It is also not required to know all the proofs of theorems by heart (it is much more useful to understand them). Also, the part of the last lecture regarding public key encryption is not part of the final exam.

Here is another example of decoding a BCH code. This time, using a Reed-Solomon example. Also have a look at the file distributed in class.

Last year's final is here and solutions here.

Here are some sample problems with solutions (Hint: try not to look at the solutions before you haven't tried to solve the problems). I tried to omit typos as much as possible, but they may still be in there.
Unfortunately, I don't have the source code for these problems anymore so I cannot adapt them to this year. NB: The sample problems are only a rough approximation, both in length and in difficulty! It is not meant to be a sample final!
You may find entire sample exams on Dr. Bowman's home page. Some of the problems there are from courses with a different schedule, though, so you may not be able to solve all problems. For most problems there is a solution in Dr. Bowman's Lecture Notes.

It is a good idea to look at the old homework problems (including solutions) and solve sample problems, both from the sample exams and the book (or Dr. Bowman's Lecture Notes). Notice that the section on BCH codes in the book is not very helpful.

Note that the solution of Probkem 1c) in Assignment 8 was wrong. It is corrected by now (April 16).

Finally, once again, if you have any questions, then please ask! You may drop by anytime, but if you want to make sure I'm available, then please write an e-mail in advance.