ECE Dept | IISc

## E2 205 Error-Control Coding

### Aug - Dec 2023

[ Lectures | Homework | Course Outline | References | Online Resources | MS Teams Site]

Instructor
Navin Kashyap
Office: SP 2.17

Teaching Assistants

Lectures
Tuesdays & Thursdays, 11:30am to 1:00pm
Location: EC 1.08
The first meeting will be held on Thursday, August 3.

Tutorial/Discussion Sessions
Mondays 5:30pm to 7:00pm in EC 1.08

Homework Assignments
Homework assignments will be posted on the MS Teams site for the course. (If you have an IISc email id, you can join the Team using the team code 7iaw4tu.)

Exams
There will be a midterm and a final exam. The midterm exam will be held on Thursday, October 5, during class hours.

The final exam will be held on Thursday, December 7, 09:00-12:00hrs, Monday, December 4, 09:00-12:00hrs in Room EC 1.08.

The course grade will be mainly based on the homework assignments, the midterm and the final exam, with 20% weightage assigned to the homeworks, 30% to the midterm, and 50% to the final exam.

Course Outline
• Introductory Concepts: Noisy channels, block codes, encoding and decoding, maximum-likelihood decoding, minimum-distance decoding, error detection and correction. Shannon's noisy-channel coding theorem.

• Linear codes: Minimum distance, generator and parity-check matrices, dual codes, standard array decoding, syndrome decoding. Repetition codes, Hamming codes.

• Bounds on Code Parameters: Hamming bound, Singleton bound, Gilbert-Varshamov bound, Plotkin bound.

• Basic Finite Field Theory: Definitions, prime fields, construction of prime power fields via irreducible polynomials, existence of primitive elements, minimal polynomials.

• Algebraic Codes: Bose-Choudhury-Hocquenghem (BCH) codes, Reed-Solomon codes, and alternant codes as instances of generalized Reed-Solomon (GRS) codes. Decoding algorithms for GRS codes.

• Cyclic codes: Definition, characterization as ideals of polynomial rings. BCH codes viewed as cyclic codes.

• Convolutional Codes: Definitions, encoders, state and trellis diagrams, Viterbi decoder.

• The Generalized Distributive Law: As expounded in the paper
S.M. Aji and R.J. McEliece, "The generalized distributive law", IEEE Transactions on Information Theory, vol. 46, no. 2, pp. 325-343, March 2000.

• Low-Density Parity-Check (LDPC) Codes: Definitions, Tanner graph, iterative message-passing decoding algorithms. Material largely based on the paper
T. Richardson and R.L. Urbanke, "The capacity of low-density parity-check codes under message-passing decoding", IEEE Transactions on Information Theory, vol. 47, no. 2, pp. 599-618, Feb. 2001.

• Other topics to be selected from, as time permits: Polar codes and Reed-Muller codes, erasure codes for distributed storage

References

The following books are recommended as references:

• R.M. Roth, Introduction to Coding Theory, Cambridge University Press, 2006. (An excellent textbook primarily covering block codes. Access to e-book is available courtesy of the IISc library.)

• T. Richardson and R. Urbanke, Modern Coding Theory, Cambridge University Press, 2008. (Focuses on LDPC and related codes. Access to e-book is available courtesy of the IISc library.)

• R. Johanneson and K.Sh. Zigangirov, Fundamentals of Convolutional Coding, IEEE Press, 1999. (Covers exactly what the title says.)

• S. Lin and D.J. Costello, Error Control Coding (2nd edition), Prentice-Hall, 2004. (A good introduction from the engineering perspective.)

• R.E. Blahut, Algebraic Codes for Data Transmission, Cambridge University Press, 2002. (This is an updated version of the original classic, now out of print, Theory and Practice of Error-Control Codes, Addison-Wesley, 1983.)

• F.J. MacWilliams and N.J.A. Sloane, The Theory of Error-Correcting Codes, Elsevier/North-Holland, 1977. (All you wanted to know about classical coding theory but were afraid to ask. An encyclopaedic reference.)

• E.R. Berlekamp, Algebraic coding theory, McGraw-Hill, 1968. Revised edition published by Aegean Park Press in 1984.

• W.C. Huffman and V. Pless, Fundamentals of Error Correcting Codes, Cambridge University Press, 2003. (A good book from which to learn the basics. Written at an undergraduate level, assuming only knowledge of linear algebra.)

• R.J. McEliece, Theory of Information and Coding (2nd edition), Cambridge University Press, 2002. (A concise and well-written introduction to information and coding theory.)

• Vera Pless, Introduction to the Theory of Error-Correcting Codes (3rd edition), Wiley-Interscience, 1998. (A classic undergraduate text.)

• J.H. van Lint, Introduction to Coding Theory (3rd edition), Springer-Verlag (Graduate Texts in Mathematics), 1999. (Not really the most accessible introduction to the subject, but if you are comfortable with elementary abstract algebra and combinatorics, then it's a great book to read. Written for advanced undergraduates and graduate students in mathematics.)

Online Resources

The following online resources are likely to be useful:

[ Lectures | Homework | Course Outline | References | Online Resources]