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

This course develops the 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.

A short introduction to counting and probability theory leads to concepts of information and entropy, and then noiseless coding and compression. Shannon's Noisy Coding Theorem, a more substantial piece of work, follows, showing just how much error-correction one can achieve. That covers the material up to the first exam.

After the first exam, the course starts with redundancy checks, which lead to algebraic techniques, which motivate development of abstract algebra and linear algebra over finite fields methods. Those are then used to construct a variety of error-correcting codes.

• Special assignment due by midnight, Saturday, Jan. 24, via email to odlyzko@umn.edu:
  • If you were born in January through June, send in a string of 50 heads or tails, obtained by tossing a coin 50 times
  • If you were born in July through December, send in a string of 50 heads or tails that you write down without using a coin or a computer random number generator, just something that seems random
  • Important: do not tell me how you produced your string!
  • Worth 10 points on the homework due Jan. 28.
• Due Jan. 28: Textbook exercises 1.02 (10 pts), 1.11 (20 pts), 1.13 (20 pts), 1.16 (20 pts), 1.21 (20 pts).

• Due Feb. 4: Texbook exercises 1.33 (10 pts), 1.46 (20 pts), 1.47 (20 pts), 1.53 through 1.55 (20 pts total, this is basically a single problem with three values of a parameter), 2.02 (10 pts), 2.04 (20 pts).

• Due Feb. 11: Material for the last 3 problems will be covered in Monday's lecture, and is also available in the textbook.
  • (10 pts): Textbook exercise 1.51.
  • (25 pts): Let X be the number of tosses of a fair coin until a head appears. Compute the variance of X.
  • (25 pts): Consider n independent tosses of a biased coin that comes up heads with probability 1/3 and tails with probability 2/3. Let p(k) be the probability that k heads appear. For what value or values of k is p(k) maximized? Find the asymptotics of this maximum (i.e., the ratio of your answer to the true value should tend to 1 as n goes to infinity).
  • (10 pts): Consider 10 independent tosses of a fair coin. What is the probability that the number of heads will be divisible by 3, given that this number is even?
  • (15 pts): Textbook exercise 3.02.
  • (15 pts): Textbook exercise 3.05.

• Due Feb. 18: The material needed for the last three problems will be covered on Monday.
  • (20 pts): Let X be the number of tosses of a fair coin until a head appears. Compute the expectation of the fourth power of the difference of X and its expected value. (The variance is the expectation of the second power.)
  • (15 pts): Consider the first example on p. 47 of the textbook, a code with words 00, 01, 110, and 001. Is this code uniquely decodable? If so, provide a proof.
  • (15 pts): Textbook exercise 3.06.
  • (20 pts): Textbook exercise 4.04.
  • (10 pts): Textbook exercise 4.06.
  • (20 pts): Consider a binary symmetric channel with bit error probability p, 0 < p < 1/2. Suppose we encode a binary message (x1, x2, ..., x100) (i.e., there are 100 bits) as n copies of x1, followed by n copies of x2, n copies of x3, ...., n copies of x100. The receiver will look at the first n bits and choose y1 by majority vote from them (and y1 = 0 if there is a tie, say), then look at the next n bits and choose y2 by majority vote of those, and so on. Prove that (y1, y2, ..., y100) = (x1, x2, ..., x100) with probability approaching 1 as n tends to infinity.

• Feb. 25: No homework due, in-class exam. Open book, open notes, open calculator, no computers or smart phones. Material to be covered: Chapters 1-5 of textbook (including Chapter 5!).

• Due March 4: Textbook exercises 5.04 (10 pts), 5.06 (10 pts), 5.08 (10 pts), 6.01 (15 pts), 6.04 (15 pts), 6.22 (15 pts), 6.23 (25 pts).

• Due March 11: Textbook exercises 6.30 (5 pts), 6.31 (10 pts), 6.32 (15 pts), 6.38 (10 pts), 6.50 (10 pts), 6.59 (10 pts), 6.66 (15 pts), 6.67 (10 pts), 6.81 (15 pts).

• March 18: No homework due, spring break.

• March 25: No homework due, in-class exam. Open book, open notes, open calculator, no computers or smart phones. Material to be covered: Chapters 6, 10, and 11. Exam and solutions.

• April 1:
  • Textbook exercises 12.01 (10 pts), 12.02 (10 pts), 12.10 (10 pts), 12.15 (20 pts), 12.17 (10 pts), 13.09 (10 pts), 13.10 (10 pts).
  • (20 pts): Suppose that we consider codes over F_5 (the field of 5 elements), except that instead of the Hamming distance, we consider the Lee distance, so that the distance between two vectors x = (x_1, ..., x_n) and y = (y_1, ..., y_n), with the x_i and y_i from F_5, is the sum of d(x_i, y_i) for i going from 1 to n, and d(u, v) for u and v both in the set {0, 1, 2, 3, 4} is defined as min( |u - v|, 5 - |u - v| ). (Think of 0, 1, 2, 3, 4 arranged in a circle, then d(u, v) is the number of steps from u to v in the shorter direction.) Extend the Hamming bound for codes to obtain an upper bound on the size of a code of length 20 over F_5 in which any two codewords are at Lee distance at least 9 apart.

• April 8:
  • Textbook exercises 14.02 (where the field is the binary field F_2) (15 pts), 14.04 (15 pts), 14.05 (15 pts).
  • Find a linear dependence or prove that none exists over the field F_3 of the vectors (-1, 1, 0, 1, 1, 0), (0, 1, -1, 0, 1, -1), (1, 0, -1, 1, 0, -1), (1, -1, 1, -1, 1, -1), and (1, 1, -1, 0, 0, 0) (15 pts).
  • (20 pts): Consider an [n, k] linear code over F_q in which the generator matrix does not have any column that consists only of zeros. Show that the sum of the weights of the q^k codewords is n*(q-1)*q^(k-1).
  • (20 pts): Consider an [n, k] linear code over F_2 in which some codewords have weights that are odd integers. How many codewords of even weight does this code have?

• Term project: For some examples of writeups (none what is expected in this class, but all of which have elements of what's needed), which I will discuss briefly in class on Monday, April 6, take a look at Digital Fountain technology page, and the three papers available there (on the right side of the page).

• Monday, April 13, and Wednesday, April 22: There will be guest lectures by Professor Don Kahn, on chapters 8 and 9 from the textbook. This material is part of the course, and will be on the homeworks and the third exam.

• April 15: Textbook exercises 8.06 (10 pts), 8.10 (10 pts), 8.19 (10 pts), 15.05 (10 pts), 15.09 (20 pts), 16.03 (10 pts), 16.05 (10 pts), and 16.08 (20 pts).

• April 22:
  • Textbook exercises 8.21 (10 pts), 8.23 (10 pts), and 8.27 (10 pts).
  • (10 pts): Let C be the binary Hamming [7,4] code, given by the generator matrix at the top of p. 219 of the textbook. Is this code cyclic?
  • (15 pts): Let C be the binary Hamming [7,4] code, and let C# be the dual code of C. How many errors can C# detect? How many errors can C# correct?
  • (15 pts): Let C be the binary Hamming [7,4] code. Let C* be the binary code of length 8, obtained from C by appending to each codeword c = (c1, c2, ..., c7) an extra bit c8, with c8 = c1 + c2 + ... + c7 (addition in the binary field F_2). Show that C* is linear. What is the dimension of C*? How many errors can C* detect? How many can it correct?
  • (15 pts): Prove that f(x) = x^5+x^2+x+2 is irreducible over F_3, the field of 3 elements. What is the minimal computation that would be required to check whether f(x) is primitive? (You don't have to actually do the computation.)
  • (15 pts): Let F_243 be defined by the polynomial f(x) from the preceding problem over F_3. How many elements of F_243 would you have to test before you could be sure you would find a primitive element, if you were maximally unlucky? (Unless you are a glutton for punishment, do not look for one.)

• April 29 (revised):
  • Textbook exercises 9.12 (10 pts), 9.13 (10 pts), 16.17, but with F_16 modeled as F_2[x] modulo the polynomial x^4 + x^3 + 1 (the one in the textbook does not work, as it is divisible by x + 1) (20 pts), 17.06 (10 pts), and 17.09 (15 pts).
  • (20 pts): Consider a binary code of length 9, with codewords c = (c_1, c_2, ..., c_9) such that c_1 = c_2 = c_3, c_4 = c_5 = c_6, and c_7 = c_8 = c_9. Show that this code is linear and find its dimension, and write down the generator matrix for it. Show this code is not cyclic, and find a permutation of the positions of C that make it into a cyclic code.
  • (15 pts): Suppose that C is a binary cyclic code of length n with generator polynomial g(x) such that g(x) divides x^n + 1. Suppose that flipping all the 0's to 1's and 1's to 0's in any codeword of C produces another codeword in C. What does this say about g(x)?

• May 4: Class evaluations at end of class. Exercises, not to be handed in, to be discussed in class:
  • Textbook exercises 11.11, 12.19, 14.03, 15.10, 17.10, 17.12, 18.03, and 18.04.
  • 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.
  • How many primitive monic polynomials of degree 5 are there in F_5[x]?
  • What is the smallest length n for which the Gilbert-Varshamov bound guarantees that there will be a binary linear code of length n, dimension 5, and minimum distance 5? For this n, what are the upper bounds on the possible minimum distance that the Hamming and Singleton bounds provide?

• May 6: In-class exam. Open book, open notes, open calculator, no computers or smart phones. Material to be covered: Chapters 8 and 9 to the level that was covered in homeworks, Section 18.1 of Chapter 18, and Chapters 11-17, skipping Sections 15.7, 15.9, and 16.4.

• May 11: Term paper due by 11 am, either via email or in mailbox in Vincent 107.