(57)【要約】【解決手段】  情報は、複数の送信アンテナからのＭＩＭＯチャネルでの送信により受け取った信号で検出される。情報は、時空間および／または周波数上のＱＡＭシンボルとして符号化される。  検出の方法は、階層的木構造へ、利用可能なＱＡＭシンボルを配置することを具備し、木構造の各々のレベルは以前のレベル）よりも大きい粒度のレベルを提供していて、最小の細部以降の前記木構造の各々のレベルに対して  レベルの中で木構造の各々の選択された枝に対して、枝尤度測度を決定し、枝の中のシンボルを含む受信された信号の近似尤度を示し、それらの枝尤度測度に基づいて１つ以上の枝を選択し、選択された枝は木構造の次のレベルを考慮して選択されていて、最後のレベルでは、各々の枝はシンボルに対応し、枝尤度測度は、対応するシンボルを含む受信された信号の尤度に対応させることを具備する。対応する検出装置はさらに提供される。【選択図】図１
2009545190.tif 000002
【特許請求の範囲】
【請求項１】
複数の送信アンテナからのＭＩＭＯチャネルでの送信により受け取った信号により運ばれる情報を検出する方法であって、前記情報は、時空間および／または周波数上でＱＡＭシンボルとして符号化されていて、前記方法は、
階層的木構造へ、前記利用可能なＱＡＭシンボルを配置し、前記木構造の各々のレベルは以前のレベルよりも大きい粒度のレベルを提供していて、最小の細部以降の前記木構造の各々のレベルに対して、
前記レベルの中で前記木構造の各々の選択された枝に対して、枝尤度測度を決定し、前記枝の中のシンボルを含む受信された信号の近似尤度を示し、それらの枝尤度測度に基づいて１つ以上の前記枝を選択することを具備し、前記選択された枝は前記木構造の次のレベルを考慮して選択されていて、
最後のレベルでは、各々の枝はシンボルに対応し、前記枝尤度測度は、前記対応するシンボルを含む前記受信された信号の尤度に対応させることを特徴する方法。
【請求項２】
枝尤度測度の決定ステップは、枝の擬似シンボルを含む前記受信された信号の前記尤度を決定することを具備し、１つの枝に対する１つの擬似シンボルは、前記枝により示される前記シンボルの関数であることを特徴とする請求項１に記載の方法。
【請求項３】
枝の擬似シンボルは、前記枝によって示される前記シンボルの平均であることを特徴とする請求項２に記載の方法。
【請求項４】
１本以上の枝を選択するステップは、複数の前記枝を選択することを具備し、考慮する際には前記複数の枝は全体の枝の数よりも少ないことを特徴とする請求項１から請求項３のいずれか１項に記載の方法。
【請求項５】
選択ステップは、前記決定ステップにおいて決定された前記枝尤度測度のうちの最も高い尤度測定をもつ枝を選択することを具備することを特徴とする請求項１から請求項４のいずれか１項に記載の方法。
【請求項６】
複数の送信アンテナを有する送信機および複数の受信アンテナを具備する受信機を具備するＭＩＭＯシステムにおける情報通信の方法であって、
各々のシンボルが許可されたシンボルの１セットのメンバであるシンボルとして、情報を符号化し、
時空間および／または周波数に従い変調された前記シンボルを前記送信アンテナで送信することを具備し、その後、受信機において請求項１から請求項５の情報検出方法にしたがって情報を復号することを特徴とする方法。
【請求項７】
複数の送信アンテナからのＭＩＭＯチャネルでの送信により受け取った信号で生成される情報を復号する復号器であって、前記信号は複数の受信アンテナで受信され、前記情報は時空間および／または周波数上で一連のＱＡＭシンボルとして符号化されていて、
前記利用可能なＱＡＭシンボルの階層的木構造であり、前記木構造の各々のレベルは、以前のレベルよりも大きい粒度のレベルを提供して格納する手段と、
前記木の各々のレベルおよび前記レベルの前記木構造の各々の選択された枝において、前記枝の中のシンボルを含む受信された信号の近似尤度を示す、枝尤度測度を決定する手段と、
枝尤度測度に基づいて前記枝の１つ以上を選択する手段とを具備し、
前記選択された枝は前記木構造の次のレベルを考慮して選択され、
最後のレベルでは、各々の枝はシンボルに対応し、前記枝尤度測度は、前記対応するシンボルを含む前記受信された信号の尤度に対応させて、
前記選択手段は、尤度測度の決定および考慮のために１つ以上のシンボルを選択することを具備することを特徴とする復号器。
【請求項８】
情報を複数のシンボルとして符号化することが可能であり、各々のシンボルは許可されたシンボルの１セットのメンバであり、前記送信アンテナで時空間および／または周波数に従って変調された前記シンボルを送信する、複数の送信アンテナを有する送信機と、
前記情報の復号することが可能であり、複数の受信アンテナと請求項７に記載の復号器とを具備する受信機と、を具備するＭＩＭＯ通信システム。
【請求項９】
汎用コンピュータ通信装置が請求項１から請求項６のいずれか１項に従う方法を行うように設定することが可能なコンピュータ読み取り可能な命令を格納することを特徴とするコンピュータプログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は多重化送信機からの送信の復号に関するが、特に、空間多重されたＭＩＭＯシステムのみとは限らない。
【背景技術】
【０００２】
ＭＩＭＯ通信は、ＭＩＭＯチャネル上で生まれたシンボルの受信機における検出を含む。これを達成する１つの評判のよい方法は、Ｓｐｈｅｒｅ Ｄｅｃｏｄｅｒ（ＳＤ）を用いることである。Ｓｐｈｅｒｅ Ｄｅｃｏｄｅｒの動作原理は、"Improved methods for calculating vectors of short lengths in a lattice, including a complexity analysis," (U. Fincke and M. Pohst, Mathematics of Computation, Vol. 44, No. 3, pp. 463-471, (Apr. 1985))の中で開示される。ＳＤの複雑さは、無線チャネルによって非常に影響される。したがって、検出処理のための固定記憶および計算資源を割り当てる実際の適用には、その技術は不適当である。  
別の効率的な最先端技術の方法はｓｅｑｕｅｎｔｉａｌ Ｇａｕｓｓｉａｎ ａｐｐｒｏｘｉｍａｔｉｏｎ（ＳＧＡ）アルゴリズムである。これは固定の複雑さおよびメモリ要求の実際的な制約に対して最適性能（ｐｅｒｆｏｒｍａｎｃｅ）近く達成することが実証されている。ＳＧＡアルゴリズムの鍵となるステップは、Ｍ個の最も有意なシンボルの組み合わせを識別することであり、ＮＴアンテナおよびＮ−ＱＡＭ変調を備えたＭＩＭＯシステム用のＭＮＮＴ個のシンボル確率の計算および並び替えを必要とする。ＳＧＡアルゴリズムの複雑さは、ＳＤの複雑さよりは少ないが、大きいコンスタレーションサイズ（constellation size）（例えば１６ＱＡＭ、６４ＱＡＭ）を備えたＭＩＭＯシステム用のＳＧＡアルゴリズムの実際的な実装は、まだかなりの計算コストを含んでいる。  
より大きなコンスタレーション（ｃｏｎｓｔｅｌｌａｔｉｏｎ）は、マルチレベル構造を表す。マルチレベル構造は、様々な状況で過去に複雑さ低減のために使用されていた。例えば、D. Guo, X. Wang, and R. Chen, "Multilevel mixture kalman filter," (EURASIP Journal of Applied Signal Processing, Vol. 15, pp. 2255-2266, Nov 2004), Y.L.C.de Jong and T.J. Willink, "Iterative tree search detection for MIMO wireless systems" (Vol. 53, No. 6 pp. 930-935, Jun. 2005. IEEE Trans. On Wireless Communications) and Y.L.C.de Jong and T.J. Willink, "Iterative trellis search detection for asynchronous MIMO systems" (In proc. IEEE VTC'2003,pp503-507, Oct. 2003)。
【発明の概要】
【０００３】
もとのＳＧＡアルゴリズムは、擬似シンボルの組み合わせのＭＮ個の近似シンボル確率を計算し、ＮＴ本のアンテナにとって最も高い確率をもつこれらのＭ個を選択するが、本発明の第１の態様は、擬似シンボルの組み合わせの４Ｍ個の近似シンボル確率を計算し、最初の繰り返しで各々のアンテナにおけるｌｏｇ４（Ｎ）ステージで最も高い確率をもつこれらのＭ個を選択する。  
本発明は、発明の方法のどんなものでも実行するため、および／または発明のどんな態様の装置としても設定されるようになるために、コンピュータ装置がコンピュータプログラムによって実行されるように、設定されたことにより具体化されうることが認識されるだろう。その場合、コンピュータプログラムは、いかなる実際的な手段によって取り入れることができる。例えば、光学または磁気の記憶媒体によって、例えばインターネットによって実行されるダウンロードを通して受信された信号によって、スマート・カード、フラッシュ・メモリーあるいは他の集積回路蓄積手段によって、あるいはＡＳＩＣのような特定用途向けハードウェアを使用する構成によって取り入れられる。
【図面の簡単な説明】
【０００４】
【図１】本発明の特定の実施形態に従うＭＩＭＯデータ通信システムの概念図を示す。
【図２】ＳＧＡに従う有意なシンボルの組み合わせを識別する方法を示す。
【図３】本発明の典型的な実施形態に従うＱＡＭ配置に配列された階層木を示す。
【図４】図３に示されたＱＡＭ配置の木構造のさらに詳細を示す。
【図５】本発明のさらに典型的な実施形態に従う擬似シンボルのマルチレベルのセットを示す。
【図６】本発明が説明された実施形態に従うマルチレベル識別処理を示す。
【図７】本発明が説明された実施形態の使用例におけるモデル化された性能（ｐｅｒｆｏｒｍａｎｃｅ）特性を示す。
【図８】本発明が説明された実施形態に従う有意なシンボルの組み合わせの識別の中で実行される処理を示す。
【発明を実施するための形態】
【０００５】
本発明の特定の実施形態は、例のみとしておよび添付の図面を参照して説明されるだろう。  
図１は、送信装置１２および受信装置１４を具備するＭＩＭＯデータ通信システム１０を図示する。  
送信装置１２はデータソース１６を含む。それはチャネル符号器１８にデータ（情報ビットまたはシンボルを具備する）を供給する。この例におけるチャネル符号器１８は、再帰型組織畳込み（ＲＳＣ）符号器のような畳み込み符号器を含む。  
チャネル符号器１８は、符号器から出力されるビットの方が入力されたビットよりも多くなるように操作する。また、典型的にその割合は２分の１または３分の１である。
【０００６】
説明された実施形態では、チャネル符号器は、符号化されたビットをチャネルインタリーバ２０に差し出し、時空間符号器２２に差し出す。  
チャネルインタリーバ２０は、ビットをシンボルへインタリーブする。それは、同じアンテナからのデータフレーム中の、ある位置のビットの繰り返された送信のためにエラーが発生しないか、送信の中断によるエラーができる限り回復されることができるように隣接したビットが分離されることをいくぶんか保証する。
【０００７】
時空間符号器２２は、複数の送信アンテナ２５を具備する送信アンテナアレー２４からの同時送信用に、入力されたシンボルまたは複数のコード・シンボルであるシンボルを符号化する。この図示された例では、３本の送信アンテナ２５が与えられる。一般的な場合では、送信アンテナの数はＮＴ本で設計される。符号化されて送信された信号は、送信アンテナアレー２４と対応する受信装置１６の受信アンテナアレー２６との間で定義された、ＭＩＭＯチャネル２８を通して伝搬する。  
受信アンテナアレー２６は、受信装置１６の時空間（または周波数）復号器３０に複数の入力を与えるＮＲ本の受信アンテナ２７を含む。この特定の実施形態では、受信アンテナアレー２６は３本の受信アンテナ２７を含む。一般的な場合では、操作性の条件は単にＮＲ≧ＮＴである。  
時空間復号器３０は、符号器２２の影響を取り除くために使用可能である。特定の実施形態の受信機１４は、送信機１２を考慮して設定される。時空間復号器３０の出力は、複数の信号ストリームを含み、１つのストリームが各々の送信アンテナ２５の１つに対応し、それぞれのアンテナは、送信されたシンボルの特定の値を持つ確率で、いわゆるソフトデータあるいは尤度データを運ぶ。このデータは、チャネルインタリーバ２０の効果を逆にし、および時空間復号器３０によって提供された尤度データに基づいて畳み込み符号を出力するチャネルデインタリーバ３２に与えられる。  
その後、チャネルデインタリーバ３２による畳み込み符号出力はチャネル復号器３４に差し出される。この例では、チャネル復号器３４はビタビ復号器であり、畳み込み符号を復号するのに使用可能である。  
チャネル復号器３４は、ＳＩＳＯ（ｓｏｆｔ−ｉｎ ｓｏｆｔ−ｏｕｔ：軟入力軟出力）復号器である。それはシンボル（またはビット）尤度データを受け取り、出力として、例えば硬判定に基づいたデータではなく、同様の尤度データを提供するために使用可能である。チャネル復号器３４の出力は、任意の所望の方法でさらなるデータ処理のためにデータシンク３６へ提供される。チャネル復号器３４は、送信機１２のチャネルインタリーバ２０と同様な設計の、さらなるチャネルインタリーバ３８へその出力をさらに差し出し、したがって送信機１２で基のデータがインタリーブされたのと同じ方法で復号された受信データをインタリーブする。その後、このインタリーブされた受信データは、時空間復号処理で使用される事前（ａ ｐｒｉｏｒｉ）データとして時空間復号器３０に差し戻される。
【０００８】
時空間復号器３０の動作は図２を参照して説明する。  
時空間復号器３０の動作は、上記を参照し説明したｓｐｈｅｒｅ ｄｅｃｏｄｅｒに関連した複雑さの平均レベルを使用し、比較的高い次数の変調スキームを使用して信号変調の復号を可能にする。明瞭さの理由から、その方法は、ＮＴ本の送信アンテナ２５およびＮＲ本の受信アンテナ２７と共に、一般的な場合を参照して説明される。一般的な例のこの説明から、３本の送信アンテナ２５と３本の受信アンテナ２７を備えた特定の図示された例の動作は理解されるだろう。背景知識として、シンボルがＭＩＭＯチャネル２８を通して転送される方法にそってＭＩＭＯ通信の動作の方法がここに説明される。  
上述の通り、一般論として、実施形態の空間多重ＭＩＭＯシステムは、ＮＴ本の送信アンテナ２５とＮＲ本（ＮＲ≧ＮＴ）の受信アンテナ２７を持っている。  
各々の瞬間で、変調コンスタレーションＡ＝｛ａ１、ａ２、．．．、ａＮ｝から取られたＮＴ個のシンボル
【数１】
2009545190.tif 000003
【０００９】
（但し［＊］Ｔは、ベクトルまたは行列の転置を示す）
は、送信アンテナアレー２４のそれぞれの送信アンテナ２５から送信される。  
ＮＲ個の観測点
【数２】
2009545190.tif 000004
【００１０】
は、同様に受信アンテナアレー２６で得られる。
【００１１】
ｘとｙの関係は次のとおりである：
【数３】
2009545190.tif 000005
【００１２】
但し、
【数４】
2009545190.tif 000006
【００１３】
はＮＲ×ＮＴの伝搬路行列で、ｈ（ｉ，ｊ）は行列の（ｉ，ｊ）番目のエントリである。ｈ（ｉ，ｊ）の量は、送信アンテナｊから受信アンテナｉへのチャネル利得を示す。ベクトル
【数５】
2009545190.tif 000007
【００１４】
は、共分散行列
【数６】
2009545190.tif 000008
【００１５】
での、ＮＲ×１のゼロ平均複素円対称ガウス雑音である（zero-mean complex circular symmetric Gaussian noise）。以下の分析では、［＊］＊および［＊］Ｈの表示は、それぞれベクトルまたは行列の共役および共役の転置を示すために使われている。時空間復号器３０のタスク（ｔａｓｋ）は、チャネル状態情報
【数７】
2009545190.tif 000009
【００１６】
を与えられた観測値ｙから、送信されたシンボルｘを推定することである。より正確には、周辺化事後分布
【数８】
2009545190.tif 000010
【００１７】
が必要である。以下の説明では、状態
【数９】
2009545190.tif 000011
【００１８】
は暗に示されていると仮定され、したがって、解析の明瞭さは省略される。以前に英国の特許出願０４２６４８６．７に開示されたように、ＳＧＡアルゴリズムは周辺化事後分布
【数１０】
2009545190.tif 000012
【００１９】
の近似を許可する。これらの正確な計算は、すべての可能なシンボルの組み合わせの徹底的な探索を要求する。さらに、これらの正確な計算は、Ｍ個の最も有意なシンボルの組み合わせである式（２）によって効率的に近似できる。
【数１１】
2009545190.tif 000013
【００２０】
但し、
【数１２】
2009545190.tif 000014
【００２１】
はアンテナj以外のすべてのアンテナにあてはまり、Ｄ−ｊは
【数１３】
2009545190.tif 000015
【００２２】
の可能な値を
【数１４】
2009545190.tif 000016
【００２３】
含んでいるセットである。これが達成される方法は、先に開示した特許出願に従って上記に言及し、ここで簡潔に説明される。  
これらのＭ個の最も有意なシンボルの組み合わせの選択には、すべての可能なシンボルの組み合わせの演算が原則として必要であり、さらに送信アンテナの数とともに指数的に増加する極度に重い計算コストがかかると認識される。ＳＧＡアルゴリズムの中で、Θの選択はＮＴステップに分解される。Ｍ個の最も有意なシンボルの組み合わせは以下を得るために識別される。  
【数１５】
2009545190.tif 000017
【００２４】
各々のステップで、全ての可能な組み合わせ｛（ｘ１（ｍ），…，ｘｊ−１（ｍ），ｘｊ），１，…Ｍ，ｘｊ∈Ａ｝のＭＮ個の近似尤度Ψｍ（ｘｊ）が計算される。  
その後、Θｊのために最大のΨｍ（ｘｊ）によってＭ個の最も有意なシンボルの組み合わせが選ばれる。繰り返しの最後で、ｊ＝ＮＴのとき、Θ＝ΘＮＴが結果として得られる。  
説明されたＳＧＡアルゴリズム中の有意なシンボルの組み合わせを定義するステップは、図２に図示されるような例によってここで実証される。この例では、格子表現は３本の送信アンテナ（１、２、３）上で、配置（Ａ＝ａ１，ａ２，ａ３，ａ４）の中で４つの可能なシンボルが図示される。従って、ＮＴ＝３であれば、ＮＲ≧３であると推測される。目的は、６４の可能性からのＭ＝２の最も有意なシンボルの組み合わせを識別することである。
【００２５】
可能なシンボルの組み合わせは、図２（ａ）中の格子線で示される：  
２本の太線は、２つの最も有意なシンボルの組み合わせを示す、すなわち（ａ４、ａ４、ａ４）そして（ａ１、ａ３、ａ１）。  
第１ステップで、つまりｊ＝１のとき、アンテナ２および３がｘ０＝０を送信したと仮定されている間に、ｘ１∈Ａのときの近似尤度Ψ０（ｘ１）は計算される。Ψ０（ａ１）およびΨ０（ａ４）がｘ１∈Ａのとき２つの最大のΨ０（ｘ１）であると仮定すれば、そのときΘ１＝｛ａ１，ａ４｝となる。このステップは図２（ｂ）に図示される。  
第２のステップで、ここでｊ＝２とし、ｍ＝１、２およびｘ２∈Ａに対してΨｍ（ｘ２）の８つの可能な値が計算され、さらにｘ０はアンテナ３によって送信されたと仮定する。
【００２６】
Ψ１（ａ３）およびΨ２（ａ４）が８つの可能性の中で２つの最大値であると仮定すると、Θ２は｛（ａ４，ａ４），（ａ１，ａ３）｝となる。このステップは図２（ｃ）に図示される。  
この手順は、図２（ｄ）に示すようにΘ３を｛（ａ４，ａ４，ａ４），（ａ１，ａ３，ａ１）｝と定義するために再び繰り返される。
【００２７】
このＳＧＡアルゴリズムの識別ステップの複雑さは、コンスタレーションサイズ（ｃｏｎｓｔｅｌｌａｔｉｏｎ ｓｉｚｅ）Ｎに依存する：  
ＭＮ個の尤度の並び替えおよび計算はＮＴステップとなる。より高い次数のＮ−ＱＡＭ配置は、帯域幅効率を改善するために現代の通信システムの中で広く使用される。そのような場合、このアルゴリズムがまだＳＤアルゴリズムより低い複雑さを示すことは認められるが、ＳＧＡアルゴリズムの複雑さは望ましくなく高くなるかもしれない。幸運にも、より高い次数のＮ−ＱＡＭ配置は、異なる処理段階の中で複雑さの低減に使用されたマルチレベル構造を自然に表す。  
例えば、"Multilevel mixture Kalman Filter"(D. Guo, X. Wang and R. Chen, EURASIP Journal of Applied Signal Processing, special issue onf pParticule Filtering in Singal Processing, Vol. 15, pp. 2255-2266, (Nov. 2004))は、シングルユーザーシステムのための接続チャネル推定およびチャネル検出の状況で、このマルチレベル構造を使用する。さらに、"Iterative tree search detection for MIMO wireless systems"(Yvo L. C. de Jong and Tricia J. Willink, Proc. IEEE VTC 2003, pp. 503-507, (Oct 2003))、そして"Iterative trellis search detection for asynchronous MIMO systems"(Yvo L. C. de Jong and Tricia J. Willink, IEEE Trans. Wireless Commun., Vol. 53, No. 6, pp. 930-935, (Jun 2005))では、このマルチレベル構造をＭＩＭＯシステム用の反復木探索に基づいたシンボル検出の中で使用する。
【００２８】
しかしながら、ＩＴＳ復号器は、尤度の計算において真のシンボルの代わりに擬似シンボルを使う効果を考慮しない。説明した特定の実施形態では、擬似シンボルと真のシンボル間の誤差を補うために、ペナルティ項はガウス近似から導かれる。本発明の特定の実施形態は、Ｎ−ＱＡＭ配置のマルチレベル構造の利用を提供し、ここに説明される。一般論では、Ｎ−ＱＡＭ（Ｎ＝４２、４２、…）配置は、以下のときにl＝１、…Ｌレベルとして考慮されうる。  
【数１６】
2009545190.tif 000018
【００２９】
このアプローチによって、最低のレベル（l＝１のとき）がＡであることに注意すべきである。例えば、６４ＱＡＭ配置には図３に図示されるような３レベルの階層がある。図４は、６４ＱＡＭの階層的構造の例を提示する。１番上（３番目）のレベルにある擬似シンボルａ３，２は、その下のレベルのａ２，３，ａ２，４，ａ２，７，ａ２，８の平均値であり、他も同様である。l番目のレベルについては、配置Ａは
【数１７】
2009545190.tif 000019
【００３０】
個のサブセットllｋに分割され、このとき以下の式を満たす。
【数１８】
2009545190.tif 000020
【００３１】
但しｍ、ｎ＝１、…、Ｎl、ｍ≠  ｎ．
したがって、この例ではl＝１、２、３について６４、１６および４つのサブセットをそれぞれもつ。  
l＝１：  
llｋ｛ａｋ｝、ｋ＝１、…、６４、  
l＝２：  
l２１＝｛ａ１、ａ２、ａ９、ａ１０｝、l２２＝｛ａ３、ａ４、ａ１１、ａ１２｝、l２３＝｛ａ５、ａ６、ａ１３、ａ１４｝、l２４＝｛ａ７、ａ８、ａ１５、ａ１６｝、l２５＝｛ａ１７、ａ１８、ａ２５、ａ２６｝、l２６＝｛ａ１９、ａ２０、ａ２７、ａ２８｝、l２７＝｛ａ２１、ａ２２、ａ２９、ａ３０｝、l２８＝｛ａ２３、ａ２４、ａ３１、ａ３２｝、  
l２９＝｛ａ３３、ａ３４、ａ４１、ａ４２｝、l２１０＝｛ａ３５、ａ３６、ａ４３、ａ４４｝、l２１１＝｛ａ３７、ａ３８、ａ４５、ａ４６｝、l２１２＝｛ａ３９、ａ４０、ａ４７、ａ４８｝、l２１３＝｛ａ４９、ａ５０、ａ５７、ａ５８｝、l２１４＝｛ａ５１、ａ５２、ａ５９、ａ６０｝、l２１５＝｛ａ５３、ａ５４、ａ６１、ａ６２｝、l２１６＝｛ａ５５、ａ５６、ａ６３、ａ６４｝、  
l＝３：  
l３１＝｛ａ１、ａ２、ａ９、ａ１０、ａ５、ａ６、ａ１３、ａ１４、ａ１７、ａ１８、ａ２５、ａ２６、ａ１９、ａ２０、ａ２７、ａ２８｝、  
l３２＝｛ａ３、ａ４、ａ１１、ａ１２、ａ５、ａ６、ａ１３、ａ１４、ａ２１、ａ２２、ａ２９、ａ３０、ａ２３、ａ２４、ａ３１、ａ３２｝、  
l３３＝｛ａ３３、ａ３４、ａ４１、ａ４２、ａ３５、ａ３６、ａ４３、ａ４４、ａ４９、ａ５０、ａ５７、ａ５８、ａ５１、ａ５２、ａ５９、ａ６０｝、  
l３４＝｛ａ３７、ａ３８、ａ４５、ａ４６、ａ３９、ａ４０、ａ４７、ａ４８、ａ５３、ａ５４、ａ６１、ａ６２、ａ５５、ａ５６、ａ６３、ａ６４｝、
但し、l＝１、…、Ｌ、ｓ＝１、…Ｎlのときの擬似シンボルａl，ｓおよび各々の擬似事前情報ｐ（ａl、ｓ）は、以下のように定義される：
【数１９】
2009545190.tif 000021
【００３２】
l番目の擬似シンボルセットとして
【数２０】
2009545190.tif 000022
【００３３】
となる。ＡlセットもまたＮl＋１のサブセットへ分解することができ、それは以下のようなものである。
【数２１】
2009545190.tif 000023
【００３４】
ｓ番目の要素ａｓ，l＋１∈Ａl＋１もまた、対応するサブセット
【数２２】
2009545190.tif 000024
【００３５】
の中の要素の中心である。６４ＱＡＭ配置では、上記の分析にしたがって以下のようになる：
【数２３】
2009545190.tif 000025
【００３６】
ｄｅ Ｊｏｎｇら（１）の中で説明したように、上記の分割は最小ユークリッド距離の平方のサブセットを生成する。  
６４ＱＡＭ変調のマルチレベル構造を利用して、４Ｍシンボルだけが各々のステップで探索される場合、ＳＧＡの選択ステップは３ステップへ分解される。  
第１ステップでは、すべての第３レベルの擬似シンボル｛ａ３，１，…，ａ３，４｝は探索され、またいくつかは次のステップに選ばれるだろう。  
第２ステップでは、上のレベルの擬似シンボルに関連する４Ｍの第２レベルの擬似シンボルのみが考慮される。  
次のステップでは、もし前のステップでａ３，２が選択された場合、そのときは擬似シンボル｛ａ２，３，ａ２，４，ａ２，７，ａ２，８｝だけが考慮される。このステップでは、選択された第２レベルの擬似シンボルと関係のある４Ｍのシンボルだけが考慮される。  
その後、次のステップでは、もしａ２，３が前のステップで選択された場合、シンボル｛ａ５，ａ６，ａ１５，ａ１６｝のみ考慮される。その結果、計算量は、以下に説明されるマルチレベルの方法によって６４Ｍから１２Ｍになる。
【００３７】
同様に、マルチレベルの擬似シンボルの１セットは、図５に示されるような１６ＱＡＭのために構築されることができる：  
l１ｋ＝｛ａｋ｝，ｋ＝１，．．．，１６  
l２１＝｛ａ１、ａ２、ａ５、ａ６｝、l２２＝｛ａ３、ａ４、ａ７、ａ８｝、l２３＝｛ａ９、ａ１０、ａ１３、ａ１４｝、l２４＝｛ａ１１、ａ１２、ａ１５、ａ１６｝、  
【数２４】
2009545190.tif 000026
【００３８】
マルチレベルのｓｅｑｕｅｎｔｉａｌ Ｇａｕｓｓｉａｎ ａｐｐｒｏｘｉｍａｔｉｏｎにとって、初期の焦点は、ｊ番目の識別ステップでΘjを得ることにある。ＳＧＡアルゴリズムでは、ＭＮ個の尤度の計算および並び替えが必要であることに注意されるべきである。  
対照的に、Ｎ−ＱＡＭ配置のマルチレベル構造では、このステップはl＝ｌｏｇ４Ｎ、…、１の段階へさらに分解される。各々の段階では、Ｍ個の最も有意な擬似シンボルの組み合わせが以下を得るために定義される。  
【数２５】
2009545190.tif 000027
【００３９】
最初に、Θｊ−１の中のＭ個の要素の全ての可能な組み合わせの４Ｍ個の近似尤度ψｍ（ｘｊ，Ｌ）およびＡＬ中の４つのシンボルが、下に述べられるような式（５）によって計算される。その後、尤度ψｍ（ｘｊ，Ｌ）が最大となるＭ個の最も有意な擬似シンボルの組み合わせΘｊｌが選択される。その後、最低の変調レベルl＝１に到達するまで、そのプロセスは下へ移動する。各々のレベルlにおいて、ｘｊ＋ｌ∈Ａｌｍのときに４Ｍ個の擬似シンボルの組み合わせ（ｘ１（ｍ），…，ｓｊ−１（ｍ），ｘｊ、ｌ）だけが考慮されることに注意される。Ａｌｍ中の要素の平均はｘｊ＋１（ｍ）であり、次のとおりである：
【数２６】
2009545190.tif 000028
【００４０】
最終段階において、l＝１のとき、Ｍ個の最も有意なシンボルの組み合わせΘｊ＝｛（ｘ１（ｍ），…，ｘｊ（ｍ）），ｍ＝１，…Ｍ｝のセットが得られる。
【００４１】
図６はマルチレベルの識別手順の例を示す。この手順は、アンテナ１のシンボルが、Ｍ＝４および６４ＱＡＭの場合、Θ１＝｛ａ３、ａ１５、ａ５、ａ１０、｝であると識別されていると仮定している。マルチレベルの識別手順は、Θ２を得る第２アンテナのために行なわれることになっている。ＳＧＡアルゴリズムの中で要求されるであろう、シンボルの組み合わせ（ａ３、ａ１）、（ａ３、ａ６４）、（ａ１５、ａ１）、．．．、（ａ１０、ａ６４）の４×６４の近似尤度Ψｍ（ｘ２）の計算および並び替えをおこなう代わりに、ＭＳＧＡアルゴリズムは、４Ｍ個の近似尤度の計算および並び替えに以下のようにただ３ステップだけ必要とする。  
最初の段階で、l＝３のとき、ｘ２，３∈Ａ３のときの（ａ３、ｘ２、３）、（ａ１５、ｘ２、３）、（ａ５、ｘ２、３）、（ａ１０、ｘ２、３）の１６個のΨｍ（ｘ２，３）が計算される。
【００４２】
Ψ1（ａ３，１）、Ψ３（ａ３，１）、Ψ４（ａ３，１）およびΨ４（ａ３，２）が４つの最大量であると仮定されると、次にΘ２３=｛（ａ３、ａ３、１）、（ａ５、ａ３、１）、（ａ１０、ａ３、１）（ａ１０、ａ３、２）｝が得られる。  
次のレベル（ｌ＝２）で、ｘ２、２∈Ａ２１およびｘ’２、２∈Ａ２２のとき、（ａ３、ｘ２、２）、（ａ１５、ｘ２、２）、（ａ１０、ｘ２、２）、および（ａ１０、ｘ’２，２）の１６個のΨｍ（ｘ２，３）計算される。  
熟練者によって、ａ３，１はＡ２１中のすべての要素の平均であり、ａ３，２はそれぞれＡ２２の中のすべての要素の平均であるということを指摘されるだろう。その後、選択は繰り返されて、Θ２２＝｛（ａ３、ａ２，１）、（ａ５、ａ２，１）、（ａ１０、ａ２，１）、（ａ１０、ａ２，４）｝が得られる。最終的に、上記の計算と選択との手順は、Θ２＝｛（ａ３、ａ１）、（ａ５、ａ９）、（ａ１０、ａ１）、（ａ１０、ａ７）｝を識別するために再び繰り返される。記述されたマルチレベルの手法は、ｌｏｇ４Ｎレベルのための４Ｍ個の近似尤度の計算および並び替えを必要とする。ｌｏｇ４Ｎレベルは、それぞれ１６ＱＡＭと６４ＱＡＭの変調コンスタレーション（ｃｏｎｓｔｅｌｌａｔｉｏｎ）のためのＳＧＡアルゴリズム中の、選択手順のたった１／２および３／１６だけである。
【００４３】
本手法は、図８を参照して一般論で以下に例示される。  
Ａ．初期化  
ステップＳ１−２では、ゼロフォーシング（ｚｅｒｏ ｆｏｒｃｉｎｇ）出力である
【数２７】
2009545190.tif 000029
【００４４】
と、分散行列Λ、擬似シンボルアルファベットの分散Ａlγl（ここでl＝１、…、ｌｏｇ４Ｎ）、およびＡの分散は以下のように計算される：
【数２８】
2009545190.tif 000030
【００４５】
また、シンボル組み合わせのセットΘ０は、
【数２９】
2009545190.tif 000031
【００４６】
およびＬ＝ｌｏｇ４Ｎに対して空集合として初期化される。  
Ｂ．ｊ＝１、…、ＮＴに対するマルチレベル識別ステップ  
ステップＳ１−４では、Ψｍ（ｘｊ、Ｌ）は、ｘｊ、Ｌ∈ＡＬおよびｍ＝１、…、Ｍに対して以下の方程式（５）によって計算される。その後、以下のセットΘｊＬを持つ最大のΨｍ（ｘｊ、Ｌ）を持っているＭ＝ｍｉｎ（Ｍ、４（ｊ−１）Ｌ＋１）個のシンボルの組み合わせが選択される:
【数３０】
2009545190.tif 000032
【００４７】
確率ｐ（ｘｊ）は、ｊ＝１、…、ＮＴにおける事前（ｐｒｉｏｒ）情報である。ベクトルｅｋは、その要素がすべてゼロだがｋ番目が１である列ベクトルである。
【数３１】
2009545190.tif 000033
【００４８】
は複素数の実数部を意味する。［ＩＩｊ−１］ｊｊは、マトリックスＩＩｊ−１のｊ番目の対角線成分を意味する。ペナルティ項
【数３２】
2009545190.tif 000034
【００４９】
は、マルチレベルの擬似シンボルｘｊ，l∈Ａlと、Ａの中で値をとる実際の送信されたシンボルとの間の誤差を保証するためにガウス近似に由来することに注意されるべきである。  
ａ）ｍ＝１、…、Ｍに対し
【数３３】
2009545190.tif 000035
【００５０】
のようなｘｊ、l∈Ａlｍにとって、l＝Ｌ−１、...、１で、式（５）に従ってΨｍ（ｘｊ、l）を計算する。  
ｂ）Θｊlにとって最大のΨｍ（ｘｊ、l）を持っているＭ＝ｍｉｎ（Ｍ、４ｊＬ−ｌ＋１）のシンボルの組み合わせを選択する。
【００５１】
Ｃ．ｊ＝１、…、ＮＴまでの周辺（ｍａｒｇｉｎａｌ）シンボル確率の計算  
ステップＳ１−６では、周辺（ｍａｒｇｉｎａｌ）シンボル確率はシンボルｘｊから計算される。  
１）ｍ＝１、…、Ｍおよびｘｊ∈Ａのときに以下の式（６）を計算する。  
【数３４】
2009545190.tif 000036
【００５２】
２）ｘｊ∈Ａのときのシンボル確率を計算する。  
【数３５】
2009545190.tif 000037
【００５３】
これらの手法の実装のシミュレーションでは、両方のアルゴリズムとも、最適性能に近い性能（ｐｅｒｆｏｒｍａｎｃｅ）（Ｍａｘ−Ｌｏｇ  ＡＰＰ）を達成することが観測されている。マルチレベルＳＧＡの複雑さは、１６ＱＡＭおよび６４ＱＡＭ変調ＭＩＭＯシステム（ＮＴ＝ＮＲ＝４）用のオリジナル（ｏｒｉｇｉｎａｌ）のＳＧＡアルゴリズムの複雑さのわずかそれぞれ約７０％および３０％である。これは図７に図示される。  
多くの状況では、無線通信装置は送信機および受信機の設備の組み合わせとして提供されることが認識されるだろう。しかし、この例については、装置は単純さの理由により一方向通信装置として図示された。図示された例の中で使われた特定の変調スキームは説明しない。それは可能なシンボルの数、およびシンボル間の関係（シンボルが区別される方法を決定すること）が本発明の性能（ｐｅｒｆｏｒｍａｎｃｅ）に関連がないからである。しかしながら、説明された実施形態はＢＰＳＫまたはＱＰＳＫを用いることができ、さらにまた、本発明は、性能（ｐｅｒｆｏｒｍａｎｃｅ）もしくは計算の複雑性がほとんど悪化することなく、より高次の変調スキームに適用することができることは認識されるだろう。  
本発明は畳み込みチャネル符号器に関して説明されているが、本発明はいわゆるターボ符号器（それはインタリーバを含んでいる）のようなより強い符号器に関して実装されることができることが認識されるだろう。本発明は、送信機および受信機機能をそれぞれ提供しているハードウェアの点から説明されている一方、本発明を実行および／または提供するための、いくつかあるいはすべての装置は、汎用コンピュータの操作を命令するソフトウェアを用いることによって実装されてもよいことが認識されるだろう。その汎用コンピュータはおそらく無線通信を確立するためのハードウェアによって適切に設定される。本発明の実装を提供するためのソフトウェアは、適切な装置に搭載されるためにソフトウェア製品として提供されるかもしれない。  
ソフトウェア製品は，データキャリアを備えていてもよい。データキャリアは、磁気記憶装置（例えば、ディスクまたはテープ）、光記憶装置（例えば光ディスク（例えば、コンパクトディスクまたはＤＶＤフォーマット）、信号運搬データ（signal carrying data）（例えば、インターネット経由のようなもので、遠隔にアクセスできる格納場所からのものであり、信号が向けられる装置と通信するもの）を含んでいてもよい。
【符号の説明】
【００５４】
１０・・・ＭＩＭＯデータ通信システム、１２・・・送信装置、１４・・・受信装置、１６・・・データソース、１８・・・チャネル符号器、２０、３８・・・チャネルインタリーバ、２２・・・時空間符号器、２４・・・送信アンテナアレー、２５・・・送信アンテナ、２６・・・受信アンテナアレー、２７・・・受信アンテナ、２８・・・ＭＩＭＯチャネル、３０・・・時空間復号器、３２・・・チャネルデインタリーバ、３４・・・チャネル復号器、３６・・・データシンク。
【図１】
2009545190.tif 000038
【図２】
2009545190.tif 000039
【図３】
2009545190.tif 000040
【図４】
2009545190.tif 000041
【図５】
2009545190.tif 000042
【図６】
2009545190.tif 000043
【図７】
2009545190.tif 000044
【図８】
2009545190.tif 000045
【国際調査報告】
2009545190.tif 000046
2009545190.tif 000047
2009545190.tif 000048