everything.study
6.441

Information Theory

Graduate · Historical course

Spring 2016

This is a graduate-level introduction to mathematics of information theory. We will cover both classical and modern topics, including information entropy, lossless data compression, binary hypothesis testing, channel coding, and lossy data compression.

Readings

  • T. Cover, and J. Thomas. Elements of Information Theory, Second Edition . Wiley-Interscience, 2006. ISBN: 9780471241959.
    Listed reading
Spring 2010

Topics

  • Introduction, entropy
  • Jensen’s inequality, data processing theorem, Fanos’s inequality
  • Different types of convergence, asymptotic equipartition property (AEP), typical set, joint typicality
  • Entropies of stochastic processes
  • Data compression, Kraft inequality, optimal codes
  • Huffman codes
  • Shannon-Fano-Elias codes, Slepian-Wolf
  • Channel capacity, binary symmetric and erasure channels
  • Maximizing capacity, Blahut-Arimoto
  • The channel coding theorem
  • Strong coding theorem, types of errors
  • Strong coding theorem, error exponents
  • In-class midterm
  • Fano’s inequality and the converse to the coding theorem
  • Feedback capacity
  • Joint source channel coding
  • Differential entropy, maximizing entropy
  • Additive Gaussian noise channel
  • Gaussian channels: parallel, colored noise, inter-symbol interference
  • Gaussian channels with feedback
  • Multiple access channels
  • Broadcast channels
  • In-class presentations (2 sessions)
  • Finite state Markov channels
  • Channel side information, wide-band channels

Readings

  • Reading assignments were taken from the course textbook:
    Listed reading
  • Cover, Thomas, and Joy Thomas. Elements of Information Theory . 2nd ed. New York, NY: Wiley-Interscience, 2006. ISBN: 9780471241959.
    Listed reading
  • LEC #: 1 · TOPICS: Introduction, entropy · READINGS: Chapter 1, sections 2.1 - 2.5
    Reading assignment
  • LEC #: 2 · TOPICS: Jensen’s inequality, data processing theorem, Fanos’s inequality · READINGS: Sections 2.6 - 2.8, 2.11
    Reading assignment
  • LEC #: 3 · TOPICS: Different types of convergence, asymptotic equipartition property (AEP), typical set, joint typicality · READINGS: Sections 3.1 - 3.3, 8.6
    Reading assignment
  • LEC #: 4 · TOPICS: Entropies of stochastic processes · READINGS: Chapter 4
    Reading assignment
  • LEC #: 5 · TOPICS: Data compression, Kraft inequality, optimal codes · READINGS: Sections 5.1 - 5.4
    Reading assignment
  • LEC #: 6 · TOPICS: Huffman codes · READINGS: Sections 5.5 - 5.7
    Reading assignment
  • LEC #: 7 · TOPICS: Shannon-Fano-Elias codes, Slepian-Wolf · READINGS: Sections 5.8 - 5.9, section 14 through the end of 14.4.4.1
    Reading assignment
  • LEC #: 8 · TOPICS: Channel capacity, binary symmetric and erasure channels · READINGS: Sections 8.1 - 8.3
    Reading assignment
  • LEC #: 10 · TOPICS: The channel coding theorem · READINGS: Sections 8.4, 8.7
    Reading assignment
  • LEC #: 13 · TOPICS: Fano’s inequality and the converse to the coding theorem · READINGS: Section 8.9
    Reading assignment
  • LEC #: 14 · TOPICS: Feedback capacity · READINGS: Section 8.12
    Reading assignment
  • LEC #: 15 · TOPICS: Joint source channel coding · READINGS: Section 8.13
    Reading assignment
  • LEC #: 16 · TOPICS: Differential entropy, maximizing entropy · READINGS: Chapter 9, sections 11.1 - 11.6
    Reading assignment
  • LEC #: 17 · TOPICS: Additive Gaussian noise channel · READINGS: Sections 10.1 - 10.3
    Reading assignment
  • LEC #: 18 · TOPICS: Gaussian channels: parallel, colored noise, inter-symbol interference · READINGS: Sections 10.4 - 10.5
    Reading assignment
  • LEC #: 19 · TOPICS: Gaussian channels with feedback · READINGS: Section 10.6
    Reading assignment
  • LEC #: 20 · TOPICS: Multiple access channels · READINGS: Sections 14.1 - 14.3
    Reading assignment
  • LEC #: 21 · TOPICS: Broadcast channels · READINGS: Section 14.6
    Reading assignment
  • [* Lectures 4-5] Elias, Peter. “Predictive Coding: Part I.” IRE Transactions: Information Theory 1, no. 16 (1955): 16-24.
    Listed reading
  • [* Lecture 6] Huffman, David. “A Method for the Construction of Minimum-Redundancy Codes.” Proceedings of the IRE 40, no. 9 (1952): 1098-1101.
    Listed reading
  • [** Lecture 7] Slepian, David, and Jack Wolf. “Noiseless Coding of Correlated Information Sources.” IEEE Transactions on Information Theory 19, no. 4 (1973): 471-480.
    Listed reading
  • [** Lecture 7] Elias, Peter. “Predictive Coding: Part II.” IRE Transactions: Information Theory 1, no. 16 (1955): 24-33.
    Listed reading
  • [** Lecture 7] Gallagher, Robert. “Variations on a Theme by Huffman.” IEEE Transactions on Information Theory 24, no. 6 (1978): 668-674.
    Listed reading
  • [** Lectures 10-12] Gallagher, Robert. “A Simple Derivation of the Coding Theorem and Some Applications.” IEEE Transactions on Information Theory 11, no. 1 (1965): 3-18.
    Listed reading
  • [* Lectures 14, 16-20] Cover, Thomas. “The Role of Feedback in Communication.” In Performance Limits in Communication Theory and Practice . Edited by J. K. Skwirzynski. New York, NY: Springer, 1988, pp. 225-235. ISBN: 9789024736959.
    Listed reading
  • [** Lecture 20] El Gamal, Abbas, and Thomas Cover. “Multiple User Information Theory.” Proceedings of the IEEE 68, no. 12 (1980): 1466-1483.
    Listed reading
  • [** Lecture 20] Cover, Thomas, Abbas El Gamal, and Masoud Salehi. “Multiple Access Channels with Arbitrarily Correlated Sources.” IEEE Transactions on Information Theory 26, no. 6 (1980): 648-657.
    Listed reading
  • [** Lecture 20] Gallagher, Robert. “A Perspective on Multiaccess Channels.” IEEE Transactions on Information Theory 31, no. 2 (1985): 124-142.
    Listed reading
  • [** Lecture 21] Cover, Thomas. “Comments on Broadcast Channels.” IEEE Transactions on Information Theory 44, no. 6 (1998): 2524-2530.
    Listed reading
  • [** Lecture 21] Bergmans, Patrick, and Thomas Cover. “Cooperative Broadcasting.” IEEE Transactions on Information Theory 20, no. 3 (1974): 317-324.
    Listed reading
  • [*** Lecture 21] Weingarten, Hanan, Yosef Steinberg, and Shlomo Shamai (Shitz). “The Capacity Region of the Gaussian Multiple-Input Multiple-Output Broadcast Channel.” IEEE Transactions on Information Theory 52, no. 9 (2006): 3936-3964.
    Listed reading
  • [** Lectures 21-22] Jindal, Nihar, Sriram Vishwanath, and Andrea Goldsmith. “On the Duality of Gaussian Multiple-Access and Broadcast Channels.” IEEE Transactions on Information Theory 50, no. 5 (2004): 768-783.
    Listed reading
  • [*** Lectures 22-23] Goldsmith, Andrea, and Pravin Varaiya. “Capacity, Mutual Information, and Coding for Finite-State Markov Channels.” IEEE Transactions on Information Theory 42, no. 3 (1996): 868-886.
    Listed reading
  • [*** Lecture 23] Médard, Muriel, and Robert Gallagher. “Bandwidth Scaling for Fading Multipath Channels.” IEEE Transactions on Information Theory 48, no. 4 (2002): 840-852.
    Listed reading
  • Gallagher, Robert. Information Theory and Reliable Communication . New York, NY: Wiley, 1968. ISBN: 9780471290483.
    Recommended
Sources