Shannon's Noisy Channel Coding Theorem — Binary Symmetric Channel

C = 1 − H(p) bits/use. Shannon proved: reliable communication is possible iff rate R < C, with arbitrarily small error probability. The BSC flips each bit independently with probability p.

Flip probability p0.100

Rate R (bits/use)0.50

Block length n1000

Capacity C

0.531

H(p) (binary entropy)

0.469

Rate vs Capacity

R < C ✓

Sphere-pack bound

2³⁵⁰

C = 1 − H(0.100) = 1 − 0.469 = 0.531 bits/use