第9章

誤り訂正
無線でのデータ伝送では，誤り訂正の技術が不可欠です．誤り訂正技術がなければ，今日の通信のディジタル化は難しかったでしょう．もっとも簡単なハミング符号から，最近のターボ符号までさまざまな方法が使われています．ここではすべてを説明することはできません．詳しく説明すると誤り訂正だけで 1 冊の本になってしまうので，ここではその中の一つを代表として説明します．もっと詳しく基礎から勉強したい方は参考文献（59）を読んでください．
先に勉強したガロア体の代数を使うブロック符号の BCH 符号について説明します．BCH 符号は，現在使われているブロック符号にもっとも多く使われているアルゴリズムです．その中には，ハミング符号や，リード・ソロモン符号も含まれます．これを理解できれば実際の応用も広がるでしょう．ただし，第 2 章など前のほうで説明したガロア体の代数に関して理解していないと，なかなか理解できないかもしれません．残念ながら，数学的計算抜きには理解できません．
ここで取り上げる BCH 符号の誤り訂正方法は，ピーターソン法を使って説明します．そのほかもっと実践的に使われるバレカンプ・マーシー法（BM 法）などもありますが，紙面の関係で説明を参考文献（59）に譲ることにします．

9-1 BCH符号
ハミング符号は，符号語間のハミング距離 3 で誤り訂正が 1 個しかできません．それでも，そもそもの開発目的のコンピュータ・メモリの信頼性向上には充分ですが，そのほかのたとえば信頼性が低い無線伝送路などの応用では，回線の誤り率に対して誤り訂正能力が充分ではありません．そこ
で，複数の誤りも訂正できるように考えられた符号の一つに BCH 符号があります．
この符号は 1959 年に Hocquenghem によって，また 1960 年に Bose と Chaudhuri によってそれぞれ独立に発見されたものです．それぞれの頭文字をとって BCH 符号と呼ばれています．ハミング符号
も BCH 符号の一種だと考えることができます．BCH 符号も大きく分けて，符号語の多項式の係数が2 元すなわち GF(2)の場合と，ガロア拡大体 GF(2M)の場合があります．実際に使われるほとんどの巡276

第 9 章 誤り訂正

回ブロック符号は BCH 符号の一種で，とても応用の幅が広い符号です．ここでは，その中のデータが 1/0 のみで構成される 2 元 BCH 符号について説明します．拡大体の多元 BCH 符号は，発見者にちなんでリード・ソロモン符号と呼ばれています．
BCH 符号は純粋に，数学を使って展開された符号なので，数式を使った説明なしには残念ながら理解はできません．ただし最終的に得られた結果は，直感的に理解できるものです．ある程度式を理解した後，具体例をじっくり理解することにより，確かな直感とイメージがつかめると思います．

9-2 t 個の誤りを訂正するBCH符号
ブロック符号の特徴として，生成された符号 F(X)は必ず生成多項式 G(X)で割り切れます．この際に計算は，その符号が定義されたガロア拡大体 GF(2M)上で行われます．すなわち，受信側でこの符号を受信し G(X)で割ったときに完全に割り切れれば，誤りがなかったことがわかります．
伝送路上で，誤りが発生した場合は，ゼロになりません．この受信符号を G(X)で割った余りをシンドロームと呼んでいます．誤り訂正では，このシンドロームを使って計算し誤りの訂正を行います．シンドロームは符号を作る前の情報ビット列の組み合わせにはまったく影響を受けません．ただ伝送路での誤りのパターンのみで一意に決まります．この生成多項式の性質によって，どれくらいの誤り訂正能力があるかがわかります．
BCH 符号の一種であるハミング符号は，1 個の誤りを訂正できる能力があります．これを一般化した t 個の誤りを訂正する BCH 符号は，どのような生成多項式をしているのでしょうか．
（9-1）
G(X) = (X + α )(X + α 2 )(X + α 3 )…(X + α 2t )F(X) …………………………………………………
一般的に GF(2M)上の原始元を α とするとき，上式を符号生成多項式とするものを BCH 符号と呼んでいます．G(X) = 0 は式のように，α から連続した，α 2t までの α のベキ乗を根にもちます．GF(24)のハミング符号では，G(X) = X 4 + X + 1 = (X + α )(X + α 2 )F(X)ただし，F(X) = (X + α 4)(X + α 8) ………………（9-2）

2t = 2 ですから，1 個の誤りを訂正可能な BCH 符号といえます．2 個の誤りを訂正できる BCH 符号
では，G(X) = (X 4 + X + 1)(X 4 + X 3 + X 2 + X + 1)
= (X + α )(X + α 2 )(X + α 3)(X + α 4)F(X )ただし……………………………………
（9-3）

F(X ) = (X + α )(X + α )(X + α )(X + α )68129です．2t = 4 として，4 個の G(X) = 0 の根が α のべき乗として連続していることがわかると思います．
しかしここで注意することは，2 元符号の多項式係数として α のままでは具体的にシフト・レジスタなどを実現できません．そこで，BCH 生成多項式として直接必要のない共役根を含め，生成多項式のすべての係数に α が現れないようにしなければなりません．そのため F(X)の項が必要になります．
これはむだに生成多項式の次数を大きくすることです．できるだけ F(X)の次数を小さく設計したものが効率の良い符号となります．
すなわち 1 個の誤り訂正には，α を根にもつ最小多項式（共役根をもち係数に α を含まない最小次数9-2t 個の誤りを訂正する BCH 符号277多項式），2 個の場合は α と α 3，3 個の場合は α，α 3，α 5 をそれぞれ根にもつ最小多項式の積になります．このように共役関係にない根を，生成多項式に新たに加えることによって，誤りを訂正できる数が増えていきます．
具体的に GF(24)の場合の根と最小多項式の関係を下に書き直します．

α → X4 + X +1
α 3 → X 4 + X 3 + X 2 + X + 1
α 5 → X2 + X +1
α 7 → X4 + X3 +1
……………………………………………………………………
（9-4）

そこで，これらを使っていろいろな生成多項式を計算します．
1 個エラーG( X ) = ( X + α )( X + α 2 ) F( X )G( X ) = ( X + α )( X + α 2 )( X + α 3 )( X + α 4 ) F( X )= ( X 4 + X + 1)( X 4 + X 3 + X 2 + X + 1)
876
4= X + X + X + X +1
23456G( X ) = ( X + α )( X + α )( X + α )( X + α )( X + α )( X + α ) F( X )
= ( X 4 + X + 1)( X 4 + X 3 + X 2 + X + 1)( X 2 + X + 1)
87642= ( X + X + X + X + 1)( X + X + 1)
108542= X + X + X + X + X + X +1

= X4 + X +1

2 個エラー

3 個エラー

……………
（9-5）

ここでは GF(24)の話でした．そのほかのガロア拡大体に対しても，最少多項式が決まり，その組み合わせで同じ方法で BCH 符号の生成多項式が求められます．

9-3 BCH符号の復号
抽象的な話ではなかなかわかりにくいので，具体的な例題を使って説明します．GF(24)における(15, 5)の BCH 符号を使って話を進めます．
● シンドロームの計算
まずはシンドロームの計算をします．ここでは，もっと具体的に説明していきます．
(15, 5)の BCH 符号の生成多項式は，3 個エラー

G( X ) = ( X + α )( X + α 2 )( X + α 3 )( X + α 4 )( X + α 5 )( X + α 6 ) F( X )
= ( X 4 + X + 1)( X 4 + X 3 + X 2 + X + 1)( X 2 + X + 1)
（9-6）
 ………………
87642= ( X + X + X + X + 1)( X + X + 1)

= X 10 + X 8 + X 5 + X 4 + X 2 + X + 1


でした．符号語は G(X )で割り切れるはずです．したがって，下記のように表せます．
R(X ) = I(X ) G(X ) ………………………………………………………………………………
（9-7）
そのため R(X )は G(X ) = 0 と同じ根をもつことは明らかです．そこで，278

第 9 章 誤り訂正