情報源とは

/情報・暗号

情報源とは

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

例えばアルファベットの場合、情報源は26個の文字($a,b,c,\cdots,z$)が手持ちとし、時刻 $t$ から{$\mathrm{hello}\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文字の場合

情報源から続いて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文字の場合

一般に $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\to\infty}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}$$

 

数学
解析学、代数学、幾何学、統計学、論理・基礎論、情報・暗号、機械学習、金融・ゲーム理論、高校数学
散策路TOP
数学、応用数学、古典物理、量子力学、物性論、電子工学、IT、力学、電磁気学、熱・統計力学、連続体力学、解析学、代数学、幾何学、統計学、論理・基礎論、プラズマ物理、量子コンピュータ、情報・暗号、機械学習、金融・ゲーム理論

Wikipedia

 

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