Introduction to Coding Theory (89-662)

Yehuda Lindell

The aim of this course

Coding theory deals with the problem of communication over a noisy channel, where some of the bits of the message may be corrupted en route. Beyond its immediate application to “correct communication”, coding theory has become an important tool in the theory of computer science, and in particular in computational complexity. In this course, we will study the basics of coding theory. We will study both lower and upper bounds, and will also see well-known families of codes. Our view is that of computer science and we will therefore be interested in the efficiency of encoding and decoding procedures. The course is intended for 3rd year undergraduate students, as well as for graduate students.

There is no single textbook for this course, although we have used the books Coding Theory – A First Course, by San Ling and Chaoping Xing (Cambridge University Press, 2004), and an Introduction to Coding Theory (Cambridge University Press 2006) by Ron Roth. We note that although most of the technical material can be found in these texts, our presentation will often be quite different. Full lecture notes have been written and it is recommended to refer to these.

The requirements of the course are homework exercises, a final exam, and possibly a midterm exam as well. This year we will be experimenting with cooperative group learning. As such attendance is compulsory and participating may also be taken into account for the final grade. We will discuss this more in the first class.

Lecture Notes

Full lecture notes for the course can be found in this PDF file.
Please send me any comments that you have, or let me know if you find errors.

Course Syllabus

Introduction: the coding problem and definitions.
Linear Codes: definition, hamming weight, bases, generator and parity-check matrices, encoding and decoding procedures.
Bounds:
- The main coding theory problem
- The sphere covering bound and the sphere packing (Hamming) bound
- Perfect codes: Hamming and Golay
- The Singleton bound and MDS codes; the Reed-Solomon code
- Other bounds: Gilbert-Varshamov and Plotkin; Hadamard codes
- Asymptotic bounds
- Shannon’s theorem and its converse
Constructions of some specific codes:
- Propagation rules
- Reed-Muller codes
- Generalized Reed-Solomon (GRS) codes and decoding algorithms
Asymptotically good codes: definition; concatenation of codes; construction via Reed-Solomon and Gilbert-Varshamov; efficient decoding of concatenated codes (Forney’s algorithm)
Local decodability: definition; properties; local decodability of Hadamard codes
List decoding: definition; Sudan’s algorithm for list-decoding of GRS codes
Hard problems in coding theory: the nearest codeword problem; NP-completeness; hardness of approximation
CIRC: coding and decoding for the CD-ROM

Past Exams

Moed aleph, 2007/8
Moed bet, 2007/8
Moed aleph, 2008/9

Reading Material

Main course texts:

S. Ling and C. Xing. Coding Theory – A First Course. Cambridge University Press, 2004.
R. Roth. Introduction to Coding Theory. Cambridge University Press, 2006.

Other relevant texts:

W.C. Huffman and V. Pless. Fundamentals of Error-Correcting Codes. Cambridge University Press, 2003.
M. Sudan. Algorithmic Introduction to Coding Theory – Lecture Notes.
S. Roman. Introduction to Coding and Information Theory. Springer-Verlag, 1997.

Yehuda Lindell