Coding Theory

To be able to use structured redundancy to protect digital data efficiently against noise. These techniques are commonly applied whenever information is digitally stored and transmitted. Two approaches will be taught: block codes (algebraic of nature; no memory of the past) and convolutional codes (that take the encoding of previous information into account).

Block coding theory

• Shannon's communication model, the capacity of the BSC channel.
• Linear codes, characteristic parameters (like the dimension, the minimum distance and the covering radius), a generator matrix, a parity-check matrix, coset leaders and syndrome decoding. 
• Some bounds, e.g. those of Hamming, Gilbert-Varshamov, Griesmer
• The weight enumerator and the MacWilliams relations.
• Hamming codes with their weight enumerator, Reed-Muller codes and their decoding.
• Cyclic codes with the standard notions, like the generator polynomial and the parity check polynomial. Construction and description by means of finite fields and extension fields. 
• BCH codes, Reed Solomon codes and the two Golay codes.
• Decoding cyclic codes.

Convolutional coding theory

• Description of convolutional codes via polynomial matrices; basic notions    (generator and parity check matrices, degree, Forney indices, dual code).
• Bounds for the distance (Griesmer and MDS bound) and a construction of MDS convolutional codes via Reed Solomon block codes.
• State space description, computing the distance, weight enumerator.
• Decoding (Viterbi algorithm).
• LDPC codes and Tanner graphs.

• Henk van Tilborg, Error-Correcting Codes - A First Course, Studentlitteratur, Lund, Sweden, 1993 (Out of print, copy obtainable from lecturer)
• R.J. McEliece: The Algebraic Theory of Convolutional Codes,  in: V. Pless, W. Huffman (eds.), Handbook of Coding Theory, vol. 1, Elsevier, 1998,  1065-1138
  (copy can be obtained from the lecturer)
• Other articles or hand-outs over convolutional codes will be announced throughout the course.