LECTURE |
TOPIC |
DESCRIPTION |
1. |
Error correcting Linear codes |
Definition of a linear code, length and dimension, parity check matrix, generator matrix, examples of linear codes, equivalent codes, dual codes |
2. |
Decoding of a linear code |
Hamming distance, Hamming weight, minimum distance of a code, nearest neighbor decoding, standard array, syndrome decoding, examples, decoding error, perfect and quasi-perfect codes, single error correcting Hamming code |
3. |
Bounds on linear codes |
Hamming sphere-packing bound, Singleton bound, Gilbert-Vershamov bound |
4. |
Construction of new codes from old |
Extending, puncturing, expurgating, augmention, lengthening, shortening, examples, u|v construction, u|u+v construction |
5. |
Reed-Muller (RM) codes |
Inductive definition, examples, length, dimension and minimum distance of a RM code, definition of RM codes from Boolean function |
6. |
Binary double-error correcting BCH codes |
Parity check matrix, decoding procedure, Galois field GF(p^n) construction with examples - polynomial representation, power representation and vector representation of Galois field element, addition, multiplication, finding inverse and square roots |
7. |
Cyclic codes |
Definition of cyclic codes, principal ideal, generator polynomial, properties of cyclic codes, generator matrix, parity check matrix, examples, dual of a cyclic code, zeros and non-zeros of a cyclic code |
8. |
Minimal polynomial of an element of GF(p^n) |
Definition, properties, examples, cyclotomic cosets modulo p^n-1, determining minimal polynomial of an element of GF(p^n) |
9. |
Splitting field GF(q^m) of x^n-1 where m is the multiplicative order of q modulo n |
Determining m using cyclotomic cosets modulo n, factoring x^n-1 over the splitting field GF(q^m), factoring x^n-1 over the base field GF(q) |
10. |
BCH codes |
BCH bound, generator polynomial of binary Hamming code and BCH code, BCH code of designated distance, examples, narrow sense BCH code, primitive and non-primitive BCH code, nested BCH code, Bose distance, perfect tripple error correcting Goley code |
11. |
Reed-Solomon (RS) codes |
Definition, properties, examples, extended RS codes, mapping GF(2^n) codes into binary codes, examples, contruction of Justesen codes |
12. |
Goppa code |
Definition, Goppa polynomial, properties |
13. |
Maximal distance seperable (MDS) codes |
Generator and parity check matrices of MDS codes, dual of MDS codes, examples |
14. |
The Mattson-Solomon (MS) polynomials |
Definition, examples, properties of MS plynomials, inversion formula, relation between locator polynomial and evaluator polynomial, Newton’s identities to find error locator polynomial, decoding of binary BCH codes, generalized Newton’s identities and linear feedback shift register (LFSR), the Berlekamp algorithm to find LFSR of shortest length, decoding of non-binary BCH codes |
15. |
Non-linear codes |
Definition, equivalent codes, weight distribution, distance distribution, the Plotkin bound, Hadamard matrix - Sylvester type and Paley type, quadratic residues and Legendre symbol, examples, Hadamard codes, Conference matrix, Conference codes, examples, Levensthein theorem, |
16. |
designs |
t-designs, Steiner system, projective plane of order n, affine plane of order n, balanced incomplete block design (BIBD), properties of t-designs, block intersection number, Pascal property, complementary design, costruction of codes from Steiner system, construction of designs from codewords of fixed weight from a code, examples, properties |
17. |
Golay code |
Extended Golay code, properties, Steiner system from octads, t-designs from dodecads, unextended perfect triple error correcting Golay code |
18. |
Dual codes and their weight distribution |
Weight enumerator of a code, examples, MacWilliams theorem for binary linear codes, Hadamard transform/Walsh transform/discrete Fourier transform, examples, Krawtchouk polynomial, moments of weight distribution, power moments of weight distribution |
19. |
Group algebra (QG) |
Definition, addition, multiplication in QG, examples, character, MacWilliams transform, MacWilliams theorem for non-linear codes |
·
Week 1: Lecture 1-5:
Lecture Note
·
Week 2: Lecture 6-10:
Lecture Note
·
Week 3: Lecture 11-13:
Lecture Note
·
Week 4: Lecture 14:
Lecture Note
·
Week 5: Lecture 15:
Lecture Note
·
Week 6: Lecture 16: Lecture Note
·
Week 7: Lecture 17: Lecture Note
·
Week 8: Lecture 18-19: Lecture Note