Coding Theory Comprehensive Exam

This comprehensive examination is based on the four courses:

• Math 620 (Error-Correcting Coding),
• Math 621 (Mathematical Theory of Error-Correcting Codes),
• Math 622 (Mathematical Information Theory), and
• Math 623 (Mathematical Theory of Convolutional Codes).

A student is expected to master the material of three of these four courses. The examination will consist of four corresponding parts, from which the student chooses three. (If all students agree in advance on the parts to use, then the examination will consist of those three parts.)

From Math 620:

• Finite Fields and their Vector Spaces, linear block codes.
• Cyclic codes, The Golay code as a cyclic code,
• Galois fields, primitive elements and Hamming codes,
• the discrete Fourier transform,
• Reed Solomon codes, BCH codes,
• Algorithms based on the Fourier Transform,
• Product Codes and Interleaved Codes,
• Codes and Algorithms for Majority Decoding, Reed Muller Codes, algebraic geometry codes.

Bibliography:

1. Algebraic Codes for Data Transmission by Richard Blahut, Cambridge University Press.
2. Fundamentals of Error-Correcting Codes by Huffman and Pless, Cambridge University Press.

From Math 621:

• Sphere packing bound, covering radius, perfect codes,
• Plotkin bound, Johnson bounds, singleton bound, MDS codes,
• Elias bound, linear Programming bound,
• Griesmer bound, Gilbert bound,
• Varshamov bound, asymptotic bounds,
• MacWilliams Equivalence Theorems, MacWilliams identities.

Bibliography:

1. Algebraic Codes for Data Transmission by Richard Blahut, Cambridge University Press.
2. Fundamentals of Error-Correcting Codes by Huffman and Pless, Cambridge University Press.

From Math 622:

• Axiomatic description of entropy as a measure of information,
• Kraft and McMillan inequalities,
• Computational considerations and relation of entropy to other parameters,
• Huffman Encoding,
  
• Conditional entropy,
  
• Mutual Information and Capacity of Channels,
• Shannon’s fundamental theorems.
  

1. Coding and Information Theory (Graduate Texts in Mathematics) by Steven Roman, Springer-Verlag (1992)
2. The Theory of Information and Coding, Student Edition, by Robert MacEliece, Cambridge University Press, 2004
3. Elements of Information Theory by Cover and Thomas, 2^nd. Edition, Wiley, 2006.

From Math 623:

• Integral domains, fields of quotients,
• Rings of polynomials, Field of rational functions, Field of Laurent Series,
• Vector spaces over the Field of Laurent Series,
• Polynomial generator matrices for convolutional codes: predictable degree property, catastrophicity,
• Basic and reduced matrices: existence results,
• Smith normal forms, modules over Principal ideal domains,
• Free distance bounds,
• Dual Convolutional Codes,
• Cyclic Convolutional Codes.

Bibliography:

1. The Algebraic Theory of Convolutional Codes by Robert McEliece, Chapter 12 of the Handbook of Coding Theory (Pless and Huffman, Eds.), Elsevier Science.
2. Convolutional Codes, An Algebraic Approach by Phillipe Piret, MIT Press, 1988.