EE 564, CSE 554 - Error Correcting Codes, Spring 2018

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 and Singleton Bound.

  3. Random Coding and Communications: Shannon's coding theorem, capacity achieving Polar codes

  4. Graph-based codes: LDPC and expander codes, iterative message passing decoding.

  5. Emerging topics in coding theory: Codes for distributed storage and distributed computing, index and network coding.
Time permitting, additional topics related to applications to inference, secret sharing and compressed sensing will be covered.

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: 101 EE West

CLASS HOURS: MWF 1:25 PM - 2:15 PM

INSTRUCTOR: Viveck Cadambe (230 EE West, viveck@engr.psu.edu)

OFFICE HOURS: Instructor available after class or by appointment.

TEXTBOOK AND REFERENCE BOOKS

There is no textbook for the course, the following reference materials might be useful. REFERENCE MATERIALS

There are a number of good textbooks and online reference materials on the topic of error correcting codes. list some which the student is likely to find particularly useful.
  1. Ron Roth, Introduction to Coding Theory, Cambridge University Press 2006.
  2. Error Correction Coding: Mathematical Methods and Algorithms (1st Edition), by Todd K. Moon.
  3. Modern Coding Theory, Richardson, T. Urbanke, R. Cambridge university press 2008.
  4. Online lecture notes by Prof. Madhu Sudan and a draft of a textbook by Venkat Guruswami, Madhu Sudan and Atri Rudra

GRADING POLICY

Homeworks (35%), One midterm exam (25%), Final Project (30%), Class participation (including scribing) (10%).

Collaboration and extra reading is allowed for homework questions. Copying homework answers is NOT allowed. In case a student has collaborated with another student in solving a question, or the student borrowed an idea from some external reference, the student must list the name of the collaborator or cite the external reference, and briefly describe the borrowed ideas. 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.

The class notes will be scribed in a group-wise effort by the students. Students will type out week-wise notes in Latex. Notes for Monday-Wednesday-Friday will be due on Thursday of the following week. Each student will sign up for two weeks in the semester. For each week, we will have either two or three students scribing, and the scribes will collaborate and send one document to me. The student scribe is expected to understand the material properly, possibly via discussions with instructor, and via reference material, and type out correct, well-written lecture notes. The non-scribing students are encourage to detect errors and typos in scribed notes and mail them to me. A latex template and sign up link will be emailed to you.

ACADEMIC INTEGRITY

All Penn State policies regarding ethics and honorable behavior apply to this course.

Counseling & Psychological Services (CAPS) Statement

Students who experience personal issues that interfere with their academic performance, social development or satisfaction at Penn State are encouraged to seek confidential assistance from Counseling and Psychological Services (CAPS) Center (http://studentaffairs.psu.edu/counseling/). They can be reached at (814) 863-0395. Some of the more common concerns they can help with include anxiety, depression, difficulties in relationships (friends, roommates, or family); sexual identity; lack of motivation or difficulty relaxing, concentrating or studying; eating disorders; sexual assault and sexual abuse recovery; and uncertainties about personal values and beliefs. Crisis intervention is available from Centre County CAN HELP (http://centrecountypa.gov/index.aspx?NID=593) at 1-800-643-5432, 24 hours a day, seven days a week.

LECTURES

Lectures notes may (will!) contain errors, use at your own risk.

First lecture

Week 1

Week 2

Week 3

Week 4

Week 5

Week 6

Week 7

Week 8

Week 9

Week 10

Week 11

Week 12

Week 13

Week 14

PROJECT DETAILS

The course project will be done in teams of two, or one. The main goal of the project is to get tutorial-like understanding of 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 can be demonstrated via simulations, or theoretical approaches, or a combination of both as appropriate. The project will involve
  1. A 25 minute presentation delivered in class that clearly explains the topic/problem, the model considered in the paper/papers/books, and the main technical contribution. Slides are recommended for this presentation. The project should also aim to give a sense of the state of the art in the topic, especially if the topic is of current-day relevance.
  2. A second possibly longer lecture/presentation+discussion extending the in-class presentation, to be presented to me in my office. You can prepare for this part via via slides, or an on-board talk where you go into the technical details.
  3. A project report going into 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.