(57)【要約】【課題】ビタビ復号におけるトレースバック処理を簡単化する。【解決手段】入力される符号ビットに対し，取りうる状態ビットに対応して，その状態ビットのパスメトリックに応じて最尤の遷移元状態ビットを選択して，サバイバルパスメモリ内に記憶する。よって，トレースバック処理ではその遷移元状態ビットの最上位ビットの抽出を繰り返すだけで復号ビットを出力することができる。よって，トレースバック処理を極めて簡単に行うことができ，汎用プロセッサによるソフトウエアの実行であっても短時間での復号化処理が可能になる。【選択図】図１０
2007174561.tif 000002
【特許請求の範囲】
【請求項１】
入力ビットとそれに先行する（Ｋ−１）個の入力ビットとを有する状態ビットから畳み込み符号された符号ビットを入力し，前記符号ビットから最尤符号して前記入力ビット列を復号するビタビ符号装置において，
前記入力される符号ビットに対して，パスメトリックに応じて所定の状態ビットに対応する遷移元状態ビットを選択し，取りうる複数の所定の状態ビットそれぞれについて当該遷移元状態ビットをサバイバルパスメモリに記憶するパスメモリ生成処理ユニットと，
前記入力される符号ビットに対する前記サバイバルパスメモリへの前記遷移元状態ビットの記憶がトレースバック長分終了した後に，トレースバックの起点となる状態ビットの最上位ビットを抽出し，当該最上位ビットが抽出された状態ビットに対応する前記サバイバルパスメモリ内の遷移元状態ビットの最上位ビットの抽出を繰り返し，当該抽出された最上位ビットを復号結果として出力するトレースバック処理ユニットとを有することを特徴とするビタビ復号装置。
【請求項２】
請求項１において，
前記ビタビ復号装置は，前記符号ビットを順番に受信し，
前記パスメモリ生成処理ユニットは，前記符号ビットを受信するたびに前記遷移元状態ビットのサバイバルパスメモリへの記憶を行い，
前記トレースバック処理ユニットは，前記トレースバック長分の符号ビットを受信した後に，トレースバック処理を行うことを特徴とするビタビ復号装置。
【請求項３】
請求項２において，
さらに，前記取りうる複数の所定の状態ビットに対応して，前記入力される符号ビットと前記遷移元状態ビットに対応する符号ビットとのブランチパラメトリックを求めるブランチパラメトリック処理ユニットを有し，
前記パスメモリ生成処理ユニットは，前記求められたブランチパラメトリックに前記遷移元状態ビットのパスメトリックのうち最小のパスメトリックを加算して，当該所定の状態ビットのパスメトリックを求め，当該求めたパスメトリックのうち最小のパスメトリックに対応する遷移元状態ビットを選択することを特徴とするビタビ復号装置。
【請求項４】
請求項３において，
前記パスメモリ生成処理ユニットは，前記符号ビットを受信するたびに，全ての状態ビットに対するパスメトリックを求め，当該求めたパスメトリックを更新することを特徴とするビタビ復号装置。
【請求項５】
入力ビットとそれに先行する（Ｋ−１）個の入力ビットとを有する状態ビットから畳み込み符号された符号ビットを入力し，前記符号ビットから最尤符号して前記入力ビット列を復号するビタビ符号プログラムにおいて，
前記入力される符号ビットに対して，パスメトリックに応じて所定の状態ビットに対応する遷移元状態ビットを選択し，取りうる複数の所定の状態ビットそれぞれについて当該遷移元状態ビットをサバイバルパスメモリに記憶するパスメモリ生成処理ユニットと，
前記入力される符号ビットに対する前記サバイバルパスメモリへの前記遷移元状態ビットの記憶がトレースバック長分終了した後に，トレースバックの起点となる状態ビットの最上位ビットを抽出し，当該最上位ビットが抽出された状態ビットに対応する前記サバイバルパスメモリ内の遷移元状態ビットの最上位ビットの抽出を繰り返し，当該抽出された最上位ビットを復号結果として出力するトレースバック処理ユニットとを，コンピュータに構築させるビタビ復号プログラム。
【請求項６】
請求項５において，
前記符号ビットが順番に受信され，
前記パスメモリ生成処理ユニットは，前記符号ビットを受信するたびに前記遷移元状態ビットのサバイバルパスメモリへの記憶を行い，
前記トレースバック処理ユニットは，前記トレースバック長分の符号ビットを受信した後に，トレースバック処理を行うことを特徴とするビタビ復号プログラム。
【請求項７】
請求項６において，
さらに，取りうる複数の所定の状態ビットに対応して，前記入力される符号ビットと前記遷移元状態ビットに対応する符号ビットとのブランチパラメトリックを求めるブランチパラメトリック処理ユニットを，コンピュータに構築させ，
前記パスメモリ生成処理ユニットは，前記求められたブランチパラメトリックに前記遷移元状態ビットのパスメトリックのうち最小のパスメトリックを加算して，当該所定の状態ビットのパスメトリックを求め，当該求めたパスメトリックのうち最小のパスメトリックに対応する遷移元状態ビットを選択することを特徴とするビタビ復号プログラム。
【請求項８】
請求項７において，
前記パスメモリ生成処理ユニットは，前記符号ビットを受信するたびに，全ての状態ビットに対するパスメトリックを求め，当該求めたパスメトリックを更新することを特徴とするビタビ復号プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，ビタビ復号装置に関し，特に，ソフトウエアによる復号処理を簡単にしたビタビ復号装置に関する。
【背景技術】
【０００２】
ビタビ復号法は，畳み込み符号を復号することができる最尤復号法（受信符号に対して最も確からしい送信符号を推定し出力する復号法）の一つであり、伝送路上で生じる伝送データの誤りに対して高い誤り訂正能力を持つ。このため、無線通信分野などにおいて、データ伝送の信頼性を高めるため、伝送路上で生ずる伝送データの符号誤りを訂正する誤り訂正技術として用いられる。
【０００３】
送信側では，送信データを畳み込み符号器により符号化し，その符号ビットを伝送路上に送出する。受信側では受信した符号ビットについてビタビ符号を行い送信データに復号する。このビタビ復号器では，受信した符号ビットと，実現可能な送信データの状態の遷移に伴って生成される符号ビットとの距離（ハミング距離，メトリック）に基づいて，送信データを再現するトレースバック処理を行う。ビタビ復号器では，このトレースバック処理を可能にするために，受信した符号ビットに対して上記のメトリックを求め，それに基づき選択パス情報を記憶するサバイバルパスメモリを構築する。そして，所定のデータ長の符号ビットの受信を完了した後に，サバイバルパスメモリの選択パス情報に基づいて送信データをトレースバックし，送信データを復号し出力する。
【０００４】
このようなビタビ復号器については，例えば，特許文献１に記載されている。
【０００５】
この特許文献１には，ｋビットの情報をｎビット（ｎ＞ｋ）の符号に符号化する符号化率Ｒ＝ｋ／ｎ，拘束長Ｋの畳み込み符号をパスメモリを用いて最尤復号するビタビ復号器において，状態遷移情報に従って，少なくとも状態数に等しいＮワード（Ｎは２のK-k乗）を格納するパスメモリを設け，該パスメモリの各ワードの内容をＭＳＢ側にシフトしながら，選択された状態番号（２進数）の一部ｋビットをＬＳＢ側に追加記憶更新して行き，パスメモリの上記シフト処理による桁あふれ情報から復号出力を得るようにしたものが記載されている。つまり，パスメモリ内に遷移元の状態番号のＬＳＢを記憶しておき，トレースバック処理の際に，状態番号をＭＳＢ側にシフトしながらＬＳＢにパスメモリ内の情報系列（状態番号のＬＳＢ）を加えていき，シフト処理で桁あふれした情報から復号出力を得るようにしている。
【０００６】
それ以外にも，ビタビ復号器については，特許文献２，３，４に記載されている。
【０００７】
これらのうち，特に特許文献４では，全ての経路についてのパスメトリックを算出した後にトレースバック処理を行うのではなく，符号ビットを受信するたびに経路選択を随時行いながら，その選択されたパスについてのパス選択信号（これが復号データとなる）を，パスメモリ部の行レジスタに動的に書き込む。このとき，選択されたパスについての一連のパス選択信号が１行に収まるように書き込みを制御し，最終時刻において，選択された経路に関するパス選択信号列を行レジスタから一気に読み出して，復号データとしている。
【特許文献１】特開平５−３１５９７６号公報
【特許文献２】特開２０００−３５７９７１号公報
【特許文献３】特開２０００−１９６４６８号公報
【特許文献４】特開２００４−１５３３１９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
特許文献１に記載されたビタビ復号器では，復号出力を得るトレースバック処理において，トレース開始の状態番号をＭＳＢ側にシフトし，シフトにより空いたＬＳＢにバスメモリ内の情報系列を加え，シフト処理で桁あふれした情報を復号ビット列として出力する。したがって，特許文献１に示されたビタビ復号器では，パスメモリ内に遷移元の状態番号のＬＳＢのみしか記憶しないので，パスメモリの容量を小さくすることはできるが，それに伴ってトレースバック処理が煩雑になっている。
【０００９】
また，特許文献４などでは，符号ビットを受信するたびに復号データとなるパス選択信号を生成しているので，パス選択信号の生成処理が複雑であり，送信されるデータ列のサイズが大きいとそのパス選択信号生成処理の負担が重くなる。
【００１０】
そこで，本発明の目的は，トレースバック処理を簡単にしたビタビ符号装置を提供することにある。
【課題を解決するための手段】
【００１１】
上記の目的を達成するために，本発明の第１の側面によれば，入力ビットとそれに先行する（Ｋ−１）個の入力ビットとを有する状態ビットから畳み込み符号された符号ビットを入力し，前記符号ビットから最尤符号して前記入力ビット列を復号するビタビ符号装置において，
前記入力される符号ビットに対して，パスメトリックに応じて所定の状態ビットに対応する遷移元状態ビットを選択し，取りうる複数の所定の状態ビットそれぞれについて当該遷移元状態ビットをサバイバルパスメモリに記憶するパスメモリ生成処理ユニットと，
前記入力される符号ビットに対する前記サバイバルパスメモリへの前記遷移元状態ビットの記憶がトレースバック長分終了した後に，トレースバックの起点となる状態ビットの最上位ビットを抽出し，当該最上位ビットが抽出された状態ビットに対応する前記サバイバルパスメモリ内の遷移元状態ビットの最上位ビットの抽出を繰り返し，当該抽出された最上位ビットを復号結果として出力するトレースバック処理ユニットとを有することを特徴とする。
【００１２】
上記の本発明の第１の側面において，好ましい態様では，前記ビタビ復号装置は，前記符号ビットを順番に受信し，前記パスメモリ生成処理ユニットは，前記符号ビットを受信するたびに前記遷移元状態ビットのサバイバルパスメモリへの記憶を行い，前記トレースバック処理ユニットは，前記トレースバック長分の符号ビットを受信した後に，トレースバック処理を行うことを特徴とする。
【００１３】
上記の目的を達成するために，本発明の第１の側面によれば，入力ビットとそれに先行する（Ｋ−１）個の入力ビットとを有する状態ビットから畳み込み符号された符号ビットを入力し，前記符号ビットから最尤符号して前記入力ビット列を復号するビタビ符号プログラムにおいて，
前記入力される符号ビットに対して，パスメトリックに応じて所定の状態ビットに対応する遷移元状態ビットを選択し，取りうる複数の所定の状態ビットそれぞれについて当該遷移元状態ビットをサバイバルパスメモリに記憶するパスメモリ生成処理ユニットと，
前記入力される符号ビットに対する前記サバイバルパスメモリへの前記遷移元状態ビットの記憶がトレースバック長分終了した後に，トレースバックの起点となる状態ビットの最上位ビットを抽出し，当該最上位ビットが抽出された状態ビットに対応する前記サバイバルパスメモリ内の遷移元状態ビットの最上位ビットの抽出を繰り返し，当該抽出された最上位ビットを復号結果として出力するトレースバック処理ユニットとを，コンピュータに構築させるビタビ復号プログラムである。
【発明の効果】
【００１４】
本発明の第１の側面によれば，入力される符号ビットに対し，取りうる状態ビットに対応して，その状態ビットのパスメトリックに応じて最尤の遷移元状態ビットを選択して，サバイバルパスメモリ内に記憶する。よって，トレースバック処理ではその遷移元状態ビットの最上位ビットの抽出を繰り返すだけで復号ビットを出力することができる。よって，トレースバック処理を極めて簡単に行うことができ，汎用プロセッサによるソフトウエアの実行であっても短時間での復号化処理が可能になる。
【発明を実施するための最良の形態】
【００１５】
以下，図面にしたがって本発明の実施の形態について説明する。但し，本発明の技術的範囲はこれらの実施の形態に限定されず，特許請求の範囲に記載された事項とその均等物まで及ぶものである。
【００１６】
［畳み込み符号化とビタビ符号化］
ビタビ復号装置は，畳み込み符号などの最尤符号法に用いられ，誤り訂正能力が高いので，伝送経路誤りが生じやすい衛星通信や移動体通信などの伝送方式における復号器として用いられている。ビタビ復号では，受信符号ビットと期待符号ビットとの差分からなるハミング距離（ブランチメトリック）を求めるブランチメトリック処理と，加算・比較・選択処理（ＡＣＳ：Ａｄｄ，Ｃｏｍｐａｒｅ，Ｓｅｌｅｃｔ）によるパスメモリ生成処理とが繰り返され，それらの処理が状態ビットの数×トレースバック長の回数だけ繰り返された後，最後に入力データに復号するトレースバック処理が行われる。
【００１７】
以下，入力ビットの畳み込み符号を生成する符号化処理と，その符号ビットから元の入力ビットに復号するビタビ復号化処理とについて，基本的事項を簡単に説明する。
【００１８】
図１は，畳み込み符号器の一例を示す図である。入力ビットＩＮが遅延機能を有するレジスタＲ１〜Ｒ８に順に入力され，入力ビットＩＮとレジスタＲ１〜Ｒ８に格納されたビットの排他的論理和ｃ０と，入力ビットＩＮとレジスタＲ２，Ｒ３，Ｒ４，Ｒ８に格納されたビットの排他的論理和ｃ１とが，排他的論理和回路ｇ０，ｇ１により生成される。符号ビットｃ０，ｃ１は，対応する入力ビットの「１」が奇数であれば「１」，偶数であれば「０」になる。１個の入力ビットＩＮの入力に伴って符号ビットｃ０，ｃ１が生成されると，次の入力ビットＩＮが入力され，各レジスタの情報は後段のレジスタにシフトされる。つまり，入力ビットＩＮが供給されるたびに符号化が行われ，レジスタ間でシフトされる。それにより，符号器の２つのレジスタ内の情報ビットからなる状態は２の８乗存在する。この状態を示すビット列を，以下状態ビットと称して説明する。
【００１９】
この符号器は，レジスタ数８，１個の入力ビットＩＮに対して２個の符号ビットｃ０，ｃ１が生成されるので符号化率ｒｃ＝１／２（ｋビットの入力ビットからｎビットの符号ビットが生成される場合の符号化率はｋ／ｎである。），１個の入力ビットＩＮと先行する８個の入力ビット（Ｒ１〜Ｒ８）から符号化されるので，符号化に影響を与える入力ビット数である拘束長ＫはＫ＝９である。
【００２０】
一般に符号器への入力ビットと出力ビットとの比率である符号化率は，入力ビット数に対して出力ビット数が多いほど小さくなり，伝送速度は落ちるが誤り訂正能力は高くなる。通常は，伝送速度の低下を回避するために符号化率は１／２にされる。また，拘束長Ｋは，符号ビット出力を得るために必要な過去の入力ビット数を表し，拘束長を大きくすることで誤り訂正能力は高くなるが，状態ビットの数が多くなりビタビ復号器の構成が複雑になる。
【００２１】
図２は，図１の符号器（Ｋ＝９）において入力ビットＩＮが「１，０，１，１，０，１，０」の場合の符号化の例を示す図表である。レジスタＲ１〜Ｒ８は全て「０」に初期化されているものとする。入力ビットＩＮが入力されるたびに，レジスタＲ１〜Ｒ８の状態が遷移し，それぞれの状態に対する符号ビットｃ０，ｃ１が出力される。
【００２２】
図３は，本実施の形態における符号器と復号器とを示す図である。送信側符号器１０では入力ビットＩＮと過去の入力ビットＲ１，Ｒ２から符号ビットｃ０，ｃ１を生成し，伝送路ＴＲを介して送出する。この例では，簡単化のために，符号器１０は２つのレジスタＲ１，Ｒ２を有し，拘束長Ｋ＝３，符号化率１／２である。したがって，符号器内のレジスタによる状態は，２の（Ｋ−１）乗である。また，受信側復号器２０では，受信した符号ビットを入力バッファＩＢＵＦに取り込み，復号処理プログラム２２を中央処理ユニットＣＰＵが実行することで，受信した符号ビットｃ０，ｃ１から元の入力ビットＩＮを復号化する。この復号化法は，前述の最尤復号法によって行われる。そして，復号化された元の入力ビットは出力バッファＯＢＵＦから出力される。復号器２０では，中央処理ユニットＣＰＵが内部バス２４を介してメモリ２６に接続され，復号化処理に際して，メモリ２６にはブランチメトリック２６１とパスメトリック２６２とを格納する領域と，選択パス情報を格納するサバイバルパスメモリ１６３の領域とが確保される。ブランチメトリック，パスメトリック，選択パス情報などについては，後に詳述する。
【００２３】
以下，畳み込み符号器とビタビ復号器の基本的原理について説明する。
【００２４】
ビタビ復号とは，畳み込み符号化された情報（符号ビット）を復号する復号方法であり，復号時に最も確からしい（最尤）送信符号ビットを推定し，その符号ビットを生成する状態ビットから元の入力ビットを出力する。そこでまず，畳み込み符号器の状態遷移を示すトレリス線図について説明する。
【００２５】
図４は，図３の畳み込み符号器におけるトレリス線図である。図３の畳み込み符号器１０は，２つのレジスタＲ１，Ｒ２を有し，拘束長Ｋ＝３，符号化率１／２である。したがって，２個のレジスタＲ１，Ｒ２の状態は，２の２乗（Ｋ−１乗）である４つの状態になる。図４中に，レジスタＲ１，Ｒ２のビットの組合せからなる４つの状態ビットが示されている。この４つの状態それぞれに対して，入力ビットＩＮが「０」の時の状態遷移が実線の矢印で示され，入力ビットＩＮが「１」の時の状態遷移が破線の矢印で示される。これら矢印はブランチとも称される。横方向には時間ｔ０〜ｔ５が示され，各時間での状態が黒丸で示されている。そして，黒丸で示した各状態からの遷移（実線と破線の矢印）に対して生成される符号ビットｃ０，ｃ１が示されている。
【００２６】
たとえば，時間ｔ０の状態ビットＲ１，Ｒ２＝００では，入力ビットＩＮ＝０で符号ビットｃ０，ｃ１＝００が生成され，状態ビット＝００に遷移し（実線矢印），入力ビットＩＮ＝１で符号ビットｃ０，ｃ１＝１１が生成され，状態ビット＝１０に遷移（破線矢印）する。同様に，時間ｔ０の状態ビットＲ１，Ｒ２＝０１では，入力ビットＩＮ＝０で符号ビットｃ０，ｃ１＝１１が生成され，状態ビット＝００に遷移し（実線矢印），入力ビットＩＮ＝１で符号ビットｃ０，ｃ１＝００が生成され，状態ビット＝１０に遷移（破線矢印）する。状態ビットＲ１，Ｒ２＝１０では，入力ビットＩＮ＝０で符号ビットｃ０，ｃ１＝１０が生成され，状態ビット＝０１に遷移し（実線矢印），入力ビットＩＮ＝１で符号ビットｃ０，ｃ１＝０１が生成され，状態ビット＝１１に遷移（破線矢印）する。最後に，状態ビットＲ１，Ｒ２＝１１では，入力ビットＩＮ＝０で符号ビットｃ０，ｃ１＝０１が生成され，状態ビット＝０１に遷移し（実線矢印），入力ビットＩＮ＝１で符号ビットｃ０，ｃ１＝１０が生成され，状態ビット＝１１に遷移（破線矢印）する。
【００２７】
上記の状態遷移とそれに伴って生成される符号ビットｃ０，ｃ１は，いずれの時間ｔ０〜ｔ４においても同じである。一般に，入力ビットＩＮ＝０に対して状態ビットはより上側に遷移し，入力ビットＩＮ＝１に対して状態ビットはより下側に遷移する。
【００２８】
上記のトレリス線図によれば，受信側の復号器は，受信する符号ビットｃ０，ｃ１に基づいて状態ビットの遷移を逆トレースすることができる。状態ビットの遷移が逆トレースできれば，その状態ビットに遷移させた入力ビットＩＮを知ることができるので，元の入力ビットＩＮに復号することができる。ただし，伝送路には誤りが発生するので受信する符号ビットが全て正しいとは限らない。そこで，遷移元の状態ビットを選択するために，受信符号ビットｃ０，ｃ１と，トレリスのブランチ（パス）に対応する送信符号ビットｃ０，ｃ１とのハミング距離（差分）であるメトリックが利用される。つまり，このメトリックがより小さいほうに状態が遷移したとすることでより確からしい（最尤の）状態遷移を推測することができる。
【００２９】
図５は，ビタビ復号におけるパスメトリックを説明する図である。前述したトレリス線図と同様に，４つの状態ビットそれぞれに対応して入力ビットＩＮ＝０，１に対する２つの遷移が示されている。そして，２つの遷移を示すブランチ（図４のトレリス線図の矢印）にはそれぞれ生成される符号ビットが示されている。この符号ビットは，送信側から送信される符号ビットＴｄａｔａである。また，図５には受信側で受信される符号ビットＲｄａｔａの例が示されている。
【００３０】
期待符号ビットである送信符号ビットＴｄａｔａと，受信符号ビットＲｄａｔａとのハミング距離がブランチメトリックＢＭとして算出可能である。ハミング距離とは，２つのビット列の異なるビット数のことであり，例えば，１１と１１であれば完全一致でありハミング距離は０になり，１１と１０であれば１ビットのみ異なるのでハミング距離は１となり，１１と００であれば２ビットが異なるのでハミング距離は２となる。
【００３１】
たとえば，時間ｔ１の状態ビット００のノードＮ１の上下には，その状態ビットに遷移するときの送信符号ビットＴｄａｔａと，受信符号ビットＲｄａｔａとのハミング距離であるブランチメトリックＢＭ「２」「０」が示されている。つまり，受信符号ビットＲｄａｔａ＝１１に対して，そのノードＮ１に遷移可能な２つのブランチの送信符号ビットＴｄａｔａ＝００，１１とのハミング距離は，それぞれ２，０である。したがって，このノードＮ１（状態ビット００，時間ｔ１）に遷移する時に送出された送信符号ビットＴｄａｔａは，受信符号ビットＲｄａｔａとのハミング距離（ブランチメトリック）が小さいほう（ＢＭ＝０）がより確からしいと判定すると，ノードＮ１に遷移した最尤のパスは状態ビット００からのパスと判定できる。
【００３２】
時間ｔ５の状態ビット００のノードＮ４に示されるとおり，各ノードの上下には，ブランチメトリックＢＭと，時間ｔ０からそのノードに至るブランチメトリックＢＭの累積値であるパスメトリックＰＭが括弧内に示されている。つまり，各ノードにはＢＭ（ＰＭ）が上下に示されている。ここで，パスメトリックＰＭは，当該状態に遷移可能な経路の最小メトリックとブランチメトリックの累和である。たとえば，時間ｔ２の状態ビット００のノードＮ３のブランチメトリックＢＭは１，１であるが，遷移元のノードＮ１（時間ｔ１の状態ビット０１）のブランチメトリックＢＭ（ノードＮ１ではＰＭと等しい）のうち小さい値「０」と，当該ノードＮ３のブランチメトリックＢＭ＝１との累和＝１が，そのノードＮ３のパスメトリックＰＭ＝１になる。また，遷移元のノードＮ２（時間ｔ１の状態ビット０１）のブランチメトリックＢＭのうち小さい値「１」（上下ＢＭは同じ値）と，ノードＮ３のブランチメトリックＢＭ＝１との累和＝２が，そのノードＮ３のパスメトリックＰＭ＝２になる。したがって，ノードＮ３の上下にはＢＭ（ＰＭ）＝１（０），１（２）が示されている。他のノードも同様である。
【００３３】
上記のように，受信符号ビットＲｄａｔａを受信するたびに，各状態ノードのブランチメトリックＢＭとパスメトリックＰＭとを演算で求めることができる。そして，伝送路にノイズが発生して受信符号ビットＲｄａｔａが送信符号ビットＴｄａｔａと異なっても，そのハミング距離（メトリック）が最小になる遷移経路を選択することで，最尤の遷移経路を見つけ出し，最尤の入力データを復号することができる。
【００３４】
図５の例では，時間ｔ５までの全ての状態のノードに対してブランチメトリックＢＭとパスメトリックＰＭとが示されている。そして，時間ｔ５の４つのノードのパスメトリックＰＭを比較すると状態ビット１０に対応するノードＮ５が最も小さいパスメトリックＰＭ＝０を有している。そこで，このノードＮ５をトレースバック処理の開始点に選ぶことで最尤入力データの復号ができる。トレリス線図では，各状態に遷移する２つのパスのうち，パスメトリックＰＭの小さい方のパスをサバイバルパスと称する。つまり，トレースバック処理の開始点であるノードＮ５から，パスメトリックＰＭの小さい方のサバイバルパスをトレースすることで，最も確からしい（最尤）の遷移経路をたどることができる。図５の例では，ノードＮ５の状態から，状態ビット００へ，さらに状態ビット００へ，さらに状態ビット０１へ，さらに状態ビット１０へ，最後に状態ビット００にトレースバックされる。
【００３５】
なお，トレースバック処理の開始点の選択において，入力ビットの最後にテールビットとして送信側と受信側で既知のビット列，例えば０００〜を付加することで，最終状態ビットを００に確定することができる。このように最終状態ビットが既知の場合，状態ビット００のノードＮ４がトレースバック処理の開始ノードにされる。このようにテールビットを利用することで開始ビットが伝送路の誤りに影響を受けることを避けることができる。このように遷移経路をトレースバックすれば，各遷移の原因となった元の入力ビットを高い確率で復元することができる。なお，テールビットが１１１〜の場合は，開始ノードは状態ビット１１になる。
【００３６】
以上のように，トレリス線図の各ノードにブランチメトリックＢＭとパスメトリックＰＭを演算で求めておき，最終状態のノードを開始点として，より小さいパスメトリックの遷移ブランチをトレースバックすることで，符号器における最尤の状態遷移経路を検出することができ，それに基づいて最尤の元の入力データを復号化することができる。ただし，トレリス線図の情報を全てメモリに格納するとデータ容量が膨大になり現実的ではない。
【００３７】
［特許文献１の復号方法］
図６は，特許文献１の復号方法を示す図である。特許文献１によれば，復号器が符号ビットを受信するたびにサバイバルメモリ内に選択パス情報を格納し，トレース長の符号ビットを受信完了した後に，サバイバルメモリ内の選択パス情報に基づいてトレースバック処理をして，元の入力ビットを復号化する。
【００３８】
上記のサバイバルメモリへの選択パス情報の格納工程では，（１）各状態ノードにおける上下のパスのパスメトリック値を遷移元の少ない方のパスメトリックに当該状態ノードのブランチメトリックとを加算して求め，（２）各状態ノードにおいて上下の入力パスのパスメトリック値を比較し，（３）パスメトリック値が小さいほうの遷移元状態ビットを選択し，その遷移元状態ビットの最下位ビットＬＳＢを選択パス情報としてサバイバルパスメモリ２６３に記憶する。パスメトリック値が等しい場合はいずれかの遷移元状態ビットのＬＳＢ（０または１）を記憶する。図６の例では０を記憶している。例えば，時間ｔ５での４つの状態ノードの場合は，それぞれパスメトリック値が小さい方の遷移元状態ビットのＬＳＢは，０，０，０，０になる。それ以外の時間ｔ４〜ｔ１での遷移元状態ビットのＬＳＢも同様に記憶されている。
【００３９】
上記のように，サバイバルパスメモリ２６３に記憶する選択パス情報を各状態ノードでＬＳＢの１ビットのみにしているので，メモリ容量を小さくすることができる。
【００４０】
図７は，トレースバック処理を示す図である。図７では，トレースバック処理の開始状態ノードが状態ビット１０のノードの例で示されている。特許文献１のトレースバック処理では，開始される状態ビット１０を変数として取得する（Ｓ１）。そして，その状態ビット１０を左シフトする（Ｓ２）。そして，左シフトした変数の最下位ビットにサバイバルパスメモリ内の選択パス情報０を入力する（Ｓ３）。そして，変数の最上位ビットＭＳＢから復号結果１を抽出する（Ｓ４）。さらに，変数の下位２ビットを遷移元状態ビット００として抽出する（Ｓ５）。
【００４１】
上記の工程Ｓ２〜Ｓ５が，全てのトレースバック長だけ繰り返される。そのトレースバック処理によりトレースされる状態の遷移経路は，図７中のサバイバルパスメモリにグレーの格納領域で示している。その結果，復号された出力値として１０００１が抽出される。
【００４２】
［本実施の形態の復号方法］
本実施の形態では，ビタビ復号のトレースバック処理を簡素化してソフトウエア処理に適合しやすくする。一方，サバイバルパスメモリに格納する選択パス情報のデータ量の増大は許容する。つまり，近年におけるメモリの廉価化に伴いメモリ容量よりもソフトウエア処理の簡素化に重点を置いた復号方法である。
【００４３】
図８，図９は，本実施の形態における復号方法を示す図であり，図８はサバイバルパスメモリの生成を示し，図９はトレースバック処理を示す。図８において，図６と同様のトレリス線図と受信符号ビットＲｄａｔａとが示されている。そして，符号ビットＲｄａｔａを受信するたびに，各状態ビットに対応してブランチメトリックＢＭとパスメトリックＰＭとを演算することは特許文献１と同じである。ただし，パスメトリックの比較に基づき選択処理により選択された遷移元状態ビットそのものが，サバイバルパスメモリに記憶される。この点が特許文献１と異なる。こうすることでトレースバック処理を簡単化できる。
【００４４】
図８の例で説明すると，時間ｔ５における４つの取りうる状態ノードにおいて，状態ビット００では，パスメトリックＰＭが等しいので低いビットである遷移元状態ビット００が選択され記憶される。また，状態ビット０１でも同様にＰＭが等しいので低いビットである遷移元状態ビット１０が選択され記憶される。そして，状態ビット１０ではＰＭが低いほうの遷移元状態ビット００が選択され記憶される。さらに，状態ビット１１ではＰＭが等しいので低いビットである遷移元状態ビット１０が選択され記憶される。他の時間ｔ４〜ｔ１においても同様に，パスメトリックの比較とより低いパスメトリックの遷移元状態ビットが選択され記憶される。
【００４５】
受信符号ビットＲｄａｔａを受信するたびに，ブランチメトリックＢＭとパスメトリックＰＭとが求められ，選択パス情報としてパスメトリックの低い遷移元状態ビットが選択され記憶される。ただし，ブランチメトリックＢＭとパスメトリックＰＭとは全ての時間について記憶しておく必要はなく，パスメトリックＰＭのみが更新される。
【００４６】
次に，サバイバルパスメモリの選択パス情報の格納がトレースバック長だけ完了すると，トレースバック処理が行われる。本実施の形態によれば，サバイバルパスメモリ内に遷移元状態ビットがそのまま記憶されているので，トレースバック処理は簡素化される。つまり，図９に示すとおり，まずトレース開始ノードの状態ビット１０を取得し（Ｓ１０），その状態ビット１０の最上位ビットＭＳＢを復号ビットとして抽出する（Ｓ１１）。次に，サバイバルメモリに格納されている選択パス情報（遷移元状態ビット）を読み出す（Ｓ１２）。この読み出した選択パス情報が遷移元状態ビットそのものであるので，そのＭＳＢが次の復号ビットとして抽出される（Ｓ１１）。上記の処理Ｓ１２，Ｓ１１を繰り返すことで，サバイバルパスメモリのグレーの状態ビットがトレースされる。
【００４７】
上記のように，トレースバック処理は単にサバイバルパスメモリに格納されている遷移元状態ビットを読み出して，そのＭＳＢを抽出する処理を繰り返すだけでよい。したがって，ソフトウエア処理を簡素化することができる。通常の畳み込み符号器は拘束長Ｋが比較的長いので，その拘束長をバイト単位またはワード単位にすれば，ソフトウエアによる情報処理への適合性を高くすることができる。
【００４８】
次に，本実施の形態におけるビタビ復号器の具体例を説明する。
【００４９】
図１０は，本実施の形態におけるビタビ復号器の処理モジュールとメモリの関係を示す図である。ビタビ復号器２０のハードウエア構成は，図３に示したとおり，中央処理ユニットＣＰＵと復号処理プログラム２２とメモリ２６とで構成される。そして，復号処理プログラムの処理モジュールが図１０に示されている。これら処理モジュールを有するビタビ復号プログラムがコンピュータにインストールされることで処理ユニットを構築する。
【００５０】
図１０に示されるとおり，受信符号ビットＲｄａｔａを受信すると，ブランチメトリック処理モジュールＳ１が全ての状態ビットに対応してブランチメトリックＢＭを求める。具体的には，前述の通り送信符号ビットＴｄａｔａと受信符号ビットＲｄａｔａとのハミング距離がブランチメトリックである。そして，求められたブランチメトリックＢＭがパスメモリ生成処理モジュールＳ２に供給される。パスメモリ生成処理モジュールＳ２は，供給されたブランチメトリックＢＭとパスメトリックメモリ２６２内に格納されている遷移元状態ビットの小さいほうのパスメトリックＰＭとを加算して新たなパスメトリックを求め，２つの遷移元状態ビットに対応して新たに求めたパスメトリックをパスメトリックメモリ２６２に記憶する。そして，求めたパスメトリックの小さいほうに対応する遷移元状態ビットを，サバイバルパスメモリ２６３に記憶する。
【００５１】
そして，トレースバック長分のサバイバルパスメモリへの遷移元状態ビットの記憶が終了すると，トレースバック処理モジュールＳ３が，サバイバルパスメモリ内の情報に基づいて，図９で説明したトレースバック処理を行い，最尤の元の入力ビットを復号する。
【００５２】
図１１は，パスメモリ生成処理モジュールの概略処理フローチャート図である。この処理では，受信した符号ビットであるデータＤ（ｎ）に対する状態Ｘの上下のパスメトリックＰＭを求める（Ｓ１０１）。そして，上下の入力パスのパスメトリックを比較する（Ｓ１０２）。比較した結果，パスメトリックが小さいほうの遷移元状態の状態ビットをサバイバルパスメモリに記憶する（Ｓ１０３）。上記の処理を全ての状態について繰り返す（Ｓ１０４）。さらに，上記処理Ｓ１０１〜Ｓ１０４が，符号ビットを受信するたびに行われる（Ｓ１０５）。あるいは，トレースバック長分の符号ビットを受信した後に，トレリス線図の全状態ノードと全受信符号ビットについて，図１１の処理を行うことでサバイバルパスメモリを作成してもよい。ただし，その場合は，符号ビットの受信完了後に行われる処理工数が増加する。よって，符号ビットを受信するたびにサバイバルパスメモリに遷移元状態ビットを記憶する処理を行うことが好ましい。
【００５３】
図１２は，トレースバック処理の概略処理フローチャート図である。最初に変数Ａを定義する（Ｓ１１０）。この変数Ａは，図９に示した２ビットの変数であり，拘束長Ｋ＝３の場合には変数Ａのビット数はＫ−１＝２である。そして，変数Ａにトレースバック開始の状態ビットを設定する（Ｓ１０）。そして，変数ＡのＭＳＢを抽出して復号結果を取得する（Ｓ１１）。さらに，その状態ビットに対応するサバイバルパスメモリ２６３内に格納されている遷移元状態ビットを読み出し，変数Ａに設定する（Ｓ１２）。この変数Ａに設定された遷移元状態ビットのＭＳＢを抽出して復号結果を出力する（Ｓ１１）。上記の処理Ｓ１２，Ｓ１１が，全ての受信符号ビットについて繰り返されて（Ｓ１１２），トレースバック処理が完了する。
【００５４】
図１３，図１４，図１５は，本実施の形態におけるビタビ復号器の処理モジュールの具体的なフローチャート図である。図１３のブランチメトリック処理は，受信した符号ビットＲｄａｔａが入力されるたびに実行される。そこで受信時の時間をｔ（ｎ）とする。このブランチメトリック処理では，最初に変数Ｘに状態ビットを設定する（Ｓ１２１）。初期値は状態ビット００である。次に，状態Ｘに遷移可能な２つの遷移元状態から状態Ｘに遷移するときの符号ビットｃ０，ｃ１を求める（Ｓ１２２）。この符号ビットｃ０，ｃ１は，遷移元状態ビットと入力ビットから畳み込み符号化されたビットである。そして，求めた状態Ｘに対応する符号ビットと，その時間ｔ（ｎ）での受信符号ビットとのブランチメトリックＢＭを計算する（Ｓ１２３）。最後に，計算で求めたブランチメトリックＢＭを状態Ｘの情報としてパスメモリ生成処理モジュールＳ２に通知する（Ｓ１２４）。上記の処理は，時間ｔ（ｎ）における全ての状態（図８の例では４つの状態）について繰り返される（Ｓ１２５）。
【００５５】
図１４のパスメモリ生成処理も，受信符号ビットＲｄａｔａが入力されるたびに実行される。最初に，状態ビットの変数Ｘと，状態Ｘに遷移可能な２つの状態ビット（遷移元状態ビット）の変数Ｙ，Ｚとを定義する（Ｓ１３１）。さらに，変数設定として，時間ｔ（ｎ）におけるパスメトリック設定用変数Ｔを定義する（Ｓ１３２）。
【００５６】
初期値が００の状態Ｘに遷移可能な２つの状態ビット００，０１を変数Ｙ，Ｚに設定する（Ｓ１３３）。遷移可能な２つの状態ビットＹ，Ｚは，状態ビットＸに対してＹ＝２Ｘ，Ｙ＝２Ｘ＋１の演算により算出可能である。ただし，０ビット目をＬＳＢとし，拘束長をＫとするとＫ−１ビット目を０にする必要がある。一例として，Ｘ＝１１なら，Ｙ＝２Ｘ＝１１０，Ｚ＝２Ｘ＋１＝１１１で，Ｋ−１ビット目を０にすれば，Ｙ＝０１０，Ｚ＝０１１となり，下位２ビットが遷移可能な２つの状態ビットＹ，Ｚとして算出可能である。
【００５７】
そして，状態Ｙ，Ｚの時間ｔ（ｎ−１）におけるパスメトリックをパスメトリックメモリ２６２から読み出す（Ｓ１３４）。状態Ｙ＝００のパスメトリックに，時間ｔ（ｎ）に状態Ｙから状態Ｘに遷移した場合のブランチメトリックを加算する。同様に，状態Ｚ＝０１のパスメトリックに，時間ｔ（ｎ）に状態Ｚから状態Ｘに遷移した場合のブランチメトリックを加算する（Ｓ１３５）。上記加算により得た２つのパスメトリック値を比較し，小さい方の遷移元状態ビットを時間ｔ（ｎ）における状態Ｘのパス選択情報としてサバイバルパスメモリ２６３に記憶する（Ｓ１３６）。さらに，加算により得た２つのパスメトリック値のうち小さい方を状態Ｘの時間ｔ（ｎ）におけるパスメトリック値として変数Ｔに設定する（Ｓ１３７）。
【００５８】
図１６は，パスメトリックメモリの具体例を示す図である。図中状態数分の要素を有するパスメトリックＰＭメモリが示されている。つまり，時間ｔ（ｎ）のパスメトリック値が常に更新され保存されるのであり，全ての時間におけるパスメトリック値を保存する必要はない。
【００５９】
上記の処理Ｓ１３３〜Ｓ１３７が時間ｔ（ｎ）での全ての状態について繰り返される。状態Ｘは０１と設定され，Ｙ＝１０，Ｚ＝１１と設定され，同様の処理が行われパスメトリック値の算出，パスメトリック値が小さいほうの遷移元状態ビットがサバイバルパスメモリに記憶され，パスメトリック値の小さいほうが変数Ｔに設定される。続いて，状態Ｘ＝１０に，Ｙ＝００，Ｚ＝０１に設定され同様の処理が行われる。最後に，状態Ｘ＝１１に，Ｙ＝１０，Ｚ＝１１に設定され同様の処理が行われる。時間ｔ（ｎ）の全状態について処理が完了すると，最後に，変数Ｔに設定されたパスメトリック値が，時間ｔ（ｎ）のパスメトリック値としてパスメトリックメモリに上書きされる（Ｓ１３９）。
【００６０】
図１７は，サバイバルパスメモリの一例を示す図である。横方向がトレースバック長に対応する時間ｔ（０）〜ｔ（ｎ），縦方向が状態に対応し，それぞれの要素に遷移元状態ビットが記憶される。したがって，サバイバルパスメモリは，トレースバックに必要な選択パス情報を記憶しておく必要がある。
【００６１】
図１５のトレースバック処理は，図１３，図１４の処理がトレースバック長分完了した後に実行される。つまりデータブロックの受信完了した後にトレースバック処理が行われる。まず，状態ビットを示す変数Ｘが定義される（Ｓ１４１）。受信データの最終時間をｔ（ｎ）とすると，パスメトリックメモリ内の時間ｔ（ｎ）におけるパスメトリック値のうち最も小さい値に対応する状態ビットを抽出し，変数Ｘに設定して，トレースバック開始とする（Ｓ１４２）。トレースバック開始位置は，上記以外に，送受信間で既知のテールビットが設定されているなど，トレースバック開始すべき状態が既知の場合は，その状態ビットを変数Ｘに設定する（Ｓ１４２）。
【００６２】
次に，サバイバルパスメモリ内の時間ｔ（ｎ）における状態Ｘのビットを，開始状態ビットとして変数Ｘに設定する（Ｓ１０）。設定された変数ＸのＭＳＢを，または拘束長Ｋの場合のＫ−１ビット目を，時間ｔ（ｎ）における復号ビットとして出力する（Ｓ１１）。さらに，サバイバルパスメモリ内に状態Ｘに対応して格納されている状態ビットを，変数Ｘに上書きする（Ｓ１２）。そして，その変数Ｘについて工程Ｓ１２を行い，次の復号ビットを出力する（Ｓ１１）。上記の工程Ｓ１２，Ｓ１１が全ての受信符号ビットについて繰り返され，最尤の入力ビットがｔ（ｎ），ｔ（ｎ−１）．．．ｔ（１），ｔ（０）の順に出力される（Ｓ１４３）。
【００６３】
以上のように，トレースバック処理は，単にサバイバルパスメモリ内に格納された遷移元状態ビットを読み出して，そのＭＳＢを復号出力として出力するだけであり，ソフトウエア処理としては極めて簡単な処理となる。したがって，専用のハードウエア回路を設ける必要がなく，コストダウンすることができる。
【００６４】
図１８は，本実施の形態におけるビタビ復号器の動作のメリットを示す図である。上の段にデータブロックが時間ｔ１，ｔ２，ｔ３で送信されることが示されている。データブロックは，入力ビットのデータ列ｄａｔａと最後に付加されるテールビット列ｔａｉｌとで構成される。本実施の形態のビタビ復号器では，データブロックに対応する符号ビット列を受信完了した後に，トレースバック処理を行う。しかも，そのトレースバック処理ではサバイバルパスメモリから選択パス情報として遷移元情報ビットを読み出すので，読み出したデータに復号出力とトレースバックする遷移元状態ビットが含まれている。よって，復号結果の抽出とトレースバックの処理が簡単になる。よって，トレースバック時間を短くすることができる。そのことは，図１８の下段に示すとおり，データブロック内に格納できる入力ビット列のデータ数を増やすことができ，単位時間当たりの伝送データ量を増加し，伝送効率を高くすることができることを意味する。
【００６５】
図１９は，本実施の形態におけるビタビ復号器の動作の別のメリットを示す図である。図１９の上段に示されるとおり，複数のユーザ情報を一度に処理する基地局では，先行するデータブロックのトレースバック処理が完了する前に，オーバラップ（図中ＯＬＡＰ）して次のデータブロックを受信することがある。そのため，２つのサバイバルパスメモリを確保し，オーバラップ中の先行するデータブロック用のサバイバルパスメモリと，後続のデータブロック用のサバイバルパスメモリとが利用される。しかし，本実施の形態のビタビ復号器ではトレースバック処理が簡単化されて短時間で行うことができるので，図１９の下段に示すように，オーバラップを解消し，１つのサバイバルパスメモリだけで復号処理可能になる。
【００６６】
以上の実施の形態をまとめると，次の付記のとおりである。
【００６７】
（付記１）入力ビットとそれに先行する（Ｋ−１）個の入力ビットとを有する状態ビットから畳み込み符号された符号ビットを入力し，前記符号ビットから最尤符号して前記入力ビット列を復号するビタビ符号装置において，
前記入力される符号ビットに対して，パスメトリックに応じて所定の状態ビットに対応する遷移元状態ビットを選択し，取りうる複数の所定の状態ビットそれぞれについて当該遷移元状態ビットをサバイバルパスメモリに記憶するパスメモリ生成処理ユニットと，
前記入力される符号ビットに対する前記サバイバルパスメモリへの前記遷移元状態ビットの記憶がトレースバック長分終了した後に，トレースバックの起点となる状態ビットの最上位ビットを抽出し，当該最上位ビットが抽出された状態ビットに対応する前記サバイバルパスメモリ内の遷移元状態ビットの最上位ビットの抽出を繰り返し，当該抽出された最上位ビットを復号結果として出力するトレースバック処理ユニットとを有することを特徴とするビタビ復号装置。
【００６８】
（付記２）付記１において，
前記ビタビ復号装置は，前記符号ビットを順番に受信し，
前記パスメモリ生成処理ユニットは，前記符号ビットを受信するたびに前記遷移元状態ビットのサバイバルパスメモリへの記憶を行い，
前記トレースバック処理ユニットは，前記トレースバック長分の符号ビットを受信した後に，トレースバック処理を行うことを特徴とするビタビ復号装置。
【００６９】
（付記３）付記２において，
さらに，前記取りうる複数の所定の状態ビットに対応して，前記入力される符号ビットと前記遷移元状態ビットに対応する符号ビットとのブランチパラメトリックを求めるブランチパラメトリック処理ユニットを有し，
前記パスメモリ生成処理ユニットは，前記求められたブランチパラメトリックに前記遷移元状態ビットのパスメトリックのうち最小のパスメトリックを加算して，当該所定の状態ビットのパスメトリックを求め，当該求めたパスメトリックのうち最小のパスメトリックに対応する遷移元状態ビットを選択することを特徴とするビタビ復号装置。
【００７０】
（付記４）付記３において，
前記パスメモリ生成処理ユニットは，前記符号ビットを受信するたびに，全ての状態ビットに対するパスメトリックを求め，当該求めたパスメトリックを更新することを特徴とするビタビ復号装置。
【００７１】
（付記５）付記１において，
前記入力される符号ビットは，所定ビット長の入力ビットとそれに後続する所定ビット長のテールビットとから符号化された符号ビットであり，
前記トレースバック処理ユニットは，前記テールビットに対応する状態ビットをトレース開始状態ビットとすることを特徴とするビタビ復号装置。
【００７２】
（付記６）付記１において，
前記取りうる複数の所定の状態ビットの数は，２の（Ｋ−１）乗であることを特徴とするビタビ復号装置。
【００７３】
（付記７）入力ビットとそれに先行する（Ｋ−１）個の入力ビットとを有する状態ビットから畳み込み符号された符号ビットを入力し，前記符号ビットから最尤符号して前記入力ビット列を復号するビタビ符号プログラムにおいて，
前記入力される符号ビットに対して，パスメトリックに応じて所定の状態ビットに対応する遷移元状態ビットを選択し，取りうる複数の所定の状態ビットそれぞれについて当該遷移元状態ビットをサバイバルパスメモリに記憶するパスメモリ生成処理ユニットと，
前記入力される符号ビットに対する前記サバイバルパスメモリへの前記遷移元状態ビットの記憶がトレースバック長分終了した後に，トレースバックの起点となる状態ビットの最上位ビットを抽出し，当該最上位ビットが抽出された状態ビットに対応する前記サバイバルパスメモリ内の遷移元状態ビットの最上位ビットの抽出を繰り返し，当該抽出された最上位ビットを復号結果として出力するトレースバック処理ユニットとを，コンピュータに構築させるビタビ復号プログラム。
【００７４】
（付記８）付記７において，
前記符号ビットが順番に受信され，
前記パスメモリ生成処理ユニットは，前記符号ビットを受信するたびに前記遷移元状態ビットのサバイバルパスメモリへの記憶を行い，
前記トレースバック処理ユニットは，前記トレースバック長分の符号ビットを受信した後に，トレースバック処理を行うことを特徴とするビタビ復号プログラム。
【００７５】
（付記９）付記８において，
さらに，取りうる複数の所定の状態ビットに対応して，前記入力される符号ビットと前記遷移元状態ビットに対応する符号ビットとのブランチパラメトリックを求めるブランチパラメトリック処理ユニットを，コンピュータに構築させ，
前記パスメモリ生成処理ユニットは，前記求められたブランチパラメトリックに前記遷移元状態ビットのパスメトリックのうち最小のパスメトリックを加算して，当該所定の状態ビットのパスメトリックを求め，当該求めたパスメトリックのうち最小のパスメトリックに対応する遷移元状態ビットを選択することを特徴とするビタビ復号プログラム。
【００７６】
（付記１０）付記９において，
前記パスメモリ生成処理ユニットは，前記符号ビットを受信するたびに，全ての状態ビットに対するパスメトリックを求め，当該求めたパスメトリックを更新することを特徴とするビタビ復号プログラム。
【００７７】
（付記１１）付記７において，
前記入力される符号ビットは，所定ビット長の入力ビットとそれに後続する所定ビット長のテールビットとから符号化された符号ビットであり，
前記トレースバック処理ユニットは，前記テールビットに対応する状態ビットをトレース開始状態ビットとすることを特徴とするビタビ復号プログラム。
【図面の簡単な説明】
【００７８】
【図１】畳み込み符号器の一例を示す図である。
【図２】図１の符号器において入力ビットの変化に対する符号化の例を示す図表である。
【図３】本実施の形態における符号器と復号器とを示す図である。
【図４】図３の畳み込み符号器におけるトレリス線図である。
【図５】ビタビ復号におけるパスメトリックを説明する図である。
【図６】特許文献１の復号方法を示す図である。
【図７】トレースバック処理を示す図である。
【図８】本実施の形態における復号方法を示す図である。
【図９】本実施の形態における復号方法を示す図である。
【図１０】本実施の形態におけるビタビ復号器の処理モジュールとメモリの関係を示す図である。
【図１１】パスメモリ生成処理モジュールの概略処理フローチャート図である。
【図１２】トレースバック処理の概略処理フローチャート図である。
【図１３】本実施の形態におけるビタビ復号器の処理モジュールの具体的なフローチャート図である。
【図１４】本実施の形態におけるビタビ復号器の処理モジュールの具体的なフローチャート図である。
【図１５】本実施の形態におけるビタビ復号器の処理モジュールの具体的なフローチャート図である。
【図１６】パスメトリックメモリの具体例を示す図である。
【図１７】サバイバルパスメモリの一例を示す図である。
【図１８】本実施の形態におけるビタビ復号器の動作のメリットを示す図である。
【図１９】本実施の形態におけるビタビ復号器の動作の別のメリットを示す図である。
【符号の説明】
【００７９】
２０：ビタビ復号装置                  Ｓ１：ブランチメトリック処理モジュール
Ｓ２：パスメモリ生成処理モジュール    Ｓ３：トレースバック処理モジュール
２６２：パスメトリックメモリ          ２６３：サバイバルパスメモリ
【図１】
2007174561.tif 000003
【図２】
2007174561.tif 000004
【図３】
2007174561.tif 000005
【図４】
2007174561.tif 000006
【図５】
2007174561.tif 000007
【図６】
2007174561.tif 000008
【図７】
2007174561.tif 000009
【図８】
2007174561.tif 000010
【図９】
2007174561.tif 000011
【図１０】
2007174561.tif 000012
【図１１】
2007174561.tif 000013
【図１２】
2007174561.tif 000014
【図１３】
2007174561.tif 000015
【図１４】
2007174561.tif 000016
【図１５】
2007174561.tif 000017
【図１６】
2007174561.tif 000018
【図１７】
2007174561.tif 000019
【図１８】
2007174561.tif 000020
【図１９】
2007174561.tif 000021
【手続補正書】
【提出日】平成18年4月7日(2006.4.7)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
入力ビットとそれに先行する（Ｋ−１）個の入力ビットとを有する状態ビットから畳み込み符号された符号ビットを入力し，前記符号ビットから最尤符号して前記入力ビット列を復号するビタビ復号装置において，
前記入力される符号ビットに対して，パスメトリックに応じて所定の状態ビットに対応する遷移元状態ビットを選択し，取りうる複数の所定の状態ビットそれぞれについて当該遷移元状態ビットをサバイバルパスメモリに記憶するパスメモリ生成処理ユニットと，
前記入力される符号ビットに対する前記サバイバルパスメモリへの前記遷移元状態ビットの記憶がトレースバック長分終了した後に，トレースバックの起点となる状態ビットの最上位ビットを抽出し，当該最上位ビットが抽出された状態ビットに対応する前記サバイバルパスメモリ内の遷移元状態ビットの最上位ビットの抽出を繰り返し，当該抽出された最上位ビットを復号結果として出力するトレースバック処理ユニットとを有することを特徴とするビタビ復号装置。
【請求項２】
請求項１において，
前記ビタビ復号装置は，前記符号ビットを順番に受信し，
前記パスメモリ生成処理ユニットは，前記符号ビットを受信するたびに前記遷移元状態ビットのサバイバルパスメモリへの記憶を行い，
前記トレースバック処理ユニットは，前記トレースバック長分の符号ビットを受信した後に，トレースバック処理を行うことを特徴とするビタビ復号装置。
【請求項３】
請求項２において，
さらに，前記取りうる複数の所定の状態ビットに対応して，前記入力される符号ビットと前記遷移元状態ビットに対応する符号ビットとのブランチメトリックを求めるブランチメトリック処理ユニットを有し，
前記パスメモリ生成処理ユニットは，前記求められたブランチメトリックに前記遷移元状態ビットのパスメトリックのうち最小のパスメトリックを加算して，当該所定の状態ビットのパスメトリックを求め，当該求めたパスメトリックのうち最小のパスメトリックに対応する遷移元状態ビットを選択することを特徴とするビタビ復号装置。
【請求項４】
請求項３において，
前記パスメモリ生成処理ユニットは，前記符号ビットを受信するたびに，全ての状態ビットに対するパスメトリックを求め，当該求めたパスメトリックを更新することを特徴とするビタビ復号装置。
【請求項５】
入力ビットとそれに先行する（Ｋ−１）個の入力ビットとを有する状態ビットから畳み込み符号された符号ビットを入力し，前記符号ビットから最尤符号して前記入力ビット列を復号するビタビ復号プログラムにおいて，
前記入力される符号ビットに対して，パスメトリックに応じて所定の状態ビットに対応する遷移元状態ビットを選択し，取りうる複数の所定の状態ビットそれぞれについて当該遷移元状態ビットをサバイバルパスメモリに記憶するパスメモリ生成処理ユニットと，
前記入力される符号ビットに対する前記サバイバルパスメモリへの前記遷移元状態ビットの記憶がトレースバック長分終了した後に，トレースバックの起点となる状態ビットの最上位ビットを抽出し，当該最上位ビットが抽出された状態ビットに対応する前記サバイバルパスメモリ内の遷移元状態ビットの最上位ビットの抽出を繰り返し，当該抽出された最上位ビットを復号結果として出力するトレースバック処理ユニットとを，コンピュータに構築させるビタビ復号プログラム。
【請求項６】
請求項５において，
前記符号ビットが順番に受信され，
前記パスメモリ生成処理ユニットは，前記符号ビットを受信するたびに前記遷移元状態ビットのサバイバルパスメモリへの記憶を行い，
前記トレースバック処理ユニットは，前記トレースバック長分の符号ビットを受信した後に，トレースバック処理を行うことを特徴とするビタビ復号プログラム。
【請求項７】
請求項６において，
さらに，取りうる複数の所定の状態ビットに対応して，前記入力される符号ビットと前記遷移元状態ビットに対応する符号ビットとのブランチメトリックを求めるブランチメトリック処理ユニットを，コンピュータに構築させ，
前記パスメモリ生成処理ユニットは，前記求められたブランチメトリックに前記遷移元状態ビットのパスメトリックのうち最小のパスメトリックを加算して，当該所定の状態ビットのパスメトリックを求め，当該求めたパスメトリックのうち最小のパスメトリックに対応する遷移元状態ビットを選択することを特徴とするビタビ復号プログラム。
【請求項８】
請求項７において，
前記パスメモリ生成処理ユニットは，前記符号ビットを受信するたびに，全ての状態ビットに対するパスメトリックを求め，当該求めたパスメトリックを更新することを特徴とするビタビ復号プログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，ビタビ復号装置に関し，特に，ソフトウエアによる復号処理を簡単にしたビタビ復号装置に関する。
【背景技術】
【０００２】
ビタビ復号法は，畳み込み符号を復号することができる最尤復号法（受信符号に対して最も確からしい送信符号を推定し出力する復号法）の一つであり、伝送路上で生じる伝送データの誤りに対して高い誤り訂正能力を持つ。このため、無線通信分野などにおいて、データ伝送の信頼性を高めるため、伝送路上で生ずる伝送データの符号誤りを訂正する誤り訂正技術として用いられる。
【０００３】
送信側では，送信データを畳み込み符号器により符号化し，その符号ビットを伝送路上に送出する。受信側では受信した符号ビットについてビタビ復号を行い送信データに復号する。このビタビ復号器では，受信した符号ビットと，実現可能な送信データの状態の遷移に伴って生成される符号ビットとの距離（ハミング距離，メトリック）に基づいて，送信データを再現するトレースバック処理を行う。ビタビ復号器では，このトレースバック処理を可能にするために，受信した符号ビットに対して上記のメトリックを求め，それに基づき選択パス情報を記憶するサバイバルパスメモリを構築する。そして，所定のデータ長の符号ビットの受信を完了した後に，サバイバルパスメモリの選択パス情報に基づいて送信データをトレースバックし，送信データを復号し出力する。
【０００４】
このようなビタビ復号器については，例えば，特許文献１に記載されている。
【０００５】
この特許文献１には，ｋビットの情報をｎビット（ｎ＞ｋ）の符号に符号化する符号化率Ｒ＝ｋ／ｎ，拘束長Ｋの畳み込み符号をパスメモリを用いて最尤復号するビタビ復号器において，状態遷移情報に従って，少なくとも状態数に等しいＮワード（Ｎは２のK-k乗）を格納するパスメモリを設け，該パスメモリの各ワードの内容をＭＳＢ側にシフトしながら，選択された状態番号（２進数）の一部ｋビットをＬＳＢ側に追加記憶更新して行き，パスメモリの上記シフト処理による桁あふれ情報から復号出力を得るようにしたものが記載されている。つまり，パスメモリ内に遷移元の状態番号のＬＳＢを記憶しておき，トレースバック処理の際に，状態番号をＭＳＢ側にシフトしながらＬＳＢにパスメモリ内の情報系列（状態番号のＬＳＢ）を加えていき，シフト処理で桁あふれした情報から復号出力を得るようにしている。
【０００６】
それ以外にも，ビタビ復号器については，特許文献２，３，４に記載されている。
【０００７】
これらのうち，特に特許文献４では，全ての経路についてのパスメトリックを算出した後にトレースバック処理を行うのではなく，符号ビットを受信するたびに経路選択を随時行いながら，その選択されたパスについてのパス選択信号（これが復号データとなる）を，パスメモリ部の行レジスタに動的に書き込む。このとき，選択されたパスについての一連のパス選択信号が１行に収まるように書き込みを制御し，最終時刻において，選択された経路に関するパス選択信号列を行レジスタから一気に読み出して，復号データとしている。
【特許文献１】特開平５−３１５９７６号公報
【特許文献２】特開２０００−３５７９７１号公報
【特許文献３】特開２０００−１９６４６８号公報
【特許文献４】特開２００４−１５３３１９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
特許文献１に記載されたビタビ復号器では，復号出力を得るトレースバック処理において，トレース開始の状態番号をＭＳＢ側にシフトし，シフトにより空いたＬＳＢにパスメモリ内の情報系列を加え，シフト処理で桁あふれした情報を復号ビット列として出力する。したがって，特許文献１に示されたビタビ復号器では，パスメモリ内に遷移元の状態番号のＬＳＢのみしか記憶しないので，パスメモリの容量を小さくすることはできるが，それに伴ってトレースバック処理が煩雑になっている。
【０００９】
また，特許文献４などでは，符号ビットを受信するたびに復号データとなるパス選択信号を生成しているので，パス選択信号の生成処理が複雑であり，送信されるデータ列のサイズが大きいとそのパス選択信号生成処理の負担が重くなる。
【００１０】
そこで，本発明の目的は，トレースバック処理を簡単にしたビタビ符号装置を提供することにある。
【課題を解決するための手段】
【００１１】
上記の目的を達成するために，本発明の第１の側面によれば，入力ビットとそれに先行する（Ｋ−１）個の入力ビットとを有する状態ビットから畳み込み符号された符号ビットを入力し，前記符号ビットから最尤符号して前記入力ビット列を復号するビタビ復号装置において，
前記入力される符号ビットに対して，パスメトリックに応じて所定の状態ビットに対応する遷移元状態ビットを選択し，取りうる複数の所定の状態ビットそれぞれについて当該遷移元状態ビットをサバイバルパスメモリに記憶するパスメモリ生成処理ユニットと，
前記入力される符号ビットに対する前記サバイバルパスメモリへの前記遷移元状態ビットの記憶がトレースバック長分終了した後に，トレースバックの起点となる状態ビットの最上位ビットを抽出し，当該最上位ビットが抽出された状態ビットに対応する前記サバイバルパスメモリ内の遷移元状態ビットの最上位ビットの抽出を繰り返し，当該抽出された最上位ビットを復号結果として出力するトレースバック処理ユニットとを有することを特徴とする。
【００１２】
上記の本発明の第１の側面において，好ましい態様では，前記ビタビ復号装置は，前記符号ビットを順番に受信し，前記パスメモリ生成処理ユニットは，前記符号ビットを受信するたびに前記遷移元状態ビットのサバイバルパスメモリへの記憶を行い，前記トレースバック処理ユニットは，前記トレースバック長分の符号ビットを受信した後に，トレースバック処理を行うことを特徴とする。
【００１３】
上記の目的を達成するために，本発明の第２の側面によれば，入力ビットとそれに先行する（Ｋ−１）個の入力ビットとを有する状態ビットから畳み込み符号された符号ビットを入力し，前記符号ビットから最尤符号して前記入力ビット列を復号するビタビ復号プログラムにおいて，
前記入力される符号ビットに対して，パスメトリックに応じて所定の状態ビットに対応する遷移元状態ビットを選択し，取りうる複数の所定の状態ビットそれぞれについて当該遷移元状態ビットをサバイバルパスメモリに記憶するパスメモリ生成処理ユニットと，
前記入力される符号ビットに対する前記サバイバルパスメモリへの前記遷移元状態ビットの記憶がトレースバック長分終了した後に，トレースバックの起点となる状態ビットの最上位ビットを抽出し，当該最上位ビットが抽出された状態ビットに対応する前記サバイバルパスメモリ内の遷移元状態ビットの最上位ビットの抽出を繰り返し，当該抽出された最上位ビットを復号結果として出力するトレースバック処理ユニットとを，コンピュータに構築させるビタビ復号プログラムである。
【発明の効果】
【００１４】
本発明の第１及び第２の側面によれば，入力される符号ビットに対し，取りうる状態ビットに対応して，その状態ビットのパスメトリックに応じて最尤の遷移元状態ビットを選択して，サバイバルパスメモリ内に記憶する。よって，トレースバック処理ではその遷移元状態ビットの最上位ビットの抽出を繰り返すだけで復号ビットを出力することができる。よって，トレースバック処理を極めて簡単に行うことができ，汎用プロセッサによるソフトウエアの実行であっても短時間での復号化処理が可能になる。
【発明を実施するための最良の形態】
【００１５】
以下，図面にしたがって本発明の実施の形態について説明する。但し，本発明の技術的範囲はこれらの実施の形態に限定されず，特許請求の範囲に記載された事項とその均等物まで及ぶものである。
【００１６】
［畳み込み符号化とビタビ符号化］
ビタビ復号装置は，畳み込み符号などの最尤復号法に用いられ，誤り訂正能力が高いので，伝送経路誤りが生じやすい衛星通信や移動体通信などの伝送方式における復号器として用いられている。ビタビ復号では，受信符号ビットと期待符号ビットとの差分からなるハミング距離（ブランチメトリック）を求めるブランチメトリック処理と，加算・比較・選択処理（ＡＣＳ：Ａｄｄ，Ｃｏｍｐａｒｅ，Ｓｅｌｅｃｔ）によるパスメモリ生成処理とが繰り返され，それらの処理が状態ビットの数×トレースバック長の回数だけ繰り返された後，最後に入力データに復号するトレースバック処理が行われる。
【００１７】
以下，入力ビットの畳み込み符号を生成する符号化処理と，その符号ビットから元の入力ビットに復号するビタビ復号化処理とについて，基本的事項を簡単に説明する。
【００１８】
図１は，畳み込み符号器の一例を示す図である。入力ビットＩＮが遅延機能を有するレジスタＲ１〜Ｒ８に順に入力され，入力ビットＩＮとレジスタＲ１〜Ｒ８に格納されたビットの排他的論理和ｃ０と，入力ビットＩＮとレジスタＲ２，Ｒ３，Ｒ４，Ｒ８に格納されたビットの排他的論理和ｃ１とが，排他的論理和回路ｇ０，ｇ１により生成される。符号ビットｃ０，ｃ１は，対応する入力ビットの「１」が奇数であれば「１」，偶数であれば「０」になる。１個の入力ビットＩＮの入力に伴って符号ビットｃ０，ｃ１が生成されると，次の入力ビットＩＮが入力され，各レジスタの情報は後段のレジスタにシフトされる。つまり，入力ビットＩＮが供給されるたびに符号化が行われ，レジスタ間でシフトされる。それにより，符号器の８つのレジスタ内の情報ビットからなる状態は２の８乗存在する。この状態を示すビット列を，以下状態ビットと称して説明する。
【００１９】
この符号器は，レジスタ数８，１個の入力ビットＩＮに対して２個の符号ビットｃ０，ｃ１が生成されるので符号化率ｒｃ＝１／２（ｋビットの入力ビットからｎビットの符号ビットが生成される場合の符号化率はｋ／ｎである。），１個の入力ビットＩＮと先行する８個の入力ビット（Ｒ１〜Ｒ８）から符号化されるので，符号化に影響を与える入力ビット数である拘束長ＫはＫ＝９である。
【００２０】
一般に符号器への入力ビットと出力ビットとの比率である符号化率は，入力ビット数に対して出力ビット数が多いほど小さくなり，伝送速度は落ちるが誤り訂正能力は高くなる。通常は，伝送速度の低下を回避するために符号化率は１／２にされる。また，拘束長Ｋは，符号ビット出力を得るために必要な過去の入力ビット数を表し，拘束長を大きくすることで誤り訂正能力は高くなるが，状態ビットの数が多くなりビタビ復号器の構成が複雑になる。
【００２１】
図２は，図１の符号器（Ｋ＝９）において入力ビットＩＮが「１，０，１，１，０，１，０」の場合の符号化の例を示す図表である。レジスタＲ１〜Ｒ８は全て「０」に初期化されているものとする。入力ビットＩＮが入力されるたびに，レジスタＲ１〜Ｒ８の状態が遷移し，それぞれの状態に対する符号ビットｃ０，ｃ１が出力される。
【００２２】
図３は，本実施の形態における符号器と復号器とを示す図である。送信側符号器１０では入力ビットＩＮと過去の入力ビットＲ１，Ｒ２から符号ビットｃ０，ｃ１を生成し，伝送路ＴＲを介して送出する。この例では，簡単化のために，符号器１０は２つのレジスタＲ１，Ｒ２を有し，拘束長Ｋ＝３，符号化率１／２である。したがって，符号器内のレジスタによる状態は，２の（Ｋ−１）乗である。また，受信側復号器２０では，受信した符号ビットを入力バッファＩＢＵＦに取り込み，復号処理プログラム２２を中央処理ユニットＣＰＵが実行することで，受信した符号ビットｃ０，ｃ１から元の入力ビットＩＮを復号化する。この復号化法は，前述の最尤復号法によって行われる。そして，復号化された元の入力ビットは出力バッファＯＢＵＦから出力される。復号器２０では，中央処理ユニットＣＰＵが内部バス２４を介してメモリ２６に接続され，復号化処理に際して，メモリ２６にはブランチメトリック２６１とパスメトリック２６２とを格納する領域と，選択パス情報を格納するサバイバルパスメモリ１６３の領域とが確保される。ブランチメトリック，パスメトリック，選択パス情報などについては，後に詳述する。
【００２３】
以下，畳み込み符号器とビタビ復号器の基本的原理について説明する。
【００２４】
ビタビ復号とは，畳み込み符号化された情報（符号ビット）を復号する復号方法であり，復号時に最も確からしい（最尤）送信符号ビットを推定し，その符号ビットを生成する状態ビットから元の入力ビットを出力する。そこでまず，畳み込み符号器の状態遷移を示すトレリス線図について説明する。
【００２５】
図４は，図３の畳み込み符号器におけるトレリス線図である。図３の畳み込み符号器１０は，２つのレジスタＲ１，Ｒ２を有し，拘束長Ｋ＝３，符号化率１／２である。したがって，２個のレジスタＲ１，Ｒ２の状態は，２の２乗（Ｋ−１乗）である４つの状態になる。図４中に，レジスタＲ１，Ｒ２のビットの組合せからなる４つの状態ビットが示されている。この４つの状態それぞれに対して，入力ビットＩＮが「０」の時の状態遷移が実線の矢印で示され，入力ビットＩＮが「１」の時の状態遷移が破線の矢印で示される。これら矢印はブランチとも称される。横方向には時間ｔ０〜ｔ５が示され，各時間での状態が黒丸で示されている。そして，黒丸で示した各状態からの遷移（実線と破線の矢印）に対して生成される符号ビットｃ０，ｃ１が示されている。
【００２６】
たとえば，時間ｔ０の状態ビットＲ１，Ｒ２＝００では，入力ビットＩＮ＝０で符号ビットｃ０，ｃ１＝００が生成され，状態ビット＝００に遷移し（実線矢印），入力ビットＩＮ＝１で符号ビットｃ０，ｃ１＝１１が生成され，状態ビット＝１０に遷移（破線矢印）する。同様に，時間ｔ０の状態ビットＲ１，Ｒ２＝０１では，入力ビットＩＮ＝０で符号ビットｃ０，ｃ１＝１１が生成され，状態ビット＝００に遷移し（実線矢印），入力ビットＩＮ＝１で符号ビットｃ０，ｃ１＝００が生成され，状態ビット＝１０に遷移（破線矢印）する。状態ビットＲ１，Ｒ２＝１０では，入力ビットＩＮ＝０で符号ビットｃ０，ｃ１＝１０が生成され，状態ビット＝０１に遷移し（実線矢印），入力ビットＩＮ＝１で符号ビットｃ０，ｃ１＝０１が生成され，状態ビット＝１１に遷移（破線矢印）する。最後に，状態ビットＲ１，Ｒ２＝１１では，入力ビットＩＮ＝０で符号ビットｃ０，ｃ１＝０１が生成され，状態ビット＝０１に遷移し（実線矢印），入力ビットＩＮ＝１で符号ビットｃ０，ｃ１＝１０が生成され，状態ビット＝１１に遷移（破線矢印）する。
【００２７】
上記の状態遷移とそれに伴って生成される符号ビットｃ０，ｃ１は，いずれの時間ｔ０〜ｔ４においても同じである。一般に，入力ビットＩＮ＝０に対して状態ビットはより上側に遷移し，入力ビットＩＮ＝１に対して状態ビットはより下側に遷移する。
【００２８】
上記のトレリス線図によれば，受信側の復号器は，受信する符号ビットｃ０，ｃ１に基づいて状態ビットの遷移を逆トレースすることができる。状態ビットの遷移が逆トレースできれば，その状態ビットに遷移させた入力ビットＩＮを知ることができるので，元の入力ビットＩＮに復号することができる。ただし，伝送路には誤りが発生するので受信する符号ビットが全て正しいとは限らない。そこで，遷移元の状態ビットを選択するために，受信符号ビットｃ０，ｃ１と，トレリスのブランチ（パス）に対応する送信符号ビットｃ０，ｃ１とのハミング距離（差分）であるメトリックが利用される。つまり，このメトリックがより小さいほうに状態が遷移したとすることでより確からしい（最尤の）状態遷移を推測することができる。
【００２９】
図５は，ビタビ復号におけるパスメトリックを説明する図である。前述したトレリス線図と同様に，４つの状態ビットそれぞれに対応して入力ビットＩＮ＝０，１に対する２つの遷移が示されている。そして，２つの遷移を示すブランチ（図４のトレリス線図の矢印）にはそれぞれ生成される符号ビットが示されている。この符号ビットは，送信側から送信される符号ビットＴｄａｔａである。また，図５には受信側で受信される符号ビットＲｄａｔａの例が示されている。
【００３０】
期待符号ビットである送信符号ビットＴｄａｔａと，受信符号ビットＲｄａｔａとのハミング距離がブランチメトリックＢＭとして算出可能である。ハミング距離とは，２つのビット列の異なるビット数のことであり，例えば，１１と１１であれば完全一致でありハミング距離は０になり，１１と１０であれば１ビットのみ異なるのでハミング距離は１となり，１１と００であれば２ビットが異なるのでハミング距離は２となる。
【００３１】
たとえば，時間ｔ１の状態ビット００のノードＮ１の上下には，その状態ビットに遷移するときの送信符号ビットＴｄａｔａと，受信符号ビットＲｄａｔａとのハミング距離であるブランチメトリックＢＭ「２」「０」が示されている。つまり，受信符号ビットＲｄａｔａ＝１１に対して，そのノードＮ１に遷移可能な２つのブランチの送信符号ビットＴｄａｔａ＝００，１１とのハミング距離は，それぞれ２，０である。したがって，このノードＮ１（状態ビット００，時間ｔ１）に遷移する時に送出された送信符号ビットＴｄａｔａは，受信符号ビットＲｄａｔａとのハミング距離（ブランチメトリック）が小さいほう（ＢＭ＝０）がより確からしいと判定すると，ノードＮ１に遷移した最尤のパスは状態ビット０１からのパスと判定できる。
【００３２】
時間ｔ５の状態ビット００のノードＮ４に示されるとおり，各ノードの上下には，ブランチメトリックＢＭと，時間ｔ０からそのノードに至るブランチメトリックＢＭの累積値であるパスメトリックＰＭが括弧内に示されている。つまり，各ノードにはＢＭ（ＰＭ）が上下に示されている。ここで，パスメトリックＰＭは，当該状態に遷移可能な経路の最小メトリックとブランチメトリックの累和である。たとえば，時間ｔ２の状態ビット００のノードＮ３のブランチメトリックＢＭは１，１であるが，遷移元のノードＮ１（時間ｔ１の状態ビット００）のブランチメトリックＢＭ（ノードＮ１ではＰＭと等しい）のうち小さい値「０」と，当該ノードＮ３のブランチメトリックＢＭ＝１との累和＝１が，そのノードＮ３のパスメトリックＰＭ＝１になる。また，遷移元のノードＮ２（時間ｔ１の状態ビット０１）のブランチメトリックＢＭのうち小さい値「１」（上下ＢＭは同じ値）と，ノードＮ３のブランチメトリックＢＭ＝１との累和＝２が，そのノードＮ３のパスメトリックＰＭ＝２になる。したがって，ノードＮ３の上下にはＢＭ（ＰＭ）＝１（０），１（２）が示されている。他のノードも同様である。
【００３３】
上記のように，受信符号ビットＲｄａｔａを受信するたびに，各状態ノードのブランチメトリックＢＭとパスメトリックＰＭとを演算で求めることができる。そして，伝送路にノイズが発生して受信符号ビットＲｄａｔａが送信符号ビットＴｄａｔａと異なっても，そのハミング距離（メトリック）が最小になる遷移経路を選択することで，最尤の遷移経路を見つけ出し，最尤の入力データを復号することができる。
【００３４】
図５の例では，時間ｔ５までの全ての状態のノードに対してブランチメトリックＢＭとパスメトリックＰＭとが示されている。そして，時間ｔ５の４つのノードのパスメトリックＰＭを比較すると状態ビット１０に対応するノードＮ５が最も小さいパスメトリックＰＭ＝０を有している。そこで，このノードＮ５をトレースバック処理の開始点に選ぶことで最尤入力データの復号ができる。トレリス線図では，各状態に遷移する２つのパスのうち，パスメトリックＰＭの小さい方のパスをサバイバルパスと称する。つまり，トレースバック処理の開始点であるノードＮ５から，パスメトリックＰＭの小さい方のサバイバルパスをトレースすることで，最も確からしい（最尤）の遷移経路をたどることができる。図５の例では，ノードＮ５の状態から，状態ビット００へ，さらに状態ビット００へ，さらに状態ビット０１へ，さらに状態ビット１０へ，最後に状態ビット００にトレースバックされる。
【００３５】
なお，トレースバック処理の開始点の選択において，入力ビットの最後にテールビットとして送信側と受信側で既知のビット列，例えば０００〜を付加することで，最終状態ビットを００に確定することができる。このように最終状態ビットが既知の場合，状態ビット００のノードＮ４がトレースバック処理の開始ノードにされる。このようにテールビットを利用することで開始ビットが伝送路の誤りに影響を受けることを避けることができる。このように遷移経路をトレースバックすれば，各遷移の原因となった元の入力ビットを高い確率で復元することができる。なお，テールビットが１１１〜の場合は，開始ノードは状態ビット１１になる。
【００３６】
以上のように，トレリス線図の各ノードにブランチメトリックＢＭとパスメトリックＰＭを演算で求めておき，最終状態のノードを開始点として，より小さいパスメトリックの遷移ブランチをトレースバックすることで，符号器における最尤の状態遷移経路を検出することができ，それに基づいて最尤の元の入力データを復号化することができる。ただし，トレリス線図の情報を全てメモリに格納するとデータ容量が膨大になり現実的ではない。
【００３７】
［特許文献１の復号方法］
図６は，特許文献１の復号方法を示す図である。特許文献１によれば，復号器が符号ビットを受信するたびにサバイバルメモリ内に選択パス情報を格納し，トレース長の符号ビットを受信完了した後に，サバイバルメモリ内の選択パス情報に基づいてトレースバック処理をして，元の入力ビットを復号化する。
【００３８】
上記のサバイバルメモリへの選択パス情報の格納工程では，（１）各状態ノードにおける上下のパスのパスメトリック値を遷移元の少ない方のパスメトリックに当該状態ノードのブランチメトリックを加算して求め，（２）各状態ノードにおいて上下の入力パスのパスメトリック値を比較し，（３）パスメトリック値が小さいほうの遷移元状態ビットを選択し，その遷移元状態ビットの最下位ビットＬＳＢを選択パス情報としてサバイバルパスメモリ２６３に記憶する。パスメトリック値が等しい場合はいずれかの遷移元状態ビットのＬＳＢ（０または１）を記憶する。図６の例では０を記憶している。例えば，時間ｔ５での４つの状態ノードの場合は，それぞれパスメトリック値が小さい方の遷移元状態ビットのＬＳＢは，０，０，０，０になる。それ以外の時間ｔ４〜ｔ１での遷移元状態ビットのＬＳＢも同様に記憶されている。
【００３９】
上記のように，サバイバルパスメモリ２６３に記憶する選択パス情報を各状態ノードでＬＳＢの１ビットのみにしているので，メモリ容量を小さくすることができる。
【００４０】
図７は，トレースバック処理を示す図である。図７では，トレースバック処理の開始状態ノードが状態ビット１０のノードの例で示されている。特許文献１のトレースバック処理では，開始される状態ビット１０を変数として取得する（Ｓ１）。そして，その状態ビット１０を左シフトする（Ｓ２）。そして，左シフトした変数の最下位ビットにサバイバルパスメモリ内の選択パス情報０を入力する（Ｓ３）。そして，変数の最上位ビットＭＳＢから復号結果１を抽出する（Ｓ４）。さらに，変数の下位２ビットを遷移元状態ビット００として抽出する（Ｓ５）。
【００４１】
上記の工程Ｓ２〜Ｓ５が，全てのトレースバック長だけ繰り返される。そのトレースバック処理によりトレースされる状態の遷移経路は，図７中のサバイバルパスメモリにグレーの格納領域で示している。その結果，復号された出力値として１０００１が抽出される。
【００４２】
［本実施の形態の復号方法］
本実施の形態では，ビタビ復号のトレースバック処理を簡素化してソフトウエア処理に適合しやすくする。一方，サバイバルパスメモリに格納する選択パス情報のデータ量の増大は許容する。つまり，近年におけるメモリの廉価化に伴いメモリ容量よりもソフトウエア処理の簡素化に重点を置いた復号方法である。
【００４３】
図８，図９は，本実施の形態における復号方法を示す図であり，図８はサバイバルパスメモリの生成を示し，図９はトレースバック処理を示す。図８において，図６と同様のトレリス線図と受信符号ビットＲｄａｔａとが示されている。そして，符号ビットＲｄａｔａを受信するたびに，各状態ビットに対応してブランチメトリックＢＭとパスメトリックＰＭとを演算することは特許文献１と同じである。ただし，パスメトリックの比較に基づき選択処理により選択された遷移元状態ビットそのものが，サバイバルパスメモリに記憶される。この点が特許文献１と異なる。こうすることでトレースバック処理を簡単化できる。
【００４４】
図８の例で説明すると，時間ｔ５における４つの取りうる状態ノードにおいて，状態ビット００では，パスメトリックＰＭが等しいので低いビットである遷移元状態ビット００が選択され記憶される。また，状態ビット０１でも同様にＰＭが等しいので低いビットである遷移元状態ビット１０が選択され記憶される。そして，状態ビット１０ではＰＭが低いほうの遷移元状態ビット００が選択され記憶される。さらに，状態ビット１１ではＰＭが等しいので低いビットである遷移元状態ビット１０が選択され記憶される。他の時間ｔ４〜ｔ１においても同様に，パスメトリックの比較とより低いパスメトリックの遷移元状態ビットが選択され記憶される。
【００４５】
受信符号ビットＲｄａｔａを受信するたびに，ブランチメトリックＢＭとパスメトリックＰＭとが求められ，選択パス情報としてパスメトリックの低い遷移元状態ビットが選択され記憶される。ただし，ブランチメトリックＢＭとパスメトリックＰＭとは全ての時間について記憶しておく必要はなく，パスメトリックＰＭのみが更新される。
【００４６】
次に，サバイバルパスメモリへの選択パス情報の格納がトレースバック長だけ完了すると，トレースバック処理が行われる。本実施の形態によれば，サバイバルパスメモリ内に遷移元状態ビットがそのまま記憶されているので，トレースバック処理は簡素化される。つまり，図９に示すとおり，まずトレース開始ノードの状態ビット１０を取得し（Ｓ１０），その状態ビット１０の最上位ビットＭＳＢを復号ビットとして抽出する（Ｓ１１）。次に，サバイバルメモリに格納されている選択パス情報（遷移元状態ビット）を読み出す（Ｓ１２）。この読み出した選択パス情報が遷移元状態ビットそのものであるので，そのＭＳＢが次の復号ビットとして抽出される（Ｓ１１）。上記の処理Ｓ１２，Ｓ１１を繰り返すことで，サバイバルパスメモリのグレーの状態ビットがトレースされる。
【００４７】
上記のように，トレースバック処理は単にサバイバルパスメモリに格納されている遷移元状態ビットを読み出して，そのＭＳＢを抽出する処理を繰り返すだけでよい。したがって，ソフトウエア処理を簡素化することができる。通常の畳み込み符号器は拘束長Ｋが比較的長いので，その拘束長をバイト単位またはワード単位にすれば，ソフトウエアによる情報処理への適合性を高くすることができる。
【００４８】
次に，本実施の形態におけるビタビ復号器の具体例を説明する。
【００４９】
図１０は，本実施の形態におけるビタビ復号器の処理モジュールとメモリの関係を示す図である。ビタビ復号器２０のハードウエア構成は，図３に示したとおり，中央処理ユニットＣＰＵと復号処理プログラム２２とメモリ２６とで構成される。そして，復号処理プログラムの処理モジュールが図１０に示されている。これら処理モジュールを有するビタビ復号プログラムがコンピュータにインストールされることで処理ユニットを構築する。
【００５０】
図１０に示されるとおり，受信符号ビットＲｄａｔａを受信すると，ブランチメトリック処理モジュールＳ１が全ての状態ビットに対応してブランチメトリックＢＭを求める。具体的には，前述の通り送信符号ビットＴｄａｔａと受信符号ビットＲｄａｔａとのハミング距離がブランチメトリックである。そして，求められたブランチメトリックＢＭがパスメモリ生成処理モジュールＳ２に供給される。パスメモリ生成処理モジュールＳ２は，供給されたブランチメトリックＢＭとパスメトリックメモリ２６２内に格納されている遷移元状態ビットの小さいほうのパスメトリックＰＭとを加算して新たなパスメトリックを求め，２つの遷移元状態ビットに対応して新たに求めたパスメトリックをパスメトリックメモリ２６２に記憶する。そして，求めたパスメトリックの小さいほうに対応する遷移元状態ビットを，サバイバルパスメモリ２６３に記憶する。
【００５１】
そして，トレースバック長分のサバイバルパスメモリへの遷移元状態ビットの記憶が終了すると，トレースバック処理モジュールＳ３が，サバイバルパスメモリ内の情報に基づいて，図９で説明したトレースバック処理を行い，最尤の元の入力ビットを復号する。
【００５２】
図１１は，パスメモリ生成処理モジュールの概略処理フローチャート図である。この処理では，受信した符号ビットであるデータＤ（ｎ）に対する状態Ｘの上下のパスメトリックＰＭを求める（Ｓ１０１）。そして，上下の入力パスのパスメトリックを比較する（Ｓ１０２）。比較した結果，パスメトリックが小さいほうの遷移元状態の状態ビットをサバイバルパスメモリに記憶する（Ｓ１０３）。上記の処理を全ての状態について繰り返す（Ｓ１０４）。さらに，上記処理Ｓ１０１〜Ｓ１０４が，符号ビットを受信するたびに行われる（Ｓ１０５）。あるいは，トレースバック長分の符号ビットを受信した後に，トレリス線図の全状態ノードと全受信符号ビットについて，図１１の処理を行うことでサバイバルパスメモリを作成してもよい。ただし，その場合は，符号ビットの受信完了後に行われる処理工数が増加する。よって，符号ビットを受信するたびにサバイバルパスメモリに遷移元状態ビットを記憶する処理を行うことが好ましい。
【００５３】
図１２は，トレースバック処理の概略処理フローチャート図である。最初に変数Ａを定義する（Ｓ１１０）。この変数Ａは，図９に示した２ビットの変数であり，拘束長Ｋ＝３の場合には変数Ａのビット数はＫ−１＝２である。そして，変数Ａにトレースバック開始の状態ビットを設定する（Ｓ１０）。そして，変数ＡのＭＳＢを抽出して復号結果を取得する（Ｓ１１）。さらに，その状態ビットに対応するサバイバルパスメモリ２６３内に格納されている遷移元状態ビットを読み出し，変数Ａに設定する（Ｓ１２）。この変数Ａに設定された遷移元状態ビットのＭＳＢを抽出して復号結果を出力する（Ｓ１１）。上記の処理Ｓ１２，Ｓ１１が，全ての受信符号ビットについて繰り返されて（Ｓ１１２），トレースバック処理が完了する。
【００５４】
図１３，図１４，図１５は，本実施の形態におけるビタビ復号器の処理モジュールの具体的なフローチャート図である。図１３のブランチメトリック処理は，受信した符号ビットＲｄａｔａが入力されるたびに実行される。そこで受信時の時間をｔ（ｎ）とする。このブランチメトリック処理では，最初に変数Ｘに状態ビットを設定する（Ｓ１２１）。初期値は状態ビット００である。次に，状態Ｘに遷移可能な２つの遷移元状態から状態Ｘに遷移するときの符号ビットｃ０，ｃ１を求める（Ｓ１２２）。この符号ビットｃ０，ｃ１は，遷移元状態ビットと入力ビットから畳み込み符号化されたビットである。そして，求めた状態Ｘに対応する符号ビットと，その時間ｔ（ｎ）での受信符号ビットとのブランチメトリックＢＭを計算する（Ｓ１２３）。最後に，計算で求めたブランチメトリックＢＭを状態Ｘの情報としてパスメモリ生成処理モジュールＳ２に通知する（Ｓ１２４）。上記の処理は，時間ｔ（ｎ）における全ての状態（図８の例では４つの状態）について繰り返される（Ｓ１２５）。
【００５５】
図１４のパスメモリ生成処理も，受信符号ビットＲｄａｔａが入力されるたびに実行される。最初に，状態ビットの変数Ｘと，状態Ｘに遷移可能な２つの状態ビット（遷移元状態ビット）の変数Ｙ，Ｚとを定義する（Ｓ１３１）。さらに，変数設定として，時間ｔ（ｎ）におけるパスメトリック設定用変数Ｔを定義する（Ｓ１３２）。
【００５６】
初期値が００の状態Ｘに遷移可能な２つの状態ビット００，０１を変数Ｙ，Ｚに設定する（Ｓ１３３）。遷移可能な２つの状態ビットＹ，Ｚは，状態ビットＸに対してＹ＝２Ｘ，Ｙ＝２Ｘ＋１の演算により算出可能である。ただし，０ビット目をＬＳＢとし，拘束長をＫとするとＫ−１ビット目を０にする必要がある。一例として，Ｘ＝１１なら，Ｙ＝２Ｘ＝１１０，Ｚ＝２Ｘ＋１＝１１１で，Ｋ−１ビット目を０にすれば，Ｙ＝０１０，Ｚ＝０１１となり，下位２ビットが遷移可能な２つの状態ビットＹ，Ｚとして算出可能である。
【００５７】
そして，状態Ｙ，Ｚの時間ｔ（ｎ−１）におけるパスメトリックをパスメトリックメモリ２６２から読み出す（Ｓ１３４）。状態Ｙ＝００のパスメトリックに，時間ｔ（ｎ）に状態Ｙから状態Ｘに遷移した場合のブランチメトリックを加算する。同様に，状態Ｚ＝０１のパスメトリックに，時間ｔ（ｎ）に状態Ｚから状態Ｘに遷移した場合のブランチメトリックを加算する（Ｓ１３５）。上記加算により得た２つのパスメトリック値を比較し，小さい方の遷移元状態ビットを時間ｔ（ｎ）における状態Ｘのパス選択情報としてサバイバルパスメモリ２６３に記憶する（Ｓ１３６）。さらに，加算により得た２つのパスメトリック値のうち小さい方を状態Ｘの時間ｔ（ｎ）におけるパスメトリック値として変数Ｔに設定する（Ｓ１３７）。
【００５８】
図１６は，パスメトリックメモリの具体例を示す図である。図中状態数分の要素を有するパスメトリックＰＭメモリが示されている。つまり，時間ｔ（ｎ）のパスメトリック値が常に更新され保存されるのであり，全ての時間におけるパスメトリック値を保存する必要はない。
【００５９】
上記の処理Ｓ１３３〜Ｓ１３７が時間ｔ（ｎ）での全ての状態について繰り返される。状態Ｘは０１と設定され，Ｙ＝１０，Ｚ＝１１と設定され，同様の処理が行われパスメトリック値が算出され，パスメトリック値が小さいほうの遷移元状態ビットがサバイバルパスメモリに記憶され，パスメトリック値の小さいほうが変数Ｔに設定される。続いて，状態Ｘ＝１０に，Ｙ＝００，Ｚ＝０１に設定され同様の処理が行われる。最後に，状態Ｘ＝１１に，Ｙ＝１０，Ｚ＝１１に設定され同様の処理が行われる。時間ｔ（ｎ）の全状態について処理が完了すると，最後に，変数Ｔに設定されたパスメトリック値が，時間ｔ（ｎ）のパスメトリック値としてパスメトリックメモリに上書きされる（Ｓ１３９）。
【００６０】
図１７は，サバイバルパスメモリの一例を示す図である。横方向がトレースバック長に対応する時間ｔ（０）〜ｔ（ｎ），縦方向が状態に対応し，それぞれの要素に遷移元状態ビットが記憶される。したがって，サバイバルパスメモリは，トレースバックに必要な選択パス情報を記憶しておく必要がある。
【００６１】
図１５のトレースバック処理は，図１３，図１４の処理がトレースバック長分完了した後に実行される。つまりデータブロックの受信完了した後にトレースバック処理が行われる。まず，状態ビットを示す変数Ｘが定義される（Ｓ１４１）。受信データの最終時間をｔ（ｎ）とすると，パスメトリックメモリ内の時間ｔ（ｎ）におけるパスメトリック値のうち最も小さい値に対応する状態ビットを抽出し，変数Ｘに設定して，トレースバック開始とする（Ｓ１４２）。トレースバック開始位置は，上記以外に，送受信間で既知のテールビットが設定されているなど，トレースバック開始すべき状態が既知の場合は，その状態ビットを変数Ｘに設定する（Ｓ１４２）。
【００６２】
次に，サバイバルパスメモリ内の時間ｔ（ｎ）における状態Ｘのビットを，開始状態ビットとして変数Ｘに設定する（Ｓ１０）。設定された変数ＸのＭＳＢを，または拘束長Ｋの場合のＫ−１ビット目を，時間ｔ（ｎ）における復号ビットとして出力する（Ｓ１１）。さらに，サバイバルパスメモリ内に状態Ｘに対応して格納されている遷移元状態ビットを，変数Ｘに上書きする（Ｓ１２）。そして，その変数Ｘについて工程Ｓ１２を行い，次の復号ビットを出力する（Ｓ１１）。上記の工程Ｓ１２，Ｓ１１が全ての受信符号ビットについて繰り返され，最尤の入力ビットがｔ（ｎ），ｔ（ｎ−１）．．．ｔ（１），ｔ（０）の順に出力される（Ｓ１４３）。
【００６３】
以上のように，トレースバック処理は，単にサバイバルパスメモリ内に格納された遷移元状態ビットを読み出して，そのＭＳＢを復号出力として出力するだけであり，ソフトウエア処理としては極めて簡単な処理となる。したがって，専用のハードウエア回路を設ける必要がなく，コストダウンすることができる。
【００６４】
図１８は，本実施の形態におけるビタビ復号器の動作のメリットを示す図である。上の段にデータブロックが時間ｔ１，ｔ２，ｔ３で送信されることが示されている。データブロックは，入力ビットのデータ列ｄａｔａと最後に付加されるテールビット列ｔａｉｌとで構成される。本実施の形態のビタビ復号器では，データブロックに対応する符号ビット列を受信完了した後に，トレースバック処理を行う。しかも，そのトレースバック処理ではサバイバルパスメモリから選択パス情報として遷移元情報ビットを読み出すので，読み出したデータに復号出力とトレースバックする遷移元状態ビットが含まれている。よって，復号結果の抽出とトレースバックの処理が簡単になる。よって，トレースバック時間を短くすることができる。そのことは，図１８の下段に示すとおり，データブロック内に格納できる入力ビット列のデータ数を増やすことができ，単位時間当たりの伝送データ量を増加し，伝送効率を高くすることができることを意味する。
【００６５】
図１９は，本実施の形態におけるビタビ復号器の動作の別のメリットを示す図である。図１９の上段に示されるとおり，複数のユーザ情報を一度に処理する基地局では，先行するデータブロックのトレースバック処理が完了する前に，オーバラップ（図中ＯＬＡＰ）して次のデータブロックを受信することがある。そのため，２つのサバイバルパスメモリを確保し，オーバラップ中の先行するデータブロック用のサバイバルパスメモリと，後続のデータブロック用のサバイバルパスメモリとが利用される。しかし，本実施の形態のビタビ復号器ではトレースバック処理が簡単化されて短時間で行うことができるので，図１９の下段に示すように，オーバラップを解消し，１つのサバイバルパスメモリだけで復号処理可能になる。
【００６６】
以上の実施の形態をまとめると，次の付記のとおりである。
【００６７】
（付記１）入力ビットとそれに先行する（Ｋ−１）個の入力ビットとを有する状態ビットから畳み込み符号された符号ビットを入力し，前記符号ビットから最尤符号して前記入力ビット列を復号するビタビ復号装置において，
前記入力される符号ビットに対して，パスメトリックに応じて所定の状態ビットに対応する遷移元状態ビットを選択し，取りうる複数の所定の状態ビットそれぞれについて当該遷移元状態ビットをサバイバルパスメモリに記憶するパスメモリ生成処理ユニットと，
前記入力される符号ビットに対する前記サバイバルパスメモリへの前記遷移元状態ビットの記憶がトレースバック長分終了した後に，トレースバックの起点となる状態ビットの最上位ビットを抽出し，当該最上位ビットが抽出された状態ビットに対応する前記サバイバルパスメモリ内の遷移元状態ビットの最上位ビットの抽出を繰り返し，当該抽出された最上位ビットを復号結果として出力するトレースバック処理ユニットとを有することを特徴とするビタビ復号装置。
【００６８】
（付記２）付記１において，
前記ビタビ復号装置は，前記符号ビットを順番に受信し，
前記パスメモリ生成処理ユニットは，前記符号ビットを受信するたびに前記遷移元状態ビットのサバイバルパスメモリへの記憶を行い，
前記トレースバック処理ユニットは，前記トレースバック長分の符号ビットを受信した後に，トレースバック処理を行うことを特徴とするビタビ復号装置。
【００６９】
（付記３）付記２において，
さらに，前記取りうる複数の所定の状態ビットに対応して，前記入力される符号ビットと前記遷移元状態ビットに対応する符号ビットとのブランチメトリックを求めるブランチメトリック処理ユニットを有し，
前記パスメモリ生成処理ユニットは，前記求められたブランチメトリックに前記遷移元状態ビットのパスメトリックのうち最小のパスメトリックを加算して，当該所定の状態ビットのパスメトリックを求め，当該求めたパスメトリックのうち最小のパスメトリックに対応する遷移元状態ビットを選択することを特徴とするビタビ復号装置。
【００７０】
（付記４）付記３において，
前記パスメモリ生成処理ユニットは，前記符号ビットを受信するたびに，全ての状態ビットに対するパスメトリックを求め，当該求めたパスメトリックを更新することを特徴とするビタビ復号装置。
【００７１】
（付記５）付記１において，
前記入力される符号ビットは，所定ビット長の入力ビットとそれに後続する所定ビット長のテールビットとから符号化された符号ビットであり，
前記トレースバック処理ユニットは，前記テールビットに対応する状態ビットをトレース開始状態ビットとすることを特徴とするビタビ復号装置。
【００７２】
（付記６）付記１において，
前記取りうる複数の所定の状態ビットの数は，２の（Ｋ−１）乗であることを特徴とするビタビ復号装置。
【００７３】
（付記７）入力ビットとそれに先行する（Ｋ−１）個の入力ビットとを有する状態ビットから畳み込み符号された符号ビットを入力し，前記符号ビットから最尤符号して前記入力ビット列を復号するビタビ復号プログラムにおいて，
前記入力される符号ビットに対して，パスメトリックに応じて所定の状態ビットに対応する遷移元状態ビットを選択し，取りうる複数の所定の状態ビットそれぞれについて当該遷移元状態ビットをサバイバルパスメモリに記憶するパスメモリ生成処理ユニットと，
前記入力される符号ビットに対する前記サバイバルパスメモリへの前記遷移元状態ビットの記憶がトレースバック長分終了した後に，トレースバックの起点となる状態ビットの最上位ビットを抽出し，当該最上位ビットが抽出された状態ビットに対応する前記サバイバルパスメモリ内の遷移元状態ビットの最上位ビットの抽出を繰り返し，当該抽出された最上位ビットを復号結果として出力するトレースバック処理ユニットとを，コンピュータに構築させるビタビ復号プログラム。
【００７４】
（付記８）付記７において，
前記符号ビットが順番に受信され，
前記パスメモリ生成処理ユニットは，前記符号ビットを受信するたびに前記遷移元状態ビットのサバイバルパスメモリへの記憶を行い，
前記トレースバック処理ユニットは，前記トレースバック長分の符号ビットを受信した後に，トレースバック処理を行うことを特徴とするビタビ復号プログラム。
【００７５】
（付記９）付記８において，
さらに，取りうる複数の所定の状態ビットに対応して，前記入力される符号ビットと前記遷移元状態ビットに対応する符号ビットとのブランチメトリックを求めるブランチメトリック処理ユニットを，コンピュータに構築させ，
前記パスメモリ生成処理ユニットは，前記求められたブランチメトリックに前記遷移元状態ビットのパスメトリックのうち最小のパスメトリックを加算して，当該所定の状態ビットのパスメトリックを求め，当該求めたパスメトリックのうち最小のパスメトリックに対応する遷移元状態ビットを選択することを特徴とするビタビ復号プログラム。
【００７６】
（付記１０）付記９において，
前記パスメモリ生成処理ユニットは，前記符号ビットを受信するたびに，全ての状態ビットに対するパスメトリックを求め，当該求めたパスメトリックを更新することを特徴とするビタビ復号プログラム。
【００７７】
（付記１１）付記７において，
前記入力される符号ビットは，所定ビット長の入力ビットとそれに後続する所定ビット長のテールビットとから符号化された符号ビットであり，
前記トレースバック処理ユニットは，前記テールビットに対応する状態ビットをトレース開始状態ビットとすることを特徴とするビタビ復号プログラム。
【図面の簡単な説明】
【００７８】
【図１】畳み込み符号器の一例を示す図である。
【図２】図１の符号器において入力ビットの変化に対する符号化の例を示す図表である。
【図３】本実施の形態における符号器と復号器とを示す図である。
【図４】図３の畳み込み符号器におけるトレリス線図である。
【図５】ビタビ復号におけるパスメトリックを説明する図である。
【図６】特許文献１の復号方法を示す図である。
【図７】トレースバック処理を示す図である。
【図８】本実施の形態における復号方法を示す図である。
【図９】本実施の形態における復号方法を示す図である。
【図１０】本実施の形態におけるビタビ復号器の処理モジュールとメモリの関係を示す図である。
【図１１】パスメモリ生成処理モジュールの概略処理フローチャート図である。
【図１２】トレースバック処理の概略処理フローチャート図である。
【図１３】本実施の形態におけるビタビ復号器の処理モジュールの具体的なフローチャート図である。
【図１４】本実施の形態におけるビタビ復号器の処理モジュールの具体的なフローチャート図である。
【図１５】本実施の形態におけるビタビ復号器の処理モジュールの具体的なフローチャート図である。
【図１６】パスメトリックメモリの具体例を示す図である。
【図１７】サバイバルパスメモリの一例を示す図である。
【図１８】本実施の形態におけるビタビ復号器の動作のメリットを示す図である。
【図１９】本実施の形態におけるビタビ復号器の動作の別のメリットを示す図である。
【符号の説明】
【００７９】
２０：ビタビ復号装置                  Ｓ１：ブランチメトリック処理モジュール
Ｓ２：パスメモリ生成処理モジュール    Ｓ３：トレースバック処理モジュール
２６２：パスメトリックメモリ          ２６３：サバイバルパスメモリ