誤り訂正符号 - waxwing_k @ ウィキ

誤り検出またはエラー検出とは，
データに符号誤り（エラー）が発生した場合に
それを検出する技術である．

さらに，誤りを検出し訂正する技術を
誤り訂正またはエラー訂正と呼ぶ．

これらを総称して，誤り検出訂正と呼ぶ．

誤り検出訂正により，記憶装置やデジタル通信・信号処理の信頼性が確保されている．

誤りの種類

---

誤りには

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

の2種類がある．

誤り検出・訂正の例

---

誤り検出

• ２重化
  • バックアップ
  • ミラーリング（RAID-1）
  • 一方向誤り訂正（FEC, Forward Error Correction）
• パリティ符号（パリティチェック）（シリアル通信，RAID-3/4/5/6）
  • 垂直パリティチェック（VRC）
  • 水平パリティチェック（LRC）
• 定比率符号（l out of n 符号）
• チェックサム
  • 群計数チェック
• 巡回符号
  • 巡回冗長検査（CRC）（フロッピーディスク，USB）
• ハッシュ関数
  • MD4
  • MD5
  • SHA-1

誤り訂正

• 多重化
  • 反復符号（repitition code）
• 縦横パリティ
• ハミング符号（RAM, RAID-2）
• 巡回符号
  • 巡回ハミング符号
  • BCH符号（BCH code）（自動車無線: 43, 41, 衛星ラジオ: 63, 56）
    • リード・ソロモン符号（RS code, RSC）
      • CIRC（Cross-Interleaved Reed-Solomon Code）（CD）
    • リードソロモン積符号（RSP符号）（DAT）
  • 差集合巡回符号
    • 短縮化差集合巡回符号（文字放送: 272, 190）
  • ファイア符号（ハードディスク）
• 畳み込み符号（convolutional code）
  • Hagelbarger code
  • 最尤復号符号, ビタビアルゴリズム
• 疎グラフ符号 (sparse graph code)
  • ターボ符号 (turbo code)
  • 低密度パリティ検査符号 (LDPC, low-density parity-check code)
• binary Golay code