| SCHEDULE |
The goals of this course are to cover the fundamentals of coding theory and the most widely used error-correcting codes. The mathematics involved is essentially linear algebra over finite fields. We start with the simplest finite field F_2= {0,1} and look at the standard first examples: Hamming codes, Golay codes and Reed-Muller codes. We then look at cyclic codes, which entails studying polynomials over F_2. If you know some ring theory that will help, but I won't assume that students have taken Math 521. The codes used in most applications, Reed-Solomon and BCH codes, require us to work in extension fields of F_2, so we will spend some time developing that subject. I also hope to spend a week on a very different type of code that is also widely applied, convolutional codes.
You will be expected to read the book carefully and to do the exercises. Doing the exercises as you read will clarify the concepts and greatly help your understanding of the material. Many of the exercises are fairly routine, and the answers are in the book of the book.
There will be a mix of homework assignments, quizes, exams in addition to the final exam. The homework problems will be a bit harder than the exercises in the book. You should write up the results carefully, explaining your reasoning.
I typically assign letter grades using 85% and above is an A and dropping by 10 or 12 points for each lower grade.
| Weekly work | 350 |
| Tests | 300 |
| Final | 350 |
| Total | 1000 |
The Final Exam is
Mon. Dec. 13 10:30-12:30
R. Blahut Theory and Practice of Error Control Codes Addison Wesley 1983 [Good material on decoding algorithms, logical circuitry for finite field arithmetic and decoding.]
A. Dholakia, Introduction to Convolutional Codes with Applications, Kluwer, QA268 D48 a994. [Definitions, structure and classification of convolutional codes, several chapters on encoding/decoding, applications (automatic repeat-repeat request (ARQ), variable redundancy ARQ, asynchronous transfer mode (ATM) networks.]
R. Hill A First Course in Coding Theory, Oxford Applied Math and Computing Series, QA 268 H55 1986. [Main coding theory problem. Linear codes over finite fields, little decoding, Hamming codes , perfect codes, latin squares. Cyclic codes, weight enumerators, best parameters, MDS codes.]
H. Imai (ed.), Essentials of Error Control Coding Techniques, Academic Press, QA 268 E87 1990. [Engineers approach. Statements, no proofs of theorems. Block codes and convolutional codes, little on decoding. Several chapters on applications: design technique, communication systems, computer systems, audio visual systems.]
R. Johannesson, K. Zigangirov, Fundamentals of Convolutional Coding IEEE Series on Digital & Mobile Communication, IEEE Press, New York, TK5102.92 .J64 1999.
S. Lin, An Introduction to Error Correcting Codes, Prentice-Hall, TK 5102.5 L55, 1970. [Substantial book by an engineer, somewhat out of date. Linear codes over fields, binary cyclic, BCH and RS, majority logic decoding, convolutional codes, burst and random error correction.]
F. MacWilliams, N. Sloane, The Theory of Error-Correcting Codes North-Holland, Elsevier Science Publishers, QA 268 M33 1977. [The standard reference. ]
V. Pless, Introduction to the Theory of Error-Correcting Codes 3rd edition, Wiley-Interscience Series in Discrete Mathematics and Optimization, QA 268 P 55, 1998. [Nice introductory text. Cyclic codes, quadratic residue codes, BCH and RS codes, weight distributions, designs and games, uniqueness of codes.]
M. Purser, Introduction to Error Correcting Codes, Artech Publishing, TK 5102.9 P87, 1995. [Short and to the point, no exercises. Linear codes and bounds, including nonbinary. Cyclic codes, BCH codes, RS codes. Convolutional codes and trellises.]
S. Roman Introduction to Coding and Information Theory, Springer, QA268 R66 1997. [Part I on source coding, Huffman coding, entropy, the noiseless coding theorem. Part II, information theoretic approach to error control coding, statement of noisy coding theorem. Linear codes over finite fields, cyclic codes, some decoding, special codes (Hamming, Golay, Reed-Muller, latin squares).]