Advanced Topics in Communications and Information Theory 1:

Codes on Graphs and Iterative Decoding Algorithms (048703).

The purpose of this course

The channel coding theorem of Shannon assures the existence of codes which in principle can be decoded reliably at all rates below the channel capacity, and on the other hand, it states that reliable communication is not possible at rates above the channel capacity. For more than 50 years, a central challenge of coding theory has been to devise coding schemes which come close to achieving the channel capacity with practical decoding complexity and tolerable delay. Following the breakthrough introduction of turbo codes and the rediscovery of low-density parity-check codes, it was realized that these codes and lots of other variants of capacity-approaching error correcting codes can all be understood as codes defined on graphs. Graphs not only describe the codes, but more importantly, they structure the operation of efficient iterative decoding algorithms which are used to decode these codes, having the potential to approach channel capacity while maintaining reasonable decoding complexity. These exciting developments in coding theory during the last decade did not only revolutionize the field of channel coding, but had also a great impact in other areas, such as channel equalization, lossless and lossy data compression, interference cancellation, multi-user detection etc., where the ``turbo-principle'' can be applied efficiently. In this course, we focus on codes defined on graphs, derive practical and efficient iterative decoding algorithms, and provide analytic tools to analyze their performance and complexity.

Announcements

The course 'Information Theory' (048733) is a pre-requisite for this course.
The homework assignments are expected to provide a deeper understanding of the material.
Grading policy: The grading policy takes into account the homework assignments (40%). At the end of the semester, there is a possibility to write a critical summary report and discuss it with me (including related material) in my office, or an oral exam about my lectures and the homework assignments (60%).

Lecturing Style

I do not teach from slides. I always use the black-board. I like to prove every result that I teach in details. So, you are guaranteed to have reasons provided for every claim that I will make. It is mathematics after all!
This is the first time that I am teaching this course. I will learn from this experience and will figure out what is the best way of presenting the material. I am very much open to suggestions and criticism and encourage you to give me your valuable comments and opinions so that I can improve future offerings.

General Information

Course information leaflet: ps, pdf.

Course Staff

Lecturer	E-mail	Phone	Office	Office Hours
Dr. Igal Sason	sason@ee.technion.ac.il	04-8294699 (internal: 4699).	Meyer 756.	Monday 16:30--17:30 (and also after the lecture by appointment).

Time & Place

Type	Day	Hour	Room
Lecture	Sunday	16:30--18:30	Meyer 351.

Slides which provide a general overview about codes on graphs and iterative decoding algorithms.

Planned Lectures & Schedule

Number of lectures (March 14 - July 2, 2004) The subject of the lectures

2 lectures
Introduction: communication channels and channel capacity, block and convolutional codes, and motivating the study of codes on graphs and iterative decoding algorithms.

1.5 lectures
Low-density parity-check (LDPC) codes: setting and notations.

2.5 lectures
Asymptotic analysis of LDPC codes on the binary erasure channel (BEC): the iterative message-passing decoder, simplifications, concentration, the recursive equation for the erasure probability, thresholds, stability, capacity-achieving degree distributions.

5 lectures
Asymptotic analysis of LDPC codes on binary, memoryless, symmetric channels: iterative message-passing decoders, density evolution, monotonicity, thresholds, stability, concentration, EXIT charts, the Gaussian approximation for density evolution and approximated threshold transformations.

1 lecture
Parity-check density versus performance of binary linear block codes over memoryless symmetric channels, the connection between parity-check density and complexity for codes defined by standard Tanner graphs, and capacity-achieving ensembles for the binary erasure channel with bounded complexity.

1 lecture
Factor graphs: graphical representation of factorization, recursive determination of marginal functions, belief-propagation decoding of codes on graphs.

1 lecture
The BCJR algorithm, and iterative decoding of turbo codes and interleaved serially concatenated convolutional codes. Repeat-accumulate codes.

Homework Assignments
The purpose of the homework assignments is to enable a deeper understanding of the course. At least four homework assignments should be submitted by every student; the weight of the homework assignments in the final grade is 40% (based on the best four homework assignments).

Homework Assignments (pdf files) Due date

Homework assignment no. 1
April 18, 2004

Homework assignment no. 2
May 2, 2004

Homework assignment no. 3
May 16, 2004

Homework assignment no. 4
Solution included here (NOT for submission).

Homework assignment no. 5
May 30, 2004

Homework assignment no. 6
June 13, 2004

Homework assignment no. 7
July 11, 2004

Homework assignment no. 8
July 25, 2004

Critical summary report
July 25, 2004

References

R. G. Gallager, Low-Density Parity-Check Codes, M.I.T Press, 1963.
Special issue on Codes on Graphs and Iterative Algorithms , IEEE Trans. on Information Theory, vol. 47, no. 2, February 2001.
Special issues on The Turbo Principle: From Theory to Practice (Parts I, II), IEEE Journal on Selected Areas in Communications, vol. 19, no. 5 & 9, May and Sept. 2001.
C. Berrou and A. Glavieux, ``Near optimum error-correcting coding and decoding: turbo codes,'' IEEE Trans. on Communications, vol. 44, no. 10, pp. 1261 - 1271, October 1996.
T. Richardson and R. Urbanke, ``An introduction to the analysis of iterative coding systems,'' in Codes, Systems, and Graphical Models, IMA Volume in Mathematics and Its Applications, pp. 1-37, Springer, 2001.
A. Shokrollahi, ``LDPC codes: an Introduction,'' 2003.
W. Ryan, ``Concatenated convolutional codes and iterative decoding,'' 2001.
S. B. Wicker and S. Kim, Fundamentals of Codes, Graphs, and Iterative Decoding, Kluwer Academic Publishers, 2003. ISBN 1-4020-7264-3.

Send suggestions and/or comments to: sason@ee.technion.ac.il

Last modified : June 21, 2004.

Number of lectures (March 14 - July 2, 2004)	The subject of the lectures
2 lectures	Introduction: communication channels and channel capacity, block and convolutional codes, and motivating the study of codes on graphs and iterative decoding algorithms.
1.5 lectures	Low-density parity-check (LDPC) codes: setting and notations.
2.5 lectures	Asymptotic analysis of LDPC codes on the binary erasure channel (BEC): the iterative message-passing decoder, simplifications, concentration, the recursive equation for the erasure probability, thresholds, stability, capacity-achieving degree distributions.
5 lectures	Asymptotic analysis of LDPC codes on binary, memoryless, symmetric channels: iterative message-passing decoders, density evolution, monotonicity, thresholds, stability, concentration, EXIT charts, the Gaussian approximation for density evolution and approximated threshold transformations.
1 lecture	Parity-check density versus performance of binary linear block codes over memoryless symmetric channels, the connection between parity-check density and complexity for codes defined by standard Tanner graphs, and capacity-achieving ensembles for the binary erasure channel with bounded complexity.
1 lecture	Factor graphs: graphical representation of factorization, recursive determination of marginal functions, belief-propagation decoding of codes on graphs.
1 lecture	The BCJR algorithm, and iterative decoding of turbo codes and interleaved serially concatenated convolutional codes. Repeat-accumulate codes.

Homework Assignments (pdf files)	Due date
Homework assignment no. 1	April 18, 2004
Homework assignment no. 2	May 2, 2004
Homework assignment no. 3	May 16, 2004
Homework assignment no. 4	Solution included here (NOT for submission).
Homework assignment no. 5	May 30, 2004
Homework assignment no. 6	June 13, 2004
Homework assignment no. 7	July 11, 2004
Homework assignment no. 8	July 25, 2004
Critical summary report	July 25, 2004