JPH0522255A

JPH0522255A - 連接符号化方式

Info

Publication number: JPH0522255A
Application number: JP17487791A
Authority: JP
Inventors: Atsushi Yamashita; 敦山下
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 1991-07-16
Filing date: 1991-07-16
Publication date: 1993-01-29

Abstract

(57)【要約】（修正有）【目的】外符号復号器が訂正すべき誤りパターンの数
を削減し外符号の符号化率を高め外符号復号器の回路規
模を削減する。【構成】受信側で内符号の復号後に生じる誤りパター
ンに応じた外符号を生成する多項式として, 送信データ
とパリティ全体のブロック長とパリティビット数n と発
生確率の高い誤りパターンとを決め，次数n の多項式で
誤りパターンを割り算し,剰余が互に異なる多項式を選
択する。, 送信側100には、その多項式からパリティ生
成回路111 でパリティ符号を生成し、送信データと合成
し内符号符号化器へ送る外符号符号化器11を備える。受
信側200には内符号復号器からの符号を入力してシンド
ローム生成回路221で生成したシンドロームによる誤り
ブロックの位置情報とI'ブロック内のビット誤りパター
ンとを加えて訂正パターン生成器222により訂正パター
ンを生成し、位相同期させた入力符号に加える外符号復
号器22を具える。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は衛星通信や深宇宙探査機
などのデータ通信において通信品質を保証するために，
伝送路で生じる符号誤りを訂正する誤り訂正符号を使用
した誤り訂正方式に係り、特に十分な訂正能力を得るた
めに誤り訂正符号を外符号と内符号の２つの誤り訂正符
号を組合せて使用する連接符号化方式に関するものであ
る。

【０００２】

【従来の技術】従来の連接符号化方式は、図６の(1) に
示す如く、２つの誤り訂正符号として伝送路3 に対し外
側の外符号符号化と内側の内符号符号化とを組合せて送
信側の変調器の前の符号化器10と受信側の復調器の後の
復号器20とに使用しているが、受信側の復号器20の内符
号復号器21で復号した出力データに含まれる符号誤り
は、内符号の復号器に特有の連続したバースト的な誤り
となることが多い。そのため，外符号と内符号の間に,
送信側はインタリーブ回路13を，受信側はデインタリー
ブ回路23を設けて, 連続バースト的な誤りをランダム化
している。

【０００３】

【発明が解決しようとする課題】然しながら、上述の如
く、送信側の符号化器10にインタリーブ回路13を設け、
受信側の復号器20にデインタリーブ回路23を設けると,
全体の回路規模が大きくなるばかりでなく, 両回路13,2
3により, データ伝送に大きな時間遅延を生じるという
問題がある。そのインタリーブ回路13とデインタリーブ
回路23を設けない場合は、図７の(2) に示す如く、外符
号符号化器11Aとして上記のバースト誤りを訂正できる
非常に訂正能力の高い符号を使用しなければならず,訂
正能力の高い符号は、送信側の符号化器11Aで, より多
くのパリティビットを必要とするので, 情報伝送の効率
を表す符号化率R が劣化し，回路規模が大きくなり、ま
た、受信側の誤り訂正の復号器22Aの回路規模も大きく
なるという問題があった。また、誤り訂正符号の外符号
として訂正能力の低い符号, 即ち符号化率R が高く回路
規模が小さい符号を使用すると，受信側の内符号復号器
21で生じるバースト誤りのために外符号復号器22が誤訂
正を起し外符号復号器22の復号出力の受信データの符号
誤り率BER が却って劣化することになる。本発明の目的
は、外符号の符号化率が高く送信側の外符号符号化器11
と受信側の外符号復号器22の回路規模が小形で済む連接
符号化方式を提供することにある。

【０００４】以下に従来方式の問題点を図７，図８を用
いて詳しく説明する。例えば、内符号として１誤り訂正
のブロック符号（BCH 符号等) を用いるとする。図７の
連接符号化ブロックの例のように，符号化率k/n のＢＣ
Ｈ符号(n,k）を内符号とし,それを Lブロック集めて外
符号ブロック(E' ブロック: n * L ビット) を構成す
る。なお，内符号の１ブロックをＩブロックと呼ぶ。先
ず，図示しないが,E'ブロック内に１ビットの誤りが生
じた場合は，内符号で訂正できるので，内符号の復号後
には誤りが無い。次に，図８(A) の如く,E'ブロック内
に２ビットの誤りが生じた場合で，其の(1) のように,
２ケのＩブロックに分れて生じた場合は，夫々の内符号
で訂正できるが、其の(2)のように, 1 ケのＩブロック
内に２ビットの誤りが生じた場合は, 内符号で訂正でき
ず誤訂正となる。図示しないが, E'ブロック内に２ビッ
ト以上の誤りが生じた場合も同様に考えねばならない。
この様に, 受信側の内符号の復号後には, kビットのＩ
ブロック内に,0〜k ビットの誤りが生じると考える必要
がある。ここで, 0 は復号後の全ての誤りが内符号のパ
リティ部に集中した場合でありその場合を含む。図８
(A) の(2) のように, ２ビットの誤りが１ケのＩブロッ
ク内に生じた場合は, 内符号の復号後にそのＩブロック
には，誤訂正のために３ビットの誤りが生じ得る。その
ため，外符号として，従来はインタリーブにより連続の
バースト誤りをランダム化して訂正能力の小さい複数の
外符号で誤り訂正するか、３ビット以上の訂正能力を持
つ強力な外符号を使用しなければならないが、これは前
述の問題を生じる。例えばE'ブロック内に２ビットの誤
りが生じた場合は，先に述べた様に，外符号は３ビット
の誤り訂正能力を必要とする。ここで、内符号の復号後
のE'ブロック(k * Lビット)の長さの外符号を外符号復
号器で誤り訂正しようとすると、従来のランダム誤り訂
正符号では,(1+_k*L C₁+_k*L C₂+_k*L C₃)通りの誤りパ
ターンを識別して訂正できる外符号を使用しなければな
らず，その時の符号化率R は小さくなり且つ復号器の回
路規模が大きなものとなる。

【０００５】本発明の目的は、この様な場合の内符号の
復号後の誤りパターンが, ランダムではなくてＩブロッ
ク毎に集中して発生する性質に着目して，内符号の復号
器の後の外符号の復号器が訂正すべき誤りパターンの数
を削減し，外符号の符号化率を高め且つ外符号復号器の
回路規模を削減することにある。

【０００６】

【課題を解決するための手段】この目的は、受信側の復
調出力の内符号の復号後に生じるバースト誤りのパター
ンが、上述の如く, 外符号の符号構成に応じて定まる特
有の誤りパターンであることに着目し、先ずその内符号
の復号後に生じる特有の誤りパターンに応じた外符号を
生成する生成多項式として、ブロック長とパリティビッ
ト数ｎ，発生確率の高い誤りパターンとを決め，パリテ
ィビット数ｎに等しいｎ次の多項式で誤りパターンを割
り[ ガロア体 GF(2)上の割算],全ての誤りパターンに対
する剰余が互に異なるような多項式を選択する。そして
其の選択した多項式により, 図１の原理図の如く、送信
側100の外符号符号化器11はパリティ符号を生成するパ
リティ生成回路111とその生成したパリティ符号を直列
符号に P/S変換器112 で変換し,入力の送信データと合
成器113 で合成して其の合成出力を誤り訂正の外符号と
して内符号符号化器12へ送出するように構成される。そ
して受信側200の外符号復号器22は、その前の内符号復
号器21からの外符号を入力し前記と同じ生成多項式を用
いてシンドロームS を生成するシンドローム生成回路22
1と其の出力のシンドロームSによる誤りブロックの位置
情報[m=0─(m+1)]と I'ブロック内のビット誤りパター
ン( i,j─k)とにより,誤り訂正パターンを生成する訂正
パターン生成器222 と其の出力の訂正パターンと前記内
符号復号器から入力した外符号を位相同期させるために
相当時間だけ遅延回路220で遅延させた出力符号とを排
他的論理和の加算器223で加算し其の加算出力を外符号
復号器22の復号出力とするように構成される。送信側の
一般的な (n+1)次の外符号符号化器11の構成は、図２の
(A) の如く、先ずパリティ生成回路111兼 P/S変換器112
のスイッチを ON し, セレクタSEL を送信データ入力
側として、送信データ入力をそのまま次の内符号符号化
器へ出力する。そして該送信データ入力の出力の終了
後, スイッチを OFFし, セレクタSEL をパリティ生成回
路側として, (n+1) 次の生成多項式の第ｊ次の係数Kj(=
0/1)と１ビットの DフリップフロップFFと排他的論理和
の加算器+ とにより, 直列に生成した (n+1)個のパリテ
ィ符号を出力する。そして受信側の外符号復号器22の一
般的な (n+1)次のシンドローム生成回路221 の構成は、
図２の(B) の如く、内符号復号器21からの受信符号入力
を,(n+1)次の生成多項式の第ｊ次の係数Kj(=0/1)との排
他的論理和の加算を行い, その加算出力をフリップフロ
ップFFで次の加算器へ出力すると同時に, 其の出力を各
FFから並列に(n+1)個の各シンドロームSjとして出力す
るように構成される。

【０００７】

【作用】本発明による誤り訂正符号の外符号の生成多項
式を求める手順は、図３の手順図に示す如く、先ずステ
ップStep 111で, 受信側の内符号復号器の出力に大きな
確率で生じる誤りブロックI'の番号m (=0〜m+1)と m番
目のI'ブロック内で生じるビット誤りのパターン( 誤り
位置はi,j ─k)とを決め、次Step 112で, 外符号全体E'
のブロック長, パリティビット数n を決める。そしてSt
ep 113で,パリティビット数n に等しい次数n の生成多
項式G(x)を決める。そしてStep 114で, E'ブロック内の
誤り位置i の１ビット誤りに対するシンドロームS(i)を
計算し，Step 115で,m個のI'ブロックの各I'ブロックの
ビット誤り位置i に対するシンドロームS(i)を表とした
シンドローム・テーブルを作成する。そしてStep 116で
は、誤りブロックI'の番号m = 0 について, 続いてStep
117では、誤りブロックI'の番号m = m+1 について上記
のシンドローム・テーブルを使用し, Step 118で,m番目
のI'ブロックで生じうる誤りパターン（誤り位置i,j ─
k ）に対するシンドロームS(i)+S(j)+─S(k)を計算す
る。そしてStep 119で, 異なる誤りパターンに対して同
一のシンドロームが有るか無いかを調べて, 無かった場
合は, Step 120で,全ての誤りパターンを調べたか否か
をチエックし, Noならば, Step 118に戻り, Yes なら
ば, Step 121に進み, 全てのm について調べたかをチエ
ックする。そして Yesならば, 終了するが, Noならば,
Step 117に戻る。また、Step 119で,異なる誤りパター
ンに対して同一のシンドロームが有るか無いかを調べ
て,有った場合は, Step 122で, 全ての生成多項式を調
べたか否かをチエックし, Noならば, Step 123で,生成
多項式を変更して，Step 114に戻り, Yes ならば, Step
124で, ブロック長とパリティビット数を変更して, St
ep 113に戻る。

【０００８】受信側の内符号復号器の出力の各Ｉブロッ
ク( k ビット) の中には 0〜k ビットの誤りが含まれ得
るが、複数のＩブロックに渡って内符号の誤りが誤訂正
される確率は，１つのＩブロックの誤りが誤訂正される
確率に比べて極めて小さい。例えば，E'ブロック中に２
ビットの誤りが発生した場合は，先述の如く，１つのＩ
ブロックで誤訂正が起きるだけである。E'ブロック中に
３ビット誤りが発生した場合は，図８(B)に示す３つの
パターン(1)(2)(3)があるが，やはり１つのＩブロック
で誤訂正が起きるだけである。２つ以上のＩブロックで
誤訂正が起きるには，４ビット以上の誤りが発生する必
要があり,而も２ビット以上の誤りが１つのＩブロック
に集中して発生する確率は小さいことから，複数のＩブ
ロックで誤訂正が起きる確率は非常に小さくなる。E'ブ
ロック内の１つのＩブロックのみを訂正する符号の場
合，訂正能力を３ビットとすると，外符号で識別し訂正
すべき誤りパターンの数は(1+ _kC₁+ _kC₂+ _kC₃)* Lと
なり, ランダム誤り訂正符号の場合に比べて遙かに少な
くて済む。後述の実施例で説明するが、例えば k=4,L=1
5とした場合, 訂正能力が３ビットのランダム誤り訂正
符号で識別し訂正すべき誤りパターン数が 1+₆₀C₁+₆₀C₂
+₆₀C₃= 36051通りであるのに対し、本発明の方式では
（1+4+6+4 )* 15= 225通りとなり，大幅な減少となる。
よって大幅な符号化率の向上と復号器の回路規模の縮小
が実現できる。

【０００９】

【実施例】本発明の実施例の連接符号化方式として, 先
ず内符号として１誤り訂正符号のＢＣＨ符号(n,k）が,
ＢＣＨ符号(7,4) の L=15組を使用し、次に外符号とし
て,ブロック長k*L が 60 ビットの誤り訂正用ブロック
符号を使用した場合の例を示す。先に述べたように, 本
発明による外符号のブロック符号は、受信側で 225通り
の誤りパターンを識別して訂正すれば良いため, パリテ
ィビット数は８ビットで良い（2⁸ > 225) と推定され
る。即ち誤り訂正符号の外符号は（60,52)符号で良いと
考えられる。但し実際には，この所要パリティビット数
８は必要条件であるが実際に符号が存在するとは限らな
い。

【００１０】本発明の実施例の外符号の（60,52)符号の
生成多項式G(x)の一例を示せば、G(x)= X⁸＋X⁵＋X ＋
１となる。但し本多項式G(x)以外にも相反多項式など此
れと同等の能力をもつ生成多項式が存在する。なお、生
成多項式G(x)を求めるには前述の図３の手順の如く、ブ
ロック長k*L ，パリティビット数n ，発生確率の高い誤
りパターンのI'ブロックの番号 m, 誤りビット位置i,j
─k を決め、パリティビット数n に等しい次数n の多項
式（パリティビット数n が８ビットなら, ８次多項式）
で、各誤りパターンを割り（ガロア体 GF(2)上の割算),
全ての誤りパターンに対する剰余が互に異なるような上
記多項式を外符号の生成多項式として選択する。実際に
は、前述の図３の手順によって上記の生成多項式G(x)が
決められる。この生成多項式G(x)を用いた誤り訂正の外
符号符号化器の構成例を図４の(A) に示し、外符号復号
器のシンドローム生成器の構成例を図４の(B) に示す。
これは、図２の(A),(B) の一般的な (n+1)次の外符号符
号化器とシンドローム生成器の構成において、次数(n+
1)=8 の生成多項式G(x)の係数K₈,K₅,K₁,K₀は１であり_,
他の係数K₇,K₆,K₄,K₃,K₂が０であって、図４の(A),(B)
の外符号符号化器の構成と外符号復号器のシンドローム
生成器の構成には、信号X⁸ _,X⁵,X¹,X⁰のみが存在する。

【００１１】本発明による実施例の外符号の（60,52)符
号を、従来のランダム誤り訂正符号と比較してみる。外
符号として従来のＢＣＨ符号を使用する場合，ブロック
長の60ビット中の３ビット誤りを訂正しなければならな
い場合は，(63,46,7) 符号を使用する必要があり, この
場合の符号化率 R= 73.0％となる。これに対し、本発明
の実施例では（60,52)符号であり, その符号化率 R= 8
6.7％であって、符号化率が大幅に向上していることが
判る。また、受信側の外符号復号器の回路規模について
も，識別して訂正すべき誤りパターンの数が、従来方式
では 36051通りあったのに対し, 本発明の方式では,225
通りと 1/ 100 以下であるので, 誤り訂正パターン生
成器の回路等の大幅な小形化が実現できる。

【００１２】誤り訂正能力についても, 従来の 3ビット
誤り訂正符号と比べ殆ど劣化しない。先ず, E'ブロック
中に, 1 〜3 ビットの誤りが生じた場合に, 誤訂正する
I'ブロックは１つ以下であるため，従来符号で訂正でき
る誤りパターンは全て本発明の符号で正しく訂正でき
る。E'ブロック中に, ４ビットの誤りが生じた場合に,
本発明の符号で訂正できないものは，複数のI'ブロック
で誤訂正する場合だけであり，従来の 3ビット誤り訂正
符号で訂正できる誤りパターンのうち本発明の符号で訂
正できないパターンは，２％だけであり，殆ど差が無い
と言える。４ビット以上の誤りは，生じる確率自体が非
常に小さいため，これらの劣化は無視できる程度であ
る。図５に，内符号としてＢＣＨ符号の（7,4)符号を用
い, 外符号として従来のＢＣＨ符号の（63,46,7)符号の
短縮符号を使用した場合と本発明による実施例の（60,5
2)符号を使用した場合のビット誤り率（BER)特性の理論
値を示す。両者に殆ど差が無いことが判る。

【００１３】

【発明の効果】以上のように、本発明によれば、誤り訂
正符号の連接符号化を行った場合には, 受信側の内符号
の復号時に生じるバースト的な誤りに対し, 外符号を符
号化率の高い符号とした効率の良い誤り訂正符号化方式
を実現できる。また回路規模も, 同等の訂正能力を持つ
従来の符号の場合に比べて小さくすることが出来る。

【００１４】なお、ここでは内符号として，１誤り訂正
のＢＣＨ符号を使用する場合についてのみ述べたが、他
の符号、例えばブロック長の異なる符号，訂正能力の異
なる符号（２ビット以上の誤りを訂正する符号など),Ｂ
ＣＨ符号以外の符号，或いは畳み込み符号等を使用する
場合も同様に実現できる。また，外符号についても，こ
こで述べたブロック長，訂正能力，生成多項式は一例で
あり，他のものであっても，同様の効果を得ることが出
来る。

【図面の簡単な説明】

【図１】本発明の連接符号化方式の基本構成を示す原
理図

【図２】本発明の連接符号化方式の一般的な（n+1)次
の外符号符号化器の構成と外符号復号器のシンドローム
生成器の構成の図

【図３】本発明の連接符号化方式の外符号の生成多項
式を求める手順図

【図４】本発明の実施例の生成多項式による外符号符
号化器の構成例と外符号復号器のシンドローム生成器の
構成例の図

【図５】本発明の実施例の連接符号化方式の効果を説
明するためのビット誤り率特性の理論値の図

【図６】従来の連接符号化方式の構成を示すブロック
図

【図７】連接符号化ブロックの説明図

【図８】連接符号化方式における誤りの発生パターン

【符号の説明】

11は外符号符号化器、22は外符号復号器、 111 はパリ
ティ生成回路、112 はP/S変換器、 113は合成器、 220
は遅延回路、 221 はシンドローム生成回路、222 は排
他的論理和の加算器である。

Claims

【特許請求の範囲】【請求項１】データ伝送の誤り訂正符号として外符号
と内符号の２つを組合せて使用する連接符号化方式にお
いて、受信側で内符号を復号した後に生じる誤りパター
ンに応じた外符号を生成する多項式として, 送信データ
と誤り検出のパリティ全体のブロック長と該パリティビ
ット数(n) と発生確率の高い誤りパターンとを決め，該
パリティビット数に等しい次数(n) の多項式で該誤りパ
ターンを割り算し,全ての誤りパターンに対する剰余が
互に異なるような多項式を選択し, 送信側(100)には其
の選択した多項式でパリティ符号を生成するパリティ生
成回路(111) と其の生成したパリティ符号を前記送信デ
ータと合成(113)し其の合成出力を誤り訂正の外符号と
して内符号符号化器へ送出する外符号符号化器(11)と、
受信側(200) には内符号復号器からの符号を入力し前記
と同じ生成多項式を用いてシンドロームを生成するシン
ドローム生成回路(221)と其の出力のシンドロームによ
る誤りブロックの位置情報[m=0─(m+1)]とI'ブロック内
のビット誤りパターン(i,j─k)とにより誤り訂正パター
ンを生成する訂正パターン生成器(222)と其の出力の訂
正パターンと前記内符号復号器から入力した符号を位相
同期させるために相当時間だけ遅延(220)させた出力符
号とを排他的論理和の加算器(223)で加算し其の加算出
力を復号出力とする外符号復号器(22)を具えることを特
徴とした連接符号化方式。