Information Theory — Binary Symmetric Channel

Error prob p 0.10

Input bias q = P(X=1) 0.50

Block length n 100

Channel capacity C—

H(p) binary entropy—

Mutual info I(X;Y)—

H(X) source entropy—

BER (observed)—

H(p) = −p log₂p − (1−p)log₂(1−p)
C = 1 − H(p) bits/use
I(X;Y) = H(Y) − H(p)
Shannon limit: R < C

BSC: each bit flipped with prob p, independent. Shannon 1948: reliable communication possible iff R < C = 1−H(p). At p=0.5: complete noise, C=0. At p=0: noiseless, C=1 bit/use. Capacity curve (gold), mutual information for given input bias (green). Bottom: simulated block transmission.