• phone 612-625-5413
• email: odlyzko@umn.edu (preferred and most reliable method)

• 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.

• 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.

• 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.
• Topics 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 material.
• 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).
  • Textbook exercises 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 lecture room).
  • 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 order:
  • complete Chapter 10
  • Lagrange interpolation and erasure codes, notes in file http://www.dtc.umn.edu/~odlyzko/Math5251/lagrange20101103.pdf
  • Chapter 5
  • Chapter 14
  • Chapter 11.

• 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[0], a[1], ..., a[n-1], you send them as they are, in this order, and appended to them bits b[0], b[1], ..., b[k-1], where the CRC generating polynomial g(x) had degree k, and b[0]*x^(k-1) + ... + b[k-1] is the remainder you obtain on dividing a[0]*x^(n-1) + ... + a[n-1] by g(x)).)

• 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 lecture room).
  • 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 minimum distance.

• 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 lecture room).
  • 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, work on 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.