Information Theory
Theory of communication, entropy measures, data compression, and channel coding.
"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."
Course Introduction & Overview
- The Shannon Centennial: 1100100 years of bits
- Journey into information theory (Khan Academy)
- Journey into information theory | Computer Science
- Cautionary Tales – Fritterin’ Away Genius ▶️
- 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)
- The Information: A History, a Theory, a Flood (James Gleick)
- Reinventing Entropy , But what is cross-entropy? (3brown1blue)
- Hamming Codes ( 3brown1blue) part 1 , part 2
- Informação em quadrinhos ( webtoons , funktoon )
- Como Medimos a Informação e a Incerteza no Mundo ( substack )
Asymptotic Equipartition Property (AEP)
- Nem Tudo que Ă© PossĂvel Ă© Provável ( substack )
Video Lectures Series
Complete video lecture collections from leading researchers and courses:
- my lectures (portuguese)
- 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, Topics & Readings
- 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
Recommended 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 & Media
- 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 )
- 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
Scripts & Interactive Notebooks
- 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 .
- analysis of 2-grams in English ( notebook )
- analysis of n-grams and types in English ( notebook )
- markov chain ( notebook ), Garkov (fun)
- text compression using huffman and lz ( notebook )
- rules (portuguese)
- slides (portuguese)
- video lectures (portuguese)
- homework (portuguese)
- old exams (portuguese)
- equation sheet