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

  1. Algebraic coding: linear codes, basics of finite fields, Hamming, Reed-Solomon and BCH codes.

  2. Bounds on Error Correcting Codes: Sphere-packing, Plotkin, and linear programming bounds. .

  3. Random Coding and Communications: Shannon's coding theorem, convolutional codes and LDPC codes.

  4. 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
  1. Linear Algebra: Vector spaces, linear transformations, matrices.
  2. Elementary probability theory
  3. 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.
  1. Error Correction Coding: Mathematical Methods and Algorithms (1st Edition), by Todd K. Moon.
  2. Online lecture notes by Prof. Madhu Sudan and a draft of a textbook by Venkat Guruswami, Madhu Sudan and Atri Rudra
  3. 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
  1. 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.
  2. 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:
  1. 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.
  2. 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.
  3. 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.