情報に関する理論

要点と定義

情報に関する理論では、情報を数値や記号で表す方法、符号化、状態遷移などを扱います。情報をデジタル化するときは、表現の規則を決め、送受信や処理の両方で同じ規則を使います。

2進数とビット演算。 2進小数の各桁は、小数点から左へ進むごとに 1/2、1/4、1/8…の重みを持ちます。例えば、10進数の7÷32は、7/32=4/32+2/32+1/32 なので、2進小数では0.00111です。分母が2の累乗なら、このように有限桁で表せます。

ビット演算では、排他的論理和は対応するビットが異なるとき1、同じとき0になります。8ビットすべてが1の値と排他的論理和を取ると、各ビットが反転します。例えば、00101100と11111111の排他的論理和は11010011です。

ハフマン符号。 ハフマン符号化は、文字の出現頻度に応じて符号長を変え、よく出る文字には短い符号、まれな文字には長い符号を割り当てる可変長符号化です。木を作るときは、未結合の節から頻度の小さいものを二つ選んで親にまとめる操作を繰り返します。左枝を0、右枝を1とすれば、根から葉への経路がその文字の符号になります。符号のどれも別の符号の先頭部分にならないため、符号列を左から読んで一意に復号できます。

符号表ができたら、圧縮後のビット数は「各文字の出現回数×その文字の符号長」の合計です。例えば、出現回数がA=1、B=7、C=3、D=2で、符号長が順に3、1、2、3ビットなら、合計は1×3+7×1+3×2+2×3=22ビットです。各文字を固定長2ビットで表した場合は13文字で26ビットなので、圧縮率は22÷26≈0.846です。圧縮率が1より小さければ、圧縮後の方が短くなっています。

オートマトンとシフトレジスタ。 有限オートマトンは、有限個の状態と、入力に応じて次の状態を決める規則で処理を表します。出力も伴う形式では、現在の状態と入力から出力と次状態が決まります。処理を追うときは、初期状態から入力を一つずつ適用し、出力を順に記録します。

シフトレジスタは、クロックなどのタイミングに合わせてビット列を移動し、新しいビットを取り込む回路です。8ビットのレジスタに9個のビットを順に取り込んで上位方向へシフトするなら、最後に残るのは最後の8ビットです。たとえば入力列が110001101なら、保持される列は10001101となります。

機械学習とディープラーニング。 機械学習は、データから規則や特徴を学び、未知の入力に対する予測や判断に使う方法です。ディープラーニングは、多層のニューラルネットワークを用いる機械学習の一種です。人の脳神経回路に着想を得た構造で、データから認識に有用な特徴を学習します。あらかじめ人がすべての判断ルールを書く方式とは異なり、特定分野だけに限定される手法でもありません。

適用条件と例

ハフマン符号は、文字などの出現頻度が分かっていて、頻度に応じて可変長符号を設計したい場合に使えます。頻度が均等なら、固定長符号とのビット数の差が小さくなることがあります。また、符号表を共有しないと、受信側はビット列を文字へ戻せません。頻度に基づく符号化では、符号表などの付加情報も含めた総量が、実際の保存・伝送量を左右します。

符号が一意に復号できる条件は、ある符号語が別の符号語の先頭部分にならないことです。例えば、符号語に10と101の両方を使うと、ビット列101を読んだときに10と1なのか101なのか区切りを決められません。ハフマン木の葉だけに符号を割り当てれば、この先頭部分の重なりを避けられます。

オートマトンの出力列を求めるときは、入力記号の数だけ遷移を実行します。各遷移に出力が付く機械なら、その都度出力を記録します。状態だけを更新して終えると、出力付きの問題では必要な情報が抜けます。シフトレジスタでは、取り込みのタイミングとシフト方向、保持幅を確認します。幅を超える入力があれば、古いビットが押し出されます。