Universitatea Babeş-Bolyai Cluj-Napoca                                     
Facultatea de Matematică şi Informatică
Ciclul de studii: Masterat
Domeniul: Informatica
Programul de studii: Matematică Computaţională (în limba maghiară)
Limba de predare: Engleză

SYLLABUS

I. General data
Code	Subject	
MML1012	Coding Theory	

Semester	Hours: C+S+L	Category	Status	
1	2+2+0	specialty	optional	

II. Full status faculty members
Name and	Scientific	Didactic	Chair	Type of activity	
surname	title	title		C	S	L	
MARCUS Andrei	Ph.D.	Prof.	Algebra	*	*		

Associated faculty members
Name and	Scientific	Institution	Type of	Type of activity	
surname	title		position	C	S	L	

III. Course objectives
This course is an introduction to the theory of error-correcting codes,with a focus on linear codes. It starts by introducing the necessaryalgebraic 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.	

IV. Course contents
Polynomials. Extensions of fields. Finite fields. Polynomials over finite fields. Factorization of polynomials over finite fields. Berlekamp's algorithm. Application of finite fields to cryptology. Basic concepts of coding theory. Linear codes. Cyclic codes. Special cyclic codes. BCH codes. Convolutional codes. GAP packages for coding theory computations.	

V. Bibliography
1.	S. Crivei, A. Marcus, C. Sacarea and Cs. Szanto,  Computational algebra with applications to coding theory and cryptography, EFES Cluj-Napoca, 2006, 198  pages (library)
2.	A. Marcus, Komputeralgebra (Hungarian), Cluj University Press, 2005, 150 pages (library)

VI. Thematic of didactic activities per weeks
Schedule of the courses and seminars 
WEEK 1.
1. Polynomials  (2 hours course + 2 hours seminar) [1, Chapter 3]
   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 [1, Chapter 4]
   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 [1, Chapter 5]
   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 [1, Chapter 7]
   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  [1, Chapter 8]
   5.1. The Chinese Remainder Theorem for polynomials
   5.2. Berlekamp's algorithm
WEEK 6.
   5.3. Application of finite fields to cryptology [1,  8.3]
        5.3.1. AES (Advanced Encryption Standard)
        5.3.2. The Diffie-Hellmann key exchange system
WEEK 7.
6. Coding theory
   6.1. Introduction [1,  9.1]
   6.2. Basic concepts  [1,  9.2]
WEEK 8.
   6.3. Linear codes  [1,  9.3]
        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 [1,  9.3.3]
WEEK 10.
        6.3.4. Hamming codes  [1,  9.3.4]
WEEK 11.
   6.4. Cyclic codes  [1,  9.4]
        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 [5]
WEEK 13.
   6.5. Convolutional codes [7]
WEEK 14.
   6.5. GAP packages for coding theory computations [8]

VII. Didactic methods used
Lectures, presentations, conversations, projects, exercises, individual study, homework assignments.

VIII. Assessment
The activity ends with a written final. The exam subjects have theoretical questions from all the studied topics, and one problem, among the problems studied at the course and the seminar. There is an evaluation of the overall seminar activity, and the documentations prepared for the programming projects will be evaluated. The final grade is the mean of the grades mentioned above. The final grade = Homeworks 50%. Written Exam 50%.	

IX. Additional 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	

Date,							                        Course responsible,
2008, October 4							Prof. MARCUS Andrei, Ph.D.

DECAN,                                                                                             SEF DE CATEDRA,
Prof.dr. Leon Tâmbulea                                                                  Conf. dr. Simion Breaz