General remarks:
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.
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.
-
No office hours on Wed Jan 23.
-
Material to be covered Jan 23 and the week of Jan 28: Chapters 1, 2, most of 13, and (lightly) the Appendix
on pp. 356-8.
-
Due Wed Jan 30:
-
Textbook exercise 1.21 (15 pts)
-
A1. (The definition of Hamming distance, discussed in class on Wed Jan 23, is covered
in the book at the beginning of Section 4.3. The definition of a sphere, or ball, in
Hamming spaces is in Section 13.1.) Suppose we are considering the
alphanet Q = { 0, 1}, so that q, the size of Q, is 2.
What is the intersection of the two spheres, both of radius 2, centered at the
points (0, 1, 0, 1, 0) and (1, 1, 1, 1, 1)? What is the size of the intersection
of a sphere of radius 2 centered at (0, 1, 0, 1, 0), and a sphere of radius 3
centered at (1, 0, 1, 0, 1)? (20 pts)
-
A2. Suppose n = 10. Is there some finite alphabet Q such that there are vectors x, y, z, and w
in Q^n (i.e., q-ary n-tuples, with q the size of Q) such that (with d denoting Hamming distance)
d(x,y) = 4, d(x,z) = 8, d(x,w) = 5, d(y,z) = 3, d(y,w) = 4, and d(z,w) = 3 ? (15 pts)
-
Homework solutions: file http://www.dtc.umn.edu/~odlyzko/Math5251/soln20130130.pdf
-
Material to be covered the week of Feb 4: Complete Chapter 1, go lightly over Chapter 2,
and start Chapter 3.
-
Due Wed Feb 6:
-
Textbook exercises 13.02 and 13.09 (20 pts each).
-
A3. (20 pts) Determine the sum of k*binomial(n,k) as k runs from 0 to n, where
binomial(n,k) is the binomial coefficient "n choose k."
-
A4. (20 pts) Obtain upper and lower bounds for the largest possible codes
over the binary alphabet, with length 100, and capable of correcting 5 bit errors.
-
A5. (20 pts) Find the largest code that exists over the binary alphabet with length 6 and
minimum distance 4. (That is, you have to produce a code and show there is no larger
code for these parameters.)
-
A6. (Extra credit problem, 20 pts) Consider a code over the binary alphabet, of length 7, and with 16 codewords, in
which the first 4 symbols are arbitrary binary symbols (the information bits), and if
a codeword is (x1, x2, x3, x4, x5, x6, x7), then x5 is chosen to make x2 + x3 + x4 + x5 even,
x6 is chosen to make x1 + x3 + x4 + x6 even, and x7 is chosen to make x1 + x2 + x4 + x7 even.
Show that this code has minimum distance 3.
-
Homework solutions: file http://www.dtc.umn.edu/~odlyzko/Math5251/soln20130206.pdf
-
Material to be covered the week of Feb 11: Complete Chapter 3, do most of Chapter 4.
-
Due Wed Feb 13:
-
Textbook exercises 1.31 (10 pts), 1.45, 1.49, 1.57, 2.02, 2.03, and 2.04 (15 pts each).
(Note on Problem 1.57: It is incorrect as stated. Prove that the probability of getting
at least 2,000 heads is at most 1/900.)
-
A7. (Extra credit problem, 20 pts) The code with words 00, 01, 110, and 001 is not
a prefix code, as is noted on p. 47 of the textbook. Show that it is a uniquely
decodable code. (Remember that on extra credit problems you are supposed to work alone.)
-
Homework solutions: file http://www.dtc.umn.edu/~odlyzko/Math5251/soln20130213.pdf
-
Material to be covered on Mon Feb 18: Chapter 4.
-
Wednesday, Feb 20: in-class exam.
- Same rules as on other exams, and as described earlier on this page: 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 a little bit of Section 1.1, and skipping conditional
probability), 2 (but only to the extent of being able to compute
entropies), 3, and 13 (with the Gilbert-Varshamov bound replaced by the Gilbert bound).
-
No homework due this week. For practice on material from Feb 11 and 13 that was not covered on homeworks,
work on
textbook exercises 3.01, 3.02, 3.04, 3.05, and 3.07. However, in 3.04, there should be just 2 source
words with probability 1/16 (the ones given add up to 17/16), and in 3.07 your task is to show that the
answer given in the back of the book is wrong.
-
Solutions: file http://www.dtc.umn.edu/~odlyzko/Math5251/soln20130217.pdf
-
Midterm: file http://www.dtc.umn.edu/~odlyzko/Math5251/exam20130220.pdf
-
Midterm solutions: file http://www.dtc.umn.edu/~odlyzko/Math5251/soln20130220.pdf
-
Material to be covered the week of Feb 25: sections 5.1, 6.1-6.3, 6.7, and start on Chapter 8.
-
Due Wed Feb 27:
-
Textbook exercises: 4.04, 4.05, 4.11, 4.12 (15 pts each).
-
A8. Extra credit problem, 20 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.)
-
Homework solutions: file http://www.dtc.umn.edu/~odlyzko/Math5251/soln20130227.pdf
-
Material to be covered the week of March 4: Chapter 9, start on Chapter 6.
-
Due Wed March 6:
-
Textbook exercises: 8.06, 8.07, 8.09, 8.10, 8.12, 8.24 (where the 3.5 in the exponent
means multiplication of 3 and 5, or 15), 8.29, and 8.35. 10 pts for each of the
first 6, and 20 for each of the last 2.
-
Homework solutions: file http://www.dtc.umn.edu/~odlyzko/Math5251/soln20130306.pdf
-
Material to be covered the week of March 11: Chapter 6 (section 6.1 - 6.8 only at this time),
Chapter 12.
-
Due Wed March 13:
-
Textbook exercises: 6.01, 6.05, 6.07, 6.22, 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): (This has been changed!) Prove from first principles that there is no finite field of order 6.
-
Homework solutions: file http://www.dtc.umn.edu/~odlyzko/Math5251/soln20130313.pdf
-
Material to be covered the week of March 25: Finish Chapter 12, do Section 13.2 for linear codes,
and start Chapter 5.
-
Due Wed March 27:
-
Textbook exercises: 6.38, 6.39, 12.01, 12.10, and 12.12 (10 pts each).
-
Extra credit problem (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.
-
Homework solutions: file http://www.dtc.umn.edu/~odlyzko/Math5251/soln20130327.pdf
-
Material to be covered on Mon Apr 1: Sections 10.1 and 10.2 and Chapter 5.
-
Wed Apr 3: 2nd midterm.
- Same rules as on other exams, and as described earlier on this page: 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: Chapter 4 (very lightly, to the extent covered in class and on
homework problems), Chapter 6 (sections 6.1 - 6.8), chapters 8, 9, 12, 13, and section 14.1.
-
No homework due this week. For practice on material from Mar 25 and 27 that was not covered on homeworks,
work on textbook exercises 12.15, 12.17, and 12.19, 13.07, and 14.02.
-
A9. 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.
-
A10. 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).
-
Solutions: file http://www.dtc.umn.edu/~odlyzko/Math5251/soln20130401.pdf
-
Midterm: file http://www.dtc.umn.edu/~odlyzko/Math5251/exam20130403.pdf
-
Midterm solutions: file http://www.dtc.umn.edu/~odlyzko/Math5251/soln20130403.pdf
-
Material to be covered the week of Apr 8: Wrap up Chapter 5, cover the Lagrange
interpolation formula and erasure codes (not in the textbook, notes in file
http://www.dtc.umn.edu/~odlyzko/Math5251/lagrange20101103.pdf), and
then go back and start work on covering
those parts of chapters 6 and 10 not covered before (namely sections 6.9 - 6.15, and 10.3 - 10.5).
-
Due Wed Apr 10:
-
Textbook exercises: 5.03 (10 pts), 5.04 (10 pts), 5.05 (10 pts), 5.06 (15 pts), 5.08 (15 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) Problem 4 of the 2nd midterm asked for the minimal length of a linear code
over the binary alphabet that has dimension 4 and minimal distance 4. If we let C be
such a code, then the answer (as worked out in the posted solution) is that the length
of C is no more than 10. (a) Find the smallest length m for which the Gilbert-Varshamov
bound guaranteeds that there is a binary linear code of length m, dimension 4, and minimal
distance 3. Let such a code be called D.
(b) Let D' be obtained from D by adding a parity check to each codeword of D (so that
the length of D' is one more than the length of D, and the last big of a codeword of
D' is 1 if there is an odd number of 1s in the preceding positions, and 0 otherwise.
What are the length, dimension, and minimal distance of D', and how do they compare
to those of C?
-
Extra credit problem (30 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)).)
-
Homework solutions: file http://www.dtc.umn.edu/~odlyzko/Math5251/soln20130410.pdf
-
Material to be covered the week of Apr 15: complete Chapter 6 (sections 6.9 - 6.15), and start Chapter 11.
-
Due Wed Apr 17:
-
Textbook exercises: 10.04 and 10.06 (10 pts each).
-
A11. (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),
-
A12. (20 pts) Find all irreducible monic polynomials of degree 2 over F_5.
-
A13. (20 pts) Factor the polynomial x^4 + 14 x^3 + x^2 + 4 x + 11 into irreducible ones over F_17.
-
A14. (15 pts) Show that if a is a non-zero element of a finite field F, and f(x) and g(x) are polynomials
in F[x], then the canonical reduction of f(x) modulo g(x) is the same as the
canonical reduction of f(x) modulo a*g(x).
-
Extra credit problem (20 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.
-
Homework solutions: file http://www.dtc.umn.edu/~odlyzko/Math5251/soln20130417.pdf
-
Material to be covered the week of Apr 22: review Section 14.1, cover 14.2, start on Chapter 17.
-
Due Wed Apr 24:
-
Textbook exercises: 6.59, 6.66, 6.67, 11.02, 11.07, and 11.08 (10 pts each).
-
A15. (15 pts) 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))?
-
A16. (25 pts) 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.
-
Homework solutions: file http://www.dtc.umn.edu/~odlyzko/Math5251/soln20130424.pdf
-
No class and no office hour on Mon Apr 29.
-
Material to be covered on May 1 and 6: complete Chapter 17, cover Chapter 15.
-
Due Wed May 1:
-
Textbook exercises 14.02 (15 pts), 14.04 (15 pts), 14.05 (15 pts), 17.04 (5 pts), 17.06 (10 pts),
17.08 (20 pts), and 17.09 (20 pts).
Problem 14.02 should be done the easy way, using the theory of cyclic codes, not the laborious
process outlined in the solution to problems assigned in preparation for the 2nd midterm.
-
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?
If it is, is it cyclic? And if if it
cyclic, what is its generator polynomial?
-
Homework solutions: file http://www.dtc.umn.edu/~odlyzko/Math5251/soln20130501.pdf
-
Mon May 6: last regular class. Class evaluation forms will be handed
out to be completed after the (shortened) lecture.
-
Material to be covered: complete Chapter 17, sections 15.1 - 15.6, 15.8, 15.10, 16.1 - 16.3.
-
Wed May 8: 3rd midterm.
- Same rules as on other exams, and as described earlier on this page: open book, ..., 75 minutes.
-
Material to be covered on exam (some to be covered in class on Mon May 6): Chapters 5, 6 (sections 6.9 - 6.15),
10, 11, 14, 15 (sections 15.1 - 15.6, 15.8, 15.10), 16 (sections 16.1 - 16.3), 17.
-
No homework due this week. For practice on recent material that had not been
covered on homeworks, work on textbook exercises 15.03, 15.05, 15.13, 15.14, 16.03, 16.06, 17.12, and 17.13.
-
A17. Show that the designed distance of a Reed-Solomon code equals its
minimum distance.
-
A18. (A hard one, equivalent to an extra credit problem.) 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_n). 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?
-
Solutions (corrected version, original had a mistake on 16.06): file http://www.dtc.umn.edu/~odlyzko/Math5251/soln20130506.pdf
-
Midterm: file http://www.dtc.umn.edu/~odlyzko/Math5251/exam20130508.pdf
-
Midterm solutions: file http://www.dtc.umn.edu/~odlyzko/Math5251/soln20130508.pdf
-
Mon May 13: term papers due, 11 am, either in the mailbox in Vincent 107, or via email (preferably
in PDF format). Rough comments will be provided on drafts submitted via email (preferably in
PDF format) by Fri May 10, 11 am.
-
Grades should be ready by Thu May 16, and will be emailed to each person.
Up [
Return to home page
]