(57)【特許請求の範囲】
【請求項１】
ディジタル通信システムの受信機で情報を処理する方法であって、該方法は、
送信シンボルの系列に信号処理操作を適用するステップを有し、
該送信シンボルは第１変調コンステレーション内の点に対応し、該第１変調コンステレーションは第２変調コンステレーションを回転したものに対応しており、該送信シンボルの各々は、特定の数の情報ビットを表しており、
該信号処理操作はチャネル推定値の要素と、該送信シンボルのうちの所与の１つのシンボルとの積を計算するために少なくとも１つのセレクタ（３０）を利用しており、
該セレクタは、第１および第２の制御可能なインバータ（１０−１、１０−２）と、第１および第２のスイッチ（１２−１、１２−２）とから成り、該第１および第２の制御可能なインバータは該チャンネル推定値の要素のそれぞれの実部および虚部を受けとるよう機能し、該第１の制御可能なインバータは第１の制御信号に基づいて該実部を反転しもしくは反転せず、該第２の制御可能なインバータは第２の制御信号に基づいて該虚部を反転しもしくは反転しないよう動作し、該第１および第２のスイッチの各々は、該第１の制御可能なインバータから該反転されたもしくは反転されなかった実部を受けとるよう機能する一方の入力と、該第２の制御可能なインバータから該反転されたもしくは反転されなかった虚部を受けとるよう機能する他方の入力とを有し、該第１および第２のスイッチの各々は、第３の制御信号に応答して、２つのスイッチ入力のうちの１つをスイッチ出力として選択するよう動作し、該第１および第２のスイッチの出力は、該チャンネル推定値の該要素と該所与のシンボルの対応する要素との積のそれぞれの実部および虚部を提供するようになっていることを特徴とする方法。
【請求項２】
前記第１の変調コンステレーションは、前記第２の変調コンステレーションを４５°回転することにより生成される請求項１に記載の方法。
【請求項３】
前記第２の変調コンステレーションは、ＰＳＫコンステレーションおよびＱＡＭコンステレーションのうちの１つから成る請求項１に記載の方法。
【請求項４】
前記信号処理操作は、有限インパルス応答（ＦＩＲ）フィルタリング操作、最小平均二乗（ＬＭＳ）推定操作、およびビタビアルゴリズムを用いた最尤（ＭＬ）系列検出操作のうちの少なくとも１つから成る請求項１に記載の方法。
【請求項５】
前記セレクタは、さらに第１および第２の加算ユニット（１４−１）、（１４−２）をから成り、これら加算ユニットは、
ベクトル内積のそれぞれの実部および虚部の要素を計算するものである請求項１に記載の方法。
【請求項６】
前記加算ユニットの出力から前記加算ユニットの対応する入力へのフィードバックを含ませることにより、前記セレクタを用いてＦＩＲフィルタ操作を実現する請求項５に記載の方法。
【請求項７】
前記信号処理操作は、乗法演算なしで実現された多段演算を含み、該多段演算の各段は１つのセレクタに対応し、左シフト要素（３２、３６）が、前記段（３０、３４）のうちの与えられた段の出力と、後続段（３４、３８）の対応する入力との間に配置される請求項１に記載の方法。
【請求項８】
ディジタル通信システムの受信機で使用する情報を処理するための装置であって、該装置は、
送信シンボルの系列を処理する信号処理回路を有し、
該送信シンボルは第１変調コンステレーション内の点に対応し、該第１変調コンステレーションは第２変調コンステレーションを回転したものに対応しており、該送信シンボルの各々は、特定の数の情報ビットを表しており、
該信号処理回路は、チャネル推定値の要素と、該送信シンボルのうちの所与の１つのシンボルとの積を計算するよう構成された少なくとも１つのセレクタ（３０）からなり、
該セレクタは、第１および第２の制御可能なインバータ（１０−１、１０−２）と、第１および第２のスイッチ（１２−１、１２−２）とから成り、該第１および第２の制御可能なインバータは該チャンネル推定値の要素のそれぞれの実部および虚部を受けとるよう機能し、該第１の制御可能なインバータは第１の制御信号に基づいて該実部を反転しもしくは反転せず、該第２の制御可能なインバータは第２の制御信号に基づいて該虚部を反転しもしくは反転しないよう動作し、該第１および第２のスイッチの各々は、該第１の制御可能なインバータから該反転されたもしくは反転されなかった実部を受けとるよう機能する一方の入力と、該第２の制御可能なインバータから該反転されたもしくは反転されなかった虚部を受けとるよう機能する他方の入力とを有し、該第１および第２のスイッチの各々は、第３の制御信号に応答して、２つのスイッチ入力のうちの１つをスイッチ出力として選択するよう動作し、該第１および第２のスイッチの出力は、該チャンネル推定値の該要素と該所与のシンボルとの積のそれぞれの実部および虚部を提供するようになっていることを特徴とする装置。
【請求項９】
ディジタル通信システムであって、
送信シンボルの系列を生成する送信機（１０２）であって、
該送信シンボルが、第２変調コンステレーションに所定の回転を施すことによって生成される第１変調コンステレーション内の点に対応し、該送信シンボルの各々が、特定の数の情報ビットを表す送信機（１０２）と、
該送信シンボルの系列に対して信号処理操作を適用するための受信機（１００）とを備え、該信号処理操作は、チャネル推定値の要素と、該送信シンボルのうちの所与の１つのシンボルとの積を計算するよう構成された少なくとも１つのセレクタ（３０）を利用して実行可能であり、
該セレクタは、第１および第２の制御可能なインバータ（１０−１、１０−２）と、第１および第２のスイッチ（１２−１、１２−２）とから成り、該第１および第２の制御可能なインバータは該チャンネル推定値の要素のそれぞれの実部および虚部を受けとるよう機能し、該第１の制御可能なインバータは第１の制御信号に基づいて該実部を反転しもしくは反転せず、該第２の制御可能なインバータは第２の制御信号に基づいて該虚部を反転しもしくは反転しないよう動作し、該第１および第２のスイッチの各々は、該第１の制御可能なインバータから該反転されたもしくは反転されなかった実部を受けとるよう機能する一方の入力と、該第２の制御可能なインバータから該反転されたもしくは反転されなかった虚部を受けとるよう機能する他方の入力とを有し、該第１および第２のスイッチの各々は、第３の制御信号に応答して、２つのスイッチ入力のうちの１つをスイッチ出力として選択するよう動作し、該第１および第２のスイッチの出力は、該チャンネル推定値と該所与のシンボルとの積のそれぞれの実部および虚部を提供するようになっていることを特徴とするシステム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ディジタル通信システムに関し、特に、ディジタル通信システムで用いられるフィルタリング、チャネル推定、およびチャネル等化のような信号処理操作に関する。
【０００２】
【従来の技術】
チャネルの推定および等化は、ディジタル通信システム受信機において達成されるデータスループットの品質の重要な決定要素である。従来の受信機では、チャネル推定は最小平均二乗（ＬＭＳ）推定として知られる技術を用いて実行されることが多い一方、チャネル等化は、ビタビアルゴリズムによる最尤（ＭＬ）系列検出を用いて実行される。これらの従来技術の問題点は、それらの最初の形では、一般に多くの複素乗算を要することである。具体的には、ＬＭＳ推定は２Ｍ個の乗算を要し、完全探索ビタビアルゴリズムはＰＭ個の乗算を要する。ただし、Ｍはチャネル推定器の次数であり、Ｐはシンボルアルファベットのサイズである。多数の乗算は、特に非常に高いデータレートで要求される計算資源に関して、これらの従来の推定および等化技術を極端に高価なものにすることがある。
【０００３】
ＬＭＳ推定技術のその後の実装では、回帰ベクトルや誤差信号の符号付き近似を用いることにより、必要な乗算数を低減しようとしている（例えば、
・T. A. C. M. Claasen and W. F. G. Mecklenbrauker, "Comparison of the convergence of two algorithms for adaptive FIR digital filters", IEEE Trans. on Acoustics, Speech and Signal Processing, Vol.ASSP-29, No.3, pp.670-678, June 1981
・D. L. Duttweiler, "A twelve-channel digital echo canceler", IEEE Trans. on Communications, Vol.COM-26, No.5, May 1978
・R. D. Gitlin, J. E. Mazo and M. G. Taylor, "On the design of gradient algorithms for digitally implemented adaptive filters", IEEE Trans. on Circuit Theory, Vol.20, No.2, pp.125-136, Mar. 1973
を参照）。しかし、これらの非線形法は、トレーニング速度がかなり低下するようにトレーニング動作を変えることがある。その結果、これらの方法は一般に、長いトレーニング系列が利用可能なアプリケーション（例えば、放送アプリケーション）での使用にしか適さない。
【０００４】
また、実装されたハードウェアのスループットを向上させるために、パイプライン化を導入することも提案されている（例えば、M. D. Meyer and D. P. Agrawal, "A modular pipelined implementation of a delayed LMS transversal adaptive filter", Proc. of ISCAS, New Orleans, pp.1943-1946, 1990、を参照）。しかし、パイプライン化法もまた、ＬＭＳアルゴリズムの学習挙動を劣化させる遅延更新を引き起こす（例えば、
・P. Kabal, "The stability of adaptive minimum mean square error equalizers using delayed adjustment", IEEE Trans. on Communications, Vol.COM-31, No.3, pp.430-432, Mar. 1983
・G. Long, F. Ling and J. A. Proakis, "The LMS algorithm with delayed coefficient adaptation", IEEE Trans. on Acoustics, Speech and Signal Processing, Vol.ASSP-37, No.9, pp.1397-1405, Sept. 1989
・G. Long, F. Ling and J. A. Proakis, "Corrections to 'The LMS algorithm with delayed coefficient adaptation'", IEEE Trans. on Signal Processing, Vol.SP-40, No.1, pp.230-232, Jan. 1992
を参照）。
【０００５】
上記の劣化を保障するためにいくつかの技術が開発されている（例えば、
・M. Rupp and R. Frenzel, "The behavior of LMS and NLMS algorithms with delayed coefficient update in the presence of spherically invariant processes", IEEE Trans. on Signal Processing, Vol.SP-42, No.3, pp.668-672,
March 1995
・E. Bjarnason, "Noise cancellation using a modified form of the filtered-XLMS algorithm", Proc. Eusipco Signal Processing V, Brussel, pp.1053-1056, 1992
を参照）が、このような技術はしばしば、さらに多くの乗算を要する。補償付きの遅延更新ＬＭＳの直接的な実現について、T. Kimijima, K. Nishawa and H. Kiya, "A pipelined architecture for DLMS algorithm considering both hardware complexity and output latency", Proc. Eusipco, Patras, Greece, pp.503-506, Sep. 1998、に記載されている。
【０００６】
【発明が解決しようとする課題】
上記から明らかなように、対応するアルゴリズムのトレーニング動作、数値精度などの望ましい属性を大幅に変えることなく、必要な乗算数を消去または大幅に削減することが可能な、改善されたチャネル推定、チャネル等化およびその他の信号処理技術が必要とされている。
【０００７】
【課題を解決するための手段】
本発明は、チャネル推定、チャネル等化およびその他の信号処理操作での使用に適した効率的な計算技術を提供する。本発明によれば、信号処理操作は、ディジタル通信システム受信機において、受信シンボル系列に対して実行される。各受信シンボルは、いくつかの情報ビットを表す。シンボルは、通常の変調コンステレーション、例えば、ＱＰＳＫコンステレーション、１６−ＱＡＭコンステレーション、６４−ＱＡＭコンステレーション、２５６−ＱＡＭコンステレーション、１０２４−ＱＡＭコンステレーションなどに、所定の回転（例えば、４５°回転）を施すことによって生成される、与えられた変調コンステレーション内の点に対応する。回転したコンステレーションの使用により、有限インパルス応答（ＦＩＲ）フィルタリング、最小平均二乗（ＬＭＳ）推定、および、ビタビアルゴリズムによる最尤（ＭＬ）系列検出のような特定の信号処理操作が、乗算器を必要とせずに実行可能となる。必要な乗算器の個数を消去または大幅に削減することにより、本発明は、対応する信号処理回路に関連する複雑さおよび遅延を大幅に低減する。
【０００８】
本発明の実施例では、信号処理操作は、セレクタを利用して、チャネル推定値係数と、与えられた変調コンステレーションからのシンボルとの乗算を実行する。セレクタは、入力として、チャネル推定値係数の要素の実部および虚部を受け取り、乗法演算を利用することなく、チャネル推定値係数の要素と、与えられたシンボルの対応する要素との積の実部および虚部を出力する。セレクタは、例えば、第１および第２のスイッチと、第１および第２の加減算ユニットを有する。第１および第２のスイッチはそれぞれ、チャネル推定値係数の要素の実部または虚部の一方を、対応する加減算ユニットに送るために選択し、加減算ユニットが、ベクトル内積の実部および虚部の要素を計算するようにする。ＦＩＲフィルタ動作は、加減算ユニットの出力から加減算ユニットの対応する入力へのフィードバックを有することによって、セレクタを用いて実装可能である。セレクタは、与えられたアプリケーションに必要な特定の処理動作を実装するために、多段あるいは階層的加算器ツリー構造として構成することが可能である。
【０００９】
本発明は、いくつかの実施例で乗算を完全に消去するのみならず、チャネルの推定および等化のアルゴリズムで広く用いられているＦＩＲフィルタリングなどの動作を実装する際に必要な加算の数も最小にする。本発明は、ＬＭＳ推定のようなチャネル推定アルゴリズムと、ビタビアルゴリズムによるＭＬ系列検出のような等化アルゴリズムとして実現可能であり、アルゴリズムの数値精度を保持したまま、それらの複雑さを大幅に低減する。例えば、本発明の実施例は、複素値フィルタタップ係数とＱＰＳＫコンステレーション点との乗算を実行するために、選択演算しか必要としない（すなわち、加算器や乗算器は不要である）。
【００１０】
【発明の実施の形態】
以下、本発明について、ＦＩＲフィルタ、チャネル推定器、チャネル等化器およびビタビ復号器のような特定のタイプの信号処理装置に関して説明する。しかし、理解されるように、本発明は、他のタイプの信号処理装置やアプリケーションにも一般的に適用可能である。
【００１１】
［１．基本回転コンステレーション法］
まず、本発明について、ＱＰＳＫ変調に基づく例で説明する。本発明は、ｕi∈｛（１／√２）（±１，±ｊ）｝をコンステレーション点とする図１（ａ）に示すような通常のコンステレーションを用いるのではなく、点ｕi∈｛１，ｊ，−１，−ｊ｝を有する回転されたコンステレーションを利用する。結果として得られる回転コンステレーションを図１（ｂ）に示す。本発明により、コンステレーション点を回転することは、ディジタル変調方式やその送信の動作を変えない。与えられたハードウェアに依存する実装は、伝送チャネルとともに、一般に、いずれにしても、任意の回転を追加するからである。G. M. Durant and S. Ariyavisitakul, "Implementation of a braodband equalizer for high-speed wireless data applications", Proc. IEEE ICUPC 98, Florence, Italy, Oct. 1998、で注意されているように、ｕi∈（１／√２）（±１  ±ｊ）ではなくｕi∈（±１  ±ｊ）を用いることにより、乗算が加減算として実行可能であるため、複雑さが節減される。しかし、図１（ｂ）の回転コンステレーションはこの動作をさらに簡単化する。これについて説明するため、上記のＬＭＳおよびビタビアルゴリズムで広く使用される演算であるベクトル内積の実装を考える。例えば、チャネル推定値の要素は行ベクトルｗ＝［ｗ1，ｗ2，...，ｗM］としてまとめられ、一方、送信される変調されたシンボルは、行ベクトルｕ＝［ｕ1，ｕ2，...，ｕM］としてまとめられる。この場合、計算すべきベクトル内積は次式で与えられる。
【数１】
0004397515.tif 000002
ただし、Ｔは、転置演算を表す。すなわち、各送信シンボルｕi（ｉ＝１，...，Ｍ）と、チャネル推定値重みｗiとの乗算に１つの複素乗算が必要である。複素乗算は通常、４個の実乗算と２個の加減算を要する。すなわち、
ｕiｗi＝Ｒｅａｌ（ｕi）Ｒｅａｌ（ｗi）−Ｉｍａｇ（ｕi）Ｉｍａｇ（ｗi）＋ｊ｛Ｒｅａｌ（ｕi）Ｉｍａｇ（ｗi）＋Ｉｍａｇ（ｕi）Ｒｅａｌ（ｗi）｝次のような、３個の乗算と、さらに多くの加減算による他の実現も可能である。
Ａ＝Ｉｍａｇ（ｕi）×｛Ｒｅａｌ（ｗi）＋Ｉｍａｇ（ｗi）｝    （１）
Ｂ＝Ｒｅａｌ（ｗi）×｛Ｒｅａｌ（ｕi）＋Ｉｍａｇ（ｕi）｝    （２）
Ｃ＝Ｒｅａｌ（ｕi）×｛Ｉｍａｇ（ｗi）−Ｒｅａｌ（ｗi）｝    （３）
ｕiｗi＝Ｂ−Ａ＋ｊ（Ｂ＋Ｃ）    （４）
しかし、回転ＱＰＳＫコンステレーションｕi∈｛１，ｊ，−１，−ｊ｝の構造を考慮に入れると、乗算は完全に消え、次の４つの場合のみが残る。
ｕi＝１：  ｕiｗi＝Ｒｅａｌ（ｗi）＋ｊＩｍａｇ（ｗi）    （５）
ｕi＝ｊ：  ｕiｗi＝−Ｉｍａｇ（ｗi）＋ｊＲｅａｌ（ｗi）    （６）
ｕi＝−１：  ｕiｗi＝−Ｒｅａｌ（ｗi）−ｊＩｍａｇ（ｗi）    （７）
ｕi＝−ｊ：  ｕiｗi＝Ｉｍａｇ（ｗi）−ｊＲｅａｌ（ｗi）    （８）
すなわち、乗算は選択演算となる。以下でさらに詳細に説明するように、加減算さえも不要である。
【００１２】
図２に、図１（ｂ）の回転ＱＰＳＫコンステレーション点ｕi∈｛１，ｊ，−１，−ｊ｝への、ビットｂ1およびｂ0の対の１つの可能なマッピングを示す。まず適当な変換マッピングを施した後、図２のマッピングを行うことにより、グレイ符号化のような任意のマッピングを実装可能である。
【００１３】
図３に、上記の選択演算、すなわち、図２のテーブルおよび上記の式（５）〜（８）による複素乗算を行う、ＱＰＳＫ変調に対する選択演算を実装する基本セレクタ構造を示す。この基本セレクタ構造は、図示のように相互接続された、インバータ１０−１および１０−２と、スイッチ１２−１および１２−２とを有する。図３から明らかなように、選択演算は、乗算や加算を必要としない。その代わりに、ビットｂ0およびｂ1の値に基づいてセレクタを制御するために、いくつかの基本ロジックとともに２の補数ロジックが仮定される。このセレクタ構造では、インバータ１０−１および１０−２はアクティブ・ハイであると仮定される。すなわち、制御信号値が１である場合に反転が実行され、制御信号値が０であるときは入力信号は反転なしで通過する。スイッチ１２−１および１２−２は、制御信号値が１であるときは上の位置に接続され、制御信号値が０であるときには下の位置に接続されると仮定される。
【００１４】
図４および図５に、図２の基本セレクタを利用した、長さＭのベクトル内積を計算する動作のための可能なハードウェア実現を示す。この場合、加法演算を完全に消去することはできない。次のように、（ｋ−１）の位置まで部分和が計算されたと仮定する。
【数２】
0004397515.tif 000003
すると、Ｓkを計算するための次のステップは、
Ｓk＝Ｓk-1＋ｕkｗk，  ｋ＝２，...，Ｍ    （１０）
である。図４の実装は、図３のセレクタの要素とともに、Ｓk-1の実部および虚部をそれぞれｕkｗkの実部および虚部に加算するための加算器１４−１および１４−２を有する。図５の実装は、２の補数演算を加減算ユニット１６−１および１６−２に組み込むことによって、図３のセレクタのインバータ１０−１および１０−２を消去している。このように、和を再帰的に計算する場合、スイッチ１２−１および１２−２ならびにその他の支持ロジック以外には、２個の加減算ユニットしか必要とされない。加減算ユニット１６−１および１６−２は、それらの対応する制御信号の値が１であるときに加法演算を実行すると仮定される。
【００１５】
図６に、追加ハードウェアを必要とすることなく、式（９）に従って完全なＦＩＲ動作を実行することが可能な完全再帰構造を示す。図６の構造は、Ｓk-1の実部および虚部をそれぞれ加減算ユニット１６−１および１６−２の対応する入力に供給するフィードバックを、図５の構造に追加したものに相当する。
【００１６】
［１．１  ＱＡＭコンステレーションへの拡張］
上記の技術は、１６−ＱＡＭコンステレーションに基づく例を参照して以下で説明するように、さらに大きい信号コンステレーションにも適用可能である。図７（ａ）に、１６個のコンステレーション点ｕi∈｛±１±ｊ，±１±３ｊ，±３±ｊ，±３±３ｊ｝のセットを有する１６−ＱＡＭコンステレーションを示す。本発明に従って、図７（ａ）のコンステレーションを４５°回転することにより、図７（ｂ）に示すような回転コンステレーションを得る。図７の（ｃ）〜（ｆ）は、図７（ｂ）の回転コンステレーションの４個の異なる部分（サブセクション）を示す。
【００１７】
この例における各サブセクションは、平行移動したＱＰＳＫコンステレーションに対応する。なお、各サブセクションの中心点は、回転ＱＰＳＫコンステレーション内の点に対応する。そこで、第１のステップで、サブセクションの中心点の選択を行う。これは、前述のような回転ＱＰＳＫコンステレーション内の一点を選択することと同じである。第２のステップで、実際の信号を選択する。これは、前の選択と同様の、別の選択プロセスである。ただし、第１のステップでは、各サブセクションの中心点に対応する値は、加算されるべき補正信号の２倍の大きさである。このため、第２のステップの前に、シフト演算が必要である。すなわち、１６−ＱＡＭコンステレーションからのシンボルとの乗算を実行するためには、対応するチャネル重みを上記の式（５）〜（８）に記載したように選択した後、シフト演算を行い、最後に、別の選択された値を加算することが必要である。これについて図８で説明する。
【００１８】
図８の構造は、セレクタ（ＳＥＬ）３０、左シフト（Ｌ−ＳＨ）要素３２、および再帰セレクタ（ＲＥＣ）３４を有する。図８のセレクタ３０は、図３に示したセレクタに対応し、再帰セレクタ３４は、図４または図５の再帰構造に対応する。左シフト要素３０は、上記の左シフト演算を実行する。
【００１９】
図８の構造によって実現される処理の例は以下の通りである。通常の１６−ＱＡＭコンステレーション内のコンステレーション点（１＋３ｊ）を考える。これは、前述のようにして、（２＋ｊ）にマッピングされる。なお、実際の実装では、１単位の定義は任意であることに注意すべきである。最初のステップで、セレクタ３０によって実行される選択演算に続いて、要素３２によって実行されるシフト演算を用いて２の乗算を実行する。その後、係数にｊを乗じる。これは別の選択演算である。最後に、これらの２つのステップから得られる２つの値を足し合わせる。この複素乗算は、再帰セレクタ３４における２つの実加算を用いて実行される。
【００２０】
図９に、６４−ＱＡＭコンステレーション点との乗算を行う再帰構造を示す。１６−ＱＡＭコンステレーションに対する図８の再帰構造と比較すると、６４−ＱＡＭコンステレーションに対する構造は３段の再帰を要し、したがって、追加の左シフト要素３６および再帰セレクタ３８を有する。当業者には明らかなように、さらに大きいコンステレーションに対する構造も同様にして生成することができる。
【００２１】
［１．２  極小演算］
これまでに説明したような本発明の技術は、計算量を大幅に低減するだけでなく、パイプライン化実装にも適している。以下で詳細に説明するいくつかのアプリケーションでは、限定されたアルファベットサイズからのシンボルを複素値ｗlと乗算する際の可能な結果全体のセットを計算することが重要である。この場合、多くの中間結果が再使用可能であるため、複雑さ（計算量）をさらに低減することができる。
【００２２】
図７の１６−ＱＡＭコンステレーションの第１象限を例にとると、４個の可能な係数は次の通りである。
Ａ＋ｊＢ＝ｗR＋ｊｗI    （１１）
Ｃ＋ｊＤ＝３ｗR＋３ｊｗI    （１２）
Ｅ＋ｊＦ＝２ｗR−ｗI＋ｊ（２ｗI＋ｗR）    （１３）
Ｇ＋ｊＨ＝２ｗR＋ｗI＋ｊ（２ｗI−ｗR）    （１４）
第１行の演算にはコストがかからないが、第２行は２個の加算を要し、第３行および第４行も同様である。他のすべての値は、何回かｊを乗じることから導くことができるため、実部と虚部の値を入れ替えて反転することにより得られる。８個の異なる値（Ａ〜Ｈ）のみが関連しているため、追加の８個のインバータがあればよい。したがって、全コストは、６個の加算器および８個のインバータ、あるいは同じことであるが、１４個の加減算である。同様に、この方法を６４−ＱＡＭコンステレーションに適用した場合には、３６個の加減算と３２個のインバータが必要となる。
【００２３】
［２．実装例］
以下、上記の技術を用いて、どのようにしてＦＩＲフィルタ、ＬＭＳアルゴリズムおよびビタビアルゴリズムを用いたＭＬ系列検出を実行することができるかについて説明する。
【００２４】
［２．１  ＦＩＲフィルタ］
図１０に、さまざまなタイプの変調について、セクション１．１の技術を用いて実装されるＦＩＲフィルタに必要とされる演算数を、従来のＦＩＲフィルタの場合と比較したテーブルを示す。Ｍ個の複素値係数を有する従来のＦＩＲフィルタは、４Ｍ個の実乗算および（４Ｍ−２）個の実加算を要する。図１０のテーブルは、本発明の技術を適用するときに必要な実加減算の数を示す。このテーブルからわかるように、１０２４−ＱＡＭのような大きいコンステレーションの場合でも、本発明の技術では複雑さ（計算量）はかなり小さい。
【００２５】
図１１に、乗算に図９の６４−ＱＡＭブロックの連接を用いたＦＩＲフィルタチェインの可能な実装を示す。連接された６４−ＱＡＭブロックを４０−１，４０−２，...，４０−Ｍで示す。ブロック４０−１，４０−２，...，４０−Ｍの出力は、対応する加算器４２−１，４２−２，...，４２−（Ｍ−１）で結合される。別の可能な方法では、乗算のすべての第１段をまず結合してから、第２段を結合し、最後に第３段を結合する。この方法では、仮数の長さおよびチップ面積を節約することができる。Ｍの代表的な値は３〜６４であり、１０２４−ＱＡＭ以下のコンステレーションが通常使用される。
【００２６】
ただし、高次のＦＩＲフィルタを実装することは一般に、加算器の長いチェインを要することに注意すべきである。多くのアプリケーションでは、追加のレジスタによるレイテンシの増大およびチップ面積の増大を代償にスループットを増大させるために、この構造にパイプライン化を適用することができる。また、本発明の新規なセレクタ技術は一般に、各シンボルごとに数ビットの情報（例えば、ＱＰＳＫでは２ビット）しか記憶する必要がないため、追加レジスタによる技術のパイプライン化実装は一般に、あまり多くの面積の増大を必要としないことにも注意すべきである。
【００２７】
また、注意すべき点であるが、ＬＭＳアルゴリズムのようないくつかのアプリケーションでは、レイテンシが許容されない。この場合、階層ツリー構造を用いて、遅延を（Ｍ−１）ＴaからＴaｌｏｇ2Ｍに低減することができる。ただし、Ｔaは、１個の加算器の遅延時間である。このようなツリー構造を実装するためには、図３の基本セレクタ構造が好ましい。ただし、この場合一般に、２個の２の補数インバータが各係数に（すなわち、全部で２Ｍ個のこのようなインバータが）必要となる。これらの２の補数インバータは、セル面積を必要とするだけでなく、標準的な加算器と同様のキャリーリプル効果を引き起こし、追加遅延を生じる。この追加遅延を避ける構造について、以下で図１２、図１３および図１４を参照して説明する。
【００２８】
図１３に、２つの数ＡとＢの加算または減算を行う（すなわち、演算Ｚ＝±Ａ±Ｂを実行する）のに適した高速ＦＩＲフィルタ実装のための基本加減算構造を示す。このような演算のためには、２つの加減算構造、または、１つの加減算および追加インバータが一般に必要である。しかし、符号信号を別に扱えば、図１３に例示するように、スイッチの対５０−１、５０−２と、１個の加減算構造５２で十分である。これにより、レイテンシとともに面積も節約される。演算を効率的に実現するために、２つの数ＡおよびＢに対する符号情報Ｓ（Ａ）およびＳ（Ｂ）を与えなければならない。演算の結果は、次のような、新たな符号情報Ｓ（Ｚ）と、加減算選択（ＡＤＤ／ＳＵＢ）とを有する符号付き数Ｚである。
Ｓ（Ｚ）＝Ｓ（Ａ）∧Ｓ（Ｂ）    （１５）
【数３】
0004397515.tif 000004
「ウェッジ」演算子∧は、論理ＡＮＤ演算を表す。図１２に、符号演算子と、出力信号Ｚに関して、４個の可能な演算を列挙するテーブルを示す。さらに、減算の場合（Ａ−Ｂ、Ｂ−Ａ）に正しい入力を選択するためにはマルチプレクサが必要である。数Ｚは、その符号Ｓ（Ｚ）とともに、後続の加算器構造に渡される。第１段には、係数のための追加セレクタのみがあればよい。２個の数ＡとＢを加算するには、最初の演算Ａ＋Ｂのみがあればよい。
【００２９】
図１２および図１３で説明したように符号を別個に扱うと、いくつかの追加の利点もある。例えば、ＱＰＳＫコンステレーションは（より大きなＱＡＭコンステレーションも同様）、ＡおよびＢの符号に対してさまざまな値を割り当てることによって実現可能である。したがって、変調は、既に加算器ツリーの一部となっている。図１４に、この特徴を例示する、高速ＦＩＲフィルタ実装のための加算器ツリーの第１段を示す。このツリーの第１段は、図示のように相互接続されたスイッチ６０−１、６０−２、６０−３および６０−４と、加減算ユニット６２−１および６２−２とを有する。
【００３０】
符号を別個に扱うもう１つの利点は、符号情報を、加算器ツリーにおける次の加減算段に渡すことができ、それにより、追加のインバータを必要とせずに後続の加法演算に符号情報を含めることができる点である。ツリー構造の最後では、符号の最終的補正を行うために１個のインバータが必要となることがある。以下のセクションで示されるように、ＬＭＳアルゴリズムは、この符号情報を直接に使用することが可能であり、この最後のインバータさえも不要である。
【００３１】
前述のように、加算器ツリーは図１３に示すような加減算構造を有し、第１段は、係数の選択と加法演算を結合することができる。これを図１４の構造に示す。これは、２個の複素係数ＡR＋ｊＡI、およびＢR＋ｊＢIが、対応するビット｛ａ0，ａ1｝および｛ｂ0，ｂ1｝でＱＰＳＫ変調されることを仮定する。出力ＺR＋ｊＺIの出力符号情報は次式で与えられる。
【数４】
0004397515.tif 000005
後続の加算器段は、式（１５）および（１６）に従って直接に構成される。
【００３２】
［２．２  ＬＭＳアルゴリズム］
ＬＭＳアルゴリズムは、計算量（複雑さ）が２Ｍであり、一般に、１つの複素入力に対して８Ｍ個の実乗算を要する。その計算量は、次の２段階により定義される。すなわち、誤差方程式
ｅ（ｉ）＝ｄ（ｉ）−ｕiｗiT    （１９）
ただし、
ｕi＝［ｕ（ｉ），ｕ（ｉ−１），...，ｕ（ｉ−Ｍ＋１）］    （２０）
と、係数更新方程式
ｗi+1＝ｗi＋μｅ（ｉ）ｕi*    （２１）
ただし、
ｗi＝［ｗi（０），ｗi（１），...，ｗi（Ｍ−１）］    （２２）
であり、ｗi（ｌ）は、時刻ｉにおけるタップ重みを表し、添字ｌは０からＭ−１までにわたる。前セクションで説明した技術を適用すれば、誤差ｅ（ｉ）の計算のための乗算を、選択および加減算で置き換えることができる。係数更新（式（２１））を計算するため、ステップサイズμが２の累乗（μ＝２-t）である場合、乗算μｅ（ｉ）は、簡単なシフト演算子で置き換えることができる。シンボルｕiとの残りの乗算も、本発明の新規な技術で達成される。あと残るのは係数を更新することだけであり、これは複素加算である。
【００３３】
図１５に、さまざまな変調方式について、本発明の技術を用いて実装した場合の、ＬＭＳアルゴリズムの計算量および最小レイテンシのテーブルを示す。ＱＰＳＫコンステレーションは、誤差方程式と、係数の更新とを評価するために、２Ｍ個の加減算を要する。１６−ＱＡＭの場合、誤差計算は４Ｍ個の加減算を要し、乗算ｅ（ｉ）ｕi*は２Ｍ個の加減算を要し、係数更新は２Ｍ個の加減算を要する。すなわち、全部で８Ｍ個の加減算を要する。まとめると、ＱＰＳＫ、１６−ＱＡＭおよび６４−ＱＡＭコンステレーションに対して、それぞれ、４Ｍ、８Ｍおよび１２Ｍ個の加減算を要する。このように、コンステレーションサイズが４倍に増大すると、さらに４Ｍ個の追加演算が必要となる。
【００３４】
セクション２．１で述べたように、より高速な実現が要求されることがある。ＬＭＳアルゴリズムの場合、更新は、誤差信号が利用可能になるまで実行することができない。このため、非常に高速なＦＩＲフィルタチェインが重要となる。これは、セクション２．１で説明した階層ツリー構造を用いて実現される。図１６に、このタイプの例示的な実装を示す。これは、加減算ユニット７０−１および７０−２、セレクタ７２−１〜７２−４、ならびに加減算階層ツリー構造７４を有する。この場合の誤差信号の計算は、追加の減算ｅ（ｉ）＝ｄ（ｉ）−ｕiｗiTを要する。フィルタの次数をＭ＝２L−１となるように選んだ場合、ｄ（ｉ）は、１個のフィルタタップ重み要素として扱うことができ、追加遅延は不要である。
【００３５】
前述のように、最後の信号（この場合は誤差信号）の符号に依存して、最後の２の補数インバータが必要となることがある。これは、追加遅延のコストがかかることになる。２の補数インバータはキャリーリプル効果を引き起こすためである。しかし、ＬＭＳアルゴリズムでは、最後のインバータは、係数更新の選択プロセスに含めることが可能である。すなわち、負の情報がアクティブである場合、μｅ（ｉ）ではなく−μｅ（ｉ）が加えられる。
【００３６】
この修正されたセクションは、より高速である。これは簡単な論理ゲートによって実現され、加算器構造を必要としないからである。ＱＰＳＫの場合、１回の更新サイクルで、ＦＩＲ誤差部分にステップサイズμを乗算するために、Ｔaｌｏｇ2Ｍ（おそらくはＴa）を要し、最後に、係数の更新に１回の加算を要する。したがって、最小更新時間は、（ｌｏｇ2Ｍ＋２）Ｔaで与えられる。ステップサイズμが２の負べきである場合、誤差との乗算は簡単なスケーリング演算であるため、追加時間遅延なしで実現可能である。他のステップサイズの値は、２個のこのような値の和で近似することができる（すなわち、
【数５】
0004397515.tif 000006
）ため、誤差との乗算には１個の加減算で十分である。この操作は、可能なステップサイズの値の範囲を広くする。可能な追加演算は、図１６において破線のボックス７５で示されている。
【００３７】
例として、次数Ｍ＝１５のチャネル推定器をトレーニングするためにＬＭＳアルゴリズムを適用し、使用される技術は、１ｎｓで加減算を実行し、６ｎｓで乗算を実行すると仮定する。この場合、ＢＰＳＫ／ＱＰＳＫトレーニング系列の完全な更新は、加減算により６ｎｓで実行することができるが、乗算器を使用すると約１２ｎｓかかる。他方、必要なチップ面積およびパワー消費は、乗算器を実装すると１０倍大きくなる。この場合、１／６ｎｓ＝毎秒１６６Ｍシンボルまでのリアルタイム処理が可能である。
【００３８】
［２．３  ＭＬ系列検出］
シンボル間干渉（ＩＳＩ：Inter-Symbol Interference）を生じるチャネルを通じて情報を伝送するディジタル通信システムでは、最適な検出器は最尤シンボル系列検出器（ＭＬＳＤ：Maximum-likelihood symbol sequence detector）である。これは、例えば、
・J. G. Proakis, "Channel equalization", The Communications Handbook, CRC Press, 1997, Chapter 26
・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
に記載されている。
【００３９】
ＭＬＳＤを実現する効率的なアルゴリズムはビタビアルゴリズムである。これは、もともと畳込み符号を復号するために考案されたものである（前掲のJ. G. Proakisの文献、および、G. D. Forney, Jr., "The Viterbi algorithm", IEEE Proceedings, Vol.61, pp.268-278, March 1973、を参照）。この場合、ＩＳＩチャネルは、ＰM-1個の状態を有するトレリスと呼ばれる有限状態機械（ＦＳＭ）としてモデル化される。ここで、Ｐは、情報シンボルアルファベットサイズであり、Ｍは、複素値チャネルＦＩＲフィルタ係数ｗlの個数である。トレリスには、各状態から分かれるＰ個の遷移があり、これらは、情報シンボルｕ（ｋ）のＰ個の相異なる値に対応する。状態間の遷移に対応する値はｗlｕ（ｋ）であり、これは、与えられた推定チャネル係数ｗlに対する可能な受信値である。
【００４０】
受信系列がｒ（ｋ）であり、推定チャネル係数がｗlであり、入力情報シンボルがｕ（ｋ）であると仮定すると、ビタビアルゴリズムは、トレリス内で、ノイズを含む受信系列ｒ（ｋ）にユークリッド距離で最も近いパスを再帰的に求めることによって、最尤送信シンボル、バーｕ（ｋ）を求める。すなわち、バーｕ（ｋ）に関して次式を再帰的に最小にすることによって、ＭＬ検出器判断基準を実装する。
【数６】
0004397515.tif 000007
各再帰ステップで、ビタビアルゴリズムは、ＰM個の可能な遷移にわたる探索を行う。チャネルモデル係数が再帰ごとに異なる場合、Ｍ個の推定チャネル係数ｗlのそれぞれについて、シンボルアルファベットのＰ個のシンボルとのＰ回の乗算が必要である。このため、さまざまな項を最初に比較するためには全部でＰＭ＝Ｏ（ＰＭ）個の複素乗算が必要である。ＦＳＭ内の状態間のＰM個の遷移のコストメトリックを計算するためには、さらに（Ｍ−１）×ＰM＝Ｏ（ＭＰM）個の複素加算が必要である。通常の方法を用いてこれを行う場合、複素乗算は、シンボルに依存して４〜８個の加減算で実行される。例えば、値（３＋７ｊ）は、３による乗算に１個の加算（３＝１＋２）を要し、７には１個の減算を要する（７＝８−１）。これは、係数の実部および虚部で実行する必要があるため、Ｏ（ＰＭ）＝４ＰＭとなる。最後に、実部および虚部をｒ（ｋ）に加算する必要があり、さらに２個の加算を要する。したがって、Ｍ個の係数およびＰM個の状態のすべてに対して、全部でＯ（ＭＰM）＝２ＭＰM個の加算がある。
【００４１】
上記のセクション１．１で説明したような本発明の技術を用いると、計算量を大幅に低減することができる。ＱＰＳＫの場合、各係数ｗlとｕ（ｋ）との乗算は選択プロセスとなり、Ｏ（ＭＰM）＝０である。遷移の計算のみが、式（１６）の
【数７】
0004397515.tif 000008
を計算するために、Ｏ（ＭＰM）＝２ＭＰMが残る。１６−ＱＡＭの場合、第１段階は選択プロセスであり、次の段階は、それぞれシンボルごとに乗算を計算する２個の加減算であるため、Ｏ（ＰＭ）＝２ＰＭ＝３２Ｍである。６４−ＱＡＭの場合、４個のシンボルからなるそれぞれのサブセットで、乗算を計算するために１０個の加減算が必要であるため、Ｏ（ＰＭ）＝１６０Ｍである。この技術の適用は、追加のレジスタのためにあまり多くのチップ面積を追加せずにパイプライン化が容易に可能であるという追加の利点を有する。
【００４２】
パイプライン化の複雑さの増大とひきかえに、セクション１．２で説明した極小演算は、さらに計算の複雑さを低減することができる。例えば、１６−ＱＡＭ変調の場合、Ｏ（ＰＭ）＝１４Ｍであり、６４−ＱＡＭの場合、Ｏ（ＰＭ）＝６８Ｍとなる。
【００４３】
等化プロセスの最初にトレリスを初期化することは、一度シンボルアルファベット内のすべての要素ですべての可能な乗算を計算することを要する。これは、チャネルが１フレームのデータにわたり一定であることを仮定する。チャネルがシンボルごとに急速に変化している場合、この初期化は、トレリスの遷移値を更新する再帰ごとに実行しなければならない。得られる値は、ビタビアルゴリズムでユークリッドノルムを計算するために、ルックアップテーブルに記憶することができる。図１７に、さまざまなタイプの変調について、セクション１．１およびセクション１．２の実装の初期化の複雑さ（Ｏ（ＰＭ））を、従来の実装と比較したテーブルを示す。
【００４４】
ビタビアルゴリズムの完全な計算量を得るためには、トレリス中の完全探索を行う場合はＯ（ＭＰM）を加える必要がある。この部分は、Ｏ（ＰＭ）の初期計算量を容易に超過することがある。そのため、例えば、M. Eyuboglu and S. Qureshi, "Reduced-state sequence estimation for coded modulation on intersymbol interference channels", IEEE Journal on Selected Areas in Communications, Vol.7, pp.989-995, August 1989、に記載されている、トレリス中の探索を限定する簡約状態系列推定法のような計算量縮小技術を適用することが可能である。この場合、初期計算量は非常に大きくなることがある。加算を実装するために本発明によるツリー構造を使用することにより、上記のセクション１．１で説明したように、計算量をさらに縮小することが可能である。
【００４５】
［３．受信機の例］
図１８に、上記の信号処理操作を実装可能な受信機１００の実施例を示す。受信機１００は、送信機１０２によって送信されたシンボル系列を受信する。シンボルは、上記のように回転されたコンステレーションに従って送信機１０２によって送信される。受信機１００は、ビタビアルゴリズムを実装するＭＬ系列検出器（ＭＬＳＤ）１０４を有する。ＭＬＳＤ１０４は、ＬＭＳ推定器１０６と並列に接続される。ＭＬＳＤ１０４およびＬＭＳ推定器１０６の一方または両方は、上記の計算技術を用いて実装される。ＬＭＳ推定器１０６からのチャネル推定値は図示のようにＭＬＳＤに供給される。オプションとして、チャネル復号器１０８も受信機１００に含まれる。
【００４６】
図１９に、本発明を実装可能なもう１つの例示的な受信機１２０を示す。受信機１２０は、判定フィードバック等化（ＤＦＥ：decision feedback equalization）技術を実装し、ＭＬＳＤ１０４、ＬＭＳ推定器１０６およびオプションのチャネル復号器１０８を有するとともに、フィードフォワードフィルタのセット１２２およびフィードバックフィルタのセット１２４を有する。この場合、ＬＭＳ推定器の出力は、フィードバックフィルタのセット１２４の適応フィルタタップを決定するために使用される。受信シンボルは、フィードフォワードフィルタ１２２を通して処理された後、ＭＬＳＤ１０４に送られる。ＭＬＳＤの出力は、フィードバックフィルタ１２４を通してフィードバックされる。
【００４７】
なお、注意すべき点であるが、図１８および図１９の構成は単なる例示であり、他の実施例は、要素の異なる構成や明示的に図示していない追加要素を含むことも可能である。
【００４８】
【発明の効果】
［４．結論］
本発明は、ＰＳＫあるいはＱＡＭコンステレーション内のコンステレーション点と係数との乗算を必要とする計算アルゴリズムの実装のために計算量を大幅に低減することを可能にする効率的な計算の方法および装置を提供する。乗算を、より簡単な関数で置き換えることにより、チップ面積とレイテンシを縮小することができる。なお、この技術を適用しても、近似や精度の低下は起こらず、単に、面積を要求する演算および時間を要求する演算が除去されるだけであることに注意すべきである。
【００４９】
注意すべき点であるが、上記の実施例は、ハードウェア、ソフトウェア、または、ハードウェアとソフトウェアの組合せのいずれでも実現可能である。例えば、図３〜図６、図８、図９、図１１、図１３、図１４および図１６に例示した計算構造は、ディジタル通信システム受信機のチャネル推定器、チャネル等化器、復調器、復号器あるいはその他の要素で用いられる特定用途向け集積回路（ＡＳＩＣ）あるいはその他のディジタルデータ処理デバイスの要素として実現可能である。
【図面の簡単な説明】
【図１】（ａ）は、通常のＱＰＳＫコンステレーションの例を示し、（ｂ）は、回転したＱＰＳＫコンステレーションの例を示す図である。
【図２】本発明による回転ＱＰＳＫコンステレーション点への２ビットのマッピングを示すテーブルの図である。
【図３】本発明に従って、係数と、ＱＰＳＫコンステレーションからのシンボルとの複素乗算を実行する基本セレクタ動作の図である。
【図４】本発明に従って、図３の基本セレクタ動作を利用したフィルタ動作を実行する他の構成を示す図である。
【図５】本発明に従って、図３の基本セレクタ動作を利用したフィルタ動作を実行する他の構成を示す図である。
【図６】本発明による完全ベクトル積計算のための再帰加減算を示す図である。
【図７】１６−ＱＡＭコンステレーションの回転と、その４個のサブセットへの分割を示す図である。
【図８】本発明による１６−ＱＡＭセットにおける乗算の２ステップチェインを示す図である。
【図９】本発明による６４−ＱＡＭセットにおける乗算の３ステップチェインを示す図である。
【図１０】本発明に従って、Ｍ個の複素値タップを有するＦＩＲフィルタを実装するために必要な加減算数を示すテーブルの図である。
【図１１】本発明による乗算のための６４−ＱＡＭブロックを有するＦＩＲフィルタチェインを示す図である。
【図１２】本発明による選択演算を示すテーブルの図である。
【図１３】本発明に従ってＦＩＲフィルタを実装する基本加減算構造を示す図である。
【図１４】本発明に従ってＦＩＲフィルタを実装する加算器ツリーの第１段を示す図である。
【図１５】相異なるタイプの変調に対して、本発明によるＬＭＳ技術における、必要な加減算数と対応するレイテンシとを比較するテーブルの図である。
【図１６】本発明によるＬＭＳ更新動作を示す図である。
【図１７】相異なるタイプの変調に対して、本発明に従って、ビタビアルゴリズムのトレリスを初期化するために係数あたり必要な加減算数を比較するテーブルの図である。
【図１８】本発明の技術を実装可能な通信システム受信機の例を示す図である。
【図１９】本発明の技術を実装可能な通信システム受信機の例を示す図である。
【符号の説明】
１０  インバータ
１２  スイッチ
１４  加算器
１６  加減算ユニット
３０  セレクタ（ＳＥＬ）
３２  左シフト（Ｌ−ＳＨ）要素
３４  再帰セレクタ（ＲＥＣ）
３６  左シフト要素
３８  再帰セレクタ
４０  ６４−ＱＡＭブロック
４２  加算器
５０  スイッチ
５２  加減算構造
６０  スイッチ
６２  加減算ユニット
７０  加減算ユニット
７２  セレクタ
７４  加減算階層ツリー構造
１００  受信機
１０２  送信機
１０４  ＭＬ系列検出器（ＭＬＳＤ）
１０６  ＬＭＳ推定器
１０８  チャネル復号器
１２０  受信機
１２２  フィードフォワードフィルタ
１２４  フィードバックフィルタ
【図１】
0004397515.tif 000009
【図２】
0004397515.tif 000010
【図３】
0004397515.tif 000011
【図４】
0004397515.tif 000012
【図５】
0004397515.tif 000013
【図６】
0004397515.tif 000014
【図７】
0004397515.tif 000015
【図８】
0004397515.tif 000016
【図９】
0004397515.tif 000017
【図１０】
0004397515.tif 000018
【図１１】
0004397515.tif 000019
【図１２】
0004397515.tif 000020
【図１３】
0004397515.tif 000021
【図１４】
0004397515.tif 000022
【図１５】
0004397515.tif 000023
【図１６】
0004397515.tif 000024
【図１７】
0004397515.tif 000025
【図１８】
0004397515.tif 000026
【図１９】
0004397515.tif 000027