Error-correcting codes, finite fields, algebraic curves
[ambient page updated 28 Nov 10 08:07]
...
[ home ]
...
[ garrett@math.umn.edu ]
No, I will not be teaching this course in 2004-05
Lecture overheads 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 24 Apr 04 12:52]
-
[ 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]
- No class Monday May 3 ... office hours 9:30-11:00 on Mon, May 3
... usual office hours 3:30-4:30 on Tues May 4 ... Midterm
III on Wed, May 5
Solutions:
[s01]
...[s02]
...[s03]
...[s04]
...[s05]
...[s06]
...[s07]
...[s08]
...[s09]
...[s10]
...[s11]
The text is my "The Mathematics of Coding: Information,
Compression, Error Correction, and Finite Fields" (published
by Prentice-Hall).
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.
Email is the best way to reach me!
garrett@ma
th.umn.edu
Office Vincent Hall 353 (north stairwell), phone (612)
624-5012. Phone messages at the math department at (612) 625-2004, but
email is best.
My office hours for this course are MW, 3:00-3:30
(before class) and 5:00-5:30pm (after class), as well as Tuesday
3:30-4:30, or by appointment. Send email anytime!
Grading: We'll have
weekly take-home quizzes (given out Monday, collected
two days later on Wednesday),
three 1.25-hour
in-class exams:
Wed Feb 25,
Wed Mar 31,
Wed May 05 ,
(NO final)
Each exam is a review of the earlier quizzes.
Of the course grade, each of the three midterms is 19%,
and the take-home quizzes are 43%.
There will also be occasional [ challenge
problems ] [updated 05 Apr 04 17:04]
intended to both afford some additional
entertainment at a higher mathematical level, and to potentially offer
some small reward by
varying amounts of extra credit. I will grade these
myself. The standards for coherence, succinctness, legibility, and
other aspects of presentation will be very high. That is, I won't even
try to read a proposed solution if it looks
garbagey. Usually no partial credit will be given. I will
not accept attempted solutions within the last two weeks of the
term. You may not work together on these problems.
| A | = | 93.00-100.0
| A- | = | 90.00-92.99
|
| B+ | = | 86.67-89.99
| B | = | 83.34-86.66
| B- | = | 80.00-83.33
|
| C+ | = | 76.67-79.99
| C | = | 73.34-76.66
| C- | = | 70.00-73.33
|
| D+ | = | 65.00-69.99
| D | = | 60.00-64.99
| | etc
|
When grading in the S/N system, an 'S' is equivalent to a 'C'
or better.
We will follow IT/CLA policies on incompletes,
scholastic misconduct, etc.
© 1996-2011, Creative Commons license,
This work
by Paul Garrett is licensed
under a Creative
Commons Attribution 3.0
Unported License.
...
[ garrett@math.umn.edu ]
[this page is http://www.math.umn.edu/~garrett/coding/]
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."