(57)【特許請求の範囲】
【請求項１】
入力データについてその先頭から終端に向けトレリスを用いて前方確率の演算を行う前方確率演算手段（１１）と、
前記前方確率の演算と並行して、前記入力データについてその終端から先頭に向けトレリスを用いて後方確率の演算を行う後方確率演算手段（１２）と、
前記後方確率の演算結果を記憶する記憶手段（１４）と、
前記前方確率の演算結果と前記記憶手段（１４）に記憶された後方確率の演算結果から結合確率の演算を行う結合確率演算手段（１３）とを備え、
前記前方確率の演算と前記後方確率の演算が前記トレリスの中間まで行われると、前記結合確率演算手段（１３）は、前記記憶手段（１４）から前記前方確率の演算を行っている位置に相当するトレリス位置における後方確率の演算結果を読み出し、読み出した後方確率の演算結果と前記前方確率の演算結果から結合確率の演算を行い、
前記前方確率の演算と前記結合確率の演算が前記トレリスの終端まで行われると、前記トレリスの先端から前記トレリスの中間まで、前記前方確率演算手段（１１）は前記前方確率の演算を行い、前記結合確率手段は、前記記憶手段（１４）から前記前方確率の演算を行っている位置に相当するトレリス位置における後方確率の演算結果を読み出し、読み出した後方確率の演算結果と前記前方確率の演算結果から結合確率の演算を行うことを特徴とするＭＡＰ復号装置。
【請求項２】
前記前方確率の演算と前記後方確率の演算が前記トレリスの中間まで行われた後は、前記後方確率の演算結果が、前記記憶手段（１４）において前記結合確率の演算のために読み出された前記後方確率の演算結果の記憶位置に書き込まれることを特徴とする請求項１に記載のＭＡＰ復号装置。
【請求項３】
入力データについてその先頭から終端に向けトレリスを用いて前方確率の演算を行う前方確率演算手段（１１）と、
前記前方確率の演算と並行して、前記入力データについてその終端から先頭に向けトレリスを用いて後方確率の演算を行う第１の後方確率演算手段（１２ａ）と、
トレリス長を複数に分割しその分割したトレリス位置の前記後方確率の演算結果を記憶する記憶手段（１４）と、
前記前方確率の演算結果と前記記憶手段（１４）に記憶された後方確率の演算結果から結合確率の演算を行う結合確率演算手段（１３）と、
前記分割した区間について前記後方確率の演算を行う第２の後方確率演算手段（１２ｂ）とを備え、
前記前方確率の演算と前記後方確率の演算が前記トレリスの中間まで行われると、前記結合確率演算手段（１３）は、前記記憶手段（１４）から前記前方確率の演算を行っている位置に相当するトレリス位置における後方確率の演算結果を読み出し、読み出した後方確率の演算結果と前記前方確率の演算結果から結合確率の演算を行い、これと並行して、前記第２の後方確率演算手段（１２ｂ）は、前記結合確率演算手段（１３）が前記結合確率の演算を行っている分割区間の次の分割区間について前記後方確率の演算を行いその演算結果を前記記憶手段（１４）の所定の記憶領域に上書きして書き込むようにし、
前記前方確率の演算と前記結合確率の演算が前記トレリスの終端まで行われると、前記トレリスの先端から前記トレリスの中間まで、前記前方確率演算手段（１１）は前記前方確率の演算を行い、前記結合確率手段は、前記記憶手段（１４）から前記前方確率の演算を行っている位置に相当するトレリス位置における後方確率の演算結果を読み出し、読み出した後方確率の演算結果と前記前方確率の演算結果から結合確率の演算を行い、これと並行して、前記第２の後方確率演算手段（１２ｂ）は、前記結合確率演算手段（１３）が前記結合確率の演算を行っている分割区間の次の分割区間について前記後方確率の演算を行いその演算結果を前記記憶手段（１４）の所定領域に上書きして書き込むことを特徴とするＭＡＰ復号装置。
【請求項４】
前記前方確率の演算と前記後方確率の演算が前記トレリスの中間まで行われた後は、それまでに前記第１の後方確率演算手段（１２ａ）の演算結果を記憶していた前記記憶手段（１４）の記憶位置に、前記第１、第２の後方確率演算手段（１２ａ、１２ｂ）のそれぞれの演算結果が上書きして書き込まれることを特徴とする請求項３に記載のＭＡＰ復号装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ターボデコーダ等に用いることができるＭＡＰ復号装置に関する。
【０００２】
【従来の技術】
従来、畳込み符号とインタリーブとを組合せたターボ符号に変換して送信された符号化データを受信し、その誤りを訂正して復号を行うターボデコーダが提案されている。
【０００３】
このターボデコーダに用いられる復号方式としては、ＭＡＰ（最大事後確率：Maximum A Posteriori Probabi1ity）復号方式が知られている。図１６に従来のＭＡＰ復号装置の構成を示す。
【０００４】
受信データ（ターボ符号化されているデータ）をメモリ（図示せず）に記憶したデータが入力データとしてＭＡＰ復号装置に入力される。前方確率演算器５１は、メモリに記憶された入力データについて、トレリスを用いて先頭ビットから最終ビットに向け順に前方確率を演算する。その演算結果は、第１のメモリ５４に記憶される。トレリスとは、送信側でターボ符号化する際にどのような畳み込みをしたかによって形が決まるもので、状態（例えば３つのシフトレジスタを用いて畳み込みを行っていれば８つの状態となる）とその状態間を結ぶ枝で構成されている。また、後方確率演算器５２は、メモリに記憶された入力データについて、最終ビットから先頭ビットに向け順に後方確率を演算する。その演算結果は、第２のメモリ５５に記憶される。
【０００５】
前方確率演算器５１、後方確率演算器５２が全ての演算を終了すると、結合確率演算器５３は、第１、第２のメモリ５４、５５に記憶された前方確率演算器５１の演算結果、後方確率演算器５２の演算結果から結合確率の演算を行う。その演算結果は、復号結果として出力される。なお、結合確率演算器５３の演算結果は、元のデータが“１”である確率と、“０”である確率をアナログ的に示すものである。この演算結果を基に、図示しない硬判定（元のデータが“１”である確率と、“０”である確率のどちらが大きいかの判定）を行って、元のデータを示す情報（例えば、“１”である確率が大きい場合は＋の符号のデータ、“０”である確率が大きい場合は−の符号のデータ）が順に得られる。
【０００６】
上記した従来のＭＡＰ復号装置では、前方確率演算器５１、後方確率演算器５２の演算結果を記憶するメモリ容量が大きくなるという問題がある。そこで、メモリ容量を少なくするために、９９年６月の信学技報に記載された“Turbo符号におけるSub-log-MAPの回路規模削減方式”が提案されている。このものによれば、以下のようなＭＡＰ復号が行われる。
【０００７】
図１７にその原理説明図、図１８にタイムチャートを示す。情報長（トレリス長）ＮをＬずつのブロックに分割し、Ｌを基本単位として復号を行う。ここでは、情報の先頭ビットを０、最終ビットをＮとし、その間をＬ毎にＬ1、Ｌ2、Ｌ3…とする。
▲１▼  Ｎから０へ後方確率演算を行う。このときＬごとに…、Ｌ3、Ｌ2の各状態の後方確率の演算結果をメモリに書き込み、Ｌ1から０までの全ての時間及び各状態の後方確率演算結果をメモリに書き込む。
▲２▼  ０からＬ1まで前方確率演算を行う。これと同時に後方確率演算結果を読み出し両者により結合確率演算を行う。
▲３▼  ▲２▼と同時にＬ2の後方確率演算結果を読み出し、これを初期値としてＬ2からＬ1まで後方確率演算を行う。▲２▼と▲３▼は別々の演算回路で同時に行う。
▲４▼  Ｌ1からＬ2まで前方確率演算を行う。これと同時に後方確率演算結果を読み出し両者により結合確率演算を行う。
▲５▼  ▲４▼と同時にＬ3の後方確率演算結果を読み出し、これを初期値としてＬ3からＬ2まで後方確率演算を行う。▲４▼と▲５▼も別々の演算回路で同時に行う。
以後、上記と同様の演算を繰り返し、Ｎまで復号結果を出力する。
【０００８】
このようなＭＡＰ復号を行うことにより、図１６に示すＭＡＰ復号装置に比べて、前方確率演算器５１の演算結果を記憶するメモリを無くし、後方確率演算器５２の演算結果を記憶するメモリ５５の容量を削減することができる。
【０００９】
【発明が解決しようとする課題】
しかしながら、図１６に示すＭＡＰ復号装置および上記した論文に記載されたＭＡＰ復号装置のいずれにおいても、トレリスを片側（先頭ビットから最終ビットまであるいは最終ビットから先頭ビットまで）演算する時間を１としたとき、２の演算時間が必要となる。これは、先に後方確率演算をトレリス全体に対して行い、その演算結果をメモリに格納し、次に前方確率演算と統合確率演算をトレリス全体にするためである。このことにより、データが入力されてから初めて復号結果が出力されるまでにディレイ時間が生じる。このディレイ時間は、ターボデコーダを内包するシステムにおいては、データ処理に付加される遅延時間に相当する。
【００１０】
本発明は上記問題に鑑みたもので、ＭＡＰ復号に要する時間を短くすることを目的とする。また、ＭＡＰ復号に要する時間を短くするとともに、演算結果の記憶容量を少なくすることを目的とする。
【００１１】
【課題を解決するための手段】
上記目的を達成するため、請求項１に記載の発明では、入力データについてその先頭から終端に向けトレリスを用いて前方確率の演算を行う前方確率演算手段（１１）と、
前記前方確率の演算と並行して、前記入力データについてその終端から先頭に向けトレリスを用いて後方確率の演算を行う後方確率演算手段（１２）と、
前記後方確率の演算結果を記憶する記憶手段（１４）と、
前記前方確率の演算結果と前記記憶手段（１４）に記憶された後方確率の演算結果から結合確率の演算を行う結合確率演算手段（１３）とを備え、
前記前方確率の演算と前記後方確率の演算が前記トレリスの中間まで行われると、前記結合確率演算手段（１３）は、前記記憶手段（１４）から前記前方確率の演算を行っている位置に相当するトレリス位置における後方確率の演算結果を読み出し、読み出した後方確率の演算結果と前記前方確率の演算結果から結合確率の演算を行い、
前記前方確率の演算と前記結合確率の演算が前記トレリスの終端まで行われると、前記トレリスの先端から前記トレリスの中間まで、前記前方確率演算手段（１１）は前記前方確率の演算を行い、前記結合確率手段は、前記記憶手段（１４）から前記前方確率の演算を行っている位置に相当するトレリス位置における後方確率の演算結果を読み出し、読み出した後方確率の演算結果と前記前方確率の演算結果から結合確率の演算を行うことを特徴としている。
【００１２】
この発明によれば、トレリスの片側演算時間を１としたとき、１．５の演算時間でＭＡＰ復号が終了することになるため、ＭＡＰ復号に要する時間を短くすることができる。
【００１３】
この場合、請求項２に記載の発明のように、前記前方確率の演算と前記後方確率の演算が前記トレリスの中間まで行われた後に、前記後方確率の演算結果が、前記記憶手段（１４）において前記結合確率の演算のために読み出された前記後方確率の演算結果の記憶位置に書き込むようにすれば、演算結果の記憶容量を少なくすることができる。
【００１４】
請求項３に記載の発明では、入力データについてその先頭から終端に向けトレリスを用いて前方確率の演算を行う前方確率演算手段（１１）と、
前記前方確率の演算と並行して、前記入力データについてその終端から先頭に向けトレリスを用いて後方確率の演算を行う第１の後方確率演算手段（１２ａ）と、
トレリス長を複数に分割しその分割したトレリス位置の前記後方確率の演算結果を記憶する記憶手段（１４）と、
前記前方確率の演算結果と前記記憶手段（１４）に記憶された後方確率の演算結果から結合確率の演算を行う結合確率演算手段（１３）と、
前記分割した区間について前記後方確率の演算を行う第２の後方確率演算手段（１２ｂ）とを備え、
前記前方確率の演算と前記後方確率の演算が前記トレリスの中間まで行われると、前記結合確率演算手段（１３）は、前記記憶手段（１４）から前記前方確率の演算を行っている位置に相当するトレリス位置における後方確率の演算結果を読み出し、読み出した後方確率の演算結果と前記前方確率の演算結果から結合確率の演算を行い、これと並行して、前記第２の後方確率演算手段（１２ｂ）は、前記結合確率演算手段（１３）が前記結合確率の演算を行っている分割区間の次の分割区間について前記後方確率の演算を行いその演算結果を前記記憶手段（１４）記憶手段（１４）の所定の記憶領域に上書きして書き込むようにし、
前記前方確率の演算と前記結合確率の演算が前記トレリスの終端まで行われると、前記トレリスの先端から前記トレリスの中間まで、前記前方確率演算手段（１１）は前記前方確率の演算を行い、前記結合確率手段は、前記記憶手段（１４）から前記前方確率の演算を行っている位置に相当するトレリス位置における後方確率の演算結果を読み出し、読み出した後方確率の演算結果と前記前方確率の演算結果から結合確率の演算を行い、これと並行して、前記第２の後方確率演算手段（１２ｂ）は、前記結合確率演算手段（１３）が前記結合確率の演算を行っている分割区間の次の分割区間について前記後方確率の演算を行いその演算結果を前記記憶手段（１４）の所定の記憶領域に上書きして書き込むことを特徴としている。
【００１５】
この発明によれば、請求項１に記載の発明と同様、ＭＡＰ復号に要する時間を短くすることができるとともに、トレリス長を複数に分割しその分割したトレリス位置の後方確率の演算結果を記憶するようにしているから、後方確率の演算結果を全て記憶するものに比べて記憶容量を少なくすることができる。
【００１６】
この場合、請求項４に記載の発明のように、前記前方確率の演算と前記後方確率の演算が前記トレリスの中間まで行われた後に、それまでに前記第１の後方確率演算手段（１２ａ）の演算結果を記憶していた前記記憶手段（１４）の記憶位置に、前記第１、第２の後方確率演算手段（１２ａ、１２ｂ）のそれぞれの演算結果を上書きして書き込むようにすれば、演算結果の記憶容量をさらに少なくすることができる。
【００１７】
なお、上記各手段の括弧内の符号は、後述する実施形態に記載の具体的手段との対応関係を示すものである。
【００１８】
【発明の実施の形態】
（第１実施形態）
図１に本発明の第１実施形態に係るＭＡＰ復号装置の構成を示し、図２にその復号原理を示す。
【００１９】
このＭＡＰ復号装置には、受信データ（ターボ符号化されているデータ）をメモリ（図示せず）に記憶したデータが入力データとして入力される。前方確率演算器１１は、入力データについて、トレリスを用い、前方確率演算（演算αという）を行う。これと同時に（並行して）、後方確率演算器１２は、後方確率演算（演算βという）を行う。後方確率演算器１２の演算結果Dat#bは、メモリ１４に記憶される。この場合、後方確率演算器１２は、最終ビットから先頭ビットに向けて演算βを行うので、その演算結果Dat#bは、例えば図３に示すようにアドレスの若い順に記憶される。
【００２０】
前方確率演算器１１の演算αと後方確率演算器１２の演算βがトレリスの中間まで行われると、この後、前方確率演算器１１は演算αを行い、また結合確率演算器１３は、メモリ１４から、前方確率演算器１１が演算αを行っている位置に相当するビット位置（一般には１ビット後方の位置）における後方確率演算器１２の演算結果Dat#bを読み出し、結合確率演算（演算λという）を行う。また、これと同時に、後方確率演算器１２は演算βを継続し、その演算結果Dat#bを、先に演算λをする際にメモリ１４から読み出した後方確率演算器１２の演算結果Dat#bの記憶位置（アドレス位置）に上書きして格納する。
【００２１】
前方確率演算器１１の演算αと結合確率演算器１３の演算λがトレリスの終端まで行われると、トレリスの先端へ戻り、前方確率演算器１１は演算αを行い、また結合確率演算器１３は、メモリ１４から、前方確率演算器１１が演算αを行っている位置に相当するビット位置における後方確率演算器１２の演算結果Dat#bを読み出し、演算λを行って復号結果を出力する。そして、前方確率演算器１１の演算αと結合確率演算器１３の演算λがトレリスの中間まで行われると、全てのビットについて演算λが行われたことになるため、ＭＡＰ復号を終了する。
【００２２】
この実施形態によれば、前方確率演算器１１の演算αトレリスの中間をすぎてから、結合確率演算器１３の演算λと復号結果の出力が開始される。また、トレリスの片側演算時間を１としたとき、１．５の演算時間でＭＡＰ復号が終了することになる。従って、従来のＭＡＰ復号装置では２の演算時間が必要であったのに対し、この実施形態ではその３／４の演算時間で済むことになる。
【００２３】
また、メモリ１４は、トレリスの中間までの後方確率演算器１２の演算結果Dat#bを記憶するだけでよいため、図１６に示すＭＡＰ復号装置に比べて、前方確率演算器１１の演算結果を記憶するメモリを無くし、後方確率演算器１２の演算結果Dat#bを記憶するメモリの容量をその半分に削減することができる。なお、メモリ１４の容量に余裕があれば、トレリスの全てに対して後方確率演算器１２の演算結果Dat#bを順に記憶させていくようにしてもよい。
【００２４】
上記した前方確率演算器１１、後方確率演算器１２において、演算を行う際のトレリスのビット位置は、ビット位置制御部１５で決定される。図４に、ビット位置制御部１５の一例を示す。
【００２５】
ビット位置制御部１５は、インクリメンタ１５１、減算器１５２、およびトレリス終端検知回路１５３で構成されている。インクリメンタ１５１は、初期値０からインクリメントを行って前方確率演算器１１が演算αを行う際のトレリスのビット位置Pos#aを出力する。減算器１５２は、トレリス長からPos#aを減じて後方確率演算器１２が演算βを行う際のトレリスのビット位置Pos#bを出力する。トレリス終端検知回路１５３は、Pos#bの値から、演算αと演算λの演算がトレリスの終端まで達したことを検知し、インクリメンタ１５１をリセットして、初期値０からインクリメントを行わせるようにする。
【００２６】
このことにより、Pos#aは、その初期値から順次増大していく値となり、Pos#bは、その初期値から順次減少していく値となる。また、トレリス長だけ演算αと演算λの演算が行われると、Pos#a、Pos#bをそれぞれの初期値から増大、減少させていく。従って、前方確率演算器１１は、Pos#aを用いて、先頭ビットから最終ビットに向けて演算αを行い、トレリス長分の演算が終了すると、再度先頭ビットから演算αを行うことになる。また、後方確率演算器１２は、Pos#bを用いて、最終ビットから先頭ビットに向けて演算βを行い、トレリス長分の演算が終了すると、再度最終ビットから演算βを行うことになる。なお、トレリス長分の演算が終了した後の演算βの結果は、演算λには必要ないので、トレリス長分の演算が終了した後は、演算βを行わないようにしてもよい。
【００２７】
また、上記したメモリ１４の書き込みおよび読み出しを行うためのアドレスは、メモリアドレスデコーダ１６で決定される。図５に、メモリアドレスデコーダ１６の一例を示す。このメモリアドレスデコーダ１６は、比較・選択器１６１で構成され、入力されるPos#aの値に基づいてアドレスAdr#bを出力する。すなわち、Pos#aがトレリス長の１／２以下のときは、Pos#aをアドレスAdr#bとして出力し、Pos#aがトレリス長の１／２より大きいときは、（トレリス長−Pos#a）をアドレスAdr#bとして出力する。
【００２８】
従って、Pos#aがトレリス長の１／２以下のときは、Pos#aをアドレスAdr#bとして、演算結果Dat#bがメモリ１４に記憶され、Pos#aがトレリス長の１／２より大きいときは、（トレリス長−Pos#a）をアドレスAdr#bとして、メモリ１４に記憶された後方確率演算器１２の演算結果Dat#bが読み出され、後方確率演算器１２の新たな演算結果Dat#bがメモリ１４に書き込まれる。また、トレリスの終端までの演算が終了し、Pos#aがリセットされた後は、Pos#aがトレリス長の１／２以下であるため、そのPos#aをアドレスAdr#bとして、メモリ１４に記憶された後方確率演算器１２の演算結果Dat#bが読み出され、後方確率演算器１２の新たな演算結果Dat#bがメモリ１４に書き込まれる。
【００２９】
なお、上記したＭＡＰ復号装置は、コンピュータを用いたソフトウエアで実現することもできる。この場合の処理を図６に示す。
【００３０】
まず、第１の処理として、トレリスのビット位置を演算し（ステップ１０１）、そのビット位置において演算αを行い（ステップ１０２）、トレリス長からビット位置を減算したビット位置の演算βを行い（ステップ１０３、１０４）、演算結果を演算αのビット位置をアドレスとするメモリ１４の記憶領域に書き込み（ステップ１０５）、ビット位置の判定を行う（ステップ１０６）。ビット位置がトレリス長の１／２より小さければ、上記した第１の処理を繰り返す。
【００３１】
また、ビット位置がトレリス長の１／２になっていると、第２の処理として、まずトレリスの次のビット位置を演算し（ステップ１０７）、そのビット位置において演算αを行い（ステップ１０８）、同ビット位置をアドレスとするメモリ１４の記憶領域から演算βの結果を読み出し（ステップ１０９）、先の演算αの演算結果と読み出した演算βの結果から演算λを行い（ステップ１１０）、復号結果として出力する。また、演算αに並行して、トレリス長からビット位置を減算したビット位置の演算βを行い（ステップ１１１、１１２）、演算結果を、トレリス長からビット位置を減算したビット位置をアドレスとするメモリ１４の記憶領域に書き込み（ステップ１１３）、ビット位置の判定を行う（ステップ１１４）。ビット位置がトレリス長より小さければ、上記した第２の処理を繰り返す。
【００３２】
また、ビット位置がトレリス長になっていると、第３の処理として、まずビット位置をリセットし（ステップ１１５）、トレリスの次のビット位置を演算し（ステップ１１６）、そのビット位置において演算αを行い（ステップ１１７）、同ビット位置をアドレスとするメモリ１４から演算βの結果を読み出し（ステップ１１８）、先の演算αの演算結果と読み出した演算βの結果から演算λを行い（ステップ１１９）、復号結果として出力する。その後、ビット位置の判定を行う（ステップ１２０）。ビット位置がトレリス長の１／２より小さければ、上記した第３の処理を繰り返す。そして、ビット位置がトレリス長の１／２になっていると、処理を終了する。
【００３３】
なお、上記した実施形態では、結合確率演算器１３で演算λを行うためにメモリ１４から後方確率演算器１２の演算結果Dat#bを読み出し、その読み出したアドレス位置に、後方確率演算器１２の新たな演算結果Dat#bを書き込むようにしている。この場合、その読み出しと書き込みを、タイミングをずらして対応することになるが、図７に示すように、デュアルポートＲＡＭ１４１を使用すれば、読み書きのアクセスを同時に行うことができる。この場合、書き込み用のアドレスAdr#b#wを用いて後方確率演算器１２の演算結果Dat#bがデュアルポートＲＡＭに書き込まれ、読み出し用のアドレスAdr#b#rを用いてデュアルポートＲＡＭから後方確率演算器１２の演算結果Dat#bが読み出される。
（第２実施形態）
図８に本発明の第２実施形態に係るＭＡＰ復号装置の構成を示し、図９にその復号原理を示す。この実施形態は、上記した第１実施形態のＭＡＰ復号装置に、図１７、図１８に示すＬビット間隔で後方確率演算器１２の演算結果を記憶してＭＡＰ復号を行うように構成したものである。
【００３４】
すなわち、この実施形態では、トレリス長をＬずつのブロック（区間）に分割し、Ｌを基本単位として復号を行う。 前方確率演算器１１は、入力データについて、トレリスを用い、演算αを行う。これと同時に、第１の後方確率演算器１２ａは、後方確率演算（演算βＡという）を行う。第１の後方確率演算器１２ａは、その演算結果Dat#bを、ＬN、ＬN-1、…（図９参照）のようにＬビット間隔でメモリ１４に書き込む。この場合、第１の後方確率演算器１２ａは、最終ビットから先頭ビットに向けて演算を行うので、その演算結果Dat#bは、例えば図１０に示すようにアドレスの若い順にＬビットごとに記憶される。但し、トレリスの中間の手前Ｌビット（図９のＬN/2〜ＬN/2+1−１）については、第１の後方確率演算器１２ａは、演算結果Dat#bの全てをメモリ１４に書き込む。また、第１の後方確率演算器１２ａは、トレリスの先頭の手前Ｌビット（図９の０〜Ｌ1）についても、演算結果Dat#bの全てをメモリ１４に書き込むようにする。
【００３５】
前方確率演算器１１の演算αと第１の後方確率演算器１２ａの演算βＡがトレリスの中間まで行われると、前方確率演算器１１は演算αを行い、また結合確率演算器１３は、メモリ１４から、前方確率演算器１１が演算αを行っているビット位置に対応したビット位置の後方確率の演算結果Dat#bを読み出し、演算λを行う。
【００３６】
また、演算αと演算λと並行して、第２の後方確率演算器１２ｂは、結合確率演算器１３が次のＬ区間において演算λをするに必要な演算結果Dat#bを用意するため、後方確率演算（演算βＢという）を行い、その演算結果Dat#bをメモリに書き込む。すなわち、第２の後方確率演算器１２ｂは、前方確率演算器１１が図９のＬN/2〜ＬN/2+1−１について演算αを行うときには、ＬN/2+2の演算結果Dat#bを読み出し、これを初期値としてＬN/2+2−１からＬN/2+1まで演算βＢを行い、その演算結果Dat#bをメモリ１４に書き込み、また前方確率演算器１１が図９のＬN/2+1〜ＬN/2+2−１について演算αを行うときには、ＬN/2+3の演算結果Dat#bを読み出し、これを初期値としてＬN/2+3−１からＬN/2+2まで演算βＢを行い、その演算結果Dat#bをメモリ１４に書き込む。以後、このような処理を、トレリスの終端まで行う。
【００３７】
また、演算α、演算λ、演算βＢと並行して、第１の後方確率演算器１２ａはその演算βＡを継続し、その演算結果Dat#bをメモリ１４に書き込む。
【００３８】
前方確率演算器１１の演算αと結合確率演算器１３の演算λがトレリスの終端まで行われると、トレリスの先端へ戻り、上記したトレリスの中間からトレリスの終端までにおける処理と同様の処理を、トレリスの中間まで行う。
【００３９】
すなわち、前方確率演算器１１は演算αを行い、また結合確率演算器１３は、前方確率演算器１１が演算αを行っているビット位置に対応したビット位置の後方確率の演算結果Dat#bを読み出し、演算λを行う。また、これと同時に、第２の後方確率演算器１２ｂは、結合確率演算器１３が次のＬ区間において演算λをするに必要な演算結果Dat#bを用意するため、演算βＢを行ってその結果をメモリ１４に書き込む。また、これらと同時に、第１の後方確率演算器１２ａはその演算βＡを継続し、その演算結果Dat#bを、Ｌビット間隔でメモリ１４に書き込む。なお、トレリスの先端へ戻った後の演算βＡは、演算λには必要ないので、なくてもよい。
【００４０】
そして、前方確率演算器１１の演算αと結合確率演算器１３の演算λがトレリスの中間まで行われると、全てのビットについて演算λが行われたことになるため、ＭＡＰ復号を終了する。
【００４１】
このようにトレリス長をＬずつのブロックに分割し、Ｌを基本単位として復号を行うことにより、第１実施形態よりも、メモリ１４の容量を少なくすることができる。
【００４２】
ここで、演算βＡ、演算βＢの演算結果Dat#bをメモリ１４に書き込む方法について説明する。演算α、演算βＡがトレリスの中間まで行われると、演算βＡの演算結果Dat#bは、図１０に示すようにＬビットごとにメモリ１４に書き込まれ、トレリスの中間の手前Ｌビット（ＬN/2〜ＬN/2+1−１）についてはメモリ１４のｍ1、ｍ2…の記憶領域に書き込まれる。そして、演算α、演算βＡがトレリスの中間を超えた最初の時点においては、ｍ1、ｍ2…の記憶領域に記憶されたDat#bを用いて演算λが順に行われ、また演算βＢをするために次のＬ区間（ＬN/2+2〜ＬN/2+1）の最初のビット位置の演算結果Dat#bがＭ１の記憶領域から読み出され、それを初期値として演算βＢが行われ、その演算結果が演算λを行うために先に読み出されたｍ1、ｍ2…の記憶領域に順に書き込まれる。また、演算βＡの演算結果Dat#bはＭ１の記憶領域に書き込まれる。以後、同様の処理を繰り返すことにより、演算βＡ、演算βＢの演算結果Dat#bがメモリ１４に順に書き込まれる。なお、トレリスの先頭の手前Ｌビットについては、演算βＡの演算結果Dat#bがＬビットの記憶領域ｍ1、ｍ2…にそのまま記憶される。このような書き込みを行うようにすれば、メモリ１４の容量を第１実施形態のものより、１／Ｌ＋Ｌビット分とすることができ、メモリ容量を大幅に削減することができる。
【００４３】
図１１に、この実施形態におけるビット位置制御部１５の構成を示す。ビット位置制御部１５は、インクリメンタ１５１、減算器１５２、トレリス終端検知回路１５３、加算器１５４、およびデクリメンタ１５５で構成されている。インクリメンタ１５１は、初期値０からインクリメントを行って前方確率演算器１１が演算を行う際のトレリスのビット位置Pos#aを出力する。減算器１５２は、トレリス長からPos#aを減じて第１の後方確率演算器１２ａが演算を行う際のトレリスのビット位置Pos#bを出力する。トレリス終端検知回路１５３は、Pos#bの値から、演算αと演算λの演算がトレリスの終端まで達したことを検知し、インクリメンタ１５１をリセットし、初期値０からインクリメントを行わせるようにする。加算器１５４は、Pos#aの値がトレリスの中間になった以後において、Ｌビット毎にPos#aに２Ｌビットを加算した値（演算βＢをする次の分割区間の最初の位置を示す値）を出力する処理を行い、Ｌビット毎に更新された（Pos#a＋２Ｌビット）の値を出力する。デクリメンタ１５５は、加算器１５４の出力をデクリメントして第２の後方確率演算器１２ｂのビット位置Pos#bbを出力する。
【００４４】
このようにすれば、Pos#bbに基づき、第２の後方確率演算器１２ｂは、結合確率演算器１３が次のＬ区間において演算λをするに必要なDat#bを順次演算することができる。
【００４５】
なお、上記したＭＡＰ復号装置は、コンピュータを用いたソフトウエアで実現することもできる。この場合の処理を図１２、図１３に示す。
【００４６】
まず、第１の処理として、トレリスのビット位置を演算し（ステップ２０１）、そのビット位置において演算αを行い（ステップ２０２）、トレリス長からビット位置を減算したビット位置の演算βＡを行い（ステップ２０３、２０４）、書き込み判定を行う（ステップ２０５）。書き込み可の場合は、演算結果を、図１０に示すように、初期値ゼロから順にインクリメントした値をアドレスとするメモリ１４の記憶領域に書き込む（ステップ２０６）。上記した書き込み判定は、Ｌビット毎に１回初めに書き込み可となり、また、ビット位置がトレリス長の１／２よりＬ小さい値になった以後は、常に書き込み可になるように判定する。この後、ビット位置の判定を行う（ステップ２０７）。ビット位置がトレリス長の１／２より小さければ、上記した第１の処理を繰り返す。
【００４７】
また、ビット位置がトレリス長の１／２になっていると、第２の処理として、トレリスの次のビット位置を演算し（ステップ２０８）、そのビット位置において演算αを行い（ステップ２０９）、同ビット位置に対応する演算βＡ（もしくは演算βＢ）の結果をメモリ１４から読み出し（ステップ２１０）、先の演算αの演算結果と読み出した演算βＡ（もしくは演算βＢ）の結果から演算λを行い（ステップ２１１）、復号結果として出力する。
【００４８】
また、演算αに並行して、演算βＢのビット位置を演算して求める、すなわちＬビット毎にそのときのトレリスのビット位置を初期値として、それに２Ｌビット加算した値からビット位置を減算（デクリメント）して求める（ステップ２１２）。そして、上記の初期値とされたビット位置の後方確率βＡの演算結果Dat#bをメモリ１４から読み出し、これを初期値としてそれぞれのビット位置において演算βＢを行い（ステップ２１３）、その演算結果をメモリ１４に書き込む（ステップ２１４）。
【００４９】
また、演算αと演算βＢに並行して、トレリス長からビット位置を減算したビット位置の演算βを行い（ステップ２１５、２１６）、書き込み判定を行う（ステップ２１７）。書き込み可の場合は、演算結果をメモリ１４に書き込む（ステップ２１８）。上記した書き込み判定は、Ｌビット毎に１回初めに書き込み可となり、また、ビット位置がトレリス長よりＬ小さい値になった以後は、常に書き込み可になるように判定する。なお、演算βＢと演算βＡの書き込みが同時に発生した場合は、タイミングをずらしてそれぞれをメモリ１４に書き込むようにする。次に、ビット位置の判定を行う（ステップ２１９）。ビット位置がトレリス長より小さければ、上記した第２の処理を繰り返す。
【００５０】
また、ビット位置がトレリス長になっていると、第３の処理として、まずビット位置をリセットし（ステップ２２０）、トレリスの次のビット位置を演算し（ステップ２２１）、このビット位置に対応する演算βＡ（もしくは演算βＢ）の結果をメモリ１４から読み出し（ステップ２２３）、先の演算αの演算結果と読み出した演算βＡ（もしくは演算βＢ）の結果から演算λを行い（ステップ２２４）、復号結果として出力する。
【００５１】
また、演算αに並行して、演算βＢのビット位置を求め（ステップ２２５）、ステップ２１３と同様にそのビット位置において演算βＢを行い（ステップ２２６）、その演算結果をメモリ１４に書き込む（ステップ２２７）。その後、ビット位置の判定を行う（ステップ２２８）。ビット位置がトレリス長の１／２より小さければ、上記した第３の処理を繰り返す。そして、ビット位置がトレリス長の１／２になっていると、処理を終了する。
【００５２】
なお、この第２実施形態においても、メモリ１４としては、図７と同様、図１４に示すようにデュアルポートＲＡＭ１４１を使用し、第１、第２の後方確率演算器１２ａ、１２ｂの演算結果の書き込み用のアドレスAdr#b#w、Adr#bb#wと、第１、第２の後方確率演算器１２ａ、１２ｂの演算結果の読み出し用のアドレスAdr#b#r、Adr#bb#rを用いて、読み書きのアクセスを同時に行うようにしてもよい。
【００５３】
また、この第２実施形態において、Ｌビット間隔で後方確率演算器１２の演算結果を記憶してＭＡＰ復号を行うものを示したが、Ｌを２とすれば、演算部βＡの書き込み判定および演算βＢのビット位置の特定を容易に行うことができる。この場合の復号原理を図１５に示す。図に示すように、演算βＡの演算結果は、２ビット毎に１回書き込みを行うように書き込み判定されて、メモリ１４に書き込まれる。また、演算βＡも２ビット毎に１回演算されてメモリ１４に書き込まれる。従って、デジタル処理する場合にそれらの処理を容易に行うことができる。
【００５４】
なお、上記した各実施形態において、図１、図８に示される演算器等の各構成要素、および図６、図１２、図１３における各ステップの処理は、それぞれの機能を実現するための手段として把握され、またメモリ１４、デュアルポートＲＡＭ１４１は、記憶手段として把握される。
【図面の簡単な説明】
【図１】本発明の第１実施形態に係るＭＡＰ復号装置の構成を示す図である。
【図２】本発明の第１実施形態におけるＭＡＰ復号の原理を示す図である。
【図３】本発明の第１実施形態においてメモリに後方確率の演算結果を記憶する状態を説明するための図である。
【図４】図１中のビット位置制御部の構成を示す図である。
【図５】図１中のメモリアドレスデコーダの構成を示す図である。
【図６】本発明の第１実施形態に係るＭＡＰ復号装置をソフトウエアで実現した場合の処理を示すフローチャートである。
【図７】本発明の第１実施形態においてメモリとしてデュアルポートＲＡＭを使用した場合のＭＡＰ復号装置の構成を示す図である。
【図８】本発明の第２実施形態に係るＭＡＰ復号装置の構成を示す図である。
【図９】本発明の第２実施形態におけるＭＡＰ復号の原理を示す図である。
【図１０】本発明の第２実施形態においてメモリに後方確率の演算結果を記憶する状態を説明するための図である。
【図１１】図８中のビット位置制御部の構成を示す図である。
【図１２】本発明の第２実施形態に係るＭＡＰ復号装置をソフトウエアで実現した場合の処理を示すフローチャートである。
【図１３】図１２に続く処理を示すフローチャートである。
【図１４】本発明の第２実施形態においてメモリとしてデュアルポートＲＡＭを使用した場合のＭＡＰ復号装置の構成を示す図である。
【図１５】本発明の第２実施形態の変形例におけるＭＡＰ復号の原理を示す図である。
【図１６】従来のＭＡＰ復号装置の構成を示す図である。
【図１７】従来の他のＭＡＰ復号の原理を説明するための図である。
【図１８】図１７に示すＭＡＰ復号のタイムチャートである。
【符号の説明】
１１…前方確率演算器、１２…後方確率演算器、１３…結合確率演算器、
１４…メモリ、１５…ビット位置制御部、１６…メモリアドレスデコーダ、
１２ａ…第１の後方確率演算器、１２ｂ…第２の後方確率演算器。
【図１】
0004366867.tif 000002
【図２】
0004366867.tif 000003
【図３】
0004366867.tif 000004
【図４】
0004366867.tif 000005
【図５】
0004366867.tif 000006
【図６】
0004366867.tif 000007
【図７】
0004366867.tif 000008
【図８】
0004366867.tif 000009
【図９】
0004366867.tif 000010
【図１０】
0004366867.tif 000011
【図１１】
0004366867.tif 000012
【図１２】
0004366867.tif 000013
【図１３】
0004366867.tif 000014
【図１４】
0004366867.tif 000015
【図１５】
0004366867.tif 000016
【図１６】
0004366867.tif 000017
【図１７】
0004366867.tif 000018
【図１８】
0004366867.tif 000019