# CS395T, EE381V, M390C, Coding Theory Fall 12

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 3:30-5:00

LOCATION: RLM 10.176

UNIQUE NUMBER: (16960 for EE381V) (53225 for CS395T) (56475 for M390C)

OFFICE HOURS: Vishwanath Tue 5:00-6:30 PM and Wed 4:00-5:00 PM,
Voloch Wed 9:30-11:30 AM, Zuckerman Wed 1:30-3:30 PM or by appointment.

TA: Abhishek Bhowmick, (Email: bhowmick@cs.utexas.edu , Office hours Mon 3:30-4:30 ACES 3.102).

TEXTBOOK: Ron Roth, Introduction to Coding Theory,
Cambridge University Press 2006 and online lecture
notes by
M. Sudan,
V. Guruswami and
A. Rudra. These notes are being put together in a book and
some chapters are available.

PREREQUISITES: Basic Undergraduate Algebra and Probability background

GRADING POLICY: Final Exam (on Saturday, December 15, from 7:00-10:00 pm,
RLM 6.126): 50%,
Homework, (six assignments): 40%,
Participation: 10%

REVIEW: There will be a review for the final in class on 12/6.

## Homework

- Roth, problems: 2.11(items 1,2,3), 2.16, 4.3, 4.4, Due 10/2.
- This assignment. Due 10/9.
- Roth, problems: 2.17, 3.17, 5.5, 5.30, Due 10/30.
- This assignment. Due 11/8.
- This assignment. Due 11/27.
- This assignment. Due 12/6.

## 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.