(57)【要約】【課題】メモリを増大することなく、誤り訂正能力を向上したビタビ復号方法を提供すること。【解決手段】本発明にかかるビタビ復号方法は、トレリス線図上で第１の復号パスＰ１を求め、第１の復号パスＰ１を使用して復号データを求めて誤り検出をし、誤り検出の結果、第１の復号データに誤りがある場合は、トレリス線図の第１の復号パスＰ１において最終時点の状態として選択された第１の状態へ至るブランチを、第１の復号パスＰ１において第１の状態へ至るブランチとして選択されたブランチとは別のブランチに変更してトレースバックを行なって第２の復号パスＰ２を求め、第２の復号パスＰ２を使用して再度復号データを得る。【選択図】図１５
2008118327.tif 000002
【特許請求の範囲】
【請求項１】
トレリス線図上で第１の復号パスを求め、
前記第１の復号パスを使用して復号データを求めて誤り検出をし、
前記誤り検出の結果、前記第１の復号データに誤りがある場合は、前記トレリス線図の前記第１の復号パスにおいて最終時点の状態として選択された第１の状態へ至るブランチを、前記第１の復号パスにおいて前記第１の状態へ至るブランチとして選択されたブランチとは別のブランチに変更してトレースバックを行ない第２の復号パスを求め、
前記第２の復号パスを使用して再度復号データを得るビタビ復号方法。
【請求項２】
前記第２の復号パスの復号データに誤りが検出された場合は、前記第１の復号パスにおける前記第１の状態から一ブランチトレースバックした第２の状態へ至るブランチを、前記第１の復号パスにおいて前記第２の状態へ至るブランチとして選択されたブランチとは別のブランチに変更してトレースバックを行ない第３の復号パスを求め、
前記第３の復号パスを使用して再度復号データを得る、
ことを特徴とする請求項１記載のビタビ復号方法。
【請求項３】
第Ｎ（Ｎは２以上の整数）の復号パスの復号データに誤りが検出された場合は、前記第１の復号パスにおける前記第１の状態から（Ｎ−１）状態トレースバックした状態へ至るブランチを、前記第１の復号パスにおいて当該状態へ至るブランチとして選択されたブランチとは別のブランチに変更してトレースバックを行ない第（Ｎ＋１）の復号パスを求め、
前記第（Ｎ＋１）の復号パスを使用して再度復号データを得る、
ことを特徴とする請求項１記載のビタビ復号方法。
【請求項４】
前記復号パスの誤りが検出されなくなるまで復号パスを変更して復号データを得る
ことを特徴とする請求項１乃至３のいずれか１項記載のビタビ復号方法。
【請求項５】
所定の回数、前記復号パスを変更して復号データを得る
ことを特徴とする請求項１乃至３のいずれか１項記載のビタビ復号方法。
【請求項６】
前記第１の状態は、前記最終時点の各状態のうち、尤度が最も高い状態である
ことを特徴とする請求項１乃至５のいずれか１項記載のビタビ復号方法。
【請求項７】
前記第１の状態は、符号化器への入力データの最後に終端ビットを挿入することによりトレリス終結した状態である
ことを特徴とする請求項１乃至５のいずれか１項記載のビタビ復号方法。
【請求項８】
前記トレリス線図上の各時点の各状態へ至るブランチのうち、いずれのブランチが選択されたかをビット情報としてメモリに記憶しておき、ブランチの変更は前記ビット情報の論理を反転させることにより行なう
ことを特徴とする請求項１に記載の復号方法。
【請求項９】
トレリス線図上の最終時点におけるもっとも尤度が高い状態からトレースバックを行い第１の復号パスを求め、
前記第１の復号パスを使用して復号データを求めて誤り検出をし、
前記誤り検出の結果、前記第１の復号データに誤りがある場合は、前記最終時点で２番目に尤度が高い状態からトレースバックした第２の復号パスを求め、
前記第２の復号パスを使用して再度復号データを得るビタビ復号方法。
【請求項１０】
前記第２の復号パスの復号データに誤りが検出された場合は、前記最終時点における３番目に尤度が高い状態からトレースバックした第３の復号パスを求め、
前記第３の復号パスを使用して再度復号データを得る、
ことを特徴とする請求項９記載のビタビ復号方法。
【請求項１１】
第Ｎ（Ｎは２以上の整数）の復号パスの復号データに誤りが検出された場合は、前記トレリス線図における最終時点において（Ｎ＋１）番目に尤度が高い状態からトレースバックした第（Ｎ＋１）の復号パスを求め、
前記第（Ｎ＋１）の復号パスを使用して再度復号データを得る、
ことを特徴とする請求項９又は１０項記載のビタビ復号方法。
【請求項１２】
トレリス線図上の第１時点における第１の状態からトレースバックして求めた第１の復号パスから得た復号結果が誤りである場合、前記第１の復号パスにおける前記第１時点での前記第１の状態へ至るブランチを、前記第１の復号パスにおいて前記第１の状態へ至るブランチとして選択されたブランチとは別のブランチに変更し、
前記第１状態から再度トレースバックして第２の復号パスを求め復号を行う復号方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、Ｗ−ＣＤＭＡ（Wideband Code Division Multiple Access）通信などに使用される誤り訂正符号のビタビ復号方法に関する。
【背景技術】
【０００２】
ビタビ復号は畳み込み符号に対する復号法であり、最も一般的な誤り訂正方法の一つとして知られている。ビタビ復号は最尤復号法であり、尤もらしい状態の遷移を辿ること(トレースバック)で復号結果を得る。復号結果が正しいかどうかの判定はＣＲＣ（Cyclic Redundancy Check）などの誤り検出方法を用い、誤りであればデータの再送を要求する。
【０００３】
このようなビタビ復号の誤り訂正能力を向上させる従来技術として特許文献１がある。この特許文献１に記載のビタビ復号装置１０１は、図２８に示すように、メトリック計算回路１０２、ＡＣＳ（Add Compare Select）回路１０３、パスセレクト記憶回路１０４、パスメトリック記憶回路１０５、マルチトレースバック回路１０６、スタックメモリ１０７を有する。このビタビ復号装置１０１では、受信データ列からメトリック計算回路１０２において、各部分パス（ブランチ）の尤度（メトリック）を計算する。
【０００４】
次に、ＡＣＳ回路１０３において、各時刻の各状態に遷移する複数のパスのメトリックを比較して、パスセレクト記憶回路１０４に、メトリックの最も高いパスを選択してそのパスセレクト信号を記憶するだけでなく、他のパスとのメトリック差をも同時に記憶する。また、通常のビタビ復号と同様に、パスメトリック記憶回路１０５において、パスメトリックの記憶・更新も行なうものとする。そして、パスセレクト記憶回路１０４の情報を基に、マルチトレースバック回路１０６およびスタックメモリ１０７によって、トレースバックを行なう。この場合、与えられる許容メトリック差によっては、生き残りパスがただ１個となるとは限らず、複数回のトレースバックにより、複数個のパスが生き残ることになる。
【０００５】
この復号装置１０１の動作について説明する。図２９、図３０は、特許文献１に記載の復号方法を示すフローチャートである。図２９に示すように、最初に、初期化処理において、スタックメモリ、スタックメモリアドレス、許容メトリック差、トレースバック（ＴＢ）ブランチ数カウンタ、ＴＢカウンタ、および状態の初期化を行なう（ステップＳ１１０）。そして、時刻ｔｎを初期化し（ステップＳ１１１）、以後トレースバック処理を行なう。その状態におけるパスセレクト信号およびメトリック差をパスセレクト記憶回路から読み出し（ステップＳ１１２）、許容セレクト差と比較し（ステップＳ１１３）、メトリック差が許容メトリック差以下であれば、スタックメモリに記憶し（ステップＳ１１４）、アドレスの更新を行なう（ステップＳ１１５）。
【０００６】
そして、１時刻前の状態の計算（ステップＳ１１６）と、復号データの計算・格納（ステップＳ１１７）をした上で、時刻の変更（ステップＳ１１８）をして、さらにさかのぼるかの判断（ステップＳ１１９）を行なう。ここで１回のトレースバックが終了したと判断されると、スタックメモリに情報が記憶されているかをみて（ステップＳ１２０）、記憶されていない場合は終了し（ステップＳ１２９）、また、記憶されている場合は、図３０に示すように、最上位アドレス（最後に記憶したアドレス）の１情報の分岐フラグを判断し（ステップＳ１２１）、"１"であれば最上位アドレスの１情報を消去、アドレスを１減らして（ステップＳ１３０）、再びステップＳ１２０へ戻る。一方、分岐フラグが"０"の場合は、その１情報のその他のパラメータを読み出し、残りメトリック値を許容メトリック差として（ステップＳ１２２）、分岐フラグは０から１に変換した上で、その更新された１情報を再びスタックメモリに記憶しておく（ステップＳ１２３）。
【０００７】
そして、トレースバック（ＴＢ）されるブランチ数の累積値を計算し（ステップＳ１２４）、制限数以下であれば、ＴＢカウンタを増やし（ステップＳ１２６）、分岐点までの復号データは１つ前の復号データからコピーし（ステップＳ１２７）、さらにその分岐点の状態におけるパスセレクト信号を反転された（ステップＳ１２８）上で、ステップＳ１１６に戻ってトレースバックを行なう。一方、制限数を超える場合は、処理が足りないと判断して、復号処理を終了（ステップＳ１２９）する。
【０００８】
すなわち、このビタビ復号装置１０１においては、ＡＣＳ演算において各状態で生き残りパスの選択をする際に、最も尤度の高いパスを一つだけ選択してそのパスセレクト信号を記憶するだけでなく、最も尤度の高いパスとその他のパスとの尤度差も合わせて記憶しておく。そして、トレースバックにより復号データを求める際に、最尤度復号パスだけでなく、最尤パスのトレースバック区間での尤度との間で、あらかじめ設定したしきい値である許容メトリック差以下の尤度となるパスについて、それぞれトレースバックを行なって複数の復号パス候補を得るマルチトレースバックを行なう。
【０００９】
そしてマルチトレースバックを行なう際に、複数の候補を再帰法により検索し、このときトレースバックによりさかのぼる各状態において、許容メトリック差とその状態で記憶しておいた尤度差とを比較する。尤度差が許容メトリック差以下の場合には、複数のブランチを選択できる状態であるとして、その状態の時刻と状態とどのブランチを選択してトレースバックを行なっているかを示す分岐フラグと、許容メトリック差から尤度差を引いた値とをスタックメモリに記憶しておく。
【００１０】
再帰法により復号する際に、次のトレースバックでは、１つ前のトレースバックにより通過したパスの復号データの内、共通の部分パスの復号結果をコピーして用い、異なる部分パスは、スタックメモリに記憶された時刻および状態から新たに分岐し、その分岐点におけるパスセレクト信号のみを反転させてトレースバックを行なうことにより、残りの部分パスの復号データを得るようにしたので、ビタビ復号において複数のパスを生き残りとし複数の復号データ候補を求める際に、処理時間を縮小できる。このように、状態毎に尤度の高い複数の生き残りパスを保存して、トレースバックを複数回行うことにより、正しく復号される可能性を高める。
【特許文献１】特開平７−２８８４７８号公報
【発明の開示】
【発明が解決しようとする課題】
【００１１】
しかしながら、この特許文献１に記載の方法においては、尤度差がある閾値以下のパスを複数保存し、これらの複数のパスについての復号結果を全て保存しなければならず、さらに、どの時点（時刻）のどの状態のパスの尤度差がいくつであったか保存しなければならないため、通常のビタビ復号装置に比して対して復号データを保存するメモリが大量に必要になるという問題点がある。
【課題を解決するための手段】
【００１２】
本発明にかかるビタビ復号方法は、トレリス線図上で第１の復号パスを求め、前記第１の復号パスを使用して復号データを求めて誤り検出をし、前記誤り検出の結果、前記第１の復号データに誤りがある場合は、前記トレリス線図の前記第１の復号パスにおいて最終時点の状態として選択された第１の状態へ至るブランチを、前記第１の復号パスにおいて前記第１の状態へ至るブランチとして選択されたブランチとは別のブランチに変更してトレースバックを行ない第２の復号パスを求め、前記第２の復号パスを使用して再度復号データを得るものである。
【００１３】
本発明にかかる他のビタビ復号方法は、トレリス線図上の最終時点におけるもっとも尤度が高い状態からトレースバックを行い第１の復号パスを求め、前記第１の復号パスを使用して復号データを求めて誤り検出をし、前記誤り検出の結果、前記第１の復号データに誤りがある場合は、前記最終時点で２番目に尤度が高い状態からトレースバックした第２の復号パスを求め、前記第２の復号パスを使用して再度復号データを得るものである。
【００１４】
本発明においては、第１の復号パスで誤りが検出された場合、通常のビタビ復号でメモリに記憶されているデータのみを使用して第２の復号パスを選択することができる。そして、この第２の復号パスの復号データを復号データとすることができ、第１の復号データに誤りが検出されると復号を中止する従来に比して、誤り訂正能力が向上する。
【発明の効果】
【００１５】
本発明によれば、メモリを増大することなく、誤り訂正能力を向上したビタビ復号方法を提供することができる。
【発明を実施するための最良の形態】
【００１６】
以下、本発明を適用した具体的な実施の形態について、図面を参照しながら詳細に説明する。一般的にビタビ復号法は、最尤復号法であり、尤もらしい状態の遷移を辿ること(トレースバック)で復号結果を得る。復号結果が正しいかどうかの判定はＣＲＣなどの誤り検出方法を用い、誤りであればデータの再送を要求する。これに対し、本実施の形態においてはビタビ復号において誤り判定された場合、遷移を変えて再びトレースバックを行うことで、復号結果の再取得を行う。これを誤り判定がＯＫとなるか、規定回数に達するまで繰り返す。そうすることで復号できる可能性を高めることが可能となる。更に、本実施の形態においては、特別なメモリは必要なく、またロジックの増加も軽微に留めることができる。
【００１７】
先ず、本発明の理解を容易とするため、ビタビアルゴリズムについて簡単に説明する。まず、畳み込み符号化について説明する。ビタビアルゴリズムは復号アルゴリズムなので入力データは符号化されている必要がある。その符号化の方法として畳み込み符号（Convolutional Coding）が使用されている。図１に畳み込み符号化器を示す。
【００１８】
図１に示す畳み込み符号化器２０は、２つのレジスタ２１、２２と、３つの排他的論理和を求める論理回路２３〜２５とを有する。この符号化器２０の拘束長は３（レジスタ数＋１）である。符号化器２０は、１ｂｉｔの入力（Ｉｎｐｕｔ）に対し、２ｂｉｔの出力"Ｏｕｔｐｕｔ０，Ｏｕｔｐｕｔ１"を得るので符号化率は１／２である。
【００１９】
ここで、拘束長とは、出力を得るのに必要な、過去の入力ビット数を表す。拘束長を大きくすれば誤り訂正能力は高くなるが、ビタビ復号装置の構成は複雑になる。符号化率とは符号器への入力ビットと出力ビットの比率を示す。符号化率が小さい、つまり入力に対して出力のビット数が多い場合は、伝送速度が落ちるが誤り訂正能力は高くなる。
【００２０】
ここでは、下記表１に示すデータを入力した場合について説明する。図１に示した畳み込み符号化器２０への入力データと、この畳み込み符号化器２０からの出力データを表１に、畳み込み符号化器の状態遷移を図２に示す。
【表１】
2008118327.tif 000003
【００２１】
ここで、レジスタ２１、２２のスタート時の初期値は"０"とし、よって初期状態は（Ｄ０，Ｄ１）＝（０，０）となっている。この状態で、例えばＩｎｐｕｔから"１"を入力した場合、出力は"Ｏｕｔｐｕｔ０，Ｏｕｔｐｕｔ１"＝"１，１"となり、次の時点でレジスタ２１、２２の状態は、（Ｄ０，Ｄ１）＝（１，０）となる。一方、Ｉｎｐｕｔから"０"を入力した場合、出力は"Ｏｕｔｐｕｔ０，Ｏｕｔｐｕｔ１"＝"０，０"となり、次の時点でレジスタ２１、２２の状態は、（Ｄ０，Ｄ１）＝（０，０）となる。図２において、矢印の上に示す数値が"Ｏｕｔｐｕｔ０，Ｏｕｔｐｕｔ１"である。Ｉｎｐｕｔは"０"又は"１"であるので、一の状態からは２種類の状態にのみ変化する。よって、一の状態からは２本の矢印が出力される。上記表１に示す値（Ｉｎｐｕｔ）を入力することにより、図３に示すように、状態（Ｄ０，Ｄ１）は、（０，０）→（１，０）→（０，１）→（０，０）→（１，０）→（１，１）と変化し、得られた結果（Ｏｕｔｐｕｔ０，Ｏｕｔｐｕｔ１）は"１１１０１１１１０１"となる。
【００２２】
図１に示した畳み込み符号化器２０が表１に示す出力データを出力し、その出力データがビタビ復号装置へ入力された場合のトレリス線図を図４に示す。このトレリス線図の各時点における各状態は、図１に示した畳み込み符号化器のレジスタ２１及びレジスタ２２の各時点における各状態（Ｄ０，Ｄ１）に対応している。トレリス線図における各時点における各状態の各々から次時点の方向に向かって出ている２本の矢印はブランチといい、ある時点のある状態がとりうる次時点への二つの状態遷移を示している。図１の畳み込み符号化器２０への入力は"１"か"０"のどちらかであるので、図４のトレリス線図の一の時点における一の状態から次時点におけるいずれかの状態への遷移は２通りになる。
【００２３】
例えば時点ｔ＝０において図１の畳み込み符号化器２０に１ビットの"０"が入力された場合には、図４のトレリス線図の時点ｔ＝０における状態（Ｄ０，Ｄ１）＝（０，０）は、時点ｔ＝１において状態（Ｄ０，Ｄ１）＝（０，０）へ遷移する。一方、時点ｔ＝０において図１の畳み込み符号化器２０に１ビットの"１"が入力された場合には、図４のトレリス線図の時点ｔ＝０における状態（Ｄ０，Ｄ１）＝（０，０）は、時点ｔ＝１において状態（Ｄ０，Ｄ１）＝（１，０）へ遷移する。トレリス線図上の各ブランチに記載された数値は、一の時点から次時点への各状態遷移が生じる際に、図１に示す畳み込み符号化器２０が出力するデータを表している。これを符号語という。先に示した例では、時点ｔ＝０における状態（Ｄ０，Ｄ１）＝（０，０）から状態（Ｄ０，Ｄ１）＝（１，０）への状態遷移が生じる際に、畳み込み符号化器２０からは（Ｏｕｔｐｕｔ０、Ｏｕｔｐｕｔ１）＝（１，１）が出力されていることになる。また図４におけるビタビ復号装置への入力とは、一の時点から次時点に状態遷移が生じたときのビタビ復号装置に対する入力データである。これを受信語という。
【００２４】
トレリス線図上の初期時点におけるある状態から、その初期時点以降の時点のある状態に至るまでの状態遷移の道筋をパスという。トレリス線図上の初期時点から最終時点までの一のパスを決定すると、一の復号結果が得られる。なぜなら、トレリス線図上で初期時点から最終時点までのパスを決定すれば、そのパスを構成する各時点でのブランチが決定し、そのパスを構成する各ブランチによって初期時点から最終時点までの各時点における符号語が決定できるからである。初期時点から最終時点までの各時点の符号語が決定できれば、符号化器の状態遷移から符号化器に対する各時点の入力データが決定できるので、復号結果が得られることになる。決定したパスが受信語に対して正しければ復号結果も正しく、決定したパスが受信語に対して誤りであれば復号結果も誤りとなる。従って、ビタビ復号では受信語に対する正しいパスを定める必要がある。ビタビ復号では受信語に対する正しいパスを決定するために、トレリス線図上の初期時点からその初期時点以降の時点における状態に至る各々のパスの尤度を評価する。パスの尤度を評価するためにはまず、各時点における受信語に対するそれぞれの状態遷移の尤度が必要となる。パスはブランチのつながりだからである。
【００２５】
トレリス線図上の一の時点における一の状態からその一の時点の次時点における一の状態への遷移の尤もらしさをブランチメトリックという。ブランチメトリックはトレリス線図上の各ブランチにおける符号語と、その各ブランチに対応した受信語とに基づき計算される。硬判定と軟判定ではブランチメトリックの求め方が異なるが、例えば硬判定ではトレリス線図上の各ブランチに対応した符号語と、その各ブランチに対応した受信語とのハミング距離を用いる。ハミング距離とは２つのビット列の相違なビット数のことである。従って、ハミング距離をブランチメトリックに用いた場合、そのブランチメトリックの値が小さいほど、その遷移の尤度が高いことになる。
【００２６】
例として図４における時点ｔ＝０での状態（Ｄ０，Ｄ１）＝（０，０）から時点ｔ＝１における状態（Ｄ０，Ｄ１）＝（０，０）への状態遷移に対するブランチメトリックを考える。この状態遷移に対するブランチについている値、すなわち符号語（０，０）と、この状態遷移を生じる際のビタビ復号装置への入力、すなわち受信語（１，１）とのハミング距離は２であるので、ブランチメトリックは２となる。
【００２７】
一方、ｔ＝０での状態（Ｄ０，Ｄ１）＝（０，１）からｔ＝１における状態（Ｄ０，Ｄ１）＝（０，０）への状態遷移に対するブランチメトリックは同様に計算すると０となる。ブランチメトリックはその状態遷移の尤度を表し、図４ではハミング距離をブランチメトリックに用いているので、ブランチメトリックの値が小さい状態遷移がより確からしいと評価できる。従ってｔ＝１の状態（Ｄ０，Ｄ１）＝（０，０）へ遷移する状態のうち、ｔ＝０における状態（Ｄ０，Ｄ１）＝（０，１）からのパスが尤もらしいと評価できる。
【００２８】
上述したように、ビタビ復号では受信語に対する正しいパスを決定するために、トレリス線図上の初期時点からその初期時点以降の時点における状態に至る各々のパスの尤度を評価し、最も尤度が高い最尤パスを決定する。ビタビ復号ではトレリス線図上の各時点における各状態に至るまでのパスの尤度をパスメトリックと呼ばれる値で評価する。パスメトリックはトレリス線図上の一の状態に至るそれぞれのパスを構成するブランチのブランチメトリックの和で計算される。しかし、各時点における各状態に至る全てのパスについてのパスメトリックを求めようとすると計算量が膨大になる。そこでビタビ復号では、各時点における各状態の各々に至るパスのうち、パスメトリックに基づいて最も尤度が高いと判断されるパスのみを生き残りパスとして採用し、他のパスは破棄することで計算量を低減する方法が用いられる。
【００２９】
図４に示すように、トレリス線図上の各時点における各状態の各々に至るブランチは２つであり、各時点における各状態の各々で生き残りパスのみを採用して他のパスを破棄するため、ある状態に至るパスは必ず２つになる。そこでこのある状態に至る２つのパスについてのパスメトリックを比較して、その比較結果から尤度の高い一のパスのみを生き残りパスとする。図４では各状態の上下に数値が示されているが、各状態に対して上側からのパスに対するパスメトリックの値を上に、下側からのパスに対するパスメトリックの値を下に示している。この例では、符号語と受信語のハミング距離をブランチメトリックに用いているのでパスメトリックが小さいほど尤度が高いと判断できる。ゆえに図４では、ある状態に至る２つのパスの内、パスメトリックの小さい方を選んで生き残りパスとしている。
【００３０】
例えば図４のトレリス線図における時点ｔ＝２、状態（Ｄ０，Ｄ１）＝（０，１）を見てみると、時点ｔ＝１、状態（Ｄ０，Ｄ１）＝（１，０）から至るパスのパスメトリックは０であり、時点ｔ＝１、状態（Ｄ０，Ｄ１）＝（１，１）から至るパスのパスメトリックは３である。従ってパスメトリックが小さい、時点ｔ＝１、状態（Ｄ０，Ｄ１）＝（１，０）から至るパスを生き残りパスとする。これを実線で示す。また他方のパスを破棄し、これを破線で示している。本例においてはパスメトリックの値が等しい場合には、各状態において上側のブランチから各々の状態へ至るパスを生き残りパスとしているが、下側のブランチから各々の状態へ至るパスを生き残りパスとしてもかまわない。
【００３１】
以上述べた方法により、各時点の受信語に対してトレリス線図上の初期時点から最終時点までの最尤パスを、各時点における各状態のパスメトリックに基づいて決定したならば、そのパスに基づき復号結果を得る。ビタビ復号においては復号結果を得るにあたり、トレースバックという手法を用いる。トレースバックとは、最尤パスをパスメトリックに基づいて決定する過程でトレリス線図上の各時点における各状態に至る２つのブランチの内、どちらのブランチから各々の状態へ至るパスを生き残りパスとしたかの情報を記憶しておき、その情報に従ってトレリス線図の最終時点で最も尤度が高い状態から初期時点に向かってパスを遡る手法である。図４でいえばパスメトリックが最も小さい状態（Ｄ０，Ｄ１）＝（１，１）を起点に太線で示すパスを時点ｔ＝５からｔ＝４、・・・ｔ＝０まで辿ることになる。図４に示した例では、現在の状態が偶数（（Ｄ０，Ｄ１）＝（０，０）、（０，１））なら"０"、奇数（（Ｄ０，Ｄ１）＝（１，０）、（１，１））ならば"１"を復号結果とする。よって図４に示す例においては"１１００１"という順に結果がでる。なお、初期状態は結果を出さない。これを逆順にすれば元の順番となり、表１の復号系列が得られることとなり、復号することができる。
【００３２】
実際のＷ−ＣＤＭＡ通信において使用されている畳み込み符号化器は、レジスタ８個、１ビット入力で２又は３ビット出力される、拘束長９、符号化率１／２または１／３の畳み込み符号化器（図５参照）が使用されている。
【００３３】
次に、本実施の形態にかかるビタビ復号装置について説明する。図６は、本実施の形態にかかるビタビ復号装置を示すブロック図である。ビタビ復号装置１は、受信データ格納部１１、ＡＣＳ演算部１２、尤度情報格納部１３、ＡＣＳ結果格納部１４、ＡＣＳ結果変換部１５、復号演算部１６、ＣＲＣ演算部１７、復号結果格納部１８及び復号制御部１９を有する。
【００３４】
受信データ格納部１１は、受信データを受け取り復号に用いるデータとして格納する。ＡＣＳ演算部１２は、ビタビ復号演算のコアになる部分である。トレリス線図上における一の時点に状態Ａと状態Ｂがあり、状態Ａと状態Ｂは各々が、この一の時点より一時点後の時点における状態Ｃに至るブランチを有している。このときＡＣＳ演算部１２は、状態Ａに至るまでの生き残りパスが有するパスメトリックに状態Ａから状態Ｃに至るブランチのブランチメトリックを足した（Ａｄｄ）結果と、状態Ｂに至るまでの生き残りパスが有するパスメトリックに状態Ｂから状態Ｃに至るブランチのブランチメトリックを足した（Ａｄｄ）結果とを比較し（Ｃｏｍｐａｒｅ）、比較の結果から状態Ｃに至る尤度が高い方のパスを生き残りパスとして採用する。そして状態Ａと状態Ｂが有する状態Ｃへのブランチの内、生き残りパスを構成する一のブランチを選択（Ｓｅｌｅｃｔ）する処理を行う。
【００３５】
尤度情報格納部１３は、ＡＣＳ演算で足された（Ａｄｄ）尤度情報を格納する部分であり、次回の尤度計算の時に再利用する。尤度情報を繰り返し利用することで誤り訂正能力を高めることができる。
【００３６】
ＡＣＳ結果格納部１４は、ＡＣＳ演算の選択（Ｓｅｌｅｃｔ）結果を格納する部分であり、この情報から最終的な復号結果を得る。
【００３７】
ＡＣＳ結果変換部１５は、ＡＣＳの結果を強制的に変換する部分であり、この変換動作により遷移を変えてトレースバックが可能となる。具体的には、読み出したＡＣＳ演算の選択（Ｓｅｌｅｃｔ）をビット反転する処理である。この動作の詳細は後述する。
【００３８】
復号演算部１６は、トレースバックを行い、最も尤度が高い第１候補の復号パス（第１復号パス）にかかる復号結果を得る。ＣＲＣ演算部１７は、得られたデータの中にＣＲＣが含まれている場合、ここでＣＲＣ演算を行い復号結果の誤り判定を行う。ここで、ＣＲＣにより復号結果にエラーが発見された場合、本実施の形態においては、データの再送を行なわず、ＡＣＳ結果変換部１５の結果を使用して、第２候補となる復号パスをトレースバックし、再復号を行なう。復号結果格納部１８は、復号データを格納する。復号制御部１９は、ビタビ復号装置の制御を行なう。すなわち各ブロックの動作コントロールを行う。
【００３９】
このビタビ復号装置においては、受信データを受け取ると、ＡＣＳ演算部１２、ＡＣＳ結果格納部１４の結果に基づき、復号演算部１６が第１の復号パスを求める。そして、第１の復号パスを使用して復号データを求める。ＣＲＣ演算部１７にて、その復号データの誤り検出をする。この誤り検出の結果、第１の復号データに誤りがある場合は、ＡＣＳ結果変換部１５がＡＣＳの結果を変換する。
【００４０】
このことにより、復号演算部１６は、トレリス線図の第１の復号パスにおいて、第１の状態へ至るブランチとして選択されたブランチとは別のブランチに変更してトレースバックを行ない第２の復号パスを求め、第２の復号パスを使用して再度復号データを得る。ＣＲＣ演算部１７は、再度このＣＲＣ判定を行なうことで、第１候補の第１の復号パスに誤りが検出された場合であっても、データの再送を行なわず、第２候補である第２の復号パスを使用して復号結果を得ることで誤りを訂正する確率を向上する。ここで、第２の復号パスの復号データに誤りが検出された場合は、同様に、ＡＣＳ結果変換部１５が再びＡＣＳの結果を変換する。この変換により、復号演算部１６は、第１の復号パスにおいて、第１の復号パスにおける第１の状態から一ブランチトレースバックした第２の状態へ至るブランチとして選択されたブランチとは別のブランチに変更してトレースバックを行なった第３の復号パスを求め、第３の復号パスを使用して再度復号データを得る。このように、例えばＣＲＣ判定でＯＫがでるまで、又は所定数だけ復号パスを変更して復号結果を求めることで、誤り訂正能力を向上させることができる。
【００４１】
また、後述するように、第２候補として選択するのは、第１の復号パスの最終状態へ至るブランチと異なるブランチをトレースバックした復号パスに限られない。トレリス線図における最終状態において、最もパスメトリックが小さい状態からトレースバックして第１の復号パスを選択している場合等においては、当該最終状態において２番目にパスメトリックが小さい状態からトレースバックした復号パスを第２候補としてもよい。
【００４２】
次に、本実施の形態にかかるビタビ復号装置について更に詳細に説明する。先ず、ＡＣＳ演算部１２について説明する。図７はある時点ｔからｔ＋１に遷移する時のＡＣＳである。上述したように、時点ｔ＋１の状態Ｃに至るパスは２本存在する。それらのパスの元の状態を状態Ａ、状態Ｂとする。時点０からｔまでのパスメトリックＰＭｔとすると、それぞれの状態のＰＭはＰＭ（Ａ）ｔ、ＰＭ（Ｂ）ｔと示せる。ＡＣＳ演算部１２は、時点ｔにおける入力データから求めたブランチメトリックＢＭ（ハミング距離・ユークリッド距離）ＢＭ（ＢＭ（Ａ→Ｃ）ｔ、ＢＭ（Ｂ→Ｃ）ｔ）と各状態のＰＭ（ＰＭ（Ａ）ｔ、ＰＭ（Ｂ）ｔ）を足し合わせた結果を比較して、値が小さい方、すなわち尤度が大きい方のパスを選択する。以下の式が選択式になる。
if（PM（A）t + BM（A→C）t ＜= PM（B）t + BM（B→C）t）{
PM（C）t+1 = PM（A）t + BM（A→C）t
SEL = 0（状態A）
}else{
PM（C）t+1 = PM（B）t + BM（B→C）t
SEL = 1（状態B）
}
【００４３】
なお、上式では、ＰＭ、ＢＭが小さい程尤度が大きいとしているが、これは本実施の形態がブランチメトリックに受信語と符号語のハミング距離を用いていることに起因している。従って、異なるブランチメトリックを定義し、ブランチメトリック、パスメトリックが大きいほど尤度が大きくなるとしてもよい。ブランチメトリック、パスメトリックが小さいほど尤度が大きい場合には、その初期値は、初期状態のＰＭは０、その他の状態のＰＭは十分大きな値にしてもよい。例えば初期状態が０ならＰＭ（０）０は０、ＰＭ（Ｘ）0（Ｘ≠０）は十分大きな値にする。ＰＭ、ＢＭが大きいほど尤度が大きい場合には、この逆の初期設定にする。
【００４４】
ＳＥＬは選択したパス（生き残りパス）の情報である。状態Ｃに至るパスは２本しかないので、１ｂｉｔの情報（０，１）でどちらのパスが選択されたか分かる。ここでは、状態Ａを選択したとき（例えば図４において上側の矢印を通る状態）を"０"、状態Ｂ（例えば図４において下側の矢印を通る状態）を選択したときを"１"としてメモリに記憶する場合について示している。求めたＰＭ（Ｃ）ｔ＋１は尤度情報格納部１３に、ＳＥＬはＡＣＳ結果格納部１４に格納される。図８は、ＡＣＳ結果格納部１４に格納される結果を示す図である。このように、生き残りパスの情報ＳＥＬ（ＡＣＳ結果）は、時点ｔと状態とに関係付けられて記憶される。ここで、ＰＭ（Ｃ）ｔ＋１は次時点のＡＣＳ演算に使用され、順次上書きされる。ＡＣＳ結果は復号結果を得る際に利用される。また、本実施の形態においは、後述するように、復号パスを切り換える際にも使用される。
【００４５】
次に、復号演算部１６の復号処理について説明する。図９は図４の生き残りパス（ＡＣＳ結果）について示している。最後のＡＣＳ演算で最もパスメトリックが小さい状態は、影をつけて示す状態（１１）である。つまりこの場合、入力データから最終的に状態（１１）に至るパスが尤もらしいということになる。この状態に至るまでの生き残りパス（ＡＣＳ結果）は一本しか存在しないことが分かる。このパスを遡ることで復号結果を得る。上述したように、生き残りパスの情報はＡＣＳ結果格納部１４に格納されている。すなわち、図７に示したように、ＡＣＳ結果格納部１４における格納結果ＳＥＬが"０"であれば状態Ａ（例えば上のパス）、"１"であれば状態Ｂ（例えば下のパス）をたどればよい。こうして図１０、図１１に示すように、ＡＣＳ結果を辿ることで復号結果を得ることができる。
【００４６】
なお、Ｗ−ＣＤＭＡ通信では畳み込み符号化の最後にＴａｉｌＢｉｔ（終端ビット）と呼ばれる通常"０"のデータを８ｂｉｔ挿入することにより、ＡＣＳ演算の最終時点において最も尤度が高くなる状態を０になるようにしている。すなわち、本例の場合であれば、ＴａｉｌＢｉｔとして２ビットの"０"を入力することで、最終状態が（００）となるようにすることができる。本明細書においては、この状態を状態零ということとする。
【００４７】
図１２は、符号化器２０へ入力する入力データの最後に、Ｔａｉｌｂｉｔとして２ビットの"０"を挿入した場合を示すトレリス線図である。表２は、表１に示すデータにＴａｉｌＢｉｔを付加した符号化器２０における入出力データを示す。
【表２】
2008118327.tif 000004
【００４８】
全てのデータをこの符号化器２０に入力した後に"０"を２回入力すると必ず（Ｄ０,Ｄ１）＝（０，０）になる。つまり状態零にトレリス終結し、その入出力データは、上記表２のようになる。図１２に示すように、ＴａｉｌＢｉｔを挿入することで、時点ｔ＝６、ｔ＝７で最終状態が状態（０，０）へ導かれ、トレリス終結時において状態零となっている。
【００４９】
なお、図１２は畳み込み符号化器のレジスタの初期値が０の場合である。ＴａｉｌＢｉｔを挿入することにより、最終状態が状態零にトレリス終結している。また、図１２では（Ｄ０，Ｄ１）の初期状態を（０，０）と定義している。つまり、トレースバックの行き着く先が状態（０，０）になるはずであり、そうなるように予めＰＭに重み付けをしておく。これにより、最終的にトレースバックした時に状態零に行き着く。なお、ＴａｉｌＢｉｔを挿入してトレリス終結させる方法が一般的であるが、以下の説明においては、説明及び図面の簡単のため、ＴａｉｌＢｉｔを挿入しないものとして説明する。また、（Ｄ０，Ｄ１）の初期状態も定義しない（ＰＭの重み付けを行なわない）ものとする。
【００５０】
以上のようにして最も尤度が高い状態から生き残りパスを辿ったパスが第１の復号パスとなる。上述したように、状態が偶数か又は奇数により、"０"、又は"１"に復号することができる。この復号結果をＣＲＣ演算部１７に入力し、ＣＲＣにより復号結果を検査する。
【００５１】
次に、復号演算部１６の詳細について説明する。ＡＣＳ結果は、図１０に示すように０，１の２値（１ｂｉｔ）情報で格納される。本実施の形態においては、上述したように、ある状態に至る２つのパスのパスメトリックを比較して小さいパスメトリックを有するパスが上側だった場合は"０"を、下側だった場合は"１"をＡＣＳ結果として保存している。図１３は、生き残りパスを示すが、ここで、各状態において、下線付き数字がＡＣＳ結果を示す。本例においてはスタート時点を時点０（ｔ＝０）とした場合、時点５（ｔ＝５）まで６時点存在する。状態は（００）から（１１）まで４状態存在する。よって、図８、図１０に示すように、ＡＣＳ結果は（時点数−１）×状態数＝２０ｂｉｔ存在する。なお、最初の状態（ｔ＝０）にＡＣＳ結果がないため時点数から１を引いている。
【００５２】
この復号演算部１６は、トレースバック時に、図１０に丸印で示すデータを読み出す。ここでは最終時点（ｔ＝５）の状態が"１１"と選択されているので、４行５列目のデータを読み出す。読み出したデータは"０"だと分かる。これらの情報から復号データを求めるのだが、復号に当たって図１４を使用する。
【００５３】
Ｄ０'（３１）、Ｄ１'（３２）はフリップフロップである。まず、トレースバックを始める状態をフリップフロップ３１、３２（Ｄ０'，Ｄ１'）にセットする。本例においては、状態（１１）がトレースバックスタートの状態なのでＤ０'＝１、Ｄ１'＝１をセットする。そして、ＡＣＳ結果保存ＲＡＭから読み出した（５行４列目）値"０"をフリップフロップ３２（Ｄ１'）に入力する。そうすると、フリップフロップ３２（Ｄ１'）のデータはフリップフロップ３１（Ｄ０'）に、フリップフロップ３１（Ｄ０'）のデータは復号結果（Decoded Data）として出力される。フリップフロップ３１（Ｄ０'）に格納されていたデータは"１"だったので、最初のデコード結果は"１"となる。
【００５４】
次に、時点４（ｔ＝４）のフリップフロップ３１、３２（Ｄ０'，Ｄ１'）のＡＣＳ結果を読み出す。フリップフロップ３２（Ｄ１'）にｔ＝５のＡＣＳ結果"０"を入力したので、今は（Ｄ０'，Ｄ１'）＝（１，０）となっている。なので、ｔ＝４、状態（１，０）のＡＣＳ結果を読み出す。ここでは"０"が得られる。これをフリップフロップ３２（Ｄ１'）に入力すると復号結果として"１"が出力される。このような処理をｔ＝１まで実行すると"１１００１"という復号結果を得ることができる。結果は後ろから求まるので順番を逆にして"１００１１"が最終的な復号結果になる。
【００５５】
そして、この復号結果をＣＲＣ判定する。ここで、復号結果に誤りがあれば、ＡＣＳ結果変換部１５により、ＡＣＳ結果を変換し、第２復号候補を選択するための以下の処理を行なう。
【００５６】
次に、ＡＣＳ結果変換部１５の処理について説明する。図１１のようにＡＣＳの生き残りパスを遡ることにより復号結果を得ることができるが、この結果における誤り判定結果がエラーであった場合、本実施の形態においては、第２候補の復号パスを選択する。すなわち、最尤復号結果が誤りＮＧ判定された場合、ＡＣＳ結果の一部を変換して再復号を行う。この場合、図１５に示すように、ｔ＝５の最終時点の状態として選択された状態（１１）へ至るブランチを、第１の復号パスＰ１と異なるブランチとして実線のパスを復活させる。上述したように、ある状態に至るパスは２本あり、どの状態から遷移するのかは決まっているため、選択されなかったパスは復活させることができる。このパスの情報は、上述のＡＣＳ結果格納部１４が"０"か"１"の２値で持っているので、復活させたいパスのｂｉｔを反転させることで復活させることができる。この復活させたパスに至るまでの生き残りパスの情報は残っているため、これを遡ることで復号結果を得ることができる。すなわち、本実施の形態においては、第２候補の復号パスを選択するにあたって何ら特別なメモリ等を必要としない。
【００５７】
このＡＣＳ結果変換部１５の処理について更に詳細に説明する。図１６に第２候補の第２の復号パスを選択する場合のＡＣＳ結果格納部１４を示す。変換ビットは図１６に示すように、第２候補はトレースバックのスタート地点（ＡＣＳの最終地点）、すなわちｔ＝５の状態（１１）のＡＣＳ結果を反転させてトレースバックを行う。反転させたら、上述の図１４に示すデコーダに入力すれば同様に復号結果を得ることができる。
【００５８】
ＡＣＳ結果変換部１５は、第２候補となる第２の復号パスの復号結果がエラー検出された場合は、さらに第３候補となる第３の復号パスを選択するべく、ＡＣＳ結果を反転させる。第３候補は、図１７、図１８に示すように、トレースバックのスタート地点の次の地点（ＡＣＳの最終地点の一つ手前）のＡＣＳ結果、すなわち、ｔ＝４の状態（１０）を反転させてトレースバックを行う。同様に、第４候補、第５候補と反転するビットの位置を１時点ずらしながらトレースバックを行う。
【００５９】
なお、図１６、図１７ではＡＣＳ結果メモリの中身を書き換えているが、結果候補が間違えていた場合、再度メモリの書き換えを行わなければならないので、実回路では、図１９に示すように、ＡＣＳ結果格納部からＡＣＳ結果を読み出した後にビット反転する。
【００６０】
ここで、上述した図１２に示したトレリス終結した場合についても説明しておく。図２０は、図１２に示すトレリス線図における生き残りパスだけを抜き出して示す図である。図１２と同様、畳み込み符号化器のレジスタの初期値が０の場合を示す。図２０において、太実線は第１候補、細実線は第２候補を示している。第１候補の出力結果は"００１１００１"となる。頭の２ｂｉｔはＴａｉｌＢｉｔなので除去して、さらに結果の順番を反対にすると"１００１１"という最終結果が得られる。本例においては、最終状態においてＰＭが最も小さい状態は状態（０，０）であり、よって最も尤度が高いパスは太実線のパスであるが、最終状態においてＰＭが２番目に小さい状態は、状態（１，０）であり、よって２番目に尤度の高いパスは破線のパスとなる。ここで、尤度が高い順でみた場合、第２候補のパスは破線のパスになるはずであるがここでは、これを第２候補とはしない。
【００６１】
すなわち、上述したように、本実施の形態においては、第１候補の復号パスを最終状態において最も尤度が高い状態からトレースバックした復号パスとし、第２候補の復号パスを最終状態において２番目に尤度が高い状態からトレースバックした復号パスとする（詳細は後述する。）ことも可能であるが、本例のように、ＴａｉｌＢｉｔを挿入する場合は、最終状態は０になるというルールがある、すなわち状態（０，０）以外の状態は取りえないことから、最終状態の尤度順にトレースバックする手法はとり得ない。よって、この場合、第２候補は、第１候補である第１の復号パスの最終時点＝状態零へ至るブランチを当該第１の復号パスと異なるブランチとしてトレースバックした復号パスとなるため、第２候補の復号パスは、状態零（状態（０，０））から始まる細実線のパスとなる。なお、本例の場合、この第２候補の復号パスの最終状態（状態（０，０））のＰＭは５となっている。
【００６２】
次に、本実施の形態にかかるビタビ復号方法について説明する。図２１は、本実施の形態に係るビタビ復号方法を示すフローチャートである。先ず、図６に示す受信データ格納部１１からＡＣＳ演算部１２にデータを入力する（ステップＳ１）。ＡＣＳ演算部１２は、上述したようにＡＣＳ演算を実行する（ステップＳ２）。そして、ＡＣＳ演算が所定の打ち切り長に到達した場合（ステップＳ３：Ｙｅｓ）、復号演算部１６は、ＡＣＳ結果格納部１４に格納されたＡＣＳ結果を参照し、トレースバックを行なって復号結果を取得し、ＣＲＣ演算をしつつ、復号結果格納部１８に格納する。入力データが全部入力されるまでこれを続ける（ステップＳ５）。
【００６３】
全てのデータを入力し終えると、復号演算部１６は、トレースバックにより最終の復号結果を得る（ステップＳ６）。例えば、Ｗ−ＣＤＭＡ通信などにおいては、各入力データ毎ではなく、ある単位のデータブロックにＣＲＣが付されているため、当該単位データブロックの復号結果を取得する。そして、ＣＲＣにより、誤りビットの検出を行い（ステップＳ７）、誤りビットがあれば、第２候補、第３候補の復号パスを順次復活させていく。先ず、再復号回数が所定の回数に達していないかが判断され（ステップＳ８）、所定回数以下であれば、ＡＣＳ結果変換部１５により、ＡＣＳ結果格納部１４に格納されているＡＣＳ結果を読出しビット反転し（ステップＳ９）、これを参照して復号演算部１６が第２候補の復号パスをトレースバックし復号結果を取得する（ステップＳ６）。こうして、誤りが検出されなくなるまで、又は所定の回数だけ復号を繰り返す。なお、本例においては、ステップＳ８において所定回数に達するまで次候補の復号パスを選択するものとして説明した。
【００６４】
図２２は、拘束長４の畳み込み符号化器のトレリス線図を示す。上述したように、畳み込み符号は値"０"のＴａｉｌＢｉｔを挿入することによりトレリス終結時において状態零に遷移するのが普通である。トレースバックは最終の状態からその状態に遷移するパスの尤度の高い方を選びつつパスを遡ることで第１候補の復号結果を得る。
【００６５】
第１候補の復号結果が正しいかどうかの判定を行い、判定がＯＫならデコードを終了するが、判定がＮＧなら第２候補を復号する。第２候補は最終パスの選択されなかった方のパスであり、そこから尤度の高いパスを遡ることで復号結果を得る。この第２候補の復号結果を再度誤り判定し、誤りが無ければデコードは終了する。また、誤りがあれば第３候補の復号を開始する。第３候補は最終パスの一つ前の状態の選択されなかった方のパスを選択し、尤度の高いパスをさかのぼる。第４候補、第５候補・・・は、最終パスの２つ前、３つ前・・・のパスの選択されなかった方のパスを選択し、その後尤度の高いパスをさかのぼる。
【００６６】
上述したように、ＡＣＳ結果格納部１４は、各状態においてその状態にいたる最尤のパスの情報（ＡＣＳ結果）を記憶しているため第２候補、第３候補・・・のようなパスを選択してもその後の最尤パスを遡ることができ、復号結果を得ることができる。
【００６７】
ここで、トレリス終結しない時にも本件の適用が可能であり、その時には尤度が最も高い状態（現時点における）から最尤パスを遡るのが第１候補、現時点における尤度の最も高い状態にいたる最尤でないパスから最尤のパスを遡るのが第２候補となる。また、現時点における２番目に尤度の高い状態から最尤のパスを遡るものを第２候補としてもよい。
【００６８】
図２３乃至図２５は、本実施の形態にかかるビタビ復号方法を適用した結果を、第１候補で復号を終了する一般的なビタビ復号装置（従来例）と比較して示すグラフ図である。図２３は、畳み込み符号化率が１／３、ＴｒＢＫ（Transport Block）サイズが１０ビット、ＣＲＣが１６ビット、ＣｄＢＫ（Code Block）サイズが２６ビットの復号結果を示す。図２４は、畳み込み符号化率が１／３、ＴｒＢＫサイズが４１ビット、ＣＲＣが１６ビット、ＣｄＢＫが５７ビットの復号結果を示す。図２５は、畳み込み符号化率が１／３、ＴｒＢＫサイズが４８８ビット、ＣＲＣが１６ビット、ＣｄＢＫが５０４ビットの復号結果を示す。横軸は信号対雑音比(Ｅｂ／Ｎ０、Ｅｂ：１ｂｉｔあたりのエネルギー、Ｎ０はノイズ電力スペクトル密度)、縦軸はＢＬＥＲ（block error rate）を示す。図２３乃至図２５に示すように、いずれにおいても誤り訂正能力が向上しているが、データサイズが小さいほど、誤り訂正能力が大きい。
【００６９】
本実施の形態においては、第１候補で復号結果がエラーであれば、第２候補となる復号パスを選択して再復号を行なう。第２候補の復号結果がエラーであれば、第３候補となる復号パスを選択して再復号を行なう。すなわち、第Ｎ（Ｎ≧２）番目の復号パスの復号データに誤りが検出された場合、第１の復号パスにおける最終状態（状態零）からｔ＝（Ｎ−１）時点トレースバックした第（Ｎ＋１）番目の復号パスの復号データを使用する。このことにより、第１復号パスしか復号しない従来の方法に比して誤り訂正能力を向上することができる。また、本実施の形態においては、第２、第３候補として選択する生き残りパスは常に１種類であり、通常保持しているＡＣＳ結果を利用して再復号を行なうことができる。このため、新たに追加するハードウェアが必要なく、極めて簡易な方法で誤り訂正能力を向上することができる。
【００７０】
次に、本実施の形態において誤り訂正能力が向上する理由について説明する。送信側から送られたデータは伝送路においてノイズが乗るため、受信側では理想のデータが届かない。ビタビ復号はそれらのデータから元のデータを予測して答えを出す。
【００７１】
通常のビタビデコーダ（復号装置）は与えられた条件から一番尤もらしい答えを出す。この尤もらしい答えは合っているかどうかはこの時点では分からないので、ＣＲＣ等の誤り検出符号を用いて正誤判定を行う。この場合、送信時にＣＲＣも一緒に送る必要がある。誤りだと判定された場合には、受信側は送信側に再送要求を行う。
【００７２】
一般的なビタビ復号装置では一番尤もらしい答えが間違いだった場合にはその時点で復号を諦めてしまうが、本実施の形態においては、１番尤もらしい答えが間違いだった場合でも、第２候補により２番目に尤もらしい答えを用意することができる。２番目に尤もらしい答えが間違いだった場合には、第３候補により３番目に尤もらしい答えを用意する。このように複数の答えを用意することで、正解になる可能性（誤り訂正能力）を高めることができる。図２６（ａ）はノイズが小さい場合の復号結果である。ＡＣＳ結果変換部以外の構成が同じなら、第１候補の答えは同じになる。この場合、第１候補が正解だったものとすると、どちらの復号装置でも復号に成功している。
【００７３】
図２６（ｂ）はノイズが大きい場合の復号結果である。第１候補の答えが間違いだった場合、一般的なビタビ復号装置では復号を諦めてしまう（誤り訂正失敗）のに対し、この例においては復号を続けることにより第３候補で正解を導いている。
【００７４】
次に、データサイズが小さいほど誤り訂正能力の向上力が大きい理由について説明する。その理由として以下の２点が考えられる。
【００７５】
先ず、データサイズが小さいほど誤るデータ数が少ない。データサイズが小さいということは、間違えるデータ数も少ないことを意味する。例えば１０ｂｉｔの内１ｂｉｔ間違えるパタンの場合、実際はこれほど単純ではないが、データサイズが１０ｂｉｔなら１ｂｉｔ、１００ｂｉｔなら１０ｂｉｔ間違えることになる。１ｂｉｔでも間違えれば復号失敗であるが、前者は１ｂｉｔ修正すれば復号成功になる。１０ｂｉｔ修正するより、１ｂｉｔ修正する確率の方が高いため、データサイズが小さい程、本実施の形態にかかる方法を適用することにより復号する確率が高くなる。
【００７６】
また、データサイズが大きい場合、最初の復号で間違えた部分を２回目以降の復号で修正したとしても他の部分（元々合っていた部分）が新たに間違えてしまう可能性が高くなる。
【００７７】
第２に、データサイズが小さいほど誤り訂正能力が低い。上述のように、ビタビ復号ではあるデータを求める際に、前に入力されたデータの尤度情報（入力履歴）も利用する。データ数が大きくなれば蓄積される尤度情報も大きくなり、ある時点で誤ったデータが入力されても、入力履歴からその誤ったデータを修正する可能性が高くなる。データ数が小さい場合には入力履歴も少ないので、誤ったデータを修正しきれない可能性が高くなる。したがって、ある程度データサイズが大きい方が誤る割合は小さくなる。つまり、データサイズが小さい方が訂正能力は低いので、複数回復号することで誤りを直しやすい。
【００７８】
なお、本発明は上述した実施の形態のみに限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能であることは勿論である。例えば、上述の実施の形態においては、第２候補は、第１候補の復号パスにおいて、トレリス終結時における状態から１ブランチだけトレースバックする際、第１候補とは異なるブランチとしてトレースバックした復号パスを使用する。Ｗ−ＣＤＭＡなどでは、ＴａｉｌＢｉｔを挿入するため、トレリス終結時における状態零が通常は最も尤度が高くなり、最終状態としては、状態零を選択するようにしている。これに対し、ＴａｉｌＢｉｔを挿入しない場合などにおいては、トレリス線図における最終状態において最も尤度が高い状態は状態零に限られない。したがって、このような場合、図２７に示すように、第１候補として、当該最終状態における尤度が１番高い状態が選ばれるが、この第１候補の復号パスが誤りだった場合、第２候補として、当該最終状態における尤度が２番目に高い状態からトレースバックした復号パスＰ２'を選択するようにしてもよい。第３候補の復号パスＰ３'も同様である。３番目に尤度が高い状態からトレースバックした復号パスとすることができる。
【００７９】
すなわち、Ｎ番目の復号パスの復号データに誤りが検出された場合には、当該最終状態において、（Ｎ＋１）番目に尤度が高い状態からトレースバックした（Ｎ＋１）番目の復号パスを求め、この（Ｎ＋１）番目の復号パスをしようして再復号することで、誤り訂正能力を向上させることができる。
【００８０】
また、上述の実施の形態では、ハードウェアの構成として説明したが、これに限定されるものではなく、任意の処理を、ＣＰＵ（Central Processing Unit）にコンピュータプログラムを実行させることにより実現することも可能である。この場合、コンピュータプログラムは、記録媒体に記録して提供することも可能であり、また、インターネットその他の伝送媒体を介して伝送することにより提供することも可能である。
【図面の簡単な説明】
【００８１】
【図１】畳み込み符号化器を示す図である。
【図２】畳み込み符号化器の状態遷移を示す図である。
【図３】表１に示す値を入力した場合の遷移状態を示す図である。
【図４】表１に示す値を入力した場合のトレリス線図を示す図である。
【図５】Ｗ−ＣＤＭＡ通信において使用されている畳み込み符号化器を示す図である。
【図６】本発明の実施の形態にかかるビタビ復号装置を示すブロック図である。
【図７】ある時点ｔからｔ＋１に遷移する時のＡＣＳを示す図である。
【図８】本発明の実施の形態にかかるビタビ復号装置におけるＡＣＳ結果格納部に格納される結果を示す図である。
【図９】図４に示すトレリス線図における生き残りパス（ＡＣＳ結果）を示す図である。
【図１０】本発明の実施の形態にかかるビタビ復号装置におけるＡＣＳ結果格納部に格納される第１候補を復号する場合の結果を示す図である。
【図１１】トレリス線図において第１候補の復号パス（第１の復号パス）を示す図である。
【図１２】符号化器２０へ入力する入力データの最後に、Ｔａｉｌｂｉｔとして２ビットの"０"を挿入した場合を示すトレリス線図を示す図である。
【図１３】図４に示すトレリス線図における生き残りパス（ＡＣＳ結果）にＡＣＳ結果を合わせて示す図である。
【図１４】ＡＣＳ結果から復号データを求めるためのデコーダを示す図である。
【図１５】トレリス線図において第２候補の復号パス（第２の復号パス）を示す図である。
【図１６】第２候補の第２の復号パスを選択する場合のＡＣＳ結果格納部のＡＣＳ結果を示す図である。
【図１７】第３候補の復号パスを選択する場合のＡＣＳ結果格納部のＡＣＳ結果を示す図である。
【図１８】トレリス線図において第３候補の復号パスを示す図である。
【図１９】ＡＣＳ結果格納部からＡＣＳ結果を読み出した後にビット反転する様子を示す図である。
【図２０】図１２に示すトレリス線図における生き残りパスだけを抜き出して示す図である。
【図２１】本発明の実施の形態に係るビタビ復号方法を示すフローチャートである。
【図２２】拘束長４の畳み込み符号化器のトレリス線図において第１乃至第４候補を示す図である。
【図２３】本発明の実施の形態にかかるビタビ復号方法を適用した結果を、第１候補で復号を終了する一般的なビタビ復号装置（従来例）と比較して示すグラフ図である。
【図２４】同じく、本発明の実施の形態にかかるビタビ復号方法を適用した結果を、第１候補で復号を終了する一般的なビタビ復号装置（従来例）と比較して示すグラフ図である。
【図２５】同じく、本発明の実施の形態にかかるビタビ復号方法を適用した結果を、第１候補で復号を終了する一般的なビタビ復号装置（従来例）と比較して示すグラフ図である。
【図２６】本発明の効果を説明する図であって、（ａ）はノイズが小さい場合の復号結果であり、（ｂ）はノイズが大きい場合の復号結果を示す図である。
【図２７】ＴａｉｌＢｉｔを挿入しない場合において、トレリス線図における第１乃至第３候補の復号パスを示す図である。
【図２８】特許文献１に記載のビタビ復号装置を示すブロック図である。
【図２９】特許文献１に記載のビタビ復号方法を示すフローチャートである。
【図３０】同じく、特許文献１に記載のビタビ復号方法を示す図であって、図２６に示す以降のステップを示すフローチャートである。
【符号の説明】
【００８２】
１  ビタビ復号装置
１１  受信データ格納部
１２  ＡＣＳ演算部
１３  尤度上方格納部
１３  尤度情報格納部
１４  ＡＣＳ結果格納部
１５  ＡＣＳ結果変換部
１６  復号演算部
１７  ＣＲＣ演算部
１８  復号結果格納部
１９  復号制御部
２０  ビタビ符号化器
２１、２２  レジスタ
３１、３２  フリップフロップ
【図１】
2008118327.tif 000005
【図２】
2008118327.tif 000006
【図３】
2008118327.tif 000007
【図４】
2008118327.tif 000008
【図５】
2008118327.tif 000009
【図６】
2008118327.tif 000010
【図７】
2008118327.tif 000011
【図８】
2008118327.tif 000012
【図９】
2008118327.tif 000013
【図１０】
2008118327.tif 000014
【図１１】
2008118327.tif 000015
【図１２】
2008118327.tif 000016
【図１３】
2008118327.tif 000017
【図１４】
2008118327.tif 000018
【図１５】
2008118327.tif 000019
【図１６】
2008118327.tif 000020
【図１７】
2008118327.tif 000021
【図１８】
2008118327.tif 000022
【図１９】
2008118327.tif 000023
【図２０】
2008118327.tif 000024
【図２１】
2008118327.tif 000025
【図２２】
2008118327.tif 000026
【図２３】
2008118327.tif 000027
【図２４】
2008118327.tif 000028
【図２５】
2008118327.tif 000029
【図２６】
2008118327.tif 000030
【図２７】
2008118327.tif 000031
【図２８】
2008118327.tif 000032
【図２９】
2008118327.tif 000033
【図３０】
2008118327.tif 000034