(57)【要約】この発明は一般に、特にｓｐｈｅｒｅ復号による信号を復号する方法、装置およびプロセッサ制御コードに関係する。複数の値のうち１つの値を有する事によって生成されるシンボルを複数シンボル用いてシンボル列として符号化された後送信され、チャネルを通って受信した信号を復号するための方法であり、チャネルによって決定される多次元格子の、ある領域内のシンボルの候補を探索する事によってシンボル候補の列であるシンボル列の候補を一つ以上探索し、前記格子は前記シンボル列の各シンボルに対応する一つの次元を有し、前記領域は前記受信信号からの距離によって定義されており、前記受信信号に対して前記シンボル列の候補を一つ以上選択する事によって前記シンボル列を復号する事を含み、前記シンボル候補の探索は前記送信されたシンボルの候補値を選択し、選択された前記候補により定義された前記格子が前記受信信号からの境界距離の内側にあるか否かをテストする事を含み、前記探索を、制限された回数の候補シンボルをテストした後に止める機能を具備する事を特徴とする信号復号方法。【選択図】      図４
2007519281.tif 000002
【特許請求の範囲】
【請求項１】
複数の値のうち１つの値を有する事によって生成されるシンボルを複数シンボル用いてシンボル列として符号化された後送信され，チャネルを通って受信した信号を復号するための方法であり、
チャネルによって決定される多次元格子の、ある領域内のシンボルの候補を探索する事によってシンボル候補の列であるシンボル列の候補を一つ以上探索し、前記格子は前記シンボル列の各シンボルに対応する一つの次元を有し、前記領域は前記受信信号からの距離によって定義されており、
前記受信信号に対して前記シンボル列の候補を一つ以上選択する事によって前記シンボル列を復号する事を含み、
前記シンボル候補の探索は前記送信されたシンボルの候補値を選択し、選択された前記候補により定義された前記格子が前記受信信号からの境界距離の内側にあるか否かをテストする事を含み、
前記探索を、制限された回数の候補シンボルをテストした後に止める機能を具備する事を特徴とする信号復号方法。
【請求項２】
前記候補シンボルのテストは、シンボルにより決定される前記格子の前記部分が前記境界距離の内側にある第１のカテゴリ、シンボルにより決定される前記格子の前記部分が前記境界距離の外側にある第２のカテゴリ、および前記シンボルが推定された前記シンボル列の最後のシンボルである第３のカテゴリの3つのカテゴリのどのカテゴリに前記候補シンボルが属するかを決定するテストを含む、請求項1に記載の方法。
【請求項３】
前記復号は前記シンボル列の候補を定めることに失敗した場合は、前記送信シンボル列の線形推定結果を出力する機能を具備した請求項1または2に記載の方法。
【請求項４】
前記線形推定値がゼロフォーシング推定値である事を特徴とする請求項3に記載の方法。
【請求項５】
前記シンボル列の前記各シンボルは１つ以上のビットを含み、前記復号が前記シンボル列の各シンボルの各ビットについて尤度値を含む軟出力を提供し、方法がさらに前記線形推定値から前記ビットの尤度値を求めることを含む、請求項3または4に記載の方法。
【請求項６】
前記復号は前記シンボル列の候補の選択された１つについて距離メトリックに応答して決定された軟出力を提供し、前記距離メトリックが前記受信信号と前記シンボル列の候補の距離に依存している、請求項1または2に記載の方法。
【請求項７】
前記軟出力が前記探索により発見された全ての前記シンボル列の候補の距離メトリックに応答して決定される、請求項6に記載の方法。
【請求項８】
各シンボルが1ビット以上を有し、それにより前記シンボル列がビットの列を定義し、前記復号が前記ビットの列の各ビットについて確率値を提供することをさらに含む、請求項1、2、6および7のいずれか1項に記載の方法。
【請求項９】
前記ビットの確率値は、ビットが第1の論理値を有する前記1つ以上のシンボル列の候補の第1の組と、ビットが前記第1の論理値と異なる第２の論理値を有する前記1つ以上のシンボル列候補の第２の組とを使用し、シンボルの前記第1と第２の組を使用して決定される第1と第2の尤度値の比率を取ることによって決定され、前記第1と第２の組の１つが空であるとき、前記ビットについてデフォルト確率値を提供することをさらに含む、請求項8に記載の方法。
【請求項１０】
候補シンボルのための前記探索が前記初期の推定値から距離を増加するように進行する、請求項1乃至9のいずれか1項に記載の方法。
【請求項１１】
シンボルの前記列が複数の送信アンテナを使用しているＭＩＭＯ(多入力多出力)チャネル上で伝送され、前記受信信号が複数の受信アンテナにより受信される、請求項1ないし10のいずれか1項に記載の方法。
【請求項１２】
前記信号が空間-時間ブロックコードを使用して符号化される請求項1乃至11のいずれか1項に記載の方法。
【請求項１３】
作動するとき、請求項1乃至12のいずれか1項に記載の方法を実施するプロセッサ制御コード。
【請求項１４】
請求項13のプロセッサ制御コードを運ぶ担体。
【請求項１５】
複数の値のうち１つの値を有する事によって生成されるシンボルを複数シンボル用いてシンボル列として符号化された後送信され、チャネルを通って受信した信号を復号する復号器であって、
チャネルによって決定される多次元格子の、ある領域内のシンボルの候補を探索する事によってシンボル候補の列であるシンボル列の候補を一つ以上探索し、前記格子は前記シンボル列の各シンボルに対応する一つの次元を有し、前記領域は前記受信信号からの距離によって定義されており、
前記受信信号に対して前記シンボル列の候補を一つ以上選択する事によって前記シンボル列を復号する事を含み、
前記シンボル候補の探索は前記送信されたシンボルの候補値を選択し,  選択された前記候補により定義された前記格子が前記受信信号からの境界距離の内側にあるか否かをテストする事を含み、前記探索を、制限された回数の候補シンボルをテストした後に止める機能を具備する事を特徴とする復号器。
【請求項１６】
請求項15の復号器を含む受信機。
【請求項１７】
チャネル上で伝送されるシンボル列を含む受信信号を復号する復号器であって、
前記列について候補シンボルの受信信号空間における前記受信信号からの距離を決定することにより、前記受信信号の半径内の伝送されたシンボル列の候補を探索し、復号されたデータ出力を提供するｓｐｈｅｒｅ復号器と、
前記距離決定をカウントし、前記カウントに応答して探索することを止めるためにｓｐｈｅｒｅ復号器を制御するｓｐｈｅｒｅ復号器コントローラとを含む復号器。
【請求項１８】
前記チャネルがＭＩＭＯチャネルである請求項17に記載の復号器。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は一般に信号を復号するための方法、装置及びプロセッサ制御コードに関係し、特にｓｐｈｅｒｅ復号によるプロセッサ制御コードに関係する。
【背景技術】
【０００２】
ｓｐｈｅｒｅ復号は信号処理の分野においてさまざまな応用範囲を有する技術である。ここで、特定の参照はＭＩＭＯ(多入力多出力)チャネル上で受信される信号、および空間-時間復号への技術の応用になされるであろう。しかしながら、ここに説明される発明の実施例は、多ユーザシステムのような関連システム、および他の類似の復号、例えば、ＣＤＭＡ(符号分割多元接続) システムの多ユーザ判定器に適用することができる。
【０００３】
データ伝送速度の向上及び、同等に、利用可能な帯域幅を一定の伝送速度でさらに効率的に利用する手段に対して継続的な要求がある。現在、（ヨーロッパでは）Ｈｉｐｅｒｌａｎ／２、及び（米国では）ＩＥＥＥ８０２．１１ａといったＷＬＡＮ（無線ローカル・エリア・ネットワーク）が最高５４Ｍビット／秒のデータ伝送速度を提供している。複数の送受信アンテナを使用するとこれらのデータ伝送速度を非常に増加させる可能性があるが、１つの受信アンテナで全ての送信アンテナからの信号を受信するのでＭＩＭＯチャネル上で受信された信号を復号することは困難である。異なるチャネル上で伝送されるシンボルは無相関ではあるが、同様の問題は多ユーザシステムにおいても起こる。従って、ＭＩＭＯシステムについて復号技術の改良の必要性がある。これらの技術は無線ＬＡＮにおいて、可能性として第四世代移動電話網において、または他の多くの通信システム形式において適用性がある。
【０００４】
図１は典型的なＭＩＭＯデータ通信システム１００を示す。データ源１０２は（情報ビットまたはシンボルを含む）データをチャネル符号器１０４に提供する。チャネル符号器は一般的に再帰的組織畳込み（recursive systematic convolutional：ＲＳＣ）符号器のような畳込み符号器、またはさらに強力な所謂ターボ符号器（インタリ−ブ器を含む）を具備する。入力したビットよりも多くのビットが出力され、一般的に符号化率は２分の１または３分の１が主に用いられる。チャネル符号器１０４にはチャネル・インタリーブ器１０６、そして示された例では空間‐時間符号器１０８が続く。空間‐時間符号器１０８は複数の各送信アンテナ１１０から同時伝送のために複数の符号シンボルとして入力シンボル（単一または複数のシンボル）を符号化する。
【０００５】
空間‐時間符号化は符号器の一つとして記述され、空間及び時間伝送ダイバシティを提供するためデータに作用する符号化行列（coding matrix）によって記述される；これは伝送のための符号化シンボルを提供するために変調器に続く。空間‐周波数符号化が追加して（または代わりに）使用される。このように、広い意味では、入力シンボルはダイバシティ増加のための空間及び時間及び／または周波数座標を有する格子（grid）の中に分配される。空間‐周波数符号化が使われる所で、個別の周波数チャネルはＯＦＤＭ（直交周波数分割多重化）搬送波上に変調され、cyclic prefixがチャネル分散の影響を緩和するために各伝送シンボルに付加される。
【０００６】
符号化伝送信号はＭＩＭＯチャネル１１２を経由して受信アンテナ１１４に伝播し、アンテナは複数の入力を空間‐時間（及び／または周波数）復号器１１６へ提供する。復号器は符号器１０８及びＭＩＭＯチャネル１１２の影響を取除くという役目（task）を持ち、ｓｐｈｅｒｅ復号器によって実施される。復号器１１６の出力は複数の信号ストリームを各送信アンテナについて１つ含み、各々は特定の値を有する伝送シンボルの確率に基づき所謂軟出力、または尤度データを搬送する。このデータはチャネル・インタリーブ器１０６の結果を反転するチャネルデインタリーブ器１１８に提供され、そして畳込み符号を復号するビタビ（Viterbi）復号器のようなチャネル復号器１２０に提供される。一般的に、チャネル復号器１２０はＳＩSＯ（soft-in soft-out）復号器であり、それは受信シンボル（または、ビット）の尤度データであり、硬判定復号器より出力として精度の高い尤度データを提供する。チャネル復号器１２０の出力はある所望の方法においてデータをさらに処理するためにデータ・シンク１２２に提供される。
【０００７】
通信システムによっては、所謂ターボ復号が適用されチャネル復号器１２０からの軟出力がチャネル・インタリーブ器１０６と同一のチャネル・インタリーブ器１２４に提供され、それは反復空間‐時間（及び／または周波数）及びチャネル復号のために復号器１１６に軟出力（尤度）データを順に提供する。このように反復復号を適用する場合は誤り検査ビットを含めることなどにより、誤りの有無を復号器に伝えることができると効果的である。
【０００８】
前述の通信システムにおいてチャネル符号化及び空間‐時間符号化の双方は時間ダイバシティを提供し、斯くしてこのダイバシティは達成できる追加の信号対雑音比利得の項における戻送逓減の法則に従うことが理解されるであろう。このようにある特定の空間‐時間／周波数復号器によって提供される便宜性を考慮するとき、これらはチャネル符号化を含むシステムの状況において最もよく考慮される。
【０００９】
通信システム１００において最も困難な作業の１つは復号器１１６によって行われる空間‐時間（或いは、周波数）ブロック符号（ＳＴＢＣ）の復号であり、これは受信機において相互に干渉している伝送シンボルを分離することが含まれるためである。最適なＳＴＢＣ復号器は事後確率（ＡＰＰ）復号器 で、それは全ての可能な伝送シンボルの徹底的な探索を行う。そのような復号器はすべての送信アンテナについてあらゆる伝送される可能性のある信号点を考慮し、全ての可能な受信号を計算することによって実際に受信信号とこれらを比較しかつ最もありそうな解として最も近いユークリッド距離を有する信号を選定する。しかしながら、考慮する組合せの数は、わずかな数のアンテナ、１６ＱＡＭ（直交振幅変調）などの変調方式、および比較的短い時間の分散でさえ莫大であり、アプローチの複雑さはデータ伝送速度とともに指数関数的に増大する。したがって、準最適なアプローチは技術的かつ商業的に重要である。
【００１０】
空間‐時間ブロック復号のためのいくつかの一般的な選択はゼロフォーシング、及び最小平均２乗誤差（ＭＭＳＥ）推定器といった線型推定器を含む。ゼロフォーシング方式は伝送シンボルの列の推定値を直接計算するために適用され、もしくは推定シンボルは前に計算されたシンボルの影響を次が決定される前に減算する「逐次干渉抑制」方法で１つずつ決定される。この手法では、例えば、最も信頼度の高いシンボルを最初に計算することができる。
【００１１】
ｓｐｈｅｒｅ復号または復調は、広い意味で探索空間を（行列チャネル応答及び／または空間-時間符号器に依存して）格子として表現し、そして受信信号を中心とする所定の半径の超球内に位置する格子点を生成する可能なシンボル列上だけで、伝送シンボル列に関する最良の推定値を探索することによって、大きく負荷を制限し、ＡＰＰ復号器の性能に近づけることができる。最尤解はチャネルによって修正されたとき、対応する受信信号に最も近いチャネルの影響を加味した伝送信号である。実際、行列チャネル応答及び／または空間‐時間符号器は矩形格子から入力点空間を歪ませる傾向があり、概念的には、入力点空間における探索領域は球よりはむしろ楕円体になる。
【００１２】
探索空間は全体の格子から単に小部分の格子まで減少するので、探索に必要な計算の数はＡＰＰ復号器と比べ大幅に削減され、かつ似通った特性を得ることができる。しかしながら、そのような手順の実用的な適用において、いくつかの問題がある。まず第１に、格子点が受信信号の必要な距離内にあるかどうかを確認しなければならない。これは比較的簡単な手順であり、以下で概説される。しかしながら、第２にどんな半径を採用するか決めなければならない。これは探索の速度にとって重要であり、いくつかの、しかし多過ぎない格子点が半径内で見つかるように選択されなければならない。その半径は雑音レベルに従って、及び随意的にチャネルに従って調整される。しかしながら、探索半径を定めても探索数が定まらないというより微妙な問題がさらにあり、実用的なシステムにおいて、それはｓｐｈｅｒｅ復号化計算(および、したがって利用可能なデータ伝送速度)の演算に必要な時間が決定できないことを意味する。これは発明の実施例により処理される１つの問題である。
【００１３】
ｓｐｈｅｒｅ復号に関する背景の従来技術は下記において見ることができる：
E．Agrell、T．Eriksson、A．Vardy and K．Zeger、「Closest Point Search in Lattices」、IEEE Trans. on Information Theory、vol.４８、no.８、Aug .２０００； E．Viterbo and J．Boutros、「A universal lattice code decoder for fading channels」、IEEE Trans. Inform、Theory ,vol.４５、no.５、pp.１６３９〜１６４２、Jul.１９９９； O．Damen、A．Chkeif and J．C．Belfiore、「Lattice code decoder for space-time codes」、IEEE Comms. Letter、vol.４、no.５、pp.１６１〜１６３、May ２０００； B．M．Hochwald and S．T．Brink、「Achieving  near  capacity on a multiple-antenna channel」、http://mars.bell-labs.com/cm/ms/what/papers/listsphere/ 、December ２００２；「On the expected complexity of sphere decoding」、in Conference Record of the Thirty-Fifth Asimolar Conference on Signal,Systems and Computers,２００１、vol.２、pp.１０５１〜１０５５；B．Hassibi and H．Vikalo、「Maximum-Likelihood Decoding and Integer Least-Squares : The Expected Complexity」、in Multiantenna Channels: Capacity, Coding and Signal Processing （J．Foschini and S．Verdu）、http://www.its.caltech.edu/〜hvika1o/dimacs.ps； A．M．Chan、「A New Reduced-Complexity Sphere Decoder For Multiple Antenna System」、IEEE International Conference on Communications、２００２、vol.１、April-May ２００２； L．Brunel、J．J．Boutros、「Lattice decoding for joint detection in direct-sequence CDMA systems」、IEEE Transactions on Information Theory, Volume:４９、Issue:４、April ２００３、pp.１０３０〜１０３７；A．Wiesel、X．Mestre、A．Pages and J．R．Fonollosa、「Efficient Implementation of Sphere Demodulation」Proceedings of IV IEEE Signal Processing Advances in Wireless Communications、pp.５３５、Rome、June １５-１８,２００３；US Patent Application Number ＵＳ２００３／００７６８９０B．M．Hochwald and S．Ten  Brink、 filed July ２６,２００２,「Method and apparatus for detection and decoding of signals received from a linear propagation channel」、to Lucent Technologies；US Patent Application Number ＵＳ２００２／０１１４４１０L．Brunel、filed August ２２,２００２,「Multiuser detection method and device in DS-CDMA mode」、to Mitsubishi； H．Vikalo、「Sphere Decoding Algorithms for Digital Communications」、PhD Thesis, Stanford University,２００３； B．Hassibi and H．Vikalo、「Maximum-Likelihood Decoding and Integer Least-Squares: The Expected Complexity」、in Multiantenna  Channels: Capacity, Coding and Signal Processing,（editors J．Foschini and S．Verdu）。
【００１４】
例えば、Agrell等の論文は入力が任意のｍ次元整数、即ちｘ∈Ｚmである無限格子についての最近接点（closest-point）探索を述べており、格子復号及び探索方法の基本的な概念を概説しているが、しかし、単に硬判定出力を提供する方法を述べているに過ぎない。他の論文の大部分は探索領域境界の評価を必要とし、それにもかかわらず境界を限られた計算量の計算を保証しない。
【００１５】
【数１】
2007519281.tif 000003
ここで、Ｋは軟出力を推定するために必要なシンボルの所定の数、例えば５０、である。初期探索半径はＫシンボルが見出されるまで無限大に設定される。そのリストが一杯になるとき、即ちＫシンボルが見出されたとき、探索半径はリストにおける最大距離メトリックに設定される。候補のリストが可能な限りのＫ最短距離メトリックを持つように、多数の並べ替え（sort）が候補リストを並べ替える効率的な方法として提案される。これは効果的に設定処理手順の役割を果たす。しかしながら再び、チャネル統計に依存してこの方法の計算量は境界を限定しない。
【００１６】
他の復号器または判定器（ここで両者は元来伝送されたデータを検出している同様の問題を解こうとすることを意味しているので、それらの用語は実質的に同じ意味で使用される）はビタビ復号器（指数計算の複雑さがある）のようなトレリス復号器、及びＶ-ＢＬＡＳＴ（Bell labs Layered Space Time）復号器及びブロック判定フィードバック等化器といった、準最適な性能を提供する複雑さ低減判定器を含む。
【００１７】
この点で、ｓｐｈｅｒｅ復号処理手順の動作の概観を提供することは助けになる。Ｎ伝送シンボルの列について、Ｎ次元格子が探索され、（列の第１のシンボルに対応する）Ｎ番目次元層によって始まる。送信される可能性のある全ての信号点からあるシンボルがこの階層の信号として選択され、受信信号からの生成格子点の距離が検査される。格子点がこの距離の中にあれば、その処理手順は列における次のシンボルに関する値を選択し、Ｎ−１次元における受信信号から生成格子点の距離を検査する。その処理手順は順に連続する各シンボルを検査し続け、全てが範囲の中にあれば、それは１つの次元における格子点に最終的に収斂する。シンボルが選ばれた半径の外にあれば、その処理手順は一つ上の階層に戻り、検査のためその層（次元）における次の可能なシンボルを選択する。このように、その処理手順は最も低い節点（nodes）がシンボルの完全な列に対応するツリーを作り、且つツリーのｎ番目のレベルの節点の数が関連のｎ番目次元のｓｐｈｅｒｅ内部の格子点の数に対応する。
【００１８】
シンボル列の完全な候補が見出されるとき、受信信号とシンボル列から生成された格子点の距離が見出される。なお、最尤解の探索において、より最適な解はこの距離よりも受信信号に近い点に存在するので、初期半径をこの距離まで減少させることができる。ツリーが完成されたとき、受信信号に最も近い格子点を選択することによって、復号器は硬出力、即ち、最尤解を提供するために使用することができる。代りに、軟出力を求めるためには受信信号に最も近い複数の格子点を用いて、例えば関連する尤度値として受信信号からこれらの各々の距離を使用して提供することができる。多くの並べ替えが、さらに以下で説明されるように、受信信号に最も短い距離メトリックを有する格子点を持つ候補の部分集合を選択するために提案された。また、探索を通して固定探索半径を設定し、固定探索半径より小さい距離メトリックを提供する信号候補の部分集合を用いる手法も提案されている。
【発明の開示】
【課題を解決するための手段】
【００１９】
複数の値のうち１つの値を有する事によって生成されるシンボルを複数シンボル用いてシンボル列として符号化された後送信され、チャネルを通って受信した信号を復号するための方法が提案され、復号方法は、チャネルによって決定される多次元格子の、ある領域内のシンボルの候補を探索する事によってシンボル候補の列であるシンボル列の候補を一つ以上探索し、前記格子は前記シンボル列の各シンボルに対応する一つの次元を有し、前記領域は前記受信信号からの距離によって定義されており、前記受信信号に対して前記シンボル列の候補を一つ以上選択する事によって前記シンボル列を復号する事を含み、前記シンボル候補の探索は前記送信されたシンボルの候補値を選択し、選択された前記候補により定義された前記格子が前記受信信号からの境界距離の内側にあるか否かをテストする事を含み、前記探索を、制限された回数の候補シンボルをテストした後に止める機能を含む。
【００２０】
実施例によれば、シンボル候補のテスト (および/または、候補距離決定)を制限された回数で打ち切ることによって演算負荷の上限が定められ、かつ、復号解が欠如するようなリスクが生じることもなく、一定の速度で送信された信号の復号を可能にする。テストすることは、選択された候補、より厳密に言えば、選択された候補により生成された格子点または層が受信信号から境界距離の中にあるか否かを決定する事である。実施例において、候補シンボルテストは、シンボルが境界距離の内側または外側にあるかどうか、または、シンボルが推定された伝送列の最後のシンボルかどうかを決定するテストを含む。したがって、これらの3つのカテゴリのそれぞれの場合の数はカウントされ、予め定められた制限カウントに達した後に探索することは止められる。
【００２１】
実施例では、(初期)の境界距離または半径は、これが例えば候補シンボルテストの予定された数によって構成されたツリーに影響を及ぼすなら、まだ復号処理に効果を有する。この理由で、境界距離または半径は、例えば、雑音や雑音の分散および/またはチャネル応答に依存して適応的に変更されてもよい。
【００２２】
手順は列の各シンボルについて候補値をテストすることを試みるが、チャネルおよび受信信号に依存して、ツリーのエンドノードで列について候補シンボルの少なくとも１つの完全な組を有する完全なツリーが構成されないかもしれない。探索がシンボル列の候補を位置つけることに失敗するとき、線形の、好ましくはゼロフォーシングの推定値が復号手順の出力として提供されるかもしれない。その他、逐次干渉抑圧およびＭＭＳＥ解などの、どんな線形推定値が採用されてもかまわない。一般に各シンボルは１以上のビットによって定義されるので、シンボルの列はビットの列を定義する。そして復号はビット列の各ビットについて確率値を供給することを含む（あるいはさらに含む）かもしれない。シンボル列の候補が位置付けられないとき、ゼロフォーシングによって推定されたシンボルはそのような各ビットの軟出力を計算するために用いることができる。
【００２３】
復号は出力としてシンボル列の最小距離候補を選択することにより硬出力を提供するかもしれない、または、複数のシンボル列を確率に関連する値、（例えばシンボル列によって較正される格子点と受信信号の距離）といっしょに出力する事によって、いわゆる軟出力を提供するかもしれない。探索は、チャネル応答によって決定された多次元の格子のある領域内に格子点を形成するシンボル列の候補を探索する。軟出力は、事実上、並べかえの必要性を避けるために探索により発見されるシンボル列の候補のすべて（の確率）を用いて計算してもよい。一般に各シンボルは1ビット以上の送信ビットと関連づけられており、復号は見つけられた全てのシンボル列の候補（少なくとも一つ以上）に基づき計算される各ビットの確率を出力するように構成されてもかまわない。ビットの確率値は、ビットがそれぞれ第１および第2の論理値を持っている(確認された候補列の)シンボルの組に基づいて、第1および第2論理レベルを有するビットについての尤度値の比率を取ることによって決定されるかもしれない。ここで、あるビットに関して、候補列のどんなシンボルもそのような値を持たない場合、あるいはこれらの値とそのような比率が計算することができず、ビットのデフォルト確率値が、例えば別の論理値に関する最小距離メトリックに基づいて、または50などのデフォルト最大値を含んで提供されるかもしれない。
【００２４】
好ましい実施例において、候補シンボルのための探索は、例えば、受信信号およびチャネルの応答から決定された、伝送信号のゼロフォーシング推定値（または別の線形か計算するのが簡単な推定値）から距離を増加するように進行する。このアプローチは、(例えば、探索がシンボル列のうち、信頼度が高いシンボルで始まることができるように)探索された層に、および/またはある層（次元）またはツリーノードでコンステレーションの信頼度が高い順に選択するようにしてもかまわない。
【００２５】
シンボルの列は、多ユーザ通信システムにおける複数のユーザから伝送されたシンボル、またはＭＩＭＯ通信システム(どちらの場合も、行列・チャネルのフォームを含むチャネル)において、複数の送信アンテナにより送信され、かつ第２の複数の受信アンテナにより受信されたシンボルの列、を含むかもしれない。ＭＩＭＯ通信システムでは、シンボルの列は、空間-時間ブロックコード(STBC)のシンボル、または空間-時間トレリスコード(STTC)のシンボル、または空間-周波数コードのシンボル、あるいは空間-時間/周波数コードのシンボルを含むかもしれない。空間-周波数のコード化信号は、例えば、複数の搬送波を有するＯＦＤＭ(直交周波数分割多重化)システムで複数の周波数チャネルに亘って符号化され、その場合に、復号器は直列-並列変換器および高速フーリエ変換器により、続いて逆フーリエ変換器および並列-直列変換器により前処理されるかもしれない。
【００２６】
上述された方法は、例えばインタリーブブロックコード復号とチャネル復号を有するターボ復号器に採用されるかもしれないことが認識されるであろう。
発明はさらに上述された方法を実施するように構成される復号器、およびそのような復号器を含む受信機を提供する。
【００２７】
したがって、発明のさらなる態様では、複数の値のうち１つの値を有する事によって生成されるシンボルを複数シンボル用いてシンボル列として符号化された後送信され、チャネルを通って受信した信号を復号する復号器が提供され、復号器は、チャネルによって決定される多次元格子の、ある領域内のシンボルの候補を探索する事によってシンボル候補の列であるシンボル列の候補を一つ以上探索し、前記格子は前記シンボル列の各シンボルに対応する一つの次元を有し、前記領域は前記受信信号からの距離によって定義されており、前記受信信号に対して前記シンボル列の候補を一つ以上選択する事によって前記シンボル列を復号する事を含み、前記シンボル候補の探索は前記送信されたシンボルの候補値を選択し、選択された前記候補により定義された前記格子が前記受信信号からの境界距離の内側にあるか否かをテストする事を含み、前記探索を、制限された回数の候補シンボルをテストした後に止める機能を含む。
【００２８】
発明の上記態様において、多次元の格子は、送信機において付加的にまたは代わりに、採用された空間-時間符号やまたは他の符号により決定されるかもしれない。
別の関連する態様では、発明はＭＩＭＯチャネル上で伝送されるシンボルの列を含む受信信号を復号する復号器を提供し、復号器は、列について候補シンボルの受信信号空間における受信信号からの距離を決定することにより、受信信号の半径内の伝送されたシンボル列の候補を探索し、復号されたデータ出力を提供するｓｐｈｅｒｅ復号器と、距離判定回路をカウントし、カウントに応答して探索することを止めるためにｓｐｈｅｒｅ復号器を制御するｓｐｈｅｒｅ復号器コントローラとを含む。
【００２９】
望ましくは、復号器は伝送シンボルの初期推定値を決定するシンボル推定器を含み、そしてｓｐｈｅｒｅ復号器は、初期推定値から始めて、距離メトリックを決定することにより受信信号の半径の中に格子点を発生させる伝送シンボル列の候補を探索するかもしれない。
【００３０】
上述の方法及び復号器はプロセッサ制御コードを使用して実施され、および/またはプロセッサ制御コードにおいて具体化されることを当業者は認識するであろう。このようにさらなる態様において、本発明は、例えば、ディスク、ＣＤ‐ＲＯＭまたはＤＶＤ‐ＲＯＭや、読取専用メモリのようなプログラムされたメモリ（Firmware）のような記録媒体または光学または電気信号担体のようなデータ担体上でそのようなコードを提供する。発明の実施例はＤＳＰ（Digital Signal Processor）、ＡＳＩＣ（Application Specific Integrated Circuit）またはＦＰＧＡ（Field Programmable Gate Array）上で実施される。このように、そのコードは従来のプログラム・コード、または、例えば、ＡＳＩＣまたはＦＰＧＡを設定し、または制御するコードを含む。いくつかの実施例において、そのコードはＶｅｒｉｌｏｇ（商標名）またはＶＨＤＬ（Very high Speed integrated circuit Hardware Description Language）といったハードウェア記述言語に関するコードを含む。当業者は理解するであろうが、本発明の実施例に関するプロセッサ制御コードは相互に関係する複数の接続部品の間で分配されることもある。
【００３１】
これらの及び他の本発明の態様は付随の図面を参照して例についてのみここでさらに記述される。
【発明を実施するための最良の形態】
【００３２】
発明の実施例は、ｓｐｈｅｒｅ復号の原理上の問題である演算量が一意に定まらない問題を解決し、特に伝送シンボルの可能な候補を発見するために行われる探索の数を制限することによって、計算量の上限を設定する。その上発明の実施例は、十分な信号の候補が見つかってない場合も最大事後確率復号のための尤度に近似する軟出力を求める方法を提供する。発明の実施例は空間-時間復号または判定に関して議論が、それに制限されるものではない。
【００３３】
ここでｎＴの送信信号及びｎＲの受信信号（または、等価的に、ｎＴ及びｎＲ成分をそれぞれ持つ送信及び受信信号）による空間‐時間伝送方式について考える。時間kにおける１×ｎＲの受信信号ベクトルは：
【００３４】
【数２】
2007519281.tif 000004
例えば、トレーニング系列は各送信アンテナから順に送信され、（干渉問題を回避するため）送信アンテナから受信アンテナへのチャネルを特化するため全ての受信アンテナ上で受信を行う。これは大きな諸経費をかける必要がなく、データ伝送速度はトレーニングの間では高く、そして例えば、室内チャネルなど変動がゆるやかな場合、データ伝送速度はチャネルの変動に対して十分速く、トレーニングは例えば０．１秒毎に実行すれば十分である。その他、干渉問題が起こるのでトレーニングの複雑さを増大させるけれども、直交系列を全ての送信アンテナから同時に伝送してもよい。
【００３５】
すべての線形空間-時間ブロックコード化伝送方式は式１の形に書くことができる。
例えば、ＢＬＡＳＴ（G．J．Foschini、「Layered space-time architecture for wireless communication in a fading environment when using multi-element antennas」、Bell Labs. Tech. J. vol.１、no.２、pp.４１〜５９、１９９６）は階層構造の信号を送信するために送信アンテナを使用し、従ってｎＴは送信アンテナの数を表し、ｎＲは受信アンテナの数を表し、
【００３６】
【数３】
2007519281.tif 000005
他の例は直交系列（S．M．Alamouti、「A simple transmitter diversity scheme for wireless communications」） 、ＩＥＥＥ  Ｊ．Ｓｅｌ．Ａｒｅａ  Ｃｏｍｍ．pp.１４５１〜１４５８、Oct.１９９８；and V．Tarokh、H．Jafarkhani and A．R．Calderbank、「Space-time block codes from orthogonal designs」、IEEE Trans. Info. Theory., vol.４５、pp.１４５６〜１４６７、July １９９９）and linear dispersive codes B．Hassibi and B．Hochwald、「High-rate codes that are linear in space and time」、IEEE Trans. Info. Theory., vol.４８、pp.１８０４〜１８２４、Jul.２００２）を含み、
【００３７】
【数４】
2007519281.tif 000006
表記を簡略化するため、時間インデックスkを無視し、
【００３８】
【数５】
2007519281.tif 000007
ｘｎ＝［ｘ１ｎ  ・・・ｘｑｎ］                  式３
はｑビットの伝送データ・ビットを持つベクトルで、ｑはシンボル当たりのビットの数である。
【００３９】
【数６】
2007519281.tif 000008
従って、伝送されるビットの（ｑ・ｎＴ）‐長のベクトルは
【００４０】
【数７】
2007519281.tif 000009
【００４１】
【数８】
2007519281.tif 000010
ｎ＝１，・・・，ｎＴ    ｊ＝１，・・・，ｑ
及びＬＥ（・）項は
【００４２】
【数９】
2007519281.tif 000011
によって近似することができる。ここでｘは伝送される可能性のあるビットの系列であり、ｘ［ｎ，j］はその要素ｘｊｎを省略することによって得られたｘの部分ベクトルであり、そしてＬＡ，［ｎ，j］はまたビットに対応する要素ｘｊｎを省略して、全てのＬＡ‐値のベクトルを示す；
【００４３】
【数１０】
2007519281.tif 000012
Ｘｎ，ｊ＋１＝｛ｘ｜ｘｊｎ＝＋１｝
及び
Ｘｎ，ｊ−１＝｛ｘ｜ｘｊｎ＝−１｝
である。
云換えれば、例えば式６の分子における和はビットｘｊｎ＝＋１を持つ全てのシンボルに亘るものである。
【００４４】
【数１１】
2007519281.tif 000013
関数ＬP（・）、ＬＡ（・）及びＬＥ（・）は事後、事前及び外部尤度をそれぞれ表す。事前尤度ＬＡ（・）は、例えば、チャネル符号器からの（例えば、反復ターボ復号における）事前入力から導かれるか、或いはゼロに設定もしくは初期化される（０のログ尤度比Ｌ（・）は＋１及び−１が同確率であることを意味する）。式６は最適の最大事後確率（ＭＡＰ）解であり、そして式７はＭＡＰ解の最大対数近似を提供する（しばしばmax-log‐ＭＡＰ解と呼ばれる）。発明の実施例は式６と式７の両方の解の近似を提供する事ができる。
【００４５】
【数１２】
2007519281.tif 000014
ＡＰＰ判定の計算量はシンボル当たりのビットの数ｑ及び空間‐多重される送信シンボルの数ｎＴと共に指数的に増加する。式６を近似する１つの方法は集合Ｘ＋１及びＸ−１において
【００４６】
【数１３】
2007519281.tif 000015
である候補のみを含めることである。ここで式８ａは事前知識なしであり、式８ｂは事前知識によるものであり、ρはｓｐｈｅｒｅ復号器の限界半径である。
この近似は式８ａ及び８ｂによって定義された範囲外の距離メトリックを提供する候補がＡＰＰ判定への大きな寄与をしないことを仮定している（式６参照）。ｓｐｈｅｒｅ復号アルゴリズムは式８ａか８ｂのいずれかを満たす候補のリストを素早く見出す処理手順を提供する。
【００４７】
また格子復号器（Viterbo及びBoutros、同書）として知られる元のｓｐｈｅｒｅ復号器は最尤推定を提供し、それは実のコンステレーション及びチャネルに関する伝送シンボルの硬出力であり、通信システムを格子として表す。ここで我々は、この元のアイデアに基づいて、複数アンテナ・システムに適した軟入力／軟出力ｓｐｈｅｒｅ復号器の特別な実施例を述べる。
【００４８】
複数アンテナシステムの格子表現を得るために、式１の複素行列表現(時間インデックスkを無視する)は以下の通り元のシステムの2倍の次元で実数の行列表現に変えることができる:
ｒ＝ｓＨ＋ｖ                    式９
ここで
【００４９】
【数１４】
2007519281.tif 000016
我々はｓｐｈｅｒｅ復号器の以下の記述で式９乃至式13の実数表現を使用する。格子理論において使用される専門用語法を使用すると、チャネルＨの実数表現は格子の生成行列であり、チャネル入力（伝送信号）ｓは格子の入力点であり、そして雑音のないチャネル出力項ｓＨは格子点を定義する。
【００５０】
ｎ‐次元格子は（ｎ−１）‐次元格子層に分解することができる。ｎ‐次元格子の探索アルゴリズムは有限個の（ｎ−１）‐次元探索アルゴリズムとして再帰的に記述することができる。Viterbo及びBoutros（同書）は探索の３つの異なる状態、または場合に関して探索アルゴリズムを記述した：
【００５１】
【表１】
2007519281.tif 000017
チャネル行列のＱＲ分解またはコレスキー分解（時折、行列の平方根を取ることを意味する）から導かれる下三角行列ＵＴが格子のための生成行列として使用されれば、探索処理手順は単純化される。例えば、ＱＲ分解が使用されれば（例えば、G．H．Golub and C．F．von Loan、「Matrix Computations」、John Hopkins University Press, １９８３、参照）、下三角行列ＵＴ（及び上三角のＵ）は次のように定義される：
ＵＴＵ＝ＨＴＨ                        式１４
【００５２】
【数１５】
2007519281.tif 000018
さらに探索アルゴリズムによって使用される距離メトリックについて説明するため、我々は生成行列が下三角行列であることをここで仮定する。
【００５３】
【数１６】
2007519281.tif 000019
ｎ＋１次元目の格子探索において距離メトリックは見出されたｎ＋１番目の伝送シンボルによって異なるので、ｎ‐次元目の格子探索において使用される範囲は次のように更新される：
ρｎ２＝ρｎ＋１２−ｄｎ２                式１７
探索アルゴリズムで使用される距離メトリックを述べてきたので、探索される集団シンボルの順序付けについて以下に説明する。距離メトリックは（今、実数値表現を使用して）次のように書くことができる：
【００５４】
【数１７】
2007519281.tif 000020
但し、
【００５５】
【数１８】
2007519281.tif 000021
は伝送シンボルｓの非制約最尤推定値で、またゼロフォーシング解として知られている。従って、式８で与えられた範囲を次のように再定義することができる：
【００５６】
【数１９】
2007519281.tif 000022
例えば、シンボル集団が４ＰＡＭ（Pulse Amplitude Modulation）、即ち、Ｃｒｅａｌ＝｛−３，−１，＋１，＋３｝で、且つｎ番目のレベル探索におけるゼロフォーシング解がｓ”ｎ＝−１．１であれば、探索されるべきシンボルは｛−１，−３，＋１，＋３｝として順序付けされる。この結果、探索上限及び下限の明らかに必要のない計算を回避する事ができる。
【００５７】
【数２０】
2007519281.tif 000023
そして、探索は次の探索階層またはレベルに進む。順序付けは全ての可能な組合せを記憶する索引表を参照する事によって実現することができる。例えば、ｃ×Ｍ行列Φ（但し、ｃ＝２Ｍはシンボル探索組合せの数で、Ｍは可能な信号点の数である）が与えられと、ゼロフォーシング解ｓ"ｎに関する並べ替えベクトル slist はΦのｉ番目の行として次のように与えられる ：
【００５８】
【数２１】
2007519281.tif 000024
広い意味では、この技術はAgrell等（同書）で述べられたSchnorr-Euchner戦略の修正版を含む。
索引表を用いて探索されるシンボルを順序付けする方法は、A．Wiesel、X．Mestre、A．Pages and J．R．Fonollosa、「Efficient Implementation of Sphere Demodulation」、ＩＶ  ＩＥＥＥ Signal Processing Advances in Wireless Communications、pp.５３５、Rome、June15-18,２００３、にさらに詳細に記述され、これによって引用文献として組込まれている。
【００５９】
【数２２】
2007519281.tif 000025
探索半径は雑音及び／またはチャネル状態に応じて設定することができる。軟出力が必要とされるところでは、下で述べられるように、並べ替えアルゴリズムの複雑さが加わることを回避するために、見出された全てのシンボルが軟出力評価に利用される。
【００６０】
要するに、処理手順は３つの主な処理を含む：
ｉ）格子表現への多入力多出力（ＭＩＭＯ）チャネルの変換。
ｉｉ）硬判定の場合には受信信号に最も近い格子点を探索し、そして軟判定の場合には受信信号の周囲の格子点の集合を探索する探索処理手順。軟入力が利用可能なところでは、伝送信号または符号語の事前確率が提供されると、これは探索を補助するために利用することができる（また、例えば、H．Vikalo and B．Hassibi、「Low-Complexity Iterative Detection and Decoding of Multi-Antenna Systems Employing Channel and Space-Time Codes」、Conference Record of the Thirty-Sixth Asilomar Conference on Signals, Systems and Computers, vol.１、Nov. 3-6，２００２、pp.２９４〜２９８、及びH．Vikalo and B．Hassibi、「Towards Closing the Capacity Gap on Multiple Antenna Channels」、ＩＣＡＳＳＰ‘０２、vol.３、pp.ＩＩＩ‐２３８５〜ＩＩＩ‐２３８８、参照）。
ｉｉｉ）軟出力が必要とされるところでは、軟入力及び探索地域において見出された格子点の集合に基づいて軟出力を提供する（これは硬判定ｓｐｈｅｒｅ復号器については不必要である）。
【００６１】
以前に言及されたように、公知のｓｐｈｅｒｅ復号器は、チャネルの統計的性質と使用される空間-時間コードの型に依存して可変の計算量に悩まされるが、計算量は境界を制限されないし、一意に定まらない。しかしながら、探索のために必要とされる多くの距離メトリックdn計算が実際の計算量を決定するので、ここで我々は実行された探索の最大数を設定または制限することにより、ｓｐｈｅｒｅ復号器の計算量を制限する。
【００６２】
そのような手順を実行するｓｐｈｅｒｅ復号器のフローチャートが図３に示される。変更を有する通常のｓｐｈｅｒｅ復号手順に基づく図３において、格子H(F=H-1、ここにFは三角行列である)の生成行列は通信システムの格子表現であり、受信信号はrである(探索手順のための生成行列と同様に前処理される)。手順の出力はsML、symbollistおよびdistlistである。出力sMLは受信信号rに最も近い格子点に対応する格子入力(伝送された信号) であり、最尤解である。出力symbollistは探索領域で発見された格子点に対応する格子入力のリストである。出力distlistはsymbollistでの格子入力に対応する距離メトリックのリストである。
【００６３】
探索領域が探索半径ρ2によって定義される。機能SortedList(en,n)は信号en,nから増加する距離に従って探索されるべき可能なシンボルの順序つけられたリストを提供する。したがってslistnは長さM(slistがN × M行列であるので) のベクトルであり、stepnは1乃至Mのカウントある。記法slistn，IはベクトルslistnのI番目の要素を云う。n次元目の探索におけるゼロフォーシング解はen：=rFにより与えらる。未知の数(推定されるべきシンボルの列の長さ)はNであり(IとQ成分が推定されるべきであることを留意すると、1シンボルあたり2つ未知があるので、未知数は倍増する)、探索される可能なシンボルの数(コンステレーションにおける)はMである。
【００６４】
3つのケース A、B、およびCが上述されたようにある; 概して手順はn=Nを初期化して、すべてが試験されるまで(slistnのすべてのシンボルがn次元目の探索において試験されたとき、examined_allが真になる) slist順序でシンボルを試験し、探索半径ρ2の外側にあるとき一つ上の階層に移動し(ケース C)、ツリー(n= =N)の先端に戻るとき終了する。試験されたケース(A、BまたはC)の総数が試験され、すなわち、決定された距離メトリックdnの数が変数n_searched(開始でゼロに初期化される)によりカウントされ、手順は制限値max_n_searchedを超えるとき止められる。
【００６５】
これは図４に要約され、それは探索(表 1参照) に関する異なった状態または場合にしたがって、3つの異なる処理ブロックに探索手順を分割し、データマルチプレクサーによって確認されるケース A、BまたはCに従って、データを処理A、BまたはCに多重化する。カウントはループの各行程(またはそれぞれの多重化操作)中は保たれ、制限された値に達すると手順は止められる。その制限はあらかじめ設定されてもよいし、アプリケーションまたはデータ伝送速度に従って選択してもよい。各処理ブロック(A、B、C)は、格子点の距離メトリック、または現在どの階層で処理を実施しているのかを評価し、探索の状態を評価して、探索されるべき次の格子点(または層) を選択する。データフローおよび処理ブロックは探索の状態を定義する条件またはケースに従って選択される。したがって、探索の“反復”の最大数は、判定器の実現に必要である値や有効な最大(例えば、予め定められた) 数のフロップ(1秒あたりの浮動小数点演算)、速度またはデータスループット(1秒あたりのデータビット)に従って設定される。探索の数を制限することにより、その結果、ｓｐｈｅｒｅ復号器の計算量は上限が設定される。
【００６６】
概して、発明の実施例において、ｓｐｈｅｒｅ復号器はｓｐｈｅｒｅ復号手順によって実行される探索の最大数を定義することにより、境界を定めたまたは制限された最大複雑さを有する。これはアプリケーションのためまたはアプリケーションから期待されるデータの伝送速度やスループット、または予め定められた計算量(または、フロップ)に従って定義されるべき手順の安定性を提供する。
【００６７】
好ましいｓｐｈｅｒｅ復号器構成のさらなる特徴は以下で説明される。これらの1つ以上が手順を制限する上述の探索と関連して、そうでなければ通常の復号器において別々に実行されるかもしれない。
どんな候補も発見されないなら、すなわち、データシンボルまたはコードは、試験されまたは探索されるべき予め定められた最大数のポイントについて(または探索領域の予め定められたサイズについて)、探索領域で発見されるn次元格子点でないなら、ゼロフォーシング解(または、ＭＭＳＥ解のような別の線形解)が推定されたn次元伝送列シンボルまたは符号語として提供されてもよい。ゼロフォーシング解は、第1の探索によって得られるものであってもいいし、以前に発見されたシンボルの効果が相殺される各探索階層構造において再推定されるゼロフォーシング解であってもよい。この後者の場合では、“相殺”は相殺が‘最も強い'信号から‘最も弱い'信号の順に実行されるかもしれない。この順序付けされたゼロフォーシング解は列並べ替え付きQR分解を使用して格子生成行列を前処理することにより得られるかもしれない(例えば、D.Wubben，R.Bohnke，J.Rinas、V.Kuhn and K.D.Kammeyer「Efficient algorithm for decoding layered space-time codes」IEEE Electronics Letters、vol.37,pp.1348-1350参照、ここに、引用文献として組み込まれる)。ゼロフォーシング解の選択はアプリケーション全体に依存して選択されるかもしれない。
【００６８】
軟出力情報は以下で式23または24に示されるゼロフォーシング解s” (または、別の線形解) から得られるかもしれない。
【００６９】
【数２３】
2007519281.tif 000026
または、Ｍａｘ-Ｌｏｇ-ＭＡＰ近似を使用して:
【００７０】
【数２４】
2007519281.tif 000027
ここに、s”nは式19で与えられるゼロフォーシングベクトルのn番目の要素であり、sはqビット長のビットベクトルxnから写像するシンボル、すなわち、sn=map（xn）である。組Y+1n,jおよびY-1n,jはそれぞれxnj=+1およびxnj=-1を有するビットベクトルxnの２(q-1)通りの集合である。硬判定において、ゼロフォーシングベクトルs”が出力として提供されるかもしれない。
【００７１】
【数２５】
2007519281.tif 000028
シンボル列の少なくとも１つの候補が発見されるところでは、次にビット尤度値(例えば対数尤度比、ＬＬＲ、値)によって構成される軟出力が以下の式27を使用して決定されてもよい。事実上、与えられたビットが+1と-1の値を持っている複数の候補シンボル列上(発見されたところで)で平均されることにより、ビット値が決定されるので、最も尤度が高いビット値が最も尤度が高いシンボル列におけるシンボルに対応するというわけではないことが認識されるであろう。与えられたビットが、式27において分子(または、分母)あるいはゼロに対応している、+1(または、-1)の値を持って発見されるどんな候補列もないとき、このアプローチに困難があることが認識されるであろう。この困難は以下で説明されるように処理することができる。
【００７２】
それぞれビットxnj=+1およびxnj=-1を含む候補に対応しているいずれかのリストL+1またはL-1が空で発見された場合について、デフォルトＬＬＲ値が他の非空リストおよび/またはその距離メトリックにおいて発見されたシンボルの数に従って与えられる。例えば、L-1が空であり、リストL+1で発見された最小距離メトリックがd2minであるなら、付随的なＬＬＲが以下の通り近似される。
【００７３】
【数２６】
2007519281.tif 000029
代わりに、非空リストが候補のかなり大きい数(即ち閾値数よりも大きい)を持っていて、発見されていない候補が大きい距離メトリックを有すると仮定されるならば(探索の距離メトリックの最大許容数が計算してあるので)、デフォルト最大ＬＬＲ値LMAXが提供されるかもしれない。例えば、
【００７４】
【数２７】
2007519281.tif 000030
硬判定の場合では、デフォルトＬＬＲ値は式26でLMAX=１と決定されるかもしれない。デフォルトＬＬＲ値がいかに評価されるのかの選択は総合的なシステム設計に依存する。
我々は次に探索戦略を説明する。式8に示されるように、受信信号または出力空間でｓｐｈｅｒｅ半径によって定義される特定の球体探索領域に関して、伝送信号または入力空間に対応する探索規制がある。発明の実施例では、探索規制の下限および上限の明白な計算は、第n次元における第１の探索層が入力空間のゼロフォーシング解の第n要素であるように探索される層を順序付けることにより回避される。その後の探索は、探索されるべき層の順序が入力空間のゼロフォーシング解から距離を増加するようにするのが望ましい。探索される第n次元層が受信信号に関してｓｐｈｅｒｅ半径より大きい累積距離メトリックを有するとき、探索された第n層は現在の探索階層構造の入力境界と考えられ、格子探索は次の探索階層構造で実行される。
【００７５】
ここでビット確率値に話を変えると、ｓｐｈｅｒｅ復号器の探索手順から得られる距離メトリックは、復号器から軟出力を提供する軟出力情報計算ブロックに渡され利用されるかもしれない。再び式6を思い出して、受信されたチャネルベクトルrを条件とする復号されたまたは検出されたビットxnjの事後ＬＬＲに関する軟出力は、以下のように推定されることができる:
【００７６】
【数２８】
2007519281.tif 000031
ここに、sはビットベクトルxの空間-時間シンボルであり、HはＭＩＭＯチャネル行列であり、項σ2は実成分あたりの雑音分散であり、L+1はビットxnj=+1を含んでいる要素に対して探索手順で発見されたシンボルのリストに対応するビットベクトルxの集合であり、x[n,j]はビットxnjを省略することにより得られるxのサブベクトルを表し、LA,[n,j]はまたxnjのＬＬＲを表す要素を省略してすべての事前ＬＬＲLAのベクトルを表す。
【００７７】
雑音の分散は、総合的なシステム設計に依存して、任意の便利な方法で得られるかもしれない。例えば、雑音分散はチャネルインパルス応答が推定されるところでトレーニング期間中得られるかもしれない。トレーニング期間中、伝送シンボル系列は既知である。推定されたチャネルインパルス応答と共に、“雑音のない”受信信号が得られる。雑音分散は、“雑音のない”受信信号の系列を知っている、“トレーニング期間”中に受信された信号の系列の雑音統計値を評価することから推定されるかもしれない。
【００７８】
項dx2はビットベクトルxの空間-時間シンボル写像から得られるシンボルsに対応している探索アルゴリズムから得られる距離メトリックである。事前ＬＬＲLAはｓｐｈｅｒｅ復号器への軟入力から得られるかもしれない。項LEは外部ＬＬＲである。事前ＬＬＲLAはチャネル復号器または別の空間-時間復号器などの外部の構成要素から得られる。また、事前ＬＬＲLAは反復復号構造が採用されるなら、前の反復の復号からの外部ＬＬＲLEであるかもしれない。軟出力が事後または外部ＬＬＲのいずれから提供されるかはアプリケーションに依存する。
【００７９】
式27における和の対数の計算は従来のヤコビアン（Jacobian）対数関係(また“sam-log”近似として知られている（例えば、P．Robertson,E.Villebrun and P.Hoher, 「A comparison of optimal and sub-optimal MAP decoding algorithm operating in the log domain」）、in IEEE Intern.Conf.On Commun.1995 pp.1009-1013)、または“最大-ログ”近似によって近似されることができる。前に議論したように、リストL+1およびL-1の１つまたは両方が空であると発見され、またはどんなシンボルもxnj=+1および/またはxnj=-1に対応して発見されない場合について、デフォルトＬＬＲ値は他の非空リストの中で発見されたシンボルの数に従って与えられるかもしれない。両方のリストが空であるならば、ソフトゼロフォーシング解の軟出力に基づく通常のＬＬＲ値が提供されるかもしれない。
【００８０】
リストL+1およびL-1の占有(即ち、+1/-1の与えられたビットの値を持っている発見された数の候補解(格子点))に対応して式27、式23/24または式25/26に基づく復号器からの出力の選択は、図5のフローチャートで要約される。
図5に示されるように、ｓｐｈｅｒｅ復号アルゴリズムが受信信号に対する最も近い格子点に達したことが知られる前に(我々は、例えば上述された(部分的な)ツリーが完成されるのでこれが到達された時を知る)、ｓｐｈｅｒｅ復号アルゴリズムが止められるならば、ここまでに発見された最も近いポイントは実際に最も近いかもしれないし、そうでないかもしれない。これは図5の判定ボックスの左側のブランチである。この場合、図5に示されたものに代替があり、それは例えばゼロフォーシング(ZF)解、またはデフォルト値を使用するなどの、解を決定するためにそれほど複雑でない線形判定器を使用することである。
【００８１】
前述したように、探索領域の範囲を定義しているｓｐｈｅｒｅ半径が発見された候補または受信信号に近い格子点から得られた軟出力の信頼性を決定する。ｓｐｈｅｒｅ半径は、図6に示されるＡＰＰ検出にかなり貢献する格子点の候補のリストを得るために固定値に設定することもでき、または例えば受信状態に応答してｓｐｈｅｒｅ半径が調整されることもできる。しかしながら、硬判定出力に関しては、ｓｐｈｅｒｅ半径は、最後に見つけられた格子点と受信信号の距離に減少してもよい。
【００８２】
図６は上述された方法の処理手順の実施例を実施するために構成された復号器を組込んだ受信機３００を示す。
受信機３００は１以上の受信アンテナ３０２ａ、ｂ（例示の実施例にはその２つが示されている）を含み、各々はそれぞれのＲＦフロントエンド（高周波前置部）３０４ａ、ｂに接続され、そこからそれぞれのアナログ・ディジタル変換器３０６ａ、ｂ及びディジタル信号プロセッサ（ＤＳＰ）３０８に接続されている。ＤＳＰ３０８は一般的に１以上のプロセッサ３０８ａ及び作業用メモリ３０８ｂを含むであろう。ＤＳＰ３０８はデータ出力３１０、及びＤＳＰをフラッシュＲＡＭまたはＲＯＭといった永久的プログラム・メモリ３１４に接続するアドレス、データ及び制御バス３１２を持っている。永久的プログラム・メモリ３１４はＤＳＰ３０８のためにコード及び随意的にデータ構造或いはデータ構造定義を記憶する。
【００８３】
例示されたように、プログラム・メモリ３１４は上述された機能に対応する実施をＤＳＰ３０８で実行するとき、格子生成コード（行列チャネル推定値からの）、ゼロフォーシング推定コード、ツリー形成／探索コード、反復制限コード及び、軟出力復号器のためにソフト情報評価コードを含むｓｐｈｅｒｅ復号器コード３１４ａを含む。また、プログラムメモリ３１４はＭＩＭＯチャネル推定値Ｈを提供するＭＩＭＯチャネル推定コード３１４ｂ、及び、随意的に、デインタリーブ器コード３１４ｃ、インタリーブ器コード３１４ｄ、チャネル復号器コード３１４ｅを含む。デインタリーブ器コード、インタリーブ器コード、及びチャネル復号器コードの実装は当業者には周知である。随意的に、永久的プログラム・メモリ３１４内のコードは光学もしくは電気信号担体または、図6に例示されたように、フロッピ・ディスク３１６といった担体上で提供される。
【００８４】
ＤＳＰ３０８からのデータ出力３１０は要望どおりさらに受信機３００（図6には示されてない）のデータ処理要素に提供される。これらは高レベルのプロトコルを実施するためのベースバンド・データ・プロセッサである。
受信機の前置部（front-end）は一般にハードウェアに実装され、一方、１以上のＡＳＩＣ及び／またはＦＰＧＡもまた使用されるが、受信機処理は少なくとも部分的にソフトウェアに実装される。受信機の全ての機能はハードウェアにおいて行うことができること、及び信号がソフトウェア無線機においてディジタル化される厳密な採点基準は一般に費用／複雑さ／電力消費の取捨選択によって決まることを当業者は認識するであろう。
【００８５】
他の実施例では、復号器は、例えば軟入力／軟出力空間‐時間復号器を実装する信号処理モジュールとして提供される。
概要では、発明の実施例は、図3および4に示されるようにデータフローにおいて反復の最大数を定義することにより、即ち、可能な伝送シンボルの候補を位置付けるために実行される探索の数を制限することにより、計算量の上限を定められた方式を実施する。探索アルゴリズムは、3つの異なったケースまたは探索の状態に関連している3つの部分処理(または、処理ブロック)に分解されることができる。それぞれの処理ブロックは、格子点の距離メトリックまたは処理を実行している階層がどの階層なのかを評価し、探索の状態を評価し、探索されるべき次の格子点または層を選択する。データフローおよび処理ブロックは探索の状態を定義する条件またはケースに従って選択される(表１参照)。反復/探索の最大数に到達している探索手順によっても何ら格子点が発見されない(十分な候補が発見されない)とき、または探索境界内に格子点がないとき、ゼロフォーシング解のような線形解がデフォルト判定シンボルまたは符号語として提供されるかもしれない。軟判定のため、軟出力がソフトゼロフォーシング解の軟出力から得られる。リストL+1およびL-1のどちらか1つが空であると発見される場合について、デフォルトＬＬＲ値が、例えば他の非空リストおよび/またはその距離メトリックにおいて発見されたシンボルの数に従って提供される。これらのリストの両方が母集団にあるところでは、探索領域で発見される格子点の1つ以上の記憶された距離メトリックが、軟出力ビット確率を評価する処理に渡される。
【００８６】
図7は連接チャネル符号器を持つ送信機のブロック図を示す；周波数選択性チャネルは「符号器」であると考えることができる。図7において、符号器２は従来のチャネル符号器を含み、符号器１はチャネルと組合わされたＳＴＢＣ符号器である。
図8は図7の送信機と共に使用するのに適した、連接チャネル復号器及び判定器を持つ受信機のブロック図を示す。図8において、判定器または復号器１は上述の空間-時間ｓｐｈｅｒｅ復号器を含み、復号器２は従来のチャネル復号器を含む。図9は反復または「ターボ（turbo）」復号を用いる連接復号器または判定器をもつ、図8の受信機の変形ブロック図を示す。図10は復号器１の２つの場合を含む受信機のブロック図を示し、それは、例えば、空間‐時間復号器を含む。図10において、１つの復号器の出力は他の復号器に関する事前知識を提供する。このように、復号器構成要素は判定データの信頼性を向上させるために反復して有効にそれ自身とソフト情報を交換する。受信信号は双方の復号器に提供され、随意的に（送信機のインタリーブ配置に応じて）１つの場合ではインタリーブされる。
【００８７】
図11は４×４  １６ＱＡＭ（Quadrature Amplitude Modulation）ＭＩＭＯシステムについて、受信アンテナ当たりの信号対雑音比（ｄＢ）に対するコード化および非コード化ＢＥＲ（ビット誤り率）を示し、無相関フラットレイリーフェージング（Rayleigh-faded）チャネル状態のもとで、非コード化（曲線800，802，804，806）およびコード化（曲線801，803，805，807）伝送信号について、上述のようにさまざまな回路に計算反復を制限したようなｓｐｈｅｒｅ復号器(曲線802乃至807)、最尤（ML）検出器（曲線800，801）の特性を示している。結果は500データブロックのシミュレーションで得られ、ｓｐｈｅｒｅ復号器は250(曲線802，803)、500(曲線804，805)、および1000(曲線806，807)回の距離メトリックの計算にそれぞれ制限されている。２乗されたｓｐｈｅｒｅ半径の値は以下に等しかった：
5×(雑音分散)×(受信アンテナの数)/(送信アンテナ当たりの平均信号電力)
ＭＬ判定器は受信シンボルあたり8×16４=524288距離メトリックの測定を必要とし、その結果、250、500、および1000回の計算を行うｓｐｈｅｒｅ復号器が少なくともそれぞれおよそ1/2000、1/1000および1/500に計算量を削減している。
【００８８】
上述された技術は、我々がmax-log-MAPｓｐｈｅｒｅ復号器と称したものに適用することができる。それは、出願人の審査中の英国特許出願no．0323211.3  、2003年10月3日出願（およびこの英国出願から優先権主張した対応出願もまた）に記述され、その内容は、特に、その文献の式11のｓｐｈｅｒｅ復号器評価に関する制限を提供するため、ここにそれらの全体を引用文献として組み込んでいる。
【００８９】
発明の実施例は、例えば、無線のコンピュータまたは電話ネットワークのためのＭＩＭＯおよび多ユーザシステムを含む、多くの型の通信システムの応用を有する。多ユーザ・システムでは、例えば生成行列、または等価的なチャネル行列はユーザに関する拡散及びチャネル効果の組合せを表す（例えば、ここに引用文献として組込まれているL．Brunel、「Optimum Multiuser Detection for MC-CDMA Systems Using Sphere Decoding」、12th IEEE International Symposium on Personal, Indoor and Mobile Radio Communications、volume１、30  Sept．-3  Oct．２００１  pagesＡ１６〜Ａ２０参照）。
【００９０】
いくつかの応用において、復号器は周波数選択性フェージングのためのブロック等化器として用いられることができる。ここで、式9のチャネル・モデルは下に示すようにチャネル・メモリを考慮するように修正される： 
【００９１】
【数２９】
2007519281.tif 000032
及びＴは等化されるシンボル・ブロックの長さ、Ｈｉ，ｉ＝１，・・・，Ｌはｉ番目のＭＩＭＯチャネル・タップであり、ここにLはチャネルインパルス応答(シンボル期間における)の最大長さの推定値である。
【００９２】
【数３０】
2007519281.tif 000033
本発明の実施例はチャネル符号器が線形生成行列Ｇによって表されるところでチャネル復号器として適用することができる。その例は、符号語ｘがｘ＝ｓＧを通して情報ビットｓから生成行列Ｇによって生成され、ベクトルｓが情報ビットを含むところのハミング符号（Hamming code）及び低密度パリティ検査（Low Density Parity Check：ＬＤＰＣ）符号化といったブロックチャネル符号である（「Digital Communications: Fundamentals and Applications、Bernard  Sklar、Prentice Hall International Editions、１９９９、０‐１３‐２１２７１３‐Ｘ」、参照）。ＬＤＰＣについて、例えば、生成行列Ｇは直交条件ＧＨＴ＝０を満たすパリティ検査行列Ｈから得られ、或る正当な符号語はｘＨＴ＝０を満足させるであろう。ここで、情報及び符号語ブロック、ｓ及びｘ、それぞれは２進数、即ち１及び０から成り、行列演算は２値領域にある。
【００９３】
発明の実施例は式7に基づいて最尤符号語または軟出力を提供する。例示的実施例において、入力rを用いかつ生成行列としてＧを使用しているｓｐｈｅｒｅ復号器は受信信号rとその探索における可能な伝送符号語の各々との間の距離を決定する。最小距離を有する符号語は最尤符号語である。これは２進分野｛０，１｝から符号化値｛-1，+1｝へ情報および符号語ブロックの翻訳を採用し、したがって数学演算が使用される。
【００９４】
一般に、上記ｓｐｈｅｒｅ復号技術の実施例は(望ましくは線形) 生成行列によって表現可能な任意のシステムに適用することができる。
当業者は、上述の技術が例えば、基地局、アクセスポイントおよび/または移動体端末で使われるかもしれないことを認識するであろう。概して発明の実施例は、性能の損失なく安価な受信機を、または対応して増加する複雑さと費用の増加を伴わずデータ伝送速度の向上を容易にする。発明の実施例はまた、非無線システム、例えば、事実上多重送信機のように作動する多重読取りヘッドと多重データ記録層を有するディスクドライブに、潜在的に応用を見出すかもしれない。
【００９５】
勿論、他の多くの効果的な選択肢が当業者には頭に浮かぶであろう。本発明が記述された実施例に限定されず、これに関して付加された請求項の精神及び範囲内にある当業者に明白な修正を包含することは理解されるであろう。
【図面の簡単な説明】
【００９６】
【図１】ｓｐｈｅｒｅ復号器を用いたＭＩＭＯ空間‐時間コード化通信システムの例を示す。
【図２】ｓｐｈｅｒｅ復号器のツリー探索の図解例示を示す。
【図３】本発明の態様を具体化するｓｐｈｅｒｅ復号手順のフローチャートである。
【図４】図３の手順の概観図である。
【図５】本発明の態様の実施例に従ったｓｐｈｅｒｅ復号後処理手順のフローチャートを示す。
【図６】本発明の実施例に従って作動するように構成されたｓｐｈｅｒｅ復号器を組み込む受信機に示す。
【図７】連接符号化器を用いた送信機のブロックダイアグラムを示す。
【図８】図７の送信機とともに使用するための連接復号器を有する受信機のブロックダイアグラムを示す。
【図９】図７の送信機とともに使用する連接復号器および反復復号を有する受信機のブロックダイアグラムを示す。
【図１０】２つの等価復号器の間の反復フィードバックを採用している受信機のブロックダイアグラムを示す。
【図１１】本発明に従った復号器の実施例をチャネルコードのあるなしにかかわらず信号のために復号する最大の事後確率(MAP)と比較して、受信された信号対雑音比に対してビット誤り率を示す。
【図１】
2007519281.tif 000034
【図２】
2007519281.tif 000035
【図４】
2007519281.tif 000036
【図３】
2007519281.tif 000037
【図５】
2007519281.tif 000038
【図６】
2007519281.tif 000039
【図７】
2007519281.tif 000040
【図８】
2007519281.tif 000041
【図９】
2007519281.tif 000042
【図１０】
2007519281.tif 000043
【図１１】
2007519281.tif 000044
【国際調査報告】
2007519281.tif 000045
2007519281.tif 000046