SIGMA-SE Math & Tech Library

SIGMA-SE Math & Tech Library


数学と情報技術をテーマに、書籍や教材だけではつかみにくい考え方を具体例とともに簡潔にわかりやすく伝える解説サイトです。
技術の歴史や背景、関連知識の整理、学習のための覚書や要約記事も掲載しています。

応用情報技術 - 基礎：4/21 通信・制御理論（誤り検出・A/D変換・制御方式）

情報技術 情報処理の基礎 基礎理論 応用情報技術
作成日： 更新日：

概要

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

ビットを反転させた受信値や電圧の量子化例を使い、検出・訂正・変換の仕組みを追う。標本化の境界条件と測定結果を戻して制御する意味も確認する。

この記事の構成

誤り検出と訂正

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

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

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

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

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

    • 例 : \(7\) ビットのデータ \(1110011\) に奇数パリティを付加する。

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

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

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

  • 2ビットの反転を見逃す理由
    偶数パリティでデータ 1110011 にパリティビット1を付けた 11100111 を送る。1の個数は6個である。

    受信値が 11000111 なら、1個だけ反転して1の個数が5個となり、誤りを検出できる。一方、 10000111 では二つの1が0へ変わり、1の個数は4個に戻るため、パリティ検査を通ってしまう。パリティが確認するのは個数の偶奇であり、元のビット列との一致ではない。

垂直・水平パリティ（ \(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の略。

  • 検査結果の組合せで反転した位置を区別する
    上の配置 X1 X2 X3 P3 X4 P2 P1 で偶数パリティを使う。三つの検査をそれぞれ X1 XOR X3 XOR X4 XOR P1 、 X1 XOR X2 XOR X4 XOR P2 、 X1 XOR X2 XOR X3 XOR P3 とする。誤りがなければすべて0になる。

    上の受信例の検査結果1、1、1は三つすべてに含まれるX1を指している。訂正後の 0110011 を再び検査すると0、0、0になる。ただし、この位置特定は 1ビットだけの誤りという前提 に依存する。

    三つの検査結果には \(2^3=8\) 通りあり、誤りなしの1通りと7位置の単一ビット誤りを区別できる。ただし、2ビット以上の誤りまでこの推論を適用すると、誤った位置を訂正する場合がある。SECDEDで全体パリティを追加するのはこの区別を補うためである。

CRC

  • CRC (Cyclic Redundancy Check)
    基本的なCRCの説明では、次数rの生成多項式に対して送信データの末尾へr個の0を付け、XORを用いた多項式除算を行う。その剰余を末尾のrビットに置いて送信し、受信側でも同じ生成多項式による剰余を確認する。剰余0は検査を通ったことを表し、すべての誤りがないことの保証ではない。実際のCRC規格では初期値やビットの反転などの条件も定められる。

  • バースト誤り
    ケーブル不良や混信などによってある範囲にまとまってビット誤りが生じること。最初と最後の誤りビットの間には誤っていないビットが含まれる場合もある。
    この誤り検出には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\)バイト]

  • 標本化の細かさと量子化の細かさは別に決める
    0 V以上4 V未満を2 bitで表す簡単な量子化器を考える。区間を0〜1 V、1〜2 V、2〜3 V、3〜4 Vに分け、それぞれ 00 、 01 、 10 、 11 を割り当てる。2.6 Vは 10 となり、復元値を区間の中央の2.5 Vに決めると誤差は−0.1 Vである。

    この例では入力が範囲内なら量子化誤差の絶対値は最大0.5 V。ビット数を増やせば電圧方向の刻みは細かくなるが、時間方向の取りこぼしは解消しない。逆に標本化回数を増やしても、同じ区間内の2.1 Vと2.9 Vを2 bitのまま区別することはできない。

標本化定理

  • 標本化定理
    最高周波数が \(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\) マイクロ秒であり、実際にはこれより短い周期を選ぶ。

  • 最高周波数のちょうど2倍を設計値にしない理由
    周波数20 kHzの正弦波を40 kHzで標本化すると、位相によってはゼロ交差の瞬間ばかりを観測し、すべて0になる。そのため、任意の位相の信号を扱うには最高周波数の2倍という境界を超える余裕を持たせる。

    実際の設計では標本化前に高い周波数成分を抑えるフィルタにも余裕が必要になる。「20 kHzだから40 kHzで必ず復元できる」ではなく、帯域制限の条件と標本化周波数を組にして考える。

制御システム

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

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

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

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

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

  • 設定した時間だけ動かす場合と結果を見て調整する場合
    室温を22℃にしたいとき、「暖房を10分動かす」だけなら、実際の室温を出力に戻していない。外気温や窓の開閉によって10分後の温度は変わる。

    これに対して温度センサーで20℃を測り、目標との差2℃を使って暖房出力を調整するのがフィードバック制御である。外乱で室温が下がった場合も測定結果から調整できる。ただし、反応を強くしすぎたり測定・加熱に遅れがあったりすると、目標を行き過ぎて振動することもある。フィードバックを使うこと自体が安定性を保証するわけではない。

まとめ

  • 誤り検出は誤りを見つけ、誤り訂正は誤ったビットを直す。CRCは主に検出、通常のハミング符号は1ビット訂正、SECDEDは1ビット訂正と2ビット検出に使われる。
  • 垂直・水平パリティを組み合わせると、行方向と列方向から誤り位置を特定しやすい。
  • A/D変換では時間方向を切り出す標本化、値を段階化する量子化、ビット列にする符号化の順に処理。
  • 標本化定理では元信号の最大周波数とその信号を復元するために必要な標本化周波数の関係を扱う。
  • 検査を通ったことは元データとの一致の保証ではない。誤り数、入力範囲、信号の帯域など、各方式が成り立つ条件を確認して使う。

参考文献

この記事を共有
Xで共有 Facebookで共有 LINEで共有

「情報技術」の最新 5件
・情報セキュリティ - 暗号技術：10/10 耐量子暗号と最新暗号技術の仕組み
・情報セキュリティ - 暗号技術：9/10 実用暗号とTLSの仕組み
・情報セキュリティ - 暗号技術：8/10 公開鍵暗号とデジタル署名の仕組み
・情報セキュリティ - 暗号技術：7/10 共通鍵暗号とDESの仕組み
・情報セキュリティ - 暗号技術：6/10 機械暗号と暗号解読の仕組み

情報技術 情報処理の基礎 基礎理論 応用情報技術
作成日： 更新日：
カテゴリー
タグ Python 応用情報技術 機械学習 NumPy Python基礎 ニューラルネットワーク 暗号技術 基礎理論 深層学習 VPS Angular Django 古典暗号 Webシステム Matplotlib Git タスク指向型対話 データベース ハードウェア GitHub Apache Nginx CentOS SSH デバッグ TypeScript uWSGI scikit-learn Telegram OpenWeatherMap Let's Encrypt PostgresSQL SSL/TLS DNS systemd 中学数学 高校数学 0除算 SCXML MeCab LaTeX MathML MathJax venv Vim 共通鍵暗号 公開鍵暗号 現代暗号 耐量子暗号 換字式暗号 頻度分析 多表式暗号 近代暗号 軍事暗号 機械暗号 SQL Node.js データ構造 アルゴリズム OS UI/UX マルチメディア 乗算 除算 分数 逆数 算数 累乗 指数法則
サイトマップ
Copyright SIGMA-SE All Rights Reserved.
s-hama@sigma-se.jp