(57)【要約】【課題】ビタビ復号におけるトレースバック処理の高速化を図る。【解決手段】ビタビ復号において、ＡＣＳ演算により求められた生き残りパスを示す選択パス情報を基にトレースバック処理を行う際、時刻Ｎの状態が状態Ａに確定すると、その時刻に対しｋ時刻前の時刻（Ｎ−ｋ）の状態のうち、時刻Ｎで状態Ａに遷移し得る時刻（Ｎ−ｋ）での２k個の状態の選択パス情報をパスメモリから読み出して処理を行うようにし、従来のトレースバック処理と比較して、メモリアクセスをより早い段階で行ってメモリアクセスレイテンシを隠蔽し、トレースバック処理を高速に実行できるようにする。【選択図】図４
2011124848.tif 000002
【特許請求の範囲】
【請求項１】
畳み込み符号化されたデータに基づいて、トレリス線図における生き残りパスを演算する演算部と、
前記演算部により求められた生き残りパスを示すパス情報が格納されるメモリ部と、
前記メモリ部に格納された前記パス情報に基づいて、前記トレリス線図における状態遷移をトレースバックして復号結果を出力するトレースバック部とを備え、
前記トレースバック部は、
時刻Ｎの状態が第１の状態に確定すると、前記時刻Ｎに対してｋ時刻前（ｋは所定の２以上の整数）の時刻（Ｎ−ｋ）の状態のうち、前記時刻Ｎで前記第１の状態に遷移し得る時刻（Ｎ−ｋ）での２k個の状態の前記パス情報を前記メモリ部から読み出して処理を行うことを特徴とするビタビ復号装置。
【請求項２】
前記トレースバック部は、
前記時刻Ｎの状態が前記第１の状態であることを示す情報を基に読み出しアドレスを生成して、前記時刻（Ｎ−ｋ）での２k個の状態の前記パス情報を前記メモリ部から読み出し、
読み出した前記時刻（Ｎ−ｋ）での２k個の状態の前記パス情報から、順次確定される時刻（Ｎ−１）から時刻（Ｎ−ｋ＋１）の各時刻の状態に応じて、当該状態に遷移し得る前記時刻（Ｎ−ｋ）の状態の前記パス情報を順次選択することを特徴とする請求項１記載のビタビ復号装置。
【請求項３】
前記時刻Ｎの状態が前記第１の状態であることを示す情報は、確定した時刻（Ｎ＋１）の状態の前記パス情報であることを特徴とする請求項１又は２記載のビタビ復号装置。
【請求項４】
前記トレースバック部は、１サイクル期間中に、連続する複数の時刻の状態を確定することを特徴とする請求項１〜３の何れか１項に記載のビタビ復号装置。
【請求項５】
前記トレースバック部は、
順次確定される時刻（Ｎ−１）から時刻（Ｎ−ｋ＋１）の各時刻の状態に応じて、当該状態に遷移し得る前記時刻（Ｎ−ｋ）の状態の前記パス情報を順次選択する複数の演算回路と、
前記演算回路により選択された前記パス情報を保持する複数のレジスタとを有することを特徴とする請求項１〜４の何れか１項に記載のビタビ復号装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ビタビ復号装置に関する。
【背景技術】
【０００２】
無線通信や有線通信により情報を伝送する通信システムにおいては、通信路の状態等により伝送された情報に誤りが発生することがある。正しく情報を伝送するために、情報を冗長化するとともに誤り訂正可能にする符号化方式の一つとして畳み込み符号化がある。また、畳み込み符号の復号法の一つとして、ビタビアルゴリズムに基づき復号するビタビ復号が知られている。例えば、送信側装置は、伝送データを畳み込み符号化し、その符号化データ（畳み込み符号）を伝送路に送出する。受信側装置は、伝送路を介して受信した符号化データ（畳み込み符号）についてビタビ復号を行って伝送データに復号する。
【０００３】
ビタビ復号では、受信データを用いてＡＣＳ（Add-Compare-Select）演算を行い、ＡＣＳ演算の結果に基づいてトレースバック処理を行うことで、伝送データが復号される。ＡＣＳ演算は、トレリス線図と呼ばれる状態遷移図を基にして、受信データに応じた状態遷移に係るパス（経路）の確からしさ（尤度）を求めていく。ＡＣＳ演算では、各状態について、前回演算での生き残りパスのパスメトリックを用いてパス毎にパスメトリックを計算し（Add）、パス毎のパスメトリックを比較し（Compare）、確からしい（尤度の高い）パスを生き残りパスとして選択する（Select）。
【０００４】
トレースバック処理は、ＡＣＳ演算によって選択された最尤パス（生き残りパス）を終端から遡ってエンコーダの状態遷移を順次確定していき、伝送データを求める。トレリス線図において各状態からは２つのパスが伸びている。そして、ＡＣＳ演算で求められた生き残りパスを示す情報が格納されるパスメモリには、各状態について、一時刻前の状態の取り得る候補のうち、どちらが尤度が高いかを示す１ビットの選択パス情報が格納されている。トレースバック処理では、パスメモリに格納されている時刻Ｎの状態の選択パス情報を取得することで、時刻（Ｎ−１）へのパスが確定し時刻（Ｎ−１）の状態が確定する。時刻を遡りながら、この動作を繰り返し行うことで伝送データが求められる。
【０００５】
また、ビタビ復号に関して、処理の効率等を改善するための様々な技術が提案されている。例えば、複数のＡＣＳ演算処理を並列に連続してパイプライン処理させることで、ＡＣＳ演算処理の効率を改善しビタビ復号処理の高速化を図るようにしたビタビ復号装置が提案されている（例えば、特許文献１参照。）。また、ＡＣＳ演算における比較演算と、ＡＣＳ演算により選択された生き残りパスを示す情報ビットのレジスタへの格納とを単一サイクルで実行可能にする技術が提案されている（例えば、特許文献２参照。）。パスメモリを複数個に分割し、トレースバック回路内のシフトレジスタの値をデコードしてチップセレクト信号を生成しデータを得るパスメモリの選択を行う技術が提案されている（例えば、特許文献３参照。）。ＡＣＳ演算で求められた遷移情報を最尤状態情報により、最尤状態に至る遷移情報をパスメモリから逐次的に読み出し、最尤パスをパス打ち切り長だけ遡った状態番号を読み出すトレースバック部を有する最尤復号器が提案されている（例えば、特許文献４参照。）。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開平１０−１０７６５１号公報
【特許文献２】特許第３３５８９９６号公報
【特許文献３】特許第３２７７８５６号公報
【特許文献４】特開２００３−２５８６５０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
前述のように、従来においてトレースバック処理は、時刻Ｎの状態の選択パス情報をパスメモリから読み出して、その選択パス情報に基づき時刻（Ｎ−１）での状態（パス）を確定する。そして、確定した状態に対応する時刻（Ｎ−１）の選択パス情報をパスメモリから読み出して、その選択パス情報に基づき時刻（Ｎ−２）の状態（パス）を確定する。つまり、トレースバック処理では、パスメモリからの選択パス情報の読み出しと、その選択パス情報に基づく状態（パス）の確定とが、逐次的に繰り返し行われることで、１ビットずつ順に確定していき、伝送データが求められる。しかし、パスメモリからの選択パス情報の読み出しと、その選択パス情報に基づく状態の確定とは並列動作ができないため、１ビットの確定に複数サイクルを要してしまい、処理速度が遅いという課題があった。
【課題を解決するための手段】
【０００８】
本発明の一観点によれば、畳み込み符号化されたデータを基に生き残りパスを演算する演算部と、求められた生き残りパスを示すパス情報が格納されるメモリ部と、格納されたパス情報に基づいて状態遷移をトレースバックし復号結果を出力するトレースバック部とを備えるビタビ復号装置が提供される。トレースバック部は、時刻Ｎの状態が第１の状態に確定すると、その時刻に対してｋ時刻前（ｋは所定の２以上の整数）の時刻（Ｎ−ｋ）の状態のうち、時刻Ｎで第１の状態に遷移し得る時刻（Ｎ−ｋ）での２k個の状態のパス情報をメモリ部から読み出して処理を行う。
【発明の効果】
【０００９】
開示のビタビ復号装置は、確定した時刻Ｎの状態に遷移し得る時刻（Ｎ−ｋ）での２k個の状態のパス情報をメモリ部から予め読み出して処理を行うので、メモリアクセスレイテンシを隠蔽することができ、トレースバック処理の高速化を図ることができる。
【図面の簡単な説明】
【００１０】
【図１】本発明の実施形態におけるビタビ復号装置の構成例を示す図である。
【図２】畳み込み符号を説明するための図である。
【図３】本実施形態におけるビタビ復号でのトレースバック処理を説明するための図である。
【図４】第１の実施形態におけるトレースバック部の構成例を示す図である。
【図５】ＡＬＵアレイを有するプロセッサの構成例を示す図である。
【図６】本実施形態における演算処理部の構成例を示す図である。
【図７】第１の実施形態における動作を説明するための図である。
【図８】第１の実施形態における動作を説明するための図である。
【図９】第２の実施形態におけるトレースバック部の構成例を示す図である。
【図１０】図９に示す選択処理部の構成例を示す図である。
【図１１】図９に示すアドレス生成部の構成例を示す図である。
【図１２】第２の実施形態における動作を説明するための図である。
【図１３】第２の実施形態におけるトレースバック部の他の構成例を示す図である。
【図１４】図１３に示す選択処理部の構成例を示す図である。
【図１５】パスメモリにおける格納データの配置イメージの一例を示す図である。
【発明を実施するための形態】
【００１１】
以下、本発明の実施形態を図面に基づいて説明する。
【００１２】
図１は、本発明の一実施形態におけるビタビ復号装置の構成例を示すブロック図である。本実施形態におけるビタビ復号装置は、ブランチメトリック演算部１１、ＡＣＳ（Add-Compare-Select）演算部１２、パスメトリックメモリ１３、パスメモリ１４、及びトレースバック部１５を有する。
【００１３】
ブランチメトリック演算部１１は、復号処理の対象である畳み込み符号化されたデータが入力される。ブランチメトリック演算部１１は、その入力データに基づいて、トレリス線図におけるブランチメトリック（例えば、符号のハミング距離）を計算する。
【００１４】
ＡＣＳ演算部１２は、トレリス線図における各状態についてＡＣＳ演算を行う。すなわち、ＡＣＳ演算部１２は、まず、状態へのすべてのパスについて、ブランチメトリック演算部１１により算出されたブランチメトリックとパスメトリックメモリ１３に格納されている前回演算での生き残りパスのパスメトリックとを加算する（Add）。次に、ＡＣＳ演算部１２は、加算後のパスメトリックを比較して（Compare）、パスメトリックが小さい方（最小）のパスを生き残りパスとして選択する（Select）。ＡＣＳ演算部１２は、トレリス線図における状態毎に前述の演算を行う。ＡＣＳ演算部１２での演算により選択された生き残りパスを示す選択パス情報とそのパスのパスメトリックが、パスメモリ１４とパスメトリックメモリ１３にそれぞれ格納される。
【００１５】
トレースバック部１５は、前述したブランチメトリック演算部１１及びＡＣＳ演算部１２等により行われたビタビ演算の結果をトレースバック処理して結果を出力する。トレースバック部１５は、ＡＣＳ演算部１２での演算によって得られた選択パス情報をパスメモリ１４から読み出し、トレリス線図における状態遷移を遡って確定していき、復号した伝送データとして出力する。
【００１６】
本実施形態におけるビタビ復号装置のトレースバック部１５での処理の概要を、図２及び図３を参照して説明する。
まず、ビタビ復号装置により復号される畳み込み符号について、図２を参照して説明する。なお、以下では、説明が煩雑になることを避けるために、拘束長が３であり、符号化率が１／２である畳み込み符号化を一例として説明する。
【００１７】
図２（Ａ）は、畳み込み符号化器の一例を示す図である。図２（Ａ）に示す畳み込み符号化器は、フリップフロップ２１、２２とＥＸＯＲ回路（排他的論理和演算回路）２３、２４、２５とを有する。入力ｉｎは、１ビット遅延素子としてのフリップフロップ２１、２２が直列に接続されたシフトレジスタに入力される。ＥＸＯＲ回路２３により、入力ｉｎとフリップフロップ２２の出力（入力ｉｎの２ビット遅延出力）との排他的論理和が演算され、符号ｇ０として出力される。また、ＥＸＯＲ回路２４、２５により、入力ｉｎとフリップフロップ２１、２２の出力（入力ｉｎの１ビット遅延出力及び２ビット遅延出力）との排他的論理和が演算され、符号ｇ１として出力される。
【００１８】
図２（Ａ）に示した畳み込み符号化器では、出力は、現在及びその直前の２サイクル分の入力ｉｎによって決まる。畳み込み符号化器へ入力ｉｎが入力されることで、畳み込み符号化器における内部状態（フリップフロップ２１、２２が保持する値）及び出力される符号ｇ０、ｇ１が決まることになる。図２（Ａ）に示した畳み込み符号化器における内部状態の状態遷移を時系列に示すと、図２（Ｂ）に示すトレリス線図のようになる。図２（Ｂ）において、Ｓ００、Ｓ０１、Ｓ１０、Ｓ１１は、畳み込み符号化器における内部状態を示している。状態Ｓａｂは、フリップフロップ２１に値“ａ”が保持され、フリップフロップ２２に値“ｂ”が保持されている状態を示している。
【００１９】
図２（Ｂ）に示すように、例えば内部状態がＳ００のとき、入力ｉｎが“０”であれば、符号（ｇ０、ｇ１）＝（００）が出力され、内部状態がＳ００となり、入力ｉｎが“１”であれば、符号（ｇ０、ｇ１）＝（１１）が出力され、内部状態がＳ１０となる。同様に、内部状態がＳ０１のとき、入力ｉｎが“０”であれば、符号（ｇ０、ｇ１）＝（１１）が出力されかつ内部状態がＳ００となり、入力ｉｎが“１”であれば、符号（ｇ０、ｇ１）＝（００）が出力されかつ内部状態がＳ１０となる。また、内部状態がＳ１０のとき、入力ｉｎが“０”であれば、符号（ｇ０、ｇ１）＝（０１）が出力されかつ内部状態がＳ０１となり、入力ｉｎが“１”であれば、符号（ｇ０、ｇ１）＝（１０）が出力されかつ内部状態がＳ１１となる。また、内部状態がＳ１１のとき、入力ｉｎが“０”であれば、符号（ｇ０、ｇ１）＝（１０）が出力されかつ内部状態がＳ０１となり、入力ｉｎが“１”であれば、符号（ｇ０、ｇ１）＝（０１）が出力されかつ内部状態がＳ１１となる。
【００２０】
図２（Ｂ）に示したように、トレリス線図における各状態に対して２つのパスが存在する。ビタビ復号装置は、初期状態から終了状態に向かって（受信信号の時系列方向に）、入力された符号に基づき各状態についてのＡＣＳ演算を行い、２つのパスのうち確からしい（尤度の高い）パスを生き残りパスとして選択する。また、各状態における生き残りパスを示す選択パス情報をパスメモリに格納する。そして、終了状態から初期状態に向かって、パスメモリに格納された選択パス情報に基づきトレースバック処理を行い、初期状態−終了状態間で最も確からしいパス（最尤パス）を確定して結果を出力する。
【００２１】
ここで、トレリス線図から明らかなように、ある状態に遷移し得る一時刻前の状態は２つ存在する。そのため、時刻Ｎの状態が確定すると、その１つ前の時刻（Ｎ−１）にて取り得る状態の候補は、実際に取る状態と可能性のある状態との２つになる。また、さらに１つ前の時刻（Ｎ−２）にて取り得る状態の候補は、時刻（Ｎ−１）での実際に取る状態及び可能性のある状態に対してそれぞれ２つあり、あわせて４つの状態がある。例えば図３に示したように時刻Ｎの状態がＳＴ０２に確定すると、時刻（Ｎ−１）にて取り得る状態の候補はＳＴ０３及びＳＴ０４の２状態であり、時刻（Ｎ−２）にて取り得る状態の候補はＳＴ０５、ＳＴ０６、ＳＴ０７、及びＳＴ０７の４状態である。
【００２２】
つまり、時刻Ｎの状態が決まると、そのｋ時刻前の時刻（Ｎ−ｋ）にて取り得る状態の候補は２k個の状態である。そこで、本実施形態におけるビタビ復号装置は、時刻Ｎの状態がわかると、そのｋ時刻前の時刻（Ｎ−ｋ）の状態は２k個の状態の中にあることを利用して、トレースバック処理を行う。本実施形態におけるビタビ復号装置は、トレースバック処理において、時刻Ｎの状態が決まると、その結果に応じてパスメモリから時刻（Ｎ−ｋ）の選択パス情報（ただしｋ≧２）を読み出して処理を行う。このようにして、時刻Ｎの状態が確定した後に時刻（Ｎ−１）の選択パス情報をパスメモリから読み出して処理を行う従来のトレースバック処理と比較して、メモリアクセスをより早い段階で行ってメモリアクセスレイテンシを隠蔽し、トレースバック処理の高速化を図る。
【００２３】
以下、本実施形態におけるビタビ復号装置のトレースバック部１５の詳細について説明する。以下に説明する第１の実施形態は、トレースバック処理において１サイクルあたり１ビットずつパス（状態）を確定するものであり、第２の実施形態は、トレースバック処理において１サイクルあたり複数ビットのパス（状態）を確定可能なものである。なお、以下の説明において、ビット表現でデータ列を図示した場合、図示したデータ列の上方側又は右側を下位ビット側とする。すなわち、図示したデータ列において最も上方又は最も右側に図示したビットを最下位ビット（ＬＳＢ：Least Significant Bit）とし、最も下方又は最も左側に図示したビットを最上位ビット（ＭＳＢ：Most Significant Bit）とする。
【００２４】
（第１の実施形態）
図４は、第１の実施形態におけるトレースバック部の構成例を示す図である。
図４において、３１、３３、３５、３７はデータレジスタであり、３２、３４、３６は演算処理部である。また、３８は制御レジスタであり、３９はアドレス生成部であり、４０はメモリである。なお、メモリ４０は、後述するようにパスメモリ１４に対応するものであるが、説明の便宜上、図４において図示している。
【００２５】
データレジスタ３１は、メモリ４０から出力されたデータＤＡＴを保持する。また、データレジスタ３３、３５、３７は、それぞれ演算処理部３２、３４、３６から出力されたデータを保持する。演算処理部３２、３４、３６は、それぞれデータレジスタ３１、３３、３５に保持されているデータが入力される。演算処理部３２、３４、３６は、入力されたデータから特定ビットのデータを取り出すビット取り出し演算を行い、演算により得られたデータ（取り出したビットデータ）を出力する。制御レジスタ３８は、演算処理部３２、３４、３６に対して、ビット取り出し演算において取り出すビット数を指定する情報（抽出ビット数情報）を供給する。
【００２６】
本実施形態において、演算処理部３２、３４、３６が制御レジスタ３８からの抽出ビット数情報により指定されるビット数は、それぞれ４ビット、２ビット、１ビットである。したがって、演算処理部３２からの出力データのうち、有意なビットは４ビットであり、演算処理部３４からの出力データのうち、有意なビットは２ビットである。同様に、演算処理部３６からの出力データのうち、有意なビットは１ビットである。また、演算処理部３２、３４、３６には、ビット取り出し演算において取り出すビットの位置を指定する情報（抽出ビット位置情報）として、演算処理部３６の出力データにおける有意な１ビットが、データレジスタ３７を介して供給されている。演算処理部３２、３４、３６は、入力されたデータにおける有意なビットのなかから、抽出ビット位置情報に応じた位置のビットを取り出す。
【００２７】
メモリ４０は、図１に示したパスメモリ１４に対応する。メモリ４０は、トレリス線図における各状態についての生き残りパスを示す選択パス情報がデータとして格納されている。メモリ４０は、アドレス生成部３９から供給されたアドレスＡＤＤに格納されている選択パス情報をデータＤＡＴとして出力する。アドレス生成部３９は、データレジスタ３７を介して演算処理部３６の出力データにおける有意な１ビット、すなわち最終的な選択結果として出力される１ビットが入力される。アドレス生成部３９は、入力された有意な１ビットの選択パス情報に基づいて、その選択パス情報によって状態が決まる時刻に対し３時刻前の時刻で取り得る８（＝２3）個の状態の選択パス情報をメモリ４０から読み出すアドレスＡＤＤを生成し出力する。例えば、アドレス生成部３９は、入力される有意な１ビットの選択パス情報が時刻Ｎの状態（状態Ａとする）を決めるものであれば、時刻Ｎにて状態Ａに遷移し得る時刻（Ｎ−３）の８個の状態に係る情報をメモリ４０から読み出すためのアドレスＡＤＤを生成する。
【００２８】
ここで、図４に示したトレースバック部は、例えば図５に示すようなＡＬＵ（Arithmetic and Logic Unit）アレイを有するプロセッサを用いて構成しても良い。図５は、ＡＬＵアレイを有するプロセッサの一構成例を示す図である。図５に示すプロセッサは、命令キャッシュ５１、コントローラ５２、レジスタファイル５３、スカラ実行部５４、ロード／ストア部５５、ディスパッチメモリ５６、ＡＬＵアレイ５７、アドレス生成部５８、及びＤＭＡコントローラ５９を備える。
【００２９】
コントローラ５２は、命令キャッシュ５１から読み出した命令に基づいてプロセッサ内の各機能部に係る制御を行う。レジスタファイル５３は、演算の対象となるデータ等を保持する。スカラ実行部５４は、コントローラ５２の指示に従って演算処理を行う。ロード／ストア部５５は、ロード命令／ストア命令に係る処理を実行する。ロード／ストア部５５は、ディスパッチメモリ５６等からレジスタにデータをロードしたり（読み出したり）、レジスタからディスパッチメモリ５６等へデータをストアしたり（書き込んだり）する。ディスパッチメモリ５６は、演算処理を実行して得られたデータ等が格納されるメモリである。
【００３０】
ＡＬＵアレイ５７は、アレイ状に配置された複数のＡＬＵと、その複数のＡＬＵによるパイプラインステージを分割するパイプラインレジスタとを有する。ＡＬＵは、複数の演算器を含む演算ユニットである。パイプラインレジスタは、例えばフリップフロップで構成される。ＡＬＵアレイ５７は、複合演算を１つの命令で処理することができ、例えば入力されたデータから特定ビットのデータを取り出すビット取り出し演算を１つの命令で処理することができる。ＡＬＵアレイ５７は、どの命令を演算するか、どのデータを使用するかを各ＡＬＵに指示することでさまざまな演算処理を行うことができる。アドレス生成部５８は、ＡＬＵアレイ５７の出力からディスパッチメモリ５６にアクセスするためのアドレスを生成する。ＤＭＡコントローラ５９は、プロセッサ内のディスパッチメモリ５６とプロセッサ外部のデバイスとの間で行うＤＭＡ転送に係る制御を行う。
【００３１】
例えば、図４に示したデータレジスタ３１、３３、３５、３７、演算処理部３２、３４、３６、及び制御レジスタ３８の機能を図５に示したＡＬＵアレイ５７により実現する。また例えば、図４に示したアドレス生成部３９の機能を図５に示したアドレス生成部５８により実現し、図４に示したメモリ４０の機能を図５に示したディスパッチメモリ５６により実現する。このようにすることで、図４に示したトレースバック部を図５に示すプロセッサで実現することができる。
【００３２】
図６は、本実施形態における演算処理部の内部構成例を示す図である。
図６（Ａ）に示すように、演算処理部７１は、乗算部７２、シフト演算部７３、マスク出力部７４、及び論理積演算部７５を有する。
【００３３】
乗算部７２は、ビット取り出し演算において取り出すビット数を指定する抽出ビット数情報Ｓと、取り出すビット位置を指定する抽出ビット位置情報ａとが入力される。乗算部７２は、抽出ビット数情報Ｓと抽出ビット位置情報ａとを乗算し、その乗算結果（Ｓ×ａ）を出力する。シフト演算部７３は、入力データＸと、乗算部７２での乗算結果（Ｓ×ａ）とが入力される。シフト演算部７３は、入力データＸのビットを（Ｓ×ａ）ビット分だけ右方向（下位ビット側）にシフトして出力する。すなわち、シフト演算部７３は、入力データＸにおける（ｉ＋（Ｓ×ａ））ビット目をｉビット目にシフトして出力する。
【００３４】
マスク出力部７４は、例えば図６（Ｂ）に示すような抽出ビット数情報Ｓに応じて選択されるマスクパターンからなるテーブルを有している。マスク出力部７４は、抽出ビット数情報Ｓが入力され、抽出ビット数情報Ｓに応じたマスクパターンを出力する。なお、図６に示した例では、抽出ビット数情報Ｓの値を０〜１６の整数とし、それぞれの値に対応するマスクパターンをマスク出力部７４が有するようにしている。しかし、本実施形態におけるトレースバック処理においては、抽出ビット数情報Ｓの値は２のべき乗の整数値だけを取り得るので、２のべき乗の整数値に対応するマスクパターンだけをマスク出力部７４が有するようにしても良い。また、構成に応じて抽出ビット数情報Ｓの上限値も定まるので、抽出ビット数情報Ｓの上限値より大きい値に対応するマスクパターンは備えないようにしても良い。
【００３５】
論理積演算部７５は、シフト演算部７３の出力と、マスク出力部７４の出力とが入力される。論理積演算部７５は、シフト演算部７３の出力とマスク出力部７４の出力（マスクパターン）とをビット毎に論理積演算し、その演算結果を出力データＹとして出力する。
【００３６】
前述のように構成された演算処理部７１は、抽出ビット数情報Ｓ及び抽出ビット位置情報ａに応じて、入力データＸにおける下位側からＳビット単位で分割したときの（ａ＋１）番目のデータ（Ｓビット幅）を選択して出力データＹとして出力する。すなわち、演算処理部７１は、Ｙ＝｛Ｘ＞＞（Ｓ＊ａ）｝＆（マスクパターン）で示される演算処理を行う。ここで、“Ａ＞＞Ｂ”は、データ列ＡのＢビット右シフト（下位側へのシフト）を表す。
【００３７】
例えば、入力データＸが“0000_0000_0000_0000_0000_0000_1111_1111”（バイナリ表記）、抽出ビット数情報Ｓが１、抽出ビット位置情報ａが３であれば、演算処理部７１は、出力データＹとして“0000_0000_0000_0000_0000_0000_0000_0001”を出力する。また、例えば、入力データＸが“0000_0000_0000_0000_0000_0000_1111_1111”、抽出ビット数情報Ｓが３、抽出ビット位置情報ａが２であれば、演算処理部７１は、出力データＹとして“0000_0000_0000_0000_0000_0000_0000_0011”を出力する。
【００３８】
次に、第１の実施形態におけるトレースバック部の動作について、図７及び図８を参照して説明する。図７及び図８は、第１の実施形態におけるトレースバック部の動作を説明するための図である。図７は、ある時刻の状態に係る情報についての処理の流れを示している。また、図８は、トレースバック部におけるデータの流れを示している。図７及び図８において、図４に示した構成要素と同一の構成要素には同一の符号を付している。また、図８において、Ｄ（３１）、Ｄ（３３）、Ｄ（３５）、及びＤ（３７）は、それぞれデータレジスタ３１、３３、３５、及び３７の出力データ（レジスタに格納されているデータ）である。
【００３９】
まず、図７に基づいて動作を説明する。
第１の実施形態におけるトレースバック処理において、時刻（Ｎ＋１）の状態が確定し、データレジスタ３７の出力データとして時刻（Ｎ＋１）の状態の選択パス情報（“０”又は“１”）が出力されているとする。この時刻（Ｎ＋１）の状態の選択パス情報は、演算処理部３２、３４、３６に抽出ビット位置情報ａとして供給されるとともに、アドレス生成部３９に供給される。
【００４０】
演算処理部３６では、供給された時刻（Ｎ＋１）の状態の選択パス情報に基づいて時刻Ｎの状態（状態Ａとする）が決まり、時刻Ｎの状態の選択パス情報が出力される。また、アドレス生成部３９は、前述のように時刻Ｎの状態を決める時刻（Ｎ＋１）の状態の選択パス情報に基づいて、時刻Ｎに対し３時刻前の時刻（Ｎ−３）の状態に係る選択パス情報をメモリ４０（パスメモリ１４）から読み出すアドレスＡＤＤを生成し出力する。このとき生成されるアドレスＡＤＤは、時刻Ｎにおいて状態Ａになり得る時刻（Ｎ−３）での８個の状態に係る選択パス情報（８ビット）を読み出すためのものである。これにより、時刻Ｎに対して３時刻前の時刻（Ｎ−３）の状態に係る選択パス情報のうち、時刻Ｎにおいて状態Ａになり得る８個の状態に係る選択パス情報がメモリ４０から読み出され、データＤＡＴとしてデータレジスタ３１に入力される。なお、この８ビットの情報は、メモリ４０からロードされる際にバイトロードされ、データ列における最下位ビットからの８ビット分に配置されてデータレジスタ３１に入力される。
【００４１】
そして、次のクロックサイクルにて、時刻（Ｎ−３）での８個の状態に係る選択パス情報は、演算処理部３２に入力データＸとして入力される。また、演算処理部３２には、抽出ビット数情報Ｓとして“４”が入力されるとともに、抽出ビット位置情報ａとしてデータレジスタ３７から時刻Ｎの状態の選択パス情報（“０”又は“１”）が入力される。演算処理部３２は、抽出ビット位置情報ａとして入力される時刻Ｎの状態の選択パス情報に基づいて、時刻（Ｎ−３）での８個の状態に係る選択パス情報から上位側の４ビット又は下位側の４ビットを選択して出力する。このようにして、時刻（Ｎ−３）での８個の状態に係る選択パス情報から、時刻Ｎの状態の選択パス情報により決まる時刻（Ｎ−１）の状態に応じた時刻（Ｎ−３）での４個の状態に係る選択パス情報（４ビット）が選択され、データレジスタ３３に入力される。
【００４２】
さらに、その次のクロックサイクルにて、時刻（Ｎ−３）での４個の状態に係る選択パス情報は、演算処理部３４に入力データＸとして入力される。また、演算処理部３４には、抽出ビット数情報Ｓとして“２”が入力されるとともに、抽出ビット位置情報ａとしてデータレジスタ３７から時刻（Ｎ−１）の状態の選択パス情報が入力される。演算処理部３４は、抽出ビット位置情報ａとして入力される時刻（Ｎ−１）の状態の選択パス情報に基づいて、時刻（Ｎ−３）での４個の状態に係る選択パス情報から上位側の２ビット又は下位側の２ビットを選択して出力する。このようにして、時刻（Ｎ−３）での４個の状態に係る選択パス情報から、時刻（Ｎ−１）の状態の選択パス情報により決まる時刻（Ｎ−２）の状態に応じた時刻（Ｎ−３）での２個の状態に係る選択パス情報（２ビット）が選択され、データレジスタ３５に入力される。
【００４３】
続いて、その次のクロックサイクルにて、時刻（Ｎ−３）での２個の状態に係る選択パス情報は、演算処理部３６に入力データＸとして入力される。また、演算処理部３６には、抽出ビット数情報Ｓとして“１”が入力されるとともに、抽出ビット位置情報ａとしてデータレジスタ３７から時刻（Ｎ−２）の状態の選択パス情報が入力される。演算処理部３６は、抽出ビット位置情報ａとして入力される時刻（Ｎ−２）の状態の選択パス情報に基づいて、時刻（Ｎ−３）での２個の状態に係る選択パス情報から上位側の１ビット又は下位側の１ビットを選択して出力する。すなわち、時刻（Ｎ−３）の状態が確定し、その状態の選択パス情報が出力される。
【００４４】
以上の動作を、図８に示すようにクロックサイクル毎に順次処理し各時刻の状態について行うことで、トレースバック処理が実行される。すなわち、ｋを任意の整数として、データレジスタ３７から出力される時刻ｋの状態の選択パス情報に基づいて、それにより決まる時刻（ｋ−１）の状態になり得る時刻（ｋ−４）での８個の状態に係る選択パス情報が読み出される。また、時刻ｋの状態の選択パス情報に基づいて、演算処理部３２、３４、３６により、時刻（ｋ−３）、時刻（ｋ−２）、時刻（ｋ−１）にて取り得る状態がそれぞれ２分の１に限定される。
【００４５】
例えば、図８に示したＴＡの期間においては、データレジスタ３７から出力される時刻（Ｎ＋１）の状態の選択パス情報（時刻Ｎの状態）に基づいて、それにより決まる時刻Ｎの状態になり得る時刻（Ｎ−３）での８個の状態に係る選択パス情報が読み出される。また、演算処理部３２は、データレジスタ３１から出力される時刻（Ｎ−２）での８個の状態に係る選択パス情報から、時刻（Ｎ＋１）の状態の選択パス情報（時刻Ｎの状態）に基づいて４個の状態に係る選択パス情報を選択して出力する。同様に、演算処理部３４は、データレジスタ３３から出力される時刻（Ｎ−１）での４個の状態に係る選択パス情報から、時刻（Ｎ＋１）の状態の選択パス情報（時刻Ｎの状態）に基づいて２個の状態に係る選択パス情報を選択して出力する。演算処理部３６は、データレジスタ３５から出力される時刻Ｎでの２個の状態に係る選択パス情報から、時刻（Ｎ＋１）の状態の選択パス情報に基づいて時刻Ｎの状態に係る選択パス情報を選択して出力する。
【００４６】
第１の実施形態によれば、時刻Ｎの状態が確定すると、その状態に遷移し得るｋ時刻前の時刻（Ｎ−ｋ）での２k個の状態の選択パス情報をメモリから読み出してトレースバック処理を行う。これにより、時刻Ｎの状態が確定した後に時刻（Ｎ−１）の選択パス情報をパスメモリから読み出して処理を行う従来のトレースバック処理と比較して、メモリアクセスをより早い段階で行ってメモリアクセスレイテンシを隠蔽することができる。また、トレースバック処理における状態の確定と、選択パス情報のメモリからの読み出しとを並列して行うことができ、１サイクル毎に１ビットを確定させることが可能となる。したがって、トレースバック処理を従来と比較して高速に実行することができる。
【００４７】
（第２の実施形態）
図９は、第２の実施形態におけるトレースバック部の構成例を示す図である。
図９において、９１、９３、９５、９７、９８、１００、１０２、１０３はデータレジスタであり、９２、９４、９６、９９、１０１は演算処理部である。また、１０４は制御レジスタであり、１０５は選択処理部であり、１０６はアドレス生成部である。１０７はパスメモリ１４に対応するメモリであるが、説明の便宜上、図９において図示している。
【００４８】
データレジスタ９１は、メモリ１０７から出力されたデータＤＴＡを保持し、データレジスタ９８は、メモリ１０７から出力されたデータＤＴＢを保持する。データレジスタ９３、９５、９７、１００、１０２は、それぞれ演算処理部９２、９４、９６、９９、１０１から出力されたデータを保持する。また、データレジスタ１０３は、データレジスタ１０２から出力されたデータを保持する。
【００４９】
演算処理部９２、９４、９６、９９、１０１は、図６に示した第１の実施形態における演算処理部と同様に構成される。演算処理部９２、９４、９６、９９、１０１は、それぞれデータレジスタ９１、９３、９５、９８、１００に保持されているデータが入力される。演算処理部９２、９４、９６、９９、１０１は、入力されたデータから特定ビットのデータを取り出すビット取り出し演算を行い、演算により得られたデータ（取り出したビットデータ）を出力する。制御レジスタ１０４は、演算処理部９２、９４、９６、９９、１０１に対して、ビット取り出し演算において取り出すビット数を指定する抽出ビット数情報を供給する。
【００５０】
図９に示す第２の実施形態におけるトレースバック部において、演算処理部９２、９４、９６が制御レジスタ１０４からの抽出ビット数情報により指定されるビット数は、それぞれ８ビット、２ビット、１ビットである。また、演算処理部９９、１０１が制御レジスタ１０４からの抽出ビット数情報により指定されるビット数は、それぞれ４ビット、１ビットである。したがって、演算処理部９２からの出力データのうち、有意なビットは８ビットであり、演算処理部９４からの出力データのうち、有意なビットは２ビットであり、演算処理部９６からの出力データのうち、有意なビットは１ビットである。同様に、演算処理部９９からの出力データのうち、有意なビットは４ビットであり、演算処理部１０１からの出力データのうち、有意なビットは１ビットである。
【００５１】
また、演算処理部９２、９４、９９、１０１には、選択処理部１０５の出力が、ビット取り出し演算において取り出すビットの位置を指定する抽出ビット位置情報として供給されている。演算処理部９６には、データレジスタ１０２の出力が抽出ビット位置情報として供給されている。演算処理部９２、９４、９６、９９、１０１は、入力されたデータにおける有意なビットのなかから、抽出ビット位置情報に応じた位置のビットを取り出す。
【００５２】
メモリ１０７は、パスメモリ１４に対応し、トレリス線図における各状態についての生き残りパスを示す選択パス情報がデータとして格納されている。メモリ１０７は、アドレス生成部１０６から供給されたアドレスＡＤＤに格納されている選択パス情報をデータＤＴＡ、ＤＴＢとして出力する。
【００５３】
図１０は、図９に示した選択処理部１０５の構成例を示す図である。
選択処理部１０５は、ＡＮＤ回路（論理積演算回路）１１１、１１２及びＯＲ回路（論理和演算回路）１１３を有する。ＡＮＤ回路１１１は、信号Ａ０及び信号Ｂ０が入力され、その演算結果を出力する。また、ＡＮＤ回路１１２は、信号Ａ１が入力されるとともに信号Ｂ０が反転入力され、その演算結果を出力する。ＯＲ回路１１３は、ＡＮＤ回路１１１の出力及びＡＮＤ回路１１２の出力が入力され、その演算結果を出力する。
【００５４】
ここで、信号Ａ０、Ａ１、Ｂ０のそれぞれは１ビットの信号である。データレジスタ９５の出力の有意な２ビットのうち、上位１ビットが信号Ａ０として入力され、下位１ビットが信号Ａ１として入力される。また、データレジスタ１０２の出力の有意な１ビットが信号Ｂ０として入力される。なお、ｊを任意の数として、データレジスタ１０２からの有意な１ビット出力は時刻ｊの状態の選択パス情報であり、データレジスタ９５からの有意な２ビット出力は候補として残っている時刻（ｊ−１）の状態に係る選択パス情報である。
【００５５】
選択処理部１０５は、ＡＮＤ回路１１１、１１２及びＯＲ回路１１３によって、信号Ｂ０に応じて信号Ａ０、Ａ１の一方を選択して出力する。また、選択処理部１０５は、信号Ｂ０をそのまま出力する。すなわち、選択処理部１０５は、データレジスタ１０２からの有意な１ビットの出力に応じて、データレジスタ９５からの有意な２ビットの出力から１ビットを選択して出力するとともに、データレジスタ１０２からの有意な１ビットの出力をそのまま出力する。つまり、選択処理部１０５は、データレジスタ１０２から出力された時刻ｊの状態の選択パス情報を出力するとともに、データレジスタ１０２からの出力に基づいてデータレジスタ９５の出力から時刻（ｊ−１）の状態の選択パス情報を選択して出力する。
【００５６】
図１１は、図９に示したアドレス生成部１０６の構成例を示す図である。
図１１（Ａ）に示すように、アドレス生成部１０６は、オフセットバッファ１３１、シフト演算部１３２、１３４、論理和演算部１３３、ワードバッファ１３５、及び定数加算部１３６、１３７を有する。なお、図１１（Ａ）には、拘束長が９（状態数が２５６）である畳み込み符号化器による畳み込み符号を復号する復号装置に適用されるアドレス生成部を一例として示しており、メモリ１０７には、図１５に示すように各状態の選択パス情報が格納されているものとする。
【００５７】
図１５は、メモリ１０７における各状態の選択パス情報の配置イメージ（状態数が２５６の場合）の一例を示す図である。例えば、時刻Ｎの各状態に係る選択パス情報がメモリ１０７におけるアドレス値０〜３１の領域に格納され、時刻（Ｎ−１）の各状態に係る選択パス情報がメモリ１０７におけるアドレス値３２〜６３の領域に格納されているものとする。同様にして、時刻（Ｎ−ｋ）の各状態に係る選択パス情報がメモリ１０７におけるアドレス値３２ｋ〜（３２ｋ＋３１）の領域に格納されているものとする。なお、図１５において、“○”は各状態の選択パス情報を示しており、“０”又は“１”が格納されている。
【００５８】
オフセットバッファ１３１は、畳み込み符号に係る拘束長がｋであるとき、（ｋ−１）ビットのデータを保持するバッファである。本例では、オフセットバッファ１３１は、８ビットのデータを保持するバッファであり、例えば８個のフリップフロップで構成される。オフセットバッファ１３１は、論理和演算部１３３の出力が入力され、それを保持する。シフト演算部１３２は、オフセットバッファ１３１の出力を２ビット分だけ左方向（上位ビット側）にシフトして、すなわちオフセットバッファ１３１の出力におけるｉビット目を（ｉ＋２）ビット目にシフトして出力する。論理和演算部１３３は、シフト演算部１３２の出力と選択処理部１０５からの２ビット出力とが入力され、それらをビット毎に論理和演算して演算結果を出力する。すなわち、オフセットバッファ１３１、シフト演算部１３２、及び論理和演算部１３３により、１サイクル前の論理和演算部１３３の出力の下位側に選択処理部１０５から出力された２ビットが連結されるとともに、上位側２ビットが切り捨てられて出力される。
【００５９】
ワードバッファ１３５は、ワードアドレスを保持するためのバッファである。ワードバッファ１３５は、定数加算部１３６の出力が入力され、それを保持する。ここで、本例において１ワードは３２バイトである。定数加算部１３６は、ワードバッファ１３５の出力が入力され、それに“２”を加算して出力する。すなわち、ワードバッファ１３５及び定数加算部１３６により、サイクル毎に“２”ずつ増加させた値がワードバッファ１３５から出力される。
【００６０】
アドレス生成部１０６は、論理和演算部１３３の出力及びワードバッファ１３５の出力を基にアドレスａｄｄｒｅｓｓ１、ａｄｄｒｅｓｓ２を生成し、アドレスＡＤＤとしてメモリ１０７に出力する。ここで、アドレスａｄｄｒｅｓｓ１は、データＤＴＡとしてデータレジスタ９１に入力するデータをメモリ１０７から読み出すためのアドレスであり、アドレスａｄｄｒｅｓｓ２は、データＤＴＢとしてデータレジスタ９８に入力するデータをメモリ１０７から読み出すためのアドレスである。アドレスａｄｄｒｅｓｓ１は、ワードバッファ１３５の出力に対して定数加算部１３６により“１”だけ加算した値を上位側とし、論理和演算部１３３の出力をシフト演算部１３４により１ビット分だけ左方向（上位ビット側）にシフトした値を下位側としてビット連結し生成される。また、アドレスａｄｄｒｅｓｓ２は、ワードバッファ１３５の出力を上位側とし、論理和演算部１３３の出力を下位側としてビット連結して生成される。なお、メモリ１０７にアクセスするためのアドレスはバイト単位であるため、それぞれ下位側３ビットを除いたものがアドレスａｄｄｒｅｓｓ１、ａｄｄｒｅｓｓ２として出力される。
【００６１】
例えば、アドレス生成部１０６に対して選択処理部１０５から１サイクル目に“ｂ１”、“ａ１”の２ビットが入力され、２サイクル目に“ｂ２”、“ａ２”の２ビットが入力され、３サイクル目に“ｂ３”、“ａ３”の２ビットが入力されたとする。なお、オフセットバッファ１３１、及びワードバッファ１３５の初期値は、各ビット“０”であるとする。このとき、アドレス生成部１０６は、図１１（Ｂ）に示すように各サイクル毎にアドレスａｄｄｒｅｓｓ１、ａｄｄｒｅｓｓ２を生成して出力する。
【００６２】
次に、図９に一例を示した第２の実施形態におけるトレースバック部の動作について説明する。図１２は、第２の実施形態におけるトレースバック部の動作を説明するための図である。
第２の実施形態におけるトレースバック処理において、データレジスタ１０２から時刻Ｎの状態の選択パス情報（“０”又は“１”）が出力され、データレジスタ９５から候補として残っている時刻（Ｎ−１）の状態の選択パス情報が出力されているとする。
【００６３】
このとき、選択処理部１０５は、データレジスタ１０２からの時刻Ｎの状態の選択パス情報に基づいて、データレジスタ９５からの時刻（Ｎ−１）の２状態の選択パス情報の一方を選択する。そして、選択処理部１０５は、データレジスタ１０２からの時刻Ｎの状態の選択パス情報と、選択したデータレジスタ９５からの時刻（Ｎ−１）の状態の選択パス情報とを出力する。すなわち、選択処理部１０５は、時刻Ｎの状態の選択パス情報及び時刻（Ｎ−１）の状態の選択パス情報を出力する。また、データレジスタ１０２からの時刻Ｎの状態の選択パス情報が演算処理部９６に抽出ビット位置情報ａとして供給され、演算処理部９６は、時刻Ｎの状態の選択パス情報に基づき時刻（Ｎ−１）の状態を確定し（状態Ａとする）、時刻（Ｎ−１）の状態の選択パス情報を出力する。
【００６４】
選択処理部１０５より出力された時刻Ｎの状態の選択パス情報及び時刻（Ｎ−１）の状態の選択パス情報は、演算処理部９２、９４、９９、１０１に抽出ビット位置情報ａとして供給されるとともに、アドレス生成部１０６に供給される。アドレス生成部１０６は、時刻Ｎの状態の選択パス情報及び時刻（Ｎ−１）の状態の選択パス情報に基づいて、アドレスａｄｄｒｅｓｓ１、ａｄｄｒｅｓｓ２を生成しメモリ１０７にアドレスＡＤＤとして出力する。これにより、時刻（Ｎ−１）に対して６時刻前の時刻（Ｎ−７）の状態の選択パス情報のうち、時刻（Ｎ−１）にて状態Ａになり得る３２個の状態の選択パス情報（３２ビット）がメモリ１０７から読み出され、データＤＴＡとしてデータレジスタ９１に入力される。また、時刻（Ｎ−１）に対して５時刻前の時刻（Ｎ−６）の状態の選択パス情報のうち、時刻（Ｎ−１）にて状態Ａになり得る１６個の状態の選択パス情報がメモリ１０７から読み出され、データＤＴＢとしてデータレジスタ９８に入力される。
【００６５】
そして、次のクロックサイクルにて、データレジスタ９１より出力される時刻（Ｎ−７）での３２個の状態に係る選択パス情報は、演算処理部９２に入力データＸとして入力される。また、演算処理部９２には、抽出ビット数情報Ｓとして“８”が入力されるとともに、選択処理部１０５から時刻（Ｎ−２）の状態の選択パス情報及び時刻（Ｎ−３）の状態の選択パス情報が抽出ビット位置情報ａ（０〜３）として入力される。演算処理部９２は、入力された抽出ビット位置情報ａに基づいて、時刻（Ｎ−７）での３２個の状態に係る選択パス情報を下位側から８ビット単位で分割したときの（ａ＋１）番目の選択パス情報（８ビット）を選択して出力する。このようにして、時刻（Ｎ−７）での３２個の状態に係る選択パス情報から、時刻（Ｎ−３）の状態の選択パス情報により決まる時刻（Ｎ−４）の状態に応じた時刻（Ｎ−７）での８個の状態に係る選択パス情報が選択され、データレジスタ９３に入力される。
【００６６】
また、データレジスタ９８より出力される時刻（Ｎ−６）での１６個の状態に係る選択パス情報は、演算処理部９９に入力データＸとして入力される。また、演算処理部９９には、抽出ビット数情報Ｓとして“４”が入力されるとともに、選択処理部１０５から時刻（Ｎ−２）の状態の選択パス情報及び時刻（Ｎ−３）の状態の選択パス情報が抽出ビット位置情報ａ（０〜３）として入力される。演算処理部９９は、入力された抽出ビット位置情報ａに基づいて、時刻（Ｎ−６）での１６個の状態に係る選択パス情報を下位側から４ビット単位で分割したときの（ａ＋１）番目の選択パス情報（４ビット）を選択して出力する。このようにして、時刻（Ｎ−６）での１６個の状態に係る選択パス情報から、時刻（Ｎ−３）の状態の選択パス情報により決まる時刻（Ｎ−４）の状態に応じた時刻（Ｎ−６）での４個の状態に係る選択パス情報が選択され、データレジスタ１００に入力される。
【００６７】
さらに、その次のクロックサイクルにて、データレジスタ９３より出力される時刻（Ｎ−７）での８個の状態に係る選択パス情報は、演算処理部９４に入力データＸとして入力される。また、演算処理部９４には、抽出ビット数情報Ｓとして“２”が入力されるとともに、選択処理部１０５から時刻（Ｎ−４）の状態の選択パス情報及び時刻（Ｎ−５）の状態の選択パス情報が抽出ビット位置情報ａ（０〜３）として入力される。演算処理部９４は、入力された抽出ビット位置情報ａに基づいて、時刻（Ｎ−７）での８個の状態に係る選択パス情報を下位側から２ビット単位で分割したときの（ａ＋１）番目の選択パス情報（２ビット）を選択して出力する。このようにして、時刻（Ｎ−７）での８個の状態に係る選択パス情報から、時刻（Ｎ−５）の状態の選択パス情報により決まる時刻（Ｎ−６）の状態に応じた時刻（Ｎ−７）での２個の状態に係る選択パス情報が選択され、データレジスタ９５に入力される。
【００６８】
また、データレジスタ１００より出力される時刻（Ｎ−６）での４個の状態に係る選択パス情報は、演算処理部１０１に入力データＸとして入力される。また、演算処理部１０１には、抽出ビット数情報Ｓとして“１”が入力されるとともに、選択処理部１０５から時刻（Ｎ−４）の状態の選択パス情報及び時刻（Ｎ−５）の状態の選択パス情報が抽出ビット位置情報ａ（０〜３）として入力される。演算処理部１０１は、入力された抽出ビット位置情報ａに基づいて、時刻（Ｎ−６）での４個の状態に係る選択パス情報を下位側から１ビット単位で分割したときの（ａ＋１）番目の選択パス情報（１ビット）を選択して出力する。このようにして、時刻（Ｎ−５）の状態の選択パス情報に基づいて時刻（Ｎ−６）の状態が確定し、その状態の選択パス情報がデータレジスタ１０２に入力される。
以上の動作を、クロックサイクル毎に順次２時刻分ずつ並列処理し各時刻の状態について行うことで、トレースバック処理が実行される。
【００６９】
なお、前述した説明では、１サイクル期間中に結果を２ビット出力するトレースバック部を一例として示したが、これに限定されるものではない。１サイクルあたり任意の複数ビットの結果を出力するトレースバック部が構成可能である。例えば、１サイクルあたり３ビットの結果を出力するトレースバック部は、図１３に一例を示すように構成すれば良い。
【００７０】
図１３は、第２の実施形態におけるトレースバック部の他の構成例を示す図である。
図１３において、１５１、１５３、１５５、１５７、１５８、１６０、１６２、１６３、１６４、１６６、１６７、１６８はデータレジスタであり、１５２、１５４、１５６、１５９、１６１、１６５は演算処理部である。また、１６９は制御レジスタであり、１７０は選択処理部であり、１７１はアドレス生成部である。１７２はパスメモリ１４に対応するメモリであるが、説明の便宜上、図１３において図示している。
【００７１】
データレジスタ１５１、１５８、１６４は、メモリ１７２から出力されたデータを保持する。データレジスタ１５３、１５５、１５７、１６０、１６２、１６６は、それぞれ演算処理部１５２、１５４、１５６、１５９、１６１、１６５から出力されたデータを保持する。また、データレジスタ１６３、１６７、１６８は、それぞれデータレジスタ１６２、１６６、１６７から出力されたデータを保持する。
【００７２】
演算処理部１５２、１５４、１５６、１５９、１６１、１６５のそれぞれは、図６に示した第１の実施形態における演算処理部と同様に構成される。演算処理部１５２、１５４、１５６、１５９、１６１、１６５は、それぞれデータレジスタ１５１、１５３、１５５、１５８、１６０、１６４に保持されているデータが入力される。演算処理部１５２、１５４、１５６、１５９、１６１、１６５は、入力されたデータから特定ビットのデータを取り出すビット取り出し演算を行い、演算により得られたデータ（取り出したビットデータ）を出力する。制御レジスタ１６９は、演算処理部１５２、１５４、１５６、１５９、１６１、１６５に対して、ビット取り出し演算において取り出すビット数を指定する抽出ビット数情報を供給する。
【００７３】
図１３に示したトレースバック部において、演算処理部１５２、１５４、１５６が制御レジスタ１６９からの抽出ビット数情報により指定されるビット数は、それぞれ４ビット、２ビット、１ビットである。また、演算処理部１５９が制御レジスタ１６９からの抽出ビット数情報により指定されるビット数は２ビットであり、演算処理部１６１、１６５が制御レジスタ１６９からの抽出ビット数情報により指定されるビット数は１ビットである。
【００７４】
また、演算処理部１５２、１５９、１６５には、選択処理部１７０の出力が、ビット取り出し演算において取り出すビットの位置を指定する抽出ビット位置情報として供給されている。演算処理部１５４、１６１には、データレジスタ１６６の出力が抽出ビット位置情報として供給され、演算処理部１５６には、データレジスタ１６２の出力が抽出ビット位置情報として供給されている。演算処理部１５２、１５４、１５６、１５９、１６１、１６５は、入力されたデータにおける有意なビットのなかから、抽出ビット位置情報に応じた位置のビットを取り出す。
【００７５】
メモリ１７２は、パスメモリ１４に対応し、トレリス線図における各状態についての生き残りパスを示す選択パス情報がデータとして格納されている。メモリ１７２は、アドレス生成部１７１から供給されたアドレスに格納されている選択パス情報をデータとして出力する。
【００７６】
図１４は、図１３に示した選択処理部１７０の構成例を示す図である。
選択処理部１７０は、セレクタ回路１９１〜１９４を有する。セレクタ回路１９１は、データレジスタ１６０の出力における有意な２ビットが入力されるとともに、データレジスタ１６６の出力における有意な１ビットが入力される。セレクタ回路１９１は、データレジスタ１６６からの１ビット出力に基づいて、データレジスタ１６０の出力における有意な２ビットから１ビットを選択して外部に出力する。
【００７７】
セレクタ回路１９２、１９３は、データレジスタ１５３の出力における有意な４ビットが２ビットずつ入力されるとともに、データレジスタ１６６の出力における有意な１ビットが入力される。セレクタ回路１９２、１９３は、データレジスタ１６６からの１ビット出力に基づいて、データレジスタ１６６から入力された２ビットから１ビットを選択して出力する。また、セレクタ回路１９４は、セレクタ回路１９２、１９３の出力が入力されるとともに、セレクタ回路１９１の出力が入力される。セレクタ回路１９４は、セレクタ回路１９１の出力に基づいて、セレクタ回路１９２、１９３の出力の一方を選択して出力する。すなわち、セレクタ回路１９２、１９３、１９４は、データレジスタ１６６の出力及びセレクタ回路１９１の出力に基づいて、データレジスタ１５３の出力における有意な４ビットから１ビットを選択して外部に出力する。
また、データレジスタ１６６の出力における有意な１ビットは、そのまま外部にも出力される。
【００７８】
以上の構成によれば、選択処理部１７０は、データレジスタ１６６から出力された時刻ｊの状態の選択パス情報を出力するとともに、データレジスタ１６６からの出力に基づいてデータレジスタ１６０の出力から時刻（ｊ−１）の状態の選択パス情報を選択して出力する。また、選択処理部１７０は、データレジスタ１６６からの出力、及びそれに基づいてデータレジスタ１６０の出力から選択した時刻（ｊ−１）の状態の選択パス情報に基づいて、データレジスタ１５３の出力から時刻（ｊ−２）の状態の選択パス情報を選択して出力する。
【００７９】
なお、図１３に示すトレースバック部の動作は、演算処理部１５２、１５４、１５６、１５９、１６１、１６５の各々が演算対象とする時刻の相対的な関係は異なるが、図９に示したトレースバック部と基本的な動作は同様である。
【００８０】
第２の実施形態によれば、第１の実施形態と同様に、従来のトレースバック処理と比較してメモリアクセスをより早い段階で行いメモリアクセスレイテンシを隠蔽できるとともに、トレースバック処理での状態の確定と、選択パス情報のメモリからの読み出しとを並列して行うことができる。また、ビット取り出し演算を行うことができる図６に示したような演算処理部を並列に複数配置するだけで、１サイクル期間中に複数の時刻の状態を確定することができる。したがって、１ビット分のデータの確定を１サイクル以下で行うことが可能となり、トレースバック処理を高速に実行することができる。
なお、図９や図１３に示した第２の実施形態におけるトレースバック部を、第１の実施形態と同様に図５に一例を示したようなＡＬＵアレイを有するプロセッサを用いて構成しても良い。
【００８１】
また、前記実施形態は、何れも本発明を実施するにあたっての具体化のほんの一例を示したものに過ぎず、これらによって本発明の技術的範囲が限定的に解釈されてはならないものである。すなわち、本発明はその技術思想、またはその主要な特徴から逸脱することなく、様々な形で実施することができる。
【符号の説明】
【００８２】
１１  ブランチメトリック演算部
１２  ＡＣＳ演算部
１３  パスメトリックメモリ
１４  パスメモリ
１５  トレースバック部
３１、３３、３５、３７  データレジスタ
３２、３４、３６  演算処理部
３８  制御レジスタ
３９  アドレス生成部
４０  メモリ
【図１】
2011124848.tif 000003
【図２】
2011124848.tif 000004
【図３】
2011124848.tif 000005
【図４】
2011124848.tif 000006
【図５】
2011124848.tif 000007
【図６】
2011124848.tif 000008
【図７】
2011124848.tif 000009
【図８】
2011124848.tif 000010
【図９】
2011124848.tif 000011
【図１０】
2011124848.tif 000012
【図１１】
2011124848.tif 000013
【図１２】
2011124848.tif 000014
【図１３】
2011124848.tif 000015
【図１４】
2011124848.tif 000016
【図１５】
2011124848.tif 000017