「誤り検出訂正」の版間の差分
削除された内容 追加された内容
m →誤り訂正 |
m編集の要約なし |
||
| (33人の利用者による、間の39版が非表示) | |||
1行目:
{{参照方法|date=2018年1月}}
'''誤り検出訂正'''（あやまりけんしゅつていせい）または'''エラー検出訂正''' (error detection and correction/error check and correct) とは、[[データ]]に'''符号誤り'''（エラー）が発生した場合にそれを検出、あるいは検出し訂正（[[前方誤り訂正]]）することである。検出だけをする'''誤り検出'''または'''エラー検出'''と、検出し訂正する'''誤り訂正'''または'''エラー訂正'''を区別することもある。また[[改竄検出]]を含める場合も含めない場合もある。誤り検出訂正により、[[記憶装置]]や[[デジタル]]通信・信号処理の信頼性が確保されている。
== 誤り検出と誤り訂正 ==
一般に誤り検出訂正では、k 単位長（k [[ビット]]、k [[バイト (情報)|バイト]] など）の符号を、n = m + k 単位長の符号語に変換する。これを (n, k) 符号、あるいは、符号形式を添えて (n, k) ××符号などと呼ぶ（誤り訂正符号"Error Correction Code"を特に'''ECC'''と略す）。符号語は、最小[[ハミング距離]]が d > 1、つまり、互いに少なくとも d 単位が異なっていて、この[[冗長性 (情報理論)|冗長性]]を利用して[[前方誤り訂正]]が可能となる。dを添えて、(n, k, d) 符号ともいう。
適切な (n, k, d) 符号は、符号語あたり d - 1 単位の誤りを検出でき、[(d - 1) / 2] 単位（[ ] は[[床関数]]）の誤りを訂正できる。d ≦ 2 ならば、誤り訂正能力は [(d - 1) / 2] = 0 となり、単なる誤り検出となる。ただし、データの消失に対しては、つまり誤り位置がわかっているときは、d 単位の消失を訂正できる。これを特に[[消失訂正]]と呼ぶ。単なる誤り訂正も、最低 1 単位の消失訂正能力を持つ。
たとえば、(2, 1, 2) 符号である[[ミラーリング]]は、
* どちらかに誤りが起これば検出できるが、両方に起これば検出できない。（誤り検出能力1）
* どちらか（どちらかはわからない）に誤りが起これば訂正できない。（誤り訂正能力0）
* どちらかが消失すれば訂正できるが、両方に起これば訂正できない。（消失訂正能力1）
となる。(3, 1, 3) 符号である[[誤り検出訂正#誤り検出と誤り訂正|三重ミラーリング]]では、誤り検出能力と消失訂正能力が2となり、誤り訂正能力1も得る。
双方向の[[通信]]では、[[前方誤り訂正]]ができなくても誤り検出さえできれば、送信者に再送を要求することで実質的に誤りを訂正できる。これを自動的におこなう仕組みを、[[自動再送要求]] (ARQ, Automatic Repeat reQuest) と呼ぶ。
== バースト誤りとランダム誤り ==
誤りには、
* 短い区間に多数の誤りが集中するバースト誤り
* 散発的に単独で誤りが発生するランダム誤り
の2種類がある。
多くの誤り検出・訂正は、全体の誤り率が許容範囲でも、バースト誤りに対しては、1つのブロックに多くの誤りが集中するため、対応できない。そこで、符号の順序を入れ替え、同じブロックのデータを分散させ、バースト誤りが1つのブロックに集中しないようにする。この技術を[[インターリーブ]]という。
=== バースト誤り
切り替え動作、[[フェージング]]などが原因。％ＳＥＳを評価尺度に用いるのに適している。
=== ランダム誤り ===
[[熱雑音]]などが原因。[[符号誤り率|ＢＥＲ]]を評価尺度に用いるのに適している。
== 誤り補正 ==
特に音声や映像など、人間の感覚に訴える信号のディジタル化されたデータで真の値から多少の[[誤差]]が許容される場合、誤り検出は可能でも誤り訂正が不可能（訂正能力を超えている）かまたは誤り訂正が実装されていないとき、元のデータ自身に含まれる冗長性を利用して欠落データを予測して置き換えることがある。これを特に'''誤り補正''' (error compensation) と呼んで区別する。補正されたデータは真の値と一致するとは限らないが、真の値から許容される誤差内にあると期待される。[[コンパクトディスク|CD]]などでは、誤り補正がデータ読み取り誤りに対する「最後の手段」として使われている。
誤り補正では、一般には、近傍の標本に重み付けをした和、すなわちフィルタを畳み込んだ値を予測値（補正値）とする。特に、直前・直後の標本を使うものを、以下のように呼ぶ。
: <math>x_n = \frac{1}{2} (x_{n - 1} + x_{n + 1})</math> - 平均値補間
: <math>x_n = x_{n - 1} \,</math> - 前値ホールド
: <math>x_n = x_{n + 1} \,</math> - 後値ホールド
誤り補正は原信号自身に含まれる冗長性を使うため、[[データ圧縮]]、特に[[非可逆圧縮]]と同種の原理に基づいている。
== 誤り検出・訂正の例 ==
=== 誤り検出 ===
* [[ブロック符号]]
** 2重化
*** [[バックアップ]]
*** [[ミラーリング]] - [[RAID]]-1
*** [[一方向誤り訂正]] (FEC, forward error correction)
** [[パリティビット|パリティ符号]]（パリティチェック） - [[シリアル通信]]、RAID-3/4/5/6
*** [[垂直パリティチェック]] (VRC)
*** [[水平パリティチェック]] (LRC)
** [[定比率符号]]（l out of n 符号）
** [[チェックサム]]
*** [[群計数チェック]]
*** [[Luhnアルゴリズム]]
** [[巡回符号]]
*** [[巡回冗長検査]] (CRC) - [[フロッピーディスク]]、[[ユニバーサル・シリアル・バス|USB]]
==== ハッシュ(参考) ====
* [[暗号学的ハッシュ関数]] - 誤り検出の代用にしたり、改竄防止と誤り検出を兼ねることがある。(改竄や盗聴ではなく)ノイズの影響のみを考慮する場合、[[脆弱性]]があっても問題ない。
**
** [[Secure Hash Algorithm]] - [[SHA-1]] - [[SHA-2]] (SHA-224, SHA-256, SHA-384, SHA-512) - [[SHA-3]]
=== 誤り訂正 ===
* ブロック符号
** 多重化
*** 反復符号 (repetition code)
** 縦横パリティ
** [[ハミング符号]] - [[Random Access Memory|RAM]]、RAID-2
** [[巡回符号]]
*** [[巡回ハミング符号]]
*** [[ゴレイ符号]]
**** [[2元ゴレイ符号]] ([[
*** [[
**** [[リード・ソロモン符号]]（RS符号、RSC）
***** [[CIRC]]（[[
***** リードソロモン積符号 (RSP符号) - DAT
*** [[差集合巡回符号]]
**** 短縮化差集合巡回符号 - 文字放送(272,190)
*** [[ファイア符号]] - [[ハードディスク]]
** [[疎グラフ符号]]
*** [[ターボ符号]] ([[
*** [[低密度パリティ検査符号]] (LDPC) - [[
* [[畳み込み符号]]([[
** [[
** [[最尤復号符号]]、[[ビタビアルゴリズム]]([[:en:Viterbi Algorithm|Viterbi Algorithm]])
==
* 宮川 洋、岩垂 好裕、今井 秀樹：「コンピュータ基礎講座 18 符号理論」、昭晃堂、ISBN 978-4785630065（1973年）。
* 嵩 忠雄:「符号理論」、コロナ社 (1975年)。
* 嵩 忠雄：「情報と符号の理論入門」、昭晃堂、ISBN 978-4785620264（1989年12月）。
* 今井 秀樹：「符号理論」、電子情報通信学会、ISBN 978-4885520907 (1990年3月)。
* 汐崎 陽：「情報・符号理論の基礎」、国民科学社、ISBN 978-4875535041 (1991年4月)。
* 藤原 良、神保 雅一：「符号と暗号の数理」、共立出版、ISBN 978-4320026612 (1993年10月)。
* 江藤 良純、金子 敏信 (監修)：「誤り訂正符号とその応用」、オーム社、ISBN 978-4274034862（1996年12月）。
* 平沢 茂一、西島 利尚:「符号理論入門」、培風館、ISBN 978-4563014834 (1999年11月)。
* 福村晃夫、後藤宗弘：「算術符号理論」、 コロナ社、ISBN 978-4339003314 (2000年)。
* 内田 興二：「有限体と符号理論」 (臨時別冊・数理科学、SGCライブラリ-5)、サイエンス社 (2000年)。
* 情報理論とその応用学会 (編) :「符号理論とその応用」、培風館、ISBN 978-4563014537 (2003年7月)。
* J.ユステセン、T.ホーホルト：「誤り訂正符号入門」、森北出版、ISBN 978-4627817111 (2005年9月30日)。
* 濱田 昇：「情報理論と符号理論」、共立出版、ISBN 978-4320121645 (2006年10月)。
* 坂庭 好一、渋谷 智治：「代数系と符号理論入門」、コロナ社、ISBN 978-4339024463 (2010年4月)。
* 植松 友彦：「代数系と符号理論」、オーム社、ISBN 978-4274502743 (2010年4月9日)。
* 西村 芳一：「データの符号化技術と誤り訂正の基礎」、CQ出版; 改訂新版、ISBN 978-4789846400 (2010年7月1日)。
* 和田山 正：「誤り訂正技術の基礎」、森北出版、ISBN 978-4627817319 (2010年7月6日)。
* 汐崎 陽：「情報・符号理論の基礎」、オーム社、ISBN 978-4274210075（2011年3月1日）。
* 先名 健一：「例題で学ぶ符号理論入門」、森北出版、ISBN 978-4627817418 (2011年7月15日)。
* 神谷 幸宏、川島 幸之助： 「情報・符号理論 ―ディジタル通信の基礎を学ぶ―」、オーム社、ISBN 978-4274503870 (2012年3月24日)。
* 萩原学：「符号理論: デジタルコミュニケーションにおける数学」、日本評論社、ISBN 978-4535786646（2012年8月10日)。
* G.A.ジョーンズ、J.M.ジョーンズ： 「情報理論と符号理論」、丸善出版、ISBN 978-4621063422 (2012年7月17日)。
* Henning Stichtenoth、新妻 弘 (訳)：「代数関数体と符号理論」、共立出版、ISBN 978-4320110458 (2013年8月24日)。
* 楫 勇一:「情報・符号理論」、オーム社、ISBN 978-4274213175 (2013年10月26日)。
* 萩原 学：「進化する符号理論」、日本評論社、ISBN 978-4535787971 (2016年9月9日)。
== 関連項目 ==
* [[前方誤り訂正]]
* [[消失訂正]]
* [[改竄]]
* [[改竄検出]]
* [[符号理論]]
* [[認証]]
* [[ガロア体]]
* [[RAID]]
* [[チェックディジット]]
* [[冗長性 (情報理論)|冗長化]]
<!--*[[シャノン限界]]([[:en:Shannon limit|Shannon limit]])--><!--赤リンク-->
* [[ECCメモリ]]
{{DEFAULTSORT:あやまりけんしゆつ}}
[[Category:誤り検出訂正|*]]
[[Category:通信工学]]
[[Category:安全]]
[[Category:数学に関する記事]]
| |||