0368.4145
Error correcting codes
Spring 2010.
Lecturer: Amnon TaShma
When and where: Thursdays, 10:1013:00. Location: Dan David 204.
Grading: Based on
participation in class,
exercises, and,
an exam for B.Sc. students, a project for the rest.
Wiki  Please add / change / update the articles
Reading projects:
Yaniv Hadar 
Local list decoding Hadamard 

Yakov Matsri 
Error correcting codes from expander graphs 
http://math.mit.edu/~spielman/Research/IMA.html 




The Minimum Distance of TurboLike Codes 
http://math.mit.edu/~spielman/Research/mindist.html 






[S] 
Madhu Sudan 

[S08] 
Madhu Sudan 


Luca trevisan 


ErrorCorrecting Codes: Constructions and Algorithms 


Error Correcting Codes: Combinatorics, Algorithms and Applications 


[L] 
Serge Lang 

[LN] 
Rudolf Lidl and Herald Niederreiter 

[St93] 
Henning Stichtenoth 

[St08] 
Henning Stichtenoth 

[GS] 
Arnaldo GarciaHenning Stichtenoth

Topics in Geometry, Coding Theory and Cryptography, Chapter 1. 
Part I: The basics. Stochastic noise (Shannon theory) vs. adversarial noise. Distance and rate. Linear codes, the generating and parity check matrices. Examples: Hamming, ReedSolomon, ReedMuller, Hadamard. Efficient encoding and decoding.
Part II: The behavior of distance vs. rate. The GilbertVarashimov bound, the Singleton bound, the Hamming bound. The Plotkin bound. Asymptotically good codes. RS+HAD. Justensen. The Fourier transform. Epsilonbiased distributions. The NaorNaor construction. The Hermitian code+HAD.
Part III: List decoding. The Johnson's bound. List decoding RS codes. List decoding Hadamard codes. List decoding ReedMuller codes. Random Self reducibility. ParvareshVardy and folded RS codes. The GUV condenser.
Part
IV: Local decoding. 2local decoding
Hadamard. A lower bound. Efremenko's codes.
Date 
Lecture notes in Hebrew by Kiril Solovey and Yuval Pinter 
Topic 
(1) 25.2.10

by Kiril Solovey and Yuval Pinter 
Codes, distance (S 2:1518) The Gilbert Bound (S 5:4849) Linear codes (S 3:2729) Hamming code and the Hamming bound (S 3:3032) The Varashamov bound (S 5:4650) 
(2) 4.3.10

by Kiril Solovey and Yuval Pinter 
The Singleton bound (S 4:33), ReedSolomon codes (S 4:3435), ReedMuller codes (S 4:3738), Hadamard (S 4:38) Wozencrfat collection of codes (S 6:5253) Concatenation (S 6:56). RS+OPT, the Zyablov bound (S 6:57). RS+RS+OPT. Justensen: RS+Wozencraft (S 6:59) The plotkyn bound (S 8:6971) 
(3) 11.3.10 
by Kiril Solovey and Yuval Pinter 
List decoding (S 8:72, def 8.8) The Johnson's bound (S 8:73). The EliasBassalygo bound The plotkyn bound (S 8:7273) Some Algebra (S sec 2.42.7 : 1924, sec 13.3.2 13:123124), finite fields (LN 2.1: 4448). Recommended reading: (LN Chapters 1+2). 
(4) 18.3.10

by Kiril Solovey and Yuval Pinter 
BCH codes (S 4044) Unique decoding RS codes (S 10.3:9194) Decoding concatenated codes I (S 11.2:101105) 
(5) 8.4.10 
by Kiril Solovey and Yuval Pinter 
Decoding concatenated codes II (S 11.2:101105) Tight bounds on the rate vs the list decoding radius for binary and nonbinary codes. (S08 Lecture 12) A list decoding algorithm for RS. (S 12.3:111118)

(6) 15.4.10 
by Kiril Solovey and Yuval Pinter 
Multiplicites ( DKSS09 , Section 2 ) An improved list decoding algorithm for RS using multiplicities. (S 13.2:118122)

(7) 22.4.10

by Kiril Solovey and Yuval Pinter 
ParvershVardy codes (S08 Lectures 1516.12)

(8) 29.4.10 
by Kiril Solovey and Yuval Pinter 
GuruswamiRudra codes (S08 Lectures 1516.3) 
(9) 6.5.10 
by Kiril Solovey and Yuval Pinter 
Lossless condensers; The GUV lossless condensers ( GUV08 ) Mergers; The DvirWigderson mergers ( DW08 , DKSS09 , Section 2 ) 
(10) 13.5.10 
by Kiril Solovey and Yuval Pinter 
Introduction to AG codes. Bezout theorem. An example: [19,9,10]_13 and [19,6,13]_13 codes. (S 7:6466) Epsbalanced codes. A construction using the Hermitian curve and Beziut's theorem. Some more algebra: Commutative rings, Integral domain, Unique factorization domain, principal ideal domain, Euclidean rings and fields. Polynomials in one and more variables. (L, chapter II, IV.2). Irreducible vs. Prime elements. 
(11) 20.5.10 
by Kiril Solovey and Yuval Pinter 
Ideals in commutative rings. Algebraic function field. Valuation rings, places, primes, valuations. (St08, I.1) The rational function field. (St08, I.2) 
(12) 27.5.10

by Kiril Solovey and Yuval Pinter 
The number of zeroes and poles of an element in the function field (St08, Thm I.4.11). Algebraic extensions of function fields: extensions and restrictions of places, ramification index, relative degree (St08, III.1), the fundamental equality. (St08, Thm III.1.11). Integral extensions (St08, Thm III.3.7). Kummer extensions (St08, Thm III.7.3). The Hermitian function field. 
(13) 3.6.10 
by Kiril Solovey and Yuval Pinter 
The analysis of the ramification locus and splitting locus of the tower T3 (GS, pages 2023 + Sec 4.3 + Abhyankar's lemma (GS, Thm 2.11)) Riemann spaces (St08, Def I.4.4). Algebraic geometric codes (St08, Sec II.2). The RiemannRoch theorem (St08, Thm I.5.17). The genus (St08, Def I.4.15). 
(14) 10.6.10 
by Kiril Solovey and Yuval Pinter 
Hurwitz Genus formula (St08, Def III.4.12). The tower T3 gives a code over F_49 that beats the GilbertVarashamov bound (GS, pages 1623). The limits of the method – The DrinfeldVladut bound (GS, Thm 2.5) 