Math 5251: Error-correcting codes, finite fields, algebraic curves
Spring 2012: Professor Andrew Odlyzko
Classes: MW 4:00 - 5:15, in MechE 102 and on UNITE
Office Vincent Hall 511
Office hours: M 3:00 - 4:00, W 5:30 - 7:00, and by appointment. However, always check this web page
before coming over, as on some days the hours may be changed.
Office hours of the grader, Kyle Johnson, email@example.com: Tuesday 1:10 - 2:10, in the
grad student lounge in Vincent 502.
Textbook: "The Mathematics of Coding: Information,
Compression, Error Correction, and Finite Fields" by Paul Garrett, available
in the Campus Bookstore. (This book has not been revised recently, so used copies
will do just fine.) Please note that some corrections are available at
Additional material: Web page from 2003 version of the course, with lecture
overheads, etc. at Paul Garrett's home page.
You might also find useful two books that are available
freely (and legally) online,
A Computational Introduction to Number Theory and Algebra, and
Notes on Coding Theory.
Computer algebra systems (very helpful, but not essential and not required): Maple, Mathematica,
available in Math computer labs, and also (for CSE undergrads) for free downloads at
CSE Labs. One can also do well with the freely
available Web-based Wolfram Alpha, or other systems.
Exams: No final, three 75-minute in-class exams on Wed Feb 15, Wed Mar 28, and Wed May 2.
These will all be held in MechE 212, upstairs from the regular classroom.
Weekly homework assignments (usually), due (usually) on Wednesdays, first one due Jan 26.
Always due at the beginning of a class, late homeworks will not be accepted.
If you can't make it to class, you can leave your homework in
my mailbox in Vincent 107, or email it to me (in either typeset or scanned form, in either
case PDF is preferred).
- phone 612-625-5413
- email: firstname.lastname@example.org (preferred and most reliable method)
Special challenge problems: There will be occasional challenge problems for extra credit.
These you can only work on by yourself.
- You may work with others on homework
problems, but you have to write up your solution yourself, in your own words, to show you
understand the solution.
Exams will be open book: you may bring books, notes, and calculators, but no smart
phones, iPads, or other communication devices can be used, and you have to do all the work
Term project: due Mon May 7, by 11:00 am either via email (PDF format strongly preferred) or in my mail box in Vincent 107.
Each of these problems will be worth some number of points towards the
homework score (with fractional credit for partial solutions).
Suppose that the maximal score on all the regular homeworks is x, and you get y points
on those regular homeworks and z on the extra credit ones. Then your final homework score will be
the max of x and y+z.
Grades: homework will count for 35%, term project for 15%, the three exams for 15%, 15%, and 20%, respectively.
Scholastic Conduct: Cheating or other misconduct will not be tolerated. The standard University
policies will be followed.
Expected effort: This is a 4-credit course, so you are expected to devote 12 hours per week,
on average (including lectures).
Solution files for homeworks and midterms are provided for your personal use only. Do not
distribute them via email or posting anyplace.
How can music CDs that have been scratched still produce perfect music? How do spacecraft out past Saturn communicate with Earth? And how do high quality movies fit on DCDs? All these depend on some pretty mathematics that is not too complicated and can be learned with minimal prerequisites, given the willingness to pick up some abstract algebraic, combinatorial, and probabilistic concepts.
- Flexible format, could be done individually or in groups of up to 3.
To encourage collaborative efforts, the maximal score on an individual term paper
will be 80 (as compared to 100 in general), except for UNITE students.
Expected length 5 to 10 pages, less for an individual effort, more for a group.
to be coordinated with me, typically literature searches on methods used for error-correction
or compression in various settings, with requirement to explain how the material of this course
is (or, often, is not) relevant there. Presentation should be clear, but relatively little weight will
be placed on spelling, grammar, and the like, as this is not a writing-intensive course.
References should be given, with preference to the peer-reviewed literature. Online
references are fine to some extent, with Wikipedia on the borderline, but in all such
cases give the complete URL and data material was downloaded.
Historical material is welcome, but should not dominate, as the point
is to learn some new technical matter, even if not to a great depth.
- A good approach might be to think of the paper as something meant for your
fellow students in the class, teaching them something that was not covered in
the course, and doing it in a way that will be understandable based on course
- I will be happy to provide rough feedback on early drafts that are submitted (preferably
in PDF) by 11 am on Fri May 4.
This course develops basic ideas of information theory,
compression, and error-correction. It does not present a comprehensive
coverage of these topics. Instead, the stress is on basic concepts that
have cohesive mathematical foundations.
Due Wed Jan 25:
Problem 0 (10 pts): compute gcd(15,35), gcd(12,18), lcm(15,35), lcm(12,18) (and explain
how you got the answers).
8.06, 8.07, 8.09, 8.10, 8.11, and 8.12 (15 pts each).
Material covered on Jan. 18: touched on sections 5.1, 6.1-6.3, 6.7, and started on Chapter 8.
Material to be covered the week of Jan. 25: rest of Chapter 8 and start on Chapter 9.
Due Wed Feb 1:
Textbook exercises 8.24, 8.29, 8.32, 8.35, 9.06, 9.10, 9.14, 9.19 (10 pts each), and 9.22 (20 pts).
In 9.22, the last two sentences have serious mistakes. They should read: Let J be
an ideal in S. Show that I, the set of elements i of R such that f(i) is in J is
an ideal in R.
Extra credit problem (30 pts): Textbook exercise 9.23.
Material to be covered the week of Jan. 30: complete Chapter 9, start Chapter 6.
Due Wed Feb 8:
Textbook exercises 6.01, 6.05, 6.07, 6.22, 6.30, 6.38, and 6.39 (15 pts each, but max of 100 pts total).
Extra credit problem: Textbook exercise 6.23 (20 pts).
Material to be covered the week of Feb 6: Chapter 12. In
Chapter 6, covered sections 1-8, the rest will come later.
Material to be covered on Mon Feb 13: Review Chapter 12, start Chapter 10.
Wednesday, Feb 15: in-class exam. NOTE CHANGE IN LOCATION: MechE 212 (upstairs from regular
Material to be covered on exam: Chapters 6 (sections 6.1 - 6.8 only), 8, 9, and 12 (sections 12.4 - 12.8 only).
No homework due this week. For practice on material that was not covered on homeworks, work on
textbook exercises 12.01, 12.10, 12.12, 12.15, 12.17, and 12.19.
Also, is the 3 x 3 matrix with rows (1 0 1), (0 1 1), and (1 1 1) invertible over F_2?
If it is, find its inverse.
No office hours on Wed Feb 15, instead, on Mon, Feb 13, will be
available 3-4 and 5:30 - 7.
Due Wed Feb 22:
1. (10 pts) Textbook exercise 10.06.
2. (20 pts) Reduce the polynomial f(x) = 3*x^5 + x^3 + 4*x^2 + 2 modulo the polynomial
g(x) = 6*x^4 + x^3 + 2*x^2 + 5*x over the field F_7.
3. (15 pts) Suppose C is a linear code of length n and dimension k over a
finite field that has q elements. How many cosets of C are there?
4. (15 pts). Consider the binary linear code C with generator matrix formed by the rows
(1 0 0 0 0 1 1 1 0 0 0 0 1 1), (0 1 0 0 1 0 1 0 1 0 0 1 0 1), (0 0 1 0 1 1 0 0 0 1 0 1 1 0),
and (0 0 0 1 1 1 1 0 0 0 1 1 1 1). (If you look on p. 219 of the textbook, or at notes
from lectures, you will see this matrix is obtained by putting together two copies of the
generator matrix for the [7, 4] Hamming code.)
What is the minimal distance of C? How many errors can C detect, and how many can it correct?
Decode the received word (0 1 1 1 0 1 1 0 1 1 0 0 1 0).
5. (25 pts) Suppose that C and D are two codes (not necessarily linear) over some finite
alphabet F_q, or lengths m and n, respectively. Define a new code E of length m + n
over that same alphabet by writing down the codewords (c, d) where c runs over
all of C and d runs over all of D, where (c, d) = (c_1, c_2, ..., c_m, d_1, d_2, ..., d_n),
if c = (c_1, ..., c_m), d = (d_1, d_2, ..., d_n). What is the minimum distance of
the code E? If C and D are linear, of dimensions g and h, respectively, show that
E is linear, and find its dimension in terms of g and h.
6. (15 pts) Find all subgroups of (Z/20)#, the multiplicative group of integers modulo 20.
Extra credit problem (20 pts): Textbook exercise 8.23, except that replace the last sentence by: More
generally, show that without any relative primeness hypothesis on the orders of g, h,
that |gh| divides the least common multiple of |g| and |h|. Find a counterexample to the claim
in the exercise as printed, namely an abelian group with two elements g, h, such that |gh| is
strictly less than the least common multiple of |g| and |h|.
Material to be covered the week of Feb 20 (and following weeks), roughly in the
complete Chapter 10
Lagrange interpolation and erasure codes, notes in
Due Wed Feb 29:
1. (15 pts) Prove that if f(x) is an irreducible polynomial of degree d over some field F,
then x^d f(1/x) is another irreducible polynomial of degree d.
5. (25 pts) What is the gcd of the polynomials f(x) = 2*x^3 + x^2 + 2 and g(x) = x^4 + 2*x^2 + x + 2
over the field F_3 with 3 elements? Express it as a linear combination with polynomial
coefficients of f(x) and g(x),
6. (15 pts) Find all irreducible monic polynomials of degree 2 over F_5.
7. (15 pts) Factor the polynomial x^4 + 14 x^3 + x^2 + 4 x + 11 into irreducible ones over F_17.
Textbook exercises 5.03 (5 pts), 5.04 (10 pts), 10.03 (10 pts), and 10.04 (5 pts).
Extra credit problem (25 pts): Prove from first principles that there is no finite field of order 6.
Due Wed Mar 7:
Textbook exercises 5.05 (10 pts), 5.06 (15 pts), 5.08 (10 pts).
1. (20 pts)
Suppose C is a linear code of length n and dimension k over a
finite field that has q elements. Define a new code C* of length n+1
over the same field to consist of the vectors (c_1, c_2, ..., c_n, x)
where (c_1, c_2, ..., c_n) runs over the codewords in C, and for each
such codeword, x = - c_1 - c_2 - ... - c_n. Prove that C* is linear.
What is its dimension? How does its minimum distance compare to
that of C?
2. (20 pts)
Compute f(x)^23 mod g(x) over F_3, where f(x) = 2*x^4+x^2+2, g(x) = 2*x^3+x+1.
If you did not attend class on Wed Feb 29, read Section 6.13 of the textbook, and
recall the basic philosophy that polynomials over a finite field behave almost
always like integers.
3. (15 pts) Find a polynomial f(x) over F_11 of degree at most 3 such that
f(1) = 2, f(2) = 1, f(5) = 6, f(6) = 5.
4. (10 pts) Find a polynomial f(x) over F_11 of degree at most 3 such that
f(7) = 6, f(8) = 5, f(9) = 4, f(10) = 3.
Extra credit problem (25 pts): Consider a CRC with generating polynomial g(x) (everything in F_2[x]).
As discussed in class and in the textbook, some 2-bit errors will not be detected
by this CRC. However, we can hope to choose g(x) so that positions of such two bits
that slip through are so far apart that in practice this will not be a problem.
Suppose we have found a good g(x). The basic theory of the CRC shows how it detects
errors that arise in the transmission of the data. But what happens if
there is an error in the CRC that is sent along with the data? Can you find a
way to use/construct/... something using the same g(x) that will also tell you
when errors occur in the bits that are added to the data (possibly in combination
with errors that happen in the data bits), and do it elegantly?
(Note: The way this topic was presented in class is that if
you have bits a, a, ..., a[n-1], you send them as they are, in this order, and appended
to them bits b, b, ..., b[k-1], where the CRC generating polynomial g(x) had degree k,
and b*x^(k-1) + ... + b[k-1] is the remainder you obtain on dividing a*x^(n-1) + ... + a[n-1]
Some useful notes on polynomials over finite fields: file http://www.dtc.umn.edu/~odlyzko/Math5251/polynomials20120305.pdf
Due Wed Mar 21:
Textbook exercises 14.02 (15 pts), 14.04 (15 pts), 14.05 (15 pts), 17.04 (5 pts), and 17.06 (10 pts).
Extra credit problem (25 pts): Suppose that n is an odd positive integer, and that
g(x) in F_2[x] is the generator polynomial of a cyclic code C with
g(x) dividing x^n - 1. Let C* be the collection of codewords of C
that have weights that are even
integers. If C* = C, what can you say about g(x)? If C* is a proper
subset of C, is it a linear code? (The word linear was omitted from the initial
statement of the problem.) If it is, is it cyclic? And if if it
cyclic, what is its generator polynomial?
Material covered recently far: Chapters 5 and 14, sections 6.13 and 17.1.
Week of March 19: rest of Chapter 6, Chapter 11.
Wednesday, Mar 28: in-class exam. SAME LOCATION AS LAST TIME: MechE 212 (upstairs from regular
Material to be covered on exam: Lagrange interpolation and erasure codes,
chapters 5, 6, 10, 11, and 17 (section 17.1 only).
No homework due this week. For practice on material that was not covered on homeworks, work on:
Textbook exercises 6.59, 6.66, 6.67, 6.81, 6.82, 11.02, 11.07, 11.08.
Express the polynomials f(x) = x^3 + 2 and g(x) = x^2 + 4 x + 5 as products of irreducible
ones over F_11. Is there a polynomial h(x) over F_11 that satisfies
h(x) = x + 7 (mod f(x)) and h(x) = x - 7 (mod g(x))?
Show that f(x) = x^3 + x + 1 is irreducible over F_5. Consider the field F_5[x]/f(x). Let
alpha be the image of x. Find the reduced forms of 1/(3 + alpha^2) and alpha^1000.
No office hours on Wed Mar 28, instead, on Tue, March 27, will be available from 1:30 to 2:30.
Mon Mar 26 (and much of week of Apr 2): Chapters 15 and 16.
Due Wed Apr 4:
Textbook exercises 15.03 (10 pts), 15.05 (15 pts), 15.07 (15 pts), 15.09 (20 pts),
and 16.17 (25 pts, but the definining polynomial is to have coefficient 10011, the
one given in the book is reducible).
(15 pts) Let alpha be the image of x under the mapping of F_2[x] to F_4 = F_2[x]/(x^2 + x + 1),
and consider the polynomial g(y) = (alpha + 1)*y^3 + alpha * y + 1
in F_4[y]. Compute g(y)^2 and g(y)^4 as explicit sums of monomials with coefficients
that are in canonical form.
Extra credit problem (25 pts): Suppose that B and C are linear codes over F_2 with lengths
m and n respectively, and of dimension k each. Define a new binary code B*C of
length m*n by creating, for every b = (b_1, ..., b_m) in B and every
c = (c_1, ..., c_n), a codeword in B*C by b*c = (b_1*c_1, b_1*c_2, ..., b_1*c_n, b_2*c_1, ...,
b_2*c_n, ..., b_m*c_b). What is the minimal non-zero weight of a codeword in B*C in
terms of the minimal distances in B and C? Is B*C always linear?
Due Wed Apr 11:
Textbook exercises 15.13, 15.14, 17.08, and 17.09 (20 pts each).
- (10 pts) How many monic polynomials over F_2 of degree 8 are irreducible? How many
of those are primitive?
(There are mistakes on p. 264 where these are computed.)
- (10 pts) Show that the designed distance of a Reed-Solomon code equals its
Due Wed Apr 18:
Textbook exercises 1.15, 1.21, 13.02, 13.10, 17.12, and 17.13 (15 pts each).
(10 pts) Is there a binary linear code of dimension 3, with minimum distance 3, and with
block length 6? What if we keep the other parameters the same, but ask for dimension equal to 4?
Due Wed Apr 25:
Textbook exercises 1.31 (10 pts), 1.33, 1.45, 1.49, 2.02, 2.03, and 2.04 (15 pts each).
Extra credit problem (25 pts): Suppose a source emits A with probability 1/2,
B with probability 1/2 - 1/10^6, and C with probability 1/10^6. Find a way
to do lossless encoding of this source into binary strings that uses only a little bit more
than 1 bit on average per source symbol. (Unlike the setting in class and in the book,
the recipient may
use knowledge of the past outcomes, and may have to wait a while to get
the correct decoding.)
Monday, Apr 30: last regular class. Class evaluation forms will be handed
out to be completed after the (shortened) lecture.
Wednesday, May 2: last session, in-class exam. LOCATION: MechE 212 (upstairs from regular
- Same rules as on other exams: open book, ..., 75 minutes.
- Blue books will be available, but are not required. Feel free to use your own paper.
Material to be covered on exam: Chapters 1 (but only to the extent that was covered on the
homeworks or on the exercises below), 2 (but only to the extent of being able to compute
entropies), 3, 13 - 17, and sections 19.6 - 19.8.
No homework due this week. For practice on material from April 23 and 25 that was not covered on homeworks,
textbook exercises 3.01, 3.02, 3.04, 3.05, and 3.07, where in 3.07 your task is to show that the
answer given in the back of the book is wrong.
All students in the class, not just those enrolled through UNITE, should have access to all
the videos of all the lectures starting on the evening of April 25.
No office hour on Wed May 2, but will be available on Tue May 1 from 2:00 to 3:00.
Monday, May 7: Term papers due by 11:00 am, either via email (PDF format preferred) or in my mailbox in Vincent 107.
I will be happy to provide rough feedback on early drafts that are submitted by 11 am
on Fri May 4.
Return to home page