4・4・2 誤り訂正の原理
受信側で同じG(X)を用いて受信符号を割算する。誤りの検出は受信符号を送信側と同じG(X)で割算したとき
(1) 受信信号がG(X)で割り切れるとき:正しく受信できた。
(2) 受信信号がG(X)で割り切れないとき:誤りが生じた。さらに
(3) 割算したときの余りの符号から誤りのビットの位置が分かるので訂正できる。
送信側で訂正ビットR(X)を作るにはI(X)をG(X)で割算して出てきた余りR(X)とする。
数学的に割算は分数となるのでI(X)がG(X)で割り切れるときは
と表せる。ここでQ(X)は割算の商と呼ばれるXの多項式で示される。
G(X)で割り切れないときは割算の余りをR(X)とすると
I(X)=Q(X)・G(X)+R(X) (4・12)
となる。この両辺にR(X)を加えると
I(X)+R(X)=Q(X)・G(X)+R(X)+R(X) (4・13)
+は排他的和、EX−ORをとるので、R(X)+R(X)=0となるので(4・13)式は
I(X)+R(X)=Q(X)・G(X) (4・14)
書き直すと
(4・11)式と比較するとI(X)にR(X)を付け加えるとG(X)で割り切れるようになることが分かる。すなわちI(X)を生成多項式G(X)を用いて割算をして余りのR(X)を訂正ビットとして付け加えればG(X)で割り切れる送信符号を作り出すことができる。
受信符号に誤りが発生すると受信符号を送信側と同じG(X)で割算すると割り切れないで余りが発生する。誤りビットの検出については次に述べる。