2016/03/31

パリティビットと誤り検出


1の数の偶奇の情報を付加することで誤りを検出できる(ことがある)。

やりたいこと

情報を送る際,(ノイズが入ったり攻撃を受けたりすることにより)送信者が送った信号が受信者に正しく伝わらないことがあります。

そこで,送信者があらかじめ冗長な情報を付加することによって,ある程度なら間違いを検出(誤り検出)したり,訂正(誤り訂正)したりすることができます。

ここでは,誤り検出の方法の一番簡単な例として,パリティビットを用いる方法を紹介します。

ちなみに(数学において)パリティとは,偶奇性のことです。

パリティビットの例

情報はビット列(0, 1の列)で送ります。

状況設定

送信者が 0011000 という情報を送る
(途中で1ビット反転してしまう)
受信者が 0011010 を受け取る
→正しくつたわらない!

解決策

あらかじめ送信者がパリティビットを付加(1の数が偶数個なら0,奇数個なら1を末尾につける)して送る。つまり,
00110000を送る
(途中で1ビット反転してしまう)
受信者が 00110100 を受け取る
→受信者は,末尾以外の1の数が奇数個なのに末尾が0なので,おかしいと気づく!

ちなみに,この方式を偶数パリティチェックと言います(1の数を偶数個にするよう調節するため)。一方,1の数が偶数個なら1,奇数個なら0を付加する方式を奇数パリティチェックと言います。

パリティチェックでできること

ビット反転の個数が奇数個なら誤り検出可能ですが,偶数個の場合,誤りを検出することはできません。また,誤りを検出できても,それを訂正することはできません(どのビットが反転してしまったかは分からない)。

これらの問題を解決するためには,より多くの冗長な情報を付加する必要があります。

例えば,4ビットの情報を送りたいときに,3ビットの冗長な情報をうまく付加することによって,

  • 1ビットの反転なら誤り訂正可能(どこが反転してしまったかも分かる)
  • 2ビットの反転なら誤り検出可能

という性質を持たせることができます(ハミング符号)。

数式の計算などでも,2箇所間違った結果正解だった,ラッキー,なんてこともたまにありますね。