===== Modern Coding Theory (IC-068/4 ETCS) ===== |Instructor|**Ruediger Urbanke**| |Office|[[http://plan.epfl.ch/?room=INR116|INR 116]]| |Phone|**+4121 6937692**| |Email|**ruediger.urbanke@epfl.ch**| |Office Hours|**By appointment**| |Teaching Assistant|**Amin (Troublemaker) Karbasi**| |Phone|**+4121 6936604**| |Office|[[http://plan.epfl.ch/?room=INR039|INR 039]]| |Email|**amin.karbasi@epfl.ch**| |Office Hours|**24/7**| ||| |Lectures|**Wednesday 13:15 - 15:00**| |Exercises|**Wednesday 15:15 - 17:00**| |Room|**[[http://plan.epfl.ch/?room=INR113|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 [[http://algo.epfl.ch/index.php?p=courses_0708_ct|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. \\ \\ {{en:courses:2007-2208:handout4.pdf|}} ==== Detailed Schedule ==== \\ ^ Date ^ Topic ^ Assignment ^Due Date^ Remarks ^ | Feb 20| Why you are all already world experts on iterative coding. (inspired by [[http://www.stanford.edu/class/ee388/handouts/lecture-1.pdf|A. Montanari]]) | read Introduction; problems 1.1, 1.2, 1.6, 1.8 | Mar 5 | | Feb 27| Factor Graphs| {{en:courses:2007-2208:handout1.pdf|HW2}}| Mar 12 | Chapter 2| | Mar 5| sum-product versus min-sum, LDPC ensemble; how many small cycles are there in an average graph| {{en:courses:2007-2208:handout2.pdf|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; | {{en:courses:2007-2208:handout3.pdf|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 | {{en:courses:2007-2208:handout4.pdf|HW6}}| Apr 23 | Chapter 4 | | Apr 16| expander codes and the flipping algorithm | {{en:courses:2007-2208:handout5.pdf|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 | {{en:courses:2007-2208:handout6.pdf|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| {{en:courses:2007-2208:handout7.pdf|Take Home Exam}} | June 9th at noon| | ==== Course Notes ==== \\ {{en:courses:2007-2208:mct.jpg|}} \\ \\ ==== Figures ==== [If you are a teacher and would like to receive the solutions manual, just mail me.] \\ {{en:courses:2007-2208:mctfig.pdf|mctfig.pdf}} \\ \\ ==== Exams ==== \\ TBD \\ \\ ==== 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]] * [[http://www.amazon.com/Funny-Farsi-Growing-Iranian-America/dp/1400060400|Funny in Farsi: A Memoir of Growing Up Iranian in America, Dumas (when you get sick of coding)]] \\ **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]] \\ Binary Erasure Channel: \\ * [[http://www.icsi.berkeley.edu/~luby/PAPERS/anaerr.ps| Analysis of Low Density Codes and Improved Designs Using Irregular Graphs , M. Luby, M.Mitzenmacher, A. Shokrollahi, and D. A. Spielman]]\\ * [[http://ieeexplore.ieee.org/iel5/18/19638/00910575.pdf| Efficient erasure correcting codes, M. Luby, M.Mitzenmacher, A. Shokrollahi, and D. A. Spielman]]\\ * [[http://ieeexplore.ieee.org/iel5/18/19638/00910576.pdf| Improved low-density parity-check codes using irregular graphs, M. Luby, M.Mitzenmacher, A. Shokrollahi, and D. A. Spielman]]\\ * [[http://www.icsi.berkeley.edu/~luby/PAPERS/losscode.ps| Practical Loss-Resilient Codes , M. Luby, M. Mitzenmacher, A. Shokrollahi, D. A. Spielman]]\\ \\ Weight Distribution: \\ * [[http://ieeexplore.ieee.org/iel5/18/28939/01302293.pdf| Asymptotic enumeration methods for analyzing LDPC codes , D. Burshtein and G. Miller]]\\ * [[http://ieeexplore.ieee.org/iel5/18/36107/01715529.pdf| Weight Distribution of Low-Density Parity-Check Codes ,T.Richardson, and R.Urbanke]] \\ Binary Memoryless Symmetric Channel: \\ * [[http://www.icsi.berkeley.edu/~luby/PAPERS/anaerr.ps|Analysis of low density codes and improved designs using irregular graphs, Luby, Mitzenmacher, Shokrollahi, Spielman]] * [[http://ieeexplore.ieee.org/iel5/18/19638/00910578.pdf|Design of Capacity-Approaching Irregular Low-Density Parity-Check Codes,T Richardson, A. Shokrollahi, R. Urbanke ]] * [[http://ieeexplore.ieee.org/iel5/18/19638/00910577.pdf|The Capacity of Low-Density Parity-Check Codes Under Message-Passing Decoding, T. Richardson, R. Urbanke ]] \\ Efficient Encoding: \\ * [[http://ieeexplore.ieee.org/iel5/18/19638/00910579.pdf|Efficient encoding of low-density parity-check codes, Richardson and Urbanke]] \\ Expander Codes: \\ * [[http://ieeexplore.ieee.org/iel5/18/4439828/04439836.pdf|On the Error Correction of Regular LDPC Codes Using the Flipping Algorithm, David Burshtein]] * [[http://www-math.mit.edu/~spielman/PAPERS/expandersIT.pdf| Expander Codes, M. Sipser and D. A. Spielman]] \\ Wormald Method: \\ * [[http://www.math.uwaterloo.ca/~nwormald/papers/de.pdf| The differential equation method for random graph processes and greedy algorithms, N. C.Wormald]]\\ * [[http://www.icsi.berkeley.edu/~luby/PAPERS/losscode.ps| Practical Loss-Resilient Codes , M. Luby, M. Mitzenmacher, A. Shokrollahi, D. A. Spielman]] \\ Linear Program Decoder: \\ * [[http://www.eecs.berkeley.edu/~wainwrig/Papers/FelWaiKar05.pdf| Using Linear Programming to Decode Binary Linear Codes, J. Feldman, M. J. Wainwright]]\\ \\ Other Classes of Codes: \\ * [[http://ieeexplore.ieee.org/iel2/3171/8993/00397441.pdf| Near Shannon Limit Error - Correcting Coding and Decoding : Turbo-Codes ,C. Berrou, A. Glavieux and P. Thitimajshima]]\\ * [[http://ieeexplore.ieee.org/iel5/18/34354/01638543.pdf| Raptor Codes, A. Shokrollahi]]\\ *[[http://www.mceliece.caltech.edu/publications/Brest00.pdf| Irregular Repeat–Accumulate Codes, R. McEliece]]\\ * [[http://ieeexplore.ieee.org/iel5/10511/33287/01577834.pdf| Protograph Based LDPC Codes with Minimum Distance Linearly Growing with Block Size, D. Divsalar, C. R. Jones, S. Dolinar, and J. Thorpe]]\\ * [[http://ieeexplore.ieee.org/iel5/18/20731/00959255.pdf| Low-Density Parity-Check Codes Based on Finite Geometries: A Rediscovery and New Results, Y. Kou, S. Lin, and M. P. C. Fossorie]]\\ \\ EXIT and GEXIT Charts: \\ * [[http://ieeexplore.ieee.org/iel5/2220/16738/00771431.pdf?tp=&isnumber=&arnumber=771431|Convergence of iterative decoding, ten Brink]] * [[http://ieeexplore.ieee.org/iel5/7942/21920/01023387.pdf|Code rate and the area under extrinsic information transfer curves, Ashikhmin, Kramer, ten Brink]] * [[http://www.stanford.edu/~montanar/PAPERS/FILEPAP/gatpap.pdf|The Generalized Area Theorem and Some of its Consequences, C. Measson, A. Montanari, T. Richardson, R. Urbanke]] * [[http://www.stanford.edu/~montanar/PAPERS/FILEPAP/maxwellpap.pdf| Maxwell Construction: The Hidden Bridge between Iterative and Maximum a Posteriori Decoding,C. Measson, A. Montanari, R. Urbanke]] ---- ==== 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]]