CODING THEORY (course for MSc in Applied Mathematics), Fall 2020/21

The course will be about error correcting codes. I will upload some
material and links here (you can also check the wikipedia articles):

Finite Fields

The field GF(64)

Finite vector spaces


Basic notions

Hamming codes

MDS codes

Perfect codes

Golay codes

GRS codes

Decoding linear codes

Decoding RS codes

Reed-Muller codes

RM codes, figures

Gilbert-Varshamov bound

Plotkin bound (simple version)

Cyclic codes

BCH codes

TOPICS FOR THE EXAM: 1. Finite fields (constructions, examples, the order of a finite field is a prime power, structure of the additive, multiplicative group. Field extensions, minimal polynomial) 2. Vector spaces over finite fields (description of subspaces, generator matrix, parity check matrix, number of subspaces) 3. Basic notions for codes (Hamming distance, block code, linear code, connection of the minimum distance and parity check matrix, e-error correcting codes) 4. Perfect codes, Hamming code (binary and non-binary Hamming codes, dual codes of binary Hamming codes, parameters determine perfectness, connection with designs) 5. Bounds for codes (Hamming bound, Singleton bound for linear and non-linear codes, Gilbert-Varshamov bound in different versions) 6. MDS codes (systematic codes, MDS codes, dual of an MDS code is MDS, non-trivial examples of MDS codes (Reed-Solomon)) 7. Generalized Reed-Solom codes of their duals (GRS codes are MDS, dual of a GRS code is a GRS, generator matrix, parity check matrix) 8. Decoding, decoding RS codes (syndromes, decoding with coset leaders, the algorithm for decoding RS codes) 9. Cyclic codes (definition, generator polynomial, generator matrix, parity check polynomial, parity check matrix, connection with ideals) 10. Golay codes (parameters, icosahedron construction, important properties of Golay codes, such as self-duality etc.) 11. Binary Reed-Muller codes (construction, dimension, minimum distance, dual codes of RM are RM, binary Hamming codes as RM codes) 12. BCH codes (subfield subcodes, parity check matrix, RS codes in polynomial setting, bound on the dimension and the BCH bound on the designed distance)

Tamas Szonyi
Last modified: Wed Aug 23 13:38:19 CEST 2017