CS 673 - Error Correcting Codes

Bulletin Description

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.

Prerequisites

CS 515 or consent of instructor.

Expected Preparation

Students must have a solid background in discrete mathematics (CS275) and algorithm design and analysis (CS515).

Student Learning Outcomes

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.

Syllabus Information

Week by Week Course Outline:

This is a sample outline. Exact outline will be determined by the instructor offering this course.

 

Weeks Topics
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
9 Reed-Solomon codes
10-11 Reed-Muller codes
12-13 Trellis and convolutional codes
14-15 Student talks

Graded Work:

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.

Grading:

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:

Homeworks: 40%
Paper presentation: 25%
Final Examination: 35%

Possible Textbooks:

F. MacWilliams and N. Sloane,
The Theory of Error-Correcting Codes,
North-Holland Press, 1977.