0368.3072 Error
Correcting Codes
CS dept, Tel-Aviv University, Fall 2017
|
Syllabus (including
links and references)
|
Lecture Sunday, 14:00-17:00, Shenkar
(physics) 104 Instructor Amnon
Ta-Shma | Schreiber 127 | 5364 Open
for Undergrad
and grad students. Grading
policy 50% final exam, the
rest is exercises and based on participation in class. Our
forum is here. |
|
|
Textbooks
and links |
·
Venkatesan
Guruswami, Atri Rudra and Madhu Sudan – Essential
Coding Theory. ·
W. Cary
Huffman and Vera Pless – Fundamentals of Error Correcting Codes. ·
Ron M. Roth
– Introduction to Coding Theory. ·
Madhu Sudan
– Essential Coding theory lecture
notes. ·
Venkatesan
Guruswami – Introduction to Coding Theory lecture notes. |
|
Date |
Class Topic |
Lecture notes |
References |
|
Oct 22 |
Basic
definitions. Hamming and Hadamard codes. Reed-Solomon codes. Basic Algebra. |
See syllabus. |
|
|
Oct 29 |
Basic algebra.
Cyclic codes. |
See syllabus. |
|
|
Nov 5 |
The Hamming code
is cyclic. Reed-Muller codes. The Hermitian code. |
Lectures 1 and 2 |
See syllabus. |
|
Nov 12 |
Existence of good
codes. Concatenation – RS with Hadamard, nested concatenation. Naïve
decoding of concatenated codes. GMD decoding. The Justensen code. |
Lecture 3 |
See syllabus. |
|
Nov 19 |
The Justensen
code – cont. HW1 Review. The
Berlekamp-Welch algorithm for unique decoding of RS codes. |
|
See syllabus. |
|
Nov 26 |
The
Berlekamp-Welch algorithm – cont. List decoding. The punctured Hadamard
code is tight. Bounds on vectors in the Euclidean space. The binary
Johnson's bound. |
|
The Johnson's
bound proof roughly followed [G4] in the syllabus. |
|
Dec 3 |
Sudan's
list-decoding algorithm for RS codes. Hasse derivative. |
|
See syllabus. |
|
Dec 10 |
More properties
of Hasse derivative. Guruswami-Sudan's
list-decoding algorithm for RS codes. |
|
See syllabus. |
|
Dec 24 |
HW2 Review. The
Gilbert-Varshamov bound, Singleton bound, Plotkin bound. |
|
See syllabus. |
|
Dec 31 |
The Hamming bound,
the Elias-Bassalygo bound. Fourier analysis.
The LP Bound via Fourier analysis – started. |
|
|
|
Jan 7 |
The LP Bound via
Fourier analysis. |
|
|
|
Jan 14 |
Capacity of
list-decoding. Folded Reed-Solomon – started. |
|
|
|
Jan 21 |
|
|
|