情報に関する理論の基礎

要点と定義

ビット列は、0と1を並べたデータ表現です。nビットで作れるパターンは各ビットに0か1を選べるため、2ⁿ通りです。したがって、ビット数の差が8ならパターン数の比は2⁸＝256になります。

論理演算はビットごとに条件を適用します。ANDは両方が1のときだけ1です。下位4ビットだけを取り出すには、上位4ビットが0、下位4ビットが1のマスクとANDを取ります。16進数0Fは8ビットで00001111です。

2進数の左シフトは、桁あふれがなければ1ビットごとに値を2倍します。2ビット左シフトした値は4xで、そこにxを足すと5xです。10xを作るなら、その5xをさらに1ビット左シフトします。

論理回路は、入力値に論理演算を組み合わせて出力を決めます。XOR（排他的論理和）は、二つの入力が異なるときに1、同じときに0を出力します。

有限オートマトンは、有限個の状態と入力による状態遷移で、文字列を受理するか判定する仕組みです。入力を順に読み、読み終えた時点で受理状態にいれば、その列を受理します。

7セグメントLEDのような出力装置では、ビットの並びと各ビットの接続先、点灯条件を合わせて表示を決めます。アノードコモン型の例では出力0で点灯するため、ビット値と点灯状態の対応を逆に読む必要があります。

CRCは、ビット列を生成多項式で割った余りを付加し、受信側でも同じ多項式で割った余りを調べる誤り検出方式です。余りによって伝送中の誤りを検出する考え方であり、この説明だけから誤り訂正までできるとはいえません。

適用条件と例

ビット数からパターン数を求めるときは、各ビットが独立に0または1を取れるものとして2ⁿを使います。24ビットから32ビットへの増加なら、比は2³²÷2²⁴＝2⁸＝256です。表現できるパターン数の比較であり、実際の利用可能な値の範囲は、数値表現の方式など別の条件に左右されます。

マスクは、残したい位置に1、消したい位置に0を置きます。たとえば8ビット値10110110に00001111をANDすると、00000110です。下位4ビットは1とのANDで保たれ、上位4ビットは0とのANDで消えます。ORでは下位ビットが1に変わることがあり、XORでは反転するため、元の下位ビットを保つ目的に合いません。

左シフトを掛け算として扱えるのは、固定幅のレジスタで桁あふれが起きないなど、値が失われない条件です。xを10倍する例では、xを2ビット左シフトして4x、xを足して5x、さらに1ビット左シフトして10xと追います。途中であふれれば、単純な整数の掛け算と同じ結果にならないことがあります。

XORの確認には真理値を場合分けします。同じ入力の組なら出力0、異なる組なら出力1です。複雑なゲート回路も、途中の出力を順に書き出せば、最終的な入力と出力の関係に整理できます。

オートマトンでは、開始状態から入力を一文字ずつ読み、状態遷移を追跡します。たとえば「まず1を読み、その後0を読めば受理状態に入り、以後は0と1のどちらでもそこに留まる」機械なら、1010は受理されます。受理状態に到達する前に入力が終われば受理されません。