Course Objectives:

This is a first-level graduate course on coding theory, which will introduce students to some of the classical methods in coding theory. While mathematical background on linear algebra and probability is assumed, coverage of necessary background on finite fields is included as part of the course. Through concrete examples of code construction, where simple, yet powerful mathematical tools are put to use, the course is expected to improve students’ insights into the mathematical foundations.

Course Contents

Binary block codes, Minimum distance, Error-detecting capability and error-correcting capability. (2 lectures)

Linear block codes: Linear block codes, Generator matrix, Parity-check matrix. Dual code, Alternate characterizations of minimum distance for linear block codes, Repetition code, Single-parity-check code, Hamming Code, Bounds on Codes – Singleton Bound, Hamming bound, Gilbert-Varshamov bound, Plotkin bound. Asymptotic version of these bounds. (8 lectures)

Decoding of linear block codes: Maximum a-posteriori probability (MAP) decoding, Maximum likelihood (ML) decoding, Standard Array Decoding (6 lectures)

Cyclic codes: Review of Finite fields, Polynomial description of cyclic codes, generator and check polynomials, Roots of cyclic codes, BCH codes, Reed-solomon codes. Berlekamp-Welch decoding algorithm. (16 lectures)

LDPC codes binary expander codes, Sipser-Spielman decoding algorithm, introduction to iterative decoding. (10 lectures)

Learning Outcomes:

Upon successful completion of this course, students are expected to:

  1. Use algebraic techniques to construct efficient codes
  2. Identify the parameters of a given code the quality of a given code.
  3. State and prove the limits on achievable code performance

Text Books:

  1. Ron M. Roth, Introduction to Coding Theory, Cambridge University Press, 2006, ISBN-13: 978-0521845045.
  2. Tom Richardson, Rudiger Urbanke, Modern Coding Theory, Cambridge University Press, 2009, ISBN-13: 978-0521165761.

References:

  1. J. H. van Lint, Introduction to Coding Theory, Springer, 1999, ISBN-13: 978-3540641339.
  2. Shu Lin, Daniel J. Costello, Error Control Coding: Fundamentals and Applications, Prentice-Hall, 1982, ISBN-13: 978-0132837965.
  3. W. Cary Huffman, Vera Pless, Fundamentals of Error-Correcting Codes, Cambridge University Press, 2010, ISBN-13: 978-0521131704.
  4. Parikshit Gopalan, Cheng Huang, Huseyin Simitci, and Sergey Yekhanin, On the locality of codeword symbols, IEEE Transactions on Information Theory, 58(11) pp 6925–6934, 2012.
  5. P.Vijaykumar, Error Correcting Codes, NPTEL Course, https://nptel.ac.in/courses/117/108/117108044/

Metadata

Proposing Faculty: Department: Computer Science and Engineering Programme: B.Tech Proposing date: Approved date: Proposal type: Offerings:

Past Offerings