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)