(57)【特許請求の範囲】
【請求項１】
畳み込み符号の各遷移状態でのパスの選択情報を、１ライト−１リ−ドのデュアルポートを備える書き換え可能なｍ個のメモリを用いて記憶するパスメモリを備え、そのパスメモリに保持された情報を打ち切り長分トレースすることでビタビ復号を行うビタビ復号装置において、
上記ｍ個のメモリの合計のワード数を打ち切り長の２倍とされ、
各クロックと同期して上記ｍ個のメモリの中で１個のメモリに上記パス選択情報を書き込むと共に、上記ｍ個のメモリのそれぞれから同時にｍワードを読み出し、
１クロックの間にｍ時刻分のトレースを行って復号を行うことを特徴とするビタビ復号装置。
【請求項２】
請求項１において、
上記ｍ個のメモリから同時に読み出しを行ってｍ時刻分のトレースを行う際に、
上記ｍ個のメモリの各々から読み出されるパス選択情報の内、トレースする可能性のあるステートの情報を、トレース開始ステートに基づいて予め選択し、選択したステートの情報についてトレースを行うことを特徴とするビタビ復号装置。
【請求項３】
畳み込み符号の各遷移状態でのパスの選択情報を、シングルポートを備える書き換え可能なｍ個のメモリを用いて記憶するパスメモリを備え、そのパスメモリに保持された情報を打ち切り長分トレースすることでビタビ復号を行うビタビ復号装置において、
上記ｍ個のメモリの合計のワード数を打ち切り長の２倍とされ、
各クロックと同期して上記ｍ個のメモリの中で１個のメモリに上記パス選択情報を書き込むと共に、（ｍ−１）個のメモリのそれぞれから同時に（ｍ−１）ワードを読み出し、
１クロックの間に（ｍ−１）時刻分のトレースを行って復号を行うことを特徴とするビタビ復号装置。
【請求項４】
請求項３において、
上記ｍ個のメモリから同時に読み出しを行って（ｍ−１）時刻分のトレースを行う際に、
上記ｍ個のメモリの各々から読み出されるパス選択情報の内、トレースする可能性のあるステートの情報を、トレース開始ステートに基づいて予め選択し、選択したステートの情報についてトレースを行うことを特徴とするビタビ復号装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、例えば衛星放送等で使用される畳み込み符号の最尤復号法に使用されるビタビ復号装置に関する。
【０００２】
【従来の技術】
畳み込み符号を復号する方式の一つとして、ビタビ復号方式が知られている。このビタビ復号方式は、畳み込み符号に対する最尤復号方式であり、送信側のエンコーダから生成され得る符号系列の中から、受信された符号系列に最も近い系列（以下、このような系列を最尤パスと表記する）を選ぶことにより、誤り訂正を行う。すなわち、送信側のエンコーダによる符号化方法に基づいて作成される、遷移ダイヤグラム（以下、トレリスと表記する）を前提とし、遷移ダイヤグラム上で生じ得る遷移の内から、例えば受信された符号系列とのハミング距離が最小となるものを最尤パスとして選択するようになされている。
【０００３】
ビタビ復号方式を行うビタビ復号装置は、ブランチメトリック、すなわちトレリス上の各状態に到達するパスと受信された符号系列とのハミング距離をクロックに従って計算するブランチメトリック計算回路と、ブランチメトリックに基づいてステートメトリックを計算し、ステートメトリックの値を比較して最尤パスを選択するＡＣＳ回路、ステートメトリックの値を正規化する正規化回路、ステートメトリックの値を記憶するステートメトリック記憶回路、ＡＣＳによる選択結果に従って復号データを生成するパスメモリ回路を備える構成とされている。
【０００４】
ここで、パスメモリ回路としては、レジスタ列を用いてパス選択内容を遷移させるレジスタ遷移法を行うものと、ＲＡＭを用いてパス選択内容を記憶させ、記憶内容をトレースして復号する方法を行うものの２種類がある。以下、これら２種類の方法について説明する。
【０００５】
従来のビタビ復号装置において一般的に使用されてきたレジスタ遷移法においては、パスメモリ回路内にセレクタとレジスタからなるメモリセルをトレリス上に配置し、ＡＣＳ回路から出力されるパス選択情報に基づいてレジスタの内容を遷移させる。メモリセルの構成の一例を図１６に示した。また、拘束長＝３の場合のメモリセルの配置の一例を図１７に示した（図１７中ではメモリセルをＭＳと表記した）。このような構成により、各メモリセルのレジスタ内には、各ステートからの生き残りパスに対応する情報が保存されることになる。メモリセルには打ち切り長分の段数が配置され、最終段の出力の内、最尤ステートの出力を選ぶことによって最尤パスに対する情報を選択し、復号データを出力する。
【０００６】
このようなレジスタ遷移法は、高速動作が可能であるという利点がある反面、打ち切り長が長くなると回路規模が膨大になるという欠点がある。特に、最近は、打ち切り長が１００を越えるような用途も出てきたので、回路規模の大型化が深刻な問題となっている。
【０００７】
そこで、近年では、打ち切り長分のＲＡＭ(Random Access Memory)を用いてパス情報を記憶し、記憶した情報をトレースすることで復号する方法が盛んに研究されている。以下、この方法をトレースバック法と呼ぶ。
【０００８】
【発明が解決しようとする課題】
トレースバック法によれば、レジスタ遷移法よりも遥に回路規模の小さいパスメモリ回路を構成できる。しかしながら、トレースバック法を行う従来の装置においては、依然としてパスメモリ回路が大きな回路規模を有している。
【０００９】
この発明はこのような事情に鑑みて提案されたものであり、従って、この発明の目的は、回路規模が小さく、高速動作可能なビタビ復号装置を提供することにある。
【００１０】
【課題を解決するための手段】
請求項１の発明は、畳み込み符号の各遷移状態でのパスの選択情報を、１ライト−１リ−ドのデュアルポートを備える書き換え可能なｍ個のメモリを用いて記憶するパスメモリを備え、そのパスメモリに保持された情報を打ち切り長分トレースすることでビタビ復号を行うビタビ復号装置において、
ｍ個のメモリの合計のワード数を打ち切り長の２倍とされ、
各クロックと同期してｍ個のメモリの中で１個のメモリにパス選択情報を書き込むと共に、ｍ個のメモリのそれぞれから同時にｍワードを読み出し、
１クロックの間にｍ時刻分のトレースを行って復号を行うことを特徴とするビタビ復号装置である。
【００１１】
以上のような発明によれば、１クロックの間に複数時刻分のトレースを行って復号を行うことにより、ＲＡＭの総ワード数を少なくすることができる。
【００１２】
また、パス選択情報を書き込む際には複数個の書き換え可能なメモリに順に書き込みを行い、トレースの際には、かかる複数個のメモリから順に読み出しを行って複数時刻分のトレースを行うことにより、各クロックの各メモリへのアクセス回数を１回としつつ、複数時刻分のトレースが可能となる。
【００１３】
さらに、複数個のメモリの各々の出力の内、トレースする可能性のあるステートの情報を、トレース開始ステートに基づいて予め選択し、選択されたステートの情報についてトレースを行うようにすることで、複数時刻分のトレースを行っても遅延の増大を最小限に抑えることが可能となる。
【００１４】
【発明の実施の形態】
以下、図面を参照して、この発明の第１の実施形態について説明する。まず、図１を参照してこの発明の第１の実施形態の全体的な構成について説明する。この発明の第１の実施形態は、ブランチメトリック計算回路７０１、ＡＣＳ回路７０２、正規化回路７０３、ステートメトリック記憶回路７０４、およびパスメモリ回路７０５を備える構成とされており、送信側から伝送路を介して受信されたデータが入力された時、送信側のエンコーダから生成され得る符号系列の中から最尤パスを選択し、選択内容に基づいて復号データを生成する。
【００１５】
すなわち、送信側のエンコーダによる符号化方法に基づいて作成される、例えば図２に示すような遷移ダイヤグラム（以下、トレリスと表記する）を前提とし、遷移ダイヤグラム上で生じ得る遷移の内から、例えば受信された符号系列とのハミング距離が最小となるものを最尤パスとして選択するようになされている。
【００１６】
ブランチメトリック計算回路７０１は、受信データ信号ｓ７０１が入力されたとき、この受信データのブランチメトリックを計算して、計算結果をブランチメトリック信号ｓ７０２として出力する。ＡＣＳ回路７０２は、ブランチメトリック信号ｓ７０２と、ステートメトリック記憶回路７０４から入力されるステートメトリック信号ｓ７０５とに基づいて、あるステートに合流する２本のそれぞれのパスに対し、ブランチメトリックとステートメトリックとを加算してそれら加算値を比較し、比較結果に基づいて尤度の高いものを選択して、新ステートメトリックとする。
【００１７】
このような選択の内容をパス選択情報ｓ７０６として出力し、最小のステートメトリックを持つステートの番号を最尤ステート信号ｓ７０７として出力し、新たに得られたステートメトリックを新ステートメトリック信号ｓ７０３として出力する。
【００１８】
ここで、パスの選択方法について、拘束長＝４の場合を例として説明する。図２のトレリスは、８個のステート０００、００１、０１０、０１１、１００、１０１、１１０、１１１を有し、拘束長＝４の場合のトレリスの一例である。ここで矢印は各タイムスロット毎に生じ得るパスを示しており、復号データ'0' に対応するパスを点線で示し、復号データ'1' に対応するパスを実線で示した。各タイムスロット毎にすべてのステートには合流する２本のパスが存在する。そこで、あるステートに合流する２本のそれぞれのパスに対し、受信信号とパスとのハミング距離（ブランチメトリック）と、それまでのブランチメトリックの累積和（ステートメトリック）とを加算して比較を行い、この比較結果に基づいて尤度の高いものが選択される。
【００１９】
正規化回路７０３は、ＡＣＳ回路７０２から出力される新ステートメトリック信号ｓ７０３から最小のステートメトリックを減算する方法等を用いて正規化し、予め設定されている範囲内の値にして、正規化ステートメトリック信号ｓ７０４として出力する。ステートメトリック記憶回路７０４は、正規化回路７０３から出力される正規化ステートメトリック信号ｓ７０４を記憶し、これをステートメトリック信号ｓ７０５としてＡＣＳ回路７０２に戻す。
【００２０】
パスメモリ回路７０５は、トレースバック法による復号動作を行うものであり、上述したような、トレースバック法を行う一般的なパスメモリと比較してＲＡＭの面積を小さくするようになされたものである。かかるパスメモリ回路７０５の説明を行うに先立って、理解を容易とするために、一般的なトレースバック法におけるトレースの動作を拘束長＝４の場合を例として説明する。図３において、ステート０１からトレースする場合を考える。ステート００１への遷移の可能性があるステートは、ステート０００とステート１００である。ここでパスメモリには、ステート０００側のパスを選んであった時には０、ステート１００側のパスを選んであった時には１（すなわち前ステートの最上位ビット）が記憶してある。
【００２１】
また、何れのステートから遷移する場合にも入力は１であり、これはステート００１の最下位ビットで表現されている。以上により、トレースの動作は次のように行えば良い。すなわち、図４に示すように、トレースを開始するトレース開始ステートの最下位ビットを復号ビットとし、トレース開始ステートに後続してトレースする次トレースステートの番号は、トレース開始ステートの最上位ビットから下位２ビット目までに、パスメモリ内のビットを新たに最上位ビットとして付け加えることで生成する。このような動作によって、最小ステートメトリックをとるステートから、選択されたパスを遡ることができる。
【００２２】
ビタビ復号装置を高速に動作させるためには、ＲＡＭはクロック毎に一回しかアクセスできない。各ＲＡＭに対して１回のアクセスで復号を行うためのパスメモリ回路の動作を、シングルポートのメモリを４個使用する場合を例として説明する。以下の説明においては、符号の拘束長＝４とし、打ち切り長＝６とする。この場合に、４個のシングルポートのメモリとしては、ステート数分のビット数（ここでは８ビット）と打ち切り長分のワード数（ここでは６ワード）を持つものが使用される。ＡＣＳ回路からパスメモリへは、ステート数分のパス選択情報が毎クロック入力される。４個のＲＡＭは、以下の（１）〜（４）の４個の役割を打ち切り長分のクロック（ここでは６クロック）毎に順次切り替える（図５参照）。
【００２３】
（１）パス選択情報を順次書き込む。
【００２４】
（２）書き込まれたパス選択情報に基づいて順次トレースする。復号は行わない。
【００２５】
（３）アクセス無し。
【００２６】
（４）（２）でのトレース結果から順次トレースを行って復号ビットを出力する。
【００２７】
このような切り替え動作の基づく各ＲＡＭの動作を図６に示す。以上のようなメモリオペレーションによって、ＲＡＭを用いても高速な復号が可能なビタビ復号装置を構成することができる。このような一般的なトレースバック法によればレジスタ遷移法を行う場合と比較して遥に回路規模を縮小できる。しかしながら、打ち切り長分のワード数を持つＲＡＭが４個必要なため、ＲＡＭの総ワード数は打ち切り長×４となり、依然として大きな回路規模が必要とされる。そこで、この発明の一実施形態は、パスメモリ回路の回路規模をさらに縮小するものである。
【００２８】
図７を参照して、この発明の一実施形態におけるパスメモリ回路７０５について説明する。パスメモリ回路７０５は、拘束長＝４の符号に対し、打ち切り長＝６の復号を行う場合に、ビット数＝８でワード数＝４の１ライト−１リ−ドのデュアルポートのＲＡＭを３個備え、１クロックの間に３時刻分のトレースを行うパスメモリ回路である。
【００２９】
ＡＣＳ回路から入力されるパス選択情報ｓ１０２は、コントロール回路１０１で生成される書き込みコントロール信号ｓ１０３に基づいて、毎クロック、ＲＡＭ１２→ＲＡＭ１１→ＲＡＭ１０→ＲＡＭ１２→ＲＡＭ１１・・・の順にＲＡＭに記憶される。ＲＡＭ１０、ＲＡＭ１１、ＲＡＭ１２からはコントロール回路１０１で生成される読み出しコントロール信号ｓ１０４に従って、毎クロック全てのＲＡＭからパス選択情報の読み出しを行って読出パス選択情報ｓ１０５、ｓ１０６、ｓ１０７をトレース回路１０２に入力する。
【００３０】
なお、コントロール回路１０１に基づくメモリオペレーションのタイミングを図８に示す。トレース回路１０２では、ＲＡＭ１０，ＲＡＭ１１，ＲＡＭ１２から出力される読出パス選択情報ｓ１０５、ｓ１０６、ｓ１０７、およびコントロール回路１０１で生成されるトレース開始ステート情報ｓ１０８に従って３時刻分のトレースを行い、その結果はトレース結果信号ｓ１０９としてコントロール回路ｓ１０１に入力される。コントロール回路ｓ１０１では、トレース結果信号ｓ１０９と最尤ステート信号ｓ１０１に基づいて、打ち切り長／２クロック毎にトレース開始ステートの初期化を行いながら、次のクロックのトレース開始ステートを求める。
【００３１】
このようなメモリオペレーションについて、図９および図１０を参照してより具体的に説明する。図９および図１０は連続する時刻におけるＲＡＭ１０，ＲＡＭ１１，ＲＡＭ１２に対する書き込み／読み出しについて図示したものである。上述したように、これら３個のＲＡＭは、ビット数＝８でワード数＝４のデュアルポートのＲＡＭである。記載スペースの都合により、図９に時刻１〜時刻６までを図示し、図１０に時刻７〜時刻１３までを図示した。ここで、各メモリのアドレスは何れも左から順に０、１、２、３であるとする。時刻１、２、３・・・９までは、各ＲＡＭに順次パス選択情報が書き込まれ、時刻９においては、各ＲＡＭについて３つのアドレスに書き込みがなされている。
【００３２】
時刻１０以降のオペレーションが図８に示されている。時刻１０に対応する図８の先頭のクロックにおいては、各ＲＡＭのアドレス３から記憶内容（３個のパス選択情報９、８、７）を読み出し、トレースを行うと共に、ＲＡＭ１２のアドレス０に後続のパス選択情報１０を書き込む。ここで、図９および図１０においては、読み出しの矢印に付し’ｔ’はトレースを行うことを示し、’ｄ’はトレースして復号を行うことを示す。
【００３３】
時刻１１に対応する図８の２番目のクロックにおいては、各ＲＡＭのアドレス２から記憶内容（３個のパス選択情報６、５、４）を読み出し、トレースを行うと共に、ＲＡＭ１１のアドレス０に後続のパス選択情報１１を書き込む。さらに、時刻１２に対応する図８の３番目のクロックにおいては、各ＲＡＭのアドレス１から記憶内容（パス選択情報３、２、１）を読み出し、トレースしてから、パス選択情報１〜９に対応する復号を行うと共に、ＲＡＭ１２のアドレス０に後続のパス選択情報１２を書き込む。そして、時刻１３に対応する図８の４番目のクロックにおいては、各ＲＡＭのアドレス０から記憶内容（３個のパス選択情報１０、１１、１２を読み出し、トレースおよびトレース開始ステートの初期化を行うと共に、ＲＡＭ１２アドレス１に後続のパス選択情報１３を書き込む。
【００３４】
このように復号およびそれに後続するクロックにおけるトレース開始ステートの初期化が３クロックに１度行われ、また、何れのクロックにおいても、後続のパス選択情報が１アドレス分入力される。
【００３５】
一方、トレース開始ステート情報ｓ１０８は出力バッファ１０３にも入力される。出力バッファ１０３では打ち切り長以上トレースを行った後のトレース開始ステート情報ｓ１０８の下位３ビットを復号ビットとしてバッファし、本来の時系列順に並べ換えた後に復号ビット信号ｓ１１０として出力する。以上のような構成によって、各ＲＡＭへのアクセスは、毎クロックにつき１回としたまま、パスメモリ回路内のＲＡＭの総ワード数を打ち切り長×２にすることができる。これによってビタビ復号装置の回路規模を削減できる。
【００３６】
次にトレース回路１０２について説明する。トレースはＲＡＭ１０→ＲＡＭ１１→ＲＡＭ１２の順に行われるので、パス選択情報ｓ１０５の中から何れのステートのパス選択情報を選ぶかは、トレース開始ステート情報ｓ１０８によって決定される。また、トレース開始ステート情報ｓ１０８によってパス選択情報ｓ１０６、ｓ１０７からは選ぶべきステートの候補を、それぞれ２つ、４つまで絞ることができる（図１１参照）。トレース回路１０２は、この性質を用いることで構成する。
【００３７】
図１２に、トレース回路１０２の構成を図示した。ＲＡＭ１０，ＲＡＭ１１，ＲＡＭ１２から入力されるパス選択情報ｓ１０５，ｓ１０６，ｓ１０７は、それぞれ、選択回路４０１、４０２、４０３に入力される。一方、選択回路４０１、４０２、４０３には、トレース開始ステート情報ｓ１０７も入力される。選択回路４０１では、トレース開始ステート情報ｓ１０７に従って、パス選択情報ｓ１０４からトレースするステートのパス選択情報を選択して、トレース結果情報ｓ４０１として出力する。また、選択回路４０２では、トレース開始ステート情報ｓ１０７に従って、パス選択情報ｓ１０５からトレースする可能性のある２つのステートのパス選択情報を選択して、前トレース情報ｓ４０２として出力する。
【００３８】
前トレース情報ｓ４０２は選択回路４０４に入力される。選択回路４０４にはさらに、トレース結果情報ｓ４０１が入力される。選択回路４０４は、トレース結果情報ｓ４０１に従ってトレースするステートのパス選択情報を選択して、トレース結果情報ｓ４０３として出力する。また、選択回路４０３では、トレース開始ステート情報ｓ１０７に従ってパス選択情報ｓ１０６からトレースする可能性のある４個のステートのパス選択情報を選択して、前トレース情報ｓ４０４として出力する。前トレース情報ｓ４０４は、選択回路４０５に入力される。選択回路４０５にはさらに、トレース結果情報ｓ４０１およびｓ４０３が入力される。選択回路４０５は、トレース結果情報ｓ４０１およびｓ４０３に従ってトレースするステートのパス選択情報を選択してトレース結果情報ｓ４０５として出力する。最後にトレース結果情報ｓ４０１，ｓ４０３，ｓ４０５を３ビットまとめてトレース結果信号ｓ１０９として出力する。
【００３９】
以上のようなトレース回路１０２の構成により、この発明の一実施形態においては、複数時刻分のトレースを行っても、１時刻分のトレースを行う場合と比較してセレクタ２段分の遅延を生じるのみであり、復号動作速度が殆ど損なわれようにすることができる。
【００４０】
上述したこの発明の一実施形態は、１ライト−１リ−ドのデュアルポートのＲＡＭを３個備え、１クロックの間に３時刻分のトレースを行うパスメモリ回路を使用するものである。これに対して、異なる構成を有するパスメモリ回路を使用する、この発明の他の実施形態も可能である。図１３に、この発明の他の実施形態におけるパスメモリ回路の構成を図示した。かかるパスメモリ回路は、拘束長＝４の符号に対し、打ち切り長＝６の復号を行う場合に、ビット数＝８でワード数＝３のシングルポートのＲＡＭを４個（ＲＡＭ５０，ＲＡＭ５１，ＲＡＭ５２，ＲＡＭ５３）備え、１クロックの間に３時刻分のトレースを行う回路である。
【００４１】
ＡＣＳ回路から入力されるパス選択情報ｓ５０２は、書き込みコントロール信号ｓ５０３に従って、毎クロック、ＲＡＭ５３→ＲＡＭ５２→ＲＡＭ５１→ＲＡＭ５０→ＲＡＭ５３→・・・の順にＲＡＭに記憶される。また、ＲＡＭ５０、ＲＡＭ５１、ＲＡＭ５２、ＲＡＭ５３は読み出しコントロール信号ｓ５０４に従って、毎クロック３つのＲＡＭからパス選択情報の読み出しを行って、パス選択情報ｓ５０５、ｓ５０６、ｓ５０７、ｓ５０８を出力する。パス選択情報ｓ５０５、ｓ５０６、ｓ５０７、ｓ５０８は、トレース回路５０２に入力される。ここで、書き込みコントロール信号ｓ５０３および読み出しコントロール信号ｓ５０４は、コントロール回路５０１で生成され、ＲＡＭ５０，ＲＡＭ５１，ＲＡＭ５２，ＲＡＭ５３にそれぞれ入力される。なお、コントロール回路５０１に基づくメモリオペレーションのタイミングを図１４に示す。
【００４２】
トレース回路５０２では、ＲＡＭ５０、５１、５２、５３から出力されるパス選択情報ｓ５０５，ｓ５０６，ｓ５０７，ｓ５０８、およびコントロール回路５０１で生成されるトレース開始ステート情報ｓ５０９に従って３時刻分のトレースを行い、その結果がトレース結果信号ｓ５１０としてコントロール回路５０１に入力される。トレース回路５０２は、例えば図１２に示したこの発明の一実施形態におけるトレース回路１０２に用いられているような選択回路を組み合わせて構成することができる。また、コントロール回路５０１では、トレース結果信号ｓ５１０と最尤ステート信号ｓ５０１とに基づいて、打ち切り長／２毎にトレース開始ステートの初期化を行いながら、次のクロックのトレース開始ステートを求める。
【００４３】
このようなメモリオペレーションについて、図１５および図１６を参照してより具体的に説明する。図１５および図１６は連続する時刻におけるＲＡＭ５０，ＲＡＭ５１，ＲＡＭ５２、ＲＡＭ５３に対する書き込み／読み出しについて図示したものである。上述したように、これら４個のＲＡＭは、ビット数＝８でワード数＝３のシングルポートのＲＡＭである。記載スペースの都合により、図１５に時刻１〜時刻６までを図示し、図１６に時刻７〜時刻１３までを図示した。ここで、各メモリのアドレスは何れも左から順に０、１、２であるとする。時刻１、２、３・・・９までは、各ＲＡＭに順次パス選択情報が書き込まれ、時刻９においては、各ＲＡＭについて２つのアドレスに書き込みがなされている。
【００４４】
この状態に後続する時刻１０以降のオペレーションが図１４に示されている。時刻１０に対応する図１４の先頭のクロックにおいては、３個のＲＡＭ（すなわちＲＡＭ５０、ＲＡＭ５１、ＲＡＭ５２）のアドレス２から記憶内容（パス選択情報９、８、７）を読み出し、トレースを行うと共に、１つのＲＡＭ（すなわちＲＡＭ５３）のアドレス０に後続のパス選択情報１０を書き込む。ここで、読み出しの矢印に付した’ｔ’はトレースを行うことを示し、’ｄ’はトレースして復号を行うことを示す。
【００４５】
時刻１１に対応する図１４の２番目のクロックにおいては、３個のＲＡＭ（すなわちＲＡＭ５０、ＲＡＭ５１、ＲＡＭ５３）から記憶内容（パス選択情報６、５、４）を読み出し、トレースを行うと共に、１つのＲＡＭ（すなわちＲＡＭ１１）のアドレス０に後続のパス選択情報１１を書き込む。この際の読み出しは、２個のＲＡＭ（ＲＡＭ５０、ＲＡＭ５１）についてはアドレス１についてなされ、他の１個のＲＡＭ（ＲＡＭ５３）についてはアドレス２についてなされる。
【００４６】
さらに、時刻１２に対応する図１４の３番目のクロックにおいては、３個のＲＡＭ（すなわちＲＡＭ５０、ＲＡＭ５２、ＲＡＭ５３）から記憶内容（パス選択情報３、２、１）を読み出し、トレースしてから、パス選択情報１〜９に対応する復号を行うと共に、他の１つのＲＡＭ（すなわちＲＡＭ５１）のアドレス０に後続のパス選択情報１２を書き込む。この際の読み出しは、２個のＲＡＭ（ＲＡＭ５２、ＲＡＭ５３）についてはアドレス１についてなされ、他の１個のＲＡＭ（ＲＡＭ５１）についてはアドレス０についてなされる。
【００４７】
そして、時刻１３に対応する図１４の４番目のクロックにおいては、３個のＲＡＭ（すなわちＲＡＭ５１、ＲＡＭ５２、ＲＡＭ５３）のアドレス０から記憶内容（パス選択情報１０、１１、１２）を読み出し、トレースおよびトレース開始ステートの初期化を行うと共に、他の１つのＲＡＭ（すなわちＲＡＭ５０）のアドレス０に後続のパス選択情報１３を書き込む。
【００４８】
このように復号およびそれに後続するクロックにおけるトレース開始ステートの初期化が３クロックに１度行われ、また、何れのクロックにおいても、後続のパス選択情報が１アドレス分入力される。
【００４９】
一方、トレース開始ステート情報ｓ５０９は、出力バッファ５０３にも入力される。出力バッファ５０３は打ち切り長以上トレースを行った後のトレース開始ステート情報ｓ５０７の下位３ビットを復号ビットとしてバッファし、本来の時系列順に並べ換えた後に復号ビット信号ｓ５１１として出力する。
【００５０】
このように、この発明の他の実施形態においても、各ＲＡＭへのアクセスは毎クロックにつき１回としたまま、パスメモリのＲＡＭの総ワード数を打ち切り長×２にすることができる。また、この発明の他の実施形態におけるパスメモリ回路は、シングルポートのメモリのみを用いるために、図７等を参照して上述したこの発明の一実施形態と比較してさらに回路規模を削減できる。さらに、トレース回路５０２においては、この発明の一実施形態におけるパスメモリ回路７０５中のトレース回路１０２と同様に予めステートの候補を絞ることにより、遅延の増大を最小限に抑えることができる。
【００５１】
上述したこの発明の一実施形態およびこの発明の他の実施形態においては、拘束長＝４、打ち切り長＝６の場合について説明したが、拘束長および打ち切り長かこの値に限らず任意の値をとすることができる。また、この発明の一実施形態等においては、１クロック毎に３時刻分のトレースを行う場合を例としたが、例えば４個のデュアルポートＲＡＭを備える構成によって１クロック毎に４時刻分のトレースを行う、或いは５個のシングルポートＲＡＭを備える構成によって１クロック毎に４時刻分のトレースを行う等、種々の変形が可能である。
【００５２】
【発明の効果】
上述したように、この発明は、１クロックの間に複数時刻分のトレースを行って復号を行うようにしたので、パスメモリ回路内のＲＡＭの総ワード数を削減することができる。このため、装置の回路規模の縮小に寄与することができる。
【００５３】
また、毎クロックでの各ＲＡＭへのアクセス回数は１回であること、およびトレース回路の上述した構成によって遅延の増大を最小限に抑えるようにしたことにより、高速な復号動作が可能となる。
【００５４】
従って、この発明により、回路規模が小さく、高速動作可能なビタビ復号装置を提供することができる。
【図面の簡単な説明】
【図１】この発明の一実施形態の全体的な構成について説明するためのブロック図である。
【図２】拘束長＝４の場合の遷移ダイアグラムについて説明するための略線図である。
【図３】トレースバック法におけるトレースの原理について説明するための略線図である。
【図４】トレースバック法におけるトレースの方法について説明するための略線図である。
【図５】従来から行われている一般的なトレースバック法における各ＲＡＭの役割について説明するための略線図である。
【図６】従来から行われている一般的なトレースバック法におけるメモリオペレーションについて説明するための略線図である。
【図７】この発明の一実施形態におけるパスメモリ回路について説明するためのブロック図である。
【図８】この発明の一実施形態におけるメモリオペレーションについて説明するための略線図である。
【図９】この発明の一実施形態におけるメモリオペレーションについてより具体的に説明するための略線図である。
【図１０】この発明の一実施形態におけるメモリオペレーションについてより具体的に説明するための略線図である。
【図１１】トレースする可能性のあるステートについて説明するための略線図である。
【図１２】この発明の一実施形態におけるトレース回路について説明するためのブロック図である。
【図１３】この発明の他の実施形態におけるパスメモリ回路について説明するためのブロック図である。
【図１４】この発明の他の実施形態におけるメモリオペレーションについて説明するための略線図である。
【図１５】この発明の他の実施形態におけるメモリオペレーションについてより具体的に説明するための略線図である。
【図１６】この発明の他の実施形態におけるメモリオペレーションについてより具体的に説明するための略線図である。
【図１７】レジスタ遷移法におけるパスメモリのメモリセルについて説明するための略線図である。
【図１８】レジスタ遷移法におけるパスメモリ中のメモリセルの配置について説明するための略線図である。
【符号の説明】
７０５・・・パスメモリ回路、１０１・・・コントロール回路、１０２・・・トレース回路、４０１、４０２、４０３、４０４、４０５・・・選択回路、５０１・・・コントロール回路
【図１】
0003747604.tif 000002
【図２】
0003747604.tif 000003
【図３】
0003747604.tif 000004
【図４】
0003747604.tif 000005
【図５】
0003747604.tif 000006
【図６】
0003747604.tif 000007
【図７】
0003747604.tif 000008
【図８】
0003747604.tif 000009
【図９】
0003747604.tif 000010
【図１０】
0003747604.tif 000011
【図１１】
0003747604.tif 000012
【図１２】
0003747604.tif 000013
【図１３】
0003747604.tif 000014
【図１４】
0003747604.tif 000015
【図１５】
0003747604.tif 000016
【図１６】
0003747604.tif 000017
【図１７】
0003747604.tif 000018
【図１８】
0003747604.tif 000019