(57)【特許請求の範囲】
【請求項１】
複数の畳込み符号をインターリーバで並列に連接した誤り訂正符号の繰り返し復号処理を行う誤り訂正符号復号装置において、
受信データを格納する受信データ格納手段と、
要素符号に対応する外部情報を格納する外部情報格納手段と、
前記外部情報の局所的な入出力が可能である局所的な軟入力軟出力復号手段を複数個持ち、
複数の前記局所的な軟入力軟出力復号手段は並列に動作し、
前記局所的な軟入力軟出力復号手段は他の要素符号に対応する局所的な軟入力軟出力復号手段で随時更新された外部情報を読み込み復号処理を行う、
ことを特徴とする誤り訂正符号復号装置。
【請求項２】
請求項１記載の誤り訂正符号復号装置であって、
前記要素符号の個数は２個であり、
前記局所的な軟入力軟出力復号手段の個数は２個であり、
前記局所的な軟入力軟出力復号手段は前記要素符号の先頭から順に復号処理を同時に実行する、
ことを特徴とする誤り訂正符号復号装置。
【請求項３】
請求項１記載の誤り訂正符号復号装置であって、
前記局所的な軟入力軟出力復号手段が、
符号トレリス上の異なる時点のバックワード処理を同時に行う複数のバックワード処理モジュールを持ち、
受信データ、事前情報をメモリから周期的に逆順に読み込み、
前記バックワード処理モジュールへの入力は前記メモリから読み込んだ受信データ、事前情報であるか、もしくは予め決められた他のバックワード処理モジュールから出力される受信データ、事前情報であり、
前記メモリから読み込んだ受信データ、事前情報を入力とする前記バックワード処理モジュールは前記周期で交代する、
ことを特徴とする誤り訂正符号復号装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は誤り訂正符号の復号技術に関し、特にターボ符号の復号法に代表される、連接符号に対し構成要素の軟出力復号を繰り返す復号技術に関する。
【背景技術】
【０００２】
誤り訂正符号化技術は、データの符号化・復号という操作を通じてデータ伝送時の通信路上で発生したビット反転等のエラーからデータを保護する技術であり、デジタル無線通信・記憶媒体をはじめとして現在広く利用されている。符号化は、送信する情報を、冗長ビットを付加した符号語に変換する操作である。復号は、その冗長性を利用してエラーが混入した符号語（受信語と呼ぶ）から送信された符号語（情報）を推定する操作である。
【０００３】
誤り訂正符号は、同一の符号であっても複数の復号法を考えることができる。通常、復号結果は、前述のように符号語またはそれを生成する情報ビット列として与えられるが、受信系列に対して各情報ビットを重み付きで推定する復号方法も知られており、軟出力復号法と呼ばれている。最適な軟出力復号は、符号語を構成するシンボル列であるという制約条件の下、受信語を条件として情報シンボルや符号語の各ビットの条件付き確率を出力する復号法であり、事後確率復号法と呼ばれている。情報シンボルが２値の場合には事後確率復号は次式（１）で与えられる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となる条件付確率である。
【０００６】
１９９３年ターボ符号と呼ばれる高性能符号が提案された（例えば、非特許文献１参照）。図７にターボ符号装置および復号装置の構成例を示す。ターボ符号装置は図７(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 アルゴリズムとも呼ばれる）が知られている（例えば、非特許文献２参照）。また、式（１）に示す値L(u(k)) の近似値を求めることで計算量を小さくするMax-Log-MAP アルゴリズムやLog-MAP アルゴリズムも知られている（例えば、非特許文献３参照）。
【００１１】
これらのアルゴリズムでは受信系列と事前情報の条件の下、トレリスの開始状態から各ノードへ到達する確率（フォワード値）を求める処理（フォワード処理）と、トレリスの終結状態から各ノードへ到達する確率（バックワード値）を求める処理（バックワード処理）と、フォワード値とバックワード値を利用して実際に式（１），（２）に示す値、またはその近似値である軟出力を求める軟出力生成処理から成る。フォワード処理は、畳込み符号の最尤復号法として知られているビタビ復号処理と同様の処理であり、時点を追ってフォワード値の更新を行う。バックワード処理は、トレリスの終端から時点を遡りバックワード値の更新を行う。このバックワード処理が必要であることがビタビ復号の場合と大きく異なる点である。
【００１２】
ターボ符号復号器の一般的な構成を図８に示す。図８において受信データメモリ801 は、復調器（図示せず）から受け取った受信値を格納する。外部情報メモリ802 は、繰り返しにおいて前回出力された各情報ビットの外部情報を格納する。要素符号の軟入力軟出力復号手段803 は、受信データメモリ801 および外部情報メモリ802 からデータを読み込み、算出された外部情報を外部情報メモリ802 に書き込む。必要に応じてインターリーバに合わせたアドレス変換を行う。ターボ符号では要素符号は時点数の大きな畳込み符号を用いるため、実装上はトレリス全体ではなく、その一部を利用して逐次出力を生成する局所的な復号を可能にすることで軟入力軟出力復号手段803 の小型化を図ることが可能となる。このときトレリスの初期時点から復号処理を開始する通常の方式においては、バックワード処理をどのように行うかが問題になる。これに関してはトレリスの一定時点分（ウィンドウと呼ばれる）先のすべての状態を等確率としてバックワード処理を行えば十分となることが知られている（例えば、非特許文献４参照）。
【００１３】
復号装置では装置の大きさとともにデータのスループットを向上させることが重要である。上述のようにウィンドウを用いた方法においても軟出力復号は１サイクル毎に軟出力を生成できるようにすることが望まれる。バックワード処理部を２時点分設け、ウィンドウの大きさの時点分だけずらして動作させる復号スケジュールを組むことでこれを実現する方法が知られている（例えば、非特許文献５参照）。また、バックワード処理をウィンドウの大きさの時点分用意し、それをパイプライン化するハードウェア構成が知られている（例えば、非特許文献６参照）。この装置構成では受信値を順に連続的に読み込んでウィンドウの大きさの２倍の遅延で連続的に軟出力を生成することが可能となる。
【００１４】
【非特許文献１】“Near Shannon limit error-correcting coding and decoding: Turbo codes”(Proceedings of IEEE International Conference of Communications, 1064-1070, 1993)
【非特許文献２】“Optimal decoding of linear codes for minimizing symbol error rate ”(IEEE Transaction on Information Theory, pp.284-287, 1974)
【非特許文献３】“A Comparison of optimal and sub-optimal MAP decoding algorithms ”(Proceedings of IEEE International Conference of Communications, pp.1009-1013, 1995)
【非特許文献４】“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)
【発明の開示】
【発明が解決しようとする課題】
【００１５】
ターボ符号の復号の特徴は、要素符号の軟出力復号で得られる外部情報を交換しながら復号を繰り返すことによって復号特性を向上させることにあり、この繰り返し復号という性質から遅延が生ずる。一般に通信路のSN比が小さいときには図７の復号器704,705 の処理を10回程度繰り返し実行させることが必要となる。インターリーバ、デインターリーバが存在するため、要素符号復号間の単純なパイプライン化も困難である。この繰り返し遅延を解決する手段の一つとして、要素符号１，２を同時に復号する方法が考えられる。このことに関しては例えば文献“Turbo Codes for PCS Applications”(Proceedings of the International Conference on Communications, pp.54-59, 1995) などに記述されている。この方法は、二つの要素符号1, 2, 1, 2, …という順序の復号を行う従来方式と、要素符号2, 1, 2, 1, …という復号を同時に独立に行う方式となり、最終的な硬判定出力を行うところのみが要素符号１，２，１，２，…とシリアルに復号する従来方法と異なり、本質的には従来方式を二重に行っていることに相当する。この方式では計算量の観点からは要素符号１，２の同時に１度の復号処理が繰り返し１回になるが、前述のように本質的には従来方式を二重化しただけのため繰り返し回数の増加を招く。
【００１６】
本発明の目的は、異なる要素符号間で同時に復号処理を実行させた場合の繰り返し回数を削減し、ターボ復号処理の高速化を図ることにある。
【課題を解決するための手段】
【００１７】
本発明の誤り訂正符号復号装置は、異なる要素符号間で同時に復号処理を実行させた場合の繰り返し回数を削減し、復号処理の高速化を図るため、
複数の畳込み符号をインターリーバで並列に連接した誤り訂正符号の繰り返し復号処理を行う誤り訂正符号復号装置において、
受信データを格納する受信データ格納手段と、
要素符号に対応する外部情報を格納する外部情報格納手段と、
前記外部情報の局所的な入出力が可能である局所的な軟入力軟出力復号手段を複数個持ち、
複数の前記局所的な軟入力軟出力復号手段は並列に動作し、
前記局所的な軟入力軟出力復号手段は他の要素符号に対応する局所的な軟入力軟出力復号手段で随時更新された外部情報を読み込み復号処理を行う。
【００１８】
〔作用〕
この構成によれば、要素符号１，２の復号が同時に行われるので、要素符号１の復号と要素符号２の復号を順に繰り返す従来のターボ復号と比較して、１度の反復における処理時間は１／２になる。なおかつ、この構成では、局所的な軟入力軟出力復号手段を用いることで１度の反復でも既に更新済みの外部情報を用いて軟出力生成処理を行うため、要素符号１，２を同時に復号しても繰り返し回数の増加を抑えることができる。
【発明の効果】
【００１９】
要素符号１の復号と要素符号２の復号を順に繰り返す従来のターボ復号と比較して、本発明は要素符号１，２を同時に復号するため、１度の反復における処理時間は１／２になる。なおかつ、本発明では局所的な軟入力軟出力復号手段を用いることで１度の反復でも既に更新済みの外部情報を用いて軟出力生成処理を行うため、要素符号１，２を同時に復号しても繰り返し回数の増加を抑えることができる。図１の構成例の場合でブロック長がターボ符号のインターリーブ長の１／10程度以下ならば繰り返し回数の増加は従来のターボ復号と比較して１回以下の増加で済む場合がほとんどである。従来の復号法で繰り返し回数が６の場合であったら本発明では繰り返し回数は７となるが１度の繰り返しに必要な時間は１／２のため従来の復号法の3.5 ／６（約０．６）に相当する時間で繰り返し復号全体を終了することができる。つまり、この場合には本発明によって従来の復号法に比して40％の処理時間の削減が可能となる。
【発明を実施するための最良の形態】
【００２０】
次に本発明の実施の形態について図面を参照して詳細に説明する。
【００２１】
本発明の前提技術を図１に示す。図１は、例えば、図７(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)とを備えているので、図４に示すように、軟出力を一定の遅延の後にサイクル毎に連続的に生成することができ、しかも、各バックワード処理モジュールが格納する入力データの時点数を小さくしてもウィンドウサイズを大きくし、良好な復号特性を得ることができる。
【００４４】
次に、本発明の実施の形態について説明する。本実施の形態は、ターボ符号の個々の要素符号に対して局所的な軟入力軟出力復号手段を持っている。図５を参照すると、本実施の形態は、局所的な軟入力軟出力復号手段500,501 と、外部情報メモリ502,503 と、受信データメモリ504,505 とから構成されている。軟入力軟出力復号手段500,501 は、それぞれ符号要素１，２に対応するものであり、例えば、図１に示した構成を有する。軟入力軟出力復号手段501 は、要素符号２に対応する。軟入力軟出力復号手段500 は外部メモリ503 から外部情報を読み込み、生成された外部情報を外部メモリ502 に書き出す。一方、軟入力軟出力復号手段501 は外部メモリ502 から外部情報を読み込み、外部メモリ503 に書き出す。これらのメモリへの読み書きはターボ符号の構成に応じてインターリーバもしくはデインターリーバでアドレスを変換して行う。
【００４５】
次に、本実施の形態の効果について説明する。最初に本実施の形態では、図５に示すように個々の要素符号に対して軟入力軟出力復号手段500,501 を用意することで、通常のターボ復号方式のように要素符号１，２を順に復号するのではなく要素符号１，２を同時に並列に復号することが可能となる。加えて、従来の要素符号１，２の並列復号方式のように繰り返し１回分の処理の中では２個の復号器が独立に動作するのではなく、局所的な軟入力軟出力復号手段を用い、図５のように２個の外部情報メモリ502,502 を配置することで更新済みの外部情報を随時利用することが可能となる。このことにより要素符号１，２を同時に復号する状況で外部情報の更新速度が大きくなることが期待できる。
【００４６】
〔実施例〕
最初に前提技術におけるパラメータ設定についての説明を行う。復号性能を十分にするためには、前提技術において十分なウィンドウ長を持つバックワード処理を行う必要がある。ウィンドウの大きさの最小値をＷ、シフトレジスタ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 アルゴリズムでは事後確率最大アルゴリズムで必要であった積が不要になることが大きな特徴である。
【００５９】
次に本実施の形態の実施例を示す。本実施の形態においては、繰り返し復号の１度の反復内において逐次的に外部情報が更新されることに特徴があり、この外部情報更新の様子を示した例が図６である。要素符号１，２はともに情報長＝16であるとし、インターリーバは時点ｐの情報ビットを式（８）に示す時点に変換するものを考える(p=0,1, ・・・,15)。
【００６０】
ｐ→（５×ｐ）mod 16 …  （８）
【００６１】
局所的な復号手段として、仮想的に受信データと他要素符号の外部情報を４時点単位で読み込み、軟出力を生成する方式を考える。この４時点をここではブロックと呼ぶことにする。図６の601, 602は、それぞれ図５の外部情報メモリ503,502 に対応する。より詳しく述べると、601 には要素符号２の復号で得られた外部情報をデインターリーブの順序で書き込んであり、602 には要素符号１の復号で得られた外部情報をインターリーブの順序で書き込んである。601 、602 において色付きのマスは繰り返し復号における現在の反復において既に更新済みの外部情報に対応する事前情報の位置を示す。
【００６２】
第１ブロックの復号において読み込まれる事前情報で現在の反復で更新されているものはない（図６(a) ）。第１ブロック終了後はブロック１（時点0,1,2,3 ）の外部情報は生成されているため、式（８）から要素符号２の時点0,5,10,15 に対応する時点は更新済みの事前情報を利用することができる。そこで要素符号２の復号手段による第２ブロックの復号には時点５の事前情報は更新済みのものが利用可能となる（図６(b) ）。同様に要素符号１の第２ブロック復号時には時点７の事前情報として更新済みを外部情報を用いることが可能となる（図６(b) ）。第２ブロック終了時には式（８）から要素符号１の時点4,5,6,7 に対応する、要素符号２の時点4,9,14,3の事前情報が繰り返し復号における現在の反復で生成された外部情報に新たに対応する。よって要素符号２の第３ブロック復号時には時点9,10の事前情報が現在の反復で更新済みの値となる。同様に要素符号１の第３ブロック復号時には時点10, 11が現在の反復で更新済みの事前情報となる（図６(c) ）。第４ブロックでも同様に考えると要素符号１，２ともに４時点分中３時点分の事前情報は現在の反復で更新済みの事前情報を利用して復号可能となる（図６(d)）。このように本発明においては要素符号の終わりのブロックはほとんどの時点において現在の反復で更新済みの外部情報を利用できるようになり、2 個の要素符号を同時に復号させた場合でも繰り返し回数に対する復号誤り率特性を従来のターボ復号程度に保持できるようになる。
【産業上の利用可能性】
【００６３】
本発明は、ターボ符号の復号装置に適用でき、異なる符号間で同時に復号するので、復号処理の高速化を図ることができる。
【図面の簡単な説明】
【００６４】
【図１】本発明の前提技術の構成例を示すブロック図である。
【図２】バックワード処理モジュール100,110,120 の構成例を示すブロック図である。
【図３】フォワード処理・軟出力生成モジュール130 の構成例を示すブロック図である。
【図４】バックワード処理モジュール100,110,120 及びフォワード処理・軟出力生成モジュール130 が復号器の各サイクルにおいて符号トレリス上のどの時点の処理を行っているかを表す図である。
【図５】本発明の実施の形態の構成例を示すブロック図である。
【図６】本発明の実施の形態における外部情報の更新の様子を模式的に表した図である。
【図７】ターボ符号の符号装置、復号装置の一般的な構成例を示したブロック図である。
【図８】ターボ符号復号器の一般的な装置例を示したブロック図である。
【符号の説明】
【００６５】
100,110,120…バックワード処理モジュール
130…フォワード処理・軟出力生成モジュール
140…受信データメモリ
150…外部情報メモリ
101…受信データ格納手段
102…事前情報格納手段
103…バックワード値格納手段
104…バックワード値更新手段
131…フォワード値更新手段
132…フォワード値格納手段
133…軟出力生成手段
134…受信データ格納手段
135…事前情報格納手段
136…バックワード値格納手段
500，501…局所的な軟入力軟出力復号手段
502, 503…外部情報メモリ
504, 505…受信データメモリ
601, 602…外部情報メモリ
701, 702…畳込み符号器
703, 706…インターリーバ
704, 705…復号器
707…デインターリーバ
801…受信データメモリ
802…外部情報メモリ
803…軟入力軟出力復号手段
【図１】
0004525658.tif 000002
【図２】
0004525658.tif 000003
【図３】
0004525658.tif 000004
【図４】
0004525658.tif 000005
【図５】
0004525658.tif 000006
【図６】
0004525658.tif 000007
【図７】
0004525658.tif 000008
【図８】
0004525658.tif 000009