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.

**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**:**CIRC:**coding and decoding for the CD-ROM

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

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

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