(57)【要約】【課題】軟判定ビタビ復号装置において、トリレス線図における１つのノードに合流する２つの枝の枝尤度（ユークリッド距離）の演算に必須の乗算器の数を減らし、回路規模および消費電力を削減すること。【解決手段】正確な枝尤度を計算する前に、状態尤度大小判定部１０１で、近似計算による暫定の枝尤度を求め（近似演算部１０）、暫定の状態尤度の大小を比較し（大小判定部２０）、生き残る枝を検出する。そして、生き残る枝についての情報をセレクタ３０８ａ〜３０８ｃで選択して枝尤度計算部９０に供給し、生き残る枝についてのみ正確な枝尤度を算出し、加算器１０７により、その枝尤度に直前の状態尤度を加算して状態尤度〈更新値〉を求める。【選択図】      図１
2004235698.tif 000002
【特許請求の範囲】
【請求項１】
トリレス線図における各内部状態に合流する２つの枝〈ブランチ〉の少なくとも一方の枝尤度（ブランチメトリック）を、受信データ系列と送信データ系列（枝尤度期待値）との間のユークリッド距離を算出することにより求め、求められた枝の枝尤度を、その内部状態に至る過去の各枝の枝尤度と合算することによって状態尤度（ステートメトリック）を更新し、所定長までの各内部状態における最尤の枝を選択することによって受信した符号を復号する軟判定ビタビ復号方法であって、
前記トリレス線図における各内部状態に合流する２つの枝について、まず、近似計算を行って暫定の状態尤度を求め、それらの大小判定を行って生き残る枝を決定するステップと、
生き残る枝のみについての枝尤度を算出し、算出された前記枝尤度を用いて更新された状態尤度を計算するステップと、
を有することを特徴とする軟判定ビタビ復号方法。
【請求項２】
請求項１に記載の方法を実行する軟判定ビタビ復号装置であって、
トリレス線図における各内部状態に合流する２つの枝について、近似計算を行って暫定の状態尤度を求め、それらの大小判定を行って生き残る枝を決定する状態尤度の大小判定部と、
生き残る枝のみについての枝尤度を算出し、算出された前記枝尤度に基づいて更新された状態尤度をする状態尤度計算部と、
を有することを特徴とする軟判定ビタビ復号装置。
【請求項３】
請求項２において、
前記状態尤度の大小判定部は、前記暫定の状態尤度を求めるために、整数部の自乗値表を内蔵する参照テーブルと、整数部と小数部の積を求める手段と、前記整数部の自乗値および前記整数部と小数部の積を加算する手段と、を有することを特徴とする軟判定ビタビ復号装置。
【請求項４】
請求項３において、
前記整数部と小数部の積を求める手段は、整数部と小数部の積をビットシフト演算および加算演算により生成することを特徴とする軟判定ビタビ復号装置。
【請求項５】
請求項３において、
前記状態尤度の大小判定部は、前記参照テーブルと、前記整数部と小数部の積を求める手段と、前記整数部の自乗値および整数部と小数部の積を加算する手段の各々を、時分割で使用することを特徴とする軟判定ビタビ復号装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、軟判定ビタビ復号方法および装置に関する。
【０００２】
【従来の技術】
ビタビ復号では、ビタビアルゴリズムに基づき、送信側エンコーダで生成され得る符号系列の中から、受信符号系列に最も近い系列を選択することにより、受信符号を復号する。
【０００３】
ビタビ復号は、通信路で生じるランダム誤りに対する訂正能力が高く、特に、軟判定復調方式と組み合わせると、大きな復号利得を得ることができる。
【０００４】
ビタビ復号器の内部状態の遷移は、トリレス線図により表される。図６に例示されるように、各状態では、１つのノードに必ず２つの枝（ブランチ）が合流する。
【０００５】
図６では、時刻ｔ１１（状態Ｐ１）の一番上のノードには、時刻ｔ１０（状態ｔ０）における２つのノードからの枝が合流している。ここでは、上側の枝を偶数側の枝とし、下側の枝を奇数側の枝とする。どちらの枝を選択するかは、状態尤度（ステートメトリック）を比較して決定される。
【０００６】
状態尤度は、そのノードに至るまでの全部の枝の枝尤度（ブランチメトリック）を合算することで求められる。
【０００７】
図６において、Ｋ１，Ｋ２は枝尤度（ブランチメトリック）を表しており、Ｓ０，Ｔ０，Ｕ０，Ｖ０，Ｓ１，Ｔ１・・・は、各ノードにおける状態尤度（ステートメトリック）を表す。
【０００８】
例えば、（Ｓ０＋Ｋ１）＜（Ｕ０＋Ｋ２）ならば、２つの枝のうちの上側の枝が選択され（つまり、上側の枝が生き残る枝となり）、時刻ｔ１１の一番上のノードについての状態尤度Ｓ１＝Ｓ０＋Ｋ１となる。
【０００９】
所定長までの各状態の各ノードの状態尤度を求め、最後に、トレースバック処理を実行する（すなわち、各状態の中で最も尤度の高い枝のみを選んでいく作業を実行する）ことにより、最も確からしいパスが選択され、このパス情報に基づき、受信符号が復号される。
【００１０】
硬判定ビタビ復号では、枝尤度（ブランチメトリック）は、送信符号系列と受信符号系列との間のハミング距離を計算することにより求められ、一方、軟定ビタビ復号では、枝尤度は、ユークリッド距離を計算することにより求められる。
【００１１】
図７に、ユークリッド距離の算出例を示す。
【００１２】
図７では、ＱＰＳＫ変調信号を復調する場合を想定している。ここで、Ｉ，Ｑの位相平面における、復調された受信信号の座標をＰ（ｘ，ｙ）とする。また、Ａ，Ｂ，Ｃ，Ｄの各点は、送信信号系列の符号の座標（軟判定復号の期待値）を示している。
【００１３】
図中、ｒ０〜ｒ３がユークリッド距離を示している。ユークリッド距離は、三平方の定理を用いて幾何学的に求められる。２点間のＩ成分，Ｑ成分の差を、ｘ１，ｘ２，ｙ１，ｙ２とする。例えば、ｒ０２＝ｘ１２＋ｙ１２となる。
【００１４】
図８に、本発明の発明者によって検討されたビタビ復号装置の構成を示す。
【００１５】
ＱＰＳＫ復調器７００の復調信号は、枝尤度計算部５０２に入力される。枝尤度計算部５０２は、図６に示されるような、１つのノードに合流する２つの枝（偶数側の枝と奇数側の枝）のそれぞれについて枝尤度を計算する。
【００１６】
図８の枝尤度計算部５０２の上半分が偶数側の枝尤度を計算する部分であり、下半分が奇数側の枝尤度を計算する部分である。
【００１７】
枝尤度は、復調信号と期待値〈図７のＡ〜Ｄの各点の座標〉との差を、減算器（６０１ａ〜６０１ｄ）を用いて計算し、各減算器の出力の自乗値を、乗算器（６０２ａ〜６０２ｄ）を用いて計算し、自乗値同士を加算器（６０３ａ，６０３ｂ）を用いて加算することにより求められる。
【００１８】
ＡＣＳ演算部５０３は、求められた枝尤度を、直前の状態尤度（過去の枝尤度を合算したもの）に加算して更新された状態尤度を求め、２つの状態尤度を比較して、値が小さい方の枝を選択する。枝尤度を直前の状態尤度を加算する処理は、加算器６０４ａ，６０４ｂにより行われ、状態尤度同士の比較は比較器６０５により行われ、生き残るパスについての状態尤度を選択する処理はセレクタ６０６により行われる。
【００１９】
セレクタ６０６から出力される状態尤度は、状態尤度メモリ５０４およびパスメモリ５０５に蓄積される。状態尤度メモリ５０４は小容量のメモリであり、更新された状態尤度が上書きされて一時的に記憶される。一方、パスメモリ５０５は、各状態尤度をすべて記録していく。
【００２０】
そして、所定長の処理を行った後、トレースバック処理部５０６がパスメモリ５０５に記録された情報を読み出し、各状態における最尤の枝を選択していくことにより、一本の生き残りパスが決定され、これによって、誤り訂正復号がなされる。
【００２１】
軟判定ビタビ復号装置の具体的な構成は、下記特許文献１に記載されている。
【００２２】
【特許文献１】
特開２０００−２２４０５０号公報（図１１等）
【００２３】
【発明が解決しようとする課題】
軟判定ビタビ復号では、ユークリッド距離を求める必要があり、このためには自乗演算が必須である。また、軟判定は、要するにアナログ量（位相偏移量）に基づく精度の高い処理であり、小数点を含むデータの処理が必要であることから、高精度の自乗演算を行うことは、回路の負担を増大させる。
【００２４】
しかも、上述のとおり、１つのノードに合流する２つの枝（偶数側および奇数側の枝）について枝尤度を計算する必要がある。
【００２５】
ここで、処理の高速化を図るために、状態尤度の計算を偶数側／奇数側の両方を同時に実施する構成（図８）をとった場合、大規模な乗算器を複数個搭載する必要があり、回路規模、消費電力が増大する。
【００２６】
本発明は、かかる点に鑑みてなされたものであり、その目的は、ビタビ復号装置の回路規模および消費電力の削減を実現することにある。
【００２７】
【課題を解決するための手段】
従来の軟判定ビタビ復号では、１つのノードに合流する２つの枝の各々について枝尤度を計算し、状態尤度を計算し、状態尤度を比較して１つの枝を選択するという処理手順となる。
【００２８】
見方を変えると、選択されなかった方の枝の枝尤度は、その後、何も利用されることなく捨てられるということである。つまり、せっかく高精度の演算を行って枝尤度を計算しても、一方の枝尤度は捨てられるのであるから、この点で無駄が多いといえる。
【００２９】
一方、どちらの枝を選択するかは、２つの状態尤度の大小関係だけで決まるため、要するに、２つの値の大小だけ判定できればよく、小数点を含めた正確な値自体は不要である。
【００３０】
本発明の軟判定ビタビ復号方法では、これらの点に着目し、まず、状態尤度の近似計算〈精度の荒い簡易な計算〉を行って暫定的な状態尤度を算出し、大小比較をして生き残る枝を先に決定し、その後、その生き残る枝のみについて、枝尤度を正確に求め、高精度な状態尤度を算出する、という手順とする。
【００３１】
この方法によれば、状態尤度の近似計算は、乗算器を使用せずに行うことができる。
【００３２】
したがって、乗算器は、生き残る枝についての枝尤度計算のみで使用すればよいため、乗算器の数を減らすことができる。よって、回路規模や消費電力の削減が実現される。
【００３３】
すなわち、本発明の軟判定ビタビ復号方法では、トリレス線図における各内部状態に合流する２つの枝について、まず、近似計算を行って暫定の状態尤度を求め、それらの大小判定を行って生き残る枝を決定するステップと、生き残る枝のみについての枝尤度を算出し、算出された前記枝尤度を用いて更新された状態尤度を計算するステップと、を有する。
【００３４】
また、本発明のビタビ復号装置は、トリレス線図における各内部状態に合流する２つの枝について、近似計算を行って暫定の状態尤度を求め、それらの大小判定を行って生き残る枝を決定する状態尤度の大小判定部と、生き残る枝のみについての枝尤度を算出し、算出された前記枝尤度に基づいて更新された状態尤度をする状態尤度計算部と、を有する。
【００３５】
この構成により、高速性を重視して偶数側／奇数側の状態尤度を同時に計算する場合でも、従来、最低で４つの乗算器が必要であったものが、尤度の高い状態尤度のみを計算するため、乗算器は最低２つあればよいことになる。大規模ロジックである乗算器が半減することにより、回路規模を削減することができる。また、状態尤度の更新動作は頻繁に発生するが、乗算器が半減することによって、消費電力の削減も図ることができる。
【００３６】
また、本発明の軟判定ビタビ復号装置の一つの態様では、状態尤度の大小判定部は、前記暫定の状態尤度を求めるために、整数部の自乗値表を内蔵する参照テーブルと、整数部と小数部の積を求める手段と、前記整数部の自乗値および前記整数部と小数部の積を加算する手段とを有する。
【００３７】
この構成によれば、あらかじめ整数値の自乗値をテーブル化しておくことで自乗演算を省略することが可能となり、乗算器が不要となるため回路規模を削減することができる。
【００３８】
また、本発明の軟判定ビタビ復号装置の他の態様では、前記整数部と小数部の積を求める手段は、整数部と小数部の積をビットシフト演算および加算演算により生成する。
【００３９】
この構成によれば、自乗対象データを整数部と小数部に分割し、自乗演算を整数部の自乗値表とシフタ、および少数の加算器で構成することが可能となることで、乗算器が不要となるため回路規模を削減することができる。
【００４０】
また、本発明の軟判定ビタビ復号装置の他の態様では、前記状態尤度の大小判定部は、前記参照テーブルと、前記整数部と小数部の積を求める手段と、前記整数部の自乗値および整数部と小数部の積を加算する手段の各々を、時分割で使用する。
【００４１】
この構成によれば、整数部の自乗表、整数部と小数部の積演算器を時分割で共有することにより回路規模を削減することができる。
【００４２】
【発明の実施の形態】
（実施の形態１）
図１は、本発明の実施の形態１に係る軟判定ビタビ復号装置の全体構成を示すブロック図である。
【００４３】
この軟判定ビタビ復号装置は、状態尤度大小判定部１０１と、状態尤度計算部１０２と状態尤度メモリ１０３と、パスメモリ１２０と、トレースバック処理部１２１と、を有する。全体の基本的な動作は図８の装置と同じである。
【００４４】
ただし、図１の軟判定ビタビ復号装置では、状態尤度大小判定部１０１は、近似演算を行って暫定の枝尤度を算出する近似演算部１０と、暫定的な状態尤度（暫定の枝尤度を直前の状態尤度に加算することで求められる）の大小を判定する大小判定部２０と、生き残る枝に関する情報（枝尤度期待値および直前の状態尤度の情報）を選択して出力するセレクタ３０８ａ〜３０８ｃと、を有している。
【００４５】
また、状態尤度計算部１０２は、受信データと枝尤度期待値との差を自乗演算するための乗算器１０４，１０５と、偶数側／奇数側の状態尤度値を加算する加算器１０６と、前状態における状態尤度値を加算する加算器１０７と、を具備している。
【００４６】
なお、乗算器１０４，１０５および加算器１０６は、枝尤度計算部９０を構成する。
【００４７】
図１の軟判定ビタビ復号装置の特徴的な動作を、図２に示す。
【００４８】
すなわち、本実施の形態のビタビ復号装置では、まず、近似計算を行って、生き残る枝を検出する（ステップ２００）。次に、生き残る枝についてのみ、正確な枝メトリックを計算する（ステップ２０１）。
【００４９】
そして、先の状態尤度に、求められた枝尤度を加算して、状態尤度（更新値）を求める（ステップ２０２）。
【００５０】
これにより、図１の軟判定ビタビ復号装置では、高速性を重視して偶数側／奇数側の状態尤度を同時に計算しつつ、従来（図８）では最低で４つの乗算器が必要であったものが、尤度の高い状態尤度のみを計算するため、乗算器は最低２つでよく、乗算器の数が半減される。
【００５１】
大規模ロジックである乗算器が半減することにより、回路規模を削減することができる。また、消費電力の削減も図ることができる。
【００５２】
（実施の形態２）
図３は、本発明の軟判定ビタビ復号装置における状態尤度大小判定部の具体的な構成例を示すブロック図である。
【００５３】
図３の状態尤度大小判定部１０１は、受信データと枝尤度期待値との差を求める加算器３０１と、暫定的な状態尤度〈仮の状態尤度〉を求める整数部自乗値テーブル（ＬＵＴ）３０２  と、整数と小数の積を求める整数対小数積演算部３０３と、整数部自乗値テーブルと整数対小数積演算部の出力値を加算する加算器３０４と、加算器３０４の出力と前状態（直前の状態）における状態尤度とを加算する加算器３０５と、状態尤度の偶数側／奇数側を比較する加算器３０７（この加算器３０７が、暫定的な状態尤度の大小判定器として機能する）と、選択された枝についての情報（受信データ、枝尤度期待値および状態尤度）を選択する選択部３０８（３つのセレクタ３０８ａ〜３０８ｃを具備する）と、を具備する。
【００５４】
この構成によれば、偶数側／奇数側のユークリッド距離を計算するための自乗計算を乗算器を使用せず、整数部自乗値テーブルと整数対小数積演算部により仮の状態尤度値を計算し、大小判定を行うことで、乗算器を効果的に削減することができる。また、回路構成が比較的簡単であり、実現が容易である。
【００５５】
図３の状態尤度大小判定部１０１の具体的な動作を図４に示す。
【００５６】
受信データ（Ｒ）と枝尤度期待値（Ｅ）および前状態における状態尤度（Ｐ）が入力される。
【００５７】
まず、受信データと枝尤度期待値のユークリッド距離を求めるために『受信データ（Ｒ）−枝尤度期待値（Ｅ）』を計算する（ステップ２１０）。
【００５８】
この受信データおよび枝尤度期待値（Ｅ）を１２ビットデータとし、また、ビット［１１］を符号ビットとし、ビット［１０：８］を整数部とする。また、ビット［７：０］を小数部とする。
【００５９】
受信データ（Ｒ）−枝尤度期待値（Ｅ）も１２ｂｉｔデータであり、Ｒ−Ｅ＝Ｉｎｔ＋Ｄｅｃ（Ｉｎｔ：整数，Ｄｅｃ：０≦Ｄｅｃ＜１）である。
【００６０】
本来、ユークリッド距離を求めるために、Ｒ−Ｅの自乗値を計算する。しかし、本実施の形態では、以下の近似演算を行う〈ステップ２１１〜２１３〉。
（Ｒ−Ｅ）２  ＝  （Ｉｎｔ＋Ｄｅｃ）２
＝（Ｉｎｔ）２＋２・（Ｉｎｔ）・（Ｄｅｃ）＋（Ｄｅｃ）２
≒（Ｉｎｔ）２＋２・（Ｉｎｔ）・（Ｄｅｃ）      ∵  （Ｄｅｃ）２≪１
上式の第１項（Ｉｎｔ）２は、３ビット整数の自乗値であり、３ビット整数は０〜７までの値をとり、その自乗値は、０〜４９までの６ビット整数であり８種類である。
【００６１】
ここで（Ｉｎｔ）２は乗算器を使用して求めず、デコーダもしくは、ＬＵＴを参照することで求める。
【００６２】
上式の第２項、２・（Ｉｎｔ）・（Ｄｅｃ）は、小数部Ｄｅｃの２×Ｉｎｔ倍の値である。Ｉｎｔは３ビット整数値であることから、小数部Ｄｅｃのビットシフトおよび加算で構成することにより乗算器を使用せずに求めることができる。
【００６３】
上記の方法により（Ｒ−Ｅ）２＝（Ｉｎｔ＋Ｄｅｃ）２＝（Ｉｎｔ）２＋２・（Ｉｎｔ）・（Ｄｅｃ）を求め、続いて状態尤度（Ｐ）と加算する（ステップ２１４）。
【００６４】
上記計算を状態尤度の偶数側／奇数側それぞれに関して実施し、その大小関係を比較する（ステップ２１５）。
【００６５】
その比較結果に基づき、状態尤度の大きい方（ユークリッド距離の小さい方）がどちらであるかを判定し、尤度が大きくなる受信データ、枝尤度期待値および、前時刻の状態尤度を出力する（ステップ２１６）。
【００６６】
出力された受信データ、枝尤度期待値および、前時刻の状態尤度は、状態尤度計算部１０２に入力され、状態尤度が求められる。その結果は、図１の状態尤度メモリ１０３に一時的に蓄積される。
【００６７】
この構成によれば、仮の状態尤度を求め、その大小判定によりセレクト信号を出力し、選択された状態尤度のみを正確に演算する構成をとるため、ユークリッド距離を計算するための乗算器を半減することが可能である。よって、回路規模を削減することができる。
【００６８】
（実施の形態３）
図５は、本発明の軟判定ビタビ復号装置における状態尤度大小判定部の他の構成例を示すブロック図である。
【００６９】
本実施の形態の特徴は、制御部４０５によってパイプライン的な制御を行い、演算器（仮の状態尤度を求める整数部自乗値テーブル（ＬＵＴ）３１０と、整数と小数の積を求める整数対小数積演算部３１１と、整数部自乗値テーブルと整数対小数積演算部の出力値を加算する加算器３１２と、加算器３１２の出力と前状態における状態尤度とを加算する加算器３１３）を時分割で共有して、回路規模をさらに低減することである。
【００７０】
図示されるように、図５の状態尤度大小判定部１０１は、受信データと枝尤度期待値との差を求める加算器３０１と、仮の状態尤度を求める整数部自乗値テーブル３１０と、整数と小数の積を求める整数対小数積演算部３１１と、整数部自乗値テーブルと整数対小数積演算部の出力値を加算する加算器３１２と、加算器３１２の出力と前状態における状態尤度とを加算する加算器３１３と、状態尤度の偶数側／奇数側を比較する加算器３１４と、入力データと演算結果を選択する選択部４０１と、受信データ、枝尤度期待値、状態尤度を格納するレジスタ４０２と、仮の状態尤度を求めるための入力データを選択する選択部４０３と、偶数側／奇数側の状態尤度を選択する選択部４０４と、時分割により演算器を共有するように制御する制御部４０５と、を有する。
【００７１】
この構成によれば、演算処理をパイプライン化することにより、演算器を時分割で共有することが可能となる。よって、回路規模を削減することができる。
【００７２】
【発明の効果】
以上説明したように、本発明によれば、生き残る枝についてのみ高精度な枝尤度の計算を行うため、回路的な負担が軽減される。すなわち、状態尤度の偶数側／奇数側の大小比較において状態尤度を求める前に状態尤度の大小判定することが可能となり、状態尤度算出のための自乗計算時に使用する乗算器を半減させることができる。よって、一つのノードに合流する偶数側の枝および奇数側の枝の状態尤度を同時に計算するという手法を採って高速処理を確保しつつ、その一方で、処理量を増加させることなく回路規模を削減することができる。また、状態尤度の更新は頻繁に発生するため大規模な乗算器の動作が削減されることにより、消費電力も低減することができる。
【図面の簡単な説明】
【図１】本発明の実施の形態１に係る軟判定ビタビ復号装置の全体構成を示すブロック図
【図２】図１の軟判定ビタビ復号装置の特徴的な動作を示すフロー図
【図３】本発明の軟判定ビタビ復号装置における状態尤度大小判定部の構成の一例を示すブロック図
【図４】図３の状態尤度大小判定部の具体的な動作手順を示すフロー図
【図５】本発明の軟判定ビタビ復号装置における状態尤度大小判定部の構成の他の例を示すブロック図
【図６】枝尤度、状態尤度、ならびに１つのノードに合流する偶数側の枝／奇数側の枝について説明するための図
【図７】ユークリッド距離について説明するための図
【図８】本発明を用いずに、偶数側の枝／奇数側の枝の双方の枝尤度を同時に演算する構成のビタビ復号装置の全体構成を示すブロック図
【符号の説明】
１０  近似演算部
２０  大小判定部
９０  枝尤度計算部
１０１  状態尤度大小判定部
１０２  状態尤度計算部
１０３  状態尤度メモリ
１０４，１０５  乗算器
１０６，１０７  加算器
１２０  パスメモリ
１２１  トレースバック処理部
【図１】
2004235698.tif 000003
【図２】
2004235698.tif 000004
【図３】
2004235698.tif 000005
【図４】
2004235698.tif 000006
【図５】
2004235698.tif 000007
【図６】
2004235698.tif 000008
【図７】
2004235698.tif 000009
【図８】
2004235698.tif 000010