3F7 Information theory Tripos Revision

$ \require{amstext} \require{amsmath} \require{amssymb} \require{amsfonts} $

Full notes can be viewed over here: rendered version and LaTex Source Code

Calculation of entropy, joint entropy, conditional entropy, differential entropy for continuous pdf, relative entropy.
Remember the entropy and the mutual information non-negative
Usage of the chain rule for entropy.
Entropy is the minimum/limit of the expected length of a uniquely decodable code. “Fundamental Limit of Compression”
Fact: Conditionally Independent If X,Y conditionally independent given Z, then X and Y only independent if given Z. i.e. $ H(X|Y,Z) = H(X|Z) \qquad H(Y|X,Z) = H(Y|Z) $ since independent variable does not reduce the uncertainty(entropy)
Important Inequality: $\ln x \le x-1 $

For any estimator $\hat{X}$ such that $X-Y-\hat{X}$, the probability of error $P_e$: $ P_e=Pr(\hat{X}\not = X) \ge \frac{H(X|Y) - 1}{\log(|\mathcal{X}|)} $
If we consider the error such that $\hat{X}\not = X$, therefore we can replace the $\mathcal{X}$ by $\mathcal{X} -1 $, we would get a stronger version of the Fano’s inequality: $ P_e=Pr(\hat{X}\not = X) \ge \frac{H(X|Y) - 1}{\log(|\mathcal{X}| - 1)} $

Start by dividing the interval $[0,1)$ (this means that 0 is inclusive and 1 is exclusive) using the probability of each symbol
- Assume the symbols with probability as following: $P(a) = 0.45$, $P(b)=0.3$, $p(c)=0.25$
- Then we would divide the interval into 3 groups.
  - $[0,0.45)\quad[0.45,0.75)\quad[0.75, 1)$
  - Each interval corresponds to each of the symbol
After dividing the interval, choose the interval according to the first symbol $X_1$, if symbol a then $[0,0.45)$ etc.
Then divide the interval $[0,0.45)$ into sub-intervals with the same probability distribution.
Repeat until finishes with the last symbol $X_n$, and keep a record of the final probability interval.
Find the largest dyadic interval of the form: $ [\frac{j}{2^l}, \frac{j+1}{2^l}) $ lies inside the final probability interval.
The codeword is the binary representation of $j$, and $l$ is the code length.

The length of the binary codeword is at most $\lceil \log_2 \frac{1}{P(X_1,…,X_n)} \rceil + 1$. The expected code length L is therefore: $ L < H(X) + 2/N $ where N is the length of the sequence.

If the probability is not dyadic (integer powers of 1/2), then arithmetic uses lower number of blocks of symbols, Huffman requires longer blocks of symbols.
The complexity of the algorithm grows exponentially with k for Huffman, but linearly with arithmetic coding, therefore arithmetic coding is always more practical compared to Huffman.

Channel Capacity: $ C = \max_{P_x}I(X;Y) $
Define the Channel Rate $R$, $R < C$ to enable probability of error $P_e^{(n)} \rightarrow 0$ as $n \rightarrow 0$.
Use the channel $n$ times to transmit $k$ bits of message. $R = \frac{k}{n}$ bits/transmission. Total number of messages is $2^k=2^{nR}$
Construct the codebook of length $2^{nR}$, each codeword generated i.i.d according to the $P_X$ that maximize the mutual information. Label the codebook as $\{ X^n(1),…,X^n(2^{nR})\}.
A message $i\in\{1,2,…,2^{nR}\} is transmitted as $X^n(i)$
The receiver receives $Y^n$ and uses joint typicality decoding. It decodes the codeword $\hat{W}$ if $X^n(\hat{W})$ and $Y^n$ together is jointly typical w.r.t P_{XY}.
If no such codeword $\hat{W}$ is found, then error arises.