(57)【特許請求の範囲】
【請求項１】
復調シンボルを入力してブランチメトリックを発生するブランチメトリック演算手段と、
前記ブランチメトリックとパスメトリックを加算する加算手段と、
該加算手段の出力を比較および選択する比較選択手段と、
該比較選択手段の選択結果を記録する複数のパスメモリ手段と、
該複数のパスメモリ手段の各々に対して設けられ対応するパスメモリ手段の値から情報系列を推定する複数のトレースバック手段と、
該複数のトレースバック手段の出力を多重して所定の順序に並べ替えるバッファ手段と、
を備えてなるビタビ復号装置によるビタビ復号方法であって、
前記パスメモリ手段と前記トレースバック手段とを互いに独立に動作可能な複数組とし、
この各組それぞれが、前記パスメモリ手段へのアクセスをアドレス昇順とアドレス降順とを交互に繰り返すことによりパスメモリ更新動作及び出力動作を同時に行うとともに、各組で位相をずらして交互に動作することを特徴とするビタビ復号方法。
【請求項２】
復調シンボルを入力してブランチメトリックを発生するブランチメトリック演算手段と、
ブランチメトリックとパスメトリックを加算する加算手段と、
該加算手段の出力を比較および選択する比較選択手段と、
該比較選択手段の選択結果を記録する複数のパスメモリ手段と、
パスメトリックのうち最小パスの状態を選択する最尤判定手段と、
前記複数のパスメモリ手段の各々に対して設けられ前記最尤判定手段結果を初期値として対応するパスメモリ手段の値から情報系列を推定する複数のトレースバック手段と、
該複数のトレースバック手段の出力を多重して所定の順序に並べ替えるバッファ手段と、
を備えてなるビタビ復号装置によるビタビ復号方法であって、
前記パスメモリ手段と前記トレースバック手段とを互いに独立に動作可能な複数組とし、
この各組それぞれが、前記パスメモリ手段へのアクセスをアドレス昇順とアドレス降順とを交互に繰り返すことによりパスメモリ更新動作及び出力動作を同時に行うとともに、各組で位相をずらして交互に動作することを特徴とするビタビ復号方法。
【請求項３】
復調シンボルを入力してブランチメトリックを発生するブランチメトリック演算手段と、
ブランチメトリックとパスメトリックを加算する加算手段と、
該加算手段の出力を比較および選択する比較選択手段と、
該比較選択手段の選択結果を記録する複数のパスメモリ手段と、
パスメトリックのうち最小パスの状態を選択する最尤判定手段と、
該最尤判定手段の判定結果によりパスメトリックを正規化する正規化手段と、
前記複数のパスメモリ手段の各々に対して設けられ前記最尤判定手段の判定結果を初期値として対応するパスメモリ手段の値から情報系列を推定する複数のトレースバック手段と、
該複数のトレースバック手段の出力を多重して所定の順序に並べ替えるバッファ手段と、
を備えてなるビタビ復号装置によるビタビ復号方法であって、
前記パスメモリ手段と前記トレースバック手段とを互いに独立に動作可能な複数組とし、
この各組それぞれが、前記パスメモリ手段へのアクセスをアドレス昇順とアドレス降順とを交互に繰り返すことによりパスメモリ更新動作及び出力動作を同時に行うとともに、各組で位相をずらして交互に動作することを特徴とするビタビ復号方法。
【請求項４】
前記パスメモリ手段と前記トレースバック手段との組は２組備えられ、これらの組の動作位相は、
第１の組がパスメモリ更新及び読出出力のための読出修正書込動作を行っている間に第２の組がパスメモリ更新及び読み捨てのための読出修正書込動作を行う第１の位相と、
第２の組がパスメモリ更新及び読出出力のための読出修正書込動作を行っている間に第１の組がパスメモリ更新及び読み捨てのための読出修正書込動作を行う第２の位相と、
を含み、これら第１の位相及び第２の位相を交互に繰り返すことを特徴とする請求項１ないし請求項３のいずれか１項記載のビタビ復号方法。
【請求項５】
復調シンボルを入力してブランチメトリックを発生するブランチメトリック演算手段と、
前記ブランチメトリックとパスメトリックを加算する加算手段と、
該加算手段の出力を比較および選択する比較選択手段と、
該比較選択手段の選択結果を記録する複数のパスメモリ手段と、
該複数のパスメモリ手段の各々に対して設けられ対応するパスメモリ手段の値から情報系列を推定する複数のトレースバック手段と、
該複数のトレースバック手段の出力を多重して所定の順序に並べ替えるバッファ手段と、
前記パスメモリ手段とこれに対応する前記トレースバック手段とを互いに独立に動作可能な複数組とし、この各組それぞれに、前記パスメモリ手段へのアクセスをアドレス昇順とアドレス降順とを交互に繰り返すことによりパスメモリ更新動作及び出力動作を同時に行わせるとともに、各組で位相をずらして交互に動作させる制御手段と、
を備えたことを特徴とするビタビ復号装置。
【請求項６】
復調シンボルを入力してブランチメトリックを発生するブランチメトリック演算手段と、
ブランチメトリックとパスメトリックを加算する加算手段と、
該加算手段の出力を比較および選択する比較選択手段と、
該比較選択手段の選択結果を記録する複数のパスメモリ手段と、
パスメトリックのうち最小パスの状態を選択する最尤判定手段と、
前記複数のパスメモリ手段の各々に対して設けられ前記最尤判定手段結果を初期値として対応するパスメモリ手段の値から情報系列を推定する複数のトレースバック手段と、
該複数のトレースバック手段の出力を多重して所定の順序に並べ替えるバッファ手段と、
前記パスメモリ手段とこれに対応する前記トレースバック手段とを互いに独立に動作可能な複数組とし、この各組それぞれに、前記パスメモリ手段へのアクセスをアドレス昇順とアドレス降順とを交互に繰り返すことによりパスメモリ更新動作及び出力動作を同時に行わせるとともに、各組で位相をずらして交互に動作させる制御手段と、
を備えたことを特徴とするビタビ復号装置。
【請求項７】
復調シンボルを入力してブランチメトリックを発生するブランチメトリック演算手段と、
ブランチメトリックとパスメトリックを加算する加算手段と、
該加算手段の出力を比較および選択する比較選択手段と、
該比較選択手段の選択結果を記録する複数のパスメモリ手段と、
パスメトリックのうち最小パスの状態を選択する最尤判定手段と、
該最尤判定手段の判定結果によりパスメトリックを正規化する正規化手段と、
前記複数のパスメモリ手段の各々に対して設けられ前記最尤判定手段の判定結果を初期値として対応するパスメモリ手段の値から情報系列を推定する複数のトレースバック手段と、
該複数のトレースバック手段の出力を多重して所定の順序に並べ替えるバッファ手段と、
前記パスメモリ手段とこれに対応する前記トレースバック手段とを互いに独立に動作可能な複数組とし、この各組それぞれに、前記パスメモリ手段へのアクセスをアドレス昇順とアドレス降順とを交互に繰り返すことによりパスメモリ更新動作及び出力動作を同時に行わせるとともに、各組で位相をずらして交互に動作させる制御手段と、
を備えたことを特徴とするビタビ復号装置。
【請求項８】
前記パスメモリ手段と前記トレースバック手段との組は２組備えられ、これらの組の動作位相は、
第１の組がパスメモリ更新及び読出出力のための読出修正書込動作を行っている間に第２の組がパスメモリ更新及び読み捨てのための読出修正書込動作を行う第１の位相と、
第２の組がパスメモリ更新及び読出出力のための読出修正書込動作を行っている間に第１の組がパスメモリ更新及び読み捨てのための読出修正書込動作を行う第２の位相と、
を含み、これら第１の位相及び第２の位相を交互に繰り返すことを特徴とする請求項５ないし請求項７のいずれか１項記載のビタビ復号装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は畳み込み符号を復号するビタビ復号方法および装置に関し、特にパスメモリ回路に読出修正書込（ Read Modify Write）を行ってその回路規模縮小を可能とするビタビ復号方法および装置に関する。
【０００２】
【従来の技術】
ディジタル伝送における誤り訂正法として、ビタビ復号法（G.D.Forney, Jr.,“The Viterbi Algorithm” Proceedings of IEEE, vol.61, pp268-278, Mar.1973. 参照）がある。このビタビ復号法は、最尤復号を効率よく、実現するアルゴリズムである。
【０００３】
このビタビ復号法が適用されるたたみ込み符号は、例えば、図５に示すたたみ込み符号器を用いて送信側で符号化する。図５のたたみ込み符号器は、入力ｕが接続されたａ，ｂの２ビットからなるシフトレジスタと、ｙ(1) ＝ｕ＋ｂ＋ａ，ｙ(2) ＝ｕ＋ａを生成する２つの排他的論理和回路とで構成されている。そしてこの符号器は、１ビットの入力ｕに対して２ビットの出力ｙ(1)，ｙ(2)が生成され、入力の１ビットの変化が出力の連続する３ビットに影響するので、符号化率Ｒ＝１／２，拘束長Ｌ＝３である。こうして符号化が施されたビタビ符号は、受信側で図６に示すトレリス表現に基づいた復号（誤り訂正）が行われる。
【０００４】
この図６を参照するに、各太線は時刻ｋ＝４まで復号をすすめたときの、各状態｛ａ，ｂ｝＝｛０，０｝，〜，｛１，１｝でそれぞれ選択され生き残った生き残りパス（復号系列の候補）Ｖ（０），〜，Ｖ（３）を表すものである。この生き残りパスは、受信系列と伝送系列の距離差をもとに選択される。各時刻まで復号をすすめたときの、その距離差（ハミング距離差）に相当するパスメトリックを図６では実線の四角で表している。点線の四角は捨てられたパスのパスメトリックである。
【０００５】
図６から明らかなように、時刻：ｋ＝４まで復号をすすめたときの生き残りパスＶ（０），〜，Ｖ（３）のパスメトリックは、それぞれ１，１，２，２である。一般に、各生き残りパスの過去の系列ほど１本にまとまる確率が高いので、生き残りのパスのメモリ長を適当な長さ（拘束長の４〜６倍）で打ち切り、最過去のシンボルをその時刻の復号シンボルとして出力する。
【０００６】
また誤りパターンによっては各生き残りパスの最過去のビットが一致しないことがままあるが、上記パスメトリックが最小のものが、最も確からしい復号系列に相当することはいうまでもない。
【０００７】
ビタビ復号の装置化において、パスメトリックの演算は図７に示す状態遷移の組を単位として実現できる。時刻（ｋ−１）で選択された生き残りパスのパスメトリックをそれぞれΓｋ−１，Γ’ｋ−１とし、現在の受信符号との距離差に相当するブランチメトリックをλｋ，λ’ｋとする。現在の時刻ｋにおける生き残りパスの候補は、各状態で２つずつ存在し、それぞれのパスメトリックはΓｋ−１，Γ’ｋ−１，λｋ，λ’ｋを用いて（Γｋ−１＋λｋ），（Γ’ｋ−１＋λ’ｋ），（Γｋ−１＋λ’ｋ），（Γ’ｋ−１＋λｋ）で表される。また各状態ではそれぞれのパスメトリックの内、小さい方に相当するパスが選択される。
【０００８】
このようにパスメトリックの演算は加算(Add）、比較(Compare）および選択（Select）の操作で実現できる。そこで、このようなパスメトリックの演算器をＡＣＳユニット（ＡＣＳＵ）と呼ぶことにする。
【０００９】
ビタビ復号器全体の構成例を図８のブロック図に示す。ＡＣＳＵ（図８では８０４ａ及び８０４ｂで示す）の数は可能な状態数をＮｓ＝２Ｌ−１（Ｌ：拘束長）とすると、それぞれが状態２個分に対応するので、（Ｎｓ／２）個である。したがって、この従来例ではＬ＝３のため、Ｎｓ／２＝２である。
【００１０】
３つの比較判定回路８２１ａ，８２１ｂ，８２１ｃにより構成される最尤判定部８０５は最も確からしい生き残りパス（最尤パス）を判定するために、最小のパスメトリックを検出することを目的とするものである。図８に示すように比較判定回路８２１ａ，８２１ｂ，８２１ｃをツリー状に構成して最尤判定部８０５を構成するときには、（Ｎｓ−１）個の比較選択回路を必要とする。
【００１１】
パスメモリ更新回路８０７は各状態で残すパスを更新することを目的とするものである。すなわち、各状態｛０，０｝＝（０），｛０，１｝＝（１），｛０，１｝＝（２），｛１，１｝＝（３）で選択し残したパスを示すパス選択信号β（０），β（１），β（２），β（３）により、図６に示すＶ（０），〜，Ｖ（３）の最過去のシンボルに相当する復号シンボルの候補σ（０），〜，σ（３）を出力する。
【００１２】
ビタビ復号のセレクタ８０８はこれらの復号シンボルの候補σ（０），〜，σ（３）のうちから最尤パスに相当する復号シンボルを選択し、ビタビ復号シンボルとして、出力するものである。この選択には最尤判定部８０５から出力される最尤パスを示す選択情報Ｐｍ（＝０ or １ or ２ or ３）を用いる。
【００１３】
ところで図６では、ブランチメトリックとしてハミング距離を用いたが、より訂正能力を高めるため、軟判定を導入して、ユークリッド距離、あるいは、ユークリッド距離の二乗をブランチメトリックに用いる方法がある。この場合、ブランチメトリックを３ｂｉｔで表現するとすれば、復号性能を劣化させないためには各パスメトリックのレジスタは６ｂｉｔから８ｂｉｔが必要である。
【００１４】
実際に用いるたたみ込み符号は、拘束長が大きいほど、訂正能力が大きいので、Ｌ＝７程度のものがよく用いられている。符号化率Ｒ＝１／２，拘束長Ｌ＝７の場合のビタビ復号器の全体構成図を図９に示す。たたみ込み符号器の状態数はＮａ＝２L-1 ＝６４であるから最尤判定部の比較入力の数も６４となる。
【００１５】
ビタビ復号は復号パスの候補を、各状態に対応したパスメトリックに基づいて逐次的に切り捨てていくことで、常に状態数（Ｎｓ）分の復号パス（生き残りパス）しか残さないようにする。こうすることで、効率的な最尤復号を実現できるわけである。
【００１６】
図１０のように各生き残りパスは、ある適当な長さＭｓより過去に相当するパスについて１本に合流する確率が高い。生き残りパスのうち対応するパスメトリックが最小のパス（最尤パス）をＭｓ段分さかのぼった遷移に対応する情報ビットδ（ｔ−Ｍｓ）がビタビ復号出力になる。
【００１７】
これをこのまま、パスメモリ上にすべての６４個のパスを記憶し、１ステップごとに選択、記録していたのでは効率が悪い。それを改善する手法としてトレースバック方法がある。
【００１８】
トレースバック方法では、パスメモリでは各状態からの遷移方向（ｒ＝１／２の時１ビット）のみを記録しておき、最終状態から逆方向にパスの遷移をＭｓだけ遡り復号出力を行う。
【００１９】
ただし、毎ステップにこの遡る動作を行うことは、大変なので、ある程度の長さ分を一度に行う。例えば、Ｍｓは十分な長さの（遡りパスが収束するぐらいの）値を取る得る値とした時、２Ｍｓ分を行えば、前半のＭｓは、パスの収束がないため、信頼性が低いということでデータを捨て、残りのＭｓ遡る時の復号出力を行う。ただし、時間方向とは逆方向に進むので、一度バッファリングを行い出力する（ＬＩＦＯのようなもの）。
【００２０】
トレースバック回路は図１１に示すような、たたみ込み符号化を鏡に向かって、折り返した様な回路を用いる。たたみ込みとは時間的に逆の動作が行われる。状態数のレジスタはちょうど、逆方向にシフトし、状態変化は符号化とまったく逆となる。この出力をとると、たたみ込みの入力系列が再現される。
【００２１】
トレースバック動作ではパスメモリのデータの読み込みが時間的に逆方向なため、実際に必要なデータ長さは、
［パスメモリの時間方向の書き込み２Ｍｓ］＋［トレースバック前半Ｍｓ分だけのデータ破棄］＋［復号Ｍｓ］＝４Ｍｓ
となり、Ｍｓ長のデータを復号するためには４Ｍｓだけの時間が必要になる。そこでデータを連続に復号するためには４個のＲＡＭを必要とする。図１２にＲＡＭをＡ，Ｂ，Ｃ，Ｄとした時のタイミング図を示す。それぞれは位相をずらして、実行を行う。
【００２２】
【発明が解決しようとする課題】
しかしながら、従来開発されているビタビ復号器は例えば拘束長７の時、パスメモリの幅が６４ビットとなり、深さはトレースバックに必要なパスメモリ長Ｍｓの２倍のＲＡＭが４個必要となっており、回路構成上、規模の大きいものであり、民生品に応用するのはかなり困難であるという問題点があった。
【００２３】
本発明は上記問題点に鑑みてなされたもので、特にその装置化において、パスメモリの縮小化を可能としたビタビ復号方法および装置を提供することを目的とする。
【００２４】
【課題を解決するための手段】
上記目的を達成するために、本発明は次の構成を有する。
すなわち請求項１記載の発明は、復調シンボルを入力してブランチメトリックを発生するブランチメトリック演算手段と、前記ブランチメトリックとパスメトリックを加算する加算手段と、該加算手段の出力を比較および選択する比較選択手段と、該比較選択手段の選択結果を記録する複数のパスメモリ手段と、該複数のパスメモリ手段の各々に対して設けられ対応するパスメモリ手段の値から情報系列を推定する複数のトレースバック手段と、該複数のトレースバック手段の出力を多重して所定の順序に並べ替えるバッファ手段と、を備えてなるビタビ復号装置によるビタビ復号方法であって、前記パスメモリ手段と前記トレースバック手段とを互いに独立に動作可能な複数組とし、この各組それぞれが、前記パスメモリ手段へのアクセスをアドレス昇順とアドレス降順とを交互に繰り返すことによりパスメモリ更新動作及び出力動作を同時に行うとともに、各組で位相をずらして交互に動作することを要旨とするビタビ復号方法である。
【００２５】
また請求項２記載の発明は、復調シンボルを入力してブランチメトリックを発生するブランチメトリック演算手段と、ブランチメトリックとパスメトリックを加算する加算手段と、該加算手段の出力を比較および選択する比較選択手段と、該比較選択手段の選択結果を記録する複数のパスメモリ手段と、パスメトリックのうち最小パスの状態を選択する最尤判定手段と、前記複数のパスメモリ手段の各々に対して設けられ前記最尤判定手段結果を初期値として対応するパスメモリ手段の値から情報系列を推定する複数のトレースバック手段と、該複数のトレースバック手段の出力を多重して所定の順序に並べ替えるバッファ手段と、を備えてなるビタビ復号装置によるビタビ復号方法であって、前記パスメモリ手段と前記トレースバック手段とを互いに独立に動作可能な複数組とし、この各組それぞれが、前記パスメモリ手段へのアクセスをアドレス昇順とアドレス降順とを交互に繰り返すことによりパスメモリ更新動作及び出力動作を同時に行うとともに、各組で位相をずらして交互に動作することを要旨とするビタビ復号方法である。
【００２６】
また請求項３記載の発明は、復調シンボルを入力してブランチメトリックを発生するブランチメトリック演算手段と、ブランチメトリックとパスメトリックを加算する加算手段と、該加算手段の出力を比較および選択する比較選択手段と、該比較選択手段の選択結果を記録する複数のパスメモリ手段と、パスメトリックのうち最小パスの状態を選択する最尤判定手段と、該最尤判定手段の判定結果によりパスメトリックを正規化する正規化手段と、前記複数のパスメモリ手段の各々に対して設けられ前記最尤判定手段の判定結果を初期値として対応するパスメモリ手段の値から情報系列を推定する複数のトレースバック手段と、該複数のトレースバック手段の出力を多重して所定の順序に並べ替えるバッファ手段と、を備えてなるビタビ復号装置によるビタビ復号方法であって、前記パスメモリ手段と前記トレースバック手段とを互いに独立に動作可能な複数組とし、この各組それぞれが、前記パスメモリ手段へのアクセスをアドレス昇順とアドレス降順とを交互に繰り返すことによりパスメモリ更新動作及び出力動作を同時に行うとともに、各組で位相をずらして交互に動作することを要旨とするビタビ復号方法である。
【００２７】
また請求項４記載の発明は、請求項１ないし請求項３のいずれか１項記載のビタビ復号方法において、前記パスメモリ手段と前記トレースバック手段との組は２組備えられ、これらの組の動作位相は、第１の組がパスメモリ更新及び読出出力のための読出修正書込動作を行っている間に第２の組がパスメモリ更新及び読み捨てのための読出修正書込動作を行う第１の位相と、第２の組がパスメモリ更新及び読出出力のための読出修正書込動作を行っている間に第１の組がパスメモリ更新及び読み捨てのための読出修正書込動作を行う第２の位相と、を含み、これら第１の位相及び第２の位相を交互に繰り返すことを要旨とする。
【００２８】
また請求項５記載の発明は、復調シンボルを入力してブランチメトリックを発生するブランチメトリック演算手段と、前記ブランチメトリックとパスメトリックを加算する加算手段と、該加算手段の出力を比較および選択する比較選択手段と、該比較選択手段の選択結果を記録する複数のパスメモリ手段と、該複数のパスメモリ手段の各々に対して設けられ対応するパスメモリ手段の値から情報系列を推定する複数のトレースバック手段と、該複数のトレースバック手段の出力を多重して所定の順序に並べ替えるバッファ手段と、前記パスメモリ手段とこれに対応する前記トレースバック手段とを互いに独立に動作可能な複数組とし、この各組それぞれに、前記パスメモリ手段へのアクセスをアドレス昇順とアドレス降順とを交互に繰り返すことによりパスメモリ更新動作及び出力動作を同時に行わせるとともに、各組で位相をずらして交互に動作させる制御手段と、を備えたことを要旨とするビタビ復号装置である。
【００２９】
また請求項６記載の発明は、復調シンボルを入力してブランチメトリックを発生するブランチメトリック演算手段と、ブランチメトリックとパスメトリックを加算する加算手段と、該加算手段の出力を比較および選択する比較選択手段と、該比較選択手段の選択結果を記録する複数のパスメモリ手段と、パスメトリックのうち最小パスの状態を選択する最尤判定手段と、前記複数のパスメモリ手段の各々に対して設けられ前記最尤判定手段結果を初期値として対応するパスメモリ手段の値から情報系列を推定する複数のトレースバック手段と、該複数のトレースバック手段の出力を多重して所定の順序に並べ替えるバッファ手段と、前記パスメモリ手段とこれに対応する前記トレースバック手段とを互いに独立に動作可能な複数組とし、この各組それぞれに、前記パスメモリ手段へのアクセスをアドレス昇順とアドレス降順とを交互に繰り返すことによりパスメモリ更新動作及び出力動作を同時に行わせるとともに、各組で位相をずらして交互に動作させる制御手段と、を備えたことを要旨とするビタビ復号装置である。
【００３０】
また、請求項７記載の発明は、復調シンボルを入力してブランチメトリックを発生するブランチメトリック演算手段と、ブランチメトリックとパスメトリックを加算する加算手段と、該加算手段の出力を比較および選択する比較選択手段と、該比較選択手段の選択結果を記録する複数のパスメモリ手段と、パスメトリックのうち最小パスの状態を選択する最尤判定手段と、該最尤判定手段の判定結果によりパスメトリックを正規化する正規化手段と、前記複数のパスメモリ手段の各々に対して設けられ前記最尤判定手段の判定結果を初期値として対応するパスメモリ手段の値から情報系列を推定する複数のトレースバック手段と、該複数のトレースバック手段の出力を多重して所定の順序に並べ替えるバッファ手段と、前記パスメモリ手段とこれに対応する前記トレースバック手段とを互いに独立に動作可能な複数組とし、この各組それぞれに、前記パスメモリ手段へのアクセスをアドレス昇順とアドレス降順とを交互に繰り返すことによりパスメモリ更新動作及び出力動作を同時に行わせるとともに、各組で位相をずらして交互に動作させる制御手段と、を備えたことを要旨とするビタビ復号装置である。
【００３１】
また請求項８記載の発明は、請求項５ないし請求項７のいずれか１項記載のビタビ復号装置において、前記パスメモリ手段と前記トレースバック手段との組は２組備えられ、これらの組の動作位相は、第１の組がパスメモリ更新及び読出出力のための読出修正書込動作を行っている間に第２の組がパスメモリ更新及び読み捨てのための読出修正書込動作を行う第１の位相と、第２の組がパスメモリ更新及び読出出力のための読出修正書込動作を行っている間に第１の組がパスメモリ更新及び読み捨てのための読出修正書込動作を行う第２の位相と、を含み、これら第１の位相及び第２の位相を交互に繰り返すことを要旨とする。
【００３２】
【発明の実施の形態】
次に、本発明の一実施形態について図面を参照しながら説明する。図１は本発明に係るビタビ復号装置の構成を示すブロック図である。
【００３３】
同図において、ビタビ復号装置１は、復調シンボルが入力される入力端子３と、復調シンボルからブランチメトリックを計算するブランチメトリック演算手段であるブランチメトリックユニット（以下、ＢＭＵと略す）５と、正規化回路７と、ブランチメトリックとパスメトリックとの加算及び加算結果の比較選択を行う加算比較選択ユニット（以下、ＡＣＳＵと略す）９と、パスメトリックのうち最小パスを選択する最尤判定回路１１と、それぞれ２×Ｍｓ段からなりＡＣＳＵの選択結果を記憶するパスメモリ回路１３ａ，１３ｂと、パスメモリ回路１３ａ，１３ｂから情報系列を推定するトレースバック回路１５ａ、１５ｂと、トレースバック回路１５ａ、１５ｂの一方を選択して出力するセレクタ１７と、セレクタ１７の時系列出力をラストイン・ファーストアウト（以下、ＬＩＦＯと表記する）の順序で並べ変えるバッファ回路１９と、出力端子２１と、トレースバック制御回路２３とを備えて構成されている。
【００３４】
パスメモリ回路１３ａ、１３ｂは、それぞれ６４ビット×（２×Ｍｓ）ワードのＲＡＭである。また、パスメモリ回路１３ａとトレースバック回路１５ａ、パスメモリ回路１３ｂとトレースバック回路１５ｂは、それぞれ互いに独立に動作可能な組をなすものである。
【００３５】
次に、本実施の形態の動作を説明する。軟判定された復調データ’Ｉ’及び’Ｑ‘は、ＢＭＵ５によりブランチメトリックが算出される。次いで、正規化回路７によるパスメトリックのオーバフローを防ぐための正規化処理の後、各状態に対応したＡＣＳＵ９（図８に示した構成を３２組備える）にてパスメトリックの更新が行われる。各パスメトリックΓ（０）〜Γ（６３）のうち最尤パスに対応した最尤パスメトリックΓ（通常はΓの最小値：Γmin ）が最尤判定回路１１にて判定され、これが前記正規化に用いられる。
【００３６】
ビタビ復号の候補を必要段数（Ｍｓ段）記憶・保持するのが、それぞれ２×Ｍｓ段（２×Ｍｓワード）のパスメモリ回路１３ａ、１３ｂである。この内容の更新には、各状態に対応したいずれのパスを選択したかを示す選択フラグβ（０）〜β（６３）と、最尤パスに対応した最尤パス情報を用いる。なお、必要段数よりも十分大なる段数分記憶保持することが可能ならば、必ずしも最尤パス情報を必要としない。
【００３７】
トレースバック法を用いて数十Ｍｂｐｓの復号レートを実現する要点は、図１０に示したように、生き残りパスをいったんＭｓ段さかのぼったときに、すべての生き残りパスが１本に合流している場合には、さらにその先も１本に合流している（図１０の破線部分）という、きわめて明快で単純な原理を利用することである。
【００３８】
例えば、パスメモリ回路として２×Ｍｓ段分用意しておき、トレースバックの１周期を２×Ｍｓステップとする。上記の原理から、一旦Ｍｓ段トレースバックするとそこから先のトレースバックは、ビタビ復号の訂正能力の範囲内で正しい復号出力を次々と得ることができる。
【００３９】
ｋステップのトレースバック後のレジスタの内容Ｓｒ，ｋを、
【数１】
Ｓｒ，ｋ＝βｒ−ｋ（Ｓｒ，ｋ−１）＾（Ｓｒ，ｋ−１>>１）
とする。ここで、Ｓｒ，０＝ＳＬ，ｔである。すると、ビタビ復号出力はＭｓ≦ｋ≦２×Ｍｓの範囲で有効となり、
【数２】
δ（ｔ−ｋ）＝Ｓｒ，ｋ＾１
となる。
【００４０】
ただし、時間的に逆の順番で再生されるので、ＬＩＦＯ機能を有するバッファ回路１９を設けて正しい順に出力する。バッファ回路１９には、例えば１ビット×Ｍｓワードのメモリまたは左右シフト可能なシフトレジスタを用いても良い。このように、１回のトレースバックでビタビ復号出力がＭｓビット得られる。
【００４１】
トレースバックの開始する状態数は、最尤判定回路１１によって行われた最小状態から開始するとより正しいパスに収束しやすくなる。ただし、パスメモリの段数Ｍｓが十分に長い場合はどの状態からトレースバックを行っても、パスが収束する可能性が高いので、最尤判定を行わなくてもかまわない。
【００４２】
連続的にビタビ復号を行うには、２×Ｍｓ段のパスメモリ回路１３と図１１に詳細を示したトレースバック回路１５をそれぞれａおよびｂの２組用意し、時間差を与えて動作させ、それぞれの復号出力をセレクタ１７で切り替えて用いる。その動作を説明するタイミング図を図２に示す。
【００４３】
なお、パスメモリ回路１３とトレースバック回路１５との組の数は２に限定されず、例えば３組設けて、各パスメモリ回路を３×Ｍｓ段とし、各組を２×Ｍｓ段トレースバックした後、Ｍｓ段出力動作させることもできる。
【００４４】
図２のタイミング図において、十分に長い復号系列のビタビ復号が行われるものとし、それぞれβ（０）〜β（６３）からなる６４ビットで構成されたパス選択フラグβ（以下、６４ビットのパス選択フラグを単にβで示すとともに、時刻を示す添え字を付加する）がＡＣＳＵ９よりクロック毎に出力されるとする（図２（ａ））。
【００４５】
これによりパス選択フラグβｔはクロック毎に状態が変化するが、時系列上でＭｓ個ずつのパス選択フラグβｔにより、本実施の形態の動作の区切り（位相）がつけられている。図２（ｊ）には、Ｍｓクロック毎に動作の区切りを示す期間Ｔｉ（ｉ＝１，２，…）を付与している。
【００４６】
まず、図２（ａ）ないし（ｄ）及び（ｈ）ないし（ｊ）を参照して、パスメモリ回路１３ａ及びトレースバック回路１５ａからなるａ組の動作について説明する。
【００４７】
パスメモリ回路１３ａは、Ｔ１及びＴ２からなる最初の２Ｍｓクロックの期間に、２Ｍｓ個のパス選択フラグ部β0 〜β2Ms-1を順次アドレス昇順で各記憶番地に記憶する。そして、次のＭｓクロックの期間（Ｔ３）に、パスメモリ回路１３ａからパス選択フラグβ2Ms-1〜βMsがアドレス降順で読み出され、トレースバック回路ａによりトレースバックされる（ＴＢａ）。このトレースバック回路の“ＴＢ”とは、トレースバック動作のみでは出力しない読み捨てサイクルを示す。
【００４８】
次いで、次のＭｓクロックの期間（Ｔ４）に、パスメモリ回路１３ａからパス選択フラグβMs-1〜β0 がアドレス降順で読み出され、トレースバック回路１５ａによりトレースバックされ、有効なＭｓ個のトレースバック出力が出力される（ＯＵＴａ）とともに、セレクタ１７を介して順次バッファ回路１９に書き込まれる。
【００４９】
次いで、次のＭｓクロックの期間（Ｔ５）に、バッファ回路１９から書きこまれた順序と逆の順序（ＬＩＦＯ）でトレースバックデータを読み出し、ビタビ復号出力として出力端子２１より出力される。
【００５０】
次に、図２（ｅ）ないし（ｊ）を参照して、パスメモリ回路１３ｂ及びトレースバック回路１５ｂからなるｂ組の動作について説明する。ｂ組の動作は、ａ組の動作からＭｓクロックだけ位相が遅れている。
【００５１】
すなわち、パスメモリ回路１３ａの書き込み開始（Ｔ１の開始）からＭｓクロック遅れたＴ２の開始からパスメモリ回路１３ｂの書き込みが始まり、２Ｍｓクロックの期間（Ｔ２及びＴ３）に、２Ｍｓ個のパス選択フラグβMs〜β3Ms-1 を順次アドレス昇順で各記憶番地に記憶する。そして、次のＭｓクロックの期間（Ｔ４）に、パスメモリ回路１３ｂからパス選択フラグβ3Ms-1 〜β2Ms がアドレス降順で読み出され、トレースバック回路１５ｂによりトレースバックされる（ＴＢｂ）。
【００５２】
次いで、次のＭｓクロックの期間（Ｔ５）に、パスメモリ回路１３ｂからパス選択フラグβ2Ms-1 〜βMsがアドレス降順で読み出され、トレースバック回路１５ｂによりトレースバックされ、有効なＭｓ個のトレースバック出力が出力される（ＯＵＴｂ）とともに、セレクタ１７を介して順次バッファ回路１９に書き込まれる。
【００５３】
次いで、次のＭｓクロックの期間（Ｔ６）に、バッファ回路１９から書き込まれた順序と逆の順序（ＬＩＦＯ）でトレースバックデータを読み出してビタビ復号出力として出力端子２１より出力される。
【００５４】
次に、パスメモリ回路１３ａ及びトレースバック回路１５ａからなるａ組の読出修正書込動作について説明する。パスメモリ回路１３ａ（１３ｂも同様）は、前に説明したように４Ｍｓサイクルかけてデータを復号する。ただし、後半の２Ｍｓサイクル（例えば期間Ｔ３、Ｔ４）ではアドレスを降順でＲＡＭを読み出しているが、この１サイクルごとに各アドレスに対して読み出し−修正−書き込みを行う（リードモデファイライト）。
【００５５】
この２Ｍｓクロックの期間Ｔ３、Ｔ４に、パスメモリ回路１３ａの各記憶番地に対し、読み出し−修正−書き込みにより、２Ｍｓ個のパス選択フラグβ0 〜β2Ms-1 に対する読出しを順次アドレス“降順”で行うとともに、２Ｍｓ個のパス選択フラグβ2Ms 〜β4Ms-1 を順次アドレス“降順”（β0 〜β2Ms-1 を記憶したアドレス昇順とは逆であることに注目）で記憶する。
【００５６】
そして、次のＭｓクロックの期間（Ｔ５）に、読出−修正−書込により、パスメモリ回路１３ａからパス選択フラグβ4Ms-1 〜β3Ms がアドレス“昇順”で読み出され、トレースバック回路１５ａによりトレースバックされる（ＴＢａ）とともに、パス選択フラグβ4Ms 〜β5Ms-1 がアドレス“昇順”で書き込まれる。次いで、次のＭｓクロックの期間（Ｔ６）に、読出−修正−書込により、パスメモリ回路１３ａからパス選択フラグβ3Ms-1 〜β2Ms がアドレス“昇順”で読み出されるとともに、パス選択フラグβ5Ms 〜β6Ms-1 がアドレス“昇順”で書き込まれる。
【００５７】
このパスメモリ回路１３ａから読み出されたパス選択フラグβ3Ms-1 〜β2Ms は、有効なＭｓ個のトレースバック出力として出力される（ＯＵＴａ）とともに、セレクタ１７を介して順次バッファ回路１９に書き込まれる。
【００５８】
同様に、パスメモリ回路１３ｂにおいても、読出−修正−書込と、アドレスの昇順、降順の反転が行われる。
【００５９】
このようにＲＡＭのアクセスをアドレス昇順とアドレス降順とを交互に繰り返す利用法により、従来４個必要だったＲＡＭを２個で実現することが可能になった。
【００６０】
図３は、パスメモリ回路１３ａ、１３ｂを構成するメモリ回路周辺の入出力信号の詳細を示す回路図である。図３において、ＲＡＭ１０１には、入力信号であるアドレスＡＤＤＲ、書込信号ＷＥ、及び双方のメモリデータＤＡＴＡがある。ＤＡＴＡは、ＲＥでラッチされるラッチ１０５で受けられて、読出データＲead Ｄata として出力される。また外部から入力される書込データＷrite Ｄata は、３状態のバッファ１０３を介してＤＡＴＡに接続されている。書込モードまたは読出モードを指定するＲ／Ｗは、書込のとき３状態のバッファ１０３を有効し、読出のときに３状態のバッファ１０３の出力を無効にする。
【００６１】
図４は、図３のメモリの読出−修正−書込の動作のタイミングを示すタイムチャートである。アドレスＡＤＤＲとして、２Ｍｓ−１が与えられたとき、このＡＤＤＲの値の期間の前半で、Ｒ／Ｗが読出モードＲを示し、この期間の後半で、Ｒ／Ｗが書込モードＷを示す。Ｒ／Ｗが読出モードＲから書込モードＷに変わる直前のタイミングでＲＥ信号が”１”から”０”に変化し、読出データをラッチする。これと同時にＳ状態バッファが出力を有効とし、次いで、ＷＥパルスが与えられ、メモリに書込が行われる。このような、メモリの読出ー修正ー書込動作は、読出と書込とを同一アドレスに対して行うので、読出と書込とをそれぞれ別のアドレスに対して行うよりも高速に実行できる。
【００６２】
また本発明は実施の形態に示した回路構成だけでなく、例えばＤＳＰやＭＰＵといったソフトウェア操作によるビタビ復号においても、アドレスの共有化、パスメモリの節約、アクセス量の減少による高速化効果が確認された。
【００６３】
【発明の効果】
以上説明したように本発明によれば、ＡＣＳＵのパス選択結果を記録するパスメモリ手段と、このパスメモリ手段の値から情報系列を推定する複数のトレースバック手段と、備えるビタビ復号装置において、パスメモリ手段とトレースバック手段とを互いに独立に動作可能な複数組とし、この各組それぞれが、パスメモリへのアクセスをアドレス昇順とアドレス降順とを交互に繰り返すことによりパスメモリ更新動作及び出力動作を同時に行うとともに、各組で位相をずらして交互に動作することにより、パスメモリのアドレス発生回路およびＲＡＭが半分となるので大幅に回路規模を削減することができるという効果がある。
【図面の簡単な説明】
【図１】本発明の一実施形態を示すブロック図である。
【図２】トレースバックによる復号動作を示すタイミング図である。
【図３】パスメモリ回路の詳細を示す回路図である。
【図４】パスメモリ回路の読出修正書込（ＲＭＷ）のタイミング図である。
【図５】たたみ込み符号器の構成例を示す回路図である。
【図６】ビタビ復号法を説明するトレリス線図である。
【図７】状態遷移の組とパスメトリックとの関係を説明するための図である。
【図８】従来のビタビ復号装置全体の構成を示すブロック図である。
【図９】従来のビタビ復号装置全体の構成を示すブロック図である。
【図１０】生き残りパスの説明図である。
【図１１】従来のトレースバック回路の構成を示すブロック図である。
【図１２】従来のトレースバックによる復号動作を示すタイミング図である。
【符号の説明】
１…ビタビ復号装置、３…入力端子、５…ＢＭＵ、７…正規化回路、９…ＡＣＳＵ、１１…最尤判定回路、１３ａ、１３ｂ…パスメモリ回路、１５ａ、１５ｂ…トレースバック回路、１７…セレクタ、１９…バッファ回路、２１…出力端子、２３…トレースバック制御回路。
【図１】
0003753822.tif 000002
【図２】
0003753822.tif 000003
【図３】
0003753822.tif 000004
【図４】
0003753822.tif 000005
【図５】
0003753822.tif 000006
【図６】
0003753822.tif 000007
【図７】
0003753822.tif 000008
【図８】
0003753822.tif 000009
【図９】
0003753822.tif 000010
【図１０】
0003753822.tif 000011
【図１１】
0003753822.tif 000012
【図１２】
0003753822.tif 000013