## "Babes-Bolyai" University of Cluj-Napoca Faculty of Mathematics and Computer Science

 Coding Theorys
 Code Semes-ter Hours: C+S+L Type Section MA265 2 2+2+0 compulsory Optimizarea modelelor informatice - în limba magh.
 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