• Analog vs Digital Signal
• bit (signal processing)
  • Source-Channel Separation Theorem

Clarke’s Third Law

Sufficiently advance technology is indistinguishable from magic

information

Information is the amount of surprise a message provides.

Shannon (1948): a mathematical theory for communication.

information value

The information value, or entropy, of a information source is its probability-weighted average surprise of all possible outcomes:

\begin{equation} H(X) = \sum_{x \in X}^{} s(P(X=x)) P(X=x) \end{equation}

properties of entropy

• entropy is positive: \(H(x) \geq 0\)
• entropy of uniform: for \(M \sim CatUni[1, …, n]\), \(p_{i} = \frac{1}{|M|} = \frac{1}{n}\), and \(H(M) = \log_{2} |M| = \log_{2} n\)
• entropy is bounded: \(0 \leq H(X) \leq H(M)\) where \(|X| = |M|\) and \(M \sim CatUni[1 … n]\) (“uniform distribution has the highest entropy”); we will reach the upper bound IFF \(X\) is uniformly distributed.

binary entropy function

For some binary outcome \(X \in \{1,2\}\), where \(P(x=1) = p_1\), \(P(X_2 = 2) = 1-p_1\). We can write:

joint entropy

Suppose we have two information sources; joint entropy is the measure of joint surprise when we are defined over more than one information source.

For a pair of random variables, \(X, Y\), their joint entropy is defined over a new random variable of \(X \cup Y\).

\begin{equation} H(x,y) = \sum_{i \in X}^{} \sum_{j \in Y}^{} P(X=i, Y=j) \log_{2} \qty(\frac{1}{P(X=i, Y=j)}) \end{equation}

If \(X \perp Y\), we can write \(H(x,y) = H(x)+H(y)\) (shown below.) Further, we have for all \(X\) and \(Y\), \(H(x,y) \leq H(x) + H(y)\) because you can never be more surprised than if you got two completely independent pieces of information.

We want a way of generating a Prefix-Free code for any Source Coding problem.

Huffman Coding

See Huffman Coding

Diadic Source

Diadic Source is an information source for which the probability of occurrence for each symbol is a member of \(\frac{1}{2^{n}}\) for integer \(n\).

That is, the probability of each symbol is in powers of \(\frac{1}{2}\).

In THESE sources, Huffman Coding will always result in a code that communicates the information in the same number of bits as the entropy of the source.

Non-IID Sequence Can Have Smaller Entropy

For sequences that are not IID, we may have:

\begin{equation} H(X_1, \dots, X_{n)} \ll \sum_{j=1}^{n} H(X_{j}) \end{equation}

This means that for very dependent sequences:

\begin{equation} \lim_{n \to \infty} \frac{H(X_1, \dots, X_{n})}{n} \ll \sum_{j=1}^{n}H(x_{j}) \end{equation}

so to measure how good our compression is, we should use this.

signal

a signal is, mathematically, just a function.

\begin{equation} f: \mathbb{R}^{n} \to \mathbb{R}^{m} \end{equation}

whereby the input is space (time, coordinates, etc.) and the output is the “signal” (pressure, level of gray, RGB, etc.)