Codes on Graphs
Catalog Data: 

Graduate Course Information


ECE 635 - Codes on Graphs

Credits:  3.00

Course Website:

UA Catalog Description:

Course Assessment: 

Homework:  assigned but not graded

Project:  1-2 projects

Exams:  2 Midterm Exams, 1 Final Exam

Grading Policy:

Typically: 30% Midterms,

               35% Final Exam,

               15% Homework,

                 0% Laboratory,

                20% Project.

Course Summary:

This graduate course provides an in-depth treatment of modern error correction codes and decoding algorithms.

            Error correcting codes (ECC) are an integral part of modern day communications, computer and data storage systems and play a vital role in ensuring he integrity of data in the presence of errors. In the most general terms, the purpose of error correcting code is to protect user data, and this is achieved by appending redundant, so called parity bits, along with the data bits. Low-density parity-check (LDPC) codes are a class of error-correction codes that have revolutionized communications and data storage industry. They have been the focus of intense research over more than a decade because they can approach theoretical limits of reliable transmission over various communications and storage channels even when decoded by sub-optimal low complexity iterative algorithms. The past decade in

information theory has been marked by the quest for low complexity decoders, and the emergence of iterative message passing decoders.        Efficient and high-speed implementations coupled with recent advances in integrated circuit technologies, have made LDPC codes de-facto industry standards in a number of systems. With emerging technologies requiring much faster processing speeds with stricter energy utilization constraints while still requiring very low target error-rates, there has been an increasing need for reduced-complexity iterative decoders that provide improved performance.

            Wireless networks, satellite communications, deep-space communications, power line communications are among applications where the LDPC codes are the standardized ECC scheme. More specifically LDPC codes are used as an error correcting scheme in: digital video broadcast over satellite (DVB-S2 Standard) and over cable (DVB-C2 Standard), terrestrial television broadcasting (DVB-T2, DVB-T2-Lite Standards), GEO-Mobile Radio (GMR) satellite telephony (GMR-1 Standard), local and metropolitan area networks (LAN/MAN) (IEEE 802.11 (WiFi)), wireless personal area networks (WPAN) (IEEE 802.15.3c (60 GHz PHY)), wireless local and metropolitan area networks (WLAN/WMAN) (IEEE 802.16 (Mobile WiMAX), near-earth and deep space communications (CCSDS), wire and power line communications ( ITU-T (G.9960)), utra-wide band technologies (WiMedia 1.5 UWB), etc. [11]. Very recently LDPC codes have found their way in magnetic hard disk drives and optical communications, and they are the main candidates for ECC system in ash memories.

Graduate Standing

Tom Richardson, and Ruediger Urbanke, Modern Coding Theory

S. Lin and W. Ryan, Channel Codes: Classical and Modern

D. J. C. Mackay, Information Theory, Inference & Learning Algorithms

M. I. Jordan, An Introduction to Probabilistic Graphical Models 

Course Topics: 

1.     Codes on graphs and low-density parity-check codes

2.     Graphical representation of a code (trellis, Tanner graph)

3.     Low-density parity check (LDPC) codes

4.     Codes constructed from combinatorial designs and other structures

5.     Expander codes and expander arguments

6.     Graph topology and code parameters

7.     Iterative decoding

8.     Bayesian networks, exact and approximate inference

9.     Factor graphs, inference, counting, message passing algorithms,

10.  Gallager type algorithms, bit-flipping

11.  Analysis of LDPC codes and error floor phenomenon

12.  Trapping sets

13.  Llinear programming decoding

14.  Polar codes

Relationship to Student Outcomes: 

Lecture:  150 minutes/week

University of Arizona College of Engineering