E2 205 Aug.
3:0
Error-Control Codes
Instructor
Navin Kashyap
Email: nkashyap@iisc.ac.in
Teaching Assistant
Email:
Department: Electrical Communication Engineering
Course Time:
Lecture venue:
Detailed Course Page: http://ece.iisc.ernet.in/~nkashyap/E2_205/
Announcements
Brief description of the course
This is a first course in the theory of error-control coding, aimed at first-year graduate students (Master's and
PhD). It is a soft-core course for the M.Tech. (Communications and Networks) stream.
Error-control codes form an integral part of all digital communications systems, and every communications
engineer should have a good working knowledge of the theory underlying these codes. This course aims to
provide this knowledge.
Prerequisites
A prior course in linear algebra.
Syllabus
1. 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.
Page 1/4
2. Linear codes: Minimum distance, generator and parity-check matrices, dual codes, standard array
decoding, syndrome decoding. Repetition codes, Hamming codes.
3. Bounds on Code Parameters: Hamming bound, Singleton bound, Gilbert-Varshamov bound, Plotkin
bound. Using bounds to determine and design good codes for a given set of parameters.
4. Basic Finite Field Theory: Definitions, prime fields, construction of prime power fields via irreducible
polynomials, existence of primitive elements, minimal polynomials.
5. 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.
Applications of Reed-Solomon codes in digital communications and storage.
6. Cyclic codes: Definition, characterization as ideals of polynomial rings. BCH codes viewed as cyclic
codes.
7. Convolutional Codes: Definitions, encoders, state and trellis diagrams, Viterbi decoder, catastrophic error
propagation
8. 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.
9. 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.
Course outcomes
At the end of the course, a student is expected to have a good understanding of the principles underlying the
design and implementation of error-correcting codes. The course places an emphasis on code design and
Page 2/4
implementation, and on decoding algorithms in particular. Specifically, the students are exposed to a variety of
code constructions, both classical (algebraic) and modern (graphical). They are also introduced to a wide range
of decoding algorithms, from basic linear-algebraic decoders to sophisticated algebraic decoders to modern
iterative message-passing decoders.
Grading policy
10% for quizzes based on homework assignments;
40% for midterm;
50% for final exam.
Assignments
Homework assignments are given roughly every week. While students are expected to solve all homework
problems, the solutions are not graded. Discussion sessions are held for the purpose of helping students solve
homework problems.
Resources
There is no required textbook for the course. 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.)
T. Richardson and R. Urbanke, Modern Coding Theory, Cambridge University Press, 2008. (Focuses on
LDPC and related codes.)
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.)
Page 3/4
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.
Page 4/4
