Introduction to Coding Theory (236309)

2010/2011 Winter Semester

When:	Wednesday 14:30-16:30 (lecture) 16:30-17:30 (recitation class)
Where:	Taub 6
Instructor:	Ronny Roth, Taub 637, ronny@cs.technion.ac.il
Teaching assistant:	Artyom Sharov, Taub 638, sharov@cs.technion.ac.il

The course provides the basics of the theory of error-correcting codes. The topics to be covered include the following:

Knowledge of basic terms in linear and modern algebra is assumed. Examples of such terms include: vector spaces, groups, rings, and ideals.

Introduction
- The q-ary symmetric channel
- Maximum-likelihood decoding
- Error correction, error detection, and erasure correction
Linear codes
- Representation through generator and parity-check matrices
- Syndrome decoding
- Hamming codes
Introduction to finite fields and double-error-correcting codes
- Irreducible polynomials
- Primitivity
- Double-error-correcting codes
Bounds on the parameters of codes
- The Singleton bound; MDS codes
- The Hamming sphere-packing bound; perfect codes
- The Gilbert-Varshamov bound
Reed-Solomon and related codes
- Generalized Reed-Solomon (GRS) codes
- BCH codes and alternant codes as subfield subcodes of GRS codes
- Concatenated codes
- Decoding GRS codes using Euclid's algorithm
Structure of finite fields and cyclic codes
- Minimal polynomials
- Cyclic codes
- BCH codes as cyclic codes
- The BCH bound

R.M. Roth, Introduction to Coding Theory, Cambridge University Press, Cambridge, UK, 2006.

E.R. Berlekamp, Algebraic Coding Theory, Second Edition, Aegean Park Press, Laguna Hills, California, 1984.
R.E. Blahut, Theory and Practice of Error-Control Codes, Addison-Wesley, Reading, Massachusetts, 1983.
F.J. MacWilliams, N.J.A. Sloane, The Theory of Error-Correcting Codes, North-Holland, Amsterdam, 1977.
R.J. McEliece, The Theory of Information and Coding, Second Edition, Cambridge University Press, Cambridge, 2002.
S. Lin, D.J. Costello, Jr., Error Control Coding: Fundamentals and Applications, Second Edition, Prentice-Hall, Upper Saddle River, New Jersey, 2004.

The course material is available only to students who are enrolled to the course. To obtain the material, please send an email to Artyom (sharov@cs.technion.ac.il) with the subject "textbook", and include in that email your name and ID number. Enrolled students will be mailed back a pdf copy of the relevant chapters of the textbook.

Topics covered in the course are as follows:

Introduction (20 Oct through 03 Nov 10)
Linear codes (03 through 17 Nov 10)
Introduction to finite fields (17 Nov through 01 Dec 10)
Bounds on the parameters of codes (01 Dec 10)
GRS and related codes (08 and 15 Dec 10)
Decoding of GRS codes (22 Dec 10)
Structure of finite fields (29 Dec 10 and 05 Jan 11)
Cyclic codes (05 through 19 Jan 11)

Homework assignment 1: Problems 1.12, 1.13, 3.3, 3.13, A.1 (parts 1-3), A.2 (part 1, only the unproved direction). Due date: 17 Nov 2010.
Homework assignment 2: Problems: 2.8, 2.11, 2.14, 3.4, 3.5. Due date: 01 Dec 2010.
Homework assignment 3: 2.4, 2.6, 2.7, 2.17, 2.18. Due date: 15 Dec 2010.
Homework assignment on finite fields (not for submission): Problems: 3.18, 3.21, 3.22.
Homework assignment 4: 3.16, 4.2, 4.12, 4.13, 4.14. Due date: 05 Jan 2011.
Homework assignment 5: 5.2, 6.3, 6.11, 7.5, 8.7. Due date: 19 Jan 2011.

There will be five home assignments which will constitute 20% of the final grade. The remaining 80% will be determined by a final exam. The dates of the final exam are 30 Jan 2011 and 30 Mar 2011.