A Course in Algebraic Error-Correcting Codes

by Simeon Ball

This is a series of 13 videos which were lectures given as part of the Applied Mathematics and Mathematical Engineering Masters course of the Universitat Politècnica de Catalunya run by the Facultat de Matemàtiques in the spring term of 2020.

The reference book used for the main part of the course is A Course in Algebraic Error-Correcting Codes which was published by Springer-Birkhuaser as part the Compact Textbooks in Mathematics book series in May 2020. The book includes over a hundred exercises which are useful for assimilating the material, as well as chapters on Algebraic geometric codes, Reed-Muller and Kerdock codes and p-adic codes, which are not covered by these lectures.

Other references include Information and Coding Theory by Jones and Jones, which covers the first few classes on Information Theory, and Quantum Computation and Quantum Information by Nielsen and Chuang, which covers most of the last two lectures on quantum error-correcting codes.

Class 1 : Memoryless sources, uniquely decodable codes, Kraft's and McMillan's inequalities.

Class 2 : Optimal codes, Huffman codes, information and entropy, Shannon-Fano code.

Class 3 : Noiseless coding theorem, information channels, system entropies and mutual information.

Class 4 : Shannon's theorem.

Class 5 (1) (2): Block codes, Gilbert-Varshamov bound, sphere-packing bound, Plotkin lemma and Ploktin bound, asymptotically good codes.

Class 6 : Linear codes, dual code, syndrome decoding, MacWilliams identities, designs.

Class 7 : Assmus-Mattson theorem, linear codes and points sets in projective spaces, Griesmer bound, factorising cyclotomic polynomials over finite fields.

Class 8 : Cyclic codes, quadratic residue codes, BCH codes, Golay codes.

Class 9 : Maximum Distance Separable codes (MDS codes), Reed-Solomon codes, fast decoding and list decoding algorithms for Reed-Solomon codes, MDS conjecture.

Class 10 : MDS codes, Segre's theorem, subfield subcode, alternant codes.

Class 11 : Low density parity check codes (LDPC codes), expanders, polynomial time decoding for LDPC codes.

Class 12 : Quantum teleportation, Hilbert spaces, qu-bits, unitary and Hermitian maps, measurements, Pauli matrices.

Class 13 : Quantum error-correcting codes, stabiliser codes, syndrome decoding, qu-bit stabiliser codes as binary linear codes.

Updated 28 May 2020