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
Encoding/decoding
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
SOME EXTRA MATERIAl ON BLOCK DESIGNS:
Designs
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