シャノンの情報源符号化定理
Σ1, Σ2 を2つの有限のアルファベットとし、Σ∗1 と Σ∗2 をそれぞれのアルファベットからの全ての有限語の集合とする。
X を Σ1 の値をとる確率変数とし、 f を Σ∗1 から Σ∗2 への一意復号可能な符号とする(ここで、|Σ2| = a)。S を単語長 f (X) で与えられる確率変数とする。
f が X の最小単語長さという意味で最適であるとき、
H ( X ) log 2  a ≤ E S < H ( X ) log 2  a + 1 {\displaystyle {\frac {H(X)}{\log _{2}a}}\leq \mathbb {E} S<{\frac {H(X)}{\log _{2}a}}+1}
である。(Shannon 1948)