誤り制御

■ 誤り制御。

  伝送時における誤りは、
  伝送路に固有の一定の確率で起こり、
  完全に避けることはできない。

  そこで伝送誤りが発生したとき、その都度検出したり、
  事後正しいデータに置き換えるようにすることを、
  誤り制御という。

  誤り検出の方法には、
  パリティチェック、巡回冗長検査、ハミング符号方式、
  チェックサムなどがある。

  また、誤りを検出した場合のデータの回復方法には、
  再送訂正方式と自己訂正方式がある。

■ パリティチェック。Parity Check。

  もっともシンプルな誤り検出方法。

  送信側では、ビットブロックごとに、
  パリティビット(冗長ビット)を追加し、
  1の個数の偶奇がつねに一定になるようにして送り出す。

  受信側では、ブロックに含まれる1の個数を確認し、
  もしも偶奇が合わなければデータに誤りがあると判断し、
  再送を要求する。

  (1) 垂直パリティチェック。VRC。Vertical Redundancy Check。

    1個の文字データ(7ビット)ごとに冗長ビットを付け加え、
    その8ビットの中で1の個数が偶数または奇数になるようにするもの。

  (2) 水平パリティチェック。LRC。Longitudinal Redundancy Check。

    複数個の文字データ(8ビット)に
    ブロックチェックキャラクタ(8ビット)を付け加え、
    ビット桁ごとに串刺しにしたとき、
    桁ごとの1の個数が偶数または奇数になるようにするもの。

    垂直パリティチェック方式と併用されることが多い。

  (3) 群計数チェック方式。

    水平パリティチェックを高度化したもの。

    複数個の文字データ(8ビット)について、
    ビット桁ごとの串刺し計算で各桁の1の個数を求め、
    その結果の数(2進数)のうち下位2ビットを、
    2つのチェック用文字と見立て、末尾に付加する。

    垂直パリティチェック方式と併用されることが多い。

  なお、パリティチェックでは、
  エラー箇所が奇数個であれば誤りを検出できるが、
  偶数の場合には誤りを検出できない。

■ 巡回冗長検査。CRC。Cyclic Redundancy Check。

  CRCでは、送信側と受信側で、
  生成多項式と呼ばれる計算式をあらかじめ示し合わせておく。

  送信側は、生成多項式と送信するビット列から、
  短いチェック用の符号を計算し、データの末尾に付加して送る。
  受信側では、受信したビット列と生成多項式から演算を行い、
  矛盾があればエラーあり、なければエラーなしと判断する。

  送信側
  (1) 送信するデータのビット列をXの多項式として表現する。
  (2) この多項式に、生成多項式の最高次数を掛ける。
  (3) 新しくできた多項式を、生成多項式で割り算する。mod2。
  (4) 剰余を検査用データとし、送信データに付加して送信する。

  受信側
  (1) 受信したデータのビット列をXの多項式として表現する。
  (2) この多項式に、生成多項式の最高次数を掛ける。
  (3) この多項式に、検査用データを表す多項式を加える。
  (4) 新しくできた多項式を、生成多項式で割り算する。mod2。 
  (5) 余りが0になれば、伝送誤りがないと判断できる。

  CRCは、バーストエラーに強い誤り検出方式であり、
  生成多項式がn次の場合、長さ(n-1)以下のバースト誤りをすべて検出できる。

■ ハミング符号方式。Hamming code。

  ハミング符号方式は、
  自己訂正方式(FEC)の代表とされる方式であり、
  送信データに誤り訂正符号(ECC)と呼ばれる冗長データを付加する。

　これにより伝送誤りを検出するだけでなく、 
  軽度の誤りであれば、送信元に再送要求を行わなくても、
  受信側単独で訂正できるようにしている。

  ハミング符号方式は、
  メモリの誤り制御やRAID-2などに、使われている。

■ チェックサム。Checksum。

  伝送データを数値化し、
  その合計が合致するかどうかを送受信の前後でチェックする方法。

  送信側では、データをブロックに分けて、
  その中のデータを数値として合計し、
  その合計(またはその一部)をブロックに付加する。

  受信側では、同じ方法で計算した合計が
  付加されたデータ(チェックサム)と一致するかどうかを調べる。

■ 再送訂正方式。

  誤りがあったデータの再送要求を送信側に出し、
  正しいデータをもう一度送り直してもらうこと。

  再送訂正方式ではまず、フレームを識別するため、
  個々のフレームに通し番号を付けておく。
  この識別番号のことをシーケンス番号という。

  そして受信側がフレームをを正しく受け取ると、
  ACKメッセージとシーケンス番号を返す。
  送信側はACKを受け取ると、新しいフレームを送信する。
  
  もしも壊れたデータを受信した場合には、
  受信側はNACKメッセージと共にシーケンス番号を返す。
  送信側はNACKメッセージを受け取ると、当該フレームを再送する。

  受信側からまった反応がない場合には、
  送信側はフレームの送出と同時にタイマーを起動しているので、
  タイマーが切れた時点で、当該フレームを再送する。

  この方式を使えば、
  データを確実に送り届けることができるが、
  エラーの多い回線上では再送による遅延が発生しやすい。

  (1) Stop-N-Wait。

    1つのフレームを送信するごとに、
    対応するACKメッセージが帰ってくるのを待ち、
    次のフレームを送信しない方法。

    確実に再送できるが、いちいち待つ羽目になるので、
    通信の効率はよくない。

  (2) Go-Back-N。

    一定のフレーム数に達するまでは、
    受信側からのACKメッセージを待つことなく、
    後に続くフレームを送り出す方法。

    バッファがいっぱいになるまでフレームを送信し、
    ACKが帰ってきたものから、消去していく。
    スライディングウィンドウ方式ともいう。

■ 自己訂正方式。

  データに誤りがあった場合でも、
  受信側の処理によって正しいデータを復元をできるように、
  あらかじめ専用の符号を付加して送る方法。

  送信側は、送信データから誤り訂正用の冗長ビットを作成して、
  元のデータに付加して送る。この冗長ビットのことを、
  誤り訂正符号(ECC: Error Correction Code)と呼ぶ。

  受信側では、この冗長ビットを解析して、
  再送を要求せず、単独処理によってビット誤りを回復する。
  これを前方誤り訂正(FEC:Forward Error Correction)と呼ぶ。

  この方式を使えば
  再送による遅延を避けることができるため、
  動画や音声等のリアルタイム性が要求されるデータに適している。

以上。

2004/03/15 pm