(57)【特許請求の範囲】
【請求項１】
共分散行列の第１の行を生成する装置であって、
複数個のサンプルを表す、前記共分散行列の部分ではない値のアレイを有するメモリと、
そのメモリに結合される環状のバッファとを含み、その環状のバッファは、予め定められた数のメモリ位置を与えるように構成され、さらに、
前記メモリおよび前記環状のバッファに結合される乗算アキュムレータと、
前記共分散行列の第１の行の第１のエレメントを生成するために、前記メモリから前記乗算アキュムレータへ、アレイの値の順次部分集合を転送する手段とを備え、前記順次部分集合は第１のアドレスジェネレータに基づいて選択され、前記メモリからのアレイの値の順次部分集合は、前記環状のバッファを充足するために前記環状のバッファに同時に転送され、さらに、
前記乗算アキュムレータへ、前記メモリからのアレイの値の、第１の一連の順次部分集合と、前記環状のバッファからのアレイの値の、第２の一連の順次部分集合とを同時に転送し、前記共分散行列の第１の行の第１のエレメントの残りのエレメントを生成する手段を備え、前記第１の一連の順次部分集合の各々は前記第１のアドレスジェネレータに基づいて選択され、前記第２の一連の順次部分集合の各々は第２のアドレスジェネレータに基づいて選択され、前記第１の一連の順次部分集合の各々は、互いに関連する前記第２の一連の順次部分集合と同時に、前記乗算アキュムレータへ入力として与えられ、
前記第１のアドレスジェネレータは、アレイの値を有する前記メモリ内のアドレスを示すように構成され、前記第２のアドレスジェネレータは、前記環状のバッファ内のアドレスを示すように構成される、装置。
【請求項２】
前記環状のバッファが、二重ポートレジスタファイルを含み、そのレジスタファイルは読出アドレスジェネレータおよび書込アドレスジェネレータを含み、それらのアドレスジェネレータはラップアラウンドするように構成されている、請求項１に記載の装置。
【請求項３】
共分散行列の上部または下部の三角形部分を生成する装置であって、
第１のおよび第２のメモリを含み、第１のメモリは複数個のサンプルを表す、前記共分散行列の部分ではない値のアレイを含み、さらに、
前記第１のメモリに結合される環状のバッファを含み、そのバッファは、初めは、第１
の予め定められた数のメモリ位置を与えるように構成され、さらに、
前記第１のおよび第２のメモリ、ならびに前記環状のバッファに結合される乗算アキュムレータと、
前記第２のメモリおよび前記乗算アキュムレータに結合される演算論理装置と、
前記第１のメモリから前記乗算アキュムレータへ、前記アレイの値の順次部分集合を転送し、前記共分散行列の第１の行の第１のエレメントを生成する手段とを備え、前記順次部分集合は第１のアドレスジェネレータに基づいて選択され、前記メモリからのアレイの値の順次部分集合は、前記環状のバッファを充足するために前記環状のバッファに同時に転送され、さらに、
前記第２のメモリ内に、前記共分散行列の第１の行の第１のエレメントを記憶する手段と、
前記乗算アキュムレータへ、前記第１のメモリからの、前記アレイの値の第１の一連の順次部分集合、および前記環状のバッファからの前記アレイの値の第２の一連の順次部分集合を、同時に転送し、前記乗算アキュムレータの出力において、前記共分散行列の第１の行の第１のエレメントの残りのエレメントを生成する手段とを備え、前記第１の一連の順次部分集合の各々は前記第１のアドレスジェネレータに基づいて選択され、前記第２の一連の順次部分集合の各々は第２のアドレスジェネレータに基づいて選択され、前記第１の一連の順次部分集合の各々は、互いに関連する前記第２の一連の順次部分集合と同時に、前記乗算アキュムレータへ入力として与えられ、さらに、
前記第２のメモリ内に、前記共分散行列の第１の行の第１のエレメントの残りのエレメントを記憶する手段と、
前記演算論理装置内で、前記共分散行列の上部または下部の三角形部分の残りのエレメントを生成する手段と、
前記第２のメモリ内で、前記共分散行列の上部または下部の三角形部分の残りのエレメントを記憶する手段とを含み、
前記第１のアドレスジェネレータは、アレイの値を有する前記メモリ内のアドレスを示すように構成され、前記第２のアドレスジェネレータは、前記環状のバッファ内のアドレスを示すように構成される、装置。
【請求項４】
前記環状のバッファが、読出アドレスジェネレータおよび書込アドレスジェネレータを有する、二重ポートレジスタファイルを含み、それらのアドレスジェネレータはラップアラウンドするように構成される、請求項３に記載の装置。
【請求項５】
前記演算論理装置内で生成する手段が、前記第１のメモリおよび前記環状のバッファファイルから、前記乗算アキュムレータへ、データを選択的に適用する手段と、前記第２のメモリおよび前記乗算アキュムレータから、前記演算論理装置へ、データを選択的に適用する手段とを含む、請求項３に記載の装置。
【請求項６】
共分散行列の上部または下部の三角形部分の残りのエレメントが、前記共分散行列の第１の行が生成される間に、前記演算論理装置内で生成され、演算論理装置内で生成する手段が、前記第２のメモリからその演算論理装置へ、データを選択的に適用する手段を含む、請求項３に記載の装置。
【請求項７】
共分散行列を生成する方法であって、
複数個のサンプルを表す、前記共分散行列の部分ではない値のアレイを有する第１のメモリを設けるステップと、
乗算アキュムレータを設けるステップと、
予め定められた深さで環状のバッファを設けるステップと、
乗算アキュムレータ内でその共分散行列の第１の行の第１のエレメントを生成するステップと、
前記共分散行列の第２のメモリ内でその第１のエレメントを記憶するステップと、
前記第１のメモリ内に記憶された値と前記環状のバッファ内に記憶された値とを用いて、前記共分散行列の第１の行の第１のエレメントの残りのエレメントを生成するステップと、
前記共分散行列の前記第２のメモリ内に、第１の行の第１のエレメントの残りのエレメントを記憶するステップと、
演算論理装置内で、前記共分散行列の上部または下部の三角形部分の残りのエレメントを、対角線ごとに生成するステップと、
前記共分散行列の前記第２のメモリ内に、前記共分散行列の上部または下部の三角形部分の残りのエレメントを記憶するステップとを含む方法。
【請求項８】
前記第１のエレメントを生成するステップは、前記第１のメモリから前記乗算アキュムレータへ、前記アレイの値の順次部分集合を転送するそのステップを含む、請求項７に記載の方法。
【請求項９】
前記第１の行の第１のエレメントの残りのエレメントを生成するステップは、前記共分散行列の前記第１のメモリから前記乗算アキュムレータへ、前記アレイの値の、第１の一連の順次部分集合を転送する一方で、前記環状のバッファから前記乗算アキュムレータへ、前記アレイの値の、第２の一連の順次部分集合を同時に転送するステップを含む、請求項７に記載の方法。
【請求項１０】
前記共分散行列の上部または下部の三角形部分の残りのエレメントを対角線ごとに生成するステップが、前記共分散行列の第１の行の第１のエレメントの残りのエレメントを生成するステップと同時に行なわれる、請求項７に記載の方法。
【請求項１１】
共分散行列の第１の行のエレメントを生成する方法であって、
複数個のサンプルを表す、前記共分散行列の部分ではない値のアレイを有する、第１のメモリを設けるステップと、
乗算アキュムレータを設けるステップと、
予め定められた深さの環状のバッファを設けるステップと、
前記第１のメモリから前記乗算アキュムレータへ、前記アレイの値の順次部分集合を連続的に入力することにより、前記乗算アキュムレータ内で、前記共分散行列の第１の行の第１のエレメントを生成するステップとを含み、前記順次部分集合は第１のアドレスジェネレータに基づいて選択され、前記メモリからのアレイの値の順次部分集合は、前記環状のバッファを充足するために前記環状のバッファに同時に転送し、さらに、
前記共分散行列の第２のメモリ内に前記第１のエレメントを記憶するステップと、
前記第１のメモリから、前記乗算アキュムレータへ、前記アレイの値の、第１の一連の順次部分集合を連続的に入力する一方で前記環状のバッファから前記乗算アキュムレータへ、前記アレイの値の、第２の一連の順次部分集合を同時に入力することにより、前記共分散行列の第１の行の第１のエレメントの残りのエレメントを生成するステップとを含み、前記第１の一連の順次部分集合の各々は前記第１のアドレスジェネレータに基づいて選択され、前記第２の一連の順次部分集合の各々は第２のアドレスジェネレータに基づいて選択され、前記第１の一連の順次部分集合の各々は、互いに関連する前記第２の一連の順次部分集合と同時に、前記乗算アキュムレータへ入力として与えられ、さらに、
前記第２のメモリ内に、前記第１の行の第１のエレメントの残りのエレメントを記憶するステップを含み、
前記第１のアドレスジェネレータは、アレイの値を有する前記メモリ内のアドレスを示すように構成され、前記第２のアドレスジェネレータは、前記環状のバッファ内のアドレスを示すように構成される、方法。
【請求項１２】
共分散行列の上部または下部の三角形部分の第１の行を生成する方法であって、
複数個のサンプルを表す、前記共分散行列の部分ではない値のアレイを有するメモリを設けるステップと、
乗算アキュムレータを設けるステップと、
予め定められた深さの環状のバッファを設けるステップと、
前記メモリにおける第１のアドレスジェネレータに基づいて、複数個のサンプルを表す、前記メモリからの一連の値を、前記乗算アキュムレータおよび前記環状のバッファへ同時に適用することにより、前記共分散行列の前記第１の行の第１のエレメントを生成する
ステップと、
前記メモリにおける前記第１のアドレスジェネレータに基づいて、前記乗算アキュムレータおよび前記環状のバッファへ、前記メモリからの第１の一連の値を適用するステップ、ならびに、前記環状のバッファにおける第２のアドレスジェネレータに基づいて、前記乗算アキュムレータへ前記環状のバッファからの第２の一連の値を適用するステップを同時に実行することにより、前記第１の行の第１のエレメントの残りのエレメントの各々を生成するステップとを含み、
前記第１のアドレスジェネレータは、アレイの値を有する前記メモリ内のアドレスを示すように構成され、前記第２のアドレスジェネレータは、前記環状のバッファ内のアドレスを示すように構成される、方法。
【請求項１３】
共分散行列の三角形部分を生成する方法であって、その三角形部分は、第１の行のエレメントおよびエレメントの複数個の対角線アレイを規定し、前記方法は、
第１のメモリおよび第２のメモリを設けるステップを含み、その第１のメモリはサンプルを表す、前記共分散行列の部分ではない複数個の値を含み、さらに
乗算アキュムレータを設けるステップと、
予め定められた深さの環状のバッファを設けるステップと、
前記乗算アキュムレータおよび前記環状のバッファへ、第１のアドレスジェネレータに基づいて検索された、前記第１のメモリからの一連の値を同時に適用することにより、前記共分散行列の前記第１の行の第１のエレメントを生成するステップと、
前記共分散行列の前記第２のメモリ内に、前記第１の行の第１のエレメントを記憶するステップと、
前記乗算アキュムレータへ、前記第１のアドレスジェネレータに基づいて検索された、前記第１のメモリからの第１の一連の値、および第２のアドレスジェネレータに基づいて検索された、前記環状のバッファからの第２の一連の値を同時に適用することにより、前記第１の行の第１のエレメントの残りのエレメントの各々を生成するステップと、
前記共分散行列の前記第２のメモリ内に、前記第１の行の第１のエレメントの残りのエレメントの各々を記憶するステップと、
演算論理装置を設けるステップと、
その演算論理装置内で、前記共分散行列の対角線アレイの各々の残りのエレメントを、対角線ごとに生成するステップと、
前記第２のメモリ内で、前記共分散行列の前記対角線アレイの各々の残りのエレメントを記憶するステップとを含み、
前記第１のアドレスジェネレータは、アレイの値を有する前記メモリ内のアドレスを示すように構成され、前記第２のアドレスジェネレータは、前記環状のバッファ内のアドレスを示すように構成される、方法。
【請求項１４】
２つの入力レジスタおよび１つの出力レジスタを有する乗算アキュムレータと、
第１および第２のマルチプレクサとを含み、前記第１のマルチプレクサは、前記乗算アキュムレータの、一方の入力レジスタに結合され、前記第２のマルチプレクサは、前記乗算アキュムレータの、他方の入力レジスタに結合され、さらに、
読出アドレスジェネレータおよび書込アドレスジェネレータを有する、二重ポートレジスタファイルを含み、前記レジスタファイルの出力は、前記第２のマルチプレクサに結合され、さらに、
前記レジスタファイルの入力に結合される第３のマルチプレクサと、
２つの入力レジスタおよび１つの出力レジスタを有する演算論理装置と、
第４および第５のマルチプレクサとを含み、前記第４のマルチプレクサは前記演算論理装置の、一方の入力レジスタに結合され、前記第５のマルチプレクサは前記演算論理装置の、他方の入力レジスタに結合され、さらに、
前記第１、第２、第３、第４、および第５のマルチプレクサに結合される第１のデータ
バスを含み、前記第１のデータバスはさらに前記乗算アキュムレータの出力レジスタ、前記ＡＬＵ（演算論理装置）の出力レジスタ、および前記ファイルレジスタの出力に結合され、さらに、
前記第１、第２、および第４のマルチプレクサに結合される第２のデータバスを含み、前記第２のデータバスはさらに前記乗算アキュムレータの出力レジスタ、前記演算論理装置の出力レジスタ、および前記レジスタファイルの出力に結合され、さらに、
前記第３のマルチプレクサおよび前記第５のマルチプレクサに結合される第３のデータバスを含み、前記第３のデータバスはさらに前記乗算アキュムレータの出力レジスタ、前記演算論理装置の出力レジスタ、および前記レジスタファイルの出力に結合され、さらに、
第１のアドレスレジスタを有する第１のメモリを含み、前記第１のメモリは前記第１のデータバスに結合され、さらに、
第２のアドレスレジスタを有する第２のメモリを含み、前記第２のメモリは前記第２のデータバスに結合される、共分散行列ジェネレータ。
【発明の詳細な説明】
【０００１】
【発明の分野】
この発明は、ＣＭＯＳ集積回路に関し、より特定的には、共分散行列を生成する方法および装置に関する。
【０００２】
【発明の背景】
多数の応用は、ランダム変数の集合間の変化を測定するステップを必要とするプロセスを含む。これらの測定値は、２次元アレイの形態をとって記憶され、または表示されるかもしれない。そのようなアレイは、以下文中では、共分散行列として言及される。
【０００３】
共分散行列の生成を必要とする、応用の一例は、ＩＳ−５４米国ディジタルセルラー無線規格の実現である。この規格は、「ベクトル和励起線形予測コーディング（Vector Sum Excited Linear Predictive Coding:VSELP ）」として知られる音声コーダを使用しており、それは、ディジタル音声サンプルのブロックを入力として使用する共分散行列の計算を必要とする。音声サンプルは、アナログ入力から、８ＫＨｚサンプリング率で記憶される。ＩＳ−５４規格の詳細は、ＥＩＡ／ＴＩＡドキュメント２２１５（セルラーシステム−二重モード移動局／１つの州互換性規格ＩＳ−５４，１９８９年１２月）において論議される。
【０００４】
１７０の入力音声サンプルから、共分散行列を生成する公式は、式（１）において示され、そこでは、φ（ｉ，ｋ）は、共分散行列の、行ｉ、列ｋでの値を表わし、ＮA は、入力音声サンプルの総数を表わし（ＮA ＝１７０）、ＮP は、共分散行列の、最大の行および列の数を表わし（ＮP ＝１０）、ならびにＳ（ｘ）はｘ番目の入力サンプルの値を表わす。
【０００５】
【数１】
0003740516.tif 000002
【０００６】
式（１）により生成される共分散行列の表現は、図１（Ａ）に示され、そこでは、ｘ，ｙは、共分散行列の、行ｘ、列ｙで記憶された共分散測定値を表わす。
【０００７】
図１（Ｂ）は、ランダムアクセスメモリ（ＲＡＭ）内で、図１（Ａ）に示される共分散行列の値を記憶する可能な方法を示す。共分散行列は対称なので、１１×１１共分散行列を記憶するのに必要なのは６６のＲＡＭ位置だけであることに注目されたい。したがって、共分散行列中の各エレメントφ（ｉ，ｋ）について言えば、φ（ｉ，ｋ）＝φ（ｋ，ｉ）となる。結果として、共分散行列全体を表わすには、中心対角線に沿うエレメント、および共分散行列の三角形上部（または下部）のみが生成され、記憶される必要がある。
【０００８】
図２は、３つの行列Ｆ、Ｂ、およびＣの記憶構成を示しており、それらは、図１（Ｂ）に示されるように記憶された共分散行列の部分集合である。これらの３つの行列もまた対称である。
【０００９】
共分散行列の、行が０のエレメント（すなわち、φ（０，０）ないしφ（０，１０））が生成されると、残りのエレメントは下記の式（２）を使用して容易に生成され得るという点で、式（１）は冗長を表す。
【００１０】
【数２】
0003740516.tif 000003
【００１１】
φ（１，１）について、式（２）から以下の式が導かれる。
【００１２】
【数３】
0003740516.tif 000004
【００１３】
式（２）の実行は、一般的に、乗算累積ハードウェアを用いた簡単なものである。しかしながら、共分散行列の、行が０のエレメント（すなわち、φ（０，０）ないしφ（０，１０））は、行列の残りが式（２）により生成される前に、まず、式（１）により生成されねばならない。
【００１４】
式（１）により必要とされる乗算においてのオペランドは、固定数により互いからオフセットされたサンプルである。たとえば、φ（０，１）を生成する式は、次のようになる。
【００１５】
【数４】
0003740516.tif 000005
【００１６】
この例では、すべての乗算のオペランドは、１だけ互いにオフセットされたサンプルである。
【００１７】
先行技術によると、効率的に式（１）の形をとる式を実行するには、共分散行列ジェネレータは、１７０の音声サンプルを有する２つの別個のメモリ、または１７０のサンプルを有する１つのメモリのパイプラインのいずれかを含んでいなければならない。これらのアーキテクチュアのブロック図は、それぞれ図３および図４に示される。
【００１８】
パイプライニングは、機能単位がその処理をいくつかのステップで行なう、処理形態である。第１のステップが完了すると、その結果は別個のハードウェアを使用する第２のステップへと移される。したがって第１のステップのハードウェアは、新しいデータ処理を始めるのが自由である。パイプライン処理は一般に、順次処理のために早いスループットを与えるが、それは典型的には、コンピュータシステムの幾つかの機能単位を通過するのに必要な時間が、別の方法ではデータが機能単位に入力される間隔より長くなってしまうような、プロセスのために使用される。
【００１９】
図３に示される二重メモリアーキテクチュアには、図４に示されるパイプラインアーキテクチュアの２倍のメモリを必要とするという、明らかな不利益がある。しかしながら、図４に示されるパイプラインアーキテクチュアを用いての共分散行列ジェネレータが、たとえばφ（０，１０）を生成するときには、１０のレベルのパイプラインが必要とされる。そのようなパイプラインは、共分散行列を速やかに生成するが、その目的は、共分散行列を生成するためだけに制限される。そのようなパイプラインは、たとえばＶＳＥＬＰに対する計算上の要求の他の部分のような、他の計算にとっては（いかなる自明の態様においても）役に立たない。
【００２０】
それゆえに、多目的の結果記憶装置として容易に使用されるが、行列の基となるサンプルがメモリの２バンクに記憶されることを必要としない、効率的な共分散行列ジェネレータを提供することが明らかに望ましい。
【００２１】
さらに望ましいのは、低いハードウェアのコストで共分散計算を効率的に実行し、かつ、一時的な結果を記憶するために、他の計算のためのシステムにおいて役立つ「スクラッチパッド」メモリを供給する、共分散行列ジェネレータを提供することである。
【００２２】
【発明の概要】
この発明の一局面によれば、共分散行列の第１の行を生成する装置が提供される。この装置は、一般的に、複数個のサンプルを表す値のアレイを有するメモリと、そのメモリに結合される環状のバッファとを含み、その環状のバッファは予め定められた数のメモリ位置を与えるように構成されており、さらに第１のメモリおよび環状のバッファに結合される乗算アキュムレータを含む。
【００２３】
この発明のもう１つの局面によれば、共分散行列の三角形部分の上部または下部を生成する装置が提供される。この装置は、一般的に、第１、および第２のメモリと、その第１のメモリに結合される環状のバッファと、第１および第２のメモリ、ならびに環状のバッファに結合される乗算アキュムレータと、第２のメモリおよび乗算アキュムレータに結合される演算論理装置とを含む。第１のメモリは、複数個のサンプルを表す値のアレイを有する。環状のバッファは、初めは、第１の予め定められた数のメモリ位置を与えるように構成される。
【００２４】
この装置は、第１のメモリから乗算アキュムレータへとアレイの値の順次部分集合を転送して、共分散行列の第１の行の第１のエレメントを生成し、かつ共分散行列の第１の行の第１のエレメントを第２のメモリ内に記憶する。
【００２５】
この装置は、第１のメモリからのアレイの値の第１の一連の順次部分集合、および、環状のバッファからのアレイの値の第２の一連の順次部分集合を、乗算アキュムレータへと同時に転送して、乗算アキュムレータの出力において、共分散行列の第１の行の残りのエレメントを生成する。この装置は、第２のメモリ内に、共分散行列の第１の行の残りのエレメントを記憶する。
【００２６】
さらにこの装置は、共分散行列の三角形部分の上部または下部の残りのエレメントを、演算論理装置内で生成し、かつ第２のメモリ内に記憶するように構成される。
【００２７】
さらにこの発明は、共分散行列の生成方法を提供する。この方法は、複数個のサンプルを表す値のアレイを有するメモリを設けるステップと、乗算アキュムレータを設けるステップと、予め定められた深さの環状のバッファを設けるステップと、乗算アキュムレータ内で、共分散行列の第１の行の第１のエレメントを生成するステップとを含む。さらにこの方法は、第２のメモリ内に第１のエレメントを記憶するステップと、共分散行列の第１の行の残りのエレメントを生成するステップと、第２のメモリ内に第１の行の残りのエレメントを記憶するステップとを含む。さらにこの方法は、演算論理装置内で、共分散行列の三角形部分の上部または下部の、残りのエレメントを対角線ごとに生成するステップと、第２のメモリ内に、共分散行列の三角形部分の上部または下部の、残りのエレメントを記憶するステップとを含む。
【００２８】
以下、この発明は添付図面に関して述べられ、以下文中では、同じ数字は同じエレメントを表わす。
【００２９】
【好ましい実施例の詳細な説明】
図５を参照すると、共分散行列ジェネレータ１０が、この発明の好ましい例示的な実施例に従って示されている。ジェネレータ１０は一般的に、複数個のランダムアクセスメモリ（ＲＡＭ）１２および４８と、複数個のアドレスジェネレータ１４、１６、および１８と、二重ポートレジスタファイル２０と、複数個のマルチプレクサ２４および２６とを含む。ジェネレータ１０はさらに、２つのデータバス２８および３０と、乗算アキュムレータ（以下ＭＡＣ）３２とを含む。
【００３０】
ＭＡＣ３２は３レベルのパイプラインで、２つの入力ポート、および１つの出力ポートを有する。具体的には、２つのオペランドがＭＡＣ３２の入力ポートに与えられて３サイクル後に、オペランドの乗算累積または乗算の積が、その出力ポートで利用可能となる。このアーキテクチュアは、ＭＡＣ３２のハードウェアの構成を最小にし、１つの乗算累積を演算する計算時間に３クロックサイクルのペナルティを課す。しかしながら、１７０のサンプルのセットの各々の共分散測定は、１６０の乗算累積計算を要求する（式（１）参照）ため、１サイクルの乗算アキュムレータに対する、ＭＡＣ３２の計算時間の増加のパーセンテージは、２％未満である。
【００３１】
アドレスジェネレータ１８は、レジスタファイル２０の「読出」アドレスジェネレータであり、アドレスジェネレータ１６は、レジスタファイル２０の「書込」アドレスジェネレータである。ジェネレータ１０を用いて、式（１）の数値を求める方法は、レジスタファイル２０を、１０の位置の深さを持つ環状のバッファとして使用する。アドレスジェネレータ１６および１８は、限界アドレス（位置９）に達すると、それぞれのアドレスポインタが与えられた開始アドレス（位置０）に「ラップアラウンドする」ことを可能にするよう構成されている。たとえば、アドレスジェネレータ１６のポインタがレジスタファイル２０の位置９を指すとき、増加されるなら、ポインタはリセット、または「ラップアラウンド」して、レジスタファイル２０の位置０を指す。同様に、アドレスジェネレータ１６のポインタが、レジスタファイル２０の位置０を指すとき、減少されるなら、ポインタは「ラップアラウンド」して、レジスタファイル２０の位置９を指す。アドレスジェネレータ１８のポインタは、同様の態様で「ラップアラウンド」するよう構成されている。
【００３２】
ＭＡＣ３２への一方の入力は、データバス２８によって直接与えられ、他方は、マルチプレクサ２４によって制御される。マルチプレクサ２４は、データをデータバス２８から、それが制御するＭＡＣ３２の入力へと向けるよう、初めは構成されている。マルチプレクサ２６は、レジスタファイル２０への入力を制御し、データを、データバス２８から、レジスタファイル２０内のアドレスジェネレータ１６によって指された位置へと向けるよう初めは構成されている。
【００３３】
共分散行列の生成は、図６に示されるステップ５２、５４、５６、および５８に従って実現され得るだろう。ステップ５２および５４は、ジェネレータ１０に関して説明され、一方ステップ５６および５８は図１２を参照して、後に詳しく説明される拡大されたジェネレータに関して説明される。具体的には、ステップ５２では、共分散行列の行０、列０、すなわちφ（０，０）が生成される。ステップ５４では、共分散行列の第１の行（行０）、すなわちφ（０，１）ないしφ（０，１０）を完成する測定値が生成される。ステップ５６では、行列の中心対角線のエレメント、すなわちφ（１，１）ないしφ（１０，１０）が生成され、ステップ５８では、行列の残りのエレメントが生成される。これらのステップの各々は、図８−１６を参照して、後により詳しく説明される。
【００３４】
上述のように、ステップ５２では、ジェネレータ１０は、式（１）に従って、共分散行列のφ（０，０）パラメータを最初に生成する。ステップ５２の実現のフローチャートは、図８に示される。具体的には、ステップ２０２では、ＲＡＭ１２のためのアドレスジェネレータであるアドレスジェネレータ１４は、ＲＡＭ１２の位置１０を指すよう設定され、アドレスジェネレータ１６は、レジスタファイル２０の位置０を指すよう設定され、アドレスジェネレータ１８は作動不可にされる。マルチプレクサ２４および２６は、データバス２８からデータを受取るように構成されている。こうして初期化され、ジェネレータ１０は、ＲＡＭ１２からのデータが、データバス２８を介して、ＭＡＣ３２の両方の入力へと送られるように、構成されている。
【００３５】
ステップ２０４では、タイマが開始されて、１６０の乗算累積を与え、ステップ２０６ないし２１４が、１６０の乗算累積が起こるまで、反復的に実行される。
【００３６】
ステップ２０６では、ＲＡＭ１２内のアドレスジェネレータ１４が指す場所のサンプルが、ＭＡＣ３２の両方の入力に入力され、レジスタファイル２０に書込まれる。ＭＡＣ３２は入力値を乗じて、その乗算の積を、前の計算の和に加える。ステップ２０８では、アドレスジェネレータ１４および１６は同期して増加する。
【００３７】
したがって、アドレスジェネレータ１４は、それぞれ値Ｓ（１０）ないしＳ（１６９）を有するＲＡＭ１２のアドレス１０ないし１６９を連続して指す。前述のように、アドレスジェネレータ１６のポインタはラップアラウンドするように構成されている。こうして、ステップ２１０および２１２で、アドレスジェネレータ１６が増加するにつれて、そのポインタは位置９を指した後、位置０にラップアラウンドする。各々の「ラップアラウンド」の後、レジスタファイル２０に書込まれた新しいデータは、そこに前に記憶されたデータをオーバライトする。
【００３８】
ステップ２０６ないし２１４までの反復の間、データのサンプルＳ（１０）ないしＳ（１６９）が、ＭＡＣ３２の入力ポートに送り込まれ、それら自身で乗算され、かつ前の計算の結果と累積されて、最終結果φ（０，０）を生じる。同時に、Ｓ（１０）ないしＳ（１６９）が、レジスタファイル２０に連続して書込まれる。レジスタファイル２０は、１０のメモリの位置のみに書込むよう構成されているので、最後の１０の入力値のみがそこに記憶される。したがって、１６０の乗算累積が完了すると、ＭＡＣ３２の出力はφ（０，０）を含み、レジスタファイル２０は図示のように構成されている。ここでＸは、それぞれのアドレスジェネレータが指す、レジスタファイル２０内の位置を表わす。（この場合、アドレスジェネレータ１８は作動不可で、アドレスジェネレータ１６は位置９を指す。）
【００３９】
【表１】
0003740516.tif 000006
【００４０】
ステップ２１６では、ＭＡＣ３２の出力（すなわちφ（０，０））は、データバス３０を介して、ＲＡＭ４８に記憶され、ステップ２１８ではＭＡＣ３２の出力レジスタは、クリアされる。アドレスジェネレータ１４は、ここではＲＡＭ１２の位置１６９内のＳ（１６９）を指しており、アドレスジェネレータ１６は、レジスタファイル２０の位置９を指し、これもまたＳ（１６９）を含む。
【００４１】
共分散行列の中心対角線上の他の１０の項（すなわちφ（１，１）ないしφ（１０，１０））を上述の式（２）に従って生成するよりもむしろ、レジスタファイル２０のここでの構成を用いて、共分散行列の行０の他の１０のエレメント（すなわちφ（０，１）ないしφ（０，１０））を生成する（ステップ５４）方が有利である。
【００４２】
そのフローチャートが図９ないし図１１に示されるステップ５４の実行は、ここでより詳細に説明される。φ（０，１）の生成を始めるにあたり、ステップ２２０で、マルチプレクサ２４は、レジスタファイル２０から読出すよう構成されている。こうして、ＭＡＣ３２への一方の入力は、ここではレジスタファイル２０からであり、ＭＡＣ３２への他方の入力は、まだＲＡＭ１２からである。
【００４３】
φ（０，０）の生成と同様に、行０の各々のエレメントの生成は、１６０の乗算累積を要求する。しかしながら、これらの計算に要求される乗算のオペランドは整列されない。より具体的には、すべての共分散エレメントφ（０，ｋ）に対して、φ（０，ｋ）を生成するため要求される乗算のオペランドは、ｋサンプルによってオフセットされる。たとえば、φ（０，１）を生成するのに要求される乗算のオペランドは、１サンプルだけ（たとえばＳ（１０）Ｓ（９）、Ｓ（１１）Ｓ（１０）など）、オフセットされる。結果として、φ（０，１）の生成においてこのオフセットを与えるため、ステップ２２２で、アドレスジェネレータ１４は再整列されて、ＲＡＭ１２の位置１６８を指し、アドレスジェネレータ１６は再整列されて、レジスタファイル２０の位置８を指す（すなわち、アドレスジェネレータ１４および１６は減少される。）。アドレスジェネレータ１８は、レジスタファイル２０の位置９を指すよう設定される。レジスタファイル２０は、ここでは次のように構成されている。
【００４４】
【表２】
0003740516.tif 000007
【００４５】
したがって、φ（０，１）の生成を始めるため、アドレスジェネレータ１４は、ＲＡＭ１２内の値Ｓ（１６８）を有する位置１６８を指し、アドレスジェネレータ１６は、レジスタファイル２０内の値Ｓ（１６８）を有する位置８を指し、かつアドレスジェネレータ１８は、レジスタファイル２０の値Ｓ（１６９）を有する位置９を指す。結果として、データバス２８からの値Ｓ（１６８）、およびレジスタファイル２０内の位置９からのＳ（１６９）は、初めは、ＭＡＣ３２の入力ポートへとロードされる。
【００４６】
ステップ２２４で、アドレスジェネレータ１４、１６、および１８は減少モードに置かれている。マルチプレクサ２６は、データバス２８から、アドレスジェネレータ１６によりアドレスされたレジスタファイル２０の書込ポートへとデータをまだ送っているため、レジスタファイル２０の書込ポートは、データバス２８からのＳ（１６８）を入力として有する。
【００４７】
ステップ２２６で、タイマが開始されて、φ（０，１）の生成によって要求される１６０の乗算累積のためのカウンタを与える。したがって、ＭＡＣ３２は、Ｓ（１６９）とＳ（１６８）との積をＳ（１６８）とＳ（１６７）との積と、というように集積し始める。レジスタファイル２０は、読出／書込モードにあり、ここで、クロックサイクルの前半の間アドレスジェネレータ１８が指す位置から、データが読出され、クロックサイクルの後半の間アドレスジェネレータ１６が指す位置に、データが書込まれる。このタイミングは、図７に示される。
【００４８】
したがって、φ（０，１）の生成の第１のサイクルで、Ｓ（１６９）は、レジスタファイル２０から読出され、かつＳ（１６８）は、ステップ２２８でＲＡＭ１２から読出される。ステップ２３０においてＭＡＣ３２でこれらの値は乗じられ、累積される。それから、ステップ２３２で、Ｓ（１６８）は、レジスタファイル２０内のアドレスジェネレータ１６によって指された位置８に書込まれる。次に、ステップ２３４で、アドレスジェネレータ１４、１６、および１８のポインタは減少され、そのためアドレスジェネレータ１４は、ここではＲＡＭ１２内の値Ｓ（１６７）を有する、位置１６７を指し、アドレスジェネレータ１８は、レジスタファイル２０内の値Ｓ（１６８）を有する、アドレス８を指し、アドレスジェネレータ１６はレジスタファイル２０内の、φ（０，０）の生成からの値Ｓ（１６７）を有する、アドレス７を指す。ステップ２３６および２３８で、アドレスジェネレータ１６およびアドレスジェネレータ１８のポインタは、それらのラップアラウンドの限界を越えてしまうと、ラップアラウンドする。第１のサイクルでは越えていないので、実行はステップ２４０まで進む。ステップ２４０で、タイマの状態がチェックされる。１６０の反復が完了していなければ、実行は分岐してステップ２２８に戻る。
【００４９】
φ（０，１）の生成の第２のサイクルで、ステップ２２８ないし２４０において、ＭＡＣ３２は、ＲＡＭ１２からのＳ（１６７）を、レジスタファイル２０からのＳ（１６８）と乗じ、その乗算の積を、Ｓ（１６９）とＳ（１６８）との積と累積する。ＭＡＣ３２でφ（０，１）のすべての項が生成され、累積されるまで（つまり１６０の乗算累積のため）、このプロセスは続く。上述のように、これらの計算の間、同期して減少したアドレスジェネレータ１６および１８は、１の位置だけオフセットされ、位置０に達するごとにラップアラウンドする。またレジスタファイル２０の値は、継続的にオーバライトされる。しかしながら、アドレスジェネレータ１８は、実質的にアドレスジェネレータ１６より「先に」あり、かつアドレスジェネレータ１８は常に、φ（０，１）の生成のための次のオペランドを指すため、φ（０，１）の生成は、効率的に実行される。
【００５０】
タイマの完了の際に、レジスタファイル２０は以下のように構成されているだろう。
【００５１】
【表３】
0003740516.tif 000008
【００５２】
φ（０，１）の生成の最後の項は、Ｓ（１０）Ｓ（９）である。したがって、値Ｓ（１０）は、レジスタファイル２０内の現在アドレスジェネレータ１８によって指されている位置にあり、値Ｓ（９）は、レジスタファイル２０の位置９に書込まれている。ＭＡＣ３２の出力レジスタは、ここでは値φ（０，１）を含み、かつ、アドレスジェネレータ１４は、ＲＡＭ１２内の値Ｓ（９）を有する位置９を指す。
【００５３】
この時点で、実行はステップ２４２まで進み、ここでφ（０，１）は、データバス３０を介してＲＡＭ４８に書込まれ、かつＭＡＣ３２の出力レジスタはクリアされる。ステップ２４４で、アドレスジェネレータ１４、およびアドレスジェネレータ１６は、もう一度減少され、ＲＡＭ１２からレジスタファイル２０の位置８へＳ（８）を書込むことを可能にする（Ｓ（１８）をオーバライトする）。ステップ２４６で、アドレスジェネレータ１４は、それからＳ（１０）を指すよう設定され、アドレスジェネレータ１６のポインタは、アドレスジェネレータ１８のポインタと交換される。こうして、アドレスジェネレータ１４は、ここではＲＡＭ１２の位置１０のＳ（１０）を指し、アドレスジェネレータ１６は、レジスタファイル２０の位置０のＳ（１０）を指し、アドレスジェネレータ１８は、レジスタファイルの２０の位置８のＳ（８）を指す。アドレスジェネレータ１６、およびアドレスジェネレータ１８は、所望の位置を指すように、直接設定されてもよいし、またはそのアドレス出力がアドレスマルチプレクサ（図示せず）によって切換えられてもよい。アドレスジェネレータ１６およびアドレスジェネレータ１８のポインタは、ここでは２だけステップから外れている。
【００５４】
ジェネレータ１０は、ここで次の式によってφ（０，２）を生成する。
【００５５】
【数５】
0003740516.tif 000009
【００５６】
この生成の始まりにおけるレジスタファイル２０の構成を以下に示す。
【００５７】
【表４】
0003740516.tif 000010
【００５８】
ステップ２４８で、アドレスジェネレータ１４、１６、および１８は、増加モードに入れられる。マルチプレクサ２４、および２６の構成は変わらないままである。ステップ２５０で、タイマが開始され、φ（０，２）の生成のため、１６０の乗算累積を与える。φ（０，１）の生成のステップ２２８ないし２４０と同様に、ステップ２５２ないし２６０で、ＭＡＣ３２は、φ（０，２）の項を乗算累積し、かつレジスタファイル２０は継続的にその内容がオーバライトされる。具体的には、アドレスジェネレータ１８が、レジスタファイル２０の、Ｓ（１７）を有する位置７を指しているとき、アドレスジェネレータ１６は、Ｓ（１９）を位置９に書込んでいる。前のクロックサイクルで、Ｓ（１８）は位置８に書込まれており、２クロックサイクル後に、アドレスジェネレータ１８が位置８にアクセスするときのために備えている。
【００５９】
φ（０，２）の生成の完了の際に、レジスタファイル２０は、以下のように構成されている。
【００６０】
【表５】
0003740516.tif 000011
【００６１】
ＭＡＣ３２の出力レジスタは、φ（０，２）を含む。実行はステップ２６２に続き、ここでＭＡＣ３２の出力はＲＡＭ４８に記憶され、ＭＡＣ３２の出力レジスタはクリアされる。
【００６２】
φ（０，３）の生成に先立って、ステップ２６４で、アドレスジェネレータ１４、１８、および１６のポインタはそれぞれ、ＲＡＭ１２の場所１６６、レジスタファイル２０の場所９、およびレジスタファイル２０の場所６を指すよう設定されている。こうして、アドレスジェネレータ１４はサンプルＳ（１６６）を指し、アドレスジェネレータ１８はサンプルＳ（１６９）を指し、かつアドレスジェネレータ１６はサンプルＳ（１６６）を指す。アドレスジェネレータ１６、およびアドレスジェネレータ１８のポインタは、それぞれのポインタを示される位置に直接設定することによって設定されてもよいし、またはアドレスジェネレータ１８のポインタを１だけ減少させ、かつアドレスマルチプレクサ（図示せず）を介して、アドレスジェネレータ１８のポインタと、アドレスジェネレータ１６のそれを切換えることによって、設定されてもよい。
【００６３】
ステップ２６６で、行０のすべてのエレメントが生成されたかどうかが定められる。生成されていないので、ステップ２２４に戻って実行が進む。ステップ２２４で、アドレスジェネレータ１４、１６、および１８は、減少モードに置かれる。こうして、φ（０，３）の生成を始めるにあたり、レジスタファイル２０は、以下のように構成される。
【００６４】
【表６】
0003740516.tif 000012
【００６５】
次に共分散行列のエレメントφ（０，３）は、上述のステップ２２６ないし２４２に従って生成される。具体的には、ステップ２２６で、タイマが再び開始され、１６０の乗算累積を与える。１６０の乗算累積が完了すると、ＭＡＣ３２の出力は、値φ（０，３）を有し、次にそれが、ステップ２４２に従ってＲＡＭ４８に記憶される。そしてＭＡＣ３２の出力レジスタはクリアされる。φ（０，３）の生成の完了の際に、レジスタファイル２０は以下のように構成される。
【００６６】
【表７】
0003740516.tif 000013
【００６７】
φ（０，３）の生成の後、アドレスジェネレータ１４、およびアドレスジェネレータ１６は、ステップ２４４に従って減少され、Ｓ（６）が位置６に書込まれることを可能にする。そしてステップ２４６で、アドレスジェネレータ１４は、リセットされて、ＲＡＭ１２の位置１０を指し、アドレスジェネレータ１６および１８のポインタが交換される。したがって、φ（０，４）の生成の初めに、アドレスジェネレータ１４はＳ（１０）を指し、アドレスジェネレータ１６はＳ（１０）を指し、かつアドレスジェネレータ１８はＳ（６）を指す。ステップ２４８で、アドレスジェネレータ１４、１６、および１８は、ここでは増加モードに置かれている。
【００６８】
この操作のシーケンスは、共分散行列の行０の最後のエレメント、φ（０，１０）が生成されるまで繰返される。具体的には、φ（０，９）の生成の完了の際に、実行はステップ２４４にあり、レジスタファイル２０は以下のように構成される。
【００６９】
【表８】
0003740516.tif 000014
【００７０】
前述のように、ステップ２４４で、アドレスジェネレータ１４およびアドレスジェネレータ１６は減少されて、そのためアドレスジェネレータ１６は位置０を指し、かつＳ（０）がレジスタファイル２０の位置０に書込まれる。そしてステップ２４６で、アドレスジェネレータ１４はＳ（１０）にリセットされ、アドレスジェネレータ１６および１８は交換される。（両方ともアドレス０を指している。）そしてステップ２４８で、アドレスジェネレータ１４、１６、および１８は、増加モードに設定される。そして行０の最後の行列エレメント、φ（０，１０）は、次の式に従って、生成される。
【００７１】
【数６】
0003740516.tif 000015
【００７２】
具体的には、アドレスジェネレータ１４は、ＲＡＭ１２内のＳ（１０）を指し、アドレスジェネレータ１６および１８の両方は、レジスタファイル２０の位置０のＳ（０）を指す。ジェネレータ１０は、いかなる与えられたクロックサイクルででも、書込より読出が先に起こるよう構成されているため、ステップ２５２で、Ｓ（０）はレジスタファイル２０の位置０から最初に読取られ、それからＳ（１０）がレジスタファイル２０の位置０でＳ（０）の上に書込まれる。φ（０，１０）の生成を完了すると、ＭＡＣ３２の出力がＲＡＭ４８に記憶され、ＭＡＣ３２の出力はステップ２６２に従ってクリアされる。ステップ２６４は、この最後のサイクルの間、随意にスキップされてもよい。というのは、アドレスジェネレータ１４、１６、および１８のポインタはステップ５６の開始の際に新しい値に設定されるからである。
【００７３】
ステップ５４はこれで完了し、共分散行列のエレメントφ（０，０）ないしφ（０，１０）が生成され、記憶された。ステップ５６の間、共分散行列の中心対角線の残りのエレメント、φ（１，１）ないしφ（１０，１０）が式（２）に従って生成される。具体的には、φ（１，１）は次の式に従って生成される。
【００７４】
【数７】
0003740516.tif 000016
【００７５】
ステップ５６および５８の実行は、図１２を参照して説明される。この図は、共分散行列ジェネレータ１００の、拡張された実施例を表わしている。ステップ５２および５４が、ジェネレータ１０に関して上述したように、ジェネレータ１００によって実行され得ることが当業者には容易に明らかになるであろう。ステップ５６および５８の説明において、ステップ５２および５４が、上述のようにジェネレータ１００によって実行されたと仮定する。
【００７６】
図１２を参照すると、共分散行列ジェネレータ１００が、この発明の例示的な実施例に従って示されている。ジェネレータ１００は一般には、複数個のランダムアクセスメモリ（ＲＡＭ）１１２、および１５２と、複数個のアドレスジェネレータ１１４、１１６、１１８、および１５０と、二重ポートレジスタファイル１２０と、複数個のマルチプレクサ１０２、１０４、１０６、１０８、および１２６とを含む。ジェネレータ１００はさらに、３つのデータバス１２８、１３０、および１５４と、乗算アキュムレータ（ＭＡＣ）１３２と、演算論理装置（ＡＬＵ）１１０とを含み、その出力レジスタは、ＡＬＵの出力を保持する、またはそれをデータバス１３０にトランスペアレントにパスすることができる。
【００７７】
ＭＡＣ１３２は２つの入力ポート、および１つの出力ポートを有し、上述のＭＡＣ３２に類似した３レベルのパイプラインとして設計されている。ＭＡＣ１３２の一方の入力は、マルチプレクサ１０２によって制御され、他方はマルチプレクサ１０４によって制御される。その具体的な動作が図１３、および図１４に示されているステップ５６の開始の際、マルチプレクサ１０２、およびマルチプレクサ１０４の両方が、ステップ３００に従ってデータバス１２８から、ＭＡＣ１３２へとデータを送るよう構成されている。
【００７８】
レジスタファイル１２０は、２０の位置の深さを有する環状のバッファとして構成されている。アドレスジェネレータ１１８は、レジスタファイル１２０の「読出」アドレスジェネレータで、アドレスジェネレータ１１６は、レジスタファイル１２０の「書込」アドレスジェネレータである。アドレスジェネレータ１１６および１１８は、上述のようにそれぞれのアドレスポインタが「ラップアラウンドする」ことを可能にするよう設計されている。マルチプレクサ１２６は、レジスタファイル１２０への入力を制御し、レジスタファイル１２０のアドレスジェネレータ１１６によって指された位置に、データバス１２８からデータを送るよう構成されている。
【００７９】
ＡＬＵ１１０は、マルチプレクサ１０６、およびマルチプレクサ１０８によって制御される２つの入力を有する。ステップ５６および５８の間、ＡＬＵ１１０が用いられて、ＭＡＣ１３２の出力を集積する。こうしてステップ５４の完了の際に、ＭＡＣ１３２は乗算専用モードに置かれる。
【００８０】
アドレスジェネレータ１１４は、ＲＡＭ１１２のアドレスジェネレータで、２つの修正可能なポインタを備えて構成されている。ステップ３０２では、アドレスジェネレータ１１４の第１の修正可能なポインタは、ＲＡＭ１１２の位置９を指すよう、初めに設定され、かつアドレスジェネレータ１１４の第２のアドレスポインタは、ＲＡＭ１１２の位置１６９を指すよう初めに設定されている。ステップ３０４において、アドレスジェネレータ１１４の両方のアドレスポインタは初めは減少モードに設定されている。アドレスジェネレータ１１４はさらに、その２つのポインタの各々が以下に示されるように交互のクロックサイクルでデータバス１２８を駆動することを可能にするよう構成されている。
【００８１】
【表９】
0003740516.tif 000017
【００８２】
結果として、データバス１２８は、値Ｓ（９）、Ｓ（１６９）、Ｓ（８）、Ｓ（１６８）、…、Ｓ（０）、Ｓ（１６０）を順次与える。上で特定したように構成され、ジェネレータ１００は、対角線のエレメントφ（１，１）ないしφ（１０，１０）の生成を始める。具体的には、ステップ３０６でＭＡＣ１３２の両方の入力は、値Ｓ（９）、Ｓ（１６９）、…、Ｓ（０）、Ｓ（１６０）をデータバス１２８から連続して送り込む。こうしてＭＡＣ１３２は、積Ｓ（９）Ｓ（９）、Ｓ（１６９）Ｓ（１６９）、…、Ｓ（０）Ｓ（０）、Ｓ（１６０）Ｓ（１６０）を連続して出力する。ステップ３０６の交互の実行の間、データバス１２８を読出すことによって、ファイルレジスタ１２０は値Ｓ（０）ないしＳ（９）を入力する。
【００８３】
ステップ３０６の間でまた、ＭＡＣ１３２の出力は、データバス１３０を介してＡＬＵ１１０のマルチプレクサ１０８に順次送られる。ステップ３０８および３１０で、ＲＡＭ１５２は第１にデータバス１５４を介してＲＡＭ１５２からマルチプレクサ１０６にφ（０，０）を供給する。Ｓ（９）がＭＡＣ１３２の両方の入力に送り込まれて３サイクル後に、ＭＡＣ１３２はＳ（９）Ｓ（９）を出力する。次のクロックサイクルで、ステップ３１４に従って、ＡＬＵ１１０のφ（０，０）に、Ｓ（９）Ｓ（９）が加えられる。φ（０，０）とＳ（９）Ｓ（９）との和は、同じサイクルにおいてＡＬＵ１１０の出力で利用可能となる。ステップ３１６でこの和は、データバス１５４を介してマルチプレクサ１０６にその後のアクセスのため渡される。ＡＬＵ１１０の出力は、データバス１３０に接続されているが、このプロセスの間、データバス１３０から切り離されている。ステップ３１８で、ＭＡＣ１３２はＳ（１６９）Ｓ（１６９）を生成し、ステップ３２０でこれはマルチプレクサ１０８に転送される。ＡＬＵ１１０の出力はデータバス１５４に直接送り込まれ、したがってステップ３２２に従ってマルチプレクサ１０６に送り込まれる。５番目のサイクルで、積Ｓ（１６９）Ｓ（１６９）が、ステップ３２０に従ってデータバス１３０を介してＭＡＣ１３２の出力からマルチプレクサ１０８に入力され、かつステップ３２４でＡＬＵ１１０はこの値を前の累積から減じる。この演算はφ（０，０）＋Ｓ（９）Ｓ（９）−Ｓ（１６９）Ｓ（１６９）を生み、φ（１，１）に等しくなる。サイクル５の間、ＡＬＵ１１０の出力はデータバス１５４で利用可能となり、ステップ３２６でＲＡＭ１５２に書込まれ、次の式に従ってφ（２，２）を生成するのに用いるため、マルチプレクサ１０６に同時に与えられる。
【００８４】
【数８】
0003740516.tif 000018
【００８５】
ステップ３２８で、中心対角線が完了したかどうかが定められる。完了していないので実行が再びステップ３０６で始まる。
【００８６】
積Ｓ（８）Ｓ（８）、およびＳ（１６８）Ｓ（１６８）がＭＡＣ１３２からの次の２つの出力であるので、ステップ３０６ないし３２８に関して説明したプロセスは、φ（１０，１０）が生成されＲＡＭ１５２で記憶されるまで、ＭＡＣ１３２のパイプラインで、中断なく繰返される。データバス１２８、１３０、および１５４はすべて、この動作で矛盾なく利用される。
【００８７】
先に示したように、ステップ５４の完了においてレジスタファイル１２０はその１０の位置で、値Ｓ（１６０）ないしＳ（１６９）を含む。加えて、ステップ５６の実行中、値Ｓ（０）ないしＳ（９）がレジスタファイル１２０の残りの１０の位置に転送される。示されるように、この転送においていかなるオーバヘッドをも受けない。というのはφ（１，１）ないしφ（１０，１０）の生成の間、値Ｓ（０）ないしＳ（９）が、ＲＡＭ１１２からデータバス１２８にアクセスされるからである。さらに、ステップ５６の終わりにＲＡＭ１５２は、ステップ５２からφ（０，０）を、ステップ５４からφ（０，１）ないしφ（０，１０）を、ステップ５６からφ（１，１）ないしφ（１０，１０）を含む。
【００８８】
ステップ５６の間、値Ｓ（０）ないしＳ（１０）がレジスタファイル１２０に転送されているので、レジスタファイル１２０はステップ５８の間にＭＡＣ１３２の一方の入力を供給する適切な値をもって構成される。結果として、ステップ３５０で、マルチプレクサ１０４はレジスタファイル１２０からデータをアクセスするよう構成されている。ステップ５６の間と同様、ステップ５８の間、ＭＡＣ１３２の他方の入力は、ＲＡＭ１１２からデータバス１２８を通って直接供給される。こうしてＭＡＣ１３２のパイプラインは、一杯に保たれている。
【００８９】
φ（１，２）、および対角線の次の値を生成するためには、レジスタファイル１２０に記憶された値が用いられなくてはならない。レジスタファイル１２０が、マルチプレクサ１０４を介してＭＡＣ１３２の一方の入力に供給できるので、データバスの矛盾はまだない。ステップ５６のように、レジスタファイル１２０の出力はデータバス１３０に接続されているが、しかし切り離されている。
【００９０】
値φ（１，２）ないしφ（９，１０）がその間に生成されるステップ５８を実行するため、レジスタファイル１２０のアドレスジェネレータ１１８は２つのポインタを備えて構成されており、それらはいずれも減少されることが可能である。また、アドレスジェネレータ１１４は２つのアドレスポインタを有し、これらが値Ｓ（１６９）ないしＳ（１６１）、およびＳ（９）ないしＳ（１）を、データバス１２８に交互のサイクルで供給する。
【００９１】
ステップ３５２で、レジスタファイル１２０のアドレスジェネレータ１１８のポインタは、値Ｓ（１６８）ないしＳ（１６０）、およびＳ（８）ないしＳ（０）を交互のサイクルで供給するよう構成されている。
【００９２】
こうしてステップ３５４の間、ＲＡＭ１１２はＭＡＣ１３２の一方の入力に、値Ｓ（９）、Ｓ（１６９）、Ｓ（８）、Ｓ（１６８）、…、Ｓ（１）、Ｓ（１６１）を、データバス１２８およびマルチプレクサ１０２を用いて供給し、一方レジスタファイル１２０は、ＭＡＣ１３２の他方の入力に値Ｓ（８）、Ｓ（１６８）、Ｓ（７）、Ｓ（１６７）、…、Ｓ（０）、Ｓ（１６０）をマルチプレクサ１０４を用いて供給する。ＭＡＣ１３２（まだ乗算のみをするよう構成されている）からの、結果として起こる出力は次のようになる。
【００９３】
【数９】
0003740516.tif 000019
【００９４】
ＡＬＵ１１０は、ステップ３５６ないし３６０に従って、マルチプレクサ１０６を介してＲＡＭ１５２から値φ（０，１）を与えられ、マルチプレクサ１０８を介してＭＡＣ１３２の出力Ｓ（９）Ｓ（８）を与えられる。ＡＬＵ１１０はこれらの値を加える。次にステップ３６６ないし３７０で、ＡＬＵ１１０はその最後の計算の和、およびＭＡＣ１３２の次の出力、Ｓ（１６９）Ｓ（１６８）を与えられ、ステップ３７２で後者を前者から減じて、φ（１，２）を生む。ステップ３７４でφ（１，２）がＲＡＭ１５２に記憶される。このプロセスは図１５ないし図１６で示されるステップに従って繰返され、ステップ３７６で定められるように、共分散行列の三角形の上部のすべてのエレメントが生成されるまで、レジスタファイル１２０およびＲＡＭ１１２のポインタは適切に変化される。このプロセスの間、ＭＡＣ１３２のパイプラインは一杯に保たれ、すべての対角線のエレメントφ（１，２）ないしφ（９，１０）が効率的に生成され、データバス１５４を介してＡＬＵ１１０の出力からＲＡＭ１５２に記憶される。
【００９５】
ジェネレータ１００を用いてステップ５２および５４を完了するためのマシンサイクルの数は約１，７６３である。具体的には、φ（０，０）ないしφ（０，１０）の生成は、１６０の乗算累積を１１回と、パイプラインサイクルを３回必要とし、それは１，７６３サイクルに等しい。アドレス生成、およびリセットオーバヘッドのために付加的なサイクルが要求されるかもしれない。
【００９６】
ステップ５２および５４のペナルティは３パイプラインサイクルである。というのはφ（０，０）がＲＡＭ１５２で記憶するために利用可能となる３サイクル前に、φ（０，０）を生成する最終のアドレスがレジスタファイル１２０、およびＲＡＭ１１２に与えられるからである。しかしながら、この３サイクルの遅延がアドレス生成オーバヘッドを最小にするため使用され得る。特に、３サイクルの遅延の間、レジスタファイル１２０およびＲＡＭ１１２のポインタは、次の共分散エレメントの計算を始めるのに要求される値にリセットされてもよい。
【００９７】
その間にエレメントφ（１，１）ないしφ（１０，１０）が生成されるステップ５６は、約２０の乗算演算を要求し、複数のパイプライン操作と並行して、ＡＬＵが加算／減算する。
【００９８】
その間に共分散行列の残りが生成されるステップ５８は、約１１０の乗算、および３パイプラインサイクルを要求する。したがって、ジェネレータ１００での共分散行列の生成が要求するのは合計僅か１，８７６サイクルに何らかのアドレスジェネレータのリセットオーバヘッドをも加えたもののみである。
【００９９】
ＭＡＣ１３２が、乗算を出力しながら乗算を累積することができるように修正されるならば、共分散行列を生成する上述の方法は約５５サイクルを節約できるよう修正され得る。具体的には、行０のエレメント、φ（０，０）ないしφ（０，１０）を、それぞれの対角線のエレメントから離れて生成するよりもむしろ、ＭＡＣ１３２は、行０のエレメントを生成しながら対角線のエレメントを生成するよう構成されてもよく、こうして５５の冗長な計算を回避するのである。
【０１００】
たとえば、φ（０，０）の計算中、Ｓ（１０）Ｓ（１０）ないしＳ（１６９）Ｓ（１６９）の積が、以下のように計算される。
【０１０１】
【数１０】
0003740516.tif 000020
【０１０２】
しかしながら、φ（０，０）の生成で用いられる１０のファクタ、Ｓ（１６０）Ｓ（１６０）ないしＳ（１６９）Ｓ（１６９）は、以下のように対角線のエレメントφ（１，１）ないしφ（１０，１０）を生成するために要求されるファクタでもある。
【０１０３】
【数１１】
0003740516.tif 000021
【０１０４】
値Ｓ（１６０）Ｓ（１６０）ないしＳ（１６９）Ｓ（１６９）の各々を２回計算するよりむしろ、共分散行列を生成する上述の方法を以下のように修正することによって、これらの冗長な計算は回避され得る。
【０１０５】
共分散エレメントφ（０，０）は、アドレスジェネレータ１１４が、ＲＡＭ１１２内の値Ｓ（０）を有する位置０を最初に指すよう設定され、かつタイマが、１６０ではなく１７０の演算を与えるよう設定される以外は、上述のように生成される。初めの１０のクロックサイクルの間、Ｓ（０）Ｓ（０）ないしＳ（９）Ｓ（９）がＭＡＣ１３２によって生成されるが、累積はされない。その代わりに、これらの１０のパラメータは、ＭＡＣ１３２から直ちに出力され、データバス１５４を介してＲＡＭ１５２に記憶される。データバス１５４は、その他では、ステップ５２で用いられて、最後に生成されたエレメントをＲＡＭ４８に記憶するのみなので、バスの矛盾が起こらない。
【０１０６】
Ｓ（０）Ｓ（０）ないしＳ（９）Ｓ（９）が記憶された後、φ（０，０）が先に述べたように生成される。しかしながら、φ（０，０）の生成の最後の１０の要素、Ｓ（１６０）Ｓ（１６０）ないしＳ（１６９）Ｓ（１６９）が、ＭＡＣ１３２から利用可能であるとき、これらもまたデータバス１５４を介してＲＡＭ１５２に記憶される。一旦φ（０，０）が生成され、記憶されると、ＲＡＭ４８はφ（０，０）、Ｓ（０）Ｓ（０）ないしＳ（９）Ｓ（９）、およびＳ（１６０）Ｓ（１６０）ないしＳ（１６９）Ｓ（１６９）を含む。したがって、ＲＡＭ４８は、対角線の要素φ（１，１）ないしφ（１０，１０）を生成するのに必要なデータをすべて含む。
【０１０７】
行列の行０の次のエレメント、φ（０，１）の生成の間、ＡＬＵ１１０は、新たな行０のエレメントの生成が完了したときを除いて、乗算の最初の群を記憶する間、および乗算の最後の群を記憶する間のいかなるときでも、バスの矛盾なしにデータバス１５４を介してＲＡＭ１５２に記憶されたデータにアクセスすることができるだろう。
【０１０８】
具体的には、φ（０，１）を生成する間、ＭＡＣ１３２は操作の最初の９サイクルの間はデータバス１５４を用いて、値Ｓ（１）Ｓ（０）ないしＳ（９）Ｓ（８）をＲＡＭ１５２で記憶し、次の１５０サイクルの間はデータバス１５４を用いないで、Ｓ（１０）Ｓ（９）ないしＳ（１６０）Ｓ（１５９）を集積し、再びデータバス１５４を用いてφ（０，１）の最後の９のファクタＳ（１６１）Ｓ（１６０）ないしＳ（１６９）Ｓ（１６８）をＲＡＭ１５２に記憶する。データバス１５４およびＲＡＭ１５２が、ＭＡＣ１３２によって使用されない１５０のサイクルの中休みの間は、ＡＬＵ１１０はデータバス１５４およびＲＡＭ１５２を利用して、共分散行列の第１の対角線の残りのエレメントであるφ（１，１）ないしφ（１０，１０）を生成する。このように、ＭＡＣ１３２がφ（０，１）を生成する間、ＡＬＵ１１０はデータバス１５４およびＲＡＭ１５２を用いて、φ（１，１）ないしφ（１０，１０）を計算し、その結果をＲＡＭ１５２に記憶する。
【０１０９】
対角線の要素の各々の生成は４のサイクルを要求するため、φ（１，１）ないしφ（１０，１０）の生成は、１０×４＝４０サイクルを必要とする。したがって、これらの生成は、ＭＡＣ１３２がφ（０，１）の生成のためにデータバス１５４またはＲＡＭ１５２の使用を要求しない１５０のサイクルの中休みの間、容易に完了され得る。Ｓ（１６０）Ｓ（１６０）ないしＳ（１６９）Ｓ（１６９）が、φ（０，０）の生成の間記憶されるので、φ（１，１）ないしφ（１０，１０）の生成のためのこれらの値の冗長な計算は回避され、１０の乗算が節約できる。
【０１１０】
共分散行列のすべてのエレメントが生成されるまでこのプロセスは繰返される。たとえば、φ（０，１）がＭＡＣ１３２で生成されている間、対角線のエレメントφ（１，１）ないしφ（１０，１０）が、ＡＬＵ１１０によって生成され、ＲＡＭ１５２に記憶され、値Ｓ（１）Ｓ（０）ないしＳ（９）Ｓ（８）、およびＳ（１６１）Ｓ（１６０）ないしＳ（１６９）Ｓ（１６８）もまた、ＲＡＭ１５２に記憶される。φ（０，３）がＭＡＣ１３２で生成されている間、これらの値は次にＡＬＵ１１０によって用いられて、次の対角線のエレメント、φ（１，２）ないしφ（９，１０）を生成する。
【０１１１】
こうしてＭＡＣ１３２と、ＡＬＵ１１０とは、並行して動作し、ジェネレータ１００の資源を効率的に活用する。上述したのと同じアドレスの機構を用いるため、これらの修正は簡単に実現される。全体的に、上述の修正は第１のパスで１０のサイクルの節約を、第２のパスで９のサイクルの節約を、第３のパスで８のサイクルの節約を生むといった具合に、全体で５５のサイクルの節約を生む。
【０１１２】
こうして、このアーキテクチュアのパイプラインの能力が十分に活用され、多数の機能装置の存在を活用する並行処理が起こる。具体的には、レジスタファイル１２０と、ＡＬＵ１１０と、ＭＡＣ１３２と、ＲＡＭ１１２および１５２とは、すべて並行して動作し、ＶＳＥＬＰのための共分散行列計算の実現において、高い性能を提供する。
【０１１３】
この発明の特定の実施例を説明し、示したが、前掲の特許請求の範囲に規定されたこの発明の真の精神および範囲から逸脱することなく、特定して示し、説明した実施例の詳細についての変更が可能であることは明らかになるであろう。たとえば、上述のこの発明の例示的な実施例は、１７０のサンプル値に基づく１１×１１の行列に関して説明されている。しかしながら、ここで開示されたジェネレータのアーキテクチュア、および生成方法は、容易に修正可能であり、いかなる数の入力サンプルに基づくいかなる寸法の共分散行列をも生成する。
【図面の簡単な説明】
【図１】共分散行列に関する図であり、
（Ａ）は、各１対のペアになった数字Ｘ，Ｙが、共分散行列の行Ｘ、列Ｙにおいてのエレメントの値を表わす、１１×１１共分散行列の図であり、
（Ｂ）は、対称性の結果として、メモリ内で１１×１１共分散行列がいかに記憶され得るかを示す図である。
【図２】図１の（Ｂ）に示される共分散行列の、対称な部分行列の図である。
【図３】２つの個別のメモリ内でサンプル値を記憶する、共分散行列ジェネレータのブロック図である。
【図４】１つのメモリ上にレジスタパイプラインを有する、共分散行列ジェネレータのブロック図である。
【図５】この発明の一局面による、共分散行列ジェネレータのブロック図である。
【図６】この発明の一局面による、共分散行列ジェネレータの動作のフローチャートの図である。
【図７】クロックサイクルに関しての、データ転送シーケンスの図である。
【図８】共分散行列の第１の行の、第１のエレメントを生成するプロセスのフローチャートの図である。
【図９】共分散行列の第１の行の残りのエレメントを生成するプロセスのフローチャートの図である。
【図１０】共分散行列の第１の行の残りのエレメントを生成するプロセスのフローチャートの図である。
【図１１】共分散行列の第１の行の残りのエレメントを生成するプロセスのフローチャートの図である。
【図１２】この発明のもう１つの局面による、拡張された共分散行列ジェネレータのブロック図である。
【図１３】共分散行列の中心対角線を生成するプロセスのフローチャートの図である。
【図１４】共分散行列の中心対角線を生成するプロセスのフローチャートの図である。
【図１５】共分散行列の残りのエレメントを生成するプロセスのフローチャートの図である。
【図１６】共分散行列の残りのエレメントを生成するプロセスのフローチャートの図である。
【符号の説明】
１２  ランダムアクセスメモリ
１４  アドレスジェネレータ
１６  アドレスジェネレータ
１８  アドレスジェネレータ
２０  レジスタファイル
３２  乗算アキュムレータ
４８  ランダムアクセスメモリ
【図１】
0003740516.tif 000022
【図２】
0003740516.tif 000023
【図３】
0003740516.tif 000024
【図４】
0003740516.tif 000025
【図５】
0003740516.tif 000026
【図６】
0003740516.tif 000027
【図７】
0003740516.tif 000028
【図８】
0003740516.tif 000029
【図９】
0003740516.tif 000030
【図１０】
0003740516.tif 000031
【図１１】
0003740516.tif 000032
【図１２】
0003740516.tif 000033
【図１３】
0003740516.tif 000034
【図１４】
0003740516.tif 000035
【図１５】
0003740516.tif 000036
【図１６】
0003740516.tif 000037