Information Theory

ELEC 535, Spring 2003

Rice University

This course covers the basic concepts of information theory at a fairly rigorous level and
discusses applications to Digital Communication Systems such as Coding, Channel Capacity and Data Compression.

[Requirement] [Outline] [Textbooks] [Grading] [Reading assignment] [Homework problems and solutions] [Tests]


Dr. Rudolf Riedi
Duncan Hall 2025, 713 / 348 3020,
Office Hours: Tu 4-6pm (DH 2025), or by appointment
Nasir Ahmed
Duncan Hall DH2123, 713 / 348 2827,
Office Hours: Thursday 4pm-6pm, or by appointment
Alireza Keshavarz-Haddad
Duncan Hall, 713 / 348 3579,
Office Hours: W 3-5pm, or by appointment
Time and Place
Monday Wednesday Friday 10:00 - 10:50 am, AL (Abercrombie Lab) 126

For current updates check the official Rice page


ELEC 533 or equivalent course on the basics of probability theory

More explicitly, required is a basic understanding of conditional probability and expectation, as well as the concepts of convergence of random sequences.


Basic concepts: (mutual) information, entropy rates
QUIZ (one sheet = two pages of hand-written personal notes)
Data compression; entropy; mutual information
Midterm EXAM (open-notes, closed-books)
Channel capacity; Gaussian channel; rate distortion
Second EXAM (open-notes)

[Outline] [Textbooks] [Grading] [Reading assignment] [Homework problems and solutions] [Tests]


Further suggested reading Useful books on Probability Theory for reference

[Outline] [Textbooks] [Grading] [Reading assignment] [Homework problems and solutions] [Tests]


15%  QUIZ
30%  Midterm EXAM
30%  Last EXAM
20%  Homework
5%  Notes and participation in class

[Outline] [Textbooks] [Grading] [Reading assignment] [Homework problems and solutions] [Tests]

Classes and Reading Assignments
  This doubles as a calendar for the course.
Covered material Reading: Cover&Thomas
January 13 Orientation, history
January 15 Discrete and differential entropy 2-8, 12-14, 224-225
January 17 Quantization, joint+conditional entropy 228-230, 15-16
January 22 Chain rule, KL distance, Mutual Information 16-21, 231-232
January 24 Basic properties of information, Markov Chains 22-23, 231; 32
January 27 Data processing inequality 32-33, (33-38)
January 29 Jensen's inequality 23-26
January 31 Convexity; thermodynamics 26-31; (33-38)
February 3 Convexity and maximal entropy 233-234
up to here: Material for Quiz
February 5 Codes: basics 78-82
February 7 Kraft Inequality 82-86
February 10 HW3, D-ary expansions 90-92
February 12 QUIZ in class
February 14 extended Kraft, McMillan 90-92
February 17 Optimal Codes, Lagrange multipliers 87
February 19 Shannon Codes 88-89
February 21 Entropy rate, Cesaro means 60-66
February 24 Penalty for mismatched code 89-90
February 26 Huffman Codes: optimality 92-97, 97-101
February 28 Shannon-Fano-Elias Codes 101-103
March 3 Markov Chains, entropy rate 60-66
March 5 Arithmetic Codes 104-107
March 7 Homework solutions
Up to here Material for Test 1
March 10 Midterm Recess
March 12 Midterm Recess
March 14 Midterm Recess
March 17 LLN, Asymptotic Equipartition Property 50-51
March 19 AEP and compression; Channel capacity 52-54; 183-185
March 21 Examples of channels 185-188
March 24 Symmetric channels 189-191
March 26 Joint AEP 191-197
March 28 Shannon's Channel Coding Theorem 198-203
March 31 Fano' s inequality (2nd part of Shannon) 204-207
April 2 Discussion Test 1
April 4 no class
April 7 Feedback, Joint Source-Channel Coding 213-214, 215-218
April 9 Hamming codes 209-212
April 11 Gaussian Channel: Capacity 239-243
April 14 AEP for continuous r.v.; Achieving capacity 226-227;243-247
April 16 Parallel channels and water filling 250-256
Up to here Material for Test 2 download Test 2 from the following URL (access only within Rice, request password here) [ps] [pdf] [tex]
April 18 Review Homework; Rate distortion intro 336-339
April 21 Achievable distortion rates 340-349,357

[Outline] [Textbooks] [Grading] [Reading assignment] [Homework problems and solutions] [Tests]

(tex-source and solutions restricted to Rice University)

Homework sheet Due date (in class) Solutions
Problem Set 1 [ps] [pdf] [tex] January 24, 2003 Jan 31 [ps] [pdf] [tex]
Problem Set 2 [ps] [pdf] [tex] January 31, 2001 handed out Feb 7 [ps] [pdf] [tex]
Problem Set 3 [ps] [pdf] [tex] February 7, 2003 handed out Feb 10 [ps] [pdf] [tex]
Problem Set 4 [ps] [pdf] [tex] February 21, 2003 handed out February 28 [ps] [pdf] [tex]
Problem Set 5 [ps] [pdf] [tex] February 28, 2003 handed out March 7 [ps] [pdf] [tex]
Problem Set 6 [ps] [pdf] [tex] March 7, 2003 handed out March 7 [ps] [pdf] [tex]
Problem Set 7 [ps] [pdf] [tex] March 28, 2003 handed out April 7 [ps] [pdf] [tex]
Problem Set 8 [ps] [pdf] [tex] April 7, 2003 handed out April 11 [ps] [pdf] [tex]
Problem Set 9 [ps] [pdf] [tex] April 16, 2003 handed out April 16


Late Homework Policy

Homework is due at the beginning of class on the due date. After the due date, but before solutions are handed out, homework can be turned in for 50% credit. In this case, please slip your homework under the door of DH 2025 or bring it to class. After solutions are handed out, 0% credit will be issued. You are encouraged to work in groups for homeworks but you will hand in your own solution which you are expected to understand.

[Outline] [Textbooks] [Grading] [Reading assignment] [Homework problems and solutions] [Tests]

Quiz (15% towards the grade) February 12, 2003, 10 am AL126 In class, 30 min, (open: only two hand-written pages )
Test 1 (30%) Handed out: March 7. Due March 21, midnight. download Test 1 from the following URL (access only within Rice, request password here) [ps] [pdf] [tex] Take home, 3 hours, (open: personal notes and lecture notes)
Test 2 (30%) Handed out: April 18. Due April 25, midnight. download Test 2 from the following URL (access only within Rice, request password here) [ps] [pdf] [tex] Take home, 3 hours (open books)

Any student with a documented disability needing academic adjustments or accommodations is requested to speak with me during the first two weeks of class. All discussions will remain confidential. Students with disabilities should also contact Disabled Student Services in the Ley Student Center.
Dec 19, 2002.  Dr. Rudolf Riedi