0368.4145

Error correcting codes

Spring 2010.

Lecturer: Amnon Ta-Shma

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

1. participation in class,

2. exercises, and,

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

# 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

# [S08]

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

# Serge Lang

Algebra, 3rd edition, 2002

# Rudolf Lidl and Herald Niederreiter

Introduction to finite fields and their applications

# Henning Stichtenoth

Algebraic function fields and Codes. 1st edition. 1993

# Henning Stichtenoth

Algebraic function fields and Codes. 2nd edition 2008

# 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)