情報源とは

/情報・暗号

情報源

情報源とは、事象が系列となって次々出てくるもので、ある事象の発生する確率が過去に発生した事象の依存する場合を言います。

例えばアルファベットの場合、情報源は26個の文字($a,b,c,\cdots,z$)が手持ちとし、時刻 $t$ から{$\mathrm{hellow}\cdots$}の順に文字が発生したとすると、確率変数 $x$ は次のように表されます。

$$x_t=’\mathrm{h}’ , x_{t+1}=’\mathrm{e}’ , x_{t+2}=’\mathrm{l}’ ,\cdots$$

一般に、発生する文字列が{$x_{t-s},\cdots,x_{t-1},x_t$}である確率を、

$$p(x_{t-s}\cdots x_{t-1}x_t)$$

文字列{$x_{t-s}\cdots x_{t-1}$}にの後に文字 $x_t$ が発生する確率を、

$$p(x_t|x_{t-s}\cdots x_{t-1})$$

で定義すると、これらの関係は以下で表されます。

$$p(x_{t-s}\cdots x_{t-1}x_t)=p(x_t|x_{t-s}\cdots x_{t-1})p(x_{t-s}\cdots x_{t-1})$$

情報源のエントロピー

情報源のエントロピーとは、情報源から出る文字のエントロピーです。時刻 $t$ に文字 $x_t$ が出る確率は $p(x_t)$ であるため、このエントロピー $H$ は以下で表されます。ここでの和は、文字の種類の和となります。

$$H(x_t)=-\sum_{x_t}p(x_t)\log_2{p(x_t)}$$

情報源は定常的で、文字の発生確率は時間により変化しない前提を置くと以下になります。

$$H(x)=-\sum_xp(x)\log_2{p(x)}$$

情報源から続いて2文字 $x_1,x_2$ が出る場合のエントロピーは、

$$H(x_1x_2)=-\sum_{x_1,x_2}p(x_1x_2)\log_2{p(x_1x_2)}$$

2文字の間に相関があれば、独単である場合のエントロピーより小さくなります。

$$H(x_1x_2)\le H(x)$$

一般に $n$ 文字続く場合のエントロピーは、$x^n=x_1x_2\cdots x_n$ と置くと以下で表されます。

$$H(x^n)=-\sum_{x^n}p(x^n)\log_2{p(x^n)}$$

この場合、1文字当たりのエントロピー $H_n$ は、

$$H_n=\frac{H(x^n)}{n}$$

さらに情報源の1文字当たりのエントロピーは以下で定義されます。

$$H\equiv\lim_{n\to0}H_n$$

情報源の冗長度

冗長度とは、同じエントロピーを出す無駄のない(文字間に相関が無い)情報源との差分です。言い換えると、同じ情報を伝えるという前提で、削減可能な文字数の割合です。

例えば、文字の種類が $k$ の場合、相関が無ければ文字は $p_i=1/k$ の確率で発生します。このときのエントロピーは、

$$H_0=-\sum_{i=1}^kp_i\log_2{p_i}=\log_2{k}$$

実際のエントロピーを $H$ とすると、冗長度 $r$ は以下で求められます。

$$r=\frac{H_0-H}{H_0}$$

 

数理の散策路
力学、電磁気・相対論、熱・統計力学、量子力学、物性物理、機械学習、情報処理、金融、物理数学

Wikipedia

 

タイトルとURLをコピーしました