Modern Coding Theory (short course in Turin, April 15-22)

Instructor Ruediger Urbanke
Place Room Buzano, Department of Mathematics, Politecnico di Torino
Contact Fabio Fagnani ([email protected])
Email [email protected]
Lectures Tue, April 15, 10:30 -12
Thu, April 17, 10:30-12
Fri, April 18, 10:30-12
Mo, April 21, 10:30 -12
Tue, April 22, 10:30-12

HOMEWORK

Abstract

In Modern Coding Theory, codes are viewed as large complex systems described by random sparse graphical models and encoding as well as decoding are accomplished by efficient local algorithms. The local interactions of the code bits are simple but the overall code is nevertheless complex (and so sufficiently powerful to allow reliable communication) because of the large number of interactions. The idea of random codes is in the spirit of Shannon’s original formulation. What is new is the sparseness of the description and the local nature of the algorithms. The main aim of the course is to introduce you to iterative coding and to show some of the basic techniques that have been shown to be useful for their design and analysis. But it is hopefully clear by the end of the lectures that iterative techniques are not limited to coding or communications but can be applied in a wide variety of settings.


Detailed (Tentatative) Schedule

Date Topic Assignment Due Date Remarks
Tue, April 15 introduction (BMS channels, the decoding problem, Tanner graphs, message-passing decoders, configuration model of codes), weight distributions and a first phase transition, concentration of weight distribution, convergence to Poisson distribution; open problems Sec. 3.24, Sec. C.5, Sec. D.4
Thu, April 17 density evolution, stability, capacity achieving degree distributions, and fundamental properties; open problems
Fri, April 18 MAP versus BP: EXIT, GEXIT, and the Maxwell construction; open problems
Mon, April 21 Scaling laws and the Wormald method; open problems
Tue, April 22 Linear program decoding, min-sum decoding, pseudo-codewords, and errorfloors; open problems

Course Notes

mct.jpg

Additional Reading Material

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.