|
4・4 誤りの訂正方法
受信側で誤りを自動的に訂正できる符号がハミングにより発見されてから種々な符号が発見されて通信やコンピュータ等に利用できるようになった。誤り訂正符号はブロック符号と畳み込み符号の方式に大別できる。それぞれの方式において多種類の訂正符号が考案されている。
次に誤り訂正の原理を説明する。
一般に2進符号を記号Xの多項式で表示する。6ビット符号， 110101をXの多項式で表示する場合を例として考える。符号を変数Xの多項式， I（X）で表示する。符号の右端から左に進むに従ってXの右肩のベキ数を1， 2， 3， ・・・と付ける。110101は
| |
1 |
|
1 |
|
0 |
|
1 |
0 |
|
1 |
|
| I (X) = |
X5 |
+ |
X4 |
|
|
+ |
X2 |
|
+ |
1 |
の多項式で表せるので |
| I (X) = |
X5 |
+ |
X4 |
+ |
X2 |
+ |
1 |
|
|
|
（4・10） |
|
と表示される。ここでは， 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）で割算すると割り切れないで余りが発生する。誤りビットの検出については次に述べる。
誤り訂正符号の種類はブロック符号と畳み込み符号に大別される。ブロック符号は現在送られる1区切りのデータ（ブロック符号）から誤り訂正をするのに対して畳み込み符号は過去と現在のデータを用いて誤り訂正をするので通信状態の悪い移動体通信や遠距離通信等に多く使用される。ブロック符号は過去のデータが不要なので短時間で訂正ができるので通信の他にコンピュータのデータ処理等にも使用される。
この項でブロック符号の基本となったハミング（7， 4）符号について解説する。
ハミングは4ビットの情報に3ビットの誤り訂正符号をつけた7ビット長の通報により誤りの訂正ができることを発見した。この符号をハミング（7， 4）符号と呼ぶ。ハミング符号による1通報（文字）の構成は図4・4に示したように情報4ビットI（X）と訂正用3ビットR（X）で構成される。
図4・4 ハミング（7， 4）符号の構成
a1〜a4が情報ビット， c1〜c3が訂正用ビットである。4ビットの符号により全部で24=16種類の通報がつくれる。それぞれのビットa1〜a4に対して生成多項式G（X）
G(X)=X3+X+1 （4・16）
で割算して余りR（X）が訂正用ビットc1〜c3となる。
図4・5（a）に訂正用ビットを付けた16種類の通報を示す。
図4・5 ハミング（7， 4）符号と誤りの表れ方
2番目の情報ビット， 0001に訂正用ビットを付ける場合を考える。3ビットの訂正用ビットを付け加えるために000を加えて
0001→0001000 としてXの多項式で表すとX3に1があるので
| 0 |
0 |
0 |
1 |
0 |
0 |
0 |
| X6 |
X5 |
X4 |
X3 |
X2 |
X |
1→X3 |
|
X3を生成多項式G(X)=X3+X+1で割算（EX-OR）すると余りは， X+1， となるので符号は， 11となる。cは3桁の符号となるので0を付けて， 011となる。
この結果， 訂正用ビットR（X）は011として付け加えられる。送信信号は0001011となる。
通信伝送中に1ビットの誤りが何処かに発生したとする6受信符号を送信と同じG（X）で割算して誤りの検出を行う。誤りがあると割り切れないで余りが発生する。このときの余りをすべて図4・5（b）に示した。16種類の通報に対して誤りが発生したビットの位置に対応してすべて同じ余りとなる。1ビット目が誤ると余りはすべて， 101となる。このことから誤りのチェック回路で受信符号を生成多項式G（X）で割算した余りが101となったときは受信符号の1ビット目を1→0， 又は0→1と反転すれば自動的に誤り訂正ができる。
ハミング符号は1ビットの誤り訂正ができる。複数ビットの誤り訂正をするにはより高次のG（X）を用いたり， 幾何学符号のように訂正の手順を組合せることから複数ビットの訂正ができるが検出に長い時間が必要になり，処理回路が複雑になる問題が生ずる。
GMDSSの非常用位置指示無線標識， EPIRBにはBCH符号という誤り訂正用のブロック符号が使用されている。
|
