線形システム解法のためのアレイ処理
【課題】本発明は、線形システムを解くためのアレイ処理の方法を提供する。
【解決手段】線形システムを解くためにＰＥ（５４〜５４Ｎ）を利用する。本発明の一実施形態（図３ｂ）では、コレスキーファクタを判定するため、行列の対角要素がスカラーＰＥに射影される。別の実施形態では、コレスキーファクタを判定するため、２次元スカラーアレイが使用される。限られたバンド幅をもつ行列の場合、使用するプロセッサの数を減らした、プロセッサ（５４〜５４Ｎ）を用いることができる。
【解決手段】線形システムを解くためにＰＥ（５４〜５４Ｎ）を利用する。本発明の一実施形態（図３ｂ）では、コレスキーファクタを判定するため、行列の対角要素がスカラーＰＥに射影される。別の実施形態では、コレスキーファクタを判定するため、２次元スカラーアレイが使用される。限られたバンド幅をもつ行列の場合、使用するプロセッサの数を減らした、プロセッサ（５４〜５４Ｎ）を用いることができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、線形システムの解法に関する。具体的には、本発明は、線形システムを解くためのアレイ処理の使用に関する。
【背景技術】
【０００２】
工学上の問題を解くのに、線形システム解法が用いられることが多い。このような課題の１つに、ＴＤＤ（time division duplex）通信において、ＣＤＭＡ（code division multiple access）を用いて、複数のユーザ信号をジョイントユーザ検出（joint user detection）することがある。このようなシステムにおいては、複数のユーザが、同じ固定継続時間間隔（タイムスロット）で、同時に複数の通信バーストを伝送する。マルチプルバーストは、異なる拡散符号を用いて伝送される。伝送中、各バーストはチャネルレスポンスを経験する。伝送されたバーストからデータを復元するための１つのアプローチが、ジョイント検出（joint detection）であり、このアプローチでは、全てのユーザデータが同時に受信される。このようなシステムを図１に示す。ＵＥ（user equipment）または基地局において、ジョイント検出レシーバを使用することができる。
【０００３】
マルチプルバースト９０は、チャネルレスポンスを経験した後、コンバイン受信信号（combined received signal）として、アンテナ９２またはアンテナアレイで受信される。受信信号は、デモジュレータ９４などによって、ベースバンドに変換され、受信ベクトルｒを生成するため、１つのＡＤＣ（analog to digital converter）９６または複数のＡＤＣなどによって、符号の１チップレートまたは符号の複数チップレートでサンプリングされる。チャネル推定デバイス９８は、通信バーストのトレーニング系列の一部を使用して、バースト９０のチャネルレスポンスを推定する。ジョイント検出器１００は、各ユーザのバーストの推定または既知の拡散符号と、推定または既知のチャネルレスポンスとを使用して、全てのユーザの元の伝送データをデータベクトルｄとして推定する。
【０００４】
ジョイント検出問題は、一般に、式１によってモデル化される。
【０００５】
Ａｄ＋ｎ＝ｒ 式１
【０００６】
ｄは伝送データベクトル、ｒは受信ベクトル、ｎはＡＷＧＮ（additive white gaussian noise）であり、Ａはチャネルレスポンスを既知の拡散符号を用いて畳み込むことによって構成されるＭ×Ｎ行列である。
【０００７】
式１を解くための２つのアプローチに、ゼロフォーシング（ＺＦ）およびＭＭＳＥ（Minimum Mean Square Error）アプローチがある。ｎを０に接近させるＺＦ解法は、式２による。
【０００８】
ｄ＝（ＡHＡ）-1ＡHｒ 式２
【０００９】
ＭＭＳＥアプローチは、式３および式４による。
【００１０】
ｄ＝Ｒ-1ＡHｒ 式３
Ｒ＝ＡHＡ＋σ2Ｉ 式４
【００１１】
σはノイズｎの分散であり、Ｉは単位行列である。
【００１２】
拡散符号、チャネルレスポンスと、ノイズの分散の平均は、推定されるか、または既知であり、受信ベクトルは既知であるので、唯一の未知の変数は、データベクトルｄである。行列の直接逆変換といった力ずくの解法は、どちらのアプローチによるとしても、極めて複雑である。この複雑さを緩和するための１つの技法に、コレスキー分解（Cholesky decomposition）がある。コレスキーのアルゴリズムは、
【００１３】
【数１】
【００１４】
またはＲなどの対称正定値行列を、式５によって、下三角行列Ｇと上三角行列ＧHに因数分解する。
【００１５】
【数２】
【００１６】
対称正値行列
【００１７】
【数３】
【００１８】
は、式６によって、Ａにその共役転置（エルミート）行列ＡHを乗算することによって、Ａから生成することができる。
【００１９】
【数４】
【００２０】
【数５】
【００２１】
は、簡単に式７によって定義される。
【００２２】
【数６】
【００２３】
その結果、式１は、ＺＦでは式８として、ＭＭＳＥでは式９として、書き換えられる。
【００２４】
【数７】
【００２５】
【数８】
【００２６】
式８または式９を解くため、式１０によってコレスキーファクタ（Cholesky factor）が用いられる。
【００２７】
【数９】
【００２８】
変数ｙは式１１によって定義される。
【００２９】
ＧHｄ＝ｙ 式１１
【００３０】
変数ｙを使用して、式１０は式１２として書き換えられる。
【００３１】
【数１０】
【００３２】
データベクトルを取得するための複雑さの大半は、３つのステップで実行される。第１のステップで、式１３に示すように、
【００３３】
【数１１】
【００３４】
またはＲなどの派生対称正値行列からＧが生成される。
【００３５】
【数１２】
【００３６】
Ｇを用い、式１４に示すように、式８においてＧの前進代入（forward substitution）を使用してｙを解く。
【００３７】
【数１３】
【００３８】
Ｇの共役転置行列ＧHを用い、式１５に示すように、式１１において後退代入（backwardsubstitution）を使用してｄを解く。
【００３９】
ｄ＝ＢＡＣＫＷＡＲＤ ＳＵＢ（ＧH，ｙ） 式１５
【００４０】
式１３によってコレスキーファクタＧを判定するアプローチは、
【００４１】
【数１４】
【００４２】
またはＲに関して示された以下のアルゴリズムとするが、Ｒに関しては類似のアプローチも用いられる。
【００４３】
【数１５】
【００４４】
ａd,eは行列
【００４５】
【数１６】
【００４６】
またはＲのｄ行ｅ列の要素を表す。「：」は「ｊからＮまで」などの「まで」演算子を示し、（・）Hは共役転置（エルミート）演算子を示す。
【００４７】
コレスキーファクタを求解するための別のアプローチでは、Ｎ個の並列ベクトルベースプロセッサが使用される。各プロセッサは、
【００４８】
【数１７】
【００４９】
またはＲ行列の列にマップされる。各プロセッサの列は、変数μによって定義され、μ＝１：Ｎである。並列プロセッサに基づくサブルーチンは、μ＝１：Ｎとした場合の以下のサブルーチンとして考察することができる。
【００５０】
【数１８】
【００５１】
ｒｅｃｖ（・,left）は左側のプロセッサ演算器からの受信であり、ｓｅｎｄ（・,right）は右側のプロセッサ演算器への伝送であり、ｇK,Lは隣接プロセッサからの値である。
【００５２】
このサブルーチンは、図２ａ〜図２ｈを用いて図説される。図２ａは、ジョイント検出器のベクトルプロセッサとその関連メモリセルのブロック図である。各プロセッサ５０1から５０N（５０）は、行列の列に対して演算を行う。Ｇ行列は下三角行列であり、
【００５３】
【数１９】
【００５４】
またはＲは下三角行列によって完全に定義されるので、下三角行列の要素ａk,lだけが使用される。
【００５５】
図２ｂおよび図２ｃには、プロセッサの下側のセル上で、プロセッサによって実行され得る２つの機能が示されている。図２ｂでは、下向き三角形で表される機能５２が、μ番目のプロセッサ５０の下側のセル（ａμμからａNμ）上で、式１６および式１７を実行する。
【００５６】
【数２０】
【００５７】
ａμ:N,μ：＝ν 式１７
【００５８】
「←」は同時代入を示し、「：＝」は逐次代入を示し、νは右側のプロセッサに伝送される値である。
【００５９】
図２ｃでは、右向き三角形で表される機能５２が、μ番目のプロセッサ５０の下側のセル上で、式１８および式１９を実行する。
【００６０】
ν←ｕ 式１８
ａμ:N,μ：＝ａμ:N,μ−νμνμ:N 式１９
【００６１】
νkは、第ｋ番目のプロセッサ５０の右側に出ていく値に関係付けした値を示す。
【００６２】
図２ｄ〜図２ｇには、４×４ Ｇ行列に対して実行されるデータフローと機能が示されている。処理のステージ１から４までに対しては、図２ｄ〜図２ｇに示すように、最も左側のプロセッサ５０がドロップアウトし、下向き三角形の機能５２が、左から右に移動していく。図２ｄ〜図２ｇをインプリメントするため、下向き三角形は、プロセッサを物理的に右向きに置き換えることができ、または下向き三角形の機能を担うことによって、プロセッサをバーチャルに右向きに置き換えることができる。
【００６３】
これらエレメント（element）は、ステージ１を表す図２ｈに示すように、（（Ｎ−４）個の）プロセッサ５０を第４番目のプロセッサ５０4の右側に追加し、プロセッサ５０の各々に行列の対角より下方の（Ｎ−４個の）セルを追加することによって、Ｎ×Ｎ行列とＮ個のプロセッサ５０に拡張可能である。このような構成による処理はＮステージにわたって実行される。
【００６４】
このようなコレスキー分解のインプリメントは、ベクトルプロセッサを用いるにしても、スカラーＰＥへの直接分解を用いるにしても、各ステージの処理の後で、大量の処リソースがアイドル状態になるため、効率的ではない。
【発明の概要】
【発明が解決しようとする課題】
【００６５】
したがって、線形システムを解くための代替アプローチを有するのが望ましい。
【課題を解決するための手段】
【００６６】
線形システムを解くためにＰＥが利用される。本発明の一実施形態では、コレスキーファクタを判定するため、行列の対角の行列要素がスカラーＰＥに射影される。別の実施形態では、２次元スカラーアレイを用いて、コレスキーファクタを判定する。第３の実施形態では、再構成可能スカラー線形アレイを用いて、コレスキーファクタを判定し、前進代入および後退代入を実行する。行列が、限られたバンド幅を有する場合は、これらの実施形態で使用されるプロセッサの数を減らすことができる。プロセッサのフォールディング（folding）を用いて、これらの実施形態で使用されるプロセッサの数を減らすことができる。本発明の別の実施形態は、コレスキーファクタを判定し、前進代入および後退代入を実行するように再構成できるＰＥである。
【図面の簡単な説明】
【００６７】
【図１】ジョイント検出レシーバの簡略な図である。
【図２ａ】ベクトルプロセッサを用いてコレスキーファクタを判定する様子を示した図である。
【図２ｂ】ベクトルプロセッサを用いてコレスキーファクタを判定する様子を示した図である。
【図２ｃ】ベクトルプロセッサを用いてコレスキーファクタを判定する様子を示した図である。
【図２ｄ】ベクトルプロセッサを用いてコレスキーファクタを判定する様子を示した図である。
【図２ｅ】ベクトルプロセッサを用いてコレスキーファクタを判定する様子を示した図である。
【図２ｆ】ベクトルプロセッサを用いてコレスキーファクタを判定する様子を示した図である。
【図２ｇ】ベクトルプロセッサを用いてコレスキーファクタを判定する様子を示した図である。
【図２ｈ】ベクトルプロセッサを用いてコレスキーファクタを判定する様子を示した図である。
【図３ａ】コレスキー分解を実行するＮ個のスカラープロセッサの好ましい実施形態を示した図である。
【図３ｂ】コレスキー分解を実行するＮ個のスカラープロセッサの好ましい実施形態を示した図である。
【図４ａ】コレスキー分解のために３次元グラフを使用した一例を示した図である。
【図４ｂ】コレスキー分解のために３次元グラフを使用した一例を示した図である。
【図４ｃ】コレスキー分解のために３次元グラフを使用した一例を示した図である。
【図４ｄ】コレスキー分解のために３次元グラフを使用した一例を示した図である。
【図４ｅ】コレスキー分解のために３次元グラフを使用した一例を示した図である。
【図５ａ】コレスキー分解を実行するベクトルプロセッサをスカラープロセッサにマップする一例を示した図である。
【図５ｂ】コレスキー分解を実行するベクトルプロセッサをスカラープロセッサにマップする一例を示した図である。
【図５ｃ】コレスキー分解を実行するベクトルプロセッサをスカラープロセッサにマップする一例を示した図である。
【図５ｄ】コレスキー分解を実行するベクトルプロセッサをスカラープロセッサにマップする一例を示した図である。
【図５ｅ】コレスキー分解を実行するベクトルプロセッサをスカラープロセッサにマップする一例を示した図である。
【図６ａ】非バンド行列に関するスカラーアレイの処理フローを示した図である。
【図６ｂ】非バンド行列に関するスカラーアレイの処理フローを示した図である。
【図６ｃ】非バンド行列に関するスカラーアレイの処理フローを示した図である。
【図６ｄ】非バンド行列に関するスカラーアレイの処理フローを示した図である。
【図６ｅ】バンド行列に関するスカラーアレイの処理フローを示した図である。
【図６ｆ】バンド行列に関するスカラーアレイの処理フローを示した図である。
【図６ｇ】バンド行列に関するスカラーアレイの処理フローを示した図である。
【図６ｈ】バンド行列に関するスカラーアレイの処理フローを示した図である。
【図６ｉ】バンド行列に関するスカラーアレイの処理フローを示した図である。
【図６ｊ】バンド行列に関するスカラーアレイの処理フローを示した図である。
【図７】図４ａの射影をｋ軸に沿ってＮ×Ｎ行列に拡張した図である。
【図８ａ】２Ｄスカラーアレイ中のスカラープロセッサ間の遅延を利用した処理フローを示した図である。
【図８ｂ】２Ｄスカラーアレイ中のスカラープロセッサ間の遅延を利用した処理フローを示した図である。
【図８ｃ】２Ｄスカラーアレイ中のスカラープロセッサ間の遅延を利用した処理フローを示した図である。
【図８ｄ】２Ｄスカラーアレイ中のスカラープロセッサ間の遅延を利用した処理フローを示した図である。
【図８ｅ】遅延素子とその関連式を示した図である。
【図９ａ】図８ａ〜図８ｄのスカラープロセッサアレイの、４つのスカラープロセッサからなる１Ｄアレイへの射影を示した図である。
【図９ｂ】１つおきのプロセッサ間に遅延要素を有するスカラープロセッサアレイの、４つのスカラープロセッサからなる１Ｄアレイへの射影を示した図である。
【図９ｃ】１つおきのプロセッサ間に遅延要素を有するバンド行列のコレスキー分解に関する処理フローを示した図である。
【図９ｄ】１つおきのプロセッサ間に遅延要素を有するバンド行列のコレスキー分解に関する処理フローを示した図である。
【図９ｅ】１つおきのプロセッサ間に遅延要素を有するバンド行列のコレスキー分解に関する処理フローを示した図である。
【図９ｆ】１つおきのプロセッサ間に遅延要素を有するバンド行列のコレスキー分解に関する処理フローを示した図である。
【図９ｇ】１つおきのプロセッサ間に遅延要素を有するバンド行列のコレスキー分解に関する処理フローを示した図である。
【図９ｈ】１つおきのプロセッサ間に遅延要素を有するバンド行列のコレスキー分解に関する処理フローを示した図である。
【図９ｉ】１つおきのプロセッサ間に遅延要素を有するバンド行列のコレスキー分解に関する処理フローを示した図である。
【図９ｊ】１つおきのプロセッサ間に遅延要素を有するバンド行列のコレスキー分解に関する処理フローを示した図である。
【図９ｋ】１つおきのプロセッサ間に遅延要素を有するバンド行列のコレスキー分解に関する処理フローを示した図である。
【図９ｌ】１つおきのプロセッサ間に遅延要素を有するバンド行列のコレスキー分解に関する処理フローを示した図である。
【図９ｍ】１つおきのプロセッサ間に遅延要素を有するバンド行列のコレスキー分解に関する処理フローを示した図である。
【図９ｎ】１つおきのプロセッサ間に遅延要素を有するバンド行列のコレスキー分解に関する処理フローを示した図である。
【図９ｏ】バンド行列を処理する線形アレイのメモリアクセスを示した図である。
【図９ｐ】バンド行列を処理する線形アレイのメモリアクセスを示した図である。
【図９ｑ】バンド行列を処理する線形アレイのメモリアクセスを示した図である。
【図９ｒ】バンド行列を処理する線形アレイのメモリアクセスを示した図である。
【図９ｓ】バンド行列を処理する線形アレイのメモリアクセスを示した図である。
【図９ｔ】バンド行列を処理する線形アレイのメモリアクセスを示した図である。
【図９ｕ】バンド行列を処理する線形アレイのメモリアクセスを示した図である。
【図９ｖ】バンド行列を処理する線形アレイのメモリアクセスを示した図である。
【図９ｗ】バンド行列を処理する線形アレイのメモリアクセスを示した図である。
【図９ｘ】バンド行列を処理する線形アレイのメモリアクセスを示した図である。
【図９ｙ】バンド行列を処理する線形アレイのメモリアクセスを示した図である。
【図９ｚ】バンド行列を処理する線形アレイのメモリアクセスを示した図である。
【図１０ａ】スカラープロセッサがＮ個に拡張された、図９ａの射影されたアレイを示した図である。
【図１０ｂ】スカラープロセッサがＮ個に拡張された、図９ｂの射影されたアレイを示した図である。
【図１１ａ】除算の平方根をとる関数の図１０ａのアレイからの分離を示す図である。
【図１１ｂ】除算の平方根をとる関数の図１０ｂのアレイからの分離を示す図である。
【図１２ａ】各プロセッサ間で遅延要素を有する前進代入アレイの、４つのスカラープロセッサへの射影を示した図である。
【図１２ｂ】１つおきのプロセッサ間で遅延要素を有する前進代入アレイの、４つのスカラープロセッサへの射影を示した図である。
【図１２ｃ】前進代入に関する星型で表される関数によって実行される式を示した図である。
【図１２ｄ】前進代入に関するひし形で表される関数によって実行される式を示した図である。
【図１２ｅ】１つおきのプロセッサ間に同時代入を有するバンド行列の前進代入に関する処理フローを示した図である。
【図１２ｆ】１つおきのプロセッサ間に遅延要素を有するバンド行列の前進代入に関する処理フローを示した図である。
【図１２ｇ】１つおきのプロセッサ間に遅延要素を有するバンド行列の前進代入に関する処理フローを示した図である。
【図１２ｈ】１つおきのプロセッサ間に遅延要素を有するバンド行列の前進代入に関する処理フローを示した図である。
【図１２ｉ】１つおきのプロセッサ間に遅延要素を有するバンド行列の前進代入に関する処理フローを示した図である。
【図１２ｊ】１つおきのプロセッサ間に遅延要素を有するバンド行列の前進代入に関する処理フローを示した図である。
【図１２ｋ】バンド行列を処理する前進代入線形アレイのメモリアクセスを示した図である。
【図１２ｌ】バンド行列を処理する前進代入線形アレイのメモリアクセスを示した図である。
【図１２ｍ】バンド行列を処理する前進代入線形アレイのメモリアクセスを示した図である。
【図１２ｎ】バンド行列を処理する前進代入線形アレイのメモリアクセスを示した図である。
【図１２ｏ】バンド行列を処理する前進代入線形アレイのメモリアクセスを示した図である。
【図１２ｐ】バンド行列を処理する前進代入線形アレイのメモリアクセスを示した図である。
【図１３ａ】スカラープロセッサがＮ個に拡張された、図１２ａの射影されたアレイを示した図である。
【図１３ｂ】スカラープロセッサがＮ個に拡張された、図１２ｂの射影されたアレイを示した図である。
【図１４ａ】図１２ｂの射影されたアレイに関する処理フローを示した図である。
【図１４ｂ】図１２ｂの射影されたアレイに関する処理フローを示した図である。
【図１４ｃ】図１２ｂの射影されたアレイに関する処理フローを示した図である。
【図１４ｄ】図１２ｂの射影されたアレイに関する処理フローを示した図である。
【図１５ａ】各プロセッサ間で遅延要素を有する後退代入アレイの、４つのスカラープロセッサへの射影を示した図である。
【図１５ｂ】１つおきのプロセッサ間で遅延要素を有する後退代入アレイの、４つのスカラープロセッサへの射影を示した図である。
【図１５ｃ】後退代入に関する星型で表される関数によって実行される式を示した図である。
【図１５ｄ】後退代入に関するひし形で表される関数によって実行される式を示した図である。
【図１５ｅ】１つおきのプロセッサ間に同時代入を有するバンド行列の後退代入に関する処理フローを示した図である。
【図１５ｆ】１つおきのプロセッサ間に遅延要素を有するバンド行列の後退代入に関する処理フローを示した図である。
【図１５ｇ】１つおきのプロセッサ間に遅延要素を有するバンド行列の後退代入に関する処理フローを示した図である。
【図１５ｈ】１つおきのプロセッサ間に遅延要素を有するバンド行列の後退代入に関する処理フローを示した図である。
【図１５ｉ】１つおきのプロセッサ間に遅延要素を有するバンド行列の後退代入に関する処理フローを示した図である。
【図１５ｊ】１つおきのプロセッサ間に遅延要素を有するバンド行列の後退代入に関する処理フローを示した図である。
【図１５ｋ】バンド行列を処理する後退代入線形アレイのメモリアクセスを示した図である。
【図１５ｌ】バンド行列を処理する後退代入線形アレイのメモリアクセスを示した図である。
【図１５ｍ】バンド行列を処理する後退代入線形アレイのメモリアクセスを示した図である。
【図１５ｎ】バンド行列を処理する後退代入線形アレイのメモリアクセスを示した図である。
【図１５ｏ】バンド行列を処理する後退代入線形アレイのメモリアクセスを示した図である。
【図１５ｐ】バンド行列を処理する後退代入線形アレイのメモリアクセスを示した図である。
【図１６ａ】スカラープロセッサがＮ個に拡張された、図１５ａの射影されたアレイを示した図である。
【図１６ｂ】スカラープロセッサがＮ個に拡張された、図１５ｂの射影されたアレイを示した図である。
【図１７ａ】図１５ｂの射影されたアレイに関する処理フローを示した図である。
【図１７ｂ】図１５ｂの射影されたアレイに関する処理フローを示した図である。
【図１７ｃ】図１５ｂの射影されたアレイに関する処理フローを示した図である。
【図１７ｄ】図１５ｂの射影されたアレイに関する処理フローを示した図である。
【図１８ａ】分離された除算機能をもつ図１３ａ、図１６ａのアレイを示した図である。
【図１８ｂ】分離された除算機能をもつ図１３ｂ、図１６ｂのアレイを示した図である。
【図１９ａ】Ｇ、前進代入、および後退代入を判定するための再構成可能アレイを示した図である。
【図１９ｂ】Ｇ、前進代入、および後退代入を判定するための再構成可能アレイを示した図である。
【図２０ａ】除算および平方根をとる関数の再構成可能アレイからの分離を示す図である。
【図２０ｂ】除算および平方根をとる関数の再構成可能アレイからの分離を示す図である。
【図２１ａ】双方向フォールディングを示した図である。
【図２１ｂ】単方向フォールディングを示した図である。
【図２２ａ】Ｎ個のプロセッサを用いた双方向フォールディングの実施を示した図である。
【図２２ｂ】Ｎ個のプロセッサを用いた単方向フォールディングの実施を示した図である。
【図２３】簡単な再構成可能ＰＥの好ましいスライスを示した図である。
【発明を実施するための形態】
【００６８】
図３ａおよび図３ｂは、Ｇを取得するためコレスキー分解を行うＮ個のスカラーＰＥ５４1ないし５４N（５４）の好ましい実施形態を示す。簡略のため、４×４ Ｇ行列について説明し記述するが、このアプローチは、図３ａおよび図３ｂに示すように、任意に、４×４ Ｇ行列に拡張することができる。
【００６９】
図４ａは、上記のアルゴリズムをパフォームするための３次元計算依存グラフ（computational dependency graph）を示す。簡略のため、図４ａには、バンド幅が３である５×５行列の処理を示す。各ノードによりパフォームされる機能を、図４ｂ〜図４ｅに示す。図４ｂにおいて五角形で表す機能は、式２０および式２１を実行する。
【００７０】
【数２１】
【００７１】
ａout←ｙ 式２１
【００７２】
←は同時代入を示す。ａinは下位レベルから当該ノードへの入力であり、ａoutは上位レベルへの出力である。図４ｃは、式２２および式２３を実行する四角形で表される機能である。
【００７３】
ｙ←ｚ* 式２２
ａout←ａin−｜ｚ｜2 式２３
【００７４】
図４ｄは、式２４、式２５、および式２６を実行する八角形で表される機能である。
【００７５】
ｙ←ｗ 式２４
ｘ←ａin／ｗ 式２５
ａout←ｘ 式２６
【００７６】
図４ｅは、式２７、式２８、および式２９を実行する円で表される機能である。
【００７７】
ｙ←ｗ 式２７
ｘ←ｚ 式２８
ａout←ａin−ｗ×ｘ 式２９
【００７８】
図５ａは、４×４ Ｇ行列に対するベクトルベースのコレスキー分解のステージ１を、２次元スカラーベースアプローチにマップする様子を示した図である。各ベクトルプロセッサ５２、５４は、図５ａに示すように、少なくとも１つのスカラープロセッサ５６、５８、６０、６２にマップされる。各スカラープロセッサ５６、５８、６０、６２は、メモリセルａijに関係付けしてある。各プロセッサ５６、５８、６０、６２でパフォームされる機能が、図５ｂ〜図５ｅに示されている。図５ｂには、五角形で表される機能５６が示されており、これは式３０および式３１を実行する。
【００７９】
【数２２】
【００８０】
ａij：＝ｙ 式３１
【００８１】
：＝は逐次代入を示す。ｙは下側のプロセッサに伝送される値を示す。図５ｃには、八角形で表される機能５８が示されており、これは式３２、式３３、および式３４を実行する。
【００８２】
ｙ←ｗ 式３２
ｘ←ａij／ｗ 式３３
ａij：＝ｘ 式３４
【００８３】
ｗは上側のプロセッサから伝送された値を示す。図５ｄには、四角形で表される機能６０が示されており、これは式３５および式３６を実行する。
【００８４】
ｙ←ｚ* 式３５
ａij：＝ａij−｜ｚ｜2 式３６
【００８５】
ｘは右側のプロセッサに伝送される値を示す。図５ｅには、円で表される機能６２示されており、これは式３７、式３８、および式３９を実行する。
【００８６】
ｙ←ｗ 式３７
ｘ←ｚ 式３８
ａij：＝ａij−ｗ×ｚ 式３９
【００８７】
図６ａ〜図６ｄには、４つの逐次ステージ（ステージ１ないし４）における、プロセッサ５６、５８、６０、６２によるデータフローが示されている。図６ａ〜図６ｄに示すように、各ステージの後、プロセッサ５６、５８の列がドロップオフする。この処理には、４処理サイクルを必要とし、一般にはＮサイクルを必要とする。各ステージにつき１処理サイクルを必要とする。図５ａに示すように、４×４ Ｇ行列を判定するのに、１０個のスカラープロセッサを必要とする。Ｎ×Ｎ行列の場合、必要なプロセッサの数は、式４０による。
【００８８】
【数２３】
【００８９】
図６ｅ〜図６ｊには、５×５バンド行列に関する処理フローが示されている。アクティブなプロセッサを実線で示す。このバンド行列では、左下の３つのエントリ（ａ41、ａ51、ａ52、図６ｅ〜図６ｊでは図示せず）が０である。図６ｅに示すように、ステージ１では、上側の６つのプロセッサがオペレートしている。図６ｆに示すように、ステージ１でアクティブな６つのプロセッサが、ｇ11、ｇ21、ｇ31と、ステージ２で使用する３つの即値結果α22、α32、α33を決定する。
【００９０】
ステージ２では、６つのプロセッサ（α22，α32，α33，
【００９１】
【数２４】
【００９２】
）がオペレートしている。ステージ２では、図６ｇ（ステージ３）に示すように、ｇ22、ｇ32、ｇ42の値と、β33、β43、β44の即値結果が決定される。図６ｈ（ステージ４）では、ｇ33、ｇ43、ｇ53の値と、γ44、γ54、γ55の即値結果が判定される。図６（ステージ５）では、ｇ44、ｇ54と、即値δ55が決定される。図６ｊ（最終ステージ）では、残りの値ｇ55が利用できる。図に示すように、バンド行列という行列の性質から、ロードされない行列要素に対応する左下のプロセッサは不要であり、図示していない。
【００９３】
図６ａ〜図６ｄの簡略な説明は、図７に示すように、Ｎ×Ｎ行列に拡張することができる。これら図に示すように、最上部のプロセッサ５６は、五角形で表される機能をパフォームする。八角形で表される機能のプロセッサ５８は、第１列に沿って下方に拡張され、四角形／五角形を組み合わせた形で表される二重目的のプロセッサ６４は、主対角に沿って拡張される。残りのプロセッサ６６は、八角形／円を組み合わせた形で表される二重目的のプロセッサ６６である。この構成によって、スカラープロセッサだけを用いて、Ｎ×Ｎ Ｇ行列がＮ処理サイクルで決定される。
【００９４】
行列のバンド幅が、限られた幅、例えばＰしかない場合、ＰＥの数を減らすことができる。説明のため、仮にＰがＮ−１に等しい場合には、ａN1用の左下のプロセッサがドロップオフする。仮にＰがＮ−２に等しい場合には、さらに２つのプロセッサ（ａN-1 1，ａN2）がドロップオフする。
【００９５】
スカラーＰＥの数が減少していく様子を、図８ａ〜図８ｅおよび図９ａ、図９ｂに関して説明する。図８ａ〜図８ｅには、図６ａ〜図６ｄの４スカラープロセッサ・インプリメンテーションについての１次元実行プレーン（execution plane）が説明されている。図８ｅの遅延素子６８が、図８ａに示すように、各同時接続（concurrent connection）において挿入される。図８ｅの遅延素子６８は、式４１によって、入力ｙを遅延させて、逐次出力ｘとする。
【００９６】
ｙ：＝ｘ 式４１
【００９７】
タイムｔ1から開始する各処理サイクルにおいて、プロセッサは、実行プレーンを表す斜線が示すように、逐次に処理を行う。この様子を説明すると、タイムｔ1では、ａ11用のプロセッサ５６だけがオペレートする。タイムｔ2では、ａ21用のプロセッサ５８だけがオペレートし、タイムｔ3では、ａ31およびａ22用のプロセッサ５８、６０がオペレートする。以降、ステージ４まで同様に続いて、タイムｔ16では、ａ44用のプロセッサ５６だけがオペレートする。その結果、Ｎステージの処理全体では、Ｎ2のクロックサイクルが必要になる。
【００９８】
複数の行列を２次元スカラー処理アレイによりパイプライン処理することができる。図８ａ〜図８ｄに示すように、ある特定の実行プレーンで、ｔ1からｔ16までがアクティブである。あるステージでは、実行プレーンの数に等しい数までの行列を、同時に処理することができる。ステージ１について説明すると、第１の行列が斜線ｔ1に沿って処理される。次のクロックサイクルで、第１の行列はプレーンｔ2に渡され、プレーンｔ1は第２の行列のために使用される。このパイプラインは、任意の数の行列について続けることができる。パイプライン処理の１つの難点は、パイプライン処理においては、行列データの利用スケジュールが処理速度の低下を招くような場合には、全ての行列に関するデータを保存する必要がある点にある。
【００９９】
行列のグループがステージ１でパイプライン処理された後、その行列のグループはステージ２でパイプライン処理され、以降、ステージＮまでこれが続く。パイプライン処理を用いることにより、プロセッサの利用率ばかりか、アレイのスループットも劇的に向上する。
【０１００】
各クロックサイクルにおいて、プロセッサ５６、５８、６０、６２が全て使用されるわけではないので、行列を１つだけ処理する場合、ＰＥ５６、５８、６０、６２を実行プレーン間で共用することによって、ＰＥの数を減らすことができる。図９ａおよび図９ｂは、ＰＥを減らすための２つの好ましいインプリメンテーションを示す。図９ａに示すように、実行プレーンに垂直な（行列の対角に沿った）線が、第１列の各ＰＥ５６、５８に関して示されている。各垂直な線に沿ったプロセッサ５６、５８、６０、６２は、全て、異なる処理サイクルでオペレートするので、その機能５６、５８、６０、６２を、下方に射影されるような単一のプロセッサ６６、６４によって実行することができる。処理機能５６、６０は、新しいコンバイン機能６４によって実行される。処理機能５８、６２は、新しいコンバイン機能６６によって実行される。遅延素子６８およびプロセッサ間の接続も射影される。最も左側のＰＥは、二重機能素子６６を使用するものとして示されているが、非バンド行列にとって都合がよいのであれば、この素子は八角形で表される機能５８だけを実行するように簡略化することができる。
【０１０１】
図１０ａは、Ｎ×Ｎ Ｇ行列に対応できるように図９ａを拡張したものである。図１０ａに示すように、Ｎ個のプロセッサ６６、６４を使用して、Ｎ×Ｎ Ｇ行列を処理する。図３ａに示すように、図１０ａの処理機能は、Ｎ個のスカラープロセッサ５４によってパフォームすることができる。バンド行列の場合は、バンド幅Ｐと同じ数のスカラープロセッサを使用して、Ｇ行列を処理することができる。
【０１０２】
図３ａのインプリメンテーションにおいては、各プロセッサを１つおきのクロックサイクルで使用する。偶数番のプロセッサが、あるサイクルでオペレートし、奇数番のプロセッサが、次のサイクルでオペレートする。例えば、図９ａのプロセッサ２（右から２番目）はタイムｔ2、ｔ4、ｔ6で処理を行い、プロセッサ３はタイムｔ3、ｔ5で処理を行う。その結果、アレイへの入力として２つのＧ行列をインタレースしながらアレイを処理することによって、同時に２つのＧ行列を決定することができる。このアプローチによれば、図７のインプリメンテーションに比べて、プロセッサ利用率が大幅に向上する。
【０１０３】
単一のアレイの処理時間を短縮するため、図９ｂのインプリメンテーションが利用される。図９ｂに示すように、１つおきのプロセッサ接続で遅延素子がドロップオフ（drop off）する。タイムｔ1では、ａ11用のプロセッサ５６だけがオペレートする。しかし、タイムｔ2では、ａ21、ａ22、ａ31用のプロセッサ５８、６０が全てオペレートしている。（元の行列の対角に沿った）垂直線に沿ったこのアレイの射影も、図９ｂに示されている。図示するように、遅延素子６８の数が半分に減少する。このアレイを使用した場合、Ｎ×Ｎ Ｇ行列の処理時間は、（ＮＰ−（Ｐ2−Ｐ）／２）となる。したがって、単一のＧ行列の処理時間が大幅に短縮される。
【０１０４】
図７、図３ａ、および図３ｂのインプリメンテーションの別の利点は、行列のバンド幅に応じて、各処理アレイをスケーリングすることができる点にある。バンド幅が小さい行列（下三角行列の要素が０）の場合、図７のそれらの要素のためのプロセッサ５８、６６をドロップアウトすることができる。図３ａおよび図３ｂに関しては、下三角行列の要素は図９ａおよび図９ｂの最も左側の垂直線に対応するので、それらの垂直線によって射影されるプロセッサはドロップアウトされる。図９ａを用いて説明すると、当該行列のバンド幅は、ａ41、ａ31、ａ42が０であるＰＥ５８、６２を有する。その結果、プロセッサ６６（最も左側の２つ）への射影は、この処理では不要である。その結果、これらのインプリメンテーションは、当該行列のバンド幅に応じてスケーリングすることができる。
【０１０５】
図９ｃ〜図９ｎには、バンド幅が３である５×５バンド行列に関する、１つおきの接続に遅延が生じる、各処理サイクルごとのタイミング図が示されている。各時間期間においては、各プロセッサに関連付けをした値が示されている。アクティブなプロセッサを実線で示す。図に示すように、ステージ１、タイム０を示す図９ｃの左上のプロセッサ（
【０１０６】
【数２５】
【０１０７】
）から、ステージ５を示す図９ｎの右下のプロセッサ（δ55）へと、処理が伝播していく。図に示すように、バンド行列という行列の性質のため、非バンド行列を処理する左下のプロセッサは不要であり、図示していない。
【０１０８】
図９ｏ〜図９ｚには、図９ｂなどによる、５×５バンド行列を処理する線形アレイの各処理サイクルごとのタイミング図とメモリアクセスが示されている。図示するように、５×５行列のバンド幅は３であるので、必要なプロセッサは３個のみである。バンド行列を処理するため、３個のプロセッサを必要とすることが、図示されている。さらに図示するように、各ステージは比較的高いプロセッサの利用効率を有しており、この利用効率はＮ／ｐが増加するにつれて増加する。
【０１０９】
ＰＥの複雑さを減らすために、除算および平方根を求める機能は、これらＰＥで実行しない（除かれる）。除算および開平は、より複雑であるから、加算器、減算器、乗算器でインプリメントするよりは、ＡＳＩＣにインプリメントされる。
【０１１０】
除算または開平をパフォームする機能は、五角形および八角形で表される機能５６、５８の２つだけである。図６ａ〜図６ｄに示すように、あるステージについて、五角形および八角形で表される機能５６、５８は、全て、１ステージの間に単一の列で実行される。特に、これらの列の各々は、最上部に五角形５８をもち、その下に八角形５８をもつ。各八角形５８は同時にそのｗ入力をそのｙ出力に代入するので、五角形５６の出力は、ｗの値をいずれかのａij用に直ちに保存しなくても、列全体に行き渡る。八角形５８は、ｗ入力を使用してｘ出力も生成し、ｘ出力もａijにフィードバックされる。ｘ出力は、四角形および円で表される機能６０、６２によって、ａijの計算において使用される。その結果、各八角形のｘ出力の値だけが判定されればよい。八角形のｘ出力は、その八角形５８のａijを、五角形５６のｙ出力であって、各八角形５８で同じ値となるｗ入力の値で除算したものである。したがって、除算／開平機能は、八角形５８でｘを計算する際に、実行する必要があるだけである。
【０１１１】
各八角形の出力ｘは、式３４および式３０を用いて、その八角形のａijを五角形のａijの平方根で割ったものである。あるステージについて、各八角形プロセッサにおいて、除算器に代えて乗算器を使用した場合には、五角形のａijの平方根の代りに、その平方根の逆数を判定しさえすればよく、除算機能を五角形プロセッサにおいてだけでパフォームされるように分離して、アレイ全体の複雑さを緩和することができる。平方根の逆数は、五角形に関連付けをした行列要素のａijとして、その逆数の代りに、保存される。このようにすると、後で前進代入および後退代入を行う際にも都合がよい。それらのアルゴリズム中の除算機能がこの逆数を掛ける乗算に変り、他のＰＥ、すなわち図１２ｄおよび図１５ｄのｘ出力でも除算器の必要がなくなるからである。図９ａおよび図９ｂに示す五角形の機能５６は、同じプロセッサ６４によってパフォームされるので、図１０ａおよび図１０ｂに示すように、五角形／四角形プロセッサ６４からの入力と、そのプロセッサ６４への出力とを有する単一の逆数／開平回路７０を用いて、プロセッサ６６、６４をインプリメントすることができる。平方根の逆数を求めた結果は、プロセッサ６６に渡されていく。図１１ａおよび図１１ｂは、図１０ａおよび図１０ｂに対応する。逆数／開平回路７０を分離したことによって、他のプロセッサ６６、６４の複雑さが緩和される。逆数／開平回路７０は、逆数回路および開平回路を用いてインプリメントすることができるが、ＬＵＴ、特にＦＰＧＡ（field programmable gate array）用のＬＵＴを用いてインプリメントするのが好ましい。ただし、メモリはコストエフィシエント（cost efficient）である。
【０１１２】
コレスキーファクタＧが判定された後、図１２ａおよび図１２ｂに示すような前進代入を用いて、ｙが決定される。前進代入のアルゴリズムは次のようになる。
【０１１３】
【数２６】
【０１１４】
バンド行列の場合、アルゴリズムは次のようになる。
【０１１５】
【数２７】
【０１１６】
ｇLKはコレスキー行列ＧのＬ行Ｋ列に相当する要素である。
【０１１７】
図１２ａおよび図１２ｂは、スカラープロセッサを用いた、４×４ Ｇ行列に関する前進代入の２つの実施形態である。図１２ｃの星形で表される機能７２と、図１２ｄのひし形で表される機能７４の２つの機能が、プロセッサ７２、７４によって実行される。星形の機能７２は、式４２および式４３を実行する。
【０１１８】
ｙ←ｗ 式４２
ｘ←ｚ−ｗ×ｇij 式４３
【０１１９】
ひし形の機能７４は、式４４および式４５を実行する。
【０１２０】
ｘ←ｚ／ｇij 式４４
ｙ←ｘ 式４５
【０１２１】
図１２ａに示すようにＰＥの同時接続の間に遅延素子を挿入し、実行プレーン（ｔ1からｔ7）に垂直なアレイを射影することにより、そのアレイを線形アレイ上に射影することができる。
【０１２２】
【数２８】
【０１２３】
から得た受信ベクトルの値ｒ1〜ｒ4をアレイにロードし、アレイからｙ1〜ｙ4出力を得る。ひし形の機能７４は主対角に沿ってのみ存在するので、４つのＰＥからなるアレイを、図１３ａに示すようにＮ個のＰＥを用いてＮ×Ｎ行列を処理するように拡張することができる。このアレイの処理時間は２Ｎサイクルとなる。
【０１２４】
各ＰＥは１つおきの処理サイクルでのみ使用されるので、遅延素子の半数は、図１２ｂに示すように削除することができる。この射影される線形アレイは、図１３ｂに示すように任意のＮ×Ｎ行列を処理するように拡張することができる。このアレイの処理時間はＮサイクルとなる。
【０１２５】
図１３ｂに示す射影先アレイのＰＥのサイクルごとのオペレーションが、図１４ａ〜図１４ｄに示されている。図１３ａに示す第１サイクルｔ1では、ｒ1が左側のプロセッサ１（７４）にロードされ、ｙ1がｒ1とｇ11を用いて決定される。図１４ｂに示す第２サイクルｔ2では、ｒ2、ｒ3がロードされ、ｇ31、ｇ21、ｇ22が処理され、ｙ2が決定される。図１４ｃに示す第３サイクルｔ3では、ｒ4がロードされ、ｇ41、ｇ42、ｇ32、ｇ33がロードされ、ｙ3が決定される。図１４ｄに示す第４サイクルｔ4では、ｇ43、ｇ44が処理され、ｙ4が決定される。
【０１２６】
図１２ｅ〜図１２ｊには、５×５バンド行列の各処理サイクルに関するタイミング図が示されている。図１２ｅは、左下隅の３つのエントリが０というバンド行列の性質（バンド幅が３の場合）を示している。
【０１２７】
コレスキー分解のときと同様に、前進代入でも、同じＰＥが利用できることを示すために、図１２ｆはステージ６から開始する。ステージ６は、図９ｃ〜図９ｎの最終ステージの後のステージである。
【０１２８】
同様に、図１２ｋ〜図１２ｐは、図９ｏ〜図９ｚのプロセッサが前進代入もパフォームできるように拡張した例を示す。これらの図においては、ステージは、コレスキー分解を行う５つのステージの後のステージ６から開始される。この処理は、各処理サイクルに対して、ステージ６のタイム０（図１２ｋ）から、ステージ６のタイム４（図１２ｏ）の後の最終結果（図１２ｐ）まで、パフォームされる。
【０１２９】
前進代入によってｙ変数が判定された後、後退代入によってデータベクトルを判定することができる。後退代入は次のサブルーチンによって実行される。
【０１３０】
【数２９】
【０１３１】
バンド行列の場合、次のサブルーチンが用いられる。
【０１３２】
【数３０】
【０１３３】
（・）*は複素共役関数を示す。
【０１３４】
【数３１】
【０１３５】
は、コレスキーファクタＧについて判定された対応する要素の複素共役である。ＹLはｙの対応する要素である。
【０１３６】
後退代入は、４×４処理アレイに関する図１５ａおよび図１５ｂに示すように、星形およびひし形の機能７６、７８を用いるスカラープロセッサによってもインプリメントされる。しかし、これらの機能は、図１５ｃおよび図１５ｄに示すように、Ｇ行列の値の複素共役を用いてパフォームされる。したがって、式４２〜式４５は、それぞれ、式４６〜式４９となる。
【０１３７】
ｙ←ｗ 式４６
【０１３８】
【数３２】
【０１３９】
ｙ←ｘ 式４９
【０１４０】
プロセッサ７６、７８の間の同時代入で、遅延素子６８を挿入することにより、図１５ａのアレイは、実行プレーンを横断して線形アレイに射影される。このアレイは、Ｎ×Ｎ行列を処理するため、図１６ａに示すように拡張することができる。ｙベクトルの値が図１６ａのアレイにロードされ、データベクトルｄが出力される。このアレイは、ｄを判定するのに２Ｎクロックサイクルを要する。１つおきのプロセッサが１つおきのクロックサイクルでオペレートするので、２つのｄを同時に判定することができる。
【０１４１】
図１６ａの各プロセッサ７６、７８は１つおきのクロックサイクルでオペレートするので、図１５ｂに示すように１つおきの遅延素子を削除することができる。図１５ｂの射影先アレイは、Ｎ×Ｎ行列を処理するため、図１６ｂに示すように拡張することができる。このアレイは、ｄを判定するのにＮクロックサイクルを要する。
【０１４２】
図１６ｂの射影先アレイのＰＥ７６、７８のサイクルごとの動作が、図１７ａ〜図１７ｄに示されている。図１７ａに示す第１サイクルｔ1では、ｙ4がロードされ、
【０１４３】
【数３３】
【０１４４】
が処理され、ｄ4が決定される。図１７ｂに示す第２サイクルｔ2では、ｙ2、ｙ3がロードされ、
【０１４５】
【数３４】
【０１４６】
、
【０１４７】
【数３５】
【０１４８】
が処理され、ｄ3が決定される。図１７ｃに示す第３サイクルｔ3では、ｙ1がロードされ、
【０１４９】
【数３６】
【０１５０】
および
【０１５１】
【数３７】
【０１５２】
が処理され、ｄ2が決定される。図１７ｄに示す第４サイクルｔ4では、
【０１５３】
【数３８】
【０１５４】
、
【０１５５】
【数３９】
【０１５６】
が処理され、ｄ4が決定される。
【０１５７】
図１５ｅ〜図１５ｊには、後退代入を実行できるようにするための、図１２ｅ〜図１２ｊのプロセッサの拡張が示されている。図１５ｅは、左下隅の３つのエントリが０というバンド行列の性質を示している。
【０１５８】
タイミング図は、前進代入のステージ６の後に置かれたステージ７から開始する。処理は、ステージ７のタイム０（図１５ｆ）から開始し、ステージ７のタイム４（図１５ｊ）で完了する。ステージ７のタイム４（図１５ｊ）の後、全てのデータｄ1からｄ5が決定される。
【０１５９】
同様に、図１５ｋ〜図１５ｐには、後退代入も実行できるようにするための、図１２ｋ〜図１２ｐのプロセッサの拡張が示されている。これらの図は、前進代入のステージ６の後、ステージ７から開始する。処理は、ステージ７のタイム０（図１５ｋ）から最終結果（図１５ｐ）の各処理サイクルで実行される。図９ｃ〜図９ｎと、図１２ｅ〜図１２ｊと、図１５ｅ〜図１５ｊとに示すように、バンド行列の場合は、コレスキー分解と、前進代入と、後退代入とを実行するための２次元アレイのプロセッサ数を減らすことができる。図９ｏ〜図９ｚ、図１２ｋ〜図１２ｐに示すように、線形アレイのプロセッサ数は、行列の次元数からバンド行列のバンド幅に減らされる。
【０１６０】
前進代入および後退代入に関する個々のＰＥ７２、７４、７６、７８の複雑さを軽減するため、図１８ａおよび図１８ｂに示すように、ＰＥ７２、７４、７６、７８から除算機能８０を分離することができる。図１８ａおよび図１８ｂは、それぞれ、図１６ａおよび図１６ｂに対応する。ＰＥ７２、７４、７６、７８に関連する前進代入および後退代入のためのデータは異なるが、ＰＥ７２、７４、７６、７８によってパフォームされる機能は同じである。除算器８０は、除算機能をパフォームするために、最も右側のＰＥ７４、７８によって使用される。除算器８０は、逆数値を判定するためのＬＵＴとしてインプリメントされ、ＬＵＴは、最も右側のプロセッサ７４、７８によって乗算において使用される。前進代入および後退代入を行う際には、コレスキー分解の実行によって得た逆数がすでにメモリに存在しているので、前進代入および後退代入のための逆数の乗算には、すでにメモリに格納されている逆数を利用することができる。
【０１６１】
３つの全ての処理（Ｇの判定、前進代入および後退代入）で、計算データフローはＮまたはバンド幅Ｐが同じフローとなるので、３つの機能を全て、同じ再構成可能アレイで実行することができる。再構成可能アレイの各ＰＥ８４、８２は、図１９ａおよび図１９ｂに示すように、Ｇを判定する機能と前進代入および後退代入をパフォームする機能をパフォームさせることができる。最も右側のプロセッサ８２は、五角形／四角形とひし形の機能６４、７４、７８を実行することができる。他のプロセッサ８４は、円／八角形と星形の機能６６、７２、７６をパフォームすることができる。コレスキー分解を実行する場合、最も右側のＰＥ８２は、五角形／四角形の機能６４を用いてオペレートし、他のＰＥ８４は、円／八角形の機能６６を用いてオペレートする。前進代入および後退代入を実行する場合、最も右側のプロセッサ８２は、ひし形の機能７４、７８を用いてオペレートし、他のＰＥ８４は、星形の機能７２、７６を用いてオペレートする。ＰＥ８２、８４は好ましくは、必要な機能をパフォームするように構成される。再構成可能アレイを用いることにより、各ＰＥ８２、８４は、前進代入および後退代入の２つの算術機能と、コレスキー分解に関する４つの機能を実行し、ＰＥ８２、８４ごとに実行される算術機能は全部で６つとなる。これらの機能は、演算論理ユニット（ＡＬＵ）と適切な制御ロジック、またはその他の手段で実行することができる。
【０１６２】
再構成可能アレイ内の個々のＰＥ８２、８４の複雑さを軽減するため、除算および開平機能８６は、好ましくは、逆数および開平装置８６としてアレイから切り離される。逆数および開平装置８６は、好ましくは、図２０ａおよび図２０ｂに示すように、前進代入および後退代入において最も右側のＰＥ８２によって、乗算において使用される逆数を判定し、最も右側のプロセッサのデータを用いた乗算において使用され、ＰＥ８４に渡される平方根の逆数を判定する。逆数と平方根の逆数の判定は、好ましくは、ＬＵＴを用いて実行される。あるいは、除算および開平機能ブロック８６は、除算回路と開平回路とすることもできる。
【０１６３】
ＰＥ８２、８４の数をさらに減らすために、フォールディング（folding）が用いられる。図２１ａおよび図２１ｂにフォールディングが示されている。フォールディングでは、線形システム解法のためにＰ個のＰＥ８２、８４を使用する代りに、より少ない数ＦのＰＥがＱ段のフォールドで使用される。例えば、Ｐを９個のＰＥ８２、８４とした場合、３段のフォールドでは、３個のＰＥ８２、８４が９個のＰＥの機能をパフォームする。フォールディングの１つの難点は、縮小されたアレイの処理時間がＱ倍に増加することである。１つの利点は、プロセッサ利用度の効率が一般に増大することである。３段のフォールドの場合、処理時間は３倍になる。したがって、プロセッサ数の最小化とデータを処理するのに許容できる最大処理時間とのトレードオフに基づいて、フォールドのステージ数が選択される。
【０１６４】
図２１ａには、図１１ｂのアレイを３段にフォールドすることによって、１２個のＰＥの機能を４個のＰＥ７６1、７６2、７６3、７６4／７８でパフォームする双方向フォールドが示されている。ＰＥ７６1、７６2、７６3、７６4／７８の間に遅延素子を挿入する代りに、デュアルポートメモリ８６1、８６2、８６3、８６4（８６）を使用して、各フォールドのデータを保存する。遅延素子（デュアルポートメモリ８６）は、図１２ａの実施形態でのように各ＰＥ接続ごとに存在できるが、図１２ｂのインプリメンテーションでのように１つおきの接続ごとに存在するものとして示されている。デュアルポートメモリの代りに、２組のシングルポートメモリを使用することもできる。
【０１６５】
第１のフォールドにおいては、各ＰＥのデータは、それに関連づけられたデュアルポートメモリ８６のフォールド１用のアドレスに保存される。行列のデータもメモリセル８８1〜８８4（８８）からプロセッサ７６1〜７６3、７６4／７８に入力される。フォールド１のＰＥ７６4／７８とフォールド３のプロセッサ７６1の間にデータのラップアラウンドは起らないので、これらのプロセッサの間でデュアルポートメモリ８６は使用されない。しかし、フォールド１とフォールド２のプロセッサ７６1の間およびフォールド２とフォールド３のプロセッサ７６4／７８の間に単一のアドレスが必要とされるので、デュアルポートメモリ８６が破線で示されている。第２のフォールドの間、各プロセッサのデータはフォールド２用のメモリアドレスに保存される。行列のデータもフォールド２用にＰＥ７６1〜７６3、７６4／７８に入力される。フォールド２のＰＥ７６1用のデータはフォールド１のＰＥ７６1から来るが、これらは物理的には同じＰＥ７６1であるので、この接続は（示されてはいるが）必要がない。第３のフォールドにおいて、各ＰＥのデータはフォールド３用のメモリアドレスに保存される。行列のデータもフォールド３用にＰＥ７６1〜７６3、７６4／７８に入力される。フォールド３のＰＥ７６4／７８用のデータはフォールド２のＰＥ７６4／７８から来るので、この接続は必要がない。次の処理ステージでは、フォールド１から手順が繰り返される。
【０１６６】
図２２ａは、図２１ａの双方向フォールドの実施形態をＮ個のＰＥ７６1〜７６N-1、７６N／７８に拡張したものである。ＰＥ７６1〜７６N-1、７６N／７８は機能的に線形アレイとして構成され、デュアルポートメモリ８６または２組のシングルポートメモリをアクセスする。
【０１６７】
図２１ｂには、図１１ｂのアレイの単方向フォールドバージョンが示されている。第１のフォールドにおいて、各ＰＥのデータは、それに関連づけられたデュアルポートメモリのフォールド１用のアドレスに保存される。フォールド１のＰＥ７６4／７８とフォールド３のＰＥ７６1は物理的に接続されているが、動作上、これらのＰＥ間で直接データを伝送することはない。したがって、これらの間のメモリポート８６4はアドレスが１つ少ない記憶域をもつ。フォールド２のＰＥ７６4／７８は、ＰＥ間のリンク状の接続によって効率的にフォールド１のＰＥ７６1に結合される。同様に、フォールド３のＰＥ７６4／７８は、フォールド２のＰＥ７６1に結合される。
【０１６８】
図２２ｂは、図２０ｂの単方向フォールディングのインプリメンテーションをＮ個のＰＥに拡張したものである。ＰＥ７６1〜７６N-1、７６N／７８は、デュアルメモリの周りにリング状に機能的に配置される。
【０１６９】
フォールディングされたＰＥで、コレスキー分解、前進代入および後退代入をインプリメントするには、アレイ内のＰＥ７６4／７８などのＰＥは、コレスキー分解、前進代入および後退代入のためのプロセッサ機能とともに、各フォールドのためのプロセッサ機能もパフォームできなければならない。ＰＥ７６4／７８について図２０ａおよび図２０ｂに示すように。インプリメントによっては、追加されるＰＥに必要な機能が、そのインプリメンテーションの複雑さを増大させる。ＡＬＵを用いてフォールディングをインプリメントするには、１個のＰＥ（ＰＥ ７６4／７８など）は、１２種の演算機能（前進代入および後退代入のための４種とコレスキー分解のための８種）をパフォームするが、他のＰＥは６種の演算機能をパフォームするだけである。
【０１７０】
図２３には、コレスキー分解、前進代入および後退代入で定義される６種の機能全てをパフォームするのに使用できる、好ましい簡単な再構成可能ＰＥの１スライスが示されている。除算を１個のＰＥ（以下ＰＥ１という）に分離した後、このＰＥは使用される。好ましくは２つのスライスが使用され、一方はｘおよびｙの実数成分を生成するため、他方はそれらの虚数成分を生成するためのものである。添え字ｉおよびｒは、それぞれ、実数成分および虚数成分を示すのに使用される。
【０１７１】
信号ｗ、ｘ、ｙ、ｚは、先にＰＥ機能を定義する際に定義したものと同じである。信号ａqおよびａdはそれぞれ、処理のあるサイクルでリード（read）され、かつ／またはライト（write）されるＰＥのメモリロケーションの現在の状態と、次の状態とを表す。括弧内の名前は、第２のスライスで使用される信号を示す。
【０１７２】
この好ましいＰＥは、どのＰＥとしても使用できるが、他のＰＥから独立して除算機能をパフォームするＰＥ１の最適化に使用するのが望ましい。マルチプレクサ９４1から９４8への各入力にはラベル付けされており、「０」はその入力がＰＥ１だけに使用されることを、「−」はＰＥ１以外の全てのＰＥに使用されることを、「＋」は全てのＰＥに使用されることを示す。ＰＥ１の実数スライスの場合を除いて、ｉｓｑｒ入力は０に接続され、ＰＥ１の実数スライスの場合は、ｉｓｑｒ入力はａqr入力の平方根の逆数を生成する機能の出力に接続される。このような機能は、適当な固定小数点ワードサイズのＲＯＭを用いてＬＵＴとしてインプリメントすることができる。
【０１７３】
図２３に示すように、マルチプレクサ９４1と９４2の出力は、乗算器９６1によって掛け合される。マルチプレクサ９４3と９４4の出力は、乗算器９６2によって掛け合される。乗算器９６1と乗算器９６2の出力は、加算／減算回路９８によってコンバインされる。加算／減算回路９８の出力は、減算器９９によってマルチプレクサ９４5の出力とコンバインされる。減算器９９の出力は、マルチプレクサ９４8への入力となる。
【技術分野】
【０００１】
本発明は、一般に、線形システムの解法に関する。具体的には、本発明は、線形システムを解くためのアレイ処理の使用に関する。
【背景技術】
【０００２】
工学上の問題を解くのに、線形システム解法が用いられることが多い。このような課題の１つに、ＴＤＤ（time division duplex）通信において、ＣＤＭＡ（code division multiple access）を用いて、複数のユーザ信号をジョイントユーザ検出（joint user detection）することがある。このようなシステムにおいては、複数のユーザが、同じ固定継続時間間隔（タイムスロット）で、同時に複数の通信バーストを伝送する。マルチプルバーストは、異なる拡散符号を用いて伝送される。伝送中、各バーストはチャネルレスポンスを経験する。伝送されたバーストからデータを復元するための１つのアプローチが、ジョイント検出（joint detection）であり、このアプローチでは、全てのユーザデータが同時に受信される。このようなシステムを図１に示す。ＵＥ（user equipment）または基地局において、ジョイント検出レシーバを使用することができる。
【０００３】
マルチプルバースト９０は、チャネルレスポンスを経験した後、コンバイン受信信号（combined received signal）として、アンテナ９２またはアンテナアレイで受信される。受信信号は、デモジュレータ９４などによって、ベースバンドに変換され、受信ベクトルｒを生成するため、１つのＡＤＣ（analog to digital converter）９６または複数のＡＤＣなどによって、符号の１チップレートまたは符号の複数チップレートでサンプリングされる。チャネル推定デバイス９８は、通信バーストのトレーニング系列の一部を使用して、バースト９０のチャネルレスポンスを推定する。ジョイント検出器１００は、各ユーザのバーストの推定または既知の拡散符号と、推定または既知のチャネルレスポンスとを使用して、全てのユーザの元の伝送データをデータベクトルｄとして推定する。
【０００４】
ジョイント検出問題は、一般に、式１によってモデル化される。
【０００５】
Ａｄ＋ｎ＝ｒ 式１
【０００６】
ｄは伝送データベクトル、ｒは受信ベクトル、ｎはＡＷＧＮ（additive white gaussian noise）であり、Ａはチャネルレスポンスを既知の拡散符号を用いて畳み込むことによって構成されるＭ×Ｎ行列である。
【０００７】
式１を解くための２つのアプローチに、ゼロフォーシング（ＺＦ）およびＭＭＳＥ（Minimum Mean Square Error）アプローチがある。ｎを０に接近させるＺＦ解法は、式２による。
【０００８】
ｄ＝（ＡHＡ）-1ＡHｒ 式２
【０００９】
ＭＭＳＥアプローチは、式３および式４による。
【００１０】
ｄ＝Ｒ-1ＡHｒ 式３
Ｒ＝ＡHＡ＋σ2Ｉ 式４
【００１１】
σはノイズｎの分散であり、Ｉは単位行列である。
【００１２】
拡散符号、チャネルレスポンスと、ノイズの分散の平均は、推定されるか、または既知であり、受信ベクトルは既知であるので、唯一の未知の変数は、データベクトルｄである。行列の直接逆変換といった力ずくの解法は、どちらのアプローチによるとしても、極めて複雑である。この複雑さを緩和するための１つの技法に、コレスキー分解（Cholesky decomposition）がある。コレスキーのアルゴリズムは、
【００１３】
【数１】
【００１４】
またはＲなどの対称正定値行列を、式５によって、下三角行列Ｇと上三角行列ＧHに因数分解する。
【００１５】
【数２】
【００１６】
対称正値行列
【００１７】
【数３】
【００１８】
は、式６によって、Ａにその共役転置（エルミート）行列ＡHを乗算することによって、Ａから生成することができる。
【００１９】
【数４】
【００２０】
【数５】
【００２１】
は、簡単に式７によって定義される。
【００２２】
【数６】
【００２３】
その結果、式１は、ＺＦでは式８として、ＭＭＳＥでは式９として、書き換えられる。
【００２４】
【数７】
【００２５】
【数８】
【００２６】
式８または式９を解くため、式１０によってコレスキーファクタ（Cholesky factor）が用いられる。
【００２７】
【数９】
【００２８】
変数ｙは式１１によって定義される。
【００２９】
ＧHｄ＝ｙ 式１１
【００３０】
変数ｙを使用して、式１０は式１２として書き換えられる。
【００３１】
【数１０】
【００３２】
データベクトルを取得するための複雑さの大半は、３つのステップで実行される。第１のステップで、式１３に示すように、
【００３３】
【数１１】
【００３４】
またはＲなどの派生対称正値行列からＧが生成される。
【００３５】
【数１２】
【００３６】
Ｇを用い、式１４に示すように、式８においてＧの前進代入（forward substitution）を使用してｙを解く。
【００３７】
【数１３】
【００３８】
Ｇの共役転置行列ＧHを用い、式１５に示すように、式１１において後退代入（backwardsubstitution）を使用してｄを解く。
【００３９】
ｄ＝ＢＡＣＫＷＡＲＤ ＳＵＢ（ＧH，ｙ） 式１５
【００４０】
式１３によってコレスキーファクタＧを判定するアプローチは、
【００４１】
【数１４】
【００４２】
またはＲに関して示された以下のアルゴリズムとするが、Ｒに関しては類似のアプローチも用いられる。
【００４３】
【数１５】
【００４４】
ａd,eは行列
【００４５】
【数１６】
【００４６】
またはＲのｄ行ｅ列の要素を表す。「：」は「ｊからＮまで」などの「まで」演算子を示し、（・）Hは共役転置（エルミート）演算子を示す。
【００４７】
コレスキーファクタを求解するための別のアプローチでは、Ｎ個の並列ベクトルベースプロセッサが使用される。各プロセッサは、
【００４８】
【数１７】
【００４９】
またはＲ行列の列にマップされる。各プロセッサの列は、変数μによって定義され、μ＝１：Ｎである。並列プロセッサに基づくサブルーチンは、μ＝１：Ｎとした場合の以下のサブルーチンとして考察することができる。
【００５０】
【数１８】
【００５１】
ｒｅｃｖ（・,left）は左側のプロセッサ演算器からの受信であり、ｓｅｎｄ（・,right）は右側のプロセッサ演算器への伝送であり、ｇK,Lは隣接プロセッサからの値である。
【００５２】
このサブルーチンは、図２ａ〜図２ｈを用いて図説される。図２ａは、ジョイント検出器のベクトルプロセッサとその関連メモリセルのブロック図である。各プロセッサ５０1から５０N（５０）は、行列の列に対して演算を行う。Ｇ行列は下三角行列であり、
【００５３】
【数１９】
【００５４】
またはＲは下三角行列によって完全に定義されるので、下三角行列の要素ａk,lだけが使用される。
【００５５】
図２ｂおよび図２ｃには、プロセッサの下側のセル上で、プロセッサによって実行され得る２つの機能が示されている。図２ｂでは、下向き三角形で表される機能５２が、μ番目のプロセッサ５０の下側のセル（ａμμからａNμ）上で、式１６および式１７を実行する。
【００５６】
【数２０】
【００５７】
ａμ:N,μ：＝ν 式１７
【００５８】
「←」は同時代入を示し、「：＝」は逐次代入を示し、νは右側のプロセッサに伝送される値である。
【００５９】
図２ｃでは、右向き三角形で表される機能５２が、μ番目のプロセッサ５０の下側のセル上で、式１８および式１９を実行する。
【００６０】
ν←ｕ 式１８
ａμ:N,μ：＝ａμ:N,μ−νμνμ:N 式１９
【００６１】
νkは、第ｋ番目のプロセッサ５０の右側に出ていく値に関係付けした値を示す。
【００６２】
図２ｄ〜図２ｇには、４×４ Ｇ行列に対して実行されるデータフローと機能が示されている。処理のステージ１から４までに対しては、図２ｄ〜図２ｇに示すように、最も左側のプロセッサ５０がドロップアウトし、下向き三角形の機能５２が、左から右に移動していく。図２ｄ〜図２ｇをインプリメントするため、下向き三角形は、プロセッサを物理的に右向きに置き換えることができ、または下向き三角形の機能を担うことによって、プロセッサをバーチャルに右向きに置き換えることができる。
【００６３】
これらエレメント（element）は、ステージ１を表す図２ｈに示すように、（（Ｎ−４）個の）プロセッサ５０を第４番目のプロセッサ５０4の右側に追加し、プロセッサ５０の各々に行列の対角より下方の（Ｎ−４個の）セルを追加することによって、Ｎ×Ｎ行列とＮ個のプロセッサ５０に拡張可能である。このような構成による処理はＮステージにわたって実行される。
【００６４】
このようなコレスキー分解のインプリメントは、ベクトルプロセッサを用いるにしても、スカラーＰＥへの直接分解を用いるにしても、各ステージの処理の後で、大量の処リソースがアイドル状態になるため、効率的ではない。
【発明の概要】
【発明が解決しようとする課題】
【００６５】
したがって、線形システムを解くための代替アプローチを有するのが望ましい。
【課題を解決するための手段】
【００６６】
線形システムを解くためにＰＥが利用される。本発明の一実施形態では、コレスキーファクタを判定するため、行列の対角の行列要素がスカラーＰＥに射影される。別の実施形態では、２次元スカラーアレイを用いて、コレスキーファクタを判定する。第３の実施形態では、再構成可能スカラー線形アレイを用いて、コレスキーファクタを判定し、前進代入および後退代入を実行する。行列が、限られたバンド幅を有する場合は、これらの実施形態で使用されるプロセッサの数を減らすことができる。プロセッサのフォールディング（folding）を用いて、これらの実施形態で使用されるプロセッサの数を減らすことができる。本発明の別の実施形態は、コレスキーファクタを判定し、前進代入および後退代入を実行するように再構成できるＰＥである。
【図面の簡単な説明】
【００６７】
【図１】ジョイント検出レシーバの簡略な図である。
【図２ａ】ベクトルプロセッサを用いてコレスキーファクタを判定する様子を示した図である。
【図２ｂ】ベクトルプロセッサを用いてコレスキーファクタを判定する様子を示した図である。
【図２ｃ】ベクトルプロセッサを用いてコレスキーファクタを判定する様子を示した図である。
【図２ｄ】ベクトルプロセッサを用いてコレスキーファクタを判定する様子を示した図である。
【図２ｅ】ベクトルプロセッサを用いてコレスキーファクタを判定する様子を示した図である。
【図２ｆ】ベクトルプロセッサを用いてコレスキーファクタを判定する様子を示した図である。
【図２ｇ】ベクトルプロセッサを用いてコレスキーファクタを判定する様子を示した図である。
【図２ｈ】ベクトルプロセッサを用いてコレスキーファクタを判定する様子を示した図である。
【図３ａ】コレスキー分解を実行するＮ個のスカラープロセッサの好ましい実施形態を示した図である。
【図３ｂ】コレスキー分解を実行するＮ個のスカラープロセッサの好ましい実施形態を示した図である。
【図４ａ】コレスキー分解のために３次元グラフを使用した一例を示した図である。
【図４ｂ】コレスキー分解のために３次元グラフを使用した一例を示した図である。
【図４ｃ】コレスキー分解のために３次元グラフを使用した一例を示した図である。
【図４ｄ】コレスキー分解のために３次元グラフを使用した一例を示した図である。
【図４ｅ】コレスキー分解のために３次元グラフを使用した一例を示した図である。
【図５ａ】コレスキー分解を実行するベクトルプロセッサをスカラープロセッサにマップする一例を示した図である。
【図５ｂ】コレスキー分解を実行するベクトルプロセッサをスカラープロセッサにマップする一例を示した図である。
【図５ｃ】コレスキー分解を実行するベクトルプロセッサをスカラープロセッサにマップする一例を示した図である。
【図５ｄ】コレスキー分解を実行するベクトルプロセッサをスカラープロセッサにマップする一例を示した図である。
【図５ｅ】コレスキー分解を実行するベクトルプロセッサをスカラープロセッサにマップする一例を示した図である。
【図６ａ】非バンド行列に関するスカラーアレイの処理フローを示した図である。
【図６ｂ】非バンド行列に関するスカラーアレイの処理フローを示した図である。
【図６ｃ】非バンド行列に関するスカラーアレイの処理フローを示した図である。
【図６ｄ】非バンド行列に関するスカラーアレイの処理フローを示した図である。
【図６ｅ】バンド行列に関するスカラーアレイの処理フローを示した図である。
【図６ｆ】バンド行列に関するスカラーアレイの処理フローを示した図である。
【図６ｇ】バンド行列に関するスカラーアレイの処理フローを示した図である。
【図６ｈ】バンド行列に関するスカラーアレイの処理フローを示した図である。
【図６ｉ】バンド行列に関するスカラーアレイの処理フローを示した図である。
【図６ｊ】バンド行列に関するスカラーアレイの処理フローを示した図である。
【図７】図４ａの射影をｋ軸に沿ってＮ×Ｎ行列に拡張した図である。
【図８ａ】２Ｄスカラーアレイ中のスカラープロセッサ間の遅延を利用した処理フローを示した図である。
【図８ｂ】２Ｄスカラーアレイ中のスカラープロセッサ間の遅延を利用した処理フローを示した図である。
【図８ｃ】２Ｄスカラーアレイ中のスカラープロセッサ間の遅延を利用した処理フローを示した図である。
【図８ｄ】２Ｄスカラーアレイ中のスカラープロセッサ間の遅延を利用した処理フローを示した図である。
【図８ｅ】遅延素子とその関連式を示した図である。
【図９ａ】図８ａ〜図８ｄのスカラープロセッサアレイの、４つのスカラープロセッサからなる１Ｄアレイへの射影を示した図である。
【図９ｂ】１つおきのプロセッサ間に遅延要素を有するスカラープロセッサアレイの、４つのスカラープロセッサからなる１Ｄアレイへの射影を示した図である。
【図９ｃ】１つおきのプロセッサ間に遅延要素を有するバンド行列のコレスキー分解に関する処理フローを示した図である。
【図９ｄ】１つおきのプロセッサ間に遅延要素を有するバンド行列のコレスキー分解に関する処理フローを示した図である。
【図９ｅ】１つおきのプロセッサ間に遅延要素を有するバンド行列のコレスキー分解に関する処理フローを示した図である。
【図９ｆ】１つおきのプロセッサ間に遅延要素を有するバンド行列のコレスキー分解に関する処理フローを示した図である。
【図９ｇ】１つおきのプロセッサ間に遅延要素を有するバンド行列のコレスキー分解に関する処理フローを示した図である。
【図９ｈ】１つおきのプロセッサ間に遅延要素を有するバンド行列のコレスキー分解に関する処理フローを示した図である。
【図９ｉ】１つおきのプロセッサ間に遅延要素を有するバンド行列のコレスキー分解に関する処理フローを示した図である。
【図９ｊ】１つおきのプロセッサ間に遅延要素を有するバンド行列のコレスキー分解に関する処理フローを示した図である。
【図９ｋ】１つおきのプロセッサ間に遅延要素を有するバンド行列のコレスキー分解に関する処理フローを示した図である。
【図９ｌ】１つおきのプロセッサ間に遅延要素を有するバンド行列のコレスキー分解に関する処理フローを示した図である。
【図９ｍ】１つおきのプロセッサ間に遅延要素を有するバンド行列のコレスキー分解に関する処理フローを示した図である。
【図９ｎ】１つおきのプロセッサ間に遅延要素を有するバンド行列のコレスキー分解に関する処理フローを示した図である。
【図９ｏ】バンド行列を処理する線形アレイのメモリアクセスを示した図である。
【図９ｐ】バンド行列を処理する線形アレイのメモリアクセスを示した図である。
【図９ｑ】バンド行列を処理する線形アレイのメモリアクセスを示した図である。
【図９ｒ】バンド行列を処理する線形アレイのメモリアクセスを示した図である。
【図９ｓ】バンド行列を処理する線形アレイのメモリアクセスを示した図である。
【図９ｔ】バンド行列を処理する線形アレイのメモリアクセスを示した図である。
【図９ｕ】バンド行列を処理する線形アレイのメモリアクセスを示した図である。
【図９ｖ】バンド行列を処理する線形アレイのメモリアクセスを示した図である。
【図９ｗ】バンド行列を処理する線形アレイのメモリアクセスを示した図である。
【図９ｘ】バンド行列を処理する線形アレイのメモリアクセスを示した図である。
【図９ｙ】バンド行列を処理する線形アレイのメモリアクセスを示した図である。
【図９ｚ】バンド行列を処理する線形アレイのメモリアクセスを示した図である。
【図１０ａ】スカラープロセッサがＮ個に拡張された、図９ａの射影されたアレイを示した図である。
【図１０ｂ】スカラープロセッサがＮ個に拡張された、図９ｂの射影されたアレイを示した図である。
【図１１ａ】除算の平方根をとる関数の図１０ａのアレイからの分離を示す図である。
【図１１ｂ】除算の平方根をとる関数の図１０ｂのアレイからの分離を示す図である。
【図１２ａ】各プロセッサ間で遅延要素を有する前進代入アレイの、４つのスカラープロセッサへの射影を示した図である。
【図１２ｂ】１つおきのプロセッサ間で遅延要素を有する前進代入アレイの、４つのスカラープロセッサへの射影を示した図である。
【図１２ｃ】前進代入に関する星型で表される関数によって実行される式を示した図である。
【図１２ｄ】前進代入に関するひし形で表される関数によって実行される式を示した図である。
【図１２ｅ】１つおきのプロセッサ間に同時代入を有するバンド行列の前進代入に関する処理フローを示した図である。
【図１２ｆ】１つおきのプロセッサ間に遅延要素を有するバンド行列の前進代入に関する処理フローを示した図である。
【図１２ｇ】１つおきのプロセッサ間に遅延要素を有するバンド行列の前進代入に関する処理フローを示した図である。
【図１２ｈ】１つおきのプロセッサ間に遅延要素を有するバンド行列の前進代入に関する処理フローを示した図である。
【図１２ｉ】１つおきのプロセッサ間に遅延要素を有するバンド行列の前進代入に関する処理フローを示した図である。
【図１２ｊ】１つおきのプロセッサ間に遅延要素を有するバンド行列の前進代入に関する処理フローを示した図である。
【図１２ｋ】バンド行列を処理する前進代入線形アレイのメモリアクセスを示した図である。
【図１２ｌ】バンド行列を処理する前進代入線形アレイのメモリアクセスを示した図である。
【図１２ｍ】バンド行列を処理する前進代入線形アレイのメモリアクセスを示した図である。
【図１２ｎ】バンド行列を処理する前進代入線形アレイのメモリアクセスを示した図である。
【図１２ｏ】バンド行列を処理する前進代入線形アレイのメモリアクセスを示した図である。
【図１２ｐ】バンド行列を処理する前進代入線形アレイのメモリアクセスを示した図である。
【図１３ａ】スカラープロセッサがＮ個に拡張された、図１２ａの射影されたアレイを示した図である。
【図１３ｂ】スカラープロセッサがＮ個に拡張された、図１２ｂの射影されたアレイを示した図である。
【図１４ａ】図１２ｂの射影されたアレイに関する処理フローを示した図である。
【図１４ｂ】図１２ｂの射影されたアレイに関する処理フローを示した図である。
【図１４ｃ】図１２ｂの射影されたアレイに関する処理フローを示した図である。
【図１４ｄ】図１２ｂの射影されたアレイに関する処理フローを示した図である。
【図１５ａ】各プロセッサ間で遅延要素を有する後退代入アレイの、４つのスカラープロセッサへの射影を示した図である。
【図１５ｂ】１つおきのプロセッサ間で遅延要素を有する後退代入アレイの、４つのスカラープロセッサへの射影を示した図である。
【図１５ｃ】後退代入に関する星型で表される関数によって実行される式を示した図である。
【図１５ｄ】後退代入に関するひし形で表される関数によって実行される式を示した図である。
【図１５ｅ】１つおきのプロセッサ間に同時代入を有するバンド行列の後退代入に関する処理フローを示した図である。
【図１５ｆ】１つおきのプロセッサ間に遅延要素を有するバンド行列の後退代入に関する処理フローを示した図である。
【図１５ｇ】１つおきのプロセッサ間に遅延要素を有するバンド行列の後退代入に関する処理フローを示した図である。
【図１５ｈ】１つおきのプロセッサ間に遅延要素を有するバンド行列の後退代入に関する処理フローを示した図である。
【図１５ｉ】１つおきのプロセッサ間に遅延要素を有するバンド行列の後退代入に関する処理フローを示した図である。
【図１５ｊ】１つおきのプロセッサ間に遅延要素を有するバンド行列の後退代入に関する処理フローを示した図である。
【図１５ｋ】バンド行列を処理する後退代入線形アレイのメモリアクセスを示した図である。
【図１５ｌ】バンド行列を処理する後退代入線形アレイのメモリアクセスを示した図である。
【図１５ｍ】バンド行列を処理する後退代入線形アレイのメモリアクセスを示した図である。
【図１５ｎ】バンド行列を処理する後退代入線形アレイのメモリアクセスを示した図である。
【図１５ｏ】バンド行列を処理する後退代入線形アレイのメモリアクセスを示した図である。
【図１５ｐ】バンド行列を処理する後退代入線形アレイのメモリアクセスを示した図である。
【図１６ａ】スカラープロセッサがＮ個に拡張された、図１５ａの射影されたアレイを示した図である。
【図１６ｂ】スカラープロセッサがＮ個に拡張された、図１５ｂの射影されたアレイを示した図である。
【図１７ａ】図１５ｂの射影されたアレイに関する処理フローを示した図である。
【図１７ｂ】図１５ｂの射影されたアレイに関する処理フローを示した図である。
【図１７ｃ】図１５ｂの射影されたアレイに関する処理フローを示した図である。
【図１７ｄ】図１５ｂの射影されたアレイに関する処理フローを示した図である。
【図１８ａ】分離された除算機能をもつ図１３ａ、図１６ａのアレイを示した図である。
【図１８ｂ】分離された除算機能をもつ図１３ｂ、図１６ｂのアレイを示した図である。
【図１９ａ】Ｇ、前進代入、および後退代入を判定するための再構成可能アレイを示した図である。
【図１９ｂ】Ｇ、前進代入、および後退代入を判定するための再構成可能アレイを示した図である。
【図２０ａ】除算および平方根をとる関数の再構成可能アレイからの分離を示す図である。
【図２０ｂ】除算および平方根をとる関数の再構成可能アレイからの分離を示す図である。
【図２１ａ】双方向フォールディングを示した図である。
【図２１ｂ】単方向フォールディングを示した図である。
【図２２ａ】Ｎ個のプロセッサを用いた双方向フォールディングの実施を示した図である。
【図２２ｂ】Ｎ個のプロセッサを用いた単方向フォールディングの実施を示した図である。
【図２３】簡単な再構成可能ＰＥの好ましいスライスを示した図である。
【発明を実施するための形態】
【００６８】
図３ａおよび図３ｂは、Ｇを取得するためコレスキー分解を行うＮ個のスカラーＰＥ５４1ないし５４N（５４）の好ましい実施形態を示す。簡略のため、４×４ Ｇ行列について説明し記述するが、このアプローチは、図３ａおよび図３ｂに示すように、任意に、４×４ Ｇ行列に拡張することができる。
【００６９】
図４ａは、上記のアルゴリズムをパフォームするための３次元計算依存グラフ（computational dependency graph）を示す。簡略のため、図４ａには、バンド幅が３である５×５行列の処理を示す。各ノードによりパフォームされる機能を、図４ｂ〜図４ｅに示す。図４ｂにおいて五角形で表す機能は、式２０および式２１を実行する。
【００７０】
【数２１】
【００７１】
ａout←ｙ 式２１
【００７２】
←は同時代入を示す。ａinは下位レベルから当該ノードへの入力であり、ａoutは上位レベルへの出力である。図４ｃは、式２２および式２３を実行する四角形で表される機能である。
【００７３】
ｙ←ｚ* 式２２
ａout←ａin−｜ｚ｜2 式２３
【００７４】
図４ｄは、式２４、式２５、および式２６を実行する八角形で表される機能である。
【００７５】
ｙ←ｗ 式２４
ｘ←ａin／ｗ 式２５
ａout←ｘ 式２６
【００７６】
図４ｅは、式２７、式２８、および式２９を実行する円で表される機能である。
【００７７】
ｙ←ｗ 式２７
ｘ←ｚ 式２８
ａout←ａin−ｗ×ｘ 式２９
【００７８】
図５ａは、４×４ Ｇ行列に対するベクトルベースのコレスキー分解のステージ１を、２次元スカラーベースアプローチにマップする様子を示した図である。各ベクトルプロセッサ５２、５４は、図５ａに示すように、少なくとも１つのスカラープロセッサ５６、５８、６０、６２にマップされる。各スカラープロセッサ５６、５８、６０、６２は、メモリセルａijに関係付けしてある。各プロセッサ５６、５８、６０、６２でパフォームされる機能が、図５ｂ〜図５ｅに示されている。図５ｂには、五角形で表される機能５６が示されており、これは式３０および式３１を実行する。
【００７９】
【数２２】
【００８０】
ａij：＝ｙ 式３１
【００８１】
：＝は逐次代入を示す。ｙは下側のプロセッサに伝送される値を示す。図５ｃには、八角形で表される機能５８が示されており、これは式３２、式３３、および式３４を実行する。
【００８２】
ｙ←ｗ 式３２
ｘ←ａij／ｗ 式３３
ａij：＝ｘ 式３４
【００８３】
ｗは上側のプロセッサから伝送された値を示す。図５ｄには、四角形で表される機能６０が示されており、これは式３５および式３６を実行する。
【００８４】
ｙ←ｚ* 式３５
ａij：＝ａij−｜ｚ｜2 式３６
【００８５】
ｘは右側のプロセッサに伝送される値を示す。図５ｅには、円で表される機能６２示されており、これは式３７、式３８、および式３９を実行する。
【００８６】
ｙ←ｗ 式３７
ｘ←ｚ 式３８
ａij：＝ａij−ｗ×ｚ 式３９
【００８７】
図６ａ〜図６ｄには、４つの逐次ステージ（ステージ１ないし４）における、プロセッサ５６、５８、６０、６２によるデータフローが示されている。図６ａ〜図６ｄに示すように、各ステージの後、プロセッサ５６、５８の列がドロップオフする。この処理には、４処理サイクルを必要とし、一般にはＮサイクルを必要とする。各ステージにつき１処理サイクルを必要とする。図５ａに示すように、４×４ Ｇ行列を判定するのに、１０個のスカラープロセッサを必要とする。Ｎ×Ｎ行列の場合、必要なプロセッサの数は、式４０による。
【００８８】
【数２３】
【００８９】
図６ｅ〜図６ｊには、５×５バンド行列に関する処理フローが示されている。アクティブなプロセッサを実線で示す。このバンド行列では、左下の３つのエントリ（ａ41、ａ51、ａ52、図６ｅ〜図６ｊでは図示せず）が０である。図６ｅに示すように、ステージ１では、上側の６つのプロセッサがオペレートしている。図６ｆに示すように、ステージ１でアクティブな６つのプロセッサが、ｇ11、ｇ21、ｇ31と、ステージ２で使用する３つの即値結果α22、α32、α33を決定する。
【００９０】
ステージ２では、６つのプロセッサ（α22，α32，α33，
【００９１】
【数２４】
【００９２】
）がオペレートしている。ステージ２では、図６ｇ（ステージ３）に示すように、ｇ22、ｇ32、ｇ42の値と、β33、β43、β44の即値結果が決定される。図６ｈ（ステージ４）では、ｇ33、ｇ43、ｇ53の値と、γ44、γ54、γ55の即値結果が判定される。図６（ステージ５）では、ｇ44、ｇ54と、即値δ55が決定される。図６ｊ（最終ステージ）では、残りの値ｇ55が利用できる。図に示すように、バンド行列という行列の性質から、ロードされない行列要素に対応する左下のプロセッサは不要であり、図示していない。
【００９３】
図６ａ〜図６ｄの簡略な説明は、図７に示すように、Ｎ×Ｎ行列に拡張することができる。これら図に示すように、最上部のプロセッサ５６は、五角形で表される機能をパフォームする。八角形で表される機能のプロセッサ５８は、第１列に沿って下方に拡張され、四角形／五角形を組み合わせた形で表される二重目的のプロセッサ６４は、主対角に沿って拡張される。残りのプロセッサ６６は、八角形／円を組み合わせた形で表される二重目的のプロセッサ６６である。この構成によって、スカラープロセッサだけを用いて、Ｎ×Ｎ Ｇ行列がＮ処理サイクルで決定される。
【００９４】
行列のバンド幅が、限られた幅、例えばＰしかない場合、ＰＥの数を減らすことができる。説明のため、仮にＰがＮ−１に等しい場合には、ａN1用の左下のプロセッサがドロップオフする。仮にＰがＮ−２に等しい場合には、さらに２つのプロセッサ（ａN-1 1，ａN2）がドロップオフする。
【００９５】
スカラーＰＥの数が減少していく様子を、図８ａ〜図８ｅおよび図９ａ、図９ｂに関して説明する。図８ａ〜図８ｅには、図６ａ〜図６ｄの４スカラープロセッサ・インプリメンテーションについての１次元実行プレーン（execution plane）が説明されている。図８ｅの遅延素子６８が、図８ａに示すように、各同時接続（concurrent connection）において挿入される。図８ｅの遅延素子６８は、式４１によって、入力ｙを遅延させて、逐次出力ｘとする。
【００９６】
ｙ：＝ｘ 式４１
【００９７】
タイムｔ1から開始する各処理サイクルにおいて、プロセッサは、実行プレーンを表す斜線が示すように、逐次に処理を行う。この様子を説明すると、タイムｔ1では、ａ11用のプロセッサ５６だけがオペレートする。タイムｔ2では、ａ21用のプロセッサ５８だけがオペレートし、タイムｔ3では、ａ31およびａ22用のプロセッサ５８、６０がオペレートする。以降、ステージ４まで同様に続いて、タイムｔ16では、ａ44用のプロセッサ５６だけがオペレートする。その結果、Ｎステージの処理全体では、Ｎ2のクロックサイクルが必要になる。
【００９８】
複数の行列を２次元スカラー処理アレイによりパイプライン処理することができる。図８ａ〜図８ｄに示すように、ある特定の実行プレーンで、ｔ1からｔ16までがアクティブである。あるステージでは、実行プレーンの数に等しい数までの行列を、同時に処理することができる。ステージ１について説明すると、第１の行列が斜線ｔ1に沿って処理される。次のクロックサイクルで、第１の行列はプレーンｔ2に渡され、プレーンｔ1は第２の行列のために使用される。このパイプラインは、任意の数の行列について続けることができる。パイプライン処理の１つの難点は、パイプライン処理においては、行列データの利用スケジュールが処理速度の低下を招くような場合には、全ての行列に関するデータを保存する必要がある点にある。
【００９９】
行列のグループがステージ１でパイプライン処理された後、その行列のグループはステージ２でパイプライン処理され、以降、ステージＮまでこれが続く。パイプライン処理を用いることにより、プロセッサの利用率ばかりか、アレイのスループットも劇的に向上する。
【０１００】
各クロックサイクルにおいて、プロセッサ５６、５８、６０、６２が全て使用されるわけではないので、行列を１つだけ処理する場合、ＰＥ５６、５８、６０、６２を実行プレーン間で共用することによって、ＰＥの数を減らすことができる。図９ａおよび図９ｂは、ＰＥを減らすための２つの好ましいインプリメンテーションを示す。図９ａに示すように、実行プレーンに垂直な（行列の対角に沿った）線が、第１列の各ＰＥ５６、５８に関して示されている。各垂直な線に沿ったプロセッサ５６、５８、６０、６２は、全て、異なる処理サイクルでオペレートするので、その機能５６、５８、６０、６２を、下方に射影されるような単一のプロセッサ６６、６４によって実行することができる。処理機能５６、６０は、新しいコンバイン機能６４によって実行される。処理機能５８、６２は、新しいコンバイン機能６６によって実行される。遅延素子６８およびプロセッサ間の接続も射影される。最も左側のＰＥは、二重機能素子６６を使用するものとして示されているが、非バンド行列にとって都合がよいのであれば、この素子は八角形で表される機能５８だけを実行するように簡略化することができる。
【０１０１】
図１０ａは、Ｎ×Ｎ Ｇ行列に対応できるように図９ａを拡張したものである。図１０ａに示すように、Ｎ個のプロセッサ６６、６４を使用して、Ｎ×Ｎ Ｇ行列を処理する。図３ａに示すように、図１０ａの処理機能は、Ｎ個のスカラープロセッサ５４によってパフォームすることができる。バンド行列の場合は、バンド幅Ｐと同じ数のスカラープロセッサを使用して、Ｇ行列を処理することができる。
【０１０２】
図３ａのインプリメンテーションにおいては、各プロセッサを１つおきのクロックサイクルで使用する。偶数番のプロセッサが、あるサイクルでオペレートし、奇数番のプロセッサが、次のサイクルでオペレートする。例えば、図９ａのプロセッサ２（右から２番目）はタイムｔ2、ｔ4、ｔ6で処理を行い、プロセッサ３はタイムｔ3、ｔ5で処理を行う。その結果、アレイへの入力として２つのＧ行列をインタレースしながらアレイを処理することによって、同時に２つのＧ行列を決定することができる。このアプローチによれば、図７のインプリメンテーションに比べて、プロセッサ利用率が大幅に向上する。
【０１０３】
単一のアレイの処理時間を短縮するため、図９ｂのインプリメンテーションが利用される。図９ｂに示すように、１つおきのプロセッサ接続で遅延素子がドロップオフ（drop off）する。タイムｔ1では、ａ11用のプロセッサ５６だけがオペレートする。しかし、タイムｔ2では、ａ21、ａ22、ａ31用のプロセッサ５８、６０が全てオペレートしている。（元の行列の対角に沿った）垂直線に沿ったこのアレイの射影も、図９ｂに示されている。図示するように、遅延素子６８の数が半分に減少する。このアレイを使用した場合、Ｎ×Ｎ Ｇ行列の処理時間は、（ＮＰ−（Ｐ2−Ｐ）／２）となる。したがって、単一のＧ行列の処理時間が大幅に短縮される。
【０１０４】
図７、図３ａ、および図３ｂのインプリメンテーションの別の利点は、行列のバンド幅に応じて、各処理アレイをスケーリングすることができる点にある。バンド幅が小さい行列（下三角行列の要素が０）の場合、図７のそれらの要素のためのプロセッサ５８、６６をドロップアウトすることができる。図３ａおよび図３ｂに関しては、下三角行列の要素は図９ａおよび図９ｂの最も左側の垂直線に対応するので、それらの垂直線によって射影されるプロセッサはドロップアウトされる。図９ａを用いて説明すると、当該行列のバンド幅は、ａ41、ａ31、ａ42が０であるＰＥ５８、６２を有する。その結果、プロセッサ６６（最も左側の２つ）への射影は、この処理では不要である。その結果、これらのインプリメンテーションは、当該行列のバンド幅に応じてスケーリングすることができる。
【０１０５】
図９ｃ〜図９ｎには、バンド幅が３である５×５バンド行列に関する、１つおきの接続に遅延が生じる、各処理サイクルごとのタイミング図が示されている。各時間期間においては、各プロセッサに関連付けをした値が示されている。アクティブなプロセッサを実線で示す。図に示すように、ステージ１、タイム０を示す図９ｃの左上のプロセッサ（
【０１０６】
【数２５】
【０１０７】
）から、ステージ５を示す図９ｎの右下のプロセッサ（δ55）へと、処理が伝播していく。図に示すように、バンド行列という行列の性質のため、非バンド行列を処理する左下のプロセッサは不要であり、図示していない。
【０１０８】
図９ｏ〜図９ｚには、図９ｂなどによる、５×５バンド行列を処理する線形アレイの各処理サイクルごとのタイミング図とメモリアクセスが示されている。図示するように、５×５行列のバンド幅は３であるので、必要なプロセッサは３個のみである。バンド行列を処理するため、３個のプロセッサを必要とすることが、図示されている。さらに図示するように、各ステージは比較的高いプロセッサの利用効率を有しており、この利用効率はＮ／ｐが増加するにつれて増加する。
【０１０９】
ＰＥの複雑さを減らすために、除算および平方根を求める機能は、これらＰＥで実行しない（除かれる）。除算および開平は、より複雑であるから、加算器、減算器、乗算器でインプリメントするよりは、ＡＳＩＣにインプリメントされる。
【０１１０】
除算または開平をパフォームする機能は、五角形および八角形で表される機能５６、５８の２つだけである。図６ａ〜図６ｄに示すように、あるステージについて、五角形および八角形で表される機能５６、５８は、全て、１ステージの間に単一の列で実行される。特に、これらの列の各々は、最上部に五角形５８をもち、その下に八角形５８をもつ。各八角形５８は同時にそのｗ入力をそのｙ出力に代入するので、五角形５６の出力は、ｗの値をいずれかのａij用に直ちに保存しなくても、列全体に行き渡る。八角形５８は、ｗ入力を使用してｘ出力も生成し、ｘ出力もａijにフィードバックされる。ｘ出力は、四角形および円で表される機能６０、６２によって、ａijの計算において使用される。その結果、各八角形のｘ出力の値だけが判定されればよい。八角形のｘ出力は、その八角形５８のａijを、五角形５６のｙ出力であって、各八角形５８で同じ値となるｗ入力の値で除算したものである。したがって、除算／開平機能は、八角形５８でｘを計算する際に、実行する必要があるだけである。
【０１１１】
各八角形の出力ｘは、式３４および式３０を用いて、その八角形のａijを五角形のａijの平方根で割ったものである。あるステージについて、各八角形プロセッサにおいて、除算器に代えて乗算器を使用した場合には、五角形のａijの平方根の代りに、その平方根の逆数を判定しさえすればよく、除算機能を五角形プロセッサにおいてだけでパフォームされるように分離して、アレイ全体の複雑さを緩和することができる。平方根の逆数は、五角形に関連付けをした行列要素のａijとして、その逆数の代りに、保存される。このようにすると、後で前進代入および後退代入を行う際にも都合がよい。それらのアルゴリズム中の除算機能がこの逆数を掛ける乗算に変り、他のＰＥ、すなわち図１２ｄおよび図１５ｄのｘ出力でも除算器の必要がなくなるからである。図９ａおよび図９ｂに示す五角形の機能５６は、同じプロセッサ６４によってパフォームされるので、図１０ａおよび図１０ｂに示すように、五角形／四角形プロセッサ６４からの入力と、そのプロセッサ６４への出力とを有する単一の逆数／開平回路７０を用いて、プロセッサ６６、６４をインプリメントすることができる。平方根の逆数を求めた結果は、プロセッサ６６に渡されていく。図１１ａおよび図１１ｂは、図１０ａおよび図１０ｂに対応する。逆数／開平回路７０を分離したことによって、他のプロセッサ６６、６４の複雑さが緩和される。逆数／開平回路７０は、逆数回路および開平回路を用いてインプリメントすることができるが、ＬＵＴ、特にＦＰＧＡ（field programmable gate array）用のＬＵＴを用いてインプリメントするのが好ましい。ただし、メモリはコストエフィシエント（cost efficient）である。
【０１１２】
コレスキーファクタＧが判定された後、図１２ａおよび図１２ｂに示すような前進代入を用いて、ｙが決定される。前進代入のアルゴリズムは次のようになる。
【０１１３】
【数２６】
【０１１４】
バンド行列の場合、アルゴリズムは次のようになる。
【０１１５】
【数２７】
【０１１６】
ｇLKはコレスキー行列ＧのＬ行Ｋ列に相当する要素である。
【０１１７】
図１２ａおよび図１２ｂは、スカラープロセッサを用いた、４×４ Ｇ行列に関する前進代入の２つの実施形態である。図１２ｃの星形で表される機能７２と、図１２ｄのひし形で表される機能７４の２つの機能が、プロセッサ７２、７４によって実行される。星形の機能７２は、式４２および式４３を実行する。
【０１１８】
ｙ←ｗ 式４２
ｘ←ｚ−ｗ×ｇij 式４３
【０１１９】
ひし形の機能７４は、式４４および式４５を実行する。
【０１２０】
ｘ←ｚ／ｇij 式４４
ｙ←ｘ 式４５
【０１２１】
図１２ａに示すようにＰＥの同時接続の間に遅延素子を挿入し、実行プレーン（ｔ1からｔ7）に垂直なアレイを射影することにより、そのアレイを線形アレイ上に射影することができる。
【０１２２】
【数２８】
【０１２３】
から得た受信ベクトルの値ｒ1〜ｒ4をアレイにロードし、アレイからｙ1〜ｙ4出力を得る。ひし形の機能７４は主対角に沿ってのみ存在するので、４つのＰＥからなるアレイを、図１３ａに示すようにＮ個のＰＥを用いてＮ×Ｎ行列を処理するように拡張することができる。このアレイの処理時間は２Ｎサイクルとなる。
【０１２４】
各ＰＥは１つおきの処理サイクルでのみ使用されるので、遅延素子の半数は、図１２ｂに示すように削除することができる。この射影される線形アレイは、図１３ｂに示すように任意のＮ×Ｎ行列を処理するように拡張することができる。このアレイの処理時間はＮサイクルとなる。
【０１２５】
図１３ｂに示す射影先アレイのＰＥのサイクルごとのオペレーションが、図１４ａ〜図１４ｄに示されている。図１３ａに示す第１サイクルｔ1では、ｒ1が左側のプロセッサ１（７４）にロードされ、ｙ1がｒ1とｇ11を用いて決定される。図１４ｂに示す第２サイクルｔ2では、ｒ2、ｒ3がロードされ、ｇ31、ｇ21、ｇ22が処理され、ｙ2が決定される。図１４ｃに示す第３サイクルｔ3では、ｒ4がロードされ、ｇ41、ｇ42、ｇ32、ｇ33がロードされ、ｙ3が決定される。図１４ｄに示す第４サイクルｔ4では、ｇ43、ｇ44が処理され、ｙ4が決定される。
【０１２６】
図１２ｅ〜図１２ｊには、５×５バンド行列の各処理サイクルに関するタイミング図が示されている。図１２ｅは、左下隅の３つのエントリが０というバンド行列の性質（バンド幅が３の場合）を示している。
【０１２７】
コレスキー分解のときと同様に、前進代入でも、同じＰＥが利用できることを示すために、図１２ｆはステージ６から開始する。ステージ６は、図９ｃ〜図９ｎの最終ステージの後のステージである。
【０１２８】
同様に、図１２ｋ〜図１２ｐは、図９ｏ〜図９ｚのプロセッサが前進代入もパフォームできるように拡張した例を示す。これらの図においては、ステージは、コレスキー分解を行う５つのステージの後のステージ６から開始される。この処理は、各処理サイクルに対して、ステージ６のタイム０（図１２ｋ）から、ステージ６のタイム４（図１２ｏ）の後の最終結果（図１２ｐ）まで、パフォームされる。
【０１２９】
前進代入によってｙ変数が判定された後、後退代入によってデータベクトルを判定することができる。後退代入は次のサブルーチンによって実行される。
【０１３０】
【数２９】
【０１３１】
バンド行列の場合、次のサブルーチンが用いられる。
【０１３２】
【数３０】
【０１３３】
（・）*は複素共役関数を示す。
【０１３４】
【数３１】
【０１３５】
は、コレスキーファクタＧについて判定された対応する要素の複素共役である。ＹLはｙの対応する要素である。
【０１３６】
後退代入は、４×４処理アレイに関する図１５ａおよび図１５ｂに示すように、星形およびひし形の機能７６、７８を用いるスカラープロセッサによってもインプリメントされる。しかし、これらの機能は、図１５ｃおよび図１５ｄに示すように、Ｇ行列の値の複素共役を用いてパフォームされる。したがって、式４２〜式４５は、それぞれ、式４６〜式４９となる。
【０１３７】
ｙ←ｗ 式４６
【０１３８】
【数３２】
【０１３９】
ｙ←ｘ 式４９
【０１４０】
プロセッサ７６、７８の間の同時代入で、遅延素子６８を挿入することにより、図１５ａのアレイは、実行プレーンを横断して線形アレイに射影される。このアレイは、Ｎ×Ｎ行列を処理するため、図１６ａに示すように拡張することができる。ｙベクトルの値が図１６ａのアレイにロードされ、データベクトルｄが出力される。このアレイは、ｄを判定するのに２Ｎクロックサイクルを要する。１つおきのプロセッサが１つおきのクロックサイクルでオペレートするので、２つのｄを同時に判定することができる。
【０１４１】
図１６ａの各プロセッサ７６、７８は１つおきのクロックサイクルでオペレートするので、図１５ｂに示すように１つおきの遅延素子を削除することができる。図１５ｂの射影先アレイは、Ｎ×Ｎ行列を処理するため、図１６ｂに示すように拡張することができる。このアレイは、ｄを判定するのにＮクロックサイクルを要する。
【０１４２】
図１６ｂの射影先アレイのＰＥ７６、７８のサイクルごとの動作が、図１７ａ〜図１７ｄに示されている。図１７ａに示す第１サイクルｔ1では、ｙ4がロードされ、
【０１４３】
【数３３】
【０１４４】
が処理され、ｄ4が決定される。図１７ｂに示す第２サイクルｔ2では、ｙ2、ｙ3がロードされ、
【０１４５】
【数３４】
【０１４６】
、
【０１４７】
【数３５】
【０１４８】
が処理され、ｄ3が決定される。図１７ｃに示す第３サイクルｔ3では、ｙ1がロードされ、
【０１４９】
【数３６】
【０１５０】
および
【０１５１】
【数３７】
【０１５２】
が処理され、ｄ2が決定される。図１７ｄに示す第４サイクルｔ4では、
【０１５３】
【数３８】
【０１５４】
、
【０１５５】
【数３９】
【０１５６】
が処理され、ｄ4が決定される。
【０１５７】
図１５ｅ〜図１５ｊには、後退代入を実行できるようにするための、図１２ｅ〜図１２ｊのプロセッサの拡張が示されている。図１５ｅは、左下隅の３つのエントリが０というバンド行列の性質を示している。
【０１５８】
タイミング図は、前進代入のステージ６の後に置かれたステージ７から開始する。処理は、ステージ７のタイム０（図１５ｆ）から開始し、ステージ７のタイム４（図１５ｊ）で完了する。ステージ７のタイム４（図１５ｊ）の後、全てのデータｄ1からｄ5が決定される。
【０１５９】
同様に、図１５ｋ〜図１５ｐには、後退代入も実行できるようにするための、図１２ｋ〜図１２ｐのプロセッサの拡張が示されている。これらの図は、前進代入のステージ６の後、ステージ７から開始する。処理は、ステージ７のタイム０（図１５ｋ）から最終結果（図１５ｐ）の各処理サイクルで実行される。図９ｃ〜図９ｎと、図１２ｅ〜図１２ｊと、図１５ｅ〜図１５ｊとに示すように、バンド行列の場合は、コレスキー分解と、前進代入と、後退代入とを実行するための２次元アレイのプロセッサ数を減らすことができる。図９ｏ〜図９ｚ、図１２ｋ〜図１２ｐに示すように、線形アレイのプロセッサ数は、行列の次元数からバンド行列のバンド幅に減らされる。
【０１６０】
前進代入および後退代入に関する個々のＰＥ７２、７４、７６、７８の複雑さを軽減するため、図１８ａおよび図１８ｂに示すように、ＰＥ７２、７４、７６、７８から除算機能８０を分離することができる。図１８ａおよび図１８ｂは、それぞれ、図１６ａおよび図１６ｂに対応する。ＰＥ７２、７４、７６、７８に関連する前進代入および後退代入のためのデータは異なるが、ＰＥ７２、７４、７６、７８によってパフォームされる機能は同じである。除算器８０は、除算機能をパフォームするために、最も右側のＰＥ７４、７８によって使用される。除算器８０は、逆数値を判定するためのＬＵＴとしてインプリメントされ、ＬＵＴは、最も右側のプロセッサ７４、７８によって乗算において使用される。前進代入および後退代入を行う際には、コレスキー分解の実行によって得た逆数がすでにメモリに存在しているので、前進代入および後退代入のための逆数の乗算には、すでにメモリに格納されている逆数を利用することができる。
【０１６１】
３つの全ての処理（Ｇの判定、前進代入および後退代入）で、計算データフローはＮまたはバンド幅Ｐが同じフローとなるので、３つの機能を全て、同じ再構成可能アレイで実行することができる。再構成可能アレイの各ＰＥ８４、８２は、図１９ａおよび図１９ｂに示すように、Ｇを判定する機能と前進代入および後退代入をパフォームする機能をパフォームさせることができる。最も右側のプロセッサ８２は、五角形／四角形とひし形の機能６４、７４、７８を実行することができる。他のプロセッサ８４は、円／八角形と星形の機能６６、７２、７６をパフォームすることができる。コレスキー分解を実行する場合、最も右側のＰＥ８２は、五角形／四角形の機能６４を用いてオペレートし、他のＰＥ８４は、円／八角形の機能６６を用いてオペレートする。前進代入および後退代入を実行する場合、最も右側のプロセッサ８２は、ひし形の機能７４、７８を用いてオペレートし、他のＰＥ８４は、星形の機能７２、７６を用いてオペレートする。ＰＥ８２、８４は好ましくは、必要な機能をパフォームするように構成される。再構成可能アレイを用いることにより、各ＰＥ８２、８４は、前進代入および後退代入の２つの算術機能と、コレスキー分解に関する４つの機能を実行し、ＰＥ８２、８４ごとに実行される算術機能は全部で６つとなる。これらの機能は、演算論理ユニット（ＡＬＵ）と適切な制御ロジック、またはその他の手段で実行することができる。
【０１６２】
再構成可能アレイ内の個々のＰＥ８２、８４の複雑さを軽減するため、除算および開平機能８６は、好ましくは、逆数および開平装置８６としてアレイから切り離される。逆数および開平装置８６は、好ましくは、図２０ａおよび図２０ｂに示すように、前進代入および後退代入において最も右側のＰＥ８２によって、乗算において使用される逆数を判定し、最も右側のプロセッサのデータを用いた乗算において使用され、ＰＥ８４に渡される平方根の逆数を判定する。逆数と平方根の逆数の判定は、好ましくは、ＬＵＴを用いて実行される。あるいは、除算および開平機能ブロック８６は、除算回路と開平回路とすることもできる。
【０１６３】
ＰＥ８２、８４の数をさらに減らすために、フォールディング（folding）が用いられる。図２１ａおよび図２１ｂにフォールディングが示されている。フォールディングでは、線形システム解法のためにＰ個のＰＥ８２、８４を使用する代りに、より少ない数ＦのＰＥがＱ段のフォールドで使用される。例えば、Ｐを９個のＰＥ８２、８４とした場合、３段のフォールドでは、３個のＰＥ８２、８４が９個のＰＥの機能をパフォームする。フォールディングの１つの難点は、縮小されたアレイの処理時間がＱ倍に増加することである。１つの利点は、プロセッサ利用度の効率が一般に増大することである。３段のフォールドの場合、処理時間は３倍になる。したがって、プロセッサ数の最小化とデータを処理するのに許容できる最大処理時間とのトレードオフに基づいて、フォールドのステージ数が選択される。
【０１６４】
図２１ａには、図１１ｂのアレイを３段にフォールドすることによって、１２個のＰＥの機能を４個のＰＥ７６1、７６2、７６3、７６4／７８でパフォームする双方向フォールドが示されている。ＰＥ７６1、７６2、７６3、７６4／７８の間に遅延素子を挿入する代りに、デュアルポートメモリ８６1、８６2、８６3、８６4（８６）を使用して、各フォールドのデータを保存する。遅延素子（デュアルポートメモリ８６）は、図１２ａの実施形態でのように各ＰＥ接続ごとに存在できるが、図１２ｂのインプリメンテーションでのように１つおきの接続ごとに存在するものとして示されている。デュアルポートメモリの代りに、２組のシングルポートメモリを使用することもできる。
【０１６５】
第１のフォールドにおいては、各ＰＥのデータは、それに関連づけられたデュアルポートメモリ８６のフォールド１用のアドレスに保存される。行列のデータもメモリセル８８1〜８８4（８８）からプロセッサ７６1〜７６3、７６4／７８に入力される。フォールド１のＰＥ７６4／７８とフォールド３のプロセッサ７６1の間にデータのラップアラウンドは起らないので、これらのプロセッサの間でデュアルポートメモリ８６は使用されない。しかし、フォールド１とフォールド２のプロセッサ７６1の間およびフォールド２とフォールド３のプロセッサ７６4／７８の間に単一のアドレスが必要とされるので、デュアルポートメモリ８６が破線で示されている。第２のフォールドの間、各プロセッサのデータはフォールド２用のメモリアドレスに保存される。行列のデータもフォールド２用にＰＥ７６1〜７６3、７６4／７８に入力される。フォールド２のＰＥ７６1用のデータはフォールド１のＰＥ７６1から来るが、これらは物理的には同じＰＥ７６1であるので、この接続は（示されてはいるが）必要がない。第３のフォールドにおいて、各ＰＥのデータはフォールド３用のメモリアドレスに保存される。行列のデータもフォールド３用にＰＥ７６1〜７６3、７６4／７８に入力される。フォールド３のＰＥ７６4／７８用のデータはフォールド２のＰＥ７６4／７８から来るので、この接続は必要がない。次の処理ステージでは、フォールド１から手順が繰り返される。
【０１６６】
図２２ａは、図２１ａの双方向フォールドの実施形態をＮ個のＰＥ７６1〜７６N-1、７６N／７８に拡張したものである。ＰＥ７６1〜７６N-1、７６N／７８は機能的に線形アレイとして構成され、デュアルポートメモリ８６または２組のシングルポートメモリをアクセスする。
【０１６７】
図２１ｂには、図１１ｂのアレイの単方向フォールドバージョンが示されている。第１のフォールドにおいて、各ＰＥのデータは、それに関連づけられたデュアルポートメモリのフォールド１用のアドレスに保存される。フォールド１のＰＥ７６4／７８とフォールド３のＰＥ７６1は物理的に接続されているが、動作上、これらのＰＥ間で直接データを伝送することはない。したがって、これらの間のメモリポート８６4はアドレスが１つ少ない記憶域をもつ。フォールド２のＰＥ７６4／７８は、ＰＥ間のリンク状の接続によって効率的にフォールド１のＰＥ７６1に結合される。同様に、フォールド３のＰＥ７６4／７８は、フォールド２のＰＥ７６1に結合される。
【０１６８】
図２２ｂは、図２０ｂの単方向フォールディングのインプリメンテーションをＮ個のＰＥに拡張したものである。ＰＥ７６1〜７６N-1、７６N／７８は、デュアルメモリの周りにリング状に機能的に配置される。
【０１６９】
フォールディングされたＰＥで、コレスキー分解、前進代入および後退代入をインプリメントするには、アレイ内のＰＥ７６4／７８などのＰＥは、コレスキー分解、前進代入および後退代入のためのプロセッサ機能とともに、各フォールドのためのプロセッサ機能もパフォームできなければならない。ＰＥ７６4／７８について図２０ａおよび図２０ｂに示すように。インプリメントによっては、追加されるＰＥに必要な機能が、そのインプリメンテーションの複雑さを増大させる。ＡＬＵを用いてフォールディングをインプリメントするには、１個のＰＥ（ＰＥ ７６4／７８など）は、１２種の演算機能（前進代入および後退代入のための４種とコレスキー分解のための８種）をパフォームするが、他のＰＥは６種の演算機能をパフォームするだけである。
【０１７０】
図２３には、コレスキー分解、前進代入および後退代入で定義される６種の機能全てをパフォームするのに使用できる、好ましい簡単な再構成可能ＰＥの１スライスが示されている。除算を１個のＰＥ（以下ＰＥ１という）に分離した後、このＰＥは使用される。好ましくは２つのスライスが使用され、一方はｘおよびｙの実数成分を生成するため、他方はそれらの虚数成分を生成するためのものである。添え字ｉおよびｒは、それぞれ、実数成分および虚数成分を示すのに使用される。
【０１７１】
信号ｗ、ｘ、ｙ、ｚは、先にＰＥ機能を定義する際に定義したものと同じである。信号ａqおよびａdはそれぞれ、処理のあるサイクルでリード（read）され、かつ／またはライト（write）されるＰＥのメモリロケーションの現在の状態と、次の状態とを表す。括弧内の名前は、第２のスライスで使用される信号を示す。
【０１７２】
この好ましいＰＥは、どのＰＥとしても使用できるが、他のＰＥから独立して除算機能をパフォームするＰＥ１の最適化に使用するのが望ましい。マルチプレクサ９４1から９４8への各入力にはラベル付けされており、「０」はその入力がＰＥ１だけに使用されることを、「−」はＰＥ１以外の全てのＰＥに使用されることを、「＋」は全てのＰＥに使用されることを示す。ＰＥ１の実数スライスの場合を除いて、ｉｓｑｒ入力は０に接続され、ＰＥ１の実数スライスの場合は、ｉｓｑｒ入力はａqr入力の平方根の逆数を生成する機能の出力に接続される。このような機能は、適当な固定小数点ワードサイズのＲＯＭを用いてＬＵＴとしてインプリメントすることができる。
【０１７３】
図２３に示すように、マルチプレクサ９４1と９４2の出力は、乗算器９６1によって掛け合される。マルチプレクサ９４3と９４4の出力は、乗算器９６2によって掛け合される。乗算器９６1と乗算器９６2の出力は、加算／減算回路９８によってコンバインされる。加算／減算回路９８の出力は、減算器９９によってマルチプレクサ９４5の出力とコンバインされる。減算器９９の出力は、マルチプレクサ９４8への入力となる。
【特許請求の範囲】
【請求項１】
データ信号の既知の拡散符号を用いて畳み込まれた前記データ信号の、推定された、または、既知の、チャネルレスポンスの畳み込みである行列Ａに関連付けされた受信ベクトルとして受信された複数の前記データ信号からデータを復元するための方法であって、
バンド幅Ｐを有するＮ×Ｎ行列ＡＨＡのコレスキーファクタを決定し（ここでＡＨはＡの共役転置（エルミート）であり、ＰはＮより小さい）、かつ、前記決定されたコレスキーファクタを前進代入および後退代入において使用してＰ個のスカラー・プロセシング・エレメントのアレイを使用することで線形方程式を解く、ことによって、受信ベクトルのデータを決定するステップと、
前記アレイの各スカラー・プロセシング・エレメントが、前記行列ＡＨＡの対角要素を受信し、前記コレスキーファクタの対応する対角要素を決定し、かつ前進代入および後退代入を実行するステップと
を具えたことを特徴とする方法。
【請求項２】
データ信号の既知の拡散符号を用いて畳み込まれた前記データ信号の、推定された、または、既知の、チャネルレスポンスの畳み込みである行列Ａ及びノイズ分散σ2に関連付けされた受信ベクトルとして受信された複数の前記データ信号からデータを復元するための方法であって、
バンド幅Ｐを有するＮ×Ｎ行列ＡHＡ＋σ2Ｉのコレスキーファクタを決定し（ここで、Ｉは、単位行列であり、ＡHは、Ａの共役転置（エルミート）であり、ＰはＮより小さい）、かつ、前記決定されたコレスキーファクタを前進代入および後退代入において使用してＰ個のスカラー・プロセシング・エレメントのアレイを使用することで線形方程式を解く、ことによって、受信ベクトルのデータを決定するステップと、
前記アレイの各スカラー・プロセシング・エレメントが、前記行列ＡHＡ＋σ2Ｉの対角要素を受信し、前記コレスキーファクタの対応する対角要素を決定し、かつ前進代入および後退代入を実行するステップと
を具えたことを特徴とする方法。
【請求項３】
請求項１又は２に記載の方法であって、スカラー・プロセシング・エレメントの前記アレイから、前記受信ベクトルのデータを出力するステップをさらに備えたことを特徴とする方法。
【請求項１】
データ信号の既知の拡散符号を用いて畳み込まれた前記データ信号の、推定された、または、既知の、チャネルレスポンスの畳み込みである行列Ａに関連付けされた受信ベクトルとして受信された複数の前記データ信号からデータを復元するための方法であって、
バンド幅Ｐを有するＮ×Ｎ行列ＡＨＡのコレスキーファクタを決定し（ここでＡＨはＡの共役転置（エルミート）であり、ＰはＮより小さい）、かつ、前記決定されたコレスキーファクタを前進代入および後退代入において使用してＰ個のスカラー・プロセシング・エレメントのアレイを使用することで線形方程式を解く、ことによって、受信ベクトルのデータを決定するステップと、
前記アレイの各スカラー・プロセシング・エレメントが、前記行列ＡＨＡの対角要素を受信し、前記コレスキーファクタの対応する対角要素を決定し、かつ前進代入および後退代入を実行するステップと
を具えたことを特徴とする方法。
【請求項２】
データ信号の既知の拡散符号を用いて畳み込まれた前記データ信号の、推定された、または、既知の、チャネルレスポンスの畳み込みである行列Ａ及びノイズ分散σ2に関連付けされた受信ベクトルとして受信された複数の前記データ信号からデータを復元するための方法であって、
バンド幅Ｐを有するＮ×Ｎ行列ＡHＡ＋σ2Ｉのコレスキーファクタを決定し（ここで、Ｉは、単位行列であり、ＡHは、Ａの共役転置（エルミート）であり、ＰはＮより小さい）、かつ、前記決定されたコレスキーファクタを前進代入および後退代入において使用してＰ個のスカラー・プロセシング・エレメントのアレイを使用することで線形方程式を解く、ことによって、受信ベクトルのデータを決定するステップと、
前記アレイの各スカラー・プロセシング・エレメントが、前記行列ＡHＡ＋σ2Ｉの対角要素を受信し、前記コレスキーファクタの対応する対角要素を決定し、かつ前進代入および後退代入を実行するステップと
を具えたことを特徴とする方法。
【請求項３】
請求項１又は２に記載の方法であって、スカラー・プロセシング・エレメントの前記アレイから、前記受信ベクトルのデータを出力するステップをさらに備えたことを特徴とする方法。
【図１】
【図２ａ】
【図２ｂ】
【図２ｃ】
【図２ｄ】
【図２ｅ】
【図２ｆ】
【図２ｇ】
【図２ｈ】
【図３ａ】
【図３ｂ】
【図４ａ】
【図４ｂ】
【図４ｃ】
【図４ｄ】
【図４ｅ】
【図５ａ】
【図５ｂ】
【図５ｃ】
【図５ｄ】
【図５ｅ】
【図６ａ】
【図６ｂ】
【図６ｃ】
【図６ｄ】
【図６ｅ】
【図６ｆ】
【図６ｇ】
【図６ｈ】
【図６ｉ】
【図６ｊ】
【図７】
【図８ａ】
【図８ｂ】
【図８ｃ】
【図８ｄ】
【図８ｅ】
【図９ａ】
【図９ｂ】
【図９ｃ】
【図９ｄ】
【図９ｅ】
【図９ｆ】
【図９ｇ】
【図９ｈ】
【図９ｉ】
【図９ｊ】
【図９ｋ】
【図９ｌ】
【図９ｍ】
【図９ｎ】
【図９ｏ】
【図９ｐ】
【図９ｑ】
【図９ｒ】
【図９ｓ】
【図９ｔ】
【図９ｕ】
【図９ｖ】
【図９ｗ】
【図９ｘ】
【図９ｙ】
【図９ｚ】
【図１０ａ】
【図１０ｂ】
【図１１ａ】
【図１１ｂ】
【図１２ａ】
【図１２ｂ】
【図１２ｃ】
【図１２ｄ】
【図１２ｅ】
【図１２ｆ】
【図１２ｇ】
【図１２ｈ】
【図１２ｉ】
【図１２ｊ】
【図１２ｋ】
【図１２ｌ】
【図１２ｍ】
【図１２ｎ】
【図１２ｏ】
【図１２ｐ】
【図１３ａ】
【図１３ｂ】
【図１４ａ】
【図１４ｂ】
【図１４ｃ】
【図１４ｄ】
【図１５ａ】
【図１５ｂ】
【図１５ｃ】
【図１５ｄ】
【図１５ｅ】
【図１５ｆ】
【図１５ｇ】
【図１５ｈ】
【図１５ｉ】
【図１５ｊ】
【図１５ｋ】
【図１５ｌ】
【図１５ｍ】
【図１５ｎ】
【図１５ｏ】
【図１５ｐ】
【図１６ａ】
【図１６ｂ】
【図１７ａ】
【図１７ｂ】
【図１７ｃ】
【図１７ｄ】
【図１８ａ】
【図１８ｂ】
【図１９ａ】
【図１９ｂ】
【図２０ａ】
【図２０ｂ】
【図２１ａ】
【図２１ｂ】
【図２２ａ】
【図２２ｂ】
【図２３】
【図２ａ】
【図２ｂ】
【図２ｃ】
【図２ｄ】
【図２ｅ】
【図２ｆ】
【図２ｇ】
【図２ｈ】
【図３ａ】
【図３ｂ】
【図４ａ】
【図４ｂ】
【図４ｃ】
【図４ｄ】
【図４ｅ】
【図５ａ】
【図５ｂ】
【図５ｃ】
【図５ｄ】
【図５ｅ】
【図６ａ】
【図６ｂ】
【図６ｃ】
【図６ｄ】
【図６ｅ】
【図６ｆ】
【図６ｇ】
【図６ｈ】
【図６ｉ】
【図６ｊ】
【図７】
【図８ａ】
【図８ｂ】
【図８ｃ】
【図８ｄ】
【図８ｅ】
【図９ａ】
【図９ｂ】
【図９ｃ】
【図９ｄ】
【図９ｅ】
【図９ｆ】
【図９ｇ】
【図９ｈ】
【図９ｉ】
【図９ｊ】
【図９ｋ】
【図９ｌ】
【図９ｍ】
【図９ｎ】
【図９ｏ】
【図９ｐ】
【図９ｑ】
【図９ｒ】
【図９ｓ】
【図９ｔ】
【図９ｕ】
【図９ｖ】
【図９ｗ】
【図９ｘ】
【図９ｙ】
【図９ｚ】
【図１０ａ】
【図１０ｂ】
【図１１ａ】
【図１１ｂ】
【図１２ａ】
【図１２ｂ】
【図１２ｃ】
【図１２ｄ】
【図１２ｅ】
【図１２ｆ】
【図１２ｇ】
【図１２ｈ】
【図１２ｉ】
【図１２ｊ】
【図１２ｋ】
【図１２ｌ】
【図１２ｍ】
【図１２ｎ】
【図１２ｏ】
【図１２ｐ】
【図１３ａ】
【図１３ｂ】
【図１４ａ】
【図１４ｂ】
【図１４ｃ】
【図１４ｄ】
【図１５ａ】
【図１５ｂ】
【図１５ｃ】
【図１５ｄ】
【図１５ｅ】
【図１５ｆ】
【図１５ｇ】
【図１５ｈ】
【図１５ｉ】
【図１５ｊ】
【図１５ｋ】
【図１５ｌ】
【図１５ｍ】
【図１５ｎ】
【図１５ｏ】
【図１５ｐ】
【図１６ａ】
【図１６ｂ】
【図１７ａ】
【図１７ｂ】
【図１７ｃ】
【図１７ｄ】
【図１８ａ】
【図１８ｂ】
【図１９ａ】
【図１９ｂ】
【図２０ａ】
【図２０ｂ】
【図２１ａ】
【図２１ｂ】
【図２２ａ】
【図２２ｂ】
【図２３】
【公開番号】特開２０１２−１５０８２７（Ｐ２０１２−１５０８２７Ａ）
【公開日】平成２４年８月９日（２０１２．８．９）
【国際特許分類】
【出願番号】特願２０１２−６０９５８（Ｐ２０１２−６０９５８）
【出願日】平成２４年３月１６日（２０１２．３．１６）
【分割の表示】特願２００７−３０４９５１（Ｐ２００７−３０４９５１）の分割
【原出願日】平成１４年１１月１３日（２００２．１１．１３）
【出願人】（５９６００８６２２）インターデイジタル テクノロジー コーポレーション (871)
【Ｆターム（参考）】
【公開日】平成２４年８月９日（２０１２．８．９）
【国際特許分類】
【出願日】平成２４年３月１６日（２０１２．３．１６）
【分割の表示】特願２００７−３０４９５１（Ｐ２００７−３０４９５１）の分割
【原出願日】平成１４年１１月１３日（２００２．１１．１３）
【出願人】（５９６００８６２２）インターデイジタル テクノロジー コーポレーション (871)
【Ｆターム（参考）】
[ Back to top ]