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 12:30 -- 1:45pm EGR 3111

**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

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).