Math 406

Introduction to Coding Theory

Winter 2013

Instructor

Dr. Ernst Kani
Office: Jeffery Hall, Room 211
E-mail: kani@mast.queensu....
Telephone: 533-2435
Office hours: Mondays 10:30-11:20, Wednesdays 9:30-10:20, Thursdays 11:30-12:20

Lectures

Monday 9:30, Wednesday 8:30, Thursday 10:30
Jeffery 115

Pre/Corequisites

Basic algebraic methods, as seen in MATH 210 or 211 or 212 or 213 or 217.
Knowledge of linear algebra (at the level of MATH 112 or APSC 174) is a must.

Marking Scheme

Undergraduate students: Assignments 20%, Midterm 30%, Final exam 50%
Graduate students: Assignments 20%, Midterm 20%, Final exam 40%, Project 20%

The project for graduate students will consist of a written survey of research papers or implementation of some software.

Assignments

Due Thursdays at 10:30 (every second week)

Midterm Test

14 February 2013 at 10:30

Final Exam

24 April 2013, 9:00-11:00 (2 hours)

Textbooks

There is no required textbook for the course. However, the following books are recommended as references.

• R.M. Roth, Introduction to Coding Theory, Cambridge University Press, 2006.
• J.H. van Lint, Introduction to Coding Theory, GTM 86, Springer-Verlag, New York, 1982.

These books have been ordered by the Campus bookstore. A few chapters of the following text are also useful:

• W. Trappe, L. Washington, Introduction to Cryptography with Coding Theory, 2nd ed., Pearson, 2006.

Course Outline (Tentative) - see also Course Content 2013

• Introductory Concepts: Noisy channels, block codes, encoding and decoding, maximum-likelihood decoding, minimum-distance decoding, error detection and correction. Shannon's noisy-channel coding theorem.

• Linear codes: Minimum distance, generator and parity-check matrices, dual codes, standard array decoding, syndrome decoding. Repetition codes, Hamming codes.

• Bounds on Code Parameters: Hamming bound, Singleton bound, Gilbert-Varshamov bound, Plotkin bound. Using bounds to determine and design good codes for a given set of parameters.

• Basic Finite Field Theory: Definitions, prime fields, construction of prime power fields via irreducible polynomials, existence of primitive elements, minimal polynomials.

• Algebraic Codes: Bose-Choudhury-Hocquenghem (BCH) codes, Reed-Solomon codes, and alternant codes as instances of generalized Reed-Solomon (GRS) codes. Decoding algorithms for GRS codes. Applications of Reed-Solomon codes in digital communications and storage.

• Cyclic codes: Definition, characterization as ideals of polynomial rings. BCH codes viewed as cyclic codes.

• Other topics to be selected from, as time permits: List decoding of Reed-Solomon codes, Golay codes, Reed-Muller codes, Goppa codes and algebraic geometry codes, convolutional codes, turbo codes, expander codes, low-density parity-check (LDPC) codes.

Academic Integrity

Academic integrity is constituted by the five core fundamental values of honesty, trust, fairness, respect and responsibility (see www.academicintegrity.org). These values are central to the building, nurturing and sustaining of an academic community in which all members of the community will thrive. Adherence to the values expressed through academic integrity forms a foundation for the freedom of inquiry and exchange of ideas essential to the intellectual life of the University (see the Senate Report on Principles and Priorities).

Students are responsible for familiarizing themselves with the regulations concerning academic integrity and for ensuring that their assignments conform to the principles of academic integrity. Information on academic integrity is available in the Arts and Science Calendar (see Academic Regulation 1), on the Arts and Science website, and from the instructor of this course. Departures from academic integrity include plagiarism, use of unauthorized materials, facilitation, forgery and falsification, and are antithetical to the development of an academic community at Queen's. Given the seriousness of these matters, actions which contravene the regulation on academic integrity carry sanctions that can range from a warning or the loss of grades on an assignment to the failure of a course to a requirement to withdraw from the university.