b35eb1ea-4e25-41b8-a517-7de92219a5bf.jpeg

# Lecture 24 ## Channel Capacity - Last time - Introduced the idea of channel capacity - Defined the capacity of the discrete memoryless channel (DMC) ### Discrete Memoryless Channel (DMC) *Channel Model* $p(y|x)$ *Information* $I(X;Y) = H(Y) - H(Y|X)$ $= H(Y) - \sum_x p(x)H(Y|X=x)$...

# Lecture 24 ## Channel Capacity - Last time - Introduced the idea of channel capacity - Defined the capacity of the discrete memoryless channel (DMC) ### Discrete Memoryless Channel (DMC) *Channel Model* $p(y|x)$ *Information* $I(X;Y) = H(Y) - H(Y|X)$ $= H(Y) - \sum_x p(x)H(Y|X=x)$ *Capacity* $C = \max_{p(x)} I(X;Y)$ The capacity is the maximum mutual information when we vary the input distribution. ### Example: Binary Symmetric Channel (BSC) *Binary Symmetric Channel* Alphabet $\{0,1\}$ $p(y|x) = \begin{cases} 1-p, & y=x \\ p, & y \neq x \end{cases}$ *Calculation* $I(X;Y) = H(Y) - H(Y|X)$ $H(Y|X) = \sum_x p(x)H(Y|X=x)$ $= p(X=0)H(Y|X=0) + p(X=1)H(Y|X=1)$ $= p(X=0)H(p) + p(X=1)H(p)$ $= H(p)\underbrace{(p(X=0) + p(X=1))}_{1}$ $\therefore H(Y|X) = H(p)$ $I(X;Y) = H(Y) - H(p)$ We want to maximize $I(X;Y)$ by choosing the best $p(x)$. $I(X;Y)$ is maximized when $H(Y)$ is maximized. $H(Y)$ is maximized when $Y$ is uniform, i.e. $p(Y=0) = p(Y=1) = 1/2$. We can achieve this by setting $p(X=0) = p(X=1) = 1/2$. In this case, $p(Y=0) = p(Y=0|X=0)p(X=0) + p(Y=0|X=1)p(X=1)$ $= (1-p)\frac{1}{2} + p\frac{1}{2} = \frac{1}{2}$ $\therefore p(Y=0) = \frac{1}{2}$, and hence $p(Y=1) = \frac{1}{2}$. $C = \max I(X;Y) = H(Y) - H(p) = 1 - H(p)$ $C = 1 - H(p)$ bits. ### Example: Binary Erasure Channel (BEC) *Binary Erasure Channel* Alphabet $\{0,1,?\}$ $p(y|x) = \begin{cases} 1-\alpha, & y = x \\ \alpha, & y = ? \\ 0, & otherwise \end{cases}$ *Calculation* $I(X;Y) = H(Y) - H(Y|X)$ $H(Y|X) = \sum_x p(x) H(Y|X=x)$ $= p(X=0)H(Y|X=0) + p(X=1)H(Y|X=1)$ $Y|X=0 = \begin{cases} 0, & 1-\alpha \\ ?, & \alpha \end{cases}$ $H(Y|X=0) = H(\alpha)$ Similarly, $H(Y|X=1) = H(\alpha)$ $H(Y|X) = H(\alpha)[p(X=0) + p(X=1)]$ $= H(\alpha)$ $\therefore I(X;Y) = H(Y) - H(\alpha)$ We want to maximize $H(Y)$. Let $p(X=0) = \pi_0$ $p(X=1) = \pi_1$ $p(Y=0) = p(Y=0|X=0)p(X=0) = (1-\alpha)\pi_0$ $p(Y=1) = p(Y=1|X=1)p(X=1) = (1-\alpha)\pi_1$ $p(Y=?) = \alpha$ $H(Y) = - (1-\alpha)\pi_0 \log((1-\alpha)\pi_0) - (1-\alpha)\pi_1 \log((1-\alpha)\pi_1) - \alpha \log \alpha$ $= - (1-\alpha)\pi_0 [\log(1-\alpha) + \log \pi_0] - (1-\alpha)\pi_1 [\log(1-\alpha) + \log \pi_1] - \alpha \log \alpha$ $= -(1-\alpha)\log(1-\alpha)\underbrace{(\pi_0 + \pi_1)}_{1} - (1-\alpha)[\pi_0 \log \pi_0 + \pi_1 \log \pi_1] - \alpha \log \alpha$ $= -(1-\alpha)\log(1-\alpha) - \alpha \log \alpha \underbrace{- (1-\alpha)[\pi_0 \log \pi_0 + \pi_1 \log \pi_1]}_{(1-\alpha)H(X)}$ $H(Y) = H(\alpha) + (1-\alpha)H(X)$ To maximize $H(Y)$, we need to maximize $H(X)$, which occurs when $p(X=0) = p(X=1) = 1/2$. Then $H(X) = 1$. $C = \max I(X;Y) = H(Y) - H(\alpha)$ $= H(\alpha) + (1-\alpha)\underbrace{H(X)}_{1} - H(\alpha)$ $C = 1 - \alpha$ bits