0368.3072 Error
Correcting Codes
CS dept, TelAviv University, Fall 2017

Syllabus (including
links and references)
Lecture Sunday, 14:0017:00, Shenkar
(physics) 104 Instructor Amnon
TaShma  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. ReedSolomon codes. Basic Algebra. 
See syllabus. 

Oct 29 
Basic algebra.
Cyclic codes. 
See syllabus. 

Nov 5 
The Hamming code
is cyclic. ReedMuller 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
BerlekampWelch algorithm for unique decoding of RS codes. 

See syllabus. 
Nov 26 
The
BerlekampWelch 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
listdecoding algorithm for RS codes. Hasse derivative. 

See syllabus. 
Dec 10 
More properties
of Hasse derivative. GuruswamiSudan's
listdecoding algorithm for RS codes. 

See syllabus. 
Dec 24 
HW2 Review. The
GilbertVarshamov bound, Singleton bound, Plotkin bound. 

See syllabus. 
Dec 31 
The Hamming bound,
the EliasBassalygo bound. Fourier analysis.
The LP Bound via Fourier analysis – started. 


Jan 7 
The LP Bound via
Fourier analysis. 


Jan 14 
Capacity of
listdecoding. Folded ReedSolomon – started. 


Jan 21 


