Instructor : Alexander Barg,
Professor
Department of Electrical and
Computer Engineering
Department of Computer Science
Applied Mathematics and Scientific Computation Program
2361 A.V.Williams Building
Tel. (301) 405 7135
E-mail abarg at umd
dot edu
Class times: Tuesday and Thursday 3:30-4:45pm
CSI2118
Instructor availability outside class hours:
After class and by appointment
Homepage: http://www.ece.umd.edu/~abarg/626
Contents of the course
I.
Introduction to coding theory
Lectures 1-8.
General properties of linear codes.
Lecture 9. Weight distribution of codes. The MacWilliams theorem.
II. Algebraic
coding theory
Lectures 10-11. Introduction to Finite Fields.
Lecture 12. Reed-Solomon (RS) codes and MDS codes
Lecture 13. Decoding of RS codes. The Berlekamp-Welch algorithm
Lecture 14. List decoding of RS codes: The Sudan algorithm
Lecture 15-16. List decoding of RS codes: The Guruswami-Sudan algorithm
Lecture 17. More on finite fields: Cyclotomic cosets and Minimal polynomials
Lecture 18-19. Cyclic codes; BCH codes
III
Random coding; Coding theorems
Lecture 21. Bounds on codes. Asymptotics of binomial coefficients.
Asymptotic bounds.
Lecture 22. Ensembles of random binary codes and
the Gilbert-Varshamov bound.
Lecture 23-24. Linear codes reach capacity of the binary
symmetric channel.
IV.
Practical ways of approaching capacity. Iterative
decoding
Lecture 26. Code concatenations: Serial, parallel. Codes on graphs.
Lecture 27. Iterative decoding: the belief propagation algorithm.
Lecture 28. LDPC codes on the erasure channel.
Time
permitting
Lecture xx. LDPC codes on binary-input channels.
Lecture xx. Reed-Muller codes.
Lecture xx. Fast decoding of the RM(1,m) code
Prerequisites
for the course
The main prerequisite is mathematical maturity,
in particular, interest in learning new mathematical concepts.
No familiarity with information theory and communications-related courses
will be assumed. On the other hand,
I am expecting the students to be comfortable with linear spaces,
elementary probability and
calculus, and elementary concepts in discrete mathematics such
as binomial coefficients and an assortment of related facts.
Although I will give all the necessary definitions, prior
familiarity will facilitate understanding. No required
textbook.
Homeworks,
Exams, Grading
There will be several home assignments, one midterm exam, and one final exam. The
midterm will be held on Tue 10/23 in class, final exam
TBA, CSI2118. The exams are closed books. No computers,
calculators are allowed.
·
Grading Policy:
Home assignments 20%, Midterm 40%, Final
40%
Course mail: A class e-mail list will be set up using the e-mail
addresses recorded in the university system. I am expecting the
students to access
their e-mail accounts at least once a week. Class-related communication
will be distributed via e-mail.
Materials available
·
Slides of lectures.
·
Part I
·
Part II
·
Part III
·
Part IV
·
2005 Course notes
· Final
exams 2007 '06
'05
·
Midterms
2007 '06
'05
References
[1] R. Roth, Introduction to coding theory, Cambridge University Press 2006,
ISBN-13 978-0-321-94504-5
[2] F. J. MacWilliams and N.J.A. Sloane, The theory of error-correcting codes,
North Holland 1991. ISBN: 0-444-85193-3
[3] J. Justesen and T. Hoholdt, A course in error correcting codes, European
Math. Society 2004. ISBN: 3-03719-001-9
Announcements
Changes of schedule
·
No class on Sept. 23. Make-up
class on Sept. 12 (4:00pm). Room TBA
·
Come to the research
seminar
on
information and coding theory to learn about current research in these fields