Fall 2004

MWF 11:00-11:50

GMCS 307

San Diego State University

Other times: by appointment.

SCHEDULE |

First Assignment: due Fri. Sep. 10.

Second Assignment: due Wed. Sep 22.

Third Assignment: due Mon. Oct. 4.

Fourth Assignment: due Wed. Oct. 20.

Fifth Assignment: due Wed. Oct. 27.

Sixth Assignment: due Fri. Nov. 5.

Seventh Assignment: due Wed. Nov. 24.

Eighth Assignment: due Fri. Dec. 3.

Ninth Assignment: due Wed. Dec 8.

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:

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