シャノンの情報源符号化定理
ここで、2行目はギブスの不等式に、5行目はクラフトの不等式による。
C = ∑ i = 1 n a − s i ≤ 1 {\displaystyle C=\sum _{i=1}^{n}a^{-s_{i}}\leq 1}
よって log C ≤ 0 である。
2行目の不等式について、
s i = ⌈ − log a  p i ⌉ {\displaystyle s_{i}=\lceil -\log _{a}p_{i}\rceil }
とすると、
− log a  p i ≤ s i < − log a  p i + 1 {\displaystyle -\log _{a}p_{i}\leq s_{i}<-\log _{a}p_{i}+1}
情報理論において、シャノンの情報源符号化定理(シャノンのじょうほうげんふごうかていり、英語: Shannon's source coding theorem, noiseless coding theorem)は、データ圧縮の可能な限界と情報量(シャノンエントロピー)の操作上の意味を確立する定理である。1948年のクロード・シャノンの論文『通信の数学的理論』で発表された。シャノンの第二基本定理(通信路符号化定理)に対してシャノンの第一基本定理とも言う。
情報源符号化定理によれば、(独立同分布(iid)の確率変数のデータの列の長さが無限大に近づくにつれて)、符号化率(記号1つ当たりの平均符号長)が情報源のシャノンエントロピーよりも小さいデータを、情報が失われることが事実上確実ではないように圧縮することは不可能である。しかし、損失の可能性が無視できる場合、符号化率を任意にシャノンエントロピーに近づけることは可能である。
シンボルコードの情報源符号化定理は、入力語(確率変数と見なされる)のエントロピーとターゲットアルファベットの大きさの関数として、符号語の可能な期待される長さに上限と下限を設定する。