received_2436087983418857.jpeg

# Lecture 19 ## Channel Capacity Channel Capacity $$ C = \max_{p(x)} I(X; Y) $$ Shannon **Example:** Noiseless channel:  $$ X \longrightarrow Y $$ $$ p(y|x) = \begin{cases} 1 & \text{if } y = x \\ 0 & \text{if } y \neq x \en...

# Lecture 19 ## Channel Capacity Channel Capacity $$ C = \max_{p(x)} I(X; Y) $$ Shannon **Example:** Noiseless channel:  $$ X \longrightarrow Y $$ $$ p(y|x) = \begin{cases} 1 & \text{if } y = x \\ 0 & \text{if } y \neq x \end{cases} $$ $$ I(X; Y) = H(X) - H(X|Y) = H(X) - 0 = H(X) $$ $$ C = \max_{p(x)} I(X; Y) = \max_{p(x)} H(X) = \log |\mathcal{X}| $$ where $|\mathcal{X}|$ is the number of elements in the alphabet $\mathcal{X}$. Argmax is achieved by uniform distribution on $X$. **Example: Noisy Typewriter**  Each letter goes to itself and to the next letter with equal probability. $$ p(y|x) = \begin{cases} \frac{1}{2} & \text{if } y = x \text{ or } y = x + 1 \pmod{26} \\ 0 & \text{otherwise} \end{cases} $$ Since $H(Y|X) = 1$ bit. $$ I(X; Y) = H(Y) - H(Y|X) = H(Y) - 1 $$ $$ C = \max I(X; Y) = \max H(Y) - 1 = \log 26 - 1 = \log 13 $$ Achieved when $p(x)$ is uniform over the alphabet. **Example: Binary Symmetric Channel (BSC)**  $$ X \longrightarrow Y $$ $$ p(y|x) = \begin{cases} p & \text{if } y \neq x \\ 1-p & \text{if } y = x \end{cases} $$ $$ I(X; Y) = H(Y) - H(Y|X) = H(Y) - H(p) $$ $$ C = \max_{p(x)} I(X; Y) = \max_{p(x)} H(Y) - H(p) = 1 - H(p) $$ where $H(p) = -p \log p - (1-p)\log(1-p)$. $C$ is achieved by uniform distribution on $X$. **Example: Binary Erasure Channel (BEC)**  $$ X \longrightarrow Y $$ $$ p(y|x) = \begin{cases} 1 - \alpha & \text{if } y = x \\ \alpha & \text{if } y = ? \\ 0 & \text{otherwise} \end{cases} $$ $$ I(X; Y) = H(Y) - H(Y|X) = H(Y) - \alpha $$ Let $\Pr(X = 1) = \pi$, then $$ \Pr(Y = 1) = \pi(1-\alpha) $$ $$ \Pr(Y = 0) = (1 - \pi)(1 - \alpha) $$ $$ \Pr(Y = ?) = \alpha $$ $$ H(Y) = H(\pi(1-\alpha), (1-\pi)(1-\alpha), \alpha) $$ $$ = H(\alpha) + (1-\alpha)H(\pi) $$ $$ I(X; Y) = H(Y) - H(Y|X) $$ $$ = H(\alpha) + (1-\alpha)H(\pi) - H(\alpha) $$ $$ = (1 - \alpha)H(\pi) $$ $$ C = \max_{\pi} I(X; Y) = \max_{\pi} (1 - \alpha)H(\pi) = 1 - \alpha $$ Achieved for $\pi = \frac{1}{2}$.