Error Correcting Codes (EE5350) : Aug-Dec 2024.

Instructor

• Myna Vajha

Timings and Venue

• Slot F: Tue: 11am-12pm, Wed: 2.30-4pm, Fri: 10-11am

• A221

Office Hours

• Fri: 12-1pm

Teaching Assistants (TBD)

Outline (Tentative)

• Basics of binary codes: block length, Hamming weight, minimum distance, rate

• Mathematical Preliminaries: Group, Ring, Field, Vector Spaces

• Linear block codes: generator and parity check matrices

• Bounds on code sizes: Hamming, Gilbert-Varshamov, Singleton bounds

• MDS codes: Reed Solomon Codes, Systematic Encoding of RS codes

• Applications to Learning: Straggler Mitigation

  • Distributed Gradient Computation

  • Distributed Matrix Multiplication ( Polynomial Codes)

  • Distributed Polynomial Computation

• Decoding Linear Block Codes

  • Standard Array, ML, MAP decoder

• Channel coding theorem (time permitting)

• Generalized Distributive Law

  • LDPC codes

  • Belief Propagation/ Message Passing decoder

• Convolutional Codes, Viterbi Decoder

• Finite Fields, Cyclic Codes (BCH codes)

• Polar and Reed Muller Codes (time permitting)

References

• Error Control Codes (NPTEL course) by Prof. P. Vijay Kumar.

• Cary Huffmann and Vera Pless: Fundamentals of Error-Correcting Codes, Cambridge University Press, 2003

• Tom Richardson and Ruediger Urbanke: Modern Coding Theory Cambridge University Press, 2008.

• Will add links to any additional references as course progresses