Course: A Crash Course on Coding Theory
Lecturer: Madhu Sudan, MIT

Date: November 6 - 10, 2000
Location: IBM Almaden Research Center, San Jose, California

Organizers:

David P. Williamson , IBM Almaden, dpw@almaden.ibm.com

This course is a fast-paced introduction to the theory of
error-correcting codes aimed at computer scientists. This theory,
dating back to the works of Shannon and Hamming from the late 40's,
overflows with theorems, techniques, and notions of interest to the
computer scientist. The course will focus on results of asymptotic or
algorithmic significance. The topics will be divided up as follows:

1. Introduction to the theory of error-correcting codes:
   Start with Shannon's coding and converse coding theorem.
   Describe motivation of error-correcting codes (ECCs) in the setting 
   of probabilistic noisy channels. Move to worst-case setting. 
   Introduce fundamental parameters: block length, information 
   rate, distance, and alphabet size. Introduce linear codes.

2. Construction and existence results for ECCs:
   Basic ECCs: Hamming, Hadamard, Reed-Solomon, Reed-Muller, BCH.
   Codes obtained by combining codes: tensor product and concatenation.
		Example of Justesen codes.	
   Existence of good codes via the probabilistic method.
   Bird's eyeview of Algebraic geometry (AG) codes.
   (More codes to be introduced in Part 5.)

3. Limitations on the combinatorial performance of ECCs.
   The nature of the tradeoff between rate and distance.
   Quantitative review of positive results: (Justesen, Prob. codes, AG)
   Limitation results: Singleton bound, Hamming bound, Plotkin
   		bound, and Bassalygo-Elias bounds. 
   (Perspective: How to deal with huge number of bounds?)
   Duality and the MacWilliams Identities.
   Linear Programming bound.

4. Decoding algorithms - Part 1.
   The decoding problem: Unambigous and list-decoding versions.
   Unambiguous Decoding for algebraic codes:
		Example: Reed Solomon decoding
		Abstracting to wide subfamily of linear codes.
   		Sample corollary: decoding AG codes.
   List decoding for algebraic codes:
		Example: Reed Solomon decoding
		Abstracting to "ideal" codes.
		Corollary: decoding number-theoretic codes.

5. Decoding algorithms - Part 2.
   The linear time decoding problem: worst-case and random error settings.
   Worst case setting: Expander (Spielman) codes.
   Probabilistic noise setting: Tornado(TM) codes.
			Achieving Shannon limit on erasure channel.
			(May include Turbo codes here).

6. Complexity results.
   Complexity of the decoding problem for arbitrary linear codes.
   Complexity of estimating the distance.
   Decoding up to minimum distance.
   Status of the ``decoding up to unambiguous decoding radius problem''

7. Applications in computer science. (Assorted collection.)

Breakup of topics to be covered:
	Day 1 - Parts 1,2
	Day 2 - Part 3
	Day 3 - Part 4
	Day 4 - Part 5
	Day 5 - Parts 6, 7.

Next: Call for Participation

Workshop Index

DIMACS Homepage