4・4 誤りの訂正方法
受信側で誤りを自動的に訂正できる符号がハミングにより発見されてから種々な符号が発見されて通信やコンピュータ等に利用できるようになった。誤り訂正符号はブロック符号と畳み込み符号の方式に大別できる。それぞれの方式において多種類の訂正符号が考案されている。
次に誤り訂正の原理を説明する。
一般に2進符号を記号Xの多項式で表示する。6ビット符号、110101をXの多項式で表示する場合を例として考える。符号を変数Xの多項式、I(X)で表示する。符号の右端から左に進むに従ってXの右肩のベキ数を1、2、3、・・・と付ける。110101は
と表示される。ここでは、XとX3の桁の符号は0なのでI(X)には含まれない。一般にある情報は1又は0の2進符号で表示できるのでXの多項式I(X)で表示される。
情報ビットI(X)に誤り訂正ビットR(X)を付け加えてI(X)+R(X)として誤り訂正可能な送信信号を発生する。
図4・3 送信符号の構成
ただし、付加するR(X)は生成多項式G(X)符号で割り切れるように情報I(X)ごとに計算してR(X)を見つけてI(X)に付け加える。生成多項式G(X)も2進符号で情報内容により変化するI(X)ごとに一定のG(X)で割り切れるようなR(X)を計算してI(X)の右に付けて送信信号とする。
受信側で同じ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・15)は、分子をI(X)+R(X)とすればG(X)で割り切れることを示している。
(4・11)式と比較するとI(X)にR(X)を付け加えるとG(X)で割り切れるようになることが分かる。すなわちI(X)を生成多項式G(X)を用いて割算をして余りのR(X)を訂正ビットとして付け加えればG(X)で割り切れる送信符号を作り出すことができる。
受信符号に誤りが発生すると受信符号を送信側と同じG(X)で割算すると割り切れないで余りが発生する。誤りビットの検出については次に述べる。
|