# Information Theory

"The fundamental problem of communication is that of reproducing at one point either exactly or approximately a message selected at another point. Frequently the messages have meaning; that is, they refer to or are correlated according to some system with certain physical or conceptual entities. These semantic aspects of communication are irrelevant to the engineering problem. The significant aspect is that the actual message is one selected from a set of possible messages" (Shannon, 1948).

## Introduction

The Science of Information: From Language to Black Holes (The Great Courses)

Gleick J., The Information: A History, a Theory, a Flood. Vintage books. 2012. (book, talk)

Dasher: information-efficient text entry (talk and paper by David J. C. MacKay)

## Video Lectures

Jeff Bilmes's lectures: Information Theory I and Information Theory II

Gallager: Principles of Digital Communications I and Principles of Digital Communications II

MacKay: Information Theory, Pattern Recognition, and Neural Networks

## Course Schedule and Reading

Introduction. What is information? How to measure it? Shannon model for communication. (notebook English entropy)

Review: Stochastic Process.

Entropy, its properties and relations. Shannon proof of entropy equation (see Shannon, 1948, appendix).

Conditional Entropy, Joint Entropy, Mutual Information, Chain Rule. Bounds on Entropy (see Cover, T. M. and Thomas, J. A., 2012).

Kullback-Leibler Divergence, Jensen Inequality, Non-negativity of the Mutual Information (see Cover, T. M. and Thomas, J. A., 2012).

Information Measure, correspondence between Shannon’s information measures and set theory (see Yeung R. W. 2008, chap. 3).

Log Sum Inequality, Concavity of Entropy, Implications to Mutual Information.

Data Processing Inequality, Markov Chain.

Statistics, Sufficient Statistics.

Fano Inequality.

Asymptotic Equipartition Property, Typical Set. Properties, Typical Sequences, Coding for the Typical Set.

Method of Types, Type, Type Class. Bounds, Typical Set Revisited.

Universal Coding, (M,n) Code.

Probability Simplex.

Shannon Coding Theorem.

Stochastic Processes, Markov Process, Random Walk, Cesáro Mean.

Source Coding, Kraft Inequality, Optimal Code, Shannon Code, Huffman Code, Shannon-Fano-Elias Code.

Arithmetic Coding, Lempel Ziv.

Channel Capacity, Channel Models.

Shannon Noisy-Channel Coding Theorem.

Error Correction, Repeating Code, Parity Check, Hamming Codes

## Bibliography

Cover, T. M., and Thomas, J. A., Elements of Information Theory, Wiley, 2012. (google books, archive)

Shannon, C.E. and Weaver, W., The Mathematical Theory of Communication, Bell System Technical Journal, 1948. (archive)

MacKay, D. J. C., Information Theory, Inference and Learning Algorithms, Cambridge University Press, 2003. (inference, archive)

Gallager, R. G., Principles of Digital Communication. Cambridge. 2008. (mit)

Yeung, R. W., Information Theory and Network Coding. Springer. 2008. (draft)

Yeung, R. W., A First Course in Information Theory. Springer. 2012. (draft)

Pierce, J. R., An Introduction to Information Theory: Symbols, Signals and Noise. Dover. 2012. (google books)

Gallager, R. G., Information Theory and Reliable Communication. Wiley. 1968. (archive)

Hamming, W. H., Coding and Information Theory, Prentice Hall, 1986.

## Suggested readings

Shannon, C. E., Prediction and Entropy of Printed English, Bell System Technical Journal, 30: 1, January 1951. (archive)

Verdú, V., Fifty Years of Shannon Theory, IEEE Transactions on Information Theory, 44(6), October 1998. (IEEE)

Csiszar , I., The method of types, IEEE Transactions on Information Theory, 44(6), October 1998. (IEEE)

Wyner, A. D., Ziv, J., Wyner, J. A. On the Role of Pattern Matching in Information Theory, IEEE Transactions on Information Theory, 44(6), October 1998. (IEEE)

Lapidoth, A., Narayan, P., Reliable Communication Under Channel Uncertainty, IEEE Transactions on Information Theory, 44(6), October 1998. (IEEE)

Gray, R., Neuhoff, D. L., Quantization, IEEE Transactions on Information Theory, 44(6), October 1998. (IEEE)

## Scripts

random numbers (notebook, portuguese)

frequency of occurrence of letters and words in a text, entropy of words (bash - notebook, script, asciinema (bash), asciinema (octave), asciinema (R), svg)

>> tip for Windows 10 users: install Windows Subsystem for Linux.

## On The Media

11 Nov 2019 - Andrey Markov & Claude Shannon Counted Letters to Build the First Language-Generation Models

22 Aug 2018 - The Desperate Quest for Genomic Compression Algorithms

13 Jan 2018 - Para Claude Shannon, é brincando que se trabalha, mostra livro

29 Apr 2016 - Claude Shannon: The Juggling Unicyclist Who Pedaled Us Into the Digital Age

20 Apr 2016 - The Shannon Limit - Bell Labs - Future Impossible

16 Jan 2008 - Claude Shannon - Father of the Information Age