情報に関する理論

要点と定義

情報理論では、事象の生起確率と情報量の関係を扱います。底を2とする自己情報量は、確率をPとすると −log₂P で表され、確率が小さい事象ほど値が大きくなります。たとえば確率が正で、P＝1/16なら、自己情報量は −log₂(1/16)＝4ビットです。これは指定された新しい計算例であり、確率を代入して対数を求めます。

符号化は、情報を伝送・保存しやすい表現に変換することです。情報源符号化はデータ量の効率化に使われ、通信路符号化は伝送中の誤りの検出・訂正に使われます。どの方式が適切かは、必要な効率や誤りへの対応によります。

可変長符号の平均符号長は、各記号の符号長を出現確率で重み付けした和です。符号語が接頭語自由、つまりどの符号語も他の符号語の先頭部分でないなら、一意に復号できます。符号語が接頭語自由であることを確認してから平均符号長を比較する必要があります。過去の出題で扱った補足として、符号語 0、10、110、111 は接頭語自由で、指定された出現頻度を用いた平均符号長は 1.7 ビット／文字でした。この性質と計算が直接問われました。

固定長符号との長さの比較では、平均符号長だけでなく比の向きも確認します。過去の出題で扱った補足では、変換後の平均符号長が 1.9 ビット／文字、変換前が 2 ビット／文字で、変換後÷変換前＝1.9÷2＝0.95 でした。変換後の長さを変換前の長さで割る判断が必要でした。

通信路符号化では、検査情報を使って受信データの誤りを調べます。拡張ハミング符号は、全体パリティを加えることで、1ビット誤りの訂正と2ビット誤りの検出を両立させる方式として、過去の出題で扱われました。この具体的な機能は出題で確認できる補足です。

ハミング符号では、複数の検査式の結果を組み合わせて誤り位置を特定し、該当ビットを反転します。過去の出題で扱った補足として、指定された検査式を受信語に適用した結果は順に (1,1,1) となり、この組合せが X₁ の位置を示す条件でした。X₁を反転した訂正語は 0110011 です。検査結果の順序と各式の対象ビットを照合して判断します。

行・列の双方にパリティを付ける方式では、1ビット誤りが起きると、不一致となる行と列の交点から位置を特定し、反転して訂正できます。過去の出題で扱った補足では、保証される訂正能力は1ビットです。複数ビット誤りを同じ方法で一般に訂正できるとは限りません。

形式言語とオートマトンは、記号列の集合やその判定の仕組みを扱います。有限オートマトンは、入力を順に読み、状態遷移表や状態遷移図に従って状態を変えます。状態が表す履歴を読み取って、どの入力列が受理されるかを判断します。過去の出題で扱った補足として、末尾2ビットを表す状態 c は末尾が 10 の列を表します。末尾が 110 の列だけを受理したい場合、末尾2ビットだけを記録する状態では条件を区別できず、末尾3ビットを区別できる状態が必要です。

ディープラーニングは、多層のニューラルネットワークを使い、データから学習する手法です。過去の出題で扱った補足として、多層の処理を重ねて複雑な判断を可能にするという特徴が確認できます。ただし、あらゆる判断を常に正しく行うことを意味しません。

適用条件と例

平均符号長を求めるときは、符号語の長さと各記号の出現確率を対応させます。独自の例として、三つの記号に長さ1、2、3の符号語を割り当て、出現確率をそれぞれ 1/2、1/3、1/6 とすると、平均は 1×1/2＋2×1/3＋3×1/6＝5/3 ビット／文字です。確率の合計が1であることを確かめ、各長さに正しい確率を掛けます。平均が短くても、符号語の並びが一意復号可能でなければ実用上の条件を満たしません。

誤り訂正では、方式ごとに保証される誤り数を区別します。拡張ハミング符号の機能は前述の1ビット訂正・2ビット検出という条件で説明できます。行・列パリティの交点による訂正は、1ビット誤りを前提にした判断です。複数箇所の誤りでは検査結果が曖昧になったり、検出できない配置が生じたりするため、同じ訂正を保証しません。