UB - University at Buffalo, The State University of New York Computer Science and Engineering

CSE 545: Error Correcting Codes: Combinatorics, Algorithms, and Applications

Coding Theory

Error correcting codes (or just codes) are systematic ways of introducing redundancy into data so that the original information can be recovered even when the data is corrupted. Codes are used ubiquitously in communication systems and data storage. The study of error correcting codes (or coding theory) started with the seminal works of Shannon and Hamming in the late 1940s and has been an active cross-disciplinary research area since then. This course will discuss the theoretical aspects of codes and will focus mostly on the worst-case noise model pioneered by Hamming. However, we will discuss quite a few results on the stochastic noise model pioneered by Shannon. The course will roughly cover three parts: (i) combinatorial aspects of codes, i.e. the limit of what can and cannot be achieved with codes; (ii) computationally efficient algorithms for using codes; and (ii) application of codes in theoretical computer science. Major developments in coding theory since the 1990s will be emphasized.

None presently available.

Ph.D.:

This course fulfills one Theory/Algorithms Core Area (Depth) requirement.

M.S.:

This course fulfills one Theory/Algorithms Core Area (Depth) requirement.

There is no specific course pre-requisite for this course. However, some “mathematical maturity” will be essential. In particular, comfort with basics of linear algebra (vector spaces, basis, dual spaces); finite fields, field extensions and polynomials over finite fields; elementary probability; analysis of algorithms; and some exposure to computational complexity will be useful. Some of these topics (for example finite fields) can be learned on a need to know basis as the course progresses. Students should email the instructor if they have any questions about the pre-requisites.

Course Instances
Semester Section Title Instructor Credit Hours Enrolled
Spring 2013 LEC Coding Theory Dr. Atri Rudra 3 6/60
Spring 2012 LEC Coding Theory Dr. Atri Rudra 3 25/30
Spring 2011 LEC Coding Theory Dr. Atri Rudra 3 11/50
Spring 2010 LEC Coding Theory Dr. Atri Rudra 3 8/50
Spring 2009 LEC Coding Theory Dr. Atri Rudra 3 6/50
Valid XHTML 1.0 Transitional