概要

情報技術の基礎として理解しておきたい通信・制御理論について、誤り検出、誤り訂正、A/D変換、標本化定理、制御システムを整理する。

通信や計測では、データが途中で壊れたり、アナログ信号をディジタル化するときに情報が失われたりする。
この分野では、誤りを見つける方法、訂正する方法、信号を扱う基本ルールを理解することが重要となる。

この記事の構成

• 誤り検出と訂正
  通信時の回線状況問題などで起こるデータ送信の誤り検出と誤り訂正にはいくつかの方法がある。
• 奇数・偶数パリティ（ \(1\) ビット誤り検出）
  ビット列に含まれる \(1\) の個数を奇数または偶数にそろえ、誤りを検出する方法。
• 垂直・水平パリティ（ \(1\) ビット誤りの検出・訂正）
  二次元に並べたデータへ行・列方向のパリティを付加し、単一ビット誤りの位置を特定する方法。
• ハミング符号とSECDED
  ハミング符号とSECDEDの仕組みと要点を具体例から整理。
• CRC
  生成多項式による割り算の剰余を利用し、受信したビット列の誤りを検出する方法。
• A/D、D/A変換
  A/D変換 (Analog/Digital)：音、画像などのアナログ信号をディジタル信号に変換すること。
• 標本化定理
  標本化定理の意味と要点を具体例から整理。
• 制御システム
  センサー：動きや温度を検知・計測するための仕組みのこと。

誤り検出と訂正

通信時の回線状況問題などで起こるデータ送信の誤り検出と誤り訂正にはいくつかの方法がある。

以下、誤り検出・訂正の代表的な手法。

• \(1\) ビット誤り検出
  → 奇数・偶数パリティ
• \(1\) ビット誤りの検出・訂正
  → 垂直・水平パリティ
• \(1\) ビット誤り訂正
  → ハミング符号
• \(1\) ビット誤り訂正 \(+\ 2\) ビット誤り検出
  → 拡張ハミング符号（SECDED）
• バースト誤りなどの検出
  → CRC

奇数・偶数パリティ（ \(1\) ビット誤り検出）

ビット列に含まれる \(1\) の個数が奇数または偶数になるよう、データの末尾にパリティビットを付加して誤りを検出する。
単一ビットの反転は検出できるが、偶数個のビットが反転するとパリティが変わらず、検出できない場合がある。

• 奇数パリティ
  ビットの合計が奇数となるようにパリティビットを付加する方法。

  • 例 : \(7\) ビットのデータ \(1110011\) に奇数パリティを付加する。
    
    → \(1\) の個数の合計が奇数となるようにパリティビット \(0\) を付加する。
    → \(11100110\)

• 偶数パリティ
  ビットの合計が偶数となるようにパリティビットを付加する方法。

  • 例 : \(7\) ビットのデータ \(1110011\) に偶数パリティを付加する。
    → \(1\) の個数の合計が偶数となるようにパリティビット \(1\) を付加する。
    → \(11100111\)

垂直・水平パリティ（ \(1\) ビット誤りの検出・訂正）

• 垂直パリティ
  データ送信単位で末尾に \(1\) ビットのパリティビットを付加する方法のこと。

• 水平パリティ
  垂直パリティを付加した各データ（各行）を横断的（全ての各列）に対して \(1\) ビットのパリティビットを付加する方法のこと。

  垂直パリティと水平パリティを組み合わせると、単一ビット誤りではパリティが一致しない行と列の交点から誤り位置を特定し、ビット反転で訂正できる。複数ビットの誤りでは、誤りの配置によって検出できなかったり、位置を一意に特定できなかったりする。

ハミング符号とSECDED

• ハミング符号
  複数の冗長ビットを付加し、\(1\) ビットの誤りを訂正する仕組みのこと。通常のハミング符号は、訂正を行わず検出だけに使えば \(2\) ビット誤りも検出できるが、\(1\) ビット誤りの訂正と \(2\) ビット誤りの検出を同時には保証できない。

  • 例 : \(4\) ビットのデータ \(X_1,\ X_2,\ X_3,\ X_4\) に冗長ビット \(P_3,\ P_2,\ P_1\) を付加したハミング符号 \(X_1,\ X_2,\ X_3\) \(,P_3,\ X_4,\ P_2,\ P_1\) を考える。
    また、\(P_1,\ P_2,\ P_3\) は、以下（＊1）～（＊3）を満たす取り決めをする。

    （＊1）\(\ X_1 \oplus X_3 \oplus X_4\) \(\oplus P_1\ =\ 0\)
    （＊2）\(\ X_1 \oplus X_2 \oplus X_4\) \(\oplus P_2\ =\ 0\)
    （＊3）\(\ X_1 \oplus X_2 \oplus X_3\) \(\oplus P_3\ =\ 0\)

    このとき、\(1\)ビットの誤りがあるハミング符号 \(1110011\) を訂正する。

    → 受信した \(1110011\) を（＊1）～（＊3）に代入すると、三つの検査結果がすべて \(1\) となる。
    三つすべての検査対象に含まれるのは \(X_1\) のみであるため、訂正後のハミング符号は、\(X_1\) を反転した \(0110011\) となる。

• 拡張ハミング符号（SECDED）
  通常のハミング符号に、符号語全体のパリティビットを \(1\) ビット追加したもの。\(1\) ビット誤り訂正と \(2\) ビット誤り検出を両立できる。SECDEDは、Single Error Correction, Double Error Detectionの略。

CRC

• CRC (Cyclic Redundancy Check)
  送信側では、ビット列を生成多項式で割った剰余を検査用のビットとして付加する。受信側では、受信した符号語を同じ生成多項式で割り、剰余が \(0\) でなければ誤りを検出する。検出できる誤りの種類や長さは、生成多項式と符号語長によって異なる。

• バースト誤り
  ケーブル不良や混戦によって、連続した複数ビットに誤りが生じること。
  この誤り検出には、CRCが用いられている。
  （イーサネットのパケット通信でも、誤り検出にCRCが用いられている。）

A/D、D/A変換

• A/D変換 (Analog/Digital)
  音、画像などのアナログ信号をディジタル信号に変換すること。

• D/A変換 (Digital/Analog)
  ディジタル信号をアナログ信号に変換すること。

• A/D変換の原理
  A/D変換するには、以下3つの手順が必要。

  • 標本化（サンプリング）
    → アナログ信号を一定時間ごとに区切って読み込むこと。（サンプリング）

  • 量子化
    → 標本化されたアナログ値をディジタル値に変換すること。

  • 符号化
    → 量子化されたディジタル値を \(2\) 進数で表現すること。

  • 例 : サンプリング周波数が \(40\ kHz\)、量子化ビット数が \(16\) ビットでA/D変換したモノラル音声（\(1\) チャネル）の \(1\) 秒間のデータ量を求める。

    → 「サンプリング周波数が \(40\ kHz\)」であることより、標本化すると \(1\) 秒間に \(40 \times 10^3\) 回のサンプリングとなる。

    また、この \(1\) 回のサンプリング毎に「量子化ビット数が \(16\) ビット」のA/D変換となるので量子化と符号化により、「 \(1\) 秒間のデータ量」は、次の通り、\(\ 80\ \)[\(k\)バイト]となる。

    \(16\) [ビット]\(\ \times\ 40\ \times\ 10^3\) [回/秒] \(\div\ 8\) [ビット/バイト] \(=\ 80\ \times\ 10^3\)バイト \(=\ 80\ \)[\(k\)バイト]

標本化定理

• 標本化定理
  最高周波数が \(f_{max}\) に制限された信号を理想的に復元するには、少なくとも \(2f_{max}\) の標本化周波数が必要となる関係。実際のA/D変換では、折返し雑音を避けるフィルタの特性を考慮し、理論上の下限より高い周波数で標本化する。

  • 例 : \(0 ～ 20 kHz\) の帯域幅のオーディオ信号をディジタル信号に変換する際の最大サンプリング周期を求める。
    → 理論上必要なサンプリング周波数の下限は、標本化定理により
    \(20 kHz \times 2\) \(= 40 kHz\)

    ここでサンプリング周期は、サンプリング周波数 \(Hz\) の逆数（秒）となるので
    \(40 k^{-1} = 40000^{-1}\) \(= 0.000025\)（秒）\(= 25\)（マイクロ秒）となる。したがって、理論上の最大サンプリング周期は \(25\) マイクロ秒であり、実際にはこれより短い周期を選ぶ。

制御システム

• センサー
  動きや温度を検知・計測するための仕組みのこと。

• サーミスタ
  温度を測定する温度センサーのこと。

• ジャイロセンサー
  物体の角度や角速度を測定するセンサーのこと。

• 距離画像センサー
  対象までの距離を測定するセンサーのこと。
  ※ 家庭用ゲーム機などで使われており、反射する光の往復時間から距離を計測するTOF（Time of Flight）という技術が用いられている。

• アクチュエータ
  機械を物理的に正確に動かすために電気や油圧などのエネルギーを機械的な動きに変換する機構のこと。

まとめ

• 誤り検出は誤りを見つけ、誤り訂正は誤ったビットを直す。CRCは主に検出、通常のハミング符号は1ビット訂正、SECDEDは1ビット訂正と2ビット検出に使われる。
• 垂直・水平パリティを組み合わせると、行方向と列方向から誤り位置を特定しやすい。
• A/D変換では、時間方向を切り出す標本化、値を段階化する量子化、ビット列にする符号化の順に処理。
• 標本化定理では、元信号の最大周波数と、その信号を復元するために必要な標本化周波数の関係を扱う。

参考文献

• 瀬戸 美月（\(2020\)）『徹底攻略 応用情報技術者教科書』株式会社インプレス
• JOGMEC - A/D変換（日本語・アナログ／ディジタル変換の公的解説）
• NASA - Error Mitigation of Point-to-Point Communication for Fault-Tolerant Computing（英語・誤り訂正方式の技術報告）