(57)【特許請求の範囲】
【請求項１】
受信シンボルの系列を処理するための復号器であって、
状態機械の多段トレリス表現の状態間の遷移に関連するブランチメトリックを計算するブランチメトリック計算ユニットであって、少なくともブランチメトリックの部分集合が受信シンボルの与えられた１つと、トレリスの与えられた段におけるその最近接の符号語との間の線形距離に対応するものであるブランチメトリック計算ユニットと、
前記ブランチメトリック計算ユニットの出力に接続された入力を有する加算比較選択ユニットであって、トレリスの現在の段に対する生き残りパスと、対応する更新されたパスメトリックとを求める際の比較のために、トレリスの現在の段に対して前記ブランチメトリック計算ユニットにより生成される線形距離ブランチメトリックと、トレリスの前の段に対して生成されるパスメトリックとを利用する加算比較選択ユニットと、
前記加算比較選択ユニットの出力に接続された入力を有し、多段トレリスの与えられた段に対して、求められたパスメトリックに基づいて、該段に対する出力を生成するトレースバックユニットとを含み、
前記線形距離ブランチメトリックのうちの所与の１つは、前記トレリスの段ｎにおける状態ｉから状態ｊへの遷移に対応し、および前記生き残りパスは、前記線形距離ブランチメトリックに関与する下記の計算のうちの１つを利用して求められるようになっており、
【数１】
0003699344.tif 000026
ここで、ｙｎ，ｍは段ｎにおける第ｍ次元受信シンボルを表わし、ｐｉ，ｊ，ｍは、コセットＣｉ，ｊ内で前記段ｎにおける第ｍ次元受信シンボルｙｎ，ｍに最も近い符号語を表わし、Ｂｉ，ｊ，ｍは段ｎにおける状態ｉから状態ｊへの遷移についての第ｍ次元ブランチメトリックを表わし、Ｍｊ，ｎは段ｎにおける状態ｊについてのパスメトリックを表わし、およびΔＭはパスメトリック差を表わすものであることを特徴とする復号器。
【請求項２】
トレリスの段ｎにおける状態ｉから状態ｊへの遷移に対応する与えられた線形距離ブランチメトリックが、
【数２】
0003699344.tif 000027
で表される請求項１に記載の復号器。
【請求項３】
生き残りパスが、次式
【数３】
0003699344.tif 000028
を計算することにより求められ、状態ｉから状態ｊへのパスが段ｎにおいて状態ｊに行く最適パスである場合、段ｎにおける更新されたパスメトリックが次式
【数４】
0003699344.tif 000029
で与えられる請求項２に記載の復号器。
【請求項４】
トレリスの段ｎにおける状態ｉから状態ｊへの遷移に対応する与えられた線形距離ブランチメトリックが
【数５】
0003699344.tif 000030
で表される請求項１に記載の復号器。
【請求項５】
前記生き残りパスが、次式
【数６】
0003699344.tif 000031
を計算することにより求められ、状態ｉから状態ｊへのパスが段ｎにおいて状態ｊに行く最適パスである場合、段ｎにおける更新されたパスメトリックが、次式
【数７】
0003699344.tif 000032
で与えられる請求項４に記載の復号器。
【請求項６】
前記生き残りパスが、次式
【数８】
0003699344.tif 000033
を計算することにより求められ、状態ｉから状態ｊへのパスが段ｎにおいて状態ｊに行く最適パスである場合、段ｎにおける更新されたパスメトリックが、次式
【数９】
0003699344.tif 000034
で与えられる請求項４に記載の復号器。
【請求項７】
前記生き残りパスが、次式
【数１０】
0003699344.tif 000035
のうちの一方を計算することにより求められ、状態ｉから状態ｊへのパスが段ｎにおいて状態ｊに行く最適パスである場合、段ｎにおける更新されたパスメトリックが、次式
【数１１】
0003699344.tif 000036
で与えられる請求項４に記載の復号器。
【請求項８】
受信シンボル系列を処理する復号器を有する装置であって、
前記復号器は、状態機械の多段トレリス表現の状態間の遷移に関連するブランチメトリックを計算し、少なくとも一部のブランチメトリックは、与えられた受信シンボルと、トレリスの与えられた段におけるその最近接符号語との間の線形距離に対応し、
さらに、前記復号器は、トレリスの現在の段に対する生き残りパスと、対応する更新されたパスメトリックとを求める際の比較のために、トレリスの現在の段に対する線形距離ブランチメトリックと、トレリスの前の段に対して生成されたパスメトリックとを利用し、多段トレリスの与えられた段に対して求められたパスメトリックに基づいて、該段に対する出力を生成するようになっており、および
前記線形距離ブランチメトリックのうちの所与の１つは、前記トレリスの段ｎにおける状態ｉから状態ｊへの遷移に対応し、および前記生き残りパスは、前記線形距離ブランチメトリックに関与する下記の計算のうちの１つを利用して求められるようになっており、
【数１２】
0003699344.tif 000037
ここで、ｙｎ，ｍは段ｎにおける第ｍ次元受信シンボルを表わし、ｐｉ，ｊ，ｍは、コセットＣｉ，ｊ内で前記段ｎにおける第ｍ次元受信シンボルｙｎ，ｍに最も近い符号語を表わし、Ｂｉ，ｊ，ｍは段ｎにおける状態ｉから状態ｊへの遷移についての第ｍ次元ブランチメトリックを表わし、Ｍｊ，ｎは段ｎにおける状態ｊについてのパスメトリックを表わし、およびΔＭはパスメトリック差を表わすものであることを特徴とする装置。
【請求項９】
受信シンボルの系列を処理する復号器であって、
状態機械の多段トレリス表現の状態間の遷移に関連するブランチメトリックを計算する手段であって、少なくともブランチメトリックの部分集合が、受信シンボルの与えられた１つと、トレリスの与えられた段におけるその最近接符号語との間の線形距離に対応するものであるブランチメトリックを計算する手段と、
トレリスの現在の段に対する生き残りパスと、対応する更新されたパスメトリックとを求める際の比較のために、トレリスの現在の段に対する線形距離ブランチメトリックと、トレリスの前の段に対して生成されたパスメトリックとを利用する手段と、
多段トレリスの与えられた段に対して求められたパスメトリックに基づいて、該段に対する出力を生成する手段とを含み、および
前記線形距離ブランチメトリックのうちの所与の１つは、前記トレリスの段ｎにおける状態ｉから状態ｊへの遷移に対応し、および前記生き残りパスは、前記線形距離ブランチメトリックに関与する下記の計算のうちの１つを利用して求められるようになっており、
【数１３】
0003699344.tif 000038
ここで、ｙｎ，ｍは段ｎにおける第ｍ次元受信シンボルを表わし、ｐｉ，ｊ，ｍは、コセットＣｉ，ｊ内で前記段ｎにおける第ｍ次元受信シンボルｙｎ，ｍに最も近い符号語を表わし、Ｂｉ，ｊ，ｍは段ｎにおける状態ｉから状態ｊへの遷移についての第ｍ次元ブランチメトリックを表わし、Ｍｊ，ｎは段ｎにおける状態ｊについてのパスメトリックを表わし、およびΔＭはパスメトリック差を表わすものであることを特徴とする復号器。
【請求項１０】
受信シンボルの系列を処理する方法であって、
状態機械の多段トレリス表現の状態間の遷移に関連するブランチメトリックを計算するステップであって、少なくともブランチメトリックの部分集合が受信シンボルの与えられた１つと、トレリスの与えられた段におけるその最近接の符号語との間の線形距離に対応しているようなステップと、
トレリスの現在の段に対する生き残りパスと、対応する更新されたパスメトリックとを求める際の比較のために、トレリスの現在の段に対する線形距離ブランチメトリックと、トレリスの前の段に対して生成されたパスメトリックとを利用するステップと、
多段トレリスの与えられた段に対して求められたパスメトリックに基づいて、該段に対する出力を生成するステップとを含み、および
前記線形距離ブランチメトリックのうちの所与の１つは、前記トレリスの段ｎにおける状態ｉから状態ｊへの遷移に対応し、および前記生き残りパスは、前記線形距離ブランチメトリックに関与する下記の計算のうちの１つを利用して求められるようになっており、
【数１４】
0003699344.tif 000039
ここで、ｙｎ，ｍは段ｎにおける第ｍ次元受信シンボルを表わし、ｐｉ，ｊ，ｍは、コセットＣｉ，ｊ内で前記段ｎにおける第ｍ次元受信シンボルｙｎ，ｍに最も近い符号語を表わし、Ｂｉ，ｊ，ｍは段ｎにおける状態ｉから状態ｊへの遷移についての第ｍ次元ブランチメトリックを表わし、Ｍｊ，ｎは段ｎにおける状態ｊについてのパスメトリックを表わし、およびΔＭはパスメトリック差を表わすものであることを特徴とする方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、通信システムに関し、特に、通信システムで用いられる復号技術に関する。
【０００２】
【従来の技術】
畳込み符号および帯域幅効率のよいトレリス符号化変調（ＴＣＭ：Trellis Coded Modulation）は、音声帯域モデム、非対称ディジタル加入者線（ＡＤＳＬ：Asymmetric Digital Subscriber Line）システム、オーディオ放送システム、ファースト(First)あるいはギガビット(Gigabit)イーサネットシステム、セルラシステムおよびワイヤレスローカルループ(wireless local loop)システムなどの多くのさまざまなタイプの通信システムで広く使用されている。畳込み符号は、例えば、G. C. Clark, Jr. and J. B. Cain, "Error Control Coding for Digital Communications", New York, Plenum, 1981、に記載されており、ＴＣＭは、例えば、G. Ungerboeck, "Trellis-coded modulation with redundant signal sets part I", IEEE Communications Magazine, Vol.25, February 1987、および、G. Ungerboeck, "Trellis-coded modulation with redundant signal sets part II", IEEE Communications Magazine, Vol.25, February 1987、に記載されている。
【０００３】
ビタビアルゴリズムは、加法性白色ガウシアンノイズ（ＡＷＧＮ：Additive White Gaussian Noise）チャネルを通じて伝送された畳込み・トレリス符号を復号するための、効率的な最尤系列検出方法である。ビタビアルゴリズムは、例えば、
・A. J. Viterbi, "Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm", IEEE Trans. on Information Theory, Vol.IT-13, April 1967
・G. D. Forney, Jr., "Maximum-likelihood sequence detection in the presence of intersymbol interference", IEEE Trans. on Information Theory, Vol.IT-18, pp.363-378, May 1972
・G. D. Forney, Jr., "The Viterbi algorithm", IEEE Proceedings, Vol.61, pp.268-278, March 1973
に記載されている。ビタビアルゴリズムは現在、すべての実用的アプリケーションで、これらの符号を復号するために、ほぼ排他的に使用されている。また、レイリーフェージングチャネルでも、チャネル状態情報（ＣＳＩ：Channel State Information）が既知の場合には、ビタビアルゴリズムは依然として、わずかな修正で、これらの符号を検出するための最適な検出方法たりうることが知られている。例えば、E. Biglieri, D. Divsalar, P. J. McLane and M. K. Simon, "Introduction to Trellis-Coded Modulation with Applications", New York, New York, Macmillan Publishing Company, 1991、を参照。
【０００４】
ビタビアルゴリズムは、チャネル出力においてノイズのあるシンボルの特定の系列が与えられた場合に、トレリスダイヤグラムによって記述される、ある符号における最尤符号語系列を求める。これは、動的計画法の応用であり、最適経路の探索が再帰的に行われるものである。畳込み・トレリス符号を復号するためのビタビアルゴリズムでは、ＡＷＧＮチャネル、および、ＣＳＩが適切に含まれるときのレイリーフェージングチャネルで伝送される系列を復号するための最適なブランチメトリックは、２乗ユークリッド距離である。
【０００５】
ビタビアルゴリズムでは一般に、トレリスのブランチに関連するブランチメトリックを得るために２乗ユークリッド距離を計算するときだけ、乗算が必要である。２乗ユークリッド距離を得るために、ルックアップテーブルが用いられることもある。実装されるトレリスに依存して、通常のルックアップテーブルのサイズは少なくとも２9×９〜４ｋビットとなる。高ビットレートアプリケーションでは、並列ブランチメトリック計算が要求されることがある。並列ブランチメトリック計算を実装するために乗算器やルックアップテーブルを複製すると、復号器の複雑さが極端に増大し、高ビットレートアプリケーションに対するこのような構成は法外に高価になる可能性がある。さらに、乗算器や、大規模なルックアップテーブルにアクセスする際の遅延は、高ビットレートアプリケーションにおける完全パイプライン化ビタビ復号器の処理ボトルネックとなる可能性がある。
【０００６】
別法として、絶対値距離が、ブランチメトリックとして使用するために提案されている。しかし、絶対値距離をブランチメトリックとして使用することには、ビタビ復号器の性能を低下させるという好ましくない効果がある。H. Lou, "Implementing the Viterbi algorithm.  Fundamentals and real-time issues for processor designers", IEEE Signal Processing Magazine, Vol.12, pp.42-52, September 1995、を参照。
【０００７】
【発明が解決しようとする課題】
したがって、性能を劣化させずに復号器を簡単化する、より効率的なブランチメトリック表現が必要とされている。
【０００８】
【課題を解決するための手段】
本発明は、線形距離に基づく改善されたブランチメトリック表現を提供する。
これは、上記の従来技術の復号器の複雑さの問題を解決するとともに、復号器の性能の大幅な劣化を回避する。
【０００９】
受信シンボル系列を復号する本発明の実施例は、ブランチメトリック（計算）ユニット、加算比較選択（ＡＣＳ）ユニット、およびトレースバックユニットを有する。ブランチメトリックユニットは、状態機械の多段トレリス表現の状態間の遷移に関連するブランチメトリックを計算する。本発明によれば、各ブランチメトリックは、与えられたトレリス段において、与えられた受信シンボルと、その最近接符号語との間の線形距離に対応する。加算比較選択ユニットは、多段トレリスの現在の段に対する生き残りパスおよび対応する更新パスメトリックを求める際の比較のために、現在の段のブランチメトリックを、前に生成されたパスメトリックとともに利用する。トレースバックユニットは、更新パスメトリックを利用して、対応する復号出力を生成する。
【００１０】
本発明によれば、復号器は、２乗距離ブランチメトリックを用いて達成されるのと同等の性能レベルを、線形距離ブランチメトリックを用いて達成するように構成されるとともに、復号器の複雑さは、乗算の消去により低減される。具体的には、本発明によれば、乗算器や大規模なルックアップテーブルではなく加算器を用いてブランチメトリックを得ることを可能にし、それにより、復号器を大幅に簡単化する。本発明の技術は、例えば、ＱＰＳＫ(Quadrature Phase Shift Keying)、８−ＰＳＫ(Phase Shift Keying)、１６−ＱＡＭ(Quadrature Amplitude Modulation)、３２−ＱＡＭおよびより大きいコンステレーションのような、さまざまな変調コンステレーションの畳込み・トレリス符号での使用に適している。
【００１１】
【発明の実施の形態】
図１に、本発明を実装可能なビタビ復号器１０を示す。復号器１０は、ブランチメトリック計算器（計算ユニット）１２、再帰ＡＣＳエンジン１４、およびトレースバックユニット１６を有する。軟シンボルが、ブランチメトリック計算器１２への入力バッファ１８に入力される。計算器１２は、与えられたトレリス段に対するすべての可能な遷移に関連するブランチメトリックを計算する。ＡＣＳエンジン１４は再帰的である。すなわち、与えられたトレリス段に対して計算される新たなパスメトリックは、前の段に対して計算されたパスメトリックと、前の段から次の段への遷移に関連するブランチメトリックとに依存する。ＡＣＳエンジン１４の出力はトレースバックユニット１６に供給され、その結果として得られる出力は出力バッファ２０にバッファリングされる。有限状態機械コントローラ２２は、ビタビ復号器１０のさまざまな要素の動作を制御する。
【００１２】
２乗ユークリッド距離を利用してブランチメトリックを表現する従来のビタビ復号器とは異なり、本発明による復号器１０は、線形距離を用いてブランチメトリックを表現する。以下でさらに詳細に説明するように、これにより、復号器の性能に悪影響を及ぼすことなく、復号器の複雑さを大幅に低減することが可能となる。例えば、本発明の技術を用いると、図１のブランチメトリック計算（ＢＭＣ：branch metric calculation）ユニット１２でブランチメトリックを計算するために、複雑な乗算器の代わりに比較的簡単な加算器を使用可能である。本発明によれば、例えば、ＱＰＳＫ、８−ＰＳＫ、１６−ＱＡＭ、３２−ＱＡＭおよびより大きいコンステレーションのような、さまざまな変調コンステレーションの畳込み・トレリス符号のブランチメトリックとして、線形距離が使用される。
【００１３】
図１のビタビ復号器１０において線形距離がブランチメトリックとしてどのように使用されるかについて、図２〜図６を参照して以下で説明する。以下の説明は、次の記法を利用する。
ｙn,m：  復号段ｎにおける第ｍ次元の受信されたノイズのあるシンボル（ｍ＝１のとき、ｙn,m＝ｙn）。
Ｃi,j：  状態ｉから状態ｊへの遷移に関連する出力シンボル（このシンボルのことを、畳込み符号の場合は符号語ともいい、トレリス符号の場合はコセット番号ともいう）。
Ｐi,j,n,m：  復号段ｎにおいて、トレリス符号のコセットＣi,j内で、第ｍ次元受信シンボルｙn,mに最も近い符号語（ｍ＝１のとき、Ｐi,j,n,m＝Ｐi,j,n）。
Ｂi,j,n,m：  復号段ｎにおける状態ｉから状態ｊへの遷移に対する第ｍ次元のブランチメトリック。
【数１】
0003699344.tif 000002
と定義する（ｍ＝１のとき、Ｂi,j,n,m＝Ｂi,j,n）。
Ｍj,n：  復号段ｎにおける状態ｊに対するパスメトリック
｛ｉ｝：  状態ｊへの遷移を有する状態の集合
【００１４】
各復号段において、ビタビアルゴリズムは、各状態へのパスメトリックが最小となるパスを計算する。例えば、復号段ｎで状態ｊに行く生き残りパスを求めるには、ビタビアルゴリズムは次の計算を行う。
【数２】
0003699344.tif 000003
前述のように、ＡＷＧＮにおける最適なビタビアルゴリズム性能のためには、前掲のG. D. Forney, Jr.の文献に記載されているように、与えられた遷移のブランチメトリックは、ノイズのあるシンボルと、遷移の出力シンボルとの間の２乗距離として定義される。
Ｂi,j,n＝（ｙn−Ｃi,j）2    （２）
【００１５】
トレリス符号に対して、Ｃi,jは、セット内に通常複数のシンボルを含むコセット番号である。図２に、トレリス符号による１６−ＱＡＭコンステレーションの分割の例を示す。この分割は、図示のようにＣレベルおよびＤレベルのコセットを含むいくつかのコセットを生成する。Ｃレベルコセット、すなわち、コセットＣ０〜Ｃ３は、それぞれ４個の符号語を有し、Ｄレベルコセット、すなわち、コセットＤ０〜Ｄ７は、各コセット内に２個の符号語を有する。与えられた受信シンボルｙnに対して、まず、ユークリッド距離でｙnに最も近い符号語を計算しなければならない。コセットＣi,jにおけるこの最近接符号語をＰi,j,nで表す。この場合のブランチメトリックは次のようになる。
Ｂi,j,n＝（ｙn−Ｐi,j,n）2    （３）
【００１６】
ビタビアルゴリズムでは、各状態に対する生き残りパスを求めるために、パスメトリックどうしの間の比較が必要である。このため、一般に、パスメトリック間の差のみに関心がある。すなわち、復号段ｎにおいて、状態ｊに行く比較すべき２つのパスが状態ｉおよびｋから出ている場合、比較の結果は、次の差のみに依存する。
ΔＭ＝（Ｍi,n-1＋Ｂi,j,n）−（Ｍk,n-1＋Ｂk,j,n）    （４）
【００１７】
一般には、ｙnは多次元であることが可能である。高次元トレリス符号の場合、最近接符号語の探索は一度に１次元ずつは行われなくても、いったん多次元の最近接符号語が計算されれば、ブランチメトリックは一度に１次元ずつ計算することが可能であり、その後、これらの１次元ブランチメトリックの和が、多次元シンボルに対するブランチメトリックとなる。具体的には、ｙnがＮ次元であり（すなわち、ｙn＝（ｙn,1，ｙn,2，...，ｙn,N））、Ｂi,j,n,mが、再帰ｎにおける状態ｉから状態ｊへの遷移に対する第ｍ次元のブランチメトリックを表す場合、Ｎ次元シンボルに対するブランチメトリックは次のようになる。
【数３】
0003699344.tif 000004
生き残りパスを求めるため、状態ｉから状態ｊへのパスのパスメトリックを、状態ｋから状態ｊへのものと比較しなければならない。すなわち、次式を計算する。
【数４】
0003699344.tif 000005
ただし、
【数５】
0003699344.tif 000006
である。比較規則は、
【数６】
0003699344.tif 000007
である。
【００１８】
図３は、１次元シンボルｙnを仮定して、２乗ユークリッド距離に基づく上記の処理を示す流れ図である。ステップ１００および１０２は、２つの異なる２乗距離ブランチメトリックの計算を示し、ステップ１０４は、式（４）に従ってこれらのブランチメトリックを用いて生成される新しいパスメトリック間の差の計算を示す。ステップ１０６は、式（７）の比較を実行し、ステップ１０８および１１０はそれぞれ、２つの異なる可能な新しいパスメトリックのうちの一方を一時変数Ｔｍｐに代入する。ステップ１１２は、復号段ｎに対する新しいパスメトリックの値として、選択されたほうの変数Ｔｍｐを代入する。
【００１９】
以下で示すように、式（６）の項｜Ｐk,j,n,m−Ｐi,j,n,m｜は、実際に興味のある符号の各状態に行くすべてのブランチに対する比較中は一定である。さらに、以下で示すように、式（６）の項ｓｉｇｎ（Ｐk,j,n,m−Ｐi,j,n,m）は、（ｙn,m−Ｐi,j,n,m）および（ｙn,m−Ｐk,j,n,m）の正負によって決定される。したがって、比較中、ブランチメトリックを表現するために、受信シンボルと最近接符号語の間の線形距離（例えば、（ｙn,m−Ｐk,j,n,m））を使用することができる。その結果、各状態に対する生き残りパスを探索するための加算比較選択プロセスのクリティカルパスにおいて、２乗や乗算は不要となる。
【００２０】
図４は、同じく１次元シンボルｙnを仮定して、本発明による線形距離ブランチメトリックを用いた上記の処理を示す流れ図である。ステップ２００および２０２は、２つの異なる線形距離ブランチメトリックの計算を示し、ステップ２０４は、式（４）に従ってこれらのブランチメトリックを用いて生成される新しいパスメトリック間の差の計算を示す。ステップ２０６は、式（７）の比較を実行し、ステップ２０８および２１０はそれぞれ、２つの異なる可能な新しいパスメトリックのうちの一方を一時変数Ｔｍｐに代入する。ステップ２１２は、復号段ｎに対する新しいパスメトリックの値として、選択されたほうの変数Ｔｍｐを代入する。
【００２１】
以下の説明では、上記の線形距離ブランチメトリック法を、ＱＰＳＫコンステレーションを有する畳込み符号（場合Ｉ）、ＣレベルおよびＤレベルの分割と無限コンステレーションを有するトレリス符号（場合ＩＩ）、ならびに、ＣレベルおよびＤレベルの分割と有限コンステレーションを有するトレリス符号（場合ＩＩＩ）に適用する。これらのカテゴリは、実用的に興味のある多くの符号をカバーするが、当業者には明らかなように、本発明の技術は、他のタイプの符号にも適用可能である。
【００２２】
［場合Ｉ：ＱＰＳＫコンステレーション］
Ｐi,j∈｛±１，±ｊ｝のＱＰＳＫコンステレーションに対して、一度に１次元ずつシンボルに注目すると、Ｐi,j,1∈｛±１｝である。式（６）から、受信シンボルのｘ方向をｙn,1で表すと、
ΔＢ＝ｓｉｇｎ（Ｐk,j,n,1−Ｐi,j,n,1）｜Ｐk,j,n,1−Ｐi,j,n,1｜［（ｙn,1−Ｐi,j,n,1）＋（ｙn,1−Ｐk,j,n,1）］    （８）
である。比較されるべき符号語のすべての対に対して｜Ｐk,j,n,1−Ｐi,j,n,1｜＝２であるため、比較結果を変えることなくΔＭをこの因子で割ることができる。したがって、
【数７】
0003699344.tif 000008
となる。したがって、生き残りパスの探索中、時刻ｎにおける状態ｉおよび状態ｊへの１次元ブランチメトリックは次のように表すことができる。
【数８】
0003699344.tif 000009
Ｂi,j,n,2も同様に計算される。生き残りパスを探索するには、次式を計算する。
【数９】
0003699344.tif 000010
このように、状態ｉから状態ｊへのパスが、復号段ｎにおいて状態ｊに行く最適パスである場合、更新されたパスメトリックは
Ｍj,n＝Ｍi,n-1＋Ｂi,j,n    （１２）
となる。
【００２３】
［場合ＩＩ：無限コンステレーションを有するトレリス符号］
図５に、無限トレリス符号コンステレーションを示す。図５に示すように、各次元に対して、比較されるべき２個のコセット（Ｃ０およびＣ１で表す）は、等間隔の符号語を有し、コセットＣ０内の符号語は、コセットＣ１内の符号語の判定境界上に位置し、その逆も同様である。この場合、各次元における受信シンボルｙnは、常に、２つのコセットからの２つの最近接符号語間にあることになる。さらに、式（６）の項｜Ｐk,j,n−Ｐi,j,n｜は、すべてのブランチメトリックの比較において定数である。このため、比較結果を変えることなく、ΔＭをこの定数値で割ることができる。
【００２４】
式（５）および（６）の項ｓｉｇｎ（Ｐk,j,n−Ｐi,j,n）を求めるため、Ｐi,j,nがＰk,j,nより大きいか小さいかを知らなければならない。例えば、図５において、ｙn＝ｙの場合、（Ｃ０の）Ｐi,j,n＝ａであり、（Ｃ１の）Ｐk,j,n＝ｂである。したがって、ｓｉｇｎ（Ｐk,j,n−Ｐi,j,n）≧０である。なお、この場合、
0003699344.tif 000011
である。他方、ｙn＝ｚの場合、（Ｃ０の）Ｐi,j,n＝ｃであり、（Ｃ１の）Ｐk,j,n＝ｂである。したがって、ｓｉｇｎ（Ｐk,j,n−Ｐi,j,n）≦０である。この場合、
0003699344.tif 000012
である。これらの２つの場合の一方のみが生じるため、項ｓｉｇｎ（Ｐk,j,n−Ｐi,j,n）を明示的に計算する必要はない。そこで、与えられたｍ次元シンボルに対する生き残りパスを求めるには、次式を計算する。
【数１０】
0003699344.tif 000013
ただし、
【数１１】
0003699344.tif 000014
である。上記で導いた性質をＣレベル分割を用いたＣコセット（図２）に適用すると、理解されるように、任意のＣコセットの対に対して、一方のコセット内の符号語は、他方のコセット内の符号語の判定境界上にあるか、または、各次元において他方のコセットとちょうど同じ位置にあるかのいずれかである。このため、上記で導いた性質を用いて、各状態に対する生き残りパスを次式により探索することができる。
Ｍj,n＝Ｍi,n,1＋Ｂi,j,n    （１５）
Ｄレベル分割を用いたトレリス符号は、各状態に行く偶数番号のコセットか奇数番号のコセットかのいずれかを有する。このため、上記で導いた性質は、各復号段において比較されるべきすべてのコセットについて成り立つ。しかし、例えば、与えられた復号段において、コセットＤ０のブランチメトリックはコセットＤ３のブランチメトリックとは比較されないが、これらが現在の復号段における生き残りパスに関連する場合、これらは、次の復号段で互いに比較される可能性がある。Ｄ３内の符号語は、Ｄ０内の符号語の判定境界と一致しない。このため、各次元における受信シンボルｙnは、Ｄ０およびＤ３内の２つの最近接符号語の間にあるとは限らない。さらに、式（５）の項｜Ｐk,j,n−Ｐi,j,n｜は、ｙnの位置に依存する。このため、各復号段でΔＢを同じ項で割ることができても、ΔＭを｜Ｐk,j,n−Ｐi,j,n｜で割ることはできない。したがって、式（１３）を用いて、各状態に対する生き残りパスを求めることができる。しかし、状態ｉから状態ｊへのパスが、復号段ｎにおいて状態ｊに行く最適パスである場合、与えられたｍ次元シンボルに対して、更新されたパスメトリックは
【数１２】
0003699344.tif 000015
となるはずであり、ｙn,m2はすべてのパスメトリックに共通であるため、これは次のように書ける。
【数１３】
0003699344.tif 000016
さらに、すべてのパスメトリックの項（Ｐi,j,n,m2−２ｙn,mＰi,j,n,m）は、比較結果を変えることなく、２で割ることができる。すなわち、
【数１４】
0003699344.tif 000017
である。この場合、項
【数１５】
0003699344.tif 000018
を計算しなければならないが、これは状態ごとに１回だけ計算すればよく、各状態に対する生き残りパスを探索するための加算比較選択プロセスと並列に実行可能である。すなわち、これは、各状態に対する生き残りパス探索のクリティカルパスではない。さらに、Ｐi,j,n,mがコンステレーション点、すなわち、定数であり、ｙn,mまたは
【数１６】
0003699344.tif 000019
とコンステレーション点との乗算は、乗算の演算を必要とすることなく実行可能である（例えば、優先日が同一の特許出願（整理番号Ａ００４２７）に記載されている）。
【００２５】
図６は、１次元シンボルｙnを仮定して、本発明による線形距離ブランチメトリックを用いた無限トレリス符号コンステレーションに対する上記の処理を示す流れ図である。ステップ３００および３０２は、２つの異なる線形距離ブランチメトリックの計算を示し、ステップ３０４は、これらのブランチメトリックを用いて生成される２つの可能な新しいパスメトリック間の差の計算を示す。ステップ３０６は、これらの差に基づく２つの可能な新しいパスメトリックの比較を実行し、ステップ３０８、３１０および３１２は、復号段ｎに対するこれらの２つの可能な新しいパスメトリックのうちの一方を選択する。変数ＳおよびＴは、ステップ３０８および３１０に示すように定義された一時変数を表す。
【００２６】
［場合ＩＩＩ：有限コンステレーションを有するトレリス符号］
図７に示すような有限のトレリス符号コンステレーションの場合、２つのコセットからの最近接符号語が両方とも、ｙn（例えば、ｙn＝ｚ）より小さい値またはｙn（例えば、ｙn＝ｙ）より大きい値を有することがある。これらの場合には、与えられたコンステレーションに対して、いずれのコセット内の符号語ほうが小さい値を有するかが事前に既知となる。例えば、この例では、Ｃ０内の最近接符号語はＣ１のものより小さい値を有する。このため、いったんこれらの場合が検出されると、式（６）の項ｓｉｇｎ（Ｐk,j,n−Ｐi,j,n）に対する適当な正負が既知となる。これらの場合が生じたかどうかを判定するためには、次に注意する。
ｙn≧Ｐi,j,n  かつ  ｙn≧Ｐk,j,n  の場合、ｙn−Ｐi,j,n≧０  かつ  ｙn−Ｐk,j,n≧０
ｙn≦Ｐi,j,n  かつ  ｙn≦Ｐk,j,n  の場合、ｙn−Ｐi,j,n≦０  かつ  ｙn−Ｐk,j,n≦０
Ｐi,j,n≦ｙn≦Ｐk,j,n  の場合、ｙn−Ｐi,j,n≧０  かつ  ｙn−Ｐk,j,n≦０    （１８）
したがって、Ｐi,j,nおよびＰk,j,nの正負を見ることにより、受信値ｙnが２つの最近接符号語に関してどこにあるかを判定することができる。他方、受信シンボルｙnが２つの最近接符号語の間にあるとき、
【数１７】
0003699344.tif 000020
であることは既知である。さらに、ｓｉｇｎ（ｙn−Ｐi,j,n）＝１である場合、Ｐi,j,n＞Ｐk,j,nであり、したがって、ｓｉｇｎ（Ｐk,j,n−Ｐi,j,n）＝１である。
【００２７】
要するに、復号段ｎにおけるｍ次元受信シンボルに対して、Ｃ０が状態ｉから状態ｊへの遷移に関連し、Ｃ１が状態ｋから状態ｊへの遷移に関連する場合であって、ｓi＝ｓｉｇｎ（ｙn,m−Ｐi,j,n,m）である場合、（
【数１８】
0003699344.tif 000021
かつｓi＝１）の場合の生き残りパスを探索するには式
【数１９】
0003699344.tif 000022
を計算し、それ以外の場合には式
【数２０】
0003699344.tif 000023
を計算する。ブランチメトリック比較の正負は、比較されるべき２つのコセットに依存するため、各状態についていったん生き残りパスが求められたら、真のブランチメトリックを蓄積しなければならない。すなわち、復号段ｎにおいて状態ｉから状態ｊへのパスが状態ｊに行く最適パスである場合、更新されたパスメトリックは次式のようになる。
【数２１】
0003699344.tif 000024
Ｄレベル分割および無限コンステレーションを有するトレリス符号の場合と同様に、項
【数２２】
0003699344.tif 000025
は、加算比較選択プロセスのクリティカルパスではなく、状態あたり１回だけ計算すればよい。さらに、この項の計算は簡単である。その理由は、Ｐi,j,n,mはコンステレーション点であるため、計算は、前述のように、乗算の演算なしで実行可能であるからである。
【００２８】
図８は、本発明による線形距離ブランチメトリックを用いた有限トレリス符号コンステレーションに対する上記の処理を示す流れ図である。図３、図４および図６の流れ図と同様に、図８もまた１次元シンボルｙnを仮定している。ステップ４００および４０２は、２つの異なる線形距離ブランチメトリックの計算を示し、ステップ４０４、４０６および４０８は、これらのブランチメトリックを用いて生成される２つの可能な新しいパスメトリック間の差の計算を示す。ステップ４１０は、２つの可能な新しいパスメトリックの比較を実行し、ステップ４１２、４１４および４１６は、復号段ｎに対するこれらの２つの可能なパスメトリックのうちの一方の選択を実行する。変数ＳおよびＴは、ステップ４１２および４１４に示すように定義された一時変数を表す。
【００２９】
理解されるように、上記の実施例では、線形距離ブランチメトリックが、一般に、加算比較選択ユニットで比較のために使用される。すなわち、線形距離ブランチメトリックが、生き残りパスを求めるプロセスで相異なる候補パスを比較するために使用される。しかし、加算比較選択ユニットは、更新演算のために他の形式のメトリック（例えば、従来の２乗距離メトリック）を使用することも可能である。これは、例えば上記の式（１６）および（１７）に示したパスメトリック更新演算における２乗項から明らかである。
【００３０】
上記の実施例は、ハードウェア、ソフトウェア、または、ハードウェアとソフトウェアの組合せとして実装可能である。例えば、上記の計算は、図１のビタビ復号器１０のような復号器のハードウェア要素、特定用途向け集積回路（ＡＳＩＣ）、あるいは、例えば通信システム受信機で用いられるその他のディジタルデータ処理装置を用いて、実行可能である。
【００３１】
【発明の効果】
以上述べたごとく、本発明によれば、線形距離に基づく改善されたブランチメトリック表現が得られ。これは、従来技術の復号器の複雑さの問題を解決するとともに、復号器の性能の大幅な劣化を回避する。
【図面の簡単な説明】
【図１】本発明を実装可能な例示的なビタビ復号器のブロック図である。
【図２】１６−ＱＡＭコンステレーションのＣレベルおよびＤレベル分割の図である。
【図３】従来の２乗ユークリッド距離ブランチメトリックを用いたブランチメトリックおよび生き残りパスの計算を示す流れ図である。
【図４】本発明による線形距離ブランチメトリックを用いたブランチメトリックおよび生き残りパスの計算を示す流れ図である。
【図５】１次元無限コンステレーションの例を示す図である。
【図６】無限コンステレーションに対する、本発明による線形距離ブランチメトリックを用いたブランチメトリックおよび生き残りパスの計算を示す流れ図である。
【図７】１次元有限コンステレーションの例を示す図である。
【図８】有限コンステレーションに対する、本発明による線形距離ブランチメトリックを用いたブランチメトリックおよび生き残りパスの計算を示す流れ図である。
【符号の説明】
１０  ビタビ復号器
１２  ブランチメトリック計算ユニット
１４  再帰ＡＣＳエンジン
１６  トレースバックユニット
１８  入力バッファ
２０  出力バッファ
２２  有限状態機械コントローラ
【図１】
0003699344.tif 000040
【図２】
0003699344.tif 000041
【図３】
0003699344.tif 000042
【図４】
0003699344.tif 000043
【図５】
0003699344.tif 000044
【図６】
0003699344.tif 000045
【図７】
0003699344.tif 000046
【図８】
0003699344.tif 000047