Instructor | Ruediger Urbanke |
Place | Room Buzano, Department of Mathematics, Politecnico di Torino |
Contact | Fabio Fagnani ([email protected]) |
[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
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:
Under construction – more to follow.
—-
Links
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.