Modern Coding Theory

Instructor Ruediger Urbanke
Office INR 116
Phone +4121 6937692
Email ruediger.urbanke@epfl.ch
Office Hours By appointment
Teaching Assistant Amin (Troublemaker) Karbasi
Phone +4121 6936604
Office INR 039
Email amin.karbasi@epfl.ch
Office Hours 24/7
Lectures Wednesday 13:15 – 15:00
Exercises Wednesday 15:15 – 17:00
Room INR 113

—-

Special Announcements

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.


Objectives

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

Detailed Schedule

 

Date Topic Assignment Due Date Remarks
Feb 20 Why you are all already world experts on iterative coding. (inspired by A. Montanari) read Introduction; problems 1.1, 1.2, 1.6, 1.8 Mar 5  
Feb 27 Factor Graphs HW2 Mar 12 Chapter 2
Mar 5 sum-product versus min-sum, LDPC ensemble; how many small cycles are there in an average graph HW3 Mar 19  
Mar 12 how to prove convergence to Poisson distribution; weight distribution; Hayman approximation no homework :-) Mar 26  
Mar 19 belief propagation for the BEC; all-one codeword assumption; computation graph; HW4 Apr 9 Chapter 3
Apr 2 BEC: density evolution; irregular ensembles; tresholds; stability; capacity achieving ensembles problems 3.2, 3.3, 3.4, 3.6, 3.20 Apr 16 Chapter 3
Apr 9 BMS channels; message-passing decoders; all-one codeword assumption; density evolution for Gallager A, threshold; density evolution for BP HW6 Apr 23 Chapter 4
Apr 16 expander codes and the flipping algorithm HW7 Apr 30 Chapter 8
Apr 23 density evolution for BP; threshold; stability; optimization of degree distributions no homework :-)
April 30 duality rule, extremes of information combining, symmetry of distributions for BMS channels, basic properties of density evolution no homework :-)
April 30 LP decoding and pseudocodewords no homework :-)  
May 14 Wormald method and scaling laws HW8 May 28 Chapter 3 and Appendix C
May 21 MAP versus BP; Azuma inequality and some applications 3.21, 3.31, C.5 June 4th Section 3.20, Appendix C
May 28 rateless codes      
June 2 Take Home Exam June 9th at noon    

Course Notes

 

Figures

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

mctfig.pdf

Exams

TBD

Additional Reading Material

Books:

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

Factor graphs:

Binary Erasure Channel:

Weight Distribution:

 

Binary Memoryless Symmetric Channel:

Efficient Encoding:

Expander Codes:

Wormald Method:

Linear Program Decoder:

Other Classes of Codes:

EXIT and GEXIT Charts:


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.