情報理論・符号・オートマトンとAI

要点と定義

有限オートマトンは、入力記号を一つずつ読み、状態遷移によって入力列の性質を判定する仕組みです。状態が直前2ビットを表すなら、読み終えた状態で分かるのは末尾2ビットです。したがって末尾が110の列だけを受理する条件は、末尾が010の列も同じ状態になるため表現できません。末尾3ビットを区別できる状態設計が必要です。過去の出題で扱った補足として、状態遷移表から読み取れる範囲と、表現したい条件が一致するかを確かめます。

符号化は、数値や記号を決められた符号に対応付けることです。過去の出題で扱った補足として、Aを0、Bを1、…、Zを25とする英字の26進表現があります。例えば数値67は、67＝2×26＋15なので、商の2に対応するC、余りの15に対応するPを並べてCPです。各桁の重みを掛けて67に戻ることを検算できます。シラバスには代表的な文字コードが挙げられていますが、この英字を使う26進変換の細則そのものが明記されているとは扱いません。

可変長符号の平均符号長は、各符号の長さを出現確率で重み付けして求めます。例えば確率が0.5、0.3、0.2で、符号長が1、2、3ビットなら、平均は0.5×1＋0.3×2＋0.2×3＝1.7ビット／文字です。固定長が2ビット／文字なら、変換後÷変換前は1.7÷2＝0.85です。比は変換後の長さを変換前の長さで割ります。情報源符号化やハフマン符号では、出現確率に応じた符号長と平均の関係を理解します。

通信路符号化では、冗長ビットを加えて伝送誤りを検出・訂正します。ハミング符号は1ビット誤りを訂正できるように構成できます。拡張ハミング符号は全体パリティも加え、2ビット誤りの検出と1ビット誤りの訂正を両立します。これは2ビット誤りを訂正するという意味ではありません。

ハミング符号では、検査式の結果（シンドローム）と各ビット位置の対応から、1ビット誤りの位置を特定します。例として符号語を位置順にp1、p2、d1、p3、d2、d3、d4とし、検査式をそれぞれ位置1・3・5・7、2・3・6・7、4・5・6・7の排他的論理和が0になるよう定めます。データをd1=0、d2=1、d3=1、d4=0とすると、検査式からp1=1、p2=1、p3=0となり、符号語は1100110です。位置6が反転した受信語1100100の検査結果は順に0、1、1です。検査2と3に含まれ、検査1には含まれない位置6を反転して訂正します。この対応は1ビット誤りを前提とします。

過去の出題で扱った補足として、1桁の2進加算では、入力をA、B、桁上がりをX、和の1桁目をYとすると、X＝A AND B、Y＝A XOR Bです。入力00、01、10、11の順に、Xは0、0、0、1、Yは0、1、1、0です。両入力が1のときだけ桁上がりが生じ、入力が異なるときだけ和の1桁目が1になります。提示されたシラバスの個別の論理ゲート回路細目としてではなく、過去の出題で扱った補足として説明します。

ディープラーニングは、多層ニューラルネットワークを用いてデータから特徴や規則を学習し、複雑な判断などを可能にする手法です。多層のネットワークによる学習が中心です。

過去の出題で扱った補足として、論理回路の出力を確かめるときは、入力を回路式に代入して出力表と照合します。例えば中間信号がB AND Cなら、左回路の出力はE＝A AND（B AND C）、F＝D AND（B AND C）です。各入力でこの式を計算し、表の両出力と比較します。個別のゲート回路は、提示されたシラバスの細目に明記されたものとしてではなく、過去の出題で扱った補足として位置付けます。

適用条件と例

接頭語性のある符号は、どの符号語も別の符号語の先頭部分にならないため、左から順に一意に復号できます。例えばR=0、S=10、T=110、U=111とし、ビット列110010111を復号します。左から符号語を区切ると110｜0｜10｜111となり、結果はTSRUです。この符号表とビット列では区切りが一意であることを確かめて適用します。