The problem of correct transmission of data in a noisy environment. The design and analysis of codes that efficiently (in terms of data rate and encryption and decryption speed) correct errors. Linear and nonlinear block codes, general encoding and decoding techniques, fundamental bounds, dual codes, cyclic codes. Specific codes will be studied, including Hamming, BCH, Reed-Muller, Reed-Solomon, trellis, and convolutional codes.
CS 515 or consent of instructor.
Students must have a solid background in discrete mathematics (CS275) and algorithm design and analysis (CS515).
Successful students will learn:
1. Basic issues of communication in a noisy environment.
2. Basic approaches to error correction.
3. Mathematical tools for analyzing and designing error correcting codes, including the theory of finite fields.
4. Fundamental limits of error correction.
5. The background needed to read the current literature in coding theory.
Week by Week Course Outline:
This is a sample outline. Exact outline will be determined by the instructor offering this course.
|1-2||Introduction and linear codes|
|3||Hamming codes and basic constructions|
|4-5||Finite fields and double error correcting BCH codes|
|6-7||Dual codes and cyclic codes|
|8||Multiple error correcting BCH codes|
|12-13||Trellis and convolutional codes|
Exact details about graded work in this course will be determined by the instructor offering the course and will be made available in the syllabus during the first class meeting. Typically there will be a presentation of a paper in the recent literature by each student, bi-weekly homework, and a two-hour final examination.
A student's grade will be determined by a weighted average of homework assignments, presentation, and the final examination. The faculty offering the course will make the details available at the start of the course. A typical weighting is:
Paper presentation: 25%
Final Examination: 35%
F. MacWilliams and N. Sloane,
The Theory of Error-Correcting Codes,
North-Holland Press, 1977.