(57)【要約】      （修正有）【課題】受信機で使用するためのシンボル検出器の提供。【解決手段】シンボルベースの通信システムは、システム内の受信機におけるシンボル検出を含む。このシンボル検出は、受信データの系列上に存在するであろうシンボルの集合を決定する。この役割を完了するために提供されるシンボル検出器は、隠れマルコフモデル状態トレリス内の状態確率を決定するために、低減されたアクティブ状態の集合に基づいて、前方後方再帰手段を実行させる手段を含む。前記シンボル検出手段は、低減状態前方再帰の実施のために利用可能な状態の集合に関連付けられた低減された前方メッセージの集合を決定するように動作する前方メッセージ決定手段と、前記低減状態後方再帰の実施のために後方メッセージ決定手段に関連付けられた低減された後方メッセージの集合を決定するように、前記前方メッセージ決定手段とは独立して動作する後方メッセージ決定手段とを更に備えている。【選択図】図２
2006340373.tif 000002
【特許請求の範囲】
【請求項１】
通信システムで使用される受信機であって、
前記受信機は、受信データの系列上で存在するであろうシンボルの集合を決定するように動作するシンボル検出手段を含み、前記シンボル検出手段は、隠れマルコフモデル状態トレリスの状態確率を決定するように動作する低減状態前方後方再帰手段を含み、更に前記シンボル検出手段は、低減状態前方再帰の実施のために利用可能な状態の集合に関連付けられた低減された前方メッセージの集合を決定するように動作する前方メッセージ決定手段と、低減状態後方再帰の実施のための後方メッセージ決定手段に関連付けられた低減された後方メッセージの集合を決定するように、前記前方メッセージ決定手段と独立して動作する後方メッセージ決定手段と
を備えた受信機。
【請求項２】
請求項１に記載の受信機において、
前記シンボル検出手段は、前記前方メッセージ決定手段、および前記後方メッセージ決定手段によって使用されるために、アクティブ状態の集合を決定するよう動作するアクティブ状態選択手段を含んでいる受信機。
【請求項３】
請求項２に記載の受信機において、
前記アクティブ状態選択手段は、前記状態変数の周辺事後分布の近似に基づいて、隠れマルコフモデルのアクティブ状態の集合を選択するように動作する受信機。
【請求項４】
請求項２又は請求項３に記載の受信機において、
前記アクティブ状態選択手段は、非アクティブ状態を、予め定めた値に設定するよう動作する受信機。
【請求項５】
請求項４に記載の受信機において、
前記アクティブ状態選択手段は、非アクティブ状態を、予め定めた零ではない値に設定するよう動作する受信機。
【請求項６】
請求項１乃至５のうち何れか１項に記載の受信機において、
前記低減状態前方後方再帰手段は、準ＢＣＪＲ再帰処理に従って動作する受信機。
【請求項７】
通信チャンネルによる送信から受信されるデータ系列上のシンボルを検出する方法であって、
前記方法は、受信データの系列上に存在するであろうシンボルの集合に帰結し、
前記方法は、低減状態前方後方再帰処理を適用して、隠れマルコフモデル状態トレリス中の状態確率を決定することを含み、
前記方法は、前記低減状態前方再帰の実施のために利用可能な状態の集合に関連付けられた低減された前方メッセージの集合を決定することと、低減された前方メッセージの集合を決定するステップと独立して、前記低減状態後方再帰の実施のために後方メッセージ決定手段に関連付けられた低減された後方メッセージの集合を決定することとを含む方法。
【請求項８】
請求項７に記載の方法において、
低減された前方メッセージの集合を決定するステップにおいて使用するため、また、低減された後方メッセージの集合を決定するステップにおいて使用するためにアクティブ状態の集合を選択することを含む方法。
【請求項９】
請求項８に記載の方法において、
前記アクティブ状態の集合を選択するステップは、前記状態変数の周辺事後分布の近似に基づいて行われる方法。
【請求項１０】
請求項８又は請求項９に記載の方法において、
アクティブ状態として選択されなかった状態を、予め定めた値に設定するステップを含む方法。
【請求項１１】
請求項１０に記載の方法において、前記予め定めた値は、零ではない方法。
【請求項１２】
通信システムにおいて受信機内で使用されるシンボル検出器であって、
前記シンボル検出器は、受信データの系列上で存在するであろうシンボルの集合を決定するように動作し、
前記シンボル検出手段は、
隠れマルコフモデル状態トレリスにおける状態確率を決定するように動作する低減状態前方後方再帰手段を含み、更に、低減状態前方再帰の実施のために利用可能な状態の集合に関連付けられた低減された前方メッセージの集合を決定するように動作する前方メッセージ決定手段と、
低減状態後方再帰の実施のために後方メッセージ決定手段に関連付けられた低減された後方メッセージの集合を決定するように、前記前方メッセージ決定手段とは独立して動作する後方メッセージ決定手段と
を備えたシンボル検出器。
【請求項１３】
コンピューター実行可能な命令を与えるコンピュータプログラム製品であって、
前記命令は、コンピューターによって実行された時、前記コンピューターが、請求項７乃至１１のうちの何れか１項に記載の方法を実行するように設定されるコンピュータプログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、無線通信に関し、特に、無線通信チャネルによって送信された信号の復号に関する。ここでは、復号はＢＣＪＲ手順の変形を用いたシンボルトレリスに基づいて実行される。
【背景技術】
【０００２】
トレリスダイヤグラムは、データエンコーダの状態を表す、時間によりインデクスされた状態の集合からなる系列と、符号化されたデータを表す状態間の遷移とを含む。したがって、トレリスは、受信機において無線チャネルによる送信から受信された符号化データを検出する処理を支援する代表的なツールである。
【０００３】
反復して復号処理を改善するための演繹的な情報としてそのようなソフト情報を使用することができるので、トレリスデコーダは、一般に(しかし必ずしも必要ではないが)データシンボル（遷移）、あるいは個々のトレリス状態の可能性についての情報を提供する。
【０００４】
直接それらを測定することができないか、受信データとして取り扱うことができないという意味で、これらの状態は隠されている。観測データに基づいて、様々なトレリス段階における状態の中で最も有望なアイデンティティーを決定することがシンボル検出の目的である。内在する隠れマルコフモデルを表わすトレリスダイヤグラムは、この処理への適切なアプローチを提供する。
【０００５】
離散確率変数（ｄ．ｒ．ｖ）Ｘｔは、隠れマルコフモデルにおける「状態変数」である。これは、それがシステムの観測された変数ではないことを意味する。図１は、一例として、状態変数Ｘｔに関する単純な確率分布を示す。この例において、変数Ｘｔの配置空間又は領域は集合
【数１】
2006340373.tif 000003
【０００６】
である。
【０００７】
したがって、離散確率変数Ｘｔの状態は、Ｘｔの取りうる配置、すなわち
【数２】
2006340373.tif 000004
【０００８】
のうちの１つである。
【０００９】
さらに、この分布の「サポート」は、零ではない確率、すなわち
【数３】
2006340373.tif 000005
【００１０】
を持つ状態Ｘｔの集合である。図１に示された一例において、分布のサポートは集合
【数４】
2006340373.tif 000006
【００１１】
である。
【００１２】
状態の集合は、Ｘｔの領域で定義されうる。状態の集合は、Ｘｔの領域からの要素の集合である。例えば、
【数５】
2006340373.tif 000007
【００１３】
は、この場合における状態の集合である。
【００１４】
その他のある変数の実現について分布を調整することは可能である。しかしながら、調整された分布が、オリジナルの変数に関する分布のままであることに注目することは重要である。例えば、
【数６】
2006340373.tif 000008
【００１５】
は、まだＸｔに関する分布である。
【００１６】
ほとんどの無線アプリケーションでは、チャネルコーデックが、受信機の性能を改善するために使用される。したがって、ほとんどの受信機、特に反復型受信機の場合、軟値出力検出器／デコーダ／等化器が、チャネルデコーダに軟値入力を供給するために必要とされる。メモリを備えたエンコーダについて、ＢＣＪＲアルゴリズム (L. Bahl, J. Cocke, F. Jelinek and J. Raviv, "Optimal decoding of linear codes for minimizing symbol error rate," IEEE Trans. Information Theory, vol. 20, pp. 284-287, March 1974)（非特許文献１）は、最適のトレリスベースのデコーダ／検出器である。（発明者にちなんで命名された）ＢＣＪＲ手順は、マルコフデータを仮定したトレリス復号を提供する（ここでは、状態の進展は、過去の状態ではなく、現在の状態に依存する）。
【００１７】
ＢＣＪＲアルゴリズムは、特定の観測シーケンスを仮定すると、隠れマルコフモデル（ＨＭＭ：hidden Markov model）における連続状態のペアと、状態の周辺事後分布を計算するために一般に使用される。周波数選択チャネルの最適な等化及び最適なチャネル復号のような通信における多くの問題は、これらの周辺事後分布の計算として定式化することができるので、ＢＣＪＲアルゴリズムは、使用のための広い範囲を持っている。
【００１８】
一例として、チャネルメモリがＬである場合、単一の送信アンテナと単一の受信アンテナとの間のチャネルを介した無線通信を整えるシステムが説明される。ｄ番目のチャネルタップのフェージング係数は、ｄ∈［０，Ｌ］の場合ｈ（ｄ）と示される。ｔ番目の時間インスタンスにおける受信信号および送信アンテナシンボルは、それぞれｙｔ及びｂｔによって示される。
【００１９】
この場合、シンボルｂｔは、基数Ｎである集合Ｂ＝｛ａ１，ａ２，・・・，ａＮ｝から選択される。受信信号ｙｔは、チャネルインパルス応答と、Ｌ＋１の時間インスタンスまで送信されたシンボルの系列との畳み込み、及び加えられたホワイトガウシアンノイズｗｔからなる。
【数７】
2006340373.tif 000009
【００２０】
便宜上、表記Ａｔ：ｔ’は、ｔ≦ｔ’の場合、時間ｔからｔ’までの幾つかの時間インデクスされた変数の系列を参照するために使用される。すなわち、Ａｔ：ｔ’＝｛Ａｔ，・・・，Ａｔ’｝である。Ｔ個のシンボルのフレーム送信を仮定すると、このシナリオにおける最適な等化器のタスクは、受信信号系列Ｘ１：Ｔを考慮し、ｔ∈｛１，・・・，Ｔ｝の場合におけるｐ（ｂｔ｜ｙ１：Ｔ）を最大にする送信シンボルｂｔを検出することである。
【００２１】
今、
【数８】
2006340373.tif 000010
【００２２】
によってベクトル転置演算を表すと、状態変数は、時間ｔにおいて、等化器のために
【数９】
2006340373.tif 000011
【００２３】
のように定義される。
【００２４】
したがって、各Ｘｔは、基数｜ＳＸ｜である集合ＳＸ＝ＢＬから値をとる。この基数は、ある状況では、｜ＳＸ｜以外かもしれないことが認識されるであろう。状態変数系列Ｘ０：Ｔ（ここで、Ｘ０は、等化器の初期状態を示す）は、ｐ（ｙｔ｜Ｘ１：ｔ）＝ｐ（ｙｔ｜Ｘｔ−１，Ｘｔ）からなる条件付き独立性を備えたマルコフチェーンを形成する。したがって、関連する変数は、隠れマルコフモデルによって表わすことができる。さらに、送信シンボルｐ（ｂｔ｜ｙ１：Ｔ）の周辺事後分布も、ｐ（Ｘｔ−１，Ｘｔ｜ｙ１：Ｔ）からなる分布から直接導出されることが分かる。
【００２５】
したがって、最適な等化の問題は、ＨＭＭの連続状態のペアからなる周辺事後分布の効率的な計算の問題として定式化することができる。したがって、ＢＣＪＲアルゴリズムは、最適解を得るために以下のように適用することができる。
【００２６】
ＢＣＪＲアルゴリズムは、状態変数系列Ｘ０：Ｔの可能性によって形成されたトレリスによる前方及び後方再帰を含む。前方再帰では、以下のような再帰計算が、各ｔ∈｛１，・・・，Ｔ｝と、各Ｘｔ∈ＳＸについて行われる。
【数１０】
2006340373.tif 000012
【００２７】
ここで、
【数１１】
2006340373.tif 000013
【００２８】
である。
【００２９】
後方再帰では、以下のような再帰計算が、各ｔ∈｛１，・・・，Ｔ｝と、各Ｘｔ∈ＳＸについて行われる。
【数１２】
2006340373.tif 000014
【００３０】
α（Ｘｔ）とβ（Ｘｔ）とは、これら２つの再帰で反映されたメッセージと考えられることに留意されたい。最後に、状態変数の事後確率、及び連続状態変数のペアは、全てのＸｔ−１，Ｘｔ∈ＳＸ及びｔ∈｛１，・・・，Ｔ｝について、
【数１３】
2006340373.tif 000015
【００３１】
によって評価することができる。これから、特定の例に対する送信シンボルの周辺事後分布は、
【数１４】
2006340373.tif 000016
【００３２】
のように計算することができる。ここで、集合
【数１５】
2006340373.tif 000017
【００３３】
は、シンボルｂｔの送信となる（Ｘｔ−１，Ｘｔ）のペアの集合を表し、Ｚｔは、規格化定数である。
【００３４】
上に述べられた事後確率の規格化は、ＨＭＭの連続状態変数のペアと、状態変数の適切な周辺事後分布を提供するであろうことも理解されよう。決定的なＢＣＪＲアルゴリズムは、離散的な状態空間を備えた隠れマルコフチェーンの仮定の下における最大の事後状態推定のための効率的かつ最適なアルゴリズムである。それは、トレリス段階を経由して後方再帰が続く各トレリス段落（連続した時間インスタントに対応する連続トレリス段階）を経由した前方再帰によるシステムのトレリス表現を解決する。これは後でより詳細に記述される。しかしながら、多くのアプリケーションでは、特定のトレリス段階における状態のアイデンティティーは多くの可能性から来ているかもしれない。このアルゴリズムの複雑さは時間Ｔで線形であるが、さらにまた｜ＳＸ｜に関連している。この状態の改善するために、ＢＣＪＲアルゴリズムの低減状態バージョンがしばしば使用される。これによって再帰計算は、｜ＳＸ｜にそれほど依存しなくする。
【００３５】
「純粋な」又は決定的なＢＣＪＲアルゴリズムは、例えばブロードバンドシステム又はＭＩＭＯシステムのような大規模なトレリスによって代表されるシステムでは、相当な計算コストがかかるため、現実的な実装のためには、複雑さを低減したバリエーションが使用される。すでに複雑さを低減した様々なアルゴリズムが提案されたり実装されており、これらは、計算上の複雑さを低減するための状態低減処理を含んでいる。これらはいわゆる状態数を低減したＢＣＪＲアルゴリズムであり、Ｍ−ＢＣＪＲおよびＴ−ＢＣＪＲアルゴリズムを含んでいる。
【００３６】
これらのアルゴリズムは、ＢＣＪＲアルゴリズムに類似した前方再帰及び後方再帰を持っており、同様の計算が行なわれる。しかしながら、前方再帰では、アクティブ状態の集合が、前方メッセージのサポートとして、各時間インスタンスで選択される。アクティブ状態は、前方メッセージα（Ｘｔ）それ自身の計算可能な近似によって選択される。
【００３７】
Ｍ−ＢＣＪＲアルゴリズムはV. Franz及びJ.B. Andersonによる"Concatenated decoding with a reduced-search BCJR algorithm," (IEEE Journal on Selected Areas in Commun., vol. 16, pp. 186-195, Feb 1998)（非特許文献２）に記載されている。これは、各トレリス段階において、Ｍ個の状態のみ（トレリス状態の完全な集合からなるサブセット）について、ＢＣＪＲアルゴリズムで再帰計算が行われる。このＭ個の状態は、ＢＣＪＲアルゴリズムの判定基準に基づいて選択される。より詳しくは、時間ｔにおいて、大きな前方再帰パラメーターαｔを持つＭ個の状態を選択する。システムのメモリが小さい場合（つまり、チャネルインパルス応答が短い場合）、このＭ−ＢＣＪＲアルゴリズムは良好に実行可能であるが、メモリが増加する場合、良好には実行せず、著者は、このアプローチが「不成功である」と結論付ける。同じ論文（Ｔ−ＢＣＪＲ）で記述された代替アプローチでは、閾値よりも大きな前方再帰パラメーターαｔを持つ状態のみが選択されるが、しかし、著者は、このアプローチは、計算量が大きく変わるというデメリットがあると言及する。これは、特定のアプリケーション、特に最大サイクルレートを持つハードウェア実装において困難であることを示す。
【００３８】
時間インスタンスｔにおいて選択されたアクティブ状態の集合は、Ωｔによって示され、時間ｔのアクティブ状態であると主張される状態の集合は、
【数１６】
2006340373.tif 000018
【００３９】
によって示される。Ωｔ−１が選択され、時間ｔ−１に対応する前方メッセージが
【数１７】
2006340373.tif 000019
【００４０】
である場合、時間インスタンスｔにおけるＭおよびＴ−ＢＣＪＲアルゴリズムの前方再帰について説明する。以下の解析では、関連する量の最終的な近似をチルダ記号
【数１８】
2006340373.tif 000020
【００４１】
を用いることにより示す。
【００４２】
第１に、（集合
【数１９】
2006340373.tif 000021
【００４３】
内の状態について）時間ｔにおける暫定的な前方メッセージは、次のように計算される。
【数２０】
2006340373.tif 000022
【００４４】
集合
【数２１】
2006340373.tif 000023
【００４５】
は、Ｘｔ−１∈Ωｔ−１の場合、γ（Ｘｔ−１，Ｘｔ）のＸｔにおけるサポートの単位である。図２は、この例の等化器トレリスのセクションを示す（トレリスダイヤグラムは、状態変数の配列空間を垂直に示す）。これは集合Ωｔ−１及び
【数２２】
2006340373.tif 000024
【００４６】
を示す。
【００４７】
さて、Ｍ−ＢＣＪＲアルゴリズムは、
【数２３】
2006340373.tif 000025
【００４８】
のうちの大きなＭ個の値に基づいて、
【数２４】
2006340373.tif 000026
【００４９】
からＭ個の状態を選択する。これは、Ωｔにおける対応する状態を含んでいる。対照的に、Ｔ−ＢＣＪＲアルゴリズムは、予め定めた閾値しきい値Ｔを超える値
【数２５】
2006340373.tif 000027
【００５０】
に対応するアクティブ状態の可変数を選択する。したがって、前方メッセージは、
【数２６】
2006340373.tif 000028
【００５１】
である。
【００５２】
これが、２つのアルゴリズム間のただ一つの相違であるので、簡略のために、更なる議論は、Ｍ−ＢＣＪＲアルゴリズムに集中される。
【非特許文献１】L. Bahl, J. Cocke, F. Jelinek, J. Raviv著、"Optimal decoding of linear codes for minimizing symbol error rate," IEEE Trans. Information Theory, vol. 20, pp. 284-287, 1974年3月
【非特許文献２】V. Franz, J.B. Anderson著、"Concatenated decoding with a reduced-search BCJR algorithm," IEEE Journal on Selected Areas in Commun., vol. 16, pp. 186-195, 1998年2月
【非特許文献３】T. Heskes及びO. Zoeter著、"Expectation propagation for approximate inference in dynamic bayesian networks,"(Proceedings of UAI-2002, A. Darwiche and N. Friedman, Eds., 2002, pp. 216-233)
【発明の開示】
【００５３】
この再帰は、各時間インスタンスでアクティブ状態の系列を選択するという結果になる。その結果、Ω１：Ｔとなる。さらに、前方メッセージは、｜ＳＸ｜からＭに低減されたサポートによるスパース表現を持っていると見なすことができる。
【００５４】
後方再帰と、
【数２７】
2006340373.tif 000029
【００５５】
の計算は、これら選択されたアクティブ状態中の状態のためにのみ計算される。したがって、このアルゴリズムの複雑さは、｜ＳＸ｜ではなく、Ｍに関連している。これはアルゴリズムに対して、調整可能な複雑さを提供する。しかしながら、現実には、相当なメモリを備えたシステムが、ほぼ最適な性能を達成するために、Ｍ値は、｜ＳＸ｜のかなりの割合である必要がある。
【００５６】
また、
【数２８】
2006340373.tif 000030
【００５７】
であるので、Ｍ−ＢＣＪＲのアクティブ状態選択は、各時間インスタンスにおいて、フィルタ処理された状態変数の確率分布に基づくことも知られている。
【００５８】
したがって、一般に、当該技術で周知の複雑さを低減した方法は、トレリス状態が低減された場合に、情報の損失による性能低下を被っていることは明らかである。さらに、これらの方法の性能は、「エンコーダ」のエネルギー分布及びメモリに依存する。
【００５９】
Ｍ−又はＴ−ＢＣＪＲアルゴリズムは、フィルタされた状態の確率分布に基づいて、前方再帰におけるアクティブ状態の集合を選択する。これは、アクティブ状態の集合を決める場合、考慮中の時間インスタントまでの受信信号だけが考慮されることを示唆する。当然のことながら、将来の受信信号も同様に考慮するほうがよい。
【００６０】
本発明は、上に述べられた問題に取り組む。
【００６１】
本発明の第一の目的は、通信システムにおいて受信機で使用されるためのシンボル検出器を提供する。このシンボル検出器は、受信データの系列上に存在するであろうシンボルの集合を決定するよう動作する。このシンボル検出器は、隠れマルコフモデル状態トレリス中の状態確率を決定するように動作する、低減状態前方後方再帰手段を含む。このシンボル検出器は、低減状態前方再帰の実行のために利用可能な状態の集合に関連付けられた低減された前方メッセージの集合を決定するように動作する前方メッセージ決定手段と、前記前方メッセージ決定手段と独立して動作し、低減状態後方再帰の実行のために後方メッセージ決定手段に関連付けられた低減された後方メッセージの集合を決定するように動作する後方メッセージ決定手段とを備えている。
【００６２】
本発明の第二の目的は、トレリスに基づいた処理に従って、受信信号のシンボルを復号する方法を提供する。前記シンボルは、前記トレリスの状態間の遷移の系列であり、前記方法は、与えられた時間インスタンスについて、その時間インスタンスにおける状態の周辺事後分布の評価を決定することと、前記トレリス中の状態の集合からアクティブ状態を選択することであって、前記アクティブ状態を選択するステップは、その時間インスタンスにおける状態の前記周辺事後分布を用いることと、その後、前方後方再帰の実行のために選択された状態に対する前方及び後方メッセージを計算し、前記トレリス内の状態確率を決定することとを含む。
【００６３】
本発明の目的は、T. HeskesとO. Zoeterとによって著された"Expectation propagation for approximate inference in dynamic bayesian networks,"(Proceedings of UAI-2002, A. Darwiche and N. Friedman, Eds., 2002, pp. 216-233)（非特許文献３）の中で示されるような「予測伝播」の概念に基づいた周辺事後分布ｐ（Ｘｔ｜ｙ１：Ｔ）の現在利用可能な近似に基づいて前方再帰を行うよう動作する前方後方再帰チャネルデコーダを提供する。
【００６４】
本発明のこの目的に従って、デコーダは、前方再帰の中で使用されたアクティブ状態の集合から独立して選択されたアクティブ状態の集合に基づいて後方再帰を行なうよう動作する。デコーダは、アルゴリズムが一定のポイントに達するまで、前方再帰および後方再帰を反復して行なうよう動作する。
【００６５】
前方後方再帰で使用されるアクティブ状態の集合の独立した選択を達成するために、非アクティブ状態の前方／後方メッセージが予め定めた値（例えばη）に設定されるかもしれない。これは、非アクティブな状態に関連付けられたメッセージを零にするＭ−ＢＣＪＲアルゴリズムと対照をなす。
【００６６】
本発明は、アプリケーション特有の電子デバイス又は他のデバイスの手段によって実施されうる一方、この実施は、従来のハードウェア上で達成され、コンピューター実施可能命令によって適切に設定される。
【００６７】
具体的な実施例が、添付図面を参照して、本発明の一例、及び例示することを意図して説明される。
【発明を実施するための最良の形態】
【００６８】
本発明は、無線通信システムの等化のための実施に関して記述される。図３は、一般に知られている構成のＭＩＭＯデータ通信システム１０を備えたシステムを示す。新しい構成要素は、本発明の具体的な実施例に従って、次の記述から明白になる。
【００６９】
通信システム１０は、送信機デバイス１２および受信機デバイス１４を含む。多くの状況では、送信機および受信機が組み合わされた設備が無線通信デバイスに提供されるであろうことが認識されるだろう。しかし、この例では、説明を容易にするために、これらのデバイスは一方向通信デバイスとして例示される。
【００７０】
送信機デバイス１２は、チャネルエンコーダ１８にデータ（情報ビットあるいはシンボルを含む）を供給するデータ送信装置１６より構成される。この例におけるチャネルエンコーダ１８は、再帰体系畳み込み（ＲＳＣ：recursive systematic convolutional）エンコーダのような畳み込み符号器、あるいはより強力と言われるターボ符号化器（インタリーバを含む）を含む。入力されるビットよりも多くのビットが出力され、一般に、そのレートは、２分の１あるいは３分の１である。
【００７１】
図示する例では、チャネルインタリーバ２０と時空間エンコーダ２２とがチャネルエンコーダ１８の後に続く。時空間エンコーダ２２は、複数個の送信アンテナ２５を含む送信機アンテナアレー２４からの同時送信のために、複数個のコードシンボルとして入力シンボルを符号化する。この図示する例では、３本の送信アンテナ２５の場合であるが、実際の実装では、用途により多く又は少ないアンテナ数でも構わない。
【００７２】
符号化された送信信号は、送信アンテナアレー２４と、受信機デバイス１４の対応する受信アンテナアレー２６との間で定義されるＭＩＭＯチャネル２８を通って伝搬する。受信アンテナアレー２６は、受信機デバイス１４のデコーダ３０に複数個の入力を供給する複数個の受信アンテナ２７を含む。この具体的な実施例では、受信アンテナアレー２６は３本の受信アンテナ２７を含む。
【００７３】
デコーダ３０は、エンコーダ２２の影響を除去するタスクを行う。送信アンテナ２５の各々から１つの信号ストリームが送信され、デコーダ３０の出力は複数個の信号ストリームを含む。それぞれの信号ストリームは、特定の値の送信シンボルの確率に関するいわゆる軟値データ又は尤度データを持っている。このデータは、チャネルインタリーバ２０の効果を逆にするチャネル逆インタリーバ３２に供給される。そして、このチャネル逆インタリーバ３２による畳み込み符号出力は、この例では、Ｖｉｔｅｒｂｉデコーダであるチャネルデコーダ３４に提示される。これは、畳み込み符号を復号する。
【００７４】
デコーダ３０の具体的な機能を記述する。
【００７５】
一般的に、チャネルデコーダ３４は、ＳＩＳＯ(soft-in soft-out)デコーダである。それは、シンボル（あるいはビット）尤度データを受信し、例えば、硬判定がなされたデータとは異なる類似の尤度データを出力として提供するよう動作する。チャネルデコーダ３４の出力は、任意の所望の方法からなる更なる処理のために、データシンク３６に供給される。
【００７６】
チャネルデコーダ３４からの軟出力が、チャネルインタリーバ２０に相当するチャネルインタリーバ３８に提供される場合に、反復復号が適用される。チャネルインタリーバ３８は、反復時空間（及び／又は周波数）復号と、チャネル復号のために、軟値（尤度）データを時空間デコーダ３０に供給する。この配置では、チャネルデコーダ３４が、例えば、エラーチェックビットを含んでいる完全に送信されたシンボルを、空間−時間デコーダ３０に供給することが認識されるだろう。
【００７７】
図４は、受信機デバイス１６として（ソフトウェアまたはアプリケーション特有のハードウェア構成要素によって）操作可能な構成のハードウェアを概略的に示す。受信機デバイス１６は、ワーキングメモリ１１２に格納されたマシンコード命令を実行し、大容量記憶装置１１６からの検索が可能なように動作するプロセッサ１１０を含む。多目的バス１１４によって、ユーザー操作可能な入力装置１１８は、プロセッサ１１０と通信できる。ユーザー操作可能な入力装置１１８は、この例では、キーボード、マウスあるいは他のポインティングデバイス、ライティングタブレット、音声認識手段、又はユーザー入力動作を解釈することができ、データ信号に変換することができる他の手段を含むことができる。
【００７８】
更に、オーディオ／ビデオ出力ハードウェアデバイス１２０が、ユーザーへの情報の出力のために、多目的バス１１４に接続される。オーディオ／ビデオ出力ハードウェアデバイス１２０は、表示装置、スピーカー、あるいはユーザーに情報を提示することができるその他任意のデバイスを含むことができる。
【００７９】
多目的バス１１４に接続された通信ハードウェアデバイス１２２は、アンテナ２６に接続される。図４で説明された実施例では、ワーキングメモリ１１２は、プロセッサ１１０によって実行された時、ユーザインターフェースの確立によって、ユーザーとのデータの通信を可能にさせるユーザーアプリケーション１３０を格納する。この実施例内のアプリケーションは、多目的、あるいはユーザーによって習慣的に使用されるかもしれない特定のコンピューターに実装されたユーティリィティを設定する。
【００８０】
特定の実施例に従う通信設備１３２も、ワーキングメモリ１１２に格納され、アプリケーション１３０のうちの１つの実行で生成されたデータが処理され、次に、送信および別の通信デバイスとの通信のために通信ハードウェアデバイス１２２に渡されることを可能にするために通信プロトコルを設定する。便宜上、アプリケーション１３０を定義するソフトウェア、および通信設備１３２は、ワーキングメモリ１１２および大容量記憶装置１１６内に部分的に格納されるかもしれないことが理解されるだろう。ワーキングメモリ１１２および大容量記憶装置１１６に格納されたデータへのアクセスの可能な異なる速度を考慮するために、これが有効に管理されることを可能にするために、メモリーマネージャーがオプションとして提供されうる。
【００８１】
通信設備１３２に対応するプロセッサ実行可能命令のプロセッサ１１０による実行においては、プロセッサ１１０が、認識された通信プロトコルに従って別のデバイスとの通信を確立するように動作する。
【００８２】
記述された実施例では、デコーダが、各時間インスタンスにおいて固定数のアクティブ状態を選択する。これは、Ｍ−ＢＣＪＲアルゴリズムに従って得られたアプローチに類似している。一方、この選択アプローチは、［２］におけるＴ−ＢＣＪＲアルゴリズムに関連して議論されたように、選択基準に基づいて可変数のアクティブ状態を選択することを含む。
【００８３】
記述された実施例では、等化器が、合計Ｉ回の前方後方再帰の反復を行ない、ｔ∈｛１，・・・，Ｔ｝のそれぞれについて、アルゴリズムのｉ番目の反復において、前方メッセージ
【数２９】
2006340373.tif 000031
【００８４】
及び後方メッセージ
【数３０】
2006340373.tif 000032
【００８５】
を計算する。アルゴリズムのｉ番目の反復では、ｔ番目の時間インスタントにおいて、前方及び後方再帰のアクティブ状態の集合は、それぞれ
【数３１】
2006340373.tif 000033
【００８６】
及び
【数３２】
2006340373.tif 000034
【００８７】
によって示され、
【数３３】
2006340373.tif 000035
【００８８】
と
【数３４】
2006340373.tif 000036
【００８９】
とは、それぞれ前方及び後方再帰におけるアクティブ状態であると示している状態の集合を示す。
【００９０】
前方再帰におけるｔ番目の時間インスタンスでは、前方メッセージが、（ｉ＋１）番目の反復における時間（ｔ−１）が、
【数３５】
2006340373.tif 000037
【００９１】
の場合
【数３６】
2006340373.tif 000038
【００９２】
として計算され、後方メッセージが、ｉ番目の反復における時間ｔが、
【数３７】
2006340373.tif 000039
【００９３】
の場合
【数３８】
2006340373.tif 000040
【００９４】
として計算される。
【００９５】
図５は、（ｉ＋１）番目の反復と、関連する計算の前方再帰におけるｔ番目の時間インスタンスの初めにおいて利用可能な状態の集合を示している。
【００９６】
したがって、
【数３９】
2006340373.tif 000041
【００９７】
の場合、状態変数の周辺事後分布の近似は、
【数４０】
2006340373.tif 000042
【００９８】
のように決定される。ここでは、
【数４１】
2006340373.tif 000043
【００９９】
を決定するために、
【数４２】
2006340373.tif 000044
【０１００】
のような予備計算が行われる。ここで、
【数４３】
2006340373.tif 000045
【０１０１】
を仮定している。
【０１０２】
その後、デコーダは、
【数４４】
2006340373.tif 000046
【０１０３】
のうちの大きいＭ個の要素を選択し、Ｘｔの対応する配列を
【数４５】
2006340373.tif 000047
【０１０４】
に含める。これによって、それらを選択されたアクティブ状態にする。新たな前方メッセージは、
【数４６】
2006340373.tif 000048
【０１０５】
のように計算される。同様に、ここでは、
【数４７】
2006340373.tif 000049
【０１０６】
を仮定している。
【０１０７】
同様に、各時間インスタンスの前方アクティブ状態および前方メッセージは、再帰的に更新される。
【０１０８】
例示するように、（ｉ＋１）番目の反復における時間（ｉ＋１）の後方メッセージを
【数４８】
2006340373.tif 000050
【０１０９】
として、（ｉ＋１）番目の反復における時間ｔの前方メッセージを
【数４９】
2006340373.tif 000051
【０１１０】
として考慮することによって達成される。
【０１１１】
後方再帰に関して、後方アクティブ状態選択が、（ｉ＋１）番目の反復におけるｔ番目の時間インスタンスの後方メッセージ計算とともに記述される。
【０１１２】
図６は、（ｉ＋１）番目の反復と、関連する計算の後方再帰におけるｔ番目の時間インスタンスの初めにおいて利用可能な状態の集合を示している。したがって、
【数５０】
2006340373.tif 000052
【０１１３】
の場合、状態変数の周辺事後分布の近似は、
【数５１】
2006340373.tif 000053
【０１１４】
のように決定される。ここでは、
【数５２】
2006340373.tif 000054
【０１１５】
であり、
【数５３】
2006340373.tif 000055
【０１１６】
を仮定している。
【０１１７】
その後、検出器は、
【数５４】
2006340373.tif 000056
【０１１８】
のうちの大きいＭ個の要素を選択し、Ｘｔの対応する配列を
【数５５】
2006340373.tif 000057
【０１１９】
に含める。これによって、それらを選択されたアクティブ状態にする。これは、以下を含む新たな後方メッセージとなる。
【数５６】
2006340373.tif 000058
【０１２０】
ここでは、同様に
【数５７】
2006340373.tif 000059
【０１２１】
を仮定している。
【０１２２】
前方再帰段階のように、各時間インスタンスの後方アクティブ状態および後方メッセージは、その後、再帰的に更新される。Ｉ番目の反復における後方再帰中に、状態変数の周辺事後分布、および連続状態変数のペアの最終評価は、次のように計算される。
【数５８】
2006340373.tif 000060
【０１２３】
これは、アクティブ状態の前方／後方集合にはない状態の前方／後方メッセージが、値ηに設定されるという理解に従う。最終的に、送信されたシンボルの周辺事後分布が、
【数５９】
2006340373.tif 000061
【０１２４】
のように推定される。ここで、集合
【数６０】
2006340373.tif 000062
【０１２５】
は、シンボルｂｔの送信となる（Ｘｔ−１，Ｘｔ）のペアの集合を表し、
【数６１】
2006340373.tif 000063
【０１２６】
は規格化定数である。
【０１２７】
トレリスが終了したシステム（例えば、状態ｘ０）において、
【数６２】
2006340373.tif 000064
【０１２８】
及び
【数６３】
2006340373.tif 000065
【０１２９】
は、
【数６４】
2006340373.tif 000066
【０１３０】
及び
【数６５】
2006340373.tif 000067
【０１３１】
のように設定される。
【０１３２】
疑いを避けるために、数Ｉは、予め定められるか、適切な停止規則に基づいて動的に決定されるかもしれない。例えば、後方再帰の選択されたアクティブ状態の著しい変化がない場合、再帰を止めることは適切になりえる。しかしながら、簡略のために、上述された方法論の実施の以下に示す具体例では、反復回数は予め定められている。
【０１３３】
図７Ａおよび図７Ｂ（１つの図７の２つの部と見なされた）のフローチャートによって示された処理は、各時間インスタンスにおいて、アクティブ状態の固定数を用いて、無線通信システムの等化を実行するように動作する。この処理は、系列ｙ１：Ｔのチャネル等化器における受信に基づいて始まる。
【０１３４】
最初のステップＳ２では、パラメーターＭ，η，及びＩが設定される。これによって、反復カウンタｉが初期化される。つまりｉ＝０となる。さらに、
【数６６】
2006340373.tif 000068
【０１３５】
が、
【数６７】
2006340373.tif 000069
【０１３６】
のように初期化される。
【０１３７】
その後、ステップＳ４では、ｔが１に設定され、
【数６８】
2006340373.tif 000070
【０１３８】
が｛ｘ０｝に設定され、
【数６９】
2006340373.tif 000071
【０１３９】
が
【数７０】
2006340373.tif 000072
【０１４０】
に従って設定される。
【０１４１】
次に、ステップＳ６では、前方メッセージ
【数７１】
2006340373.tif 000073
【０１４２】
が、式（１１）で示した式を用いて計算される。
【０１４３】
ステップＳ８では、確率
【数７２】
2006340373.tif 000074
【０１４４】
が、式（１０）を用いて計算される。次に、ステップＳ１０では、
【数７３】
2006340373.tif 000075
【０１４５】
のうちの大きなＭ個の要素が選択される。この選択ステップは、領域内の状態の集合
【数７４】
2006340373.tif 000076
【０１４６】
の生成を引き起こす。
【０１４７】
ステップＳ１２では、前方再帰に使用される集合の選択に続いて、前方メッセージ
【数７５】
2006340373.tif 000077
【０１４８】
が、式（１３）を用いて、
【数７６】
2006340373.tif 000078
【０１４９】
の場合に計算される。
【０１５０】
ステップＳ１４では、考慮中の時間ｔに基づいて、判定がなされる。ｔ＜Ｔの場合、ｔはステップＳ１６において１インクリメントされ、処理はステップＳ６に戻る。そうでなければ、その処理は、ステップＳ１８（図７Ｂは図７Ａから続く）に継続する。そこでｔはＴ−１に設定される。同ステップで、処理は、
【数７７】
2006340373.tif 000079
【０１５１】
を設定する。
【０１５２】
この処理は、式（１５）を用いて後方メッセージ
【数７８】
2006340373.tif 000080
【０１５３】
を計算することによりステップＳ２０を続ける。次に、ステップＳ２２では、確率
【数７９】
2006340373.tif 000081
【０１５４】
が、式（１４）を用いて
【数８０】
2006340373.tif 000082
【０１５５】
のために計算される。前方メッセージに関し、
【数８１】
2006340373.tif 000083
【０１５６】
のうち大きなＭ個の要素がステップＳ２４で選択され、もって、後方再帰のための集合
【数８２】
2006340373.tif 000084
【０１５７】
を決定する。
【０１５８】
一旦、後方再帰のための状態の集合が決定されたならば、ステップＳ２６では、後方メッセージ
【数８３】
2006340373.tif 000085
【０１５９】
が、式（１７）を用いて、
【数８４】
2006340373.tif 000086
【０１６０】
のために計算される。
【０１６１】
ステップＳ２８では、ｉの値に関して判定がなされる。ｉ＝Ｉ−１の場合、ステップＳ３０において、式（１９）から
【数８５】
2006340373.tif 000087
【０１６２】
を、式（２０）から
【数８６】
2006340373.tif 000088
【０１６３】
を計算する。そうでない場合、この計算は行なわれず、ステップＳ３０がバイパスされる。
【０１６４】
次に、この処理は、ｔ＞１であるかを判定することによるステップＳ３２に続く。ｔ＞１であるならば、ｔはステップＳ３４において１ずつ減少され、この処理はステップＳ２０に戻る。そうでない場合、この処理はステップＳ３６に続く。ここでは、ｉ＜Ｉ−１であれば、ステップＳ３８において１ずつ増加され、次にこの処理は、ステップＳ６に戻る。一方、ｉ＝１の場合、この処理は終了する。
【０１６５】
図８は、ターボ等化スキームで、シミュレーション環境において、上述された処理の使用例を示す。ターボ等化器では、等化器とチャネルデコーダの間に反復がある。本発明は、当然ながらターボ等化器の反復に統合することができる。
【０１６６】
図示するシミュレーションでは、最初の全体的なターボ等化反復で、2つの反復が等化器内で行なわれた。その後、前方及び後方再帰のみが、等化器内で実行された。さらに、最初の全体的なターボ反復の後、シミュレーションは、提案されたアルゴリズムの前方再帰のために、前の全体的なターボ反復の後方再帰のメッセージおよびアクティブ状態の系列を使用する。
【０１６７】
図８は、ＢＣＪＲと、３２のアクティブ状態を持つＭ−ＢＣＪＲと、８ＰＳＫシンボル送信で５タップ一律遅延プロファイル準静的レイリーフェージングチャネル内に１６のアクティブ状態を持つ上述した等化処理とのシミュレーションを示している。比較のため、最適な等化器（ＢＣＪＲ）は、合計４０９６の状態を持っている。示された結果は、５回のターボ等化繰り返しのものである。記述されたシステムおよび従来のＭ−ＢＣＪＲシステムは、この例では、同様の計算上の複雑さを持っているが、記述された実施例は、Ｍ−ＢＣＪＲアプローチに類似しておらず、最適なアプローチと実質的に同様に、改善された性能を提供することが注目されるべきである。
【０１６８】
要約すると、本発明は、通信チャネルを介して通信から得られる信号を決定することに関連する。具体的な例は、無線通信チャネルのコンテキストの中で示されているが、これが本発明の応用についての制限と見なされるべきでないことは読者によって認識されるだろう。
【０１６９】
通信受信機（例えばチャネルデコーダおよび等化器）の中の多くの構成要素の最適な復号は、隠れマルコフモデル（ＨＭＭ）の連続状態変数のペア、および状態変数の周辺事後分布を見つける問題として定式化することができる。ＢＣＪＲアルゴリズムは、これら要求される周辺事後分布を計算するための効率的なアルゴリズムである。しかしながら、このアルゴリズムは、それが最も現実的な状況において扱いにくい複雑さを被っているので、一般に、非実用的であると言われている。したがって、ＢＣＪＲアルゴリズムの複雑さを低減したバージョンが明らかにされた。これによって、性能面で容認できる低下を犠牲にして、容認できる復号信頼性を提供する。そのような１つのアルゴリズムは、Ｍ−ＢＣＪＲアルゴリズムである。その中では、アクティブ状態の集合が、前方再帰中の各時間インスタンスにおいて選択され、計算は、これら選択されたアクティブ状態のためにほとんど実行される。そのようにして、システム設計者には、制御可能で調整可能な複雑さが提供される。
【０１７０】
本発明は、低減状態前方−後方再帰アルゴリズムを使用するデコーダを提供する。このデコーダは、完全状態ＢＣＪＲアルゴリズムの複雑さの一部のみを用いながら、以前に識別された低減状態復号によって改善された性能を提供する。これを行うために、本発明の局面の決定者は、状態変数の周辺事後分布の近似を、アクティブ状態の選択のために使用する。一つの実施例は、アルゴリズムの各再帰における異なる状態選択を可能にする。このように、このアルゴリズムは恐らく不適切なアクティブ状態選択から戻ることができ、それによって、時期尚早の状態選択から生じる情報損失を低減する。
【０１７１】
本発明の実施例は、通信システム、ターボデコーダ（例えば、ＵＭＴＳ、無線ＬＡＮ標準に要求される）、および等化器（例えば、ＥＤＧＥ規格に要求される）において様々な用途を持つ。さらに、状態変数の周辺事後分布、及び連続状態変数のペアの計算を含んでいるあらゆるアプリケーションに適用可能なので、本発明は、音声認識のような様々な他の用途に適用可能である。
【０１７２】
疑いを避けるために、具体的な実施例は、一例として記述される。そして、具体的な特徴の変形及び変更が、本発明の意図した範囲から外れることなく、代替として、あるいは追加されうることが認識されるであろう。求められる保護範囲は、前述を参照して、及び添付図面を参照して解釈されるように、特許請求の範囲の文言によって定義されるべきである。
【図面の簡単な説明】
【０１７３】
【図１】図１は、上述したイントロダクションで述べたように、無線通信チャネルを介した送信によって受信されるような離散確率変数上の確率分布を例示するグラフである。
【図２】図２は、上述したイントロダクションで述べたように、使用された一例の等化器トレリスの節を表わす概略図である。
【図３】図３は、無線通信における送信機および受信機を含む本発明の具体的な実施例に従った通信システムの概略図である。
【図４】図４は、図３の中で例示された受信機の概略図である。
【図５】図５は、本発明の記述された実施例の演算で使用される特定の時間インスタンスにおける前方再帰に利用可能な状態を例示する状態ダイヤグラムである。
【図６】図６は、本発明の記述された実施例の演算で使用される前記時間インスタンスにおける後方再帰に利用可能な状態を例示する状態ダイヤグラムである。
【図７Ａ】図７Ａは、本発明の記述された実施例に従ったシンボル検出の処理のフローチャートである。
【図７Ｂ】図７Ｂは、本発明の記述された実施例に従ったシンボル検出の処理のフローチャートである。
【図８】図８は、当該技術に含まれるシンボル検出処理の性能に対するシミュレーション環境の中でモデル化された本発明の記述された実施例の性能を例示するグラフである。
【図１】
2006340373.tif 000089
【図２】
2006340373.tif 000090
【図３】
2006340373.tif 000091
【図４】
2006340373.tif 000092
【図５】
2006340373.tif 000093
【図６】
2006340373.tif 000094
【図７Ａ】
2006340373.tif 000095
【図７Ｂ】
2006340373.tif 000096
【図８】
2006340373.tif 000097
【外国語明細書】
2006340373000001.pdf