(57)【特許請求の範囲】
【請求項１】
複数のユーザ(Ｋ)によりまたは複数のユーザ(Ｋ)に向けて送信される複数のシンボル(ｄk(ｉ))を検出するための方法であって、各シンボルは変調コンスタレーションに属しまた拡散系列と乗算され、該方法は、受信された信号をフィルタリングし、その各成分がユーザに関連付けられる観測ベクトル(ｚ)を供給するフィルタリングステップを含み、また該方法はさらに、
複数の生成ベクトル(v1,v2,・・・v2K)によって生成される点の格子の前記変調コンスタレーションにより決まる部分集合に属する候補ベクトルの中から前記観測ベクトルの最も近い隣接点を探索するための探索ステップであって、前記探索は前記観測ベクトルを中心にした体積に限定され、かつ前記生成ベクトルに関連付けられた表現における前記点の格子の各次元のための候補ベクトルの座標(ｂk)を順番に選択することにより実行される、探索ステップを含んでおり、前記探索は探索ツリーに従って行われ、ツリーの各レベルは格子の次元に相当し、もしあるなら、各ノードがすでに選択された複数の座標に相当し、
各次元(ｋ)に対して、前記次元の部分集合の射影を表す第１の区間(［Ｍk-，Ｍk+］)が定義され、
各ノードに対して、もしあるなら、既に選択されている複数の座標に対して、前記次元に沿った前記体積の一部を表す第２の区間(［Ｌk-，Ｌk+］)が定義され、さらに第３の区間(［Ｂk-，Ｂk+］)が前記第１の区間と前記第２の区間との交差部として定義され、
前記第３の区間と前記第２の区間の長さの比率により前記ノードに対して通過率が定義され、
次元に従った前記探索ツリーのレベルに属するノードの通過率の平均によって前記次元に対して通過率が定義され、
次元の通過率に関する値を演算する手段を使用して各次元に対して上記値が演算され、
前記観測ベクトルの成分が前記探索前に並べ替え規則に従って前記生成ベクトルを並べ替えて得られる並べ替えられた点の格子内に示され、前記並べ替え規則は通過率に関する前記値により定義され、探索される第１の次元が低通過率を示す、ことを特徴する方法。
【請求項２】
並べ替えられた点の格子の各次元(ｋ)に対して、もしあるなら、既に選択されている複数の座標に対して、その際、前記次元のための座標の選択が前記第３の区間に限定されることを特徴とする請求項１に記載の方法。
【請求項３】
並べ替えられた点の格子の各次元に対して、前記第１の区間の大きさによって正規化された、前記次元(ρk)における前記体積の中央の射影と前記第１の区間の中央との間の距離を表す値(εk)が計算され、
前記並べ替え規則は、探索されることになる第１の次元が、探索されることになる後続の次元に関連付けられる値よりも高い正規化された距離値に関連付けられるような規則であることを特徴とする請求項２に記載の方法。
【請求項４】
並べ替えられた点の格子の各次元に対して、前記次元(ρk)における前記体積の中央の射影が前記第１の区間内に入るか否かを検査し、入らない場合には、前記射影と前記第１の区間のそれぞれ上限および下限との間の距離の大きい方の値が確定され、
前記並べ替え規則は、探索されることになる第１の次元が、探索されることになる後続の次元に関連付けられる値よりも高い値に関連付けられるような規則であることを特徴とする請求項２に記載の方法。
【請求項５】
並べ替えられた点の格子の各次元に対して、前記次元(ρk)における前記体積の中央の射影が前記第１の区間内に入るか否かを検査し、入る場合には、前記射影と前記区間の中央との間の距離の値が確定され、
前記並べ替え規則は、探索されることになる第１の次元が、探索されることになる後続の次元に関連付けられる値よりも高い値に関連付けられるような規則であることを特徴とする請求項２に記載の方法。
【請求項６】
第１の次元における前記体積の中央の射影が前記第１の次元に沿ったコンスタレーションを表す前記第１の区間の外側に入り、第２の次元における前記体積の中央の射影が前記第２の次元に沿ったコンスタレーションを表す別の第１の区間内に入るとき、
前記並べ替え規則は、前記第１の次元が前記第２の次元の前に探索されるような規則であることを特徴とする請求項４または５に記載の方法。
【請求項７】
並べ替えられた点の格子の各次元に対して、前記体積の前記次元上への射影を表す第４の区間が確定され、第５の区間が前記第１の区間と前記第４の区間との交差部として得られ、前記第４の区間の長さに対する前記第５の区間の長さの比を表す値(σ2KK)が計算され、
前記並べ替え規則は、探索されることになる第１の次元が、探索されることになる後続の次元に関連付けられる値よりも低い値に関連付けられるような規則であることを特徴とする請求項２に記載の方法。
【請求項８】
一旦、最も近い隣接点が見つけられたなら、前記並べ替え規則の逆の処理に従ってその座標が並べ替えられ、前記複数のユーザに対してまたは前記複数のユーザによって送信されるシンボルが前記並べ替えられた座標から導出されることを特徴とする請求項１ないし７のいずれか１項に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は複数のユーザによりまたは複数のユーザに向けて送信される複数のシンボルを検出するための方法、すなわちマルチユーザ検出方法に関する。より詳細には、本発明はＤＳ−ＣＤＭＡ(直接拡散符号分割多元接続)通信システムあるいはＭＣ−ＣＤＭＡ(マルチキャリア符号分割多元接続)通信システムのための最尤マルチユーザ検出方法に関する。
【０００２】
【従来の技術】
ＤＳ−ＣＤＭＡ移動体通信システムでは、種々のユーザから到来する通信および種々のユーザに向けられる通信の分離は、一人のユーザの各複素シンボルとそのユーザに固有の拡散系列とを掛け合わせることにより達成される。このため、拡散系列はユーザシグネチャとも呼ばれる。拡散周波数(チップレート)がシンボルの周波数よりも高いとき、各ユーザによって送信される信号は周波数空間内に分散(あるいは拡散)される。拡散信号によって占有される帯域と情報信号によって占有される帯域との間の比は拡散率と呼ばれる。受信時に、所与のユーザの分離は、対応するシグネチャに適応するフィルタリングによって達成される。伝送チャネルが複数の伝搬経路を有するとき、適応的なフィルタリングの出力はその伝搬経路と同じ数の相関ピーク値を含む。チャネルの各経路は、複素乗算係数と遅延とによってモデル化されることができる。種々の経路に沿って伝搬されている信号は、伝搬係数の共役数である複素係数によって同相にされ、かつ合成されて、それにより伝送チャネルに適応するフィルタリングを達成することができる。専門用語を簡単にするために、一般的な表現「ユーザｋに整合したフィルタリング」は、ユーザｋのシグネチャに整合したフィルタリング動作および伝送チャネルに整合したフィルタリング動作の両方を含む。
【０００３】
種々のユーザに向けられる(ダウンリンク)信号と種々のユーザから到来する(アップリンク)信号との間の干渉を打ち消すために、マルチユーザ検出方法、とりわけＰＩＣ(パラレル型干渉キャンセル)およびＳＩＣ(シリアル型干渉キャンセル)として知られるような反復検出方法が提案されている。その方法は、送信されたシンボルを推定すること、干渉を計算すること、およびそれを受信された信号から減算することを含む、干渉除去サイクルの反復に基づく。高性能ではあるが、これらの方法は最適ではない。なぜなら、それらの方法は、種々のユーザによって送信されるシンボルの最尤推定という意味の推定値を与えないためである。
【０００４】
さらに最近になって、最尤判定基準を利用し、点の格子による表現に基づくマルチユーザ検出の方法が、ウェブサイトwww.enst.fr/〜brunel上で入手可能な「Lattice decoding for joint detection in Direct Sequence CDMA systems」というタイトルの論文においてL. Brunelによって提案された。この方法によれば、種々のユーザによって送信されるシンボルを最尤検出するのに十分な統計値を表す受信信号の特性を示すベクトルが判定される。ある条件下において、その特性ベクトルは、雑音による擾乱を受ける格子内の点として表せることがわかっている。その際、その検出は、受信されたベクトルに対応する点に最も近い格子内の点を求めることからなる。
【０００５】
より具体的には、最初に、基地局がＫ人のユーザと通信するＤＳ−ＣＤＭＡ通信システムについて考えるものとし、ｄk(ｉ)をダウンリンクチャネル上で瞬間ｉにおいてユーザｋに送信される複素シンボルとする。このシンボルは、Ａkで示される、ユーザｋに対するコンスタレーション変調に属し、これ以降、ユーザｋの変調アルファベットと呼ばれる。
【０００６】
基地局は各ユーザｋに対して、振幅ａkの信号でＮシンボルのブロックを送信する。ユーザｋのためのシンボルは、シンボル周期Ｔに等しい持続時間を有する実数シグネチャｓk(ｔ)によって拡散される。すなわち、
【０００７】
【数１】
0004270934.tif 000002
【０００８】
の場合にｓk(ｔ)＝０である。瞬間ｉにおいて送信されるＫ個の複素シンボルは、ｄ(ｉ)＝(ｄ1(ｉ)，ｄ2(ｉ)，・・・，ｄK(ｉ))として定義される行ベクトルｄ(ｉ)に入れられる。
【０００９】
その際、対応する変調された信号は時間ｔの関数として表される。
【００１０】
【数２】
0004270934.tif 000003
【００１１】
ダウンリンクチャネルが、白色付加ガウス雑音(ＡＷＧＮ)を有する理想的なチャネルであると仮定する。ｒt＝Ｓt＋ηtが、ユーザｋによって時刻ｔにおいて受信される信号を示すものとする。ただし、ηtは平均値が０で、分散がＮ0のガウス成分を有する実数ベクトルである。ｄ(ｉ)の最尤検出のために十分な統計値は観測ベクトルｙ(ｉ)＝(ｙ1(ｉ)，ｙ2(ｉ)，・・・，ｙK(ｉ))から構成される。ただし、ｙk(ｉ)はユーザｋに関連付けられるマッチトフィルタ出力であり、以下の式が成り立つ。
【００１２】
【数３】
0004270934.tif 000004
【００１３】
ここで、
【００１４】
【数４】
0004270934.tif 000005
【００１５】
式(２)は行列による式を採用することにより、以下のように書き換えることができる。
【００１６】
【数５】
0004270934.tif 000006
【００１７】
ここで、Ｍ＝ＡＲであり、Ａ＝ｄｉａｇ(ａ1，・・・ａK)はＫ人の稼動中のユーザの振幅係数を含むＫ×Ｋの対角行列であり、Ｒ＝［Ｒqk］はＫ×Ｋのシグネチャ相互相関行列である。
【００１８】
式(３)のベクトルｙ(ｉ)は、生成行列Ｍが雑音ｎによって擾乱を受けた、次元Ｋの格子の１つの点とみなすことができる。「次元Ｋの点の格子Λ」という用語は、以下の式を満足するＲKのベクトルの任意の集合の場合に用いられる。
【００１９】
【数６】
0004270934.tif 000007
【００２０】
ここでｖ1、ｖ2、・・・、ｖKはＲKの基底である。
【００２１】
これらの基底ベクトルは格子の生成行列Ｇの行を形成する。それゆえ、以下のように書き表すことができる。
【００２２】
【数７】
0004270934.tif 000008
【００２３】
そのような格子は、Ｋ＝２の場合に図１に表されている。
【００２４】
実際には、雑音ベクトルｎ(ｉ)の成分が相関するとき、復号化前に、信号ｙ(ｉ)において雑音白色化の演算が実行される。自己相関行列Ｒが対称に定義された正の行列であるとき、それはコレスキー分解によって以下のように分解することができる。
【００２５】
【数８】
0004270934.tif 000009
【００２６】
ここで、Ｗは大きさＫ×Ｋの下三角行列である。白色化された観測ベクトルは(〜)ｙ(ｉ)＝ｙ(ｉ)(ＷT)-1と定義され、ベクトル(〜)ｘを表す新たな格子Ωが定義される。ただし、(〜)ｘ(ｉ)＝ｘ(ｉ)(ＷT)-1であり、ｘ(ｉ)はΛに属する。
【００２７】
それゆえ、式(３)は以下のように書き換えることができる。
【００２８】
【数９】
0004270934.tif 000010
【００２９】
ここで、(〜)Ｍ＝Ｍ(ＷT)-1および(〜)ｎ(ｉ)＝ｎ(ｉ)(ＷT)-1である。白色化後に、フィルタリングされた雑音(〜)ｎ(ｉ)の共分散行列がＮ0ＩKに等しいことは容易に示されることができる。ここで、ＩKは次元Ｋの恒等行列である。雑音ベクトル(〜)ｎ(ｉ)が実数のガウス分布の独立した成分を有するとき、最尤検出は、受信されたベクトル(〜)ｙに最も近い格子Ωに属するベクトルｘ、言い換えると、以下の距離を最小にするベクトルｘを見つけることを意味する。
【００３０】
【数１０】
0004270934.tif 000011
【００３１】
ベクトルｙ(ｉ)は、以下の共分散行列に基づく距離が用いられる場合には、白色化される必要はないことに留意されたい。
【００３２】
【数１１】
0004270934.tif 000012
【００３３】
これ以降、簡略化するために、観測ベクトルは白色化されている((〜)ｙ(ｉ))か、白色化されていない(ｙ(ｉ))かにかかわらずｚで表され、式(８)あるいは(９)において作用する距離は||.||で表される。
【００３４】
送信されるシンボルの集合ｄk(ｉ)は、これ以降コンスタレーションと呼ばれる有限個のアルファベットＡK⊂ＺKに限定される。このコンスタレーションは、Ｋ人の各ユーザに対する変調コンスタレーションによって決定され、アルファベットＡKのカージナルス数は種々の変調アルファベットのカージナルス数の積に等しい。コンスタレーションは格子Λ、それゆえ格子Ωの部分集合に対応する。
【００３５】
完全な最尤復号化では、コンスタレーション全体にわたって最も近い隣接点を探索することが必要となるであろう。限界距離復号化方法(sphere decoding method)は、その計算を、受信された点の周囲に配置されるコンスタレーションの領域内、好ましくは図１に示されるように受信される点を中心にした所与の半径√(Ｃ)の球Ｓ内に配置される点に限定する。それゆえ、距離(８)あるいは(９)の最小化のために、受信された点からＣ未満の平方距離に配置される格子内の点のみが考慮される。
【００３６】
実際には、復号器は以下の最小化を達成する。
【００３７】
【数１２】
0004270934.tif 000013
【００３８】
これを果たすために、平行移動された集合ｚ−Ω内の最も小さなベクトルｗが求められる。そのベクトルｚおよびｗは以下のように表されることができる。
【００３９】
【数１３】
0004270934.tif 000014
【００４０】
ρおよびξが実数ベクトルであることに留意することが重要である。ｘが格子Ωに属する場合に、ｗ＝ｚ−ｘであるので、これは式ξi＝ρi−ｂi(ｉ＝１，・・・，Ｋ)を与え、その場合に
【００４１】
【数１４】
0004270934.tif 000015
【００４２】
である。ベクトルｗは、その座標ξiが、受信された点ｚを中心にして平行移動された基準座標系において表される、格子内の点である。ベクトルｗは、以下の式が成り立つ場合にのみ、０を中心にした平方半径Ｃの球に属する。
【００４３】
【数１５】
0004270934.tif 000016
【００４４】
それゆえ、ξによって定義される新たな座標系では、ｚを中心にした平方半径Ｃの球は原点を中心にした楕円に変換される。グラム行列Γ＝ＧＧTのコレスキー分解によってΓ＝ΔΔTが与えられる。ここで、Δは要素δijからなる下三角行列である。
【００４５】
ベクトルｙが白色化されている場合には、その格子のための生成行列は既に下三角行列であるので、この分解を実行する必要がないことに留意されたい。いずれの場合でも、以下の式が成り立つ。
【００４６】
【数１６】
0004270934.tif 000017
【００４７】
上記の式に以下の式を代入する。
【００４８】
【数１７】
0004270934.tif 000018
【００４９】
その結果として、以下の式が得られる。
【００５０】
【数１８】
0004270934.tif 000019
【００５１】
まず、ξKの取り得る変動の範囲について考え、その後、降順に成分を１つずつ加えるとき、以下のＫ個の不等式が得られ、それは楕円内の全ての点を定義する。
【００５２】
【数１９】
0004270934.tif 000020
【００５３】
不等式(１６)により、ｂの整数成分が以下の式を満たすために必要かつ十分になることが明らかである。
【００５４】
【数２０】
0004270934.tif 000021
【００５５】
ここで、
【００５６】
【数２１】
0004270934.tif 000022
【００５７】
は実数ｘよりも大きな最も小さい整数であり、
【００５８】
【数２２】
0004270934.tif 000023
【００５９】
は実数ｘよりも小さな最も大きい整数である。
【００６０】
実際には、各カウンタが特定の境界の対に関連付けられるものとすると、Ｋ個の内部カウンタ、すなわち次元当たり１つのカウンタが用いられ、各カウンタによって、(１７)に示されるような上限と下限との間の数が数えられる。実際には、これらの境界は繰返し更新されることができる。ここで、ＴK＝Ｃの場合に、以下のようにする。
【００６１】
【数２３】
0004270934.tif 000024
【００６２】
式(１８)〜(２０)を用いると、各成分ｂiの変動の範囲は、成分ｂKで開始して、帰納的に決定される。
【００６３】
【数２４】
0004270934.tif 000025
【００６４】
これまで、ユーザのシグネチャｓk(ｔ)は実数であるものと仮定してきた。より一般的には、ユーザシグネチャｓk(ｔ)が複素値である場合には、ｓk(ｔ)＝ｓkR(ｔ)＋ｊ・ｓkI(ｔ)である。そのような場合には、(３)に類似の結果が得られることが明らかである。すなわち以下の式が成り立つ。
【００６５】
【数２５】
0004270934.tif 000026
【００６６】
ここで、ｄk(ｉ)＝ｄkR(ｉ)＋ｊ・ｄkI(ｉ)の場合に、ベクトルｄ2(ｉ)＝(ｄ1R(ｉ)，ｄ1I(ｉ)，・・・，ｄKR(ｉ)，ｄKI(ｉ))は種々のユーザのためのシンボルの実数値および虚数値を表し、ｙ2(ｉ)＝(ｙ1R(ｉ)，ｙ1I(ｉ)，・・・，ｙKR(ｉ)，ｙKI(ｉ))は観測ベクトルである。その場合に、ｙk(ｉ)＝ｙkR(ｉ)＋ｊ・ｙkI(ｉ)はユーザｋに整合するフィルタの瞬間ｉにおける複素出力であり、すなわち以下の式が成り立つ。
【００６７】
【数２６】
0004270934.tif 000027
【００６８】
＊は共役演算を示しており、ここでＡ2＝ｄｉａｇ(ａ1，ａ1，・・・，ａK，ａK)の場合にＭ2＝Ａ2Ｒ2であり、Ｒ2は大きさ２Ｋ×２Ｋの行列である。
【００６９】
【数２７】
0004270934.tif 000028
【００７０】
式(２３)中のベクトルｙ2(ｉ)は、生成行列Ｍ2が実数雑音ｎ2によって擾乱を受けている、次元２Ｋの格子Λ2の点とみなすことができる。雑音ベクトルｎ2(ｉ)の成分が相関するとき、雑音白色化の演算が復号化前に信号ｙ2(ｉ)において実行される。白色化された観測ベクトルは(〜)ｙ2(ｉ)で表される。ただし、(〜)ｙ2(ｉ)＝ｙ2(ｉ)(Ｗ2T)-1であり、Ｒ2＝Ｗ2Ｗ2Tである。
【００７１】
ここで再び、最尤検出は、受信されるベクトル(〜)ｙ2に最も近い格子Ω2(大きさ２Ｋ)に属するベクトルｘを見つけることを意味する。限界距離復号化方法は、式(１２)〜(２２)において詳述される形式に従って、すなわち楕円内で、コンスタレーションに属する点を探索することにより実行されることができる。
【００７２】
またその限界距離復号化方法は、ProceedingsPIRMC’01(２００１年９月)に発表され、参照して本明細書に援用される「Optimum multi-user detection for MC-CDMA systems using sphere decoding」というタイトルのL. Brunelの論文に記載されるように、ＭＣ−ＣＤＭＡにも同じようにうまく適用されている。ＭＣ−ＣＤＭＡに適用される限界距離復号化方法の主な特徴が以下に詳述される。
【００７３】
ＭＣ−ＣＤＭＡ技法が直交周波数分割多重(ＯＦＤＭ)変調とＣＤＭＡとの組み合わせであることを思い起こされたい。より厳密には、送信側では、その周波数スペクトルを拡散するために各ユーザのための信号が時間領域で乗算されるＤＳ−ＣＤＭＡとは対照的に、ここではシグネチャが周波数領域においてユーザの信号を掛け合わせられ、シグネチャの各要素が種々のサブキャリアの信号と掛け合わせられる。それゆえ、ＭＣ−ＣＤＭＡ技法は、周波数領域において拡散した後にＯＦＤＭ変調するものとみなすことができる。
【００７４】
受信側では、受信された信号が、ＯＦＤＭ多重のＬ個の異なるサブキャリアに対する１組の周波数成分に(高速フーリエ変換によって)分解される。
【００７５】
最初に、ＭＣ−ＣＤＭＡ受信機が移動端末内に配置され、基地局が複数(Ｋ)のユーザにシンボルを送信するものとする。ｒ(ｉ)＝(ｒ1(ｉ)，・・・，ｒL(ｉ))はＬ個のサブキャリア上の周波数成分のベクトルを表し、ｄ(ｉ)＝(ｄ1(ｉ)，・・・，ｄk(ｉ))は種々のユーザによって時刻ｉにおいて送信されるＫ個のシンボルのベクトルを表し、Ｃは以下のようなＫ個の拡散系列の行列を表す。
【００７６】
【数２８】
0004270934.tif 000029
【００７７】
周波数成分のベクトルは以下のように表されることができる。
【００７８】
【数２９】
0004270934.tif 000030
【００７９】
ここで、η(ｉ)＝(η1(ｉ)，・・・，ηL(ｉ))は白色付加ガウス雑音ベクトルであり、Ａ＝ｄｉａｇ(ａ1，・・・，ａK)は種々のユーザの振幅係数によって形成される対角行列であり、Ｈ(ｉ)＝ｄｉａｇ(ｈ1(ｉ)，・・・，ｈL(ｉ))は、基地局とユーザとの間の伝送チャネルに対する、ダウンリンクチャネル係数ｈl(ｉ)によって形成される対角行列である。式(２７)は以下のように書き直すことができる。
【００８０】
【数３０】
0004270934.tif 000031
【００８１】
アップリンクの場合について考えてみると、各ユーザから到来する信号が異なるチャネル内を伝送するので、複数の伝送チャネルが考慮に入れられる。拡散およびチャネル効果は行列ＣU(ｉ)において合成されることができる。
【００８２】
【数３１】
0004270934.tif 000032
【００８３】
全てのユーザが同期して受信されるものとすると、受信される信号は(２８)と同様に書き表されることができる。
【００８４】
【数３２】
0004270934.tif 000033
【００８５】
以下の式によって、ダウンリンクの場合における観測ベクトルｙ(ｉ)が定義され得る。
【００８６】
【数３３】
0004270934.tif 000034
【００８７】
同様に、アップリンクの場合には以下のようになる。
【００８８】
【数３４】
0004270934.tif 000035
【００８９】
ただし・Hは共役転置演算を表す。
【００９０】
いずれの場合でも、観測ベクトルｙ(ｉ)は、各ユーザｋに関連するシグネチャとチャネルとに整合するフィルタで、受信された信号ｒ(ｉ)をフィルタリングした結果とみなすことができる。またそれは、ダウンリンクの場合には生成行列ＡＣDＣDH、アップリンクの場合には生成行列ＡＣUＣUHを有する格子ΛΛの点とみなすこともできる。ｙ(ｉ)の雑音成分の相関をなくすために、雑音白色化を適用することができる。(〜)ｙ(ｉ)が観測ベクトルの白色化されたものを表すとき、送信されるシンボルの最尤検出は再び、(〜)ｙ(ｉ)に最も近い格子のベクトルｘを見つけることを意味する。
【００９１】
上記の説明において、限界距離復号化方法をＤＳ−ＣＤＭＡおよびＭＣ−ＣＤＭＡ(アップリンクおよびダウンリンクの場合)における最尤検出のために用いることができることを見てきた。先に記載された全ての場合に、ＭＬ検出は、観測ベクトルｙを与えるために、各拡散系列と、ユーザのチャネルとにそれぞれ整合するフィルタで、受信された信号をフィルタリングする最初のステップと、その後に、ベクトル(〜)ｙ(ｉ)に最も近い格子(Ω，Ω2)のベクトルｘが求められる限界距離復号化ステップとを含む。
【００９２】
図２は、限界距離復号化方法を用いるＤＳ−ＣＤＭＡあるいはＭＣ−ＣＤＭＡ受信機を概略的に示す。
【００９３】
受信された信号ｒ(ｉ)は、Ｋ個のユーザのシグネチャおよびチャネルに整合したフィルタ２１０でフィルタリングされ、観測ベクトルｙ(ｉ)が出力される。２２０の雑音白色化によって観測ベクトルの白色化されたもの(〜)ｙ(ｉ)が与えられ、限界距離復号器(sphere decoder)２３０において(〜)ｙ(ｉ)に最も近い格子点が探索される。最も近い格子点ｘが限界距離復号器から出力され、そこから、種々のユーザに対して、あるいは種々のユーザによって送信されるシンボルが推定される。
【００９４】
式(１７)〜(２２)に関連して先に記載されたように、限界距離復号化過程は、楕円(１６)に含まれる全ての格子点を探索し、それぞれについてのノルム||ｗ||を計算することを必要とする。この走査アルゴリズムは、特にユーザの数Ｋが大きいときには、多大な時間を消費する。
【００９５】
限界距離復号化過程を迅速化するために、いくつかの対策が既に提案されている。
【００９６】
まず、半径√(Ｃ)を最も低い計算されたノルム||ｗ||で更新し、それにより、より低いノルムを見つける度に楕円を縮小することにより、その探索を加速することができる。しかしながら、大きさの見直しはそれぞれ、新たな境界Ｌｉ-およびＬｉ+を計算し、その後、更新された境界内で新たな探索が行われることを意味する。
【００９７】
また、Proceedings of ICC’02(２００２年４月)において発表され、参照して本明細書に援用される「Optimum and sub-optimum multi-user detection based on sphere decoding for multi-carrier code division access systems」というタイトルのL.Brunelの論文では、コンスタレーションの外側に配置される点を不必要に検査しないように、(２１)および(２２)によって定義される変動の範囲を制限することを提案している。
【００９８】
【発明が解決しようとする課題】
本発明の目的は、符号分割多元接続方式のマルチユーザ検出の限界距離復号化過程の複雑さを緩和した方法を提供することである。
【００９９】
【課題を解決するための手段】
上記の目的に鑑み、この発明は、複数のユーザ(Ｋ)によりまたは複数のユーザ(Ｋ)に向けて送信される複数のシンボル(ｄk(ｉ))を検出するための方法であって、各シンボルは変調コンスタレーションに属しまた拡散系列と乗算され、該方法は、受信された信号をフィルタリングし、その各成分がユーザに関連付けられる観測ベクトル(ｚ)を供給するフィルタリングステップを含み、また該方法はさらに、複数の生成ベクトル(v1,v2,・・・v2K)によって生成される点の格子の前記変調コンスタレーションにより決まる部分集合に属する候補ベクトルの中から前記観測ベクトルの最も近い隣接点を探索するための探索ステップであって、前記探索は前記観測ベクトルを中心にした体積に限定され、かつ前記生成ベクトルに関連付けられた表現における前記点の格子の各次元のための候補ベクトルの座標(ｂk)を順番に選択することにより実行される、探索ステップを含んでおり、前記探索は探索ツリーに従って行われ、ツリーの各レベルは格子の次元に相当し、もしあるなら、各ノードがすでに選択された複数の座標に相当し、各次元(ｋ)に対して、前記次元の部分集合の射影を表す第１の区間(［Ｍk-，Ｍk+］)が定義され、各ノードに対して、もしあるなら、既に選択されている複数の座標に対して、前記次元に沿った前記体積の一部を表す第２の区間(［Ｌk-，Ｌk+］)が定義され、さらに第３の区間(［Ｂk-，Ｂk+］)が前記第１の区間と前記第２の区間との交差部として定義され、前記第３の区間と前記第２の区間の長さの比率により前記ノードに対して通過率が定義され、次元に従った前記探索ツリーのレベルに属するノードの通過率の平均によって前記次元に対して通過率が定義され、次元の通過率に関する値を演算する手段を使用して各次元に対して上記値が演算され、前記観測ベクトルの成分が前記探索前に並べ替え規則に従って前記生成ベクトルを並べ替えて得られる並べ替えられた点の格子内に示され、前記並べ替え規則は通過率に関する前記値により定義され、探索される第１の次元が低通過率を示す、ことを特徴する方法にある。
【０１００】
【発明の実施の形態】
上記および他の本発明の特徴は、添付の図面に関連して与えられる以下の説明を読むことからさらに明らかになるであろう。
【０１０１】
再び、たとえばＤＳ−ＣＤＭＡあるいはＭＣ−ＣＤＭＡ通信システムの受信機において実施されるような限界距離復号化過程について考える。
【０１０２】
以下の説明においては、各ユーザｋに対して、あるいは各ユーザｋによって送信されるシンボルｄk(ｉ)＝ｄkR(ｉ)＋ｊ・ｄkI(ｉ)は、カージナルス数|Ａk|の複素変調アルファベットＡkに属するものと仮定する。
【０１０３】
一般性を損なうことなく、その後、成分ｄkR(ｉ)およびｄkI(ｉ)はＰＡＭ変調シンボルであると仮定される。詳細には、以下の結果は、ウェブサイトmars.bell-labs.comにおいて入手可能な「Achieving near-capacity on a multiple antenna channel」というタイトルのHochwald等の論文に示されるように、ユーザに対してあるいはユーザによって送信されるシンボルがＰＳＫ変調シンボルである場合に拡張されることができる。
【０１０４】
Ｍ2k-1およびＭ2kがそれぞれｄkR(ｉ)およびｄkI(ｉ)の場合の変調順序を表すとき、以下の式が成り立つ。
【０１０５】
【数３５】
0004270934.tif 000036
【０１０６】
たとえば、これは、ｄk(ｉ)が１６ＱＡＭシンボルの場合に相当する(そのような場合には、Ｍ2k-1＝Ｍ2k＝４)。
【０１０７】
以下の平行移動が達成されるものとすると、
【０１０８】
【数３６】
0004270934.tif 000037
【０１０９】
再びベクトルで表すと
【０１１０】
【数３７】
0004270934.tif 000038
【０１１１】
ここで、ｗM＝(Ｍ1−１，Ｍ2−１，・・・，Ｍ2K−１)である。成分ｄ’kR(ｉ)およびｄ’kI(ｉ)はＺの要素であり、結果としてｄ’2(ｉ)はＺ2Kのベクトルである。
【０１１２】
一般論として、成分ｄkR(ｉ)およびｄkI(ｉ)をＺの要素に変換するアフィン変換が存在し、ベクトルｄ’2(ｉ)はＺ2Kのベクトルによって表されることができる。
【０１１３】
これ以降、ベクトルｄ’2(ｉ)の集合はベクトルｄ2(ｉ)の集合のようにコンスタレーションと呼ばれることになり、前者は上記の変換によって後者に直接に結び付けられる。
【０１１４】
同じようにして、対応する変換が、(２３)に定義されるようにｙ2(ｉ)上で達成される。言い換えると、以下の式が成り立つ。
【０１１５】
【数３８】
0004270934.tif 000039
【０１１６】
これ以降、暗黙のうちに行われるものと仮定される、このアフィン変換によって、ベクトルｄ2(ｉ)Ｍ2は、Ｇ＝Ｍ2の場合の式(５)によって定義されるような次元２．Ｋの点の格子ΛΛ2に属する。同様に、ｙ2(ｉ)において雑音白色化が実行される場合には、ベクトルｄ2(ｉ)(〜)Ｍ2は、行列Ｇ＝(〜)Ｍ2＝Ｍ2(Ｗ2T)-1によって生成される点の格子Ω2に属する。
【０１１７】
各ユーザｋの場合に、次元２ｋ−１および２ｋはそれぞれ、考慮されるユーザｋによって、あるいはそのユーザｋに対して送信される複素シンボルの実数部および虚数部を有する。図３に示されるように、ユーザｋのコンスタレーション、すなわち同じ意味で変調コンスタレーションが次元２ｋ上に射影される。この射影は区間［Ｍ2k-，Ｍ2k+］を定義する。境界Ｌ2k-およびＬ2k+が(１８)〜(２２)に従って確定されているとき、探索区間［Ｂ2k-，Ｂ2k+］は以下の式によって定義される。
【０１１８】
【数３９】
0004270934.tif 000040
【０１１９】
一旦、探索区間［Ｂ2k-，Ｂ2k+］において値ｂ2kが選択されたなら、境界Ｌ2k-およびＬ2k+が確定され、次元２ｋ−１上の新たな探索区間［Ｂ2k-1-，Ｂ2k-1+］が以下の式によって定義される。
【０１２０】
【数４０】
0004270934.tif 000041
【０１２１】
ここで［Ｍ2k-1-，Ｍ2k-1+］は次元２ｋ−１上へのコンスタレーションの射影である。
【０１２２】
図３では、楕円内に配置される格子の点は、それらの点がコンスタレーションに属する場合には灰色の丸によって表され、それらの点がコンスタレーションの外側に配置される場合には灰色の十字によって表される。
【０１２３】
そのアルゴリズムは、ある次元から先行する次元へと順番に進む。所与の次元ｋの場合に［Ｌk-，Ｌk+］の代わりに［Ｂk-，Ｂk+］内の各成分ｂxを変更することにより、その楕円内に配置され、コンスタレーションに属する候補の中からのみ最も近い格子点が確実に求められるようになる。
【０１２４】
本発明の根底をなす概念は、格子の次元が取り扱われる順序が探索の複雑さに大きく影響を及ぼすということである。(１７)から明らかなように、探索は、生成行列Ｇの最後の行に対応する最も高い順序の次元(この場合には２Ｋ)で開始し、より低い順序の次元で順番に進められる。
【０１２５】
図４に示されるように、所与のコンスタレーションの場合に、最初の２つの次元２Ｋおよび２Ｋ−１について考えてみる。
【０１２６】
そのコンスタレーションに属する点は、それらの点が楕円内に配置される場合には灰色の丸によって、そうでなければ黒色の丸によって表される。灰色の十字は、楕円内に配置されるが、コンスタレーションには属さない格子点を示す。受信された点ρの、次元２Ｋおよび２Ｋ−１によって定義される超平面への射影は、その実数座標ρ2Kおよびρ2K-1によって特徴付けられる。
【０１２７】
ユーザＫに対して、あるいはユーザＫによって送信されるシンボルは１６−ＱＡＭであると仮定される。それゆえ、コンスタレーションの次元２Ｋあるいは２Ｋ−１への射影は区間［０，３］に対応する。
【０１２８】
従来の限界距離復号化を用いる探索ツリーが図５の(ａ)に示されており、探索ツリーの各レベルは格子の次元に対応し、最も低いレベルは最も高い順序の次元(２Ｋ)と関連付けられる。最初の２つのレベル(図４の２Ｋおよび２Ｋ−１に対応する)が表されているが、探索ツリーが２Ｋレベルを含むことは理解されたい。探索ツリーの各ノードの水平方向への広がりは区間［Ｌi-，Ｌi+］を示しており、その細分区間［Ｂi-，Ｂi+］は白抜きの四角によって表され、一方、残りは灰色の四角によって表される。
【０１２９】
その探索は［Ｂ2K-，Ｂ2K+］の決定で開始する。図４から、［Ｌ2K-，Ｌ2K+］＝［０，３］および［Ｍ2K-，Ｍ2K+］＝［０，３］であり、それゆえ［Ｂ2K-，Ｂ2K+］＝［０，３］であることが明らかであり、それはｂ2Kが４つの値を取り得ることを意味する。
【０１３０】
ｂ2K＝０の場合には、
【０１３１】
【数４１】
0004270934.tif 000042
【０１３２】
であり、それゆえｂ2K-1の候補値が考慮されることはなく、それゆえノードは枯れた葉(dead leaf)ノードである。
【０１３３】
ｂ2K＝１の場合には、
【０１３４】
【数４２】
0004270934.tif 000043
【０１３５】
であり、それゆえ、そのノードも枯れた葉ノードである。
【０１３６】
ｂ2K＝２の場合には、
【０１３７】
【数４３】
0004270934.tif 000044
【０１３８】
であり、それゆえ、ｂ2K-1＝３が、考慮されることになる１つの候補値である。１つの分岐のみがこのノードから後続のレベル２Ｋ−２に延びる。
【０１３９】
ｂ2K＝３の場合には、
【０１４０】
【数４４】
0004270934.tif 000045
【０１４１】
であり、それゆえ、再びｂ2K-1＝３が、考慮されることになる１つの候補値である。１つの分岐のみがこのノードからレベル２Ｋ−２に延びる。
【０１４２】
以下に示される比によって、１つのノードの通過率σi(passing rate)が定義される。
【０１４３】
【数４５】
0004270934.tif 000046
【０１４４】
ノードの通過率は、探索を区間［Ｂi-，Ｂi+］に限定することによってもたらされるフィルタリング効果の指標である。通過率が低い場合には、フィルタリング効果が高く、逆に、通過率が高い場合には、フィルタリング効果は小さい。
【０１４５】
次元ｋの通過率、すなわち同じ意味で探索ツリーのレベルの通過率は、そのレベルに属するノードの平均通過率として定義される。
【０１４６】
図５の(ａ)から明らかなように、探索ツリーは、その根では選択性が不十分であり(ｂ2Kの場合に４つの中から４つの候補が保持される)、一方、より高いレベルのノードはかなり選択性が高くなる(ｂ2K-1の場合に３つの中から多くても１つの候補しか保持されない)。１つのノードの通過率は、そのノードの四角の全数に対する白抜きの四角の比として得られることができることに留意されたい。
【０１４７】
そのような探索ツリーは探索には不適切である。なぜなら、最終的に枯れた葉ノードに達する(すなわち、空の区間［Ｂk-，Ｂk+］に関連付けられる)多数の分岐が無駄に探索されるためであり、境界の計算は、最終的に無用であることがわかっている分岐に沿った中間ノードにおいて行われるべきである。
【０１４８】
本発明によれば、格子のベクトル、すなわち生成行列の行を並べ替えて、探索ツリーの根および低レベルのノードが低い通過率(すなわち、高い選択性)に対応するようにすることが提案される。これにより、コンスタレーションを横切らない楕円の大きな部分が初期段階において破棄されるようになる。
【０１４９】
第１の実施の形態によれば、生成行列の行あるいは次元が、射影されるコンスタレーションの大きさに正規化された、楕円の射影された中心の距離を表す値に従って並べられる。より具体的には、行あるいは次元ｋ毎に、以下の式が計算される。
【０１５０】
【数４６】
0004270934.tif 000047
【０１５１】
ここで、δk＝|ρk−(１／２)(ＭK-＋ＭK+)|は、射影されたコンスタレーションの中央に対する、次元ｋ上に射影された楕円の中心の距離を表す。
【０１５２】
実際には、式(４０)の代わりに、その正規化された距離を反映する任意の式を用いることができることは理解されたい。
【０１５３】
値εKは、射影されたコンスタレーションに対するコンスタレーション中心の射影の偏心度を表す。偏心度が高くなると、おそらく区間［ＬK-，ＬK+］および［ＭK-，ＭK+］はほとんど重ならなくなり、区間［ＢK-，ＢK+］は［ＬK-，ＬK+］よりも小さくなるであろう。
【０１５４】
第１の並べ替え規則によれば、行が、εKの値を増やすことにより並べ替えられ、すなわち正規化された距離が長くなると(あるいは同じ意味で、偏心度が高くなると)、行の順序が高くなる。そうすることにより、探索ツリー内の低いレベルは、楕円の中心の射影が、コンスタレーションの射影のはるか外側に位置する次元に対応する。それゆえ、低い通過率を示す次元は、探索ツリーの低いレベルに集められ、それにより初期段階で格子点を破棄できるようになる。第１の並べ替え規則を適用することにより、楕円とコンスタレーションとの交差部に属する候補点の探索が著しく加速されるであろう。
【０１５５】
どの次元に沿ってもコンスタレーションが同じ大きさを有する場合を対象にする第２の態様によれば、以下の並べ替え規則が用いられる。
【０１５６】
第２の並べ替え規則によれば、生成行列の最後の行は、それらが、ρK＜ＭK-あるいはρK＞ＭK+である次元Ｋに対応するように選択される。δ’KがρKとＭK-との間の距離(ρK＜ＭK-の場合)あるいはρKとＭK+との間の距離(ρK＞ＭK+の場合)を表すとき、これらの行はδ’Kの値を増やすことにより並べられ、すなわち、距離が長くなると、行の順序が高くなる。その探索は比較的長い距離値を示す次元で開始する。それゆえ、探索ツリーの低いレベルは、楕円中心の射影がコンスタレーションの射影のはるか外側に位置する次元に対応する。結果として、低い通過率を示す次元は探索ツリーの低いレベルに集められる。
【０１５７】
第３の並べ替え規則によれば、生成行列の第１の行は、それらが、ＭK-≦ρK≦ＭK+である次元ｋに対応するように選択される。
【０１５８】
これらの行は、上記のようにδKの値を増やすことにより並べられ、すなわち、距離が長くなると、その行の順序が高くなる。その探索は、比較的長い距離値を示す次元で開始する。所与の区間［ＬK-，ＬK+］の場合に、δKが低くなると、おそらく区間［ＢK-，ＢK+］は［ＬK-，ＬK+］と同じ大きさを有するであろう。それゆえ、高い通過率(すなわち低い選択性)を示す次元が探索ツリーの高いレベルに集められる。
【０１５９】
第２および第３の並べ替え規則は次元を並べ替えるために一緒に用いることができ、最後の行がρK＜ＭK-あるいはρK＞ＭK+を満たす行になり、最初の行がＭK-≦ρK≦ＭK+を満たす行になる。
【０１６０】
第２および／または第３の並べ替え規則を適用することにより、楕円とコンスタレーションとの交差部に属する候補点の探索が著しく加速される。この点が、本発明の限界距離復号化方法による探索ツリーを示す図５の(ｂ)に示される。ここで、第１あるいは第２の並べ替え規則を適用することにより、次元２Ｋを次元２Ｋ−１で置き換える、すなわち生成行列Ｇの最後の２行を置き換えることに繋がる。
【０１６１】
置き換え後に、その探索は新たな区間［Ｂ2K-，Ｂ2K+］の決定で開始する。図４から明らかなように、［Ｌ2K-，Ｌ2K+］＝［３，５］および［Ｍ2K-，Ｍ2K+］＝［０，３］であり、それゆえ［Ｂ2K-，Ｂ2K+］＝｛３｝である。成分ｂ2Kは１つの値のみをとることができ、それゆえ１つの分岐のみが探索されることになる。
【０１６２】
ｂ2K＝３の場合、［Ｌ2K-1-，Ｌ2K-1+］＝［２，３］であり、それゆえ、［Ｂ2K-1-，Ｂ2K-1+］＝［Ｌ2K-1-，Ｌ2K-1+］∩［Ｍ2K-1-，Ｍ2K-1+］＝［２，３］∩［０，３］＝［２，３］である。２つのノードのみ(図５の(ａ)の５つのノードと比較すると)を探索した後に、２つの候補点が見出される。
【０１６３】
第３の実施の形態によれば、各次元に対して、探索がその次元で開始されていた場合に(この次元に対応する行が生成行列の最後であったときに)、根によって示される通過率が計算される。この通過率はσ2Kiで表され、以下のように表されることができる。
【０１６４】
【数４７】
0004270934.tif 000048
【０１６５】
式(４０)の右辺に現れる項ｑ2K,2Kは、行列Δの右下角に現れる係数である。ここで、行列Δは、ｉ番目の行を行列の底部に置くために行置換にかけられた後に生成行列Ｇをコレスキー分解することによって得られるので、その項はｉに依存する。
【０１６６】
第４の並べ替え規則によれば、生成行列の行が、σ2Kiの値を減らすことにより並べられ、すなわち、その行は、通過率が低くなると、行の順序が高くなるように並べ替えられる。それゆえ、探索は、比較的低い通過率を示す次元で開始する。
【０１６７】
第３の実施の形態は２Ｋ回のコレスキー分解を必要とするので、それはユーザの数がかなり少ないときに有利である。
【０１６８】
並べ替え規則が用いられるときは必ず、次元の並べ替えはそれぞれ、生成行列の行の置換πとして表されることができる。一旦、受信された点ρに最も近いコンスタレーションの点ｂが見いだされたなら、ｂの成分において逆置換π-1が実行され、そこからＫ人のユーザのシンボルｄk(ｉ)が導出される。
【０１６９】
【発明の効果】
本発明によれば、符号分割多元接続方式のマルチユーザ検出の限界距離復号化過程の複雑さを緩和した方法を実現することができる。
【図面の簡単な説明】
【図１】  図２に示される受信機において用いられる検出方法に有用な点の格子を示す図である。
【図２】  限界距離復号化方法を用いるマルチユーザ受信機の構造の概略図である。
【図３】  コンスタレーションを考慮に入れる限界距離復号化の一例の概略図である。
【図４】  限界距離復号化において用いられる、コンスタレーションおよび受信された点の最初の２次元によって定義される超平面への射影を示す図である。
【図５】  (ａ)は従来技術による限界距離復号化方法の探索ツリーを示す図、(ｂ)は本発明による限界距離復号化方法の探索ツリーを示す図である。
【符号の説明】
２１０  フィルタ、２２０  雑音白色化、２３０  限界距離復号器(sphere decoder)。
【図１】
0004270934.tif 000049
【図２】
0004270934.tif 000050
【図３】
0004270934.tif 000051
【図４】
0004270934.tif 000052
【図５】
0004270934.tif 000053