シンボルコードの情報源符号化定理の証明
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/11/13 23:47 UTC 版)
「シャノンの情報源符号化定理」の記事における「シンボルコードの情報源符号化定理の証明」の解説
1 ≤ i ≤ n について、si をそれぞれ可能な xi の語長とする。 q i = a − s i / C {\displaystyle q_{i}=a^{-s_{i}}/C} と定義する。ここで、 C は q1 + ... + qn = 1 となるように選択される。 H ( X ) = − ∑ i = 1 n p i log 2 p i ≤ − ∑ i = 1 n p i log 2 q i = − ∑ i = 1 n p i log 2 a − s i + ∑ i = 1 n p i log 2 C = − ∑ i = 1 n p i log 2 a − s i + log 2 C ≤ − ∑ i = 1 n − s i p i log 2 a ≤ E S log 2 a {\displaystyle {\begin{aligned}H(X)&=-\sum _{i=1}^{n}p_{i}\log _{2}p_{i}\\&\leq -\sum _{i=1}^{n}p_{i}\log _{2}q_{i}\\&=-\sum _{i=1}^{n}p_{i}\log _{2}a^{-s_{i}}+\sum _{i=1}^{n}p_{i}\log _{2}C\\&=-\sum _{i=1}^{n}p_{i}\log _{2}a^{-s_{i}}+\log _{2}C\\&\leq -\sum _{i=1}^{n}-s_{i}p_{i}\log _{2}a\\&\leq \mathbb {E} S\log _{2}a\\\end{aligned}}} ここで、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} であり a − s i ≤ p i {\displaystyle a^{-s_{i}}\leq p_{i}} であり ∑ a − s i ≤ ∑ p i = 1 {\displaystyle \sum a^{-s_{i}}\leq \sum p_{i}=1} よって、クラフトの不等式には、これらの語長を持つ接頭辞のない符号が存在する。従って、最小の S は以下を満たす。 E S = ∑ p i s i < ∑ p i ( − log a p i + 1 ) = ∑ − p i log 2 p i log 2 a + 1 = H ( X ) log 2 a + 1 {\displaystyle {\begin{aligned}\mathbb {E} S&=\sum p_{i}s_{i}\\&<\sum p_{i}\left(-\log _{a}p_{i}+1\right)\\&=\sum -p_{i}{\frac {\log _{2}p_{i}}{\log _{2}a}}+1\\&={\frac {H(X)}{\log _{2}a}}+1\\\end{aligned}}}
※この「シンボルコードの情報源符号化定理の証明」の解説は、「シャノンの情報源符号化定理」の解説の一部です。
「シンボルコードの情報源符号化定理の証明」を含む「シャノンの情報源符号化定理」の記事については、「シャノンの情報源符号化定理」の概要を参照ください。
- シンボルコードの情報源符号化定理の証明のページへのリンク
