誤り検出訂正

誤り検出訂正︵あやまりけんしゅつていせい︶またはエラー検出訂正 (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などでは、誤り補正がデータ読み取り誤りに対する﹁最後の手段﹂として使われている。

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

$x_{n}={\frac {1}{2}}(x_{n-1}+x_{n+1})$$x_{n}={\frac {1}{2}}(x_{n-1}+x_{n+1})$ - 平均値補間

$x_{n}=x_{n-1}\,$$x_{n}=x_{n-1}\,$ - 前値ホールド

$x_{n}=x_{n+1}\,$$x_{n}=x_{n+1}\,$ - 後値ホールド

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

誤り検出・訂正の例

誤り検出

●ブロック符号
●2重化
●バックアップ

●ミラーリング - RAID-1

●一方向誤り訂正 (FEC, forward error correction)

●パリティ符号︵パリティチェック︶ - シリアル通信、RAID-3/4/5/6
●垂直パリティチェック (VRC)

●水平パリティチェック (LRC)

●定比率符号︵l out of n 符号︶

●チェックサム
●群計数チェック

●Luhnアルゴリズム

●巡回符号
●巡回冗長検査 (CRC) - フロッピーディスク、USB

ハッシュ(参考)

●暗号学的ハッシュ関数 - 誤り検出の代用にしたり、改竄防止と誤り検出を兼ねることがある。(改竄や盗聴ではなく)ノイズの影響のみを考慮する場合、脆弱性があっても問題ない。
●MDMD4 - MD5

●Secure Hash Algorithm - SHA-1 - SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512) - SHA-3

誤り訂正

●ブロック符号
●多重化
●反復符号 (repetition code)

●縦横パリティ

●ハミング符号 - RAM、RAID-2

●巡回符号
●巡回ハミング符号

●ゴレイ符号
●2元ゴレイ符号 (binary Golay code)

●BCH符号 - 自動車無線(43,31)、衛星ラジオ(63,56)
●リード・ソロモン符号︵RS符号、RSC︶
●CIRC︵Cross-Interleaved Reed-Solomon Code︶- CD

●リードソロモン積符号 (RSP符号) - DAT

●差集合巡回符号
●短縮化差集合巡回符号 - 文字放送(272,190)

●ファイア符号 - ハードディスク

●疎グラフ符号
●ターボ符号 (turbo code)

●低密度パリティ検査符号 (LDPC) - 10GBASE-T (IEEE 802.3an)、Mobile WiMAX (IEEE 802.16e)

●畳み込み符号(convolutional code)
●Hagelbarger code

●最尤復号符号、ビタビアルゴリズム(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

●チェックディジット

●冗長化

●ECCメモリ