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.

 

 

 

Date

Class Topic

Lecture notes

References

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.

Nov 3

Sudan's list-decoding algorithm for RS codes.

Hasse derivative.

 

See syllabus.