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

Code	Subject	
MML1012	Coding Theory	

Section	Sem.	Hours: C+S+L	Category	Type	
Computational Mathematics - in Hungarian	1	2+1+0	speciality	compulsory	
Optimization of computational models- in Hungarian	1	2+1+0	speciality	compulsory	

Teaching Staff in Charge	Prof. MARCUS Andrei, Ph.D., marcus@math.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

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

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

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

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

6. Coding theory
   6.1. Introduction
   6.2. Basic concepts
   6.3. Linear codes
        6.3.1. The minimum distance of a linear code
        6.3.2. The dual of a linear code
        6.3.3. Decoding algorithm for linear codes
        6.3.4. Hamming codes
   6.4. Cyclic codes
        6.4.1. The dual of a cyclic code
        6.4.2. Decoding algorithm in cyclic codes
        6.4.3. Special cyclic codes. BCH codes
   6.5. Convolutional codes
   6.5. GAP packages for coding theory computations

	
Bibliography	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%.