| Day | Topics | Preparation |
|---|---|---|
| Mon. 1/12 | Introduction. | . |
| Wed. 1/14 | Review of number theory. Intro to commutative rings. |
Notes Sec 2,3. |
| Wed. 1/21 | Polynomial rings. Polynomial rings over a field. |
Notes Sec. 3, 4. |
| Mon. 1/26 | Finite fields. | Sec. 4, 5. |
| Wed. 1/28 | Finite fields: Existence and uniqueness. | Sec. 5 |
| Mon. 2/2 | Coding for error correction. Reed-Solomon codes. |
RS Sec. 1, 2. |
| Wed. 2/4 | Ideals of polynomial rings.
Reed-Solomon codes as cyclic codes. |
RS Sec. 3 |
| Mon. 2/9 | Cyclic codes and systematic encoding.
Dual codes. |
RS Sec. 3 |
| Wed. 2/11 | Decoding, the error locator polynomial.
The syndrome as a map on the polynomial ring. |
RS Sec.4, 5. |
| Mon. 2/16 | Decoding: the Berlekamp-Massey algorithm. Error location. |
RS Sec. 5. |
| Wed. 2/18 | Cancelled for Uwe Bubeck's talk on ProverBox | . |
| Mon. 2/23 | Decoding: Peterson-Gorenstein-Zierler algorithm. Circuitry for polynomial and finite field computation. |
Blahut handout. |
| Wed. 2/25 | The syndrome polynomial and evaluator polynomial | RS Sec. 7 |
| Mon. 3/1 | Extended BM algorithm. An alternative method for error evaluation |
RS Sec. 8 |
| Wed. 3/3 | Berlekamp-Massey with computation of error evaluator
polynomial. A better error evaluation formula |
. |
| Mon. 3/8 | Convolutional codes | Hankerson 8.1 |
| Mon. 3/10 | Convolutional code: state diagrams | Hankerson 8.2 |
| Mon. 3/22 | Convolutional codes: Trellis representation. Error free decoding. |
Hankerson 8.3 |
| Mon. 3/24 | Viterbi algorithm. | Hankerson 8.4 |
| Wed. 3/26 | Probability, Bayes' theorem and decoding | . |
| Mon. 3/29 | The generalized distributive law. A decoding example | . |
| Mon. 4/5 | The generalised distributive law decoding on trees |
. |
| Wed. 4/7 | Local algorithms approximating the GDL | . |
| Mon. 4/12 | Constructions using groups | Margulis, Rosenthal-Vontobel. |
| Wed. 4/14 | Constructions using groups. Constructions using quasi-cyclic codes |
Margulis, Rosenthal-Vontobel. Fossorier and others. |
| Mon. 4/19 | Student presentations. | . |
| Wed. 4/21 | Shannon's noisy coding theorem. | . |
| Mon. 4/26 | . | . |
| Wed. 4/28 | . | . |
| Mon. 5/5 | Final presentations (two). | . |