(57)【特許請求の範囲】
【請求項１】
受信データおよび事前情報に基づき、符号トレリス上でのフォワード処理、バックワード処理およびそれらの処理で算出された値を利用して軟出力生成を行う誤り訂正符号復号装置において、
符号トレリス上の異なる時点のバックワード処理を同時に行う複数のバックワード処理モジュールを持ち、
受信データ、事前情報をメモリから周期的に逆順に読み込み、
前記バックワード処理モジュールへの入力は前記メモリから読み込んだ受信データ、事前情報であるか、もしくは予め決められた他のバックワード処理モジュールから出力される受信データ、事前情報であり、
前記メモリから読み込んだ受信データ、事前情報を入力とする前記バックワード処理モジュールは前記周期で交代する、
ことを特徴とする誤り訂正符号復号装置。
【請求項２】
畳み込み符号の軟入力軟出力復号処理を行う誤り訂正符号復号装置において、
受信データおよび事前情報が格納されるメモリと、
複数のバックワード処理モジュールと、
フォワード処理・軟出力生成モジュールとを備え、
前記メモリから一定時点数分の受信データ及び事前情報を逆順に読み込むバックワード処理モジュールが、循環的に切り替えられ、
前記各バックワード処理モジュールが、
自バックワード処理モジュールが前記メモリから逆順に読み込んだ前記一定時点数分の受信データおよび事前情報と、自バックワード処理モジュールよりも前記メモリからの受信データおよび事前情報の読み込み順が１つ前の前バックワード処理モジュールから出力される受信データ及び事前情報とを、前記一定時点数の２倍の時点数だけ遅延させて、自バックワード処理モジュールよりも前記メモリからの受信データおよび事前情報の読み込み順が１つ後の後バックワード処理モジュールに対して出力する構成を有すると共に、
自バックワード処理モジュールが前記メモリから読み込んだ受信データおよび事前情報に基づいてバックワード値を算出し出力すると共に、前記前バックワード処理モジュールから出力される受信データおよび事前情報に基づいてバックワード値を算出し出力する構成を有し、
前記フォワード処理・軟出力生成モジュールが、
前記メモリから受信データおよび事前情報を読み込み中のバックワード処理モジュールから出力される受信データおよび事前情報に基づいてフォワード値を算出すると共に、該算出したフォワード値と、前記メモリから受信データおよび事前情報を読み込み中のバックワード処理モジュールの後バックワード処理モジュールから出力されるバックワード値に基づいて軟出力を生成する構成を有することを特徴とする誤り訂正符号復号装置。
【請求項３】
請求項１記載の誤り訂正符号復号装置において、
前記バックワード処理モジュールはバックワード値更新手段、バックワード値格納手段、受信データ格納手段および事前情報格納手段で構成され、
受信データ格納手段、事前情報格納手段をシフトレジスタで構成し、
前記シフトレジスタから出力される受信データ、事前情報、およびバックワード値更新手段で生成されるバックワード値をバックワード処理モジュールからの出力データとする、
ことを特徴とする誤り訂正符号復号装置。
【請求項４】
請求項１記載の誤り訂正符号復号装置において、
前記フォワード処理と前記軟出力生成を行うフォワード処理・軟出力生成モジュールへの入力は前記バックワード処理モジュールの中の１つに入力される受信データ、事前情報および前記バックワード値更新手段で生成される値であり、なおかつ該当するバックワード処理モジュールは前記周期で交代する、ことを特徴とする誤り訂正符号復号装置。
【請求項５】
前記受信データを読み込む際にブランチメトリックを計算してから読み込み、以降、前記シフトレジスタは前記ブランチメトリックを保持し、バックワード処理、フォワード処理および軟出力生成処理は前記ブランチメトリックに基づいて処理を行う、
ことを特徴とする請求項３記載の誤り訂正符号復号装置。
【請求項６】
前記バックワード処理、フォワード処理および軟出力生成処理は事後確率最大復号アルゴリズムに基づく、
ことを特徴とする請求項１記載の誤り訂正符号復号装置。
【請求項７】
前記バックワード処理、フォワード処理および軟出力生成処理はMax-Log-MAP 復号アルゴリズムに基づく、
ことを特徴とする請求項１記載の誤り訂正符号復号装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は誤り訂正符号の復号技術に関し、特にターボ符号の復号法に代表される、連接符号に対し構成要素の軟出力復号を繰り返す復号技術に関する。
【０００２】
【従来の技術】
誤り訂正符号化技術は、データの符号化・復号という操作を通じてデータ伝送時の通信路上で発生したビット反転等のエラーからデータを保護する技術であり、デジタル無線通信・記憶媒体をはじめとして現在広く利用されている。符号化は、送信する情報を、冗長ビットを付加した符号語に変換する操作である。復号は、その冗長性を利用してエラーが混入した符号語（受信語と呼ぶ）から送信された符号語（情報）を推定する操作である。
【０００３】
誤り訂正符号は、同一の符号であっても複数の復号法を考えることができる。通常、復号結果は、前述のように符号語またはそれを生成する情報ビット列として与えられるが、受信系列に対して各情報ビットを重み付きで推定する復号方法も知られており、軟出力復号法と呼ばれている。最適な軟出力復号は、符号語を構成するシンボル列であるという制約条件の下、受信語を条件として情報シンボルや符号語の各ビットの条件付き確率を出力する復号法であり、事後確率復号法と呼ばれている。情報シンボルが２値の場合には事後確率復号は次式（１）で与えられるL(u(k)) を生成すれば十分である。
【０００４】
L(u(k))=log(P(u(k)=0｜Y)/P(u(k)=1｜Y)) …（１）
【０００５】
ここで、u(k)はk 番目の情報ビット、Y は受信語、P(u(k)=b｜Y)（b=0,1）は受信語Y の下でu(k)=bとなる条件付確率である。
【０００６】
１９９３年ターボ符号と呼ばれる高性能符号が提案された。ターボ符号に関しては文献１“Near Shannon limit error-correcting coding and decoding: Turbo codes”(Proceedings of IEEE International Conference of Communications, 1064-1070, 1993) に詳述されている。図５にターボ符号装置および復号装置の構成例を示す。ターボ符号装置は図５(a) に示すように、フィードバックを持つ組織的な畳込み符号器701,702 をインターリーバ703 を介して２個並列に連接した形態を基本型とする。畳込み符号は、メモリ数４以下の符号が通常使用される。インターリーバ703 は、ビットの並び替えを行う手段であり、インターリーバ703 の大きさと設計で符号性能が大きく左右される。図５(a) の畳込み符号器701,702 で生成されるパリティビットを情報ビットと合わせてそれぞれ要素符号１，２と呼ぶことにする。
【０００７】
一方、ターボ符号の復号装置の構成としては、符号装置の構成に対応して復号器704,705 を用意する。復号器704 は要素符号１に対する復号手段であり、復号器705 は要素符号２を復号する手段である。ターボ符号の復号法の特徴は、復号器704,705 に前述の軟出力復号法を適用することにある。復号器704(705)は復号器705(704)で生成された各情報ビットに対する軟出力値を事前情報として扱い、受信値に重みを付けて復号を行う。ここで他方の復号器で事前情報として使用される値は、式（１）の値L(u(k)) そのものではなく、次式（２）で表される外部情報と呼ばれる値Le(u(k))である。
【０００８】
Le(u(k))=L(u(k))−Ｃ・y(k)−La(u(k)) …  （２）
【０００９】
ここで、y(k)は情報ビットu(k)に対する受信値、La(u(k))は事前情報であり、ターボ符号の復号においては他方の復号手段で生成される外部情報と一致し、Ｃは通信路のSN比で決まる定数である。ターボ符号の繰り返し復号においては要素符号１の復号が完全に終了した後、要素符号２の復号に移行する。このとき、インターリーバ703 と同一のインターリーバ706 で要素符号２の情報ビットの順序に合うように復号器705 に読み込まれ、事前情報として利用される。復号器705 では情報ビットに対する受信値もインターリーバ706 で順序を変更され読み込まれる。繰り返し復号においては、この要素符号２の復号が完全に終了した後に要素符号１の復号を再び実行する。このときインターリーバ706 の逆変換であるデインターリーバ707 で外部情報を要素符号１の情報ビットの順序に合うように並び替える。このように二つの復号器の間で外部情報を順次更新していく処理を行う繰り返し復号の構造を持つことがターボ復号の特徴である。繰り返しを行う度に復号誤り率は順次改善され、要素符号１，２の復号で１度の繰り返しとカウントすると、通常２回〜10回程度の繰り返し回数が十分となる。一般に繰り返し回数は通信路のSN比が小さいときほど大きくする必要がある。繰り返しの結果、最終的に得られた値L(u(k)) を硬判定して復号情報とすることで復号処理が終了する。
【００１０】
ターボ符号の復号装置を開発する上では前述の畳込み符号の軟入力軟出力装置の設計が重要となる。畳込み符号の軟入力軟出力復号は、符号のトレリス構造を利用することで効率よく実行することが可能となる。符号トレリスを利用して式（１）に示す値L(u(k)) の出力を行う軟入力軟出力復号アルゴリズムとしてBCJRアルゴリズム（MAP アルゴリズムとも呼ばれる）が知られており、文献２“Optimal decoding of linear codes for minimizing symbol error rate ”(IEEE Transaction on Information Theory, pp.284-287, 1974)  に詳述されている。また、式（１）に示す値L(u(k)) の近似値を求めることで計算量を小さくするMax-Log-MAP アルゴリズムやLog-MAP アルゴリズムも知られており、例えば文献３“A Comparison of optimal and sub-optimal MAP decoding algorithms ”(Proceedings of IEEE International Conference of Communications, pp.1009-1013, 1995)に詳述されている。
【００１１】
これらのアルゴリズムでは受信系列と事前情報の条件の下、トレリスの開始状態から各ノードへ到達する確率（フォワード値）を求める処理（フォワード処理）と、トレリスの終結状態から各ノードへ到達する確率（バックワード値）を求める処理（バックワード処理）と、フォワード値とバックワード値を利用して実際に式（１），（２）に示す値、またはその近似値である軟出力を求める軟出力生成処理から成る。フォワード処理は、畳込み符号の最尤復号法として知られているビタビ復号処理と同様の処理であり、時点を追ってフォワード値の更新を行う。バックワード処理は、トレリスの終端から時点を遡りバックワード値の更新を行う。このバックワード処理が必要であることがビタビ復号の場合と大きく異なる点である。
【００１２】
ターボ符号復号器の一般的な構成を図６に示す。図６において受信データメモリ801 は、復調器（図示せず）から受け取った受信値を格納する。外部情報メモリ802 は、繰り返しにおいて前回出力された各情報ビットの外部情報を格納する。要素符号の軟入力軟出力復号手段803 は、受信データメモリ801 および外部情報メモリ802 からデータを読み込み、算出された外部情報を外部情報メモリ802 に書き込む。必要に応じてインターリーバに合わせたアドレス変換を行う。ターボ符号では要素符号は時点数の大きな畳込み符号を用いるため、実装上はトレリス全体ではなく、その一部を利用して逐次出力を生成する局所的な復号を可能にすることで軟入力軟出力復号手段803 の小型化を図ることが可能となる。このときトレリスの初期時点から復号処理を開始する通常の方式においては、バックワード処理をどのように行うかが問題になる。これに関してはトレリスの一定時点分（ウィンドウと呼ばれる）先のすべての状態を等確率としてバックワード処理を行えば十分となることが知られており、例えば文献４“Soft-output decoding algorithms for continuous decoding of parallel concatenated convolutional codes”(Proceeding of IEEE International Conference on Communications, pp.112-117, 1996) に詳述されている。
【００１３】
復号装置では装置の大きさとともにデータのスループットを向上させることが重要である。上述のようにウィンドウを用いた方法においても軟出力復号は１サイクル毎に軟出力を生成できるようにすることが望まれる。バックワード処理部を２時点分設け、ウィンドウの大きさの時点分だけずらして動作させる復号スケジュールを組むことでこれを実現する方法が文献５“An intuitive justification and a simplified implementation of the MAP decoder for convolutional codes ”(IEEE Journal on Selected Areas on Communications, pp.260-264,1998)に記述されている。また、バックワード処理をウィンドウの大きさの時点分用意し、それをパイプライン化するハードウェア構成が文献６“VLSI architectures for turbo codes”(IEEE Transactions on VLSI systems, pp.369-379, 1999) に提案されている。この装置構成では受信値を順に連続的に読み込んでウィンドウの大きさの２倍の遅延で連続的に軟出力を生成することが可能となる。
【００１４】
【発明が解決しようとする課題】
ターボ符号の復号装置では要素符号である畳込み符号の局所的な軟入力軟出力復号装置の構成方法が第一の問題となる。基本的な要求としてスループットは大きく、装置規模は小さくということが挙げられる。軟入力軟出力復号装置ではフォワード処理、バックワード処理などの演算部とともにそれらの処理で算出したフォワード値、バックワード値をレジスタに格納する必要があり、このレジスタの個数が装置の大きさに影響を与える。また、文献６のように完全にパイプライン化したハードウェア構成ではバックワード処理部の個数が非常に大きくなり、レジスタの大きさも小さくすることはできない。
【００１６】
本発明の目的は、畳み込み符号の軟入力軟出力復号処理を行う誤り訂正符号復号装置の高いスループットを保ったままバックワード値を保持するレジスタの個数を小さくすることで小型化を図ることにある。
【００１７】
【課題を解決するための手段】
本発明の誤り訂正符号復号装置は、高いスループットを保ったままバックワード値を保持するレジスタの個数を小さくできるようにするため、
受信データおよび事前情報に基づき、符号トレリス上でのフォワード処理、バックワード処理およびそれらの処理で算出された値を利用して軟出力生成を行う誤り訂正符号復号装置において、
符号トレリス上の異なる時点のバックワード処理を同時に行う複数のバックワード処理モジュールを持ち、
受信データ、事前情報をメモリから周期的に逆順に読み込み、
前記バックワード処理モジュールへの入力は前記メモリから読み込んだ受信データ、事前情報であるか、もしくは予め決められた他のバックワード処理モジュールから出力される受信データ、事前情報であり、
前記メモリから読み込んだ受信データ、事前情報を入力とする前記バックワード処理モジュールは前記周期で交代するようにしている。
【００１８】
この構成によれば、軟出力を１サイクル毎に正順に出力し、しかも各バックワード処理モジュールが格納する入力データの時点数Ｔを小さくしても大きなウィンドウを実現することが可能となる。バックワード処理モジュールの個数をｎ、Ｔ＝２Ｂとしたとき、復号特性を決めるウィンドウの大きさの最小値は、（ｎ−１）Ｂで与えられる。フォワード処理，軟出力生成処理を行う手段が必要とするレジスタ数は、Ｂに比例するため、ｎの大きな装置構成を実現することで、復号特性を劣化させずにレジスタ数の小さな誤り訂正符号復号装置を得ることが可能になる。
【００２１】
【発明の実施の形態】
次に本発明の実施の形態について図面を参照して詳細に説明する。
【００２２】
本発明の実施の形態を図１に示す。図１は、例えば、図５(b) に示すターボ復号器704 あるいはターボ復号器705 の構成を示す図であり、複数個のバックワード処理モジュール100,110,120 と、フォワード処理・軟出力生成モジュール130 と、受信データメモリ140 と、外部情報メモリ150 とから構成される。受信データメモリ140 及び外部情報メモリ150 は、一般には外部メモリとして実現される。以下、図１に示すバックワード処理モジュールの個数が「３」の場合に説明するが、任意の個数（但し複数）でも同様である。
【００２３】
バックワード処理モジュール100,110,120 への入力は、受信データと事前情報であり、受信データメモリ140,外部情報メモリ150 から読み込む受信データ，事前情報もしくは他のバックワード処理モジュールから出力されるそれらの値である。メモリ140,150 から受信データ，事前情報を入力するバックワード処理モジュールは循環的に一定の周期で切り替えられ、メモリ140,150 から読み込み中でないバックワード処理モジュールは、メモリ140,150 からの読み込み順が自バックワード処理モジュールよりも１つ前のバックワード処理モジュールから出力されている受信データ，事前情報を読み込む。図１は、バックワード処理モジュール100 がメモリ140,150 から受信データ，事前情報を読み込み、バックワード処理モジュール110,120 がそれぞれバックワード処理モジュール100,110 から出力されている受信データ，事前情報を入力している状態を示している。
【００２４】
フォワード処理・軟出力生成モジュール130 への入力は、或るバックワード処理モジュールから出力される受信データ及び事前情報と、上記或るバックワード処理モジュールとは別のバックワード処理モジュールから出力されるバックワード値である。上記或るバックワード処理モジュールは、現在メモリ140,150 から受信データ，事前情報の読み込みを行っているバックワード処理モジュールであり、上記別のバックワード処理モジュールは、メモリ140,150 からの読み込み順が上記或るバックワード処理モジュールの次のバックワード処理モジュールである。図１は、フォワード処理・軟出力生成モジュール130 が、バックワード処理モジュール100 から出力される受信データ，事前情報を入力し、バックワード処理モジュール110 から出力されるバックワード値を入力している状態を示している。このように本実施の形態では複数の処理単位であるモジュールが簡単に連結された構成で軟入力軟出力復号処理を実現する。以下、それぞれの処理モジュールについて詳しく説明する。
【００２５】
バックワード処理モジュール100,110,120 は、すべて同一の構成である。その構成は図２に示すように受信データ格納手段101,事前情報格納手段102,バックワード値格納手段103 およびバックワード値更新手段104 から成る。受信データ格納手段101 および事前情報格納手段102 はシフトレジスタで構成する。以下の説明では、受信データ格納手段101 ，事前情報格納手段102 をシフトレジスタ101,102 と呼ぶ場合もある。図１と併せて復号器全体としてはそれらが直列に連結されて、円状の構成をとるとみることもできる。つまり、本実施の形態は、バックワード値格納手段103 とバックワード値更新手段104 とからなる複数のモジュールと、円状の一つの大きなシフトレジスタから成る受信データ格納手段，事前情報格納手段を持つ構成と解釈することも可能である。101,102 のシフトレジスタは同一の長さ（偶数）である。受信データメモリ140 から読み込んだ受信データは、受信データ格納手段101 に保存され、外部情報メモリ150 から読み込んだ事前情報は、事前情報格納手段102 に格納される。このとき必要に応じてインターリーバもしくはデインターリーバでアドレス変換された位置のデータを読み込む。バックワード値格納手段103 は、畳込み符号の少なくとも１時点分の各状態におけるバックワード値を格納するレジスタで構成される。バックワード値更新手段104 は、バックワード値格納手段103 の値を入力データに基づいて更新する。バックワード処理モジュール100,110,120 からの出力は、更新されたバックワード値およびシフトレジスタ101,102 の末端から出力される受信データ，事前情報である。
【００２６】
フォワード処理・軟出力生成モジュール130 は、図３に示すようにフォワード値更新手段131,フォワード値格納手段132,軟出力生成手段133,受信データ格納手段134,事前情報格納手段135 およびバックワード値格納手段136 から成る。フォワード値更新手段131 は、符号トレリスの先頭からのフォワード処理を実行し、フォワード値格納手段132 は、少なくとも畳込み符号の状態数と同一の個数のレジスタから構成される。また受信データ格納手段134 および事前情報格納手段135 は、バックワード処理モジュールのシフトレジスタ101,102 の長さと同一の個数のレジスタが必要かつ十分な大きさとなる。バックワード値格納手段136 は、（シフトレジスタ101 の長さ×畳込み符号の状態数）個のレジスタから構成される。
【００２７】
次に本実施の形態における各部位の動作を説明する。
【００２８】
本発明ではすべてのバックワード処理モジュール100,110,120 における受信データ格納手段101,事前情報格納手段102,演算部であるバックワード値更新手段104 およびフォワード処理モジュール130 におけるフォワード値更新手段131 および軟出力生成手段133 を同一のステップで動作させることを基本とする。以下、これらの要素で畳込み符号１時点分の処理を行うステップを１サイクルと呼ぶことにする。
【００２９】
バックワード処理モジュール100,110,120 は、１サイクル毎に、メモリ140,150 もしくは隣接するバックワード処理モジュール120,100,110 から１時点分の受信データと事前情報とを読み込む。入力をメモリ140,150 からとするバックワード処理モジュールは、バックワード処理モジュール100 →バックワード処理モジュール110 →バックワード処理モジュール120 →バックワード処理モジュール100 …の順で周期的に変更する。受信データ格納手段101 を構成するシフトレジスタの長さを２Ｂとすると、その周期はＢとなる。また、メモリ140,150 から受信データ，事前情報を読み込むバックワード処理モジュールは、読み込みが済んでいるメモリ140,150 上の受信データ，事前情報の次のＢサイクル分の受信データ，事前情報を逆順（発生順と逆の順序）で読み込む。一方、入力をメモリ140,150 からとしていないバックワード処理モジュールは、隣接するバックワード処理モジュールから出力される受信データ，事前情報を入力する。
【００３０】
従って、メモリ140,150 上の受信データおよび事前情報の内、時点Ｂ，…，１の受信データおよび事前情報が先ずバックワード処理モジュール100 に読み込まれ、以下、時点２Ｂ，…，Ｂ＋１の受信データ，事前情報がバックワード処理モジュール110 に、時点３Ｂ，…，２Ｂ＋１の受信データ，事前情報がバックワード処理モジュール120 に、時点４Ｂ，…，３Ｂ＋１の受信データ，事前情報が再びバックワード処理モジュール100 に読み込まれる。バックワード処理モジュールが読み込んだ受信データ，事前情報は、受信データ格納手段101,事前情報格納手段102 およびバックワード値更新手段104 に入力される。
【００３１】
シフトレジスタから構成される受信データ格納手段101,事前情報格納手段102 は、それぞれ入力された受信データ，事前情報を、１サイクルに１段ずつシフトする。受信データ格納手段101,事前情報格納手段102 を構成するシフトレジスタの段数は、２Ｂ段であるので、各バックワード処理モジュール100,110,120 は、入力した受信データ，事前情報を２Ｂだけ遅延して出力することになる。
【００３２】
バックワード値更新手段104 は、入力された受信データ，事前情報を用いてバックワード値格納手段103 に格納されているバックワード値を更新する処理を行う。バックワード値格納手段103 の初期化は、それを含んでいるバックワード処理モジュールへの入力がメモリからとなるタイミングで行われる。
【００３３】
各サイクルにおいて、或る１つのバックワード処理モジュールへの入力データ及びそこで生成されるバックワード値がフォワード処理・軟出力生成モジュール130 の入力となる。上記或る１つのバックワード処理モジュールは、メモリ140,150 から受信データ，事前情報を読み込んでいるバックワード処理モジュールの１個先のモジュールである。例えば、図１に示すように、バックワード処理モジュール100 がメモリ140,150 から受信データ，事前情報を読み込んでいる場合は、バックワード処理モジュール110 が上記或る１つのバックワード処理モジュールとなる。
【００３４】
フォワード値更新手段131 は、フォワード値格納手段132 に格納されているフォワード値を、受信データ格納手段134 および事前情報格納手段135 の内容に従って更新する。軟出力生成手段133 は、フォワード値格納手段132 に格納されているフォワード値と、受信データ格納手段134 に格納されている受信データと、事前情報格納手段135 に格納されている事前情報と、バックワード値格納手段136 に格納されているバックワード値とから式（２）に示す外部情報Le(u(k))を生成する。必要に応じて式（１）に基づき硬判定結果した情報も生成する。生成された外部情報は再び外部情報メモリ150 に書き込むか、別のメモリに書き込まれ、繰り返し復号における次の反復に利用される。
【００３５】
次に、図１〜図４を参照して本実施の形態の動作をより詳細に説明する。図４は図１〜図３に示した復号器の各部位が復号開始からの各サイクルで符号トレリス上のどの時点に対応する処理を行っているかを表す線図である。
【００３６】
サイクル１〜Ｂにおいて、バックワード処理モジュール100 は、バックワード値格納手段103 の初期化を行い、時点Ｂ，Ｂ−１，…，１の受信データおよび事前情報をメモリ140,150 から順に読み込んでバックワード処理を実行する。
【００３７】
サイクルＢ＋１〜２Ｂにおいて、バックワード処理モジュール110 は、バックワード値格納手段103 の初期化を行い、時点２Ｂ，２Ｂ−１，…，Ｂ＋１の受信データおよび事前情報をメモリ140,150 から順に読み込んでバックワード処理を実行する。
【００３８】
サイクル２Ｂ＋１〜３Ｂにおいて、バックワード処理モジュール120 は、バックワード値格納手段103 の初期化を行い、時点３Ｂ，３Ｂ−１，…，２Ｂ＋１の受信データおよび事前情報をメモリ140,150 から順に読み込んでバックワード処理を実行する。また、このサイクル２Ｂ＋１〜３Ｂにおいては、バックワード処理モジュール100 からバックワード処理モジュール110 に対して時点Ｂ，Ｂ−１，…，１の受信データ，事前情報が出力され、バックワード処理モジュール110 はそれらに従ってバックワード処理を行う。つまり、バックワード処理モジュール110 は、時点２Ｂから時点Ｂ，Ｂ−１，…，１までのバックワード値を順次求めることになる。
【００３９】
サイクル３Ｂ＋１〜４Ｂにおいて、バックワード処理モジュール100 は、バックワード値格納手段103 の初期化を行い、時点４Ｂ，４Ｂ−１，…，３Ｂ＋１の受信データ，事前情報をメモリ140,150 から読み込んでバックワード処理を行う。また、このサイクル３Ｂ＋１〜４Ｂにおいては、バックワード処理モジュール110 からバックワード処理モジュール120 に対して時点２Ｂ，２Ｂ−１，…，Ｂ＋１の受信データ，事前情報が出力され、バックワード処理モジュール120 は、時点３Ｂから時点２Ｂ，２Ｂ−１，…，Ｂ＋１までのバックワード値を順次求める。
【００４０】
サイクル４Ｂ＋１〜５Ｂにおいて、バックワード処理モジュール110 は、バックワード値格納手段103 の初期化を行い、時点５Ｂ，５Ｂ−１，…，４Ｂ＋１の受信データ，事前情報をメモリ140,150 から読み込んでバックワード処理を行う。また、このサイクル４Ｂ＋１〜５Ｂにおいては、バックワード処理モジュール120 からバックワード処理モジュール100 に対して時点３Ｂ，３Ｂ−１，…，２Ｂ＋１の受信データ，事前情報が出力され、バックワード処理モジュール100 が、時点４Ｂから時点３Ｂ，３Ｂ−１，…，２Ｂ＋１までのバックワード値を求める。更に、このサイクル４Ｂ＋１〜５Ｂにおいてはバックワード処理モジュール110 からバックワード処理モジュール120 に対して時点Ｂ，Ｂ−１，…，１の受信データ，事前情報が出力され、バックワード処理モジュール120 が、時点３Ｂから時点Ｂ，Ｂ−１，…，１までのバックワード値（ウィンドウサイズ２Ｂ〜３Ｂのバックワード値）を順次求める。つまりウィンドウの大きさ２Ｂ以上でのバックワード値算出が可能となる。以下同様に、各バックワード処理モジュールではウィンドウの大きさ２Ｂ以上のバックワード値算出を実現する。
【００４１】
一方、フォワード処理・軟出力生成モジュール130 は、サイクル４Ｂ＋１〜５Ｂにおいてバックワード処理モジュール120 で算出されたバックワード値をバックワード値格納手段136 に格納する。また、バックワード値を算出する際にバックワード処理モジュール120 で使用された時点Ｂ〜１の受信データ，事前情報（バックワード処理モジュール110 から出力された時点Ｂ〜１の受信データ，事前情報）もそれぞれ受信データ格納手段134,事前情報格納手段135 に保存される。従って、これらのデータを用いて、次のサイクル５Ｂ＋１から、時点１からのフォワード処理および軟出力生成処理を開始することが可能になる。
【００４２】
また、サイクル５Ｂ＋１〜６Ｂにおいて、フォワード処理・軟出力生成モジュール130 は、モジュール100 から出力されるバックワード値（時点２Ｂ，２Ｂ−１，…，Ｂ＋１に対応）を、バックワード値格納手段136 に格納し、バックワード処理モジュール120 から出力される受信データ，事前情報（時点２Ｂ，２Ｂ−１，…，Ｂ＋１に対応）をそれぞれ受信データ格納手段134,事前情報格納手段135 に格納する。本実施の形態では、受信データ格納手段134,事前情報格納手段135 を構成するレジスタの個数を２Ｂとしており、また、バックワード値格納手段136 を構成するレジスタの個数を（２Ｂ×状態数）としているので、現在フォワード処理，軟出力生成処理に使用している位置に上書きせずに、上記した各データを格納することができる。例えば、各格納手段134 〜136 を前半部分と後半部分とに２等分し、前半部分を（フォワード処理，軟出力生成処理）→（格納処理）→（フォワード処理，軟出力生成処理）…の順で使用し、後半部分を（格納処理）→（フォワード処理，軟出力生成処理）→（格納処理）…の順で使用すれば良い。以下、同様にサイクル毎に外部情報を連続的に生成することが可能となる。
【００４３】
次に、本実施の形態の効果について説明する。
【００４４】
本実施の形態では、それぞれがメモリ140,150 から一定時点数（Ｂ）分のデータを逆順に読み込む複数のバックワード処理モジュール100,110,120 を連結し、メモリ140,150 からの読み込みを行うバックワード処理モジュールを循環的（100 →110 →120 →100 …の順）に切り替えるようにすると共に、各バックワード処理モジュール100,110,120 に、メモリ140,150 から読み込んだ受信データ，事前情報と、１つ前のバックワード処理モジュールから送られてくる受信データ，事前情報とを２Ｂ遅延させて１つ先のバックワード処理モジュールに送る手段（受信データ格納手段101,事前情報格納手段102)と、自バックワード処理モジュールに入力される受信データ，事前情報に基づいてバックワード値を算出する手段（バックワード値格納手段103,バックワード値更新手段104)とを設けたので、各バックワード処理モジュール100,110,120 において、循環的に、ウィンドウサイズ２Ｂ〜３Ｂでバックワード値を算出することができる。また、フォワード処理・軟出力生成手段130 は、メモリ140,150 からの読み込みを行っているバックワード処理モジュールが出力している受信データ，事前情報に基づいてフォワード値を算出する手段（フォワード値更新手段131,フォワード値格納手段132,受信データ格納手段134,事前情報格納手段135)と、各バックワード処理モジュール100,110,120 において循環的に算出されるウィンドウサイズ２Ｂ〜３Ｂのバックワード値と、フォワード値と、受信データ，事前情報とに基づいて軟出力を生成する手段（軟出力生成手段133,バックワード値格納手段136)とを備えているので、図４に示すように、軟出力を一定の遅延の後にサイクル毎に連続的に生成することができ、しかも、各バックワード処理モジュールが格納する入力データの時点数を小さくしてもウィンドウサイズを大きくし、良好な復号特性を得ることができる。
【００４７】
【実施例】
最初に実施の形態におけるパラメータ設定についての説明を行う。復号性能を十分にするためには、本実施の形態において十分なウィンドウ長を持つバックワード処理を行う必要がある。ウィンドウの大きさの最小値をＷ、シフトレジスタ101,102 の長さを2B, バックワード処理モジュールの個数をｎとすると次式（３）の関係が成り立つ。
【００４８】
Ｗ＝Ｂ（ｎ−１）  …  （３）
【００４９】
一般にメモリ数ｍの畳込み符号を用いた場合には、８ｍ程度の時点数のウィンドウを使用してバックワード処理を行えば十分であることが知られている。ターボ符号の場合に広く利用されているｍ＝３の場合であったら、式（３）でＷが２４以上となる範囲でＢ，ｎをなるべく小さく設定することが装置規模の上で有利となる。Ｂは受信データ格納手段101,134 、事前情報格納手段102,135 およびバックワード値格納手段136 の大きさを決め、ｎはバックワード処理モジュールの個数を決めるパラメータであり、式（３）の制約の下でトータルとして最適化する形態でＢ，ｎを設定することが望ましい。
【００５０】
受信データメモリ140 から読み込む際に、ブランチメトリックを計算してからそれ以降の処理を行う実装法も考えることができる。このとき受信データ格納手段101 には受信データそのものではなく、ブランチメトリックを格納する。ブランチメトリックを格納することによるビット数の増加は、レート１／２であったら受信値２個で１つのブランチメトリックが生成されるため高々１エントリあたり１ビットの増加である。一方、バックワード処理モジュール、フォワード処理モジュールではブランチメトリックを計算する必要がなくなり、本実施の形態では同一のブランチメトリックを複数のバックワード処理モジュールで使用するため、ブランチメトリックを計算してから読み込むことは計算量、装置規模の両面で特に有効となる。
【００５１】
次にバックワード値更新手段104 、フォワード値更新手段131 および軟出力生成手段133 の実施例について述べる。ここでは事後確率最大(MAP) 復号アルゴリズム（BCJRアルゴリズムとも呼ばれる）に基づく場合について詳しく述べる。
【００５２】
畳込み符号の状態の集合をＳ＝｛０，１，…，｜Ｓ｜−１｝、時点ｔ，状態ｓにおけるフォワード値、バックワード値をそれぞれα(t, s), β(t, s)とおく。また、γ(t, s, s')で、状態ｓから状態s'への時点t での遷移の確率を表すとする。これは状態ｓから状態s'への遷移に対応する符号語と受信値との間の尤度と時点ｔの情報ビットの信頼度を表す事前情報から計算でき、尤度は白色ガウス通信路では通信路のSN比を用いて容易に計算することができる。ターボ符号の復号においては他方の要素符号の復号で生成された外部情報を事前情報として用いることが大きな特徴である。事後確率最大アルゴリズムにおけるバックワード処理は、次のように１時点後の値を用いて次式（４）に基づきそれぞれ実行される。
【００５３】
β(t, s) =Σβ(t+1, s') γ(t+1, s, s')  …  （４）
【００５４】
ここで和Σは、すべてのs'にわたる。時点ｔの軟出力（事後確率）は、すべての状態ｓ，s'に対するα(t-1, s), β(t+1, s') およびγ(t, s, s')を用いて生成することができる。各バックワード処理モジュールは、状態数個の式（４）を求める回路が並列に動作する実装形態が望ましい。一方、フォワード処理は、次のように１時点前の値を用いて式（５）に基づきそれぞれ実行される。
【００５５】
α(t, s)＝Σα(t-1, s') γ(t, s', s)  …  （５）
【００５６】
フォワード処理も状態数個の式（５）に基づく計算を行う回路が並列に動作する実装形態が望ましい。
【００５７】
また時点ｔの軟出力生成処理については最初に次式（６），（７）を求める。
【００５８】
M0 ＝Σ_(0)α(t-1, s')γ(t, s', s)β(t, s')     …  （６）
M1 ＝Σ_(1)α(t-1, s')γ(t, s', s)β(t, s')     …  （７）
【００５９】
ここで式（６）におけるΣ_(0) は、ｓからs'への遷移が情報ビット0 に対応する場合すべてをとり、Σ_(1) は、ｓからs'への遷移が情報ビット1 に対応する場合すべてをとる。Log(M1/M0)から式（１）に示すL(u(k)) が算出でき、またこれから式（２）に示した外部情報Le(u(K))が容易に算出される。Max-log-MAP アルゴリズムは上記の処理においてα, β, γの対数値をとって積を和に、和を最大値をとる操作に変更することにより行われる。Max-Log-MAP アルゴリズムでは事後確率最大アルゴリズムで必要であった積が不要になることが大きな特徴である。
【００６４】
【発明の効果】
以上説明したように、本発明の誤り訂正符号復号装置は、複数のバックワード処理モジュールを連結し、入力データを周期的に逆順に読み込む構成を有するので、軟出力を１サイクル毎に正順に出力し、しかも各バックワード処理モジュールが格納する入力データの時点数Ｔを小さくしても大きなウィンドウを実現することが可能となる。バックワード処理モジュールの個数をｎ、Ｔ＝２Ｂとしたとき、復号特性を決めるウィンドウの大きさの最小値は、（ｎ−１）Ｂで与えられる。バックワード値格納手段136 が必要とするレジスタ数は、Ｂに比例するため、本発明によってｎの大きな装置構成を実現することで、復号特性を劣化させずにレジスタ数の小さな誤り訂正符号復号装置を得ることが可能になる。特に、本発明に基づく装置構成では、各モジュールが簡単な入出力関係で連結されているため、モジュール毎に独立に設計すれば十分であり、ｎが大きな場合でも装置設計を容易に行うことができる。バックワード処理モジュールの装置量は、当然ｎに比例して増大するため、最適なｎはレジスタ数の減少との間で最適化を図ることで決定される。
【図面の簡単な説明】
【図１】  本発明の実施の形態の構成例を示すブロック図である。
【図２】  バックワード処理モジュール100,110,120 の構成例を示すブロック図である。
【図３】  フォワード処理・軟出力生成モジュール130 の構成例を示すブロック図である。
【図４】  バックワード処理モジュール100,110,120 及びフォワード処理・軟出力生成モジュール130 が復号器の各サイクルにおいて符号トレリス上のどの時点の処理を行っているかを表す図である。
【図５】  ターボ符号の符号装置、復号装置の一般的な構成例を示したブロック図である。
【図６】  ターボ符号復号器の一般的な装置例を示したブロック図である。
【符号の説明】
100,110,120…バックワード処理モジュール
130…フォワード処理・軟出力生成モジュール
140…受信データメモリ
150…外部情報メモリ
101…受信データ格納手段
102…事前情報格納手段
103…バックワード値格納手段
104…バックワード値更新手段
131…フォワード値更新手段
132…フォワード値格納手段
133…軟出力生成手段
134…受信データ格納手段
135…事前情報格納手段
136…バックワード値格納手段
701, 702…畳込み符号器
703, 706…インターリーバ
704, 705…復号器
707…デインターリーバ
801…受信データメモリ
802…外部情報メモリ
803…軟入力軟出力復号手段
【図１】
0003888135.tif 000002
【図２】
0003888135.tif 000003
【図３】
0003888135.tif 000004
【図４】
0003888135.tif 000005
【図５】
0003888135.tif 000006
【図６】
0003888135.tif 000007