(57)【要約】    【課題】      ターボ符号により誤り訂正符号化されたデータ列をＭＡＰ復号によって高速に復号するターボ復号装置をメモリ容量の増加を抑えつつシングル・ポート・メモリで構成すること。    【解決手段】  ウインドウ範囲を単位とした前方確率の計算と後方確率の計算とからなるウインドウ処理を所定回数繰り返すデータ範囲を２つに等分割する。一方のデータ範囲では、先に第２の状態確率計算手段１０４が後方確率を計算し、その後第１の状態確率計算手段１０３が前方確率を計算する。他方のデータ範囲では、先に第３の状態確率計算手段１０５が前方確率を計算し、その後第４の状態確率計算手段１０６が後方確率を計算する。メモリ選択手段１０９はウインドウ処理毎に２つの状態確率記憶手段１０７、１０８間で読み書きする状態確率を切り替える。  【選択図】      図１
2006217072.tif 000002
【特許請求の範囲】
【請求項１】
ターボ符号により誤り訂正符号化されたデータ列についての誤り訂正復号にスライディング・ウインドウ・アルゴリズムを用いた最大事後確率復号法が適用されるターボ復号装置において、
ウインドウ範囲を単位とした前方確率の計算と後方確率の計算とからなるウインドウ処理を所定回数繰り返すデータ範囲を偶数個に等分割し、そのうち２つのデータ範囲での一方のデータ範囲におけるデータ列について前記ウインドウ処理として先に前記後方確率の計算を行い、その後に前記前方確率の計算を行う第１のウインドウ処理手段と、
他方のデータ範囲におけるデータ列について前記ウインドウ処理として先に前記前方確率の計算を行い、その後に前記後方確率の計算を行う第２のウインドウ処理手段と、
２つの記憶領域を有し前記第１のウインドウ処理手段での後方確率の計算結果と前記第２のウインドウ処理手段での前方確率の計算結果とをそれぞれ記憶する状態確率記憶手段と、
前記第１のウインドウ処理手段での前方確率の計算結果と前記状態確率記憶手段が記憶する後方確率の計算結果とに基づく対数尤度比及び前記第２のウインドウ処理手段での後方確率の計算結果と前記状態確率記憶手段が記憶する前方確率の計算結果とに基づく対数尤度比をそれぞれ計算する対数尤度計算手段と、
前記状態確率記憶手段が有する２つの記憶領域の間で、前記第１のウインドウ処理手段が後方確率の計算結果を書き込みそれを前記対数尤度計算手段が読み出す記憶領域と、前記第２のウインドウ処理手段が前方確率の計算結果を書き込みそれを前記対数尤度計算手段が読み出す記憶領域とを前記ウインドウ処理毎に交互に切り替えるメモリ選択手段と、を具備することを特徴とするターボ復号装置。
【請求項２】
前記状態確率記憶手段が有する２つの記憶領域のそれぞれをウインドウ幅以下の容量を有する複数個の小領域に区分して管理し、前記メモリ選択手段が選択した記憶領域において書き込みと読み出しが競合しないように、アクセスするアドレスを前記複数個の小領域に割り当てる制御を行うアドレス制御手段、を具備することを特徴とする請求項１記載のターボ復号装置。
【請求項３】
前記アドレス制御手段は、前記複数個の小領域への割り当てをアクセスするアドレスの下位ビットの論理値によって制御することを特徴とする請求項２記載のターボ復号装置。
【請求項４】
ターボ符号により誤り訂正符号化されたデータ列についての誤り訂正復号にスライディング・ウインドウ・アルゴリズムを用いた最大事後確率復号法が適用されるターボ復号方法において、
ウインドウ範囲を単位とした前方確率の計算と後方確率の計算とからなるウインドウ処理を所定回数繰り返すデータ範囲を偶数個に等分割し、そのうち２つのデータ範囲において、一方のデータ範囲におけるデータ列について前記ウインドウ処理として先に前記後方確率の計算を行い、その後に前記前方確率の計算を行う第１のウインドウ処理工程と、
他方のデータ範囲におけるデータ列について前記ウインドウ処理として先に前記前方確率の計算を行い、その後に前記後方確率の計算を行う第２のウインドウ処理工程と、
前記第１のウインドウ処理工程での後方確率の計算結果と前記第２のウインドウ処理工程での前方確率の計算結果とを状態確率記憶手段が有する２つの記憶領域にそれぞれ記憶する工程と、
前記第１のウインドウ処理工程での前方確率の計算結果と前記状態確率記憶手段が記憶する後方確率の計算結果とに基づく対数尤度比及び前記第２のウインドウ処理工程での後方確率の計算結果と前記状態確率記憶手段が記憶する前方確率の計算結果とに基づく対数尤度比をそれぞれ計算する対数尤度計算工程と、
前記状態確率記憶手段が有する２つの記憶領域の間で、前記第１のウインドウ処理工程にて後方確率の計算結果を書き込みそれを前記対数尤度計算工程にて読み出す記憶領域と、前記第２のウインドウ処理工程にて前方確率の計算結果を書き込みそれを前記対数尤度計算工程にて読み出す記憶領域とを前記ウインドウ処理毎に交互に切り替えるメモリ選択工程と、を具備することを特徴とするターボ復号方法。
【請求項５】
前記状態確率記憶手段が有する２つの記憶領域のそれぞれをウインドウ幅以下の容量を有する複数個の小領域に区分して管理し、前記メモリ選択工程にて選択された記憶領域において書き込みと読み出しが競合しないように、アクセスするアドレスを前記複数個の小領域に割り当てる制御を行うアドレス制御工程、を具備することを特徴とする請求項４記載のターボ復号方法。
【請求項６】
前記アドレス制御工程では、前記複数個の小領域への割り当てをアクセスするアドレスの下位ビットの論理値によって制御することを特徴とする請求項５記載のターボ復号方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ターボ符号により誤り訂正符号化されたデータ列についての誤り訂正復号にスライディング・ウインドウ・アルゴリズムを用いた最大事後確率復号法が適用されるターボ復号装置及びターボ復号方法に関する。
【背景技術】
【０００２】
ターボ符号は、シャノンが提示した誤り制御符号の訂正能力の理論限界値に近接し、かつ現実的な処理量で実現することのできる符号として、近年、多くの分野で利用されてきている。例えば、第３世代移動通信では、標準符号化の１つとして用いられている。
【０００３】
ターボ符号器は、複数の要素符号器を交錯器（インターリーバ）を介して並列に使用することで構成される。復号時には、複数の要素復号器が各要素符号器に対応して軟判定復号を行い、相互に外部値である復号情報を交換し合って誤り訂正能力を向上させている。また、符号化後のデータ長を制御するために、各要素符号器出力の冗長データを定期的に削除するパンクチャリング処理を実施することで、符号化率を変える方法が採られている。
【０００４】
このターボ符号の復号では、最大事後確率（Maximum A posteriori Probability：ＭＡＰ）復号法がよく知られている。このＭＡＰ復号法は、要素復号器に入力されるデータ系列から、符号器内部データの符号化時の状態を推定し、発生した確率が最も高いと推定される状態に変化させる符号器入力を推定し、それを復号結果とする方法である。
【０００５】
この符号器入力の推定は、データ系列の先頭（始端）から末尾（終端）に向かって逐次的に状態を推定する前方確率の計算で得られる状態確率値と、データ系列の末尾（終端）から先頭（始端）に向かって逐次的に状態を推定する後方確率の計算で得られる状態確率値との両方を用いて行われるが、回路で実現する際は、何れか一方の確率値を先行して計算し、その全てをメモリに記憶し、その後に他方の確率値を逐次計算し、同時にメモリに蓄えられた一方の確率値とから符号器入力を推定する方法が採られる。
【０００６】
この推定方法では、確率値を記憶するメモリには、データ系列の長さ×状態確率数に従う大きさの記憶容量が必要となり回路実現の際に大きな負荷となる。これを解決する方法として、スライディング・ウインドウ・アルゴリズムが知られている（非特許文献１）。このスライディング・ウインドウ・アルゴリズムでは、データ系列をある程度のウインドウ長毎に分断し、それぞれのウインドウ範囲に対してウインドウ境界での状態値を推定しつつ順次復号処理を行うことで、確率値を記憶するメモリの記憶容量をウインドウ長×状態確率数に従う大きさに低減することができる。以下、ＭＡＰ復号法を用いる従来のターボ復号装置について概略説明する。
【０００７】
図８は、スライディング・ウインドウ・アルゴリズムを実現する従来のターボ復号装置の構成例を示すブロック図である。図８に示すターボ復号装置８００は、入力データ記憶手段８０１と、遷移確率計算手段８０２と、第１の状態確率計算手段８０３と、第２の状態確率計算手段８０４と、第１の状態確率記憶手段８０５と、第１の対数尤度計算手段８０６と、外部値計算手段８０７と、外部値記憶手段８０８と、出力データ記憶手段８０９とを備えている。
【０００８】
また、本図ならびに以降で示す図ではインターリーバをさす記号は記載されていないが、ターボ符号として当然所定の位置に付与されているものとする。
【０００９】
図８において、受信復調された入力データは、一旦入力データ記憶手段８０１に記憶される。遷移確率計算手段８０２は、入力データ記憶手段８０１と外部値記憶手段８０８とからそれぞれウインドウ長の単位で読み出されるデータ列に基づき、時点間の遷移確率を計算する。計算結果は、第１の対数尤度計算手段８０６と第１の状態確率計算手段８０３と第２の状態確率計算手段８０４とにそれぞれ出力される。
【００１０】
第１の状態確率計算手段８０３は、前方確率をウインドウ長毎にそのウインドウ長の始端から終端に向かう昇順で計算することを所定のデータ範囲において繰り返し行い、計算結果を第１の対数尤度計算手段８０６に出力する。第２の状態確率計算手段８０４は、後方確率をウインドウ長毎にそのウインドウ長の終端から始端に向かう降順で計算し、計算結果を第１の状態確率記憶手段８０５に記憶させることを所定のデータ範囲において繰り返し行う。
【００１１】
第１の状態確率計算手段８０３と第２の状態確率計算手段８０４との間では、先に第２の状態確率計算手段８０４が後方確率を上記のように計算し、その後に第１の状態確率計算手段８０３が前方確率を上記のように計算するようになっている。
【００１２】
第１の対数尤度計算手段８０６は、遷移確率計算手段８０２から入力する遷移確率と、第１の状態確率計算手段８０３から入力する前方確率と、第１の状態確率記憶手段８０５から読み出した同位置の後方確率とによって対数尤度比を計算する。
【００１３】
外部値計算手段８０７は、第１の対数尤度計算手段８０６が求めた対数尤度比から外部値を計算し、それを外部値記憶手段８０８に記憶させる。以上の動作が所定の復号回数繰り返し行われる。所定の復号回数経過時における第１の対数尤度計算手段８０６が求めた対数尤度比が硬判定用の出力データとして出力データ記憶手段８０９に記憶される。
【００１４】
ところで、スライディング・ウインドウ・アルゴリズムでは、ウインドウ単位に独立して計算できることを利用し、通常、前方確率の計算及び後方確率の計算とからなるウインドウ処理を所定の復号回数繰り返すデータ範囲を複数に分割し、各データ範囲においてウインドウ処理を並列に実行することで復号時間の短縮を図ることが行われている。
【００１５】
図９は、ウインドウ処理を所定の復号回数繰り返すデータ範囲を２つに等分割し、各データ範囲においてウインドウ処理を並列に実行する場合での従来のターボ復号装置の構成例を示すブロック図である。なお、図９では、図８に示した構成要素と同一ないしは同等である構成要素には同一の符号が付されている。
【００１６】
即ち、図９に示すように、２つのデータ範囲においてウインドウ処理の並列に実行する従来のターボ復号装置９００は、図８に示した構成に対して、前方確率の計算を行う第３の状態確率計算手段９０１と、後方確率の計算を行う第４の状態確率計算手段９０２と、後方確率を記憶する第２の状態確率記憶手段９０３と、対数尤度比を計算する第２の対数尤度計算手段９０４とが追加されている。その結果、外部値計算手段８０７は、第１の対数尤度計算手段８０６と第２の対数尤度計算手段９０４とがそれぞれ求めた対数尤度比から外部値を計算し、それを外部値記憶手段８０８に記憶させることになる。
【００１７】
なお、第１の対数尤度計算手段８０６は、遷移確率計算手段８０２から入力する遷移確率と、第１の状態確率計算手段８０３から入力する前方確率と、第２の状態確率記憶手段９０３から読み出した同位置の後方確率とによって対数尤度比を計算する。また、第２の対数尤度計算手段９０４は、遷移確率計算手段８０２から入力する遷移確率と、第３の状態確率計算手段９０１から入力する前方確率と、第１の状態確率記憶手段８０５から読み出した同位置の後方確率とによって対数尤度比を計算するとしている。
【００１８】
次に、図１０を参照して、動作について概略説明する。図１０は、図９に示す第１及び第２の状態確率記憶手段へのアクセスタイミングを説明するタイムチャートである。図１０に示すように、データ範囲は４８であるとし、上記したウインドウ長であるスライディング・ウインドウ範囲は８であるとする。したがって、復号開始時で言えば、時点「０」〜時点「４７」のデータ範囲は、時点「０」を始端とし時点「２３」を終端とするデータ範囲と、時点「２４」を始端とし時点「４７」を終端とするデータ範囲とに２等分割される。それぞれのデータ範囲では、３つのウインドウ処理が順に実行されるが、分割した２つのデータ範囲の間では対応する２つのウインドウ処理が並列に実行されることになる。
【００１９】
なお、図１０では、時点の順序番号を“□”内に示してあるが、この“□”表示は、「メモリへの書き込み要求」発生と、「メモリへの読み出し要求」発生と、「メモリ内のデータ占有期間」とを同時に示したものである。この“□”表示は、以下に示す各図において共通である。
【００２０】
さて、図１０において、復号処理が開始すると、スライディング・ウインドウ範囲を単位として各対象データ範囲の先頭から復号処理が実行される。ここでは、第１の状態確率計算手段８０３、第２の状態確率計算手段８０４及び第１の状態確率記憶手段８０５の対象データ範囲は、時点「０」を始端とし時点「２３」を終端とするデータ範囲であるとする。また、第３の状態確率計算手段９０１、第４の状態確率計算手段９０２及び第２の状態確率記憶手段９０３の対象データ範囲は、時点「２４」を始端とし時点「４７」を終端とするデータ範囲であるとする。双方とも同内容の復号処理が同様の手順で行われる。ここでは、時点「０」を始端とし時点「２３」を終端とするデータ範囲での復号処理について説明する。
【００２１】
時点「０」を始端とし時点「２３」を終端とするデータ範囲では、復号処理が開始されると、まず、時点「７」から時点「０」まで降順にデータがデータ入力記憶手段８０１から読み出される。そして、時点「７」の後方確率が第２の状態確率計算手段８０４にて計算される。計算された後方確率は、第１の状態確率記憶手段８０５にてアドレス「７」に書き込まれる。次に、時点「６」の後方確率が第２の状態確率計算手段８０４にて計算され、第１の状態確率記憶手段８０５にてアドレス「６」に書き込まれる。この処理が時点「０」の後方確率計算まで繰り返され、時点「０」の後方確率計算後に第１の状態確率計算手段８０３による前方確率の計算が開始される。
【００２２】
前方確率の計算は、時点「０」から昇順で開始される。前方確率の計算と同時に第１の状態確率記憶手段８０５から同位置の後方確率が昇順で読み出されて対数尤度比の計算に用いられる。つまり、第１の状態確率記憶手段８０５では、書き込みは降順に行われ、時点「０」の後方確率計算を終了すると、直後のタイミングから、時点「０」から昇順に時点「７」までの後方確率が読み出されることとなる。
【００２３】
以上のウインドウ処理が、次の時点「８」〜時点「１５」までのデータ、時点「１６」〜時点「２３」までのデータについて同様に行われる。時点「２４」を始端とし時点「４７」を終端とするデータ範囲についても同様である。このように所定のデータ範囲を２等分割して並列処理が行えるので、高速に復号することができる。
【００２４】
ここで、第１の状態確率記憶手段８０５と第２の状態確率記憶手段９０３の記憶幅は、通常、それぞれ、スライディング・ウインドウ範囲８と同じ幅８である。そのため、第１の状態確率記憶手段８０５及び第２の状態確率記憶手段９０３の読み出しが完了してからでないと、書込要求を発行できないので、復号の更なる高速化を図るのが困難である。例えば、時点「１３」の後方確率の書込要求が第１の状態確率記憶手段８０５のアドレス「５」に対して行われるタイミングでは、対数尤度比の計算では第１の状態確率記憶手段８０５のアドレス「２」の読み出しタイミングであるので、前回のウインドウ処理で書き込まれた時点「５」の後方確率が読み出されていない。この場合に、復号の更なる高速化を目的としてこの前回のウインドウ処理で書き込まれた時点「５」の後方確率が読み出される前に時点「１３」の後方確率の書込要求を発行すると、上書きが発生し、データの正確性が保障されなくなることが起こるからである。
【００２５】
そのため、復号の更なる高速化を図るためには、例えば、図１１に示すように、第１の状態確率記憶手段８０５及び第２の状態確率記憶手段９０３の容量を、それぞれスライディング・ウインドウ範囲×状態数以上の大きさにしてデータの正確性を保障する必要がある。図１１は、図１０に示すＭＡＰ復号の更なる高速化を従来技術によって図る場合の一例を示す図である。図１１（１）（２）では、第１の状態確率記憶手段８０５及び第２の状態確率記憶手段９０３を、それぞれスライディング・ウインドウ範囲８と同じ容量を有する２つのバンク（バンク１、バンク２）で構成し、ウインドウ範囲の単位で使用バンクを交互に変更する例が示されている。
【００２６】
この問題を解決する方策として、例えば特許文献１では、移動通信システム等のシステム内で要求される降順書き込み及び昇順読み出しのアドレスを仮想アドレスとし、実際にメモリ（第１の状態確率記憶手段８０５及び第２の状態確率記憶手段９０３）に与える物理アドレスを、昇順読み出しの後に行われる処理では昇順書き込み降順読み出しとなり、降順読み出しの後に行われる処理では降順書き込み昇順読み出しとなるようにメモリアドレスを制御する方法を提案されている。
【特許文献１】特開２００３−３２１２６号公報
【非特許文献１】“An intuitive justification and a simplified implementation of the MAP decoder for convolutional codes”, IEEE J. Sel. Areas Commun., vol.16, no.2, pp.260-264, Feb.1998.
【発明の開示】
【発明が解決しようとする課題】
【００２７】
しかし、特許文献１に開示される方法では、システム内で要求される仮想アドレスを物理アドレスに変換するアドレス変換手段を必要とする。また、読み出しの完了以前に書き込みを開始するために、メモリをシングル・ポート・メモリで構成することができず、デュアル・ポート・メモリで構成することが必要となってしまう。
【００２８】
通常、デュアル・ポート・メモリは、シングル・ポート・メモリと比較して回路規模が大きいので、大規模化する。また、ＡＳＩＣを用いた回路設計では、シングル・ポート・メモリを基本として設計が行われることが多いので、シングル・ポート・メモリを用いて構成できることが望まれる。
【００２９】
本発明は、かかる点に鑑みてなされたものであり、ターボ符号により誤り訂正符号化されたデータ列をＭＡＰ復号によって高速に復号する場合に、メモリ容量の増加を抑えつつシングル・ポート・メモリで構成することのできるターボ復号装置及びターボ復号方法を提供することを目的とする。
【課題を解決するための手段】
【００３０】
かかる課題を解決するため、本発明に係るターボ復号装置は、ターボ符号により誤り訂正符号化されたデータ列についての誤り訂正復号にスライディング・ウインドウ・アルゴリズムを用いた最大事後確率復号法が適用されるターボ復号装置において、ウインドウ範囲を単位とした前方確率の計算と後方確率の計算とからなるウインドウ処理を所定回数繰り返すデータ範囲を偶数個に等分割し、そのうち２つのデータ範囲での一方のデータ範囲におけるデータ列について前記ウインドウ処理として先に前記後方確率の計算を行い、その後に前記前方確率の計算を行う第１のウインドウ処理手段と、他方のデータ範囲におけるデータ列について前記ウインドウ処理として先に前記前方確率の計算を行い、その後に前記後方確率の計算を行う第２のウインドウ処理手段と、２つの記憶領域を有し前記第１のウインドウ処理手段での後方確率の計算結果と前記第２のウインドウ処理手段での前方確率の計算結果とをそれぞれ記憶する状態確率記憶手段と、前記第１のウインドウ処理手段での前方確率の計算結果と前記状態確率記憶手段が記憶する後方確率の計算結果とに基づく対数尤度比及び前記第２のウインドウ処理手段での後方確率の計算結果と前記状態確率記憶手段が記憶する前方確率の計算結果とに基づく対数尤度比をそれぞれ計算する対数尤度計算手段と、前記状態確率記憶手段が有する２つの記憶領域の間で、前記第１のウインドウ処理手段が後方確率の計算結果を書き込みそれを前記対数尤度計算手段が読み出す記憶領域と、前記第２のウインドウ処理手段が前方確率の計算結果を書き込みそれを前記対数尤度計算手段が読み出す記憶領域とを前記ウインドウ処理毎に交互に切り替えるメモリ選択手段とを具備する構成を採る。
【００３１】
この構成によれば、全てのウインドウ処理を通常通りに同一方向から行うのではなく、２つのデータ範囲において、対応するウインドウ処理が互いに逆となるように進行する。その結果、同一タイミングで発生する状態確率記憶手段への書き込み要求は、昇順降順共に存在し、また、読み出し要求も昇順降順共に存在する。そこで、状態確率を記憶手段に書き込む際に、昇順読み出しが行われた記憶手段に対しては昇順書き込みを行うウインドウの状態確率を選択し、降順読み出しが行われた記憶手段に対しては降順書き込みを行うウインドウの状態確率を選択することで、特別のアドレス変換手段を不要にすることができる。これによって、回路規模を増加させることなく、また記憶手段の容量を増加することなく、記憶手段内のデータの正確性を保障することができ、高速ＭＡＰ復号が実現できる。
【００３２】
本発明に係るターボ復号装置は、上記の発明において、前記状態確率記憶手段が有する２つの記憶領域のそれぞれをウインドウ幅以下の容量を有する複数個の小領域に区分して管理し、前記メモリ選択手段が選択した記憶領域において書き込みと読み出しが競合しないように、アクセスするアドレスを前記複数個の小領域に割り当てる制御を行うアドレス制御手段を具備する構成を採る。
【００３３】
この構成によれば、状態確率記憶手段が有する２つの記憶領域のそれぞれでは、降順書き込み昇順読み出しと昇順書き込み降順読み出しとが交互に発生するが、各記憶手段の持つ記憶領域を複数に分割して管理し、アクセスアドレスを割り当てるので、書き込み要求と読み出し要求との同時発生を回避することができる。したがって、状態確率記憶手段を実装面積の小さいシングル・ポート・メモリで構成することが可能となる。
【００３４】
本発明に係るターボ復号装置は、上記の発明において、前記アドレス制御手段は、前記複数個の小領域への割り当てをアクセスするアドレスの下位ビットの論理値によって制御する構成を採る。
【００３５】
この構成によれば、アドレス制御手段を簡素な構成で実現することができる。
【００３６】
本発明に係るターボ復号方法は、ターボ符号により誤り訂正符号化されたデータ列についての誤り訂正復号にスライディング・ウインドウ・アルゴリズムを用いた最大事後確率復号法が適用されるターボ復号方法において、ウインドウ範囲を単位とした前方確率の計算と後方確率の計算とからなるウインドウ処理を所定回数繰り返すデータ範囲を偶数個に等分割し、そのうち２つのデータ範囲において、一方のデータ範囲におけるデータ列について前記ウインドウ処理として先に前記後方確率の計算を行い、その後に前記前方確率の計算を行う第１のウインドウ処理工程と、他方のデータ範囲におけるデータ列について前記ウインドウ処理として先に前記前方確率の計算を行い、その後に前記後方確率の計算を行う第２のウインドウ処理工程と、前記第１のウインドウ処理工程での後方確率の計算結果と前記第２のウインドウ処理工程での前方確率の計算結果とを状態確率記憶手段が有する２つの記憶領域にそれぞれ記憶する工程と、前記第１のウインドウ処理工程での前方確率の計算結果と前記状態確率記憶手段が記憶する後方確率の計算結果とに基づく対数尤度比及び前記第２のウインドウ処理工程での後方確率の計算結果と前記状態確率記憶手段が記憶する前方確率の計算結果とに基づく対数尤度比をそれぞれ計算する対数尤度計算工程と、前記状態確率記憶手段が有する２つの記憶領域の間で、前記第１のウインドウ処理工程にて後方確率の計算結果を書き込みそれを前記対数尤度計算工程にて読み出す記憶領域と、前記第２のウインドウ処理工程にて前方確率の計算結果を書き込みそれを前記対数尤度計算工程にて読み出す記憶領域とを前記ウインドウ処理毎に交互に切り替えるメモリ選択工程とを具備するようにした。
【００３７】
この方法によれば、全てのウインドウ処理を通常通りに同一方向から行うのではなく、２つのデータ範囲において、対応するウインドウ処理が互いに逆となるように進行する。その結果、同一タイミングで発生する状態確率記憶手段への書き込み要求は、昇順降順共に存在し、また、読み出し要求も昇順降順共に存在する。そこで、状態確率を記憶手段に書き込む際に、昇順読み出しが行われた記憶手段に対しては昇順書き込みを行うウインドウの状態確率を選択し、降順読み出しが行われた記憶手段に対しては降順書き込みを行うウインドウの状態確率を選択することで、特別のアドレス変換手段を不要にすることができる。これによって、回路規模を増加させることなく、また記憶手段の容量を増加することなく、記憶手段内のデータの正確性を保障することができ、高速ＭＡＰ復号が実現できる。
【００３８】
本発明に係るターボ復号方法は、上記の発明において、前記状態確率記憶手段が有する２つの記憶領域のそれぞれをウインドウ幅以下の容量を有する複数個の小領域に区分して管理し、前記メモリ選択工程にて選択された記憶領域において書き込みと読み出しが競合しないように、アクセスするアドレスを前記複数個の小領域に割り当てる制御を行うアドレス制御工程を具備するようにした。
【００３９】
この方法によれば、状態確率記憶手段が有する２つの記憶領域のそれぞれでは、降順書き込み昇順読み出しと昇順書き込み降順読み出しとが交互に発生するが、各記憶手段の持つ記憶領域を複数に分割して管理し、アクセスアドレスを割り当てるので、書き込み要求と読み出し要求との同時発生を回避することができる。したがって、状態確率記憶手段を実装面積の小さいシングル・ポート・メモリで構成することが可能となる。
【００４０】
本発明に係るターボ復号方法は、上記の発明において、前記アドレス制御工程では、前記複数個の小領域への割り当てをアクセスするアドレスの下位ビットの論理値によって制御するようにした。
【００４１】
この方法によれば、アドレス制御を簡単な方法で実現することができる。
【発明の効果】
【００４２】
本発明によれば、ターボ符号により誤り訂正符号化されたデータ列をＭＡＰ復号によって高速に復号するターボ復号装置をメモリ容量の増加を抑えつつシングル・ポート・メモリで構成することができる。
【発明を実施するための最良の形態】
【００４３】
本発明の骨子は、ターボ符号により誤り訂正符号化されたデータ列についての誤り訂正復号にスライディング・ウインドウ・アルゴリズムを用いたＭＡＰ復号法が適用されるターボ復号装置において、ウインドウ範囲を単位とした前方確率の計算と後方確率の計算とからなるウインドウ処理を所定回数繰り返すデータ範囲を偶数個に等分割し、そのうちの２つのデータ範囲において、対応するウインドウ処理では、前方確率の計算と後方確率を計算とが互いに逆の関係で進行するようにし、２つの状態確率記憶手段では、降順書き込み昇順読み出しの要求と昇順書き込み降順読み出しの要求とが交互に行われるようにするが、２つの状態確率記憶手段間での書き込みと読み出しをウインドウ処理毎に切り替えるようにし、実際には１つの状態確率記憶手段では、順次読み出しが完了する前にこの読み出しと同方向の順次書き込みが行われるようにすることである。
【００４４】
以下、本発明の実施の形態について図面を参照して詳細に説明する。
【００４５】
（実施の形態１）
図１は、本発明の実施の形態１に係るターボ復号装置の構成を示すブロック図である。図１に示すターボ復号装置１００は、入力データ記憶手段１０１と、遷移確率計算手段１０２と、第１の状態確率計算手段１０３と、第２の状態確率計算手段１０４と、第３の状態確率計算手段１０５と、第４の状態確率計算手段１０６と、第１の状態確率記憶手段１０７と、第２の状態確率記憶手段１０８と、メモリ選択手段１０９と、アドレス制御手段１１０と、第１の対数尤度計算手段１１１と、第２の対数尤度計算手段１１２と、外部値計算手段１１３と、外部値記憶手段１１４と、出力データ記憶手段１１５とを備えている。
【００４６】
図１において、受信復調された入力データは、一旦入力データ記憶手段１０１に記憶される。遷移確率計算手段１０２は、入力データ記憶手段１０１と外部値記憶手段１１４とからそれぞれウインドウ長の単位で読み出されるデータ列に基づき、時点間の遷移確率を計算する。計算結果は、第１の状態確率計算手段１０３と、第２の状態確率計算手段１０４と、第３の状態確率計算手段１０５と、第４の状態確率計算手段１０６と、第１の対数尤度計算手段１１１と、第２の対数尤度計算手段１１２とにそれぞれ出力される。
【００４７】
第１の状態確率計算手段１０３は、前方確率をウインドウ長毎にそのウインドウ長の始端から終端に向かう昇順で計算することを所定のデータ範囲において繰り返し行い、計算結果を第１の対数尤度計算手段１１１に出力する。第２の状態確率計算手段１０４は、後方確率をウインドウ長毎にそのウインドウ長の終端から始端に向かう降順で計算し、計算結果を第１の状態確率記憶手段１０７と第２の状態確率記憶手段１０８のうちメモリ選択手段１０９が選択した状態確率記憶手段に書き込むことを所定のデータ範囲において繰り返し行う。
【００４８】
第１の状態確率計算手段１０３と第２の状態確率計算手段１０４との間では、先に第２の状態確率計算手段１０４が後方確率を上記のように計算し、その後に第１の状態確率計算手段１０３が前方確率を上記のように計算するようになっている。
【００４９】
第３の状態確率計算手段１０５は、前方確率をウインドウ長毎にそのウインドウ長の始端から終端に向かう昇順で計算し、計算結果を第１の状態確率記憶手段１０７と第２の状態確率記憶手段１０８のうちメモリ選択手段１０９が選択した状態確率記憶手段に書き込むことを所定のデータ範囲において繰り返し行う。第４の状態確率計算手段１０６は、後方確率をウインドウ長毎にそのウインドウ長の終端から始端に向かう降順で計算することを所定のデータ範囲において繰り返し行い、計算結果を第２の対数尤度計算手段１１２に出力される。
【００５０】
第３の状態確率計算手段１０５と第４の状態確率計算手段１０６との間では、先に第３の状態確率計算手段１０５が前方確率を上記のように計算し、その後に第４の状態確率計算手段１０６が後方確率を上記のように計算するようになっている。
【００５１】
第１の対数尤度計算手段１１１は、遷移確率計算手段１０２から入力する遷移確率と、第１の状態確率計算手段１０３から入力する前方確率と、第１の状態確率記憶手段１０７と第２の状態確率記憶手段１０８のうちメモリ選択手段１０９が選択した状態確率記憶手段から読み出した同位置の後方確率とによって対数尤度比を計算する。
【００５２】
また、第２の対数尤度計算手段１１２は、遷移確率計算手段１０２から入力する遷移確率と、第４の状態確率計算手段１０６から入力する後方確率と、第１の状態確率記憶手段１０７と第２の状態確率記憶手段１０８のうちメモリ選択手段１０９が選択した状態確率記憶手段から読み出した同位置の前方確率とによって対数尤度比を計算する。
【００５３】
外部値計算手段１１３は、第１の対数尤度計算手段１１１と第２の対数尤度計算手段１１２が、それぞれ求めた対数尤度比から外部値を計算し、それを外部値記憶手段１１４に記憶させる。以上の動作が所定の復号回数繰り返し行われる。所定の復号回数経過時における第１の対数尤度計算手段１１１と第２の対数尤度計算手段１１２が求めた対数尤度比が硬判定用の出力データとして出力データ記憶手段１１５に記憶される。
【００５４】
ここで、メモリ選択手段１０９は、第１の状態確率記憶手段１０７と第２の状態確率記憶手段１０８とをウインドウ処理毎に交互に選択して、書き込みを一方の状態確率記憶手段に実行し、読み出しを他方の状態確率記憶手段に実行することを実現する。
【００５５】
アドレス制御手段１１０は、後述（図３）するように、各ウインドウ処理において第１の状態確率記憶手段１０７及び第２の状態確率記憶手段１０８における書き込みアドレスと読み出しアドレスとを管理し、書き込みアドレスと読み出しアドレスとが競合しないように、メモリ選択手段１０９が選択する状態確率記憶手段における書き込みアドレスと読み出しアドレスとを制御する。
【００５６】
次に、図２を参照して、全体的な動作について説明する。図２は、図１に示す第１及び第２の状態確率記憶手段へのアクセスタイミングを説明するタイムチャートである。図２（１）は一連の処理動作を説明するタイムチャート、図２（２）は第２の状態確率記憶手段１０８へのアクセスタイミングを説明するタイムチャート、図２（３）は第１の状態確率記憶手段１０７へのアクセスタイミングを説明するタイムチャートである。
【００５７】
図２（１）に示すように、データ範囲は４８であるとし、スライディング・ウインドウ範囲は８であるとする。したがって、復号開始時で言えば、時点「０」〜時点「４７」のデータ範囲は、時点「０」を始端とし時点「２３」を終端とするデータ範囲と、時点「２４」を始端とし時点「４７」を終端とするデータ範囲とに２等分割される。それぞれのデータ範囲では、３つのウインドウ処理が順に実行されるが、分割した２つのデータ範囲の間では対応する２つのウインドウ処理が並列に実行されることになる。
【００５８】
この図２（１）と図１０（１）との比較から理解できるように、本実施の形態１では、時点「０」を始端とし時点「２３」を終端とするデータ範囲と、時点「２４」を始端とし時点「４７」を終端とするデータ範囲とにおいて、対応するウインドウ処理では、前方確率の計算と後方確率を計算とが互いに逆の関係で進行するようになっている。そして、第１の状態確率記憶手段１０７及び第２の状態確率記憶手段１０８への書き込みと読み出しは、メモリ選択手段１０９がウインドウ処理毎に切り替えるようにしている。
【００５９】
図２では、第１の状態確率計算手段１０３及び第２の状態確率計算手段１０４の対象データ範囲は、時点「０」を始端とし時点「２３」を終端とするデータ範囲であるとし、第３の状態確率計算手段１０５及び第４の状態確率計算手段１０６の対象データ範囲は、時点「２４」を始端とし時点「４７」を終端とするデータ範囲であるとしている。
【００６０】
さて、図２（１）において、復号処理が開始すると、スライディング・ウインドウ範囲を単位として各対象データ範囲の先頭から復号処理が実行される。なお、メモリ選択手段１０９は、復号処理の開始直後に行われる最初のウインドウ処理の期間では、初期状態として、第１の状態確率記憶手段１０７と第２の状態確率計算手段１０４及び第２の対数尤度計算手段１１２との間を接続し、第２の状態確率記憶手段１０８と第３の状態確率計算手段１０５及び第１の対数尤度計算手段１１１との間を接続している。その後の各ウインドウ処理では、交互に選択を切り替えるようになっている。このとき、アドレス制御手段１１０が、第１の状態確率記憶手段１０７及び第２の状態確率記憶手段１０８に書き込むアドレスと読み出すアドレスの制御を行うようになっている。
【００６１】
時点「０」を始端とし時点「２３」を終端とするデータ範囲での最初のウインドウ処理では、時点「７」の後方確率が第２の状態確率計算手段１０４にて計算され、第１の状態確率記憶手段１０７に書き込まれる。次に、時点「６」の後方確率が第２の状態確率計算手段１０４にて計算され、第１の状態確率記憶手段１０７に書き込まれる。この処理が時点「０」の後方確率まで繰り返され、時点「０」の後方確率計算後に第１の状態確率計算手段１０３による前方確率の計算が開始される。
【００６２】
前方確率の計算は、時点「０」から昇順で開始され、計算結果が第１の対数尤度計算手段１１１に与えられる。前方確率の計算と同時に第１の状態確率記憶手段１０７から同位置の後方確率が昇順で読み出され、第１の対数尤度計算手段１１１による対数尤度比の計算に用いられる。つまり、第１の状態確率記憶手段１０７では、時点「７」から時点「０」までの後方確率の書き込みが降順に行われ、時点「０」の後方確率の計算を終了すると時点「０」から昇順に時点「７」までの後方確率が読み出されることとなる。
【００６３】
一方、時点「２４」を始端とし時点「４７」を終端とするデータ範囲での最初のウインドウ処理では、時点「４０」の前方確率が第３の状態確率計算手段１０５にて計算され、第２の状態確率記憶手段１０８に書き込まれる。次に、時点「４１」の前方確率が第３の状態確率計算手段１０５にて計算され、第２の状態確率記憶手段１０８に書き込まれる。この処理が時点「４７」の前方確率まで繰り返され、時点「４７」の前方確率計算後に第４の状態確率計算手段１０６による後方確率の計算が開始される。
【００６４】
後方確率の計算は、時点「４７」から降順で開始され、計算結果が第２の対数尤度計算手段１１２に与えられる。後方確率の計算と同時に第２の状態確率記憶手段１０８から同位置の前方確率が降順で読み出され、第２の対数尤度計算手段１１２による対数尤度比の計算に用いられる。つまり、第２の状態確率記憶手段１０８では、時点「４０」から時点「４７」までの前方確率の書き込みが昇順に行われ、時点「４７」の前方確率の計算を終了すると、時点「４７」から時点「４０」までの前方確率が降順で読み出されることとなる。
【００６５】
２回目のウインドウ処理は、上記した１回目のウインドウ処理において読み出しが開始された直後のタイミングから開始される。同時に、メモリ選択手段１０９は、第１の状態確率記憶手段１０７及び第２の状態確率記憶手段１０８への接続を切り替える。即ち、メモリ選択手段１０９は、第１の状態確率記憶手段１０７と第３の状態確率計算手段１０５及び第１の対数尤度計算手段１１１との間を接続し、第２の状態確率記憶手段１０８と第２の状態確率計算手段１０４及び第２の対数尤度計算手段１１２との間を接続している。
【００６６】
時点「０」を始端とし時点「２３」を終端とするデータ範囲での２回目のウインドウ処理では、１回目のウインドウ処理において時点「１」の前方確率の計算が行われるタイミングで、時点「１５」の後方確率が第２の状態確率計算手段１０４にて計算され、第２の状態確率記憶手段１０８に書き込まれる。次に、時点「１４」の後方確率が第２の状態確率計算手段１０４にて計算され、第２の状態確率記憶手段１０８に書き込まれる。この処理が時点「８」の後方確率計算まで繰り返され、時点「８」の後方確率計算後に第１の状態確率計算手段１０３による前方確率の計算が開始される。
【００６７】
前方確率の計算は、時点「８」から昇順で開始される。前方確率の計算と同時に第２の状態確率記憶手段１０８から同位置の後方確率が昇順で読み出されて対数尤度比の計算に用いられる。つまり、第２の状態確率記憶手段１０８では、後方確率の書き込みは降順に行われ、時点「８」の後方確率計算を終了すると、時点「８」から昇順に時点「１５」までの後方確率が読み出されることとなる。
【００６８】
ここで、第２の状態確率記憶手段１０８では、図２（２）に示すように、時点「４７」の前方確率が読み出された次のタイミングで時点「１５」の後方確率が書き込まれるというように、時点「４７」から時点「４０」までの前方確率が降順で読み出された直後に時点「１５」から時点「８」までの後方確率が降順で書き込まれることになるので、データの上書きが発生せず、データの正確性が確保される。
【００６９】
時点「２４」を始端とし時点「４７」を終端とするデータ範囲での２回目のウインドウ処理では、１回目のウインドウ処理において時点「４８」の前方確率の計算が行われるタイミングで、時点「３２」の前方確率が第３の状態確率計算手段１０５にて計算され、第１の状態確率記憶手段１０７に書き込まれる。以降、第３の状態確率計算手段１０５にて計算される時点「３２」から時点「３９」まで前方確率が第１の状態確率記憶手段１０７に書き込まれる。
【００７０】
この場合、第１の状態確率記憶手段１０７では、図２（３）に示すように、時点「０」の後方確率が読み出された次のタイミングで時点「３２」の前方確率が書き込まれるというように、時点「０」から時点「７」までの後方確率が昇順で読み出された直後に時点「３２」から時点「３９」までの前方確率が昇順で書き込まれることになるので、データの上書きが発生せず、データの正確性が確保される。
【００７１】
３回目のウインドウ処理は、上記した２回目のウインドウ処理において読み出しが開始された直後のタイミングから開始される。同時に、メモリ選択手段１０９は、第１の状態確率記憶手段１０７及び第２の状態確率記憶手段１０８への接続を切り替える。即ち、メモリ選択手段１０９は、第１の状態確率記憶手段１０７と第２の状態確率計算手段１０４及び第２の対数尤度計算手段１１２との間を接続し、第２の状態確率記憶手段１０８と第３の状態確率計算手段１０５及び第１の対数尤度計算手段１１１との間を接続している。これは、最初のウインドウ処理での接続関係である。
【００７２】
時点「０」を始端とし時点「２３」を終端とするデータ範囲での３回目のウインドウ処理では、２回目のウインドウ処理において時点「９」の前方確率の計算が行われるタイミングで、時点「２３」の後方確率が第２の状態確率計算手段１０４にて計算され、第１の状態確率記憶手段１０７に書き込まれる。以降、第２の状態確率計算手段１０４にて計算される時点「２３」から時点「１６」まで後方確率が第１の状態確率記憶手段１０７に書き込まれる。
【００７３】
この場合、第１の状態確率記憶手段１０７では、図２（３）に示すように、時点「３９」の前方確率が読み出された次のタイミングで時点「２３」の後方確率が書き込まれるというように、時点「３９」から時点「３２」までの前方確率が降順で読み出された直後に時点「２３」から時点「１６」までの後方確率が降順で書き込まれることになるので、データの上書きが発生せず、データの正確性が確保される。
【００７４】
また、時点「２４」を始端とし時点「４７」を終端とするデータ範囲での３回目のウインドウ処理では、２回目のウインドウ処理において時点「３８」の前方確率の計算が行われるタイミングで、時点「２４」の前方確率が第３の状態確率計算手段１０５にて計算され、第２の状態確率記憶手段１０８に書き込まれる。以降、第３の状態確率計算手段１０５にて計算される時点「２４」から時点「３１」まで前方確率が第２の状態確率記憶手段１０８に書き込まれる。
【００７５】
この場合、第２の状態確率記憶手段１０８では、図２（２）に示すように、時点「８」の後方確率が読み出された次のタイミングで時点「２４」の前方確率が書き込まれるというように、時点「８」から時点「１５」までの後方確率が昇順で読み出された直後に時点「２４」から時点「３１」までの前方確率が昇順で書き込まれることになるので、データの上書きが発生せず、データの正確性が確保される。
【００７６】
次に、図３は、図１に示す第１及び第２の状態確率記憶手段１０７、１０８の構成と図１に示すアドレス制御手段の動作とを説明する図である。図３（１）は、図２（３）に示す第１の状態確率記憶手段１０７のアクセス内容を転記したものである。図３（２）（３）は、各状態確率記憶手段が備える記憶領域を構成する２つのバンクのアクセス内容を示す図である。
【００７７】
図２で示したタイミングで復号処理がなされるときは、状態確率記憶手段にアクセスする書き込みアドレスと読み出しアドレスが偶数アドレスと奇数アドレスとで競合する。一方、アドレスは昇順列又は降順列で発生するため、読み出しアドレスと書き込みアドレスとの競合が偶数アドレスと奇数アドレスとで発生する場合には、偶数同士或いは奇数同士の読み出し書き込みが競合することはありえない。
【００７８】
そこで、状態確率記憶手段が備える記憶領域をスライディング・ウインドウ範囲と同じ幅８で構成する。そして、アドレス制御手段１１０は、その幅８の記憶領域を幅４の領域に区分し、一方を奇数アドレス用バンク（図３（２））とし、他方を偶数アドレス用バンク（図３（３））として用いる。
【００７９】
具体的には、アドレス制御手段１１０は、各状態確率記憶手段にアクセスするアドレスの最下位ビットを確認し、値「１」、値「３」等の奇数であるときは、奇数アドレス用バンク（図３（２））にアクセスし、値「０」、値「２」等の偶数であるときは、偶数アドレス用バンク（図３（３））にアクセスする制御を行うようにしている。
【００８０】
読み出しと書き込みとが競合する場合は、両者のアドレスの一方が奇数であり、他方が偶数であるので、実際に状態確率記憶手段への要求時に読み書きの競合が発生する場合において、それぞれ、奇数アドレス用バンク、偶数用アドレス用バンクへと異なるバンクに対してアクセスが行われる。
【００８１】
書き込みの具体例を示す。例えば、時点「０」を始端とし時点「２３」を終端とするデータ範囲での最初のウインドウ処理の例で言えば、時点「７」の後方確率が第２の状態確率計算手段１０４にて計算され、第１の状態確率記憶手段１０７にてアドレス「７」に記憶しようとする場合、アドレス「７」の最下位ビットが“１”であるので、図３（２）に示すうに、奇数アドレス用バンクのアドレス「３」に時点「７」の後方確率を書き込む。
【００８２】
次の時点「６」の後方確率が第２の状態確率計算手段１０４にて計算され、第１の状態確率記憶手段１０７にてアドレス「６」に記憶しようとする場合、アドレス「６」の最下位ビットが“０”であるので、図３（３）に示すように、偶数アドレス用バンクのアドレス「３」に時点「６」の後方確率を書き込む。
【００８３】
以上のように、実施の形態１によれば、ウインドウ範囲を単位とした前方確率の計算と後方確率の計算とからなるウインドウ処理を所定回数繰り返すデータ範囲を２つに等分割し、その分割した２つのデータ範囲において、対応するウインドウ処理では、前方確率の計算と後方確率を計算とが互いに逆の関係で進行するようにし、２つの状態確率記憶手段では、降順書き込み昇順読み出しの要求と昇順書き込み降順読み出しの要求とが交互に行われるようにするが、２つの状態確率記憶手段間での書き込みと読み出しをウインドウ処理毎に切り替えるようにし、実際には１つの状態確率記憶手段では、順次読み出しが完了する前にこの読み出しと同方向の順次書き込みが行われるので、データの上書きが発生せず、データの正確性を確保することができる。
【００８４】
したがって、状態確率記憶手段の記憶領域を有効に利用しつつ、つまりメモリ容量を節約しつつ読み出しの完了前に書き込みが行えるので、ＭＡＰ復号の高速化を図ることができる。そして、特許文献１のように特別のアドレス変換手段を用いてアドレスそのものを変更することなく、アクセスするアドレスの順序を逆にすることができるので、回路規模の小型化が図れる。
【００８５】
また、２つの状態確率記憶手段では、それぞれへのアクセス制御を読み書きのアクセス競合が偶数と奇数との間で起きないように、ウインドウ幅以下の複数の小容量記憶領域で構成できるので、シングル・ポート・メモリを用いた構成が可能となり、実装面積を小さくすることができる。
【００８６】
ところで、ウインドウ処理間の処理タイミングとして、図２では、第２の状態確率計算手段１０４によって計算された時点「０」の後方確率が第１の状態確率記憶手段１０７から読み出される次のタイミングで、第３の状態確率計算手段１０５によって計算された時点「３２」の前方確率が第１の状態確率記憶手段１０７に書き込まれる場合を示したが、実際には、その他、各種のタイミングが考えられる。この場合には、第１の状態確率記憶手段１０７及び第２の状態確率記憶手段１０８の構成とアドレス制御手段１１０の動作とが異なることになる。以下、若干の変形態様を実施の形態２、３に示す。
【００８７】
（実施の形態２）
図４は、本発明の実施の形態２に係るターボ復号装置における第１及び第２の状態確率記憶手段１０７、１０８へのアクセスタイミングを説明するタイムチャートである。図４（１）は一連の処理動作を説明するタイムチャート、図４（２）は第２の状態確率記憶手段１０８へのアクセスタイミングを説明するタイムチャート、図４（３）は第１の状態確率記憶手段１０７へのアクセスタイミングを説明するタイムチャートである。
【００８８】
また、図５は、本発明の実施の形態２に係るターボ復号装置における第１及び第２の状態確率記憶手段１０７、１０８の構成とアドレス制御手段の動作とを説明する図である。図５（１）は、図４（３）に示す第１の状態確率記憶手段１０７のアクセス内容を転記したものである。図５（２）（３）は、状態確率記憶手段が備える記憶領域を構成する２つのバンクのアクセス内容を示す図である。
【００８９】
本実施の形態２では、図４（１）に示すように、ウインドウ処理間の処理タイミングとして、第２の状態確率計算手段１０４によって計算された時点「０」の後方確率が第１の状態確率記憶手段１０７から読み出される同じタイミングで、第３の状態確率計算手段１０５によって計算された時点「３２」の前方確率が第１の状態確率記憶手段１０７に書き込まれる場合について説明する。
【００９０】
２つの状態確率記憶手段が用意すべき記憶領域の幅は、図２（１）に示すタイミング関係でのウインドウ処理ではウインドウ幅と同じで良いが、図４（１）に示すタイミング関係でのウインドウ処理ではウインドウ幅よりも１つ多く必要となる。したがって、図４（２）（３）に示すように、２つの状態確率記憶手段の何れもがアクセスアドレスを１つインクリメントした幅を有する記憶領域を用意する必要がある。
【００９１】
これによって、例えば、第２の状態確率計算手段１０４によって計算される時点「７」の後方確率は、図４（３）に示すように、アドレス制御手段１１０によって第１の状態確率記憶手段１０７のアドレス「８」に書き込むデータとして以後扱い、同様に時点「０」の後方確率はアドレス「１」に書き込むデータとして以後扱うことができる。
【００９２】
また、第２の状態確率計算手段１０４によって計算される時点「１５」の後方確率は、図４（２）に示すように、アドレス制御手段１１０によって、第２の状態確率記憶手段１０８のアドレス「８」に書き込むデータとして以後扱い、同様に時点「８」の後方確率はアドレス「１」に書き込むデータとして以後扱うことができる。
【００９３】
また、第３の状態確率計算手段１０５によって計算される時点「４０」の前方確率は、図４（２）に示すように、アドレス制御手段１１０によって第２の状態確率記憶手段１０８のアドレス「０」に書き込むデータとて以後扱い、同様に時点「４７」の前方確率はアドレス「７」に書き込むデータとして以後扱うことができる。
【００９４】
また、第３の状態確率計算手段１０５によって計算される時点「３２」の前方確率は、図４（３）に示すように、アドレス制御手段１１０によって第１の状態確率記憶手段１０７のアドレス「０」に書き込むデータとして以後扱い、同様に時点「３９」の前方確率はアドレス「７」に書き込むデータとして以後扱うことができる。
【００９５】
このような処理では、２つの状態確率記憶手段へのアクセスアドレスが昇順列又は降順列で発生するので、２つの状態確率記憶手段では、読み出しと書き込みのアクセス競合が偶数同士、奇数同士で発生することとなる。この場合には、図５（２）（３）に示すように、２つの状態確率記憶手段に幅９の記憶領域をそれぞれ用意する。そして、実施の形態１にて説明したように、アクセスするアドレスの最下位ビットの偶奇を判定するアドレス制御手段１１０が、その幅９の記憶領域を幅５の領域と幅４の領域とに区分して管理し、幅５の領域（図５（２））を偶数アドレス用バンクとし、幅４の領域（図５（３））を奇数アドレス用バンクとして用いるようにする。但し、ウインドウ幅の始端と終端では、一方を偶数アドレス用バンクに割り当てるときは、他方は奇数アドレス用バンクに割り当てるようにする。
【００９６】
例えば、第２の状態確率計算手段１０４で計算される時点「７」の後方確率は、第１の状態確率記憶手段１０７に対してアドレス「８」に書き込まれるデータとして送られる。このアドレス番号の最下位ビットは“０”、つまり偶数であるので、アドレス制御手段１１０は図５（２）に示すように偶数アドレス用バンクのアドレス「４」に割り当てる。この場合、第２の状態確率計算手段１０４で計算される時点「０」の後方確率は、図５（３）に示すように、奇数アドレス用バンクのアドレス「０」に割り当てる。
【００９７】
また、第３の状態確率計算手段１０５で計算される時点「３２」の前方確率は、第１の状態確率記憶手段１０７に対してアドレス「０」に書き込まれるデータとして送られる。このアドレスの最下位ビットは“０”、つまり偶数であるので、アドレス制御手段１１０は図５（２）に示すように、偶数アドレス用バンクのアドレス「０」に割り当てる。この場合、第３の状態確率計算手段１０５で計算される時点「３９」の前方確率は、図５（３）に示すように、奇数アドレス用バンクのアドレス「３」に割り当てる。
【００９８】
図５（２）（３）に示すように、適切にバンク分けした記憶領域に、アクセスアドレスの下位ビットに従って割り当てることで、偶数同士、奇数同士で発生する読み出しと書き込みの競合を回避することができる。
【００９９】
このように、本実施の形態２によれば、２つの状態確率記憶手段へのアクセスアドレスが昇順列又は降順列で発生する場合においても、読み出しと書き込みの競合を回避することが可能となり、シングル・ポート・メモリを用いた実装が可能となる。ウインドウ幅が実施の形態１よりも増加することになるが、復号処理に影響を与えない。
【０１００】
（実施の形態３）
図６は、本発明の実施の形態３に係るターボ復号装置における第１及び第２の状態確率記憶手段１０７、１０８へのアクセスタイミングを説明するタイムチャートである。図６（１）は一連の処理動作を説明するタイムチャート、図６（２）は第２の状態確率記憶手段１０８へのアクセスタイミングを説明するタイムチャート、図６（３）は第１の状態確率記憶手段１０７へのアクセスタイミングを説明するタイムチャートである。
【０１０１】
また、図７は、本発明の実施の形態３に係るターボ復号装置における第１及び第２の状態確率記憶手段１０７、１０８の構成とアドレス制御手段の動作とを説明する図である。図７（１）は、図６（３）に示す第１の状態確率記憶手段１０７のアクセス内容を転記したものである。図７（２）（３）は、各状態確率記憶手段が備える記憶領域を構成する２つのバンクのアクセス内容を示す図である。
【０１０２】
本実施の形態３では、ウインドウ処理間の処理タイミングとして、状態確率記憶手段への読み出しと書き込みとを連続的に実行するのではなく、時間を置いて実行する場合について説明する。図６（１）では、読み出しが発生するタイミングから２時点遅れた時点で書き込みが開始される形態が示されている。この場合には、２つの状態確率記憶手段へのアクセス内容は、図６（２）（３）に示すようになる。
【０１０３】
本実施の形態３に示す処理形態でも、状態確率記憶手段での読み出し書き込みの競合は、実施の形態２と同様に、偶数同士、奇数同士のアドレスで発生する。但し、実施の形態２と異なり、本実施の形態３では、各状態確率記憶手段が備える記憶領域の幅は、実施の形態１と同様に、ウインドウ幅と同じ幅８にして構成することができる。
【０１０４】
つまり、アドレス制御手段１１０は、実施の形態１（図３）と同様に、その幅８の記憶領域を幅４の領域に２分して管理する。但し、本実施の形態３では、アドレス制御手段１１０は、第２の状態確率計算手段１０４で計算される奇数番目のデータと第３の状態確率計算手段１０５とで計算される偶数番目のデータとを同じバンク（図７（２））にアクセスされるように制御し、また第２の状態確率計算手段１０４で計算される偶数番目のデータと第３の状態確率計算手段１０５とで計算される奇数番目のデータとを同じバンク（図７（３））にアクセスされるように制御する。この場合も、アドレス制御手段１１０は、アドレスの最下位ビットによって判断することが可能である。
【０１０５】
このように、本実施の形態３によれば、状態確率記憶手段への読み出しと書き込みとが時間を置いて実行される場合においても、適切にバンク分けした記憶領域にアクセスアドレスの下位ビットに従って割り当てることで、偶数同士、奇数同士で発生する読み出しと書き込みの競合を回避することができるので、シングル・ポート・メモリを用いた実装が可能となる。ウインドウ処理間に遅延が生ずるが、その遅延量は復号処理に影響を与えない。
【産業上の利用可能性】
【０１０６】
本発明は、ターボ符号により誤り訂正符号化されたデータ列をＭＡＰ復号によって高速に復号するターボ復号装置をメモリ容量の増加を抑えつつシングル・ポート・メモリで構成するのに有用であり、特にＭＡＰ復号を高速かつ小規模回路で行うことを要求するシステム、例えば移動通信システムに好適である。
【図面の簡単な説明】
【０１０７】
【図１】本発明の実施の形態１に係るターボ復号装置の構成を示すブロック図
【図２】図１に示す第１及び第２の状態確率記憶手段へのアクセスタイミングを説明するタイムチャート
【図３】図１に示す第１及び第２の状態確率記憶手段の構成と図１に示すアドレス制御手段の動作とを説明する図
【図４】本発明の実施の形態２に係るターボ復号装置における第１及び第２の状態確率記憶手段へのアクセスタイミングを説明するタイムチャート
【図５】本発明の実施の形態２に係るターボ復号装置における第１及び第２の状態確率記憶手段の構成とアドレス制御手段の動作とを説明する図
【図６】本発明の実施の形態３に係るターボ復号装置における第１及び第２の状態確率記憶手段へのアクセスタイミングを説明するタイムチャート
【図７】本発明の実施の形態３に係るターボ復号装置における第１及び第２の状態確率記憶手段の構成とアドレス制御手段の動作とを説明する図
【図８】スライディング・ウインドウ・アルゴリズムを実現する従来のターボ復号装置の構成例を示すブロック図
【図９】ウインドウ処理を所定の復号回数繰り返すデータ範囲を２つに等分割し、各データ範囲においてウインドウ処理を並列に実行する従来のターボ復号装置の構成例を示すブロック図
【図１０】図９に示す第１及び第２の状態確率記憶手段へのアクセスタイミングを説明するタイムチャート
【図１１】図１０に示すＭＡＰ復号の更なる高速化を従来技術によって図る場合の一例を示す図
【符号の説明】
【０１０８】
１００  ターボ復号装置
１０１  入力データ記憶手段
１０２  遷移確率計算手段
１０３  第１の状態確率計算手段
１０４  第２の状態確率計算手段
１０５  第３の状態確率計算手段
１０６  第４の状態確率計算手段
１０７  第１の状態確率記憶手段
１０８  第２の状態確率記憶手段
１０９  メモリ選択手段
１１０  アドレス制御手段
１１１  第１の対数尤度計算手段
１１２  第２の対数尤度計算手段
１１３  外部値計算手段
１１４  外部値記憶手段
１１５  出力データ記憶手段
【図１】
2006217072.tif 000003
【図２】
2006217072.tif 000004
【図３】
2006217072.tif 000005
【図４】
2006217072.tif 000006
【図５】
2006217072.tif 000007
【図６】
2006217072.tif 000008
【図７】
2006217072.tif 000009
【図８】
2006217072.tif 000010
【図９】
2006217072.tif 000011
【図１０】
2006217072.tif 000012
【図１１】
2006217072.tif 000013