(57)【要約】      （修正有）【課題】テプリッツ行列、またはブロックテプリッツ行列を係数行列とする連立方程式の求解効率を大幅に上げる。【解決手段】初期連立方程式を、巡回または近似的に巡回である行列の積に分離し、次数を縮小した多数の連立方程式に分離した後で、次数が少なくなった連立方程式の解をもとに初期連立方程式の解を計算する。【選択図】図１
2010262622.tif 000002
【特許請求の範囲】
【請求項１】
撮像装置、検出装置、通信装置、制御装置、および一般信号処理装置のうちの１つのコンポーネントであり、デジタル信号を処理するためのデジタル回路からなる装置であって、
行列Ｔ０およびベクトルＹ０の要素からなる信号Ｓｓを解Ｘから計算する第２のシステムソルバーと、
前記解Ｘから信号Ｊを計算するシステムプロセッサと、からなり、
前記解Ｘ、前記信号Ｓｓ、および前記信号Ｊは、
ビームパターン、目標物の物理的特徴、送信音声、画像およびデータ、機械的、電気的、化学的、または生物学的コンポーネントを制御するための情報、画像、および音声およびデータのフレームのうち少なくとも１つを表すし、かつ、
前記第２のシステムソルバーは、
前記信号Ｓｓをもとに、変換した係数行列Ｔｔからなる変換した連立方程式を生成すること
を特徴とするデジタル信号処理用装置。
【請求項２】
請求項１に記載の装置において、前記第２のシステムソルバーは、
行列Ｔ０の要素に近似的に等しい要素からなる係数行列Ｔを前記行列Ｔ０から計算し、
前記係数行列Ｔを、巡回または近似的に巡回である行列Ｃｉからなる行列の積の和に分離し、
前記行列Ｃｉから前記変換した係数行列Ｔｔを計算し、
前記ベクトルＹ０から計算したベクトルである、変換したベクトルＹｔを計算し、
前記変換した係数行列Ｔｔおよび前記変換したベクトルＹｔから解Ｘを計算する、
請求項１に記載のデジタル信号処理用装置。
【請求項３】
請求項１に記載の装置において、前記第２のシステムソルバーは、
ブロック行列である前記行列Ｔ０から、この行列Ｔ０の要素に近似的に等しい要素からなるブロック係数行列Ｔを計算し、
前記ブロック係数行列Ｔを、ブロック巡回または近似的にブロック巡回である行列Ｃｉからなる、行列の積の和に分離し、
ブロック行列である、前記変換した係数行列Ｔｔを前記行列Ｃｉから計算し、
前記ベクトルＹ０から計算した、ブロック変換したベクトルＹｔを計算し、
ブロック解Ｘを前記ブロック変換した係数行列Ｔｔおよび前記ブロック変換したベクトルＹｔから計算する、
請求項１に記載のデジタル信号処理用装置。
【請求項４】
請求項１に記載の装置において、前記第２のシステムソルバーは、解ＸｐＲからなる和をもとに前記解Ｘを計算し、その際に、前記解ＸｐＲは、前記行列Ｔ０の部分、またはこの行列Ｔ０に近似的に等しい行列Ｔの部分をもとに生成されたブロック係数行列Ｔｂをもつ連立方程式の解である、請求項１に記載のデジタル信号処理用装置。
【請求項５】
前記行列の積の和はさらに対角行列からなる請求項２に記載の装置。
【請求項６】
請求項２に記載の装置において、前記装置はさらに、前記解Ｘから解Ｘ０を計算する反復子からなり、前記システムプロセッサは、信号Ｊを前記解Ｘ０から計算する、請求項２に記載のデジタル信号処理用装置。
【請求項７】
請求項２に記載の装置において、前記第２のシステムソルバーは、前記解Ｘを前記変換した係数行列Ｔｔと前記変換したベクトルＹｔとから計算する並列処理コンピュータハードウェアアーキテクチャからなる、請求項２に記載のデジタル信号処理用装置。
【請求項８】
請求項２に記載の装置において、前記撮像装置、検出装置、通信装置、制御装置、および一般信号処理装置のうちの１つの装置は、さらに、
センサー、センサアレイ、トランスデューサ、トランスデューサアレイ、および配線接続のうち少なくとも１つの装置を備える、信号Ｓｉｎを生成する第１の入力と、
前記信号Ｓｓを前記信号Ｓｉｎから計算する第１のプロセッサと、
出力と、からなる
ことを特徴とする請求項２に記載のデジタル信号処理用装置。
【請求項９】
請求項３に記載の装置において、前記撮像装置、検出装置、通信装置、制御装置、および一般信号処理装置のうちの１つの装置は、さらに、
センサー、センサアレイ、トランスデューサ、トランスデューサアレイ、および配線接続のうち少なくとも１つの装置を備える、信号Ｓｉｎを生成する第１の入力と、
前記信号Ｓｓを前記信号Ｓｉｎから計算する第１のプロセッサと、
出力と、からなること
を特徴とする請求項３に記載の装置デジタル信号処理用装置。
【請求項１０】
請求項４に記載の装置において、前記撮像装置、検出装置、通信装置、制御装置、および一般信号処理装置のうちの１つの装置は、さらに、
センサー、センサアレイ、トランスデューサ、トランスデューサアレイ、および配線接続のうち少なくとも１つの装置を備える、信号Ｓｉｎを生成する第１の入力と、
前記信号Ｓｓを前記信号Ｓｉｎから計算する第１のプロセッサと、
出力と、からなること
を特徴とする請求項４に記載のデジタル信号処理用装置。
【請求項１１】
撮像装置、検出装置、通信装置、制御装置、および一般信号処理装置のうちの１つの装置のコンポーネントであり、デジタル信号を処理するためのデジタル回路からなる装置であって、該装置は、さらに、
係数行列Ｔ０およびａベクトルＹ０の要素からなる信号Ｓｓをもとに解Ｘ０を計算する第１のシステムソルバーと、
信号Ｊを前記解Ｘ０から計算するシステムプロセッサと、からなり、
前記解Ｘ０、前記信号Ｓｓ、および前記信号Ｊは、ビームパターン、目標物の物理的特徴、送信された音声・画像・データ、機械的、電気的、化学的、または生物学的コンポーネントを制御するための情報、また、画像、および音声フレームとデータフレーム、のうち少なくとも１つを表し、
前記第１のシステムソルバーは、対称ベクトルおよび非対称ベクトルを前記ベクトルＹ０から計算してなること、
を特徴とするデジタル信号処理用装置。
【請求項１２】
請求項１１に記載の装置において、前記第１のシステムソルバーは対称係数行列および歪対称係数行列を前記係数行列Ｔ０から計算する請求項１１に記載のデジタル信号処理用装置。
【請求項１３】
請求項１１に記載の装置において、前記第１のシステムソルバーは、対称サブブロックからなる対称係数行列と歪対称サブブロックからなる歪対称係数行列とを前記係数行列Ｔ０から計算する請求項１１に記載のデジタル信号処理用装置。
【請求項１４】
請求項１２に記載の装置において、前記撮像装置、検出装置、通信装置、制御装置、および一般信号処理装置のうちの１つの装置は、さらに、
センサー、センサアレイ、トランスデューサ、トランスデューサアレイ、および配線接続のうち少なくとも１つの装置を備える、信号Ｓｉｎを生成する第１の入力と、
前記信号Ｓｓを前記信号Ｓｉｎから計算する第１のプロセッサと、
出力と、からなること
を特徴とする請求項１２に記載のデジタル信号処理用装置。
【請求項１５】
請求項１３に記載の装置において、前記撮像装置、検出装置、通信装置、制御装置、および一般信号処理装置のうちの１つの装置は、さらに、
センサー、センサアレイ、トランスデューサ、トランスデューサアレイ、および配線接続のうち少なくとも１つの装置を備える、信号Ｓｉｎを生成する第１の入力と、
前記信号Ｓｓを前記信号Ｓｉｎから計算する第１のプロセッサと、
出力と、からなること
を特徴とする請求項１３に記載のデジタル信号処理用装置。
【請求項１６】
撮像装置、検出装置、通信装置、制御装置、および一般信号処理装置のうちの１つの装置のコンポーネントであり、デジタル信号を処理するためのデジタル回路からなる装置であって、該装置は、さらに、
係数行列Ｔ０およびベクトルＹ０の要素からなる信号Ｓｓをもとに解Ｘ０を計算する第３のシステムソルバーと、
信号Ｊを前記解Ｘ０から計算するシステムプロセッサと、からなり、
前記解Ｘ０、前記信号Ｓｓ、および前記信号Ｊは、ビームパターン、目標物の物理的特徴、送信音声データ、機械的、電気的、化学的、または生物学的コンポーネントを制御するための情報、画像、および音声フレームとデータフレーム、のうち少なくとも１つを表し、
前記第３のシステムソルバーは、前記信号Ｓｓをもとに少なくとも１つの巡回係数行列を生成すること
を特徴とするデジタル信号処理用装置。
【請求項１７】
請求項１６に記載の装置において、前記第３のシステムソルバーは、前記係数行列Ｔ０をもとに対称係数行列および歪対称係数行列のうち少なくとも１つを計算する請求項１６に記載のデジタル信号処理用装置。
【請求項１８】
請求項１６に記載の装置において、前記第３のシステムソルバーは、前記係数行列Ｔ０をもとに、対称サブブロックからなる対称係数行列および歪対称サブブロックからなる歪対称係数行列のうち少なくとも１つを計算する請求項１６に記載のデジタル信号処理用装置。
【請求項１９】
請求項１７に記載の装置において、前記撮像装置、検出装置、通信装置、制御装置、および一般信号処理装置のうちの１つの装置は、さらに、
センサー、センサアレイ、トランスデューサ、トランスデューサアレイ、および配線接続のうち少なくとも１つの装置を備える、信号Ｓｉｎを生成する第１の入力と、
前記信号Ｓｓを前記信号Ｓｉｎから計算する第１のプロセッサと、
出力と、からなること
を特徴とする請求項１７に記載のデジタル信号処理用装置。
【請求項２０】
請求項１８に記載の装置において、前記撮像装置、検出装置、通信装置、制御装置、および一般信号処理装置のうちの１つの装置は、さらに、
センサー、センサアレイ、トランスデューサ、トランスデューサアレイ、および配線接続のうち少なくとも１つの装置を備える、信号Ｓｉｎを生成する第１の入力と、
前記信号Ｓｓを前記信号Ｓｉｎから計算する第１のプロセッサと、
出力と、からなること
を特徴とする請求項１８に記載のデジタル信号処理用装置。
【発明の詳細な説明】
【技術分野】
【０００１】
［発明の背景］
【０００２】
本発明は信号を決定する装置および手法に関する。撮像、検出、制御、通信などを行う一般信号処理装置の多くは、信号を決定・判断してそれぞれのオペレーションを行っている。一般信号処理装置としては、デジタルフィルタリング装置、線形予測装置、システム識別装置、および音声・画像処理装置などがあげられる。本開示装置を、これらの信号処理装置のコンポーネントとすることが可能である。
【背景技術】
【０００３】
通信装置は一般的に、送信データ、音声または画像情報を表す信号の入力、処理および出力を行い、これらの装置を通信チャネルの推定、符号間干渉の軽減、エコーやノイズのキャンセル、チャネル等化、およびユーザー検出などに使用することができる。こうした装置は、デジタル形式の入力信号を使用して、信号重みを決定する連立方程式に対する分散行列および相互相関ベクトルを生成する。装置のオペレーション用の信号を決定するには通常この信号重みが使用される。分散行列は、テプリッツ（Ｔｏｅｐｌｉｔｚ）行列、ブロックテプリッツ行列、またはテプリッツ行列あるいはブロックテプリッツ行列に近似のものであってよい。通信装置の性能には、通常その連立方程式の最大次元数および連立方程式の求解速度が直接かかわっている。連立方程式の次元が大規模であるほど重みベクトルが収容できる情報量は多くなり、また連立方程式を解く速度が速いほど装置の処理能力は高くなる。
【０００４】
レーダー、レーザーレーダーおよびソナーシステムなどの検出装置では、一般に、センサアレイでエネルギーを収集し、その収集したエネルギーで生成した信号を処理して係数を取得し、それをビームフォーミングなどの用途に使用している。信号によって目標物の反射率、速度、形状、および位置といった物理的特性を表すことができる。係数取得にあたっては、センサアレイが等間隔要素を有する場合、テプリッツ行列またはブロックテプリッツ行列を係数行列とした連立方程式の求解を要することがある。その方程式の次元で通常センサアレイのサイズおよび装置の分解能が決定されるため、検出装置の性能は通常その連立方程式の最大次元数とかかわっている。また、検出装置の性能は、連立方程式の求解速度によっても左右される。この処理速度をあげることで、目標物の追従や目標物のリアルタイムの位置決定を向上させることが可能になる。また、センサアレイをより大規模にすることでビームがかなり狭くなり、所望外の信号に対する耐性を得られる。
【０００５】
合成開口レーダー、故障検査装置、ＬＩＤＡＲ、地質学用撮像装置、さらには磁気共鳴画像（ＭＲＩ）、コンピュータ断層撮影（ＣＴ）、ポジトロン断層法（ＰＥＴ）、超音波装置などの医用撮像装置といった各種撮像装置では、テプリッツ行列またはブロックテプリッツ行列を係数行列とした連立方程式の解が必要とされる。その解とは、生体物質または非生体物質の画像を表すデジタル信号である。センサ要素数および装置の分解能は通常は次元数で決定されるため、撮像装置の性能は通常その連立方程式の最大次元数とかかわっている。また、連立方程式の求解速度を上げることでも装置性能は向上するが、これはリアルタイムの演算が容易になるためである。
【０００６】
制御装置としては、機械的、生物学的、化学的および電気的コンポーネントを制御する装置があげられる。これらの装置は、一般に、被制御物体の変形、位置、温度、および速度といった広範な物理量を表す信号の処理を行う。これらの信号を使用してテプリッツまたはブロックテプリッツ型の分散行列および連立方程式の既知ベクトルを生成し、それを解いて被制御物体の制御に必要な信号重みを求める。連立方程式の求解速度が速くなると被制御物体の制御に要する応答時間が改善されるため、装置の性能は、通常この求解速度に直接かかわっている。
【０００７】
一般信号処理装置は、画像、音声、データ、送信データ、および圧縮データを表す信号、および生物学的・非生物学的目標物、その他これらに制限されない広範な物理量を表す信号の入力、処理、および出力を行っている。この出力信号は、テプリッツ行列またはブロックテプリッツ行列を係数行列とした連立方程式の解、または解から求められたものである。一般信号処理装置の性能は、連立方程式の次元やその求解速度に左右される。
【０００８】
上記装置の性能は、通常、テプリッツ行列、またはブロックテプリッツ行列を係数行列とする連立方程式の求解効率によって決まる。従来より、ブロックテプリッツ行列を係数行列とした連立方程式の解法として反復法と直接法がある。反復法には、共役勾配手法族からなる手法がある。一方、直接法には、ガウスの消去法、およびコレスキー分解、ＬＤＵ分解、固有値分解、特異値分解、およびＱＲ分解といった分解法がげられる。直接法ではＯ（ｎ３）フロップスの解を求める。
【０００９】
従来より、テプリッツ行列を係数行列とした連立方程式の解法はすでにあり、これらの手法については広く研究されているため、本明細書ではごく簡単にまとめる程度にとどめる。これらの手法は一般的に直接法または反復法に分類されるが、直接法はその連立方程式の求解に要するステップ数に応じて、古典的解法、高速解法または超高速解法にさらに分類される。反復法として最も一般的なのは、共役勾配手法族の手法である。一方、Ｏ（ｎ３）フロップスでなされる直接法の古典的な解法としては、ガウスの消去法、および固有値分解、特異値分解、ＬＤＵ分解、ＱＲ分解、およびコレスキー分解などの分解法があげられる。古典的な解法では、行列の変位構造は利用しない。一方、高速解法は行列の変位構造を利用し、Ｏ（ｎ２）フロップスでなされる。高速解法の例として、レビンソン（Ｌｅｖｉｎｓｏｎ）型、およびシュール（Ｓｃｈｕｒ）型がある。超高速解法は比較的新しく、Ｏ（ｎ  ｌｏｇ２−ｎ）フロップスでなされる。反復法は安定性はあるが、システムによっては収束速度が遅くなる。古典的な解法は安定しているが低速である。高速解法は安定していて、かつ、反復法より高速である。超高速解法では安定性は実証されておらず、その多くは漸近的に超高速なだけにとどまる。
【００１０】
以下にあげるのは、ブロックテプリッツ行列、またはテプリッツ行列を係数行列とする連立方程式の求解演算を要する装置である。Ｚｒｎｉｃ（６，４４８，９２３）、Ｂａｒｎａｒｄ（６，５４５，６３９）、Ｄａｖｉｓ（６，０９１，３６１）、Ｐｉｌｌａｉ（２００６／０１１４１４８）、Ｙｕ（６，５６７，０３４）、Ｖａｓｉｌｉｓ（６，０４４，３３６）、Ｇａｒｒｅｎ（６，６４６，５９３）、Ｄｚａｋｕｌａ（６，４３８，２０４）、Ｓｉｔｔｏｎ  ｅｔ  ａｌ．（６，０３８，１９７）、およびＤａｖｉｓ  ｅｔ  ａｌ．（２００６／００２０４０１）に開示のレーダー、レーザーレーダーおよびソナー装置などの検出装置。Ｋｕｎｇ  ｅｔ  ａｌ．（２００３／００４８８６１）、Ｗｕ  ｅｔ  ａｌ．（２００７／０１３３８１４）、Ｖｏｌｌｍｅｒ  ｅｔ  ａｌ．（６，０６４，６８９）、Ｋｉｍ  ｅｔ  ａｌ．（２００４／０１４１４８０）、Ｍｉｓｒａ  ｅｔ  ａｌ．（２００５／０２８１２１４）、Ｓｈａｍｓｕｎｄｅｒ（２００６／００１８３９８）、およびＲｅｚｎｉｋ  ｅｔ  ａｌ．（２００６／００３４３９８）に開示のエコーキャンセラ、イコライザーならびにチャネル推定、搬送波周波数補正、符号間干渉の軽減、およびユーザー検出用装置などの通信装置。Ｊｏｈｎｓｏｎ  ｅｔ  ａｌ．（６，００５，９１６）、Ｃｈａｎｇ  ｅｔ  ａｌ．（２００８／０１０７３１９）、Ｚａｋｈｏｒ  ｅｔ  ａｌ．（４，９８２，１６２）、およびＬｉｕ（６，０４３，６５２）に開示のＭＲＩ、ＣＴ、ＰＥＴおよび超音波装置などの撮像装置。Ｐｒｅｕｓｓ（６，４８７，５２４）に開示のノイズおよび振動コントローラなどの一般信号処理装置、Ｗｕ  ｅｔ  ａｌ．（２００６／００４０７０６）、およびＫｉｍ  ｅｔ  ａｌ．（２００５／０２７１０１６）に開示のアンテナのビーム形成システム、およびＴｒｉｍｅｃｈｅ  ｅｔ  ａｌ．（２００６／００１３４７９）に開示の画像復元器。
【発明の開示】
【発明が解決しようとする課題】
【００１１】
上記にあげた装置において各種連立方程式の求解に従来手法を使用した場合、通信装置の容量は低く、検出装置および撮像装置の分解能が低い上にリアルタイム性能に劣り、制御装置の応答時間は遅く、また一般信号処理装置は性能が低くなる。また、従来手法を使用する装置は係数行列の正則化を要することが多く、パワー損失および放熱要件が大きいことが多い。本明細書に開示する手法では、上記にあげた装置においてテプリッツ行列またはブロックテプリッツ行列を係数行列とする連立方程式を解く際に、従来手法よりもその求解効率を大幅に上げることにより、上記のさまざまな問題の解決を図っている。求解を効率化することにより、上記装置の、リアルタイムでの信号処理性能の向上、高容量化、追従能力の向上、および応答時間の短縮を実現する。また、ここに開示の手法により、実質的に従来手法より大規模な次元の連立方程式の求解が可能となる。これにより、上記装置のセンサアレイをより大きくして高分解能とし、より大量の過去情報の処理を行うことができる装置が実現する。ここに開示の手法では、係数行列の条件数が減るように係数行列が変化していくため正則化は通常は要らない。そのため、通常は正則化で導かれる上記装置の画像歪みは、本手法では少なくなる。また、ここに開示の手法では必要処理ステップ数が大幅に少なくなるため、上記装置の消費電力や放熱の要件も少なくてすむ。ここに開示の手法では、コンピュータメモリも従来手法のものより少なくてすむ。この手法はまた、より安価なコンピュータハードウェアでも実施可能である。
【課題を解決するための手段】
【００１２】
［発明の簡単な概要］
【００１３】
多くの信号処理装置の性能は、テプリッツ行列またはブロックテプリッツ行列を係数行列とした連立方程式に対するその装置の求解効率で決まる。係数行列および連立方程式の次数を縮小すれば、この解を高効率で求めることが可能である。ここに開示の装置および手法では、連立方程式およびその係数行列の次数を短縮している。連立方程式の次数を短縮した後は、公知のいずれの手法を用いても次数を縮小した連立方程式の解を高効率で求めることが可能である。
【００１４】
テプリッツ行列またはブロックテプリッツ行列を係数行列とする連立方程式の解を高効率で求めることができるのは、さらに、テプリッツの係数行列、またはブロックテプリッツの係数行列のサブブロックを、次数をあげて変化させ、行および列を加算して変形し、近似させて、変換した場合である。変換後の行列、または変換後のサブブロックは狭帯域になっている。その後、連立方程式の行および列を再構成して、単一の狭帯域をもつ係数行列を求め、単一の狭帯域係数行列をもつ連立方程式を解く。それからこの解をもとに元の連立方程式の解を反復法によって求める。連立方程式の次数が増大した場合や、行列を変形した場合は、未知変数をさらに連立方程式に導入する。これらの未知変数は多数の異なる手法を用いて求めることができる。
【００１５】
テプリッツ行列またはブロックテプリッツ行列を係数行列とする連立方程式の解は、テプリッツ行列、またはブロックテプリッツ行列のサブブロックを巡回形式に展開することによって求めることができる。この展開を行うためには、未知変数を連立方程式に加算しなければならない。初期連立方程式が特定の式に正しく因数分解されていれば、元の未知変数、および付加未知変数を効率的に求めることができる。
【００１６】
ブロックテプリッツ行列、またはテプリッツ行列を係数行列とする連立方程式の解を要する装置にこの開示の手法を使用して、かなり大幅に性能改善を達成することができる。ここに開示の手法にあるパラメタを選択すると、個々の装置に応じてこれらの手法を最適に実装することが可能である。
【図面の簡単な説明】
【００１７】
【図１】図１は、開示装置を信号処理装置のコンポーネントとした場合を示す。
【図２】図２（ａ）、２（ｂ）および２（ｃ）は本明細書に開示する装置および手法の各種実施形態のサブコンポーネントを示す。
【発明を実施するための最良の形態】
【００１８】
［発明の詳細な説明］
【００１９】
図１は信号処理装置１００の非限定的な実施例を示しており、信号Ｊを決定する求解成分１３０からなっている。第１の入力１１０は第１のプロセッサ１２０で処理される少なくとも１つの信号Ｓｉｎに対するソースであり、該プロセッサはこの信号Ｓｉｎをもとにブロックテプリッツ行列またはテプリッツ行列の係数行列Ｔ０、およびベクトルＹ０の各要素を生成する。行列Ｔ０およびベクトルＹ０の要素を含んだ信号Ｓｓを求解成分１３０に入力する。連立方程式が生成され、本応用例に開示の求解成分１３０で解Ｘを求める。この求解成分１３０は解Ｘをもつ第２の入力１６０をもとに信号Ｊ０を処理することができる。求解成分１３０からの出力は信号Ｊであり、これらの信号は第２のプロセッサ１４０で処理され、出力１５０の信号Ｓｏｕｔを生成する。多くの装置ではこれらのコンポーネントすべてを備えているわけではなく、追加のコンポーネントを備えている装置が多い。各種装置は、第２のプロセッサ１４０から第１のプロセッサ１２０、または求解成分１３０に対するフィードバックなど、コンポーネント間でフィードバックを行うことができる。第２の入力１６０からの信号は、第１の入力１１０からの１つまたはそれ以上の信号Ｓｉｎであってよい。求解成分１３０は、信号Ｊ０を処理しなくても解Ｘを信号Ｊとして出力することができる。この場合、第２のプロセッサ１４０は、必要に応じて信号Ｊ０を信号Ｊで処理することができる。装置１００は、通信装置、検出装置、画像装置、制御装置、または公知の一般信号処理装置いずれであってもよい。以下にあげる装置は、装置１００によって表すことが可能な装置の非限定的な実施例である。これらの装置のコンポーネントのほとんどは公知である。
【００２０】
非限定的な実施例として、検出装置には、能動的および受動的レーダー、ソナー、レーザレーダー、音響流量計、医用装置および制震装置がある。これらの装置の場合、第１の入力１１０はセンサまたはセンサアレイである。このセンサは音響トランスデューサであったり、光学センサおよび電磁センサであったりする。第１のプロセッサ１２０としては復調器、復号器、デジタルフィルタ、ダウンコンバータ、およびサンプラなどがあげられるが、これらに制限されるものではない。第１のプロセッサ１２０は通常、１つまたはそれ以上のセンサアレイでサンプリングされた開口幅データを表す信号Ｓｉｎをもとに生成した行列要素の係数行列Ｔ０を計算する。信号Ｓｉｎおよび信号Ｓｓは物理的物体の位置、速度、および電気的特徴といった物理的物体関連の情報を表すことができる。アレイ要素が等間隔の場合、その分散行列はエルミートテプリッツ行列またはブロックテプリッツ行列である。既知ベクトルＹ０はステアリングベクトル、データベクトルまたは任意のベクトルであってよい。求解成分１３０は連立方程式を解いて信号重みＸを求める。この信号重みＸを信号Ｊ０に当てはめてビームパターンを作る信号Ｊを生成することが可能である。信号Ｊおよび信号重みＸは目標物の物理的性質に係わる情報を含むこともできる。また、信号重みを信号Ｊの一部として含めることもできる。第２のプロセッサ１４０はさらに信号Ｊを処理して出力１５０の信号Ｓｏｕｔを求めることができ、これは目標物情報表示用ディスプレイ装置、または輻射信号用センサアレイであってよい。
【００２１】
非限定的な実施例として、通信装置にはエコーキャンセラ、イコライザー、さらにはチャネル推定、搬送波周波数補正、音声符号化、符号間干渉の軽減、およびユーザー検出などを行う各種装置があげられる。これらの装置の場合、第１の入力１１０は通常配線接続ｓまたはアンテナアレイを備えている。第１のプロセッサ１２０としては、増幅器、検出器、受信機、復調器、デジタルフィルタ、および送信信号Ｓｉｎの処理用サンプラなどがあげられるが、これらに制限されるものではない。第１のプロセッサ１２０は通常入力信号Ｓｉｎのうちの１信号で生成した分散行列からの係数行列Ｔ０の要素を計算する。信号Ｓｉｎおよび信号Ｓｓは通常送信された音声、画像またはデータを表す。分散行列は対称テプリッツ行列またはブロックテプリッツ行列であってよい。既知ベクトルＹ０は通常２つの送信された信号Ｓｉｎ同士の相互相関ベクトルであり、音声、画像またはデータも表す。求解成分１３０は連立方程式を解いて信号重みＸを求め、信号重みと第２の入力１６０からの信号Ｊ０との統合を行い、通常は送信された音声、画像およびデータも表す信号Ｊの所望のものを生成する。第２のプロセッサ１４０はさらに出力１５０の信号Ｊを処理するが、これは配線接続、トランスデューサ、またはディスプレイ出力であってよい。第２の入力１６０からの信号は第１の入力１１０からの信号Ｓｉｎと同一のものであってよい。
【００２２】
非限定的な実施例として、制御装置には、機械的、化学的、生物学的および電気的な各種コンポーネントの制御を行う装置がある。行列Ｔ０およびベクトルＹ０の要素は、第１のプロセッサ１２０によって信号Ｓｉｎから生成することができる。信号Ｓｉｎおよび信号Ｓｓは被制御物体の物理的状態を表す。信号Ｓｉｎは通常センサ１１０で収集される。求解成分１３０は、信号Ｊ０からの制御信号Ｊの生成に使用する重みベクトルＸを計算する。信号Ｊ０は第２の入力１６０の入力である。この信号Ｊは通常第２のプロセッサ１４０でさらに処理された後、アクチュエータまたはトランスデューサ１５０へ送られる。物体の物理的状態には、車両の性能データ、医用情報、振動データ、流体または気体の流量特性、化学処理の測定可能量、および運動、パワー、熱流量データなどがある。
【００２３】
非限定的な実施例として、撮像装置にはＭＲＩ、ＰＥＴ、ＣＴ、および超音波装置、合成開口レーダー、故障検査システム、超音波検査、心エコーのほか、音響用および地質学用撮像装置などがあげられる。第１の入力コンポーネント１１０は通常センサーまたはセンサアレイである。センサは、受信エネルギーから信号Ｓｉｎを発生する音響トランスデューサ、および光学センサや電磁センサであってよい。第１のプロセッサ１２０としては、復調器、復号器、デジタルフィルタ、ダウンコンバータ、およびサンプラなどがあげられるが、これに制限されるものではない。第１のプロセッサ１２０は、信号Ｓｉｎから生成された分散行列から係数行列Ｔ０の要素計算を行ったり、グリーン関数（Ｇｒｅｅｎｅ’ｓ ｆｕｎｃｔｉｏｎ）などの既知関数から係数行列の生成を行ったりすることができ、その要素はメモリ内に格納される。分散行列はエルミートテプリッツ行列またはブロックテプリッツ行列である。既知ベクトルＹ０は、測定信号Ｓｉｎ、データベクトル、または任意の定数で生成することができる。信号Ｓｓには画像情報が含まれる。求解成分１３０は連立方程式を解いて未知ベクトルＸを求める。このベクトルＸには画像情報が含まれ、これは第２のプロセッサ１４０でさらに処理され、画像ディスプレイ装置１５０の画面に表示するための画像Ｓｏｕｔが生成される。信号Ｊには、求解成分１３０の出力としてのベクトルＸが含まれている。
【００２４】
撮像装置の非限定的な実施例であるＭＲＩ装置は、ＭＲＩスキャナ付き走査装置を備える第１の入力１１０からなる。第１のプロセッサ１２０はＲＦ信号Ｓｉｎをｋ空間データに変換する。求解成分１３０は、ｋ空間データを画像空間データＸに変換することにより画像再構成を行い、その際にブロックテプリッツ行列を係数行列とする連立方程式の生成、求解を手段としている。第２のプロセッサ１４０は画像空間データＸを光学式データに写像し、光学式データをディスプレイ１５０の信号Ｓｏｕｔに変換する。行列Ｔ０は、画像空間データをｋ空間データに写像するフーリエ作用素であってよい。ベクトルＹ０は測定したｋ空間データで、ベクトルＸは画像空間データである。
【００２５】
撮像装置の非限定的な実施例である超音波装置は、音響レシーバ１１０からなる。第１のプロセッサ１２０は、増幅器、位相検出器、およびアナログ-デジタル変換器で構成される。第１のプロセッサ１２０は信号Ｓｓを生成するが、その際、グリーン関数で出した係数行列Ｔ０の要素、および検出された入射場エネルギーの既知ベクトルＹ０の要素を計算して生成を行う。求解成分１３０は目標物体の伝導率および誘電率を表す信号係数Ｘを計算する。第２のプロセッサ１４０は、送信マルチプレクサ、走査装置、発振器、および増幅器で構成される。出力１５０は音響送信機、ディスプレイ、プリンタ、およびストレージからなる。
【００２６】
非限定的な実施例として、装置はアンテナアレイ１１０を備えるアレイアンテナシステムであってよい。第１のプロセッサ１２０としてダウンコンバータ、復調器、およびチャネルセレクタがあげられる。第１のプロセッサ１２０はステアリングベクトルＹ０の要素およびアンテナの開口信号Ｓｉｎから生成した分散行列Ｔ０の要素について計算を行う。求解成分１３０は信号重みＸを計算し、関連するアンテナ要素の信号Ｊ０に信号重みＸを乗算して信号Ｊを求める。この信号Ｊは第２のプロセッサ１４０でさらに処理される。出力１５０はアンテナアレイ、トランスデューサ、またはディスプレイであってよい。信号Ｓｓは送信情報を表す。
【００２７】
非限定的な実施例として、装置１００はフィルタリング装置であってよい。第１のプロセッサ１２０は係数行列Ｔ０およびベクトルＹ０の要素を計算し、その際に、サンプリングした信号Ｓｉｎからの自己相関および相互相関手法を手段としている。信号Ｓｉｎおよび信号Ｓｓは音声、画像およびデータを表す。入力１１０は配線接続またはセンサーであってよい。解法１３０はベクトルＸを計算するが、これに含まれるフィルタ係数を第２の入力１６０からの信号Ｊ０にあてはめて音声、画像およびデータを表す所望の信号Ｊを得る。装置１００はまた、フィードバックを提供して所望の信号と、所望信号に対する計算近似との照合性を改善を行うこともできる。信号Ｊ０は１つまたはそれ以上の信号Ｓｉｎであってよい。
【００２８】
非限定的な実施例として、装置１００は演算を行うために線形予測、信号推定、またはデータ圧縮手法に依存する装置であってよい。第１のプロセッサ１２０は、サンプリングした信号Ｓｉｎから生成した自己相関行列の係数行列Ｔ０の要素を計算する。ベクトルＹ０をサンプリングした信号Ｓｉｎから計算して求めてもよいし、またはベクトルがその第１の要素以外はすべてゼロ値であることもある。信号Ｓｓは音声、画像およびデータを表す。解法１３０はベクトルＸを計算し、これには通常信号Ｊ０の信号Ｊを計算する際に使用する予測係数が含まれている。信号Ｊは予測した音声、画像またはデータを表す。ベクトルＸが装置の出力である場合、信号Ｊは計算されないことがある。この場合、信号Ｊ音声、画像およびデータを表すベクトルＸを含んでいる。
【００２９】
非限定的な実施例として、装置１００は、その演算を行うためにシステム識別コード、システムモデリング、またはパターン認識手法に依存する装置であってよい。第１のプロセッサ１２０は係数行列Ｔ０の要素を計算するが、通常は入力１１０で生成されたサンプリング信号Ｓｉｎをもとに生成した自己相関行列から計算する。ベクトルＹ０の要素は通常第１の入力１１０によって生成されたサンプリング信号Ｓｉｎの相互相関演算を行って計算される。信号Ｓｓは音声、画像、システムの特徴、およびデータを表す。解法１３０は音声、画像、システムの特徴、またはデータを表す係数を含むベクトルＸを計算する。解法１３０は信号Ｊを生成することもできる。ベクトルＸは第２のプロセッサ１４０によってさらに処理される。この処理にはベクトルＸとその他の既知ベクトルとの対照比較が含まれる。これらの対照比較結果を出力１５０で示すことが可能である。
【００３０】
非限定的な実施例として、装置１００は画像処理およびネットワークルーティングを行う一般信号処理装置であってよい。係数行列Ｔ０の要素は、既知関数で計算する。ベクトルＹ０は、入力１１０で生成されたサンプリング信号Ｓｉｎで第１のプロセッサ１２０によって生成することができる。信号Ｓｉｎおよび信号Ｓｓは画像およびデータを表すことができる。解法１３０が計算するベクトルＸは画像をを表すことができ、それは第２のプロセッサ１４０によってさらに処理され、出力１５０により表示される。
【００３１】
非限定的な実施例として、装置１００はテプリッツのシナプス行列をもつ人工の神経回路網であってよい。第１のプロセッサ１２０は係数行列Ｔ０、およびベクトルＹ０の要素を計算する際に、入力１１０に適用されたトレーニング信号Ｓｉｎに自己相関および相互相関手法を用いて行っている。信号Ｓｉｎおよび信号Ｓｓは通常音声、画像およびデータを表す。解法１３０はベクトルＸを計算し、それにはシナプス重みが含まれている。解法１３０はシナプス重みＸを第２の入力１６０の信号Ｊ０に当てはめて信号Ｊを生成する。この信号Ｊは第２のプロセッサ１４０によってさらに処理される。これには、信号Ｊに対して非線形関数を適用し、ディスプレイ装置１５０に送信される出力信号Ｓｏｕｔを出す、という処理が含まれる。信号Ｊは人工の神経回路網の線形部で処理された音声、画像およびデータを表す。信号Ｊ０は装置１００に対する入力を表す。
【００３２】
図２（ａ）、２（ｂ）、および２（ｃ）は、テプリッツ行列またはブロックテプリッツ行列を係数行列とする連立方程式（１）を解く求解成分１３０の各サブコンポーネントを開示したものである。図２（ａ）に開示の第１のシステムソルバー１３１は方程式（１）の求解を正確に行う。図２（ｂ）に開示の第２のシステムソルバー１３２は連立方程式（１）の係数行列の近似である係数行列Ｔをもつ連立方程式を解く。図２（ｃ）に開示の第３のシステムソルバー１３３は方程式（１）の求解を正確に行う。求解成分１３０が図２（ｂ）の実施形態を使用した場合、反復子１３５は第２のシステムソルバー１３２による解の精度を改善する。図２（ａ）、２（ｂ）、および２（ｃ）では、解Ｘ０から信号Ｊを生成するシステムプロセッサ１３４を開示する。係数行列Ｔ０およびベクトルＹ０の要素は求解成分１３０に対する信号Ｓｓとしての入力される。係数行列Ｔ０の要素、ベクトルＸ、Ｘ０およびＹ０、および信号Ｊは上記で開示したように物理量を表す。
【００３３】
【数１】
2010262622.tif 000003
【００３４】
本発明の図２（ａ）に開示する実施形態において、第１のシステムソルバー１３１は、方程式（１）のベクトルＸ０およびＹ０を、要素ｉと要素（Ｎ-１-ｉ）が等しい対称ベクトルＸＳ（ｉ）とＹＳ（ｉ）とに、そして要素ｉと要素（Ｎ-１-ｉ）の負値とが等しい非対称ベクトルＸＡ（ｉ）とＹＡ（ｉ）とに分離する。ｉの範囲は０から（Ｎ／２-１）を含む。ベクトルの要素はＮ個である。方程式（１）のテプリッツ行列Ｔ０を歪対称テプリッツ行列ＴＡと対称テプリッツ行列ＴＳとに分離する。元の連立方程式を、対称ベクトルと非対称ベクトルを有する新たな連立方程式と、対称または歪対称いずれかの係数行列とに因数分解する。ベクトル内の冗長要素はベクトルが対称であるか非対称であるかによって、それぞれテプリッツ行列の畳み込み、あるいは対応要素の加算または減算により除去することができる。その結果として出る係数行列は、テプリッツ行列とハンケル（Ｈａｎｋｅｌ）行列との和である。この連立方程式の行の半数は冗長であるため、第１のシステムソルバー１３１で廃棄することができる。以下の関係を使用して初期連立方程式を因数分解することができる。対称テプリッツ行列ＴＳと対称ベクトルＸＳの積は対称ベクトルＹＳである。対称の行列ＴＳと非対称ベクトルＸＡの積は非対称ベクトルＹＡである。歪対称テプリッツ行列ＴＡと対称ベクトルＸＳの積は非対称ベクトルＹＡである。歪対称行列ＴＡと非対称ベクトルＸＡとの積は対称ベクトルＹＳである。
【００３５】
非限定的な実施例として、連立方程式（１）は実部であり、係数行列Ｔ０は対称である。ベクトルを対称ベクトルＸＳとＹＳと、非対称ベクトルＸＡとＹＡとに分離する。その後ベクトルの重解を除去して連立方程式（２）および（３）の次数を半分に縮小する。次数が半分になった２本の実連立方程式は、第１のシステムソルバー１３１で公知のいずれの手法を用いても求解できる。初期連立方程式が複雑で、かつ、係数行列がエルミートテプリッツ行列であるとき、次数が同じ２本の実連立方程式を初期連立方程式として生成しそれを第１のシステムソルバー１３１によって求解する。
【００３６】
【数２】
2010262622.tif 000004
【００３７】
非限定的な実施例として、連立方程式（１）はブロックテプリッツ行列を係数行列に持ち、ブロックベクトルを有している。その解を効率的に求めることが可能で、係数行列の各サブブロックを対称および歪対称サブブロックに分離し、またベクトルＸ０とＹ０の各サブベクトルを対称および非対称サブベクトルに分離することにより行う。方程式の各項を因数分解して対称および非対称サブベクトルを有する連立方程式を複数生成する。その後サブベクトルの重複要素を除去して新たな連立方程式の次数を縮小する。
【００３８】
本発明の図２（ａ）に開示したある実施形態においては、第１のシステムソルバー１３１は、ベクトルＸ０およびＹ０のサブベクトルを分離して、要素ｉと要素（Ｎ-１-ｉ）が等しい対称サブベクトルｘＳ（ｉ）とｙＳ（ｉ）を有する対称ベクトルＸＳとＹＳと、要素ｉと要素（Ｎ-１-ｉ）の負値とが等しいサブベクトルｘＡ（ｉ）とｙＡ（ｉ）を有する非対称ベクトルＸＡとＹＡとを生成する。ｉの範囲は０から（Ｎ／２-１）を含む。サブベクトルの要素はＮ個である。ブロックテプリッツ行列のサブブロックＴ０を、歪対称テプリッツ行列のサブブロックＴＡと、対称テプリッツ行列のサブブロックＴＳとに分離する。連立方程式（１）は、対称および非対称サブベクトルを有するベクトルをもつ連立方程式と、対称または歪対称サブブロックのいずれかを有する係数行列とに因数分解することができる。第１のシステムソルバー１３１は、通常、次数がより小規模の実連立方程式を生成する。これらの連立方程式の係数行列のサブブロックはもはやテプリッツ行列ではなくて、ハンケル行列とテプリッツ行列との和または差となっている。新規の各サブブロックは第１のシステムソルバー１３１で生成し、その際、サブベクトルが対称であるか非対称であるかによって、各テプリッツ行列のサブブロックを畳み込んだり、あるいは対応要素を加算または減算したりして行う。
【００３９】
非限定的な実施例として、連立方程式（１）は、実テプリッツ行列ブロックテプリッツの係数行列Ｔ０を有する。この係数行列Ｔ０はサブブロックの行・列あたりＮｃ個の対称サブブロックを有する。ベクトルＸ０およびＹ０にはＮｃ個のサブベクトルがある。行列Ｔ０の次数は（ＮｘＮ）であり、Ｔ０のサブブロックの次数は（ＮｂｘＮｂ）である。
【００４０】
【数３】
2010262622.tif 000005
【００４１】
第１のシステムソルバー１３１は、各サブベクトルを対称サブベクトルと非対称サブベクトルとに分離する。式（２）および（３）の形をした２本の連立方程式では、１本は対称ベクトルで、もう１本は非対称ベクトルとなる。ベクトルＸＡおよびベクトルＸＳのサブベクトルには重複要素がある。連立方程式それぞれの次数は各サブブロックの畳み込みを行って半分に縮小し、テプリッツ行列とハンケル行列との和または差を求める。各サブブロックの下半分は無視する。この結果、異なる係数行列ＴＡおよびＴＳを有し、次数が（Ｎ／２ｘＮ／２）である２本の連立方程式（４）および（５）ができる。係数行列がブロックテプリッツ行列であるとき、これらの２本の連立方程式を第１のシステムソルバー１３１で求解して、ベクトルＸＳとＸＡそれぞれのサブベクトルの上半分および下半分である、ＸＳ１とＸＡ１を求めることができる。
【００４２】
【数４】
2010262622.tif 000006
【００４３】
係数行列Ｔ０がテプリッツ行列のブロックテプリッツ行列であるとき、第１のシステムソルバー１３１は係数行列ＴＡおよびＴＳの双方で行と列の再構成を行い、再構成した２本のブロックテプリッツ行列を得る。これら再構成された行列は次数が（ＮｃｘＮｃ）のテプリッツ行列であるサブブロックを有する。方程式（４）および（５）のベクトルの行もまた再構成される。これら再構成されたベクトルはその後対称サブベクトルを有するベクトルと非対称サブベクトルを有するベクトルとに分割される。再構成された行列双方の各サブブロックは半分に畳み込みされ、その結果得られた各サブブロックの要素は、テプリッツ行列とハンケル行列との和または差のいずれかとなる。こうして、各サブブロックの次数は（Ｎｃ／２ｘＮｃ／２）になった。この時点で４本の連立方程式ができあがっている。各連立方程式は異なる係数行列を有している。４本の連立方程式それぞれの次数は（Ｎ／４ｘＮ／４）である。これらの４本の連立方程式は公知の任意の手法を用いて第１のシステムソルバー１３１により求解される。得られた４つの解を統合して連立方程式（１）の解Ｘ０を生成する。
【００４４】
非限定的な実施例においては、方程式（１）の行列Ｔ０は複素エルミートテプリッツ行列のブロックテプリッツ行列である。ベクトルＸ０およびＹ０は複素ベクトルである。連立方程式を乗算すると、実方程式と虚方程式がそれぞれ一組になった方程式を得ることができる。これら２組の方程式はいずれもさらに分割して、対称サブベクトルを有するベクトルをもった方程式と、非対称サブベクトルを有するベクトルをもった方程式の、各組がいくつか得られる。これらの４組の方程式を統合すると、次数が（２Ｎｘ２Ｎ）である同一の係数行列をもつ２組の方程式（６）および（７）にすることができる。このサブブロックの次数は（ＮｂｘＮｂ）である。各行および列には２Ｎｃ個のサブブロックがある。サブブロックＴＳＲは行列Ｔ０の実対称コンポーネントであり、サブブロックＴＡＩは行列Ｔ０の虚非対称コンポーネントである。方程式（６）および（７）の下付き文字Ｒ、Ｉ、Ｓ、Ａは、それぞれコンポーネントが実、虚、対称、非対称であることを表している。
【００４５】
【数５】
2010262622.tif 000007
【００４６】
行列Ｔの各象限にはテプリッツ行列のサブブロックがある。ブロックベクトルＸ０１、Ｘ０２、Ｙ０１、Ｙ０２はサブベクトルを有し、そこに含まれる重複要素の除去は、行列Ｔの各サブブロックを畳み込みを行って半分にし、各サブブロックの次数を（Ｎｂ／２ｘＮｂ／２）まで縮小し、係数行列Ｔ１を生成することによって行うことができる。係数行列Ｔ０がブロックテプリッツ行列の場合、第１のシステムソルバー１３１は同一係数行列をもつこれら２本の連立方程式を解いてベクトルＸ０１およびベクトルＸ０２の要素を求める。それからこれらのベクトルを統合してベクトルＸ０を決定する。
【００４７】
テプリッツ・ブロックテプリッツ行列である係数行列Ｔ０については、係数行列Ｔ１の行および列を各象限内で再構成するとブロックテプリッツ行列の係数行列Ｔ２を得ることができる。ブロックベクトルについても再構成を行い、こうして２本の連立方程式の再構成によって得られたブロックベクトルを分割して、対称ブロックベクトルＸ１１Ｓ、Ｘ１２Ｓ、Ｙ１１Ｓ、Ｙ１２Ｓと、非対称ブロックベクトルＸ１１Ａ、Ｘ１２Ａ、Ｙ１１Ａ、Ｙ１２Ａとが得られるが、双方ともに重複要素がある。行列Ｔ２の各サブブロックについて畳み込みを行い、重複ベクトル要素を除去して次数を半分にできる。その結果、２つの異なる係数行列Ｔ２ＳおよびＴ２Ａをもつ（Ｎ／２ｘＮ／２）次数の連立方程式が４本できる。これら４本の連立方程式それぞれを第１のシステムソルバー１３１で解くと、４つのブロックベクトルＸ１１Ｓ、Ｘ１１Ａ、Ｘ１２Ｓ、Ｘ１２Ａの要素が求められる。その後、これらのベクトルを統合して解Ｘ０を決定する。
【００４８】
本発明の図２（ｂ）に開示するある実施形態においては、方程式（１）でテプリッツ行列である係数行列Ｔ０を変換すると、狭帯に近似した形になる。変換した係数行列の帯域外要素の大きさを小さくするには、行列Ｔ０の有する対角成分が拡張して行列Ｔ０より次数が大規模な行列Ｔを生成していてよい。行列Ｔ０の対角成分を拡張することにより、任意値の要素をもった付加対角成分も導かれることになる。この任意の値としては、以下の関係式（８）によって与えられる値があげられるが、これに制限されるものではない。
【００４９】
【数６】
2010262622.tif 000008
【００５０】
行列Ｔ（ｉ）（ｊ）の次数は（ＮｘＮ）である。インデックスｉおよびｊの値はゼロから付加対角成分数までを含む。この関係式で求めるのは、新たな対角成分の要素であって、それぞれの対角線上の他の要素に近似的に等しくなっている、拡張もとの対角成分の新要素ではない。ベクトルＸおよびベクトルＹはゼロ詰めされ、行にあるゼロ要素は行列Ｔで付加された行および列のパッドと対応している。付加未知変数Ｓｐを連立方程式に導入する。行列Ａｐは、パッド行に対応する非ゼロ要素を除いたすべてのゼロ要素をもつ列で構成される。行列Ｂｐは、行列Ｔ０に付加され行列Ｔを生成したパッド行で構成される。
【００５１】
変換した係数行列の帯域外要素の大きさも、行列Ｔ０の行および列の変形によって縮小可能である。行列Ｂｑは変形行からなる。一方、行列Ａｑは変形列と、変形行に対応する非ゼロ要素を除いたすべてのゼロ要素をもつ列とからなる。
【００５２】
【数７】
2010262622.tif 000009
【００５３】
方程式（９）の行列ＡｐおよびＡｑの値を求めるには、対角成分の拡張後で、しかも変形前に、行列Ｔを行列の積の和に分離する。行列の積のこの和は、対角行列Ｄ１ｉとＤ２ｉと、巡回行列Ｃｉとからなる。この行列Ｄ１ｉおよびＤ２ｉの対角線上の要素は通常指数関数で与えられる。指数Ｕｒｉ／Ｌｒｉを各対角行列Ｄｒｉに近似的に代入する。行列Ｕｒｉをフーリエ変換したものが帯行列Ｕｒｉｔである。以下の方程式（１０）の総和はインデックスｉについてのものである。
【００５４】
【数８】
2010262622.tif 000010
【００５５】
各指数Ｕｒｉ／Ｌｒｉの計算は、対角行列Ｄｒｉ、ｇｒｉ（ｘ）の主対角線上の要素をもとに式（１１）によって行うことができる。この和はインデックスｍについてのものである。
【００５６】
【数９】
2010262622.tif 000011
【００５７】
非線形回帰手法などの回帰手法を使用して展開関数ｃｏｓｉｎｅおよびｓｉｎｅの重み定数を求めることができる。回帰手法は公知の手法である。また、方程式（１２）の反復重み付け最小二乗法を使用しても重み定数を求めることが可能である。パッドや変形行および変形列に対応するｇｒｉ（ｘ）の要素は、通常は、重み定数を求める計算には含まれない。重み定数を求めたところで、パッドや変形行および変形列に対応する要素の値を計算する。その後、こうして求めた値を行列の元の値の代わりに使用して、パッドや変形行および変形列を求める。変形行および変形列は、ｇ（ｘ）と方程式（１１）の総和との差から計算する。方程式（１２）の外総和はインデックスｘに対するものである。方程式（１２）の内総和はインデックスｍに対するものである。
【００５８】
【数１０】
2010262622.tif 000012
【００５９】
ここでＢｒｐ（ｘ）は反復ごとの定数であり、かつ、その前の反復で得られた定数値に基づいて、反復ごとに更新される。以下の総和はインデックスｍに対するものである。
【００６０】
【数１１】
2010262622.tif 000013
【００６１】
方程式（９）は、狭帯域の変換後係数行列Ｔｔをもつ連立方程式（１３）に変換可能である。ベクトルＹｔを方程式（１４）で計算する。行列Ｕ１ｉｔおよびＵ２ｉｔは、メモリ内に格納されている定数、かつ帯状の、既知行列である。行列（PＬ１ｉ）はメモリ内に格納されている対角行列である。行列ＡｑｔおよびＡｐｔには列はほとんどなく、やはりメモリ内に格納されている。行列［ＦＦＴ］は高速離散フーリエ変換行列である。行列Ｃｉｔ、ＵｒｉｔおよびＬｒｉｔは行列Ｃｉ、ＵｒｉおよびＬｒｉのＦＦＴである。
【００６２】
【数１２】
2010262622.tif 000014
【００６３】
連立方程式（１３）は、図２（ｂ）の第２のシステムソルバー１３２により、任意の分解法を含めた公知のいずれの手段によっても解くことができる。通常は、まず未知変数ＳｐおよびＳｑを方程式（１５）、（１６）または（１７）で求めてから、未知変数Ｘを計算する。変形行および変形列がなければ、方程式（１７）を用いてベクトルＸＹのパッドの行部からＳｐ値を計算する。一般に、第２のシステムソルバー１３２でＳｐおよびＳｑを計算し、ついで方程式（１８）を使用してベクトルＸを計算する。
【００６４】
【数１３】
2010262622.tif 000015
【００６５】
行列Ｔが行列Ｔ０の十分な近似値であるとき、行列Ｔをもつ連立方程式の解Ｘを共分散係数行列Ｔ０をもつ連立方程式の解Ｘ０として使用することができる。解Ｘが解Ｘ０の十分な近似値でないとき、図２（ｂ）の反復子１３５は公知の任意の手法で解Ｘを使用して解Ｘ０を計算する。これらの手法に含まれるのは、初期解Ｘをとって更新解を求め、それを元の行列方程式（１９）の解として使用することである。その後、Ｙ０ベクトルと、元のＴ０行列と解Ｘの積との差を、Ｔ行列を持つ行列方程式（２０）に対する新しい入力列ベクトルとして使用する。ベクトルＹａはベクトルＹと近似的に等しい。ベクトルＸｕおよびＹａはパッドされたベクトルである。ベクトルＳｕは求めるべき未知変数である。
【００６６】
【数１４】
2010262622.tif 000016
【００６７】
ここに開示した発明のある実施形態においては、図２（ｂ）の第２のシステムソルバー１３２は、方程式（１）におけるブロックテプリッツ行列の係数行列Ｔ０の各サブブロックに対して、パッド行およびパッド列の付加や、既存の行および列の変形を行ったりして、係数行列Ｔを生成することができる。係数行列Ｔは、サブブロックがすべて対称である対称係数行列ＴＳと、サブブロックがすべて歪対称である歪対称係数行列ＴＡとの和に分離することができる。連立方程式（１）のベクトルＸ０およびＹ０はブロックベクトルであり、それぞれ、ＸＳとＸＡ、およびＹＳとＹＡという２つのブロックベクトルの和に分離できる。これらのベクトルの各サブベクトルはゼロ詰めされる。対称ベクトルＸＳおよびＹＳは対称サブベクトルを有し、また歪みベクトルＸＡおよびＹＡは歪対称サブベクトルを有している。対称サブベクトルの要素ｉは要素（Ｎ-ｉ）に等しい。歪対称サブベクトルの要素ｉは要素（Ｎ-ｉ）の負に等しい。ｉの範囲は１から（Ｎ／２-１）である。サブベクトルの要素はＮ個である。要素０およびＮ／２は歪対称サブベクトルではゼロであり、対称サブベクトルではいかなる値でもとれる。
【００６８】
以下の関係式を使用するとブロックテプリッツ行列を係数行列とする連立方程式の因数分解を行える。対称テプリッツ行列のサブブロックＴＳと、対称サブベクトルＸＳとの積が対称サブベクトルＹＳである。また対称サブブロックＴＳと、歪対称サブベクトルＸＡとの積が歪対称サブベクトルＹＡである。歪対称テプリッツ行列のサブブロックＴＡと、対称サブベクトルＸＳとの積は歪対称サブベクトルＹＡとなる。歪対称サブブロックＴＡと歪対称サブベクトルＸＡの積は対称サブベクトルＹＳである。対称サブベクトルのフーリエ変換は実であり、歪対称サブベクトルのフーリエ変換は虚である。
【００６９】
一般に、第２のシステムソルバー１３２は複素連立方程式の展開を行い、それを１本は実項の、そしてもう１本は虚項の、２本の連立方程式に分離する。これらの連立方程式はそれぞれをさらに分解して対称ベクトルを持つ連立方程式および歪対称ベクトルをもつ連立方程式を得る。こうしてできた４組の方程式を統合して次数が（４Ｎｘ４Ｎ）である実連立方程式を生成する。
【００７０】
非限定的な実施例において、係数行列Ｔ０は実テプリッツ・ブロックテプリッツ行列である。第２のシステムソルバー１３２は、方程式（１）を因数分解することにより、実テプリッツ・ブロックテプリッツ行列の係数行列Ｔをもつ２本の連立方程式（２１）および（２２）を生成する。行列Ｔのサブブロックは対称であり次数が（ＮｂｘＮｂ）である。係数行列Ｔの次数は（ＮｘＮ）である。Ｔ０の各行および列のサブブロックはＮｃ個である。方程式（２１）は対称ベクトルＸＳおよびＹＳで構成される。方程式（２２）は歪対称ベクトルＸＡおよびＹＡで構成される。方程式（２１）および（２２）はともに同一の係数行列Ｔを有している。
【００７１】
第２のシステムソルバー１３２は、パッド行およびパッド列を各サブブロック周辺に配置することにより、係数行列方程式（１）のサブブロックそれぞれの次数を増大させる。行列Ａは、行列Ｔ０より次数が大きい行列Ｔ、および行列Ｔ０の行および列の変形を行って生成した行列Ｔにより得られる。ベクトルＳは求めるべき未知変数を含んでいる。行列Ａは、連立方程式の求解の特性を改善する要素で構成することもでき、例えば、行列ＴとＴ０との照合性の向上、行列Ｔの条件数の削減、および行列Ｔ、行列Ｔｔの実変換などがあげられる。行列Ａは、変形列と、行列Ｔのパッドおよび変形行に対応する１つまたは２つの非ゼロ値を除いたすべてのゼロ値を有する列とで構成可能である。行列Ｂは、パッド行と、Ｔ０行列の要素を変形する変形行とで構成可能である。ベクトルＸＳ、ＸＡ、ＹＳおよびＹＡのサブベクトルは、パッド行に対応するゼロ埋め要素を有している。
【００７２】
【数１５】
2010262622.tif 000017
【００７３】
係数行列Ｔのサブブロックそれぞれを第２のシステムソルバー１３２によって、対角行列ｄ１ｉと巡回行列Ｃｉｘｙと対角行列ｄ２ｉとの積の和に分離する。この和はインデックスｉに対してのものである。対角行列ｄ１ｉおよびｄ２ｉの要素は、実偏角および／または虚偏角をもつ指数関数と、三角関数と、主対角線要素の下半分または上半分いずれかの要素とそのもう一方にある主対角線要素の上半分または下半分の負の要素とからなる要素と、再帰関係式によって対角成分の他の要素から求めた要素と、これらの要素を含んだ行列を因数分解または変換して求めた要素とによって与えられる。一般的ブロックテプリッツ行列の非限定的な実施例の場合、サブブロックは方程式（２３）で表わされる一般的な形をしている。
【００７４】
【数１６】
2010262622.tif 000018
【００７５】
方程式（２３）の部分行列Ｔｘｙは、行列ｕｒｉ、ｌｒｉ、とＣｉｘｙとの積からなる。以下の総和はインデックスｉに対するものである。
【００７６】
【数１７】
2010262622.tif 000019
【００７７】
非限定的な実施例として、ブロック係数行列Ｔは、２つの積からなるｉについての和によって表すことができる。各サブブロックは同じ対角行列ｄおよびｄ＊で分離され、ここでは行列ｄのフーリエ変換は、行列ｄ＊のフーリエ変換の複素共役である。これには、少なくとも１つのパッド行およびパッド列、または変形行および変形列を有する連立方程式が要る。ブロック行列Ｔは以下のように分離することができる。方程式（２４）において、行列ＤおよびＣｉはブロック行列である。
【００７８】
【数１８】
2010262622.tif 000020
【００７９】
対角行列ｕ／ｌまたはｕ＊／ｌの指数を含むサブブロックを、各サブブロックｄまたはｄ＊それぞれに近似的に代入する。対角行列ｕおよびｌは、方程式（１２）の手法など公知の任意の手法によって求められる。変換後の連立方程式（２６）は、係数行列の各サブブロックを個々に変換し、帯状のサブブロックを生成することにより生成される。行列ＴＬおよびＴＲは、高速フーリエ変換（ＦＦＴ）サブブロックと逆高速フーリエ変換（ｉＦＦＴ）サブブロックとで構成されるブロック行列であり、各サブブロックＴｘｙからなる積に変形する。行列積（PＬｒｉ）は、行列ｌｒｉの積からなるサブブロックをもつブロック行列である。行列ＴＬ、ＴＲおよび（PＬｒｉ）は、通常、主対角線成分に非ゼロブロックしか持たない。非限定的な実施例において、方程式（２７）から行列Ｔｔを効率的に計算することが可能である。行列Ｃｉｔは各サブブロックが対角行列であるブロック行列である。各サブブロックは行列Ｃｉの対応する巡回サブブロックのＦＦＴであり、方程式（２４）で求められる。行列ＵｒｉｔおよびＬｒｉｔは主対角線成分のサブブロックである非ゼロサブブロックのみを有するブロック行列である。行列Ｕｒｉｔの非ゼロサブブロックは全く等しい狭帯域サブブロックである。Ｌｒｉｔの非ゼロサブブロックは全く等しい。行列ＵｒｉｔおよびＬｒｉｔの非ゼロサブブロックは、それぞれ、行列ＵｒｉおよびＬｒｉの非ゼロサブブロックのフーリエ変換である。行列ＵｒｉおよびＬｒｉは、主対角線成分の対角サブブロックを除いてはすべてのサブブロックはゼロに等しい。行列ＵｒｉｔおよびＬｒｉｔは通常メモリ内に格納される。行列Ｌｒｉがすべて等しいとき、項（PＬｒｉ）は単一行列Ｌである。方程式（２７）で開示するように、必要な行列Ｕｒｉｔは２つのみであってよい。行列Ｕｒｉｔの非ゼロサブブロックは、行列の右上隅および左下隅にあるコーナー帯域からなる。これらのコーナー帯域は、行列Ｔｔのサブブロックに対するコーナー帯域となる。行列Ｔｔのサブブロックのコーナー帯域と行列Ｔｔのサブブロックの主対角線周辺にある帯域とを統合すると、行列Ｔｔのサブブロックは畳み込まれ次数が縮小される。
【００８０】
【数１９】
2010262622.tif 000021
【００８１】
方程式（２１）および（２２）を変換した後、係数行列の各変換後サブブロックを次数（Ｎｂ／２＋１）ｘ（Ｎｂ／２＋１）まで畳み込みして、変換後ベクトルの変換後サブベクトルにある重複要素を除去することができる。その結果できた２本の実連立方程式の係数行列の行および列に再構成を行って、次数がＮｃ（Ｎｂ／２＋１）ｘＮｃ（Ｎｂ／２＋１）である係数行列ＴＡおよびＴＳを生成することができる。係数行列Ｔ０がブロックテプリッツ行列のとき、係数行列ＴＡおよびＴＳの行および列で帯状の係数行列が連立方程式に生成され、この式を第２のシステムソルバー１３２で解くことができる。
【００８２】
係数行列Ｔ０がテプリッツ・ブロックテプリッツ行列のとき、係数行列ＴＡおよびＴＳは、テプリッツ行列のサブブロックからなる帯域を有する。これらのテプリッツ行列のサブブロックをパッドおよび変形して、行列Ｔ１ＳおよびＴ１Ａを生成できる。係数行列Ｔ１ＳとＴ１Ａとが生成されると、ベクトルＸ１Ｓ、Ｘ１Ａ、Ｙ１Ｓ、、Ｙ１Ａと、行列Ａ１Ｓ、Ａ１Ａとが生成される。ベクトルＳには付加未知変数が含まれる。行列Ａ１Ｓ、Ａ１Ａ、Ｂ１Ｓ、Ｂ１Ａは、それぞれ、行列ＡＳ、ＡＡ、ＢＳ、ＢＡであり、これらはさらにＴＳ行列およびＴＡ行列の要素を変形する際に使用した変形行および変形列と、行列ＴＳおよび行列ＴＡの次数を増大する際に使用したパッド行に対応する非ゼロ要素をもった列とで構成される。ベクトルＸ１Ｓ、Ｘ１Ａ、Ｙ１ＳおよびＹ１Ａにはゼロ埋め要素があり、これらは係数行列のサブブロックＴＳおよびＴＡの次数増大の際に使用した行に対応した、上記ベクトルの行に付加されたものである。
【００８３】
次いで、各連立方程式を因数分解して、１本は対称ベクトル、そしてもう１本は歪対称ベクトルである２本の連立方程式にする。第２のシステムソルバー１３２は、各サブブロックをパッド／変形した行列Ｔ１ＳおよびＴ１Ａに変換する。各連立方程式を方程式（２６）に開示の行列ＴＲ、ＴＬおよびＬｒｉで変換する。その後、各サブブロックを畳み込み、次数（Ｎｃ／２＋１）ｘ（Ｎｃ／２＋１）まで縮小する。次数が（Ｎｃ／２＋１）（Ｎｂ／２＋１）ｘ（Ｎｃ／２＋１）（Ｎｂ／２＋１）である４本の連立方程式それぞれに対して、異なる単一帯域の変換係数行列Ｔ２ＳＳ、Ｔ２ＳＡ、Ｔ２ＡＳおよびＴ２ＡＡを生成する。第２のシステムソルバー１３２はこの４本の連立方程式を解いて方程式（３１）の形式の方程式を求める。４本の連立方程式の各解を統合して解Ｘを生成する。
【００８４】
非限定的な実施例において、連立方程式（１）は複素エルミートテプリッツ・ブロックテプリッツ行列の係数行列Ｔ０、および複素ベクトルＸ０とＹ０を有する。連立方程式（１）を因数分解して２本の連立方程式（６）および（７）にすることができる。第２のシステムソルバー１３２は、方程式（６）および（７）の行列Ｔの各サブブロックについてパッド、分離、および変形を行い、方程式（２８）および（２９）の行列Ｔを求める。
【００８５】
【数２０】
2010262622.tif 000022
【００８６】
【数２１】
2010262622.tif 000023
【００８７】
方程式（２８）および（２９）の行列Ｔの各サブブロックは、ついで、方程式（２６）に開示したように行列ＴＲ、ＴＬおよびＬｒｉによって帯状サブブロックに変換が可能である。このサブベクトルについても変換を行い、各変換後のサブベクトルに含まれる重複要素は、行列Ｔの各サブブロック自身に畳み込みを行って除去する。係数行列Ｔ０がブロックテプリッツ行列のとき、２つの係数行列の行および列を帯状に再構成し、次数を縮小後に２本の連立方程式を第２のシステムソルバー１３２で解く。いずれの連立方程式も、行および列の再構成前は同じ係数行列Ｔ１を有している。
【００８８】
係数行列Ｔ０がテプリッツ・ブロックテプリッツ行列のとき、Ｔ１の各象限内の行および列を各象限内で再構成して、帯域をもつ係数行列をテプリッツ行列のサブブロックを含む各象限内に生成することができる。第２のシステムソルバー１３２は、パッドおよび／または変形行および変形列を各テプリッツ行列のサブブロックに付加し、ついで、各サブブロックを帯状の式に変換する。変換後のサブブロックは実部であることから、変換後のベクトルのサブベクトルは、重複要素のある対称サブベクトルおよび歪対称サブベクトルに分割が可能である。各サブブロック自身に畳み込みを行っていくと、各サブベクトルの重複要素を除去できる。４本の連立方程式には、次数が２（Ｎｃ／２＋１）（Ｎｂ／２＋１）ｘ２（Ｎｃ／２＋１）（Ｎｂ／２＋１）である２つの異なる係数行列ができる。第２のシステムソルバー１３２はこの４本の連立方程式を解いて、方程式（３１）の形の連立方程式４本を得る。４つの解ベクトルを統合して解Ｘを得る。
【００８９】
図２（ｃ）に開示の本発明のある実施形態においては、ベクトルが対称または歪対称のいずれかである実連立方程式における対称または歪対称テプリッツ行列の係数行列は、上記で定義したように、ベクトルＳにあるＮ／２の未知変数要素を加算すると巡回行列Ｃに展開できる。同様の手法で、上記で定義したように、ベクトルが対称または非対称ベクトルである連立方程式にもあてはめることができる。巡回行列であるＣは、フーリエ変換で対角化されるテプリッツ行列型である。方程式（８）でＣの新しい対角要素を求めることができる。図２（ｃ）の第３のシステムソルバー１３３は、連立方程式にフーリエ変換を用いる手法などの公知の任意の手法によって方程式（３０）のベクトルＳおよびベクトルＸの計算を行う。これらの計算にはＯ（Ｎ／２）３フロップスという複雑性がともなう。初期連立方程式の次数は（ＮｘＮ）である。連立方程式（３０）および行列Ｃの次数は（２Ｎｘ２Ｎ）に近似である。ベクトルＸおよびＹにはゼロ埋め要素があり、これらは通常ベクトルの始点および終点にあり、テプリッツ行列から巡回行列Ｃを作成する際に使用したパッド行およびパッド列と対応している。
【００９０】
【数２２】
2010262622.tif 000024
【００９１】
複素連立方程式の場合は、ベクトルＳが持つことが可能な未知変数の数は２Ｎ個もある。元の連立方程式の形は、通常、この手法の応用には適していない。そういう場合は、上記で開示したように連立方程式の因数分解を行い、対称および非対称、または歪対称および対称の各ベクトルと、対称および歪対称のテプリッツ行列とを持つ形に整える。ベクトルおよび係数行列がこの形になったところで、本手法を適用する。この手法の計算効率は全行列についてみるとよくはないが、行列によってはよいものがある。
【００９２】
非限定的な実施例において、ブロックテプリッツ行列を係数行列とする連立方程式で、その係数行列のサブブロックが対称または歪対称いずれかであり、かつ、そのベクトルが有するサブベクトルが上記で定義したように対称または非対称いずれかであるか、または上記で定義したように対称または歪対称のいずれかであれば、この連立方程式の次数を増大させることが可能なので、ブロックテプリッツ行列の係数行列からブロック巡回の係数行列を生成できる。そのためには、通常各サブブロックを取り囲むようにして存在するパッド行およびパッド列を連立方程式に付加する必要がある。連立方程式の次数は通常２倍、または近似的に２倍になり、近似的にＮ／２個の付加未知変数が連立方程式に導入される。初期連立方程式の次数は（ＮｘＮ）であり、行列Ａの持つ列数は、通常Ｎ／２列で、各列の１つまたは２つの非ゼロ要素以外はすべてゼロ値である。これらの列には通常２Ｎ個の要素がある。Ｓの値を求めるには、次数が通常（Ｎ／２ｘＮ／２）である連立方程式を解かなければならない。巡回サブブロックをフーリエ変換して対角サブブロックを得ることができる。係数行列の行および列を再構成して非ゼロサブブロックが主対角線上にしかない係数行列を生成する。この連立方程式を第３のシステムソルバー１３３で解いて方程式（３１）の形をした方程式を得る。方程式（３２）を使用してベクトルＳを求めることができる。方程式（３２）は、方程式（３１）のパッド行から生成する。これらの行にはベクトルＹのゼロ値がある。ベクトルＳが既知になっていれば方程式（３１）を使用してベクトルＸを計算できる。
【００９３】
非限定的な実施例において、初期連立方程式の係数行列は実対称または複素エルミートのテプリッツ・ブロックテプリッツ行列である。上記のいずれの手法を使用しても、サブブロックが対称であり、かつ、その手法により異なるが、ベクトルのサブベクトルが対称または非対称、または対称または歪対称である係数行列をもつ連立方程式を第３のシステムソルバー１３３で生成できる。係数行列の各サブブロックを展開して巡回式を得る。展開した連立方程式を変換、再構成して、ベクトルＳおよびＸを求める。
【００９４】
連立方程式を、巡回型または帯状の係数行列を持つ形、または次数が縮小された形にした後、公知の任意の手法で求解可能である。これらの手法には、ガウスの消去法などの古典的な手法、各種共役勾配手法などの反復法、および固有値分解、特異値分解、ＬＤＵ分解、ＱＲ分解、およびコレスキー分解などの分解法が含まれる。求解後の連立方程式はそれぞれ方程式（３１）の形になっている。方程式（３１）において、項Ｘｙは上記で開示した任意の係数行列の逆行列とベクトルＹとの積である。この任意の係数行列は、巡回、帯状、または初期の係数行列より次数が小規模である係数行列であってよい。ベクトルＹは、再構成または変換されたベクトルであってよい。行列ＸＡは逆係数行列と、上記で開示した任意の行列Ａとの積である。ベクトルＸおよびベクトルＳは未知ベクトルである。行列ＸＡは通常図２（ａ）の実施形態には必要ない。図２（ｃ）の実施形態では、行列ＸＡは巡回係数行列を生成する際に使用したパッド列から求められる。行列Ｂは行列Ｂｐおよび行列Ｂｑからなり、それぞれ、パッド行および変形行を含んでいる。求解した連立方程式それぞれの解を統合して方程式（１）の解を生成する。図２（ｂ）および２（ｃ）の実施形態でのパッド行およびパッド列については、ベクトルＳｐは方程式（３２）により求めることができる。
【００９５】
【数２３】
2010262622.tif 000025
【００９６】
テプリッツ・ブロックテプリッツ行列構造を持つ係数行列において、ここに開示する発明の別の実施形態は、係数行列にあるどのテプリッツ行列レベルにも使用可能である。ここに開示の手法はまた、あらゆるテプリッツ行列のサブブロックに適用可能である。
【００９７】
各種の装置１００では、メモリストレージ、メモリアクセス、および計算複雑性に関するその性能要件もさまざまである。装置１００に応じて、各種の手法を並列コンピュータアーキテクチャに実装できる。ここに開示の手法を特定の装置に実装する場合、行列Ｔｔの帯幅ｍをどのくらいにするか、パッドや変形した行ｐおよび行ｑをいくつにするか、どのハードウェアアーキテクチャにするか、といった手法パラメタをその特定の装置用に選択する必要がある。
【００９８】
さらなる効率改善が得られるのは、係数行列のサブブロックが大きく、かつ、係数行列Ｔ０の逆行列Ｔ０−１が、行列Ｔ０−１のサブブロックそれぞれの主対角線から離れるに従って、その大きさが小さくなるという要素を持つときである。図２（ｂ）の第２のシステムソルバー１３２はベクトルＸ０をゼロ値を持つ行でゼロ詰めしてベクトルＸを生成する。ベクトルＸのゼロに設定される行は通常Ｘの各サブベクトルの始点および終点にある行である。ゼロ値の行をベクトルＹ０の各サブベクトルの始点と終点に付加してゼロ埋めされたベクトルＹを生成する。それから、ベクトルＸをベクトルＸｙｒとベクトルＸｒとに分割する。ベクトルＸｙｒをまず方程式（３３）から計算し、次いで、ベクトルＸｙｒの各サブベクトルの始点と終点にある、追加の選択行要素をゼロに設定してベクトルＸｙｒｐを生成する。ベクトルＸｙｒｐは、ベクトルＹにのみ近似的に依存するベクトルＸの一部である。その後、ベクトルＸｒを方程式（３４）で計算する。行列Ｔｓには、行列Ｔ０の要素、またはベクトルＸｙｒｐの一部となっていないベクトルＸ非ゼロ要素に対応する行列Ｔの要素いずれかが含まれる。これらの要素は、通常、パッド行またはパッド列ではない、行列Ｔまたは行列Ｔ０のサブブロックのコーナー部の要素である。ベクトルＸｒの要素は、ベクトルＸｙｒｐを生成するためにベクトルＸｙｒにおいてゼロに設定された追加の選択行要素である。第２のシステムソルバー１３２は、上記に開示した任意の手法により方程式（３３）および（３４）を解く。連立方程式（３４）は、通常、連立方程式（３３）よりかなり小規模である。行列Ｔはテプリッツ行列に近似ではあるが、行列ＴおよびＴｓに含まれる対称行列ゆえに、実施形態図２（ａ）に開示の手法を使用して方程式（３３）および（３４）の解を求めることができる。この対称性は、係数行列の異なる行の要素のオーダーに関係している。一般に、図２（ａ）の実施形態の手法は、係数行列に含まれる行が、その係数行列の別の行にある要素の逆オーダーになっている要素を持つ場合に適用可能である。通常、実施形態図２（ｂ）に開示の手法を使用して方程式（３３）および（３４）を解く。係数行列が２階（ｌｅｖｅｌ）のテプリッツ行列からなるとき、１度に１階ずつ行い２度で方程式（３３）および（３４）の形の方程式を生成することができる。
【００９９】
【数２４】
2010262622.tif 000026
【０１００】
多くのテプリッツ・ブロックテプリッツ行列Ｔは悪条件である。パッド行およびパッド列を使用して行列Ｔの条件を実質的に改善することができる。解Ｘが解Ｘ０に十分近似でないとき、図２（ｂ）の反復子１３５は方程式（１９）および（２０）を使用して公知の任意の手法により解Ｘ０を計算する。大部分がすでに計算されて各更新事項が求められているため更新には数学的な演算はほとんど要らない。解Ｘが解Ｘ０に十分近似であるとき、解Ｘは反復子１３５が出す解Ｘ０としての出力である。
【０１０１】
システムプロセッサ１３４は信号Ｊを解Ｘ０から計算する。信号Ｊの計算には、解Ｘ０および信号Ｊ０の両方を要する。信号Ｊは、ベクトルＸ０および信号Ｊ０の要素からなる積の和を計算するなど、任意の既知の従来手法で計算できる。装置によっては、信号Ｊ０がないものがある。そのような場合、信号ＪはベクトルＸ０、または実際にベクトルＸ０でありうるものからなる。ベクトルＸ０および信号Ｊが双方ともに求解成分１３０の出力であるとき、信号ＪはベクトルＸ０でも構成される。信号ＪおよびＪ０いずれも、複数の信号、単一の信号、デジタル信号、またはアナログ信号であってよい。
【０１０２】
どのハードウェアアーキテクチャにするかは、その手法を実装する個々の装置１００がもつ性能、コストおよびパワーなどに対する制約によって決まる。方程式（３１）のベクトルＸｙと行列ＸＡの列とを、ＳＩＭＤ型並列コンピュータアーキテクチャ上で同じ時間に出された同じ命令により、ベクトルＹｔおよび行列Ａｔから計算することができる。ベクトルＹｔおよび行列Ｔｔは、上記で開示した変換した連立方程式のいずれでも得られる行列ＡおよびベクトルＳの積、および行列Ｔｔの計算を要する積は、どれも既存の並列コンピュータアーキテクチャで計算することが可能である。行列Ｔｔの分解もまた既存の並列コンピュータアーキテクチャで計算可能である。
【０１０３】
図２（ａ）および２（ｃ）の実施形態に開示した手法は、テプリッツ行列およびブロックテプリッツ行列を係数行列とする連立方程式に制限されるものではない。いずれの手法も、係数行列の行要素がその係数行列の別の行の要素のオーダーに対して逆オーダーになっている連立方程式であればいずれにも適用可能である。連立方程式のベクトルは、対称ベクトルと、そのベクトルの要素の負である他の要素を持つベクトルとの和に分離可能である。ベクトルの重複する大きさを除去するには、係数行列の次数を縮小する。これにより、別の連立方程式は生成されないが、求解効率が上がる。
【０１０４】
ここに開示の手法を効率的に実装することができる回路としては、デジタル信号プロセッサ、一般的なマイクロプロセッサ、特定用途向け集積回路、フィールドプログラム可能なゲートアレイ、および中央演算処理装置などのコンピュータアーキテクチャの回路があるが、これらに制限されるものではない。これらのコンピュータアーキテクチャは、係数行列を持つ連立方程式を求解して動作を行う装置の一部である。本発明は、フロッピーディスク、読取専用メモリ、コンパクトディスク、ハードディスク・ドライブなどのコンピュータで読み取り可能な記憶媒体を備えた有形の媒体で実行されるコンピュータコードという形で実施してよく、その場合、コンピュータのプロセッサがコンピュータプログラムコードの読み込みを行い、それを実行した時点で、そのコンピュータのプロセッサが本発明を実施するための装置となる。コンピュータのプロセッサに実装した場合は、コンピュータプログラムコードの各セグメントでそのプロセッサの環境設定を行って特定の論理回路を作成する。
【０１０５】
本発明は、ここに示した詳細な説明に限定することを意図するものではない。本発明の範囲から外れることなく、さまざまな変形を細部に行うことが可能である。本開示で使用した用語の代わりに、それと同義または類義の他の語を使用することが可能である。開示のコンポーネントの数および構成は変えてもよい。装置１００および求解成分１３０の異なるコンポーネントを統合したり、または多数のコンポーネントにとに分離したりすることができる。装置１００のコンポーネントすべてを統合して単一のコンポーネントとすることが可能である。求解成分１３０のサブコンポーネントすべてを統合して単一のコンポーネントとすることが可能である。求解成分１３０のサブコンポーネントを装置１００のコンポーネントと統合してもよい。求解成分１３０は、本発明の実施形態のうち１つ、２つ、または３つすべてを実施するために必要とされるコンポーネントからなってよい。
【図１】
2010262622.tif 000027
【図２】
2010262622.tif 000028
【外国語明細書】
2010262622000001.pdf