The remaining 7 assignments will be discussed in class on Mondays.

Homework assignments will be posted here and handed out in class on Mondays or Tuesdays.

Solutions to the assignments will be discussed in class on Mondays. Written solutions will be provided only for the marked assignments.

For undergraduate students: Homeworks 40%, Presented assignments 10%, Final exam 50%
For graduate students: Homeworks 32%, Presented assignments 8%, Final exam 40%, Project 20%

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

Queen’s Official Grade Conversion Scale will be used.

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.

• 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.

• R.M. Roth, Introduction to Coding Theory, Cambridge University Press, 2006. This book most closely follows the spirit and topics of our course. Check the campus bookstore for availability. A number of copies have been ordered and should be coming in. One copy is available from the Douglas Engineering & Science Library.

There are a very large number of other books on coding theory that can also be used as reference material. Some of them are listed below in alphabetical order. Many of the listed books have been put on course reserve (24-hour loan) at the Douglas Engineering & Science Library.

• E.R. Berlekamp, Algebraic coding theory, McGraw-Hill, 1968. Revised edition published by Aegean Park Press in 1984.

• J. Bierbrauer, Introduction to Coding Theory, Chapman & Hall, 2005.

• R.E. Blahut, Algebraic Codes for Data Transmission, Cambridge University Press, 2002. (This is an updated version of the original classic, now out of print, Theory and Practice of Error-Control Codes, Addison-Wesley, 1983.)

• W.C. Huffman and V. Pless, Fundamentals of Error Correcting Codes, Cambridge University Press, 2003. (A good book from which to learn the basics. Written at an undergraduate level, assuming only knowledge of linear algebra.) This book can be accessed online, but you must log in through the book's entry in the Queen's Library's QCAT database.

• S. Lin and D.J. Costello, Error Control Coding (2nd edition), Prentice-Hall, 2004. (A good introduction from the engineering perspective.)

• F.J. MacWilliams and N.J.A. Sloane, The Theory of Error-Correcting Codes, Elsevier/North-Holland, 1977. (All you wanted to know about coding theory but were afraid to ask. An encyclopaedic reference.)

• R.J. McEliece, Theory of Information and Coding (2nd edition), Cambridge University Press, 2002. (A concise and well-written introduction to information and coding theory.)

• Vera Pless, Introduction to the Theory of Error-Correcting Codes (3rd edition), Wiley-Interscience, 1998. (A classic undergraduate text.)

• J.H. van Lint, Introduction to Coding Theory (3rd edition), Springer-Verlag (Graduate Texts in Mathematics), 1999. (Not really the most accessible introduction to the subject, but if you are comfortable with elementary abstract algebra and combinatorics, then it's a great book to read. Written for advanced undergraduates and graduate students in mathematics.)

• Online lecture notes on coding theory, prepared and maintained by Prof. Jonathan I. Hall. [Link provided with the permission of Prof. Hall.]