Modern Coding Theory

—-

This course is a one semester doctoral school course given once every two years. We are concerned exclusively with iterative coding systems. If you are interested in classical algebraic coding we highly recommend the course by Prof. Amin Shokrollahi.

---

Iterative methods have fundamentally changed coding, and more generally, communications in the last 10 years. We are interested in the basic principles underlying iterative coding. We will learn what makes a system perform well and how to determine its fundamental limitations? Contrary to classical coding, which is based mainly on abstract algebra, the analysis of iterative coding systems is heavily based on methods from graph theory, the probabilistic method, and ideas from statistical physics. An important objective of this course is to convey some of these fundamental tools.

handout4.pdf

[If you are a teacher and would like to receive the solutions manual, just mail me.]

mctfig.pdf

TBD

Books:

• Information Theory, Inference, and Learning Algorithms, D. MacKay
• Error Control Coding, S. Lin and D. Costello
• Fundamentals of Convolutional Coding, Johannesson and Zigangirov
• Turbo Coding, Heegard and Wicker
• Trellis and Turbo Coding, Schlegel and Perez
• Turbo Codes: Principles and Applications, Vucetic and Yuan
• Funny in Farsi: A Memoir of Growing Up Iranian in America, Dumas (when you get sick of coding)

Papers: A short selection out of the thousands of papers written on iterative decoding. More will be added as we go on.

• Gallager’s remarkable thesis; a must read
• The paper by Berrou, Glavieux and Thitimajisham that got it all started.

Factor graphs:

• An introduction to factor graphs, Loeliger
• The Generalized Distributive Law, Aji, McEliece
• Turbo Decoding as an Instance of Pearl’s “Belief Propagation” Algorithm, McEliece, MacKay, Cheng
• Codes on Graphs: Constraint Complexity of Cycle-Free Realizations of Linear Codes, Forney
• On factor graphs and the Fourier transform, Mao, Kschischang
• Optimal decoding of linear codes for minimizing symbol error rate, Bahl, Cocke, Jelinek, Raviv,
• Codes on Graphs: Constraint Complexity of Cycle-Free Realizations of Linear Codes, Forney
• A recursive approach to low complexity codes, Tanner

Binary Erasure Channel:

• Analysis of Low Density Codes and Improved Designs Using Irregular Graphs , M. Luby, M.Mitzenmacher, A. Shokrollahi, and D. A. Spielman
• Efficient erasure correcting codes, M. Luby, M.Mitzenmacher, A. Shokrollahi, and D. A. Spielman
• Improved low-density parity-check codes using irregular graphs, M. Luby, M.Mitzenmacher, A. Shokrollahi, and D. A. Spielman
• Practical Loss-Resilient Codes , M. Luby, M. Mitzenmacher, A. Shokrollahi, D. A. Spielman

Weight Distribution:

• Asymptotic enumeration methods for analyzing LDPC codes , D. Burshtein and G. Miller

• Weight Distribution of Low-Density Parity-Check Codes ,T.Richardson, and R.Urbanke

Binary Memoryless Symmetric Channel:

• Analysis of low density codes and improved designs using irregular graphs, Luby, Mitzenmacher, Shokrollahi, Spielman
• Design of Capacity-Approaching Irregular Low-Density Parity-Check Codes,T Richardson, A. Shokrollahi, R. Urbanke
• The Capacity of Low-Density Parity-Check Codes Under Message-Passing Decoding, T. Richardson, R. Urbanke

Efficient Encoding:

• Efficient encoding of low-density parity-check codes, Richardson and Urbanke

Expander Codes:

• On the Error Correction of Regular LDPC Codes Using the Flipping Algorithm, David Burshtein
• Expander Codes, M. Sipser and D. A. Spielman

Wormald Method:

• The differential equation method for random graph processes and greedy algorithms, N. C.Wormald
• Practical Loss-Resilient Codes , M. Luby, M. Mitzenmacher, A. Shokrollahi, D. A. Spielman

Linear Program Decoder:

• Using Linear Programming to Decode Binary Linear Codes, J. Feldman, M. J. Wainwright

Other Classes of Codes:

• Near Shannon Limit Error – Correcting Coding and Decoding : Turbo-Codes ,C. Berrou, A. Glavieux and P. Thitimajshima
• Raptor Codes, A. Shokrollahi
• Irregular Repeat–Accumulate Codes, R. McEliece
• Protograph Based LDPC Codes with Minimum Distance Linearly Growing with Block Size, D. Divsalar, C. R. Jones, S. Dolinar, and J. Thorpe
• Low-Density Parity-Check Codes Based on Finite Geometries: A Rediscovery and New Results, Y. Kou, S. Lin, and M. P. C. Fossorie

EXIT and GEXIT Charts:

• Convergence of iterative decoding, ten Brink
• Code rate and the area under extrinsic information transfer curves, Ashikhmin, Kramer, ten Brink
• The Generalized Area Theorem and Some of its Consequences, C. Measson, A. Montanari, T. Richardson, R. Urbanke
• Maxwell Construction: The Hidden Bridge between Iterative and Maximum a Posteriori Decoding,C. Measson, A. Montanari, R. Urbanke

---

The following is a set of links that contain some useful information on iterative coding. Some are links to courses on iterative coding given at other universities, some concern, products, and some point you to interesting demos.

• David MacKay
• Coding course at MIT by Dave Forney.
• Coding course at Yale by Daniel Spielman.
• MCT course at Stanford by Andrea Montanari.
• Previous MCT course at EPFL by Amin Shokrollahi.
• Pascal Vontobel’s pseudo codeword page.

• Software for Low Density Parity Check Codes.
• LDPC in MATLAB.
• Coded Modulation Library.
• Turbobest