# Modern Coding Theory

 Instructor Ruediger Urbanke Office INR 116 Phone +4121 6937692 Email [email protected] Office Hours By appointment Teaching Assistant Amin (Troublemaker) Karbasi Phone Office Email 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

### Figures

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

mctfig.pdf

TBD