3 符号の誤り検出・訂正

この辺の話は，参考文献 [4]にかなりわかりやすく書かれている． 余裕があると呼んでみると良い．

3.1 誤り検出と訂正がなぜ必要か?

コンピューターでは大量のデータ，すなわち気の遠くなるような0と1のビット列が取り扱 われており，一つの間違いも許されない．諸君が使っているパソコンのメインメモリーが 1G[byte]とすると，どれだけのビットがあるだろうか? $8\times 2^{30}=2^{33}\simeq 10^{10}$個のビットがある．100億個である．ハードディスクになると，その数百倍のビッ トを扱うことになる．

データのエラーは2通りの方法で生じる．一つは，メモリーやハードディスクの製造時に おける欠陥である．もう一つは，稼働時のおける書き込みあるいは読み込みの間違い，あ るいはデータ保存時にビットが変化してしまうことによるエラーである．

前者のエラー，製造時のエラーは欠陥部分を使わないようにしてしまうことにより回避で きる．いつも，同じ場所でエラーが生じるので，検査によりそのビットを使わないように する．

ここで問題とするのは後者のエラーである．すなわち，装置に欠陥が無いものの，書き込 んだものと異なる値が読み出される場合である．これは熱や宇宙線の作用により，記憶装 置のビットが変化する場合に起きる．このようなビットの変化は，ランダムに生じ，時や 場所を特定することができない．

ランダムにビットが変化するようなエラーは，情報の保存のみならず，情報の伝達の時も 生じる．情報を伝達のケーブルの電圧を下げると熱振動によるノイズの影響によりビット が変化するかもしれない．また，通信速度を上げると，パルス幅が短くなり，トランジス ターが誤動作するかもしれない．

熱や宇宙線によるこれらのビットの変化が生じる確率は，ゼロでは無いが非常に少ない．問題の無 いレベルになるように，記憶装置や通信装置を慎重に設計を行わなければならない．ただ， ゼロにすることは不可能なので，ビットが変化しても情報が失われないように，データ蓄 積と転送のとき工夫する．

データ蓄積と転送は全く異なる技術に見えるが，ランダムにビットが変化するエラーを防 ぐためには同じような技術が使える．

3.2 誤りの検出

パリティビットを使うと，蓄えた情報あるいは転送して送られてきた情報の誤りの有無が 分かる．たとえば，0110010と符号化された情報があるとする．これの最後に1ビッ ト付け加えて，列の全体の1の数を偶数³にする．すなわち，01100101とする．この ようにパリティビットを加えて，符号を記憶，あるいは転送する．

データを読み出すときに，1の数を数えれば誤りの有無が分かる．もし，何らかの原因で どれか一つのビットが反転した場合，全体の1の数は奇数となるので，おかしいと気 付く．

この方法だと，二つのビットの誤り(二重誤り)には気付かない．どのようにすれば，二重 あるいは3重の誤りが分かるだろうか?

偶数パリティを加えることにより，正しい符号のハミング距離は2以上になる．パリティ ビットを含んだ符号全体の1の数は，いつも偶数であるからである．従って，一つの誤り が生じると，正しい場合に比べてハミング距離が1変化し，不当な符号になる．もし，2重 の誤りが生じると，正しい符号と区別がつかなくなる．従って，誤りの検出ができない．

このことを一般化すると，$t$個の誤りを検出するためには，正しい符号のハミング距離 を$t+1$以上にする必要がある(図1)．

図 1: 誤りの検出限界とハミング距離の関係．

3.3 誤りの訂正

記憶装置の場合，誤りが分かっただけでは困る．データの損失になるからである．それに 対して，通信の場合は，再送信することにより，正しい情報を得ることができる．しかし， いずれの場合でも，誤りを検出すると同時に得られた誤りのある符号から，正しい符号に 訂正できれば，ハッピーである．これは，技術的に可能である．

$t$個のビットの誤りがある場合，ハミング距離が$2t+1$以上ならば，誤りを検出して訂 正までできる．このことを，図2を用いて説明する．この図，次 のように理解する．

• 誤り検出・訂正用のビットを付加して，正しい符号のハミング距離を11としてい る．
• もし，一個のビットに誤りがあると，元の正しい符号からハミング距離が1だけ離 れた場所に符号が移動する．この場合，最近接の正しい符号に戻せば，誤りの訂 正を行ったことになる．
• 二個，三個，四個，五個までならば，最近接の正しい符号に戻すことができる． このように最近接の正しい符号に戻すことにより誤りの訂正ができる．
• もし，誤りが6個以上になると，最近接の正しい符号に戻しても，元の符号に戻ら ない．誤った訂正を行ったことになり，情報が失われる．

図 2: 誤りの訂正限界とハミング距離の関係．

実際に，誤りの訂正ができることを教科書のハミング符号で示す(図 3)．この教科書のハミング符号によると，以下のようなこと が分かる．

• もし，得られた符号を検査して，$z_1$と$z_2$が間違いで，$z_3$が間違いの場合， 教科書の表2.3より，$x_1$が間違いだと分かる．
• もし，得られた符号を検査して，$z_1$が間違いで，$z_1$と$z_3$が間違いの場合， 教科書の表2.3より，$y_1$が間違いだと分かる．

ハミング符号による誤り訂正のおもしろいところは，付加したビットそのものの誤りも分 かるところである．元の符号と訂正用に付加した符号は同等に取り扱われる．

実際に使われているハミング符号は，もっと高度なもので，高速に処理ができるようになっ ている．教科書のハミング符号は，分かりやすく書くために書かれており，処理の効率は 悪い．

図 3: 教科書のハミング符号．

ホームページ: Yamamoto's laboratory
著者: 山本昌志