===== Short Course on Modern Coding Theory ===== ^^^ |Instructor|**Ruediger Urbanke**| |Place|**Room Buzano, Department of Mathematics, Politecnico di Torino**| |Contact|**Fabio Fagnani (fabio.fagnani@polito.it)**| |Email|**ruediger.urbanke@epfl.ch**| ||| |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 ==== \\ {{en:courses:2007-2208:turin1.pdf|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 ==== \\ {{en:courses:2007-2208:mct.jpg}} \\ \\ ---- ==== Additional Reading Material ==== \\ **Books:** \\ * [[http://www.inference.phy.cam.ac.uk/mackay/itila/|Information Theory, Inference, and Learning Algorithms, D. MacKay]] * [[http://www.amazon.com/Error-Control-Coding-Second-Shu/dp/0130426725|Error Control Coding, S. Lin and D. Costello]] * [[http://www.amazon.com/Fundamentals-Convolutional-Coding-Digital-Communication/dp/0780334833|Fundamentals of Convolutional Coding, Johannesson and Zigangirov]] * [[http://www.amazon.com/Springer-International-Engineering-Computer-Science/dp/0792383788/ref=sr_1_2?ie=UTF8&s=books&qid=1200082659&sr=1-2|Turbo Coding, Heegard and Wicker]] * [[http://www.amazon.com/Trellis-Turbo-Coding-Christian-Schlegel/dp/0471227552/ref=sr_1_1?ie=UTF8&s=books&qid=1200082734&sr=1-1|Trellis and Turbo Coding, Schlegel and Perez]] * [[http://www.amazon.com/Turbo-Codes-Applications-International-Engineering/dp/0792378687/ref=sr_1_2?ie=UTF8&s=books&qid=1200082866&sr=1-2|Turbo Codes: Principles and Applications, Vucetic and Yuan]] \\ **Papers:** A short selection out of the thousands of papers written on iterative decoding. More will be added as we go on. \\ * {{en:courses:2007-2208:gallager_thesis.pdf|Gallager's remarkable thesis; a must read}} * {{en:courses:2007-2208:gallager_thesis.pdf|The paper by Berrou, Glavieux and Thitimajisham that got it all started.}} \\ Factor graphs: \\ * [[http://ieeexplore.ieee.org/iel5/79/28346/01267047.pdf|An introduction to factor graphs, Loeliger]] * [[http://ieeexplore.ieee.org/iel5/18/17872/00825794.pdf|The Generalized Distributive Law, Aji, McEliece]] * [[http://ieeexplore.ieee.org/iel3/49/14424/00661103.pdf|Turbo Decoding as an Instance of Pearl’s “Belief Propagation” Algorithm, McEliece, MacKay, Cheng]] * [[http://ieeexplore.ieee.org/iel5/18/27176/01207363.pdf|Codes on Graphs: Constraint Complexity of Cycle-Free Realizations of Linear Codes, Forney]] * [[http://ieeexplore.ieee.org/iel5/18/30754/01424306.pdf?arnumber=1424306|On factor graphs and the Fourier transform, Mao, Kschischang]] * [[http://ieeexplore.ieee.org/iel5/18/22677/01055186.pdf|Optimal decoding of linear codes for minimizing symbol error rate, Bahl, Cocke, Jelinek, Raviv,]] * [[http://ieeexplore.ieee.org/iel5/18/27176/01207363.pdf|Codes on Graphs: Constraint Complexity of Cycle-Free Realizations of Linear Codes, Forney]] * [[http://ieeexplore.ieee.org/iel5/18/22722/01056404.pdf|A recursive approach to low complexity codes, Tanner]] \\ 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. \\ * [[http://www.inference.phy.cam.ac.uk/mackay/|David MacKay]] * [[http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-451Spring-2005/LectureNotes/|Coding course at MIT by Dave Forney. ]] * [[http://www.cs.yale.edu/homes/spielman/ECC/handouts.html|Coding course at Yale by Daniel Spielman. ]] * [[http://www.stanford.edu/class/ee388/|MCT course at Stanford by Andrea Montanari.]] * [[http://algo.epfl.ch/index.php?p=courses_0506_MCT|Previous MCT course at EPFL by Amin Shokrollahi.]] * [[http://www.hpl.hp.com/personal/Pascal_Vontobel/pseudocodewords/presentations/|Pascal Vontobel's pseudo codeword page.]] * [[http://www.cs.toronto.edu/~radford/ftp/LDPC-2006-02-08/index.html| Software for Low Density Parity Check Codes.]] * [[http://www.mathworks.com/access/helpdesk/help/toolbox/commblks/index.html?/access/helpdesk/help/toolbox/commblks/ref/ldpcdecoder.html&http://www.mathworks.com/cgi-bin/texis/webinator/search/?db=MSS&prox=page&rorder=750&rprox=750&rdfreq=500&rwfreq=500&rlead=250&sufs=0&order=r&is_summary_on=1&ResultCount=10&query=ldpc&submitButtonName=Search| LDPC in MATLAB.]] * [[http://www.iterativesolutions.com/index.html| Coded Modulation Library.]] * [[http://www.turbobest.com/| Turbobest]]