(57)【要約】【課題】ビタビ復号処理のトレースバックにおいてメモリアクセスの効率が高く、高速に復号化処理を実行できる復号化装置を提供する。【解決手段】復号化装置は、状態レジスタと、各時刻についての生き残りパスデータを全時刻について格納したメモリから、着目時刻から所定の先行時刻迄の複数の時刻各々について生き残りパスデータの部分データを状態レジスタの内容に応じて選択して読み出すメモリアクセスユニットと、複数の時刻のうち最後の時刻の部分データから状態レジスタの内容に応じて１ビットを選択するとともに、複数の時刻のうちの最後の時刻でない任意の時刻の部分データから１ビットを選択するビット選択処理においては、任意の時刻の次の時刻から最後の時刻までの１つ又は複数の時刻の部分データと状態レジスタの内容とに応じてビット選択する演算部とを含む。【選択図】図１
2010213225.tif 000002
【特許請求の範囲】
【請求項１】
着目時刻での内部状態を示すデータを格納する状態レジスタと、
各時刻についての第１ビット数の生き残りパスデータを全時刻について格納したメモリから、前記着目時刻から所定の先行時刻迄の複数の時刻各々について前記第１ビット数よりも少ない第２ビット数の前記生き残りパスデータの部分データを前記状態レジスタの内容に応じて選択し、前記複数の時刻各々について前記部分データを読み出すメモリアクセスユニットと、
前記複数の時刻のうち最後の時刻の前記部分データから前記状態レジスタの内容に応じて１ビットを選択するとともに、前記複数の時刻のうちの前記最後の時刻でない任意の時刻の前記部分データから１ビットを選択するビット選択処理においては、前記任意の時刻の次の時刻から前記最後の時刻までの１つ又は複数の時刻の前記部分データと前記状態レジスタの内容とに応じてビット選択することにより、前記複数の時刻のそれぞれに対して前記部分データから１ビットを選択する演算部と
を含むことを特徴とする復号化装置。
【請求項２】
前記演算部は、前記複数の時刻のうちの前記最後の時刻でない任意の時刻の前記部分データから１ビットを選択するビット選択処理においては、前記任意の時刻の次の時刻から前記最後の時刻までの１つ又は複数の時刻の前記部分データからそれぞれ選択した１ビットを少なくとも用いてビット選択することを特徴とする請求項１記載の復号化装置。
【請求項３】
前記演算部は、前記複数の時刻のうちの前記最後の時刻でなく且つ最初の時刻でない任意の時刻の前記部分データから１ビットを選択するビット選択処理においては、該任意の時刻の次の時刻から前記最後の時刻までの１つ又は複数の時刻の前記部分データからそれぞれ選択した１ビットと前記状態レジスタの内容とに応じてビット選択することを特徴とする請求項１又は２記載の復号化装置。
【請求項４】
前記演算部は、前記複数の時刻のうちの最初の時刻の前記部分データから１ビットを選択するビット選択処理においては、該最初の時刻の次の時刻から前記最後の時刻までの１つ又は複数の時刻の前記部分データからそれぞれ選択した１ビットに応じてビット選択することを特徴とする請求項１乃至３の何れか一項記載の復号化装置。
【請求項５】
着目時刻での内部状態を示すデータを状態レジスタに格納し、
各時刻についての第１ビット数の生き残りパスデータを全時刻について格納したメモリから、前記着目時刻から所定の先行時刻迄の複数の時刻各々について前記第１ビット数よりも少ない第２ビット数の前記生き残りパスデータの部分データを前記状態レジスタの内容に応じて選択して、前記複数の時刻各々について前記部分データを読み出し、
前記複数の時刻のうち最後の時刻の前記部分データから前記状態レジスタの内容に応じて１ビットを選択し、
前記複数の時刻のうちの前記最後の時刻でない任意の時刻の前記部分データから１ビットを選択するビット選択処理において、前記任意の時刻の次の時刻から前記最後の時刻までの１つ又は複数の時刻の前記部分データと前記状態レジスタの内容とに応じてビット選択する
各段階を含むことを特徴とするビタビ復号におけるトレースバック方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本願開示は、一般に電子回路に関し、詳しくは復号化装置に関する。
【背景技術】
【０００２】
無線通信では、通信路のノイズ等に起因する誤りが発生する。そのような情報誤りに対する対策として、送信側で所定の規則に従った符号変換により冗長性の高い情報を生成して送信する。受信側では、受信情報にある程度の情報誤りが含まれていても、送信情報が上記の規則に従っているべきであるとの認識に基づいて復号処理を行なうことにより、誤りを訂正して正しい符号列を復元することができる。
【０００３】
このような復号化技術として、畳み込み符号化された信号を最尤推定するビタビ復号処理がある。ビタビ復号処理では、ＡＣＳ（Add, Compare, Select）処理とトレースバック処理とが実行される。この際、各時刻における内部状態と、ある時刻の内部状態から次の時刻の内部状態への遷移の経路を示すトレリス線図が用いられる。
【０００４】
ＡＣＳでは、まずトレリス線図において、着目時刻Ｎの各内部状態から次の時刻Ｎ＋１の内部状態に遷移する経路の各々と受信データとの距離を、枝メトリックとして計算する。この枝メトリックを、着目時刻Ｎに至る経路全体のパスメトリックに加算することで、次の時刻Ｎ＋１に至る経路のパスメトリックを計算する。更に、時刻Ｎ＋１の各内部状態について、同一内部状態に到達する２つの経路間でパスメトリックを比較して、メトリック値（距離）が小さいものを選択する。時刻Ｎ＋１の各内部状態について、一時刻前から到達する２つの経路のうちの何れが選択されたかを示す１ビットの情報を割り当てておく。この１ビットの情報は、生き残りパスを示すデータであり、パスメモリに格納される。以上の処理を繰り返すことにより、初期時刻から最終時刻までの各内部状態に対して、生き残りパスデータがパスメモリに格納される。
【０００５】
トレースバックでは、ＡＣＳ処理により選択された経路を最終内部状態から前方にたどることにより、送信データを復元（復号）する。具体的には、着目時刻の着目内部状態に対応する生き残りパスデータをパスメモリから読み出す。読み出したデータが０であるか１であるかが、一時刻前に取り得る２つの内部状態のうちの何れが尤度の高いものであるかを示している。この読み出した生き残りパスデータに応じて、一時刻前の内部状態を確定する。この内部状態の確定により、当該時刻での復号結果が得られる。このパスメモリからのデータの読出し及び一時刻前の内部状態の確定を繰り返すことにより、受信データ全体が復号される。
【０００６】
このように従来のトレースバックにおいては、各時刻での復号処理において、毎回パスメモリからのデータの読出しを行なっている。そのように毎回メモリにアクセスするのでは効率が悪く、ビタビ復号処理の処理時間が長くなってしまう。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開平１０−１５０３６９号公報
【特許文献２】特許３３５８９９６号公報
【特許文献３】特開平１１−７４８００号公報
【特許文献４】特開２００７−１７４５６１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
以上を鑑みると、ビタビ復号処理のトレースバックにおいてメモリアクセスの効率が高く、高速に復号化処理を実行できる復号化装置が望まれる。
【課題を解決するための手段】
【０００９】
復号化装置は、着目時刻での内部状態を示すデータを格納する状態レジスタと、各時刻についての第１ビット数の生き残りパスデータを全時刻について格納したメモリから、前記着目時刻から所定の先行時刻迄の複数の時刻各々について前記第１ビット数よりも少ない第２ビット数の前記生き残りパスデータの部分データを前記状態レジスタの内容に応じて選択し、前記複数の時刻各々について前記部分データを読み出すメモリアクセスユニットと、前記複数の時刻のうち最後の時刻の前記部分データから前記状態レジスタの内容に応じて１ビットを選択するとともに、前記複数の時刻のうちの前記最後の時刻でない任意の時刻の前記部分データから１ビットを選択するビット選択処理においては、前記任意の時刻の次の時刻から前記最後の時刻までの１つ又は複数の時刻の前記部分データと前記状態レジスタの内容とに応じてビット選択することにより、前記複数の時刻のそれぞれに対して前記部分データから１ビットを選択する演算部とを含むことを特徴とする。
【００１０】
ビタビ復号におけるトレースバック方法は、着目時刻での内部状態を示すデータを状態レジスタに格納し、各時刻についての第１ビット数の生き残りパスデータを全時刻について格納したメモリから、前記着目時刻から所定の先行時刻迄の複数の時刻各々について前記第１ビット数よりも少ない第２ビット数の前記生き残りパスデータの部分データを前記状態レジスタの内容に応じて選択して、前記複数の時刻各々について前記部分データを読み出し、前記複数の時刻のうち最後の時刻の前記部分データから前記状態レジスタの内容に応じて１ビットを選択し、前記複数の時刻のうちの前記最後の時刻でない任意の時刻の前記部分データから１ビットを選択するビット選択処理において、前記任意の時刻の次の時刻から前記最後の時刻までの１つ又は複数の時刻の前記部分データと前記状態レジスタの内容とに応じてビット選択する各段階を含むことを特徴とする。
【発明の効果】
【００１１】
本願開示の少なくとも１つの実施例によれば、複数の時刻に対して纏めて生き残りパスデータをメモリから読出してトレースバック処理を行なうので、メモリアクセスの効率の良い、高速な復号化処理を実現することができる。
【図面の簡単な説明】
【００１２】
【図１】復号化装置の構成の一例を示す図である。
【図２】トレリス線図を示す図である。
【図３】生き残りパスデータを説明するための図である。
【図４】アドレス生成器の構成の一例を示す図である。
【図５】メモリバンク内での生き残りパスデータの格納位置を示す図である。
【図６】メモリから読み出したデータのパッキングを示す図である。
【図７】トレースバックを実行する演算器の構成の一例を示す図である。
【図８】演算器の各セレクタの動作を説明するための図である。
【図９】状態レジスタの更新動作について説明する図である。
【図１０】複数の時刻に対して纏めてトレースバック処理を行なう構成を種々の異なる時刻数に対して適用した場合の実行効率を示す図である。
【図１１】アドレス生成器の構成の変形例を示す図である。
【図１２】アドレス生成器の構成の更に別の一例を示す図である。
【図１３】図１２に示す汎用レジスタを状態レジスタとして用いた場合の演算器の入出力関係を示す図である。
【図１４】状態レジスタの更新動作について説明する図である。
【図１５】ＯＦＤＭ受信機の構成の一例を示す図である。
【発明を実施するための形態】
【００１３】
以下に、本発明の実施例を添付の図面を用いて詳細に説明する。
【００１４】
図１は、復号化装置の構成の一例を示す図である。図１に示す復号化装置１０は、命令ユニット１１、レジスタファイル１２、演算ユニット１３、及びメモリアクセスユニット１４を含む。復号化装置１０は、生き残りパスデータを格納したメモリバンク２０−１乃至２０−４に接続される。
【００１５】
復号化装置１０は、ＣＰＵ（Central Processing Unit）等の処理装置と専用のハードウェアとを組み合わせて構成してよい。例えば命令ユニット１１は、メモリから読み出した命令列をデコードして実行することにより、復号化装置１０の各部に対する制御動作を行なう部分であり、ＣＰＵの処理実行部分に相当する。レジスタファイル１２は、命令ユニット１１が種々の処理を実行する際に使用するデータを格納する部分であり、ＣＰＵの汎用レジスタに相当する。演算ユニット１３はビタビ演算器１６を含み、所定の処理を行なうための専用のハードウェアに相当する。ビタビ演算器１６は、本発明のトレースバック処理を実行するための演算器を少なくとも含み、更にＡＣＳ処理を実行するための演算器を含んでよい。
【００１６】
メモリアクセスユニット１４は、アドレス生成器１７とパッキングユニット１８とを含む。アドレス生成器１７は、メモリバンク２０−１乃至２０−４の各々から所望の生き残りパスデータの部分データを選択的に読み出すための読出しアドレスを生成し、メモリバンク２０−１乃至２０−４のそれぞれに読出しアドレスを供給する。パッキングユニット１８は、アドレス生成器１７が生成した読出しアドレスに応じてメモリバンク２０−１乃至２０−４のそれぞれから読み出された生き残りパスデータの部分データを１つのデータに纏める。パッキングユニット１８は、纏めた１つのデータをレジスタファイル１２に供給する。
【００１７】
図２はトレリス線図を示す図である。図２において各○印は各時刻における内部状態に対応する。ここでいう内部状態とは、送信側の畳み込み符号化器の複数の内部レジスタの０又は１の状態に対応する。各時刻における内部状態の数が例えば２５６個であるとすると、各内部状態（図中の各○印）は３２ビットのデータが示す１つのビットパターンに対応する。例えば“００００００００”が１つの内部状態であり、“０００００００１”が別の内部状態となる。ある時刻（例えばＮ−２）の内部状態から次の時刻（Ｎ−１）の内部状態へ遷移する経路は、各内部状態に対して２つある。これは送信側で１ビットの送信データが符号化器に入力され、この入力１ビットにより内部状態が遷移する際に、入力１ビットの０又は１に対応して現在の内部状態から遷移する次の内部状態が２つあることを示している。またある時刻（例えばＮ−２）の内部状態に前の時刻（Ｎ−３）の内部状態から遷移する経路は、各内部状態に対して２つある。これは送信側の符号化器への１ビットの送信データ入力に伴い１ビットの送信データが追い出されて内部状態が遷移する際に、追い出される１ビットの０又は１に対応して現在の内部状態に至る遷移前の内部状態が２つあることを示している。
【００１８】
前述のＡＣＳの処理により、各時刻の各内部状態について、一時刻前から到達する２つの経路のうちの何れが選択されたかを示す１ビットの情報を割り当てる。この１ビットの情報は、生き残りパスを示すデータである。
【００１９】
図３は、生き残りパスデータを説明するための図である。時刻Ｎ−２乃至Ｎに対して内部状態３０乃至３６が示されている。図示を見やすくするために、他の内部状態を示す○印の図示を省略してある。各内部状態の○印の内部に示す０又は１の値が、その内部状態の生き残りパスデータである。また、各内部状態に至る２つの経路は生き残りパスデータの値に対応付けられており、上側の経路が０に対応付けられ、下側の経路が１に対応付けられている。ＡＣＳの処理により各時刻の各内部状態について生き残りパスデータが割り当てられると、トレースバック処理により尤もらしい経路を前方に辿っていく。
【００２０】
図３の例において、時刻Ｎの内部状態３０から尤もらしい経路を前方に辿る場合を考える。まず時刻Ｎの内部状態３０の生き残りパスデータを参照する。この生き残りパスデータの値は０である。従って、内部状態３０に至る２つの経路のうちで上側の経路が生き残り経路であり、内部状態３０へ遷移する元である時刻Ｎ−１の内部状態としては内部状態３１が尤もらしい。従って次に、時刻Ｎ−１の内部状態３１の生き残りパスデータを参照する。この生き残りパスデータの値は１である。従って、内部状態３１に至る２つの経路のうちで下側の経路が生き残り経路であり、内部状態３１へ遷移する元である時刻Ｎ−２の内部状態としては内部状態３４が尤もらしい。このようにして、図３に太線で示すような最尤経路が見つけられる。
【００２１】
図２に戻り、時刻Ｎにおいて、ハッチングされた内部状態２５から尤もらしい経路を前方に辿る場合を考える。この場合、時刻Ｎ−１の内部状態のうちで、時刻Ｎの内部状態２５に遷移可能な内部状態は、時刻Ｎ−１においてハッチングされた２つの内部状態である。また時刻Ｎ−２の内部状態のうちで、時刻Ｎの内部状態２５に最終的に到達可能な内部状態は、時刻Ｎ−２においてハッチングされた４つの内部状態である。更に同様に、時刻Ｎ−３の内部状態のうちで、時刻Ｎの内部状態２５に最終的に到達可能な内部状態は、時刻Ｎ−３においてハッチングされた８つの内部状態である。
【００２２】
従って、時刻Ｎの内部状態２５からトレースバックする際に、時刻Ｎの内部状態２５の生き残りパスデータの値を参照しなくとも、１つ前の時刻Ｎ−１についてトレースバック処理に必要になる可能性のある生き残りパスデータの数は限られている。即ち、時刻Ｎ−１について、トレースバック処理に必要になる可能性のある生き残りパスデータは、時刻Ｎ−１においてハッチングされた２つの内部状態の生き残りパスデータである。同様に、２つ前の時刻Ｎ−２についてトレースバック処理に必要になる可能性のある生き残りパスデータの数は限られている。即ち、時刻Ｎ−２について、トレースバック処理に必要になる可能性のある生き残りパスデータは、時刻Ｎ−２においてハッチングされた４つの内部状態の生き残りパスデータである。更に同様に、時刻Ｎ−３について、トレースバック処理に必要になる可能性のある生き残りパスデータは、時刻Ｎ−３においてハッチングされた8つの内部状態の生き残りパスデータである。
【００２３】
トレースバック処理の各時刻において一時刻前の生き残りパスデータを毎回逐一メモリから読み出すことなく、着目時刻に先行する複数の時刻分の生き残りパスデータを纏めて読み出すことを考える。例えば内部状態数が２５６の場合、生き残りパスデータは各時刻につき２５６ビットある。従って、トレースバック処理に必要になる可能性のある生き残りパスデータの数が限られていることを考慮せずに着目時刻に先行する複数の時刻分の全ての生き残りパスデータを纏めて読み出すことは、バス幅等を考慮すると現実的に不可能である。しかしながら、図２に示すように、トレースバック処理に必要になる可能性のある生き残りパスデータは限定されている。これを考慮することにより、トレースバック処理に必要になる可能性のある生き残りパスデータを複数の時刻分纏めて読み出しておくことができる。これは、読出し対象のデータのビット幅が比較的小さい（例えば時刻Ｎ−３に対する読出し対象のデータのビット幅は８）ために可能になることである。
【００２４】
図１に示す復号化装置１０は、４つのメモリバンク２０−１乃至２０−４に接続されている。これは、着目時刻から３つ前の先行時刻迄の４つの時刻の生き残りパスデータを纏めて読み出す場合に相当する。例えば、着目時刻から１つ前の先行時刻迄の２つの時刻の生き残りパスデータを纏めて読み出す場合には、メモリバンクの数は２つであってよい。同様に、着目時刻から７つ前の先行時刻迄の８つの時刻の生き残りパスデータを纏めて読み出す場合には、メモリバンクの数は８つであってよい。本発明は、纏めて読み出す生き残りパスデータの数、即ち纏めて生き残りパスデータを読み出す対象の時刻の数は、特定の数に限られるものではない。
【００２５】
図４は、アドレス生成器１７の構成の一例を示す図である。アドレス生成器１７は、アドレス結線部４１及びアドレスバッファ４２−１乃至４２−４を含む。汎用レジスタ１２Ａ及び１２Ｂは、図１のレジスタファイル１２内部の汎用レジスタであってよい。汎用レジスタ１２Ａは、メモリ空間上で各時刻の生き残りパスデータが格納されている領域の開始アドレスをベースアドレスとして格納する。この汎用レジスタ１２Ａのベースアドレスは、処理対象時刻に応じて適宜カウントアップ或いはカウントダウンされる。汎用レジスタ１２Ｂは、着目時刻での内部状態を示すデータを格納する状態レジスタとして機能する。例えば、図２において着目時刻Ｎの内部状態２５から前方に経路を辿る場合、内部状態２５のビットパターンが汎用レジスタ１２Ｂに格納される。この例では、内部状態は８ビットであり、各時刻について２５６個の内部状態が存在することになる。なお内部状態の数は２５６に限定されるものではなく、任意の数の内部状態であってよい。状態レジスタのビット数は、その内部状態の数に応じた数になる。
【００２６】
アドレス結線部４１は、汎用レジスタ１２Ｂに格納される８ビットのデータ“ａｂｃｄｅｆｇｈ”のうちで、所定の５ビットをそれぞれのアドレスバッファ４２−１乃至４２−４に下位５ビットとして供給する。またアドレス結線部４１は更に、汎用レジスタ１２Ａに格納されるベースアドレスをそれぞれのアドレスバッファ４２−１乃至４２−４に上位ビットして供給する。
【００２７】
具体的には、８ビットのデータ“ａｂｃｄｅｆｇｈ”のうちの“ａｂｃｄｅ”がアドレスバッファ４２−１に下位５ビットとして供給される。また８ビットのデータ“ａｂｃｄｅｆｇｈ”のうちの“ｂｃｄｅｆ”がアドレスバッファ４２−２に下位５ビットとして供給される。また８ビットのデータ“ａｂｃｄｅｆｇｈ”のうちの“ｃｄｅｆｇ”がアドレスバッファ４２−３に下位５ビットとして供給される。更に、８ビットのデータ“ａｂｃｄｅｆｇｈ”のうちの“ｄｅｆｇｈ”がアドレスバッファ４２−４に下位５ビットとして供給される。ここでアドレスバッファ４２−１の格納アドレスａｒｄｓ＿４ｋ−０は、着目時刻の生き残りパスデータを読み出すアドレスである。アドレスバッファ４２−２の格納アドレスａｒｄｓ＿４ｋ−１は、着目時刻の１つ前の時刻の生き残りパスデータを読み出すアドレスである。アドレスバッファ４２−３の格納アドレスａｒｄｓ＿４ｋ−２は、着目時刻の２つ前の時刻の生き残りパスデータを読み出すアドレスである。アドレスバッファ４２−４の格納アドレスａｒｄｓ＿４ｋ−３は、着目時刻の３つ前の時刻の生き残りパスデータを読み出すアドレスである。
【００２８】
上記のアドレスバッファ４２−１乃至４２−４の下位５ビットにより、それぞれの時刻の２５６ビットの生き残りパスデータから１バイト（８ビット幅の部分データ）を選択する。即ち、２５６ビットの生き残りパスデータを３２個の１バイトデータとして考えた場合に、５ビットのアドレスにより３２バイトのうちの1バイトを選択する。図２から分かるように、ある着目時刻のある内部状態に着目した場合に、その着目内部状態に遷移可能な直前の時刻の内部状態の位置は、当該着目内部状態の位置に依存する。従って、着目内部状態の位置の情報から、そこに遷移可能な直前の時刻の内部状態の位置を特定することができる。同様に、着目内部状態の位置の情報から、そこに遷移可能な２つ前の時刻の内部状態の位置を特定することができる。更に、３つ前の時刻の内部状態の位置も特定することができる。このような位置の依存関係は、時刻に関わらず一定である。このような依存関係があるために、着目時刻の着目内部状態の位置を示す内部状態のビットパターン“ａｂｃｄｅｆｇｈ”に基づいて、着目時刻の着目内部状態に遷移可能な内部状態を特定することができる。即ち、トレースバック処理に必要になる可能性のある生き残りパスデータのメモリ内部での位置を特定することができる。
【００２９】
図５は、メモリバンク２０−１乃至２０−４内での生き残りパスデータの格納位置を示す図である。図５において０，１，２，３，・・・，４ｋ−３，４ｋ−２，４ｋ−１，４ｋの各数字を記した欄は、それぞれ時刻０，１，２，３，・・・，４ｋ−３，４ｋ−２，４ｋ−１，４ｋの各時刻における生き残りパスデータの２５６ビットの塊を示す。全部でＮ＋１個の時刻であれば、０，１，２，３，・・・，４ｋ−３，４ｋ−２，４ｋ−１，４ｋは時刻０〜Ｎに対応する。図５では、各メモリバンクにおいて４時刻おきにデータが格納されていることを明示するために、ｋを変数としてその４倍である４ｋを用いた表記としてある。
【００３０】
このように、メモリバンク２０−１乃至２０−４は、各時刻についての第１ビット数（例えば２５６ビット）の生き残りパスデータを全時刻について格納してある。メモリアクセスユニット１４のアドレス生成器１７は、着目時刻から所定の先行時刻迄の複数の時刻各々について第１ビット数よりも少ない第２ビット数（例えば８ビット）の生き残りパスデータの部分データを状態レジスタ１２Ｂの内容に応じて選択する。即ち、図４に示すようなアドレス生成により、８ビットデータ（バイトデータ）を選択する。複数の時刻各々（例えば着目時刻、一時刻前、二時刻前、三時刻前）について、このようにして選択された部分データが、メモリバンク２０−１乃至２０−４のそれぞれから並行して読み出される。
【００３１】
図６は、メモリから読み出したデータのパッキングを示す図である。図６において、図
１乃至５と同一の構成要素は同一の番号で参照し、その説明は省略する。図１に示すパッキングユニット１８は、メモリバンク２０−１乃至２０−４のそれぞれから並行して読み出されたそれぞれ８ビットのデータを纏めて１つの３２ビットのデータを生成し、レジスタファイル１２にこの３２ビットのデータを供給する。この３２ビットのデータを格納するレジスタファイル１２中の汎用レジスタ１２Ｃを、以下において、パックト・パスメモリＰＰＭと呼ぶ。
【００３２】
図７は、トレースバックを実行する演算器の構成の一例を示す図である。図７に示す演算器５１は、図１に示すビタビ演算器１６に含まれてよい。演算器５１は、状態レジスタである汎用レジスタ１２Ｂ（その内容を配列データｓｔａｔｅ［７：０］として示す）の格納データの下位３ビットとパックト・パスメモリ１２Ｃの格納データとを入力とする。演算器５１は、パックト・パスメモリ１２Ｃの格納データから選択した生き残りパスデータを、演算結果として汎用レジスタ１２Ｄに出力する。
【００３３】
前述のように、パックト・パスメモリ１２Ｃには、複数の時刻各々（この例では着目時刻、一時刻前、二時刻前、三時刻前）について、部分データ（８ビットの生き残りパスデータ）が４つ格納されている。演算器５１は、セレクタ（マルチプレクサ）５２乃至５５を含む。セレクタ５２は、上記複数の時刻のうち最後の時刻（着目時刻）の部分データ（１バイトデータ）から状態レジスタ１２Ｂの内容に応じて１ビットを選択する。セレクタ５３乃至５５は、上記複数の時刻のうちの最後の時刻でない任意の時刻の部分データ（１バイトデータ）から１ビットを選択するビット選択処理を行なう。このビット選択処理においては、前記任意の時刻の次の時刻から最後の時刻までの１つ又は複数の時刻の部分データ（１バイトデータ）と状態レジスタ１２Ｂの内容とに応じて、ビット選択する。これにより、上記複数の時刻のそれぞれに対して生き残りパスデータの部分データから１ビットを選択する。
【００３４】
図８は、演算器５１の各セレクタの動作を説明するための図である。図８において、図７と同一の構成要素は同一の番号で参照する。パックト・パスメモリ１２Ｃの例えば下位８ビットには、現在時刻４ｋの生き残りパスデータの部分データ“０１０１００１０”が格納されている。セレクタ５２は、この部分データ“０１０１００１０”から、状態レジスタの内容の下位３ビット“ｆｇｈ”の値に基づいて、濃くハッチングされたビット“０”を選択する。具体的には、“ｆｇｈ”が“０１０”であるので、最下位ビットをｂ０として２番目のビットｂ２が選択される。これは、状態レジスタの内容“ａｂｃｄｅｆｇｈ”のうち、上位５ビット“ａｂｃｄｅ”により２５６ビット中の３２バイトのうちの１バイトを選択し、残りの３ビット“ｆｇｈ”により１バイト中の１ビットを選択していることに相当する。
【００３５】
セレクタ５３乃至５５は、時刻４ｋ−３乃至４ｋのうちの最後の時刻４ｋでない時刻の部分データから１ビットを選択する際に、その時刻の次の時刻から最後の時刻４ｋまでの１つ又は複数の時刻の部分データからそれぞれ選択した１ビットを少なくとも用いる。以下にこれを説明する。
【００３６】
セレクタ５３は、セレクタ５３Ａ及び５３Ｂを含む。パックト・パスメモリ１２Ｃの例えば下から２番目の８ビットには、現在時刻から一時刻前４ｋ−１の生き残りパスデータの部分データ“１１０１１００１”が格納されている。セレクタ５３Ａは、この部分データ“１１０１１００１”から、セレクタ５２が選択した１ビット“０”の値に応じて、０，２，４，６番目のビットｂ０，ｂ２，ｂ４，ｂ６を選択する。またセレクタ５３Ｂは、状態レジスタの内容の下位２ビット“ｇｈ”に応じて、ビットｂ０，ｂ２，ｂ４，ｂ６のうちのビットｂ４を選択する。即ち、“ｇｈ”が“１０”であるので、ビットｂ０，ｂ２，ｂ４，ｂ６の並びのうちで、最下位ビットｂ０を０番目として下から２番目のビットｂ４を選択する。このビットｂ４は、濃くハッチングされたビット“１”である。
【００３７】
セレクタ５４は、セレクタ５４Ａ乃至５４Ｃを含む。パックト・パスメモリ１２Ｃの例えば下から３番目の８ビットには、現在時刻から二時刻前４ｋ−２の生き残りパスデータの部分データ“１１０００００１”が格納されている。セレクタ５４Ａは、この部分データ“１１０００００１”から、セレクタ５２が選択した１ビット“０”の値に応じて、０，１，４，５番目のビットｂ０，ｂ１，ｂ４，ｂ５を選択する。またセレクタ５４Ｂは、セレクタ５３が選択した１ビット“１”の値に応じて、ビットｂ０，ｂ１，ｂ４，ｂ５からｂ１，ｂ５を選択する。更に、セレクタ５４Ｃは、状態レジスタの内容の最下位ビット“ｈ”に応じて、ビットｂ１，ｂ５のうちのビットｂ１を選択する。即ち、“ｈ”が“０”であるので、ビットｂ１，ｂ５の並びのうちで、下から０番目のビットｂ１を選択する。このビットｂ１は、濃くハッチングされたビット“０”である。
【００３８】
以上のセレクタ５３及び５４の処理が、最後の時刻ｋでなく且つ最初の時刻４ｋ−３でない任意の時刻の部分データから１ビットを選択するビット選択処理である。このビット選択処理では、ビット選択対象の時刻の次の時刻から最後の時刻までの１つ又は複数の時刻の部分データからそれぞれ選択した１ビットと状態レジスタの内容とに応じてビット選択する。
【００３９】
また更に、複数の時刻のうちの最初の時刻の部分データから１ビットを選択するビット選択処理について以下に説明する。このビット選択処理では、最初の時刻４ｋ−３の次の時刻４ｋ−２から最後の時刻４ｋまでの１つ又は複数の時刻の部分データからそれぞれ選択した１ビットに応じてビット選択する。セレクタ５５は、セレクタ５５Ａ乃至５５Ｃを含む。パックト・パスメモリ１２Ｃの例えば下から４番目の８ビットには、現在時刻から三時刻前４ｋ−３の生き残りパスデータの部分データ“１１１００１０１”が格納されている。セレクタ５５Ａは、この部分データ“１１１００１０１”から、セレクタ５２が選択した１ビット“０”の値に応じて、０，１，２，３番目のビットｂ０，ｂ１，ｂ２，ｂ３を選択する。またセレクタ５５Ｂは、セレクタ５３が選択した１ビット“１”の値に応じて、ビットｂ０，ｂ１，ｂ２，ｂ３からｂ２，ｂ３を選択する。更に、セレクタ５５Ｃは、セレクタ５４が選択した１ビット“０”の値に応じて、ビットｂ２，ｂ３からｂ２を選択する。このビットｂ２は、濃くハッチングされたビット“０”である。
【００４０】
上記のようにして、生き残りパスデータ０，１，０，１が順次選択されて、復号データ“ｉｊｋｌ”となる。この復号データ“ｉｊｋｌ”は、図７に示すように汎用レジスタ１２Ｄに格納される。以下に説明するように、データ“ｉｊｋｌ”により、現在の状態レジスタの内容“ａｂｃｄｅｆｇｈ”を更新する。
【００４１】
図９は、状態レジスタの更新動作について説明する図である。時刻４ｋ−３乃至４ｋに対して復号化処理（トレースバック処理）が終了すると、次の時刻４（ｋ−１）−３乃至４（ｋ−１）に対して復号化処理（トレースバック処理）を実行する。この際、時刻４（ｋ−１）が着目時刻となるが、この着目時刻の最尤内部状態を求めておく必要がある。図２のトレリス線図の例では、各時刻の内部状態数が１６であり、内部状態は４ビットである。図の一番上の内部状態が“００００”であり、一番下の内部状態が“１１１１”であり、その間は上から下に２進数の値が１つずつ増加するように内部状態が並んでいる。このトレリス線図の遷移パターンを検討すると以下のことが分かる。ある内部状態から前方に辿るときに上側の経路（“０”）を選択すると、内部状態の４ビットのビットパターンを左に１ビットシフト（２倍）して、最下位ビットに“０”を挿入した下位４ビットの値が一時刻前の内部状態となっている。また内部状態から前方に辿るときに下側の経路（“１”）を選択すると、内部状態の４ビットのビットパターンを左に１ビットシフト（２倍）して、最下位ビットに“１”を挿入した４ビットの値が一時刻前の内部状態となっている。ここで上側の経路の“０”及び下側の経路の“１”の値は、選択した１ビットの生き残りパスデータの値である。従って、時刻４（ｋ−１）の内部状態は、元の内部状態“ａｂｃｄｅｆｇｈ”を４ビット左にシフトして下位４ビットに復号データ“ｉｊｋｌ”を挿入して得られる“ｅｆｇｈｉｊｋｌ”である。
【００４２】
図９において、汎用レジスタ１２Ｄには、演算器５１で演算した復号データ“ｉｊｋｌ”が格納されている。まず状態レジスタである汎用レジスタ１２Ｂの内容“ａｂｃｄｅｆｇｈ”を４ビット左にシフトして“ｅｆｇｈ００００”にする。次に汎用レジスタ１２Ｂの内容“ｅｆｇｈ００００”と汎用レジスタ１２Ｄの内容“００００ｉｊｋｌ”とのＯＲ演算を実行し、状態レジスタである汎用レジスタ１２Ｂの内容を“ｅｆｇｈｉｊｋｌ”に更新する。このビットシフト処理とＯＲ処理とは、図１の命令ユニット１１により、通常のＣＰＵのシフト命令及び演算命令等として実行してよい。この場合、ビットシフト処理とＯＲ処理とにそれぞれ１サイクルかかり、状態レジスタ更新全体では合計２サイクルかかることになる。
【００４３】
従来の構成では、各時刻のトレースバック処理について、メモリ読出しに１サイクル、状態レジスタ更新に２サイクルかかり、合計で３サイクル必要とする。従って、４つの時刻についてトレースバック処理すると、１２サイクルかかることになる。それに対して上記説明した複数の時刻に対して纏めてトレースバック処理を行なう構成では、メモリ読出しに１サイクル、復号演算（図８のビット選択処理）に１サイクル、状態レジスタ更新に２サイクルかかり、合計で４サイクルかかることになる。従って、従来の１２サイクルが４サイクルに短縮され、大幅なスピード向上を実現することができる。
【００４４】
図１０は、複数の時刻に対して纏めてトレースバック処理を行なう構成を種々の異なる時刻数に対して適用した場合の実行効率を示す図である。上記実施例に説明したように、纏めてトレースバック処理する複数の時刻の数が４である場合（図１０の段数Ｎ＝４）、メモリバンク数は４、部分データのビット幅は８、パックト・パスメモリの幅は３２、実行サイクル数は４である。このとき、各段あたりのサイクル数を示す実行効率は１．００となる。図１０の段数Ｎ＝１が従来技術の構成に相当し、実行効率は４．００となっている。また例えば、纏めてトレースバック処理する複数の時刻の数が２である場合（図１０の段数Ｎ＝２）、メモリバンク数は２、部分データのビット幅は２、パックト・パスメモリの幅は４、実行サイクル数は４となる。この場合の実行効率は２．００となる。
【００４５】
図１１は、アドレス生成器１７の構成の変形例を示す図である。図１１において、図４と同一の構成要素は同一の番号で参照し、その説明は省略する。このアドレス生成器１７は、アドレス結線部４１Ｂ及びアドレスバッファ４２−１乃至４２−４を含む。汎用レジスタ１２Ｂ−１乃至１２Ｂ−４は、それぞれが対応時刻での内部状態を示すデータのうち必要ビットを格納するレジスタである。アドレス結線部４１Ｂは、汎用レジスタ１２Ｂ−１乃至１２Ｂ−４に格納されるデータをそれぞれのアドレスバッファ４２−１乃至４２−４に下位５ビットとして供給する。具体的には、汎用レジスタ１２Ｂ−１の格納データ“ａｂｃｄｅ”が、アドレスバッファ４２−１に下位５ビットとして供給される。また汎用レジスタ１２Ｂ−２の格納データ“ｂｃｄｅｆ”が、アドレスバッファ４２−２に下位５ビットとして供給される。また汎用レジスタ１２Ｂ−２の格納データ“ｃｄｅｆｇ”が、アドレスバッファ４２−３に下位５ビットとして供給される。更に、汎用レジスタ１２Ｂ−４の格納データ“ｄｅｆｇｈ”が、アドレスバッファ４２−４に下位５ビットとして供給される。このような構成とすれば、アドレス結線部４１Ｂの結線構成を単純なものとすることができる。
【００４６】
図１２は、アドレス生成器１７の構成の更に別の一例を示す図である。図１２において図４と同一の構成要素は同一の番号で参照し、その説明は省略する。このアドレス生成器１７は、アドレス結線部４１Ｅ及びアドレスバッファ４２−１乃至４２−４を含む。汎用レジスタ１２Ｅは、複数の時刻について内部状態を示すデータの必要ビットを纏めて格納する３２ビットのレジスタである。アドレス結線部４１Ｅは、汎用レジスタ１２Ｅに格納される３２ビットのデータから適宜選択した４つの５ビットデータを、それぞれのアドレスバッファ４２−１乃至４２−４に下位５ビットとして供給する。
【００４７】
具体的には、アドレス結線部４１Ｅの下位８ビットのデータ“ａｂｃｄｅｆｇｈ”のうちの“ａｂｃｄｅ”がアドレスバッファ４２−１に下位５ビットとして供給される。またアドレス結線部４１Ｅの下から２番目の８ビットのデータ“ｂｃｄｅｆｇｈ＿”のうちの“ｂｃｄｅｆ”がアドレスバッファ４２−２に下位５ビットとして供給される。またアドレス結線部４１Ｅの下から３番目の８ビットのデータ“ｃｄｅｆｇｈ＿＿”のうちの“ｃｄｅｆｇ”がアドレスバッファ４２−３に下位５ビットとして供給される。更に、アドレス結線部４１Ｅの下から４番目の８ビットのデータ“ｄｅｆｇｈ＿＿＿”のうちの“ｄｅｆｇｈ”がアドレスバッファ４２−４に下位５ビットとして供給される。ここで空白“＿”のビットはドントケアである。このような構成とすれば、アドレス結線部４１Ｅの結線構成を比較的単純なものとすることができる。
【００４８】
図１３は、図１２に示す汎用レジスタ１２Ｅを状態レジスタとして用いた場合の演算器の入出力関係を示す図である。図１３において、図７と同一の構成要素は同一の番号で参照し、その説明は省略する。状態レジスタである汎用レジスタ１２Ｅ（その内容を配列データｓｔａｔｅ［３１：０］として示す）の下位３ビットが演算器５１に入力される。演算器５１は、パックト・パスメモリ１２Ｃの格納データから選択した生き残りパスデータを、演算結果として３２ビットの汎用レジスタ１２Ｅに出力する。この際、演算結果の４ビットのデータ“ｉｊｋｌ”は、３２ビットの汎用レジスタ１２Ｅの４箇所に重複して格納される。
【００４９】
図１４は、状態レジスタ１２Ｅの更新動作について説明する図である。図１４において、汎用レジスタ１２Ｆには、演算器５１で演算した復号データ“ｉｊｋｌ”が４箇所に格納されている。まず状態レジスタである汎用レジスタ１２Ｅの内容を４ビット左にシフトする。次に汎用レジスタ１２Ｅの内容に所定のマスクデータでマスクすることにより、不要なビット部分を０に設定する。最後に、マスク後の汎用レジスタ１２Ｅの内容と汎用レジスタ１２Ｆの内容とのＯＲ演算を実行し、状態レジスタである汎用レジスタ１２Ｅの内容を更新する。このビットシフト処理、マスク処理、及びＯＲ処理は、図１の命令ユニット１１により、通常のＣＰＵのシフト命令、マスク命令、及び演算命令等として実行してよい。
【００５０】
図１５は、ＯＦＤＭ受信機の構成の一例を示す図である。図１５の受信機６０は、受信回路７１、パスサーチ部７２、ＦＦＴ処理部７３、チャネル推定器７４、及びエラー訂正部７５を含む。アンテナにより受信されたＯＦＤＭ受信信号（無線信号）は、受信回路７１によりベースバンド信号に復調され、更にデジタル受信信号に変換される。同期処理により推定した同期点をフレーム開始点として基づいて、ＦＦＴ処理部７３が、ＦＦＴ（Ｆａｓｔ  Ｆｏｕｒｉｅｒ  Ｔｒａｎｓｆｏｒｍ）処理を実行し受信信号を復調する。チャネル推定器７４は、ＦＦＴ処理部７３による復調信号に基づいて、受信信号の位相ずれを検出するチャネル推定処理を実行する。エラー訂正部７５は、ビタビ復号化器７６を含み、ビタビ復号処理を実行することによりデジタル受信信号中のエラーを訂正する。このビタビ復号化器７６として、図１に示す復号化装置１０を用いてよい。
【００５１】
以上、本発明を実施例に基づいて説明したが、本発明は上記実施例に限定されるものではなく、特許請求の範囲に記載の範囲内で様々な変形が可能である。
【００５２】
なお本発明は、以下の内容を含むものである。
（付記１）
着目時刻での内部状態を示すデータを格納する状態レジスタと、
各時刻についての第１ビット数の生き残りパスデータを全時刻について格納したメモリから、前記着目時刻から所定の先行時刻迄の複数の時刻各々について前記第１ビット数よりも少ない第２ビット数の前記生き残りパスデータの部分データを前記状態レジスタの内容に応じて選択し、前記複数の時刻各々について前記部分データを読み出すメモリアクセスユニットと、
前記複数の時刻のうち最後の時刻の前記部分データから前記状態レジスタの内容に応じて１ビットを選択するとともに、前記複数の時刻のうちの前記最後の時刻でない任意の時刻の前記部分データから１ビットを選択するビット選択処理においては、前記任意の時刻の次の時刻から前記最後の時刻までの１つ又は複数の時刻の前記部分データと前記状態レジスタの内容とに応じてビット選択することにより、前記複数の時刻のそれぞれに対して前記部分データから１ビットを選択する演算部と
を含むことを特徴とする復号化装置。
（付記２）
前記演算部は、前記複数の時刻のうちの前記最後の時刻でない任意の時刻の前記部分データから１ビットを選択するビット選択処理においては、前記任意の時刻の次の時刻から前記最後の時刻までの１つ又は複数の時刻の前記部分データからそれぞれ選択した１ビットを少なくとも用いてビット選択することを特徴とする付記１記載の復号化装置。
（付記３）
前記演算部は、前記複数の時刻のうちの前記最後の時刻でなく且つ最初の時刻でない任意の時刻の前記部分データから１ビットを選択するビット選択処理においては、該任意の時刻の次の時刻から前記最後の時刻までの１つ又は複数の時刻の前記部分データからそれぞれ選択した１ビットと前記状態レジスタの内容とに応じてビット選択することを特徴とする付記１又は２記載の復号化装置。
（付記４）
前記演算部は、前記複数の時刻のうちの最初の時刻の前記部分データから１ビットを選択するビット選択処理においては、該最初の時刻の次の時刻から前記最後の時刻までの１つ又は複数の時刻の前記部分データからそれぞれ選択した１ビットに応じてビット選択することを特徴とする付記１乃至３の何れか一項記載の復号化装置。
（付記５）
着目時刻での内部状態を示すデータを状態レジスタに格納し、
各時刻についての第１ビット数の生き残りパスデータを全時刻について格納したメモリから、前記着目時刻から所定の先行時刻迄の複数の時刻各々について前記第１ビット数よりも少ない第２ビット数の前記生き残りパスデータの部分データを前記状態レジスタの内容に応じて選択して、前記複数の時刻各々について前記部分データを読み出し、
前記複数の時刻のうち最後の時刻の前記部分データから前記状態レジスタの内容に応じて１ビットを選択し、
前記複数の時刻のうちの前記最後の時刻でない任意の時刻の前記部分データから１ビットを選択するビット選択処理において、前記任意の時刻の次の時刻から前記最後の時刻までの１つ又は複数の時刻の前記部分データと前記状態レジスタの内容とに応じてビット選択する
各段階を含むことを特徴とするビタビ復号におけるトレースバック方法。
（付記６）
前記ビット選択する段階は、前記複数の時刻のうちの前記最後の時刻でない任意の時刻の前記部分データから１ビットを選択するビット選択処理においては、前記任意の時刻の次の時刻から前記最後の時刻までの１つ又は複数の時刻の前記部分データからそれぞれ選択した１ビットを少なくとも用いてビット選択することを特徴とする付記５記載のトレースバック方法。
（付記７）
前記ビット選択する段階は、前記複数の時刻のうちの前記最後の時刻でなく且つ最初の時刻でない任意の時刻の前記部分データから１ビットを選択するビット選択処理においては、該任意の時刻の次の時刻から前記最後の時刻までの１つ又は複数の時刻の前記部分データからそれぞれ選択した１ビットと前記状態レジスタの内容とに応じてビット選択することを特徴とする付記５又は６記載のトレースバック方法。
（付記８）
前記ビット選択する段階は、前記複数の時刻のうちの最初の時刻の前記部分データから１ビットを選択するビット選択処理においては、該最初の時刻の次の時刻から前記最後の時刻までの１つ又は複数の時刻の前記部分データからそれぞれ選択した１ビットに応じてビット選択することを特徴とする付記５乃至５の何れか一項記載のトレースバック方法。
（付記９）
無線信号をデジタル受信信号に変換する受信回路と、
前記デジタル受信信号に対してビタビ復号処理を行なう復号化装置と
を含み、前記復号化装置は、
着目時刻での内部状態を示すデータを格納する状態レジスタと、
各時刻についての第１ビット数の生き残りパスデータを全時刻について格納したメモリから、前記着目時刻から所定の先行時刻迄の複数の時刻各々について前記第１ビット数よりも少ない第２ビット数の前記生き残りパスデータの部分データを前記状態レジスタの内容に応じて選択し、前記複数の時刻各々について前記部分データを読み出すメモリアクセスユニットと、
前記複数の時刻のうち最後の時刻の前記部分データから前記状態レジスタの内容に応じて１ビットを選択するとともに、前記複数の時刻のうちの前記最後の時刻でない任意の時刻の前記部分データから１ビットを選択するビット選択処理においては、前記任意の時刻の次の時刻から前記最後の時刻までの１つ又は複数の時刻の前記部分データと前記状態レジスタの内容とに応じてビット選択することにより、前記複数の時刻のそれぞれに対して前記部分データから１ビットを選択する演算部と
を含むことを特徴とする受信機。
【符号の説明】
【００５３】
１０  復号化装置
１１  命令ユニット
１２  レジスタファイル
１３  演算ユニット
１４  メモリアクセスユニット
２０−１乃至２０−４  メモリバンク
【図１】
2010213225.tif 000003
【図２】
2010213225.tif 000004
【図３】
2010213225.tif 000005
【図４】
2010213225.tif 000006
【図５】
2010213225.tif 000007
【図６】
2010213225.tif 000008
【図７】
2010213225.tif 000009
【図８】
2010213225.tif 000010
【図９】
2010213225.tif 000011
【図１０】
2010213225.tif 000012
【図１１】
2010213225.tif 000013
【図１２】
2010213225.tif 000014
【図１３】
2010213225.tif 000015
【図１４】
2010213225.tif 000016
【図１５】
2010213225.tif 000017