2005 course plan. Notes are available only where
there is a pdf link.
Model of a communication system. Review of mathematical concepts used in
Linear codes: examples, definition. Generator and parity-check matrices. Hamming
weight. Algorithmic complexity.
Algorithmic problems of coding theory. Linear codes: correctable errors,
Syndrome decoding. Information sets. Information set decoding.
Random binary matrices.The Hamming code, perfect codes. The
Lecture 6 Weight distribution
of the Hamming code. Code optimality. Golay codes. Operations on codes.
Weight distributions. The MacWilliams theorem.Nonlinear codes.
Lecture 8 Weight distribution
for nonbinary codes. Geometric view of codes. Supplementary
view of the MacWilliams theorem. Nonlinear codes. Delsarte
Lecture 9 Introduction to
finite fields. notes: [pdf]
Lecture 10 Structure of finite fields.[pdf]
Lecture 11 Minimal
polynomials, subfields. Uniqueness of Fpm.
Lecture 12 Cyclotomic cosets and
minimal polynomials. [pdf]
Lecture 14 BCH
bound. Nonbinary Hamming codes.[pdf]
Lecture 15 Generalizations
of the BCH bound: Hartmann-Tzeng, Roos. Fourier transform in finite fields.[pdf]
Lecture 16 Linear complexity. Reed
Solomon codes and MDS codes.[pdf]
Lecture 17 Extended RS codes. The
Peterson-Gorenstein-Zierler algorithm for BCH decoding.
Lecture 18 Forney's algorithm.
Evaluation codes. The Berlekamp-Welch decoding algorithm.
Lecture 19 List decoding of codes.
Sudan's algorithm for list decoding of RS codes.
Lecture 20 The Guruswami-Sudan
algorithm, its asymptotic analysis and applications.[pdf]
Lecture 21 Error
probability for bounded distance decoding of linear codes. [pdf]
Lecture 22 Error probability of decoding for Reed-Solomon codes. Error probability for
maximum likelihood (ML) decoding of binary codes, the union bound.
Lecture 23 Asymptotics of binomial coefficients.
The ensemble of random linear codes and the Gilbert-Varshamov bound.
Lecture 24 Linear codes reach the capacity of the binary symmetric channel
Lecture 25 The ensemble of random linear
codes. Average and typical properties. Reed-Muller codes: definition.
Lecture 26 General properties of RM codes. RM
codes of the first order. [pdf]
Lecture 27 Maximum likelihood decoding of RM(1,m) codes.