誤り検出訂正








誤り検出訂正（あやまりけんしゅつていせい）またはエラー検出訂正 (error detection and correction/error check and correct) とは、データに符号誤り（エラー）が発生した場合にそれを検出、あるいは検出し訂正（前方誤り訂正）することである。検出だけをする誤り検出またはエラー検出と、検出し訂正する誤り訂正またはエラー訂正を区別することもある。また改竄検出を含める場合も含めない場合もある。誤り検出訂正により、記憶装置やデジタル通信・信号処理の信頼性が確保されている。




目次






  • 1 誤り検出と誤り訂正


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


  • 3 誤り補正


  • 4 誤り検出・訂正の例


    • 4.1 誤り検出


      • 4.1.1 ハッシュ(参考)




    • 4.2 誤り訂正




  • 5 参考図書


  • 6 関連項目





誤り検出と誤り訂正


一般に誤り検出訂正では、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などでは、誤り補正がデータ読み取り誤りに対する「最後の手段」として使われている。


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




xn=12(xn−1+xn+1){displaystyle x_{n}={frac {1}{2}}(x_{n-1}+x_{n+1})}x_{n}={frac {1}{2}}(x_{{n-1}}+x_{{n+1}}) - 平均値補間


xn=xn−1{displaystyle x_{n}=x_{n-1},}x_{n}=x_{{n-1}}, - 前値ホールド


xn=xn+1{displaystyle 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





ハッシュ(参考)



  • 暗号学的ハッシュ関数

    • MD MD4 - 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メモリ




Popular posts from this blog

Can a sorcerer learn a 5th-level spell early by creating spell slots using the Font of Magic feature?

Image
28 6 $begingroup$ Per the Font of Magic feature, sorcerer can use Flexible Casting to create 5th-level spell slots at level 7, even though they are not typically available until level 9. You can transform unexpended sorcery points into one spell slot as a bonus action on your turn. The Creating Spell Slots table shows the cost of creating a spell slot of [5th level is 7] If such a sorcerer levels up while still having this 5th-level spell slot, can they choose a 5th-level spell as the spell they gain upon levelling up? The Spellcasting feature states: Additionally, when you gain a level in this class, you can choose one of the sorcerer spells you know and replace it with another spell from the sorcerer spell list, which also must be of a level for which you have spell slots.
Read more

Does disintegrating a polymorphed enemy still kill it after the 2018 errata?

Image
up vote 13 down vote favorite 1 After the 2018 errata, the disintegrate spell description now reads: A creature targeted by this spell must make a Dexterity saving throw. On a failed save, the target takes 10d6 + 40 force damage. The target is disintegrated if this damage leaves it with 0 hit points. If you were to polymorph an enemy into a rat and then disintegrate it, would the enemy be disintegrated or would it just return to its original form? I know that for Druids, it’s not an instant kill anymore, but is this the case for polymorph as well? dnd-5e spells polymorph errata share | improve this question edited 18 hours ago
Read more

A Topological Invariant for $pi_3(U(n))$

Image
3 3 $begingroup$ Recently, I saw a construction of topological invariant for $pi_3(U(n))$ with $ngeq 2$ : $$ N=frac{1}{24pi^2}int_{S^3} d^3x epsilon^{ijk} Tr[(U^{-1}partial_{x_i}U)(U^{-1}partial_{x_j}U)(U^{-1}partial_{x_k}U)] , $$ where $Uin U(n)$ depends on $boldsymbol{x}=(x_1,x_2,x_3)in S^3$ , $epsilon^{ijk}$ is the Levi-Civita symbol, $i,j,k=1,2,3$ , and the duplicated indexes are summed over. It is claimed that $N$ is an integer, but why? Update 02/02/2019 I think I got an argument for $n=2$ . In this case, $U=e^{i varphi} q$ with $qin SU(2)$ . Due to the trace and the Levi-Civita symbol in $N$ , $varphi$ does not contribute to $N$ . As $Tr[q^{dagger}partial_i q]=0$ and $(q^{dagger}partial_i q)^{dagger}=-q^{dagger}partial_i q$ , $q^{dagger}partial_i q$ in geneeral has the form $q^{dagger}partia
Read more