誤り検出訂正

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

1. 誤り検出と誤り訂正
------------

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

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

たとえば、 符号であるミラーリングは、

どちらかに誤りが起これば検出できるが、両方に起これば検出できない。
どちらかに誤りが起これば訂正できない。
どちらかが消失すれば訂正できるが、両方に起これば訂正できない。となる。 符号である三重ミラーリングでは、誤り検出能力と消失訂正能力が2となり、誤り訂正能力1も得る。

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

2. バースト誤りとランダム誤り
----------------

誤りには、

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

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

2.1. バースト誤り
-----------

切り替え動作、フェージングなどが原因。％ＳＥＳを評価尺度に用いるのに適している。

2.2. ランダム誤り
-----------

熱雑音などが原因。ＢＥＲを評価尺度に用いるのに適している。

3. 誤り補正
-------

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

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

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

4. 誤り検出・訂正の例
------------

4.1. 誤り検出
---------

ブロック符号
2重化
バックアップ
ミラーリング - RAID-1
一方向誤り訂正 
パリティ符号 - シリアル通信、RAID-3/4/5/6
垂直パリティチェック 
水平パリティチェック 
定比率符号
チェックサム
群計数チェック
Luhnアルゴリズム
巡回符号
巡回冗長検査  - フロッピーディスク、USB

4.1.1. ハッシュ
---------------

暗号学的ハッシュ関数 - 誤り検出の代用にしたり、改ざん防止と誤り検出を兼ねることがある。ノイズの影響のみを考慮する場合、脆弱性があっても問題ない。
MD MD4 - MD5
Secure Hash Algorithm - SHA-1 - SHA-2  - SHA-3

4.2. 誤り訂正
---------

ブロック符号
多重化
反復符号 
縦横パリティ
ハミング符号 - RAM、RAID-2
巡回符号
巡回ハミング符号
ゴレイ符号
2元ゴレイ符号 
BCH符号 - 自動車無線、衛星ラジオ
リード・ソロモン符号
CIRC- CD
リードソロモン積符号  - DAT
差集合巡回符号
短縮化差集合巡回符号 - 文字放送
ファイア符号 - ハードディスク
疎グラフ符号
ターボ符号 
低密度パリティ検査符号  - 10GBASE-T 、Mobile WiMAX 
畳み込み符号
Hagelbarger code
最尤復号符号、ビタビアルゴリズム

5. 参考図書
-------

宮川 洋、岩垂 好裕、今井 秀樹：「コンピュータ基礎講座 18 符号理論」、昭晃堂、ISBN 978-4785630065。
嵩 忠雄:「符号理論」、コロナ社 。
嵩 忠雄：「情報と符号の理論入門」、昭晃堂、ISBN 978-4785620264。
今井 秀樹：「符号理論」、電子情報通信学会、ISBN 978-4885520907 。
汐崎 陽：「情報・符号理論の基礎」、国民科学社、ISBN 978-4875535041 。
藤原 良、神保 雅一：「符号と暗号の数理」、共立出版、ISBN 978-4320026612 。
江藤 良純、金子 敏信 ：「誤り訂正符号とその応用」、オーム社、ISBN 978-4274034862。
平沢 茂一、西島 利尚:「符号理論入門」、培風館、ISBN 978-4563014834 。
福村晃夫、後藤宗弘：「算術符号理論」、 コロナ社、ISBN 978-4339003314 。
内田　興二：「有限体と符号理論」 、サイエンス社 。
情報理論とその応用学会  :「符号理論とその応用」、培風館、ISBN 978-4563014537 。
J.ユステセン、T.ホーホルト：「誤り訂正符号入門」、森北出版、ISBN 978-4627817111 。
濱田 昇：「情報理論と符号理論」、共立出版、ISBN 978-4320121645 。
坂庭 好一、渋谷 智治：「代数系と符号理論入門」、コロナ社、ISBN 978-4339024463 。
植松 友彦：「代数系と符号理論」、オーム社、ISBN 978-4274502743 。
西村 芳一：「データの符号化技術と誤り訂正の基礎」、CQ出版; 改訂新版、ISBN 978-4789846400 。
和田山 正：「誤り訂正技術の基礎」、森北出版、ISBN 978-4627817319 。
汐崎 陽：「情報・符号理論の基礎」、オーム社、ISBN 978-4274210075。
先名 健一：「例題で学ぶ符号理論入門」、森北出版、ISBN 978-4627817418 。
神谷 幸宏、川島 幸之助： 「情報・符号理論 ―ディジタル通信の基礎を学ぶ―」、オーム社、ISBN 978-4274503870 。
萩原学：「符号理論: デジタルコミュニケーションにおける数学」、日本評論社、ISBN 978-4535786646