Noam's Website About Software

Back to wiki: math , cs

Information Theory Overview

Roadmap based on youtube introductory series.

Compression (efficiency, source coding) Error Correction (reliability, channel coding)
Information Theory (Math) Losless: source coding theorem, Kraft-McMillan inequality
Lossy: rate distortion theorem
Coding Methods (algorithms) Symbol Code: Huffman codes Hamming codes, BCH codes, Turbocodes, Gallager codes
Stream Codes: arithmetic coding


How many bits are needed to encode information:


Where $p$ is the probability of the event. For example, the number of bits needed for encoding the value of the result of a coin flip ($p=\frac{1}{2}$) is 1.


How many bits should be needed to send a piece of information?

$$H(X) = \sum p_{i} (log_{2}( \frac{1}{p_{1}} )) = E(I(X))$$

Binary Tree Encoding (Huffman)

$$p\_{i}$$ Encoded
"A" $\frac{1}{3}$ 11
"B" $\frac{1}{2}$ 0
"C" $\frac{1}{12}$ 100
"C" $\frac{1}{12}$ 101

Tags: informationTheory