0368.4145

Error correcting codes

Spring 2010.

Lecturer: Amnon Ta-Shma

When and where: Thursdays, 10:10-13:00. Location: Dan David 204.

Grading: Based on

1. participation in class,

2. exercises, and,

3. an exam for B.Sc. students, a project for the rest.

Exercise list

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 http://www-math.mit.edu/~spielman/PAPERS/expandersIT.pdf http://portal.acm.org/citation.cfm?id=510003
	The Minimum Distance of Turbo-Like Codes	http://math.mit.edu/~spielman/Research/mindist.html

Lecture notes:

[S]	Madhu Sudan	Course notes on coding theory pdf
[S08]	Madhu Sudan	Essential Coding Theory 2008
	Luca trevisan	Coding Theory and Complexity
	Venkatesan Guruswami	Error-Correcting Codes: Constructions and Algorithms
	Atri Rudra	Error Correcting Codes: Combinatorics, Algorithms and Applications
	Oded Regev	Coding Theory

Books (Algebra+AG):

[L]	Serge Lang	Algebra, 3rd edition, 2002
[LN]	Rudolf Lidl and Herald Niederreiter	Introduction to finite fields and their applications
[St93]	Henning Stichtenoth	Algebraic function fields and Codes. 1st edition. 1993
[St08]	Henning Stichtenoth	Algebraic function fields and Codes. 2nd edition 2008
[GS]	Arnaldo Garcia Henning Stichtenoth	Topics in Geometry, Coding Theory and Cryptography, Chapter 1.

Outline:

Part I: The basics. Stochastic noise (Shannon theory) vs. adversarial noise. Distance and rate. Linear codes, the generating and parity check matrices. Examples: Hamming, Reed-Solomon, Reed-Muller, Hadamard. Efficient encoding and decoding.

Part II: The behavior of distance vs. rate. The Gilbert-Varashimov bound, the Singleton bound, the Hamming bound. The Plotkin bound.  Asymptotically good codes. RS+HAD. Justensen. The Fourier transform. Epsilon-biased distributions. The Naor-Naor construction. The Hermitian code+HAD.

Part III: List decoding. The Johnson's bound. List decoding RS codes. List decoding Hadamard codes. List decoding Reed-Muller codes. Random Self reducibility. Parvaresh-Vardy and folded RS codes. The GUV condenser.

Part IV: Local decoding. 2-local decoding Hadamard. A lower bound. Efremenko's codes.

Lectures:

Date	Lecture notes in Hebrew by Kiril Solovey and Yuval Pinter	Topic
(1) 25.2.10	Lecture 1 by Kiril Solovey and Yuval Pinter	Codes, distance (S 2:15-18) The Gilbert Bound (S 5:48-49) Linear codes (S 3:27-29) Hamming code and the Hamming bound (S 3:30-32) The Varashamov bound (S 5:46-50)
(2) 4.3.10	Lecture 2 by Kiril Solovey and Yuval Pinter	The Singleton bound (S 4:33), Reed-Solomon codes (S 4:34-35), Reed-Muller codes (S 4:37-38), Hadamard (S 4:38) Wozencrfat collection of codes (S 6:52-53) 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:69-71)
(3) 11.3.10	Lecture 3 by Kiril Solovey and Yuval Pinter	List decoding (S 8:72, def 8.8) The Johnson's bound (S 8:73). The Elias-Bassalygo bound The plotkyn bound (S 8:72-73) Some Algebra (S sec 2.4-2.7 : 19-24, sec 13.3.2 13:123-124), finite fields (LN 2.1: 44-48). Recommended reading: (LN Chapters 1+2).
(4) 18.3.10	Lecture 4 by Kiril Solovey and Yuval Pinter	BCH codes (S 40-44) Unique decoding RS codes (S 10.3:91-94) Decoding concatenated codes I (S 11.2:101-105)
(5) 8.4.10	Lecture 5 by Kiril Solovey and Yuval Pinter	Decoding concatenated codes II (S 11.2:101-105) Tight bounds on the rate vs the list decoding radius for binary and non-binary codes. (S08 Lecture 12) A list decoding algorithm for RS. (S 12.3:111-118)
(6) 15.4.10	Lecture 6 by Kiril Solovey and Yuval Pinter	Multiplicites ( DKSS09 , Section 2 ) An improved list decoding algorithm for RS using multiplicities. (S 13.2:118-122)
(7) 22.4.10	Lecture 7 by Kiril Solovey and Yuval Pinter	Parversh-Vardy codes (S08 Lectures 15-16.1-2)
(8) 29.4.10	Lecture 8 by Kiril Solovey and Yuval Pinter	Guruswami-Rudra codes (S08 Lectures 15-16.3)
(9) 6.5.10	Lecture 9 by Kiril Solovey and Yuval Pinter	Lossless condensers; The GUV lossless condensers ( GUV08 ) Mergers; The Dvir-Wigderson mergers ( DW08 , DKSS09 , Section 2 )
(10) 13.5.10	Lecture 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:64-66) Eps-balanced 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	Lecture 11 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	Lecture 12 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. Towers (GS, page 13), The tower T3 (GS, Sec 4.3)
(13) 3.6.10	Lecture 13 by Kiril Solovey and Yuval Pinter	The analysis of the ramification locus and splitting locus of the tower T3 (GS, pages 20-23 + 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 Riemann-Roch theorem (St08, Thm I.5.17). The genus (St08, Def I.4.15).
(14) 10.6.10	Lecture 14 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 Gilbert-Varashamov bound (GS, pages 16-23). The limits of the method – The Drinfeld-Vladut bound (GS, Thm 2.5)