(57)【要約】  受信信号を値セットのうちの最小値として決定する装置であって、前記装置は、プロセッサであって、レジスタに第１値セットをロードし、前記第１値セットのうちの最大値と、前記第１値セットのうちの最小値と、を識別し、前記レジスタの中で、前記最大値を第２値セットのうちの値で置き換え、同時に、前記最小値を前記最小値に基づき計算された新しい値で置き換えて、更新第１値セットを受信し、前記更新第１値セットの全ての値が前記第２値セットの値で置き換えられるまで、前述のステップを繰り返す、よう構成されるプロセッサ、を含む。
2020511014.tif 000002
【特許請求の範囲】
【請求項１】
受信信号を値セットのうちの最小値として決定する装置であって、前記装置は、プロセッサであって、
(a)レジスタに第１値セットをロードし、
(d)前記第１値セットのうちの最大値と、前記第１値セットのうちの最小値と、を識別し、
(e)前記レジスタの中で、前記最大値を第２値セットのうちの値で置き換え、前記最小値を前記最小値に基づき計算された新しい値で置き換えて、更新第１値セットを受信し、
(f)前記更新第１値セットの全ての値が前記第２値セットの値で置き換えられるまで、ステップ(d)及び(e)を繰り返す、
よう構成されるプロセッサ、を含む装置。
【請求項２】
前記プロセッサは、ステップ(d)乃至(f)をK回繰り返すよう構成される、請求項１に記載の装置。
【請求項３】
前記第１値セット及び前記第２値セットの各々の長さはKであり、前記装置はK−Best最適化に従い最小値を計算する、請求項１乃至２のいずれか一項に記載の装置。
【請求項４】
前記プロセッサは、
（ｂ）ステップ(d)の前に、前記第１値セットの第１最小値を識別し、
（ｃ）前記レジスタの中で、ステップ（ｂ）の後に、前記第１最小値を前記最小値に基づき計算された新しい値で置き換えて、更新第１値セットを受信する、
よう構成される、請求項１乃至３のいずれか一項に記載の装置。
【請求項５】
前記第１及び第２値セットの中の前記値は、それぞれのシンボルの中の２つの異なるサブキャリアに関連する値であり、特に、それぞれの直交振幅変調（QAM）又は位相偏移キーイング（PSK）変調シンボルに関連する部分ユークリッド距離（PED）である、請求項１乃至４のいずれか一項に記載の装置。
【請求項６】
前記信号は、直交周波数分割多重（OFDM）通信に基づき、前記第１値セットは第１サブキャリアの信号を表し、前記第２値セットは第２サブキャリアの信号を表す、請求項１乃至５のいずれか一項に記載の装置。
【請求項７】
前記受信信号は、特にMIMO通信の無線信号である、請求項１乃至６のいずれか一項に記載の装置。
【請求項８】
前記第１値セットの前記最大及び前記最小値を識別することは、２値比較器の構造を用いて行われる、請求項１乃至７のいずれか一項に記載の装置。
【請求項９】
前記第１値セットの前記最大及び前記最小値を識別することは、前記レジスタの中の前記第２値セットの値を無視する強制ロジックを含む、請求項１乃至８のいずれか一項に記載の装置。
【請求項１０】
受信信号を値セットのうちの最小値として決定する方法であって、
(a)レジスタに第１値セットをロードするステップと、
(d)前記第１値セットのうちの最大値と、前記第１値セットのうちの最小値と、を識別するステップと、
(e)前記レジスタの中で、前記最大値を第２値セットのうちの値で置き換え、同時に、前記最小値を前記最小値に基づき計算された新しい値で置き換えて、更新第１値セットを受信するステップと、
(f)前記更新第１値セットの全ての値が前記第２値セットの値で置き換えられるまで、ステップ(d)及び(e)を繰り返すステップと、
を含む方法。
【請求項１１】
受信信号を値セットのうちの最小値として決定するソフトウェアプログラムプロダクトであって、
非一時的コンピュータ可読記憶媒体と、
レジスタに第１値セットをロードするための第１プログラム命令と、
前記第１値セットのうちの最大値と、前記第１値セットのうちの最小値と、を識別するための第２プログラム命令と、
前記レジスタの中で、前記最大値を第２値セットのうちの値で置き換え、前記最小値を前記最小値に基づき計算された新しい値で置き換えて、更新第１値セットを受信するための第３プログラム命令と、
前記更新第１値セットの全ての値が前記第２値セットの値で置き換えられるまで、前記第１、第２、及び第３プログラム命令を繰り返すための第４プログラム命令と、
を含み、
前記第１、第２、第３及び第４プログラム命令は、前記非一時的コンピュータ可読記憶媒体から少なくとも１つの電子化プロセッサにより実行される、ソフトウェアプログラムプロダクト。
【発明の詳細な説明】
【背景技術】
【０００１】
本発明は、その幾つかの実施形態において、複数入力単一バッファ処理に関し、より詳細には、排他的ではなく、K−Bestアルゴリズムに基づく多入力多出力（multiple  input  multiple  output、MIMO）デコーダアーキテクチャに関する。
【０００２】
無線標準の近年のバージョンは、MIMO技術が非常に高いスペクトル効率を達成するので、MIMO技術を採用する。このような技術は、同じ周波数及びタイムスロットで送信される非常に多数のストリームを含む。したがって、デコーダは非常に重要であり、直交周波数分割多重化（orthogonal  frequency−division  multiplexing、OFDM）受信機の最も複雑な部分である。最適デコーダ（最大尤度（maximum  likelihood、ML）検出問題）の複雑性は、より高次の変調及びより多数の送信ストリームにより指数関数的に増加している。したがって、最適ソリューションは実行不可能である。代替として、比較的低い複雑性により妥当な性能を達成するために、ほぼ最適なソリューションが代わりに使用される。
【発明の概要】
【０００３】
本発明の目的は、小面積且つ最小遅延の信号デコーダアーキテクチャを提供することである。
【０００４】
前述の及び他の目的は、独立請求項の特徴により達成される。さらに実装形態は、従属請求項、説明及び図面から明らかである。
【０００５】
第１の態様によると、受信信号を値セットのうちの最小値として決定する装置であって、前記装置は、プロセッサであって、
(a)レジスタに第１値セットをロードし、
(d)前記第１値セットのうちの最大値と、前記第１値セットのうちの最小値と、を識別し、
(e)前記レジスタの中で、前記最大値を第２値セットのうちの値で置き換え、同時に、前記最小値を前記最小値に基づき計算された新しい値で置き換えて、更新第１値セットを受信し、
(f)前記更新第１値セットの全ての値が前記第２値セットの値で置き換えられるまで、ステップ(d)及び(e)を繰り返す、よう構成されるプロセッサ、を含む装置が提供される。
【０００６】
第２の態様によると、受信信号を値セットのうちの最小値として決定する方法であって、
(a)レジスタに第１値セットをロードするステップと、
(d)前記第１値セットのうちの最大値と、前記第１値セットのうちの最小値と、を識別するステップと、
(e)前記レジスタの中で、前記最大値を第２値セットのうちの値で置き換え、同時に、前記最小値を前記最小値に基づき計算された新しい値で置き換えて、更新第１値セットを受信するステップと、
(f)前記更新第１値セットの全ての値が前記第２値セットの値で置き換えられるまで、ステップ(d)及び(e)を繰り返すステップと、を含む方法が提供される。
【０００７】
第３の態様によると、受信信号を値セットのうちの最小値として決定するソフトウェアプログラムプロダクトであって、
非一時的コンピュータ可読記憶媒体と、
レジスタに第１値セットをロードするための第１プログラム命令と、
前記第１値セットのうちの最大値と、前記第１値セットのうちの最小値と、を識別するための第２プログラム命令と、
前記レジスタの中で、前記最大値を第２値セットのうちの値で置き換え、前記最小値を前記最小値に基づき計算された新しい値で置き換えて、更新第１値セットを受信するための第３プログラム命令と、
前記更新第１値セットの全ての値が前記第２値セットの値で置き換えられるまで、前記第１、第２、及び第３プログラム命令を繰り返すための第４プログラム命令と、
を含み、
前記第１、第２、第３及び第４プログラム命令は、前記非一時的コンピュータ可読記憶媒体から少なくとも１つの電子化プロセッサにより実行される、ソフトウェアプログラムプロダクトが提供される。
【０００８】
前述の態様のいずれかによる装置、方法、及び／又はソフトウェアプログラムプロダクトの第１の可能な実装形式では、プロセッサはステップ(d)〜(f)をK回繰り返すよう構成される。この繰り返しにより、K個の最小値が識別される。
【０００９】
前述の態様のいずれかの第１の前述の実装形式のような又はそれによる前述の態様のいずれかによる装置、方法、及び／又はソフトウェアプログラムプロダクトの第２の可能な実装形式では、前記第１値セットお酔いｂ第２値セットの各々の長さはKであり、前記装置はK−Best最適化に従い最小値を計算する。
【００１０】
前述の態様のいずれかの前述の実装形式のうちのいずれかのような又はそれによる前述の態様のいずれかによる装置、方法、及び／又はソフトウェアプログラムプロダクトの第３の可能な実装形式では、前記プロセッサは、
（ｂ）ステップ(d)の前に、前記第１値セットの第１最小値を識別し、
（ｃ）前記レジスタの中で、ステップ（ｂ）の後に、前記第１最小値を前記最小値に基づき計算された新しい値で置き換えて、更新第１値セットを受信する、よう構成される。これは、各値が全ての他の値と比較されることを可能にし、最小値選択の結果を最適化する。
【００１１】
前述の態様のいずれかの前述の実装形式のうちのいずれかのような又はそれによる前述の態様のいずれかによる装置、方法、及び／又はソフトウェアプログラムプロダクトの第４の可能な実装形式では、前記第１及び第２値セットの中の値は、それぞれのシンボルの中の２つの異なるサブキャリアに関連する値、特に、それぞれ直交振幅変調（quadrature  amplitude  modulation、QAM）又は位相偏移キーイング（phase−shift  keying、PSK）変調シンボルに関連する部分ユークリッド距離（partial  Euclidean  distance、PED）である。
【００１２】
前述の態様のいずれかの前述の実装形式のうちのいずれかのような又はそれによる前述の態様のいずれかによる装置、方法、及び／又はソフトウェアプログラムプロダクトの第５の可能な実装形式では、前記信号は直交周波数分割多重化（orthogonal  frequency−division  multiplexing、OFDM）通信に基づき、前記第１値セットは第１サブキャリアの信号を表し、前記第２値セットは第２サブキャリアの信号を表す。
【００１３】
前述の態様のいずれかの前述の実装形式のうちのいずれかのような又はそれによる前述の態様のいずれかによる装置、方法、及び／又はソフトウェアプログラムプロダクトの第６の可能な実装形式では、前記受信信号は、特に多入力多出力（multiple  input  multiple  output、MIMO）通信の無線信号である。
【００１４】
前述の態様のいずれかの前述の実装形式のうちのいずれかのような又はそれによる前述の態様のいずれかによる装置、方法、及び／又はソフトウェアプログラムプロダクトの第７の可能な実装形式では、前記第１値セットの最大値及び最小値を識別するステップは、２値比較器の構造を用いて行われる。このアーキテクチャは、単純なハードウェアユニットを繰り返し使用する。
【００１５】
前述の態様のいずれかの前述の実装形式のうちのいずれかのような又はそれによる前述の態様のいずれかによる装置、方法、及び／又はソフトウェアプログラムプロダクトの第８の可能な実装形式では、前記第１値セットの最大値及び最小値を識別するステップは、前記レジスタ内の前記第２値セットの値を無視する強制ロジックを含む。これは、第１値セットの処理中に第２値セットの混合を防ぐ。
【００１６】
特に定められない限り、本願明細書で用いられた全ての技術的及び／又は科学的用語は、本発明の関連する分野の当業者により通常理解されるものと同じ意味を有する。ここに記載のものに類似する方法及び材料が本発明の実施形態の実施又は試験において使用できるが、例示的な方法及び／又は材料が。以下に記載される。対立する場合には、定義を含み本願明細書が制御する。さらに、材料、方法、及び例は、単に説明のためであり、必ずしも限定であることを意図しない。
【図面の簡単な説明】
【００１７】
本発明の幾つかの実施形態が、単に例として、添付の図面を参照してここで説明される。以下に特に図面を詳細に参照すると、図示の事項は例であり、本発明の実施形態の説明のための議論を目的とすることが強調される。これに関して、図面と共に取り入れられる説明は、本発明の実施形態がどのように実施されるかを当業者に明らかにする。
【００１８】
以下の図面がある。
【図１】本発明の幾つかの実施形態による、K−Best最適化に従い、受信信号を値セットの最小値として決定する処理を概略的に表すフローチャートである。
【図２】本発明の幾つかの実施形態による、K−Bestシリアル（K−Best  Serial、KBS）ツリーの例示的な最上位レベル設計の概略図である。
【図３】本発明の幾つかの実施形態による、例示的なKBSレイヤ設計の概略図である。
【図４】本発明の幾つかの実施形態による、例示的な詳細KBSレイヤ設計の概略図である。
【図５Ａ】本発明の幾つかの実施形態による、アイドル周期を有しない最小値／最大値発見処理の概略テーブルである。
【図５Ｂ】本発明の幾つかの実施形態による、アイドル周期を有する最小値／最大値発見処理の概略テーブルである。
【図６】本発明の幾つかの実施形態による最小値／最大値発見処理の構造の概略図である。
【図７】本発明の幾つかの実施形態による最小値／最大値発見処理におけるMUX単位の構造の概略図である。
【図８】本発明の幾つかの実施形態による、KBSの例示的な最上位レベルタイミングの概略図である。
【図９】本発明の幾つかの実施形態による、KBSの例示的なレイヤタイミングの概略図である。
【発明を実施するための形態】
【００１９】
本発明は、その幾つかの実施形態において、複数入力単一バッファ処理に関し、より詳細には、排他的ではなく、K−Bestアルゴリズムに基づく多入力多出力（multiple  input  multiple  output、MIMO）デコーダアーキテクチャに関する。
【００２０】
本発明の幾つかの実施形態によると、レジスタ内の第１値セットを処理すると同時に次の処理のために同じレジスタに次の値セットをロードするメカニズムが提供される。これは、２重バッファの必要を取り除き、したがって、１つのレジスタのみが２重レジスタの代わりに使用される。これは、空間を削減し（つまり小面積）及び／又は遅延を最小化する。
【００２１】
本発明の実施形態は、現在２重バッファ又は複数バッファを用いて実行されている、種々の処理タスクのためのコンピュータ性能及び／又はハードウェア設計を向上するために実施され得る。
【００２２】
幾つかの実施形態によると、受信信号の第１値セットがレジスタにロードされ、最小値及び最大値の両方が識別される。次に、レジスタ内の最大値は第２値セットの値により置き換えられ、同時に、最小値は最小値に基づき計算された新しい値により置き換えられて、更新第１値セットが形成される。この処理は、更新第１値セットの全ての値が第２セットの値により置き換えられるまで繰り返され、第１セットの最小数の値が発見される。これは、次に、受信信号の全ての値セットについて繰り返されて良い。
【００２３】
直交周波数分割多重化（orthogonal  frequency−division  multiplexing、OFDM）通信に基づく信号及び任意でMIMOデコーダの文脈では、値セットの各々は、受信信号の異なるサブキャリア（subcarrier、SC）に関連する。このメカニズムは、K−Bestアルゴリズムの部分として実装されて良く、各レイヤについて、部分ユークリッド距離（partial  Euclidean  distances、PED）のK個の最小値が発見される。このメカニズムは、単一ハードウェア段により現在ツリーレイヤのK個の新しい子を生成するために同じ回路の再使用に基づき必要なロジック、面積、及び電力を有意に削減する最適領域K−Bestツリーレイヤ構造を含む。当該設計は、K個の初期コストを計算するためにハードウェアループをK回起動することにより、変更を伴わず選択されたKに調整され得る。
【００２４】
任意で、第１最大値を発見する前に、第１最小値が新しい値により置き換えられるアイドル周期が実行される。これは、各値が全ての他の値と比較することを可能にし、したがって選択された値が正しい。
【００２５】
任意で、共に同じレジスタ内に存在する値セット間の混合を防ぐために、強制ロジックメカニズムが実施されて、更新第１値セットの全ての値が第２セットの値により置き換えられるまで、第２セットの値が最小値又は最大値として選択されることを防ぐ。
【００２６】
他の実施形態によると、他の値が発見されて良く、及び／又は他の計算が実行されて、例えば値セットの中の値の平均を求める。
【００２７】
本発明の少なくとも１つの実施形態を詳細に説明する前に、本発明は、必ずしもその用途において、以下の記載において説明された及び／又は図面及び／又は例に示されたコンポーネント及び／又は方法の構成及び配置の詳細に限定されないことが理解されるべきである。本発明は、他の実施形態又は種々の方法で実施され又は実行されることが可能である。
【００２８】
本発明は、システム、方法、及び／又はコンピュータプログラムプロダクトであって良い。コンピュータプログラムプロダクトは、プロセッサに本発明の態様を実施させるためのコンピュータ可読プログラム命令を有するコンピュータ可読記憶媒体（又は複数の媒体）を含み得る。
【００２９】
コンピュータ可読記憶媒体は、命令実行装置による使用のために命令を保持し格納可能な有形装置であり得る。コンピュータ可読記憶媒体は、例えば、限定ではないが、電子記憶装置、磁気記憶装置、光学的記憶装置、電磁気記憶装置、半導体記憶装置、又は前述の任意の適切な組合せであって良い。
【００３０】
ここに記載されるコンピュータ可読プログラム命令は、コンピュータ可読記憶媒体から個々のコンピューティング／処理装置に、又はネットワーク、例えばインターネット、ローカルエリアネットワーク、広域ネットワーク、及び／又は無線ネットワークを介して外部コンピュータ若しくは外部記憶装置にダウンロードされ得る。
【００３１】
コンピュータ可読プログラム命令は、完全にユーザのコンピュータで、部分的にユーザのコンピュータで、スタンドアロン型ソフトウェアパッケージとして、部分的にユーザのコンピュータで及び部分的にリモートコンピュータで、又は完全にリモートコンピュータ若しくはサーバで、実行されて良い。後者のシナリオでは、リモートコンピュータは、ローカルエリアネットワーク（local  area  network、LAN）又は広域エリアネットワーク(wide  area  network、WAN)を含む任意の種類のネットワークを通じてユーザのコンピュータに接続されて良く、或いは（例えば、インターネットサービスプロバイダを用いてインターネットを通じて）外部コンピュータへの接続が生成されて良い。幾つかの実施形態では、例えばプログラマブル論理回路、フィールドプログラマブルゲートアレイ（field−programmable  gate  arrays、FPGA）、又はプログラマブルロジックアレイ（programmable  logic  arrays、PLA）を含む電子回路は、本発明の態様を実行するために、コンピュータ可読プログラム命令の状態情報を利用して電子回路をパーソナライズすることにより、コンピュータ可読プログラム命令を実行して良い。
【００３２】
本発明の態様は、本発明の実施形態による方法、機器（システム）及びコンピュータプログラムプロダクトのフローチャート図及び／又はブロック図を参照してここに記載される。フローチャート図及び／又はブロック図の各々のブロック、及びフローチャート図及び／又はブロック図のブロックの組合せは、コンピュータ可読プログラム命令により実装され得ることが理解される。
【００３３】
図中のフローチャート及びブロック図は、本発明の種々の実施形態に従うシステム、方法、及びコンピュータプログラムプロダクトの可能な実装のアーキテクチャ、機能、及び動作を示す。これに関し、フローチャート又はブロック図の各々のブロックは、特定の論理機能を実装するために１又は複数の実行可能命令を有するモジュール、セグメント、又は命令の一部、を表し得る。幾つかの代替の実施形態では、ブロックの中に記される機能は、図に示した順序と異なって生じて良い。例えば、連続して示される２つのブロックは、実際には、実質的に同時に実行されて良く、或いは、これらのブロックは、含まれる機能に依存して、時には、逆の順序で実行されて良い。留意すべきことに、ブロック図及び／又はフローチャート図の各々のブロック、及びブロック図及び／又はフローチャート図のブロックの組み合わせは、特定の機能又は動作を実行する、又は特定目的ハードウェア及びコンピュータ命令の組み合わせを実行する専用ハードウェアに基づくシステムにより実施され得る。
【００３４】
ここで図面を参照すると、図１は、本発明の幾つかの実施形態による、K−Best最適化に従い、受信信号を値セットの最小値として決定する処理を概略的に表すフローチャートである。
【００３５】
K−Bestアルゴリズムは、PED（コスト（cost）としても参照される）の最小値を発見するための最も良く知られているほぼ最適なソリューションのうちの１つである。K−Bestでは、最適全数検索（最大尤度（maximum  likelihood、ML）検出問題）は、アルゴリズムの各段階でストリーム当たりの可能な選択肢の数がKまで削減される反復検索により置き換えられ、各「父親」から最低コスト値の「子」を選択する。Kは、所要システム性能に従い選択される。この技術は、最適デコーダの複雑性より遙かに少ない複雑性により、非常の良好な性能を達成可能である。
【００３６】
先ず、任意で、１０１に示すように、デコーダへの入力が受信される。入力は、例えばMIMO信号であって良い。信号は、FFTブロックからデコーダへ転送され、ベクトルyにより表される。チャネル行列Hがチャネル推定ブロックから受信される。Nrxが受信アンテナ数（Hの行の数）であり、Nstが送信アンテナ数（Hの列の数）であるとき、HはサイズがNrx＊Nstであり、８でもある。Nrxはyのサイズでもある。デコーダは、例えばそれぞれ直交振幅変調（quadrature  amplitude  modulation、QAM）又は位相偏移キーイング（phase−shift  keying、PSK）変調で変調されたベクトルシンボルを復元する。
【００３７】
K−Bestアルゴリズムは、非常に複雑なツリーのような処理を要求する。例えば、２５６QAM変調を有する８×８実数MIMOデコーダでは（２＊L＝８、ここでL＝４は虚数（image）ビット及び実数（real）ビットの数である）、ツリー及びLビットコンステレーションにL２＊８個のレイヤがある。各レイヤは、K（例えば３２）個のPED（又はコスト）及びコンステレーションヒストリ（constellation  history、SH）を前のレイヤから受信する。SHはそれぞれ（n＋１）＊L個のビットであり、ここでnはレイヤ番号（例えば、１６、０〜１５）である。各レイヤは、PED及びコンステレーションのK＊２L＝５１２個の候補を計算し、最小限のK個のPED及びそれらの関連SHを選択して次のレイヤへ転送する。各選択されたコンステレーションｓは、自身の選択されたSHに連結される。例えば、K＝３２、L＝４、及びn＝７では、それぞれ３２ビット（＝４＊（７＋１））の３２個のSHがある。QAM２５６変調では、SC当たりビット数（Nbpsc）は８である。したがって、各ツリーレイヤで、５１２個のコストが計算されなければならず、そのうち最低３２個が選択されなければならない。
【００３８】
任意で、既知のSchnorr−Euchner法に基づき計算及びコスト候補生成の量を削減するために、選択計算が行われる（例えば、Mondal,  S.,  Eltawil,  A.,  Shen,  C.及びSalama,  K.  (２０１０)  Design  and  Implementation  of  a  Sort−Free  K−Best  Sphere  Decoder、IEEE  Transactions  on  Very  Large  Scale  Integration  (VLSI)  Systems,  １８,  １４９７−１５０１、特に図３を参照）。各発見した最小値について、その（大きな）子孫が計算され、残りの３１個の候補に対して比較される、等である。この方法では、２K−１個のコストだけが計算される。例えば、K＝３２では、候補の数は５１２（１６＊K）から６３に削減される。５１２個から３２個の最小値の代わりに、１つの最小値が、３２回の間、３２から発見される。
【００３９】
任意で、１０２に示すように、Hに対して前処理が実行される。例えば、これは、再順序付けブロックによりHを再構成し、HをH＝Q＊Rに分解することを含み得る。ここで、Rは上三角であり、Qは単位である。
【００４０】
図２を参照すると、本発明の幾つかの実施形態による、K−Bestシリアル（K−Best  Serial、KBS）ツリーの例示的な最上位レベル設計の概略図である。図中、線の太さは転送されるビットの数を表す。ツリーは４×４行列（８個のツリーレイヤ）について例示される。高速フーリエ変換（Fast  Fourier  transform、FFT）出力は、メモリy０−y７（受信アンテナ当たり２個のメモリ）へ転送される。本例では、yは１５ビットのサイズである。（再順序付けH行列からの）R行列は、１／Rも共に、メモリ行０−行７（各R行は別個のメモリである）に保存される。これは、レイヤ内の計算を簡略化するために行われる。本例では、各Rnmは１１ビットのサイズであり、１／Rは１６ビットのサイズである、乗算において一層の精度を可能にする。Rnmは、対角要素ｒまで（含まず）行列Rの行nを含む。
【００４１】
レイヤ０は、メモリy０−y７から入力を受信し、第１子コストを計算する。次に、各ツリーレイヤは、前のコスト（previous  costs、PC）及びSH（レイヤ毎に４ビットがSHに追加される）を前のレイヤから受信する。各レイヤで、コストの最小値及び最大値を発見するメカニズムが適用される。
【００４２】
図３を参照すると、本発明の幾つかの実施形態による、レイヤL＝５についての例示的なKBSレイヤ設計の概略図である。図４を参照すると、本発明の幾つかの実施形態による、L＝５のときの例示的な詳細KBSレイヤ設計の概略図である。レイヤ番号L（０〜７）は、SHのサイズ（＝４＊L）及びRnmのサイズ（＝１１＊L）を決定する。これらの図中、太線は、サンプラレジスタが含まれることを示す。図は、主レジスタ（REG３２）及び最小発見回路がK回再使用されるので、最小面積設計を示し、したがって、各々の次の子毎に本ハードウェアを複製する必要を除去する。
【００４３】
１０３に示すように、第１値セットがレジスタ（REG３２）にロードされる。値は第１サブキャリアSC_０に対応する。本例では、３２個の値は、各値が７８ビットのサイズであり、Math_Bブロックにより計算され、レジスタに書き込まれる。
【００４４】
次に、１０６に示されるように、例えば、図４にレジスタの上方に示されるMUXブロックを用いて、第１値セットの最大値及び最小値が識別される。最小値はMath_Cに出力される。
【００４５】
次に、１０７に示されるように、（レジスタ内の位置Kmaxにある）最大値は、次のSCに属する新しいエントリにより置き換えられ、同時に（レジスタ内の位置Kminにある）最小値は、Math_Cにより計算された自身の子孫により置き換えられて、現在のSCの更新第１値セットを生成する。Math_CからKminへの書き込みは、処理の周波数を決定するクリティカルパスである。
【００４６】
次に、１０８に示されるように、処理は、更新第１セット（現在のSC）の全ての値が次のSCの新しいエントリにより置き換えられるまで、繰り返される。
【００４７】
最小値を発見するのと同時に、最大値も発見される。その位置は、Next_SCフィリングフェーズでNext_SCコストのうちの１つを格納するために使用される。これは、本工程の最小遅延、及びSCレートの観点で一層高いスループットをもたらす。サブキャリアを入力するレートはf／（３＋K）であり、ここで、fは動作周波数である。例えば、f＝１GHz及びK＝３２では、SCレートは２８．５７ＭSC／Ｓｅｃである。同時工程を有しなければ、SCレートはこの数値の半分、〜１４ＭSC／Ｓｅｃである。
【００４８】
図５Ａ及び図５Ｂを参照すると、それぞれ、本発明の幾つかの実施形態による、アイドル（idle）周期（cycle）を有しない／有する最小値／最大値発見処理の概略テーブルである。太字でマークされた数値は、発見された最小コストである。表の上にある数値は、必要なとき及び場合にのみ計算されるべき将来の次のコスト（next  cost、NC）を告げる。「X」は、発見された最大値の場所に書き込まれ現在SC最小値／最大値発見から除外されたNext_SCコストである。
【００４９】
任意で、アイドル周期は、第１最大値を発見する前に追加される。１０４に示されるように、第１最小値が識別され、１０５に示されるように自身の子孫により置き換わる。これは、全ての値を全ての他の値と比較させることを可能にする。図５Ａに示されるように、K個の周期のみを含み（K＝４）、選択されたコストは最低ではない。図５Ｂに示されるように、アイドル周期がMAX経路の始め及びMIN経路の終わりに追加される。したがって、処理はK＋１周期（０〜４）を行う。時間５で、Next_SC処理が開始する。
【００５０】
時間＃０で、発見された最小値は２であり（これはMINへ出力される）、１７がそのＮＣとして計算され、２の代わりに書き込まれる。
【００５１】
時間＃１で、発見された最小値は５であり（これはMINへ出力される）、８がそのＮＣとして計算され、５の代わりに書き込まれる。並行して、１７は発見された最大値であり、したがって、次のSCのコストはそれを上書きしている（Xとして示される）。
【００５２】
時間＃２で、発見された最小値は６であり（これはMINへ出力される）、９がそのＮＣとして計算され、６の代わりに書き込まれる。並行して、８は発見された最大値であり、したがって、次のSCのコストはそれを上書きしている（Xとして示される）。
【００５３】
時間＃３で、最後の発見された最小値は７である（これはMINへ出力される）。並行して、９は発見された最大値であり、したがって、次のSCのコストはそれを上書きしている（Xとして示される）。
【００５４】
時間＃４で、このSCの最後の周期である。次のSCの最後のコストは、値７を上書きしている。したがって、K個の最小値が定められる。K＋１個の周期の終わりに、（１６＊K＝５１２個の可能な値から）K個の最小値が次のツリーレイヤへ配信され、REG３２は次のSCのK個の新しい候補（＝X２）で満たされる。
【００５５】
時間＃５で、次のSC処理が開始する。
【００５６】
図６を参照すると、本発明の幾つかの実施形態による最小値／最大値発見処理の構造の概略図である。示される各ユニットは、単純な２値比較器であり、（和ではなく）桁上げのみが使用される単純な加算器により構成される。ユニットはMUXとして参照される。処理の各段階で、MUXユニットは、各２つの値の最小値及び最大値を選択し、結果を次のMUXへ転送する。図７も参照すると、本発明の幾つかの実施形態による、L＝５のときの最小値／最大値発見処理におけるMUXユニットの構造の概略図である。MUXユニットは、nで番号付けされ（n＝０〜n＝３１）、nがKmin又はKmaxに等しくないとき、それらのREG３２エントリを変更しない。
【００５７】
任意で、最小値／最大値発見処理は、新しいSC値が処理に加わることを防ぐ制御ロジックを含む。これは、両方のSCコスト候補がREG３２に一緒に存在するために必要である。例えば、処理中のSC_０及びSC_１が満たされる。Force_REG_０〜Force_REG_４は、MUXに、新しいSC値を無視するよう指示する。カウンタ０〜３０は、New_Scが処理を開始すると、Force_REGをリセットする。各関連Force_REGは、Kmaxを入力として受信し、関連MUXに追加された新しい値を無視し及び他の値を選択するよう指示する。両方の値が無視されるべきであるとき、次のForce_REGは、次のMUXに現在のMUXからの入力を無視するよう指示する。例えば、Kmax＝３のとき、REG３の値（これは既に次のSCにより占有されている）に無関係に、REG３入力は、最大値及び最小値の両方のために次の最小値／最大値レイヤへの出力として、REG２入力を強制的に選択させることにより、現在の最小値／最大値処理から除去される。これは、Force_REG_０の出力Force_NM_１／２（図示しない）により行われる。次の周期で、Kmax＝２のとき、REG２入力が除去される。ボックスMin／Max１への両方の入力が除去されるべきなので、これは、Force_REG_１により制御される次のレイヤで、Min及びMaxの両方について行われる。これは、出力Force_max_１６及びForce_min_１６により達成される。処理は、最小値／最大値メカニズムの５レイヤ下へ続く。
【００５８】
図８を参照すると、本発明の幾つかの実施形態による、KBSの例示的な最上位レベルタイミングの概略図である。１つのSCがそのツリー通過を、レイヤ当たり３５周期の、３１５周期以内に完了する。図９も参照すると、本発明の幾つかの実施形態による、KBSの例示的なレイヤタイミング（レイヤ０ではない）の概略図である。SC_０のフィリングフェーズはK（＝３２）クロック周期を要し、その後、図示のように、最小値／最大値処理はSC_０について、並行してSC_１フィリングフェーズを開始する（両方とも次の３２個のクロック周期３３〜６４の間に実行される）。
【００５９】
Math_Aは、Kmax位置でREG３２を更新するMath_Bを導出し、Math_CはKmin位置でREG３２を更新する。並列化は、主要な遅延削減要因であり、６４周期の代わりに、SC当たり３５周期がある（最小値／最大値段は３２周期＋１Math_A周期＋１IDLE周期＋Out  REG周期を要する）。
【００６０】
本発明の種々の実施形態の記載は、説明の目的で提示されたが、包括的であることを意図せず又は開示された実施形態に限定されない。多くの変更及び変形が、記載された実施形態の範囲及び精神から逸脱することなく、当業者に明らかである。ここで使用される用語は、実施形態の原理、実際の用途又は市場に見られる技術に優る技術的向上を最適に説明するために、又は当業者がここに開示された実施形態を理解できるようにするために、選択された。
【００６１】
本願から成熟する特許の寿命の間、多くの関連信号デコーダが開発されることが予想され、用語信号デコーダの範囲は推測的に全てのこのような新技術を包含することが意図される。
【００６２】
用語「含む」、「含む」、「有する」及びそれらの活用は、「含むが限定されない」を意味する。この用語は、用語「から成る」及び「基本的に〜から成る」を包含する。
【００６３】
ここで用いられるように、単数形「１つ」、「１つ」、及び「その」は、特に文脈上明示されない限り、複数への参照も含む。例えば、用語「化合物」又は「少なくとも１つの化合物」は、それらの混合物を含む複数の化合物を含み得る。
【００６４】
語「例示的な」は、「一例、例、又は説明を提供する」ことを意味するために本願明細書で用いられる。「例示的な」として記載される任意の実施形態は、必ずしも、他の実施形態より好適である又は有利であると考えられず及び／又は他の実施形態からの特徴の組み込みを排除しない。
【００６５】
語「任意的な」は、「幾つかの実施形態において提供され、他の実施形態で提供されない」ことを意味するために、本願明細書で用いられる。本発明の任意の特定の実施形態は、そのような特徴が対立しない限り、複数の「任意的な」特徴を含み得る。
【００６６】
本願を通じて、本発明の種々の実施形態が範囲形式で提示され得る。理解されるべきことに、範囲形式の記載は、単に便宜及び簡潔さのためであり、本発明の範囲に対する柔軟性のない限定として考えられるべきではない。したがって、範囲の記載は、全ての可能な下位範囲、並びに該範囲内にある個々の数値を具体的に開示しているものと考えられるべきである。例えば、１乃至６のような範囲の記載は、１乃至３、１乃至４、１乃至５、２乃至４、２乃至６、３乃至６、等のような下位範囲、並びに該範囲内の個々の数、例えば１、２、３、４、５、及び６を具体的に開示していると考えられるべきである。これは、範囲の幅に拘わらず適用される。
【００６７】
数値範囲が本願明細書に示されるときはいつも、示された範囲内の任意の前述の数（分数又は整数）を含むことを意味する。語句、第１指示数と第２指示数との「間に分布する／の範囲」、及び第１指示数から第２指示数「まで分布する／の範囲」は、本願明細書で同義的に使用され、第１及び第２指示数並びにそれらの間の全ての分数及び整数を含むことを意味する。
【００６８】
明確さのために別個の実施形態の文脈で記載された本発明の特定の特徴は、単一の実施形態の中で組み合わせて提供されても良いことが理解される。反対に、簡潔さのために単一の実施形態の文脈で記載された本発明の種々の特徴は、別個に又は任意の適切な小結合において、又は本発明の任意の他の記載された実施形態において適切であるとき提供されても良い。種々の実施形態の文脈で記載された特定の特徴は、実施形態がこれらの要素無しで動作不能でない限り、これらの実施形態の基本的特徴と考えられない。
【００６９】
本願明細書で言及される公報、特許、及び／又は特許出願は、参照により、各々個々の公報及び／又は特許出願が具体的に及び個々に参照により本願明細書に組み込まれるべきであると示されるように同程度に、それらの全体が本願明細書に組み込まれる。さらに、本願における任意の参照の引用又は特定は、このような参照が本発明に対して従来技術として利用可能であることの許可として考えられるべきではない。見出しが使用される範囲で、それらは必ずしも限定として考えられるべきではない。
【図１】
2020511014.tif 000003
【図２】
2020511014.tif 000004
【図３】
2020511014.tif 000005
【図４】
2020511014.tif 000006
【図５Ａ】
2020511014.tif 000007
【図５Ｂ】
2020511014.tif 000008
【図６】
2020511014.tif 000009
【図７】
2020511014.tif 000010
【図８】
2020511014.tif 000011
【図９】
2020511014.tif 000012
【国際調査報告】
2020511014.tif 000013