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.
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.