Babes-Bolyai University of Cluj-Napoca
Faculty of Mathematics and Computer Science
Study Cycle: Master

SUBJECT

Code
Subject
MA265 Coding Theory
Section
Semester
Hours: C+S+L
Category
Type
Optimization of computational models- in Hungarian
1
2+2+0
compulsory
Teaching Staff in Charge
Prof. MARCUS Andrei, Ph.D.,  marcusmath.ubbcluj.ro
Aims
This course is an introduction to the theory of error-correcting codes, with a focus on linear codes. It starts by introducing the necessary algebraic background, mainly concerning polynomials over finite fields, and various algorithms involving them. Homeworks include exercises of both practical and theoretical nature, and also writing computer programs.

Content
1. Polynomials
1.1. Preliminaries on polynomials
1.2. About evaluation of polynomials
1.2.1. Horner's scheme
1.2.2. The Cooley-Tukey method
1.3. Lagrange's Interpolation formula
1.4. The Discrete Fourier Transform
1.4.1. The Schoenhage-Strassen method for fast multiplication of integers

WEEK 2.
2. Extensions of fields
2.1. Finite and algebraic extensions
2.2. Simple extensions. Splitting fields
2.3. Multiple roots, separable polynomials
2.4. Adjunction of an element. Minimal polynomial

WEEK 3.
3. Finite fields
3.1. Construction of finite fields and basic properties
3.2. The discrete logarithm
3.3. Subfields of finite fields
3.4. The Silver-Pohlig-Hellman algorithm for discrete logarithms
3.5. An application of the Chinese Remainder Theorem: Fast adding of integers

WEEK 4.
4. Polynomials over finite fields
4.1. Cyclotomic polynomials
4.2. The Moebius Inversion Formula
4.3. Irreducible polynomials
4.4. The computation of minimal polynomials
4.5. The number of irreducible polynomials
4.6. The order of a polynomial. Primitive polynomials
4.6.1. Primitive polynomials
4.6.2. Methods of determining primitive polynomials

WEEK 5.
5. Factorization of polynomials over finite fields
5.1. The Chinese Remainder Theorem for polynomials
5.2. Berlekamp's algorithm
WEEK 6.
5.3. Application of finite fields to cryptology
5.3.1. AES (Advanced Encryption Standard)
5.3.2. The Diffie-Hellmann key exchange system

WEEK 7.
6. Coding theory
6.1. Introduction
6.2. Basic concepts
WEEK 8.
6.3. Linear codes
6.3.1. The minimum distance of a linear code
6.3.2. The dual of a linear code
WEEK 9.
6.3.3. Decoding algorithm for linear codes
WEEK 10.
6.3.4. Hamming codes
WEEK 11.
6.4. Cyclic codes
6.4.1. The dual of a cyclic code
6.4.2. Decoding algorithm in cyclic codes
WEEK 12.
6.4.3. Special cyclic codes. BCH codes
WEEK 13.
6.5. Convolutional codes
WEEK 14.
6.5. GAP packages for coding theory computations
References
1. Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to Algorithms. MIT 1990.

2. Knuth, D.E.: The Art of Computer Programming. Addison Wesley Longman 1998.

3. Koblitz, N.: Introduction to Number Theory and Cryptography. Springer-Verlag New York 1987.

4. Lidl, R., Niederreiter, H.: Introduction to Finite Fields and Their Applications. Cambridge University Press 1994.

5. Lidl, R., Pilz, G.: Applied Abstract Algebra. 2nd edition. Springer-Verlag New York 1998.

6. Marcus, A.: Algebra. Notes (in Hungarian) available at http://math.ubbcluj.ro/~marcus.

7. van Lint, J.H.: Introduction to Coding Theory. Springer-Verlag New York 1992.

8. The GAP Group: GAP -- Groups, Algorithms, and Programming. Version 4.4.3. http://www.gap-system.org

9. Wicker S., Kim S.: Fundamentals of codes, graphs and iterative decoding Kluwer, 2002

Assessment
Homeworks 50%. Written Exam 50%.
Links: Syllabus for all subjects
Romanian version for this subject
Rtf format for this subject