Coding Theory



Math 525
Spring 2001
Meeting Mon. Wed. Fri. 11:00-11:50
Bus. Adm./Math Building #251
San Diego State University


Professor: Mike O'Sullivan
Web page: http://www.rohan.sdsu.edu/~mosulliv
Email: m.osullivan@math.sdsu.edu
Office: Bus. Adm./Math Building #217, ext. 594-6697
Office Hours: M,W,F 12-1, M,W 3:15-5
                             I will normally be in my office and available at other times,
                             but, for my sake, try to come by during office hours.

Text

Hankerson, Hoffman et al, Coding Theory and Cryptography: The Essentials 2nd edition, Marcel Dekker, 2000.

We will cover Chapters 1-4 on linear codes, perfect codes and cyclic codes. Then we will do as much as possible of Chapter 5, BCH codes, Chapter 6, Reed-Solomon codes, and Chapter 8, convolutional codes.

Schedule and Assignments

First Assignment: due Fri. Feb. 9.
Second Assignment: due Fri. Feb. 23.
Third Assignment: due Fri. Mar 9.
Fourth Assignment: due Fri. Mar 23.
Fifth Assignment: due Mon. Apr. 16.
Sixth Assignment: due Fri. Apr. 27.
Seventh Assignment: due Wed. May 9.
Eighth Assignment: due Wed. May 16.

Course Description

Error-correcting codes are ubiquitous in communications systems. They allow engineers to scrimp on other design variables like power utilization. The resulting degradation in the performance of the system is counterbalanced by the error-correcting code. Briefly, the code works by building in a bit of redundancy at the transmitting end and then using that redundancy at the receiving end to identify where errors occured in transmission and correct them. The goals of this course are to cover the fundamentals of coding theory and to explain 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.

Prerequisites

A good knowledge of linear algebra is required. We will use everything in Math 254 except eigenvalues and related topics.

Grading

You will be expected to read the book carefully and do all the exercises. Doing the the exercises as you read while 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.

The final exam will be between 35% and 40% of your grade. There will be a mix of homework assignments, quizes, and exams making up the remainder. The homework problems will be a bit harder than the exercises in the book and 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.

I will use my web page to communicate the reading/exercise assignments and to give details about homework assignments, quizes, exams, etc. and also to give other information and resources.

Other References

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).]