(57)【要約】【課題】畳み込み符号をビタビ復号する際のトレースバック開始ステートを決定する処理が、小さな回路規模で高速で行えるようにする。【解決手段】畳み込み符号の各遷移状態でのパスの選択情報を記憶して、その記憶された情報を打ち切り長分だけトレースバックすることでビタビ復号を行う場合において、トレースバックの開始ステートを、ステートメトリックの一部のビットのみを利用して決定するようにして、簡易的に最小値を探索できるようにした。【選択図】　　　図２
2004128622.tif 000002
【特許請求の範囲】
【請求項１】
畳み込み符号の各遷移状態でのパスの選択情報を記憶して、その記憶された情報を打ち切り長分だけトレースバックすることでビタビ復号を行うビタビ復号方法において、
前記トレースバックの開始ステートを、ステートメトリックの一部のビットのみを利用して決定することを特徴とする
ビタビ復号方法。
【請求項２】
請求項１記載のビタビ復号方法において、
前記ステートメトリックが正規化されたことを示すフラグを設け、このフラグと前記一部のビットとを利用して、トレースバックの開始ステートを決定することを特徴とする
ビタビ復号方法。
【請求項３】
請求項１記載のビタビ復号方法において、
前記トレースバック開始ステートの決定を、前記一部のビットの最小値探索で行うことを特徴とする
ビタビ復号方法。
【請求項４】
請求項１記載のビタビ復号方法において、
前記トレースバック開始ステートの決定を、ステートメトリックの上位の１又は複数ビットの識別計算と、その結果をステート番号に変換して最小値探索で行うことを特徴とする
ビタビ復号方法。
【請求項５】
請求項４記載のビタビ復号方法において、
各ステートメトリックの最上位ビットが全て１になったときに、その最上位ビットを反転して正規化する場合に、
前記ステートメトリックの上位のビットの識別計算を、ステートメトリックの上位２ビットが００であるか０１であるか１０であるかを順次検出することにより行うことを特徴とする
ビタビ復号方法。
【請求項６】
請求項４記載のビタビ復号方法において、
前記ステートメトリックの上位のビットの識別計算結果をステート番号に変換して最小値探索を行う場合の、識別計算の結果として、最小値候補が複数あった場合に、ステート番号の小さい方から順位付けを行うことを特徴とする
ビタビ復号方法。
【請求項７】
請求項４記載のビタビ復号方法において、
前記ステートメトリックの上位のビットの識別計算結果をステート番号に変換して最小値探索を行う場合の、識別計算の結果として、最小値候補が複数あった場合に、ステート番号の大きい方から順位付けを行うことを特徴とする
ビタビ復号方法。
【請求項８】
請求項４記載のビタビ復号方法において、
前記ステートメトリックの上位のビットの識別計算結果をステート番号に変換して最小値探索を行う場合の、識別計算の結果として、最小値候補が複数あった場合に、ステート番号にランダムに順位付けを行うことを特徴とする
ビタビ復号方法。
【請求項９】
請求項２記載のビタビ復号方法において、
前記トレースバックの開始ステートの決定を、
ステートメトリックの上位ビットの識別計算と、その計算結果をステート番号に変換して最小値探索を行うことを特徴とする
ビタビ復号方法。
【請求項１０】
請求項９記載のビタビ復号方法において、
各ステートメトリックの最上位ビットが全て１になったときに、その最上位ビットを反転して正規化する場合に、
前記ステートメトリックの上位のビットの識別計算を、ステートメトリックの最上位ビットが０であるか１であるかと、ステートメトリックの最上位より１つ下の桁のビットが０であるか１であるかとを順次検出することにより行うことを特徴とする
ビタビ復号方法。
【請求項１１】
請求項９記載のビタビ復号方法において、
前記ステートメトリックの上位のビットの識別計算結果をステート番号に変換して最小値探索を行う場合の、識別計算の結果として、最小値候補が複数あった場合に、ステート番号の小さい方から順位付けを行うことを特徴とする
ビタビ復号方法。
【請求項１２】
請求項９記載のビタビ復号方法において、
前記ステートメトリックの上位のビットの識別計算結果をステート番号に変換して最小値探索を行う場合の、識別計算の結果として、最小値候補が複数あった場合に、ステート番号の大きい方から順位付けを行うことを特徴とする
ビタビ復号方法。
【請求項１３】
請求項９記載のビタビ復号方法において、
前記ステートメトリックの上位のビットの識別計算結果をステート番号に変換して最小値探索を行う場合の、識別計算の結果として、最小値候補が複数あった場合に、ステート番号にランダムに順位付けを行うことを特徴とする
ビタビ復号方法。
【請求項１４】
受信した畳み込み符号の各遷移状態でのパスの選択情報を記憶するパスメモリと、
該パスメモリの記憶情報を、打ち切り長分だけトレースバックさせる制御を行い、そのトレースバックの開始ステートを、ステートメトリックの一部のビットのみを利用して決定して、そのトレースバックさせた結果からビタビ復号された結果を得る制御手段とを備える
ビタビ復号装置。
【請求項１５】
請求項１４記載のビタビ復号装置において、
前記パスメモリに記憶されるステートメトリックを正規化する正規化手段と、前記正規化手段での正規化の有無に応じたフラグを設定するフラグ設定手段と、が行われたステートメトリックにフラグ正規化されたことを示すフラグとを設け、
前記制御手段は、フラグ設定手段で設定されたフラグと前記一部のビットとを利用して、トレースバックの開始ステートを決定することを特徴とする
ビタビ復号装置。
【請求項１６】
請求項１４記載のビタビ復号装置において、
前記制御手段でのトレースバック開始ステートの決定を、前記一部のビットの最小値探索で行うことを特徴とする
ビタビ復号装置。
【請求項１７】
請求項１４記載のビタビ復号装置において、
前記制御手段でのトレースバック開始ステートの決定を、ステートメトリックの上位の１又は複数ビットの識別計算と、その結果をステート番号に変換して最小値探索で行うことを特徴とする
ビタビ復号装置。
【請求項１８】
請求項１７記載のビタビ復号装置において、
受信した畳み込み符号のステートメトリックの最上位ビットが全て１になった場合に、その最上位ビットを反転して正規化する正規化手段を備えて、
前記制御手段でのステートメトリックの上位のビットの識別計算を、ステートメトリックの上位２ビットが００であるか０１であるか１０であるかを順次検出することにより行うことを特徴とする
ビタビ復号装置。
【請求項１９】
請求項１７記載のビタビ復号装置において、
前記制御手段でステートメトリックの上位のビットの識別計算結果をステート番号に変換して最小値探索を行う場合の、識別計算の結果として、最小値候補が複数あった場合に、ステート番号の小さい方から順位付けを行うことを特徴とする
ビタビ復号装置。
【請求項２０】
請求項１７記載のビタビ復号装置において、
前記制御手段でステートメトリックの上位のビットの識別計算結果をステート番号に変換して最小値探索を行う場合の、識別計算の結果として、最小値候補が複数あった場合に、ステート番号の大きい方から順位付けを行うことを特徴とする
ビタビ復号装置。
【請求項２１】
請求項１７記載のビタビ復号装置において、
前記制御手段でステートメトリックの上位のビットの識別計算結果をステート番号に変換して最小値探索を行う場合の、識別計算の結果として、最小値候補が複数あった場合に、ステート番号にランダムに順位付けを行うことを特徴とする
ビタビ復号装置。
【請求項２２】
請求項１５記載のビタビ復号装置において、
前記制御手段でのトレースバックの開始ステートの決定を、
ステートメトリックの上位ビットの識別計算と、その計算結果をステート番号に変換して最小値探索を行うことを特徴とする
ビタビ復号装置。
【請求項２３】
請求項２２記載のビタビ復号装置において、
受信した畳み込み符号のステートメトリックの最上位ビットが全て１になった場合に、その最上位ビットを反転して正規化する正規化手段を備えて、
前記制御手段でのステートメトリックの上位のビットの識別計算を、ステートメトリックの最上位ビットが０であるか１であるかと、ステートメトリックの最上位より１つ下の桁のビットが０であるか１であるかとを順次検出することにより行うことを特徴とする
ビタビ復号装置。
【請求項２４】
請求項２２記載のビタビ復号装置において、
前記制御手段でステートメトリックの上位のビットの識別計算結果をステート番号に変換して最小値探索を行う場合の、識別計算の結果として、最小値候補が複数あった場合に、ステート番号の小さい方から順位付けを行うことを特徴とする
ビタビ復号装置。
【請求項２５】
請求項２２記載のビタビ復号装置において、
前記制御手段でステートメトリックの上位のビットの識別計算結果をステート番号に変換して最小値探索を行う場合の、識別計算の結果として、最小値候補が複数あった場合に、ステート番号の大きい方から順位付けを行うことを特徴とする
ビタビ復号装置。
【請求項２６】
請求項２２記載のビタビ復号装置において、
前記制御手段でステートメトリックの上位のビットの識別計算結果をステート番号に変換して最小値探索を行う場合の、識別計算の結果として、最小値候補が複数あった場合に、ステート番号にランダムに順位付けを行うことを特徴とする
ビタビ復号装置。
【請求項２７】
畳み込み符号の各遷移状態でのパスの選択情報を記憶して、その記憶された情報を打ち切り長分だけトレースバックすることでビタビ復号を行う処理を実行するプログラムにおいて、
前記トレースバックの開始ステートを、ステートメトリックの一部のビットのみを利用して決定する処理を有することを特徴とする
プログラム。
【請求項２８】
請求項２７記載のプログラムにおいて、
上記ステートメトリックが正規化されたことを示すフラグを設け、このフラグと前記一部のビットとを利用して、トレースバックの開始ステートを決定することを特徴とする
プログラム。
【請求項２９】
請求項２７記載のプログラムにおいて、
前記トレースバック開始ステートの決定を、前記一部のビットの最小値探索で行うことを特徴とする
プログラム。
【請求項３０】
請求項２７記載のプログラムにおいて、
前記トレースバック開始ステートの決定を、ステートメトリックの上位の１又は複数ビットの識別計算と、その結果をステート番号に変換して最小値探索で行うことを特徴とする
プログラム。
【請求項３１】
請求項３０記載のプログラムにおいて、
各ステートメトリックの最上位ビットが全て１になったときに、その最上位ビットを反転して正規化する場合に、
前記ステートメトリックの上位のビットの識別計算を、ステートメトリックの上位２ビットが００であるか０１であるか１０であるかを順次検出することにより行うことを特徴とする
プログラム。
【請求項３２】
請求項３０記載のプログラムにおいて、
前記ステートメトリックの上位のビットの識別計算結果をステート番号に変換して最小値探索を行う場合の、識別計算の結果として、最小値候補が複数あった場合に、ステート番号の小さい方から順位付けを行うことを特徴とする
プログラム。
【請求項３３】
請求項３０記載のプログラムにおいて、
前記ステートメトリックの上位のビットの識別計算結果をステート番号に変換して最小値探索を行う場合の、識別計算の結果として、最小値候補が複数あった場合に、ステート番号の大きい方から順位付けを行うことを特徴とする
プログラム。
【請求項３４】
請求項３０記載のプログラムにおいて、
前記ステートメトリックの上位のビットの識別計算結果をステート番号に変換して最小値探索を行う場合の、識別計算の結果として、最小値候補が複数あった場合に、ステート番号にランダムに順位付けを行うことを特徴とする
プログラム。
【請求項３５】
請求項２８記載のプログラムにおいて、
前記トレースバックの開始ステートの決定を、
ステートメトリックの上位ビットの識別計算と、その計算結果をステート番号に変換して最小値探索を行うことを特徴とする
プログラム。
【請求項３６】
請求項３５記載のプログラムにおいて、
各ステートメトリックの最上位ビットが全て１になったときに、その最上位ビットを反転して正規化する場合に、
前記ステートメトリックの上位のビットの識別計算を、ステートメトリックの最上位ビットが０であるか１であるかと、ステートメトリックの最上位より１つ下の桁のビットが０であるか１であるかとを順次検出することにより行うことを特徴とする
プログラム。
【請求項３７】
請求項３５記載のプログラムにおいて、
前記ステートメトリックの上位のビットの識別計算結果をステート番号に変換して最小値探索を行う場合の、識別計算の結果として、最小値候補が複数あった場合に、ステート番号の小さい方から順位付けを行うことを特徴とする
プログラム。
【請求項３８】
請求項３５記載のビタビ復号方法において、
前記ステートメトリックの上位のビットの識別計算結果をステート番号に変換して最小値探索を行う場合の、識別計算の結果として、最小値候補が複数あった場合に、ステート番号の大きい方から順位付けを行うことを特徴とする
プログラム。
【請求項３９】
請求項３５記載のプログラムにおいて、
前記ステートメトリックの上位のビットの識別計算結果をステート番号に変換して最小値探索を行う場合の、識別計算の結果として、最小値候補が複数あった場合に、ステート番号にランダムに順位付けを行うことを特徴とする
プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、畳み込み符号の最尤復号に使用されるビタビ復号方法及びビタビ復号装置と、並びにこの復号処理を実行するプログラムに関する。
【０００２】
【従来の技術】
畳み込み符号を復号する方式の１つとして、ビタビ復号が知られている。このビタビ復号方式は、畳み込み符号に対する最尤復号方式であり、送信側のエンコーダで生成され得る符号系列の中から、受信された符号系列に最も近い系列（これを最尤パスという）を選ぶことで、誤り訂正を行う。
【０００３】
図１０は、ビタビ復号方式を用いた従来のビタビ復号装置の構成の一例を示したブロック図である。この図１０に示すビタビ復号装置は、受信データＳ１０００の各シンボル毎にシンボルメトリックを計算するシンボルメトリック計算回路１０００と、そのシンボル単位でのメトリック信号Ｓ１００１から、ブランチ毎のメトリックを計算するブランチメトリック計算回路１００１と、ブランチメトリック信号Ｓ１００２と記憶されたステートメトリックとを比較して加算する演算回路（以下ＡＣＳ回路と称する）１００２と、そのＡＣＳ回路１００２での比較及び加算で得られたステートメトリックを正規化する正規化回路１００３と、正規化回路１００３の出力を記憶するステートメトリック記憶回路１００４と、ＡＣＳ回路１００２から出力されるパス選択情報を記憶するパスメモリ回路１００５とを備えている。
【０００４】
ＡＣＳ回路１００２では、ブランチメトリック計算回路１００１から供給されるブランチメトリックと、ステートメトリック記憶回路１００４に記憶されたステートメトリックとに基づいて、あるステートに合流する２本のそれぞれのパスに対し、ブランチメトリックとステートメトリックを加算して比較し、この比較結果に基づいて尤度の高いものを選択して、新ステートメトリックとする。その選択内容を、パス選択情報Ｓ１００６として出力し、最小のステートメトリックをステートの番号を最尤ステート信号Ｓ１００７として出力し、新たに得られたステートメトリックを新ステートメトリック出力Ｓ１００３として出力する。パスメモリ回路１００５は、ＡＣＳ回路１００２が出力するパス選択情報Ｓ１００６を記憶し、同時にＡＣＳ回路１００２が出力する最尤ステート信号Ｓ１００７に基づいて、最尤パスに対応する情報の内、打ち切り長と呼ばれる一定の長さ以前の情報を復号データＳ１００８として出力する。
【０００５】
ここで、パスの選択方法について、拘束長Ｋ＝３の符号の場合を例として説明する。図１１の遷移ダイアグラム（以下トレリスと称する）に示すように、ステートとして、００，０１，１０，１１の４つのステートが存在するとすると、各タイムスロット毎に全てのステートには合流する２本のパスが存在する。そこで、あるステートに合流する２本のそれぞれのパスに対し、受信信号とパスとのハミング距離（ブランチメトリック）と、それまでのブランチメトリックの累積和（ステートメトリック）とをＡＣＳ回路１００２で加算して比較し、この比較結果に基づいて尤度の高いものが選択される。なお、図１１のトレリスでは、破線で示すパスが、データ１に対応したパスであり、実線で示すパスが、データ０に対応したパスである。以下に示す他のトレリスの場合も同様である。
【０００６】
正規化回路１００３は、ＡＣＳ回路１００２から出力される新ステートメトリック出力Ｓ１００３に対し、その値が予め設定されている範囲内の値になるように制御し、正規化ステートメトリック信号Ｓ１００４として出力する。正規化回路１００３での正規化方法としては、例えば、新ステートメトリック計算後に、毎タイムスロット、全ステートメトリックの中から最小のステートメトリックを減算する方法や、固定値を減算する方法がある。ビタビ復号装置を高速に動作させたい場合には、固定値を減算する方法の実装処理として、例えば各ステートメトリックの最上位ビットの値が“１”になった場合に、その最上位ビットを“０”に反転する処理が、装置化が容易であり、しばしば用いられる。
【０００７】
パスメモリ回路を実装させる場合には、レジスタ列を用いてパス選択内容を遷移させる方法が一般的であった。以下、この方法をレジスタ遷移法と称する。レジスタ遷移法においては、セレクタとレジスタとからなるメモリセルを、トレリス上に配置し、ＡＣＳ回路から出力されるパス選択情報にレジスタの内容を遷移させる。拘束長Ｋ＝３の符号の場合のメモリセルの配置を図１２に示す。各メモリセル１２０１，１２０２‥‥は、図１１に示したトレリスに従った配置としてあり、メモリセル１２０１の構成を示すと、２つの入力を選択するセレクタ１２０１ａと、そのセレクタ１２０１ａで選択されたデータを記憶するレジスタ１２０１ｂとで構成してあり、そのレジスタ１２０１ｂに記憶されたデータを、図１１に示したトレリスに従った順序で、次のタイムスロットに相当する位置の２つのメモリセルに送られる。その他のメモリセル１２０２，１２０３‥‥についても同じ構成である。
【０００８】
この図１２に示すようにパスメモリ回路を構成することで、レジスタ内には各ステートからの生き残りパスに対応する情報が保存されることになる。メモリセルは、打ち切り長分の段数が配置され、最終段の出力の内の最尤ステートの出力を選ぶことによって、最尤パスに対応する情報を選択し、復号データを出力する。
【０００９】
このレジスタ遷移法は、高速動作が可能であるというメリットがある反面、打ち切り長が長くなると回路規模が膨大になるといデメリットがある。特に最近では、打ち切り長が１００を超えるような場合もあり、回路規模の大きさは深刻な問題になっている。
【００１０】
このため、近年では、ＲＡＭ等を用いてパス選択情報を記憶し、その情報をトレースすることで復号する方法が盛んに研究されている。この記憶したパス選択情報をトレースする方法を、ここではトレースバック法と呼ぶ。
【００１１】
次に、トレースバック法におけるトレースの動作を、拘束長Ｋ＝３の場合を例にして説明する。図１３は、ステート０１からトレースする場合を示した図である。ステート０１へ遷移の可能性のあるステートは、拘束長Ｋ＝３の畳み込み符号の場合にはステート００とステート１０である。ここでパスメモリには、ステート００側のパスを選んであったときには０、ステート１０側のパスを選んであったときには１（即ち全体ステートの最上位ビット）が記憶してある。また、どちらから遷移する場合も、入力は１であり、これはステート０１の最下位ビットで表現されている。
【００１２】
以上より、トレースの動作は以下のように行えば良い。即ち、図１４に示すように、現在トレースを行っているステートの最下位ビットを復号ビットとし、次にトレースするステートの番号は現トレースステートの最上位ビットから下位２ビット目までに、パスメモリ内のビットを新たに最上位ビットとして付け加えることで生成する。この動作によって、最小ステートメトリックを取るステートから、選択されたパスを順次遡ることができる。
【００１３】
一方、打ち切り長の十分長いトレースバック法においては、ステートメトリックのビット幅に制限がなく、その値がクリップされないと仮定できる理想的なビタビ復号装置であれば、トレースバックの開始ステートを任意に設定しても最尤復号が保証されることが、Ｇ．Ｄ．Ｆｏｒｎｅｙの論文（　“Ｔｈｅ　Ｖｉｔｅｒｂｉ　Ａｌｇｏｒｉｔｈｍ　”，Ｐｒｏｃｅｅｄｉｎｇ　ｏｆ　ｔｈｅ　ＩＥＥＥ，Ｖｏｌ．６１，Ｎｏ３，Ｍａｒ．１９７３　）に記載されており、通常はオール０ステート（ステート００）からトレースバックを開始する。
【００１４】
【発明が解決しようとする課題】
ところが、実際のビタビ復号装置の実装を考えた場合、当然のことながら、ステートメトリックのビット幅には制限が存在する。このとき、例えば各ステートメトリックの最上位ビットが１となった場合に、その最上位ビットを０に反転させる正規化を行った場合、正規化が行われないままステートメトリックがクリップされた値を保持し続けるステートが発生し、最尤復号できないパターンが存在すると言う問題がある。
【００１５】
以下、その例を図面を参照しながら説明する。図１５は、拘束長Ｋ＝３の畳み込み符号化器を用いた例を示した図である。図１５の（ａ）はその畳み込み符号化器の構成を示し、図１５の（ｂ）は、その畳み込み符号の状態遷移を示した図である。この図１５に示した拘束長Ｋ＝３の畳み込み符号を受信して、復号する場合に、ここでは、ステートメトリックのビット幅を６ビットとし、ブランチメトリックのビット幅を５ビットと設定する。また、正規化は各ステートメトリックの最上位ビットが１になった場合に、その最上位ビットを０に反転するものとする。なお、ＡＣＳ回路内でステートメトリックはオーバーフローを起こさないように６３（即ち６ビットで表現される最大値）の値でクリッピングが行われているものとする。同様に、ブランチメトリック計算回路内でブランチメトリックは、オーバーフローを起こさないように３１（即ち５ビットで表現される最大値）の値でクリッピングが行われているものとする。また、符号語の１シンボル当たりのシンボルメトリックは、符号語と受信語が一致していれば０、不一致ならば１５と計算するものとする。
【００１６】
この場合の実際のトレリスの例を図１６に示す。この例では、正しいパスがオール１のパス（即ちデータ１が連続するパス）であるとして、打ち切り長は十分に長いとすると、オール１のパスを受信し続けた場合、トレリスのステートメトリックはある定常状態にあると考えて良い。これを、オール０ステート（ステート００）からトレースバックを開始して復号を行うと、図１６に示すように、ステート００を選び続け、本来復号されるべき最尤パスを復号できないことがある。これは、ステート００とステート１０からステート００に合流する２本のパスによって計算されるステートメトリックが、ともに６３という値にクリップされてパスの選択が正常に行われないことに起因している。図１６では、破線で示すパスが、データ１に対応したパスであり、実線で示すパスが、データ０に対応したパスである。
【００１７】
図１６の例の場合には、符号化器の３ビットの出力と、実際の３ビットの受信値との１ビット単位での比較で、値が異なる場合に、値として１５のシンボルメトリックを生成させる処理を、シンボルメトリック計算回路で行う。そして、ブランチメトリック計算回路では、その各ビット単位で計算されたシンボルメトリックをブランチ単位で加算する処理を行う。従って、３ビット全てが受信値と合っていた場合には、ブランチメトリックは０になり、３ビットの内のいずれか１ビットだけが受信値と異なっていた場合には、ブランチメトリックは１５になり、２ビットが異なっていた場合には、ブランチメトリックは３０になり、３ビット全てが異なっていた場合には、ブランチメトリックは４５になる。なお、ここで１ビットの違い毎に１５の値を加算するようにしたのは、軟判定を行うようにしたためである。即ち、実際にはビタビ復号の場合には軟判定を行うようにしてあり、そのときの状態により、各シンボルメトリックは０と１５の間の値を取る場合もある。但し、ここでは説明を簡単にするために、０又は１５であるとして説明する。
【００１８】
このようなステートメトリックを生成させて処理を行う。ここで、通常、同値のステートメトリックが、あるステートで合流した場合には、簡単化のために常に上側のパスが選択されるように実装が行われる。図１６の例では、ＡＣＳ回路内において、ステート００からステート００につながるパスによって計算されるステートメトリックが６３＋１５＝７８となり、クリップされて６３となる。一方、ステート１０からステート００につながるパスによって計算されるステートメトリックが６２＋１５＝７７となり、こちらもクリップされて６３となる。ＡＣＳ回路では、この合流する２つのメトリックを比較し、尤度の高い方を選択して次のタイムスロットにおけるステート００でのステートメトリックとするわけであるが、同値である６３同士の比較により、上側すなわちステート００からのパスを選択する。このため、打ち切り長を十分長くしても、トレースバックをオール０ステート（ステート００）から開始してしまうと、いつまで遡ってもステート１１にはたどり着かず、最尤復号ができないことになってしまう。図１６に太い実線で示した状態が、ステート００からのパスを選択し続ける状態を示してある。
【００１９】
もし、ステート１１からトレースバックを開始させた場合には、太い破線で示すように、元々正しいステートであるので、そのステート１１のパスを選択するが、ステート００からステート１１にたどり着くことはできない。
【００２０】
なお、通常のデータを受信した場合には、このようにデータ１が連続するようなことは稀であるが、何らかの要因で一時的にデータ１が連続することはあり得ないことではない。
【００２１】
このような問題を解決する方法の１つとして、トレースバックを開始するタイムスロットにおいて、ステートメトリックが最小であるステートを探索し、そのステートからトレースバックを開始することで、最尤復号を実現する方法がある。
【００２２】
図１７は、トレースバック開始ステート決定回路を備えたビタビ復号装置の一例を示すブロック図である。この図に示すビタビ復号装置は、シンボルメトリック計算回路１７００と、ブランチメトリック計算回路１７０１と、ＡＣＳ回路１７０２と、正規化回路１７０３と、ステートメトリック記憶回路１７０４と、パスメモリ回路１７０４を有する構成については、既に説明した図１０の対応した回路と同じで構成であるが、この例では、更にトレースバック開始ステート決定回路１７０６を備えている。そして、送信側から伝送路を通じて受信されたデータが入力されたとき、送信側のエンコーダで生成され得る符号系列の中から最尤パスを選んで、この選択内容に基づいて復号データを生成する。トレースバック開始ステート決定回路１７０６は、最小値計算回路で構成され、正規化回路１７０３が出力する全ての新ステートメトリック信号Ｓ１７０４の中から最小値を探索し、最小値を持つステート番号をトレースバック開始ステート信号Ｓ１７０９として出力する。これを元にパスメモリ回路１７０５においてトレースバックを開始し、その結果として復号データＳ１７０８を得る。
【００２３】
この処理を適用すれば、ステートメトリックのビット幅に制限が存在し正規化が行われないままステートメトリックがクリップされた値を保持し続けるステートが発生するような、図１６に示したような場合であっても最尤復号が可能になる。図１６の例の場合には、トレースバック開始ステート決定回路１７０６により最小ステートメトリックを持つステート１１が検出され、そこからトレースバックを開始することになり、図１６に太い破線で示すようなパスが順に検出されて、確かに最尤復号が実現できる。これは、最小のステートメトリックを持つステートでは、常に正常な比較と選択が行われているためである。
【００２４】
ところで、このようなビタビ復号装置においては、ステートメトリックの最小値計算回路を、忠実な最小値探索で実現してトレースバック開始ステート決定回路を構成していた。
【００２５】
図１８は、従来のトレースバック開始ステート決定回路の構成例を示した図である。図１８の回路は、拘束長Ｋ＝３、つまり状態数＝４の符号に対し、４つのステートの中から最小のステートメトリックを持つステートを探索し、そのステート番号Ｓ１８０１を出力する回路である。この例でも、ステートメトリックのビット幅は６ビットとしてある。
【００２６】
まず、４つのステートメトリックを２ステートずつ大小比較回路１８１０，１８２０でそれぞれ比較し、より小さなステートを持つ方を選択する。各大小比較回路１８１０，１８２０は、２つの入力の内の小さなステートを判断する比較器１８１１，１８２１と、それぞれの比較結果に基づいて判断されたステートのデータを選ぶセレクタ１８１２，１８２２とで構成される。
【００２７】
そして、各大小比較回路１８１０，１８２０で勝ち上がったステートメトリック同士を、次段の大小比較回路１８３０に供給して比較し、より小さなステートを持つ方を選択する。大小比較回路１８３０についても、２つの入力の内の小さなステートを判断する比較器１８３１と、比較結果に基づいて判断されたステートのデータを選ぶセレクタ１８３２とで構成される。このようにして、結果的に最小のステートメトリックＳ１８０２を持つステートが探索される。このとき、最小のステートメトリックをもつステートのステート番号Ｓ１８０１は、各大小比較回路での比較結果を束ね合わせることで求められる。
【００２８】
一般に、ビタビ復号において誤り訂正能力を高めるためには、符号の拘束長Ｋを大きくするが、そうするとトレリスの状態数は２Ｋ−１　となり、打ち切り長分のトレースバックを行う毎に、２Ｋ−１　個のステートメトリックの中から最小値を探索する処理が必要となる。最尤パスが非常に長い場合には、打ち切り長分のトレースバックを行って復号を繰り返すフィードバックループのループ回数は大きくなり、その中で２Ｋ−１　個の中の最小値探索のような時間のかかる処理を行うことは、ビタビ復号装置全体の動作速度を低下させてしまう。
【００２９】
また、任意の符号語系列について最尤復号が保証されるものの、図１８において示したよう大小比較回路が合計で２Ｋ−１　個必要となり、オール０ステート固定でトレースバックを開始する場合に比べて回路規模が非常に大きくなる。
【００３０】
以上述べたように、忠実な最小値計算回路で構成されるトレースバック開始ステートの決定処理は、最小値探索に必要となる回路規模が大きく、またこの最小値探索の動作時間に制約され復号装置全体の動作速度が上がらないという問題があった。
【００３１】
本発明はかかる点に鑑みてなされたものであり、トレースバック開始ステートを決定する場合に、回路規模が小さく、かつ高速で動作するようにすることを目的とする。
【００３２】
【課題を解決するための手段】
本発明は、畳み込み符号の各遷移状態でのパスの選択情報を記憶して、その記憶された情報を打ち切り長分だけトレースバックすることでビタビ復号を行う場合において、トレースバックの開始ステートを、ステートメトリックの一部のビットのみを利用して決定するようにしたものである。
【００３３】
このようにしたことで、トレースバック開始ステートを決定する際には、ステートメトリックの一部のビットのみを利用して、簡易的に最小値を探索でき、演算処理量や回路規模を削減することができる。
【００３４】
【発明の実施の形態】
以下、図１〜図５を参照して本発明の第１の実施の形態について説明する。
【００３５】
本例においては、従来例で説明した畳み込み符号をビタビ復号する際に、ビタビ復号装置内でトレースバックによりビタビ復号する構成としてある。ビタビ復号するデータは、例えば何らかの伝送路を介して受信したデータであるとする。即ち、ビタビ復号装置の基本的な構成については、従来例として図１７に示したビタビ復号装置を使用する。そして本例においては、図１７に示したビタビ復号装置の内の、トレースバック開始ステート決定回路１７０６を、図１に示した構成のトレースバック開始ステート決定回路１０１としたものである。
【００３６】
図１に示したトレースバック開始ステート決定回路１０１は、拘束長Ｋ＝３つまり状態数＝４の畳み込み符号に対し、４つのステートの中から、ステートメトリックの上位２ビットのみを利用して、「ステートメトリックのビット幅−１」のビット幅で決まる最大値以下のステートメトリックを持つステートを探索し、そのステート番号を出力することで、従来例として図１７及び図１８に示した復号装置と同等のビタビ復号性能を実現するトレースバック開始ステートメトリック決定回路である。ここでは、ステートメトリックのビット幅を６ビット、ブランチメトリックのビット幅を５ビットとする。
【００３７】
各ステート００，０１，１０，１１のステートメトリックの上位２ビットのデータは、トレースバック開始ステート決定回路１０１内の上位２ビット識別計算回路１０２に供給する。上位２ビット識別計算回路１０２では、各正規化ステートメトリックＳ１７０４の上位２ビットの信号であるＳ１０１〜Ｓ１０４に基づいて、その上位２ビットが００であるか０１であるか１０であるかをそれぞれ判断する。判断結果の信号Ｓ１０５をステート番号決定用プライオリティエンコーダ１０３でステート番号に変換し、トレースバック開始ステート信号Ｓ１０６を決定する。ステート番号決定用プライオリティエンコーダ１０３に供給するセレクト信号Ｓ１０７は、プライオリティエンコーダ１０３のプライオリティ（順位付け）を切り換えるための信号であり、予め順位付けを決められたものに限定しておけば必要ない信号である。
【００３８】
図２は、図１のトレースバック開始ステート決定回路１０１での処理を示したフローチャートである。まず、ステップＳＴ２０１においてステートメトリックの上位２ビットが００となるステートがあるか否か判断し、００となるステートがある場合には、ステップＳＴ２０４に移って、そのステート番号をプライオリティエンコーダを用いて求める。ステップＳＴ２０１でステートメトリックの上位２ビットが００となるステートがない場合には、ステップＳＴ２０２に移り、ステートメトリックの上位２ビットが０１となるステートがあれば、ステップＳＴ２０４に移って、そのステート番号をプライオリティエンコーダを用いて求める。ステップＳＴ２０２でステートメトリックの上位２ビットが０１となるステートがない場合には、ステップＳＴ２０３に移り、ステートメトリックの上位２ビットが１０となるステートがあれば、ステップＳＴ２０４に移って、そのステート番号をプライオリティエンコーダを用いて求める。
【００３９】
そしてステップＳＴ２０３において、ステートメトリックの上位２ビットが１０となるステートがなければ、全ステートメトリックの上位２ビットが１１であるため、ステップＳＴ２０５に移り、トレースバック開始ステート番号を００に設定する。但し、このステップＳＴ２０５に移ることは通常ではあり得ない。
【００４０】
次に、図１に示したトレースバック開始ステート決定回路１０１における上位２ビット識別計算回路１０２の構成例を、図３に示す。図３に示した上位２ビット識別計算回路３００（図１の上位２ビット識別計算回路１０２と同じ）は、正規化回路が出力する各正規化ステートメトリックＳ１７０４（図１７参照）の上位２ビットの信号である信号Ｓ１０１〜Ｓ１０４に基づいて、その上位２ビットが００であるか０１であるか１０であるかを、それぞれのステート００，０１，１０，１１毎に用意された識別回路３０１，３０２，３０３，３０４によって判断する。各識別回路３０１〜３０４は、全て同じ構成である。
【００４１】
ここでは、ステート００に対応する識別回路３０１を例にして説明すると、論理否定（ＮＯＴ）と論理和（ＯＲ）とから成る論理回路で、上位２ビット＝００の検出回路３０５と、上位２ビット＝０１の検出回路３０６と、上位２ビット＝１０の検出回路３０７が構成される。ステート００のステートメトリックの上位２ビットの信号Ｓ３０１及びＳ３０２は、並列にそれぞれの検出回路３０５〜３０７に入力される。
【００４２】
上位２ビット＝００の検出回路３０５は、ステートメトリックの最上位ビットＳ３０１と最上位より１つ下のビットＳ３０２との論理和の否定を取ることにより、００検出信号Ｓ３０３を出力する。この構成によって、ステートメトリックの上位２ビットが００である場合に、００検出信号Ｓ３０３として１が出力される。
【００４３】
各ステート毎の００検出信号Ｓ３０３〜Ｓ３０６は、ステート番号００，ステート番号０１，‥‥に対応するものか順に最下位ビットから束ねられて、ステート数分のビット幅を持つ出力信号Ｓ３１５となる。
【００４４】
同様の構成により、上位２ビット＝０１の検出回路３０６は、０１検出信号Ｓ３０７を出力する。各ステート毎の０１検出信号Ｓ３０７〜Ｓ３１０は、順に束ねられて出力信号Ｓ３１６となる。また、上位２ビット＝１０の検出回路３０７は、１０検出信号Ｓ３１１を出力する。各ステート毎の１０検出信号Ｓ３１１〜Ｓ３１４は、順に束ねられて出力信号Ｓ３１７となる。
【００４５】
各検出回路の出力信号をステート番号順に束ねた信号Ｓ３１５〜Ｓ３１７は、セレクタ回路３０８に入力される。セレクタ回路３０８は、図２のフローチャートに基づいた処理が行われる。
【００４６】
先ず、００検出信号をステート番号順に束ねた信号Ｓ３１５が０であるか否かを判断し、０でない場合には、「ステートメトリックのビット幅−２」のビット幅で決まる最大値以下のステートメトリックを持つステートが存在することになるため、これをセレクタ回路３０８の出力Ｓ３１８とし、次段のプライオリティエンコーダへの入力とする。信号Ｓ３１５が０ならば、次に、０１検出信号をステート番号順に束ねた信号Ｓ３１６が０であるか否かを判断し、０でない場合には、「ステートメトリックのビット幅−１」のビット幅で決まる最大値以下のステートメトリックを持つステートが存在することになるため、これをセレクタ回路３０８の出力Ｓ３１８とし、次段のプライオリティエンコーダへの入力とする。信号Ｓ３１６が０ならば、各ステートメトリックは正規化直前のタイムスロットにあることになるため、１０検出信号をステート番号順に束ねた信号Ｓ３１７をセレクタ回路３０８の出力Ｓ３１８とし、次段のプライオリティエンコーダへの入力とする。
【００４７】
ここで、プライオリティエンコーダの回路の一例を図４に示す。プライオリティエンコーダは、あるビット列の中に或る“１”が最下位ビットから数えて何番目に位置しているかを、予め決められたプライオリティ（順位付け）に基づいて、２進数として出力する回路である。ビット列中に複数の１があった場合の順位付けの方法は、ステート番号の小さい方から行う方法とステート番号の大きい方から行う方法とステート番号にランダムに順位を付けたテーブルを参照して行う方法とがある。図４はステート番号の小さい方から順位付けを行う場合の回路を論理ゲート回路の接続で構成させた例を示した図ある。
【００４８】
ステート数分のビット幅を持つ判断結果の信号Ｓ３１８は、上位２ビット識別計算の条件に適合したビットが１になっており、その“１”のある位置がステート番号に対応している。図４の例では、ステート０１および１０に対応するビットが１になっており、この入力に対して出力が０１となり、ステート番号に対応した出力が求められていることが分かる。したがって、プライオリティエンコーダを利用すれば所望のトレースバック開始ステートのステート番号を得ることができる。
【００４９】
なお、図４の例は、ステート番号の小さい方から順位付けを行う場合を例としたが、上位２ビット識別計算回路１０２と順位付けとの組合せは任意とすることができる。図１にあるように、セレクト信号Ｓ１０７を用いて順位付けの方法を適宜切り換えられる構成にしてもよい。
【００５０】
以上述べたように、図１〜４に示した本例の構成とすることで、「ステートメトリックのビット幅−１」のビット幅で決まる最大値以下のステートメトリックを持つステート検索できるため、従来例と同等のビタビ復号性能を実現できるようになる。
【００５１】
そして本例の場合には、各ステートメトリックの上位２ビットのみを使用することになるため、最小値計算回路で使用される信号線のビット数を大幅に削減できる。また、論理和と論理否定の組合せといった、非常に小規模かつ高速に動作する論理回路で実現可能である。
【００５２】
ここで、本例の構成で、最適なトレースバック開始ステートが探索できることについて説明する。最尤復号を実現するためには、真に最小のステートメトリックを探索する必要はなく、「ステートメトリックのビット幅−１」のビット幅で決まる最小値以下のステートメトリックを持つステートを探索できればよく、簡易的な最小値探索方法で十分であることを以下に説明する。
【００５３】
ここでは、図１５に示した拘束長Ｋ＝３の畳み込み符号化器を用いる場合を例として説明する。ステートメトリックのビット幅を６ビットとし、ブラントメトリックのビット幅を５ビットと設定する。正規化は各ステートメトリックの最上位ビットが１になった場合にその最下位ビットを判定して行うものとする。なお、ＡＣＳ回路内でステートメトリックはオーバーフローを起さないように“６３”（６ビットで表現される最大値）の値でクリッピングが行われているものとする。同様に、ブランチメトリック計算回路内でブランチメトリックはオーバーフローを越さないように“３１”（５ビットで表現される最大値）の値でクリッピングが行われているものとする。また符号語の１シンボル当りのシンボルメトリックは、符号語と受信語が一致していれば０、不一致ならば１５と計算するものとする。
【００５４】
発明が解決しようとする課題の欄で既に述べたように、打ち切り長を十分長くしても、トレースバックをオール０ステート（ステート００）から開始してしまうと最尤復号ができないことがあり、その主たる原因は、ステートメトリックの採り得る最大値にステートメトリックがクリップされている場合にクリップ値同士のパスの比較、選択が行われているステートからトレースバックを開始してしまうことにあった。
【００５５】
逆に言えば、クリップされていないステートメトリックを持つステートでは、正常な比較と選択が行われているため、最尤パスに辿り着けることになる。
【００５６】
最小のステートメトリックを持つステートは最も尤度の高いパスが通ったと推測されるステートであるため、そのステートからトレースバックを開始すれば、最尤復号は可能となることは明らかであるが真に最小のステートメトリックを持つステートを探索する必要はなく、クリップされていないステートメトリックを探索できればよい。
【００５７】
ここで注意すべきは、各ステートメトリックの最上位ビットが全て１になった場合にその最上位ビットを反転する正規化が行われることであり、単にクリップされていないステートメトリックを探索するだけでは十分とは言えないことである。正規化の直前、直後での各ステートメトリックを把握することが重要となる。
【００５８】
この例の場合、正規化は各ステートメトリックが３２以上となった場合に起こる。したがって、正規化処理が行われる直前に最尤ステートに貼り付けているステートメトリックの最大値は３１となる。よって基本的には３１以下のステートメトリックを探索すればよい。つまり、「ステートメトリックのビット幅−１」のビット幅で決まる最大値以下のステートメトリックを持つステートを探索できればよいことになる。
【００５９】
既に説明した図１９は、正規化直前においてステートメトリックが取り得る値を示している。あるステートから次のタイムスロットのステートへ伸びる枝は符号化器への入力が０に対応したもの（実線）と１に対応したもの（点線）と２種類あり、そのときの符号化器の出力すなわち符号語は畳み込み符号化器の性質上、互いをビット反転させたものとなる。例えば、符号化器への入力０に対する符号語ｃ２ｃ１ｃ０が１１１であったとすると入力１に対する符号語は０００となる。いま、受信値系列ｒ２ｒ１ｒ０が００１であったとすると、それぞれの符号語に対するブランチメトリックは図１９中に示すように、入力０に対するパスのブランチメトリックが３０、入力１に対するパスのブランチメトリックが１５となる。これを一般化すると、あるステートから次のタイムスロットのステートへ伸びる２本の枝のブランチメトリックの組合せは図１９中に示すように全４通りに限定される。
【００６０】
これを踏まえ、最尤ステートから到達するステートの正規化直前におけるステートメトリックを考えると、各ステートメトリックが全て４６以上になる場合が考えられる。これは回路実装の制約上実際には、各ステートメトリックの最上位ビットが全て１となった次のクロックで正規化処理が行われるためである。この４６という値は、「ステートメトリックのビット幅−１」のビット幅で決まる最大値にシンボルメトリックの最大値を加えたものとして一般に求められる。
【００６１】
一方、正規化直後は各ステートメトリックの最上位ビットが反転されて全ステートメトリックが３１以下となり、そのタイムスロットではステートメトリックの取り得る値が見掛け上では通常の半分となる。この場合は、ステートメトリックのビット幅が６ビットから５ビットになったと捉えることに相当し、「ステートメトリックのビット幅−２」のビット幅で決まる最大値以下のステートメトリックを持つステートを探索できればよいことになる。
【００６２】
以上述べたように、最尤復号を実現するためには、真に最小のステートメトリックを探索する必要はなく、基本的には「ステートメトリックのビット幅−１」のビット幅で決まる最大値以下のステートメトリックを持つステート探索できればよく、正規化直前には「ステートメトリックのビット幅−１」のビット幅で決まる最大値にシンボルメトリックの最大値を加えた値以下のステートメトリックを持つステート、正規化直後には「ステートメトリックのビット幅−２」のビット幅で決まる最大値以下のステートメトリックを持つステートを探索できればよい。
【００６３】
ところで、この例の場合においては、「ステートメトリックのビット幅−１」のビット幅で決まる最大３１を６ビットの２進数で表記すると０１１１１１であり、「ステートメトリックのビット幅−２」のビット幅で決まる最大値１５を６ビットの２進数で表記すると００１１１１である。また、最尤ステートから１タイムスロットで到達し得るステートのステートメトリックの最大値は４６であったため、これを６ビットの２進数で表記すると１０１１１０である。
【００６４】
したがって、最悪の場合でも、各ステートメトリックの上位２ビットが全て１１となることはおこり得ないことが分かる。このことは、ステートメトリックのビット幅がブランチメトリックのビット幅より大きければ成立するため、少なくともステートメトリックの上位２ビットのみを識別することで、簡易的に最小値を探索することが可能となる。
【００６５】
よって、本例によるビタビ復号装置は、上述したステートメトリックの性質を利用し、トレースバック開始ステート決定回路において、ステートメトリックの上位数ビットのみ、あるいは、ステートメトリックの上位数ビットと正規化が起こったことを示すフラグとを利用することで簡易的に最小値を探索する構成に基づいて、トレースバック開始ステートを決定することで、簡単な構成で高速にトレースバック開始ステートを決定することが可能になり、良好なビタビ復号処理が簡単な構成で迅速に行えるようになる。
【００６６】
例えば、従来例で図１６に示したように、正しいパスがオール１のパス（即ちデータ１が連続するパス）の場合のトレリスを、再度図５に示す。この図５の例でのトレースバック開始点として、本例の場合には、ステートメトリックが最小となるステート１１が検出され、太い破線で示すように、そのステート１１からトレースバックが行われて、トレースバックによる正しいビタビ復号が可能になる。
【００６７】
次に本発明の第２の実施の形態を、図６を参照して説明する。図６は、本例における、ビタビ復号装置のトレースバック開始ステート決定回路の構成例である。本例においてもビタビ復号装置の基本的な構成については、従来例として図１７に示したビタビ復号装置を使用し、図１７に示したビタビ復号装置の内の、トレースバック開始ステート決定回路１７０６を、図６に示した構成のトレースバック開始ステート決定回路６０１としたものである。
【００６８】
図６の回路は拘束長Ｋ＝３つまり状態数＝４の符号に対し、４つのステートの中から、ステートメトリックの上位２ビットのみを利用して、「ステートメトリックのビット幅−１」のビット幅で決まる最大値以下のステートメトリックを持つステートを探索し、そのステート番号を出力することで、図１７および図１８に示した従来例と同等のビタビ復号性能を実現するトレースバック開始ステート決定回路としたものである。ただし、ステートメトリックのビット幅を６ビット、ブランチメトリックのビット幅を５ビットとする。
【００６９】
図６の回路において、トーナメント方式の最小値計算回路で構成されるトレースバック開始ステート決定回路６０１は、各正規化ステートメトリックＳ１７０４の上位２ビットの信号であるＳ６０１〜Ｓ６０４を２ステートずつ大小比較回路６１０，６２０でそれぞれ比較し、より小さいステートメトリックを持つ方を選択する。上位２ビットが同じであった場合にどちらも選択するかは任意でよい。次に、トーナメント方式で勝上がったステートメトリックの上位２ビット同士を大小比較回路６３０で比較し、より小さなステートメトリックを持つ方を選択すると、４つのステートの中で最小のステートメトリックの上位２ビットＳ６０６を持つステートが探索される。このとき、簡易的に最小のステートメトリックをもつステートのステート番号Ｓ６０５は、各大小比較回路での比較結果を束ね合わせることで求められる。
【００７０】
大小比較回路６１０，６２０は、それぞれ比較器６１１，６２１と、その比較器で小さいステートメトリックを持つと判断された方を選択するセレクタ６１２，６２２を備える。同様に、大小比較回路６３０は、比較器６３１と、その比較器で小さいステートメトリックを持つと判断された方のステート番号を選択するセレクタ６３２と、そのステート番号のデータを選択するセレクタ６３３とを備える。
【００７１】
このように構成することで、「ステートメトリックのビット幅−１」のビット幅で決まる最大値以下のステートメトリックを持つステートを探索できるため、従来例と同等のビタビ復号性能を実現できるようになる。
【００７２】
図６に示した構成にすると、各ステートメトリックの上位２ビットのみを使用することになるため、大小比較回路内の比較およびセレクタで使用される信号線のビット数を大幅に削減できるため、非常に小規模かつ高速に動作する回路で実現可能である。
【００７３】
次に本発明の第３の実施の形態を、図７〜図９を参照して説明する。図７は、本例における、ビタビ復号装置のトレースバック開始ステート決定回路の構成例である。本例においてもビタビ復号装置の基本的な構成については、従来例として図１７に示したビタビ復号装置を使用し、図１７に示したビタビ復号装置の内の、トレースバック開始ステート決定回路１７０６を、図７に示した構成のトレースバック開始ステート決定回路７０１としたものである。
【００７４】
図７の回路は拘束長Ｋ＝３つまり状態数＝４の符号に対し、４つのステートの中から、ステートメトリックの上位２ビットと正規化が起こったことを示すフラグとを利用して、「ステートメトリックのビット幅−１」のビット幅で決まる最大値以下のステートメトリックを持つステートを探索し、そのステート番号を出力することで、図１７および図１８に示した従来例と同等のビタビ復号性能を実現するトレースバック開始ステート決定回路である。ただし、ステートメトリックのビット幅を６ビット、ブランチメトリックのビット幅を５ビットとする。
【００７５】
図７の回路において、上位２ビット識別計算回路７０２では、各正規化ステートメトリックＳ１７０４の上位２ビットの信号であるＳ７０１〜Ｓ７０４および正規化が起こったことを示す正規化検知フラグＳ７０７に基づいて、その上位２ビットが００であるか０１であるか１０であるかをそれぞれ判断する。判断結果の信号Ｓ７０５をプライオリティエンコーダ７０３でステート番号に変換し、トレースバック開始ステート信号Ｓ７０６を決定する。セレクト信号Ｓ７０８は、プライオリティエンコーダ７０３のプライオリティ（順位付け）を切り換えるための信号であり、予め順位付けを限定しておけば必要とならないものである。
【００７６】
図８は、本例の処理を示したフローチャートである。先ず、ステップＳＴ８０１において、正規化検知フラグが１であるか否かを判断する。１ならば正規化直後であるため、ステップＳＴ８０３においてステートメトリックの最上位より１つ下のビットが０となるステートがあれば、ステップＳＴ８０４にてそのステート番号をプライオリティエンコーダを用いて求める。実際にはおこり得ないが、ステップＳＴ８０３においてステートメトリックの最上位より１つ下のビットが０となるステートがなければ、全ステートメトリックの上位２ビットが正規化直後にも関わらず０１となってしまうため、ステップＳＴ８０５にてトレースバック開始ステート番号を００に設定する。正規化検知フラグが０ならば、ステップＳＴ８０２においてステートメトリックの最上位ビットが０となるステートがあればステップＳＴ８０４にてそのステート番号をプライオリティエンコーダを用いて求める。
【００７７】
ステップＳＴ８０２においてステートメトリックの最上位ビットが０となるステートがなければ、次に、ステップＳＴ８０３においてステートメトリックの最上位より１つ下のビットが０となるステートがあれば、ステップＳＴ８０４にてそのステート番号をプライオリティエンコーダを用いて求める。実際には起こり得ないが、ステップＳＴ８０３においてステートメトリックの最上位より１つ下のビットが０となるステートがなければ、ステップＳＴ８０５にて全ステートメトリックの上位２ビットが１１であるため、トレースバック開始ステート番号を００に設定する。
【００７８】
ここで、本例のトレースバック開始ステート決定回路における上位２ビット識別計算回路の構成例を図９に示す。各正規化ステートメトリックＳ１７０４の上位２ビットの信号であるＳ７０１〜Ｓ７０４（図７参照）に基づいて、その上位２ビットが００であるか０１であるか１０であるかを、識別回路９０１〜９０４によってそれぞれ判断する。識別回路９０１〜９０４はそれぞれ各ステート００，０１，１０，１１に対応しており、全て同じ構成を持つ。
【００７９】
ステート００に対応する識別回路９０１を例にその構成と動作を説明する。識別回路９０１は、それぞれ論理否定を行う論理回路のみから成る、最上位ビット＝０の検出回路９０５と、最上位より１つ下のビット＝０の検出回路９０６とから構成される。
【００８０】
ステート００のステートメトリックの上位２ビットの信号Ｓ９０１およびＳ９０２は、並列にそれぞれの検出回路９０５，９０６に入力される。
【００８１】
最上位ビット＝０の検出回路９０５はステートメトリックの最上位ビットＳ８０１の論理否定を採ることにより、０検出信号Ｓ９０３を出力する。この構成によって、各ステートメトリックの最上位ビットが０である時に０検出信号Ｓ９０３として１が出力される。各ステート毎の０検出信号Ｓ９０３〜Ｓ９０６は、ステート番号００、ステート番号０１，…，に対応するものから順に最下位ビット側から束ねられて、ステート数分のビット幅を持つ出力信号Ｓ９１１となる。
【００８２】
同様の構成により、最上位より１つ下のビット＝０の検出回路９０６は、０検出信号Ｓ９０７を出力する。各ステート毎の０検出信号Ｓ９０７〜Ｓ９１０は、順に束ねられて出力信号Ｓ９１２となる。
【００８３】
前記各検出回路の出力信号をステート番号順に束ねた検出信号Ｓ９１１，Ｓ９１２は、各ステートメトリックの最上位ビットの論理積（ＡＮＤ）を論理回路９０８によって取った正規化検知フラグＳ９１３とともにセレクタ回路９０７に入力される。正規化検知フラグＳ９１３はビット反転による正規化処理のタイミングにより、正規化処理の行われた後のタイムスロットにおいて１が出力される。つまり、各ステートメトリックの最上位ビットが全て０にビット判定された体のスロットで１となる。セレクタ回路９０７は、図８のフローチャートに基づいて選択が行われる回路として構成される。
【００８４】
先ず、正規化検知フラグＳ９１３が１つまり正規化直後であるか否かを判断する。１ならば、「ステートメトリックのビット幅−２」のビット幅で決まる最大値以下のステートメトリックを持つステートは必ず存在するため、最上位より１つ下のビット＝０の検出信号をステート番号順に束ねた信号Ｓ９１２をセレクタ回路９０７の出力Ｓ９１４とし、次段のプライオリティエンコーダへの入力とする。正規化検知フラグＳ９１３が０ならば次に、最上位ビット＝０の検出信号をステート番号順に束ねたＳ９１１が０であるか否かを判断し、０でないならば、「ストリートメトリックのビット幅−１」のビット幅で決まる最大値以下のステートメトリックを持つステートが存在することになるため、これをセレクタ回路の出力Ｓ９１４とし、次段のプライオリティエンコーダへの入力とする。信号Ｓ９１１が０ならば、各ステートメトリックは正規化直前の体のスロットにあることになるため、最上位より１つ下のビット＝０の検出信号をステート番号順に束ねたＳ９１２をセレクタ回路の出力Ｓ９１４とし、次段のプライオリティエンコーダへの入力とする。
【００８５】
以上述べたように図７〜図９に示した構成にすることによっても、「ステートメトリックのビット幅−１」のビット幅で決まる最大値以下のステートメトリックを持つステートを探索できるため、従来例と同等のビタビ復号性能を実現できるようになる。
【００８６】
なお、第３の実施の形態による構成例は、第１の実施の形態による構成例と同じく、上位２ビット識別計算回路７０２とプライオリティエンコーダ７０３における順位付けとの組合せは任意とすることができる。また、図７にあるように、セレクタ信号Ｓ７０８を用いて順位付けの方法を適宜切り換えられる構成にしても良い。
【００８７】
図７〜図９に示した構成にすると、各ステートメトリックの上位２ビットのみを使用することになるため、最小値計算回路で使用される信号線のビット数を大幅に削減できる。また、上位２ビットを１ビットずつ独立に使用するため、回路は論理否定のみで構成され、非常に小規模かつ高速に動作する論理回路で実現可能である。
【００８８】
なお、以上に示した第１，第２，第３の実施の形態の構成例は、拘束長Ｋ＝３、ステートメトリックのビット幅＝６ビット、ブランチメトリックのビット幅＝５ビットの場合を例としたが、これらはこの値に限らず、任意の値とすることができる。また、以上の例は、最小値計算回路で利用するステートメトリックのビット数を２ビットとしたが、この値に限らず、２ビット以上でステートメトリックのビット値以下の任意の値とすることができる。さらに正規化方法に関しても、各ステートメトリックの最上位ビットが全て１になった場合にその最上位ビットを反転するステートメトリック正規化方法にのみ限定されるものではなく、他の正規化方法を利用した場合の適用も考えられる。
【００８９】
例えば、正規化回路として、ステートメトリックのビットデータを、下位桁にビットシフトさせて、値を小さくする場合にも適用可能である。或いは、単純に値を１／２にして、正規化する正規化回路にも適用可能である。
【００９０】
また、ここまで説明したビタビ復号装置は、ハードウェアとして構成された回路で復号処理を行う装置としたが、例えばコンピュータ装置に、同様の処理を実行するプログラムを実装させて、そのコンピュータ装置が有する演算手段と記憶手段を使用して、同様のビタビ復号を行うように構成しても良い。
【００９１】
【発明の効果】
本発明によると、トレースバック開始ステートを決定する際には、ステートメトリックの一部のビットのみを利用して、簡易的に最小値を探索でき、演算処理量や回路規模を削減することができ、トレースバックによるビタビ復号を行う際に、簡単な構成で高速動作するという効果が得られる。
【図面の簡単な説明】
【図１】本発明の第１の実施の形態によるトレースバック開始ステート決定回路の一例を示すブロック図である。
【図２】図１例の構成でのトレースバック開始ステート決定処理を示すフローチャートである。
【図３】図１例の回路における上位２ビット識別計算回路の構成例を示すブロック図である。
【図４】本発明の第１の実施の形態によるステート番号決定用プライオリティエンコーダの一例を示す構成図である。
【図５】本発明による復号トレリスの例を示す説明図である。
【図６】本発明の第２の実施の形態によるトレースバック開始ステート決定回路の一例を示すブロック図である。
【図７】本発明の第３の実施の形態によるトレースバック開始ステート決定回路の一例を示すブロック図である。
【図８】図７例の構成でのトレースバック開始ステート決定処理を示すフローチャートである。
【図９】図７例の回路における上位２ビット識別計算回路の構成例を示すブロック図である。
【図１０】従来のビタビ復号装置の構成例を示すブロック図である。
【図１１】拘束長Ｋ＝３の畳み込み符号の場合の遷移ダイアグラムである。
【図１２】レジスタ遷移法におけるメモリセルの配置例を示した構成図である。
【図１３】トレースバック法におけるトレースの原理を示した説明図である。
【図１４】トレースバック法におけるトレース方法を示した説明図である。
【図１５】拘束長Ｋ＝３の畳み込み符号化器と状態遷移の例を示した説明図である。
【図１６】従来の復号トレリスの例を示す説明図である。
【図１７】トレースバック開始ステート決定回路を備えたビタビ復号装置の例を示したブロック図である。
【図１８】従来のトレースバック開始ステート決定回路の一例を示すブロック図である。
【図１９】正規化直前のステートメトリックが取り得る値を示した説明図である。
【符号の説明】
１０１…トレースバック開始ステート決定回路、１０２…上位２ビット識別計算回路、１０３…ステート番号決定用プライオリティエンコーダ、３００…上位２ビット識別計算回路、３０１…ステート００用上位２ビット識別計算回路、３０２…ステート０１用上位２ビット識別計算回路、３０３…ステート１０用上位２ビット識別計算回路、３０４…ステート１０用上位２ビット識別計算回路、３０５，３０６，３０７…論理回路、３０８…セレクタ、６０１…トレースバック開始ステート決定回路、６１０，６２０，６３０…大小比較回路、６１１，６２１，６３１…比較器、６１２，６２２，６３２，６３３…セレクタ、７０１…トレースバック開始ステート決定回路、７０２…上位２ビット識別計算回路、７０３…ステート番号決定用プライオリティエンコーダ、９００…上位２ビット識別計算回路、９０１…ステート００用上位２ビット識別計算回路、９０２…ステート０１用上位２ビット識別計算回路、９０３…ステート１０用上位２ビット識別計算回路、９０４…ステート１０用上位２ビット識別計算回路、９０５，９０６…論理回路、９０７…セレクタ、１０００…シンボルメトリック計算回路、１００１…ブランチメトリック計算回路、１００２…ＡＣＳ回路（比較及び加算回路）、１００３…正規化回路、１００４…ステートメトリック記憶回路、１００５…パスメモリ回路、１２０１〜１２１６…メモリセル、１２０１ａ…セレクタ、１２０１ｂ…レジスタ、１７００…シンボルメトリック計算回路、１７０１…ブランチメトリック計算回路、１７０２…ＡＣＳ回路、１７０３…正規化回路、１７０４…ステートメトリック記憶回路、１７０５…パスメモリ回路、１７０６…トレースバック開始ステート決定回路、１０３…ステート番号決定用プライオリティエンコーダ、１８００…トレースバック開始ステート決定回路、１８１０，１８２０，１８３０…大小比較回路、１８１１，１８２１，１８３１…比較器、１８１２，１８２２，１８３２，１８３３…セレクタ
【図１】
2004128622.tif 000003
【図２】
2004128622.tif 000004
【図３】
2004128622.tif 000005
【図４】
2004128622.tif 000006
【図５】
2004128622.tif 000007
【図６】
2004128622.tif 000008
【図７】
2004128622.tif 000009
【図８】
2004128622.tif 000010
【図９】
2004128622.tif 000011
【図１０】
2004128622.tif 000012
【図１１】
2004128622.tif 000013
【図１２】
2004128622.tif 000014
【図１３】
2004128622.tif 000015
【図１４】
2004128622.tif 000016
【図１５】
2004128622.tif 000017
【図１６】
2004128622.tif 000018
【図１７】
2004128622.tif 000019
【図１８】
2004128622.tif 000020
【図１９】
2004128622.tif 000021