(57)【要約】  線形システムを解くためにＰＥ（５４〜５４Ｎ）を利用する。本発明の一実施形態（図３ｂ）では、コレスキーファクタを判定するため、行列の対角要素がスカラーＰＥに射影される。別の実施形態では、コレスキーファクタを判定するため、２次元スカラーアレイが使用される。限られたバンド幅をもつ行列の場合、使用するプロセッサの数を減らした、プロセッサ（５４〜５４Ｎ）を用いることができる。
2005509959.tif 000002
【特許請求の範囲】
【請求項１】
Ｎ×Ｎ行列のコレスキーファクタを判定する装置であって、
ＰＥ（processing element）のアレイであって、該アレイの各ＰＥは、前記Ｎ×Ｎ行列の対角要素を受信し、前記コレスキーファクタの対応する対角要素を判定するアレイを備えたことを特徴とする装置。
【請求項２】
請求項１に記載の装置において、前記ＰＥは、スカラーＰＥであることを特徴とする装置。
【請求項３】
請求項１に記載の装置において、前記Ｎ×Ｎ行列は、バンド幅がＰであり、前記ＰＥの数は、Ｐであり、Ｐは、Ｎ未満であることを特徴とする装置。
【請求項４】
請求項１に記載の装置において、Ａは、ジョイント検出レシーバに関連付けした既知の拡散符号を用いてチャネルレスポンスを畳み込む（convolve）ことによって生成される行列であり、前記Ｎ×Ｎ行列は、ＡHＡであることを特徴とする装置。
【請求項５】
請求項１に記載の装置において、Ａは、ジョイント検出レシーバに関連付けした既知の拡散符号を用いてチャネルレスポンスを畳み込むことによって生成される行列であり、σ2は、ノイズの分散であり、Ｉは、単位行列であり、前記Ｎ×Ｎ行列は、ＡHＡ＋σ2Ｉであることを特徴とする装置。
【請求項６】
受信ベクトルとして受信された複数のデータ信号からデータを復元するレシーバであり、Ｎ×Ｎ行列のコレスキーファクタを判定することによって前記受信ベクトルのデータを判定するレシーバであって、
前記ＰＥのアレイは、各ＰＥが、前記Ｎ×Ｎ行列の対角要素を受信し、前記コレスキーファクタの対応する対角要素を判定することを特徴とするレシーバ。
【請求項７】
請求項６に記載のレシーバにおいて、前記ＰＥは、スカラーＰＥであることを特徴とするレシーバ。
【請求項８】
請求項６に記載のレシーバにおいて、前記Ｎ×Ｎ行列は、バンド幅がＰであり、前記ＰＥの数は、Ｐであり、Ｐは、Ｎ未満であることを特徴とするレシーバ。
【請求項９】
請求項６に記載のレシーバにおいて、Ａは、前記データ信号に関連付けをした既知の拡散符号を用いてチャネルレスポンスを畳み込むことによって生成される行列であり、前記Ｎ×Ｎ行列は、ＡHＡであることを特徴とするレシーバ。
【請求項１０】
請求項６に記載のレシーバにおいて、Ａは、前記データ信号に関連付けをした既知の拡散符号を用いてチャネルレスポンスを畳み込むことによって生成される行列であり、σ2は、ノイズの分散であり、Ｉは、単位行列であり、前記Ｎ×Ｎ行列は、ＡHＡ＋σ2Ｉであることを特徴とするレシーバ。
【請求項１１】
受信ベクトルとして受信された複数のデータ信号からデータを復元するＵＥ（user equipment）であって、Ｎ×Ｎ行列のコレスキーファクタを判定することによって前記受信ベクトルのデータを判定するＵＥであって、
レシーバは、
ＰＥのアレイであって、各ＰＥが、前記Ｎ×Ｎ行列の対角要素を受信し、前記コレスキーファクタの対応する対角要素を判定する、ＰＥのアレイを備えたことを特徴とするＵＥ。
【請求項１２】
請求項１１に記載のＵＥにおいて、前記ＰＥは、スカラーＰＥであることを特徴とするＵＥ。
【請求項１３】
請求項１１に記載のＵＥにおいて、前記Ｎ×Ｎ行列は、バンド幅がＰであり、前記ＰＥの数は、Ｐであり、Ｐは、Ｎ未満であることを特徴とするＵＥ。
【請求項１４】
請求項１１に記載のＵＥにおいて、Ａは、前記データ信号に関連付けをした既知の拡散符号を用いてチャネルレスポンスを畳み込むことによって生成される行列であり、前記Ｎ×Ｎ行列は、ＡHＡであることを特徴とするＵＥ。
【請求項１５】
請求項１１に記載のＵＥにおいて、Ａは、前記データ信号に関連付けをした既知の拡散符号を用いてチャネルレスポンスを畳み込むことによって生成される行列であり、σ2は、ノイズの分散であり、Ｉは、単位行列であり、前記Ｎ×Ｎ行列は、ＡHＡ＋σ2Ｉであることを特徴とするＵＥ。
【請求項１６】
受信ベクトルとして受信された複数のデータ信号からデータを復元する基地局であり、Ｎ×Ｎ行列のコレスキーファクタを判定することによって前記受信ベクトルのデータを判定する基地局であって、
レシーバは、
ＰＥのアレイであって、各ＰＥが、前記Ｎ×Ｎ行列の対角要素を受信し、前記コレスキーファクタの対応する対角要素を判定する、ＰＥのアレイを備えたことを特徴とする基地局。
【請求項１７】
請求項１６に記載の基地局において、前記ＰＥは、スカラーＰＥであることを特徴とする基地局。
【請求項１８】
請求項１６に記載の基地局において、前記Ｎ×Ｎ行列は、バンド幅がＰであり、前記ＰＥの数は、Ｐであり、Ｐは、Ｎ未満であることを特徴とする基地局。
【請求項１９】
請求項１６に記載の基地局において、Ａは、前記データ信号に関連付けをした既知の拡散符号を用いてチャネルレスポンスを畳み込むことによって生成される行列であり、前記Ｎ×Ｎ行列は、ＡHＡであることを特徴とする基地局。
【請求項２０】
請求項１６に記載の基地局において、Ａは、前記データ信号に関連付けをした既知の拡散符号を用いてチャネルレスポンスを畳み込むことによって生成される行列であり、σ2は、ノイズの分散であり、Ｉは、単位行列であり、前記Ｎ×Ｎ行列は、ＡHＡ＋σ2Ｉであることを特徴とする基地局。
【請求項２１】
Ｎ×Ｎ行列のコレスキーファクタを判定するのに使用し、かつ、この判定されたコレスキーファクタを前進代入および後退代入において使用し線形式を解く装置であって、
最大Ｎ個のスカラーＰＥからなるアレイであって、本アレイが、前記Ｎ×Ｎ行列の要素を受信するための入力を有し、前記スカラーＰＥが、それぞれ前記コレスキーファクタを判定し、前進代入および後退代入を実行するのに使用され、本アレイが、前記受信ベクトルのデータを出力するアレイを備えたことを特徴とする装置。
【請求項２２】
請求項２１に記載の装置において、前記スカラーＰＥは、それぞれ、前記コレスキーファクタを判定し、かつ前進代入および後退代入を実行するとき前記アレイによって処理される行列の対角要素を処理することを特徴とする装置。
【請求項２３】
請求項２１に記載の装置において、前記Ｎ×Ｎ行列は、バンド幅がＰであり、前記最大Ｎ個のスカラーＰＥの数は、Ｐであり、Ｐは、Ｎ未満であることを特徴とする装置。
【請求項２４】
請求項２１に記載の装置において、平方根および逆数デバイスをさらに備え、前記平方根および逆数デバイスは、前記アレイの単一のスカラーＰＥにのみ結合され、前記アレイのスカラーＰＥは、平方根および逆数機能をパフォームできないことを特徴とする装置。
【請求項２５】
請求項２４に記載の装置において、前記平方根および逆数デバイスは、ＬＵＴ（look up table）を使用することを特徴とする装置。
【請求項２６】
請求項２２に記載の装置において、各プロセッサは、前記Ｎ×Ｎ行列の複数の対角要素に対する処理を実行することを特徴とする装置。
【請求項２７】
請求項２６に記載の装置において、複数のフォールド（fold）の各々について、各スカラーＰＥは、前記Ｎ×Ｎ行列の１つの対角上の複数の要素のみを処理することを特徴とする装置。
【請求項２８】
請求項２７に記載の装置において、フォールドのステージ数は、前記スカラーＰＥの数を最小化し、前記Ｎ×Ｎ行列を処理する処理時間を最長許容時間未満にすることができることを特徴とする装置。
【請求項２９】
請求項２７に記載の装置において、前記スカラーＰＥは、データが前記アレイを双方向に流れるように、機能的に線形に構成されていることを特徴とする装置。
【請求項３０】
請求項２２に記載の装置において、遅延素子が各スカラーＰＥの間に動作可能に結合され、前記アレイは、２つのＮ×Ｎ行列を同時に処理できることを特徴とする装置。
【請求項３１】
請求項２２に記載の装置において、前記スカラーＰＥは、全て、共通の再構成可能なインプリメンテーションを有することを特徴とする装置。
【請求項３２】
受信ベクトルとして受信された複数のデータ信号からデータを復元するレシーバであり、Ｎ×Ｎ行列のコレスキーファクタを判定し、この判定されたコレスキーファクタを前進代入および後退代入において使用して前記受信データ信号の前記データを判定し、これにより前記受信ベクトルのデータを判定するレシーバであって、
最大Ｎ個のスカラーＰＥからなるアレイであって、該アレイが、前記Ｎ×Ｎ行列の要素と前記受信ベクトルとを受信するための入力を有し、各スカラーＰＥは、前記コレスキーファクタを判定し、前進代入および後退代入の実行において使用され、前記アレイが、前記受信ベクトルのデータを出力するアレイ
を備えたことを特徴とするレシーバ。
【請求項３３】
請求項３２に記載のレシーバにおいて、前記スカラーＰＥは、それぞれ、前記コレスキーファクタを判定し、前進代入および後退代入を実行するとき前記アレイによって処理される行列の対角要素を処理することを特徴とするレシーバ。
【請求項３４】
請求項３２に記載のレシーバにおいて、前記Ｎ×Ｎ行列は、バンド幅がＰであり、前記最大Ｎ個のスカラーＰＥの数は、Ｐであり、Ｐは、Ｎ未満であることを特徴とするレシーバ。
【請求項３５】
請求項３２に記載のレシーバにおいて、平方根および逆数デバイスをさらに備え、前記平方根および逆数デバイスは、前記アレイの単一のスカラーＰＥにのみ結合され、前記アレイのスカラーＰＥは、平方根および逆数機能を実行できないことを特徴とするレシーバ。
【請求項３６】
請求項３５に記載のレシーバにおいて、前記平方根および逆数デバイスは、ＬＵＴを使用することを特徴とするレシーバ。
【請求項３７】
請求項３３に記載のレシーバにおいて、前記スカラーＰＥは、前記Ｎ×Ｎ行列の複数の対角要素に対する処理を実行することを特徴とするレシーバ。
【請求項３８】
請求項３７に記載のレシーバにおいて、各スカラーＰＥは、複数のフォールドの各々について、前記Ｎ×Ｎ行列の１つの対角上の要素のみを処理することを特徴とするレシーバ。
【請求項３９】
請求項３８に記載のレシーバにおいて、フォールドのステージ数は、前記スカラーＰＥの数を最小化し、前記Ｎ×Ｎ行列を処理する処理時間を最長許容時間未満にすることができることを特徴とするレシーバ。
【請求項４０】
請求項３８に記載のレシーバにおいて、前記スカラーＰＥは、データが前記アレイを双方向に流れるように、機能的に線形に構成されたことを特徴とするレシーバ。
【請求項４１】
請求項３３に記載のレシーバにおいて、遅延素子が各スカラーＰＥの間に動作可能に結合され、前記アレイは、２つのＮ×Ｎ行列を同時に処理できることを特徴とするレシーバ。
【請求項４２】
請求項３３に記載のレシーバにおいて、前記スカラーＰＥは、全て共通の再構成可能なインプリメントを有することを特徴とするレシーバ。
【請求項４３】
受信ベクトルとして受信された複数のデータ信号からデータを復元するＵＥであり、Ｎ×Ｎ行列のコレスキーファクタを判定し、この判定されたコレスキーファクタを前進代入および後退代入において使用して前記受信データ信号の前記データを判定することによって、前記受信ベクトルのデータを判定するＵＥであって、
最大Ｎ個のスカラーＰＥからなるアレイであって、前記アレイは、前記Ｎ×Ｎ行列の要素と前記受信ベクトルを受信するための入力を有し、各スカラーＰＥは、前記コレスキーファクタを判定し、前進代入および後退代入の実行において使用され、前記アレイは、前記受信ベクトルのデータを出力するアレイを備えたことを特徴とするＵＥ。
【請求項４４】
請求項４３に記載のＵＥにおいて、各スカラーＰＥは、前記コレスキーファクタを判定し、前進代入および後退代入の実行において前記アレイによって処理される行列の対角要素を処理することを特徴とするＵＥ。
【請求項４５】
請求項４３に記載のＵＥにおいて、前記Ｎ×Ｎ行列は、バンド幅がＰであり、前記最大Ｎ個のスカラーＰＥの数は、Ｐであり、Ｐは、Ｎ未満であることを特徴とするＵＥ。
【請求項４６】
請求項４３に記載のＵＥにおいて、平方根および逆数デバイスをさらに備え、前記平方根および逆数デバイスは、前記アレイの単一のスカラーＰＥにのみ結合され、前記アレイのスカラーＰＥは、平方根および逆数機能を実行できないことを特徴とするＵＥ。
【請求項４７】
請求項４６に記載のＵＥにおいて、前記平方根および逆数デバイスは、ＬＵＴを使用することを特徴とするＵＥ。
【請求項４８】
請求項４４に記載のＵＥにおいて、各プロセッサは、前記Ｎ×Ｎ行列の複数の対角要素に対する処理を実行することを特徴とするＵＥ。
【請求項４９】
請求項４８に記載のＵＥにおいて、各スカラーＰＥは、複数のフォールドの各々について、前記Ｎ×Ｎ行列の１つの対角上の複数の要素のみを処理することを特徴とするＵＥ。
【請求項５０】
請求項４９に記載のＵＥにおいて、フォールドのステージ数は、前記スカラーＰＥの数を最小化し、前記Ｎ×Ｎ行列を処理する処理時間を最長許容時間未満にすることができることを特徴とするＵＥ。
【請求項５１】
請求項４９に記載のＵＥにおいて、前記スカラーＰＥは、データが前記アレイを双方向に流れるように、機能的に線形に構成されたことを特徴とするＵＥ。
【請求項５２】
請求項４４に記載のＵＥにおいて、遅延素子が各スカラーＰＥの間に動作可能に結合され、前記アレイは、２つのＮ×Ｎ行列を同時に処理できることを特徴とするＵＥ。
【請求項５３】
請求項４４に記載のＵＥにおいて、前記スカラーＰＥは、全て共通の再構成可能なインプリメントを有することを特徴とするＵＥ。
【請求項５４】
受信ベクトルとして受信された複数のデータ信号からデータを復元する基地局であって、Ｎ×Ｎ行列のコレスキーファクタを判定し、この判定されたコレスキーファクタを前進代入および後退代入において使用して前記受信データ信号の前記データを判定することによって、前記受信ベクトルのデータを判定する基地局であって、
最大Ｎ個のスカラーＰＥからなるアレイであって、該アレイが、前記Ｎ×Ｎ行列の要素と前記受信ベクトルとを受信するための入力を有し、各スカラーＰＥは、前記コレスキーファクタを判定し、前進代入および後退代入の実行において使用され、前記アレイが、前記受信ベクトルのデータを出力するアレイ
を備えたことを特徴とする基地局。
【請求項５５】
請求項５４に記載の基地局において、各スカラーＰＥは、前記コレスキーファクタを判定し、前進代入および後退代入の実行において前記アレイによって処理される行列の対角要素を処理することを特徴とする基地局。
【請求項５６】
請求項５４に記載の基地局において、前記Ｎ×Ｎ行列は、バンド幅がＰであり、前記最大Ｎ個のスカラーＰＥの数は、Ｐであり、Ｐは、Ｎ未満であることを特徴とする基地局。
【請求項５７】
請求項５４に記載の基地局において、平方根および逆数デバイスをさらに備え、前記平方根および逆数デバイスは、前記アレイの単一のスカラーＰＥにのみ結合され、前記アレイのスカラーＰＥは、平方根および逆数機能を実行できないことを特徴とする基地局。
【請求項５８】
請求項５７に記載の基地局において、前記平方根および逆数デバイスは、ＬＵＴを使用することを特徴とする基地局。
【請求項５９】
請求項５４に記載の基地局において、各プロセッサは、前記Ｎ×Ｎ行列の複数の対角要素に対する処理を実行することを特徴とする基地局。
【請求項６０】
請求項５９に記載の基地局において、複数のフォールドの各々について、各スカラーＰＥは、前記Ｎ×Ｎ行列の１つの対角上の要素のみを処理することを特徴とする基地局。
【請求項６１】
請求項６０に記載の基地局において、フォールドのステージ数は、前記スカラーＰＥの数を最小化し、前記Ｎ×Ｎ行列を処理する処理時間を最長許容時間未満にすることができることを特徴とする基地局。
【請求項６２】
請求項６１に記載の基地局において、前記スカラーＰＥは、データが前記アレイを双方向に流れるように、機能的に線形に構成されていることを特徴とする基地局。
【請求項６３】
請求項６２に記載の基地局において、遅延素子が各スカラーＰＥの間に動作可能に結合され、前記アレイは、２つのＮ×Ｎ行列を同時に処理できることを特徴とする基地局。
【請求項６４】
請求項６３に記載の基地局において、前記スカラーＰＥは、全て共通の再構成可能なインプリメントを有することを特徴とする基地局。
【請求項６５】
Ｎ×Ｎ行列についてコレスキーファクタを判定する装置であって、
スカラーＰＥのアレイであって、各ＰＥが、前記Ｎ×Ｎ行列の要素に関連づけられ、前記コレスキーファクタの対応する要素の要素を判定するアレイを備えたことを特徴とする装置。
【請求項６６】
請求項６５に記載の装置において、各スカラーＰＥは、前記Ｎ×Ｎ行列の要素に一意に関連づけられることを特徴とする装置。
【請求項６７】
請求項６５に記載の装置において、ＰＥの間に遅延要素をさらに備えたことを特徴とする装置。
【請求項６８】
請求項６７に記載の装置において、複数のＮ×Ｎ行列が前記アレイによってパイプライン処理されることを特徴とする装置。
【請求項６９】
請求項６８に記載の装置において、前記アレイは、複数のステージでＮ×Ｎ行列を処理し、ＰＥは、前記ステージの各々で、１処理サイクルを超える処理サイクルにおいてアクティブでないことを特徴とする装置。
【請求項７０】
請求項６９に記載の装置において、前記複数のＮ×Ｎ行列は、全て、次のステージに進む前に、前記複数のステージのうちの１ステージで処理されることを特徴とする装置。
【請求項７１】
請求項７０に記載の装置において、前記複数のＮ×Ｎ行列のうちの各Ｎ×Ｎ行列について、各ステージでの処理の結果は、次のステージに進む前に保存されることを特徴とする装置。
【請求項７２】
受信ベクトルとして受信された複数のデータ信号からデータを復元するレシーバであり、Ｎ×Ｎ行列のコレスキーファクタを判定することによって前記受信ベクトルのデータを判定するレシーバであって、
スカラーＰＥのアレイであって、各スカラーＰＥが、前記Ｎ×Ｎ行列の要素に関連づけられ、前記コレスキーファクタの対応する要素の要素を判定するアレイを備えたことを特徴とするレシーバ。
【請求項７３】
請求項７２に記載のレシーバにおいて、各スカラーＰＥは、前記Ｎ×Ｎ行列の要素に一意に関連づけられることを特徴とするレシーバ。
【請求項７４】
請求項７２に記載のレシーバにおいて、ＰＥの間に遅延要素をさらに備えたことを特徴とするレシーバ。
【請求項７５】
請求項７４に記載のレシーバにおいて、複数のＮ×Ｎ行列が前記アレイによってパイプライン処理されることを特徴とするレシーバ。
【請求項７６】
請求項７５に記載のレシーバにおいて、前記アレイは、複数のステージでＮ×Ｎ行列を処理し、前記ステージの各々でＰＥは、１処理サイクルを超える処理サイクルにおいてアクティブでないことを特徴とするレシーバ。
【請求項７７】
請求項７６に記載のレシーバにおいて、前記複数のＮ×Ｎ行列は、全て、次のステージに進む前に、前記複数のステージのうちの１ステージで処理されることを特徴とするレシーバ。
【請求項７８】
請求項７７に記載のレシーバにおいて、前記複数のＮ×Ｎ行列のうちの各Ｎ×Ｎ行列について、各ステージでの処理の結果は、次のステージに進む前に保存されることを特徴とするレシーバ。
【請求項７９】
受信ベクトルとして受信された複数のデータ信号からデータを復元するＵＥであり、Ｎ×Ｎ行列のコレスキーファクタを判定することによって前記受信ベクトルのデータを判定するＵＥであって、
スカラーＰＥのアレイであって、各ＰＥが、前記Ｎ×Ｎ行列の要素に関連づけられ、前記コレスキーファクタの対応する要素の要素を判定するアレイを備えたことを特徴とするＵＥ。
【請求項８０】
請求項７９に記載のＵＥにおいて、各スカラーＰＥは、前記Ｎ×Ｎ行列の要素に一意に関連づけられることを特徴とするＵＥ。
【請求項８１】
請求項７９に記載のＵＥにおいて、ＰＥの間に遅延要素をさらに備えたことを特徴とするＵＥ。
【請求項８２】
請求項８１に記載のＵＥにおいて、複数のＮ×Ｎ行列が前記アレイによってパイプライン処理されることを特徴とするＵＥ。
【請求項８３】
請求項８２に記載のＵＥにおいて、前記アレイは、複数のステージでＮ×Ｎ行列を処理し、前記ステージの各々でＰＥは、１処理サイクルを超える処理サイクルにおいてアクティブでないことを特徴とするＵＥ。
【請求項８４】
請求項８３に記載のＵＥにおいて、前記複数のＮ×Ｎ行列は、全て、次のステージに進む前に、前記複数のステージのうちの１ステージで処理されることを特徴とするＵＥ。
【請求項８５】
請求項８４に記載のＵＥにおいて、前記複数のＮ×Ｎ行列のうちの各Ｎ×Ｎ行列について、各ステージでの処理の結果は、次のステージに進む前に保存されることを特徴とするＵＥ。
【請求項８６】
受信ベクトルとして受信された複数のデータ信号からデータを復元するための基地局であって、前記基地局は、Ｎ×Ｎ行列のコレスキーファクタを判定することによって前記受信ベクトルのデータを判定し、
スカラーＰＥのアレイであって、各ＰＥは、前記Ｎ×Ｎ行列の要素に関連づけられ、前記コレスキーファクタの対応する要素の要素を判定するアレイを備えたことを特徴とする基地局。
【請求項８７】
請求項８６に記載の基地局において、各スカラーＰＥは、前記Ｎ×Ｎ行列の要素に一意に関連付けされることを特徴とする基地局。
【請求項８８】
請求項８６に記載の基地局において、ＰＥの間に遅延要素をさらに備えたことを特徴とする基地局。
【請求項８９】
請求項８８に記載の基地局において、複数のＮ×Ｎ行列が前記アレイによってパイプライン処理されることを特徴とする基地局。
【請求項９０】
請求項８９に記載の基地局において、前記アレイは、複数のステージでＮ×Ｎ行列を処理し、前記ステージの各々でＰＥは、１処理サイクルを超える処理サイクルにおいてアクティブでないことを特徴とする基地局。
【請求項９１】
請求項９０に記載の基地局において、前記複数のＮ×Ｎ行列は、全て、次のステージに進む前に、前記複数のステージのうちの１ステージで処理されることを特徴とする基地局。
【請求項９２】
請求項９１に記載の基地局において、前記複数のＮ×Ｎ行列のうちの各Ｎ×Ｎ行列について、各ステージでの処理の結果が、次のステージに進む前に保存されることを特徴とする基地局。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、線形システムの解法に関する。具体的には、本発明は、線形システムを解くためのアレイ処理の使用に関する。
【背景技術】
【０００２】
工学上の問題を解くのに、線形システム解法が用いられることが多い。このような課題の１つに、ＴＤＤ（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）がある。コレスキーのアルゴリズムは、
【００１３】
【数１】
2005509959.tif 000003
【００１４】
またはＲなどの対称正定値行列を、式５によって、下三角行列Ｇと上三角行列ＧHに因数分解する。
【００１５】
【数２】
2005509959.tif 000004
【００１６】
対称正値行列
【００１７】
【数３】
2005509959.tif 000005
【００１８】
は、式６によって、Ａにその共役転置（エルミート）行列ＡHを乗算することによって、Ａから生成することができる。
【００１９】
【数４】
2005509959.tif 000006
【００２０】
【数５】
2005509959.tif 000007
【００２１】
は、簡単に式７によって定義される。
【００２２】
【数６】
2005509959.tif 000008
【００２３】
その結果、式１は、ＺＦでは式８として、ＭＭＳＥでは式９として、書き換えられる。
【００２４】
【数７】
2005509959.tif 000009
【００２５】
【数８】
2005509959.tif 000010
【００２６】
式８または式９を解くため、式１０によってコレスキーファクタ（Cholesky factor）が用いられる。
【００２７】
【数９】
2005509959.tif 000011
【００２８】
変数ｙは式１１によって定義される。
【００２９】
ＧHｄ＝ｙ                                                              式１１
【００３０】
変数ｙを使用して、式１０は式１２として書き換えられる。
【００３１】
【数１０】
2005509959.tif 000012
【００３２】
データベクトルを取得するための複雑さの大半は、３つのステップで実行される。第１のステップで、式１３に示すように、
【００３３】
【数１１】
2005509959.tif 000013
【００３４】
またはＲなどの派生対称正値行列からＧが生成される。
【００３５】
【数１２】
2005509959.tif 000014
【００３６】
Ｇを用い、式１４に示すように、式８においてＧの前進代入（forward substitution）を使用してｙを解く。
【００３７】
【数１３】
2005509959.tif 000015
【００３８】
Ｇの共役転置行列ＧHを用い、式１５に示すように、式１１において後退代入（backwardsubstitution）を使用してｄを解く。
【００３９】
ｄ＝ＢＡＣＫＷＡＲＤ  ＳＵＢ（ＧH，ｙ）                                式１５
【００４０】
式１３によってコレスキーファクタＧを判定するアプローチは、
【００４１】
【数１４】
2005509959.tif 000016
【００４２】
またはＲに関して示された以下のアルゴリズムとするが、Ｒに関しては類似のアプローチも用いられる。
【００４３】
【数１５】
2005509959.tif 000017
【００４４】
ａd,eは行列
【００４５】
【数１６】
2005509959.tif 000018
【００４６】
またはＲのｄ行ｅ列の要素を表す。「：」は「ｊからＮまで」などの「まで」演算子を示し、（・）Hは共役転置（エルミート）演算子を示す。
【００４７】
コレスキーファクタを求解するための別のアプローチでは、Ｎ個の並列ベクトルベースプロセッサが使用される。各プロセッサは、
【００４８】
【数１７】
2005509959.tif 000019
【００４９】
またはＲ行列の列にマップされる。各プロセッサの列は、変数μによって定義され、μ＝１：Ｎである。並列プロセッサに基づくサブルーチンは、μ＝１：Ｎとした場合の以下のサブルーチンとして考察することができる。
【００５０】
【数１８】
2005509959.tif 000020
【００５１】
ｒｅｃｖ（・,left）は左側のプロセッサ演算器からの受信であり、ｓｅｎｄ（・,right）は右側のプロセッサ演算器への伝送であり、ｇK,Lは隣接プロセッサからの値である。
【００５２】
このサブルーチンは、図２ａ〜図２ｈを用いて図説される。図２ａは、ジョイント検出器のベクトルプロセッサとその関連メモリセルのブロック図である。各プロセッサ５０1から５０N（５０）は、行列の列に対して演算を行う。Ｇ行列は下三角行列であり、
【００５３】
【数１９】
2005509959.tif 000021
【００５４】
またはＲは下三角行列によって完全に定義されるので、下三角行列の要素ａk,lだけが使用される。
【００５５】
図２ｂおよび図２ｃには、プロセッサの下側のセル上で、プロセッサによって実行され得る２つの機能が示されている。図２ｂでは、下向き三角形で表される機能５２が、μ番目のプロセッサ５０の下側のセル（ａμμからａNμ）上で、式１６および式１７を実行する。
【００５６】
【数２０】
2005509959.tif 000022
【００５７】
ａμ:N,μ：＝ν                                                        式１７
【００５８】
「←」は同時代入を示し、「：＝」は逐次代入を示し、νは右側のプロセッサに伝送される値である。
【００５９】
図２ｃでは、右向き三角形で表される機能５２が、μ番目のプロセッサ５０の下側のセル上で、式１８および式１９を実行する。
【００６０】
ν←ｕ                                                                  式１８
ａμ:N,μ：＝ａμ:N,μ−νμνμ:N                                      式１９
【００６１】
νkは、第ｋ番目のプロセッサ５０の右側に出ていく値に関係付けした値を示す。
【００６２】
図２ｄ〜図２ｇには、４×４  Ｇ行列に対して実行されるデータフローと機能が示されている。処理のステージ１から４までに対しては、図２ｄ〜図２ｇに示すように、最も左側のプロセッサ５０がドロップアウトし、下向き三角形の機能５２が、左から右に移動していく。図２ｄ〜図２ｇをインプリメントするため、下向き三角形は、プロセッサを物理的に右向きに置き換えることができ、または下向き三角形の機能を担うことによって、プロセッサをバーチャルに右向きに置き換えることができる。
【００６３】
これらエレメント（element）は、ステージ１を表す図２ｈに示すように、（（Ｎ−４）個の）プロセッサ５０を第４番目のプロセッサ５０4の右側に追加し、プロセッサ５０の各々に行列の対角より下方の（Ｎ−４個の）セルを追加することによって、Ｎ×Ｎ行列とＮ個のプロセッサ５０に拡張可能である。このような構成による処理はＮステージにわたって実行される。
【００６４】
このようなコレスキー分解のインプリメントは、ベクトルプロセッサを用いるにしても、スカラーＰＥへの直接分解を用いるにしても、各ステージの処理の後で、大量の処リソースがアイドル状態になるため、効率的ではない。
【発明の開示】
【発明が解決しようとする課題】
【００６５】
したがって、線形システムを解くための代替アプローチを有するのが望ましい。
【課題を解決するための手段】
【００６６】
線形システムを解くためにＰＥが利用される。本発明の一実施形態では、コレスキーファクタを判定するため、行列の対角の行列要素がスカラーＰＥに射影される。別の実施形態では、２次元スカラーアレイを用いて、コレスキーファクタを判定する。第３の実施形態では、再構成可能スカラー線形アレイを用いて、コレスキーファクタを判定し、前進代入および後退代入を実行する。行列が、限られたバンド幅を有する場合は、これらの実施形態で使用されるプロセッサの数を減らすことができる。プロセッサのフォールディング（folding）を用いて、これらの実施形態で使用されるプロセッサの数を減らすことができる。本発明の別の実施形態は、コレスキーファクタを判定し、前進代入および後退代入を実行するように再構成できるＰＥである。
【発明を実施するための最良の形態】
【００６７】
図３ａおよび図３ｂは、Ｇを取得するためコレスキー分解を行うＮ個のスカラーＰＥ５４1ないし５４N（５４）の好ましい実施形態を示す。簡略のため、４×４  Ｇ行列について説明し記述するが、このアプローチは、図３ａおよび図３ｂに示すように、任意に、４×４  Ｇ行列に拡張することができる。
【００６８】
図４ａは、上記のアルゴリズムをパフォームするための３次元計算依存グラフ（computational dependency graph）を示す。簡略のため、図４ａには、バンド幅が３である５×５行列の処理を示す。各ノードによりパフォームされる機能を、図４ｂ〜図４ｅに示す。図４ｂにおいて五角形で表す機能は、式２０および式２１を実行する。
【００６９】
【数２１】
2005509959.tif 000023
【００７０】
ａout←ｙ                                                              式２１
【００７１】
←は同時代入を示す。ａinは下位レベルから当該ノードへの入力であり、ａoutは上位レベルへの出力である。図４ｃは、式２２および式２３を実行する四角形で表される機能である。
【００７２】
ｙ←ｚ*                                                                式２２
ａout←ａin−｜ｚ｜2                                                  式２３
【００７３】
図４ｄは、式２４、式２５、および式２６を実行する八角形で表される機能である。
【００７４】
ｙ←ｗ                                                                  式２４
ｘ←ａin／ｗ                                                          式２５
ａout←ｘ                                                              式２６
【００７５】
図４ｅは、式２７、式２８、および式２９を実行する円で表される機能である。
【００７６】
ｙ←ｗ                                                                  式２７
ｘ←ｚ                                                                  式２８
ａout←ａin−ｗ×ｘ                                                  式２９
【００７７】
図５ａは、４×４  Ｇ行列に対するベクトルベースのコレスキー分解のステージ１を、２次元スカラーベースアプローチにマップする様子を示した図である。各ベクトルプロセッサ５２、５４は、図５ａに示すように、少なくとも１つのスカラープロセッサ５６、５８、６０、６２にマップされる。各スカラープロセッサ５６、５８、６０、６２は、メモリセルａijに関係付けしてある。各プロセッサ５６、５８、６０、６２でパフォームされる機能が、図５ｂ〜図５ｅに示されている。図５ｂには、五角形で表される機能５６が示されており、これは式３０および式３１を実行する。
【００７８】
【数２２】
2005509959.tif 000024
【００７９】
ａij：＝ｙ                                                            式３１
【００８０】
：＝は逐次代入を示す。ｙは下側のプロセッサに伝送される値を示す。図５ｃには、八角形で表される機能５８が示されており、これは式３２、式３３、および式３４を実行する。
【００８１】
ｙ←ｗ                                                                  式３２
ｘ←ａij／ｗ                                                          式３３
ａij：＝ｘ                                                            式３４
【００８２】
ｗは上側のプロセッサから伝送された値を示す。図５ｄには、四角形で表される機能６０が示されており、これは式３５および式３６を実行する。
【００８３】
ｙ←ｚ*                                                                式３５
ａij：＝ａij−｜ｚ｜2                                                式３６
【００８４】
ｘは右側のプロセッサに伝送される値を示す。図５ｅには、円で表される機能６２示されており、これは式３７、式３８、および式３９を実行する。
【００８５】
ｙ←ｗ                                                                  式３７
ｘ←ｚ                                                                  式３８
ａij：＝ａij−ｗ×ｚ                                                  式３９
【００８６】
図６ａ〜図６ｄには、４つの逐次ステージ（ステージ１ないし４）における、プロセッサ５６、５８、６０、６２によるデータフローが示されている。図６ａ〜図６ｄに示すように、各ステージの後、プロセッサ５６、５８の列がドロップオフする。この処理には、４処理サイクルを必要とし、一般にはＮサイクルを必要とする。各ステージにつき１処理サイクルを必要とする。図５ａに示すように、４×４  Ｇ行列を判定するのに、１０個のスカラープロセッサを必要とする。Ｎ×Ｎ行列の場合、必要なプロセッサの数は、式４０による。
【００８７】
【数２３】
2005509959.tif 000025
【００８８】
図６ｅ〜図６ｊには、５×５バンド行列に関する処理フローが示されている。アクティブなプロセッサを実線で示す。このバンド行列では、左下の３つのエントリ（ａ41、ａ51、ａ52、図６ｅ〜図６ｊでは図示せず）が０である。図６ｅに示すように、ステージ１では、上側の６つのプロセッサがオペレートしている。図６ｆに示すように、ステージ１でアクティブな６つのプロセッサが、ｇ11、ｇ21、ｇ31と、ステージ２で使用する３つの即値結果α22、α32、α33を決定する。
【００８９】
ステージ２では、６つのプロセッサ（α22，α32，α33，
【００９０】
【数２４】
2005509959.tif 000026
【００９１】
）がオペレートしている。ステージ２では、図６ｇ（ステージ３）に示すように、ｇ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が０であるＰＥ５８、６２を有する。その結果、プロセッサ６６（最も左側の２つ）への射影は、この処理では不要である。その結果、これらのインプリメンテーションは、当該行列のバンド幅に応じてスケーリングすることができる。
【０１０４】
図９ｃ〜図９ｎには、バンド幅が３である５×５バンド行列に関する、１つおきの接続に遅延が生じる、各処理サイクルごとのタイミング図が示されている。各時間期間においては、各プロセッサに関連付けをした値が示されている。アクティブなプロセッサを実線で示す。図に示すように、ステージ１、タイム０を示す図９ｃの左上のプロセッサ（
【０１０５】
【数２５】
2005509959.tif 000027
【０１０６】
）から、ステージ５を示す図９ｎの右下のプロセッサ（δ55）へと、処理が伝播していく。図に示すように、バンド行列という行列の性質のため、非バンド行列を処理する左下のプロセッサは不要であり、図示していない。
【０１０７】
図９ｏ〜図９ｚには、図９ｂなどによる、５×５バンド行列を処理する線形アレイの各処理サイクルごとのタイミング図とメモリアクセスが示されている。図示するように、５×５行列のバンド幅は３であるので、必要なプロセッサは３個のみである。バンド行列を処理するため、３個のプロセッサを必要とすることが、図示されている。さらに図示するように、各ステージは比較的高いプロセッサの利用効率を有しており、この利用効率はＮ／ｐが増加するにつれて増加する。
【０１０８】
ＰＥの複雑さを減らすために、除算および平方根を求める機能は、これらＰＥで実行しない（除かれる）。除算および開平は、より複雑であるから、加算器、減算器、乗算器でインプリメントするよりは、ＡＳＩＣにインプリメントされる。
【０１０９】
除算または開平をパフォームする機能は、五角形および八角形で表される機能５６、５８の２つだけである。図６ａ〜図６ｄに示すように、あるステージについて、五角形および八角形で表される機能５６、５８は、全て、１ステージの間に単一の列で実行される。特に、これらの列の各々は、最上部に五角形５８をもち、その下に八角形５８をもつ。各八角形５８は同時にそのｗ入力をそのｙ出力に代入するので、五角形５６の出力は、ｗの値をいずれかのａij用に直ちに保存しなくても、列全体に行き渡る。八角形５８は、ｗ入力を使用してｘ出力も生成し、ｘ出力もａijにフィードバックされる。ｘ出力は、四角形および円で表される機能６０、６２によって、ａijの計算において使用される。その結果、各八角形のｘ出力の値だけが判定されればよい。八角形のｘ出力は、その八角形５８のａijを、五角形５６のｙ出力であって、各八角形５８で同じ値となるｗ入力の値で除算したものである。したがって、除算／開平機能は、八角形５８でｘを計算する際に、実行する必要があるだけである。
【０１１０】
各八角形の出力ｘは、式３４および式３０を用いて、その八角形のａijを五角形のａijの平方根で割ったものである。あるステージについて、各八角形プロセッサにおいて、除算器に代えて乗算器を使用した場合には、五角形のａijの平方根の代りに、その平方根の逆数を判定しさえすればよく、除算機能を五角形プロセッサにおいてだけでパフォームされるように分離して、アレイ全体の複雑さを緩和することができる。平方根の逆数は、五角形に関連付けをした行列要素のａijとして、その逆数の代りに、保存される。このようにすると、後で前進代入および後退代入を行う際にも都合がよい。それらのアルゴリズム中の除算機能がこの逆数を掛ける乗算に変り、他のＰＥ、すなわち図１２ｄおよび図１５ｄのｘ出力でも除算器の必要がなくなるからである。図９ａおよび図９ｂに示す五角形の機能５６は、同じプロセッサ６４によってパフォームされるので、図１０ａおよび図１０ｂに示すように、五角形／四角形プロセッサ６４からの入力と、そのプロセッサ６４への出力とを有する単一の逆数／開平回路７０を用いて、プロセッサ６６、６４をインプリメントすることができる。平方根の逆数を求めた結果は、プロセッサ６６に渡されていく。図１１ａおよび図１１ｂは、図１０ａおよび図１０ｂに対応する。逆数／開平回路７０を分離したことによって、他のプロセッサ６６、６４の複雑さが緩和される。逆数／開平回路７０は、逆数回路および開平回路を用いてインプリメントすることができるが、ＬＵＴ、特にＦＰＧＡ（field programmable gate array）用のＬＵＴを用いてインプリメントするのが好ましい。ただし、メモリはコストエフィシエント（cost efficient）である。
【０１１１】
コレスキーファクタＧが判定された後、図１２ａおよび図１２ｂに示すような前進代入を用いて、ｙが決定される。前進代入のアルゴリズムは次のようになる。
【０１１２】
【数２６】
2005509959.tif 000028
【０１１３】
バンド行列の場合、アルゴリズムは次のようになる。
【０１１４】
【数２７】
2005509959.tif 000029
【０１１５】
ｇLKはコレスキー行列ＧのＬ行Ｋ列に相当する要素である。
【０１１６】
図１２ａおよび図１２ｂは、スカラープロセッサを用いた、４×４  Ｇ行列に関する前進代入の２つの実施形態である。図１２ｃの星形で表される機能７２と、図１２ｄのひし形で表される機能７４の２つの機能が、プロセッサ７２、７４によって実行される。星形の機能７２は、式４２および式４３を実行する。
【０１１７】
ｙ←ｗ                                                                  式４２
ｘ←ｚ−ｗ×ｇij                                                      式４３
【０１１８】
ひし形の機能７４は、式４４および式４５を実行する。
【０１１９】
ｘ←ｚ／ｇij                                                          式４４
ｙ←ｘ                                                                  式４５
【０１２０】
図１２ａに示すようにＰＥの同時接続の間に遅延素子を挿入し、実行プレーン（ｔ1からｔ7）に垂直なアレイを射影することにより、そのアレイを線形アレイ上に射影することができる。
【０１２１】
【数２８】
2005509959.tif 000030
【０１２２】
から得た受信ベクトルの値ｒ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が決定される。
【０１２５】
図１２ｅ〜図１２ｊには、５×５バンド行列の各処理サイクルに関するタイミング図が示されている。図１２ｅは、左下隅の３つのエントリが０というバンド行列の性質（バンド幅が３の場合）を示している。
【０１２６】
コレスキー分解のときと同様に、前進代入でも、同じＰＥが利用できることを示すために、図１２ｆはステージ６から開始する。ステージ６は、図９ｃ〜図９ｎの最終ステージの後のステージである。
【０１２７】
同様に、図１２ｋ〜図１２ｐは、図９ｏ〜図９ｚのプロセッサが前進代入もパフォームできるように拡張した例を示す。これらの図においては、ステージは、コレスキー分解を行う５つのステージの後のステージ６から開始される。この処理は、各処理サイクルに対して、ステージ６のタイム０（図１２ｋ）から、ステージ６のタイム４（図１２ｏ）の後の最終結果（図１２ｐ）まで、パフォームされる。
【０１２８】
前進代入によってｙ変数が判定された後、後退代入によってデータベクトルを判定することができる。後退代入は次のサブルーチンによって実行される。
【０１２９】
【数２９】
2005509959.tif 000031
【０１３０】
バンド行列の場合、次のサブルーチンが用いられる。
【０１３１】
【数３０】
2005509959.tif 000032
【０１３２】
（・）*は複素共役関数を示す。
【０１３３】
【数３１】
2005509959.tif 000033
【０１３４】
は、コレスキーファクタＧについて判定された対応する要素の複素共役である。ＹLはｙの対応する要素である。
【０１３５】
後退代入は、４×４処理アレイに関する図１５ａおよび図１５ｂに示すように、星形およびひし形の機能７６、７８を用いるスカラープロセッサによってもインプリメントされる。しかし、これらの機能は、図１５ｃおよび図１５ｄに示すように、Ｇ行列の値の複素共役を用いてパフォームされる。したがって、式４２〜式４５は、それぞれ、式４６〜式４９となる。
【０１３６】
ｙ←ｗ                                                                式４６
【０１３７】
【数３２】
2005509959.tif 000034
【０１３８】
ｙ←ｘ                                                                式４９
【０１３９】
プロセッサ７６、７８の間の同時代入で、遅延素子６８を挿入することにより、図１５ａのアレイは、実行プレーンを横断して線形アレイに射影される。このアレイは、Ｎ×Ｎ行列を処理するため、図１６ａに示すように拡張することができる。ｙベクトルの値が図１６ａのアレイにロードされ、データベクトルｄが出力される。このアレイは、ｄを判定するのに２Ｎクロックサイクルを要する。１つおきのプロセッサが１つおきのクロックサイクルでオペレートするので、２つのｄを同時に判定することができる。
【０１４０】
図１６ａの各プロセッサ７６、７８は１つおきのクロックサイクルでオペレートするので、図１５ｂに示すように１つおきの遅延素子を削除することができる。図１５ｂの射影先アレイは、Ｎ×Ｎ行列を処理するため、図１６ｂに示すように拡張することができる。このアレイは、ｄを判定するのにＮクロックサイクルを要する。
【０１４１】
図１６ｂの射影先アレイのＰＥ７６、７８のサイクルごとの動作が、図１７ａ〜図１７ｄに示されている。図１７ａに示す第１サイクルｔ1では、ｙ4がロードされ、
【０１４２】
【数３３】
2005509959.tif 000035
【０１４３】
が処理され、ｄ4が決定される。図１７ｂに示す第２サイクルｔ2では、ｙ2、ｙ3がロードされ、
【０１４４】
【数３４】
2005509959.tif 000036
【０１４５】
、
【０１４６】
【数３５】
2005509959.tif 000037
【０１４７】
が処理され、ｄ3が決定される。図１７ｃに示す第３サイクルｔ3では、ｙ1がロードされ、
【０１４８】
【数３６】
2005509959.tif 000038
【０１４９】
および
【０１５０】
【数３７】
2005509959.tif 000039
【０１５１】
が処理され、ｄ2が決定される。図１７ｄに示す第４サイクルｔ4では、
【０１５２】
【数３８】
2005509959.tif 000040
【０１５３】
、
【０１５４】
【数３９】
2005509959.tif 000041
【０１５５】
が処理され、ｄ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への入力となる。
【図面の簡単な説明】
【０１７３】
【図１】ジョイント検出レシーバの簡略な図である。
【図２ａ】ベクトルプロセッサを用いてコレスキーファクタを判定する様子を示した図である。
【図２ｂ】ベクトルプロセッサを用いてコレスキーファクタを判定する様子を示した図である。
【図２ｃ】ベクトルプロセッサを用いてコレスキーファクタを判定する様子を示した図である。
【図２ｄ】ベクトルプロセッサを用いてコレスキーファクタを判定する様子を示した図である。
【図２ｅ】ベクトルプロセッサを用いてコレスキーファクタを判定する様子を示した図である。
【図２ｆ】ベクトルプロセッサを用いてコレスキーファクタを判定する様子を示した図である。
【図２ｇ】ベクトルプロセッサを用いてコレスキーファクタを判定する様子を示した図である。
【図２ｈ】ベクトルプロセッサを用いてコレスキーファクタを判定する様子を示した図である。
【図３ａ】コレスキー分解を実行するＮ個のスカラープロセッサの好ましい実施形態を示した図である。
【図３ｂ】コレスキー分解を実行するＮ個のスカラープロセッサの好ましい実施形態を示した図である。
【図４ａ】コレスキー分解のために３次元グラフを使用した一例を示した図である。
【図４ｂ】コレスキー分解のために３次元グラフを使用した一例を示した図である。
【図４ｃ】コレスキー分解のために３次元グラフを使用した一例を示した図である。
【図４ｄ】コレスキー分解のために３次元グラフを使用した一例を示した図である。
【図４ｅ】コレスキー分解のために３次元グラフを使用した一例を示した図である。
【図５ａ】コレスキー分解を実行するベクトルプロセッサをスカラープロセッサにマップする一例を示した図である。
【図５ｂ】コレスキー分解を実行するベクトルプロセッサをスカラープロセッサにマップする一例を示した図である。
【図５ｃ】コレスキー分解を実行するベクトルプロセッサをスカラープロセッサにマップする一例を示した図である。
【図５ｄ】コレスキー分解を実行するベクトルプロセッサをスカラープロセッサにマップする一例を示した図である。
【図５ｅ】コレスキー分解を実行するベクトルプロセッサをスカラープロセッサにマップする一例を示した図である。
【図６ａ】非バンド行列に関するスカラーアレイの処理フローを示した図である。
【図６ｂ】非バンド行列に関するスカラーアレイの処理フローを示した図である。
【図６ｃ】非バンド行列に関するスカラーアレイの処理フローを示した図である。
【図６ｄ】非バンド行列に関するスカラーアレイの処理フローを示した図である。
【図６ｅ】バンド行列に関するスカラーアレイの処理フローを示した図である。
【図６ｆ】バンド行列に関するスカラーアレイの処理フローを示した図である。
【図６ｇ】バンド行列に関するスカラーアレイの処理フローを示した図である。
【図６ｈ】バンド行列に関するスカラーアレイの処理フローを示した図である。
【図６ｉ】バンド行列に関するスカラーアレイの処理フローを示した図である。
【図６ｊ】バンド行列に関するスカラーアレイの処理フローを示した図である。
【図７】図４ａの射影をｋ軸に沿ってＮ×Ｎ行列に拡張した図である。
【図８ａ】２Ｄスカラーアレイ中のスカラープロセッサ間の遅延を利用した処理フローを示した図である。
【図８ｂ】２Ｄスカラーアレイ中のスカラープロセッサ間の遅延を利用した処理フローを示した図である。
【図８ｃ】２Ｄスカラーアレイ中のスカラープロセッサ間の遅延を利用した処理フローを示した図である。
【図８ｄ】２Ｄスカラーアレイ中のスカラープロセッサ間の遅延を利用した処理フローを示した図である。
【図８ｅ】遅延素子とその関連式を示した図である。
【図９ａ】図８ａ〜図８ｄのスカラープロセッサアレイの、４つのスカラープロセッサからなる１Ｄアレイへの射影を示した図である。
【図９ｂ】１つおきのプロセッサ間に遅延要素を有するスカラープロセッサアレイの、４つのスカラープロセッサからなる１Ｄアレイへの射影を示した図である。
【図９ｃ】１つおきのプロセッサ間に遅延要素を有するバンド行列のコレスキー分解に関する処理フローを示した図である。
【図９ｄ】１つおきのプロセッサ間に遅延要素を有するバンド行列のコレスキー分解に関する処理フローを示した図である。
【図９ｅ】１つおきのプロセッサ間に遅延要素を有するバンド行列のコレスキー分解に関する処理フローを示した図である。
【図９ｆ】１つおきのプロセッサ間に遅延要素を有するバンド行列のコレスキー分解に関する処理フローを示した図である。
【図９ｇ】１つおきのプロセッサ間に遅延要素を有するバンド行列のコレスキー分解に関する処理フローを示した図である。
【図９ｈ】１つおきのプロセッサ間に遅延要素を有するバンド行列のコレスキー分解に関する処理フローを示した図である。
【図９ｉ】１つおきのプロセッサ間に遅延要素を有するバンド行列のコレスキー分解に関する処理フローを示した図である。
【図９ｊ】１つおきのプロセッサ間に遅延要素を有するバンド行列のコレスキー分解に関する処理フローを示した図である。
【図９ｋ】１つおきのプロセッサ間に遅延要素を有するバンド行列のコレスキー分解に関する処理フローを示した図である。
【図９ｌ】１つおきのプロセッサ間に遅延要素を有するバンド行列のコレスキー分解に関する処理フローを示した図である。
【図９ｍ】１つおきのプロセッサ間に遅延要素を有するバンド行列のコレスキー分解に関する処理フローを示した図である。
【図９ｎ】１つおきのプロセッサ間に遅延要素を有するバンド行列のコレスキー分解に関する処理フローを示した図である。
【図９ｏ】バンド行列を処理する線形アレイのメモリアクセスを示した図である。
【図９ｐ】バンド行列を処理する線形アレイのメモリアクセスを示した図である。
【図９ｑ】バンド行列を処理する線形アレイのメモリアクセスを示した図である。
【図９ｒ】バンド行列を処理する線形アレイのメモリアクセスを示した図である。
【図９ｓ】バンド行列を処理する線形アレイのメモリアクセスを示した図である。
【図９ｔ】バンド行列を処理する線形アレイのメモリアクセスを示した図である。
【図９ｕ】バンド行列を処理する線形アレイのメモリアクセスを示した図である。
【図９ｖ】バンド行列を処理する線形アレイのメモリアクセスを示した図である。
【図９ｗ】バンド行列を処理する線形アレイのメモリアクセスを示した図である。
【図９ｘ】バンド行列を処理する線形アレイのメモリアクセスを示した図である。
【図９ｙ】バンド行列を処理する線形アレイのメモリアクセスを示した図である。
【図９ｚ】バンド行列を処理する線形アレイのメモリアクセスを示した図である。
【図１０ａ】スカラープロセッサがＮ個に拡張された、図９ａの射影されたアレイを示した図である。
【図１０ｂ】スカラープロセッサがＮ個に拡張された、図９ｂの射影されたアレイを示した図である。
【図１１ａ】除算の平方根をとる関数の図１０ａのアレイからの分離を示す図である。
【図１１ｂ】除算の平方根をとる関数の図１０ｂのアレイからの分離を示す図である。
【図１２ａ】各プロセッサ間で遅延要素を有する前進代入アレイの、４つのスカラープロセッサへの射影を示した図である。
【図１２ｂ】１つおきのプロセッサ間で遅延要素を有する前進代入アレイの、４つのスカラープロセッサへの射影を示した図である。
【図１２ｃ】前進代入に関する星型で表される関数によって実行される式を示した図である。
【図１２ｄ】前進代入に関するひし形で表される関数によって実行される式を示した図である。
【図１２ｅ】１つおきのプロセッサ間に同時代入を有するバンド行列の前進代入に関する処理フローを示した図である。
【図１２ｆ】１つおきのプロセッサ間に遅延要素を有するバンド行列の前進代入に関する処理フローを示した図である。
【図１２ｇ】１つおきのプロセッサ間に遅延要素を有するバンド行列の前進代入に関する処理フローを示した図である。
【図１２ｈ】１つおきのプロセッサ間に遅延要素を有するバンド行列の前進代入に関する処理フローを示した図である。
【図１２ｉ】１つおきのプロセッサ間に遅延要素を有するバンド行列の前進代入に関する処理フローを示した図である。
【図１２ｊ】１つおきのプロセッサ間に遅延要素を有するバンド行列の前進代入に関する処理フローを示した図である。
【図１２ｋ】バンド行列を処理する前進代入線形アレイのメモリアクセスを示した図である。
【図１２ｌ】バンド行列を処理する前進代入線形アレイのメモリアクセスを示した図である。
【図１２ｍ】バンド行列を処理する前進代入線形アレイのメモリアクセスを示した図である。
【図１２ｎ】バンド行列を処理する前進代入線形アレイのメモリアクセスを示した図である。
【図１２ｏ】バンド行列を処理する前進代入線形アレイのメモリアクセスを示した図である。
【図１２ｐ】バンド行列を処理する前進代入線形アレイのメモリアクセスを示した図である。
【図１３ａ】スカラープロセッサがＮ個に拡張された、図１２ａの射影されたアレイを示した図である。
【図１３ｂ】スカラープロセッサがＮ個に拡張された、図１２ｂの射影されたアレイを示した図である。
【図１４ａ】図１２ｂの射影されたアレイに関する処理フローを示した図である。
【図１４ｂ】図１２ｂの射影されたアレイに関する処理フローを示した図である。
【図１４ｃ】図１２ｂの射影されたアレイに関する処理フローを示した図である。
【図１４ｄ】図１２ｂの射影されたアレイに関する処理フローを示した図である。
【図１５ａ】各プロセッサ間で遅延要素を有する後退代入アレイの、４つのスカラープロセッサへの射影を示した図である。
【図１５ｂ】１つおきのプロセッサ間で遅延要素を有する後退代入アレイの、４つのスカラープロセッサへの射影を示した図である。
【図１５ｃ】後退代入に関する星型で表される関数によって実行される式を示した図である。
【図１５ｄ】後退代入に関するひし形で表される関数によって実行される式を示した図である。
【図１５ｅ】１つおきのプロセッサ間に同時代入を有するバンド行列の後退代入に関する処理フローを示した図である。
【図１５ｆ】１つおきのプロセッサ間に遅延要素を有するバンド行列の後退代入に関する処理フローを示した図である。
【図１５ｇ】１つおきのプロセッサ間に遅延要素を有するバンド行列の後退代入に関する処理フローを示した図である。
【図１５ｈ】１つおきのプロセッサ間に遅延要素を有するバンド行列の後退代入に関する処理フローを示した図である。
【図１５ｉ】１つおきのプロセッサ間に遅延要素を有するバンド行列の後退代入に関する処理フローを示した図である。
【図１５ｊ】１つおきのプロセッサ間に遅延要素を有するバンド行列の後退代入に関する処理フローを示した図である。
【図１５ｋ】バンド行列を処理する後退代入線形アレイのメモリアクセスを示した図である。
【図１５ｌ】バンド行列を処理する後退代入線形アレイのメモリアクセスを示した図である。
【図１５ｍ】バンド行列を処理する後退代入線形アレイのメモリアクセスを示した図である。
【図１５ｎ】バンド行列を処理する後退代入線形アレイのメモリアクセスを示した図である。
【図１５ｏ】バンド行列を処理する後退代入線形アレイのメモリアクセスを示した図である。
【図１５ｐ】バンド行列を処理する後退代入線形アレイのメモリアクセスを示した図である。
【図１６ａ】スカラープロセッサがＮ個に拡張された、図１５ａの射影されたアレイを示した図である。
【図１６ｂ】スカラープロセッサがＮ個に拡張された、図１５ｂの射影されたアレイを示した図である。
【図１７ａ】図１５ｂの射影されたアレイに関する処理フローを示した図である。
【図１７ｂ】図１５ｂの射影されたアレイに関する処理フローを示した図である。
【図１７ｃ】図１５ｂの射影されたアレイに関する処理フローを示した図である。
【図１７ｄ】図１５ｂの射影されたアレイに関する処理フローを示した図である。
【図１８ａ】分離された除算機能をもつ図１３ａ、図１６ａのアレイを示した図である。
【図１８ｂ】分離された除算機能をもつ図１３ｂ、図１６ｂのアレイを示した図である。
【図１９ａ】Ｇ、前進代入、および後退代入を判定するための再構成可能アレイを示した図である。
【図１９ｂ】Ｇ、前進代入、および後退代入を判定するための再構成可能アレイを示した図である。
【図２０ａ】除算および平方根をとる関数の再構成可能アレイからの分離を示す図である。
【図２０ｂ】除算および平方根をとる関数の再構成可能アレイからの分離を示す図である。
【図２１ａ】双方向フォールディングを示した図である。
【図２１ｂ】単方向フォールディングを示した図である。
【図２２ａ】Ｎ個のプロセッサを用いた双方向フォールディングの実施を示した図である。
【図２２ｂ】Ｎ個のプロセッサを用いた単方向フォールディングの実施を示した図である。
【図２３】簡単な再構成可能ＰＥの好ましいスライスを示した図である。
【図１】
2005509959.tif 000042
【図２ａ】
2005509959.tif 000043
【図２ｂ】
2005509959.tif 000044
【図２ｃ】
2005509959.tif 000045
【図２ｄ】
2005509959.tif 000046
【図２ｅ】
2005509959.tif 000047
【図２ｆ】
2005509959.tif 000048
【図２ｇ】
2005509959.tif 000049
【図２ｈ】
2005509959.tif 000050
【図３ａ】
2005509959.tif 000051
【図３ｂ】
2005509959.tif 000052
【図４ａ】
2005509959.tif 000053
【図４ｂ】
2005509959.tif 000054
【図４ｃ】
2005509959.tif 000055
【図４ｄ】
2005509959.tif 000056
【図４ｅ】
2005509959.tif 000057
【図５ａ】
2005509959.tif 000058
【図５ｂ】
2005509959.tif 000059
【図５ｃ】
2005509959.tif 000060
【図５ｄ】
2005509959.tif 000061
【図５ｅ】
2005509959.tif 000062
【図６ａ】
2005509959.tif 000063
【図６ｂ】
2005509959.tif 000064
【図６ｃ】
2005509959.tif 000065
【図６ｄ】
2005509959.tif 000066
【図６ｅ】
2005509959.tif 000067
【図６ｆ】
2005509959.tif 000068
【図６ｇ】
2005509959.tif 000069
【図６ｈ】
2005509959.tif 000070
【図６ｉ】
2005509959.tif 000071
【図６ｊ】
2005509959.tif 000072
【図７】
2005509959.tif 000073
【図８ａ】
2005509959.tif 000074
【図８ｂ】
2005509959.tif 000075
【図８ｃ】
2005509959.tif 000076
【図８ｄ】
2005509959.tif 000077
【図８ｅ】
2005509959.tif 000078
【図９ａ】
2005509959.tif 000079
【図９ｂ】
2005509959.tif 000080
【図９ｃ】
2005509959.tif 000081
【図９ｄ】
2005509959.tif 000082
【図９ｅ】
2005509959.tif 000083
【図９ｆ】
2005509959.tif 000084
【図９ｇ】
2005509959.tif 000085
【図９ｈ】
2005509959.tif 000086
【図９ｉ】
2005509959.tif 000087
【図９ｊ】
2005509959.tif 000088
【図９ｋ】
2005509959.tif 000089
【図９ｌ】
2005509959.tif 000090
【図９ｍ】
2005509959.tif 000091
【図９ｎ】
2005509959.tif 000092
【図９ｏ】
2005509959.tif 000093
【図９ｐ】
2005509959.tif 000094
【図９ｑ】
2005509959.tif 000095
【図９ｒ】
2005509959.tif 000096
【図９ｓ】
2005509959.tif 000097
【図９ｔ】
2005509959.tif 000098
【図９ｕ】
2005509959.tif 000099
【図９ｖ】
2005509959.tif 000100
【図９ｗ】
2005509959.tif 000101
【図９ｘ】
2005509959.tif 000102
【図９ｙ】
2005509959.tif 000103
【図９ｚ】
2005509959.tif 000104
【図１０ａ】
2005509959.tif 000105
【図１０ｂ】
2005509959.tif 000106
【図１１ａ】
2005509959.tif 000107
【図１１ｂ】
2005509959.tif 000108
【図１２ａ】
2005509959.tif 000109
【図１２ｂ】
2005509959.tif 000110
【図１２ｃ】
2005509959.tif 000111
【図１２ｄ】
2005509959.tif 000112
【図１２ｅ】
2005509959.tif 000113
【図１２ｆ】
2005509959.tif 000114
【図１２ｇ】
2005509959.tif 000115
【図１２ｈ】
2005509959.tif 000116
【図１２ｉ】
2005509959.tif 000117
【図１２ｊ】
2005509959.tif 000118
【図１２ｋ】
2005509959.tif 000119
【図１２ｌ】
2005509959.tif 000120
【図１２ｍ】
2005509959.tif 000121
【図１２ｎ】
2005509959.tif 000122
【図１２ｏ】
2005509959.tif 000123
【図１２ｐ】
2005509959.tif 000124
【図１３ａ】
2005509959.tif 000125
【図１３ｂ】
2005509959.tif 000126
【図１４ａ】
2005509959.tif 000127
【図１４ｂ】
2005509959.tif 000128
【図１４ｃ】
2005509959.tif 000129
【図１４ｄ】
2005509959.tif 000130
【図１５ａ】
2005509959.tif 000131
【図１５ｂ】
2005509959.tif 000132
【図１５ｃ】
2005509959.tif 000133
【図１５ｄ】
2005509959.tif 000134
【図１５ｅ】
2005509959.tif 000135
【図１５ｆ】
2005509959.tif 000136
【図１５ｇ】
2005509959.tif 000137
【図１５ｈ】
2005509959.tif 000138
【図１５ｉ】
2005509959.tif 000139
【図１５ｊ】
2005509959.tif 000140
【図１５ｋ】
2005509959.tif 000141
【図１５ｌ】
2005509959.tif 000142
【図１５ｍ】
2005509959.tif 000143
【図１５ｎ】
2005509959.tif 000144
【図１５ｏ】
2005509959.tif 000145
【図１５ｐ】
2005509959.tif 000146
【図１６ａ】
2005509959.tif 000147
【図１６ｂ】
2005509959.tif 000148
【図１７ａ】
2005509959.tif 000149
【図１７ｂ】
2005509959.tif 000150
【図１７ｃ】
2005509959.tif 000151
【図１７ｄ】
2005509959.tif 000152
【図１８ａ】
2005509959.tif 000153
【図１８ｂ】
2005509959.tif 000154
【図１９ａ】
2005509959.tif 000155
【図１９ｂ】
2005509959.tif 000156
【図２０ａ】
2005509959.tif 000157
【図２０ｂ】
2005509959.tif 000158
【図２１ａ】
2005509959.tif 000159
【図２１ｂ】
2005509959.tif 000160
【図２２ａ】
2005509959.tif 000161
【図２２ｂ】
2005509959.tif 000162
【図２３】
2005509959.tif 000163
【国際調査報告】
2005509959.tif 000164