消失訂正
消失訂正(しょうしつていせい、erasure correction)とは、前方誤り訂正において、特に発生した誤りの位置が判明している場合にそれを復元することである。
改竄検出ではない誤り検出訂正符号は、たとえ誤り訂正能力を持たなくともその検出能力内であれば消失訂正が可能である。 また改竄検出であっても、総当たりをすれば消失訂正できる可能性が高い[注釈 1]。
例[編集]
消失訂正は一般に、誤り検出訂正の逆算を行なうことを言い、下記の例もそれに従う。が、基本的に消失範囲にあり得る値の全てを試行して符号語に一致する唯一の値を発見することでも可能である。
チェックサム[編集]
チェックサムは、各情報の総和を符号語とした誤り検出である。
1,2,3,4を情報とした場合、符号語は1+2+3+4=10となる。この場合、例えば三番目の情報が消失し1,2,X,4となっていた場合、(1+2+X+4)=10→10-(1+2+4)=Xとして消失した情報を得る。
パリティビット[編集]
パリティビットは、各ビットの排他的論理和を符号語としたものである。
101101を情報とした場合、排他的論理和を⊕とすると符号語は1⊕0⊕1⊕1⊕0⊕1=0となる。この場合、例えば三番目の情報が消失し10X101となっていた場合、1⊕0⊕X⊕1⊕0⊕1=1→1⊕(1⊕0⊕1⊕0⊕1)=Xとして消失した情報を得る。
応用[編集]
一般的に前方誤り訂正が求められる場合には、消失訂正よりも汎用性の高い誤り訂正が用いられる。しかし別途消失箇所を特定する手段がある場合には、汎用性の高い誤り訂正と比較して低コストな誤り検出を使用する消失訂正が用いられる。
RAID[編集]
RAIDの5および6では、水平パリティと呼ばれるパリティビット（誤り訂正能力を持たない誤り検出符号）を用いて、読み書きに失敗した[注釈 2]ハードディスクドライブを消失位置として消失訂正を行なうことで耐障害性を高めている。
さらにRAIDの6では、それに加えてQパリティと呼ばれるCRC[注釈 3]を併用することで、単独での消失訂正の他に、水平パリティと組み合わせた連立方程式を解くことで二台のハードディスクドライブが故障しても耐えられる消失訂正を行なっている。
コンピュータウイルス[編集]
ファイル圧縮伸長プログラムLHAは、そのアーカイブファイルが通信エラーなどにより破損していないことを確認するためのCRCを用いた検査能力を持っていた。この機能はアーカイブファイルとして自分自身を指定すると自己検査するようになっていた。なのでこれにコンピュータウイルスが感染すると「破損している」と看做されるので手軽に感染が判明した。そのためにコンピュータウイルス配布者はCRC符号を含めて書き換えてから配布するようにしたが、今度はオリジナルのLHAのCRC符号を公開することで対策された。そこでコンピュータウイルスの一部に未使用領域を設け、感染LHAに対して当該未使用領域が消失したものとして消失訂正を行なうことで公開CRC符号と一致する感染LHAを生成した。
これはCRC符号を始めとする誤り検出訂正符号では改竄検出ができないことを示す一例となっている。
また改竄検出であっても、その改竄検出符号ごと差し替えられてしまえば検出はできないことも示している。これを防ぐためには電子署名やメッセージ認証符号などの、単なる検出符号にとどまらない対策が必要となる。