(57)【要約】【課題】繰り返し処理を行わないことで低遅延処理を実現し、且つ、打切り誤差による復号系列端の復号精度の劣化を低減するビタビ復号装置及びビタビ復号方法を提供すること。【解決手段】復号装置１００において、生き残りパス算出処理部１１０−１，２が、互いに異なるＡＣＳ演算スタートポイントからＡＣＳ演算することにより生き残りパスを算出し、トレースバック処理部１３０が、生き残りパス算出処理部１１０−１，２で得られた生き残りパスに基づいてトレースバック処理を行う。こうすることで、異なるスタートポイントからＡＣＳ演算を開始することにより得られる生き残りパスは、互いに誤り易い箇所が異なっている。従ってこれらの生き残りパスを用いてトレースバック処理を行うことより、従来のような繰り返し処理を行わなくても、打切り誤差による復号系列端の復号精度の劣化を低減することができる。【選択図】図１
2010041569.tif 000002
【特許請求の範囲】
【請求項１】
テイルバイティングが適用され且つ情報長がＮの符号化信号列に対して、トレリス線図上の互いに異なる開始点からＡＣＳ演算することにより生き残りパスを算出する複数の生き残りパス算出手段と、
前記複数の生き残りパス算出手段で算出された生き残りパスに基づいて、トレースバック処理を行うトレースバック処理手段と、
を具備するビタビ復号装置。
【請求項２】
前記複数の生き残りパス算出手段のそれぞれで得られた複数の生き残りパスのうち尤度が最大の生き残りパスを選択し、選択された複数の生き残りパスを合成した合成パスが巡回性を有するか否かを確認するビットバイティング条件確認手段をさらに有し、
前記トレースバック処理手段は、前記巡回性を有する合成パスに対してトレースバック処理を行う、
請求項１に記載のビタビ復号装置。
【請求項３】
前記生き残りパス算出手段は、Ｍ個並列に設けられ、
前記Ｍ個の開始点は、互いにＮ／Ｍの離間距離を持つ、
請求項１又は請求項２のいずれかに記載のビタビ復号装置。
【請求項４】
前記ビットバイティング条件確認手段は、前記合成パスを構成する複数の生き残りパスに対してＮ／Ｍ分のトレースバック処理を行うことにより、前記巡回性の確認を行う、
請求項３に記載のビタビ復号装置。
【請求項５】
前記ビットバイティング条件確認手段は、前記ＡＣＳ演算の開始点からＮ／Ｍ時点以上Ｎ時点以下の任意の時点で、前記巡回性の確認を行う、
請求項３に記載のビタビ復号装置。
【請求項６】
前記トレースバック処理手段は、第１の生き残りパス算出手段で得られた生き残りパスの１つに対してトレーニング処理を行い、このトレーニング結果に基づいて第２の生き残りパス算出手段で得られた複数の生き残りパスのうちから１つのパスを選択し、当該選択パスについてトレースバック処理を行う、
請求項１に記載のビタビ復号装置。
【請求項７】
前記トレーニング処理の対象である前記第１の生き残りパス算出手段で得られた生き残りパスは、前記第１の生き残りパスで得られる複数のパスのうち最大尤度の生き残りパスである、
請求項６に記載のビタビ復号装置。
【請求項８】
前記第１の生き残りパス算出手段は、前記第２の生き残りパス算出手段以外の前記複数の生き残りパス算出手段のうち、最大のトレーニング長を有する、
請求項６に記載のビタビ復号装置。
【請求項９】
前記生き残りパス算出手段は、Ｍ個並列に設けられ、
前記Ｍ個の開始点は、互いにＮ／Ｍの離間距離を持ち、
前記生き残りパス算出手段は、前記ＡＣＳ演算の開始点からＮ／Ｍ時点までの前記生き残りパスのみを出力する、
請求項１又は請求項２のいずれかに記載のビタビ復号装置。
【請求項１０】
前記生き残りパス算出手段は、算出した生き残りパスの一部のみを出力する、
請求項１又は請求項２のいずれかに記載のビタビ復号装置。
【請求項１１】
前記複数の生き残りパス算出手段に接続される１つのメモリを有し、
前記メモリは、複数の生き残りパス算出手段で算出された生き残りパスを一次保持し、前記トレースバック処理手段に前記生き残りパスを出力する、
請求項１に記載のビタビ復号装置。
【請求項１２】
テイルバイティングが適用され且つ情報長がＮの符号化信号列に対して、第１の開始点からＡＣＳ演算することにより生き残りパスを算出する第１の生き残りパス算出ステップと、
前記符号化信号列に対して、前記第１の開始点と異なる第２の開始点からＡＣＳ演算することにより生き残りパスを算出する第２の生き残りパス算出ステップと、
前記第１の生き残りパス算出ステップ及び第２の生き残りパス算出ステップで算出された生き残りパスに基づいて、トレースバック処理を行うトレースバック処理ステップと、
を具備するビタビ復号方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ビタビ復号装置及びビタビ復号方法に関する。
【背景技術】
【０００２】
情報信号が伝搬路を介して送信機から受信機へ伝送されるとき、情報信号は、伝搬路の歪み、雑音などの影響により、受信側に誤った情報として伝わることがある。
【０００３】
このような誤りを低減するために、送信機では符号化処理が行われ、受信機では復号化処理が行われる。特に、畳み込み符号は、比較的簡易に処理可能な、且つ、効果的に誤り訂正可能な符号として知られている。
【０００４】
図９は、畳み込み符号器の一構成例を示す図である。図９に示される畳み込み符号器の拘束長Ｋは７であり、この畳み込み符号器の状態は２Ｋ−１＝２６通りの遷移状態を取り得る。
【０００５】
ここで、情報信号列を所定数のビットからなる複数の符号化ブロックに分割し、符号化ブロック毎に伝送する方法として、「ターミネイション（Termination）」と、「テイルバイティング（Tail-biting）」という方法が知られている。
【０００６】
ターミネイションでは、符号器の初期状態を既知（一般には、Ｋ−１個のゼロ値信号からなる信号列）とする。これは、符号器に入力される上記符号化ブロックの先頭に既知信号が付加されることと等価である。また、符号器に入力される上記符号化ブロックの末尾に、既知の信号（一般には、Ｋ−１個のゼロ値信号からなる信号列）が付加される。これにより、符号器に入力された符号化ブロックの符号化処理が終了した時点における、符号器の状態は、一意に決まる。従って、復号器で上記既知信号を予め知っていれば、復号器は、受信信号に含まれる符号化ブロックに対応する初期状態並びに終了状態を認識することができる。
【０００７】
一方、テイルバイティングは、符号器が有する複数のレジスタの初期値で構成される系列と、符号化ブロックの末尾に付加されるＫ−１個の系列とを同系列にする。これにより、符号器の初期状態と終了状態が同一状態となる。しかしながら、ターミネイションと異なり、初期状態（終了状態）が常に一定ではないので、復号器は、初期状態（終了状態）がどのような状態になるのか予測できない。
【０００８】
ここで畳み込み符号器の状態遷移は、トレリス線図と呼ばれる。テイルバイティングの場合、トレリス線図は、符号器の初期状態と終了状態が同一状態となるため、図１０に示されるように巡回していると考えることができる。
【０００９】
以上に示されるような畳み込み符号に対する準最適な最尤復号として、ビタビ（Viterbi）アルゴリズムが広く知られている。
【００１０】
以下、このビタビアルゴリズムについて説明する。なお、符号器の状態をＳ０，Ｓ１，…，ＳＬ−１とする。そしてトレリス線図において、時点ｔの状態Ｓｉ（ｉ＝０，…，Ｍ−１）から時点ｔ＋１の状態Ｓｊ（ｊ＝０，…，Ｌ−１）への枝（ブランチ）が存在するとき、この枝をｂｉｊと表す。またトレリス線図の各時点において、それぞれの状態と結ばれたパスであって残されたパスを、生き残りパスと呼ぶ。そして時点ｔにおける状態Ｓｉの生き残りパスをｐｉ，ｔで表し、生き残りパスのメトリックをλｉ，ｔで表す。
【００１１】
このときビタビアルゴリズムの基本操作は次のように表される。
【００１２】
（１)トレリス線図において、時点ｔの状態Ｓｉから時点ｔ＋１の状態Ｓｊへの枝ｂｉｊの全てについて、受信系列ｙｔに対する枝メトリックλ（ｙｔ，ｂｉｊ）を計算する。
（２）全ての枝ｂｉｊについて、枝ｂｉｊの枝メトリックλ（ｙｔ，ｂｉｊ）と、枝ｂｉｊと繋がっている時点ｔの状態Ｓｉの生き残りパスｐｉ，ｔに係るメトリックλｉ，ｔとを加算する。
（３）時点ｔ＋１の状態Ｓｊに繋がる全てのパスに関する（２）で求めた和を比較し、その和が最小値となる、生き残りパスｐｉ，ｔと枝ｂｉｊの組を求める。そして、ｐｉ，ｔとｂｉｊを繋いだパスが、Ｓｊの生き残りパスｐｊ，ｔ＋１となる。そして、Ｓｊの生き残りパスｐｊ，ｔ＋１の生き残りパスメトリックλｊ，ｔ＋１が、λｉ，ｔ＋λ（ｙｔ，ｂｉｊ）で求められる。以上の（３）の処理は、時点ｔ＋１の状態Ｓｊの全てについて行われる。
【００１３】
なお、上記した（２）の加算、（３）のメトリックの比較および最小値を与えるパスの選択に係る演算を、ＡＣＳ（Add Compare Select）演算と呼ぶ。
【００１４】
次に、ＡＣＳ演算が終了すると、生き残りパスを逆に辿ることにより、復号結果が求められる。この生き残りパスを辿る処理をトレースバックと呼ぶ。
【００１５】
ここで一般に、ターミネイションで伝送される符号語とテイルバイティングで伝送される符号語とでは、前者よりも後者の方が受信側での演算量、処理時間が大きくなる。これは、上述したようにテイルバイティングでは復号器が初期状態（終了状態）を予測できないことに起因する。
【００１６】
そのため、テイルバイティング方法が採用される場合の、復号器の処理量を減らすことが望まれる。
【００１７】
次に、テイルバイティングで伝送される畳み込み符号語に対する、従来の復号方法について説明する。
【００１８】
非特許文献１では、図１１に示される復号処理が行われる。すなわち、受信パケットである符号化ブロック０（図中のTB Block 0）について、ＡＣＳ演算によるトレリス線図の構築を複数回（図中では３回）繰り返し行う。このように受信パケットに対するＡＣＳ演算を連続的に繰り返して行うのは、符号器の初期状態と終了状態とが同一であるというテイルバイティングの特徴を利用している。
【００１９】
そして、複数回ＡＣＳ演算を繰り返すことにより得られるトレリス線図に対して、トレースバックを行う。このトレースバックにおいては、トレーニング区間が用意される。トレーニングは、生き残りパスを逆に辿る処理を意味する点でトレースバックと同じであるが、そこで得られる結果が復号結果として用いられない（復号結果として出力されない）点でトレースバックと異なる。
【００２０】
このトレーニング処理の後、トレースバック処理が行われ、その処理結果が復号結果として用いられる（出力される）。
【００２１】
また、非特許文献２、非特許文献３および特許文献１では、図１２に示される処理が行われる。すなわち、受信パケットに対して１回（符号ブロック長１巡）のＡＣＳ演算が行われたタイミングで都度、テイルバイティング確認が行われる。テイルバイティング確認とは、トレースバックと同様に生き残りパスを辿ることにより、初期状態と終了状態が一致するかを確認する処理を意味する。そして、テイルバイティング確認した結果、初期状態と終了状態が一致すればその復号結果を出力し、一致しなければＡＣＳ演算が繰り返し行われる。
【００２２】
こうして従来、ビタビ復号処理では、テイルバイティングが適用される符号器の初期状態と終了状態が等しいという性質を利用するために、受信パケットをＡＣＳ演算の繰り返し単位として、受信パケットの復号処理を行っている。  
【特許文献１】特許第２９２３４３０号,“巡回ビタビ復号器の操作方法”
【非特許文献１】Bill Wilkie and Beth Cowie, ”Viterbi Decoder Block Decoding - Trellis Termination and Tail Biting”, XAPP551 (1.0) February 14, 2005.
【非特許文献２】R. Y. Shao, S. Lin and M. Fossorier, ”Two decoding algorithms for tail biting codes”, IEEE Trans. on Comm., vol.51, no.10, pp.1658-1665, Oct. 2003.
【非特許文献３】R1-073033, Ericsson, ”Complexity and Performance Improvement for Convolutional Coding”, 3GPP TSG-RAN WG1#49bis, Orlando, USA, June25-29, 2007.
【発明の開示】
【発明が解決しようとする課題】
【００２３】
しかしながら、繰り返し処理は、処理遅延の増加に繋がる。そのため、処理遅延の増大は、特に低遅延の通信システムの実現において課題となる。
【００２４】
また、上記した従来技術において、繰り返し処理を行うことなく１回のＡＣＳ演算およびトレースバックで得られる結果を復号結果として用いると、打ち切り誤差（truncation error）により復号系列の両端（先頭部および末尾部）周辺の誤り率が大きくなることが知られている。
【００２５】
本発明は、かかる点に鑑みてなされたものであり、繰り返し処理を最小限にして低遅延処理を実現し、且つ、打切り誤差による復号系列端の復号精度の劣化を低減するビタビ復号装置及びビタビ復号方法を提供することを目的とする。
【課題を解決するための手段】
【００２６】
本発明のビタビ復号装置は、テイルバイティングが適用され且つ情報長がＮの符号化信号列に対して、トレリス線図上の互いに異なる開始点からＡＣＳ演算することにより生き残りパスを算出する複数の生き残りパス算出手段と、前記複数の生き残りパス算出手段で算出された生き残りパスに基づいて、トレースバック処理を行うトレースバック処理手段と、を具備する構成を採る。
【００２７】
本発明のビタビ復号方法は、テイルバイティングが適用され且つ情報長がＮの符号化信号列に対して、第１の開始点からＡＣＳ演算することにより生き残りパスを算出する第１の生き残りパス算出ステップと、前記符号化信号列に対して、前記第１の開始点と異なる第２の開始点からＡＣＳ演算することにより生き残りパスを算出する第２の生き残りパス算出ステップと、前記第１の生き残りパス算出ステップ及び第２の生き残りパス算出ステップで算出された生き残りパスに基づいて、トレースバック処理を行うトレースバック処理ステップと、を具備する。
【発明の効果】
【００２８】
本発明によれば、繰り返し処理を行わないことで低遅延処理を実現し、且つ、打切り誤差による復号系列端の復号精度の劣化を低減するビタビ復号装置及びビタビ復号方法を提供することができる。
【発明を実施するための最良の形態】
【００２９】
本発明者は、テイルバイティングが適用された符号器の遷移状態が巡回しているため、その符号器で得られる符号語に対する復号は、トレリス線図の任意の時点から開始できることに先ず着目した。
【００３０】
そして、一般に、テイルバイティングが適用された符号器で得られる符号語を、符号ブロック長１巡のＡＣＳ演算およびトレース処理で復号結果を得る場合、復号系列の端部における誤り率が大きくなり、これに起因して平均誤り率も低下する。
【００３１】
すなわち、本発明者は、復号系列の端部で誤り率が大きくなることが、トレリス線図の開始点と終了点に近いほど誤り易いことを示している事実を見出し、この点に着目して本発明の完成に至った。
【００３２】
以下、本発明の実施の形態について図面を参照して詳細に説明する。なお、実施の形態において、同一の構成要素には同一の符号を付し、その説明は重複するので省略する。
【００３３】
（実施の形態１）
図１に示すように実施の形態１に係る復号装置１００は、生き残りパス算出処理部１１０と、テイルバイティング条件確認処理部１２０と、トレースバック処理部１３０と、生き残りパスメモリ部１７０とを有する。生き残りパス算出処理部１１０は、枝メトリック算出部１４０と、ＡＣＳ演算部１５０と、パスメトリックメモリ部１６０とを有する。復号装置１００は、例えば無線受信装置に搭載され、無線受信装置の無線受信部および復調部で所定の処理（ダウンコンバート、Ａ／Ｄ変換、デマッピング処理など）が施された後の受信信号系列を入力信号とする。
【００３４】
図１において復号装置１００は、互いにトレリス線図におけるＡＣＳ演算の開始点が異なる複数の生き残りパス算出処理部１１０を有する。ここでは説明を簡単にするために、２つの生き残りパス算出処理部１１０−１，２が設けられる場合について説明する。
【００３５】
枝メトリック算出部１４０は、ビタビ符号化されている受信系列が入力される。この受信系列は、符号化ブロック単位で入力される。
【００３６】
枝メトリック算出部１４０は、入力した受信系列を用いて枝メトリックを算出し、算出した枝メトリックをＡＣＳ演算部１５０に出力する。枝メトリック算出部１４０は、枝メトリックの出力先であるＡＣＳ演算部１５０のＡＣＳ演算開始点と一致するポイントから枝メトリックの算出を開始する。
【００３７】
ＡＣＳ演算部１５０は、枝メトリック算出部１４０で算出された枝メトリックを用いてＡＣＳ演算を行う。各時点で得られる生き残りパスのパスメトリックは、パスメトリックメモリ部１６０に一時保持される。ＡＣＳ演算部１５０は、今回の生き残りパスの算出対象である現時点の枝メトリックと、当該時点の１つ前の時点で算出され、パスメトリックメモリ部１６０に保持されているパスメトリックとを用いて、現時点での生き残りパスのパスメトリックを算出する。そしてＡＣＳ演算部１５０は、算出した生き残りパスのパスメトリックをパスメトリックメモリ部１６０に保持させると共に、その生き残りパス及び当該パスに係る情報（つまり、当該パスの枝メトリック及びパスメトリック）を生き残りパスメモリ部１７０に出力する。ここで各時点での生き残りパスの個数は、符号器が取り得る状態数と一致する。
【００３８】
生き残りパスメモリ部１７０は、ＡＣＳ演算部１５０で求められた生き残りパスを保持し、その保持情報をテイルバイティング条件確認処理部１２０に出力する。生き残りパスメモリ部１７０はメモリ１７１−１及びメモリ１７１−２を有し、これらは生き残りパス算出処理部１１０−１及び生き残りパス算出処理部１１０−２とそれぞれ対応している。
【００３９】
テイルバイティング条件確認処理部１２０は、複数の生き残りパス算出処理部１１０で算出された生き残りパスが「テイルバイティング条件」を満たしているか否かを確認する。テイルバイティング条件確認処理部１２０は、例えば、生き残りパス算出処理部１１０で算出された生き残りパスのうち、最大尤度のパスに対してテイルバイティング条件を確認する。
【００４０】
トレースバック処理部１３０は、テイルバイティング条件を満たしている生き残りパスに対してトレースバック処理を行い、得られる処理結果を復号結果として後段の機能部に出力する。
【００４１】
以上の構成を有する復号装置１００の動作について説明する。
【００４２】
生き残りパス算出処理部１１０−１，２は、図２に示すように、互いに異なる開始点からＡＣＳ演算を開始する。図２においては、生き残りパス算出処理部１１０−１はｔ＝０からＡＣＳ演算を開始する一方、生き残りパス算出処理部１１０−２はｔ＝Ｎ／２からＡＣＳ演算を開始する。ここでＮは、トレリス線図長であり、符号化ブロックの情報長と一致する。
【００４３】
図３にトレリス線図を示す。図３には、Ｎ＝８であり、符号装置の取り得る遷移状態が４状態である場合が示されている。
【００４４】
この場合、生き残りパス算出処理部１１０−１はｔ＝０からＡＣＳ演算を開始する一方、生き残りパス算出処理部１１０−２はｔ＝４からＡＣＳ演算を開始する。
【００４５】
テイルバイティング条件確認処理部１２０は、開始点から４時点以上経過した後にテイルバイティング条件確認処理を行う。すなわち、テイルバイティング条件確認処理部１２０は、複数の生き残りパス算出処理部１１０で算出された生き残りパスを合成したときの合成パスが、符号化ブロック全体を網羅する時点で、テイルバイティング条件確認処理を行う。
【００４６】
ここでテイルバイティング条件とは、時点間距離がＮである２つの時点での符号装置の状態が一致し、且つ、合成パスの連結ポイントでの符号装置の状態が一致する条件である。これは、上述したようにテイルバイティングに係るトレリス線図が巡回性を有するからである。すなわち、テイルバイティング条件確認処理部１２０は、合成パスが巡回性を有しているか否かを確認する。
【００４７】
具体的には、テイルバイティング条件確認処理部１２０は、生き残りパス算出処理部１１０−１から、時点ｔ０からｔ４までの生き残りパス（図３で太線で表されているパス）を受け取ると共に、生き残りパス算出処理部１１０−２から、時点ｔ４からｔ８までの生き残りパス（図３で太線で表されているパス）を受け取る。
【００４８】
そしてテイルバイティング条件確認処理部１２０は、符号化ブロックの最初と最後の遷移状態が一致し、且つ、連結ポイントである時点ｔ４での遷移状態が一致するか否かを確認する。ここでは開始点の数Ｍが２で、情報長Ｎが８であるので、テイルバイティング条件確認処理部１２０は、合成パスを構成する複数の生き残りパスに対してＮ／Ｍ分のトレースバック処理を行うことにより、合成パスの巡回性を確認する。
【００４９】
図３に示すようにテイルバイティング条件が満たされている場合、その生き残りパスは、トレースバック処理部１３０に通知される。
【００５０】
そしてトレースバック処理部１３０は、テイルバイティング条件確認処理部１２０でテイルバイティング条件が確認された生き残りパスをトレースバックする。
【００５１】
以上のように本実施の形態によれば、復号装置１００に、互いにＡＣＳ演算の開始点が異なる生き残りパス算出処理部１１０−１，２と、生き残りパス算出処理部１１０−１，２で得られた生き残りパスに基づいてトレースバック処理を行うトレースバック処理部１３０とを設けた。
【００５２】
こうして異なる開始点からＡＣＳ演算を開始することにより得られる生き残りパスは、互いに誤り易い箇所が異なっている。すなわち、これらの生き残りパスは、互いに誤り易い箇所を補完し合う関係を有している。従ってこれらの生き残りパスを用いてトレースバック処理を行うことより、従来のような繰り返し処理を行わなくても、打切り誤差による復号系列端の復号精度の劣化を低減することができる。
【００５３】
さらに復号装置１００には、時点間距離がＮである２つの時点での遷移状態が一致し、且つ、合成パスの連結ポイントでの遷移状態が一致する条件を確認するテイルバイティング条件確認処理部１２０が設けられる。
【００５４】
これにより、テイルバイティング方法が有する特性であるトレリス線図の巡回性を利用して、復号の成否を予測することができる。従って、無駄なトレースバック処理を行うことを防止できる。
【００５５】
ただし、テイルバイティング条件の確認処理は、必ずしも必要ではない。すなわち、上述したように、テイルバイティング条件を確認するまでもなく、誤り易い箇所を補完し合う関係を有する複数の生き残りパスを用いてトレースバックをするだけでも、従来のビタビ復号方法に比べて、復号精度を向上することができる。
【００５６】
またなお、上記説明では、２つの生き残りパス算出処理部１１０が並列に設けられ、互いに異なる開始点からＡＣＳ演算を並列に行う場合について説明したが、本発明はこれに限定されるものではない。３つ以上の生き残りパス算出処理部１１０が、互いに異なる開始点からＡＣＳ演算を行ってもよい。
【００５７】
また、複数の開始点間の距離も特に限定されない。ただし、複数の開始点間の距離が最大になるように、開始点がバランス良く配置されることが好ましい。すなわち、Ｍ個の開始点が用意される場合、開始点間の距離はＮ／Ｍであることが好ましい。こうすることで複数の生き残りパス算出処理部１１０が協働することにより、符号化ブロックのトレリス全体を網羅する合成パスを最短時間で得ることができる。そしてテイルバイティング条件確認処理部１２０は、ＡＣＳ演算開始時点からＮ／Ｍ時点以上Ｎ時点以下経過した任意の時点で、合成パスの巡回性を確認する。
【００５８】
（実施の形態２）
実施の形態２では、トレースバック処理部が、第１の生き残りパス算出処理部で得られた生き残りパスに対してトレーニング処理を行い、このトレーニング結果に基づいて第２の生き残りパス算出処理部で得られた複数の生き残りパスのうちから１つのパスを選択し、当該選択パスについてトレースバック処理を行う。
【００５９】
図４に示すように本実施の形態の復号装置２００は、トレースバック処理部２１０を有する。
【００６０】
トレースバック処理部２１０は、生き残りパス算出処理部１１０−１で得られた生き残りパスの１つに対してトレーニング処理を行い、このトレーニング結果に基づいて生き残りパス算出処理部１１０−２で得られた複数の生き残りパスのうちから１つのパスを選択し、当該選択パスについてトレースバック処理を行う。
【００６１】
逆に、トレースバック処理部２１０は、生き残りパス算出処理部１１０−２で得られた生き残りパスの１つに対してトレーニング処理を行い、このトレーニング結果に基づいて生き残りパス算出処理部１１０−１で得られた複数の生き残りパスのうちから１つのパスを選択し、当該選択パスについてトレースバック処理を行う。ここでトレーニングとは、トレリス線図の生き残りパスを辿って、初期状態を一意に求める処理を意味する。
【００６２】
なお、ここではトレースバック処理部２１０でトレーニング処理に用いられる生き残りパスは、生き残りパス算出処理部１１０−１で得られた複数の生き残りパスのうち任意の１つの生き残りパスが用いられる。生き残りパス算出処理部１１０−２についても同様である。
【００６３】
以上の構成を有する復号装置２００の動作について図３及び図５を参照して説明する。なお図５において、時計回りの細い実線の矢印は、生き残りパス算出処理部１１０−１でのＡＣＳ演算処理を示し、時計回りの細い点線の矢印は、生き残りパス算出処理部１１０−２でのＡＣＳ演算処理を示す。また、反時計回りの太い実線の矢印は、生き残りパス算出処理部１１０−１で得られた生き残りパスに対する、トレーニング処理又はトレースバック処理を示し、反時計回りの太い点線の矢印は、生き残りパス算出処理部１１０−２で得られた生き残りパスに対する、トレーニング処理又はトレースバック処理を示す。
【００６４】
トレースバック処理部２１０は、開始点から４時点以上経過した後にトレーニング処理を行う。すなわち、トレースバック処理部２１０は、複数の生き残りパス算出処理部１１０で算出された生き残りパスを合成したときの合成パスが、符号化ブロック全体を網羅する時点で、トレーニング処理を行う。
【００６５】
トレースバック処理部２１０は、開始点から４時点以上経過した後に、生き残りパス算出処理部１１０−２で得られた、ｔ＝４からｔ＝８までの生き残りパスを用いてトレーニング処理を行う（図５の内側の太い点線矢印に対応）。すなわち、トレースバック処理部２１０は、生き残りパス算出処理部１１０−２で得られた、ｔ＝４からｔ＝８までの生き残りパスのうちの１つを辿ることにより、ｔ＝４時点で最も確からしい遷移状態を一意に決定する。
【００６６】
そして、トレースバック処理部２１０は、開始点から４時点以上経過した後に、生き残りパス算出処理部１１０−１で得られた生き残りパスのうち、上記ｔ＝４時点で一意に決定された遷移状態から始まる生き残りパスに対してトレースバック処理を行う（図５の内側の太い実線矢印に対応）。
【００６７】
トレースバック処理部２１０は、生き残りパス算出処理部１１０−２で得られた生き残りパスについても、生き残りパス算出処理部１１０−１で得られた生き残りパスに対するトレーニング結果を用いて、最も確からしい生き残りパスを選択し、当該選択パスに対してトレースバック処理を行う。
【００６８】
こうして符号化ブロック全体に係るトレースバック結果が得られ、当該結果は、復号結果として後段の機能部に出力される。
【００６９】
なお以上の説明においては、２つの生き残りパス算出処理部１１０が並列に設けられ、互いに異なる開始点からＡＣＳ演算を行う場合について説明したが、本発明はこれに限定されるものではない。３つ以上の生き残りパス算出処理部１１０が、互いに異なる開始点からＡＣＳ演算を行ってもよい。
【００７０】
この場合、トレースバック処理部２１０は、トレーニング処理に用いる生き残りパスを、複数の生き残りパス算出処理部１１０で得られた生き残りパスの中から選択する必要がある。このとき、トレースバック処理部２１０は、トレーニング長が最長となる生き残りパスをトレーニング処理に用いる。トレーニング長が長い程、一意に決定される遷移状態の確からしさが向上するためである。
【００７１】
以上のように本実施の形態によれば、トレースバック処理部２１０が、第１の生き残りパス算出処理部１１０で得られた生き残りパスの１つに対してトレーニング処理を行い、このトレーニング結果に基づいて第２の生き残りパス算出処理部１１０で得られた複数の生き残りパスのうちから１つのパスを選択し、当該選択パスについてトレースバック処理を行う。
【００７２】
こうしてトレーニング処理を導入することにより、復号精度を向上することができる。さらに、ＡＣＳ演算の開始点の異なる生き残りパスのうち、或る生き残りパスのトレースバック処理に、他の生き残りパスに対するトレーニング結果を用いるので、復号精度をより向上することができる。
【００７３】
また、第１の生き残りパス算出処理部１１０は、第２の生き残りパス算出処理部１１０以外の生き残りパス算出処理部１１０のうち、最大のトレーニング長を有している。
【００７４】
なお、上記説明においては、トレースバック処理部２１０でトレーニング処理に用いられる生き残りパスが、生き残りパス算出処理部１１０−１（生き残りパス算出処理部１１０−２）で得られた複数の生き残りパスのうち任意の１つの生き残りパスが用いられる。しかしながら、本発明はこれに限定されるものではなく、生き残りパス算出処理部１１０−１（生き残りパス算出処理部１１０−２）で得られた複数の生き残りパスのうち最大の尤度を持つ１つのパスをトレーニング処理に用いてもよい。
【００７５】
こうすることで、トレースバックを開始する時点での遷移状態の確からしさをより向上することができる。
【００７６】
図６は、最大の尤度を持つ１つのパスをトレーニング処理に用いる場合の、復号装置の構成を示すブロック図である。
【００７７】
図６に示すように復号装置３００は、最大尤度パス検出部３１０を有する。
【００７８】
最大尤度パス検出部３１０は、生き残りパス算出処理部１１０−１（生き残りパス算出処理部１１０−２）で得られた複数の生き残りパスのうち最大の尤度を持つ１つのパスを検出し、当該検出パスをトレースバック処理部２１０に出力する。
【００７９】
トレースバック処理部２１０は、生き残りパス算出処理部１１０−１（生き残りパス算出処理部１１０−２）で得られた複数の生き残りパスのうち最大尤度の１つの生き残りパスに対してトレーニング処理を行い、このトレーニング結果に基づいて生き残りパス算出処理部１１０−２（生き残りパス算出処理部１１０−１）で得られた複数の生き残りパスのうちから１つのパスを選択し、当該選択パスについてトレースバック処理を行う。
【００８０】
なお、上記した３つ以上の生き残りパス算出処理部１１０が互いに異なる開始点からＡＣＳ演算を行う場合には、トレーニング処理に用いられる、生き残りパス算出処理部１１０で得られた複数の生き残りパスのうち、最大尤度の１つの生き残りパスに対してトレーニング処理を行えばよい。
【００８１】
（他の実施の形態）
（１）実施の形態１では１つの生き残りパス算出処理部１１０に対して１つのメモリ１７１が設けられている場合について説明を行った。しかしながら、本発明はこれに限定されるものではなく、図７に示すように複数の生き残りパス算出処理部１１０で１つのメモリ１７１を共有してもよい。
【００８２】
ここで本実施の形態の復号装置１００において、各生き残りパス算出処理部１１０はテイルバイティングの巡回性に関する１巡未満の部分的な生き残りパスを出力し、その各生き残りパス算出処理部１１０から出力された部分的な生き残りパスの長さの合計は、高々Ｎである。
【００８３】
このように各生き残りパス算出処理部１１０が１巡全体ではなく部分的な生き残りパスを生き残りパスメモリ部１７０に出力するので、複数の生き残りパス算出処理部１１０で１つのメモリ１７１を共有することができる。
【００８４】
（２）実施の形態１では、部分的な生き残りパスとして、生き残りパス算出処理部１１０は、ＡＣＳ演算の開始点からＮ／Ｍ時点までの部分的な生き残りパスを出力するものとして説明を行った。しかしながら、本発明はこれに限定されるものではなく、生き残りパス算出処理部１１０が、ＡＣＳ演算の開始点から所定の時点までの先頭部を除いた生き残りパスのみを出力するようにしてもよい。こうすることにより、誤り率が最も高い、トレリス線図の開始点付近の先頭部を除くことができるので、より信頼性の高い生き残りパスを得ることができる。
【００８５】
図１を用いて説明すると、ＡＣＳ演算部１５０−１，２は、ＡＣＳ演算の開始点からＮ／２までの前半部を除き、Ｎ／２からＮまでの後半部の生き残りパスをそれぞれ出力する（図８参照）。図８において点線部分は、ＡＣＳ演算部１５０で破棄される部分であり、実線部分は、ＡＣＳ演算部１５０から出力される生き残りパスである。
【００８６】
すなわち、Ｍ個の開始点が用意され、且つ、開始点間の距離がＮ／Ｍである場合、Ｍ個のＡＣＳ演算部１５０は、ＡＣＳ演算の開始点からＮ／Ｍまでの初期部を除き、当該初期部に続く、Ｎ／Ｍから２Ｎ／Ｍまでの生き残りパスをそれぞれ出力する。
【００８７】
この場合にも、上記した他の実施の形態（１）と同様に、メモリの共有化を図ることができることは言うまでもない。
【産業上の利用可能性】
【００８８】
本発明のビタビ復号装置及びビタビ復号方法は、繰り返し処理を行わないことで低遅延処理を実現し、且つ、打切り誤差による復号系列端の復号精度の劣化を低減するものとして有用である。
【図面の簡単な説明】
【００８９】
【図１】本発明の実施の形態１に係る復号装置の構成を示すブロック図
【図２】図１に示される２つの生き残りパス算出処理部のＡＧＳ演算の開始点の説明に供する図
【図３】図１の復号装置に係るトレリス線図を示す図
【図４】実施の形態２に係る復号装置の構成を示すブロック図
【図５】図４の復号装置の動作説明に供する図
【図６】実施の形態２に係る復号装置の他の構成を示すブロック図
【図７】他の実施の形態（１）に係る復号装置の構成を示すブロック図
【図８】他の実施の形態（２）の生き残りパス算出処理部の処理説明に供する図
【図９】従来の畳み込み符号器の一構成例を示す図
【図１０】テイルバイティングが適用される場合の、畳み込み符号器のトレリス線図を示す図
【図１１】テイルバイティングで伝送される畳み込み符号語に対する、従来の復号方法の説明に供する図
【図１２】テイルバイティングで伝送される畳み込み符号語に対する、従来の復号方法の説明に供する図
【符号の説明】
【００９０】
１００，２００，３００  復号装置
１１０  生き残りパス算出処理部
１２０  テイルバイティング条件確認処理部
１３０，２１０  トレースバック処理部
１４０  枝メトリック算出部
１５０  ＡＣＳ演算部
１６０  パスメトリックメモリ部
１７０  生き残りパスメモリ部
３１０  最大尤度パス検出部
【図１】
2010041569.tif 000003
【図２】
2010041569.tif 000004
【図３】
2010041569.tif 000005
【図４】
2010041569.tif 000006
【図５】
2010041569.tif 000007
【図６】
2010041569.tif 000008
【図７】
2010041569.tif 000009
【図８】
2010041569.tif 000010
【図９】
2010041569.tif 000011
【図１０】
2010041569.tif 000012
【図１１】
2010041569.tif 000013
【図１２】
2010041569.tif 000014