(57)【要約】　【課題】　ビタビ復号器において、一般のＲＡＭ等のメモリをパスメトリック記憶部とパス選択信号記憶部に用い、ＡＣＳ演算とトレースバック演算のメモリアクセス回数を減らして、消費電力を低減すると共に処理動作の高速化を図る。　【解決手段】　パス選択信号記憶部１０６から読み出した過去のパス選択信号を使用して過去の状態遷移を探索し、復号データを出力するトレースバック演算部１０７に、パス選択信号記憶部１０６より得られるパス選択信号に基づいて、生き残りパスに従ったビタビステートを格納するシフトレジスタ３０４と、次に更新されるビタビステートの一部を予測するビタビステート予測部３０５とを備えた。【選択図】　図３
2004120791.tif 000002
【特許請求の範囲】
【請求項１】
　パス選択信号を記憶するパス選択信号記憶手段と、
　前記パス選択信号記憶手段から読み出した過去のパス選択信号を使用して過去の状態遷移を探索し、復号データを出力するトレースバック演算手段とを備え、
　前記トレースバック演算手段は、
　　前記パス選択信号記憶手段より得られるパス選択信号に基づいて、生き残りパスに従ったビタビステートを格納するビタビステート格納手段と、
　　前記ビタビステート格納手段の内容に基づいて、次に更新されるビタビステートの一部を予測するビタビステート予測手段と、
　　前記ビタビステート予測手段により予測されたビタビステートの一部に基づいて、前記パス選択信号が記憶されている前記パス選択信号記憶手段のアドレスを算出するパス選択信号記憶アドレス算出手段とを備えたことを特徴とするビタビ復号器。
【請求項２】
　前記ビタビステート予測手段は、
　前記パス選択信号記憶手段の読み出し制御信号と前記ビタビステート格納手段のシフト制御信号とによって状態を変化させるアップダウンカウンタと、
　前記アップダウンカウンタの値に従って、前記ビタビステート格納手段の内容と次に更新されるビタビステートの一部との対応を変化させるセレクタを備えたことを特徴とする請求項１記載のビタビ復号器。
【請求項３】
　前記ビタビステート予測手段により予測されたビタビステートの一部に基づいて、前記パス選択信号記憶アドレス算出手段がアドレスを算出する過程、該算出したアドレスに基づいて、前記パス選択信号記憶手段のパス選択信号を読み出す過程、および該読み出したパス選択信号に基づいて、生き残りパスに従ったビタビステートを前記ビタビステート格納手段に格納する過程の少なくとも一つの過程においてパイプライン処理を使用することを特徴とする請求項１記載のビタビ復号器。
【発明の詳細な説明】
【技術分野】
【０００１】
　本発明は、畳み込み符号の最尤復号に用いられるビタビ復号器に関するものである。
【背景技術】
【０００２】
　ビタビ（Viterbi）復号器は、畳み込み符号の最尤復号法に使用されるものであり、入力符号系列が取り得る既知の複数個の符号系列のうち、畳み込み符号器が発生した符号系列に最も符号距離が近い符号系列を最尤符号系列（最尤パス）として選択し、この選択した情報に基づいて復号データを得るものである。ビタビ復号は、通信路に生じるランダム誤りに対する訂正能力が高く、軟判定復号方式と組み合わせると、特に大きな符号化利得を得ることができる。例えば、干渉波の影響を受けやすく、ビットエラーが通信品質に著しい影響を与える移動体通信システムでは、誤り訂正符号として畳み込み符号が用いられており、その復号にビタビ復号が用いられている。
【０００３】
　このビタビ復号アルゴリズムについて簡単に説明する。例えば生成多項式が以下の式で与えられる符号化率Ｒ＝１／２、拘束長Ｋ＝３の畳み込み符号を考える。
【０００４】
（数１）
　　　Ｇ０（Ｄ）＝１＋Ｄ2
　　　Ｇ１（Ｄ）＝１＋Ｄ＋Ｄ2
　図９に、このような符号を発生する畳み込み符号器の構成例を示す。図９において、入力データである情報ビットは、２個のフリップフロップ等の遅延素子９０１、９０２により順次遅延され、加算器９０３により入力データと遅延素子９０２からのデータが加算されて出力Ｇ０として取り出され、加算器９０４、９０５により、それぞれ、入力データと遅延素子９０１からのデータ、加算器９０４からのデータと遅延素子９０２からのデータが加算されて出力Ｇ１として取り出される。
【０００５】
　このような符号器における各遅延素子９０１、９０２の内容をそれぞれＳ［１］、Ｓ［０］とするとき、符号器の状態Ｓ［１：０］としては、（００）、（０１）、（１０）、（１１）の４つの状態が取り得る。また、入力が与えられた時の遷移し得る状態はつねに２通りとなる。
【０００６】
　すなわち、入力が０のとき、現在の状態が（００）または（０１）の場合に状態（００）に遷移し、現在の状態が（１０）または（１１）の場合に状態（０１）に遷移する。入力が１のときには、現在の状態が（００）または（０１）の場合に状態（１０）に遷移し、現在の状態が（１０）または（１１）の場合に状態（１１）に遷移する。
【０００７】
　このような状態遷移を示す手法としてトレリス線図があり、トレリス線図で示すと図１０のようになる。図１０において、実線の矢印（ブランチ）は入力０の時の遷移を示し、破線のブランチは入力１の時の遷移を示す。また、各ブランチに沿って記されている数字は、そのブランチの遷移が生じたときに出力される図１の符号（Ｇ０，Ｇ１）である。
【０００８】
　図１０から明らかなように、各状態への遷移時には、必ず２つのブランチが合流する。ビタビ復号アルゴリズムにおいては、各状態への２つのブランチのうち、最尤（最も確からしい）ブランチの組み合わせ（パス）を選択し、選択されたパス（生き残りパス）の情報（パス選択信号）を記憶手段に格納する。そして所定長までパスの選択を行ったのち、パス選択信号記憶手段の内容に基づいて最尤の生き残りパスを探索（トレースバック）する。このトレースバックによって得られる最尤の各状態の変化より畳み込み符号器に入力された情報を復号する。
【０００９】
　このようなビタビアルゴリズムに基づいて畳み込み符号を復号するビタビ復号器は、基本的に、送信符号系列と各ブランチで予測される符号系列との符号距離（ブランチメトリック）を計算するブランチメトリック計算手段と、各状態へのブランチメトリックの累算値（パスメトリック）を計算し、生き残りパスを選択するＡＣＳ（ADD、COMPARE、SELECT＝加算、比較、選択）演算手段と、各ステートでのパスメトリックを記憶するパスメトリック記憶手段と、選択したパスの情報を記憶するパス選択信号記憶手段と、パス選択信号記憶手段の内容に基づいて最尤の生き残りパスを探索するトレースバック手段とから構成される。
【００１０】
　ここで、上記ＡＣＳ演算手段においては、いわゆるパスメトリック・トランジション・ダイアグラムに従って、各ステートでの生き残りパスが選択され、この生き残りパスのパスメトリックが計算される。このパスメトリック・トランジション・ダイアグラムは、図１０に示すようなトレリス線図を基にして作成される。
【００１１】
　図１０に示すようなトレリス線図で示される符号が用いられている場合には、図１１（ａ）、図１１（ｂ）に示すようなパスメトリック・トランジション・ダイアグラムとなる。すなわち、図１０に示すトレリス線図の場合、状態（００）で合流するのは、状態（００）から符号（００）を出力して生じるパスと、状態（０１）から符号（１１）を生じるパスの２通りである。従って、今回の状態（００）でのパスメトリックＰＭ００（ｎｅｗ）は、前時刻のステートのパスメトリックをＰＭ００（ｏｌｄ）、ＰＭ１０（ｏｌｄ）、ブランチメトリックをＢＭ００、ＢＭ１１のように表すと、以下の２つの式のいずれかとなる。
【００１２】
（数２）
　　　ＰＭ００（ｎｅｗ）ａ＝ＰＭ００（ｏｌｄ）＋ＢＭ００
　　　ＰＭ００（ｎｅｗ）ｂ＝ＰＭ０１（ｏｌｄ）＋ＢＭ１１
　すなわち、ＡＣＳ演算途中の２つのパスメトリックＰＭ００（ｎｅｗ）ａ、ＰＭ００（ｎｅｗ）ｂの最尤の値が選択され、そのパスメトリックが、今回の状態（００）のパスメトリックＰＭ００（ｎｅｗ）として決定される。
【００１３】
　また、状態（１０）で合流するのは、状態（００）から符号（１１）を出力して生じるパスと、状態（０１）から符号（００）を生じるパスの２通りである。従って、今回のパスメトリックＰＭ１０（ｎｅｗ）は、以下の２つの式のいずれかとなる。
【００１４】
（数３）
　　　ＰＭ１０（ｎｅｗ）ａ＝ＰＭ００（ｏｌｄ）＋ＢＭ１１
　　　ＰＭ１０（ｎｅｗ）ｂ＝ＰＭ０１（ｏｌｄ）＋ＢＭ００
　また、状態（０１）で合流するのは、状態（１０）から符号（０１）を出力して生じるパスと、状態（１１）から符号（１０）を生じるパスの２通りである。従って、今回のパスメトリックＰＭ０１（ｎｅｗ）は、以下の２つの式のいずれかとなる。
【００１５】
（数４）
　　　ＰＭ０１（ｎｅｗ）ａ＝ＰＭ１０（ｏｌｄ）＋ＢＭ０１
　　　ＰＭ０１（ｎｅｗ）ｂ＝ＰＭ１１（ｏｌｄ）＋ＢＭ１０
　また、状態（１１）で合流するのは、状態（１０）から符号（１０）を出力して生じるパスと、状態（１１）から符号（０１）を生じるパスの２通りである。従って、今回のパスメトリックＰＭ１１（ｎｅｗ）は、以下の２つの式のいずれかとなる。
【００１６】
（数５）
　　　ＰＭ１１（ｎｅｗ）ａ＝ＰＭ１０（ｏｌｄ）＋ＢＭ１０
　　　ＰＭ１１（ｎｅｗ）ｂ＝ＰＭ１１（ｏｌｄ）＋ＢＭ０１
　このことに基づいて、図１１（ａ）、図１１（ｂ）に示すようなパスメトリック・トランジション・ダイアグラムを作ることができる。
【００１７】
　ここで、上式と図１１のパスメトリック・トランジション・ダイアグラムから分かる様に、ＰＭ００（ｎｅｗ）とＰＭ１０（ｎｅｗ）の違いは、ＰＭ００（ｏｌｄ）とＰＭ０１（ｏｌｄ）にＢＭ１１とＢＭ００を加算する場合におけるＰＭｘｘ（ｏｌｄ）とＢＭｘｘの対応のみである。
【００１８】
　また、ＰＭ０１（ｎｅｗ）とＰＭ１１（ｎｅｗ）の違いについても同様に、ＰＭ１０（ｏｌｄ）とＰＭ１１（ｏｌｄ）にＢＭ０１とＢＭ１０を加算する場合におけるＰＭｘｘ（ｏｌｄ）とＢＭｘｘの対応のみである。
【００１９】
　さらに、それぞれ２つのＰＭｘｘ（ｏｌｄ）は連続する偶数、奇数ステートという関係を持っており、ＰＭｘｘ（ｎｅｗ）は最上ビットのみが異なる上位、下位ステートという関係を持っている。
【００２０】
　これらのことは、連続する偶数、奇数ステートの関係を持つ２つのＰＭｘｘ（ｏｌｄ）と２つのＢＭｘｘより、上位、下位ステートの関係を持つ２つのＰＭｘｘ（ｎｅｗ）を算出可能であることを示している（例えば、特許文献１参照）。
【００２１】
　次に、パス選択信号と各状態遷移について説明する。上記説明において今回の状態に決定されるべきパスメトリックの組は、それぞれ前時刻において状態の最下位ビットのみが異なるという関係になっている。そこで、各状態の最尤パスメトリック選択情報（パス選択信号）をＰＳ００（ｎｅｗ）、ＰＳ０１（ｎｅｗ）、ＰＳ１０（ｎｅｗ）、ＰＳ１１（ｎｅｗ）とし、その値とパスメトリック選択との関係を以下の様にする。
【００２２】
（数６）
　　　ＰＳｘｘ（ｎｅｗ）＝０　→　ＰＭｘｘ（ｎｅｗ）ａを選択
　　　ＰＳｘｘ（ｎｅｗ）＝１　→　ＰＭｘｘ（ｎｅｗ）ｂを選択このとき、ＰＳｘｘ（ｎｅｗ）の値は、対応する前時刻における状態の最下位ビットの値と同じになる。
【００２３】
　つまり、時刻ｎにおける状態をＳ（ｎ）、状態Ｓにおけるパス選択信号をＰＳ（Ｓ）とすると時刻ｎ−１、時刻ｎにおけるそれぞれの状態、及びパス選択信号の関係は以下の様になる。
【００２４】
（数７）
　　　Ｓ（ｎ−１）＝｛Ｓ（ｎ），ＰＳ（Ｓ）｝ここで、｛ａ，ｂ｝はａの最下位ビット側にｂを連接し、ａの最上位ビット側をｂのビット幅分削除するという演算を表す。
【００２５】
　これらのことは、あるステートのパス選択信号から、そのステートに到達した前回のステートを決定できることを示している。
【００２６】
　上式より、パス選択信号が所定の量だけ格納された状態において、時刻ｎにおける最尤の状態を決定すれば、各時刻のパス選択信号の値から過去に選択された状態を決定することができる。この演算をトレースバックと呼び、その一例を図１２に示す。
【００２７】
　なお、時刻ｎにおける最尤の状態を決定するために、畳み込み符号の系列を終了する際に符号器の状態を所定の値（例えば００等）に収束するように情報ビットに付加ビット（Tailbit）を追加するという手法を取る場合がある。
【００２８】
　冒頭に述べた様に、畳み込み符号器の状態の遷移は、情報ビットが逐次遅延素子に入力されることによって発生するため、この状態の遷移を過去に溯って決定するということは、そのまま情報ビットを決定するということを意味する。
【００２９】
　上記過程を経て、ビタビ復号によって、受信符号系列より情報ビットを復号することが実現できる。
【特許文献１】特開平９−２３２９７３号公報
【発明の開示】
【発明が解決しようとする課題】
【００３０】
　ところで、従来のビタビ復号器において、ＡＣＳ演算を時分割処理で行い、かつＡＣＳ演算の結果から得られたパスメトリックを記憶するパスメトリックメモリにＲＡＭ（Random Access Memory）を使用するものが知られている。このようなビタビ復号器では、ＡＣＳ演算の結果から得られた次の時刻でＡＣＳ演算に使用するパスメトリックをＲＡＭの１アドレスに割り当てている。すなわち１つのステートのパスメトリックを１つのＲＡＭの１アドレスに配置している。
【００３１】
　この場合、１回のＡＣＳ演算では、過去の２つのステートのパスメトリックから新しいパスメトリックを作成することから、過去の２つのパスメトリックを読み出して新しい１つのパスメトリックを書き込むために、１回のＡＣＳ演算当たり３回のメモリアクセスが必要とされる。ここで、いわゆるデュアルポートＲＡＭを使用して、書き込みと読み出しを分離し並列的に行う様にしても、読み出しが２回必要となる。このため、メモリアクセス回数が多くなり、高速のＲＡＭが必要とされ、低消費電力化や高速化の障害となっている。
【００３２】
　さらに工夫を加えた手法として、特開平９−２３２９７３号公報には、先述した、連続する偶数、奇数ステートの関係を持つ２つのＰＭｘｘ（ｏｌｄ）と２つのＢＭｘｘより、上位、下位ステートの関係を持つ２つのＰＭｘｘ（ｎｅｗ）を算出可能であることを用いて、２つのパスメトリックを読み出し、２つのパスメトリックを算出するという計算手法が開示されている。この手法では、パスメトリックの上位、下位用にメモリを２個設け、さらに、パスメトリックの連続する偶数、奇数を同時に読み出す仕組みを設けることで、１回の読み出し、１回の書き込みで２つのパスメトリックを算出することができる。
【００３３】
　しかしながら、この手法では、ＡＣＳ演算を行うために２つのパスメトリックメモリを用意する必要がある。一般に同じ容量のメモリを作成する場合、メモリを分割すれば回路規模、面積が増加し、低消費電力化にも不利となる。
【００３４】
　次に、トレースバックについて説明する。先述した、あるステートのパス選択信号から、そのステートに到達した前回のステートを決定できることから、パス選択信号を格納したメモリ（パス選択信号記憶部）の１アドレスにｎステート分のパス選択信号を格納する（例えば、１６ステート＝１ワード）ようにし、トレースバックを実行する場合、図１３（ａ）に示すような構成となる。
【００３５】
　この構成で重要な点は、ビタビステートからパス選択信号記憶部のアドレスが決定され、さらに、読み出されたパス選択信号より次のビタビステートが決定できるということである。すなわち、１処理単位（サイクル）の間にアドレス決定、メモリ読み出しを行わなければならない。ここで、メモリの動作遅延は一般に図１３（ｂ）で表される。まず、遅延Ａで示されるアドレスの配線遅延、次に、遅延Ｃで示されるメモリの出力遅延およびデータの配線遅延がある。そしてこれらの動作遅延は一般的に大きい。
【００３６】
　そこで、トレースバック動作速度の上限は、図１３（ｃ）に示すようにして決定される。先述した遅延Ａ、遅延Ｃに加え、パス選択信号記憶部から読み出された１ワードから１ステート分のパス選択信号を取り出すためのセレクタに関する遅延Ｂ、遅延Ｄがあり、ビタビステートを格納するシフトレジスタのセットアップ時間を考慮して、以下の２つの遅延のうち、大きな方の遅延によって動作速度の上限が決定される。
【００３７】
　（１）パス選択信号記憶部を中心とした遅延：遅延Ａ＋遅延Ｃ＋遅延Ｄ
　（２）セレクタを中心とした遅延：遅延Ｂ＋遅延Ｄ上記から、パス選択信号記憶部を中心とした遅延のほうが大きく、そのために動作速度が制限を受け、高速なトレースバックが困難となっている。
【００３８】
　この問題を解決するために、パス選択信号記憶部にレジスタファイルを用いるなどして高速動作を行う手法もあるが、回路規模、面積が増加し、低消費電力化にも不利となる。
【００３９】
　本発明は、上述した実情に鑑みてなされたものであり、一般のＲＡＭ等のメモリをパスメトリック記憶部とパス選択信号記憶部に用いながら、メモリアクセス回数を減らしたＡＣＳ演算と高速動作のトレースバック演算を行い、低消費電力化や、ビタビ復号動作の高速化が可能なビタビ復号器の提供を目的とするものである。
【課題を解決するための手段】
【００４０】
　前記の目的を達成するため、本発明の第１のビタビ符号器は、入力符号に基づいてブランチメトリックを演算するブランチメトリック演算手段と、前記ブランチメトリック演算手段により算出された前記ブランチメトリックに基づいて、各ステートの上位ステート及び下位ステートのパスメトリックを同時に時分割処理により算出する加算／比較／選択（ＡＣＳ）演算手段と、前記ＡＣＳ演算手段により逐次算出される上位ステート及び下位ステートの連続する２組のパスメトリックを、下位ステート及び上位ステートのそれぞれにおいて連続する偶数ステート及び奇数ステートのパスメトリックとして、時系列に並び換えるパスメトリック並び換え手段と、前記パスメトリック並び換え手段により並び換えられたパスメトリックを記憶するパスメトリック記憶手段とを備えたことを特徴とする。
【００４１】
　前記第１のビタビ符号器において、前記パスメトリック記憶手段は、それぞれ１アドレス当たり、連続する偶数ステートのパスメトリックと奇数ステートのパスメトリックとを１記憶単位として記憶し、読み出し及び書き込みを行うことが好ましい。
【００４２】
　また、前記第１のビタビ符号器において、前記ＡＣＳ演算手段により算出された、上位ステート及び下位ステートのパスメトリックの複数組からなる時系列を一時的に遅延させ、連続する偶数ステート及び奇数ステートのパスメトリックの複数組からなる時系列にパスメトリックを並び換えるパスメトリック並び換え手段を用いて、前記パスメトリック記憶手段一つに対する２回の読み出し、２回の書き込みにより４つのパスメトリックを更新することが好ましい。
【００４３】
　また、前記第１のビタビ符号器において、前記ＡＣＳ演算手段はまた、前時刻のパスメトリックと組み合わせて最尤のパスを選択し、該選択した（生き残り）パスの情報であるパス選択信号を生成し、前記第１のビタビ復号器はさらに、前記パス選択信号を記憶するパス選択信号記憶手段と、前記パス選択信号記憶手段から読み出した過去のパス選択信号を使用して過去の状態遷移を探索し、復号データを出力するトレースバック演算手段とを備え、前記トレースバック演算手段は、前記パス選択信号記憶手段より得られるパス選択信号に基づいて、生き残りパスに従ったビタビステートを格納するビタビステート格納手段と、前記ビタビステート格納手段の内容に基づいて、次に更新されるビタビステートの一部を予測するビタビステート予測手段と、前記ビタビステート予測手段により予測されたビタビステートの一部に基づいて、前記パス選択信号が記憶されている前記パス選択信号記憶手段のアドレスを算出するパス選択信号記憶アドレス算出手段とを備えることが好ましい。
【００４４】
　また、前記ビタビステート予測手段は、前記パス選択信号記憶手段の読み出し制御信号と前記ビタビステート格納手段のシフト制御信号とによって状態を変化させるアップダウンカウンタと、前記アップダウンカウンタの値に従って、前記ビタビステート格納手段の内容と次に更新されるビタビステートの一部との対応を変化させるセレクタを備えることが好ましい。
【００４５】
　さらに、前記ビタビステート予測手段により予測されたビタビステートの一部に基づいて、前記パス選択信号記憶アドレス算出手段がアドレスを算出する過程、該算出したアドレスに基づいて、前記パス選択信号記憶手段のパス選択信号を読み出す過程、および該読み出したパス選択信号に基づいて、生き残りパスに従ったビタビステートを前記ビタビステート格納手段に格納する過程の少なくとも一つの過程においてパイプライン処理を使用することが好ましい。
【００４６】
　前記の目的を達成するため、本発明の第２のビタビ復号器は、入力符号に基づいて、ブランチメトリックを演算するブランチメトリック演算手段と、前記ブランチメトリック演算手段により算出された前記ブランチメトリックに基づいて、各ステートの上位ステート及び下位ステートのパスメトリックを同時に時分割処理により算出すると共に、前時刻のパスメトリックと組み合わせて最尤のパスを選択し、該選択した（生き残り）パスの情報であるパス選択信号を生成する加算／比較／選択（ＡＣＳ）演算手段と、前記ＡＣＳ演算手段により逐次算出される上位ステート及び下位ステートの連続する２組のパスメトリックを、下位ステート及び上位ステートのそれぞれにおいて連続する偶数ステート及び奇数ステートのパスメトリックとして、時系列に並び換えるパスメトリック並び換え手段と、前記パスメトリック並び換え手段により並び換えられたパスメトリック及び前記パス選択信号を記憶する一つのパスメトリック／パス選択信号共通記憶手段と、前記パスメトリック／パス選択信号共通記憶手段から読み出した過去のパス選択信号を使用して過去の状態遷移を探索し、復号データを出力するトレースバック演算手段であって、前記パスメトリック／パス選択信号共通記憶手段より得られるパス選択信号に基づいて、生き残りパスに従ったビタビステートを格納するビタビステート格納手段と、前記ビタビステート格納手段の内容に基づいて、次に更新されるビタビステートの一部を予測するビタビステート予測手段と、前記ビタビステート予測手段により予測されたビタビステートの一部に基づいて、前記パス選択信号が記憶されている前記パス選択信号記憶手段のアドレスを算出するパス選択信号記憶アドレス算出手段とを備えたトレースバック演算手段と、前記パスメトリック並び換え手段からのパスメトリックと前記ＡＣＳ演算手段からのパス選択信号を受けて、前記パスメトリック／パス選択信号共通記憶手段に対して特定アドレスを生成し書き込みを行うと共に、前記パスメトリック／パス選択信号共通記憶手段に記憶されている前記パスメトリックと前記パス選択信号の読み出しを行い、前記ＡＣＳ演算手段に前記パスメトリックを、また前記トレースバック演算手段に前記パス選択信号を供給させるアドレス生成／記憶制御手段とを備えたビタビ復号器であって、前記ＡＣＳ演算手段、前記パスメトリック演算手段、及び前記トレースバック演算手段は、前記アドレス生成／記憶制御手段により、前記パスメトリック／パス選択信号共通記憶手段に対して時分割にアクセスすることを特徴とする。
【００４７】
　上記構成によれば、ビタビ復号器のＡＣＳ演算を時分割処理で行い、パスメトリック並び換え手段を用いて、パスメトリック記憶手段またはパスメトリック／パス選択信号共通記憶手段へ書き込むパスメトリックステートの順番を変更すると共に、ビタビ復号器のトレースバック演算を、ビタビステート予測手段を用いて、パイプライン処理でパス選択信号記憶手段またはパスメトリック／パス選択信号共通記憶手段からのパス選択信号の読み出しにより行うことで、ＡＣＳ演算のメモリアクセス回数を減らすと共に、トレースバック演算を高速に行うことができ、低消費電力化や、ビタビ復号処理の高速化が可能となる。
【発明の効果】
【００４８】
　本発明によれば、ビタビ復号器のＡＣＳ演算を時分割処理で行い、パスメトリック並び換え部を用いて、パスメトリック記憶部へ書き込むパスメトリックステートの順番を変更することにより、一つのメモリを用いて、４回のメモリアクセスで４つのパスメトリックを算出することが実現でき、ＡＣＳ演算の１処理当たりに必要とされるメモリアクセスの回数を低下させることができ、ビタビ復号動作を高速化、あるいは低電力化を実現することができる。
【００４９】
　また、本発明によれば、ビタビ復号器のトレースバック演算部にビタビステート予測部を設けて、パイプライン処理でパス選択信号記憶部からの読み出しを行うことにより、一般のＲＡＭ等のメモリをパス選択信号記憶部に用いながら、高速動作のトレースバックを行うことができ、ビタビ復号動作を高速化、あるいは低電力化を実現することができる。
【００５０】
　さらに、アドレス生成／記憶制御部を設けて、一つのＲＡＭをＡＣＳ演算部と、パスメトリック並び換え部と、トレースバック演算部で共用することで、ＲＡＭの使用量を最小限にしたビタビ復号器を実現することができる。
【発明を実施するための最良の形態】
【００５１】
　以下、本発明に係る実施の形態について、図面を参照しながら説明する。
【００５２】
　図１は、本発明の実施の形態が適用されるビタビ復号器の概略構成を示すブロック図である。
【００５３】
　一般にビタビ復号器は、ビタビアルゴリズムを利用して、各状態での２つのブランチのうち最尤（最も確からしい）ブランチの組み合わせ（パス）を選択し、所定長まで生き残りパスの選択を行い、各状態で選択したパスのうち最尤のパスを検出することで、受信符号を復号するものである。
【００５４】
　このようなビタビアルゴリズムに基づいて畳み込み符号を復号するビタビ復号器は、基本的には、図１に示す様に、端子１０１からの受信データの系列（受信系列）と、前述した各ブランチとの間のメトリックを計算するブランチメトリック演算部１０２と、生き残りパスを選択して生き残りパスのパスメトリックを演算するＡＣＳ（ADD、COMPARE、SELECT＝加算、比較、選択）演算部１０３と、ＡＣＳ演算部１０３より逐次算出されるパスメトリックを一時的に遅延させ、算出時と異なる時系列にパスメトリックを並び換えるパスメトリック並び換え部１０４と、各ステート（状態）でのパスメトリックをそれぞれ記憶するパスメトリック記憶部１０５と、選択したパスの情報（パス選択信号）を記憶するパス選択信号記憶部１０６と、このパス選択信号記憶部１０６から読み出した過去のパス選択信号を使用して過去の状態遷移を探索し、端子１０８より復号データを出力するトレースバック演算部１０７とを有して構成されている。
【００５５】
　まず、ＡＣＳ演算部１０３におけるＡＣＳ演算について説明する。
【００５６】
　ここで、畳み込み符号／ビタビ復号の具体例として、拘束長Ｋ＝９、符号化率Ｒ＝１／２の場合について説明する。拘束長Ｋ＝９の場合のステート（状態）数は、２K-1となり、Ｋ＝９の時、２8＝２５６ステートとなる。これらの２５６ステートを、２桁の１６進数を用いて００〜ＦＦと表し、ステートｘｘのパスメトリックをＰＭ［ｘｘ］と表す。また、新たなステートのパスメトリックをＰＭ［ｘｘ］（ｎｅｗ）、その前時刻のステートのパスメトリックをＰＭ［ｘｘ］（ｏｌｄ）と表す。
【００５７】
　上記拘束長Ｋ＝９、符号化率Ｒ＝１／２の場合、ＡＣＳ演算においては、各状態（ステート）に遷移する２つのパスのうち、最尤のパスを選択する演算を行う。例えば、新たなステート００（ｎｅｗ）に遷移するパスは、図１１に示すように、前時刻のステート００（ｏｌｄ）からと、０１（ｏｌｄ）からの２つのパスであり、この前時刻のステート００（ｏｌｄ）、０１（ｏｌｄ）からステート００（ｎｅｗ）に遷移するためには、受信符号（Ｇ０，Ｇ１）が例えばそれぞれ、（００）、（１１）である必要がある。
【００５８】
　この期待される２つの受信符号は、各ステートｘｘ（ｎｅｗ）に対して、畳み込み符号器の生成多項式から一意に決定される。この２つの受信符号はそれぞれ、「情報ビットとして０が畳み込み符号器に入力された場合」、および「情報ビットとして１が畳み込み符号器に入力された場合」に期待される受信符号を表す。
【００５９】
　このことから、ブランチメトリック演算部１０２において、受信符号それぞれの受信符号パターンのメトリック（ブランチメトリック）を求め、ＡＣＳ演算部１０３において、前時刻のメトリック（パスメトリック）と組み合わせて、パスの尤度を求め、生き残りパスの選択を行うと共に、次の時刻のためのパスメトリックをパスメトリック記憶部１０５に記憶して保持する。
【００６０】
　この時の計算は、ステートｘｘにおいて、それぞれ「情報ビットとして０が畳み込み符号器に入力された場合」、「情報ビットとして１が畳み込み符号器に入力された場合」のブランチメトリック、およびパスメトリックを、それぞれ、ＢＭ０［ｘｘ］、ＢＭ１［ｘｘ］、およびＰＭ０［ｘｘ］、ＰＭ１［ｘｘ］と表し、さらに、パスメトリックと尤度との対応を
　　　パスメトリック大　→　尤度大
　　　パスメトリック小　→　尤度小のように表すと、ステート００、０１からステート００に遷移する場合、
【００６１】
（数８）
　　　ＰＭ０［００］（ｎｅｗ）＝ＰＭ［００］（ｏｌｄ）＋ＢＭ０［００］
　　　ＰＭ１［００］（ｎｅｗ）＝ＰＭ［０１］（ｏｌｄ）＋ＢＭ１［００］
　　　ＰＭ［００］（ｎｅｗ）＝ｍａｘ（ＰＭ０［００］（ｎｅｗ），ＰＭ１［００］（ｎｅｗ））となる。ここで、ｍａｘ（ｘ，ｙ）はｘ、ｙのうち、大きな値を選択する演算を表す。
【００６２】
　また、最上位ビットのみが異なるＰＭ［８０］（ｎｅｗ）については以下の様になる。
【００６３】
（数９）
　　　ＰＭ０［８０］（ｎｅｗ）＝ＰＭ［００］（ｏｌｄ）＋ＢＭ０［８０］
　　　ＰＭ１［８０］（ｎｅｗ）＝ＰＭ［０１］（ｏｌｄ）＋ＢＭ１［８０］
　　　ＰＭ［８０］（ｎｅｗ）＝ｍａｘ（ＰＭ０［８０］（ｎｅｗ），ＰＭ１［８０］（ｎｅｗ））
　次に、ステート０２、０３からステート０１に遷移する場合は、
【００６４】
（数１０）
　　　ＰＭ０［０１］（ｎｅｗ）＝ＰＭ［０２］（ｏｌｄ）＋ＢＭ０［０１］
　　　ＰＭ１［０１］（ｎｅｗ）＝ＰＭ［０３］（ｏｌｄ）＋ＢＭ１［０１］
　　　ＰＭ［０１］（ｎｅｗ）＝ｍａｘ（ＰＭ０［００］（ｎｅｗ），ＰＭ１［００］（ｎｅｗ））となり、最上位ビットのみが異なるＰＭ［８１］（ｎｅｗ）については以下の様になる。
【００６５】
（数１１）
　　　ＰＭ０［８１］（ｎｅｗ）＝ＰＭ［０２］（ｏｌｄ）＋ＢＭ０［８１］
　　　ＰＭ１［８１］（ｎｅｗ）＝ＰＭ［０３］（ｏｌｄ）＋ＢＭ１［８１］
　　　ＰＭ［８１］（ｎｅｗ）＝ｍａｘ（ＰＭ０［８０］（ｎｅｗ），ＰＭ１［８０］（ｎｅｗ））
　さらに、畳み込み符号器の生成多項式が、
【００６６】
（数１２）
　　　Ｇ０（Ｄ）＝１＋…＋ＤK-1
　　　Ｇ１（Ｄ）＝１＋…＋ＤK-1の形になっている場合、すなわち、１、ＤK-1の項をそれぞれ有している場合、情報ビットの入力の０、１によって符号のビットが常に論理反転するため、符号距離が対象の関係になり、最上位ビットのみが異なるステートに関するブランチメトリックに関しては以下の関係が成り立つ。
【００６７】
（数１３）
　　　ＢＭ０［８０］＝ＢＭ１［００］
　　　ＢＭ１［８０］＝ＢＭ０［００］
　　　ＢＭ０［８１］＝ＢＭ１［０１］
　　　ＢＭ１［８１］＝ＢＭ０［０１］
　この関係を用いると、上記パスメトリックの関係は以下の様に表される。
【００６８】
（数１４）
　　　ＰＭ０［００］（ｎｅｗ）＝ＰＭ［００］（ｏｌｄ）＋ＢＭ０［００］
　　　ＰＭ１［００］（ｎｅｗ）＝ＰＭ［０１］（ｏｌｄ）＋ＢＭ１［００］
　　　ＰＭ［００］（ｎｅｗ）＝ｍａｘ（ＰＭ０［００］（ｎｅｗ），ＰＭ１［００］（ｎｅｗ））
【００６９】
（数１５）
　　　ＰＭ０［８０］（ｎｅｗ）＝ＰＭ［００］（ｏｌｄ）＋ＢＭ１［００］
　　　ＰＭ１［８０］（ｎｅｗ）＝ＰＭ［０１］（ｏｌｄ）＋ＢＭ０［００］
　　　ＰＭ［８０］（ｎｅｗ）＝ｍａｘ（ＰＭ０［８０］（ｎｅｗ），ＰＭ１［８０］（ｎｅｗ））
【００７０】
（数１６）
　　　ＰＭ０［０１］（ｎｅｗ）＝ＰＭ［０２］（ｏｌｄ）＋ＢＭ０［０１］
　　　ＰＭ１［０１］（ｎｅｗ）＝ＰＭ［０３］（ｏｌｄ）＋ＢＭ１［０１］
　　　ＰＭ［０１］（ｎｅｗ）＝ｍａｘ（ＰＭ０［００］（ｎｅｗ），ＰＭ１［００］（ｎｅｗ））
【００７１】
（数１７）
　　　ＰＭ０［８１］（ｎｅｗ）＝ＰＭ［０２］（ｏｌｄ）＋ＢＭ１［０１］
　　　ＰＭ１［８１］（ｎｅｗ）＝ＰＭ［０３］（ｏｌｄ）＋ＢＭ０［０１］
　　　ＰＭ［８１］（ｎｅｗ）＝ｍａｘ（ＰＭ０［８０］（ｎｅｗ），ＰＭ１［８０］（ｎｅｗ））
　つまり、上式から、ＰＭ［００］（ｏｌｄ）、ＰＭ［０１］（ｏｌｄ）、ＰＭ［０２］（ｏｌｄ）、ＰＭ［０３］（ｏｌｄ）という連続する偶数、奇数ステートの４つのパスメトリックより、ＰＭ［００］（ｎｅｗ）とＰＭ［０１］（ｎｅｗ）、またはＰＭ［８０］（ｎｅｗ）とＰＭ［８１］（ｎｅｗ）という、１組が連続する偶数、奇数ステートの２つのパスメトリックからなる２組のパスメトリックが得られることがわかる。
【００７２】
　本実施の形態では、パスメトリック並び換え部１０４を用いて、ＡＣＳ演算部１０３より逐次得られる４つのパスメトリックを、１組が連続する偶数、奇数ステートの２つのパスメトリックからなる２組のパスメトリックに並び換える。
【００７３】
　さらに、パスメトリック記憶部１０５として、ＲＡＭ（Random Access Memory）を用い、かつそれぞれのＲＡＭの１アドレス当たり、連続する偶数、奇数のステートのパスメトリックを１記憶単位として記憶する様に構成することにより、（１）ＰＭ［００］（ｏｌｄ）、ＰＭ［０１］（ｏｌｄ）の読み出し、ＰＭ［００］（ｎｅｗ）、ＰＭ［８０］（ｎｅｗ）の算出（２）ＰＭ［０２］（ｏｌｄ）、ＰＭ［０３］（ｏｌｄ）の読み出し、ＰＭ［０１］（ｎｅｗ）、ＰＭ［８１］（ｎｅｗ）の算出（３）ＰＭ［００］（ｎｅｗ）、ＰＭ［０１］（ｎｅｗ）の書き込み（４）ＰＭ［８０］（ｎｅｗ）、ＰＭ［８１］（ｎｅｗ）の書き込みという４回のメモリアクセスで４つのパスメトリックを更新する様にしている。これをＰＭ［００］〜ＰＭ［ＦＦ］についての２５６ステート分行う。
【００７４】
　具体的には、例えば図２（ａ）に示すように、パスメトリック更新をおこなう。
【００７５】
　ここで、図２（ａ）において、ステート（ｏｌｄ）をｎ、ステート（ｎｅｗ）をｍと表し、さらにステート（ｎｅｗ）における上位ステートをｍ（Ｕ）、下位ステートをｍ（Ｌ）と表している。ここで上位ステート、下位ステートの定義は、図９に示すように、情報ビットの入力側がステートの最上位ビットとなっている場合において、最上位ビットを除くビットが同一であるステートの対に関して、最上位ビットが１となっているステートが上位ステート、最上位ビットが０となっているステートが下位ステートとしている。図１１のパスメトリック・トランジション・ダイアグラムを例にすると、状態遷移後のステート００が下位ステート、ステート１０が上位ステートとなる。なお、情報ビットの入力側がステートの最下位ビットとなる定義も存在するが、数学的には同一である。
【００７６】
　まず、端子２０１、２０２からそれぞれブランチメトリックＢＭ０［ｍ］、ＢＭ１［ｍ］が、また端子２０３、２０４からそれぞれ連続した偶数、奇数ステートであるパスメトリックＰＭ［ｎ］、ＰＭ［ｎ＋１］が入力される。
【００７７】
　次に、加算器２０５、２０６、２０７、２０８によって、上位、下位ステートのパスメトリックＰＭ０［ｍ（Ｌ）］、ＰＭ１［ｍ（Ｌ）］、ＰＭ０［ｍ（Ｕ）］、ＰＭ１［ｍ（Ｕ）］が算出される。
【００７８】
　次に、減算器２０９、２１０によって、それぞれ、ＰＭ０［ｍ（Ｌ）］とＰＭ１［ｍ（Ｌ）］、ＰＭ０［ｍ（Ｕ）］とＰＭ１［ｍ（Ｕ）］の大小が比較される。減算器２０９、２１０による減算結果のうち、符号ビットが大小の比較結果を意味し、ＰＭ０［ｍ（Ｌ）］とＰＭ１［ｍ（Ｌ）］の比較結果である符号ビットｓｉｇｎ［ｍ（Ｌ）］、ＰＭ０［ｍ（Ｕ）］とＰＭ１［ｍ（Ｕ）］の比較結果であるｓｉｇｎ［ｍ（Ｕ）］は、後述するセレクタ２１１、２１２の選択信号に使用されると共に、端子２１７、２１８よりそれぞれパス選択信号ＰＳ［ｍ（Ｌ）］、ＰＳ［ｍ（Ｕ）］として出力される。
【００７９】
　次に、セレクタ２１１、２１２によって、尤度の高いパスメトリックがＰＭ［ｍ（Ｌ）］、ＰＭ［ｍ（Ｕ）］として算出される。このパスメトリックは、パスメトリック並び換え部１０４におけるフリップフロップなどで構成された遅延素子２１３、２１４、２１５によって一時的に遅延される。
【００８０】
　次に、連続した偶数、奇数ステートであるパスメトリックＰＭ［ｎ＋２］、ＰＭ［ｎ＋３］から同様に、パス選択信号ＰＳ［ｍ＋１（Ｌ）］、ＰＳ［ｍ＋１（Ｕ）］、パスメトリックＰＭ［ｍ＋１（Ｌ）］、ＰＭ［ｍ＋１（Ｕ）］が算出される。
【００８１】
　次にパスメトリックＰＭ［ｍ＋１（Ｌ）］、ＰＭ［ｍ＋１（Ｕ）］は、先に遅延されていたパスメトリックＰＭ［ｍ（Ｌ）］、ＰＭ［ｍ（Ｕ）］と合わせて並び換えられ、ＰＭ［ｍ（Ｌ）］とＰＭ［ｍ＋１（Ｌ）］の組、およびＰＭ［ｍ（Ｕ）］とＰＭ［ｍ＋１（Ｕ）］の組として、セレクタ２１６より選択される。そして端子２１９、２２０より出力される。
【００８２】
　上記動作を図２（ｂ）のタイミングチャートに示す。４サイクルの動作の中で、パスメトリック読み出し、書き込み動作がそれぞれ２サイクルで行われていることが分かる。このような仕組みによって、ＡＣＳ演算におけるメモリアクセスの頻度を削減できることがわかる。
【００８３】
　次に、トレースバック演算について説明する。本実施の形態を図３（ａ）に示す。図３（ａ）において、パス選択信号を格納したパス選択信号記憶部１０６を除いた残りの部分がトレースバック演算部１０７を構成し、トレースバック演算部１０７は、複数（ｎ）ステート分のパス選択信号をまとめたパス選択信号データ（ｎビット幅）を一時的に遅延するデータバッファ３０２と、パス選択信号データから１ステート分のパス選択信号（１ビット幅）を取り出すセレクタ３０３と、パス選択信号よりビタビステートを更新するシフトレジスタ３０４と、ビタビステートから次に更新されるビタビステートの一部を予測する次ビタビステート予測部３０５と、次ビタビステート予測部３０５から算出されたパス選択信号記憶部アドレスを一時的に遅延するアドレスバッファ３０６を有して構成されている。
【００８４】
　なお、シフトレジスタ３０４は、ビタビステートを表すと共にビタビステートの遷移から得られる復号ビットも表す。
【００８５】
　上記構成で重要な点は、従来動作ではシフトレジスタ３０４で更新されたビタビステートを基に、パス選択信号記憶部１０６からパス選択信号データを読み出し、パス選択信号データから取り出されたパス選択信号によって、次サイクルでシフトレジスタ３０４を更新する必要があったトレースバック処理が、本実施の形態において新規に設けた次ビタビステート予測部３０５によって、次に更新されるビタビステートを予測し、予測したパス選択信号記憶部アドレスを算出することで、パス選択信号記憶部アドレス、及びパス選択信号データをそれぞれ一時的に遅延するアドレスバッファ３０６、データバッファ３０２を用いたトレースバック処理へと改良されたことにある。
【００８６】
　上記改良の利点を次に説明する。図３（ｂ）は、上記構成における各信号の遅延について示したタイミングチャートである。まず基準となるクロックがあり、次ビタビステート予測部出力、パス選択信号記憶部アドレス入力、パス選択信号記憶部データ出力、データバッファ出力の順に記載している。それぞれの信号には、アドレスの配線遅延、パス選択信号記憶部の出力遅延、データの配線遅延がある。これらの遅延のうち、図３（ａ）に記載した遅延Ａ、遅延Ｃについては、パス選択信号記憶部１０６がクロックに同期して動作すること、およびアドレスバッファ３０６、データバッファ３０２によって、図３（ｂ）に示す様に、パイプライン動作として分割されている。
【００８７】
　そこで、トレースバック動作速度の上限は図３（ｃ）のようにして決定される。先述した遅延Ａ、遅延Ｃに加え、セレクタ３０３に関する遅延Ｂ、遅延Ｄ、そしてシフトレジスタ３０４のセットアップ時間を考慮して、以下の遅延のうち、大きな遅延によって動作速度の上限が決定する。
【００８８】
　　・パス選択信号記憶部１０６を中心とした遅延（１）：遅延Ａ
　　・パス選択信号記憶部１０６を中心とした遅延（２）：遅延Ｃ＋遅延Ｄ
　　・セレクタ３０３を中心とした遅延：遅延Ｂ＋遅延Ｄここで、先述した様に、アドレスバッファ３０６、データバッファ３０２によって遅延Ａ、遅延Ｃは非常に小さくすることができるので、セレクタ３０３を中心とした遅延によって動作速度が制限を受けることがわかる。このセレクタ３０３を中心とした遅延は、従来のパス選択信号記憶部を中心とした遅延と比較して非常に小さいので、高速なトレースバックを実現することができる。
【００８９】
　次に、本実施例の重要な点である次ビタビステート予測部３０５の原理について図４を用いて説明する。
【００９０】
　先述した様に、ビタビステートは、畳み込み符号器の遅延素子の内容をあらわしている。この遅延素子の内容は、１ビットの情報ビットが入力される度に１ビットシフトされる。つまり、１ビットシフトと１サイクルの時間変化はビタビステートの一部分に関して等価となる。この関係を利用して、パス選択信号記憶部アドレスとなるビタビステートの一部として、シフトレジスタ３０４のどのビット範囲を選択するかによって、次に更新されるパス選択信号記憶部アドレスの予測が実現できる。
【００９１】
　この動作を実現する具体的な回路構成を示したのが、図５（ａ）である。シフトレジスタ３０４から次ビタビステート予測部３０５に入力されるビタビステートの下位（パス選択信号の入力側）が、パス選択信号データからパス選択信号を取り出すセレクタ３０３（図３（ａ））への選択情報（ビットアドレス）となり、同様に入力されるビタビステートの上位が、パス選択信号記憶部アドレス（ワードアドレス）となり、セレクタ５０１が、ワードアドレスをビタビステートのどのビット範囲から取り出すかを選択し、アップダウンカウンタ５０２がセレクタ５０１の選択情報を算出する。なお、アップダウンカウンタ５０２は、パス選択データのリード信号、及びシフトレジスタ３０４のシフト信号によってカウンタの値を変化させる。
【００９２】
　図５（ｂ）に、パス選択データリード信号、シフトレジスタシフト信号と、アップダウンカウンタ５０２の値との関係を表す。図５（ｂ）において、パス選択データリード信号が０（リードしない）、かつ、シフトレジスタシフト信号が０（シフトしない）とき、または、パス選択データリード信号が１（リードする）、かつ、シフトレジスタシフト信号が１（シフトする）ときは、アップダウンカウンタ５０２は以前の値を保持する。次に、パス選択データリード信号が１（リードする）、かつ、シフトレジスタシフト信号が０（シフトしない）ときは、アップダウンカウンタ５０２は１だけ加算する。次に、パス選択データリード信号が０（リードしない）、かつ、シフトレジスタシフト信号が１（シフトする）ときは、アップダウンカウンタ５０２は１だけ減算する。
【００９３】
　ここでトレースバック動作時は、パス選択データリードとシフトレジスタシフトが常に１対１で対応するので、パス選択データリード信号か、シフトレジスタシフト信号のどちらかのみ１であるという状態は、図３（ｂ）に示したパイプライン構成の段数によって決定される。本構成例の場合は、トレースバック初期において、パス選択データリード信号が１で、かつ、シフトレジスタシフト信号が０であるという状態が３サイクル連続し、トレースバックの終了時はパス選択データリード信号が０で、かつ、シフトレジスタシフト信号が１であるという状態が３サイクル連続する。そのため、アップダウンカウンタ５０２の初期値を０とすると、アップダウンカウンタ５０２の値は０から３の間を変化することになる。
【００９４】
　図５（ｃ）に、アップダウンカウンタ５０２の値と、セレクタ５０１によって選択されるワードアドレスとの関係を示す。アップダウンカウンタ５０２の値が増加する、すなわち、パス選択データリード信号が１で、かつ、シフトレジスタシフト信号が０の時は、ワードアドレスとして、ビタビステートの下位側を順次選択する動作となる。この動作は、図４で説明したように、次に更新されるパス選択信号記憶部アドレスを予測する動作である。この予測時は、ビットアドレスの一部をワードアドレスとして使用する動作となるため、予測範囲は、最大ビットアドレスのビット幅分取り得ることができる。
【００９５】
　図６に、上記トレースバック演算による一連の動作タイミングを示す。図６は、上から順に、基準クロック、次ビタビステート予測部３０５出力、アドレスバッファ３０６出力、メモリ（パス選択信号記憶部）１０６出力、パス選択信号、シフトレジスタ３０４の最下位ビット、パス選択データリード信号、シフトレジスタシフト信号、アップダウンカウンタ５０２の値を表している。図６に示すように、ビタビステート予測部３０５の出力を用いることにより、パイプライン動作でトレースバックが実行できていることがわかる。
【００９６】
　このような仕組みによって、通常のＲＡＭを使用しながらも、高速なトレースバックを実現することができる。
【００９７】
　次に、図７を参照して、上記したような演算手段を用いて、通常のＲＡＭを使用し、かつ、ＲＡＭの使用量を最小限にした本発明の他の実施形態によるビタビ復号器の例を説明する。
【００９８】
　図７に示すビタビ復号器は、前述したブランチメトリック演算部１０２、ＡＣＳ演算部１０３、パスメトリック並び換え部１０４、トレースバック演算部１０７に加えて、ＡＣＳ演算部１０３、パスメトリック並び換え部１０４、およびトレースバック演算部１０７に接続されるアドレス生成／記憶制御部７０６、及びアドレス生成／記憶制御部７０６に接続されるパスメトリック／パス選択信号共通記憶部７０５を有している。
【００９９】
　アドレス生成／記憶制御部７０６は、パスメトリック格納領域開始アドレスＰＭＳＡＤＲ、パス選択信号格納領域開始アドレスＰＳＳＡＤＲ、格納領域指定信号ＰＭＰＳＳＥＬをもとに、パスメトリックステート番号ｎ、ｍ、及びパス選択信号ステート番号ｊから、以下のメモリアクセスアドレスＭＥＭＡＤＲを生成する。
【０１００】
（数１８）
　　　ＭＥＭＡＤＲ＝ＰＭＰＳＳＥＬ？（ＰＭＳＡＤＲ＋ｎ）：（ＰＭＳＡＤＲ
＋ｍ）：（ＰＳＳＡＤＲ＋ｊ）ここで、演算式ｓ？ｘ：ｙ：ｚは、ｓ＝０の時ｘ、ｓ＝１の時ｙ、ｓ＝２の時ｚを出力する演算を表す。
【０１０１】
　ビタビ復号動作時は、図８に示す様に、ＰＭＰＳＳＥＬが適当な時点で０、１、２のいずれかの値となり、ＰＭＰＳＳＥＬに同期して、ＡＣＳ演算部１０３、パスメトリック並び換え部１０４、およびトレースバック演算部１０７のそれぞれが動作する。
【０１０２】
　このような仕組みによって、一つのＲＡＭを各演算部で共用し、通常のＲＡＭを使用し、かつ、ＲＡＭの使用量を最小限にしたビタビ復号を実現することができる。
【産業上の利用可能性】
【０１０３】
　本発明によれば、ビタビ復号器のトレースバック演算部にビタビステート予測部を設けて、パイプライン処理でパス選択信号記憶部からの読み出しを行うことにより、一般のＲＡＭ等のメモリをパス選択信号記憶部に用いながら、高速動作のトレースバックを行うことができ、ビタビ復号動作を高速化、あるいは低電力化を実現することが可能となり、畳み込み符号の最尤復号に用いられるビタビ復号器に有用である。
【図面の簡単な説明】
【０１０４】
【図１】本発明の実施形態によるビタビ復号器の概略構成を示すブロック図
【図２】ＡＣＳ演算部及びパスメトリック並び換え部の構成を示すブロック図及びその動作を示すタイミングチャート
【図３】トレースバック演算の構成の具体例及び動作遅延を示す図
【図４】次ビタビステート予測部の原理を示す図
【図５】次ビタビステート予測部の構成を示す図
【図６】トレースバック演算動作を示すタイミングチャート
【図７】本発明の他の実施形態による、一つのＲＡＭを各演算部で共用するビタビ復号器の概略構成を示すブロック図
【図８】一つのＲＡＭを各演算部で共用する動作を示すタイミングチャート
【図９】畳み込み符号器の一例を示すブロック図
【図１０】ビタビ復号を説明するためのトレリス線図
【図１１】ビタビ復号を説明するためのパスメトリック・トランジション・ダイアグラム
【図１２】トレースバック演算を説明するためのステート遷移図
【図１３】トレースバック演算の従来例を示す図
【符号の説明】
【０１０５】
　１０１　ビタビ復号器の受信データ入力端子
　１０２　ブランチメトリック演算部
　１０３　ＡＣＳ演算部
　１０４　パスメトリック並び換え部
　１０５　パスメトリック記憶部
　１０６　パス選択信号記憶部
　１０７　トレースバック演算部
　１０８　ビタビ復号器の復号データ出力端子
　２０１、２０２　ＡＣＳ演算部１０３のブランチメトリック入力端子
　２０３、２０４　ＡＣＳ演算部１０３のパスメトリック入力端子
　２０５、２０６、２０７、２０８　ＡＣＳ演算用加算器
　２０９、２１０　ＡＣＳ演算用減算器
　２１１、２１２　ＡＣＳ演算用セレクタ
　２１３、２１４、２１５　パスメトリック並び換え用遅延素子
　２１６　パスメトリック並び換え用セレクタ
　２１７、２１８　ＡＣＳ演算部１０３のパス選択信号出力端子
　２１９、２２０　パスメトリック並び換え部１０４のパスメトリック出力端子
　３０２　トレースバック用データバッファ
　３０３　パス選択信号取り出し用セレクタ
　３０４　トレースバック用シフトレジスタ
　３０５　次ビタビステート予測部
　３０６　トレースバック用アドレスバッファ
　５０１　次ビタビステート予測部３０５のセレクタ
　５０２　次ビタビステート予測部３０５のアップダウンカウンタ
　７０５　パスメトリック／パス選択信号共通記憶部
　７０６　アドレス生成／記憶制御部
　９０１、９０２　畳み込み符号器の遅延素子
　９０３、９０４、９０５　畳み込み符号器の加算器
【図１】
2004120791.tif 000003
【図２】
2004120791.tif 000004
【図３】
2004120791.tif 000005
【図４】
2004120791.tif 000006
【図５】
2004120791.tif 000007
【図６】
2004120791.tif 000008
【図７】
2004120791.tif 000009
【図８】
2004120791.tif 000010
【図９】
2004120791.tif 000011
【図１０】
2004120791.tif 000012
【図１１】
2004120791.tif 000013
【図１２】
2004120791.tif 000014
【図１３】
2004120791.tif 000015