JP3235333B2 - ビタビ復号方法およびビタビ復号化装置 - Google Patents
ビタビ復号方法およびビタビ復号化装置Info
- Publication number
- JP3235333B2 JP3235333B2 JP07709994A JP7709994A JP3235333B2 JP 3235333 B2 JP3235333 B2 JP 3235333B2 JP 07709994 A JP07709994 A JP 07709994A JP 7709994 A JP7709994 A JP 7709994A JP 3235333 B2 JP3235333 B2 JP 3235333B2
- Authority
- JP
- Japan
- Prior art keywords
- path
- traceback
- likelihood
- state
- metric
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Landscapes
- Error Detection And Correction (AREA)
- Dc Digital Transmission (AREA)
Description
【０００１】
【産業上の利用分野】本発明は、ディジタル自動車電話
・携帯電話等のデータ伝送に使用する誤り訂正符号のビ
タビ復号方法およびその装置に関する。
・携帯電話等のデータ伝送に使用する誤り訂正符号のビ
タビ復号方法およびその装置に関する。
【０００２】
【従来の技術】ビタビ復号とは、畳み込み符号の復号方
法の一つである。以下、従来のビタビ復号について説明
する。図７で示されるような畳み込み符号器で生成され
る高速長Ｋ＝３、符号化率Ｒ＝１／２の畳み込み符号Ｃ
を具体例にして説明する。
法の一つである。以下、従来のビタビ復号について説明
する。図７で示されるような畳み込み符号器で生成され
る高速長Ｋ＝３、符号化率Ｒ＝１／２の畳み込み符号Ｃ
を具体例にして説明する。
【０００３】図７に示したシフトレジスタＦ1、Ｆ2によ
って符号器の状態Ｓはつぎの４つの状態、すなわち、 Ｓ0＝（０，０）， Ｓ1＝（１，０）， Ｓ2＝（０，１）， Ｓ3＝（１，１） （１） のいずれかの状態をとる。
って符号器の状態Ｓはつぎの４つの状態、すなわち、 Ｓ0＝（０，０）， Ｓ1＝（１，０）， Ｓ2＝（０，１）， Ｓ3＝（１，１） （１） のいずれかの状態をとる。
【０００４】最初に状態Ｓ0にあった符号器を時々刻
々、すなわち情報信号が入力される度に各状態を遷移し
ていく模様を表現したものがトレリス線図である。符号
のＣのトレリス線図を図８に示す。なおここでは入力情
報信号系列長はＪ−Ｋ＋１であり、さらにＫ−１個の０
が続くものとする。
々、すなわち情報信号が入力される度に各状態を遷移し
ていく模様を表現したものがトレリス線図である。符号
のＣのトレリス線図を図８に示す。なおここでは入力情
報信号系列長はＪ−Ｋ＋１であり、さらにＫ−１個の０
が続くものとする。
【０００５】トレリス線図の枝状の部分をブランチ、２
個以上のブランチの連なりを部分パスと称する。図８に
示したトレリス線図において、点線のブランチは入力信
号が０であることを示し、実線は、入力信号が１である
ことをそれぞれ示すものとする。さらにブランチ部分に
符号器の出力ａ，ｂ，ｃ，ｄを示す。ただし、 ａ＝（０，０），ｂ＝（１，０），ｄ＝（１，１） （２） とし、左側の成分がＣi (1)を、また右側の成分がＣi (2)
を表すものとする。
個以上のブランチの連なりを部分パスと称する。図８に
示したトレリス線図において、点線のブランチは入力信
号が０であることを示し、実線は、入力信号が１である
ことをそれぞれ示すものとする。さらにブランチ部分に
符号器の出力ａ，ｂ，ｃ，ｄを示す。ただし、 ａ＝（０，０），ｂ＝（１，０），ｄ＝（１，１） （２） とし、左側の成分がＣi (1)を、また右側の成分がＣi (2)
を表すものとする。
【０００６】時刻ｔ＝ｔ0における状態Ｓ0（ｔ＝ｔ0）
からｔ＝ｔ1における状態Ｓ0（ｔ＝ｔ1）に至るブラン
チの連なりをパスという。このパスは畳み込み符号のＣ
の符号語に対するパスである。部分パスとの混同を避け
る必要がある場合には符号語パスとよぶことにする。
からｔ＝ｔ1における状態Ｓ0（ｔ＝ｔ1）に至るブラン
チの連なりをパスという。このパスは畳み込み符号のＣ
の符号語に対するパスである。部分パスとの混同を避け
る必要がある場合には符号語パスとよぶことにする。
【０００７】図９に符号Ｃのトレリス線図における部分
パスを示す。この部分パスに対応する符号語の部分集合
を便宜上、 Ｃs 1＝（００ ００ １１）， Ｃs 2＝（１１ １０ ００） （３） とする。ビタビ復号ではパスＣs 1とＣs 2の尤度を比較し
て、例えば、Ｃs 1の尤度の方がＣs 2の尤度よりも大きけ
ればＣs 2を棄却する。このときパスＣs 2を部分パスとし
て含むすべての符号語パスが送信符号語の候補から棄却
されたことになる。Ｃs 1のように棄却されずに残った部
分パスを生き残りパスという。
パスを示す。この部分パスに対応する符号語の部分集合
を便宜上、 Ｃs 1＝（００ ００ １１）， Ｃs 2＝（１１ １０ ００） （３） とする。ビタビ復号ではパスＣs 1とＣs 2の尤度を比較し
て、例えば、Ｃs 1の尤度の方がＣs 2の尤度よりも大きけ
ればＣs 2を棄却する。このときパスＣs 2を部分パスとし
て含むすべての符号語パスが送信符号語の候補から棄却
されたことになる。Ｃs 1のように棄却されずに残った部
分パスを生き残りパスという。
【０００８】図８のトレリス線図を見ると、各状態には
図９に示したような分岐状態を同一とする２本の部分パ
スが存在することがわかる。したがって通常のビタビ復
号では、符号語の両端の状態を除いた定常状態において
は、各時刻において常に２K- 1個の生き残りパスが存在
することがわかる。時刻ｔJ-K+2以降は生き残りパスは
１／２ずつ減少し、時刻ｔjにおいては、たった１個の
生き残りパスとなる。そしてこの生き残りパスが、トレ
ースバックにより復号され、最尤復号データを得る。
図９に示したような分岐状態を同一とする２本の部分パ
スが存在することがわかる。したがって通常のビタビ復
号では、符号語の両端の状態を除いた定常状態において
は、各時刻において常に２K- 1個の生き残りパスが存在
することがわかる。時刻ｔJ-K+2以降は生き残りパスは
１／２ずつ減少し、時刻ｔjにおいては、たった１個の
生き残りパスとなる。そしてこの生き残りパスが、トレ
ースバックにより復号され、最尤復号データを得る。
【０００９】これに対し、本願出願人が先に提案した特
願平５−６７０６１号明細書に記載のビタビ復号方法で
は、尤度に差がない場合にも一方の部分パスのみを生き
残りパスとし、他方を棄却してしまうため、誤りの多い
伝送路でのデータ伝送の際などには、生き残り符号語パ
スが正しい復号語にはならない可能性が高くなるという
問題点を解決するため、ＡＣＳ（Ａdd Ｃompare Ｓelec
t）演算において各状態で生き残りパスの選択をする際
に、最も尤度（メトリック）の高いパスを一つだけ選択
して記憶する（パスセレクト信号の記憶）だけではな
く、最も尤度の高いパスとその他のパスとの尤度差も合
わせて記憶しておき、トレースバックにより復号データ
を求める際に、最尤復号パスだけでなく、最尤パスのト
レースバック区間での尤度（トレースバックによりデー
タ復号する区間での尤度）との間で、あらかじめ設定し
たしきい値（許容メトリック差）以下の尤度となる複数
のパスについても、それぞれトレースバックを行ない、
複数回のトレースバックから複数の復号候補を得るマル
チトレースバックを行なっている。
願平５−６７０６１号明細書に記載のビタビ復号方法で
は、尤度に差がない場合にも一方の部分パスのみを生き
残りパスとし、他方を棄却してしまうため、誤りの多い
伝送路でのデータ伝送の際などには、生き残り符号語パ
スが正しい復号語にはならない可能性が高くなるという
問題点を解決するため、ＡＣＳ（Ａdd Ｃompare Ｓelec
t）演算において各状態で生き残りパスの選択をする際
に、最も尤度（メトリック）の高いパスを一つだけ選択
して記憶する（パスセレクト信号の記憶）だけではな
く、最も尤度の高いパスとその他のパスとの尤度差も合
わせて記憶しておき、トレースバックにより復号データ
を求める際に、最尤復号パスだけでなく、最尤パスのト
レースバック区間での尤度（トレースバックによりデー
タ復号する区間での尤度）との間で、あらかじめ設定し
たしきい値（許容メトリック差）以下の尤度となる複数
のパスについても、それぞれトレースバックを行ない、
複数回のトレースバックから複数の復号候補を得るマル
チトレースバックを行なっている。
【００１０】このマルチトレースバックの処理は、以下
のようにして行なわれる。 各トレースバックでは、各時刻（ｔn）毎に以下の処
理（i）〜（iv）を行なう。
のようにして行なわれる。 各トレースバックでは、各時刻（ｔn）毎に以下の処
理（i）〜（iv）を行なう。
【００１１】（i）時刻ｔnにおける許容差を求める。ｔ
nにおける許容差は、本トレースバック開始からｔn+1ま
でのパス中に、本トレースバック以前の（ｖｉ）の処理
によって逆転させた選択パスが含まれていた場合、逆転
させた両パスのメトリック差（複数含まれていた場合は
それらの合計）を、与えられている許容パスメトリック
差が減算することにより求める。
nにおける許容差は、本トレースバック開始からｔn+1ま
でのパス中に、本トレースバック以前の（ｖｉ）の処理
によって逆転させた選択パスが含まれていた場合、逆転
させた両パスのメトリック差（複数含まれていた場合は
それらの合計）を、与えられている許容パスメトリック
差が減算することにより求める。
【００１２】（ii）時刻ｔnでパスが状態Ｓiを通過する
場合、ＡＣＳで求めた［時刻ｔn，状態Ｓi］でのメトリ
ック差が上記許容差以内であれば、そのときの状態とメ
トリックの差を記憶する。ただし、［時刻ｔn，状態
Ｓi］の選択パスが（vi）によって逆転していた場合は
記憶しない。
場合、ＡＣＳで求めた［時刻ｔn，状態Ｓi］でのメトリ
ック差が上記許容差以内であれば、そのときの状態とメ
トリックの差を記憶する。ただし、［時刻ｔn，状態
Ｓi］の選択パスが（vi）によって逆転していた場合は
記憶しない。
【００１３】（iii）ＡＣＳで求めた［時刻ｔn，状態Ｓ
i］での選択パスをさかのぼり、時刻時刻ｔn-1でパスが
通過する状態を求める（通常のトレースバック処理）。
i］での選択パスをさかのぼり、時刻時刻ｔn-1でパスが
通過する状態を求める（通常のトレースバック処理）。
【００１４】（iv）時刻ｔnでの復号データを求める
（通常のトレースバック処理）。 各トレースバック終了時毎に以下の処理を行なう。
（通常のトレースバック処理）。 各トレースバック終了時毎に以下の処理を行なう。
【００１５】（v）復号データを出力する（通常のトレ
ースバック処理）。 （vi）（ii）において記憶したもののうち、時刻が最も
早い（ｔ0に最も近い）ものが［時刻ｔm，状態Ｓj］で
あった場合、次の２処理を行なう。
ースバック処理）。 （vi）（ii）において記憶したもののうち、時刻が最も
早い（ｔ0に最も近い）ものが［時刻ｔm，状態Ｓj］で
あった場合、次の２処理を行なう。
【００１６】・ＡＣＳで求めた［時刻ｔm，状態Ｓj］で
のパスセレクト信号を逆転 させる。
のパスセレクト信号を逆転 させる。
【００１７】・以前の処理によって、時刻ｔ0〜ｔm-1の
いずれかの状態に逆転パス が存在した場合、それら全
てを元に戻す。 上記を繰り返し、（vi）において逆転すべきパスが
なかった場合に終了する。
いずれかの状態に逆転パス が存在した場合、それら全
てを元に戻す。 上記を繰り返し、（vi）において逆転すべきパスが
なかった場合に終了する。
【００１８】
【発明が解決しようとする課題】しかしながら、上記先
行発明におけるマルチトレースバックの処理アルゴリズ
ムでは、各トレースバックでは、最終時刻から最初の時
刻ｔ0までの全時刻に渡り、毎回復号データの計算を行
なう必要があり、また、時刻および状態の記憶する条件
も複雑であるため、処理時間が多くかかり、このため、
ハードウェア化において限られた処理時間内でマルチト
レースバックを行なう際には、与えられた許容メトリッ
ク差以内の復号候補が多数存在している場合でも、トレ
ースバックの回数（復号データ数）により処理時間を制
限され、十分な回数のトレースバックが行なえず、その
ために一部の復号候補しか得られないという問題があっ
た。
行発明におけるマルチトレースバックの処理アルゴリズ
ムでは、各トレースバックでは、最終時刻から最初の時
刻ｔ0までの全時刻に渡り、毎回復号データの計算を行
なう必要があり、また、時刻および状態の記憶する条件
も複雑であるため、処理時間が多くかかり、このため、
ハードウェア化において限られた処理時間内でマルチト
レースバックを行なう際には、与えられた許容メトリッ
ク差以内の復号候補が多数存在している場合でも、トレ
ースバックの回数（復号データ数）により処理時間を制
限され、十分な回数のトレースバックが行なえず、その
ために一部の復号候補しか得られないという問題があっ
た。
【００１９】本発明は、このような先行発明の問題を解
決するものであり、より効率的で優れたビタビ復号方法
およびその装置を提供することを目的とするものであ
る。
決するものであり、より効率的で優れたビタビ復号方法
およびその装置を提供することを目的とするものであ
る。
【００２０】
【課題を解決するための手段】本発明は、上記目的を達
成するために、複数の復号候補を再帰法により検索し、
このときトレースバックによりさかのぼる各状態では、
許容メトリック差とその状態で記憶しておいた尤度差と
を比較し、尤度差が許容メトリック差以下の場合には、
その状態は複数のブランチを選択できる状態であるとし
て、その時刻と状態と、またどのブランチを選択してト
レースバックを行なっているかを示す分岐フラグと、さ
らに、許容メトリック差から尤度差を引いた値（残りメ
トリック値）の４つのパラメータを１つの情報としてス
タックメモリに記憶しておき、再帰法により復号する際
に、次のトレースバックでは、１つ前のトレースバック
により通過したパスの内、共通の部分パスの復号結果を
コピー（メモリ転送）して用い、異なる部分パスは、ス
タックメモリに記憶した時刻および状態で新たに分岐
し、その分岐点におけるパスセレクト信号のみを反転さ
せてトレースバックを行なうことにより、残りの部分パ
スの復号データを得るようにしたものである。
成するために、複数の復号候補を再帰法により検索し、
このときトレースバックによりさかのぼる各状態では、
許容メトリック差とその状態で記憶しておいた尤度差と
を比較し、尤度差が許容メトリック差以下の場合には、
その状態は複数のブランチを選択できる状態であるとし
て、その時刻と状態と、またどのブランチを選択してト
レースバックを行なっているかを示す分岐フラグと、さ
らに、許容メトリック差から尤度差を引いた値（残りメ
トリック値）の４つのパラメータを１つの情報としてス
タックメモリに記憶しておき、再帰法により復号する際
に、次のトレースバックでは、１つ前のトレースバック
により通過したパスの内、共通の部分パスの復号結果を
コピー（メモリ転送）して用い、異なる部分パスは、ス
タックメモリに記憶した時刻および状態で新たに分岐
し、その分岐点におけるパスセレクト信号のみを反転さ
せてトレースバックを行なうことにより、残りの部分パ
スの復号データを得るようにしたものである。
【００２１】また、限られた処理時間内でマルチトレー
スバックを行なう際には、従来のようにトレースバック
の回数（復号データ数）により処理時間を制限する方法
に代わり、新たに分岐してトレースバックを行なう部分
パスのブランチ数（パスの長さ）を、スタックメモリに
記憶してある時刻から求めて、その累積値があらかじめ
設定した制限値以下であれば、トレースバックを行なっ
て復号データを出力し、一方、制限値を越えるときは、
トレースバックを行なわずに復号処理を終了することに
より処理時間を制限するようにしたものである。
スバックを行なう際には、従来のようにトレースバック
の回数（復号データ数）により処理時間を制限する方法
に代わり、新たに分岐してトレースバックを行なう部分
パスのブランチ数（パスの長さ）を、スタックメモリに
記憶してある時刻から求めて、その累積値があらかじめ
設定した制限値以下であれば、トレースバックを行なっ
て復号データを出力し、一方、制限値を越えるときは、
トレースバックを行なわずに復号処理を終了することに
より処理時間を制限するようにしたものである。
【００２２】
【作用】したがって、本発明によれば、限られた処理時
間内でより多くの復号データ候補を求めることができ、
より効率的かつ優れた誤り訂正復号を行なうことができ
る。
間内でより多くの復号データ候補を求めることができ、
より効率的かつ優れた誤り訂正復号を行なうことができ
る。
【００２３】
【実施例】図１は本発明の一実施例におけるビタビ復号
化装置の構成を示すものである。図１において、１はビ
タビ復号化装置、２はメトリック計算回路、３はＡＣＳ
回路、４はパスセレクト記憶回路、５はパスメトリック
記憶回路、６はマルチトレースバック回路、７はスタッ
クメモリである。
化装置の構成を示すものである。図１において、１はビ
タビ復号化装置、２はメトリック計算回路、３はＡＣＳ
回路、４はパスセレクト記憶回路、５はパスメトリック
記憶回路、６はマルチトレースバック回路、７はスタッ
クメモリである。
【００２４】ビタビ復号化装置１では、受信データ列か
らメトリック計算回路２において、各部分パス（ブラン
チ）の尤度（メトリック）を計算する。次に、ＡＣＳ回
路３において、各時刻の各状態に遷移する複数のパスの
メトリックを比較して、パスセレクト記憶回路４に、メ
トリックの最も高いパスを選択してそのパスセレクト信
号を記憶するだけでなく、他のパスとのメトリック差を
も同時に記憶する。また、通常のビタビ復号と同様に、
パスメトリック記憶回路５において、パスメトリックの
記憶・更新も行なうものとする。そして、パスセレクト
記憶回路４の情報を基に、マルチトレースバック回路６
およびスタックメモリ７によって、トレースバックを行
なう。この場合、与えられる許容メトリック差によって
は、生き残りパスがただ１個となるとは限らず、図２に
示すように、一般には複数回のトレースバックにより、
複数個のパスが生き残る。
らメトリック計算回路２において、各部分パス（ブラン
チ）の尤度（メトリック）を計算する。次に、ＡＣＳ回
路３において、各時刻の各状態に遷移する複数のパスの
メトリックを比較して、パスセレクト記憶回路４に、メ
トリックの最も高いパスを選択してそのパスセレクト信
号を記憶するだけでなく、他のパスとのメトリック差を
も同時に記憶する。また、通常のビタビ復号と同様に、
パスメトリック記憶回路５において、パスメトリックの
記憶・更新も行なうものとする。そして、パスセレクト
記憶回路４の情報を基に、マルチトレースバック回路６
およびスタックメモリ７によって、トレースバックを行
なう。この場合、与えられる許容メトリック差によって
は、生き残りパスがただ１個となるとは限らず、図２に
示すように、一般には複数回のトレースバックにより、
複数個のパスが生き残る。
【００２５】図２の場合は、
【００２６】
【数１】
【００２７】の６個のパスが生き残りパスとして、マル
チトレースバック回路６において、これら複数パスをト
レースバックして複数の復号データを得る。
チトレースバック回路６において、これら複数パスをト
レースバックして複数の復号データを得る。
【００２８】図３および図４は、本実施例におけるマル
チトレースバック回路６の処理アルゴリズムの一例を示
す。この例では、図８のトレリス線図のように１状態か
ら２本のパスが出ている場合を示している。
チトレースバック回路６の処理アルゴリズムの一例を示
す。この例では、図８のトレリス線図のように１状態か
ら２本のパスが出ている場合を示している。
【００２９】まず、ステップ１０の初期化処理におい
て、スタックメモリ、スタックメモリアドレス、許容メ
トリック差、トレースバック（ＴＢ）ブランチ数カウン
タ、ＴＢカウンタ、および状態の初期化を行なう。そし
て、時刻ｔｎを初期化し（ステップ１１）、以後トレー
スバック処理を行なう。その状態におけるパスセレクト
信号およびメトリック差をパスセレクト記憶回路４から
読み出し（ステップ１２）、許容セレクト差と比較し
（ステップ１３）、メトリック差が許容メトリック差以
下であれば、スタックメモリ７に記憶し（ステップ１
４）、アドレスの更新を行なう（ステップ１５）。この
ときのスタックメモリ７に記憶される１情報（４パラメ
ータ）の１例を図５に示す。
て、スタックメモリ、スタックメモリアドレス、許容メ
トリック差、トレースバック（ＴＢ）ブランチ数カウン
タ、ＴＢカウンタ、および状態の初期化を行なう。そし
て、時刻ｔｎを初期化し（ステップ１１）、以後トレー
スバック処理を行なう。その状態におけるパスセレクト
信号およびメトリック差をパスセレクト記憶回路４から
読み出し（ステップ１２）、許容セレクト差と比較し
（ステップ１３）、メトリック差が許容メトリック差以
下であれば、スタックメモリ７に記憶し（ステップ１
４）、アドレスの更新を行なう（ステップ１５）。この
ときのスタックメモリ７に記憶される１情報（４パラメ
ータ）の１例を図５に示す。
【００３０】そして、１時刻前の状態の計算（ステップ
１６）と、復号データの計算・格納（ステップ１７）を
した上で、時刻の変更（ステップ１８）をして、さらに
さかのぼるかの判断（ステップ１９）を行なう。ここで
１回のトレースバックが終了したと判断されると、スタ
ックメモリ７に情報が記憶されているかを見て（ステッ
プ２０）、ない場合は終了し（ステップ２９）、また、
ある場合は最上位アドレス（最後に記憶したアドレス）
の１情報の分岐フラグを判断し（ステップ２１）、
“１”であれば最上位アドレスの１情報を消去、アドレ
スを１減らして（ステップ３０）、再びステップ２０へ
戻る。一方、分岐フラグが“０”の場合は、その１情報
のその他のパラメータを読み出し、残りメトリック値を
許容メトリック差として（ステップ２２）、分岐フラグ
は０から１に変換した上で、その更新された１情報を再
びスタックメモリ７に記憶しておく（ステップ２３）。
１６）と、復号データの計算・格納（ステップ１７）を
した上で、時刻の変更（ステップ１８）をして、さらに
さかのぼるかの判断（ステップ１９）を行なう。ここで
１回のトレースバックが終了したと判断されると、スタ
ックメモリ７に情報が記憶されているかを見て（ステッ
プ２０）、ない場合は終了し（ステップ２９）、また、
ある場合は最上位アドレス（最後に記憶したアドレス）
の１情報の分岐フラグを判断し（ステップ２１）、
“１”であれば最上位アドレスの１情報を消去、アドレ
スを１減らして（ステップ３０）、再びステップ２０へ
戻る。一方、分岐フラグが“０”の場合は、その１情報
のその他のパラメータを読み出し、残りメトリック値を
許容メトリック差として（ステップ２２）、分岐フラグ
は０から１に変換した上で、その更新された１情報を再
びスタックメモリ７に記憶しておく（ステップ２３）。
【００３１】そして、トレースバック（ＴＢ）されるブ
ランチ数の累積値を計算し（ステップ２４）、制限数以
下であれば、ＴＢカウンタを増やし（ステップ２６）、
分岐点までの復号データは１つ前の復号データからコピ
ーし（ステップ２７）、さらにその分岐点の状態におけ
るパスセレクト信号を反転された（ステップ２８）上
で、ステップ１６に戻ってトレースバックを行なう。一
方、制限数を越える場合は、処理直が足りないと判断し
て、復号処理を終了（ステップ２９）する。
ランチ数の累積値を計算し（ステップ２４）、制限数以
下であれば、ＴＢカウンタを増やし（ステップ２６）、
分岐点までの復号データは１つ前の復号データからコピ
ーし（ステップ２７）、さらにその分岐点の状態におけ
るパスセレクト信号を反転された（ステップ２８）上
で、ステップ１６に戻ってトレースバックを行なう。一
方、制限数を越える場合は、処理直が足りないと判断し
て、復号処理を終了（ステップ２９）する。
【００３２】上記した処理アルゴリズムの例では、ＴＢ
ブランチ数により処理時間の制限を与えているが、処理
時間ではなく復号データ数で制限したいときは、ステッ
プ２６で復号データ数をモニタしているので、予め設定
された復号データ数になったら処理を終了することで、
容易に制限できることは明らかである。
ブランチ数により処理時間の制限を与えているが、処理
時間ではなく復号データ数で制限したいときは、ステッ
プ２６で復号データ数をモニタしているので、予め設定
された復号データ数になったら処理を終了することで、
容易に制限できることは明らかである。
【００３３】図３および図４の処理アルゴリズムによっ
て、マルチトレースバックを行なうときのスタックメモ
リ７の変化の一例を図６に示す。この図は、トレースバ
ックするパスが（ａ）から（ｅ）に移って行くときのス
タックメモリ７の変化を示している。ここでは、許容メ
トリック差を５とし、黒点の状態において、メトリック
差（図中で＋ｘで表示、数字のあるパス方が尤度が低い
とする）の累計が許容メトリック差以下であるとして、
スタックメモリ７に記憶されている。
て、マルチトレースバックを行なうときのスタックメモ
リ７の変化の一例を図６に示す。この図は、トレースバ
ックするパスが（ａ）から（ｅ）に移って行くときのス
タックメモリ７の変化を示している。ここでは、許容メ
トリック差を５とし、黒点の状態において、メトリック
差（図中で＋ｘで表示、数字のあるパス方が尤度が低い
とする）の累計が許容メトリック差以下であるとして、
スタックメモリ７に記憶されている。
【００３４】例えば（ａ）のパスでは、時刻Ｎ−２にお
いてのみ、尤度の低い方を選択しているので、時刻Ｎ−
２のスタックメモリの分岐フラグが１になっている。ト
レースバックが時刻Ｎ−７において、（ｂ）のパスの方
に分岐した場合は、時刻Ｎ−７で尤度の低いパスを選択
しているので、その時刻の選択フラグが１になる。
（ｃ）の方に分岐する場合は、時刻Ｎ−７の情報は一旦
消去され、時刻Ｎ−６の選択フラグが１になり、時刻Ｎ
−７で新たに記憶されている。この情報は（ｄ）の方の
ＴＢが行なう際には、分岐フラグが１になるのは上記の
アルゴリズムから明らかである。
いてのみ、尤度の低い方を選択しているので、時刻Ｎ−
２のスタックメモリの分岐フラグが１になっている。ト
レースバックが時刻Ｎ−７において、（ｂ）のパスの方
に分岐した場合は、時刻Ｎ−７で尤度の低いパスを選択
しているので、その時刻の選択フラグが１になる。
（ｃ）の方に分岐する場合は、時刻Ｎ−７の情報は一旦
消去され、時刻Ｎ−６の選択フラグが１になり、時刻Ｎ
−７で新たに記憶されている。この情報は（ｄ）の方の
ＴＢが行なう際には、分岐フラグが１になるのは上記の
アルゴリズムから明らかである。
【００３５】
【発明の効果】本発明は、上記実施例から明らかなよう
に、マルチトレースバックを行なう際に、複数の候補を
再帰法により検索し、このときトレースバックによりさ
かのぼる各状態において、許容メトリック差とその状態
で記憶しておいた尤度差とを比較し、尤度差が許容メト
リック差以下の場合には、複数のブランチを選択できる
状態であるとして、その状態の時刻と状態とどのブラン
チを選択してトレースバックを行なっているかを示す分
岐フラグと、許容メトリック差から尤度差を引いた値と
をスタックメモリに記憶しておき、再帰法により復号す
る際に、次のトレースバックでは、１つ前のトレースバ
ックにより通過したパスの復号データの内、共通の部分
パスの復号結果をコピーして用い、異なる部分パスは、
スタックメモリに記憶された時刻および状態等から新た
に分岐し、その分岐点におけるパスセレクト信号のみを
反転させてトレーはバックを行なうことにより、残りの
部分パスの復号データを得るようにしたので、ビタビ復
号において複数のパスを生き残りとし複数の復号データ
候補を求める際に、処理時間を縮小できるという効果を
有する。
に、マルチトレースバックを行なう際に、複数の候補を
再帰法により検索し、このときトレースバックによりさ
かのぼる各状態において、許容メトリック差とその状態
で記憶しておいた尤度差とを比較し、尤度差が許容メト
リック差以下の場合には、複数のブランチを選択できる
状態であるとして、その状態の時刻と状態とどのブラン
チを選択してトレースバックを行なっているかを示す分
岐フラグと、許容メトリック差から尤度差を引いた値と
をスタックメモリに記憶しておき、再帰法により復号す
る際に、次のトレースバックでは、１つ前のトレースバ
ックにより通過したパスの復号データの内、共通の部分
パスの復号結果をコピーして用い、異なる部分パスは、
スタックメモリに記憶された時刻および状態等から新た
に分岐し、その分岐点におけるパスセレクト信号のみを
反転させてトレーはバックを行なうことにより、残りの
部分パスの復号データを得るようにしたので、ビタビ復
号において複数のパスを生き残りとし複数の復号データ
候補を求める際に、処理時間を縮小できるという効果を
有する。
【図１】本発明の一実施例におけるビタビ復号化装置の
ブロック図
ブロック図
【図２】本実施例における複数の生き残りパスの一例を
示す模式図
示す模式図
【図３】本実施例におけるマルチトレースバックの処理
アルゴリズムの一例を示すフロー図
アルゴリズムの一例を示すフロー図
【図４】同処理アルゴリズムの続きを示すフロー図
【図５】本実施例におけるマルチトレースバック処理に
おけるスタックメモリへの格納の一例を示す模式図
おけるスタックメモリへの格納の一例を示す模式図
【図６】本実施例におけるマルチトレースバック処理に
おけるスタックメモリの変化の一例を示す模式図
おけるスタックメモリの変化の一例を示す模式図
【図７】従来例における誤り訂正符号化回路の一例を示
すブロック図
すブロック図
【図８】従来例におけるトレリス線図の一例を示す模式
図
図
【図９】従来例における再合流する２本の部分パスの一
例を示す模式図
例を示す模式図
１ ビタビ復号化装置 ２ メトリック計算回路 ３ ＡＣＳ回路 ４ パスセレクト記憶回路 ５ パスメトリック記憶回路 ６ マルチトレースバック回路 ７ スタックメモリ
───────────────────────────────────────────────────── フロントページの続き (58)調査した分野(Int.Cl.7，ＤＢ名) H03M 13/00 H04L 1/00 H04L 25/00
Claims (3)
- 【請求項１】 ＡＣＳ（Ａdd Ｃompare Ｓelect）演算
において各状態で生き残りパスの選択をする際に、最も
尤度の高いパスを一つだけ選択してそのパスセレクト信
号を記憶するだけでなく、最も尤度の高いパスとその他
のパスとの尤度差も合わせて記憶しておき、トレースバ
ックにより復号データを求める際に、最尤度復号パスだ
けでなく、最尤パスのトレースバック区間での尤度との
間で、あらかじめ設定したしきい値である許容メトリッ
ク差以下の尤度となるパスについて、それぞれトレース
バックを行なって複数の復号パス候補を得るマルチトレ
ースバックを行なうとともに、前記マルチトレースバッ
クを行なう際に、複数の候補を再帰法により検索し、こ
のときトレースバックによりさかのぼる各状態におい
て、許容メトリック差とその状態で記憶しておいた尤度
差とを比較し、尤度差が許容メトリック差以下の場合に
は、複数のブランチを選択できる状態であるとして、そ
の状態の時刻と状態とどのブランチを選択してトレース
バックを行なっているかを示す分岐フラグと、さらに許
容メトリック差から尤度差を引いた値とをスタックメモ
リに記憶しておき、再帰法により復号する際に、次のト
レースバックでは、１つ前のトレースバックにより通過
したパスの復号データの内、共通の部分パスの復号結果
をコピーして用い、異なる部分パスは、スタックメモリ
に記憶された時刻および状態から新たに分岐し、その分
岐点におけるパスセレクト信号のみを反転させてトレー
スバックを行なうことにより、残りの部分パスの復号デ
ータを得ることを特徴とするビタビ復号方法。 - 【請求項２】 １つ前のトレースバックにより通過した
パスの復号データの内、その共通部分の復号結果をコピ
ーまたはメモリ転送して用い、異なる部分は、分岐点に
おけるパスセレクト信号のみを反転させてトレースバッ
クを行なう際、トレースバックを行なうブランチ数また
はパスの長さをスタックメモリに記憶してある時刻から
求め、そのブランチ数の累積値があらかじめ設定した制
限値以下であれば、トレースバックを行ない、制限値を
越えるときはトレースバックを行なわずに復号処理を終
了することを特徴とする請求項１記載のビタビ復号方
法。 - 【請求項３】 受信データ列から各部分パスの尤度を計
算するメトリック計算手段と、各時刻の各状態に遷移す
る複数のパスのメトリックを比較する手段と、メトリッ
クの最も高いパスを選択してその信号を記憶するだけで
なく、他のパスとのメトリック差をも同時に記憶するパ
スセレクト記憶手段と、パスメトリックの記憶・更新を
行なうパスメトリック記憶手段と、前記パスセレクト記
憶手段の情報を基に、請求項１または２記載のマルチト
レースバックを行なうマルチトレースバック手段と、マ
ルチトレースバックに必要な情報を記憶するスタックメ
モリとを備えたビタビ復号化装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP07709994A JP3235333B2 (ja) | 1994-04-15 | 1994-04-15 | ビタビ復号方法およびビタビ復号化装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP07709994A JP3235333B2 (ja) | 1994-04-15 | 1994-04-15 | ビタビ復号方法およびビタビ復号化装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH07288478A JPH07288478A (ja) | 1995-10-31 |
| JP3235333B2 true JP3235333B2 (ja) | 2001-12-04 |
Family
ID=13624349
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP07709994A Expired - Fee Related JP3235333B2 (ja) | 1994-04-15 | 1994-04-15 | ビタビ復号方法およびビタビ復号化装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP3235333B2 (ja) |
Families Citing this family (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6452985B1 (en) * | 1998-03-18 | 2002-09-17 | Sony Corporation | Viterbi decoding apparatus and Viterbi decoding method |
| US7197689B2 (en) * | 2002-10-30 | 2007-03-27 | Nxp B.V. | Trellis-based receiver |
-
1994
- 1994-04-15 JP JP07709994A patent/JP3235333B2/ja not_active Expired - Fee Related
Non-Patent Citations (1)
| Title |
|---|
| １９９３年電子情報通信学会春季大会講演論文集、第２−３０３頁；Ｂ−３０２ ビタビ復号におけるマルチトレースバックの導入 |
Also Published As
| Publication number | Publication date |
|---|---|
| JPH07288478A (ja) | 1995-10-31 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US4606027A (en) | Error correction apparatus using a Viterbi decoder | |
| US6148431A (en) | Add compare select circuit and method implementing a viterbi algorithm | |
| US5802116A (en) | Soft decision Viterbi decoding with large constraint lengths | |
| US6272661B1 (en) | Minimum memory implementation of high speed viterbi decoder | |
| JPS6037834A (ja) | 誤り訂正符号の復号方法および復号器 | |
| JP2007510337A (ja) | 移動通信システムのビタビ／ターボ統合デコーダ | |
| KR20020048975A (ko) | 비터비 디코더 용 고속 ａｃｓ 유닛 | |
| JP3233847B2 (ja) | ビタビ復号方法及びビタビ復号回路 | |
| US8489972B2 (en) | Decoding method and decoding device | |
| JP3235333B2 (ja) | ビタビ復号方法およびビタビ復号化装置 | |
| KR100262303B1 (ko) | 비터비알고리즘을적용하는복호과정에서의생존경로역추적방법및그장치 | |
| EP1024603A2 (en) | Method and apparatus to increase the speed of Viterbi decoding | |
| US6578119B2 (en) | Method and device for memory management in digital data transfer | |
| US7231586B2 (en) | Multi-rate viterbi decoder | |
| JP2591332B2 (ja) | 誤り訂正復号装置 | |
| JPH05335973A (ja) | ビタビ復号器及び畳み込み符号の復号器 | |
| JPWO2005117272A1 (ja) | ビタビ復号装置、およびビタビ復号方法 | |
| JPH10200419A (ja) | ビタビ復号方法および装置 | |
| JP3337950B2 (ja) | 誤り訂正復号化方法及び誤り訂正復号化装置 | |
| JP5370487B2 (ja) | 復号方法および復号装置 | |
| JP2551027B2 (ja) | 逐次復号方法及び装置 | |
| JP3269845B2 (ja) | ヴィタビ復号器 | |
| JPH0510850B2 (ja) | ||
| JP3229047B2 (ja) | ビタビ復号器 | |
| JPH0746145A (ja) | 演算装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| LAPS | Cancellation because of no payment of annual fees |