情報源を「拡大」するッ!!

ハフマン符号とブロック符号を習ったよ！

シャノンの第一符号化定理によれば、情報源からの系列を符号化する際の平均符号長Lは、ブロック符号を用いれば、情報源のエントロピーHを下限として、小さくすることができるわけですよ。

記号a,bを出す独立生起情報源を考えるとき、それぞれの確立を

とすると、エントロピーHは

となるわけです。

っつーことは、いくらブロック符号化しても、0.72ちょいまでしか平均符号長は下がらないわけですよ。

勿論これは証明されてるわけなんですが、実際に情報源を拡大してシミュレーションしてみましたよん。

平均符号長(1次)  : 1
平均符号長(2次)  : 0.78
平均符号長(3次)  : 0.728
平均符号長(4次)  : 0.7408
平均符号長(5次)  : 0.73792
平均符号長(6次)  : 0.725248
平均符号長(7次)  : 0.731756
平均符号長(8次)  : 0.732228
平均符号長(9次)  : 0.72514
平均符号長(10次) : 0.728201
平均符号長(11次) : 0.729601
平均符号長(12次) : 0.725041
平均符号長(13次) : 0.726214
平均符号長(14次) : 0.728045
平均符号長(15次) : 0.72494

さすがに、15次に拡大すると時間がかかるな・・・・

1次っておかしいね。「１次」＝「拡大してない」って意味でよろしく。

まぁ、とりあえず0.72ちょいに収束しそうな勢いですね。

みっともないプログラムですんで、要望があれば載せますね。