ENEE 626: Error Correcting Codes
Course Goals:
To introduce the main concepts of coding theory and the body of its central results (combinatorial, algebraic, probabilistic). To prepare a starting point for advanced studies in coding theory and point the students to possible research areas.
Course Prerequisite(s):
Linear Algebra
Topics Prerequisite(s):
Textbook(s)
[1] F. J. MacWilliams and N.J.A. Sloane, The theory of error-correcting codes, North Holland 1991. ISBN: 0-444-85193-3[2] R. Blahut, Algebraic codes for data transmission, Cambridge University Press 2003. ISBN: 0-521-55374-1
[3] J. Justesen and T. Hoholdt, A course in error correcting codes, European Math. Society 2004. ISBN: 3-03719-001-9
Reference(s):
Lecture notes, selected journal articles, and problem sets on ECE class web site
Core Topics:
1. Introduction to coding theory. (2 lectures)
Applications of coding theory. First properties of codes.
Complexity of algorithms.
2. Linear codes and their properties (6 lectures)
Linear codes and their properties.
Generator and parity-check matrices. Standard array.
Information sets. Decoding.
The binary Hamming codes. The binary Golay code.
Weight distributions and the MacWilliams theorem.
Krawtchouk polynomials. Delsarte inequalities.
3. Introduction to algebra (3 lectures)
Groups and fields.
Structure of finite fields. Primitive elements.
Minimal polynomials and factorization of x^n-1.
4. Cyclic codes (6 lectures)
Polynomial description of cyclic codes.
The cyclic form of the Hamming code.
BCH bound and BCH codes.
Fourier transform in finite fields.
Spectral description of BCH codes.
Improvements of the BCH bound (the Hartmann-Tzeng and Roos bounds)
MDS and Reed-Solomon codes.
The Gorenstein-Peterson-Zierler decoder of BCH codes.
Other decoding methods: the Berlekamp-Massey algorithm, the
Guruswami-Sudan algorithm.
5. Reed-Muller codes (2 lectures)
Definition and parameters of the Reed-Muller codes.
Reed-Muller codes as cyclic codes.
Reed-Muller codes of the first order. Correlation decoding.
Pseudo-noise sequences.
5. Bounds on the error probability of decoding (2 lectures)
Maximum likelihood decoding and bounded distance decoding.
The problem of attaining capacity.
Error probability of bounded distance decoding.
Probability of error events for Reed-Solomon codes.
Error probability of maximum likelihood decoding.
6. The ensemble of random linear codes (3 lectures)
The Gilbert-Varshamov bound and the average weight distribution.
Asymptotic nature of coding theory problems.
Asymptotic of binomial coefficients.
Average and typical properties of codes in the ensemble.
Linear codes reach capacity of the binary symmetric channel.
7. Bounds on codes: Hamming, Bassalygo-Elias, Delsarte. (1 lecture)
8. Convolutional codes (2 lectures)
Definition and main parameters of convolutional codes.
Trellis decoding for convolutional and block codes.
9. An overview of iterative decoding methods (as time permits)
10. Current research in coding theory (as time permits)