Web教材一覧ハードウェアとソフトウェア

誤り検出と訂正

学習のポイント

キーワード

チェックデジット、パリティチェック、CRC方式、ハミング符号


チェックデジット

長い数字列のコードの場合は入力誤りをしがちです。それで、コードの末尾に1桁のチェック用の桁をもうけておき、例えばコードの各桁を加算したときの1の位の数字を入れておき、コード入力したときに計算をして、答が合致するかどうかをチェックする方法があります(実際には後述のような複雑な計算をします)。そのチェック用の桁をチェックデジットといいます。
 POSシステムではJANコード(バーコード)をスキャンしますが、読み取りエラーを防ぐために、JANコードにはチェックデジットがつけられています。

JANコード

JANコードは12桁のコードと1桁のチェックデジットからできています。次の手順によりチェックデジットを計算します(モジュラス10、ウエイト1、3の計算方法)。
 12桁のコード部分を「4 9 1 0 1 2 3 4 5 0 6 4 」とします。

垂直パリティチェック方式(Vertical Redundancy Check)

キャラクタ単位に、誤りがないかチェックする方式です。送信時にキャラクタ内の1の個数がすべて偶数個(偶数パリティといいます。すべて奇数にするなら奇数パリティです)になるように,1ビットのパリティビットを付加して送信します。受信側で1のビット数を数えることにより誤りの検出ができます。簡単な方法であり,奇数個の誤りは検出できますが,偶数個の誤り時には検出できません。また訂正はできません。

垂直パリティチェック方式

水平パリティチェック方式(Longitudinal Redundancy Check)

ブロックについて,キャラクタの各ビット桁の1の数が偶数になるようにBCC(Block Check Character)を付加して、誤りを検出する方式です。一般に垂直パリティ方式と併せて使用されます。受信側で垂直・水平パリティチェックをすることにより,誤りの訂正もできます。しかし,検出できない場合もあります。

水平パリティチェック方式

CRC方式(Cyclic Redundancy Check)

巡回符号検査方式ともいいます。送信データをビット列を多項式として,それを決められた生成多項式(16ビットの生成多項式はX16+X12+X+1)で割り,その余りのビット列を付加します。受信側ではその逆算を行って誤りを検出します。非常に高い精度で の誤り検出が可能です。特に通信では連続的にビット誤りが発生します。それをバースト誤りといいますが,その検出に効果的です。CRCはHDLCでの誤り制御に採用されているので,LANやインターネットで広く用いられている方法です。

CRCの説明はかなり面倒ですので,簡単な例題で説明します。

 例えば,送信するべきビット列を1111,生成多項式をG(X)=X+X+1とします。すると,

   X X X  1   X X X X X X  1
                1  1     1         .
   1  0  1  1 ) 1  1  1  1         
                1  0  1  1         .
                   1  
                   1  0  1  1      .
                         1  1
                         1  0  1  1
                            1  1  1

となります(ここで0-1が-1ではなく,+1になっていますが,気にしないでください)。

余りがX+X+1ですので,付加するビットは111になり,これを検査ビット(FCS)といいます。

 受信側にデータ1111とFCS111が送られてきたときは,
   X X X  1   X X X X X X  1
                1  1     1         .
   1  0  1  1 ) 1  1  1  1  1  1  1      
                1  0  1  1         .
                   1  0  0  1  1  1
                   1  0  1  1      .
                         1  0  1  1
                         1  0  1  1
                                  0
となり,割り切れますので,誤りがなかったことがわかります。

 1101111が送られてきたときは,
   X X X  1   X X X X X X  1
                1  1  1  1         .
   1  0  1  1 ) 1  1  0  1  1  1  1      
                1  0  1  1         .
                   1  1  0  1  1  1
                   1  0  1  1      .
                      1  1  0  1  1
                      1  0  1  1   .
                         1  1  0  1
                         1  0  1  1
                            1  1  0
となり,割り切れないので,誤りがあることがわかります。

ハミング符号

(ここでは、理解を容易にするため、厳密性を欠いた説明にしています)

ハミング符号とは,情報ビットに冗長ビットを付加して,2ビットの誤り検出と1ビットの誤り訂正機能をできるようにしたものです。自動訂正機能に採用されています。
 4ビットX,X,X,Xを送りたいとします。そのとき,冗長ビットとして,

   X   +X+X+P      =偶数
   X+X   +X   +P   =偶数
   X+X+X         +P=偶数

となるようなP,P,Pの3ビットを付加して,Xを送るのです。

たとえば,1011を送るのであれば,

   1  +1+1+P      =偶数
   1+0  +1   +P   =偶数
   1+0+1        +P=偶数

から,P=1,P=0,P=0ですので,1011100として送ります。

もし,1110011を受け取ったとします。

   X X X X P P P
   1  1  0  0  1  1  1
   1    +0 +0 +1       =偶数 (a)
   1 +1    +0    +1    =奇数 (b)
   1 +1 +0          +1 =奇数 (c)

なので,bとcの両方にあってaにない変数Xが誤りで,1を0にする必要があること,すなわち,送信元は1010を送ったのだということがわかります。


理解度チェック

過去問題: 「誤りの検出と訂正」