Math 4280 - Introduction to Information Theory

Spring 2008, Georgia Tech

M W F 10:05 - 10:55 a.m. Skiles 154

Professor
Kate Hurley
  • Office: 258 Skiles
  • Office hours: 2 - 3 p.m. Wednesdays, 3 - 4 p.m. Thursdays or by appointment
  • Email: hurley@math.gatech.edu
  • Phone: 404-894-1833

    • Textbook
    Required: Information and Coding Theory by Gareth A. Jones and J. Mary Jones, Springer 2000.

    Recommended: Elements of Information Theory: 2nd Edition by Thomas M. Cover and Joy A. Cover, Wiley 2006.

    Prerequisites
    Math 3215, Introduction to Probability and Statistics, or its equivalent.

    Course Description
    The course covers the first five chapters of the textbook, i.e., source coding, optimal codes, entropy, information channels and using an unreliable channel.

    Homework
    Homework will be posted at the bottom of this web site. Problems will be assigned sporadically and will be due at the beginning of class on Friday of the following week.

    Students are encouraged to work on the assignments together, but must write them up independently. Simply transcribing another student's work or the solution from the back of the book is regarded as an honor code violation. Presentation counts toward the homework grade. Solutions should be presented clearly and logically, so as to be easily understood by another student in the class. Work should be reasonably neat and stapled.

    A subset of the homework will be graded by the grader. The homework will compose 15% of the course grade, and the lowest homework score will be dropped.

    Tests and Exams
    There are two midterm exams, the first is on Wednesday February 13th, solutions to exam 1, the second is on Wednesday April 2nd, solutions to exam 2. Each midterm will compose 25% of the final grade.

    The cumulative final exam is Wednesday April 30th from 2:50 to 5:40 p.m. It is worth 35% of the grade. Here is a review sheet for the final.

    Policies
    In order to be acceptable, excuses for missing work must be serious, documented, and timely. I reserve the right to reject lame excuses.

    Students are expected to abide by the Georgia Tech honor code .

    Getting help
    Please come to my office hours. I really like to see students individually as it gives me insight into what students understand. If these hours are not convenient, please stop by my office, e-mail me at hurley@math.gatech.edu or call me at 404-894-1833, and I would be happy to set up an appointment.

    Homework Assignments
    Homework is to be turned in at the beginning of class on the Friday of the week after it is assigned. The book has solutions to its exercises starting at page 65. While you can consult these solutions, exact or nearly exact copies of the book's solutions will not receive credit. In general, I would like to see more detail in your solutions than those in the text. Explain what you are doing and why.

    Date Assigned Problems Due Date
    1/9 Exercises 1.1 and 1.2 on page 6. (See the top of page 6 for the definition of C^infinity.) 1/18
    1/11 1.3 (pg 7), 1.4,1.5,1.6 (pg 8) 1/18
    1/14 Prove that a code is uniquely decodable if and only if its reverse code is uniquely decodable* solution, 1.8 (pg 9), 1.9 (pg 10), 1.10 (pg 11) 1/25
    1/16 1.11 (pg 13), 1.12 (pg 17) 1/25
    1/23 2.1 (pg 20) 2/1
    1/25 2.3 (pg 24), 2.10, 2.11** (pg 32) 2/1
    1/30 2.4 (pgs 25-26), 2.5 (pg 27), 2.6 (pg 28), additional problem solution 2/8
    2/1 2.7 (pg 30), 2.12 (pg 33), additional problems solutions 2/8
    2/4 2.9 (pg 32), 2.14 (pg 33) not due
    2/6 feb 6 problem solution not due
    2/15 3.1 (pg 39) 2/22
    2/18 3.2 & 3.3 (pg 44) 2/29
    2/20 3.4 (pg 46) 3.5 & 3.6 (pg 51) 3.10 (pg 52) 2/29
    2/27 4.1 (pg 59) 4.2 (pg 62), additional problem 3/7
    2/29 4.3 (pg 64), additional problem, 3/7 Homework Solutions 3/7
    3/3 4.5 (pg 65), 4.6*** (pg 66), 4.7 (pg 67) 3/14
    3/5 4.4****, Find an example of an information channel in which the input source and output source are statistically independent. 3/14 Homework Solutions 3/14
    3/10 homework problem 3/28
    3/14 4.8 (pg 73, only do BEC), 4.9 (pg 74), 4.13 & 4.15 (pg 77), 3/28 Homework Solutions 3/28
    3/26 5.1 (pg 80), 5.2 (pg 81), additional homework problem 4/4
    3/28 5.8 (pg 94) 4/4 Homework Solutions 4/4
    4/4 5.4 & 5.5 (pg 86), 5.9 & 5.10 (pgs 94-95) 4/11 Homework Solutions 4/11
    4/14 5.7 (pg 89), 2 additional homework problems 4/18 Homework Solutions 4/18
    4/21 3.2, 3.4, 3.5, 3.7 (a) and (b)***** Solutions not due

    ***** These problems are from "Elements of Information Theory: 2nd edition," by Cover and Thomas, which is on reserve at the library.

    **** Only prove the equality for the equivocation of B with respect to A, i.e., H(B|A).

    *** Please give an example other than the one in the back of the book.

    * The words in the reverse code of C are all the code words of C written backwards.

    ** For 2.11, please answer the additional question: For the given type of source, are all the instantaneous binary codes with word-lengths 1,2,...,q-1,q-1 Huffman codes?