前のページ 1/2 次のページ

誤り検出訂正(あやまりけんしゅつていせい)またはエラー検出訂正 (error detection and correction)とは、データに符号誤り(エラー)が発生した場合にそれを検出、あるいは検出し訂正することである。検出だけをする誤り検出またはエラー検出と、検出し訂正する誤り訂正またはエラー訂正を区別することもある。誤り検出訂正により、記憶装置やデジタル通信・信号処理の信頼性が確保されている。

◆ 誤り検出と誤り訂正

一般に誤り検出訂正では、k 単位長(k ビット、k バイト など)の符号を、n = m + k 単位長の符号語に変換する。これを (n, k) 符号、あるいは、符号形式を添えて (n, k) ××符号などと呼ぶ(誤り訂正符号を特にECCと略す)。符号語は、最小ハミング距離が d > 1、つまり、互いに少なくとも d 単位が異なっていて、この冗長性を利用して誤り検出訂正がなされる。dを添えて、 (n, k, d) 符号ともいう。

適切な (n, k, d) 符号は、符号語あたり d - 1 単位の誤りを検出でき、[外部リンク] - 1) / 2 単位([外部リンク] は床関数)の誤りを訂正できる。d ≦ 2 ならば、誤り訂正能力は [外部リンク] - 1) / 2 = 0 となり、単なる誤り検出となる。ただし、データの消失に対しては、つまり誤り位置がわかっているときは、d 単位の消失を訂正できる。これを特に、消失訂正と呼ぶ。単なる誤り訂正も、最低 1 単位の消失訂正能力を持つ。

たとえば、(2, 1, 2) 符号であるミラーリングは、

・ どちらかに誤りが起これば検出できるが、両方に起これば検出できない。(誤り検出能力1)

・ どちらか(どちらかはわからない)に誤りが起これば訂正できない。(誤り訂正能力0)

・ どちらかが消失すれば訂正できるが、両方に起これば訂正できない。(消失訂正能力1)

となる。(3, 1, 3) 符号である三重ミラーリングでは、誤り検出能力と消失訂正能力が2となり、誤り訂正能力1も得る。

双方向の通信では、誤り検出さえできれば誤り訂正ができなくても、送信者に再送を要求できれば、実質的に誤りを訂正できる。これを自動的におこなう仕組みを、自動再送要求 (ARQ, Automatic Repeat reQuest) と呼ぶ。

◆ バースト誤りとランダム誤り

誤りには、

・ 短い区間に多数の誤りが集中するバースト誤り

・ 散発的に単独で誤りが発生するランダム誤り

の2種類がある。

多くの誤り検出・訂正は、全体の誤り率が許容範囲でも、バースト誤りに対しては、1つのブロックに多くの誤りが集中するため、対応できない。そこで、符号の順序を入れ替え、同じブロックのデータを分散させ、バースト誤りが1つのブロックに集中しないようにする。この技術をインターリーブという。

◆ 誤り補正

特に音声や映像など、人間の感覚に訴える信号のディジタル化されたデータで真の値から多少の誤差が許容される場合、誤り検出は可能でも誤り訂正が不可能(訂正能力を超えている)かまたは誤り訂正が実装されていないとき、元のデータ自身に含まれる冗長性を利用して欠落データを予測して置き換えることがある。これを特に誤り補正と呼んで区別する。補正されたデータは真の値と一致するとは限らないが、真の値から許容される誤差内にあると期待される。CDなどでは、誤り補正がデータ読み取り誤りに対する「最後の手段」として使われている。

誤り補正では、一般には、近傍の標本に重み付けをした和、すなわちフィルタを畳み込んだ値を予測値(補正値)とする。特に、直前・直後の標本を使うものを、以下のように呼ぶ。

: $x\_n\; =\; \backslash frac(x\_+\; x\_)$ - 平均値補間

: $x\_n\; =\; x\_\backslash ,$ - 前値ホールド

: $x\_n\; =\; x\_\backslash ,$ - 後値ホールド

誤り補正は原信号自身に含まれる冗長性を使うため、データ圧縮、特に非可逆圧縮と同種の原理に基づいている。

◆ 誤り検出・訂正の例

◇ 誤り検出

・ ブロック符号

  ・ 2重化

    ・ バックアップ

    ・ ミラーリング - RAID-1

    ・ 一方向誤り訂正 (FEC, forward error correction)

  ・ パリティ符号(パリティチェック) - シリアル通信、RAID-3/4/5/6

    ・ 垂直パリティチェック (VRC)

    ・ 水平パリティチェック (LRC)

  ・ 定比率符号(l out of n 符号)

  ・ チェックサム

    ・ 群計数チェック

  ・ 巡回符号

    ・ 巡回冗長検査 (CRC) - フロッピーディスク、USB

  ・ ハッシュ関数

    ・ MD4

    ・ MD5

    ・ SHA-1

◇ 誤り訂正

・ ブロック符号

  ・ 多重化

    ・ 反復符号 (repetition code)

  ・ 縦横パリティ

  ・ ハミング符号 - RAM、RAID-2

  ・ 巡回符号

    ・ 巡回ハミング符号

    ・ ゴレイ符号

    ・* 2元ゴレイ符号 ()

    ・ BCH符号 - 自動車無線(43,31)、衛星ラジオ(63,56)

    ・* リード・ソロモン符号(RS符号、RSC)

    ・** CIRC()- CD

    ・** リードソロモン積符号 (RSP符号) - DAT

    ・ 差集合巡回符号

    ・* 短縮化差集合巡回符号 - 文字放送(272,190)

    ・ ファイア符号 - ハードディスク

  ・ 疎グラフ符号

    ・ ターボ符号 ()

    ・ 低密度パリティ検査符号 (LDPC) - 10GBASE-T (IEEE 802.3an)、Mobile WiMAX (IEEE 802.16e)

・ 畳み込み符号()

  ・

  ・ 最尤復号符号、ビタビアルゴリズム

◆ 関連項目

・ 改竄

・ 認証

・ ガロア体

前のページ 1/2 次のページ

・誤り検出訂正 page1

・誤り検出訂正 page2