ENEE 626:

ERROR CORRECTING CODES

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

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 3:30-4:45pm EGR 1104
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

Main topics:

General properties of linear codes. Matrix description, error correction, minimum distance, syndrome decoding. Bounds on 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). Mathematics of the compact disk.

Selected problems in cryptography: Secret sharing schemes, Wire-tap channel, Generating secret keys

Network coding as alternative to routing: Linear network codes and capacity of multicasting

Grading: several home assignments (20%), class participation (30%),  final (50%) (take-home exam).
No required textbook. Recommended: R. Roth, Introduction to coding theory.
Lecture notes: Part I Part II Part III


Home assignments
1 (due on Feb.18)
2 (due on March 13)
3 (Due on May 6)

Presentation topics:

(1) Index coding (Taken)
Main reference: [1]
Other references:
E. Lubetzky and U. Stav. Non-linear index coding outperforming the linear optimum. In Proc. of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 161--167, 2007.
Index coding with side information
Broadcasing with side information

(2) Rank modulation
References:
A. Jiang, R. Mateescu, M. Schwartz, and J. Bruck, ``Rank modulation for flash memories,'' IEEE Trans. Inform. Theory, vol. 55, no. 6, pp. 2659--2673, 2009.
A. Barg and A. Mazumdar, Codes in permutations and error correction for rank modulation, arXiv:0908.4094

(3) Group testing: (Taken) The main source is the book by Du and Hwang, I'll lend you a copy to prepare your presentation.