Information theory formulas

Always non-negative; a certain event ($p_i=1$) carries 0 bits.

Average information per symbol. Take $0\log 0=0$.

Minimum 0 when one symbol has probability 1; maximum ${\log }_{2}M$ when all $M$ symbols are equiprobable.

Entropy of a two-symbol source. $H_b(0.5)=1$, symmetric about $p=0.5$, $H_b(0)=H_b(1)=0$.

For the $n$th extension of a DMS (blocks of $n$ independent symbols, $M^n$ block symbols).

Chain rule. If $X$ and $Y$ are independent, $H(X,Y)=H(X)+H(Y)$. The conditional entropy is an average: $H(Y|X)={\sum }_{x}p(x)H(Y|X=x)$.

Symmetric in $X$ and $Y$; $I(X;Y)\ge 0$, with equality exactly when $X$ and $Y$ are independent.

Here $p(x,y)=p(x)P(y|x)$ and $p(y)={\sum }_{x}p(x)P(y|x)$. Terms with $p(x,y)=0$ contribute 0.

Binary code alphabet.

A binary prefix code with lengths $l_i$ exists if and only if this holds. Every uniquely decodable binary code also satisfies it, so nothing is gained in length by giving up the prefix property. It tests lengths only; a set of codewords can obey it and still not be prefix-free.

The lower bound holds for every uniquely decodable binary code; an optimal binary prefix code (e.g. Huffman) also meets the upper bound. Using the $n$th extension, $H(X)\le {\overline{L}}_n/n<H(X)+1/n$.

Binary code. For a code alphabet of $r$ symbols, $\eta =\frac{H(X)}{\overline{L}{\log }_{2}r}$. A binary code with $\overline{L}=H$ has $\eta =1$; this needs every $p_i$ to be a power of $\frac{1}{2}$.

For a channel used $r$ times per second, the capacity is $rC$ bits/s.

Reached with equiprobable inputs. $C=1$ at $p=0$ or $p=1$, and $C=0$ at $p=\frac{1}{2}$.

From $I=H(Y)-H(Y|X)$: $H(Y|X)=H_b(p)$ for every input, and $P(Y=1)=\alpha (1-p)+(1-\alpha )p$. The maximum, at $\alpha =\frac{1}{2}$, is $1-H_b(p)$.

Each bit is either received correctly or marked as erased; reached with equiprobable inputs.

From $I=H(X)-H(X|Y)$: the input is known unless the bit is erased, so $H(X|Y)=\epsilon H_b(\alpha )$. The maximum, at $\alpha =\frac{1}{2}$, is $1-\epsilon$.

Unlike discrete entropy, it can be negative. Uniform on an interval of length $a$: $h={\log }_{2}a$. Gaussian with variance ${\sigma }^2$: $h=\frac{1}{2}{\log }_2(2\pi e{\sigma }^2)$, the largest value for any density with that variance.

Band-limited AWGN channel of bandwidth $B$ Hz. $S$ is the average received signal power and $S/N$ is the power ratio (not dB); $N=N_{0}B$ with two-sided noise PSD $N_0/2$.

Convert to a ratio before using in the law: 20 dB means 100, 30 dB means 1000.

At fixed signal power $S$, capacity grows with $B$ but saturates, because the noise power $N_{0}B$ grows too.

$E_b$ is the energy per bit. With $R=C$ and $S=E_{b}C$: $\frac{E_b}{N_0}=\frac{2^{C/B}-1}{C/B}$, which tends to $\ln 2$ as $C/B\to 0$. Below this, no reliable communication is possible at any positive rate.

For a target rate $C$, a smaller bandwidth needs an exponentially larger SNR; a larger bandwidth allows a lower SNR.