目次へ
誤り制御について

データの送信エラーをチェックする仕組みはどのようになっているのでしょうか。

物理層レベルでデータがやりとりされているとき、すなわち、信号データがケーブルなどの伝送媒体上を伝わっているときに、 雑音などの影響を受けて、データが変化してしまうことがあります。このような信号データの誤りを検出し、可能な限りエラー訂正を するために用いられる情報が、 FCS ( Frame Check Sequennse ) です。
送信側では、データから作り出したチェック情報をフレームヘッダー中の FCS にセットして送信します。受信側では、受信したデータから 同じ方法で作り出したチェック情報と受信したチェック情報そのものとを比べることにより、エラーの有無を検出します。 また、ある範囲のエラーに対しては、訂正も可能です。

このような誤り制御の方式に、 パリティチェック CRC ( Cyclic Redundancy Check ) などの方式があります。
以下に、主な誤り制御方式について説明します。

 ・ 垂直パリティ方式
 ・ 水平パリティ方式
 ・ 群計数チェック方式
 ・ CRC ( Cyclic Redundancy Check ) 方式

1) 垂直パリティ方式

垂直パリティ方式は、1ビットの誤りを検出する方式です。偶数パリティ方式と奇数パリティ方式があります。
送信データの各文字を構成するビット列に含まれるビット "1" の数をカウントし、
 ・ 偶数パリティ方式では、ビット "1"が偶数個ならば "0" 、奇数個ならば "1" 、
 ・ 奇数パリティ方式では、ビット "1"が偶数個ならば "1" 、奇数個ならば "0"
パリティビット として付加して送信します。
受信側では、ビット "1" の数をカウントし、受信したパリティビットと比較して、異なっていればエラーとします。
なお、 JIS7単位符号 を用いれば、1文字を 7 ビットで表現することができますので、 残りの 1 ビットをパリティビットにすることができます。

送信時の状態
送信データABCDE
ビット 711111
ビット 600000
ビット 500000
ビット 400000
ビット 300011
ビット 201100
ビット 110101
ビット 8
(偶数パリティビット)
00101

データ "B" のビット 5 に送信エラーが発生し、 1 となったとしましょう。
受信したパリティは 0 ですが、 再計算したら 1 となり、エラーが検出されます。
受信側の状態
送信データABCDE
ビット 711111
ビット 600000
ビット 501000
ビット 400000
ビット 300011
ビット 201100
ビット 110101
ビット 8
(偶数パリティビット)
00101
再計算結果
(偶数パリティビット)
01101


垂直パリティ方式では、誤りビットの訂正はできません。また、1文字のビット列中に2ビット以上の誤りがあると、受信側でエラー検出できないということ もデメリットです。

ページトップへ

2) 水平パリティ方式

水平パリティ方式は、連続する何文字かのデータに対して水平方向にパリティビットを付加する方式です。 一般に垂直パリティ方式と合わせて用いることにより、精度の高い誤り制御ができます。
この方式では、水平方向のビット列に含まれるビット "1" の数をカウントし、以下のようなパリティビットを付加して送信します。
 ・ 偶数パリティ方式では、ビット "1"が偶数個ならば "0" 、奇数個ならば "1" 、
 ・ 奇数パリティ方式では、ビット "1"が偶数個ならば "1" 、奇数個ならば "0"
このパリティビットのことを、 BCC ( Block Check Character ) と呼んでいます。
水平パリティ方式では、文字を構成するビット中、2ビット以上の誤りに対しても検出できます。また、1ビットの誤りならば訂正も可能です。 しかし、偶数のビットに誤りがあると、検出できない場合もあります。

送信時の状態
送信データABCDE BCC  ← 水平パリティ(奇数パリティ)
ビット 711111 0
ビット 600000 1
ビット 500000 1
ビット 400000 1
ビット 300011 1
ビット 201100 1
ビット 110101 0
ビット 8
(偶数垂直パリティ)
00101 1


ケース1:受信側の状態
送信データAB CDE BCC 再計算結果
(奇数パリティビット)
ビット 711111 00
ビット 600000 11
ビット 501000 10  ← 1ビットの誤り訂正可
ビット 400000 11
ビット 300011 11
ビット 201000 10  ← 1ビットの誤り訂正可
ビット 110101 00
ビット 8
(偶数垂直パリティ)
0 0101 1
再計算結果
(偶数パリティビット)
01001 1


ケース2:受信側の状態
送信データABCDE BCC 再計算結果
(奇数パリティビット)
ビット 711111 00
ビット 600000 11
ビット 501 100 11


| 偶数ビットの
| 誤り検出不可

ビット 40000 0 11
ビット 30001 1 11
ビット 200 000 11
ビット 1101 01 00
ビット 8
(偶数垂直パリティ)
0 0101 1
再計算結果
(偶数パリティビット)
0 01 01 1


ページトップへ

3) 群計数チェック方式

群計数チェック方式は、水平方向に 2 ビットのチェック符号を付加する方式です。 チェック符号 は、 水平方向に、ビット "1" の数を加算して、得た答えの 下 2 桁 をとったものです。 水平パリティ方式に比べて、文字を構成するビットの内、 2 つ以上のビットに誤りがある場合も検出でき、 より精度の高い誤り制御ができます。

送信時の状態
送信データABCDE CF1CF2  ← チェック符号
ビット 71111 101
(注)

各データの "1" のビットの数
を加算した値の下 2 ビット
を、チェック符号にします。
ビット 60000 000
ビット 5000 0000
ビット 40000 000
ビット 30001 110
ビット 2011 0010
ビット 11010 111
ビット 8
(偶数垂直パリティ)
0 0101 10


ケース1:受信時の状態
送信データA BCDE CF1CF2 再計算結果
ビット 71111 101 0 1
ビット 60000 0 00 0 0
ビット 500 1 10 00 1 0 ← 誤りビットの検出・訂正可
ビット 400 00 0 00 0 0
ビット 300 01 1 10 1 0
ビット 201 100 10 1 0
ビット 110 10 1 11 1 1
ビット 8
(偶数垂直パリティ)
0 0101 10
再計算結果
(偶数パリティビット)
0 0011 1 1


ケース2:受信時の状態
送信データA BCDE CF1CF2 再計算結果
ビット 71111 101 0 1
ビット 60000 0 00 0 0
ビット 50 1 1 00 00 1 0 ← 誤りビットの検出可
ビット 400 00 0 00 0 0
ビット 300 01 1 10 1 0
ビット 20 0 0 00 10 0 0 ← 誤りビットの検出可
ビット 110 10 1 11 1 1
ビット 8
(偶数垂直パリティ)
0 0101 10
再計算結果
(偶数パリティビット)
0 0 1 0 1 1 0


ページトップへ


4) CRC 方式

CRC ( Cyclic Redundancy Check ) 方式も、水平パリティ方式と同様に、チェック用の符号を付加して、送信する方式です。 この符号を、 CRC 符号 と呼び、送信するデータに対して 論理的な演算をほどこして求めます。
垂直パリティ方式や水平パリティ方式は,雑音がランダムに発生するような場合に有効ですが、 何らかの原因で雑音が集中的に発生したり,ネットワーク機器の故障により雑音が集中するような バースト誤り に対しては、効果が期待できません。 それに対して、 CRC 方式は、バースト誤りに効果を発揮する有効な誤り制御方式です。

* CRC 符号の生成について

 ここでは、 CRC 符号を生成する方法について、説明します。
1. まず送信するデータの水平方向の n ビットを、 b n-1 、b n-2 、 … 、b 2 、b 1 、b 0  としてみます。このビット列を、 つぎのような多項式 M ( X ) で表わすことにします。  M は X の関数、すなわち、このビット列は、 2 の関数であるということです。

 M ( X ) = b n-1 X n-1 + b n-2 X n-2 … + b 2 X 2 + b 1 X 1 + b 0 … (1)

2. CRC 符号を求めるためには、 生成多項式 を用います。
そこで、あらかじめ送信側と受信側で、生成多項式 G ( X ) を取り決めておきます。 たとえば、 k ビットの生成多項式を考えてみると、

 G ( X ) = b k-1 X k-1 + b k-2 X k-2 … + b 2 X 2 + b 1 X 1 + b 0 … (2)

3. つぎに、データの多項式 M ( X ) に対して、 X k を 掛け算します。この意味は、データビットを k ビットだけ左へシフトすることを意味しています。
k ビット左へシフトしたデータの多項式 X k M ( X ) を 生成多項式 G ( X ) で割り、 商を Q ( X ) 、剰余を R ( X ) とすると、 これらの間には、

   X k M ( X ) / G ( X ) = Q ( X ) ・・・ 余り R ( X )

 ∴ X k M ( X ) = Q ( X ) G ( X ) + R ( X ) … (3)

という関係が成り立ちます.
4. 実は、CRC 符号とは、この R ( x ) である ビット列に他なりません。
このビット列 r k-1 、r k-2 、 … 、r 2 、r 1 、r 0 を、データに付加して送信することになります。

(注1) 送信するデータは、多項式 M ( X ) で表わすことができましたが、 M はビット列ですから、 X を 2 進数の 2 と考えることができます。すなわち、 M ( X ) とは、 2 の関数であるということです。
具体的なイメージを掴むために、たとえば、 110101 というデータで、上記の多項式を検証してみましょう。
      M ( X ) = 1 x 2 5 + 1 x 2 4 + 0 x 2 3 + 1 x 2 2 + 0 x 2 1 + 1 x 2 0
というように書き表すことができ、これを計算すれば、元の 110101 と同じ値になります。 X n-1 、 X n-2 ・・・ というのは、 いわば 2 を基底とした重み付けということができます。
(注2) Xk というのは、2進数データの場合、 2k を意味しますので、この式をデータの多項式に掛け算するということは、 データビットを  k ビットだけ左へシフトすることを意味していました。
たとえば、 4 桁の生成多項式 1101 を考えた場合、 24 は 10 進数の 16 ( ビット 10000 )になります。
元のデータ、たとえば 110101 に、 10000 を掛ければ、 1101010000 となり、元のデータを左に 4 ビットシフトしたことになります。  


データの送信について

CRC 方式では、送信するデータ M ( X )を、生成多項式の桁数 k だけ桁上げ(左へシフト)し、 その値に CRC 符号 を加算したものを送信します。 この関係を図で表すと、つぎのようになります。

(1) データ
   M ( X )
(2)データ 0 0 0 ・・・ 0
  M ( X ) を k ビットだけ左へシフト  ( k ビット )
(3)データ CRC 符号
  X k M ( X ) R ( X )

上図からも、データと CRC 符号を合わせた多項式は、 X k M ( X ) + R ( X )  であることが分かります。
すなわち、送信側は、 X k M ( X ) + R ( X )  で表わされるビット列を送信するということができます。

データの受信について

受信側は、この X k M ( X ) + R ( X )  というビット列を受信します。

 データ CRC 符号
  X k M ( X ) R ( X )

さらに、受信側は、受信したデータのビット列( X k M ( X ) で示される部分 ) を、 同じ生成多項式 G ( X ) で割り算し、 余り を求めます。
送られてきた CRC 符号 と 受信側で求めた余り との排他的論理和 ( Exclusive OR ) をとります。 排他的論理和とは、下図の例のように、 0 と 0 または 1 と 1 ならば、結果が 0 となる論理演算です。
排他的論理和
CRC 符号 1001
求めた余り 1001
結果 0000

送信エラーが発生していなければ、 CRC 符号 と 余り は同じはずですから、  結果は 0 になります。
もし送信エラーが発生していれば、 結果は 0 以外 になって、 ネットワークプロトコルにしたがって再送要求などをすることになるでしょう。

(例)  つぎのデータと生成多項式の場合の例で、具体的に見てみることにしましょう。

 データ M = 111010   ◆ 生成多項式 G = 1011

送信側
生成多項式 G = 1011
データ M = 111010
1)まず、 X4 M / G を求めます。
X は 2 として、
4 M / G
= 10000 x 111010 / 1011
= 1110100000 / 1011
= 1010100   余り R = 0100


2) 4 ビット桁上げしたデータに、 余り 0100 を加算したつぎのデータを送信します。
1110100100












送信
受信側
生成多項式 G = 1011
受信ビット列 1110100100
1)受信側では、送られてきた X4 M
111010000000 を、生成多項式 1011 で割り算し、余りを求めます。
 余り R = 0100
2) CRC 符号 と 余り の排他的論理和を求めます。
CRC 符号0 1 0 0
余り0 1 0 0
結果0 0 0 0
結果 が 0 なので、受信したデータに誤りがないことが分かります。


ページトップへ