日本財団 図書館


4・4・3 ブロック符号−ハミング符号
 誤り訂正符号の種類はブロック符号と畳み込み符号に大別される。ブロック符号は現在送られる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)符号と誤りの表れ方
(a)送信符号
 
(b)1ビット誤りが発生したときのG(X)で割算した余り
 
 2番目の情報ビット、0001に訂正用ビットを付ける場合を考える。3ビットの訂正用ビットを付け加えるために000を加えて
0001→0001000 としてXの多項式で表すとX3に1があるので
 
 
 X3を生成多項式G(X)=X3+X+1で割算(EX-OR)すると余りは、X+1、となるので符号は、11となる。cは3桁の符号となるので0を付けて、011となる。
 
 
 この結果、訂正用ビットR(X)は011として付け加えられる。送信信号は0001011となる。
 通信伝送中に1ビットの誤りが何処かに発生したとする。受信符号を送信と同じG(X)で割算して誤りの検出を行う。誤りがあると割り切れないで余りが発生する。このときの余りをすべて図4・5(b)に示した。16種類の通報に対して誤りが発生したビットの位置に対応してすべて同じ余りとなる。1ビット目が誤ると余りはすべて、101となる。このことから誤りのチェック回路で受信符号を生成多項式G(X)で割算した余りが101となったときは受信符号の1ビット目を1→0、又は0→1と反転すれば自動的に誤り訂正ができる。
 ハミング符号は1ビットの誤り訂正ができる。複数ビットの誤り訂正をするにはより高次のG(X)を用いたり、幾何学符号のように訂正の手順を組合せることから複数ビットの訂正ができるが検出に長い時間が必要になり、処理回路が複雑になる問題が生ずる。
 GMDSSの非常用位置指示無線標識、EPIRBにはBCH符号という誤り訂正用のブロック符号が使用されている。
 
4・4・4 畳み込み符号
 ブロック符号は1区切り(1ブロック)の情報符号の後に誤り訂正符号を付け加えてブロックごとに訂正を行うのに対して、畳み込み符号はブロックの情報を小さな単位に分けてその単位ごとに誤り訂正符号をつけて訂正する方式である。ブロック符号は誤りが連続して発生するバースト誤り(フェージング誤り等)に有効であるのに、畳み込み符号は誤りがバラバラに分布して発生するランダム誤りに有効でありFM放送の回線等に利用されている。
 図4・6に比較して概念を示した。ただし、情報の長さを同じとしてあるが畳み込み符号の単位を長くして過去のデータの影響も取り入れることもできる。
 
図4・6 ブロック符号と畳み込み符号
(a)ブロック符号の構成
 
(b)畳み込み符号の構成
 
 畳み込み符号はいくつかの単位の訂正符号を組合せることから訂正能力が向上して複数の誤りを能率よく訂正できる。
 誤り訂正符号の分類と主な符号について以下に示す。デジタル通信にはどれかの誤り訂正方式と組合せることが必要である。
 
誤り訂正符号の分類







日本財団図書館は、日本財団が運営しています。

  • 日本財団 THE NIPPON FOUNDATION