Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

MAT3350 Introduction to Information Theory

Prof. Kaiming SHEN @ SSE

Grades:

  • Assignments / Quiz (20%)
  • Midterm Exam (40%)
  • Final Exam (40%)

Reference Book: T. Cover & J. Thomas: Elements of Information Theory 2nd Ed.

Chapter 1: Introduction 简介

1.1 Intergration of Information

Bit: $\{0, 1\}$

Information is the minimum number of bits ($0$ or $1$) to describe a random variable.

信息即用描述一个随机变量所使用 bits 的最小数量。

e.g. Weather Forecast

$$ X = \begin{cases} \text{rain}\ &50\% \ &0 , \\ \text{shine}\ &50\% \ &1 \end{cases} $$

From weatherman, we can learn value of $X$. And $X$ contains $1$ bit of information.

我们认为这个随机变量 $X$ 包含 $1$ bit 的信息。

假设我们现在有 $8$ 种不同的天气，每个概率相同，我们可以用 $X = \{000, 001, \cdots, 111\}$ 来表示天气。那么我们认为 $X$ 包含 $3$ bit 的信息，因为其最少可以用 $3$ 位 bit 来表示。

e.g. Horse Race (sp.)

$$ X = \begin{cases} A &\frac{1}{2} &000 &0 \\ B &\frac{1}{4} &001 &10 \\ C &\frac{1}{8} &010 &110 \\ D &\frac{1}{16} &\cdots &1110 \\ E &\frac{1}{64} &\cdots &111100 \\ F &\frac{1}{64} &\cdots &111101 \\ G &\frac{1}{64} &\cdots &111110 \\ H &\frac{1}{64} &\cdots &111111 \end{cases} $$

Information of $X=1 \times \frac{1}{2} + 2 \times \frac{1}{4} + 3 \times \frac{1}{8} + 4 \times \frac{1}{16} + 6 \times \frac{1}{64} \times 4 = 2 $ bits

1.2 Information Transmission over Channel

$$ X \rightarrow \text{Channel} \rightarrow Y $$

Channel: $P(y|x)$，就是一个条件概率，用来描述 $Y$ 是如何随着 $X$ 变化的。

Channel Capacity($C$) is the maximum number of bits that can be "reliably" transimitted from X to Y.

通道容量表示一个通信信道每次使用最多能够稳定传输多少信息。

1.3 Information Theory

Information Theory answers and questions:

  1. What is the minimum number of bits to describe $X$?

    Ans: Entropy $H(X)$ ... Data compression

  2. What is the maximum numberof bits that can be reliably transmitted over channel?

    Ans: Mutual info $I(X;Y)$ ... Channel Capacity.

Chapter 2: Entropy 熵

2.1 Basics

Def. Let $X$ be a discrete random variable, e.g. $X = \{a, b, c\}$, then: $$ X = \begin{cases} a, & p_1\\ b, & p_2\\ c, & p_3 \end{cases} $$ Which is easy to describe using probability mass function (PMF).

Def. The entropy of $X$ is $$ H(X) = \sum_x p(x) \log \frac{1}{p(x)} $$

When $\log$ is in base $2$, $H(X)$ is in "bit".
When $\log$ is in base $e$, $H(X)$ is in "nat".

$$ \log_e a = \ln a = \frac{\log_2 a}{\log_2 e} $$

$H(X)$ in nats $= \sum p(x) \log_e \frac{1}{p(x)} = \sum p(x) \left(\log_2 \frac{1}{p(x)}\right) \frac{1}{\log_2 e} = \frac{1}{\log_2 e} H(X)$ in bits.

Recall: $E[f(x)] = \sum_x p(x) f(x)$ (数学期望)

Note: $H(X) = E[\log{\frac{1}{p(x)}}] = -E[\log{p(x)}] $

Theorem: $H(X) \geq 0$
Proof: $0 \leq p(x) \leq 1 \Rightarrow \frac{1}{p(x)} \geq 1 \Rightarrow \log{\frac{1}{p(x)}} \geq 0 \Rightarrow H(X) \geq 0$

Theorem: Jensen's Inequality. For a $X = \{1, 2, \cdots, m\}$ $$ X = \begin{cases} 1, &p_1 \\ 2, &p_2 \\ \ \vdots \\ m, &p_m \end{cases} $$ We have $$ H(X) \leq \log m $$ Where "$=$" hold iff $X \sim \text{Uniform}$

And now we established the lower bound and upper bound of entropy: $$ 0 \leq H(X) \leq \log m $$

2.2 Connection to Data Compression

Shannon showed that $H(X)$ is the minimum number of bits to describe $X$. (will prove in the future)

e.g. $$ X = \begin{cases} 0 \quad 100\% \\ 1 \quad 0\% \end{cases} $$ And we can have: $$ \begin{aligned} H(X) = & 1 \times \log \frac{1}{1} + 0 \times \log \frac{1}{0} \\ = & 0 \end{aligned} $$ Since: $$ \lim_{x \to 0^+} x \log \frac{1}{x} = \lim_{x \to 0^+} -x \log x = \lim_{x \to 0^+} \frac{-\log x}{1/x} = \lim_{x \to 0^+}x = 0 $$

Another e.g.:

Consider $X_1, X_2, \cdots, X_{100}$. Each $X_i = \begin{cases}0 \quad 1 \% \\ 1 \quad 99 \% \end{cases}$
For a "typical" $(X_1, X_2, \cdots, X_{100})$, only one $X_i = 0$, rest are all $1$. $\Rightarrow$ Use $\log 100$ to describe $(X_1, X_2, \cdots, X_{100})$.

2.3 Connectoin to Computer Science

Def. Kolmogorov complexity $K(X)$ is the length of the shortest program that makes computer (Turing machine) print $X$.

e.g. $K(\pi) < \infty$
"Print $3.1415926\cdots$" has length $=\infty$
"Print the value between a circle circumference and its diameter" has lenght = $c$

这里可以理解为，虽然直接输出 $\pi$ 是无限的，但是一个生成 $\pi$ 的程序可以是有限的，即有$K(\pi) < \infty$

e.g. $K(101010\cdots10) \leq 2 + c'$
Suppose $10$ repeats $n$ times, "print $101010\cdots10$ has length $=2n+c$
But "print $10$ for $n$ times has length $=2\times 1 + c'$

Chapter 3: Condition Entropy

3.1 Basics

Recall: $H(X)$ is the minimum number of bits to describe $X$, which measures the uncertainty of $X$.

Def. For $(X,Y) \sim F(X,Y)$, the joint entropy: $$ \begin{aligned} H(X,Y) &= \sum_{(x, y)} p(x, y) \log \frac{1}{p(x, y)} \\ &= E\left[ \log \frac{1}{p(x,y)} \right] \end{aligned} $$ means the total uncertainty of $X$ and $Y$.

Def. Conditional entropy of $X$ with $Y$ known to be fixed at $y$ is: $$ \begin{aligned} H(X | Y=y) &= \sum_x p(x|y) \log \frac{1}{p(x|y)} \\ &= E_x \left[ \log \frac{1}{p(x|y)} \right] \end{aligned} $$ measures the remaining uncertainty of $X$ after knowing $Y=y$.

Def. Conditional entropy of $X$ with $Y$ known is: $$ \begin{aligned} H(X|Y) &= \sum_y H(X|Y=y) \cdot p(y) \\ &= \sum_{x, y} p(x,y) \log \frac{1}{p(x|y)} \end{aligned} $$ measures the remaining uncertainty of $X$ after $Y$ is known.

e.g.

3.2 Properties of $H(X|Y)$

Entropy Chain Rule: $$ H(X, Y) = H(Y) + H(X|Y) $$ Intuition: Total uncertainty of $(X,Y)=$ uncertatinty of $Y$ alone $+$ remaining uncertainty of $X$ after knowing $Y$.

这里的加号可以理解为：熵是信息量，分两步说，第一步先告诉他 $Y$ 是什么，即有 $H(Y)$ 个 bit，第二步是已经知道 $Y$ 的情况下，在告诉他 $X$ 是什么，即 $H(X|Y)$ 个 bit，两步获得的信息量是相加的

By symmetry, $H(X,Y) = H(X) + H(Y|X)$ is also correct.

Extension: Chain rule for joint entropy: $$ H(X_1, X_2, \cdots, X_n) = H(X_1) + H(X_2 | X_1) + H(X_3 | (X_1, X_2)) + \cdots + H(X_n | (X_1, X_2, \cdots X_{n-1})) $$

Theorem: If $X$ and $Y$ are independent (no overlay), then: $$ H(X, Y) = H(X) + H(Y) $$ And we have: $$ H(X|Y) = H(X) \Leftrightarrow X \text{ and } Y \text{ are independent} \\ H(X|Y) = H(Y) \Leftrightarrow X \text{ and } Y \text{ are independent} $$

3.3 Information never hurts

Theorem: Knowing $Y$ will not hurt our existing knowledge of $X$ $$ H(X|Y) \leq H(X) $$

So when in data compression, we can have:

e.g. Consider a probability table.

$X\backslash Y$$0$$1$
$0$$0.45$$0.05$
$1$$0.05$$0.45$

And we have $$ X = \begin{cases} 0 \quad 50\% \\ 1 \quad 50\% \end{cases} $$

Without $Y$, we need $H(X) = 1$ bit to describe $X$.

Now $Y$ is provided, we can use the following equations: $$ X \oplus Y = Z \\ Y \oplus Z = X $$ Note that: $$ Z = \begin{cases} 0 \quad 90\% \\ 1 \quad 10\% \end{cases} $$ And we have $H(Z) < H(X)$, so the main idea is compressing $Z$ instead of $X$, and then recover $X$ with XOR.

e.g.

Consider $n$ balls, one ball is odd in that it is lighter or heavier than any other ball. Giving only one balance to compare two balls each time. How many times do we need to figure out which ball is odd?

Chapter 4: Mutual Information

4.1 Basics

Def. Mutual Information $$ \begin{aligned} I(X; Y) &= H(X) - H(X|Y) \\ &= H(X) + H(Y) - H(X, Y) \\ &= \sum_{x, y} p(x, y) \log \frac{p(x,y)}{p(x)p(y)} \\ &= E_{x,y} \left[ \log \frac{p(x,y)}{p(x)p(y)} \right] \\ \end{aligned} $$

Consider X -> Channel -> Y, then $I(X;Y)$ is the maximum number of bits reliably transmitted by our channel.

Now consider the venn graph below:

We have $$ \begin{aligned} &H(X|Y) = A \\ &H(Y|X) = C \\ &I(X;Y) = B \\ &H(X) = A+B \\ &H(Y) = B+C \\ &H(X, Y) = A+B+C \end{aligned} $$

4.2 KL Divergence

Def. For two distributions $p(x), q(x)$, their KL Divergence: $$ D(p || q) = \sum_x p(x) \log \frac{p(x)}{q(x)} $$

$D(p || q)$ gives "distance"(or "difference") between $p$ and $q$. BUT $D(p||q) \not= D(q||p)$

Def. Cross Entropy $$ CE(p,q) = \sum_x p(x) \log \frac{1}{q(x)} $$

Theorem: $$ CE(p,q) = H(p) + D(p||q) $$

CE（交叉熵）其实就是，比如在机器学习中，模型的理解 $q$ 和真实世界 $p$ 差得有多远，真实世界按照 $p$ 产生数据，但我用模型 $q$ 去预测它，平均会有多惊讶（可以作为 loss）

KL Divergence（KL 散度）就是因为用了错误模型 $q$，额外多付出了多少代价

4.3 Hypothesis Testing

Let $X_1, X_2, \cdots, X_n$ be independent random variables, but not sure which is their distribution, $p(x)$ or $q(x)$?

Two hypothesis:

  1. $H_1: X_i \sim p(x)$
  2. $H_2: X_i \sim q(x)$

Q: How to use $X_1, X_2, \cdots, X_n$ to decide which is true?
A: If $p(x)$ is more likely to produce $X_1, X_2, \cdots, X_n$, then $H_1$ is true, otherwise $H_2$ is true.

Def. Log-likelihood Ratoi: $$ LLR = \frac{1}{n} \log \frac{p(x_1, x_2, \cdots, x_n)}{q(x_1, x_2, \cdots, x_n)} $$ So the hypothesis test is:

  1. If $LLR > 0$, $p(x)$ will be the distribution
  2. If $LLR < 0$, $q(x)$ will be the distribution

Chapter 5: Conditional Mutual Information

5.1 Basics

Def. For $(X,Y,Z) \sim p(x,y,z)$, the conditional mutual information is $$ I(X;Y|Z)=H(X|Z)-H(X|Y,Z). $$

Equivalent forms: $$ \begin{aligned} I(X;Y|Z) &=H(Y|Z)-H(Y|X,Z) \\ &=H(X|Z)+H(Y|Z)-H(X,Y|Z) \\ &=H(X,Z)+H(Y,Z)-H(Z)-H(X,Y,Z). \end{aligned} $$

Interpretation:

  • $H(X|Z)$: uncertainty of $X$ after side information $Z$ is known.
  • $I(X;Y|Z)$: additional information about $X$ learned from $Y$ after $Z$ is already known.

先知道 $Z$，再看 $Y$。$I(X;Y|Z)$ 问的是：在已经知道 $Z$ 的情况下，$Y$ 还能额外告诉我们多少关于 $X$ 的信息。

Theorem: $$ I(X;Y|Z)\geq 0. $$ Equality holds iff $X$ and $Y$ are conditionally independent given $Z$: $$ p(x,y|z)=p(x|z)p(y|z). $$

Important warning: $$ I(X;Y|Z) $$ can be larger or smaller than $I(X;Y)$.

Example intuition:

  • If $Z$ is pure noise independent of everything, conditioning on $Z$ does not help much.
  • If $Z$ helps remove noise from $Y$, then $I(X;Y|Z)$ can become larger.
  • If $Z$ already reveals $X$, then $I(X;Y|Z)=0$.

5.2 Chain Rule for Mutual Information

Theorem: $$ I(X_1,\cdots,X_n;Y) =I(X_1;Y)+I(X_2;Y|X_1)+\cdots+I(X_n;Y|X_1,\cdots,X_{n-1}). $$

Interpretation:

Instead of decoding all users together, we may decode one by one:

$$ (X_1,\cdots,X_n)\rightarrow \text{Channel}\rightarrow Y. $$

First decode $X_1$, then subtract the known part from $Y$, then decode $X_2$, and so on.

总信息量可以拆成“第一层信息 + 已知第一层后的第二层信息 + 已知前两层后的第三层信息 + ...”。

5.3 Markov Chain and Data Processing

Def. $X\to Y\to Z$ is a Markov chain if $$ p(x,y,z)=p(x)p(y|x)p(z|y). $$

Equivalently, $$ p(z|x,y)=p(z|y). $$

Intuition:

$$ X\to Y\to Z $$ means $Z$ depends on $X$ only through $Y$.

Theorem: If $X\to Y\to Z$, then $Z\to Y\to X$ is also a Markov chain.

Theorem: If $X\to Y\to Z$, then $X$ and $Z$ are conditionally independent given $Y$: $$ I(X;Z|Y)=0. $$

Theorem (Data Processing Inequality): If $$ X\to Y\to Z, $$ then $$ I(X;Z)\leq I(X;Y). $$

Also, $$ I(X;Z)\leq I(Y;Z). $$

信息经过处理不会凭空变多。$X$ 先告诉 $Y$，$Y$ 再告诉 $Z$，所以 $Z$ 对 $X$ 的了解不可能超过 $Y$ 对 $X$ 的了解。

Useful identity for proof: $$ I(X;Y,Z)=I(X;Z)+I(X;Y|Z) =I(X;Y)+I(X;Z|Y). $$

For Markov chain $X\to Y\to Z$, since $I(X;Z|Y)=0$, $$ I(X;Z)+I(X;Y|Z)=I(X;Y). $$

Chapter 6: Three-Party Mutual Information

6.1 Basics

Def. For $(X,Y,Z)\sim p(x,y,z)$, the three-party mutual information is $$ I(X;Y;Z)=I(X;Y)-I(X;Y|Z). $$

Equivalent forms: $$ \begin{aligned} I(X;Y;Z) &=H(X)+H(Y)+H(Z) \\ &\quad -H(X,Y)-H(X,Z)-H(Y,Z)+H(X,Y,Z). \end{aligned} $$

Symmetric identities: $$ I(X;Y;Z)=I(X;Z)-I(X;Z|Y)=I(Y;Z)-I(Y;Z|X). $$

Important warning: $$ I(X;Y)\geq 0,\qquad I(X;Y|Z)\geq 0, $$ but $$ I(X;Y;Z) $$ can be positive, zero, or negative.

two-party MI 和 conditional MI 都不会负；three-party MI 不一样，它不是一个普通的“信息量”，而更像三者重叠关系的代数量。

6.2 Information Theoretic Security

Let

  • $X$ be plaintext,
  • $K$ be key,
  • $Y$ be ciphertext.

Encryption: $$ Y=f(X,K). $$

Decryption: $$ \hat X=g(Y,K). $$

Def. A system has perfect secrecy if $$ I(X;Y)=0. $$

This means the ciphertext reveals nothing about the plaintext without the key.

Def. The system is perfectly decodable if $$ H(X|Y,K)=0. $$

This means once both $Y$ and $K$ are known, $X$ can be recovered exactly.

Example (One-Time Pad):

Let $$ X\sim \operatorname{Bern}\left(\frac12\right),\qquad K\sim \operatorname{Bern}\left(\frac12\right) $$ independently, and define $$ Y=X\oplus K. $$

Then $$ \hat X=Y\oplus K. $$

So $$ I(X;Y)=0,\qquad H(X|Y,K)=0. $$

Theorem (Shannon's Perfect Secrecy Limit): If $$ I(X;Y)=0 $$ and $$ H(X|Y,K)=0, $$ then $$ H(K)\geq H(X). $$

想做到完全安全，key 的不确定性至少要和 message 一样大。One-time pad 安全，但 key 必须和 plaintext 一样长，所以实际很不方便。

Chapter 7: Entropy Rate

7.1 Motivation

For iid random variables $X_1,\cdots,X_n$, $$ H(X_1,\cdots,X_n)=\sum_{i=1}^n H(X_i)=nH(X_1). $$

But natural language, music, text, etc. are not iid. Later symbols depend on previous symbols.

Def. For a stochastic process $\mathcal X={X_i}$, the entropy rate is $$ H(\mathcal X)=\lim_{n\to\infty}\frac1n H(X_1,\cdots,X_n), $$ if the limit exists.

Examples:

If $X_i$ are iid, then $$ H(\mathcal X)=H(X_1). $$

If $X_i=X_1$ for all $i$, then $$ H(\mathcal X)=\lim_{n\to\infty}\frac1n H(X_1)=0. $$

entropy rate 是“平均每个新符号还带来多少新信息”。如果后面全是重复，平均新信息趋近于 0。

7.2 Stationary Stochastic Process

Def. A stochastic process $\mathcal X={X_i}$ is stationary if shifting time does not change the joint distribution: $$ p(X_1,\cdots,X_n)=p(X_{1+k},\cdots,X_{n+k}) $$ for all $n,k$.

Theorem:

For stationary $\mathcal X={X_i}$, $$ \lim_{n\to\infty} H(X_n|X_1,\cdots,X_{n-1}) $$ exists.

Moreover, $$ H(\mathcal X) =\lim_{n\to\infty}\frac1n H(X_1,\cdots,X_n) =\lim_{n\to\infty}H(X_n|X_1,\cdots,X_{n-1}). $$

Key idea:

Let $$ a_n=H(X_n|X_1,\cdots,X_{n-1}). $$

For stationary processes, $a_n$ is non-increasing: $$ a_{n+1}\leq a_n. $$

Also, $$ H(X_1,\cdots,X_n)=\sum_{i=1}^n a_i. $$

So the average converges to the same limit.

7.3 Markov Process

Def. A stochastic process is Markov if $$ p(X_n|X_1,\cdots,X_{n-1})=p(X_n|X_{n-1}). $$

That is, the future depends on the past only through the present.

Theorem:

If $\mathcal X$ is stationary and Markov, then $$ H(\mathcal X)=H(X_2|X_1). $$

If the stationary distribution is $\pi_i$ and transition matrix is $P_{ij}$, then $$ H(\mathcal X) =\sum_i \pi_i H(P_{i,\cdot}) =-\sum_i\sum_j \pi_i P_{ij}\log P_{ij}. $$

Example:

If $$ X_{n+1}=aX_n+Z_n, $$ where $Z_n$ are iid and independent of the past, then $$ H(\mathcal X)=H(X_2|X_1)=H(Z_1). $$

给定 $X_n$ 后，$X_{n+1}$ 的不确定性只来自新的 noise $Z_n$。

Chapter 8: AEP

8.1 LLN and AEP

Theorem (Law of Large Numbers):

For iid $X_i\sim p(x)$, $$ \frac1n\sum_{i=1}^n X_i \to E[X] $$ in probability.

Theorem (Asymptotic Equipartition Property, AEP):

For iid $X_i\sim p(x)$, $$ -\frac1n\log p(X_1,\cdots,X_n)\to H(X) $$ in probability.

Proof idea: $$ p(X_1,\cdots,X_n)=\prod_{i=1}^n p(X_i), $$ so $$ -\frac1n\log p(X_1,\cdots,X_n) =\frac1n\sum_{i=1}^n \log\frac1{p(X_i)}. $$

By LLN, this converges to $$ E\left[\log\frac1{p(X)}\right]=H(X). $$

长序列的概率通常差不多是 $2^{-nH(X)}$。所以虽然每个具体序列概率不同，但“大多数概率质量”集中在一批概率差不多的序列上。

8.2 Typical Set

Def. For $\epsilon>0$, a sequence $(x_1,\cdots,x_n)$ is $\epsilon$-typical if $$ \left|-\frac1n\log p(x_1,\cdots,x_n)-H(X)\right|\leq \epsilon. $$

Def. The typical set is $$ A_\epsilon^{(n)} =\left\{x^n: \left|-\frac1n\log p(x^n)-H(X)\right|\leq \epsilon \right\}. $$

For any $x^n\in A_\epsilon^{(n)}$, $$ 2^{-n[H(X)+\epsilon]} \leq p(x^n)\leq 2^{-n[H(X)-\epsilon]}. $$

Theorem:

For any $\delta>0$, for sufficiently large $n$, $$ \Pr\{X^n\in A_\epsilon^{(n)}\}>1-\delta. $$

Theorem (Size of Typical Set):

For any $\delta>0$, for sufficiently large $n$, $$ (1-\delta)2^{n[H(X)-\epsilon]} \leq |A_\epsilon^{(n)}| \leq 2^{n[H(X)+\epsilon]}. $$

Therefore, $$ |A_\epsilon^{(n)}|\approx 2^{nH(X)}. $$

typical set 的大小远小于全集 $|\mathcal X|^n$，但它包含几乎全部概率质量。压缩就是只给 typical set 里的序列编号。

Example (Binary Source):

If $$ X_i=\begin{cases} 0,&p,\\ 1,&1-p, \end{cases} $$ then a typical sequence contains about $np$ zeros and $n(1-p)$ ones.

Number of typical sequences is roughly $$ \binom{n}{np}\approx 2^{nH(X)}. $$

Important warning:

Typical sequence is not necessarily the most likely sequence.

If $p=0.1$, the most likely sequence may be all $1$'s, but a typical sequence has about $10%$ zeros and $90%$ ones.

8.3 Fundamental Limit of Data Compression

Theorem (Achievability):

For iid $X_i\sim p(x)$ and any $\delta>0$, for sufficiently large $n$, the sequence $$ (X_1,\cdots,X_n) $$ can be described using $$ n[H(X)+\delta] $$ bits with probability of error going to $0$.

Main idea:

  • If $x^n\in A_\epsilon^{(n)}$, encode its index inside the typical set.
  • This needs about $$ \log |A_\epsilon^{(n)}|\approx nH(X) $$ bits.
  • If $x^n\notin A_\epsilon^{(n)}$, use a fallback code.

Theorem (Converse):

There is no set $B_n$ with $$ \Pr\{X^n\in B_n\}\to 1 $$ and $$ |B_n|<2^{n[H(X)-\epsilon]} $$ for large $n$.

$H(X)$ 不是某种“推荐压缩率”，而是极限。高于它可以做到，低于它基本不可能。

Chapter 9: Data Compression

9.1 Variable Length Code

Def. A variable length code is a map $$ c:\mathcal X\to \{0,1\}^* $$ that assigns each source symbol a bit string.

For a sequence, $$ c(x_1,\cdots,x_n)=c(x_1)c(x_2)\cdots c(x_n). $$

Def. A code is uniquely decodable (U.D.) if no two different source sequences produce the same encoded bit string.

That is, $$ (x_1,\cdots,x_n)\neq (y_1,\cdots,y_m) \Rightarrow c(x_1,\cdots,x_n)\neq c(y_1,\cdots,y_m). $$

单个 codeword 不同还不够，因为拼起来以后可能撞车。U.D. 要求任意长串拼接后也不能歧义。

9.2 Prefix-Free Code

Def. A code is prefix-free if no codeword is a prefix of another codeword.

Theorem: $$ \text{prefix-free}\Rightarrow \text{uniquely decodable}. $$

But $$ \text{uniquely decodable}\nRightarrow \text{prefix-free}. $$

Example:

$$ {0,10,110,111} $$ is prefix-free.

Prefix-free codes can be represented by leaves of a binary tree.

9.3 Kraft's Inequality

Theorem (Kraft Inequality):

Let $\ell_i$ be the codeword length for symbol $i$, where $i=1,\cdots,m$.

There exists a binary prefix-free code with lengths $\ell_i$ iff $$ \sum_{i=1}^m 2^{-\ell_i}\leq 1. $$

Tree interpretation:

  • A codeword of length $\ell_i$ occupies $2^{\ell_{\max}-\ell_i}$ leaves in a full binary tree of depth $\ell_{\max}$.
  • Total occupied leaves cannot exceed $2^{\ell_{\max}}$.

For $D$-ary codes: $$ \sum_{i=1}^m D^{-\ell_i}\leq 1. $$

9.4 McMillan's Inequality

Theorem (McMillan Inequality):

There exists a binary uniquely decodable code with lengths $\ell_i$ iff $$ \sum_{i=1}^m 2^{-\ell_i}\leq 1. $$

For $D$-ary uniquely decodable codes: $$ \sum_{i=1}^m D^{-\ell_i}\leq 1. $$

prefix-free 看起来比 U.D. 更严格，但从“可实现的长度集合”角度看，它们满足同一个 Kraft/McMillan 条件。所以优化平均长度时可以专心找 prefix-free code。

Chapter 10: Shannon Code

10.1 Optimizing Codeword Length

For source alphabet $$ \mathcal X={1,\cdots,m}, $$ suppose symbol $i$ has probability $p_i$ and codeword length $\ell_i$.

We want to minimize expected length: $$ L=\sum_i p_i\ell_i $$ subject to $$ \sum_i 2^{-\ell_i}\leq 1,\qquad \ell_i\in \mathbb Z^+. $$

Relax the integer constraint. The optimal real-valued length is $$ \ell_i^*=\log\frac1{p_i}. $$

Then $$ L^*=\sum_i p_i\log\frac1{p_i}=H(X). $$

Therefore, for any uniquely decodable code, $$ L\geq H(X). $$

概率大的符号应该给短码，概率小的符号给长码。最理想长度就是 surprise：$\log(1/p_i)$。

10.2 Shannon Code

Def. The Shannon code chooses $$ \ell_i=\left\lceil \log\frac1{p_i}\right\rceil. $$

Since $$ \ell_i<\log\frac1{p_i}+1, $$ we have $$ L=\sum_i p_i\ell_i <\sum_i p_i\left(\log\frac1{p_i}+1\right) =H(X)+1. $$

Theorem:

For Shannon code, $$ H(X)\leq L < H(X)+1. $$

If every $p_i$ is a power of $2$, then $\log(1/p_i)$ is integer and $$ L=H(X). $$

10.3 Block Coding

The $+1$ bit overhead may be large for single symbols.

Idea: group $n$ symbols together: $$ Y=(X_1,\cdots,X_n). $$

Design Shannon code for $Y$.

If $X_i$ are iid, then $$ H(Y)=H(X_1,\cdots,X_n)=nH(X). $$

For the block code, $$ H(Y)\leq L_Y < H(Y)+1. $$

Divide by $n$: $$ H(X)\leq \frac{L_Y}{n}<H(X)+\frac1n. $$

As $n\to\infty$, $$ \frac{L_Y}{n}\to H(X). $$

把很多 symbols 打包一起编码，可以把每个 symbol 平均多出来的 overhead 从 $1$ bit 降到 $1/n$ bit。但代价是 codebook size 指数爆炸。

10.4 Wrong Distribution

Suppose the true test distribution is $q_i$, but the code is designed using training distribution $p_i$.

Shannon code length: $$ \ell_i=\left\lceil \log\frac1{p_i}\right\rceil. $$

Expected length under true distribution $q$: $$ \begin{aligned} L &=\sum_i q_i\ell_i \\ &<\sum_i q_i\log\frac1{p_i}+1 \\ &=H(q)+D(q||p)+1 \\ &=CE(q,p)+1. \end{aligned} $$

Note:

  • $D(q||p)$ is the extra cost of not knowing the true distribution.
  • If $p=q$, then $D(q||p)=0$.

10.5 Value of Side Information

Suppose $(X,Y)$ are correlated, and $Y$ is provided to both encoder and decoder as side information.

For each possible $y$, design a code for $X$ based on $$ p(x|y). $$

For each $y$, $$ H(X|Y=y)\leq L_y < H(X|Y=y)+1. $$

Average over $y$: $$ H(X|Y)\leq L < H(X|Y)+1. $$

Since $$ H(X|Y)\leq H(X), $$ side information can reduce the required number of bits.

如果 decoder 和 encoder 都知道 $Y$，我们可以根据不同的 $Y=y$ 使用不同 codebook。相关性越强，$H(X|Y)$ 越小，越省 bits。

Chapter 11: Huffman Code

11.1 Optimal Solution

Recall the codeword length problem: $$ \min \sum_i p_i\ell_i $$ subject to $$ \sum_i 2^{-\ell_i}\leq 1,\qquad \ell_i\in\mathbb Z^+. $$

Shannon code is simple but may be suboptimal because it only rounds $$ \log\frac1{p_i}. $$

The optimal prefix-free code is given by Huffman coding.

Algorithm (Binary Huffman Code):

  1. Sort symbols by probability.
  2. Merge the two least likely symbols.
  3. Replace them by one combined symbol with probability equal to their sum.
  4. Repeat until only one symbol remains.
  5. Assign $0/1$ labels to branches and read codewords from root to leaves.

Expected length: $$ L=\sum_i p_i\ell_i. $$

11.2 Optimality Lemmas

Lemma 1:

For an optimal prefix-free code, if $$ p_i>p_j, $$ then $$ \ell_i\leq \ell_j. $$

More likely symbols should not have longer codewords.

Lemma 2:

In an optimal binary prefix-free code, the two longest codewords can be chosen to have the same length and share the same parent node.

Lemma 3:

In an optimal binary prefix-free code, the two least likely symbols can be assigned to these two longest sibling codewords.

Theorem (Huffman Optimality):

Merging the two least likely symbols reduces the problem to a smaller optimal coding problem.

If the Huffman tree is optimal for the reduced source, expanding the merged node gives an optimal tree for the original source.

Huffman 的贪心是对的，因为在某个最优树里，最小的两个概率一定可以被放在最深处当 siblings。先把它们合并不会破坏最优性。

11.3 Remarks

Huffman code is not unique.

Reasons:

  • Ties in probability can be merged in different orders.
  • Left/right branches can swap $0$ and $1$.
  • Different trees may have the same expected length.

Theorem:

For binary Huffman code, $$ H(X)\leq L_{\text{Huffman}}<H(X)+1. $$

The lower bound follows from entropy being the fundamental limit.

To make $$ L_{\text{Huffman}}\to H(X), $$ we can Huffman-code blocks $$ (X_1,\cdots,X_n), $$ but the codebook size grows exponentially.

11.4 D-ary Huffman Code

For $D$-ary codewords: $$ c:\mathcal X\to \{0,1,\cdots,D-1\}^*. $$

Algorithm:

Merge the $D$ least likely symbols each time.

Important:

For a full $D$-ary tree, the number of leaves must satisfy $$ m\equiv 1 \pmod{D-1}. $$

If not, add dummy symbols with probability $0$ until $$ m+r\equiv 1 \pmod{D-1}. $$

Then run the normal $D$-ary Huffman algorithm.

For $D$-ary code measured in $D$-ary digits, $$ H_D(X)\leq L_D < H_D(X)+1, $$ where $$ H_D(X)=\sum_i p_i\log_D\frac1{p_i}. $$

Measured in bits: $$ H(X)\leq L_D\log_2D < H(X)+\log_2D. $$

Midterm Cheat-Sheet Priority

Must memorize:

$$ H(X,Y)=H(X)+H(Y|X) $$

$$ I(X;Y)=H(X)-H(X|Y)=H(X)+H(Y)-H(X,Y) $$

$$ I(X;Y|Z)=H(X|Z)-H(X|Y,Z) $$

$$ D(p||q)=\sum_x p(x)\log\frac{p(x)}{q(x)}\geq 0 $$

$$ A_\epsilon^{(n)}\approx 2^{nH(X)},\qquad p(x^n)\approx 2^{-nH(X)} $$

$$ \sum_i 2^{-\ell_i}\leq 1 $$

$$ H(X)\leq L_{\text{Shannon}},L_{\text{Huffman}}<H(X)+1 $$

Most likely exam operations:

  1. Expand entropy / mutual information expressions.
  2. Prove inequalities using chain rule and "conditioning reduces entropy".
  3. Compute typical set size or probability.
  4. Compute entropy rate for stationary Markov processes.
  5. Construct Huffman code and compute expected length.

Chapter 12: Channel Capacity

12.1 Discrete Channels

Def. A discrete channel consists of two finite alphabets $$ \mathcal X=\{1,\cdots,m\},\qquad \mathcal Y=\{1,\cdots,n\}, $$ and a transition probability $$ p(y|x),\qquad x\in\mathcal X,\ y\in\mathcal Y. $$

The channel only specifies how the output is generated after the input is fixed. Once an input distribution $p(x)$ is chosen, $$ p(x,y)=p(x)p(y|x), $$ and hence $$ p(y)=\sum_x p(x)p(y|x). $$

Def. The matrix representation of a channel is $$ A=[a_{ij}],\qquad a_{ij}=p(Y=j|X=i). $$

Every row of $A$ is a PMF, so $$ a_{ij}\geq0,\qquad \sum_j a_{ij}=1. $$

If $$ \mathbf p_X=[p(X=1),\cdots,p(X=m)], $$ then $$ \mathbf p_Y=\mathbf p_XA. $$

channel matrix 决定 $p(y|x)$，但不决定 $p(x)$。不同 input distribution 会产生不同 $p(y)$，也会得到不同 $I(X;Y)$。

Examples:

  1. Noiseless channel: $Y=X$, so $p(y|x)=1$ iff $y=x$.
  2. Binary Erasure Channel (BEC): the input bit is erased with probability $\gamma$.
  3. Binary Symmetric Channel (BSC): the input bit is flipped with probability $\gamma$.

For a BEC, $$ \mathcal X=\{0,1\},\qquad \mathcal Y=\{0,e,1\}, $$ and $$ A= \begin{bmatrix} 1-\gamma&\gamma&0\\ 0&\gamma&1-\gamma \end{bmatrix}. $$

For a BSC, $$ A= \begin{bmatrix} 1-\gamma&\gamma\\ \gamma&1-\gamma \end{bmatrix}. $$

12.2 Discrete Memoryless Channel

Def. The $n$-th extension of a discrete channel has input and output $$ x^n=(x_1,\cdots,x_n)\in\mathcal X^n, \qquad y^n=(y_1,\cdots,y_n)\in\mathcal Y^n. $$

Def. A channel is discrete memoryless (DMC) if the current output depends on the past only through the current input: $$ (X^{i-1},Y^{i-1})\to X_i\to Y_i. $$

Equivalently, $$ p(y_i|x^n,y^{i-1})=p(y_i|x_i). $$

Theorem:

For a DMC, $$ p(y^n|x^n)=\prod_{i=1}^n p(y_i|x_i). $$

Proof idea: $$ \begin{aligned} p(y^n|x^n) &=\prod_{i=1}^n p(y_i|y^{i-1},x^n)\\ &=\prod_{i=1}^n p(y_i|x_i). \end{aligned} $$

memoryless 是 channel 的性质，不代表输入 $X_1,\cdots,X_n$ 必须 independent。它只保证给定 $X_i$ 后，$Y_i$ 不再受其他时刻影响。

12.3 Information Capacity

Theorem (Information Capacity of a DMC): $$ C=\max_{p(x)}I(X;Y). $$

The unit is bits per channel use.

For a noiseless channel with $|\mathcal X|=m$, $$ I(X;Y)=H(X), $$ so $$ C=\max_{p(x)}H(X)=\log m, $$ achieved by the uniform input.

For a BEC with erasure probability $\gamma$, $$ H(Y|X)=H_b(\gamma), $$ where $$ H_b(t)=-t\log t-(1-t)\log(1-t). $$

Let $q=p(X=0)$. Then $$ p_Y=[q(1-\gamma),\gamma,(1-q)(1-\gamma)]. $$

$H(Y)$ is maximized at $q=1/2$, and $$ \max_q H(Y)=H_b(\gamma)+(1-\gamma). $$

Therefore, $$ C_{\mathrm{BEC}}=1-\gamma. $$

For a BSC with crossover probability $\gamma$, $$ H(Y|X)=H_b(\gamma). $$

Also, $$ H(Y)\leq1, $$ with equality for $X\sim\operatorname{Bernoulli}(1/2)$. Thus, $$ C_{\mathrm{BSC}}=1-H_b(\gamma). $$

Important distinction:

  • BEC tells the receiver which symbols were lost, so $C=1-\gamma$.
  • BSC replaces a symbol by another valid symbol, so the receiver does not know where the error occurred; its capacity is $1-H_b(\gamma)$.

Chapter 13: Random Coding

13.1 Encoding and Decoding

Consider communication over a DMC: $$ W\to X^n(W)\to Y^n\to \widehat W, $$ where $$ W\in\{1,\cdots,M\},\qquad M=2^{nR}. $$

Def. An $(M,n)$-code consists of:

  1. A message set $\{1,\cdots,M\}$.
  2. An encoding function $$ X^n:\{1,\cdots,M\}\to\mathcal X^n. $$
  3. A decoding function $$ g:\mathcal Y^n\to\{1,\cdots,M\}. $$

The rate is $$ R=\frac{\log M}{n} $$ bits per channel use.

Def. The conditional error probability for message $i$ is $$ \lambda_i =\Pr\{g(Y^n)\neq i\mid X^n=X^n(i)\}. $$

Def. The maximum error probability and average error probability are $$ \lambda_{\max}=\max_{1\leq i\leq M}\lambda_i, $$ and $$ \lambda_{\mathrm{avg}} =\frac1M\sum_{i=1}^M\lambda_i. $$

A rate $R$ is achievable if there exists a sequence of $(2^{nR},n)$-codes such that $$ \lambda_{\max}\to0 $$ or, equivalently after expurgation, $$ \lambda_{\mathrm{avg}}\to0. $$

Def. The operational channel capacity is the supremum of all achievable rates.

13.2 Joint Typicality

Def. A pair $(x^n,y^n)$ is jointly $\epsilon$-typical if $$ \left|-\frac1n\log p(x^n)-H(X)\right|<\epsilon, $$ $$ \left|-\frac1n\log p(y^n)-H(Y)\right|<\epsilon, $$ and $$ \left|-\frac1n\log p(x^n,y^n)-H(X,Y)\right|<\epsilon. $$

The set of all jointly typical pairs is denoted by $$ A_\epsilon^{(n)}(X,Y). $$

Example:

If $$ p(0,0)=p(1,1)=0.45, \qquad p(0,1)=p(1,0)=0.05, $$ then a jointly typical pair $(x^n,y^n)$ satisfies $$ x_i=y_i $$ for about $90%$ of the positions.

Theorem (Joint AEP):

Suppose $(X_i,Y_i)\sim p(x,y)$ iid.

  1. A true pair is jointly typical with high probability: $$ \Pr\{(X^n,Y^n)\in A_\epsilon^{(n)}\}\to1. $$

  2. The number of jointly typical pairs is approximately $$ |A_\epsilon^{(n)}|\approx2^{nH(X,Y)}. $$

More precisely, for sufficiently large $n$, $$ (1-\epsilon)2^{n[H(X,Y)-\epsilon]} \leq |A_\epsilon^{(n)}| \leq2^{n[H(X,Y)+\epsilon]}. $$

  1. If $U^n\sim\prod_i p(x_i)$ and $V^n\sim\prod_i p(y_i)$ are generated independently, then $$ \Pr\{(U^n,V^n)\in A_\epsilon^{(n)}\} \approx2^{-nI(X;Y)}. $$

A useful bound is $$ \Pr\{(U^n,V^n)\in A_\epsilon^{(n)}\} \leq2^{-n[I(X;Y)-3\epsilon]}. $$

真正通过 channel 产生的 $(X^n,Y^n)$ 几乎一定 jointly typical；两个独立生成的序列却“碰巧看起来相关”的概率约为 $2^{-nI(X;Y)}$。这正是 random coding 能工作的原因。

13.3 Shannon's Random Coding Idea

The random coding proof has three main steps:

  1. Choose an input distribution $p(x)$, ideally one maximizing $I(X;Y)$.
  2. Generate every codeword independently: $$ X^n(w)\sim\prod_{i=1}^n p(x_i), \qquad w=1,\cdots,2^{nR}. $$
  3. Given $y^n$, find the unique $\widehat w$ such that $$ (X^n(\widehat w),y^n)\in A_\epsilon^{(n)}. $$

There are two possible decoding errors:

  • The transmitted codeword and received sequence are not jointly typical.
  • A wrong codeword is also jointly typical with the received sequence.

Joint AEP makes the first event unlikely. The second event is controlled by comparing $$ 2^{nR} $$ wrong candidates with the probability $$ 2^{-nI(X;Y)} $$ that any one candidate looks jointly typical.

So the key condition is $$ 2^{nR}2^{-nI(X;Y)}\to0, $$ or $$ R<I(X;Y). $$

Chapter 14: Channel Coding Theorem

Theorem (Channel Coding Theorem for a DMC):

Let $$ C=\max_{p(x)}I(X;Y). $$

  1. Every rate $R<C$ is achievable.
  2. Every rate $R>C$ is not achievable.

This chapter proves achievability. The converse is proved in Chapter 15.

14.1 Random Codebook and Typicality Decoder

Fix an input distribution $p(x)$ and a rate $$ R<I(X;Y). $$

Step 1: Codebook generation.

Generate $$ M=2^{nR} $$ codewords independently. For every message $w$, $$ X^n(w)=(X_1(w),\cdots,X_n(w)), $$ where every entry is drawn iid from $p(x)$.

Thus the random codebook contains $M$ rows and $n$ columns: $$ \mathcal C= \begin{bmatrix} X_1(1)&\cdots&X_n(1)\\ X_1(2)&\cdots&X_n(2)\\ \vdots&&\vdots\\ X_1(M)&\cdots&X_n(M) \end{bmatrix}. $$

The entire codebook is revealed to both encoder and decoder.

Step 2: Encoding.

To send message $w$, transmit $$ X_1(w),X_2(w),\cdots,X_n(w) $$ sequentially through the DMC.

Step 3: Decoding.

After receiving $y^n$, find the unique $\widehat w$ satisfying $$ (X^n(\widehat w),y^n)\in A_\epsilon^{(n)}. $$

Declare an error if:

  • No such message exists; or
  • More than one such message exists.

14.2 Average Error Analysis

By symmetry of random code generation, assume without loss of generality that $$ W=1 $$ was sent.

Define $$ E_w=\{(X^n(w),Y^n)\in A_\epsilon^{(n)}\}. $$

An error occurs only if $$ E_1^c\cup E_2\cup\cdots\cup E_M $$ occurs. Therefore, by the union bound, $$ \lambda_1 \leq \Pr(E_1^c)+\sum_{w=2}^{M}\Pr(E_w). $$

For the transmitted codeword, Joint AEP gives $$ \Pr(E_1^c)\to0. $$

For every wrong codeword $w\neq1$, $X^n(w)$ is independent of $Y^n$. Hence, $$ \Pr(E_w) \leq2^{-n[I(X;Y)-3\epsilon]}. $$

Thus, for sufficiently large $n$, $$ \begin{aligned} \lambda_1 &\leq \epsilon+(2^{nR}-1)2^{-n[I(X;Y)-3\epsilon]}\\ &\leq \epsilon+2^{n[R-I(X;Y)+3\epsilon]}. \end{aligned} $$

If $$ R<I(X;Y)-3\epsilon, $$ then $$ \lambda_1\to0. $$

By symmetry, the same bound holds for every message after averaging over all randomly generated codebooks. Therefore, $$ E_{\mathcal C}[\lambda_{\mathrm{avg}}(\mathcal C)]\to0. $$

Since an average cannot be smaller than every individual value, there must exist at least one deterministic codebook $\mathcal C^$ such that $$ \lambda_{\mathrm{avg}}(\mathcal C^)\to0. $$

random coding 不是说实际通信时不断随机换 codebook。随机性只是证明工具：先证明随机 codebook 的平均表现很好，因此至少存在一个固定的好 codebook。

14.3 From Average Error to Maximum Error

Suppose a code with $M=2^{nR}$ messages satisfies $$ \lambda_{\mathrm{avg}}\leq2\epsilon. $$

Sort its conditional errors: $$ \lambda_{m_1}\leq\lambda_{m_2}\leq\cdots\leq\lambda_{m_M}. $$

Keep only the better half of the messages. For $$ k=M/2, $$ we have $$ M\lambda_{\mathrm{avg}} =\sum_{i=1}^M\lambda_{m_i} \geq\sum_{i=k+1}^M\lambda_{m_i} \geq\frac M2\lambda_{m_k}. $$

Therefore, $$ \lambda_{m_k}\leq2\lambda_{\mathrm{avg}}\leq4\epsilon. $$

After discarding the worse half, $$ \lambda_{\max}\leq4\epsilon. $$

The new rate is $$ \frac1n\log\frac{2^{nR}}2 =R-\frac1n\to R. $$

Thus vanishing average error implies vanishing maximum error with asymptotically no rate loss.

Finally, choose $p^(x)$ maximizing $I(X;Y)$. Since every $$ R<I_{p^}(X;Y)=C $$ is achievable, the achievability part of the channel coding theorem follows.

Chapter 15: Converse

15.1 Fano's Inequality

Suppose we estimate a discrete random variable $X\in\mathcal X$ from $Y$: $$ \widehat X=g(Y). $$

Let $$ P_e=\Pr\{\widehat X\neq X\}. $$

Theorem (Fano's Inequality): $$ H(X|Y) \leq H_b(P_e)+P_e\log(|\mathcal X|-1). $$

Since $$ H_b(P_e)\leq1, $$ a simpler form is $$ H(X|Y)\leq1+P_e\log|\mathcal X|. $$

Fano's inequality 把“decoding error 很小”翻译为“知道 observation 后剩余的不确定性很小”。它是 converse proof 中从 reliability 连到 information 的桥梁。

Proof:

Define the error indicator $$ E= \begin{cases} 0,&\widehat X=X,\\ 1,&\widehat X\neq X. \end{cases} $$

Because $E$ is determined by $(X,Y)$, $$ H(E|X,Y)=0. $$

Using the chain rule in two ways, $$ \begin{aligned} H(E,X|Y) &=H(X|Y)+H(E|X,Y)\\ &=H(X|Y), \end{aligned} $$ and $$ H(E,X|Y)=H(E|Y)+H(X|E,Y). $$

Now, $$ H(E|Y)\leq H(E)=H_b(P_e). $$

If $E=0$, $X=\widehat X$ is known from $Y$, so $$ H(X|E=0,Y)=0. $$

If $E=1$, at most $|\mathcal X|-1$ possibilities remain, so $$ H(X|E=1,Y)\leq\log(|\mathcal X|-1). $$

Therefore, $$ H(X|E,Y) \leq P_e\log(|\mathcal X|-1), $$ which proves the result.

15.2 Converse of the Channel Coding Theorem

Consider any $(2^{nR},n)$-code over a DMC. Let $$ W\sim\operatorname{Uniform}\{1,\cdots,2^{nR}\}. $$

Without feedback, $$ W\to X^n\to Y^n\to\widehat W $$ is a Markov chain.

Since $W$ is uniform, $$ H(W)=nR. $$

By the mutual information identity, $$ nR=H(W|\widehat W)+I(W;\widehat W). $$

Fano's inequality gives $$ H(W|\widehat W) \leq H_b(P_e)+P_e\log(2^{nR}-1) \leq1+nRP_e. $$

By data processing, $$ I(W;\widehat W)\leq I(X^n;Y^n). $$

For a DMC, $$ \begin{aligned} I(X^n;Y^n) &=H(Y^n)-H(Y^n|X^n)\\ &\leq\sum_{i=1}^n H(Y_i)-\sum_{i=1}^nH(Y_i|X_i)\\ &=\sum_{i=1}^nI(X_i;Y_i)\\ &\leq nC. \end{aligned} $$

Combining the bounds, $$ nR\leq1+nRP_e+nC. $$

Equivalently, $$ R(1-P_e)\leq C+\frac1n. $$

If a sequence of codes has $$ P_e\to0, $$ then letting $n\to\infty$ gives $$ R\leq C. $$

Therefore every $R>C$ is not achievable.

The two parts together give the fundamental separation: $$ \begin{cases} R<C,&\text{reliable communication is possible},\\ R>C,&\text{reliable communication is impossible}. \end{cases} $$

$R=C$ 是边界点。capacity 定义为 achievable rates 的 supremum；定理的标准表述通常只直接保证所有 $R<C$ 可达、所有 $R>C$ 不可达。

Chapter 16: Feedback Capacity

16.1 Channel with Feedback

With noiseless causal feedback, the encoder knows all previous outputs before choosing the next input: $$ X_i=f_i(W,Y^{i-1}). $$

The decoder still observes $Y^n$ and produces $$ \widehat W=g(Y^n). $$

Example (BEC with Feedback):

For a BEC with erasure probability $\gamma$, retransmit the current bit whenever the previous output is $e$.

The number of transmissions for one successful bit is geometric with mean $$ \frac1{1-\gamma}. $$

Therefore the achieved rate is $$ R=\frac1{1/(1-\gamma)}=1-\gamma. $$

This equals the ordinary BEC capacity.

feedback 可以让协议更直观：丢了就重传。但在 DMC 中，它不能把 capacity 提高到原来的 $C$ 以上。

16.2 Feedback Does Not Increase DMC Capacity

Theorem:

For every DMC, $$ C_{\mathrm{FB}}=C. $$

Achievability is immediate: the encoder can ignore the feedback and use an ordinary capacity-achieving code. Hence, $$ C_{\mathrm{FB}}\geq C. $$

For the converse, consider any feedback code with average error probability $P_e$.

Although $$ W\to X^n\to Y^n $$ is generally not a Markov chain because $X_i$ depends on $Y^{i-1}$, we still have $$ W\to Y^n\to\widehat W. $$

Thus, $$ I(W;\widehat W)\leq I(W;Y^n). $$

Now, $$ \begin{aligned} I(W;Y^n) &=H(Y^n)-H(Y^n|W)\\ &\leq\sum_{i=1}^nH(Y_i) -\sum_{i=1}^nH(Y_i|W,Y^{i-1}). \end{aligned} $$

Since $X_i=f_i(W,Y^{i-1})$ and the channel is memoryless, $$ H(Y_i|W,Y^{i-1})=H(Y_i|X_i). $$

Therefore, $$ \begin{aligned} I(W;Y^n) &\leq\sum_{i=1}^n \left[H(Y_i)-H(Y_i|X_i)\right]\\ &=\sum_{i=1}^nI(X_i;Y_i)\\ &\leq nC. \end{aligned} $$

Using Fano's inequality again, $$ nR\leq1+nRP_e+nC. $$

Letting $n\to\infty$ and $P_e\to0$ yields $$ R\leq C. $$

Hence, $$ C_{\mathrm{FB}}\leq C, $$ and finally $$ C_{\mathrm{FB}}=C. $$

Remarks:

  • For a DMC, iid capacity-achieving inputs are already optimal for capacity.
  • For channels with memory, feedback may increase capacity because iid inputs can be suboptimal.
  • Even when capacity is unchanged, feedback can simplify coding, reduce delay, or improve error exponents.

Chapter 17: Differential Entropy

17.1 Definition and Examples

For a discrete random variable $X\sim p(x)$, $$ H(X)=\sum_xp(x)\log\frac1{p(x)}. $$

For a continuous random variable $X$ with probability density function $f(x)$, the corresponding quantity is differential entropy.

Def. $$ h(X)=\int_{-\infty}^{\infty}f(x)\log\frac1{f(x)},dx =-\int_{-\infty}^{\infty}f(x)\log f(x),dx. $$

When the logarithm is base $2$, $h(X)$ is measured in bits. When it is base $e$, it is measured in nats.

Important warning: $$ h(X) $$ can be negative, unlike discrete entropy.

Example (Uniform Distribution):

If $$ X\sim\operatorname{Uniform}[0,a], $$ then $$ f(x)=\frac1a,\qquad 0\leq x\leq a, $$ and $$ h(X)=\int_0^a\frac1a\log a,dx=\log a. $$

Thus $h(X)<0$ when $0<a<1$.

Example (Exponential Distribution):

If $$ X\sim\operatorname{Exp}(\lambda), \qquad f(x)=\lambda e^{-\lambda x},\ x\geq0, $$ then, in nats, $$ \begin{aligned} h(X) &=-E[\ln f(X)]\\ &=\lambda E[X]-\ln\lambda\\ &=1-\ln\lambda. \end{aligned} $$

In bits, $$ h(X)=\log_2\frac e\lambda. $$

Example (Gaussian Distribution):

If $$ X\sim\mathcal N(0,\sigma^2), $$ then $$ f(x)=\frac1{\sqrt{2\pi\sigma^2}} \exp\left(-\frac{x^2}{2\sigma^2}\right), $$ and $$ h(X)=\frac12\log(2\pi e\sigma^2). $$

17.2 Continuous AEP and Typical Volume

Theorem (Continuous AEP):

If $X_i\sim f(x)$ iid, then $$ -\frac1n\log f(X_1,\cdots,X_n)\to h(X) $$ in probability.

Proof idea: $$ \begin{aligned} -\frac1n\log f(X_1,\cdots,X_n) &=-\frac1n\log\prod_{i=1}^nf(X_i)\\ &=-\frac1n\sum_{i=1}^n\log f(X_i)\\ &\to -E[\log f(X)]\\ &=h(X) \end{aligned} $$ by LLN.

Def. The continuous typical set is $$ A_\epsilon^{(n)} =\left\{x^n: \left|-\frac1n\log f(x^n)-h(X)\right|<\epsilon \right\}. $$

For every $x^n\in A_\epsilon^{(n)}$, $$ 2^{-n[h(X)+\epsilon]} <f(x^n)< 2^{-n[h(X)-\epsilon]}. $$

Theorem:

For sufficiently large $n$, $$ \Pr\{X^n\in A_\epsilon^{(n)}\}>1-\epsilon. $$

The continuous analogue of cardinality is volume: $$ \operatorname{Vol}(A_\epsilon^{(n)}) =\int_{A_\epsilon^{(n)}}dx_1\cdots dx_n. $$

Its bounds are $$ (1-\epsilon)2^{n[h(X)-\epsilon]} \leq\operatorname{Vol}(A_\epsilon^{(n)}) \leq2^{n[h(X)+\epsilon]}. $$

Therefore, $$ \operatorname{Vol}(A_\epsilon^{(n)}) \approx2^{nh(X)}. $$

Example (Gaussian Typical Set):

For $X_i\sim\mathcal N(0,\sigma^2)$, $$ -\frac1n\log f(x^n) =\frac{\log e}{2\sigma^2}\frac1n\sum_{i=1}^nx_i^2 +\frac12\log(2\pi\sigma^2). $$

Joint typicality is therefore equivalent to $$ \frac1n\sum_{i=1}^n x_i^2\approx\sigma^2. $$

Gaussian typical sequences lie in a thin spherical shell of radius approximately $\sqrt{n\sigma^2}$, rather than near the origin.

17.3 Relative Entropy and Mutual Information

Def. For two densities $f$ and $g$, the relative entropy is $$ D(f||g)=\int f(x)\log\frac{f(x)}{g(x)},dx. $$

Theorem: $$ D(f||g)\geq0, $$ with equality iff $f=g$ almost everywhere.

Def. For jointly continuous $(X,Y)$, $$ I(X;Y) =\iint f(x,y) \log\frac{f(x,y)}{f_X(x)f_Y(y)},dx,dy. $$

Equivalently, $$ I(X;Y)=h(Y)-h(Y|X) =h(X)+h(Y)-h(X,Y). $$

Although differential entropy can be negative, $$ I(X;Y)\geq0, $$ because $$ I(X;Y)=D(f_{XY}||f_Xf_Y). $$

As in the discrete case, $$ I(X;Y)=0 \Leftrightarrow X\text{ and }Y\text{ are independent}. $$

Useful properties:

  1. Differential entropy chain rule: $$ h(X^n)=\sum_{i=1}^nh(X_i|X^{i-1}). $$

  2. Mutual information chain rule: $$ I(X^n;Y) =\sum_{i=1}^nI(X_i;Y|X^{i-1}). $$

  3. Translation: $$ h(X+c)=h(X). $$

  4. Scaling: $$ h(aX)=h(X)+\log|a|,\qquad a\neq0. $$

  5. For a nonsingular matrix $A$, $$ h(AX^n)=h(X^n)+\log|\det A|. $$

17.4 Joint AEP for Continuous Variables

A pair $(x^n,y^n)$ is jointly typical if $$ -\frac1n\log f_X(x^n)\approx h(X), $$ $$ -\frac1n\log f_Y(y^n)\approx h(Y), $$ and $$ -\frac1n\log f_{XY}(x^n,y^n)\approx h(X,Y). $$

The continuous Joint AEP gives the same two facts needed for random coding:

  1. If $(X_i,Y_i)\sim f_{XY}$ iid, then $$ \Pr\{(X^n,Y^n)\text{ jointly typical}\}\to1. $$

  2. If $\widetilde X^n$ and $\widetilde Y^n$ are independently generated from $f_X$ and $f_Y$, then $$ \Pr\{(\widetilde X^n,\widetilde Y^n) \text{ jointly typical}\} \lesssim2^{-n[I(X;Y)-3\epsilon]}. $$

So the typicality-decoding proof from a DMC can later be adapted to continuous channels.

17.5 Connection Between $H(X)$ and $h(X)$

Quantize a continuous $X$ using bins of width $\Delta$. If $$ i\Delta\leq X<(i+1)\Delta, $$ map $X$ to a discrete representative $X^\Delta=x_i$.

For small $\Delta$, $$ p(X^\Delta=x_i)\approx f(x_i)\Delta. $$

Hence, $$ \begin{aligned} H(X^\Delta) &=-\sum_i f(x_i)\Delta \log[f(x_i)\Delta]\\ &\approx-\int f(x)\log f(x),dx-\log\Delta\\ &=h(X)-\log\Delta. \end{aligned} $$

Therefore, $$ h(X)=\lim_{\Delta\to0} \left[H(X^\Delta)+\log\Delta\right]. $$

当 $\Delta\to0$ 时，离散化后的 $H(X^\Delta)\to\infty$，而 $\log\Delta\to-\infty$。differential entropy 是去掉“分辨率成本”后的有限部分，所以它本身不等于描述一个实数所需的绝对 bit 数。

Chapter 18: Maximum Entropy

18.1 Gaussian Maximizes Entropy Under a Power Constraint

Goal:

Among all continuous distributions satisfying $$ E[X^2]=\int x^2f(x),dx\leq P, $$ find the one maximizing $h(X)$.

Theorem (Maximum Entropy Theorem):

If $E[X^2]\leq P$, then $$ h(X)\leq\frac12\log(2\pi eP). $$

Equality holds iff $$ X\sim\mathcal N(0,P). $$

Proof using relative entropy:

Let $$ \phi(x)=\frac1{\sqrt{2\pi P}} \exp\left(-\frac{x^2}{2P}\right) $$ be the density of $\mathcal N(0,P)$.

Since $$ D(f||\phi)\geq0, $$ we have $$ h(f)\leq-\int f(x)\log\phi(x),dx. $$

Now, $$ \begin{aligned} -\int f(x)\log\phi(x),dx &=\frac{\log e}{2P}E[X^2] +\frac12\log(2\pi P)\\ &\leq\frac12\log(2\pi eP). \end{aligned} $$

For $f=\phi$, equality holds throughout. Therefore the Gaussian is optimal.

entropy 希望 distribution 尽量 spread out；power constraint 又限制它不能无限扩散。两者平衡后的最优形状正是 Gaussian。

18.2 Lagrange Multiplier Derivation

We can also solve $$ \max_f -\int f(x)\log f(x),dx $$ subject to $$ \int f(x)x^2,dx=P, \qquad \int f(x),dx=1. $$

The functional Lagrangian is $$ \begin{aligned} L[f,\lambda,\mu] &=-\int f(x)\log f(x),dx\\ &\quad+\lambda\left(\int f(x)x^2,dx-P\right)\\ &\quad+\mu\left(\int f(x),dx-1\right). \end{aligned} $$

At an optimum, $$ \frac{\delta L}{\delta f(x)} =-\log f(x)-\log e+\lambda x^2+\mu=0. $$

Thus, $$ f^*(x)=K e^{-cx^2}, $$ which is Gaussian after choosing the constants to satisfy normalization and power.

The inequality constraint can be replaced by equality at the maximum because a distribution using less than all available power can be scaled outward to obtain larger entropy.

18.3 Exponential Maximizes Entropy Under a Mean Constraint

Suppose $X\geq0$ and $$ E[X]=m. $$

The entropy-maximization problem is $$ \max_f -\int_0^\infty f(x)\log f(x),dx $$ subject to $$ \int_0^\infty xf(x),dx=m, \qquad \int_0^\infty f(x),dx=1. $$

The Lagrange condition gives $$ f^*(x)=K e^{-cx}. $$

After normalization and matching the mean, $$ f^*(x)=\frac1m e^{-x/m},\qquad x\geq0. $$

Therefore the exponential distribution maximizes entropy among nonnegative random variables with fixed mean, and $$ h(X)\leq\log(em), $$ with equality iff $X\sim\operatorname{Exp}(1/m)$.

General pattern:

  • Fixed finite support $\Rightarrow$ uniform maximizes entropy.
  • Fixed second moment $\Rightarrow$ Gaussian maximizes entropy.
  • Nonnegative with fixed mean $\Rightarrow$ exponential maximizes entropy.

Chapter 19: Gaussian Channel

19.1 AWGN Channel and Capacity

Consider the additive white Gaussian noise (AWGN) channel $$ Y_i=X_i+Z_i, $$ where $$ Z_i\sim\mathcal N(0,\sigma^2) $$ are iid and independent of the inputs.

The codewords satisfy the average power constraint $$ \frac1n\sum_{i=1}^n x_i^2(w)\leq P. $$

The signal-to-noise ratio is $$ \operatorname{SNR}=\frac P{\sigma^2}. $$

Theorem (AWGN Channel Capacity): $$ C=\frac12\log\left(1+\frac P{\sigma^2}\right) $$ bits per channel use.

The capacity-achieving input is $$ X\sim\mathcal N(0,P). $$

Derivation: $$ \begin{aligned} I(X;Y) &=h(Y)-h(Y|X)\\ &=h(Y)-h(X+Z|X)\\ &=h(Y)-h(Z). \end{aligned} $$

Since $X$ and $Z$ are independent and $E[Z]=0$, $$ E[Y^2]=E[(X+Z)^2] =E[X^2]+E[Z^2] \leq P+\sigma^2. $$

By the maximum entropy theorem, $$ h(Y)\leq\frac12\log[2\pi e(P+\sigma^2)]. $$

Also, $$ h(Z)=\frac12\log(2\pi e\sigma^2). $$

Therefore, $$ \begin{aligned} I(X;Y) &\leq\frac12\log \frac{P+\sigma^2}{\sigma^2}\\ &=\frac12\log\left(1+\frac P{\sigma^2}\right). \end{aligned} $$

If $$ X\sim\mathcal N(0,P), $$ then $$ Y=X+Z\sim\mathcal N(0,P+\sigma^2), $$ so equality holds.

Gaussian noise 固定后，最大化 $I(X;Y)$ 等价于最大化 output entropy $h(Y)$。power constraint 下 Gaussian output entropy 最大，而 Gaussian input 加 Gaussian noise 恰好仍是 Gaussian。

19.2 Achievability

Fix $$ R<C. $$

Generate a random codebook using iid Gaussian entries: $$ X_i(w)\sim\mathcal N(0,P) $$ independently for all $i$ and $w$.

To handle a strict power constraint, one can instead use variance $P-\eta$ and discard codewords whose empirical power is atypically large. By LLN, $$ \frac1n\sum_{i=1}^nX_i^2(w)\approx P-\eta. $$

The decoder finds the unique $\widehat w$ such that $$ (X^n(\widehat w),Y^n) $$ is jointly typical.

Assume $W=1$ was sent. The error probability is bounded by $$ \begin{aligned} P_e &\leq \Pr\{(X^n(1),Y^n)\text{ is not jointly typical}\}\\ &\quad+\sum_{w=2}^{2^{nR}} \Pr\{(X^n(w),Y^n)\text{ is jointly typical}\}. \end{aligned} $$

Continuous Joint AEP gives $$ P_e \leq\epsilon+(2^{nR}-1) 2^{-n[I(X;Y)-3\epsilon]}. $$

Hence $P_e\to0$ whenever $$ R<I(X;Y)-3\epsilon. $$

Choosing Gaussian input and then letting $\epsilon,\eta\to0$ shows that every $$ R<C $$ is achievable.

19.3 Converse

Let $W$ be uniform over $2^{nR}$ messages, and let $P_e$ be the decoding error probability.

By Fano's inequality and data processing, $$ \begin{aligned} nR &=H(W)\\ &\leq1+nRP_e+I(W;\widehat W)\\ &\leq1+nRP_e+I(X^n;Y^n). \end{aligned} $$

For the AWGN channel, $$ \begin{aligned} I(X^n;Y^n) &=h(Y^n)-h(Y^n|X^n)\\ &=h(Y^n)-h(Z^n)\\ &\leq\sum_{i=1}^nh(Y_i)-\sum_{i=1}^nh(Z_i). \end{aligned} $$

Let $$ P_i=E[X_i^2]. $$

Then $$ h(Y_i)-h(Z_i) \leq\frac12\log\left(1+\frac{P_i}{\sigma^2}\right), $$ so $$ I(X^n;Y^n) \leq\sum_{i=1}^n \frac12\log\left(1+\frac{P_i}{\sigma^2}\right). $$

The power constraint gives $$ \frac1n\sum_{i=1}^nP_i\leq P. $$

Since $\log(1+x)$ is concave, Jensen's inequality gives $$ \begin{aligned} I(X^n;Y^n) &\leq\frac n2 \log\left(1+\frac{\frac1n\sum_iP_i}{\sigma^2}\right)\\ &\leq\frac n2\log\left(1+\frac P{\sigma^2}\right)\\ &=nC. \end{aligned} $$

Therefore, $$ nR\leq1+nRP_e+nC. $$

Letting $n\to\infty$ and $P_e\to0$ yields $$ R\leq C. $$

Important warning:

We cannot conclude for every $i$ that $$ P_i\leq P. $$

The constraint only controls the average $$ \frac1n\sum_iP_i\leq P. $$

Jensen's inequality is the step that converts the collection $P_1,\cdots,P_n$ into the average power $P$.

19.4 Key Interpretations

The capacity formula is $$ C=\frac12\log(1+\operatorname{SNR}). $$

At low SNR, $$ C\approx\frac{\operatorname{SNR}}{2\ln2}. $$

At high SNR, $$ C\approx\frac12\log\operatorname{SNR}. $$

So doubling signal power does not double capacity. Capacity grows only logarithmically with power.

The factor $1/2$ appears because this is a real scalar Gaussian channel. A complex Gaussian channel has two real dimensions per channel use and commonly yields $$ C=\log(1+\operatorname{SNR}). $$

Final chain of ideas: $$ \text{power constraint} \Rightarrow \text{Gaussian maximizes }h(Y) \Rightarrow \max I(X;Y) =\frac12\log(1+\operatorname{SNR}). $$