EE 564, CSE 554 - Error Correcting Codes, Spring 2016
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. Error correcting codes use
sophisticated techniques from algebra, probability, graph theory and combinatorics. This course is an introductory course on the theory of error correcting codes. The course aims to do two things: provide an introduction to the most important basic techniques in modern error correcting codes, and prepare students to begin independent research in the area of coding theory. The topics covered include
- Algebraic coding: linear codes, basics of finite fields, Hamming, Reed-Solomon and BCH codes.
- Bounds on Error Correcting Codes: Sphere-packing, Plotkin, and linear programming bounds. .
- Random Coding and Communications: Shannon's coding theorem, convolutional codes and LDPC codes.
- Emerging topics in coding theory: Codes for distributed storage, locally recoverable codes, network coding and related topics.
PREREQUISITES
The most important requirement is mathematical maturity, in particular, interest in learning new, relevant, mathematical concepts. The student will be expected to be proficient in
- Linear Algebra: Vector spaces, linear transformations, matrices.
- Elementary probability theory
- Elementary discrete mathematics
Knowledge of a programming language (preferably matlab or python) will be required to conduct some elementary simulations.
Familiarity of information theory and undergraduate algebra is helpful but not necessary.
LOGISTICS
LOCATION: 103 EE West
CLASS HOURS: MWF 1:25 PM - 2:15 PM
INSTRUCTOR:
Viveck Cadambe (111 J EE West, viveck@engr.psu.edu)
OFFICE HOURS: Instructor available after class or by appointment.
TEXTBOOK AND REFERENCE BOOKS
TEXTBOOK
Ron Roth, Introduction to Coding Theory,
Cambridge University Press 2006
ISBN-10: 0521845041
ISBN-13: 978-0521845045
REFERENCE MATERIALS
There are a number of good textbooks and online reference materials on the topic of error correcting codes. I list some which the student is likely to find particularly useful.
- Error Correction Coding: Mathematical Methods and Algorithms (1st Edition), by Todd K. Moon.
- Online lecture notes by Prof. Madhu Sudan and a draft of a textbook by Venkat Guruswami, Madhu Sudan and Atri Rudra
- Online video lectures (https://goo.gl/63Kc29) by Prof. P. Vijay Kumar on the "nptelhrd" channel on youtube.
GRADING POLICY
Homeworks (30%), Two midterm exams (20%+20%), Final Project (30%)
Collaboration is allowed for homework questions, but not encouraged. Copying homework answers is NOT allowed. In case a student has collaborated with another student in solving a question, the student must list the name of the collaborator, and briefly describe the nature of the collaboration in the submitted homework. In any case, each student must turn in his or her own homework, which should contain the student's understanding of how the problem is solved.
Project submission will involve an in-class presentation and a detailed report. Project ideas will be provided mid-way during the semester.
ACADEMIC INTEGRITY
All Penn State policies regarding ethics and honorable behavior apply to this course.
LECTURES
Lectures notes may (will!) contain errors, use at your own risk.
First lecture
Week 1
Weeks 2 and 3
Weeks 4 and 5
Notes for guest lecture on Syndrome Decoding
Week 6
Week 7
Week 8
Week 9
Week 10
Week 11
Algebraic Decoding of BCH codes
Week 12
Week 13
HOMEWORKS
Homework 1
Homework 2
Homework 3
Homework 4
Homework 5
PROJECT DETAILS
The course project will be done in teams of two, or one. The main goal of the project is to understand a topic that is not covered in the class, but related to the materials covered. The typical project will involve a literature survey, a statement of the problem, an explanation of the idea associated with the topic, and a performance comparison with other methods (if relevant). The performance comparison demonstrated via analytical or theoretical means.
The project will involve
- A 25 minute short presentation in class that clearly explains the topic/problem, the model considered in the paper/papers/books, and the main technical contribution. If the project is done in a group, the time allocated for presentation should be split among the members of the group.
- A project report of approximately 10 pages + references going to more details and formal statements. The report should not reproduce the paper or any text, but explain the student's understanding of the topic in his or her own words. If the project is done in a group, each member of the group should submit his or her own report.
Grading Scheme for the Project: I will look for the following three components in the project:
- Literature survey. The literature survey should demonstrate a comprehensive understanding of the history of the topic. It should give a sense of why the problem considered is important, and was missing before the topic/paper.
- Results and ideas: The main technical idea that helped filled this gap should be explained in a clear and understandable manner. The performance of the idea must be evaluated using numerical or analytical means as appopriate.
- Clarity of presentation and writing: Points will be given for clear and lucid presentation and writing.
List of project ideas
The following is a sample list of candidate papers/ideas. However, the student is welcome to deviate from this list with in discussion with the instructor. The papers are also representative of topics, and the student is encouraged to scout for other resources (papers, notes, textbook materials etc.) in the chosen topic. The list is provided in no particular order.
- Locally recoverable codes: A Family of Optimal Locally Recoverable Codes,
- Codes with good Repair Bandwidth in Distributed Storage: The paper introduced the problem, and/or this recent repair strategy for Reed-Solomon code Codes
- Array codes for distributed storage systems: EVENODD Code, "RDP" Code, MDS array codes with independent parity symbols and other variants.
- Rateless codes: this survey on fountain codes, and/or or this survey, and/or Raptor codes and references therein.
- Polar codes: This paper, and/or this this tutorial
- Shannon Capacity of a graph: On the Shannon capacity of a graph
- Topics in LDPC and graph-based codes: Density Evolution Analysis for LDPC Codes (found in various textbooks, including "Modern Coding Theory" by Urbanke and Richardson), Factor graphs and the sum-product algorithm
- Network Coding: This network coding algorithm, Subspace network coding