Prerequisites & Notation

Before You Begin

• Shannon entropy $\mathrm{H}(X)$ and mutual information $\mathrm{I}(X;Y)$ for discrete RVs(Review ch01)

  Self-check: Can you state the chain rule $\mathrm{H}(X,Y) = \mathrm{H}(X) + \mathrm{H}(Y|X)$ and identify when equality in the joint-entropy bound holds?

• Broadcast channel basics — single sender, multiple receivers(Review ch15)

  Self-check: Given a Gaussian BC with two receivers of different SNRs, can you sketch the capacity region?

• Basic probability and expectations over discrete distributions

  Self-check: Can you compute $\mathbb{E}[X]$ when $X$ is Zipf-distributed over $\{1,\ldots,N\}$?

• Binomial coefficients and basic counting

  Self-check: Can you state that $\binom{K}{t} = K!/(t!(K-t)!)$ and sketch why $\sum_t \binom{K}{t} = 2^K$?

• Linear codes over $\mathbb{F}_2$ and the XOR operation

  Self-check: Given bits $a$ and $b$, can you recover $a$ if you know $a \oplus b$ and $b$?

• Asymptotic notation $\Theta(\cdot)$, $O(\cdot)$, $\Omega(\cdot)$

  Self-check: Can you distinguish $\Theta(K)$ from $O(K^2)$ in the context of scaling laws?