ERROR CORRECTING CODES
Graduate course for 1st – 2nd
year students in EE, CS, Applied Math
Instructor : Alexander
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
Instructor availability outside class hours: I am in my office most of the time: arrange to see me after class
• 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
1 (due on Feb.18)
2 (due on March 13)
(1) Index coding
Main reference: 
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
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.