誤り検出訂正

データの信頼性を支える技術：誤り検出・訂正

デジタルデータの記憶や伝送において、ノイズや機器の故障などによってデータが変化（エラー）する可能性があります。これを防ぐために、誤り検出・訂正技術が不可欠です。本記事では、この技術の基礎から応用までを詳しく解説します。

誤り検出と誤り訂正

誤り検出・訂正は、データにエラーが発生した場合に、そのエラーを検出し、場合によっては訂正する技術です。検出のみを行う誤り検出と、検出と訂正の両方を同時に行う誤り訂正があり、さらに改竄検出機能を含む場合もあります。この技術は、記憶装置やデジタル通信、信号処理など、様々な分野でデータの信頼性を確保するために活用されています。

誤り検出・訂正では、元のデータ（k単位長）に冗長性を付加して符号語（n単位長）を作成します。これを(n, k)符号と呼び、冗長性によってエラーを検出・訂正します。符号語間の最小ハミング距離dを用いて、検出可能なエラー数と訂正可能なエラー数を決定します。具体的には、d-1個のエラーを検出でき、[(d-1)/2]個のエラーを訂正できます。ただし、エラーの位置がわかっている場合は、d個の消失を訂正できます（消失訂正）。

例えば、(2, 1, 2) 符号であるミラーリングは、データの複製を作成し、どちらかのデータにエラーがあれば検出できますが、訂正はできません。一方、(3, 1, 3) 符号である三重ミラーリングでは、2個のエラーを検出、1個のエラーを訂正できます。

双方向通信では、誤り訂正機能がなくても、誤り検出によって送信側に再送を要求することで、実質的に誤りを訂正できます。この自動的な再送要求機構をARQ（Automatic Repeat reQuest）と呼びます。

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

エラーの種類には、短い区間に多くの誤りが集中するバースト誤りと、散発的に発生するランダム誤りの2種類があります。多くの誤り検出・訂正技術はランダム誤りに対して有効ですが、バースト誤りには弱いため、インターリーブという技術を用いて、データの配置順序を変更することで、バースト誤りの影響を軽減します。

バースト誤りは、信号の切り替え動作やフェージングなどが原因で発生しやすく、SES（シンボルエラー率）が評価尺度として用いられます。一方、ランダム誤りは、熱雑音などが原因で発生しやすく、BER（ビットエラー率）が評価尺度として用いられます。

誤り補正

音声や映像データなど、多少の誤差が許容されるデータでは、誤り訂正が不可能な場合や、誤り訂正が実装されていない場合に、誤り補正という手法を用いることがあります。これは、元のデータの冗長性を利用して、欠落データを予測し、置き換える技術です。元のデータと完全に一致するとは限りませんが、許容範囲内の誤差に留まることが期待されます。CDなどでは、誤り補正が最後の手段として使われています。

誤り補正では、近傍のデータに重み付けを行い、予測値を算出します。代表的な手法として、平均値補間、前値ホールド、後値ホールドなどがあります。誤り補正は、データ圧縮と同様の原理に基づいています。

誤り検出・訂正の例

様々な誤り検出・訂正技術が存在します。

誤り検出:

ブロック符号
2重化、バックアップ、ミラーリング（RAID-1）
パリティ符号（パリティチェック）：シリアル[[通信]]、RAID-3/4/5/6
チェックサム、群計数チェック、Luhnアルゴリズム
巡回符号、巡回冗長検査（CRC）：フロッピーディスク、USB
ハッシュ関数（MD5、SHAなど）：改竄防止と誤り検出を兼ねる場合もある

誤り訂正:

ブロック符号
多重化、反復符号
ハミング符号：RAM、RAID-2
巡回符号、巡回ハミング符号、ゴレイ符号
BCH符号、リード・ソロモン符号（RS符号）：CD、DAT
ターボ符号、低密度パリティ検査符号（LDPC）：10GBASE-T、Mobile WiMAX
* 畳み込み符号、ビタビアルゴリズム

これらの技術は、用途やデータの種類、エラー特性に応じて適切に選択されます。

参考文献

（ここに、本文中に挙げられた参考文献リストを挿入）