CS395T, EE381V, M390C, Coding Theory Fall 10

DESCRIPTION: Error-correcting codes provide a way to efficiently add redundancy to data, so that the original data can be recovered even in the presence of noise. Such codes are essential in modern communication and storage of data, where high reliability is required. From its engineering roots, coding theory has evolved to use sophisticated mathematical techniques, centering around algebra but also involving probability and combinatorics. Moreover, coding theory has recently found unexpected uses in computer science.

In this interdisciplinary course, we study coding theory from the different perspectives of professors in math, computer science, and electrical engineering. We develop the mathematical tools, construct important codes and associated algorithms, and discuss applications in computer science and communication.

Class Outline

Algebraic coding: including linear codes, finite fields, Hamming, Reed-Solomon, BCH and Golay codes.
Algorithmic coding: including decoding algorithms, concatenated codes, list decoding concepts, and applications to computational complexity.
Random Coding and Communications: Shannon's coding theorem, LDPC and rateless coding, network coding and related topics.

INSTRUCTORS: Sriram Vishwanath (ENS 439A ph. 471-1190, sriram@ece.utexas.edu), Felipe Voloch (RLM 9.122, ph. 471-2674,

) and David Zuckerman (CSA 1.120A, ph. 471-9729, diz@cs.utexas.edu).

CLASS HOURS: TTh 11:00 -- 12:30

LOCATION: RLM 12.166

UNIQUE NUMBER: 16910 (for EE381V) 52680 (for CS395T) 55740 (for M390C)

OFFICE HOURS: Vishwanath Tue 4:00-6:00 PM, Voloch Wed 9:00-11:00 AM, Zuckerman Thu 2:00-4:00 PM or by appointment.

TEXTBOOK: Ron Roth, Introduction to Coding Theory, Cambridge University Press 2006 and Madhu Sudan, An Algorithmic Introduction to Coding Theory. (available online).

PREREQUISITES: Basic Undergraduate Algebra background

GRADING POLICY: One Exam (on 12/10 2:00-5:00 PM, ENS 109): 50%, Homework, (every other week): 40%, Participation: 10%

Homework

Chapter 2. Problems: 2.1, 2.10, 2.11, 2.16, Due 9/16.
Chapter 3, Problems: 3.6, 3.27, Chapter 4, Problem 4.7 and Chapter 5, Problem 5.15. Due 9/23.
Third assignment. Due 10/21.
Fourth assignment. Due 11/2.
Fifth assignment. Due 11/12.
Sixth assignment. Due 11/23.

Links

The University of Texas at Austin provides upon request appropriate academic accommodations for qualified students with disabilities. For more information, contact the Office of the Dean of Students at 471- 6259, 471-6441 TTY.