(57)【特許請求の範囲】
【請求項１】
畳み込み符号の復号を行うビタビ復号装置において、
畳み込み符号の各遷移状態に向かう２本のパスのうち一方のパスを選択パスとして、連続した複数の時点について記憶するパスメモリ部と、
前記パスメモリ部に記憶されている選択パスを過去に遡る方向にトレースすることによって、所定の打ち切り長より前の各時点の畳み込み符号の復号を行うトレース部と、
前記パスメモリ部を制御する制御部とを備え、
前記パスメモリ部は、各時点における各遷移状態の選択パスを記憶する記憶領域が、遷移状態の最下位から所定桁のビット値毎に分割されているとともに、その分割領域毎にデータの読出休止が可能となっており、
前記制御部は、各時点において選択パスの読み出しの必要がない分割領域を特定し、特定した分割領域に対して読出休止の制御を行うこと
を特徴とするビタビ復号装置。
【請求項２】
前記パスメモリ部は、少なくとも打ち切り長の２分の１以上の時点の選択パスを記憶可能なメモリを複数個有し、選択パスの書き込みが複数のメモリに対して巡回的に行われ、
トレース部は、複数のメモリのうちの書き込みを行っている以外のメモリから選択パスを読み出してトレースを行い、
さらに、前記パスメモリ部は、メモリ毎に選択パスの記憶領域が分割されていること
を特徴とする請求項１記載のビタビ復号装置。
【請求項３】
前記制御部は、トレース開始時点の遷移状態の最下位から所定桁のビット値を参照して、各時点において選択パスの読み出しの必要がない分割領域を特定すること
を特徴とする請求項１のビタビ復号装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、例えば衛星放送などで使用される畳み込み符号の最尤復号法に使用されるビタビ復号装置に関するものである。
【背景技術】
【０００２】
畳み込み符号を復号する方法の一つとして、ビタビ復号が知られている。ビタビ復号は、少ない計算量で最尤復号することができる復号方法である。
【０００３】
図２１は、拘束長＝４の場合の畳み込み符号の遷移ダイアグラム（トレリス線図）を示す。
【０００４】
畳み込み符号は、図２１に示すように、ある時刻の遷移状態（ステートとも言う。遷移状態は、その時刻の畳み込み符号器の記憶素子に記憶されているビット列に対応している。）から、新たな情報（１ビット）が入力されると、新たな次の遷移状態に移行する。新たな情報は、０又は１であるため、ある時刻の１つの遷移状態から次の時刻に遷移する場合、取り得る遷移状態は２つだけとなる。すなわち、畳み込み符号では、ある時刻から次の時刻の遷移状態へ至るパスは２本しかない。
【０００５】
ビタビ復号では、各時刻において、可能性のある全ての遷移状態についてその遷移状態へ至る２本のパスのうち尤度の高いいずれか一方のパスを選択する。具体的には、ある遷移状態に合流する２本のパスに対し、受信信号とパスとのハミング距離（ブランチメトリック）と、それまでのブランチメトリックの累積和（ステートメトリック）とを加算して比較を行い、この比較結果に基づいて尤度の高い一方のパスを、その遷移状態の選択パスとする。選択パスは一旦パスメモリ回路に記憶しておき、以上処理を所定期間（複数の時刻）に亘って、記憶させておく。そして、パスメモリ回路は、所定期間分の選択パスを記憶すると、その記憶した選択パスをトレースしてゆき、最も尤度の高いパスの連なりを探し出し、探し出したパスの連なりに基づき復号結果を出力する。
【０００６】
なお、トレースをする期間が長いほど復号結果にエラーは少なくなるが、メモリ容量及び計算能力にも限界があるため、一定の時間で打ち切りを行って復号結果を出力する。この時間のことを「打ち切り長」という。
【０００７】
ここで、パスメモリ回路のハードウェア実装に当たっては、ＲＡＭを用いてパス選択内容を記憶させ、それを時間を遡る方向にトレースして復号する方法が主流である（特許文献１，２，３参照。）。以下、この方法をトレースバック法と呼ぶ。
【０００８】
トレースバック法におけるトレースの動作を拘束長＝４の場合を例として説明する。図２２においてステート００１からトレースする場合を考える。ステート００１へ遷移の可能性のあるステートはステート０００とステート１００である。パスメモリ回路には、ステート０００側のパスを選んであったときには０、ステート１００側のパスを選んであったときには１（すなわち前ステートの最上位ビット）が記憶してある。また、どちらから遷移する場合も入力は１であり、これはステート００１の最下位ビットで表現されている。以上より、トレースの動作は以下のように行えばよい。
【０００９】
現在トレースを行っているステートの最下位ビットを復号ビットとし、次にトレースするステートの番号は現トレースステートの最上位ビットから下位２ビット目までに、パスメモリ内のビットを新たに最上位ビットとして付け加えることで生成する（図２３参照）。この動作によって最小ステートメトリックをとるステートから、選択されたパスを順次遡ることができる。
【００１０】
ビタビ復号装置を高速に動作させるためには、毎クロックごとにＲＡＭには１回しかアクセスできない。各ＲＡＭに対して１回のアクセスで復号を行うためのパスメモリの動作を、シングルポートのメモリを４つ使う場合を例として説明する。
【００１１】
符号の拘束長＝４とし打ち切り長を６とする。まず、ステート数分のビット数（いまの例では８ビット）と打ち切り長分のワード数（いまの例では６ワード）を持つシングルポートのＲＡＭを４つ用意する。パスメモリ回路には、パスの選択回路からステート数分のパス選択情報が、毎クロック入力される。４つのＲＡＭは以下の４つの役割を打ち切り長分のクロック（いまの例では６クロック）ごとに順次切り替える（図２４参照）。
【００１２】
（１）パス選択情報を順次書き込む 
（２）書き込まれたパス選択情報をもとに順次トレースする。復号は行わない 
（３）アクセス無し
（４）２でのトレース結果から順次トレースを行って復号ビットを出力する。
【００１３】
このオペレーションに基づくＲＡＭの動作を図２５に示す。
【００１４】
以上述べたメモリオペレーションによって、ＲＡＭを用いても高速な復号が可能なビタビ復号装置を構成することができる。
【００１５】
【特許文献１】特開２００４−１５３３１９号公報
【特許文献２】特開平１１−１８６９２０号公報
【特許文献３】特開２００１−１８６０２６号公報
【発明の開示】
【発明が解決しようとする課題】
【００１６】
ところで、トレースバック法を用いたビタビ復号装置では、消費電力の大半は、トレースの際のメモリからの読み出し時の電力であり、低消費電力化を図るには読み出し時の消費電力を少なくする必要があった。
【００１７】
本発明は、以上の事情に鑑みて提案されたものであり、パスメモリを備えたビタビ復号装置において、消費電力を小さくすることを目的とするものである。
【課題を解決するための手段】
【００１８】
本発明に係るビタビ復号装置は、畳み込み符号の復号を行うビタビ復号装置であって、畳み込み符号の各遷移状態に向かう２本のパスのうち一方のパスを選択パスとして、連続した複数の時点について記憶するパスメモリ部と、前記パスメモリ部に記憶されている選択パスを過去に遡る方向にトレースすることによって、所定の打ち切り長より前の各時点の畳み込み符号の復号を行うトレース部と、前記パスメモリ部を制御する制御部とを備え、前記パスメモリ部は、各時点における各遷移状態の選択パスを記憶する記憶領域が、遷移状態の最下位から所定桁のビット値毎に分割されているとともに、その分割領域毎にデータの読出休止が可能となっており、前記制御部は、各時点において選択パスの読み出しの必要がない分割領域を特定し、特定した分割領域に対して読出休止の制御を行うことを特徴とする。
【発明の効果】
【００１９】
本発明に係るビタビ復号装置では、パスメモリ部の記憶領域が、遷移状態を表すビット列の最下位から所定数桁毎に分割されているとともに、分割単位毎にデータの読出休止が可能となっている。ビタビ復号装置では、各時点において選択パスの読み出しの必要がない分割領域を特定し、特定した分割領域に対して読出休止の制御を行う。
【００２０】
このことにより本発明に係るビタビ復号装置では、トレース時における無駄なデータの読み出しを抑えることができ、消費電力を少なくすることができる。
【発明を実施するための最良の形態】
【００２１】
本発明を実施するための最良の形態として、本発明が適用されたビタビ復号装置について以下説明を行う。
【００２２】
ビタビ復号装置の全体構成
図１は、本発明が適用されたビタビ復号装置１０のブロック構成図である。
【００２３】
ビタビ復号装置１０は、図１に示すように、ブランチメトリック計算回路１１と、ＡＣＳ（Add Compare Select）回路１２と、正規化回路１３と、ステートメトリック記憶回路１４と、パスメモリ１５とを備えている。
【００２４】
ブランチメトリック計算回路１１には、受信信号が入力される。ブランチメトリック計算回路１１は、ある時点における受信信号と、畳み込み符号の各遷移状態の受信期待値とのハミング距離又はユークリッド距離を求め、求めたハミング距離又はユークリッド距離をその時点における各遷移状態のブランチメトリックとして出力する。
【００２５】
ＡＣＳ回路１２には、ブランチメトリック計算回路１１からブランチメトリックが供給されるとともに、ステートメトリック記憶回路１４からステートメトリック（それまでのそのパスに至るブランチメトリックの累積和を正規化したもの）が供給される。ＡＣＳ回路１２は、各遷移状態に至る２本のパスのそれぞれに対してブランチメトリックとステートメトリックとを加算して、２本のパスの加算値を比較をし、この比較結果に基づいて２本のパスのうち尤度の高いものを選択して、選択したパスの加算値をその遷移状態の新たなステートメトリックとする。ＡＣＳ回路１２から出力されたステートメトリックは、正規化回路１３に供給される。
【００２６】
さらに、ＡＣＳ回路１２は、その時点における各遷移状態に対して選択したパス（選択パス）と、その時点においての最尤遷移状態を示す最尤パス情報とを、パスメモリ回路１５に供給する。
【００２７】
正規化回路１３は、ＡＣＳ回路１２から出力された各遷移状態のステートメトリックが、予め規定された設定範囲内の値になるように正規化をする。例えば、各遷移状態のステートメトリックに対して、最小のステートメトリックを減算する方法などを用いて正規化する。正規化されたステートメトリックは、ステートメトリック記憶回路１４に供給される。
【００２８】
ステートメトリック記憶回路１４は、正規化回路１３から供給される正規化されたステートメトリックを記憶し、ＡＣＳ回路１２からの読み出しに応じて出力する。
【００２９】
パスメモリ回路１５は、ＡＣＳ回路１２から出力される選択パスを記憶する。それとともに、パスメモリ回路１５は、ＡＣＳ回路１２から出力される最尤パス情報に基づいて、記憶している選択パスを、時間を遡る方向にトレースし、打ち切り長以前の選択パスに応じた情報系列を復号して出力する。
【００３０】
パスメモリ回路１５の回路構成及び動作
つぎに、パスメモリ回路１５についてさらに詳細に説明をする。
【００３１】
（パスメモリ回路の構成）
図２は、パスメモリ回路１５のブロック構成図である。
【００３２】
パスメモリ回路１５は、選択パスを記憶する第１〜第４の４つのメモリユニット２１，２２，２３，２４と、選択パスのトレースを行うトレース回路２５と、当該パスメモリ回路１５の制御を行うコントロール回路２６と、復号結果を格納する出力バッファ２７とを有している。
【００３３】
パスメモリ回路１５には、ＡＣＳ回路１２から受信信号のサンプリングタイミング毎に選択パスが入力される。
【００３４】
選択パスは、畳み込み符号の各遷移状態に対して、それぞれ選ばれている。そのため、１時刻おいて選ばれる選択パスは、畳み込み符号の遷移状態の数だけある。例えば、拘束長＝７の畳み込み符号の場合、遷移状態は６４個あるので、ＡＣＳ回路１２からは６４個の選択パスが入力されることとなる。また、選択パスは、１ビット（０，１）で表されるため、パスメモリ回路１５には、ＡＣＳ回路１２から畳み込み符号の遷移状態の数のビット数（例えば、拘束長＝７の畳み込み符号であれば６４ビット）で表された選択パスが入力される。
【００３５】
第１〜第４のメモリユニット２１，２２，２３，２４には、選択パスが入力される。入力された選択パスは、４つのメモリユニット２１，２２，２３，２４のうち、コントロール回路２６からの書き込み制御信号により特定されたいずれか一つに書き込まれる。４つのメモリユニット２１，２２，２３，２４は、１クロック毎に巡回的に選択される。例えば、第１のメモリユニット２１ → 第２のメモリユニット２２ → 第３のメモリユニット２３ → 第４のメモリユニット２４ → 第１のメモリユニット２１→ 第２のメモリユニット２２ →  ……、といったような順序で選択パスが書き込まれる。
【００３６】
また、第１〜第４のメモリユニット２１，２２，２３，２４は、それぞれ上位ＲＡＭ２１-Ｈ，２２-Ｈ，２３-Ｈ，２４-Ｈと、下位ＲＡＭ２１-Ｌ，２２-Ｌ，２３-Ｌ，２４-Ｌとに分割されている。
【００３７】
上位ＲＡＭ２１-Ｈ，２２-Ｈ，２３-Ｈ，２４-Ｈは、全選択パス（例えば６４個）のうち上位の遷移状態についての選択パスを格納する。下位ＲＡＭ２１-Ｌ，２２-Ｌ，２３-Ｌ，２４-Ｌは、全選択パス（例えば６４個）のうち下位の遷移状態についての選択パスを格納する。
【００３８】
ここで、「上位の遷移状態」とは、畳み込み符号の遷移状態を表すビット列のうち、最下位のビットが“１”の遷移状態のことをいい、「下位の遷移状態」とは、畳み込み符号の遷移状態を表すビット列のうち、最下位のビットが“０”の遷移状態のことをいう。
【００３９】
畳み込み符号の遷移状態は、ある時刻の畳み込み符号器の記憶素子に記憶されているビットの状態に対応している。例えば、拘束長＝７の畳み込み符号であれば、その符号器は、図３に示すように、ｂ０，ｂ１，ｂ２，ｂ３，ｂ４，ｂ５の６個の記憶素子（遅延器）があるので、このｂ０，ｂ１，ｂ２，ｂ３，ｂ４，ｂ５の６個の記憶素子（遅延器）の内部のビット値が１であるか０であるかを示したものに対応することとなる。
【００４０】
すなわち、「上位の遷移状態」といった場合には、符号器の最終段の記憶素子（例えば、図３の例であればｂ５の記憶素子）の内部状態が“１”の遷移状態を示し、「下位の遷移状態」といった場合には、符号器の最終段の記憶素子（例えば、図３の例であればｂ５の記憶素子）の内部状態が“１”の遷移状態を示すこととなる。
【００４１】
このことから、拘束長＝７の畳み込み符号であれば、上位ＲＡＭ２１-Ｈ，２２-Ｈ，２３-Ｈ，２４-Ｈには、最下位の１ビットが“１”で表される３２個の遷移状態についての選択パスが書き込まれ、下位ＲＡＭ２１-Ｌ，２２-Ｌ，２３-Ｌ，２４-Ｌには、最下位の１ビットが“１”で表される３２個の遷移状態についての選択パスが書き込まれる。
【００４２】
各第１〜第４のメモリユニット２１，２２，２３，２４は、上位ＲＡＭと下位ＲＡＭとに分割されていることにより、それぞれ独立にデータの読み出し休止制御を行うことができる。すなわち、上位ＲＡＭ又は下位ＲＡＭのいずれか一方のみに対して読み出し休止制御を行うことが可能である。また、上位ＲＡＭ２１-Ｈ，２２-Ｈ，２３-Ｈ，２４-Ｈ、及び、下位ＲＡＭ２１-Ｌ，２２-Ｌ，２３-Ｌ，２４-Ｌは、それぞれ独立にコントロール回路２６からクロックインヒビット信号が供給される。上位ＲＡＭ２１-Ｈ，２２-Ｈ，２３-Ｈ，２４-Ｈ、及び、下位ＲＡＭ２１-Ｌ，２２-Ｌ，２３-Ｌ，２４-Ｌは、クロックインヒビット信号が供給されると、内部に記憶している情報の読み出しを休止する。
【００４３】
トレース回路２５は、第１〜第４のメモリユニット２１，２２，２３，２４に記憶されている選択パスを読み出して、最新の時刻の最尤パスから、時刻を遡る方向に各時刻の選択パスをトレースしてゆく。ここで、トレースとは、各時刻の遷移状態を、選択パスに従って辿ってゆく作業である。
【００４４】
トレース回路２５は、最新の時刻から一定の打ち切り長分の時刻をトレースし、さらに、打ち切り長以前の時刻の選択パスについてもトレースをする。そして、打ち切り長以前の時刻のトレース結果をコントロール回路２６に供給する。
【００４５】
コントロール回路２６は、第１〜第４のメモリユニット２１，２２，２３，２４に対して、入力された選択パスをいずれのメモリユニットに対して書き込むかを特定するための書き込み制御信号を与える。また、コントロール回路２６は、第１〜第４のメモリユニット２１，２２，２３，２４に対して、いずれのメモリユニットに記憶されている選択パスをトレース回路２５に出力するかを特定する読み出し制御信号を与える。
【００４６】
また、コントロール回路２６は、クロックインヒビット信号を発生して、第１〜第４のメモリユニット２１，２２，２３，２４の各上位ＲＡＭ及び下位ＲＡＭに対して、読み出しの休止制御を行う。
【００４７】
また、コントロール回路２６は、トレース回路２５により打ち切り長より前のトレース結果が入力されると、そのトレースされた選択パスの時間順序の並べ替えを行って情報ビットの復号を行い、出力バッファ２７に格納する。
【００４８】
出力バッファ２７は、コントロール回路２６から出力された復号された情報ビットを格納する。出力バッファ２７は、外部からの読み出し要求に従い、格納している情報ビットを出力する。
【００４９】
（書き込み及びトレース動作）
つぎに、パスメモリ回路１５の第１〜第４のメモリユニット２１，２２，２３，２４に対する選択パスの書き込み、並びに、トレース回路２５により行われるトレース動作について、図４〜図１８を参照して説明をする。
【００５０】
以下に説明する書き込み及びトレース動作は、１クロックで複数のメモリユニットにアクセスすることにより１クロックで複数の時刻に対するトレースをし、メモリ容量の削減を図ったものである。
【００５１】
なお、図４〜図１８の（Ａ）図は、第１〜第４のメモリユニット２１，２２，２３，２４に対する書き込み及び読み出しの状態を示している。また、図４〜図１８の（Ｂ）図は、トレリス線図を示している。
【００５２】
また、各第１〜第４のメモリユニット２１，２２，２３，２４は、上位ＲＡＭと下位ＲＡＭとに分割がされているのであるが、図４〜図１８では分割されている状態としては図示していない。ステートの上位と下位とで記憶領域が分割されていることの理由やメリットについては、トレース動作を説明した後に説明をする。
【００５３】
また、ここでは、説明を簡単にするため、復号する畳み込み符号の拘束長＝３の場合、すなわち、遷移状態（ステート）が４つの場合を例にとって説明をするが、本発明では拘束長が３のものに限られず適用できる。
【００５４】
まず、パスメモリ回路１５には、１クロック毎に選択パスが入力される。入力される選択パスは、その時刻における全てのステート（拘束長＝３であれば４つのステート、拘束長＝７であれば６４個のステート）の選択パスである。
【００５５】
コントロール回路２６は、４つのメモリユニット２１〜２４のうちいずれか一つのメモリユニットに対して選択パスが書き込まれるように書き込み制御信号を発生する。選択パスが書き込まれるメモリユニットは、１クロック毎に切り換えられ、４つのメモリユニットが巡回的に選択される。
【００５６】
例えば、次のように書き込みが行われることとなる。
【００５７】
まず、時刻１では、図４に示すように、時刻１の各ステートの選択パスが第１のメモリユニット２１に書き込まれる。続く時刻２では、図５に示すように、時刻２の各ステートの選択パスが、第２のメモリユニット２２に書き込まれる。続く時刻３では、図６に示すように、時刻３の各ステートの選択パスが、第３のメモリユニット２３に書き込まれる。続く時刻４では、図７に示すように、時刻４の各ステートの選択パスが、第４のメモリユニット２４に書き込まれる。
【００５８】
さらに、続く時刻５では、図８に示すように、時刻５の時点の各ステートの選択パスが、第１のメモリユニット２１に戻り書き込まれる。
【００５９】
以後、図９，図１０，図１１，図１２に示すように、各時刻の各ステートの選択パスが、第２のメモリユニット２２→第３のメモリユニット２３→第４のメモリユニット２４→第１のメモリユニット２１→といったように順番に書き込みが行われていく。
【００６０】
つぎに、パスメモリ回路１５は、打ち切り長分のより多くの選択パスを記憶すると、その次の時刻からトレースを開始することができる。
【００６１】
トレースは、トレース開始時刻から過去に遡る方向に、各時点の選択パスをメモリユニットから読み出して行う。
【００６２】
このとき、メモリユニットが複数ありそれらに順番に選択パスが記憶されているので、同時に複数の時点の選択パスを読み出すことができる。もっとも、必ず１つのメモリユニットは現在の選択パスの書き込み中となるので、メモリユニットの総数−１個の時点の選択パスの読み出しが可能となる。本例であれば、４つのメモリユニットがあるので、書き込みを行っているメモリユニット以外の３つのメモリユニットから同時に選択パスを読み出すことができる。
【００６３】
具体的には、次のように読み出しが行われることとなる。
【００６４】
まず、時刻１０では、図１３に示すように、時刻１０の各ステートの選択パスが第２のメモリユニット２２に書き込まれる。それと同時に、トレース回路２５は、第１，第４及び第３のメモリユニット２１，２４，２３から、時刻９，時刻８，時刻７の選択パスを読み出し、時刻９の時点における最尤パス情報を開始ステートとして、時刻９→時刻８→時刻７といったように時間を遡る方向に選択パスをトレースしてゆく。
【００６５】
続く時刻１１では、図１４に示すように、時刻１１の各ステートの選択パスが第３のメモリユニット２３に書き込まれる。それと同時に、トレース回路２５は、第２，第１及び第４のメモリユニット２２，２１，２４から、時刻６，時刻５，時刻４の選択パスを読み出し、先の時刻７のトレース結果に続けて、時刻６→時刻５→時刻３といったように時間を遡る方向に選択パスをトレースしてゆく。
【００６６】
この結果、時刻９，８，７，６，５，４とトレースが行われ、打ち切り長分のトレースが完了したこととなる。
【００６７】
続く時刻１２では、図１５に示すように、時刻１２の各ステートの選択パスが第４のメモリユニット２４に書き込まれる。それと同時に、トレース回路２５は、第３，第２及び第１のメモリユニット２３，２２，２１から、時刻３，時刻２，時刻１の選択パスを読み出し、先の時刻４のトレース結果に続けて、時刻３→時刻２→時刻１といったように時間を遡る方向に選択パスをトレースしてゆく。
【００６８】
時刻３，２，１のトレース結果は、打ち切り長より前の時点の選択パスのトレース結果である。従って、トレース回路２５は、時刻３、２、１のトレース結果をコントロール回路２６に供給する。コントロール回路２６は、時刻３，２，１のトレース結果で特定された各ステートの最下位ビットを時間順に並べ替えを行うことにより復号を行い、復号結果をバッファ回路２７に格納する。
【００６９】
時刻１３以降は、図１６、図１７及び図１８に示すように、選択パスの書き込み処理及びトレース（及び復号）が繰り返し行われ、復号が進行していく。
【００７０】
以上のように、パスメモリ回路１５では、トレースバック方式で選択パスのトレース及び復号を行う際に、１クロックで複数の時点の選択パスを読み出すことができるので、メモリ容量の削減を図ることができる。
【００７１】
具体的には、各第１〜第４のメモリユニット２１，２２，２３，２４の容量は、打ち切り長の１／２の時点の選択パスが格納できる容量があればよい。すなわち、打ち切り長が６であれば、各第１〜第４のメモリユニット２１，２２，２３，２４は、少なくとも３ワード分の選択パスが格納できる容量を有していればよい。
【００７２】
（メモリの分割による読み出し時の電力削減）
つぎに、パスメモリ回路１５の第１〜第４のメモリユニット２１，２２，２３，２４に対する読み出し時の電力削減方法について説明をする。
【００７３】
各第１〜第４のメモリユニット２１，２２，２３，２４は、最下位ビットが“１”とされたステートの選択パスが格納される領域（上位ＲＡＭ）と、最下位ビットが“０”とされたステートの選択パスが格納される領域（下位ＲＡＭ）とに分割されている。
【００７４】
選択パスのトレース（及び復号）の際に必要となる選択パスは、複数のステート（拘束長＝３であれば４個のステート、６４個のステート拘束長＝７であれば６４個のステート）のうちの、１つのステートについての選択パスのみである。従って、上位ＲＡＭ又は下位ＲＡＭのいずれか一方にのみ、トレース（及び復号）に必要な選択パスが含まれており、他方には必要な選択パスが含まれていない。
【００７５】
そこで、パスメモリ回路１５では、トレース（及び復号）する際に各メモリユニットから選択パスを読み出す際に、上位ＲＡＭ又は下位ＲＡＭの読み出しに必要とならない一方に対してコントロール回路２６からクロックインヒビット信号を供給して、読み出しの休止制御を行うようにしている。
【００７６】
クロックインヒビット信号が入力されたＲＡＭは読出しが行われないため、出力されるパス選択情報は全く参照不能な信号となり、クロックインヒビット信号が入力されたＲＡＭの各ステートの選択パスはトレースの対象とならないため、復号結果には何ら影響を与えない。しかし、ＲＡＭの読出しビット数は全体としてみて半分に減るため、ＲＡＭ読出しに消費される電力が約半分に低減される。
【００７７】
例えば、上述の例で説明した時刻１０の時には、図１９（Ａ），（Ｂ）に示すように、第１のメモリユニット２１については、時刻９についてのステート“００”の選択パスを読み出すので、下位ＲＡＭ２１-Ｌのみを動作させ、上位ＲＡＭ２１-Ｈの読み出しを停止させる。第４のメモリユニット２４については、時刻８についてのステート“０１”の選択パスを読み出すので、下位ＲＡＭ２４-Ｌの読み出しを停止させ、上位ＲＡＭ２４-Ｈのみを動作させる。第３のメモリユニット２３については、時刻７についてのステート“１０”の選択パスを読み出すので、下位ＲＡＭ２３-Ｌのみを動作させ、上位ＲＡＭ２３-Ｈの読み出しを停止させる。
【００７８】
なお、時刻１０の時には、第２のメモリユニット２２に対して選択パスが書き込まれているので、第２のメモリユニット２２については読み出しの停止制御は行わない。
【００７９】
ここで、上位ＲＡＭ又は下位ＲＡＭのどちら側が休止できるのか（すなわち、トレースの時にどちらのＲＡＭから選択パスを読み出すか）については、次のように判断をすることができる。
【００８０】
デジタル放送で広く使われる拘束長＝７の畳み込み符号器（図３参照。）は、６つの記憶素子（遅延器）から構成されるシフトレジスタを有している。各記憶素子のそれぞれの記憶内容（０又は１）をｂ０、ｂ１、ｂ２、ｂ３、ｂ４、ｂ５で表すことにすると、畳み込み符号のステートはこれらｂ０〜ｂ５を用いて｛ｂ５，ｂ４，ｂ３，ｂ２，ｂ１，ｂ０｝と表すことができる。畳み込み符号のステートは、｛０，０，０，０，０，０｝から｛１，１，１，１，１，１｝までの全６４通りを取り得る。
【００８１】
パスメモリ回路１５では、１クロックの間に３時刻分のトレースを行なうが、トレース開始時刻でのステートを｛ｂ５，ｂ４，ｂ３，ｂ２，ｂ１，ｂ０｝とすると、トレース開始時刻の１時刻前にトレースされる可能性があるステートは｛０，ｂ５，ｂ４，ｂ３，ｂ２，ｂ１｝又は｛１，ｂ５，ｂ４，ｂ３，ｂ２，ｂ１｝の２通りである。さらに、トレース開始時刻の２時刻前にトレースされる可能性があるステートは｛０，０，ｂ５，ｂ４，ｂ３，ｂ２｝、｛０，１，ｂ５，ｂ４，ｂ３，ｂ２｝、｛１，０，ｂ５，ｂ４，ｂ３，ｂ２｝または、｛１，１，ｂ５，ｂ４，ｂ３，ｂ２｝の４通りである。
【００８２】
つまり、図２０に示すように、トレース開始時刻に対してトレース（又は復号）する際には、当該トレース開始時刻のステートの最下位ビットｂ０が１であれば上位ＲＡＭに必要な選択パスが記憶されており、最下位ビットｂ０が０であれば下位ＲＡＭに必要な選択パスが記憶されている。従って、トレース開始時刻に対してトレース（又は復号）する際には、トレース開始時刻のステートの最下位ビットｂ０が１であれば下位ＲＡＭを休止させ、最下位ビットｂ０が０であれば上位ＲＡＭを休止させることができる。
【００８３】
また、トレース開始時刻の１時刻前に対してトレース（又は復号）する際には、トレース開始時刻のステートの下位から２ビット目ｂ１が１であれば上位ＲＡＭに必要な選択パスが記憶されており、下位から２ビット目ｂ１が０であれば下位ＲＡＭに必要な選択パスが記憶されている。従って、トレース開始時刻の１時刻前に対してトレース（又は復号）する際には、トレース開始時刻のステートの下位から２ビット目ｂ１が１であれば、下位ＲＡＭを休止させ、下位から２ビット目ｂ１が０であれば上位ＲＡＭを休止させることができる。
【００８４】
また、トレース開始時刻の２時刻前に対してトレース（又は復号）する際には、トレース開始時刻のステートの下位から３ビット目ｂ２が１であれば上位ＲＡＭに必要な選択パスが記憶されており、下位から３ビット目ｂ２が０であれば下位ＲＡＭに必要な選択パスが記憶されている。従って、トレース開始時刻の２時刻前に対してトレース（又は復号）する際には、トレース開始時刻のステートの下位から３ビット目ｂ１が１であれば、下位ＲＡＭを休止させ、下位から２ビット目ｂ１が０であれば上位ＲＡＭを休止させることができる。
【００８５】
従って、コントロール回路２６は、トレース開始時刻における最尤パスのステートの下位ビットに応じて、上位ＲＡＭ又は下位ＲＡＭについての読み出しの休止制御を行うことができる。
【００８６】
以上の例は、拘束長＝７の場合を例としたが、拘束長はこの値に限らず任意の値とすることができる。
【００８７】
また以上の例では、１クロックで複数時刻のトレースを行えるようにメモリユニットを４つにした例を示したが、選択パスを記憶するメモリを上位及び下位に分割して読み出し時の電力削減を行う手法は、トレースバック法に基づいたあらゆるパスメモリ回路に同様に適応可能である。
【００８８】
また以上の例では、１時刻分のパス選択情報を、ステートの最下位ビットで上位と下位に２分割した例を示したが、ステートの最下位ビットから所定数分のビットの内容に応じて、４分割、８分割にして読み出し時の休止をすることも可能である。
【００８９】
また以上の例では、クロックインヒビット信号を用いてＲＡＭを休止する場合を例としたが、ゲーティドクロックによってクロックそのものを止めてしまうなど種々の変形が可能である。
【図面の簡単な説明】
【００９０】
【図１】本発明が適用されたビタビ復号装置のブロック構成図である。
【図２】パスメモリ回路のブロック構成図である。
【図３】拘束長＝７の畳み込み符号化器の回路図である。
【図４】（Ａ）は、時刻１の時のメモリユニットへの書き込み及び読み出し状態を示す図であり、（Ｂ）は、時刻１の時のトレリス線図を示す図である。
【図５】（Ａ）は、時刻２の時のメモリユニットへの書き込み及び読み出し状態を示す図であり、（Ｂ）は、時刻２の時のトレリス線図を示す図である。
【図６】（Ａ）は、時刻３の時のメモリユニットへの書き込み及び読み出し状態を示す図であり、（Ｂ）は、時刻３の時のトレリス線図を示す図である。
【図７】（Ａ）は、時刻４の時のメモリユニットへの書き込み及び読み出し状態を示す図であり、（Ｂ）は、時刻４の時のトレリス線図を示す図である。
【図８】（Ａ）は、時刻５の時のメモリユニットへの書き込み及び読み出し状態を示す図であり、（Ｂ）は、時刻５の時のトレリス線図を示す図である。
【図９】（Ａ）は、時刻６の時のメモリユニットへの書き込み及び読み出し状態を示す図であり、（Ｂ）は、時刻６の時のトレリス線図を示す図である。
【図１０】（Ａ）は、時刻７の時のメモリユニットへの書き込み及び読み出し状態を示す図であり、（Ｂ）は、時刻７の時のトレリス線図を示す図である。
【図１１】（Ａ）は、時刻８の時のメモリユニットへの書き込み及び読み出し状態を示す図であり、（Ｂ）は、時刻８の時のトレリス線図を示す図である。
【図１２】（Ａ）は、時刻９の時のメモリユニットへの書き込み及び読み出し状態を示す図であり、（Ｂ）は、時刻９の時のトレリス線図を示す図である。
【図１３】（Ａ）は、時刻１０の時のメモリユニットへの書き込み及び読み出し状態を示す図であり、（Ｂ）は、時刻１０の時のトレリス線図を示す図である。
【図１４】（Ａ）は、時刻１１の時のメモリユニットへの書き込み及び読み出し状態を示す図であり、（Ｂ）は、時刻１１の時のトレリス線図を示す図である。
【図１５】（Ａ）は、時刻１２の時のメモリユニットへの書き込み及び読み出し状態を示す図であり、（Ｂ）は、時刻１２の時のトレリス線図を示す図である。
【図１６】（Ａ）は、時刻１３の時のメモリユニットへの書き込み及び読み出し状態を示す図であり、（Ｂ）は、時刻１３の時のトレリス線図を示す図である。
【図１７】（Ａ）は、時刻１４の時のメモリユニットへの書き込み及び読み出し状態を示す図であり、（Ｂ）は、時刻１４の時のトレリス線図を示す図である。
【図１８】（Ａ）は、時刻１５の時のメモリユニットへの書き込み及び読み出し状態を示す図であり、（Ｂ）は、時刻１５の時のトレリス線図を示す図である。
【図１９】（Ａ）は、メモリユニットを上位ＲＡＭ及び下位ＲＡＭに分割して、読み出し時の休止制御を行っている状態を示す図であり、（Ｂ）は、その時のトレリス線図を示す図である。
【図２０】読み出しの休止を行うＲＡＭを選択するために参照するビット位置を示した図である。
【図２１】拘束長＝４の場合の畳み込み符号の遷移ダイアグラムを示す図である。
【図２２】トレースバック法におけるトレースの原理を示した図である。
【図２３】図２２に続くトレースの原理を示した図である。
【図２４】従来のトレースバック法における各ＲＡＭの役割を示した図である。
【図２５】従来のトレースバック法におけるメモリオペレーションの例を示した図である。
【符号の説明】
【００９１】
１０  ビタビ復号装置、１５  パスメモリ回路、２１，２２，２３，２４  メモリユニット、２５  トレース回路、２６  コントロール回路、２７  出力バッファ
【図１】
0004600183.tif 000002
【図２】
0004600183.tif 000003
【図３】
0004600183.tif 000004
【図４】
0004600183.tif 000005
【図５】
0004600183.tif 000006
【図６】
0004600183.tif 000007
【図７】
0004600183.tif 000008
【図８】
0004600183.tif 000009
【図９】
0004600183.tif 000010
【図１０】
0004600183.tif 000011
【図１１】
0004600183.tif 000012
【図１２】
0004600183.tif 000013
【図１３】
0004600183.tif 000014
【図１４】
0004600183.tif 000015
【図１５】
0004600183.tif 000016
【図１６】
0004600183.tif 000017
【図１７】
0004600183.tif 000018
【図１８】
0004600183.tif 000019
【図１９】
0004600183.tif 000020
【図２０】
0004600183.tif 000021
【図２１】
0004600183.tif 000022
【図２２】
0004600183.tif 000023
【図２３】
0004600183.tif 000024
【図２４】
0004600183.tif 000025
【図２５】
0004600183.tif 000026