(57)【要約】演算数を削減し、回路を単純化し、さらに消費電力の低減を達成するための線形変換を行なう改善された方法および装置が提供される。本方法は、ＣＤＭＡアプリケーションに現われる複素Ｕ変換を行なう。本装置によって、異なる拡散係数の到来信号を同時に分析することが可能となる。
2004511046.tif 000002
【特許請求の範囲】
【請求項１】
実数または複素数、または有限の場の上で、少なくとも１つのｎ次元入力ベクトルであるｒ×ｎ行列によって表わされる線形変換の実行効率を強化する方法において、
各省略された行と各選択された行との間の比をメモリに格納する段階と、
前記行列の０の列および入力ベクトルの対応するスカラ・コンポーネントを省略する段階と、
前記行列の各列を正規化する段階と、
前記正規化された行列中の等しい列のグループから修正されたベクトルを生成する段階と、
修正された行列を生成する段階と、
出力ベクトルを獲得する段階と、
から構成されることを特徴とする方法。
【請求項２】
前記変換行列をいくつかのサブ行列へ分割し、各サブ行列の積に起因する前記出力ベクトルを単一化することにより、前記出力ベクトルを獲得する段階をさらに含むことを特徴とする請求項１記載の方法。
【請求項３】
前記修正された行列が、前記変換行列の行の部分集合を包含することを特徴とする請求項２記載の方法。
【請求項４】
各サブ・ベクトルがサブ行列に対応するように前記入力ベクトルをいくつかのサブ・ベクトルへ分割する段階をさらに含み、前記出力ベクトルは各サブ行列の積に起因する前記出力ベクトルを加えることにより獲得されることを特徴とする請求項３記載の方法。
【請求項５】
修正された行列をいくつかのサブ行列に分割する段階をさらに含み、出力ベクトルは各サブ行列の積に起因する前記出力ベクトルをそれぞれのサブ・ベクトルごとに、加えることにより獲得されることを特徴とする請求項１記載の方法。
【請求項６】
前記列にリード要素の反転を乗ずることにより、前記行列の各列を正規化する段階をさらに含むことを特徴とする請求項１記載の方法。
【請求項７】
前記出力ベクトルは、前記行列および前記入力ベクトルの積であることを特徴とする請求項１記載の方法。
【請求項８】
前記正規化された行列中の等しい列のグループを識別し、唯一の場所を各識別されたグループに付する段階をさらに含むことを特徴とする請求項１記載の方法。
【請求項９】
線形変換を実行するための装置において、
入力データおよび予め決められたデータを受け取る第１および第２入力と、
前記入力データおよび前記予め決められたデータに作用する変換回路と、
第１メモリに接続され、前記メモリのセルにアクセスするために、および、前記第１入力を経由してデータを受信するデータ受信モードと、前記第１入力を経由して到着する到来データを阻止するデータ処理モードと、の間の選択を制御するために、対応するアドレスを生成する制御およびアドレス発生回路と、
前記装置の動作タイミングを制御するためのカウンタ回路と、
から構成されることを特徴とする装置。
【請求項１０】
前記変換回路は、前記入力データの各要素を変換データの対応する要素で乗算することを特徴とする請求項９記載の装置。
【請求項１１】
前記変換回路は、前記乗算の結果を格納するメモリを含むことを特徴とする請求項１０記載の装置。
【請求項１２】
前記変換回路は、加算および累算回路を含むことを特徴とする請求項９記載の装置。
【請求項１３】
前記データ受信モードと前記データ処理モードとの間を選択するマルチプレクサ回路をさらに含むことを特徴とする請求項９記載の装置。
【請求項１４】
前記制御およびアドレス発生回路は、さらに、
予めプログラムされた処理および制御データを格納する第２メモリと、
前記データ受信モードと前記データ処理モードとの間を選択するコンパレータ回路と、
から構成されることを特徴とする請求項９記載の装置。
【請求項１５】
前記制御およびアドレス発生回路は、さらに、
第１マルチプレクサのセットであって、その各々は変換データを受信する少なくとも１つの直接入力および別の入力を有し、それに前記変換データが対応するインバータを経由して供給され、前記第１のセットは変換データまたは反転された変換データを転送するために前記変換データによって提供された予め定める値によって制御される、第１マルチプレクサのセットと、
第２マルチプレクサのセットであって、その各々は前記第１マルチプレクサのセットから選択された対応するマルチプレクサの出力に接続された少なくとも１つの入力および別の入力を有し、前記第２のセットは前記コンパレータ回路によって制御され、各マルチプレクサの出力を前記第１のセットからその対応するマルチプレクサの出力へ転送することによって前記第２のセットから第１アドレスを提供し、あるいは前記第２メモリに格納されたデータを転送することにより第２アドレスの少なくとも一部を前記第１メモリへ提供する、第２マルチプレクサのセットと、
前記データ処理モード中に前記第２マルチプレクサのセットと共同して動作し、未接続の入力および前記第２メモリ接続された入力を有し、前記コンパレータ回路によって制御されるマルチプレクサであって、それによって前記第２アドレスの残りの部分を提供するマルチプレクサと、
から構成されることを特徴とする請求項１４記載の装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、デジタル信号処理の分野に属する。それは、演算動作回数を削減し、単純化された回路および低消費電力を達成する線形変換を実行するための改善された方法および装置を提供する。
【０００２】
【従来の技術】
線形変換は、信号またはデータ処理に一般に使用される。線形変換は、「入力ベクトル」とみなされるｎ次元のベクトル、「出力ベクトル」とみなされるｒ次元のベクトルから生成する。多くの応用では、入力ベクトルは、処理を要求する所定の信号であるデジタル・サンプルから成る。しかしながら、線形変換への応用はどのような特定の領域にも制限されず、それらは科学技術のすべての分野にとって必要であるとともに、それらの効率的な特性が非常に期待されるものである。
【０００３】
１組のｎ次元ベクトル（実数、複素数、またはスカラの任意の領域からなる）から１組のｒ次元ベクトル（同じスカラ領域にわたる）への一般的な線形変換は、次式によって与えられるｒ×ｎ次数の行列（マトリックス）によって表わされる。
【０００４】
【数１】
2004511046.tif 000003
【０００５】
一般的な入力ｎ次元の列ベクトルは、次式の形式をとる。
【０００６】
【数２】
2004511046.tif 000004
【０００７】
線形変換は、入力ベクトルｘから、次の方程式によって与えられるベクトルの行列積を通して、次元ｒの出力列ベクトルｙを生成する。
【０００８】
【数３】
2004511046.tif 000005
【０００９】
線形変換の直接演算は、ｒ・ｎ回の乗算およびｒ・（ｎ−１）回の加算を要求する。
【００１０】
２進法の行列は、本発明の開発および応用に特に重要である。２進２極行列は、各エントリに±１の値だけを含むものである。今後、それらはＵ行列と称される。Ｕ行列によって表わされる線形変換はＵ変換と称される。上記の表現において、与えられた変換がＵ変換である場合、そのときｒ・（ｎ−１）回の加算／減算がその直接の演算に要求されるであろう。別のタイプの２進・行列は、０と１の値だけを含んでいるものである。それらは０−１行列と称される。０−１行列によって表わされる線形変換は０−１変換と称される。上記の表現では、平均して、ｒ・（ｎ−１）／２回の加算が直接の演算に要求されるであろう。
【００１１】
本テキストにおいて、用語「２進変換」は、上述した２つのタイプの変換、すなわち、Ｕ変換および０−１変換を含む。用語紹介を終えるにあたり、用語Ｕベクトルとはそのコンポーネントに、および同様に±１値を有するベクトルをいい、０と１の値を有するベクトルは０−１ベクトルと称される。
【００１２】
２進変換処理は、入力ベクトルの加算および減算コンポーネントから成る。それらは、加算器と減算器のようなコンポーネントを必要として、電気的な特定用途向け集積回路（ＡＳＩＣ）としてのハードウェアの中で実行される。これらのコンポーネントの使用は高価であるし、また、エネルギを消費し、さらにそれらの構造は貴重なエリアを占有することになる。これらの資源の消費量を低減した２進変換を行なうハードウェアを実現することが、多くの技術分野においてその必要性を増加させている。
【００１３】
デジタル信号処理の様々な側面から、Ｕ変換への広範囲の利用法がある。それは、イメージ処理や無線通信のような多種多様の通信技術を含む。
【００１４】
現在、直接シーケンス（ＤＳ）符号分割多重接続（ＣＤＭＡ）スペクトラム拡散通信システムに世界的な関心が集まっている。ＩＳ−９５［ＴＩＡ／ＥＩＡ／ＩＳ−９５−Ａ、「二重モードの広帯域スペクトラム拡散セルラ・システム用移動局基地局の互換性基準」、１９９６年２月２７日］が発展するＤＳ−ＣＤＭＡシステムの１つの例である。
【００１５】
ＣＤＭＡ通信技術では、複数ユーザのデータが複合信号で送られ、その後送信前に擬似ランダム雑音（ＰＮ）コードが乗じられるが、それはランダム雑音特性（低い相互相関のような）を有するＵシーケンスである。拡散特性は、マルチパス・ノイズ、ジャミングまたは検出を含むノイズに対する送信抵抗を形成する。チャネリング・コードより長いスクランブル・コードも適用される。第二世代（ＩＳ−９５−Ｂ）および第三世代（３Ｇ）の広帯域（ＷＢ）ＣＤＭＡ標準規格のこの送信方法は、受信機がマルチコード検出を行なうことを要求する。これは結合したチャンネルを同時に逆拡散を行う作業で、その各々は既に異なるチャネリング・コードに従って拡散されていたものである。それはＵ変換の応用によってなされ、ここで変換行列を含む拡散コードはアダマール行列の行である。これは、有効なＵ変換技術が資源の消費を低減する計算タスクを実現するために望まれる多くの例のうちの１つである。
【００１６】
特定のタイプにおいて、線形変換の特性を改善するいくつかの既知の手法がある。非常に広い範囲から選ばれたわずかの適切な例がここで述べられる。畳み込みを行い、ＤＳＰ中でフィルタとして使用されるトップリッツ（ＴＯＰＬＩＴＳ）変換は、ｎがドメイン領域の次元とすると、Ｏ（ｎ・ｌｏｇ２（ｎ））の加算および乗算処理を要求する古典的な高速フーリエ変換（ＦＦＴ）アルゴリズムを使用することにより効率的に行なうことができる。対照的に、標準的で、直接的な方法は、Ｏ（ｎ２）の加算および乗算を要求する。詳細は、［Ｊａｍｅｓ Ｗ． Ｃｏｏｌｅｙ ａｎｄ Ｊｏｈｎ Ｗ． Ｔｕｋｅｙ， ｉｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｔｈｅ ｍａｃｈｉｎｅ ｃａｌｃｕｌａｔｉｏｎ ｏｆ ｃｏｍｐｌｅｘ Ｆｏｕｒｉｅｒ ｓｅｒｉｅｓ， Ｍａｔｈｅｍａｔｉｃｓ ｏｆ ｃｏｍｐｕｔａｔｉｏｎ， １９（９０）： ２９７−３０１， Ａｐｒｉｌ １９６５］を参照すること。
【００１７】
ＣＤＭＡ技術を含むデジタル信号処理で使用される特定タイプのＵ変換は、アダマール行列によって表わされるウォルシュ−アダマール変換である。アダマール行列は、以下のように再帰的に定義することができる。
【００１８】
【数４】
2004511046.tif 000006
【００１９】
そして、あらゆる整数ｎ、累乗２に対し：
【００２０】
【数５】
2004511046.tif 000007
【００２１】
複雑性を低減しかつエネルギを長持ちさせるこの変換を行なうアルゴリズムは、高速ウォルシュ・アダマール変換（ＦＷＴ）であり、それは、ｎ・ｌｏｇ２（ｎ）に対するｎ×ｎアダマール行列のための加／減算の数を削減する。これは、これらの動作のための最適な節約を提供する。この方法を強調する基本概念は、ＦＦＴ手法に類似する。
【００２２】
Ｕ変換の形式は本発明による別の特徴によって修正され、トップリッツＵ変換の特性に対し効率的な方法および装置を提供する。これらの変換は与えられたＵシーケンスまたは複雑なＵシーケンスを備えた完全または部分畳み込みを表わす。トップリッツＵ変換のワイヤレス通信への応用には、実数および複素擬似ランダム（ＰＮ）あるいは黄金Ｕ変換を備える畳み込みを利用する初期時間同期および探索器を含む。黄金シーケンスは、２つのＰＮシーケンスのＺ２合計によって構成される。
【００２３】
本発明の上記２進の解釈は、発明の別の局面によって、比較的少数の異なるエントリを備えたｒ×ｎ行列によって表わされる線形変換の特性のための効率的な方法および装置へと一般化される。本発明のこの進化した局面を適用することにより、複素Ｕ変換および線形変換は、｛０，１，−１｝−エントリを備える行列によって表わされる。本発明のこの広範囲な好適な実施例は、一般化された消去法（ＧＥＭ：ｇｅｎｅｒａｌｉｚｅｄ−ｅｌｉｍｉｎａｔｉｏｎ ｍｅｔｈｏｄ）と呼ばれる。
【００２４】
広帯域ＣＤＭＡおよび進化したＤＳＰの将来技術における恐らく他の派生技術は、異なる拡散係数において到来信号の同時分析から利益を得るであろう。これは、マルチコード・チャンネルに道を与え、それによってファックス、通常電話の会話およびネットワークに過度の負担をかけないインターネット・データのような異なるタイプの情報を同時に受信することが可能となるであろう。本発明の別の局面として、この種の線形動作に対する効率的な方法および装置がある。それは、追加のプロセッサを備える発明におけるＵ−２進の修正版を含む。この追加のプロセッサは、Ｕ−２進によって要求される加算の数に関する情報を用い、多様なサブセクション中のＵ−２進をグローバルな追加の低速度で適用する構成（ｃｏｎｆｉｇｕｒａｔｉｏｎ）を発見する。
本発明の別の主用途は、ワイヤレス・マルチメディア・システム、ＧＰＳ衛星を基礎にする位置システム、その他を含む。モバイル通信や他のモバイル、および計算を基礎とするシステムの中味において、線形処理に用いられる現時点の消費を削減することが本質的である。本発明をモバイル電話技術に応用することは、バッテリの寿命を延ばし、回路を削減することができ、また応答時間を短くすることができる。
本発明のこれらや他の特徴および利点は、次の詳細な説明を参考にすることにより、また添付の図面を参照することによりさらに明らかになるであろう。
【００２５】
【実施例】
本発明の方法を解説するにあたり、基本となる２つの新しい事項がある。最初は、等価ベクトル（ｅｑｕｉｖａｌｅｎｔ ｖｅｃｔｏｒ）である。同じ次元の２つの０でないベクトルは、それらがそれぞれ他方の積である場合、本テキストにおいて等価と呼ばれる。この項は、与えられた行列の２つの行または２つの列に適用される。第２の用語は、与えられた行列中の列のリード要素である。本発明の全体に亘って使用される定義は、前述の行列の各列で最も高い指標の０でないコンポーネントである。この定義は、与えられた行列の中で一律に使用される所定の列指標次数（ｃｏｌｕｍｎ ｉｎｄｅｘ−ｏｒｄｅｒ）に依存する。新しい次数の再定義は、新しいリード要素の再定義で生じる。例えば、与えられた行列のリード要素は、どちらの次数を選択することがその目的のために適切であるらしいかに依存して、各列の最下位の０でない要素または最高位の０でない要素である。
０−１行列
本発明の好適な実施例は、０−１の２進の線形変換を行なう効率的な方法を提供する。以後、それはさらに「０−１方法」と称される。次の例は、０−１方法への導入およびその主要な概念の概略である。
【００２６】
例：与えられた０−１の２進　４×１４行列Ａ：
【００２７】
【数６】
2004511046.tif 000008
【００２８】
および１４次元の入力ベクトル、
【００２９】
【数７】
2004511046.tif 000009
【００３０】
４次元の「出力」ベクトルを計算すると仮定して、
【００３１】
【数８】
2004511046.tif 000010
【００３２】
本発明の好適な実施例によれば、行列Ａは、等価線（ｅｑｕａｌ ｌｉｎｅ）があるか最初にチェックされる。等しい２行のラインがないので、その手順は次のステップに進む。次に、出力ベクトルｙは、それぞれの入力ベクトル座標である係数を備えた列の合計として表現される。従って、
【００３３】
【数９】
2004511046.tif 000011
【００３４】
このステージで、０の列は、それらの係数と共に、削除されるであろう。入力ベクトルに関して、本発明の好適な実施例によって行われる第１のステップは、任意に出現する０でない列の係数を集めて合計することである。したがって、６つの項で、次の減少されたベクトル方程式が実現される。
【００３５】
【数１０】
2004511046.tif 000012
【００３６】
この表現は次の定義によって単純化してもよい。
【００３７】
2004511046.tif 000013
これは次式を意味する。
【００３８】
【数１１】
2004511046.tif 000014
【００３９】
これはオリジナルの問題に等しいが、削減された列数を備える。しかしながら、現時点では、この種の削減は使い尽くされている。さらに利点を増すために、そのベクトル方程式は、２つのベクトル方程式における次の等価なセットに分割されるであろう。
【００４０】
【数１２】
2004511046.tif 000015
【００４１】
この好適な実施例の第１歩として、これら２つの方程式の各々は別々に扱われるであろう。したがって、同じゼロでない列の係数は集められ合計される。その結果、このステージで、方法は６つの別々の加算項を備えた２つのベクトル方程式のセットとなる。
【００４２】
【数１３】
2004511046.tif 000016
【００４３】
さて、出力ベクトルｙの演算を完了するために、４つの追加の加算のみが要求されることが明らかである。従って、所望の結果は、１６回の加算の合計で実行された。この計算プロセスを行なう従来の先行技術の方法が２８回の加算を要求するであろうことは容易に検証されるであろう。本発明のこの好適な実施例に対する先行する記述は、行列の次元が大きくなるに従い、本方法による効率性の向上がさらに明らかになるであろう。
【００４４】
一般に、本発明の０−１の２進の特徴となる点は、ｎ次元ベクトルｘによる次元ｒ×ｎの２進の０−１行列Ａの積に対する効率的な方法および装置にある。行列は次式によって与えられる。
【００４５】
【数１４】
2004511046.tif 000017
【００４６】
入力ベクトルは次式によって与えられる。
【００４７】
【数１５】
2004511046.tif 000018
【００４８】
入力ベクトルのエントリは、実数または複素数、またはスカラ（例のためのＺ２のような）の任意の分野に属するものである。ゴールは、ベクトルｘと行列Ａの積の結果を求めることである。この結果は次式のように表現されるであろう。
【００４９】
【数１６】
2004511046.tif 000019
【００５０】
記述される手続きは再帰的であり、また、ステップの次のシーケンスまたはそれらの一部は各反復で繰り返されるであろう。本発明の好適な実施例によれば、最初のステップは、等しい行のチェックである。可能な場合、入力ベクトルのあらゆる処理も予備的な準備として始まる前に、このステップが行われるべきである。ｉ−ラインがｊ−ラインと等しいと判明する場合、そのときｙｉはｙｊと等しいと演繹することができる。したがって、２本の等しい線のうちの１本は省略されるであろう。明瞭にするために、より大きな指標を有するラインは、常に省略される１つであろう。したがって、もしｊ＞ｉならば、ｊ−ラインは省略されるであろう。このステージ（それがｙｉと等しいので）で知られているｙｊがその適切な場所へベクトルｙに挿入される場合、この初期動作は、発明の実行の最終ステップで修正される。行列Ａの中に等しい２行のラインがなくなるまで、等しい線の省略は継続する。実際上、このステージは多くの場合スキップされる。等しい線の存在の可能性が合理的である場合は常に、それは実行される。ｌｏｇ２（ｒ）＞ｎの場合この条件が等しい線の存在を保証するので、それは常に実行される。
【００５１】
煩わしい表記法を回避するために、このスクリーニング過程に起因する修正された行列は、オリジナルの行列として同じ名前Ａを有し、次元ｒ×ｎの名前も保存されるであろう。次のステージで、合計プロセスは等しい列を除去するために導入される。この手続は、最小のコストの追加で、修正された行列中の列の数を削減するであろう。最初に、ベクトル積ｙ＝Ａ・ｘによる行列は、それぞれのｘ−コンポーネントを乗じたＡ列の合計に分解される。
従って、
【００５２】
【数１７】
2004511046.tif 000020
【００５３】
この合計の各要素は、ベクトルｘの対応するスカラ係数を乗じて、行列Ａの行ベクトルから成る。この合計は、ｙ＝Ａ・ｘ＝ｘ１ｖ１＋ｘ２ｖ２＋・・・・・＋ｘｎｖｎとして、より簡潔に記述される。
ここで（あらゆるｊに対して）ｖｊは、Ａのｊ列である。
【００５４】
【数１８】
2004511046.tif 000021
【００５５】
本発明の好適な実施例に従って、ゼロ列は、それらの係数と共にこのステージで省略される。次に、同一の非ゼロ列は一つにまとめられ、その対応するスカラ係数の合計を掛けて、別個の列がそれぞれ共通因子になるように、再整理される。従って、結果としての合計は、繰り返し列を省略することによって非ゼロ列の元のシーケンスから抽出された別個の非ゼロ列ｗ１，．．．．．．．．．．，ｗｍの全てのサブシーケンスからなる。各列ｗｊは、この列と等しいすべての列の対応するオリジナルの係数の合計である係数ｔｊによって乗じられる。ｍ≦ｎ、および、ギャップ、ｎ−ｍがオリジナルのシーケンスｖ１，ｖ２，．．．．．．．．．，ｖｎ中の反復回数であることは明らかである。次の数学的な記述は、上述したプロセスは次の数学的表現によって公式化することができる。
【００５６】
2004511046.tif 000022
さて、全ての１≦ｋ≦ｍに対して、定義する：
2004511046.tif 000023
計算上のタスクはここまで、オリジナルの係数ｘ１，．．．．．．．．．．，ｘｎの合計として新しい係数ｔ１，．．．．．．．．．．，ｔｍを算出することである。その代償はｎ−ｍの加算である。積ｙ＝Ａ・ｘは、次式から求められる。
【００５７】
2004511046.tif 000024
この演算の管理状況、求められた合計における参加体（ｐａｒｔｉｃｉｐａｎｔｓ）を決定することは、入力ベクトルの到着の前に予備的準備として行列毎に一度なされてもよい。要約すると、Ｂをその列がそれぞれｗ１，．．．．．．．．．．，ｗｍであるｒ×ｍ行列にしておき、そして次のようにする。
【００５８】
【数１９】
2004511046.tif 000025
【００５９】
その後ｙ＝Ａ・ｘ＝Ｂ・ｔとする。このように、上記プロセスは、ｒ×ｎ行列Ａにｎ−ベクトルｘを乗じるオリジナルの問題を、ｒ×ｍ行列Ｂにｍ−ベクトルｔを乗じる問題へ限定した。これによって可能にされる利益は、ｍがより小さいとき、より大きい。
【００６０】
次のステップは、前のステージの行列Ｂを２つ以上のサブ行列への水平分割である、ここでラインは壊されないままにされる。サブ行列はそれぞれ、削減された列の数を有し、それは、次の反復中で上記の列収集手続の利益を増大させるであろう。行列Ｂのラインは、ｕ１，ｕ２，．．．．．．．．．．，ｕｒによって表示される。考慮中の積は次のように表現される。
【００６１】
【数２０】
2004511046.tif 000026
【００６２】
ここで各ラインは、スカラ積の中でベクトルｔが乗じられる。この表現から、ｙ＝Ｂ・ｔを計算するタスクは、ｒスカラ積、すなわち ｕ１・ｔ，ｕ２・ｔ，．．．．．．．．．．，ｕｒ・ｔを計算する結合タスクと等価である。
【００６３】
本発明の好適な実施例によれば、これはベクトル積、すなわちＢ１・ｔおよびＢ２・ｔによって行列を計算することにより行われるである、ここで行列Ｂ１およびＢ２の各々は行列Ｂのラインの部分集合を含んでおり、これらの２つの部分集合が相互に解体し、それらの結合はＢ中のすべてのラインの部分集合を含む。通常、第１の反復を除いて、２つのサブ行列は同数あるいはほとんど同数のラインを有する。しかしながら、いくつかの特別な場合における行列Ａの特性に依存して、その分割は、２を越える行列になるであろう。そのようなことは、行列Ａが特別な内部順序（オーダー）を有しておらず、またそのエントリが任意に選ばれるように考慮される場合のケースである。その後、本発明の好適な実施例は、通常次の最初のラインの分割を暗示し、全ての分割したサブ行列をｌｏｇ２（列の数）＞行の数の状態へ持って来るであろう。その後、次の反復は、ラインを２つのほとんど等しい半分へ分割するであろう。行列が勝手気ままであると考えられる場合は、本質的に最悪のシナリオである。
【００６４】
代わりにあるいはその前に挿入されてもよい別のステップ、すなわち上記言及された水平分割が垂直分割である場合である。本発明の好適な実施例によれば、上記言及した合計、
2004511046.tif 000027
は、２つに分割される。すなわち、
2004511046.tif 000028
であり、ここでｐは１とｍ−１の間で選ばれる。このように、Ｂ１に対して、その行列の１組の列は、ｗ１，．．．．．．．．．．，ｗｐであり、またＢ２に対して、その行列の１組の列は、ｗｐ＋１，．．．．．．．．．．，ｗｍである。それは、
ｙ＝Ｂ１・ｔ’＋Ｂ２・ｔ”を保持する。
【００６５】
ここで、対応するベクトルは、ｔ’＝（ｔ１，．．．．．．．．．．，ｔｐ）、そしてｔ”＝（ｔｐ＋１，．．．．．．．．．．，ｔｍ）である。
従って、本発明のこの好適な実施例によって、２つのより低い次元の積、Ｂ１・ｔ’そしてＢ２・ｔ”は別々に計算され、結局、２つのｒ−ベクトルである結果は共に合計される。Ｂ列、ｗ１，．．．．．．．．．．，ｗｍの指標の予備的な再配置は、このステップの有効性を増強することができる。
【００６６】
垂直の分割は、他の手続きにおいてもそれほど頻繁に使用されない。その主な使用は、行の数が本質的に列の数を超過する場合にあり、ＤＳＰのアプリケーションにおいて、その状況はそれほど一般的でない。このステップの基本的な欠点は、上記水平分割にパラレル性を有しないｒスカラ加算の加算のセットから成る２つの積Ｂ１・ｔ’およびＢ２・ｔ”の結果を合計する必要性にある。上記水平分割の場合のように、行列Ａの特性に依存して、垂直分割は２を越える行列になるかもしれない。
【００６７】
最後に、上記ステップの各々は繰り返される反復に適用され、再帰的なメカニズムを形成する。
【００６８】
次に、境界は、上記方法によって可能にされる削減に提示される。ｒ×ｎ　０−１行列Ａに対し、ｓ＊（ｎ，ｒ）によって表示された最悪の場合の加算回数は、ｒ＜ｌｏｇ２（ｎ）において、次の表現によって与えられる。
【００６９】
2004511046.tif 000029
次表は、小さな数の行を備える行列に対する加算の数に境界を与える。
【００７０】
2004511046.tif 000030
最悪の場合に次の境界がある。
【００７１】
2004511046.tif 000031
ｕ（Ａ）が行列Ａの中の数１’ｎｓである場合、標準（先行技術）方法はｕ（Ａ）−ｒの加算を要求する。平均では（Ａが任意のとき、期待値によって）ｕ（Ａ）＝（ｎ−２）・ｒ／２である。ｒが一定（またはｒ≦ｃ・ｌｏｇ２（ｎ）ここで１＞ｃ＞０）であるとき、ｎが無限大になるにつれｓ＊（ｎ，ｒ）／ｎが１に接近するので、この方法は、漸近的に（有界であるｒおよび非有界のｎに対して）最適である。
【００７２】
Ａがｒ×ｎ　０−１行列で、行列Ａの次元ｒ×ｎに関する仮定はないとき、積Ａ・ｘを計算するのに本発明によって要求される加算の数は、１＞□＞０の場合、（１＋□）ｎ・ｒ／ｌｏｇ２（ｎ）によって制限され、ｒおよびｎの両方が無限大に近づくと、□は０に近づく。ｒ＞ｎの場合により厳しい境界が（この場合に関して）存在し、それは垂直分割のアプリケーションに起因する。
【００７３】
（１＋□）ｎ・ｒ／ｌｏｇ２（ｒ），ここで １＞□＞０そして、ｒおよびｎの双方が無限大に近づくと、□は０に近づく。
【００７４】
このプロセスの有効性を評価するために、本発明は、管理動作を増加させ、かつ加算を削減することが認められるべきである。しかしながら、加算は、複雑性の主要原因となり、また、本発明の実施による削減により支配的な効果を発揮する。さらに、データ・ベクトルの処理が始まる前に、ほとんどの管理動作は行列毎に一回行われる。このように、示唆された方法は、本質的に電力消費と回路を節約する。与えられた行列がある程度まばらであるとき、上記０−１−２進は、特に効率的な特徴を発揮する。このようなことは、この実施例を適用することにより、本発明の実数の行列の特徴で記述されるように、一般的な実数の行列をベクトルで乗算する計算において分散型の演算と結び付くとき、しばしば遭遇する。
【００７５】
さらに、発明のこの特徴は、代数のコードに適用可能で（参照：［Ｓｈｕ Ｌｉｎ， Ｄａｎｉｅｌ Ｊ． Ｃｏｓｔｅｌｌｏ， Ｊｒ． ”Ｅｒｒｏｒ ｃｏｎｔｒｏｌ ｃｏｄｉｎｇ Ｆｕｎｄａｍｅｎｔａｌｓ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ” Ｐｒｅｎｔｉｃｅ−Ｈａｌｌ， Ｉｎｃ．， Ｅｎｇｌｅｗｏｏｄ Ｃｌｉｆｆｓ， Ｎ．Ｊ．， １９８３］）、符号化および復号化のプロセスにおいて、Ｚ２行列はＺ２ベクトル（あるいはＺ２ｎベクトル）で乗じられる。これは、Ｚ２行列がＺ２ｎベクトルで乗じられるすべての状況で真実である。最後に、上記の０−１−２進の実施例および次のＵ−２進の実施例は、特性２のフィールドを除いてスカラのすべてのフィールドで容易に交換可能である。個々の特定の場合では、より効率的な実施例が選択されるであろう。
Ｕ行列
本発明の好適な実施例（以後、「Ｕ方法」と称する）であるＵ−２進の記述に必要な予備的な概念は、ベクトルと等価な概念である。１つが他方の積ならば、同じ次元である２つの非ゼロのベクトルが等価と称されるであろう。この実施例の内容において、それらが等しい場合またはそれらのうちの１つが他方の積（−１）である場合、２つのＵベクトルが等価であることに注意すべきである。次の好適な実施例は、詳細において上記のものとかなり類似している。次の文章で、消去（ｅｌｉｍｉｎａｔｉｏｎ）が等しいベクトルに対してよりむしろ等価な（行または列）ベクトルになされることが主要な相違点である。これは消去速度を促進し、したがって効率を増強する。この実施例は、例によって導入され、その概念の本質を実証する。
例：次の５×１３　Ｕ行列Ａと１３次元の入力ベクトルｘとの積を考慮する。行列は以下のとおり与えられる。
【００７６】
【数２１】
2004511046.tif 000032
【００７７】
入力ベクトルは次のとおり与えられる。
【００７８】
【数２２】
2004511046.tif 000033
【００７９】
積の結果は次式のように記述される。
【００８０】
【数２３】
2004511046.tif 000034
【００８１】
そのプロセスにおける第１歩は、等価なラインをチェックすることである。実際上、それは、入力ベクトルの到着の前に行われる一回の動作である。スキャンは、与えられた行列中の等価なラインの１つの発生を発見することで、ライン２はライン４に等価であり、事実、ライン４はライン２に（−１）を乗じたものに等しい。それは結果としてｙ４＝−ｙ２となる。したがって、ｙ４とｙ２の両方を計算する必要はなく、ｙ４の演算は省略されるであろう。このように、ライン４は行列Ａから削除される。その結果としての行列Ａ’は、次式で与えられる。
【００８２】
【数２４】
2004511046.tif 000035
【００８３】
対応する出力ベクトルは、次式で与えられる。
【００８４】
【数２５】
2004511046.tif 000036
【００８５】
それは、ｙ’＝Ａ’・ｘであることを保持する。
【００８６】
これは最初の削減である。次のステップにおいて、積Ａ’・ｘは、それぞれのｘ−コンポーネントを乗じたＡ’列の合計に分解される。したがって、次のようになる。
【００８７】
【数２６】
2004511046.tif 000037
【００８８】
次に、上記合計中の列ベクトルの各々に対し正規化が実行され、各修正済のベクトルの上部コンポーネントが１となる。このように、ベクトルの上部コンポーネントが（−１）である場合、ベクトルおよびその係数は両方とも（−１）が乗じられる。しかしながら、ベクトルの上部コンポーネントが１である場合、修正は行われない。上記合計の正規化形が次のように導き出される。
【００８９】
【数２７】
2004511046.tif 000038
【００９０】
この正規化された合計では、各ベクトルの上部コンポーネントは１であり、また、異なるベクトル数が削減される。次のステップは、同じ列の係数を集めて合計することである。したがって、８つの加算の実行で、次の方程式が得られる。
【００９１】
【数２８】
2004511046.tif 000039
【００９２】
さて、新しい係数が定義される。
【００９３】
2004511046.tif 000040
従って、上記の方程式は次の形式で書くことができる。
【００９４】
【数２９】
2004511046.tif 000041
【００９５】
係数、ｗ１，ｗ２，ｗ３，ｗ４，ｗ５はこのステージでプロセッサには知られている。次のステージで、このベクトル方程式は、次の２つの方程式のセットに水平に分割されるであろう。
【００９６】
【数３０】
2004511046.tif 000042
【００９７】
さて、これらの方程式の各々は、第１の反復の同じ方法で別々に処理される。それが前の方程式の正規状態を継承したので、上部の方程式は正規化を要求せず、正規化は第２の方程式にのみ必要である。従って、生起する結果としてのセットは次のとおりである。
【００９８】
【数３１】
2004511046.tif 000043
【００９９】
次のステップで、同じベクトルの係数は集められ合計される。したがって、さらに６つの加算で、その結果は次のとおりである。
【０１００】
【数３２】
2004511046.tif 000044
【０１０１】
明らかに、ベクトルｙ’はさらに４つの加算で済むことがわかる。オリジナルの出力ベクトルｙを得るために、ｙ４＝−ｙ２を思い起こすことが単に必要なだけである。このように、１８回の加算の合計が、このプロセスに必要とされた。従来の先行技術方法が出力ベクトルを計算するために６０回の加算の合計を要求することに認識すべきである。
【０１０２】
本発明のＵ−２進の好適な実施例は、ｒ×ｍのＵ行列Ａとｎ次元の入力ベクトルｘとの積を求めるための効率的な方法である。それは通常０−１の好適な実施例より多くの利益を提供し、より多くのアプリケーションを有する。
【０１０３】
行列Ａは次式で与えられる。
【０１０４】
【数３３】
2004511046.tif 000045
【０１０５】
そして、入力ベクトルは次式のように書かれている。
【０１０６】
【数３４】
2004511046.tif 000046
【０１０７】
入力ベクトルのエントリ値は実数または複素数、あるいは２より大きな特性を備えるスカラ領域に属するものであってもよい。目標は、次の積の結果を計算することである。
【０１０８】
2004511046.tif 000047
最初のステップは、等価ラインの消去によって与えられた行列を修正することで、そのステップは予備的な準備の一部である。ｉラインがｊラインと等価であると分かると、そのときｙ１は±ｙｊと等しいと推論することができる。したがって、本発明の最初のステップにおける好適な実施例は、２つの等価なラインのうちの１つを省略することを決めることである。明瞭にするために、方針としては、より大きな指標を有するラインを常に省略すべき１つとすることである。このように、それがｊ＞ｉと推定される場合、、そのとき、ｊラインが省略されるであろう。このステージで知られているｙｊがベクトルｙのその場所へ戻される場合、この最初の動作はプロセスの最終ステップで逆にされる。この消去プロセスは、修正済の行列に等価である２行のラインがなくなるまで、継続する。
【０１０９】
等価なラインが実際に存在する可能性がある場合は常に、このステージが実行される。これは、多くの場合Ｕ方法による複数の積の（本発明の別の側面）アプリケーションでの場合である。ｌｏｇ２（ｒ）≧ｎの場合、この条件は等価ラインの存在を保証するので、このステージは常に行なわれる。しかしながら、等価ラインの存在を保証し、かつ検討すべきである他の条件がある。例えば、これは、アダマール行列のサブ行列中にある場合である。不体裁な表記法を回避するために、結果としての修正済の行列は、オリジナルの行列と同じ名前Ａを有し、次元ｒ×ｎの名前もまた保存されるであろう。
【０１１０】
次のステップは等価な列の消去である。これは、加算による最小の犠牲で修正済の行列における水平の次元（つまり列の数）を減少させるであろう。０−１の場合のように、このステップと関係する全ての管理は、データ・ベクトルの到着に先立って予備的な準備として通常各行列当たり１回行われる。最初に、積ｙ＝Ａ・ｘは、対応するｘコンポーネントを乗じたＡ列の合計として表現される。
【０１１１】
【数３５】
2004511046.tif 000048
【０１１２】
次に、それがまだ＋１でない場合、行列Ａにおける各列ベクトルの上部の要素が検査され、＋１値に正規化される。従って、ａ１ｊ＝＋１の場合、そのとき正規化は必要ではないが、しかしａ１ｊ＝−１ならば、そのとき正規化が行われ、その対応するｊ列のベクトルは、その対応する係数ｘｊと同様に、−１が乗じられる。上記の合計の新しい表現が得られるが、ここで各ベクトルの上部のエントリは＋１に等しくなる。この表現では、等価な列は常に等しい。
【０１１３】
その後、上記の０−１の実施例でのように、同一の列は一つにまとめられ、各列をその対応するスカラ係数の合計として乗じられる共通因子により再整理される。これによって、結果としての合計は、反復する正規化された列をふるいにかけることにより、正規化された列ベクトルのシーケンスから抽出され、個別に正規化された全ての列ベクトルｗ１，．．．．．．．．．．，ｗｍ（反復をせずに）のシーケンスからなる。別個の正規化された列ｗｊそれぞれは、係数ｔｊが乗じられ、その係数はこの列と等しいすべての正規化された列の対応する正規化された係数の合計である。ｍ≦ｎで、その差ｎ−ｍは、正規化された列のオリジナルのシーケンスにおける反復数である、すなわち、ａ１１ｖ１，ａ１２ｖ２，．．．．．．．．．．，ａ１ｎｖｎ。
【０１１４】
数学上、そのプロセスは次のとおりである。
【０１１５】
2004511046.tif 000049
全ての１≦ｋ≦ｍに対して、定義する：
2004511046.tif 000050
本発明のこの部分に含まれる主要な計算タスクは、正規化されたオリジナルの係数の合計として新しい係数ｔ１，．．．．．．．．．．，ｔｍを計算することである。加算による負担はｎ−ｍである。積Ａ・ｘは、次式で与えられる。
【０１１６】
2004511046.tif 000051
列消去プロセスによる利点は、オリジナルの行列Ａの構造に依存する。それは、アダマールまたは周期的なＰＮ行列のサブ行列のようなある種の無線通信において、信号ベクトルの符号化および復号化で一般に使用されるいくつかの行列で重要である。さらに、行列Ａ中のライン数であるｒが行ｎの数に比べて小さいとき、それは重要である。特に、ｒ≦ｌｏｇ（ｎ）、のとき、そのような場合、ｍ−ｎ≧ｎ−２ｒ−１＞０である。これらの考察は、０−１行列においてもかなり正しい。
【０１１７】
本発明のこの好適な実施例の残りの部分、水平および垂直の分割、反復は、その０−１の対応物と等価である。
【０１１８】
本発明の使用によって可能にされる節約を考察すると、その加算が複雑性の主要部分であることがまず分かる。ｒ≦ｌｏｇ２（ｎ）でｒ×ｎ　Ｕ行列Ａに対し、ｓ（ｎ，ｒ）によって表わされる最悪の場合における加算数は、次式で与えられる。
【０１１９】
2004511046.tif 000052
ここで：
2004511046.tif 000053
次の境界が常に有効である。
【０１２０】
2004511046.tif 000054
先行技術の従来方法は、（ｎ−１）・ｒ回の加算を要求する。ｎが無限大に行き、ｒが一定のとき、ｓ（ｎ，ｒ）／ｎは１に接近するので、この方法は漸近的に最適である。後で記述される本発明のより複雑な多重積による実施例は、加算の最悪の場合における加算数に正確な境界を要求する。これは次の回帰方程式によって可能になる。
【０１２１】
偶数のｒに対して：
2004511046.tif 000055
奇数のｒに対して：
2004511046.tif 000056
Ａがｒ×ｎ　Ｕ行列で、行列Ａの次元ｒ×ｎに対する制限はないとき、本発明によって求められる積Ａ・ｘを計算するのに必要な加算数は、常に次式によって制限される、すなわち（１＋□）ｎ・ｒ／ｌｏｇ２（ｎ）、ここで１＞□＞０、および、ｒおよびｎの両方が無限大に近づくと、□は０に近づく。ｒ＞ｎの場合には、よりきつい境界（この場合に関しての）が存在し、それは垂直の分割を適用することに起因する、すなわち、
（１＋□）ｎ・ｒ／ｌｏｇ２（ｒ）、ここで１＞□＞０、
および、ｒおよびｎの両方が無限大に近づくと、□が０に近づく。
【０１２２】
しかしながら、行列Ａに特定のタイプの構造がある場合、積Ａ・ｘを計算するために本発明の好適な実施例によって要求される加算の回数は、劇的に減少するであろう。その最も一般的な条件は本テキストの範囲外であるが、しかし、Ａがｎ×ｎアダマールまたは周期的な擬似ランダム（ＰＮ）行列である場合、いくつかの例が言及されるであろう。しかしながら、単にｎ・ｌｏｇ２（ｎ）、加算およびｎスカラのメモリが要求され、それはこの点で最適である。この見解はさらに０−１行列に適用できる。
産業上の応用例
上述された本発明の好適な実施例を実施することから利益を得るいくつかの技術がある。そのような技術の１つは、画像処理であり、それはＵ行列をベクトルで乗じた積を含むいくつかの手順を達成する。無線通信のＣＤＭＡ、ＩＳ−９５、またより発展した第３世代の広帯域ＣＤＭＡにおいて、Ｕ行列をベクトル乗じた積を使用するいくつかのプロセスがある。これらのプロセスは本発明の使用によって、よりエネルギ使用量、回路類およびさらに実行時間の削減をもたらすであろう。
【０１２３】
ＩＳ−９５−Ｂのマルチコード化の内容で、アダマール−６４からの８行のラインは、そのエントリが信号のサンプルであるベクトルによって乗じられるＵ行列を含む。別の応用は、デスプレッダ（ｄｅｓｐｒｅａｄｅｒ）によって成される隣接検出にある。データ・ベクトルによってわずかのアダマール・ラインからできている行列の積がある。別の応用は検索である。それは相互のスカラ積の演算によって高い相関をもつシーケンスを探索する。相関器のシーケンスは、Ｕシーケンスである擬似ランダム（ＰＮ）シーケンスから抽出され、データ・ベクトルによるそれらのスカラ積が要求された演算となる。最初の調査は、検索者の１つの段階である。
一般化された消去法
本発明の上記２進法の特徴は、下記プロセスの反復によって特徴づけられる、すなわち、ゼロ・ラインおよび等価ライン（一つが他方のスカラ積であることを意味する）が省略され、ゼロ列がそれらに関連した入力ベクトルのスカラ・コンポーネントと共に省略され、等価列は一まとめにされて合計され、また、これらの２つの特徴が使い尽くされた後にその行列は水平にまたは垂直に分割される。本発明の好適な実施例によれば、このステップの反復シーケンスは、スカラのあらゆる分野に行列とベクトルの積に適用できる。本発明のこのより広い好適な実施例は、一般化された消去法（ＧＥＭ：ｇｅｎｅｒａｌｉｚｅｄ−ｅｌｉｍｉｎａｔｉｏｎ ｍｅｔｈｏｄ）と称される。
【０１２４】
等価列の合計は、基本的に下記プロセスの反復である。ｖ１，ｖ２，．．．．．．．．．．，ｖｎを変換行列Ａの列にし、ｘ＝（ｘ１，ｘ２，．．．．．．．．．．，ｘｎ）を入力ベクトルとすると、ゴールはＡ・ｘを計算することである。列ｖｋ＋１，．．．．．．．．．．，ｖｎ（２≦ｋ＜ｎに対して）の各々が、ｋ−列のスカラ積、すなわちｋ＜ｊ≦ｎに対してｖｊ＝ｚｊｖｋであることを、指標の適切な再配置の後に保持すると仮定する。その後、ｎ次元のベクトルｘは減少したｋ次元のベクトルと置き換えられる。すなわち、
ｘ’（ｘ１，ｘ２，．．．．．．．．．．，ｘｋ−１，ｘ’ｋ）ここで、
ｘ’ｋ＝ｘｋ＋ｘｋ＋１・ｚｋ＋１＋，．．．．．．．．．．，＋ｘｎ・ｚｎ
そして、ｒ×ｎ行列は、その列がｖ１，ｖ２，．．．．．．．．．．，ｖｋである減少したｒ×ｋ行列Ａ’と置き換えられる。その後、Ａ’・ｘ’＝Ａ・ｘを保持する。本発明の好適な実施例に従って、必要ならば指標の変更を含むこのプロセスは、２つの列が等価でなくなるまで、繰り返される。確かに、このプロセスは、単に本発明におけるＵ行列の実施例で行われる正規化プロセスの一般化である。実際上、上記の等価な列の削減のすべては、同時に行われてもよい。このステージが終わると、それは全工程の最初の反復と考えられるであろう。その後、行列は、水平に分割され、各分割において上記列の削減が上記実施例中で行われたように、再帰的な方法で繰り返す。
【０１２５】
Ｕ実施例により、また次の例によって示されるように、等価な列を除去する効率的な方法は、最初に最上部のコンポーネントで各列を分割し、続いて対応する係数に同じ最上部のコンポーネントを乗ずることである。それは各修正された列の最上部のコンポーネントに１を有する結果になる。しかしながら、時々、ＧＥＭを適用する際に、変換行列中の列における最上部のコンポーネントが、この分割を不可能にする０となることがある。このような場合、簡単な解決法は、その最上部の０でないコンポーネントで各非ゼロの列を分割し、それにより、対応する係数に同じ最上部の非ゼロのコンポーネントを掛けることである．その結果、各修正済の列における最上部の非ゼロのコンポーネントに１が存在することになる。２つの列が、等しい場合および等しい場合にのみ、修正済の行列中で等価であるという望ましい結果をもたらすことになる。
【０１２６】
本発明のこの好適な実施例がその効率を増進する場合を示唆するためには、比較的小さな有限集合Ｓ中にそのエントリを有する行列を考慮することである。実際上、このセットＳは、有限集合体、集合体の乗算グループにおける有限のサブグループまたは乗算の下で閉じた集合体の有限部分集合、およびより大きな普遍性の中で、集合体の任意の有限部分集合であってよい。それは、既に議論された２進法のケースを含み、ここでＳ＝｛０，１｝、またはＳ＝｛１，−１｝および他の非常に共通した状況、ここでＳ＝｛０，１，−１｝またはＳ＝｛１，−１，ｊ，−ｊ｝またはＳ＝｛０，１，−１，ｊ，−ｊ｝である。利得はＳのサイズで減少し、その一般的な規則は、ＧＥＭがｌｏｇ｜ｓ｜（ｎ）の要因だけ加算の数を減少することを維持する、ここでｎは与えられた変換行列中の列の数である。適用可能な場合、ＧＥＭは、効率のために、後で記述されるであろう複雑で一般的な実施例と比較される。
【０１２７】
この方法が動作する方法を示すために、エントリが集合体からくる行列を示す、すなわちＵ１＝ｄｅｆ＝｛１，−１，ｊ，−ｊ｝はＵ１行列と呼ばれる。このようなタイプの行列は、しばしば実際上現われる。しかしながら、ＧＥＭがあらゆる特定のタイプの行列に制限されないことが再度強調されなければならない。加算の数は、ベクトルによるｒ×ｎ　Ｕ１行列の積のために、Ｃ＝ｎ＋４ｒ−１＋ｏ（４ｒ−１）によって制限される。
【０１２８】
例：次の３×１５　Ｕ１行列Ａを１５次元の複素入力ベクトルｘで乗じた積を検討する。行列は次式で与えられる。
【０１２９】
【数３６】
2004511046.tif 000057
【０１３０】
そして、入力ベクトルは次に与えられる。
【０１３１】
【数３７】
2004511046.tif 000058
【０１３２】
積の結果は次式で書かれる。
【０１３３】
【数３８】
2004511046.tif 000059
【０１３４】
この例において行われる加算は、すべて複素加算である。最初のステップは、等価ラインに対するチェックである。等価なラインは見つからない。次のステップで、積Ａ・ｘは、それぞれのｘコンポーネントを乗じたＡ列の合計に分解される。
【０１３５】
【数３９】
2004511046.tif 000060
【０１３６】
次に、上記合計中の各列ベクトルに正規化が行われる。それは、各ベクトルにその上部コンポーネントの逆数を掛けることにより行われる、したがって各係数に対応するベクトルの（同じ）上部コンポーネントを掛けることにより行われる。その結果、各修正済のベクトルの上部コンポーネントは１となる。ベクトルの上部コンポーネントが既に１である場合、修正は必要ではない。上記合計の正規化フォームが次に導き出される。
【０１３７】
【数４０】
2004511046.tif 000061
【０１３８】
この正規化された合計では、各ベクトルの上部コンポーネントは１であり、また、列ｎの数が、行ｒの数（要求：ｎ＞４ｒ−１）に比べて十分に大きいとき（一般的なセッティングで）、異なるベクトルの数は実質的に削減される。次のステップは、同じ列の係数を集めて合計することである。したがって、７回の加算を負担することで、次の削減が得られる。
【０１３９】
【数４１】
2004511046.tif 000062
【０１４０】
さて、新しい係数が定義される。
【０１４１】
2004511046.tif 000063
従って、上記の方程式は次の形式で書くことができる。
【０１４２】
【数４２】
2004511046.tif 000064
【０１４３】
係数：ｗ１，．．．．．．．．．．，ｗ８は、このステージでプロセッサに知られている。
【０１４４】
次に、このベクトル方程式は水平に分割され、２つの方程式からなる次の等価な組になる。
【０１４５】
【数４３】
2004511046.tif 000065
【０１４６】
一般に、両方はベクトルの方程式である。しかしながら、小規模な本例において、第２の方程式はスカラ方程式に退化している。さて規則に従えば、これらの方程式の各々は、最初の反復と同じ方法で別々に処理されるであろう。上の方程式は前の方程式の基底状態を継承したので、上の方程式は正規化を要求せず、それ故、いかなる非退化の応用においても、正規化は第２の垂直の方程式にのみ必要となる。従って、上のベクトル方程式に対して生じる減少は次のとおりである。
【０１４７】
【数４４】
2004511046.tif 000066
【０１４８】
このステップに対し、さらに４回の加算が必要になる。その演算は、両方の方程式に対しさらに１３回の加算を行って、直接の方法で実行される。その結果、この例で本発明の好適な実施例は、合計２４回の加算が使用される。力任せの演算では、４２回の加算を要求していたであろう。より大きな規模では、その節約はより本質的なものとなる。
トップリッツ行列
本発明のこの好適な実施例を紹介するために、例が提示される。
【０１４９】
例：長さ８のシーケンスが与えられると仮定する、すなわち、Ｕ＝（１，１，−１，−１，１，−１，１，−１）およびそれはデータ・ベクトルｘ＝（ｘ１，ｘ２，．．．．．．．．．．，ｘ１０）の３つの連続する仮説をチェックすることが望まれる。その目的は最大の相関の検索である。次の３つの合計を計算するこことが必要である。
【０１５０】
2004511046.tif 000067
これは、次のトップリッツ行列の積によって表わされる。
【０１５１】
【数４５】
2004511046.tif 000068
【０１５２】
次のステップは、次式のように相補するベクトルを集めることである。
【０１５３】
【数４６】
2004511046.tif 000069
【０１５４】
この段階で、各ブラケット内部の項を検討し、かつ補助定理を利用し、ｘ，ｙがスカラで、ｖ，ｕがベクトルである場合、その場合、
ｘｖ＋ｙｕ＝（１／２）（ｘ＋ｙ）（ｖ＋ｕ）＋（１／２）（ｘ−ｙ）（ｖ−ｕ）から、従って、次式となる。
【０１５５】
【数４７】
2004511046.tif 000070
【０１５６】
同様に、
【０１５７】
【数４８】
2004511046.tif 000071
【０１５８】
従って、４つの加算の負担で、結果は次のとおりである。
【０１５９】
【数４９】
2004511046.tif 000072
【０１６０】
しかし、今、上記Ｕ２進法が適用される。すなわち、次のステップは、各列の上部コンポーネントが１に等しくなるようにする正規化である。
【０１６１】
【数５０】
2004511046.tif 000073
【０１６２】
次のステップは、共通の列の係数を集めて合計することである。すなわち、６つの追加の加算による負担で、次の等式となる。
【０１６３】
【数５１】
2004511046.tif 000074
【０１６４】
したがって、便宜上次のように定義すれば、
2004511046.tif 000075
そのとき、その等式は次のように書かれる。
【０１６５】
【数５２】
2004511046.tif 000076
【０１６６】
次のステージでは、このベクトル方程式は、次の２つの方程式に水平に分割される。
【０１６７】
【数５３】
2004511046.tif 000077
【０１６８】
最初の方程式中の同一の列を集めると、さらに２回の加算で次式が得られる。
【０１６９】
【数５４】
2004511046.tif 000078
【０１７０】
さて、所望の出力ベクトルｙは、５回の追加の加算ですむことが分かる。したがって、本発明を具体化する方法は、この演算を行なうために１７回の加算を要求する。力任せの方法では、２１回の加算を要求するであろう。この小規模の例によって得られた利点は、あまり大きなものではない、しかし、大規模な応用において、その利得は上記「正方形」（非トップリッツ）Ｕ方法の利得に匹敵することを理解できるであろう。
【０１７１】
次に、本発明の特徴における一般的な構成を記述する。Ｕシーケンス、
2004511046.tif 000079
および、実数か複素数のスカラのデータのシーケンス、
2004511046.tif 000080
が与えられると仮定する。
【０１７２】
データ・シーケンスの要素は、実数か複素数または、２より大きな特性のスカラの任意の集合体に属していてもよい。次の合計を計算することが所望されると仮定する。
【０１７３】
2004511046.tif 000081
ｍ＜ｌｏｇ２（ｎ）ならば、ｒ＝ｍにする一方、ｍ≧ｌｏｇ２（ｎ）ならば、本発明の好適な実施例は、ｍ合計のセットをｒの連続する合計のブロックへ分割することにより開始し、ここでｒ＜ｌｏｇ２（ｎ）である。その方法が第１のブロック上で示されてもよいように、すべてのブロックは同一の方法で扱われる。トップリッツ行列とベクトルの積は、最初のｒ合計を表わす。そのとき、ｒ×（ｎ＋ｒ−１）トップリッツ行列は、
【０１７４】
【数５５】
2004511046.tif 000082
【０１７５】
そして、その（ｎ＋ｒ−１）次元のベクトルは、
【０１７６】
【数５６】
2004511046.tif 000083
【０１７７】
それから、最初のｒ合計は、ベクトルから与えられ、
【０１７８】
【数５７】
2004511046.tif 000084
【０１７９】
となる。ここで、ｙ＝Ａ・ｘである。
【０１８０】
本発明の好適な実施例について、その強調する概念は、上記Ｕ方法が適用可能になるように、与えられた問題を再編成することである。それらの順序に従って、ｖ１，ｖ２，．．．．．．．．．．，ｖｎ＋ｒ−１を行列Ａの列にする。次の全ての「中間」列ベクトルがＵベクトルであると考える。
【０１８１】
【数５８】
2004511046.tif 000085
【０１８２】
さらに「サイド」列ベクトルの「マッチング」ペアにおける次の合計および減算が、Ｕベクトルであることに注意すること。
【０１８３】
【数５９】
2004511046.tif 000086
【０１８４】
必要な予備的な準備を行った後に、その方法が導入される。上記に従って、再構成する。
【０１８５】
2004511046.tif 000087
次に、その発明は、ｘ，ｙがスカラであり、ｖ，ｕがベクトルであるという規則を使用する。
【０１８６】
2004511046.tif 000088
したがって、
2004511046.tif 000089
このプロセスは２ｒ−２加算の負担であり、達成された形式は実際ｒ×（ｎ＋ｒ−１）Ｕ行列とｎ＋ｒ−１ベクトルの積である。これは、上記すべてのベクトル、
2004511046.tif 000090
がＵベクトルであるので、そのとおりである。したがって、演算の残りは、Ｕ方法によって行われてもよい。Ｕ形式へのこの修正のすべての局面は、実際の合計／減算を除く、すなわちｘｊ±ｘｎ＋ｊ，は入力ベクトルの到来に先立つ「一回のジョブ」として行われる。
【０１８７】
最悪の場合での加算数は、次の式から与えられる
2004511046.tif 000091
一般的な設定で、ｍは計算され、ｍ＞ｌｏｇ２（ｎ）で、最悪の場合での加算数は（１＋□）（ｎ＋３ｌｏｇ２（ｎ））・ｍ／ｌｏｇ２（ｎ）によって制限され、ここで１＞□＞０において、ｍおよびｎ両方が無限大に近づくと□は０に近づく。
【０１８８】
上記方法への本発明の別の好適な実施例によれば、ＧＥＭのコンポーネントは、統合されてもよい。そのような場合、いくつかの「サイド」列はサイド列を結合する最初のステージでは未処理加工のまま残る。
（０、１、−１）行列
トップリッツ行列は、より一般的なクラスの行列の一部である、すなわちそれらの行列のエントリは０、１または−１である。そのような行列は、ここでは（０，１，−１）行列と称する。上記トップリッツ方法と関係する概念のより広いバージョンが、ここで展開されるであろう。Ａが次元ｒ×ｎの（０，１，−１）行列で、ｘがｎ次元の入力ベクトルであり、積Ａ・ｘを計算することが所望されると仮定する。この積は、対応するｘコンポーネントを乗じたＡ列の合計として表現される。したがって、ｖｊ（すべてのｊに対して）がＡのｊ列であることを示すと、そのとき、次式が示される。
【０１８９】
2004511046.tif 000092
いくらか、あるいは恐らくＡのすべての列は０−エントリを含む。表記を簡単にするために、指標は非常によく整えられ（もちろん、方法的にプロセッサにタスクを課さずに）、最初のｋ列ｖ１，ｖ２，．．．．．．．．．．，ｖｋの各々は０のエントリを含みかつ残りのすべてのｎ−ｋ列（いずれにあっても） ｖｋ＋１，ｖｋ＋２，．．．．．．．．．．，ｖｎはＵベクトル（すなわち０のエントリのない）であると仮定される。
「混合」ベクトル、ｖ１，ｖ２，．．．．．．．．．．，ｖｋの各々は、平均２つのＵベクトルの平均である。すなわち、各１≦ｊ≦ｋに対して、２つのＵベクトルｕｊ，ｗｊ，がｖｊ，＝（１／２）（ｕｊ＋ｗｊ）のように存在する。本発明の好適な実施例は、ベクトルｕ１，ｗ１，．．．．．．．．．．，ｕｋ，ｗｋ，を行列毎に一度の準備として認識する。したがって上記のによって次式となる。
【０１９０】
2004511046.tif 000093
しかしながら、ブラケットを開くと、ｒ×（ｎ＋ｋ）Ｕ行列と（ｎ＋ｋ）ベクトルの積の表現を発見する。本発明の好適な実施例によれば、このタスクは、本発明の上記のＵ特徴によって行われるであろう。本発明の上記トップリッツ特徴はこのより広い特徴の特別な場合である。
産業上の応用の例
サーチャ（ｓｅａｒｃｈｅｒ）は、通常トップリッツ行列とデータ・ベクトルの積によって表わされる。これは、ＣＤＭＡおよび広帯域ＣＤＭＡの両方にみられる。
【０１９１】
実数行列
本発明の別の好適な実施例によれば、計算の動作回数は分散型の算術の使用によってあらゆる実数の線形変換に対して削減される。以下の説明において、それは「実数マトリクス法」と呼ばれる。線形変換は行列によって表現され、そのエントリは整数である必要はなく、２進数の定数である実数である。行列は、２進の係数を備えた２進の行列の合計に分解されるであろう。次のステージでは、本発明の２進の実施例が適用されるであろう。この方法を導入するためには、次の例を考慮すべきである。
例：次の３×８のＵ行列Ａを検討するが、整数のエントリを有し、（この例の単純化のために）１０進数で書かれる。
【０１９２】
【数６０】
2004511046.tif 000094
【０１９３】
入力が８次元のベクトルは、次のように与えられる。
【０１９４】
【数６１】
2004511046.tif 000095
【０１９５】
３次元の出力ベクトルを計算することが所望される。
【０１９６】
【数６２】
2004511046.tif 000096
【０１９７】
プロセッサは通常２進を基本に動作するので、行列Ａはこの基本により表わされ、したがって、次のように与えられる。
【０１９８】
【数６３】
2004511046.tif 000097
【０１９９】
この表現は、その行列を３つの２進・行列の合計として表現するために、分散型算術を使用する可能性を示唆する。ここで、次式が示される。
2004511046.tif 000098
【０２００】
【数６４】
2004511046.tif 000099
【０２０１】
本発明のこの実施例によって行われる最初のステップは、その特徴に従って、Ａにおけるエントリのビットからなる２進・行列Ａ［０］，Ａ［１］，Ａ［２］を構成することである。検討中の好適な実施例は、同一の結果になるであろう。
【０２０２】
2004511046.tif 000100
次のステップは、Ａ［０］，Ａ［１］，Ａ［２］を水平に結び付けることによって形成される２４×３の２進・行列Ａ＊を構成することである。
【０２０３】
【数６５】
2004511046.tif 000101
【０２０４】
そして、また上記の合計から推定された対応する２進の重み付けを各々有する３つのベクトルｘのレプリカから構成される２４次元の列ベクトルｘ＊を形成することである。これは、入力ベクトルの到着が始まる前に、なされる。
【０２０５】
【数６６】
2004511046.tif 000102
【０２０６】
２ｌで乗ずることは、単に指標のシフト動作だけですむことに注意すること。この実施例の鍵は、次式を主張することである。
【０２０７】
2004511046.tif 000103
したがって、次にすることは、０−１方法によるＡ＊・Ｘ＊の演算を行なうことである。すなわち、次の作業は、新しい係数を作成し、それによって、行列のサイズを削減して、共通の非ゼロ列の係数を集めて合計することである。すなわち、それは次式を維持する。
【０２０８】
【数６７】
2004511046.tif 000104
【０２０９】
ここで
2004511046.tif 000105
これは１６回の加算で行われる。次に、生起する行列の行分割が行われる。すなわち、
【０２１０】
【数６８】
2004511046.tif 000106
【０２１１】
であり、そして、
ｙ３＝ｗ１＋ｗ３＋ｗ５である。
【０２１２】
さて、第１の方程式中における共通の列の係数を合計すると、次式を導く。
【０２１３】
【数６９】
2004511046.tif 000107
【０２１４】
このステップは２つの加算を要する。残りはさらに２つの加算でなされる。この例における変換を計算するために、トータル２０回の加算動作が必要とされる。従来方式を使用すれば、２９回の加算に相当する動作を要求していたであろうが、ここで意味する「相当」とは、乗算動作を含む加算も考慮に入れる。
【０２１５】
明らかに、これは顕著な削減の例ではない。それは、本発明のこの実施例についての概念を容易な方法で紹介することである。しかしながら、行列（各エントリの次元および桁数）のパラメータが大きいとき、実質的な削減は本発明によって実現される。
【０２１６】
一般に、検討中の本発明の好適な実施例は、実数，無制限の線形変換の効率的な演算に関係する。変換を表現するｒ×ｍ行列Ａは、次式で書かれる。
【０２１７】
【数７０】
2004511046.tif 000108
【０２１８】
ここで、行列のエントリは実数である。Ａ・ｘを計算することが所望され、ここでｘは次のように表現される実数か複素数のスカラのエントリからなるｎ次元のベクトルである。
【０２１９】
【数７１】
2004511046.tif 000109
【０２２０】
行列Ａのエントリは、そのポイントの前後で、固定されたデジット数の２進数で書かれていると仮定する。本発明の２つの好適な実施例が、変換行列の構造に依存する中で、その最適な解決および選択として示される。最初は、０−１分解と呼ばれ、２番目はＵ分解と称される。
【０２２１】
行列Ａのエントリが２ｍ１によって制限され、適切な正の整数ｍ１およびｍ２のためのポイントを越えるｍ２デジットの精度を有すると仮定する。プロセッサが遭遇したすべてのスカラはそのポイントの前後に有限なデジット数を有するので、この仮定は本発明の範囲を制限するものではない。ｍ＝ｍ１＋ｍ２＋１とする。分散演算は、積Ａ・ｘを上記の例によって扱われたタイプのｍ２進積の合計へ分解するために適用される。
【０２２２】
最初に、その発明は、行列のエントリが負ではなく、またその分解が０−１−ベースである場合に記述される。２ｍ１によって境界がなされ、そのポイントを越えるｍ２デジットを有する実数ｔは、次の方法で表わされる。
【０２２３】
2004511046.tif 000110
ここで、ｔｋはそれぞれ０または１である。これは標準の２進数の表現である。典型的な分散演算の議論によって、Ａは、次の方法でｍの合計　ｒ×ｎの０−１−２進・行列に分解することができる。
【０２２４】
2004511046.tif 000111
この合計では、Ａ［ｍ１］は最上位ビット（ＭＳＢ）の０−１行列であり、Ａ［−ｍ２］は最下位ビット（ＬＳＢ）の０−１行列である。一般に、行列Ａ［ｋ］の各々は０−１行列であり、そのエントリはＡにおけるエントリのｋ番目のビットで構成される、ここで各ビットはその対応するエントリに置かれる。分配規則によって、次のとおりとなる。
【０２２５】
2004511046.tif 000112
これは本発明の現在の実施例に対する基礎となる。
【０２２６】
次に、Ａ＊は、それらが合計に現われる上記合計の２進・行列の水平上のラインによって順番に構成されたｒ×（ｍ・ｎ）の０−１行列であるとする。そのとき、次式となる。
【０２２７】
2004511046.tif 000113
入力ベクトルの到着が始まる前に、これは所定の行列のために１回行われるであるであろう。
【０２２８】
さらに、ｍ・ｎ次元の列ベクトルｘ＊が次式のように与えられる。
【０２２９】
【数７２】
2004511046.tif 000114
【０２３０】
検討中の実施例を強調する重要な点は次のことである。
【０２３１】
2004511046.tif 000115
後者は、ｒ×（ｍ・ｎ）の０−１行列を、元のベクトルのシフトしたｍ個のレプリカから構成される（ｍ＋１）・ｎ次元のベクトルで乗じた積である。
積Ａ＊・ｘ＊の演算は、本発明の０−１−２進の実施例でなされる。２の整数累乗による乗算がそれぞれビットをシフトすることにより実行されるので、ほとんど、追加の複雑性は加わらない。
【０２３２】
本発明のこの実施例は、積の複雑性を著しく減少させることができる。
【０２３３】
2004511046.tif 000116
であるから、Ｃ（Ａ）は本発明によってＡ＊・ｘ＊を計算するのに必要な加算の数である。
【０２３４】
もし、ｌ≧ｒ ならば、そのとき
2004511046.tif 000117
特に、この場合その境界は次のとおりとなる。
【０２３５】
2004511046.tif 000118
ｌ≧ｒの仮定をはずすと、それは次のようになる。
【０２３６】
2004511046.tif 000119
ここで１＞□＞０、およびｍ・ｎおよびｒが無限大に行くにつれ、□は０へ接近する。
【０２３７】
積動作を含む加算が考慮に入れられる場合、積Ａ・ｘを計算する従来の（力まかせによる）先行技術の方法は、平均して、ｎ・ｒ・ｍ／２回の加算に相当する回数を要求する。
【０２３８】
いくつかの場合、特に、ｒ＝１あるいはｒがやや小さいとき、上述した実施例とは別のやり方が所望され、それはさらなる削減を可能にする。ケースｒ＝１では、問題は２つのベクトル間におけるスカラ積の問題に形をかえることに注意すること。これはそれ自体、科学技術にやや共通した演算であり、また、その効率的な実行は多くの場合役に立つ。この変形によれば、行列Ａ＊＊は、行列Ａ［−ｍ２］，Ａ［−ｍ２］，．．．．．．．．．．，Ａ［０］，．．．．．．．．．．，Ａ［ｍ１］を垂直のシーケンスにつなぐことにより形成される。したがって、それは、２進乗算のためのシフトを用いることで、所望の結果が次に合計を実行することにより得られる。次のものから与えられたｒ・（ｍ＋１）×ｎの０−１行列である。
【０２３９】
【数７３】
2004511046.tif 000120
【０２４０】
次に、Ａ＊＊・ｘの演算は０−１−行列のために本発明の好適な実施例によって行われる。積Ａ＊＊・ｘは積をすべて含んでいる。
【０２４１】
2004511046.tif 000121
従って、シフトを２進乗算のために使用することで、所要の結果はその合計を行なうことにより達成される。
【０２４２】
2004511046.tif 000122
これは、負でないエントリで行列の一部を終了する。
【０２４３】
行列Ａが両符号のエントリを有する実数のとき、行列Ａは負でないエントリを備えた２つの行列の減算として表現することができる、すなわちＡ＝Ａ１−Ａ２である。この表現に続いて、議論中の本発明の特徴は、まず積ｙ１＝Ａ１・ｘおよびｙ２＝Ａ２・ｘの各々を上記方法により別々にまたは結合した形式で計算することによりｙ＝Ａ・ｘの計算を行なう。その後、最終ステップである減算、すなわちｙ＝ｙ１−ｙ２を実行する。
【０２４４】
実数行列に関しての本発明の好適な実施例における上記０−１−２進オプションは、２進・行列を分解するとき、すなわち、Ａ［−ｍ２］，Ａ［−ｍ２＋１］，．．．．．．．．．．，Ａ［０］，．．．．．．．．．．，Ａ［ｍ１］がややばらばらであるとき、特に効率的である。これは、Ａのエントリが様々なサイズをもちポイントを越えて非同一の２進デジット数を有している結果である。そのような場合、上記言及した一定のデジタル形式に対し必要な０を挿入することにより、より高いレベルのまばらを引き起こす。
【０２４５】
Ｕ−２進の分散演算に基づいて、本発明の好適な実施例の別の形式が次に記述される。本発明のこの形式は、両方の符号のエントリを有しおよびより高速のＵ方法に基づく行列により適応した利点を有する。実際、行列のエントリのサイズにある統一性と精度があるとき、上記の０−１バージョンはより効率的である。下記方法の主な特徴は、０−１方法に類似する。
【０２４６】
次の検討は、本発明の説明を進めるために必要である。２ｍ１によって境界付けされ、そのポイントを越えるｍ２個のデジットを有する実数ｔは、次の方法でＵ２進合計として表わすことができる。
【０２４７】
2004511046.tif 000123
ここで、−ｍ２−１≦ｋ≦ｍ１−１に対する全てのｓｋは、±１であり、そしてｔが負でないとき、ｓｍ１＝１であり、ｔが負のとき、ｓｍ１＝−１である。したがって、両方の符号のエントリを備えたｒ×ｎの実数の行列Ａは、次の方法でＵ行列の合計に分解することができる。
【０２４８】
2004511046.tif 000124
ここで行列Ａ［ｋ］の各々はｒ×ｎのＵ行列である。
【０２４９】
Ａ＊がｒ×（（ｍ＋１）・ｎ）のＵ行列であるとする。
【０２５０】
2004511046.tif 000125
この行列は、入力してくるデータ・ベクトルの到着前に、各行列について１度のタスクとして構成される。さらに、（ｍ＋１）・ｎ次元の列ベクトルｘ＊は次のように定義される。
【０２５１】
【数７４】
2004511046.tif 000126
【０２５２】
それは、Ａ・ｘ＝Ａ＊・ｘ＊を保持する。これは、ｒ×（（ｍ＋１）・ｎ）のＵ行列を（ｍ＋１）・ｎ次元のベクトルで乗じた積である。この積の演算は、本発明のＵ行列実施例の応用よって行われる。
【０２５３】
０−１−２進分解に関係する上記の方法でのように、さらにここに、ｒ＝ｌまたは小さなｒのための垂直バージョンがある。それは上記記述したものと完全に類似しており、詳細を繰り返す理由はない。
【０２５４】
ｌ＝ｌｏｇ（（ｍ＋１）・ｎ）＝ｌｏｇ（ｍ＋１）＋ｌｏｇ（ｎ）とする。それはｌ≧ｒに対し、上記の方法を行なうのに必要な加算の数は、
2004511046.tif 000127
によって制限される。
【０２５５】
上記の説明のように、Ｃ（Ａ）は上記Ｕ実施例によってＡ・ｘを計算するために必要な加算の数であると定義される。より広い一般法則では、それは次のようになる。
【０２５６】
2004511046.tif 000128
ここで、１＞□＞０、（ｍ＋１）・ｎおよびｒが無限大に近づくにつれ、□は０に近づく。
産業上の応用例
線形変換は、あらゆる分野の技術と科学に共通して使用される。本発明の実数行列の面を通信技術に応用することは、マルチユーザの検出器（ＭＵＤ）行列（例えば非相関器または最小平均二乗誤差（ＭＭＳＥ）行列）をｄｅｓｐｒｅａｄｅｒの出力ベクトルで乗じた積を含む。さらに、それは最小二乗法の計算に適用可能である。有限インパルス応答（ＦＩＲ）フィルタでは、離散フーリエ変換（ＤＦＴ）が完全にまたは部分的に計算される。特に、部分ＤＦＴのＦＩＲフィルタおよびＦＦＴが効率的でない中小規模のフィルタは、本発明のこの特徴が適用可能な例である。離散コサイン変換ＤＣＴは、別のタイプの線形変換で、その演算は本発明によって改善され得る。これは、特に部分的に計算されるだけであるとか、そのサイズがあまり大きくない場合に特に効果的で、その結果、より高次の高速アルゴリズムにはあまり効率的ではない。
【０２５７】
ＦＩＲを使用する処理回路のようないくつかのデジタル信号処理アプリケーションでは、２つの比較的長いベクトルの相関が要求される。そのベクトルの１つは、 ＦＩＲフィルタのタップを表わすことがあり、それはフィルタされるべき入力を表わす第２のベクトル上で動作する。部分的な畳み込みから成るフィルタ動作は、トップリッツ行列をベクトルで乗じた積によって表わされる。これは、本発明の実数行列の面から効率的に行われる。
複素行列
例：次の合計を計算することを目的と仮定する。
【０２５８】
2004511046.tif 000129
ここで、入力スカラｘ１，ｘ２，．．．．．．．．．．，ｘ６は複素数である。
【０２５９】
従来の先行技術からのアプローチでは、６６回の実数加算を要求するであろう。これは、ソート（±１±ｊ）のファクタを複素数で乗じた積は２回の実数加算を要求し、２つの複素数の加算は２回の実数加算を必要とすることを考慮に入れると、理解される。
【０２６０】
この演算を行なうための本発明の好適な実施例の２つの主要な選択が示される。相回転プラスＧＥＭと呼ばれる本発明の第１の好適な実施例で、、それは次の事実を使用する。
【０２６１】
2004511046.tif 000130
従って、上記の合計すべてに（１／２）（１＋ｊ）を掛けることによって、ここで相回転と呼ばれる行為を行い、および我々はセット｛１，−１，ｊ，−ｊ｝からの係数を得る。
【０２６２】
2004511046.tif 000131
本発明の好適な実施例によれば、これらの合計はＧＥＭによって計算される。この例の小規模なサイズにより、従来の方法と比較して、利得はこの場合欄外であるが、しかし、それはより大きな次元で本質的なものとなる。この例のように、次元が小さい時、他の従来の演算方式が相回転ステップの後に適用される。最後に、各合計の結果は所要の結果を得るために（１−ｊ）が乗じられる。ｊまたは（−１）は、適度な量の時間とエネルギを要求する「組織的な」動作である。好適な実施例の第２のオプションは、複素Ｕ方法と呼ばれる。それは、次の方法で各係数のブラケットを開くことにより、合計を求める。
【０２６３】
2004511046.tif 000132
残りはＵ方法の適用により行われる。ｓ（１２，３）＝１２＋３＝１５であるから、複素加算の回数である場合、これはｓ（ｎ，ｒ）の上記テーブルから高々３０回の実数加算を要求する。
【０２６４】
上記の例によって基本原理を示したが、今一般的な場合の詳細な説明を与えることは適切であろう。複素行列に関しての本発明の好適な実施例を示すために、係数として使用されるセットを考慮する、すなわち、Ｕ１＝｛１，１，ｊ，−ｊ｝およびＵ２＝｛１＋ｊ，１−ｊ，−１＋ｊ，−１−ｊ｝。Ｕ１ベクトルまたはＵ１行列はＵ１の中にそれらのエントリを有する。同様に、Ｕ２ベクトルまたはＵ２行列はＵ２の中にそれらのエントリを有する。このような行列およびベクトルは、ワイヤレス応用において一般的である。続くものでは、Ｕ２の番号を複素数で乗じた積は２回の実数加算を要求し、その一方でＵ１番号を複素数で乗じた積は比較的少量の複雑性を含んでいることを考慮に入れるべきである。
【０２６５】
解決される第１の計算上の問題は、次のとおりである、すなわち、ｒ×ｎのＵ２行列Ａおよびｎ次元の複素列の入力ベクトルｘが与えられ、積ｙ＝Ａ・ｘを計算するこが所望されると仮定する。確かにスカラ積であるケースｒ＝１の場合が、含まれる。この演算への２つの主要なアプローチが示されるであろう。適切なとき、各々が所望されるであろう。そのデータ・ベクトルが実数のとき、同じプロセスが、少しの修正で、適用可能である。
【０２６６】
最初に、本発明の好適な実施例である相回転プラスＧＥＭが導入される。
【０２６７】
2004511046.tif 000133
であるとし、そのとき、Ｂはｒ×ｎのＵ１−行列であり、そして、ｚ＝Ｂ・ｘである。次に、積ｚ＝Ｂ・ｘはＧＥＭによって計算される。一旦ｚが計算されれば、出力ベクトルｙは積ｙ＝（１−ｊ）・ｚによって求められる 。最初の位相回転ステップに起因する従来方法に対する利得は、２ｒ・（ｎ−１）加算の節約である。この利得はｒ＝１の場合、すなわちスカラ積の場合でさえ存在する。一層の利得はＧＥＭのアプリケーションに起因する。
【０２６８】
第２の本発明の好適な実施例は、Ｕ複素方法と呼ばれる。第１の事項は合計としてＡ、すなわちＡ＝Ａ１＋ｊＡ２を表わすことである、ここで、Ａ１およびＡ２はＵ行列である。次に、同一を考慮すること、すなわちＡ・ｘ＝Ａ１・ｘ＋ｊＡ２・ｘを検討することである。この同一は、２ｎ複素次元の列ベクトル
【０２６９】
【数７５】
2004511046.tif 000134
【０２７０】
を備えるｒ×２ｎのＵ行列Ａ＊＝［Ａ１，Ａ２］の積によってＡ＊ｘを計算することができることを意味する。これは次の同一、すなわちＡ・ｘ＝Ａ＊・ｘ＊の中で表現される。今、積Ａ＊・ｘ＊はＵ方法によって計算されるであろう。この本発明の好適な実施例中の別の変形があり、それはｒが小さいとき合理的であり、
【０２７１】
【数７６】
2004511046.tif 000135
【０２７２】
とすると、これは２ｒ×ｎのＵ行列である。その後、積、すなわちＡ＊＊・ｘを計算するためにＵ方法を適用する。これは実際両方の積ｙ１＝Ａ１・ｘおよびｙ２＝Ａ２・ｘを計算する。そのプロセスは合計、すなわちｙ＝ｙ１＋ｙ２で終了する。
【０２７３】
上記の問題に関する変化が、ＣＤＭＡでのＰＮ相関器のトップリッツ行列表現を含むいくつかの応用で発生するかもしれない。この設定では、行列はまた０のエントリを有してもよい。従って、Ｕ’１＝｛０，１，−１，ｊ，−ｊ｝およびＵ’２＝｛０，１＋ｊ，１−ｊ，−１＋ｊ，−１−ｊ｝とする。Ｕ’１ベクトルまたはＵ’１行列はＵ’１中にそれらのエントリを有する。同様に、Ｕ’２ベクトルまたはＵ’２行列はＵ’２中にそれらのエントリを有する。ｒ×ｎのＵ’２行列Ａが与えられ、ｎ次元の複素列入力ベクトルｘが与えられる。ゴールは積ｙ＝Ａ・ｘを計算することである。確かにスカラ積であるｒ＝１のケースの場合含まれる。
【０２７４】
本発明の好適な実施例である相回転プラスＧＥＭが最初に議論されるであろう。
【０２７５】
Ｂ＝（１／２）（１＋ｊ）・Ａ　および　ｚ＝（１／２）（１＋ｊ）ｙ
とすると、そのとき、Ｂはｒ×ｎのＵ’１行列およびｚ＝Ｂ・ｘとなる。次に、積ｚ＝Ｂ・ｘがＧＥＭの応用によって計算され、または次元が低いとき、より従来の方式によって計算されるであろう。最後に、一旦ｚが計算されれば、出力ベクトルｙは、積、すなわちｙ＝（１−ｊ）・ｚによって求められるであろう。
【０２７６】
別の本発明の好適な実施例によれば、Ａが、まず合計、すなわち、Ａ＝Ａ１＋ｊＡ２として表わされる、ここでＡ１とＡ２は（０，１，−１）行列、可能ならトップリッツである。そのとき等式、すなわち、Ａ１・ｘ＋ｊＡ２・ｘ積Ａ・ｘによって、Ａ・ｘ＝は、ｒ×２ｎの（０，１，−１）行列Ａ＊＝［Ａ１，Ａ２］を２ｎ複素次元の列ベクトル、すなわち
【０２７７】
【数７７】
2004511046.tif 000136
【０２７８】
で乗じた積によって計算され得る。結局、積Ａ＊・ｘ＊は、トップリッツによって、または発明のより一般的な（０，１，−１）の特徴によって計算されるであろう。
【０２７９】
ｒが小さいとき、その非トップリッツのカウンターパートに反映して、本発明の別の（選択的な）好適な実施例は、効率的であり、
【０２８０】
【数７８】
2004511046.tif 000137
【０２８１】
とすると、これは２ｒ×ｎ（０，１，−１）行列となる。次に、積、すなわちＡ＊＊・ｘを計算するために、本発明の（０，１，−１）の特徴を適用する。これは実際に積ｙ１＝Ａ１・ｘおよびｙ２＝Ａ２・ｘを計算する。最後に、このプロセスは、合計、すなわちｙ＝ｙ１＋ｊ・ｙ２で終わる。
【０２８２】
さて、複素数の章は、一般的な複素ｒ×ｎ行列であるＡ∈Ｃｒｘｎを実数または複素数のｎ次元ベクトルｘで乗じた積を計算する方法で終了するであろう。本発明のある好適な実施例によれば、最初にＡを合計、すなわちＡ＝Ａ１＋ｊＡ２として表わす、ここでＡ１とＡ２は実数の行列である。次に等式、Ａ・ｘ＝Ａ１・ｘ＋ｊＡ２・ｘによって、Ａ・ｘ＝Ａ＊・ｘ＊であるから、Ａ・ｘがｒ×２ｎの実数行列Ａ＊＝［Ａ１，Ａ２］を２ｎ次元の列ベクトル
【０２８３】
【数７９】
2004511046.tif 000138
【０２８４】
で乗じた積によって計算することができる。最後に、積Ａ＊・ｘ＊は実数の行列法によって計算されるであろう。
【０２８５】
本発明の別の（選択的な）好適な実施例に従って、
【０２８６】
【数８０】
2004511046.tif 000139
【０２８７】
とする。これは２ｒ×ｎの実数の行列である。次に、積、すなわち、Ａ＊＊・ｘを計算するために実数の行列法を適用する。これは積ｙ１＝Ａ１・ｘおよびｙ２＝Ａ２・ｘを計算することである。最後に、そのプロセスは、合計、すなわちｙ＝ｙ１＋ｊ・ｙ２で終わる。
【０２８８】
最後に、Ｕ２係数を備えたトップリッツ行列をベクトルで乗じた積は、上記のトップリッツ技法の応用によって行われる。
トップリッツ行列、（０，１，−１）行列および複素行列技法の産業上の応用例
ＩＳ−９５　サーチャ（ｓｅａｒｃｈｅｒ）：
ＩＳ−９５　ＣＤＭＡシステムによって、小さな地理的な場所における多くの異なる基地局が、データをモバイル受信機に送信するために、スペクトラムの同じセグメントを同時に使用することができる。異なる基地局からのデータを区別するための方法は、送信データを拡散するために使用されるＰＮシーケンスによるものである。各基地局は、ＰＮシーケンスの異なった過程で送信する。モバイル受信機におけるサーチャ機構の作業は、それらのＰＮシーケンスと調整することにより周囲の基地局によって送信された異なるパイロット信号を識別することである。それはまた、同じ基地局から到着するいくつかの多重経路伝播の信号（エコーを意味する）を区別するために適用される。同様のプロセスは、初期の同期手順に適用される。
【０２８９】
サーチャは、ローカルに生成されたＰＮシーケンスをもって、各仮説（ｈｙｐｏｔｈｅｓｅ）に関して、受信信号の偏相関（ｐａｒｔｉａｌ ｃｏｒｒｅｌａｔｉｏｎ）によって、多くの仮説をテストすることを要求される。その後、シーケンスは各仮説のためにシフトされ、また、相関が信号エレメント（チップ）の固定番号に対して実行される。通常、サーチャは、与えられたウィンドウ内で仮説のすべてを検索することを要求され、一回毎に、シーケンスが１ずつシフトされる。サーチャは、行が上記言及したシフトされるＰＮシーケンスからなる行列Ａの構築により、ＤＳ−ＣＤＭＡシステムで実行され得る。その後、その検索結果はベクトルｙ＝Ａ・ｘの中で与えられるが、ここでｘは単一のチップ期間でサンプリングされた到来信号を示すベクトルである。本発明の好適な実施例によれば、効率的な線形変換のための上記言及した創作性のあるアルゴリズムは、資源の消費を削減したベクトルｙを得るために実行される。本発明の多くの応用は、さらに、広帯域ＣＤＭＡの提案された標準規格のサーチャに有用である。
多重（マルチ）積
本発明の別の好適な実施例は、ベクトル積によるＵ行列の部分和が望まれる状況と関係する。異なる速度（拡散因子：ｓｐｒｅａｄｉｎｇ ｆａｃｔｏｒ）を有するいくつかのコードが同時にテストされるとき、これはＣＤＭＡ通信への応用において生じる。この実施例の研究は、既に本発明の前状況における本質的な事項を実行した者にとってより有益である。それは、豊富な詳細がなくてもこのやや複雑な方法についての最初の概念を与える次の実例で紹介されるであろう。しかしながら、合理的なサイズの例が、この実施例のすべての状況について記述することはできない。本発明の発明の要約、項目６をさらに参照してもよい。
【０２９０】
例
次の５×８のＵ行列
【０２９１】
【数８１】
2004511046.tif 000140
【０２９２】
および、８次元の入力ベクトルを検討する。
【０２９３】
【数８２】
2004511046.tif 000141
【０２９４】
ライン１と２の拡散因子は２、およびライン３と４の拡散因子は４、およびライン５の拡散因子は８であるとする（多重積の用語において）。最初の２行では２つ毎の連続したエレメントが合計され、第３および第４行目においては各４つの連続したエレメントが合計され、第５行目では、全ラインが合計される。規約は、拡散因子は減少することはなく、すなわち、各ラインの拡散因子は前のラインの拡散因子に等しいかそれより大きいということである。この用語は後に正確に定義されるであろう。
【０２９５】
次の合計が計算されることが上記から理解されるであろう。
【０２９６】
2004511046.tif 000142
最初に４つの４×２のＵ行列への分割があり、そこで水平の次元が最低の拡散因子に反映する。その後、この新しい側面から加算がどのように削減されるかを示すために、極めて基礎的なレベルで、Ｕ方法が適用される。このように、同値のラインを消去することに適用して、２つの加算だけが各ラインのすべての最初の合計を計算するために要求される。
【０２９７】
2004511046.tif 000143
同様に、２つの加算のみが各ラインの第２の合計に必要となる。
【０２９８】
2004511046.tif 000144
など。従って、合計８回の加算がこの部分のために必要である。さらに４回の加算がライン３および４の求められた合計を計算するために必要であり、さらに４回の追加の加算がライン５の求められた合計を計算するために要求される。従って、合計１６回の加算が本発明の好適な実施例を適用することにより要求された。先行技術である従来の力まかせの方法では、同じ作業をするために、２８回の加算を要求していたであろう。
【０２９９】
本発明の現在の状況における環境はＵ行列を含み、それは上記の実例でのように各ラインで、等しい間隔のサブ合計が必要な場合、大きな次元であってもよい。入力ベクトルは実数かまたは複素数である。その行列は、ラインによっていくつかのサブ行列へサブ分割され、各ラインは上記の実例中に別々にかつ独立して使用される方法によって計算される。加算を削減しそれにより複雑性を低減する点から、ほぼ最良のサブ分割を見つける方法がこの実施例へ統合される。そのためのツールは、ダイナミックなプログラミングに基づく追加のプロセッサまたは装置であり、それはテーブル、境界およびＵ方法の回帰的な方程式ｓ（ｎ，ｒ）を使用して様々なサブ分割を分析する。非常に正確な構成がこの実施例の開発に必要である。いくつかの新しい定義は予備資料として必要であろう。
【０３００】
ｖ＝（ｖ１，ｖ２，．．．．．．．．．．，ｖｎ）にベクトルにすると、ｐはｎを分割する正の整数である（要するに：ｐ｜ｎ）。ｖ［ｐ］を、長さｐのセクションへｖを細分することにより形成される、ベクトルのベクトルであると定義する。したがって、
2004511046.tif 000145
セクションを次のように表示する。
【０３０１】
ｖ［ｐ，ｋ］＝（ｖ（ｋ−１）ｐ，ｖ２，．．．．．．．．．．，ｖｋｐ） １≦ｋ≦ｎ／ｐに対して
文中の整数ｐは拡散因子（ｓｐｒｅａｄｉｎｇ ｆａｃｔｏｒ）と呼ばれる。マルチベクトルは行列の構造と同種の構造である認識する。次の項目、すなわちマルチベクトルのマルチスカラ積は、行列積と通常のスカラ積との間のクロス（中間物）である。２つのｎ次元ベクトルをｖ＝（ｖ１，ｖ２，．．．．．．．．．．，ｖｎ）およびｗ＝（ｗ１，ｗ２，．．．．．．．．．．，ｗｎ）とすると、ｖおよびｗのｐ−マルチスカラ積は次のように定義される。
【０３０２】
2004511046.tif 000146
ここで、内部積（ｉｎｔｅｒｎａｌ ｐｒｏｄｕｃｔｓ）、ｖ［ｐ，１］・ｗ［ｐ，１］，ｖ［ｐ，２］・ｗ［ｐ，２］，．．．．．．．．．．は、通常のスカラ積である。この積の結果はｎ／ｐ次元のベクトルであることに注意すること。
【０３０３】
ＡをラインＡ１，．．．．．．．．．．，Ａｒを備えたｒ×ｎ行列であり、ｐ＝（ｐ１，ｐ２，．．．．．．．．．．，ｐｒ）を正の整数ベクトルであるとする。すべての１≦ｉ≦ｒに対し、ｐｉがｎを分割するならば、ｐはｎを分割すると言えるであろう。これはｐ｜ｎと表示される。今そのｐ｜ｎを仮定する。ｎ次元のベクトルｘをとり、ベクトルのベクトルである、Ａ掛けるｘのｐ−マルチ積をＡ・ｘ［ｐ］と表示して、次のように定義する。
【０３０４】
2004511046.tif 000147
本発明の最新の実施例は、今後記述される構成中の積の演算を改善するであろう。
マルチ積システム
マルチ積システム（または短くしてＭＰシステム）は、パラメータとして整数ｎ，ｒおよび正の整数ベクトルｐ＝（ｐ１，ｐ２，．．．．．．．．．．，ｐｒ）を含む設定である、すなわち、
2004511046.tif 000148
整数ｐ１，ｐ２，．．．．．．．．．．，ｐｒは、システムの拡散因子と呼ばれる。ＭＰシステムのパラメータは次の方法で書かれるであろう。
【０３０５】
2004511046.tif 000149
これらのパラメータに今ｒ×ｎのＵ行列Ａおよびｎ次元の実数のベクトルｘを付す。目標は効率的に積Ａ・ｘ［ｐ］を計算することである。全ＭＰシステムは次の方法で書かれるであろう。
【０３０６】
2004511046.tif 000150
さらに、整数ｐ１，ｐ２，．．．．．．．．．．，ｐｒ，ｎがすべて２の累乗であるとき、そのとき、そのシステムは２進多重積システムまたは短くして、ＢＭＰシステムと呼ばれる。
Ｍ−１方法
本発明のこの特徴は、ＭＰシステムへのＵ方法のストレートは適応である。それは上記の実例によって表わされる。実際には、後で記述されるほぼ最適のサブ区分の後に、それは、ＭＰシステムのサブシステムに通常適用されるであろう。
【０３０７】
ＭＰシステムＳ＝（ｒ，ｎ，ｐ，Ａ，ｘ）を与える。この方法は、最小の拡散因子ｐ１に関してサブ行列への行列の水平分割に基づき、サブ行列はそれぞれ幅ｐ１である。それは、行列ＡのＵ係数を備えたベクトルｘの最初のｐ１実数の合計を計算することにより始まる。これは、Ｕ−２進方法によってすべてのラインで同時に行われる。その後、それは次のｐ１列へ進み、同じプロセスを行なう。すべてのｎ変数が使い尽くされるまで、それはこのように継続する。次に、ｐｉ＞ｐ１であるラインの各々へ進み、ありふれた方法で合計プロセスを完了する。
【０３０８】
各サブ行列上のＵ方法の最初のステップは、他のラインを生のまたは反転のコピーであるラインを走査することである。例えば、ｐ１＝２の場合、そのとき、高々２つの加算がｒにかかわらず各セクションで必要とされる。一般に、わずか２ｐ１−１のラインが、あらゆるセクション中のＵ−２進方法によって考慮される。さらに、このテキストによって意図する１つのアプリケーションは、Ａがアダマールである場合である。この場合、各セクション中にわずかｐ１個の非等価ラインがある。したがって、どれだけの非等価ラインが各サブ行列に現われることがあるかについての境界を含む別のソースが挿入される。それは、近い将来行列のタイプの結果であるｚ（テーブルとして格納される）によって表示される機能に含まれるであろう。そのパラメータはｐ１とｒであり、それはｚ（ｐ１，ｒ）によって書かれる。例えば、Ａがアダマールであるとき、ｚ（４，６）＝４，ｚ（８，５）＝５であり、Ａが一般的なＵ行列であるとき、ｚ（４，４０）＝８である。それは常にｚ（ｐ１，ｒ）≦ｍｉｎ｛２ｐ１−１，ｒ｝を維持し、Ａがアダマールである場合、ｚ（ｐ１，ｒ）≦ｍｉｎ｛ｐ１，ｒ｝である。
【０３０９】
Ｍ−ｌ方法の複雑性の演算は、上記のＵ−２進方法の記述で現われるテーブルおよびｓ（ｒ）の回帰方程式に基づくであろう。すべての正の整数ｙに対して、ｓ’（ｙ）＝ｓ（ｙ）＋ｙとする。さらにｓ’（ｙ）＜２ｙ−１＋２ｙ／２＋１であることを想起し、そしてこの不等式はややきつい。これは、次の方程式中の複雑性の程度に直覚的な視点を与える。Ｍ−ｌ方法によって行われる加算の数は、次の式で境界付けられる。
2004511046.tif 000151
いくつかのつまらない点があるが、しかし、この方程式の重要な例に注意を要する。最初は、行列が１ラインを有する場合である、すなわち、ｒ＝１のとき、
2004511046.tif 000152
第２は、一定の拡散因子の場合である、すなわち、ｐ１＝ｐ２＝．．．．．．．．．．＝ｐｒのとき、
2004511046.tif 000153
明らかに、Ｍ−１方法は、ｒがｐ１に比べて大きいとき、決して効率的でない。より賢い方法のための踏み石がそれを基礎として開発されるであろう。このより強力な方法は、行列を水平に細分しＭ−ｌ方法を各サブ行列に別々に適用することによりうまくいく。より少ない計算でより少ない加算総数をもたらすサブ区分の構造を見つけるために、上記方程式の次のより短いバージョンを有することが有用であろう。そこで、次のように定義する。
【０３１０】
2004511046.tif 000154
マルチシステムのサブ区分およびマルチベクトルについての一般化された概念
次に、構成は、行列を水平ライン上に細分するように命じるために形成される。この命令は、細分するベクトルｒによって表わされるであろう。その結果は、オリジナルの問題を同じ幅ｎの少数のサブ問題に分解し、各々は上記のＭ−ｌ方法によって解決されるであろう。サブ区分は、効率を最大限にするために後で発明性のあるアルゴリズムに添付されるであろう。拡散因子のｒ次元の整数ベクトル、ｐ＝（ｐ１，ｐ２，．．．．．．．．．．，ｐｒ）、およびｒ×ｎのＵ行列を次式とする。
【０３１１】
【数８３】
2004511046.tif 000155
【０３１２】
そして、整数ｋ，ｍを、１≦ｋ≦ｍ≦ｒとする。ベクトルｐのセクションを最初に定義する。
【０３１３】
2004511046.tif 000156
それは、単にｋからｍの指標を備えたコンポーネントをとる。行列Ａのセクションを次のように定義する。
【０３１４】
【数８４】
2004511046.tif 000157
【０３１５】
同様に、それはｋからｍの指標を備えたラインを有することを意味する。
次に、整数ベクトルｒ＝（ｒ（１），．．．．．．．．．．，ｒ（ｔ＋１））が、
2004511046.tif 000158
を満たすことを考慮し、それはセクションに分割する道具となる。まず、ｒは、次の方法で、ｐのサブ区分をベクトルｐ［ｒ］のベクトルへ作成するツールである。
2004511046.tif 000159
サブ・ベクトルは次のように表示される。
【０３１６】
2004511046.tif 000160
行列Ａの行は、次の方法で細分するベクトルｒに従って同様に細分される。
すべての整数１≦ｑ≦ｔに対して、
2004511046.tif 000161
与えられたサブ区分のためのＭ方法
このセクションは、メカニズムの形成に主要なステップがあり、それはこの実施例で中心となる低い複雑性のサブ区分であるメカニズムを見つける。行列におけるラインのサブ区分を与え、各サブ行列上でＭ−ｌ方法を別々に行なう。目標は加算の総数を評価し、その結果より少数の加算のサブ区分が次のステージで見つかるであろう。ＭＰシステムＳ＝（ｒ，ｎ，ｐ＝（ｐ１，ｐ２，．．．．．．．．．．，ｐｒ），Ａ，ｘ，ｚ）およびサブ区分ベクトルｒ＝（ｒ（１），．．．．．．．．．．，ｒ（ｔ））を固定する、ここで１≦ｋ＝ｒ（１）＜ｒ（２）＜．．．．．．．．．．＜ｒ（ｔ）＜ｒ（ｔ＋１）＝ｍ＋１≦ｒ＋１である。
１≦ｑ≦ｔに対して、ＳｑＭＰサブシステムは次式によって与えられる。
【０３１７】
2004511046.tif 000162
すべてのサブシステムの加算総数は次のとおりである。
【０３１８】
2004511046.tif 000163
次の目標は効率的な方法を開発することで、それはこの事項を最小にするサブ区分を見つける。各ステージで反復する付加的なサブ事項１／ｐｋ＋．．．．．．．．．．＋１／ｐｍおよびｎ要因を見積もらずに、計算を行なうほうが効率的であろう。したがって、次のように定義する。
【０３１９】
2004511046.tif 000164
ほぼ最適なサブ区分
このステージでは、上記の項Ｃ（ｎ，ｒ，ｒ，ｐ，ｚ）によって与えられる加算量を最小限にするサブ区分の特性を検討する。最初に、加算数に対する抽象的な公式を与えるが、ここでは、サブ区分がオリジナルの問題の与えられた部分区間上で拘束される最小の最悪のケースを有する。
【０３２０】
そのとき、１≦ｋ≦ｍ≦ｎであるとして、ＭＰシステムＳ＝（ｒ，ｎ，ｐ＝（ｐ１，ｐ２，．．．．．．．．．．，ｐｒ），Ａ，ｘ，ｚ）および整数ｋ，ｍを検討する。次式を定義する。
【０３２１】
2004511046.tif 000165
ここで ｋ＝ｒ（１）＜ｒ（２）＜．．．．．．．．．．＜ｒ（ｔ）＜ｒ（ｔ＋１）＝ｍ＋１｝
それは次式を保持する。
【０３２２】
2004511046.tif 000166
次の循環公式を保持する。
【０３２３】
2004511046.tif 000167
ここで　ｍｉｎ（ｅｍｐｔｙ ｓｅｔ）＝ｉｎｆｉｎｉｔｙ
2004511046.tif 000168
さて、これらの表現は次のダイナミックなコードによって使用されるが、そのサブ構造はｋとｍの間のインターバルにある。このコードｈ＊の複雑性を低減することは、最良のサブ構造を発見するためにルート上のｈを交換する。これは最終結果に影響はない。最適のサブ区分の第１歩を見つけるために、我々はすべてのｋおよびｍに対する、式ｈ（ｋ，ｑ−１）＋ｈ（ｑ，ｋ）を最小にするｑを計算する、ここで、１≦ｋ≦ｍ≦ｎであり、それはしきｈ＊（ｋ，ｑ−１）＋＊ｈ（ｑ，ｋ）を最小にするのと同じｑである。従って、次を定義する。
【０３２４】
ｑ（ｋ，ｍ）＝ｋ
ここでｈ＊（ｋ，ｍ）＝Ｃ＊（ｎ，ｒ，ｐ（ｋ，ｍ），ｚ）
そうでなければ、
ｑ（ｋ，ｍ）＝最小のｑ，ここで、ｋ＜ｑ≦ｍおよびｈ＊（ｋ，ｍ）＝ｈ＊（ｋ，ｑ−１）＋ｈ＊（ｑ，ｋ）
今、最適なサブ区分コードを形成することができる。
最適なサブ区分を見つけるダイナミックなプログラムの創造的なコード
次のコードは、データとしてＭＰシステムＰ＝（ｒ，ｎ，ｐ，ｚ）のパラメータを受け取り、出力としてＭ−方法が最適に達成するサブ区分ｒを生成する。加えて、それは、さらに最適なＭ−方法の複雑性（ｃｏｍｐｌｅｘｉｔｙ）を返す。
【０３２５】
それを効率的に実行するために、ｓ’（ｒ）のテーブルを前もって計算し格納する必要がある。これは、次の回帰公式を使用して、このテーブルを計算する、高速コードによって行われる。
【０３２６】
2004511046.tif 000169
今残されていることは、この手続きによって構築されたテーブルｑ（ｋ，ｍ）から最適なサブ区分ベクトルを得ることである。これは最適のベクトルｒのコンポーネントを含むセットＲを作成する次のコードによって行われる。
2004511046.tif 000170
さて、最適のサブ区分ｒが見つかるので、Ｍ方法はこのサブ区分上で走るであろう。
・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・
インプリメンテーション
本発明の次の好ましい実施例は、上記方法の詳細な実行となる創造性のあるアルゴリズムを提供する。それらは、上記方法を行なうのに必要なメモリとエネルギ資源の削減を可能にする。それらは、上記方法を増強し、装置を構築するのに必要な命令を提供するのに２つのゴールを有する。これらを実行する際に強調すべき１つの仮定は、変換行列が総括的で、エントリの与えられたセットを有する行列のセットから任意に選ばれるように考慮されることができるということである。もう１つは、行の数が列の数と比較したとき、十分に少ないということであり、それにより上述した基本の境界
行の数＜ｌｏｇ（列の数）
は、満たされる。従って、等価ラインをチェックするような他の状況において適切であるステップのいくつかは、ここでは余分である。
【０３２７】
後述のテキストに記述されたマッピングは、１つの場所から次の場所へデータのフローに手順を開く。各場所は、所定の反復で、行列の列に対応する２進のアドレスで割り当てられる。Ｕ行列の場合には、列における（−１）のコンポーネントは、アドレスにおける１に対応し、同様に列における１のコンポーネントはアドレスにおける０に対応する。同様の対応が、Ｕ１行列に対して定義される。
【０３２８】
説明されるインプリメンテーションは、到来するｘｊ信号が、それらの対応する列によって決定された宛先を前もってセットするために加えられる第１ステップを含み、ここで各ｘｊは記号および／または２の累乗が乗じられる。進行する反復中において、列が本発明に従って分割される場合は常に、２つの各の分割に割り当てられたアドレスは、その所定の列アドレスへより小さいか等しい。これは、メモリのある場所に格納されたすべての情報を、処理され失われる前にその宛先へ送ることができる。加えて、それが所定の列を分割した半分の１つが０であると考えれば、この列を表わすアドレスは次の反復に使用されるであろう。これらの特性は、データの移動を最小限にするために設定されるデータ・フロー・マップの斬新な構築によって遂行される。各反復で、アドレスの最大の数は手をつけないままで、その現在の内容が次の反復によって使用することができるものをすべて含める。
【０３２９】
次のインプリメンテーションのメカニズムは、上記において記述された本発明の好適な実施例であるＧＥＭを考慮してより一層理解される。数１を含む数の有限集合Ｓが考慮され、この文章中では、それがそのコンポーネントが集合Ｓに属し、正規化されたｒ次元の列ベクトルのすべての可能なゼロでない構成から成る場合、ｒラインの行列は完全なＳ−ｒ−行列と名付けられ、その構成がそれぞれ一度正確に現われ、その正規化規約は最低のゼロでない要素が１であるべきということである。
次のより低い次元の例を観察する。
行列
【０３３０】
【数８５】
2004511046.tif 000171
【０３３１】
は、完全な｛０，１｝−２−行列である。
行列
【０３３２】
【数８６】
2004511046.tif 000172
【０３３３】
は、完全なＵ−２−行列である。
行列
【０３３４】
【数８７】
2004511046.tif 000173
【０３３５】
は、完全なＵ−３−行列である。
行列
【０３３６】
【数８８】
2004511046.tif 000174
【０３３７】
は、完全な｛０，１｝−３−行列である。
行列
【０３３８】
【数８９】
2004511046.tif 000175
【０３３９】
は、完全な｛１，−１，ｊ，−ｊ｝−２−行列である。
【０３４０】
次のインプリメンテーションは、列の数に対して行の数が十分に少ないという仮定に基づき、その結果すべての可能な構成の大部分は、変換行列の列に現われる。従って、すべての進行中のインプリメンテーションで作成された最初の反復は、演算を完全なＳ−ｒ−行列と修正済のベクトルとの積にする。従って、さら前進した反復は、より低い次元の完全なＳ行列とそれぞれの修正済のベクトルとの積を計算する。
【０３４１】
列が上記例の行列に現われる規律正しい方法は、これらのインプリメンテーションのアドレス・セッティングに別の特徴を反映する。それは、列を｜Ｓ｜−ベースのアドレスに翻訳する一貫した規則に基づいたアドレスであり、ここで、ＭＳＢがベクトルのボトム・コンポーネントであり、ＬＳＢがトップである。
【０３４２】
基本的な結果は、第１の反復の後に、一定の（そしてむしろ明白な）アドレス番号付けをする唯一の一定の完全な変換行列があるということである。この一定の行列は、Ｓおよびｒのみに依存し、初期変換行列には依存しない。これは、残りのプロセスの中で等質性に通じるが、その結果最初のステージ後に一般的かつ特定の変換行列から独立したデータ・フロー構造の創出を可能にする。これは、ハードウェア・インプリメンテーションに、およびこの章の主要な目標であるが、本発明に基づいた装置を構成する際に非常に役立つ。
【０３４３】
これらのインプリメンテーションの追加・個別的な側面は、要求された読取りおよび書込みメモリの割当て、および適切な変換行列のための加算数の削減である。従って、そのプロセスの実行のために必要とされるエネルギ、および装置のコストが削減される。いくつかの入力ｘベクトルと同じ初期変換行列を処理するとき、次の各コードの効率が強調されることが認められるべきである。
【０３４４】
最後に、適切な展望を持つために、次のインプリメンテーションは、それらが本発明の多くの可能な効率的なインプリメンテーションの内のわずかな例であることを理解して読まれるべきである。
例１：０−１−２進の行列
次のステップのシーケンスは、本発明の０−１−行列の局面からみたインプリメンテーションについて記述する。データは、ｒ×ｎの０−１−行列　Ａ＝（ａｉｊ：０−ｉ＜ｒ，０−ｊ＜ｎ）、および実数または複素数入力ベクトルｘ＝（ｘ０，．．．．．．．．．．，ｘｎ−１）から成る。行列Ａの列は、ｖ０，．．．．．．．．．．，ｖｎ−１によって表示される。このステップのシーケンスは、積ｙ＝（ｙ０，．．．．．．．．．．，ｙｒ−１）Ｔ＝Ａ・ｘを計算する。すべての与えられたｋ−反復で、各場所は、ベクトルｘに依存して、１つの実数または複素数を含んでいる。割り付けられた読取りおよび書込みメモリは、各反復でプロセスに関係する列を表わして、１から２ｒ−１までラベル付けされた２ｒ−１のアドレスを含む。次の定義は、本発明の好適な実施例の記述の一部である。
【０３４５】
定義
１）全てのｋ¬０， ｊ¬１に対して、
【０３４６】
【数９０】
2004511046.tif 000176
【０３４７】
を定義する。
２）全ての０・ｍ＜ｒに対して、Ｙｍ＝２ｍを定義する。これらのアドレスは、Ｙ０がｙ０のアドレスであり、Ｙ１がｙ１のアドレスとなる場合のように、プロセスの終わりに、出力ベクトルｙ＝（ｙ０，．．．．．．．．．．，ｙｒ−１）Ｔのコンポーネントを含むであろう。
３）ｋ¬０およびｊ¬１に対して、以下のように各場所から次の場所へのデータの移動を制御する関数Ｆｋｊ，Ｇｋｊを定義する。まず、ｌ＝ｌ（ｋ，ｊ），ｍ＝ｌ（ｋ＋ｌ，２ｊ），ｈ＝ｌ（ｋ，ｊ＋１）−１を置き、
各整数ｖ¬０に対して、
【０３４８】
【数９１】
2004511046.tif 000177
【０３４９】
を定義する。
４）すべてのベクトルｖ＝（ｖ０，．．．．．．．．．．，ｖｒ−１）∈［０，１］ｒに対して、
2004511046.tif 000178
を定義する。
【０３５０】
コード
１．初期化：１から２ｒ−１まですべてのアドレスに０を入れること。
２．第１段階：ｊが０からｎ−１へ進み
もしｖｊ≠０ なら、そのときｘｊ をアドレスｖ＝□（ｖｊ）に加える
３．主要部分：
【０３５１】
【数９２】
2004511046.tif 000179
【０３５２】
そのとき、（ソース）アドレスｖ中に存在する値を（宛先）アドレスＧｋｊ（ｖ）中の値へ加え、
さらに、（ソース・アドレスｖの）この値を（宛先）アドレスＦｋｊ（ｖ）中の値に加える。
４．出力の獲得：
このステージでは、すべてのアドレスＹ１は、すべての０・ｉ＜ｒに対して、出力コンポーネントｙｉの値を含む。
【０３５３】
複雑性
現在の用語における基礎的ステップは、ソースと呼ばれるメモリの１つの場所から数を読み、宛先と呼ばれるメモリの別の場所に置かれた数にそれを加えることである。
【０３５４】
上記コードに基づく装置は、Ａ・ｘの上記演算の主要部分を計算するための次の数の基礎的ステップを要求するだろう。
【０３５５】
2004511046.tif 000180
この数はｒにのみ依存する。
【０３５６】
Ａ・ｘの全演算は、次の合計の基礎的ステップ数を要求する。
【０３５７】
2004511046.tif 000181
チャート１：０−１−２進・行列
図１は、上記コードの主要部分を実行する装置によって使用されたメモリの内容を更新する動作を概略的に示すが、０−１−２進・行列は４つの行からなり、本発明の０−１−２進の特徴を好ましい手法でインプリメントする。各反復における各行列の列は、メモリ中のアドレスによって２進形式で表わされる。ボトム（０または１）コンポーネント（水平表示での最も右手のコンポーネント）はＭＳＢであり、また、トップ（０または１）コンポーネント（水平表示における最も左手のコンポーネント）はＬＳＢである。アドレスＹｍ＝２ｍ，０・ｍ・３は、Ｙ０がｙ０のアドレスであり、Ｙ１がｙ１のアドレスになる場合のように、そのプロセスの終わりに出力ベクトルｙ＝（ｙ０，．．．．．．．．．．，ｙｒ−１）Ｔのコンポーネントを含む。矢印は、単一アドレスの内容をとり、別のアドレスの内容に加えられるためにそれを送る行為を示す。上記のコードによって示されるように、これは、反復の順序、および各反復に関係するアドレスの（増加）順序に従って行われる。
【０３５８】
例２：Ｕ行列
次のステップのシーケンスは、本発明のＵ行列の面からのインプリメンテーションについて記述する。そのデータは、ｒ×ｎＵ行列Ａ＝（ａｉｊ：０−ｉ＜ｒ，０−ｊ＜ｎ）および入力の実数ベクトルｘ＝（ｘ０，．．．．．．．．．．，ｘｎ−１）から成る。行列Ａの列は、ｗ０，．．．．．．．．．．，ｗｎ−１によって表示されるであろう。このステップのシーケンスは、積ｙ＝（ｙ０，．．．．．．．．．．，ｙｒ−１）Ｔ＝Ａ・ｘを計算する。すべての与えられた反復では、各場所はベクトルｘに依存して、１つの実数または複素数を含む。割り当てられた読取りおよび書込みメモリは、０から２ｒ−１＋ｒ−２までラベル付けされた２ｒ−１＋ｒ−１個のアドレスを含む。次の定義および前例の定義は、本発明の好適な実施例の記述に必要である。
定義
１）各ｒ次元のＵベクトルに対し、ｕ＝（ｕ０，．．．．．．．．．．，ｕｒ−１）は：
2004511046.tif 000182
を定義する。
２）バイポーラ２進セット、Ｕ＝｛１，−１｝およびロジック・ビットの２進セット、Ｂ＝（０，１）の間の一致を次式によって定義する。
【０３５９】
2004511046.tif 000183
従って、ｒ次元のＵベクトルに対して、ｕ＝（ｕ０，．．．．．．．．．．，ｕｒ−１）は、
2004511046.tif 000184
を定義する。
３）Ｙ０＝０、およびすべての１−ｍ・ｒ−ｌに対してＹｍ＝２ｒ−１＋ｍ−１を定義する。これらのアドレスは、Ｙ０がアドレスであり、Ｙ１がｙ１のアドレスとなる場合のように、プロセスの終わりに出力ベクトルｙ＝（ｙ０，．．．．．．．．．．，ｙｒ−１）Ｔのコンポーネントを含むであろう。
４）すべてのｋ¬０およびｊ¬１に対し、マップＦｋｊ、Ｇｋｊ、Ｓｉｇｎｋｊは、以下のように定義される。
ｌ＝ｌ（ｋ，ｊ），ｍ＝ｌ（ｋ＋１，２ｊ）、ｈ＝ｌ（ｋ，ｊ＋１）−１とする。あらゆる整数ｖ¬０に対し、
【０３６０】
【数９３】
2004511046.tif 000185
【０３６１】
を定義する。
【０３６２】
コード
１．初期化：０から２ｒ−１＋ｒ−２までのあらゆるアドレスに０を入れる。
２．第１段階：ｊが０からｎ−１まで進行することに対し、Ｓｉｇｎ（ｗｊ）・ｘｊをアドレスπ（ｈ（ｗｊ））に加える。
３．主要部分：
【０３６３】
【数９４】
2004511046.tif 000186
【０３６４】
１）（ソース）アドレスｙｌ（ｋｊ）に存在する値を（宛先）アドレスＹｌ（ｋ＋１，２ｊ）中の値への加える。
2004511046.tif 000187
ソース・アドレスｕに存在する値を終点アドレスＹｌ（ｋ＋１，２ｊ）中の値へ加える。
もし、Ｆｋｊ（ｕ）＝ｕの場合、そのとき
（ソース）アドレスｕに存在する値を（宛先）アドレスＹｌ（ｋｊ）中の値へ加える。
もし、Ｇｋｊ（ｕ）＝０の場合、そのとき
（−１）で乗じられた（ソース）アドレスｕに存在する値を（宛先）アドレスＹｌ（ｋｊ）中の値に加えて、また（アドレスｕの）この値をアドレスＦｋｊ（ｕ）中の値にさらに加える。
ほかに、Ｓｉｇｎｋｊ（ｕ）を掛けたソース・アドレスｕに存在する値を終点アドレスＧｋｊ（ｕ）中の値に加えて、また（アドレスｕの）この値をアドレスＦｋｊ（ｕ）中の値にさらに加える。
４．出力の獲得：
あらゆるアドレスＹｉは、すべての０・ｉ＜ｒに対して、ｙｉの値を含む。
【０３６５】
複雑性
ｉ）上記インプリメンテーションを備えたＵ設定中の基礎的ステップは、ソースと呼ばれるメモリの１つの場所から数を読み出し、１または−１である符号をそれに掛けて、次に、その結果を宛先と呼ばれるメモリの別の場所に置かれた数に加える。
ｉｉ）複雑性は次の事項で公式化される。
【０３６６】
【数９５】
2004511046.tif 000188
【０３６７】
ｉｉｉ）上記コードに基づく装置は、Ａ・ｘの演算を完了するために次の数の基礎的ステップを要求するであろう。
（１）最初のステージに対して、ｎ個の基礎的ステップが必要である。
（２）すべての
【０３６８】
【数９６】
2004511046.tif 000189
【０３６９】
に対しては、２・ｕｋ，ｊ−ｕｋ＋１，２ｊ−ｕｋ＋１，２ｊ−１＋１
個の基礎的ステップが（ｋ，ｊ）ステップで行われる。
（３）したがって、すべての
【０３７０】
【数９７】
2004511046.tif 000190
【０３７１】
に対して、主要部分のｋ−反復は、次の数の基礎的ステップを要求する。
【０３７２】
2004511046.tif 000191
（４）Ａ・ｘの上記演算の主要部分は、このように次の個数の基礎的ステップを要求する。
【０３７３】
【数９８】
2004511046.tif 000192
【０３７４】
この数はｒにのみ依存する。
（５）Ａ・ｘの全演算は、このように次の合計の基礎的ステップ数を要求する。
【０３７５】
【数９９】
2004511046.tif 000193
【０３７６】
チャート２：Ｕ行列
図２は、上記コードの主要部分を実行する装置によって使用されたメモリの内容を更新する動作を概略的に示すが、Ｕ−２進・行列は４つの行からなり、本発明のＵ−２進の特徴を好ましい手法でインプリメントする。各反復における各行列の列は、メモリ中の２進アドレスによって表わされ、列中の（−１）コンポーネントはアドレスにおける１に対応し、列中の１のコンポーネントはアドレスにおける０に対応する。２進の知識が適用され、ボトム・コンポーネント（水平表示での最も右手のコンポーネント）はＭＳＢであり、また、トップ・コンポーネント（水平表示における最も左手のコンポーネント）はＬＳＢである。特別のアドレスＹ０＝０，Ｙ１＝８，Ｙ２＝９，Ｙ３＝１０は、プロセスの終わりに出力ベクトルｙ＝（ｙ０，．．．．．．．．．．，ｙ３）Ｔのコンポーネントを含み、ここで、Ｙ０はｙ０のアドレスであり、Ｙ１はｙ１のアドレスなどのようになるであろう。矢印は、１または−１である符号を掛けた１つのアドレスの内容をとり、別のアドレスの内容に加えられるためにそれを送る行為を示す。１つの矢印は符号が１であることを示し、そして２つの矢印は符号が−１であることを示す。これは、反復の順序、および各反復に関係するアドレスの（増加）順に従って行われる。
【０３７７】
例３：Ｕ１行列
ステップの次のシーケンスは、変換行列のエントリがセットＵ１（Ｃ）｛１，−１，ｊ，−ｊ｝に属するときに、ＧＥＭ方法のインプリメンテーションについて記述する。これは、アプリケーションにしばしば現われるＧＥＭのサブケースの１つである。データは、ｒ×ｎのＵ１行列Ａ＝（ａｉｊ：０・ｉ＜ｒ，０・ｊ＜ｎ）および入力複素ベクトルｘ＝（ｘ０，．．．．．．．．．．，ｘｎ−１）から成る。行列の列は、ｗ０，．．．．．．．．．．，ｗｎ−１によって表示される。このステップのシーケンスは積ｙ＝（ｙ０，．．．．．．．．．．，ｙｒ−１）Ｔ＝Ａ・ｘを計算する。あらゆる与えられた反復で、各場所はベクトルｘに依存して、１つの実数または複素数を含む。割り付けられた読取りおよび書込みメモリは、０から４ｒ−１＋ｒ−２までラベル付けされた４ｒ−１＋ｒ−１個のアドレスを含む。この例は、次の定義と同様に、前例においてセットされた定義を使用する。
【０３７８】
定義
１）次のものから与えられたセットＵ１とセット｛０，１，２，３｝との間の一致（および逆の一致）を定義する。
【０３７９】
2004511046.tif 000194
従って、ｒ次元のＵ１ベクトル、ｕ＝（ｕ０，．．．．．．．．．．，ｕｒ−１）に対し、次式を定義する。
【０３８０】
2004511046.tif 000195
２）各ｒ次元のＵ１ベクトル、ｕ＝（ｕ０，．．．．．．．．．．，ｕｒ−１）に対し、次式を定義する。
【０３８１】
2004511046.tif 000196
３）Ｙ０＝０およびすべての１−ｍ＜ｒに対し、Ｙｍ＝４ｒ−１＋ｍ−１を定義する。これらは出力ベクトルのコンポーネントのアドレスになるであろう。
４）すべてのｋ¬０、ｊ¬１に対し、マップＦｋｊ、Ｇｋｊが次のように定義される。
【０３８２】
ｌ＝ｌ（ｋ，ｊ），ｍ＝ｌ（ｋ＋１，２ｊ），
ｈ＝ｌ（ｋ，ｊ＋１）−１とし、
ｖ＝Σ０≦ｊ＜ｒ−２４ｊ・ｖｊによって、４つの基礎の中で表わされた、整数ｖ¬０をとり、次式を定義する。
【０３８３】
【数１００】
2004511046.tif 000197
【０３８４】
コード
１．初期化：０から４ｒ−１＋ｒ−２までのあらゆるアドレスに０を入れる。
２．第１段階：
2004511046.tif 000198
３．主要部分：
【０３８５】
【数１０１】
2004511046.tif 000199
【０３８６】
１）アドレスＹｌ（ｋ，ｊ）に存在する値をアドレスＹｌ（ｋ＋１，２ｊ）中の値に加える。
２）ｆｏｒ ｐ ｇｏｉｎｇ ｆｒｏｍ １ ｔｏ ４ｌ（ｋｊ＋１）−ｌ（ｋｊ）−１ −１ ｄｏ
ｐｕｔ ｕ＝４ｌ（ｋｊ）・ｐ ａｎｄ ｆｏｒ ｓｏｕｒｃｅ ａｄｄｒｅｓｓ ｕ ｄｏ：すなわち
Ｇｋｊ（ｕ）＝ｕの場合
（ソース）アドレスｕに存在する値を（宛先）アドレスＹｌ（ｋ＋１，２ｊ）中の値へ加える。
ほかに、Ｆｋｊ（ｕ）＝ｕの場合、（ソース）アドレスｕに存在する値を（宛先）アドレスＹｌ（ｋ，ｊ）中の値へ加える。
ほかに、Ｇｋｊ（ｕ）＝０の場合、Ｓｉｇｎｋｊ（ｕ）を掛けた（ソース）アドレスｕに存在する値を（宛先）アドレスＹｌ（ｋ，ｊ）中の値に加えて、さらにこの値（アドレスｕの）をアドレスＦｋｊ（ｕ）中の値に加える。
ほかに、Ｓｉｇｎｋｊ（ｕ）を掛けた（ソース）アドレスｕに存在する値を（宛先）アドレスＧｋｊ（ｕ）中の値に加えて、この値（アドレスｕの）をアドレスＦｋｊ（ｕ）中の値に加える。
４．出力の獲得：
あらゆるアドレスＹｉは、すべての０・ｉ＜ｒに対して、ｙｉの値を含む。
【０３８７】
複雑性
ｉ）上記インプリメンテーションを備えたＵ１設定中の基礎的ステップは、ソースと呼ばれるメモリの１つの場所から複素数を読み出し、１または−１またはｊまたは−ｊである複素符号をそれに掛けて、次に、その結果を宛先と呼ばれるメモリの別の場所に置かれた複素数に加えることを意味する。
ｉｉ）複雑性は次の事項によって形成される。
【０３８８】
【数１０２】
2004511046.tif 000200
【０３８９】
ｉｉｉ）上記のコードに基づいた装置は、Ａ・ｘの演算を完了するために次の個数の基礎的ステップを要求するであろう。
（１）最初のステージに対して、ｎ個の基礎的ステップが必要である。
（２）すべての
【０３９０】
【数１０３】
2004511046.tif 000201
【０３９１】
に対しては、２・ｗｋ，ｊ−ｗｋ＋１，２ｊ−ｗｋ＋１，２ｊ−１＋１個の基礎的ステップの合計が（ｋ，ｊ）ステップで行われる。
（３）したがって、すべての
【０３９２】
【数１０４】
2004511046.tif 000202
【０３９３】
に対して、主要部分のｋ−反復は、次の数の基礎的ステップを要求する。
【０３９４】
2004511046.tif 000203
（４）Ａ・ｘの上記演算の主要部分は、このように次の個数の基礎的ステップを要求する。
【０３９５】
【数１０５】
2004511046.tif 000204
【０３９６】
この数はｒにのみ依存する。
（５）Ａ・ｘの全演算は、このように次の合計の基礎的ステップ数を要求する。
【０３９７】
【数１０６】
2004511046.tif 000205
【０３９８】
例４：トップリッツ　Ｕ行列
ステップの次のシーケンスは、Ｕ係数を備えた本発明のトップリッツ行列の面からインプリメンテーションについて記述する。データは、Ｕシーケンスｔ０，．．．．．．．．．．，ｔｎ−１、および入力実数または複素ベクトルｘ＝（ｘ０，．．．．．．．．．．，ｘｎ＋ｒ−２）から成る。Ｕシーケンスから、ｒ×（ｎ＋ｒ−１）のトップリッツ行列Ａ（Ｃ）（ａｉｊ（Ｃ）ｔｉ−ｊ：０・ｉ＜ｒ，０・ｊ−ｎ＋ｒ−２）が形成され、ここで、すべてのｋ＜０、または、ｋ¬ｎに対して、ｔｋ（Ｃ）０である。これらのステップは、積ｙ＝（ｙ０，．．．．．．．．．．，ｙｎ−１）＝Ａ・ｘを計算する。最初のステージのみがＵ行列例のステージと異なり、したがって、このステージだけを紹介することが必要である。前例のインプリメンテーションでリストされた定義は、すべてここに適用可能である。
【０３９９】
コード
１．初期化：０から２ｒ−１＋ｒ−２までのあらゆるアドレスに０を入れる。
２．第１段階：
2004511046.tif 000206
３．主要部分：アルゴリズムは、Ｕ行列インプリメントのアルゴリズム中の主要部分のように進行し、その出力は同じアドレスに格納される。
【０４００】
複雑性
ｉ）上記トップリッツのインプリメンテーションでの基礎的ステップは、Ｕインプリメンテーションと同じである、すなわち、ソースと呼ばれるメモリの１つの場所から数を読み出し、１または−１である符号をそれに掛けて、次に、その結果を宛先と呼ばれるメモリの別の場所に置かれた数に加える。
ｉｉ）上記コードに基づく装置は、Ａ・ｘの演算を完了するために次の数の基礎的ステップを要求するであろう。
（１）最初のステージに対して、
2004511046.tif 000207
個の基礎的ステップが必要である。
（２）Ａ・ｘのトップリッツ演算の主要部分は、ｒラインを備えたＵコードの主要部分のインプリメンテーションによって行われる。したがって、それはＣｕｒ個の基礎的ステップを必要とする。
（３）Ａ・ｘのトップリッツ演算全体は、このように次の回数の基礎的ステップを要求する。
【０４０１】
2004511046.tif 000208
チャート３：トップリッツ行列
図３は、到来データを装置に使用される適切なメモリ位置へ送る動作を概略的に示すが、その装置は４つの行からなるトップリッツ行列を有して、上記コードの初期部分を実行する。この最初の部分を除いて、他のあらゆる面は、Ｕ行列インプリメンテーションおよび装置の面と同一であり、その記述がここにあてはまる。ここでまた、１つの矢印は符号が１であることを示し、そして２つの矢印は符号が−１であることを示す。
【０４０２】
例５：トップリッツ　Ｕ１行列
本発明の次の好適な実施例は、Ｕ１係数を備えた本発明のトップリッツ行列の面からのインプリメンテーションである。データは、Ｕ１シーケンスｔ０，．．．．．．．．．．，ｔｎ−１、および入力複素ベクトルｘ＝（ｘ０，．．．．．．．．．．，ｘｎ＋ｒ−２）から成る。Ｕ１シーケンスから、ｒ×（ｎ＋ｒ−１）のトップリッツ行列Ａ（Ｃ）（ａｉｊ（Ｃ）ｔｉ−ｊ：０・ｉ＜ｒ，０・ｊ−ｎ＋ｒ−２）が形成され、ここで、すべてのｋ＜０、または、ｋ¬ｎに対して、ｔｋ（Ｃ）０である。以下にリストされたステップのシーケンスは、積ｙ＝（ｙ０，．．．．．．．．．．，ｙｎ−１）＝Ａ・ｘを計算する。最初のステージのみがＵ１行列例のステージと異なり、したがって、このステージだけを紹介することが必要である。前例でリストされたすべての定義は、ここに適用可能である。
【０４０３】
コード：
１．初期化：０から４ｒ−１＋ｒ−２までのあらゆるアドレスに０を入れる。
２．第１段階：
2004511046.tif 000209
３．主要部分：Ｕ１行列アルゴリズムの主要部分として進行し、そのデータは同じ方法で受け取られる。
【０４０４】
複雑性
ｉ）上記トップリッツのインプリメンテーションでの基礎的ステップは、Ｕ１インプリメンテーションと同じである、すなわち、ソースと呼ばれるメモリの１つの場所から複素数を読み出し、１または−１またはｊまたは−ｊである複素符号をそれに掛けて、次に、その結果を宛先と呼ばれるメモリの別の場所に置かれた複素数に加える。
ｉｉ）上記コードに基づく装置は、Ａ・ｘの演算を完了するために次の数の基礎的ステップを要求するであろう。
（１）第１段階に対して、
2004511046.tif 000210
個の基礎的ステップが必要である。
（２）Ａ・ｘにおけるトップリッツ演算の主要部分は、ｒラインを備えたＵ１コードの主要部分のインプリメンテーションによって行われる。したがって、それはＣＵ１ｒ回の基礎的ステップを必要とする。
（３）Ａ・ｘのトップリッツ演算全体は、このように次の回数の基礎的ステップを要求する。
【０４０５】
2004511046.tif 000211
例６：実数の行列、２進０−１の表現
本発明の次の好適な実施例は、行列エントリの２進０−１表現を備えた本発明の実数行列の面からみたインプリメンテーションである。データは、負でないエントリを備えたｒ×ｎ実数行列Ａ＝（ａｉｊ：０・ｉ＜ｒ，０・ｊ＜ｎ）、および入力の実数または複素ベクトルｘ＝（ｘ０，．．．．．．．．．．，ｘｎ−１）から成る。アルゴリズムはｙ＝（ｙ０，．．．．．．．．．．，ｙｎ−１）＝Ａ・ｘを計算する。
【０４０６】
行列のエントリが、すべての０・ｉ＜ｒ，０・ｊ＜ｎに対して、次の０−１の２進の表現で与えられると仮定される。
【０４０７】
2004511046.tif 000212
ここで、すべての−ｍ２・ｋ・ｍ１に対しｔｉｊｋ∈｛０，１｝
第１段階だけが、０−１−行列のインプリメンテーションのステージと異なっており、このステージについてだけ記述される必要がある。０−１−行列のインプリメンテーションのセクションにリストされた定義はすべて、ここで適用可能である。さらに次のｒ次元の｛０，１｝ベクトルをすべての０・ｊ＜ｍ、−ｍ２・ｋ・ｍ１に対して定義する。
【０４０８】
2004511046.tif 000213
１．初期化：０から２ｒ−１までのあらゆるアドレスに０を入れる。
２．第１段階：
2004511046.tif 000214
３．主要部分：
｛０，１｝行列のアルゴリズムのｒ行に対する主要部分として進行し、そのデータはその演算処理の最後に同じアドレスに格納される。
【０４０９】
複雑性
ｉ）上記インプリメンテーションでの基礎的ステップは、０−１−２進のインプリメンテーションと同じである、すなわち、ソースと呼ばれるメモリの１つの場所から数を読み出し、それを宛先と呼ばれるメモリの別の場所に置かれた数に加える。
ｉｉ）上記コードに基づく装置は、Ａ・ｘの演算を完了するために次の数の基礎的ステップを要求するであろう。
（１）第１段階に対して、
2004511046.tif 000215
個の基礎的ステップが必要である。
（２）コードの主要部分は、ｒラインを備えた０−１の２進コードの主要部分によって行われる。すなわち、それはＣ０，１ｒ個の基礎的ステップを必要とする。
（３）Ａ・ｘの演算全体は、このように次の回数の基礎的ステップを要求する。
【０４１０】
2004511046.tif 000216
例７：実数の行列、２進のＵ表現
本発明の次の好適な実施例は、行列エントリの２進Ｕ表現を備えた本発明の実数行列の面からみたインプリメンテーションである。データは、ｒ×ｎ実数行列Ａ＝（ａｉｊ：０・ｉ＜ｒ，０・ｊ＜ｎ）、および入力の実数または複素ベクトルｘ＝（ｘ０，．．．．．．．．．．，ｘｎ−１）から成る。そのアルゴリズムはｙ＝（ｙ０，．．．．．．．．．．，ｙｎ−１）＝Ａ・ｘを計算する。
【０４１１】
行列のエントリは、すべての０・ｉ＜ｒ，０・ｊ＜ｎに対して、次のＵ表現で与えられると仮定される。
【０４１２】
2004511046.tif 000217
ここで、すべての−ｍ２−１・ｋ・ｍ１に対して、ｔｉｊｋ∈Ｕ
この表現の存在は、本発明の実数行列の面から既に言及されている。第１段階だけが、Ｕ行列のインプリメンテーションのステージと異なっており、このステージについてだけ記述される必要がある。Ｕ行列のインプリメンテーションのセクションにリストされた定義はすべて、ここで適用可能である。さらに次のｒ次元のＵベクトルをすべての０・ｊ＜ｎ、−ｍ２・ｋ・ｍ１に対して定義する。
【０４１３】
2004511046.tif 000218
１．初期化：０から２ｒ＋ｒ−１までのあらゆるアドレスに０を入れる。
２．第１段階
2004511046.tif 000219
３．主要部分：
ｕ行列のインプリメンテーションのアルゴリズムのｒ行に対する主要部分として進行し、そのデータはその演算処理の最後に同じアドレスに格納される。
【０４１４】
複雑性
ｉ）上記インプリメンテーションでの基礎的ステップは、Ｕインプリメンテーションと同じである、すなわち、ソースと呼ばれるメモリの１つの場所から数を読み出し、１または−１である符号をそれに掛けて、次に、その結果を宛先と呼ばれるメモリの別の場所に置かれた数に加える。
ｉｉ）上記コードに基づく装置は、Ａ・ｘの演算を完了するために次の数の基礎的ステップを要求するであろう。
（１）第１段階に対して、
2004511046.tif 000220
個の基礎的ステップが必要である。
（２）コードの主要部分は、ｒラインを備えたＵコードの上記インプリメンテーションの主要部分によって行われる。すなわち、それはＣｕｒ個の基礎的ステップを必要とする。
（３）Ａ・ｘの演算全体は、このように次の回数の基礎的ステップを要求する。
【０４１５】
2004511046.tif 000221
図４は、本発明の好適な実施例に従って、加算の回数を削減した線形変換を行なう典型的な装置のブロック図である。装置５００は、２つの入力および１つの出力を備えた乗算器１０、入力のうちの１つを選択しその出力に転送するためのマルチプレクサ（ＭＵＸ）９、２つの入力および１つの出力を備える加算器１１、その後ろに続く２つのアドレス・バス・ライン「ａｄｄ＿ａ」および「ａｄｄ＿ｂ」および２つの出力、「ｄａｔａ＿ａ」および「ｄａｔａ＿ｂ」を有するデュアル・ポート・ランダム・アクセス・メモリ（ＤＰＲＡＭ）１３を含む。ＭＵＸの動作は、アドレス・ジェネレータ５０１によって制御され、それは、さらにＤＰＲＡＭ１３中のメモリ・アドレスへのアクセスを可能にする。アドレス・ジェネレータの動作は、カウンタ３によって制御される。
【０４１６】
乗算器１０の出力は、ＭＵＸ９の１つの入力「Ｃ」に接続される。ＭＵＸ９の出力は、加算器１１の１つの入力「Ａ」に接続される。加算器１１の出力は、ＤＰＲＡＭ１３の入力に接続される。ＤＰＲＡＭ１３の１つの出力「ｄａｔａ＿ａ」は、加算器１１の入力「Ｂ」に接続される。ＤＰＲＡＭ１３の別の出力「ｄａｔａ＿ｂ」は、乗算器１２の入力「Ｅ」に接続される。乗算器１２の別の入力「Ｆ」は、アドレス・ジェネレータ５０１の出力「ｓｉｇｎ」に接続される。乗算器１２の出力は、ＭＵＸ９の別の入力「Ｄ」に接続される。カウンタ３は、アドレス・ジェネレータ５０１の２つの入力に接続される。ジェネレータ５０１の出力「Ｈ」は、乗算器１２の「ｓｉｇｎ」入力に接続される。ジェネレータ５０１の出力Ｇは、ＭＵＸ９の制御入力「Ｓ」に接続される。ジェネレータ５０１の出力「Ｊ」は、ＤＰＲＡＭ１３の第１のアドレス入力「ａｄｄ＿ａ」に接続される。ジェネレータ５０１の他の出力「Ｉ」は、ＤＰＲＡＭ１３の第２のアドレス入力「ａｄｄ＿ｂ」に接続される。変換行列は、オプションのＲＡＭ／ＲＯＭ１に格納され、それはアドレス・ジェネレータ５０１にコードのシリーズ（行列中の行のビット）Ｄ０，Ｄ１，．．．．．．．．．．，Ｄｓを供給するとともに、最上桁のビットＤ０を乗算器１０に送る。入力ベクトルは別のオプションのＲＡＭ／ＲＯＭ　２に格納されることがあるとともに、それは入力信号のサンプルで乗算器に１０を与える。代わって、入力ベクトルの要素および変換行列中のそれらに対応する要素が装置５００へ同期して提供される場合、格納メモリ１，２を除去することができる。例えば、これらの要素は、ＡＤＣまたはシーケンス・ジェネレータによって提供されてもよい。装置５００の全てのコンポーネントは、「ｃｌｏｃｋ＿ｉｎ」入力を介して共通クロックによって制御される。
【０４１７】
同じ入力セット［ｘ１　ｘ２　．．．．．．．．．．　 ｘｎ］、同じ異なるコードＤ０，Ｄ１，．．．．．．．．．．，Ｄｓを表わす同じＵ行列（それはｎ行を含む）を使用する場合、装置の動作は、以下に説明される。装置５００の動作は２つのステージ、すなわち、入力データ（つまりサンプル［ｘ１　ｘ２　．．．．．．．．．．　 ｘｎ］）が受け取られ、各コンポーネントおよび変換行列のその対応する要素の積が計算され、ＤＰＲＡＭ１３に格納される「Ｓｔａｇｅ １」と表示された第１ステージ、および、入力データが加算器９に入ることをブロックしている間、受信データが処理される「Ｓｔａｇｅ ２」と表示された第２ステージに分割される。カウンタ３は動作の蓄積数を係数するとともに、そのカウント（カウンタの出力）は２つのステージを識別するために用いられる。「Ｓｔａｇｅ １」の動作回数は入力ベクトルの長さｎである。この数を越える動作は「Ｓｔａｇｅ ２」と関連する。
【０４１８】
本発明の好適な実施例によれば、アドレス・ジェネレータ５０１は、比較器４を含み、それはカウンタ３の出力にリンクされる。その比較器は、カウンタ３の現在の出力を読み、それを入力ベクトルの長さｎと比較し、現在の動作が「Ｓｔａｇｅ １」または「Ｓｔａｇｅ ２」の中で実行されるかどうか示す対応信号を提供する。この信号は、入力「Ｃ」と「Ｄ」の間で切り替わるためにＭＵＸ９の入力「Ｓ」を制御するために使用される。
【０４１９】
アドレス・ジェネレータ５０１はさらに予めプログラムされた値を格納する非同期メモリ５（例えばＲＯＭ）を含み、入力アドレスが「ａｄｄ＿ａ」および「ａｄｄ＿ｂ」を介してＤＰＲＡＭ１３中のアドレスを決めるために参照テーブル（ＬＵＴ）としてそれらの内容の処理のために使用される。ＬＵＴのサイズは（Ｃ−ｎ）×（１＋２ｒ）であり、その内容は３つのフィールド、「ソース」フィールド、「符号」フィールド、および「宛先」フィールドからなる。各動作（つまり、カウンタ３によって計数される各クロック・サイクル）については、３つの対応するソース符号および宛先値がある。ソース・フィールドは、特定の列における２つの部分の正規化と関係する指示と同様に、スプリットされた（分割された）変換行列の各列と関係する情報からなる。ソース・フィールドは、ＤＰＲＡＭ１３上の入力「ａｄｄ＿ｂ」の値を決定する。符号フィールドは個々のスプリット列またはサブ列中のより低いコンポーネントを表わす。宛先フィールドは、対応するアドレスのどの内容が処理のために選択されたかに従って、ＤＰＲＡＭ１３上の入力「ａｄｄ＿ａ」の値を決定する。
【０４２０】
アドレス・ジェネレータはさらに１セットのｓ（ｓ＝ｒ−１）インバータ６１，６２，．．．．．．．．．．，６ｓを含み、その各々はビットＤ０，Ｄ１，．．．．．．．．．．，Ｄｓのシリーズにそれぞれ接続された入力を含む。各インバータの出力は、ｓマルチプレクサのセット、７１，７２，．．．．．．．．．．，７ｓからの対応ＭＵＸの１つの入力に接続される。ビットＤ０，Ｄ１，．．．．．．．．．．，Ｄｓのシリーズは、さらにｓマルチプレクサのセット、７１，７２，．．．．．．．．．．，７ｓからの対応ＭＵＸの別の入力に供給される。セット７１，７２，．．．．．．．．．．，７ｓからの各ＭＵＸの出力は、最上位ビットＤ０の値によって制御され、セットＤ１，．．．．．．．．．．，ＤｓをＤＰＲＡＭ１３の入力「ａｄｄｒｅｓｓ＿ａ」へ変化させないであるいは反転（つまりＤ’１，．．．．．．．．．．，Ｄ’ｓ）して転送を可能にする。セットＤ１，．．．．．．．．．．，Ｄｓ（またはＤ’１，．．．．．．．．．．，Ｄ’ｓ）は、ＬＵＴから到着する「ａｄｄ＿ａ」にＭＳＢ（ｒ番目のビット）によって供給される追加のマルチプレクサ８ｒと共に、ｓマルチプレクサの対応するセット８１，８２，．．．．．．．．．．，８ｓの１つの入力に入力される。比較器４の出力によって、「ａｄｄ＿ａ」がセット７１，７２，．．．．．．．．．．，７ｓからまたはＬＵＴから到着する選択を可能にする。入力「ａｄｄ＿ａ」（つまり宛先）は、加算器１１の入力「Ｂ」に供給するＤＰＲＡＭ１３の第１の出力「ｄａｔａ＿ａ」を制御する。ＬＵＴ（つまりソース）から得られた入力「ａｄｄ＿ｂ」はＤＰＲＡＭ　１３の第２の出力「ｄａｔａ＿ｂ」を制御し、それは乗算器１２の入力「Ｅ」に供給され、「ｄａｔａ＿ｂ」の各値をＬＵＴから抽出された対応する「符号」値と乗算し、その積を乗算器１２の入力「Ｄ」に供給する。ＤＰＲＡＭ１３中の「書込み」動作は同期しており、つまり、各セルの内容はクロックレート（例えば、クロック信号が立ち上がる時）に従って上書きされる。他方では、ＤＰＲＡＭ１３中の「読込み」動作は非同期であり、つまり、クロックにかかわらず、アドレス入力が変更されるときに、各出力は変更される。
【０４２１】
ステージ１の動作
このステージでは、ステージ１が動作を実行している間、カウンタ３は１シンボル時間（ｎクロック・サイクル）を計数し始める。ステージ１の間、ＭＵＸ９によって、入力「Ｄ」をブロックしている間、入力「Ｃ」からのデータ・フローをその出力および加算器１１の入力「Ａ」へ流れることを可能にする。入力シンボル［ｘ１　ｘ２　．．．．．．．．．．　 ｘｎ］は、乗算器１０の１つの入力へ提供される。そのコードのＭＳＢ　Ｄ０は、乗算器１０の別の入力へ提供される。このステージでは、入力「ａｄｄ＿ａ」によって決定される宛先（出力「ｄａｔａ＿ａ」）は、ＤＰＲＡＭ１３から抽出され、入力ベクトルのコンポーネント［ｘ１　ｘ２　．．．．．．．．．．　 ｘｎ］に加えられ、ＭＳＢ　Ｄ０を乗じられる。カウンタ３は、現在のシンボル時間を計数してきたが、アドレス・ジェネレータ比較器４へおよびＲＯＭ５へ現在のシンボル時間が終了し、比較器４がＭＵＸ９の入力選択を入力「Ｃ」からの別の入力「Ｄ」に切り替えるという指示を提供する。同様に、比較器４は、ＬＵＴからデータをＲＡＭ１からのデータへ選ぶために、マルチプレクサ８１，８２，．．．．．．．．．．，８ｓを駆動する。
【０４２２】
ステージ２の動作
このステージでは、ステージ２が動作を実行している間、カウンタ３は次のシンボル時間を計数し始める。ステージ２の間、ＭＵＸ９によって、入力「Ｃ」をブロックしている間、入力「Ｄ」からのデータ・フローをその出力および加算器１１の入力「Ａ」へ流れることを可能にする。このステージにおいて、各クロック・サイクルで、ＤＰＲＡＭ１３中の選択されたアドレスは、ソースを表わす「ａｄｄ＿ｂ」によってアクセスされる。ソース・データは、ＤＰＲＡＭ１３の第２の出力「ｄａｔａ＿ｂ」から、乗算器１２の入力「Ｅ」に供給され、そこでＬＵＴから抽出された「符合」値が乗じられる。この積はＭＵＸ９に入力「Ｄ」に供給され、それによって、加算器１１の入力「Ａ」に現われる。同時に、現在の宛先値の内容が加算器１１の入力「Ｂ」に現われる。２つの値は加算器１１によって加えられ、その結果は、ＤＰＲＡＭ１３（それは前の宛先値に相当する）中の同じアドレスに格納される。この合計プロセスの終わりに、対応するｒ変換ポイント（ｙｉ’ｓ）が、アドレス＃０および＃２ｒ−１から（２ｒ−１＋ｒ−２）のＤＰＲＡＭ１３に格納される。すべての変換ポイント（ｙｉ’ｓ）が計算され、かつＤＰＲＡＭ１３の異なるアドレスに格納された後、（前もって定義したカウントに従って）ステージ２が終了するという指示をクロックが提供するまで、結果としてこのプロセスは継続される。そのときに、現在のシンボル時間も終了し、また、比較器４はＭＵＸ９の入力選択を入力「Ｄ」から別の入力「Ｃ」へ切り替え、そしてＲＡＭ１からのデータをむしろＬＵＴからデータへ選ぶために、マルチプレクサ８１，８２，．．．．．．．．．．，８ｓを駆動し、それによって、ステージ１で再び動作するために装置５００を切り替える。
【０４２３】
上記方法を実行するために使用される装置の１つの実施例は図５で見られる。図５は、ｒ×ｎ　Ｕ行列Ａをｎ次元のベクトルＸで乗じた積のインプリメンテーションを図示する。行列は０または１の表現を含み、ここで０が１に相当し、１が−１に相当する。
【０４２４】
この実例において、ベクトルは実数であり、ｖビットは各コンポーネント特定する。次の構成において、行列Ａは要素１（ＲＡＭまたはＲＯＭ）に格納され、ベクトルＸは要素２（ＲＡＭまたはＲＯＭ）に格納される。行列とベクトルは、ＡＤＣまたはいくつかのシーケンス・ジェネレータなどに類するメモリ・デバイスまたは同期させられたソースのような内部または外部装置から生成される。
【０４２５】
モジュール１，２，３，１３を制御するクロックは、全体のシステムを同期させる。Ｃが以下のように定義される場合、モジュール３は０からＣまで計数するカウンタである。
【０４２６】
【数１０７】
2004511046.tif 000222
【０４２７】
ステージ１では、要素３から来るアドレスに従って、要素１および２から入って来る信号は要素１３に挿入される、ここで、各アドレスはｌｏｇ２ｎリスト重要ビット（ｌｉｓｔ ｓｉｇｎｉｆｉｃａｎｔ ｂｉｔ）を含む。
【０４２８】
加えて、カウンタは、（Ｃ−ｎ）×（１＋ｒ＋ｒ）のサイズの非同期ＲＯＭ（要素５）のアドレス・ジェネレータとして使用される。カウンタのすべてのビットは比較器である要素４に入り、現在のカウントがｎより大きいかどうかをチェックする。要素５は３つのフィールドを包含する、すなわち、符号、ソース、宛先である。ＲＯＭにおけるラインの順序は、ステージ２の第１の動作がｎサイクルの後にカウンタによって引き起こされるようになされる。
【０４２９】
シンタックスの目的のために、ｓ＝ｒ−１を定義する。データ・バスは、要素１のビットＤ１−Ｄｓから要素６＿１−６＿ｓ（それらはインバータである）にそれぞれ入る。要素７１−７ｓは、Ｄ０の状態に従って、Ｄ１−Ｄｓと６１−６ｓの出力との間を選択する。
【０４３０】
2004511046.tif 000223
要素８＿１−８＿ｓは、要素４（ｓｔａｇｅ１＿２ｎ）中の比較器の出力の状態に従って、７＿１−７＿ｓと要素５（ａｄｄ＿ａ＝宛先）のｌｏｇ２（ｎ）ＬＳＢ出力との間を選択する。
【０４３１】
2004511046.tif 000224
要素８＿ｒは、「０」と要素５のｒビット（ａｄｄ＿ａ　ＭＳＢ）との間を選択する。Ｓｔａｇｅ １＿２ｎ＝０ ＝＞ ８＿ｒ＝ａｄｄ＿ａ ＭＳＢ， Ｓｔａｇｅ １＿２ｎ＝１ ＝＞ ８＿ｒ＝０．　８＿１−８＿ｒからの出力は、要素１３の第１のアドレスバスとして使用され、それは、（２ｒ−１＋ｒ−１）×（Ｖ＋ｌｏｇ２ｎ）のサイズのデュアル・ポートＲＡＭである。このアドレスは、要素１３からの出力であるｄａｔａ＿ａバス、およびさらに要素１３への入力であるｄａｔａ＿ｉｎバスの宛先を定義する。
【０４３２】
Ａｄｄ＿ｂ（それは要素５（ソース・フィールド）の出力である）は、要素１３の第２のアドレス・バスである（このアドレスは、要素１３からの出力であるｄａｔａ＿ｂバスを制御する）。
【０４３３】
符号は要素１３からの単一ビットの出力であり、（乗算器である）要素１２でｄａｔａ＿ｂと乗算する。
【０４３４】
要素１３に関して入力であるｄａｔａ＿ｉｎバスは、要素１１から到着し、それは、ｄａｔａ＿ａおよび要素９の出力をともに合計する加算器である。ｄａｔａ＿ａとｄａｔａ＿ｂの読込み動作が非同期である間、ｄａｔａ＿ｉｎは同期した方法でａｄｄ＿ａ宛先へ行く。
【０４３５】
要素１３の動作に先立って、ゼロの挿入によって開始する。要素９は、要素１０と要素の１２の出力との間を選択する。要素１０は、要素２からのデータ・バスを要素１のＬＳＢで掛ける。Ｃサイクルの後、結果としてのベクトルは、アドレス０およびアドレス２ｒ−１から（２ｒ−１＋ｒ−２）の要素１３に格納される。
【０４３６】
本発明の多数の変形および修正は、当業者に容易に明らかになるであろう。従って、本発明は、その精神またはその本質的特質から逸脱せずに、他の特定の形式で具体化されてもよい。詳細な実施例は、単に図示されたものとして尊重され、限定的なものではなく、したがって、本発明の範囲は前述の記述によるのではなく、添付された請求項によって示される。請求項の均等の解釈および範囲内にある変更はすべて、本請求項の範囲内に包含される。
【図面の簡単な説明】
【図１】本発明の好適な実施例に従って、０−１−２進変換行列を使用して変換を行なう装置によって使用されたメモリの内容を更新する動作を概略的に図示する。
【図２】本発明の好適な実施例に従って、Ｕ変換行列を使用して変換を行なう装置によって使用されたメモリの内容を更新する動作を概略的に図示する。
【図３】本発明の好適な実施例に従って、トップリッツ変換行列を使用して変換を行なう装置によって使用されたメモリの内容を更新する動作を概略的に図示する。
【図４】本発明の好適な実施例に従って、加算の削減数を備えた線形変換を行なうための典型的な装置のブロック図である。
【図５】本発明の好適な実施例に従って、ｒ×ｎのＵ行列Ａをｎ次元のベクトルＸで乗じた積のインプリメンテーションの例を図示する。
【図１】
2004511046.tif 000225
【図２】
2004511046.tif 000226
【図３】
2004511046.tif 000227
【図４】
2004511046.tif 000228
【図５】
2004511046.tif 000229
【国際公開パンフレット】
2004511046.tif 000230
2004511046.tif 000231
2004511046.tif 000232
2004511046.tif 000233
2004511046.tif 000234
2004511046.tif 000235
2004511046.tif 000236
2004511046.tif 000237
2004511046.tif 000238
2004511046.tif 000239
2004511046.tif 000240
2004511046.tif 000241
2004511046.tif 000242
2004511046.tif 000243
2004511046.tif 000244
2004511046.tif 000245
2004511046.tif 000246
2004511046.tif 000247
2004511046.tif 000248
2004511046.tif 000249
2004511046.tif 000250
2004511046.tif 000251
2004511046.tif 000252
2004511046.tif 000253
2004511046.tif 000254
2004511046.tif 000255
2004511046.tif 000256
2004511046.tif 000257
2004511046.tif 000258
2004511046.tif 000259
2004511046.tif 000260
2004511046.tif 000261
2004511046.tif 000262
2004511046.tif 000263
2004511046.tif 000264
2004511046.tif 000265
2004511046.tif 000266
2004511046.tif 000267
2004511046.tif 000268
2004511046.tif 000269
2004511046.tif 000270
2004511046.tif 000271
2004511046.tif 000272
2004511046.tif 000273
2004511046.tif 000274
2004511046.tif 000275
2004511046.tif 000276
2004511046.tif 000277
2004511046.tif 000278
2004511046.tif 000279
2004511046.tif 000280
2004511046.tif 000281
2004511046.tif 000282
2004511046.tif 000283
2004511046.tif 000284
2004511046.tif 000285
2004511046.tif 000286
2004511046.tif 000287
2004511046.tif 000288
2004511046.tif 000289
2004511046.tif 000290
2004511046.tif 000291
2004511046.tif 000292
2004511046.tif 000293
2004511046.tif 000294
2004511046.tif 000295
2004511046.tif 000296
2004511046.tif 000297
2004511046.tif 000298
2004511046.tif 000299
2004511046.tif 000300
2004511046.tif 000301
2004511046.tif 000302
2004511046.tif 000303
2004511046.tif 000304
2004511046.tif 000305
2004511046.tif 000306
2004511046.tif 000307
2004511046.tif 000308
2004511046.tif 000309
2004511046.tif 000310
2004511046.tif 000311
2004511046.tif 000312
2004511046.tif 000313
2004511046.tif 000314
2004511046.tif 000315
2004511046.tif 000316
2004511046.tif 000317
2004511046.tif 000318
2004511046.tif 000319
2004511046.tif 000320
2004511046.tif 000321
2004511046.tif 000322
2004511046.tif 000323
【国際公開パンフレット（コレクトバージョン）】
2004511046.tif 000324
2004511046.tif 000325
2004511046.tif 000326
2004511046.tif 000327
2004511046.tif 000328
2004511046.tif 000329
2004511046.tif 000330
2004511046.tif 000331
2004511046.tif 000332
2004511046.tif 000333
2004511046.tif 000334
2004511046.tif 000335
2004511046.tif 000336
2004511046.tif 000337
2004511046.tif 000338
2004511046.tif 000339
2004511046.tif 000340
2004511046.tif 000341
2004511046.tif 000342
2004511046.tif 000343
2004511046.tif 000344
2004511046.tif 000345
2004511046.tif 000346
2004511046.tif 000347
2004511046.tif 000348
2004511046.tif 000349
2004511046.tif 000350
2004511046.tif 000351
2004511046.tif 000352
2004511046.tif 000353
2004511046.tif 000354
2004511046.tif 000355
2004511046.tif 000356
2004511046.tif 000357
2004511046.tif 000358
2004511046.tif 000359
2004511046.tif 000360
2004511046.tif 000361
2004511046.tif 000362
2004511046.tif 000363
2004511046.tif 000364
2004511046.tif 000365
2004511046.tif 000366
2004511046.tif 000367
2004511046.tif 000368
2004511046.tif 000369
2004511046.tif 000370
2004511046.tif 000371
2004511046.tif 000372
2004511046.tif 000373
2004511046.tif 000374
2004511046.tif 000375
2004511046.tif 000376
2004511046.tif 000377
2004511046.tif 000378
2004511046.tif 000379
2004511046.tif 000380
2004511046.tif 000381
2004511046.tif 000382
2004511046.tif 000383
2004511046.tif 000384
2004511046.tif 000385
2004511046.tif 000386
2004511046.tif 000387
2004511046.tif 000388
2004511046.tif 000389
2004511046.tif 000390
2004511046.tif 000391
2004511046.tif 000392
2004511046.tif 000393
2004511046.tif 000394
2004511046.tif 000395
2004511046.tif 000396
2004511046.tif 000397
2004511046.tif 000398
2004511046.tif 000399
2004511046.tif 000400
2004511046.tif 000401
2004511046.tif 000402
2004511046.tif 000403
2004511046.tif 000404
2004511046.tif 000405
2004511046.tif 000406
2004511046.tif 000407
2004511046.tif 000408
2004511046.tif 000409
2004511046.tif 000410
2004511046.tif 000411
2004511046.tif 000412
2004511046.tif 000413
2004511046.tif 000414
2004511046.tif 000415
2004511046.tif 000416
2004511046.tif 000417
2004511046.tif 000418
【国際公開パンフレット（コレクトバージョン）】
2004511046.tif 000419
【国際調査報告】
2004511046.tif 000420
2004511046.tif 000421