Error-correcting codes, finite fields, algebraic curves
[ambient page updated 27 Dec 13 10:10]
...
[ home ]
...
[ garrett@umn.edu ]
Course text
"The Mathematics of Coding: Information,
Compression, Error Correction, and Finite Fields" (formerly published
by Prentice-Hall).
(Just in case anyone wonders: My contract with the publisher states
that when they cease making the book available, upon my written
notice to them, the copyright reverts to me. As of Fall 2013, the
publisher's rep said the book is no longer available. I sent the rep
and the main office an email saying that I do reclaim the copyright.)
Lecture overheads from spring 2003
-
[ 21 Jan 2004:
first day of class stuff ]
... [ updated 26 Jan 04 17:17]
-
[ 26 Jan 2004:
review: sets, functions, counting ]
... [ updated 26 Jan 04 17:17]
-
[ 28 Jan 2004:
Probability, random variables, expected values ]
... [ updated 31 Jan 04 16:50]
-
[ 02 Feb 2004:
Expected values, generating function methods, conditional probability ]
... [ updated 03 Feb 04 11:52]
-
[ 04 Feb 2004:
self-information, entropy ]
... [ updated 07 Feb 04 14:31]
-
[ 09 Feb 2004:
prefix codes, Kraft-MacMillan, Shannon's noiseless coding, Huffman encoding ]
... [ updated 07 Feb 04 15:50]
-
[ 11 Feb 2004:
more on Huffman, noisy channels, check-bits ]
... [ updated 14 Feb 04 12:27]
-
[ 16 Feb 2004:
min-distance decoding, Hamming distance, information rate, noisy
coding thm ]
... [ updated 17 Feb 04 12:02]
-
[ 18 Feb 2004:
about the upcoming exam Wed Feb 18th
]
... [ updated 18 Feb 04 11:01]
-
[ 18-23 Feb 2004:
CRCs ]
... [ updated 02 Mar 04 16:46]
-
[ 02 Mar 2004:
CRCs, primitive polynomials, fast modular exponentiation
]
... [ updated 02 Mar 04 11:33]
-
[ 04 Mar 2004:
the integers
]
... [ updated 06 Mar 04 11:34]
-
[ 08 Mar 2004:
Sun-Ze's theorem, primitive roots mod primes
]
... [ updated 09 Mar 04 18:38]
-
[ 08 Mar 2004:
polynomial algebra, multiplicative inverses... Hamming bound for codes
]
... [ updated 13 Mar 04 14:13]
-
[ 22 Mar 2004:
Linear algebra, linear codes, Gilbert-Varshamov bound
]
... [ updated 20 Mar 04 15:06]
-
[ 24 Mar 2004:
about the upcoming Exam II, Wed March 31
]
... [ updated 23 Mar 04 15:48]
-
[ 24 Mar 2004:
row reduction and applications
]
... [ updated 23 Mar 04 15:47]
-
[ 26 Mar 2004:
Linear codes, generator matrices, check matrices, cyclic codes
]
... [ updated 10 Apr 04 11:02]
-
[ 05 Apr 2004:
More on linear and cyclic codes' descriptions
]
... [ updated 10 Apr 04 11:20]
-
[ 07 Apr 2004:
Linear algebra criterion for min dist, Proof of GV bound, Vandermonde determinants
]
... [ updated 10 Apr 04 11:33]
-
[ 12 Apr 2004:
Reed-Solomon codes, finite fields, primitive elements
]
... [ updated 13 Apr 04 18:11]
-
[ 14 Apr 2004:
Hamming codes, BCH codes
]
... [ updated 10 Apr 04 16:29]
-
[ 19 Apr 2004:
BCH codes, Frobenius automorphism
]
... [ updated 14 Apr 05 10:28]
-
[ 21 Apr 2004:
Counting irreducibles, counting primitives
]
... [ updated 16 May 16 13:23]
-
[ 26 Apr 2004:
Counting irreducibles, primitives, equations with prescribed roots,
irreducible binary quintics
]
... [ updated 05 May 04 15:11]
-
[ 28 Apr 2004:
Some proofs about finite fields, Frobenius, irreducibles
]
... [ updated 28 Apr 04 13:11]
Solutions:
[s01]
...[s02]
...[s03]
...[s04]
...[s05]
...[s06]
...[s07]
...[s08]
...[s09]
...[s10]
...[s11]
This course is an introduction to basic ideas of information theory,
compression, and error-correction. The necessary mathematics developed
along the way includes a bit of probability, number theory, and
abstract algebra. After a small introduction to probability and
information, Shannon's Noiseless Coding Theorem and the
Kraft-MacMillan inequality can be discussed, along with Huffman and
other efficient coding schemes. The larger part of the course starts
with Shannon's Noisy Coding Theorem, and aims at making good
error-correcting codes. The historical development of error-correcting
codes starts with Hamming codes, and looks at other linear codes such
as Reed-Solomon, Bose-Chaudhuri-Hocquengham, and Goppa
codes. Construction of codes (not to mention efficient
encoding/decoding algorithms) requires that we develop basic facts
about finite fields and linear algebra over them. We'll also look at
best-possible behavior of codes: Hamming (sphere-packing) bound,
Gilbert-Varshamov bound, Singleton bound, etc. If time permits, We'll give an
introduction to some very good codes, geometric Goppa codes, attached
to algebraic curves, to Turbo Codes, and other special topics.
Unless explicitly noted otherwise, everything here, work
by Paul Garrett, is licensed
under a Creative
Commons Attribution 3.0
Unported License.
...
[ garrett@umn.edu ]
The University of Minnesota explicitly requires that I
state that "The views and opinions expressed in this page are
strictly those of the page author. The contents of this page have not
been reviewed or approved by the University of Minnesota."