Instructor : Alexander Barg,
Professor
Department of Electrical and
Computer Engineering/Institute for Systems Research
Department of Computer Science;
Applied Mathematics and Scientific Computation Program
Office: 2361 A.V.Williams Building Tel. (301) 405 7135 E-mail abarg at umd
dot edu
Class times: Monday and Wednesday 2:00-3:15pm EGR2116
Instructor availability outside class hours:
After class and by appointment
Homepage: http://www.ece.umd.edu/~abarg/626
Blurb: Error-correcting codes are an integral component of all
communication systems currently in operation.
CD players and computer hard drives are protected from errors by RS codes (Lect.
12-16); communication
with deep-space missions depends crucially on LDPC codes (Lect. 28), and
transmission over fiber-optic cables
would not be possible without a number of codes discussed in our course. At the
same time, the theory of error
correcting codes offers a large number of exciting research problems in
theoretical engineering/applied mathematics,
which makes this area appealing to both theoretically minded communication
engineers and applied mathematicians
who don't mind to learn about actual applications of their ideas.
A student evaluation (2008): "Excellent
course. Well prepared lectures, good assignments. Good availability outside of
class. I definitely recommend Dr. Barg to any student (willing to work hard)
considering one of his courses."
I agree with this: the course
will require an effort, but you will learn the subject.
New in 2009: Guest lecture(s) by
Prof. Navin Kashyap (Queen's
University, Kingston, Ontario) on
graphical models for linear codes.
Contents of the course (all lectures are available on slides)
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.
Home assignment 1 Home assignment 2
Home assignment 3 Home assignment 4
Midterm
Final Thursday 12/17 1:30pm
Dates of exams To Be Determined. 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 2008 2007 '06
'05
·
Midterms
2008 '07 '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 12/2, makeup class TBA
·
Come to the research
seminar
on
information and coding theory to learn about current research in these fields