ENEE 626: ERROR CORRECTING CODES

Graduate course for 1 st – 2 nd year students in EE, CS, Applied Math

Instructor : Alexander Barg, Professor
Department of Electrical and Computer Engineering/Institute for Systems Research
Office: 2361 A.V.Williams Building Tel. (301) 405 7135 E-mail abarg at  umd  dot edu

Class times: Tuesday, Thursday 11:00am -- 12:15pm EGR 1110
Instructor availability outside class hours: I am in my office most of the time: arrange to see me after class
Homepage: http://www.ece.umd.edu/~abarg/626

Grading: several home assignments (20%)
            class participation (20%)
            course project (30%)
            final (30%) (take-home exam).

No required textbook. Lecture notes: Part I Part II Part III Part IV
Recommended reading: R. Roth, Introduction to coding theory.
J. I. Hall's lecture notes

    Home assignments (from 2015 class)

H1 H2 H3

Final exam [pdf] (from 2015)

Supplemental information for the course projects:
talk on polar codes 
Papers on Turbo and LDPC decoding
Iterative decoding;  Exit Charts 1  2 Design of LDPC codes
optimizer of LDPC codes


Main topics:

General properties of linear codes. Matrix description, error correction, minimum distance, syndrome decoding. Bounds on codes.
            References: Ch. 3,9 in J. Hall's lecture notes, see above.
Random codes. Channel capacity, capacity-achieving families: Polar codes, LDPC codes
Finite fields. Reed Solomon codes and their decoding. List decoding algorithms (correct more errors than you can think of). Coding for compact disks.
Coding for distributed storage.
            References: 1. A family of codes with locality [pdf] 2. Talk on codes with local recovery [pdf]
Selected problems in cryptography: Secret sharing schemes, Wire-tap channel, Generating secret keys
            References: 1. D. Stinson, An explication of secret sharing schemes [pdf]; 2. Ozarow-Wyner, Wire-tap channel [pdf].
Network coding as alternative to routing: Linear network codes and capacity of multicasting

Calculations with finite fields and codes are much easier with GAP (Groups, Algorithms, and Programming). It is much better suited for manipulation of codes and computations for codes than general-purpose software such as MatLab. Gap needs to be installed locally. It has a special-purpose package to work with error correcting codes, called Guava. You can use GAP to check your homework papers, but unless specially stated, your solutions should be proof-based, not computer-based, and done by hand.

Sample exams: 1 2 3 4 5 6 7 8 9 10 11 12 13
A long list of problems (some were used in the above exams).