「誤り検出訂正」の版間の差分

2006年10月7日 (土) 09:06時点における版

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

誤り検出と誤り訂正

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

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

たとえば、(2, 1) 誤り訂正であるミラーリングは、

どちらかに誤りが起これば検出できるが、両方に起これば検出できない。（誤り検出能力1）
どちらか（どちらかはわからない）に誤りが起これば訂正できない。（誤り訂正能力0）
どちらかが消失すれば訂正できるが、両方に起これば訂正できない。（消失訂正能力1）

となる。

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

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

誤りには、

短い区間に多数の誤りが集中するバースト誤り
散発的に単独で誤りが発生するランダム誤り

の2種類がある。

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

誤り補正

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

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