0368.3072 Error Correcting Codes

CS dept, Tel-Aviv University, Fall 2017


We meet at Shenkar 104.


Syllabus (including links and references)


The exercise pool (HW3 is due December 31)




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.





Class Topic

Lecture notes


Oct 22

Basic definitions. Hamming and Hadamard codes. Reed-Solomon codes. Basic Algebra.

Lecture 1

See syllabus.

Oct 29

Basic algebra. Cyclic codes.

Lecture 2

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


Justesen code

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.

LP Bound


Jan 7

The LP Bound via Fourier analysis.



Jan 14

Capacity of list-decoding. Folded Reed-Solomon started.



Jan 21