Channel Capacity

Channel Capacity

Shannon's channel capacity is the maximum rate at which information can be transmitted reliably over a noisy channel:

$C = \max_{p(X)} I(X; Y) \text{ bits/channel use}$

Binary Symmetric Channel (BSC)

The simplest noisy channel flips each bit independently with probability $p$:

$\text{BSC}(p): \begin{cases} P(Y=0|X=0) = 1-p \\ P(Y=1|X=0) = p \\ P(Y=0|X=1) = p \\ P(Y=1|X=1) = 1-p \end{cases}$

BSC Capacity

The maximum MI over BSC($p$) is achieved by the uniform input distribution:

$C_{\text{BSC}}(p) = 1 - H_b(p)$

where $H_b(p)$ is the binary entropy function:

$H_b(p) = -p \log_2 p - (1-p) \log_2(1-p)$

Special Cases

import math

def binary_entropy(p):
    if p <= 0 or p >= 1:
        return 0.0
    return -p * math.log2(p) - (1-p) * math.log2(1-p)

def binary_channel_capacity(p_error):
    return 1 - binary_entropy(p_error)

print(binary_channel_capacity(0.0))   # 1.0
print(binary_channel_capacity(0.5))   # 0.0
print(round(binary_channel_capacity(0.1), 4))  # 0.531

Your Task

Implement:

• binary_entropy(p) — $H_b(p)$; return $0.0$ for $p \leq 0$ or $p \geq 1$
• binary_channel_capacity(p_error) — $1 - H_b(p)$
• bsc_capacity(p) — alias for binary_channel_capacity