【応用情報】みんなが悩むはまりどころ「基礎理論」のスピードアンサー(2) ～ 情報や通信に関する理論

有限オートマトンが受理する入力列

出題分類：基礎理論 > 情報に関する理論

［出題：平成21年春／AP午前問3］※「AP」は応用情報技術者試験を表す略号です。

正解は「ウ」

これで解ける

オートマトンとは、ある状態に対して何らかの入力を受け付けた結果、状態が遷移するといった内容を表すもので、状態とその変化を状態遷移図などで表します。

問題文の図では、太い矢印が開始状態（S₁）で、「1」の変化があるとS₂へ状態が遷移することを表しています。最終的に◎のS₃で入力が終了すると「受理」と呼ばれる状態になります。

上記問題の状態遷移図の初期状態と受理状態を意識しながら、丁寧にトレースすれば、答えを求められます。

• 選択肢ア　S₁から1011だと、最後はS₂の状態になる。
• 選択肢イ　S₁から1100だと、S₃を経由して最後はS₂の状態になる。
• 選択肢ウ　S₁から1101だと、最後はS₃の状態になる（受理）。
• 選択肢エ　S₁から1110だと、最後はS₂の状態になる。

よって、正解は「ウ」です。

ハミング符号

出題分類：基礎理論 > 通信に関する理論

［出題：平成24年秋／AP午前問3］

正解は「エ」

理解を深める

問題文にある y₁ y₂ y₃ y₄ y₅ y₆ y₇ = 1100010 を具体的に代入して考えます。

(y₁＋y₂＋y₃＋y₅) mod 2　→　(1＋1＋0＋0) mod 2 = 2 mod 2 = 0
(y₁＋y₂＋y₄＋y₆) mod 2　→　(1＋1＋0＋1) mod 2 = 3 mod 2 = 1
(y₂＋y₃＋y₄＋y₇) mod 2　→　(1＋0＋0＋0) mod 2 = 1 mod 2 = 1

つまり、2つ目、3つ目が0になっていないため、誤りがあることがわかります。2つ目、3つ目の式に共通する情報ビットは「y₄」です。したがって、y₄を修正します。

y₁ y₂ y₃ y₄ = 1100　→　1101

よって、正解は「エ」となります。

ビット誤り

出題分類：基礎理論 > 通信に関する理論

［出題：平成24年春／AP午前問5］

正解は「ア」

理解を深める

パリティビットとは、1のビット数が奇数個または偶数個になるように調整するビットを付加し、誤りを検出するものです。パリティビットを付加する方向により、「垂直パリティ」と「水平パリティ」の2種類があります。

パリティビットを使っても基本的には、誤りを訂正することはできませんが、水平・垂直の両方向にパリティを付加する「水平垂直パリティチェック方式」であれば、行・列が交差した点の1ビットの訂正が可能になります。