\(\chi^n\)上の確率質量凾数\(P(x^n)\)から求める符号長
$$\begin{array}{rl}
I(x^n)=\lceil -\log_2{P(x^n)} \rceil &\quad\dotso \chi^n上の確率質量凾数P(x^n)から求める符号長(I:\chi^n \rightarrow \mathbb{R}^{+})\\
\end{array}$$
符号長の期待値
$$\begin{array}{rl}
E\left[\mathcal{l}(x^n)\right]=\displaystyle \sum_{x^n\in \chi^n} \mathcal{l}(x^n)P(x^n)&\quad\dotso符号長の期待値, 平均符号長(average\;codeword\;length)\\
\end{array}$$
例:\(\chi=\{0,1\},\;n=2\)
| \(y_1\) |
\(y_2\) |
\(x^2\)
\(=y_1y_2\) |
\(P(x^2)\) |
\(-\log_2{P(x^2)}\)
Shannon情報量 |
\(I(x^2)=\lceil -\log_2{P(x^2)}\rceil\)
\(\chi^2\)上の確率質量凾数\(P(x^2)\)から求める符号長 |
\(\pi(x^2)\) |
\(\mathcal{l}(x^2)\)
\(=|\pi(x^2)|\) |
\(\pi'(x^2)\) |
\(\mathcal{l}'(x^2)\)
\(=|\pi'(x^2)|\) |
\(\pi''(x^2)\) |
\(\mathcal{l}''(x^2)\)
\(=|\pi''(x^2)|\) |
| 0 |
0 |
00 |
\(\frac{1}{8}\) |
\(-\log_2{\frac{1}{8}}=3\) |
\(\lceil -\log_2{\frac{1}{8}}\rceil=3\) |
000 |
3 |
1 |
1 |
00 |
2 |
| 0 |
1 |
01 |
\(\frac{1}{8}\) |
\(-\log_2{\frac{1}{8}}=3\) |
\(\lceil -\log_2{\frac{1}{8}}\rceil=3\) |
001 |
3 |
01 |
2 |
01 |
2 |
| 1 |
0 |
10 |
\(\frac{1}{4}\) |
\(-\log_2{\frac{1}{4}}=2\) |
\(\lceil -\log_2{\frac{1}{4}}\rceil=2\) |
01 |
2 |
001 |
3 |
10 |
2 |
| 1 |
1 |
11 |
\(\frac{1}{2}\) |
\(-\log_2{\frac{1}{2}}=1\) |
\(\lceil -\log_2{\frac{1}{2}}\rceil=1\) |
1 |
1 |
000 |
3 |
11 |
2 |
上記例で\(\mathcal{l}(x^2)\)が\(I\)と等しい符号化(\(\pi\))の平均符号長
$$\begin{array}{rcl}
\displaystyle E\left[\mathcal{l}(x^2)\right]
&=&\displaystyle \sum_{x^2\in \chi^2} \mathcal{l}(x^2)P(x^2)\\
&=&\displaystyle 3\times\frac{1}{8}+3\times\frac{1}{8}+2\times\frac{1}{4}+1\times\frac{1}{2}\\
&=&\displaystyle \frac{3+3+4+4}{8} = \frac{14}{8}\\
&=&\displaystyle 1+\frac{3}{4}=1.75\\
\end{array}$$
上記例で\(\mathcal{l}'(x^2)\)が\(I\)と等しくない符号化(\(\pi'\))の平均符号長
$$\begin{array}{rcl}
\displaystyle E\left[\mathcal{l}'(x^2)\right]
&=&\displaystyle \sum_{x^2\in \chi^2} \mathcal{l}'(x^2)P(x^2)\\
&=&\displaystyle 1\times\frac{1}{8}+2\times\frac{1}{8}+3\times\frac{1}{4}+3\times\frac{1}{2}\\
&=&\displaystyle \frac{1+2+6+12}{8} = \frac{21}{8}\\
&=&\displaystyle 2+\frac{5}{8}=2.625\\
\end{array}$$
上記例で\(\mathcal{l}(x^n)=2\)と常に一定となる符号化(\(\pi''\))の平均符号長
$$\begin{array}{rcl}
\displaystyle E\left[\mathcal{l}''(x^2)\right]
&=&\displaystyle \sum_{x^2\in \chi^2} \mathcal{l}''(x^2)P(x^2)\\
&=&\displaystyle 2\times\frac{1}{8}+2\times\frac{1}{8}+2\times\frac{1}{4}+2\times\frac{1}{2}\\
&=&\displaystyle 2\times\left(\frac{1}{8}+\frac{1}{8}+\frac{1}{4}+\frac{1}{2}\right)\\
&=&\displaystyle 2\times 1 \\
&=&\displaystyle 2\\
\end{array}$$
