Information theory

Albert Guillen i Fàbregas, ICREA (UPF),  Alfonso Martinez (UPF) and Andreas Winter,  ICREA (UAB)
 Wed-Fri 15h-17h, from March 4, 2015
Room 101, Facultat de Matemàtiques i Estadística, UPC

The aims of this course are to review the fundamental principles and methods of information theory. Since Shannon’s landmark work in 1948, information theory has been at the core of information processing systems. Nowadays, information theory finds wide applications in
areas such as communications engineering, probability theory, statistics, physics, computer science, mathematics, economics, bioinformatics and computational neuroscience. The course will cover source coding, rate distortion, data transmission, and multiple-user information theory. The course will not only review the main results of information theory, but will also describe proof methodologies and illustrate the key tradeoffs between the underlying system
parameters. In the last third or quarter of the course, quantum information theory will be discussed, which is the generalization of information theory to systems that are described by quantum mechanics, exhibiting a large range of new phenomena, while giving rise to a theory that has at least partially strong similarity to “classical” information theory. No prior knowledge of quantum physics is required.

  1. Data Compression. Discrete memoryless sources. Lossless data compression. Entropy. Lossy data compression: rate distortion. Computation of rate distortion region.
  2. Data Transmission.  Discrete memoryless channels. Channel capacity (typical sequences). Computation of channel capacity. Error exponents (optimal decoding). Joint source-channel coding (lossless and lossy, separation vs oint). Hypothesis testing and lower bounds to error probability. Gaussian-noise channels. Differential entropy. Parallel channels.
  3. Multiple User Information Theory.  Multiple User Source Coding. Multiple Access Channel. Broadcast Channel. Relay and Interference channels.
  4. Basics of finite quantum systems. Quantum states as a new kind of information. No-cloning theorem. Teleportation.
  5. Quantum data compression. Von Neumann entropy. Typical subspace.
  6. Quantum data compression with side information at the decoder. Entanglement distillation. Quantum channel coding; quantum capacity.
  1. T. M. Cover and J. A. Thomas, Elements of Information Theory, Wiley Series in Telecommunications, 2nd Edition, 2006.
  2.  R. G. Gallager, Principles of Digital Communications, Cambridge University Press, 2008.
  3. D. J. C. MacKay, Information theory, inference, and learning algorithms, Cambridge University Press, 2003. (free online version)
  4. T. S. Han, Information Spectrum Methods in Information Theory, Springer, 2002.
  5. A. El Gamal and Y.-H. Kim, Network Information Theory, Cambridge University Press, 2011.
  6. Nielsen and Chuang, Quantum Computation and Quantum Information. Cambridge University Press, 2000
  7. A. Viterbi and K. Omura, Principles of Digital Communication and Coding, McGraw Hill, 1979. Reprinted by Dover, 2009.
  8. F. Jelinek, Probabilistic Information Theory, McGraw-Hill New York, 1968.
  9. I. Csiszár and J. Körner, Information Theory: Coding Theorems for Discrete Memoryless Systems, 2nd ed., Cambridge University Press, 2011.
  10. Mark Wilde, Quantum Information Theory. Cambridge University Press, 2013.