冗長度

１．それぞれの最大エントロピー

前ページで全事象が等確率で起るときに最大エントロピーとなると述べました。また最大エントロピーは事象の数が大きくなるごとに大きくなる事例も示しました。最大エントロピー（H_max）の事例をいくつか紹介しておきます。

\begin{equation} (1)コインを一回投げるとき\\ H_{max}=-\sum_{n=1}^2 \frac{1}{2} \log_2 \frac{1}{2}=1bit\\ (2)サイコロを一回振るとき\\ H_{max}=-\sum_{n=1}^6 \frac{1}{6} \log_2 \frac{1}{6}=\log_2 6 \risingdotseq 2.58bit\\ (3)アルファベット大文字のみ（26文字）の文字列\\ H_{max}=-\sum_{n=1}^{26} \frac{1}{26} \log_2 \frac{1}{26}=\log_2 26 \risingdotseq 4.70bit \\ (4)2バイト文字（日本語文字入力65536文字）\\ H_{max}=-\sum_{n=1}^{65536} \frac{1}{65536} \log_2 \frac{1}{65536}=\log_2 65536 = 16bit \end{equation}

最大エントロピーの式を立てることとその計算は簡単です。2バイト文字の65536文字の計算も、log関数の性質を思い出せばすぐに簡単な形に直せます。logの値が必要になる場合は、ネットのlog計算サイトを利用させてもらうとよいでしょう。

２．冗長度

冗長度はデータ圧縮の元になっている概念の一つです。データは実際の情報量よりも冗長な部分を含むので、その分だけ圧縮したりデータ破損の確認に利用できる、という考え方です。

２．１　冗長度の定義

冗長度（redundancy）の式は次の通りです。

\begin{equation} 1-\frac{H}{H_{max}} \end{equation}

0≦H/H_max≦1なので、冗長度も0≦r≦1の値を取ります。H/H_maxはそのデータのエントロピーが最大エントロピーに近づくごとに0から1に近づきます。1からそのH/H_maxを引いているので、最大エントロピーのとき1-1/1=0で冗長度最小です。逆にエントロピーが小さい（確率が小さかったり大きかったりする）場合はH/H_maxも0に近づいて、冗長度rは1に近づきます。結局のところ、出現頻度に偏りがあれば冗長な部分が多いのでデータ圧縮できますよ、ということを意味しています。

２．２　冗長度の例

冗長度を計算するための例を一つ示します。4文字（A、B、C、D）からなる文章があるとします。
出現確率は次の表の通りです。

文字	確率
A	1/4
B	1/2
C	1/8
D	1/8

そして冗長度を計算すると次の通りとなります。

\begin{equation} H_{max}=-\sum_{n=1}^4 \frac{1}{4} \log_2 \frac{1}{4}=2bit\\ H=-\frac{1}{4} \log_2 \frac{1}{4} -\frac{1}{2} \log_2 \frac{1}{2} -\frac{1}{8} \log_2 \frac{1}{8} -\frac{1}{8} \log_2 \frac{1}{8}\\ =\frac{1}{2}+\frac{1}{2}+2 \cdot \frac{3}{8}=1.75bit\\ 冗長度r=1-\frac{1.75}{2}=0.125 \end{equation}

H_max=2bit（2²=4）なので、4つの文字を表現するのに必要な数とbit数が一致しています。H_maxのとき、つまり冗長性なしのときのデータ量を「最小符号長」と呼びます。それに対して冗長性があるこの場合では、2bitよりも情報量が少ないので、情報量を保持したままデータの圧縮ができるのではないかと期待できます（必ずそうなるというわけではないですが）。

３．参照文献

• 参照文献：情報理論の基礎（https://www.clg.niigata-u.ac.jp/~lee/jyugyou/info_system/medsys004_printw.pdf)

<< 平均情報量（エントロピー）　データ圧縮 >>