Coding Theory Course

[Nancy Benigar]

CourseDescription:Error-correcting codes play an important role in many areas of scienceand engineering. This course is a graduate level introduction toerror-correcting codes, with a focus on the theoretical andalgorithmic aspects arising in the context of the "channel coding"problem: We want to transmit data over a noisy communication channelso that the receiver can recover the correct data despite the adverseeffects of the channel.

Starting from the basics of coding theory and some of the classictheorems of the subject, the course will discuss more recent progresson code constructions and error-correction algorithms. List ofpotential topics include: Shannon coding theorem and noise models (worst-case, stochastic) Basics notions and combinatorial bounds of coding theory Classical code constructions (algebraic, LDPC, concatenated, etc.) Reed-Solomon decoding and applications Expander codes and linear time error-correction List decoding; error-correction with optimal redundancy. Iterative decoding methods and belief propagation Rateless codes; convolutional codes. Codes in computational complexity

Course Description: Error-correcting codes play an importantrole in many areas of science and engineering, as they safeguard theintegrity of data against the adverse effects of noise incommunication and storage. They have also become important tools intheoretical computer science and related mathematics. This is atheoretically oriented graduate course, though mathematicallysophisticated undergraduates should also find the coursestimulating. Starting from the basics of coding theory and some of theclassic theorems (and challenges) of the subject, the course will moveto a subset of several modern (still actively researched) topics incode constructions and error-correction algorithms. Possible suchtopics include polar coding to achieve Shannon capacity; list decodingfor optimal recovery against worst-case errors; locally decodablecodes to correct errors very efficiently; graph based codes andefficient iterative decoders; algebraic-geometric codes; connectionsbetween coding theory and pseudorandomness; codes in distributedstorage (locally repairable codes/regenerating codes); codes forcombating synchronization errors; coding for interactivecommunication, etc. At the end of the course, the students should have a good grounding incoding theory and various approaches to construct good codes, and alsobe able to read, appreciate, and understand some of the currentresearch literature in the subject.

Lecture notes of the course "An Algorithmic Introduction to Coding Theory," by Madhu Sudan.Publication Date: 2001. The first chapter offers useful comments regarding several textbooks on coding theory.Available at

Instructor: Mary Wootters TA: Reyna Hulett When and where? T/Th 10:30-11:50am, Sapp Center for Science Teaching and Learning (STLC), Room 119. Course Description: Introduction to the theory of error correcting codes, emphasizing algebraic constructions and diverse applications throughout computer science and engineering. Topics include basic bounds on error correcting codes; Reed-Solomon and Reed-Muller codes; list-decoding, list-recovery and locality. Applications may include communication, storage, complexity theory, pseudorandomness, cryptography, streaming algorithms, group testing, and compressed sensing. Prerequisites: Linear algebra, basic probability (at the level of, say, CS109, CME106 or EE178) and "mathematical maturity" (students will be asked to write proofs). Familiarity with finite fields will be helpful but not required.

Please follow the instructions on the homework sets for doing and submitting your homework, and note the grading policies below. Homework: Homework 0: [problem set] Homework 1: [problem set, Solutions]. Due 1/25. Homework 2: [problem set, Solutions]. Due 2/8. Homework 3: [problem set, Solutions]. Due 2/22.Project: Final Project Guidelines Logistics Office hours: By appointment -- email mar...@stanford.edu. Grading: There will be three homework assignments (each 20% of the final grade) and a final project (40%). Textbooks/resources: There is no textbook, but we will occasionally refer to the in-progress textbook Essential Coding Theory, by Guruswami, Rudra and Sudan. Lecture notes and occasional readings will be posted in the schedule. Homework: Will be posted here. It is due either as a hard copy at the beginning of class or by email to marykw and rmhulett before class begins. Late homework will be docked by 20% of the points possible per day it is late up to a maximum of three days. Homework will not be accepted after three days. Do not wait to the last minute to start your homework!

The main prerequisites for this class are mathematical maturity, exposure to basic mathematical courses such as COMPSCI 240 and COMPSCI 250 and a solid grounding in linear algebra and probability theory. Students without such background can seek permissionof the instructor.

Coding Theory has been playing an important role in Theoretical Computer Science in topics such as probabilistically checkable proofs, list decoding and local testability. It has also applications in other areas of computer science such networking and security. This course will be useful to students interested in any of these areas and will expose them to a wide range of mathematical tools and techniques. The specific topics covered will include:

A group of two students will submit a single homework that will reflect the collaborative effort of that group of students. Assignments must be submitted at the beginning of the class on the deadline or by email or in Moodle. Late submission by a day (e-submission only) will incur a 20% penalty. Submissions will not be accepted if there is any more delay without substantial reason (such as a doctor's note).

A group of two students will scribe the notes for one (or two) lectures in TeX. Template for lecture notes will be provided. Scribed notes must be submitted by email to the instructor within 3 days of the lecture. Late submission by a day will incur a 20% penalty. Any more delay without a Doctor's note will incur full penalty.

Can anybody suggest to me good coding theory books? I've already taken a cryptography class last semester and I studied it with Handbook of Applied Cryptography by Alfred J. Menezes; I found it very useful. Is there a coding theory book like this with many examples?

A book I quite like that's more recent is R.M. Roth's Introduction to Coding Theory -- has a bit of a CS flavor to the approach. For engineering (esp. applications), I think Error correction coding by Moon is good.

It was a nice taste of single-error correcting codes and provided a strong foundation from which to build on. In addition, if you are looking for a book with many examples, this textbook has exercises at the end of every chapter and has answers to EVERY exercise in the back of the book.

Instructor: Luca Trevisan,luca@cs,615 Soda Hall, Tel. 642 8006Classes are Mondays-Wednesdays, 2:30-4:00pm, 405 SODAOffice hours: Tuesdays, 2-3pm or by appointment.Requirements: attendance scribing notes for two or more lectures final projectcourse descriptionError-correcting codes and relatedcombinatorial constructs play an important role is several recent (and old)results in complexity theory. In most cases, such as in the Goldreich-Levinhard-core predicate construction, the coding theory interpretation became clearonly in retrospect, but then it was essential for further improvements. Thiscourse will be about the theory, constructions, and algorithms for errorcorrecting codes, about applications in complexity theory and in cryptography,and about relations to other combinatorial constructions.

In the first part of the course we will see constructions of Reed-Solomon codes,Reed-Muller codes and Low-weight Parity Check Codes, along with theirunique-decoding and list-decoding algorithms. Then we will see "localdecoding" and "local checking" algorithms, and their applicationsto average-case complexity, cryptography, program testing, and probabilisticallycheckable proofs. In the third part of the course we will explore connectionsbetween error-correcting codes and the other three combinatorial objectsthat are ubiquitous in complexity theory: hash functions, randomnessextractors and expander graphs.

The theme addressed by these papers is combinatorial mathematics, as used in applications related to information security, cryptography and coding theory. Together they cover several topics subject to current research in the field. The volume will be of interest to mathematicians, computer scientists and engineers working in the area of digital communications, as well as to researchers and graduate students wishing to learn more about the application of combinatorial mathematics.

The tutorial style of the papers makes the book particularly suitable for use as an additional text for a course in discrete mathematics or applied combinatorics. It would similarly be of value for graduate courses in applied combinatorics with a focus on coding theory and cryptography.

Prerequisites : Math 417 Introduction to Abstract Algebra orequivalent, or consent of instructor Catalog description: We will start by covering the mathematical concepts needed to understand algebraic coding theory and the concepts of cyclic codes and in particular, Reed-Solomon codes. These will heavily focus on finite fields, combinatorics and number theory. In the second part of the course we will turn our attention to codes on graphs (LDPC codes), polar codes, codes for distributed storage, coded computing and learning and coding for synthetic biology (i.e., coding for DNA- and polymer-based data storage). Our treatment of these subjects will rely on some basic and some not-so-basic notions from combinatorics and graph theory, optimization and machine learning and rudimentary molecular biology.Due to time limitations we will not discuss convolutional codes. LECTURE NOTES (Scribed) Syllabus Hamming codes, linear codes, dual codes Scribed Lecture 1 Bounds on the size of codes MacWilliams identities Extended coverage of MacWilliams identities HW #1 Finite fields - basic treatment Finite fields - more advanced treatment Finite fields - more advanced treatment with examples HW #2 Moebius inversion formula Double error-correcting BCH codes Cyclic codes Decoding of RS codes: The PGZ algorithm Decoding of RS codes: Euclid's algorithm (McEliece notes) List decoding of RS codes: Sudan's algorithm Reed-Muller codes HW #3 Polar Codes I Polar Codes (Prof. Arikan's slides) Single-deletion-correcting codes (article by Prof. Sloan) DNA-Based Data Storage Basics String correlation and avoiding forbidden substrings Image processing in DNA DNA Storage Channels Lecture Notes: Lattice Theory Examples of Lattices Lattice Catalogue Maryna Viazovska's paper Coded String Reconstruction Shannon Channel: Joao Ribeiro's talk on Coded Trace Reconstruction HW #4 Project Instructions Prof. Atri Rudra's Tutorial on Group Testing Prof. Arya Mazumdar's Lecture Notes on Group Testing Tutorial on LDPC codes by Prof. Siegel Recommended Text I: The Theory of Error-Correcting Codes (Mac Williams and Sloane, a classic for algebraic coding theory). Recommended Text II: Algebraic Codes for Data Transmission (Blahut, an engineering-oriented approach to coding theory). Recommended Text III: Introduction to Coding Theory (Roth, contains a number of topics not covered in the above cited texts). Course Directors : Professor Olgica Milenkovic(mile...@illinois.edu) Further information

3a8082e126