JPS62194577A - 複素乗算器及び複素乗算方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔発明の技術分野〕 本発明は、概して乗算器及び乗算方法に関し、特に高速
フーリエ変換に用いるシストリック・アレーの乗算器及
び乗算方法に関する。

〔発明の背景〕

通常、高速フーリエ変換（ＦＦＴ）の計算には、相当量
の処理器能が必要となる。ＦＦＴアルゴリズムの計算の
中心をなすものは、ベクトル回転（単位ベクトルにより
乗算）の条件である。このベクトル回転の典型的なもの
は「バタフライ（Ｂｕｔｔｅｒｆｌｙ　）　Ｊと呼ばれ
る。基数２のＦＥＴバタフライは８対の値に対して複素
乗算十複素加算＋引算を必要とする。更に、複素乗算を
行なうには、４回の乗算及び２回の加算が必要である。

これらの処理は全て比較的高速度で実行され、かつ計算
回路をその最大効率で用いなければならない。

ディジタル・フーリエ変ｔ！！！　（ＤＥＴ）を実現す
るために、広範なアーキテクチャ−が設けられていた。

これらのアーキテクチャ−の多くは過度の計算（即ちチ
ャーブ（ｃｈｉｒｐ　）　ｚ変換）、過度の制御回路（
即ちウイノグラート（Ｗｉｎｏｇｒａｄ）及び混合素基
数アルゴリズム）、又は過度のゲート数、又はＩ１０ビ
ン（例えばクーレイ・タケイ（Ｃｏｏｌｅｙ　−Ｔｕｋ
ｅｙ　）を必要とする。利用されていた効果的な−アー
キテクチャーでは、１１演算装置によってバタフライを
並列計算する直列パイプライン・アーキテクチャ−が用
いられる。この形式の計算は直列演算を利用できるよう
にすると、演算装置のそれぞれにおけるスルーブツト仕
様が低下する。しかし、総合的なゲート・Ｈ２積は、各
演算ユニットが最高速度時の半分の時間で処理し、残り
の半分の時間でアイドル状態を必要とするパイプライン
・アーキテクチャ−のために、過度なものとなってしま
い、データを連続的に処理することができない。演算装
置は加算器セルのシストリック・アレーとして実現する
ことができ、かつ和及びキャリーをこれらを介してパイ
プライン化しているので、乗算サイクル時間はシストリ
ック・アレーの１ビツト・セルについての加算時間に等
しい。このシストリック・アレーの技術はマツフタガー
ト（Ｈａｃｔａｇｇａｒｔ　）及びＭ、Ａジャック（Ｊ
ａｃｋ）により「並列データ分散演算を用いた単一チッ
プ・アレーによる基数２のＦＥＴバタフライ（＾Ｓｉｎ
ｇｌｅ　Ｃｈｉｐ　Ａｒｒａｙ　Ｒａｄｉｘ　２　ＦＦ
ＴＢｕｔｔｅｒｆｌｙ　Ａｒｃ旧ｔｅｃｔｕｒｅ　Ｕｓ
ｉｎｇ　Ｐａｒａｌｌｅｌ　ＤａｔａＤｉｓｔｒｉｂｕ
ｔｅｄ　Ａｒｉｔｈｍｅｔｉｃ　）　Ｊ　、ＩＥＥＥＥ
　　Ｊ。

固体回路５Ｃ−１９，３６８（１９８４）に説明されて
いる。

パイプライン・アーキテクチャ−のいくつかの欠点には
、いくつかの処理を実行しているときのパイプラインに
おけるアイドル時間ｍがある。通常、バイブラインを実
現するために用いる回路の速度は、その回路の一部をな
す周辺の種々の加算器を実現するために用いた回路より
も速い。従って、前記パイプライン構造にはまだいくつ
かの欠点が存在する。

〔発明の概要〕

ここに開示し、特許請求の範囲に記載した本発明は、バ
タフライ処理を実行する高速フーリエ変換プロセッサを
有する。入力ベクトル及びフーリエ係数を記憶し、複素
乗算を実行して複素積を得た後、入力ベクトルのうちの
一つと複素加惇をするだめにメモリが備えられる。複素
乗算はシストリック複素乗算器により実行され、このシ
ストリック複素乗算器は係数の実数及び虚数部と、入力
ベクトルのうちの一つの実数及び虚数部との複数の積を
逐次発生する。これらの積は逐次発生し、その間に１ビ
ツト遅延を買いで予め定めた方法で出力される。先ず、
乗算器を介する第１バスで係数の実数部を用いた前記積
を乗算器により発生し、次いで係数の虚数部を用いる前
記積と加算をするために乗算器の入力にフィードバック
する。次の処理の第１バスで前記積を形成するために必
要なステップは第２バスの処理とインタレースされる。

第２バスにおいて、複素数部分の実数及び虚数部分は高
速加算器に入力され、乗算器の１クロツク・サイクルだ
け隔てられる。高速加算器はメモリにある他の入力ベク
トルの実数及び虚数部分と加算及び引算処理を実行する
。高速加算器は乗算器の速度の１／２で動作する現在処
理と次の処理と　・のインターレースによって乗算器を
介して連続的にデータが流れるようにする。

本発明及びその効果をより完全に理解するために、添付
する図面と関連させて以下説明を行なう。

〔実施例の説明〕

ＦＦＴアルゴリズムの計算にはベクトル回転（単位ペタ
ー・ルにより乗算）が必要である。次に示すような１回
の回転計算を「バタフライ」と呼ぶ。

ＷＲＢＲ−Ｗ、Ｂ１＝ＺＲ（１１ Ｗ、ＢＲ−ＷＲＢ、＝Ｚ、　　　　　　　　　！２また
だし、Ｂは入力ベクトル、Ｚは出力データ、Ｗは「トラ
イドル（ｔｗｉｄｄｌｅ　）係数」又はＦＦＴバタフラ
イと呼ぶ単位ベクトルである。（１）および（り式から
明らかなように、ＦＦＴバタフライに関するベクトル回
転を直接実行する゛ことには、４回の乗算による複素乗
算＋加算＋引算が含まれ、複素乗算積２，２．を得る。

更に、基数２のＦＦＴバタフライの計算には複素積Ｚと
入力データ・ベタ１ルＡとの２回の加算及び２回の引算
が必要である。

ＡＲ＋／−ＺＲ（３） Ａ１＋／−Ｚｌ　　　　　　　　　　　　　（４］（１
）及び（２）式を参照すると、ＺＲ及びｚ■の計算には
実数成分のＦＦＴ係数ＷＲ及び虚数部分のＦＦＴ係数Ｗ
■、が用いられることが分かる。このデータを（３）及
び（４）式に代入する前に、ＦＦＴ係数ＷＲ又はＷｌ、
逆に成分ＢＲまたはＷｌのうちの一つを用いて２つの乗
算を実行しなければならない。各計算はベクトルの成分
をメモリからアクセスしなければならないので、以下で
説明するが、計算をバイブライン化することにより、パ
イプラインのＦＦＴ係数ＷＲを用いてＺＲ及びＺｌを計
算するのに必要とするアクセスを１回だけにする。

第１図を参照すると、ＦＦＴオペレーションを実行する
ディジタル・プロセッサのブロック図が示されている。

シストリック・プロセッサ用の１御信号を発生する制御
回路１０が備えられる。

ＲＯＭ１２にはＦＦＴ係数ＷＲ及びＷｌが記憶され、バ
ス１５を介して演算装置１４に出力される。

演算装置１４は、以下で説明するように、加算器のセル
のシストリック・アレー形式にある。入力ベクトルＡ及
びＢをロードし、バス１８を介して演算装置１４に供給
するバッファ・データのためにレジスタ・ファイル１６
が儀えられる。演算装置１４の結果はバス２０を介して
レジスタ・ファイル１６に出力され、記憶される。レジ
スタ・ファイル１６はデータ入出力バス２２のインタフ
ェース処理をすることにより、レジスタ・ファイル１６
にデータを入力し、またこれからデータを出力している
。

データ入出力バス２２も処理すべきデータを含むＲＡＭ
２４によりインタフェースされる。このデータはＲＡＭ
２４からレジスタ・ファイル１６に転送されて処理され
、処理結果がレジスタ・ファイル１６からデータ入出力
バス２２に出力され、ディジタル・プロセッサから出力
される。

第２図を参照すると、第１図のディジタル・プロセッサ
のブロック図が示され、演算装置１４も詳細に示されて
いる。演算装置１４の中心には、修正ブース（Ｂｏｏｔ
ｈ　）アルゴリズムを用いて乗算を実行するパイプライ
ン・アレー乗Ｎ５２６がある。パイプライン・アレー乗
算器２６はキャリーを保持するシストリック・アレー乗
算器である。

入力ベクトル成分Ｂ　及びＢ１はバス２８上の被乗数と
して乗算される。パイプライン・アレー乗算器２６の他
の入力にはＦＦＴ係数ＷＲ及びＷｌから発生したブース
演算子である。その和出力はバス３０に出力され、また
キャリー出力はバス３２に出力される。

入力ベクトル成分ＢＲ及びＢ１はレジスタ・ファイル３
４、またこれに代わってレジスタ・ファイル３６に記憶
される。バス制御回路３８はレジスタ・ファイル３４と
バス４ｏ及び４２を介してそれぞれインタフェース接続
され、Ｂベクトルがレジスタ・ファイル３４及び３６の
うちのいずれに記憶されているかに基づき、レジスタ・
ファイル３４及び３６の間で交番することができる。バ
ス制御回路３８はパイプライン・アレー乗算器２６に入
力するためにバス２８に接続されている。

ＦＦＴ係数Ｗ　及びＷｌはＲＯＭ１２に記憶され、かつ
レジスタ４７に一時記憶される。レジスタ４７はバス４
６を介してマルチプレクサシ４４に接続されている。Ｆ
ＦＴ係数ＷＲ及びＷｌはそれぞれ１６ビツト幅であり、
両者は３２ビツト幅のバス４６に同時に出力され、かつ
レジスタ４７に記憶される。マルチプレクサ４４は１６
ビツト幅の出力を有し、ＦＦＴ係数Ｗ　及びＷＩの間で
選択可能であり、バス４６を介して出力される。

マルチプレクサ４４の出力は遅延線４８に入力され、遅
延線４８は少なくとも２つの最上位ビットに対して１ビ
ツトの遅延をし、その遅延の１ビツトは次の２ビツトに
対するものであり、かつ付加的な１ビツト遅延は次の対
の各ビットのものであり、２つの最上位ビットは総計８
ビツトの遅延をする。従って、遅延線４８には１６本の
遅延線がある。

遅延線４８の出力はブース・デコーダ５ｏに入力され、
ブース・デコーダ５０は修飾したブース・アルゴリズム
によって３ビツトを調べ、ブース演算子を発生する。乗
算器の２ビツトのそれぞれに対して、１ブース演算子を
発生するので、１６ビツト・ワードに対して８ブース演
算子を発生する。これは、レーウイスＰ、ルーピンフィ
ールド（Ｌｅｗｉｓ　Ｐ　Ｒｕｂｉｎｆｉｅｌｄ）、「
乗算用修飾ブース演算子の証明（、Ａ　Ｐｒｏｏｆ　ｏ
ｒ　Ｔｈｅ　Ｍｏｄｉｆｉｅｄ　Ｂｏｏｔｈ’ｓＡｌｏ
ｇｏｒｉｔｈｍ、Ｆｏｒ　Ｈｕｌｔｉｐｌｉｃａｔｉｏ
ｎ）　、Ｉ　Ｅ　Ｅ　Ｅコンピュータ学会、１９７５年
１０月、第１０１４頁〜第１０１５頁に記載されている
通常のアルゴリズムである。更に、修飾したブース演算
子の説明は、テキサス・インスツルメンツ■に譲渡され
、１９８４年８月３１日に出願された米国特許出願筒６
４６，８６８号にも見出すことができる。

パイプライン・アレー乗算器２６は先ず積ＷＲＢＲ及び
ＷＲＢｌの値を計算し、その和及びキャリーをバス３０
及び３２に出力する動作が可能である。これをパイプラ
イン・アレー乗算器２６を介する「第１バス」と考える
。次いで、バス３０上の和ＩＩ　Ｓ　１１はバス５４を
介して２ビツト遅延５２に入力され、従ってキャリー１
１　Ｃ１１はバス５６を介して２ピツト遅延５２に入力
される。遅延された和及びキャリーはバス５８及び６０
を介してパイプライン・アレー乗算器２６の和及びキャ
リー入力に入力される。以下で説明するように、処理が
初期化されたときに、１６ビツト幅のＯ値ワードをパイ
プライン・アレー乗算器２６の和入力及びキャリー入力
に入力させるゲート６２が備えられている。

第１バスの後にパイプライン・アレー乗４Ｂ２６に和入
力及びキャリー入力がフィードバックされたときは、Ｗ
Ｉの値がマルチプレクサ４４に入力され、被乗数の８　
及びＢＲが再び「第２バス」■ のために、パイプライン・アレー乗算器２６を通過する
。この結果、最初に７　、次に７１を１ビット遅延して
複素積成分Ｚ　及びＺｌの値を出力する。

この第２バスにおいて、第１バスからフィードバックさ
れたＷＲ−ＢＩｌの和及びキャリーの値からＷ、Ｂ、の
値を引算する。この引算処理は乗数又は被乗数の符号を
変更することにより行なわれる。

これには通常の回路（図示せず）が利用される。

バス３０及び３２上のパイプライン・アレー乗算器２６
の和及びキャリーは、それぞれ加算処理用に構成された
高速加算器６４及び引算処理用に構成された高速加算器
６６に入力される。高速加算器６４及び６６の入力はバ
ス６８に接続され、マルチプレクサ７０から六入カベク
トルの実数及び虚数部分を受け取る。高速加算器６４及
び６６は、ラッチ入力を有し、乗算器クロックの一つ置
きのクロック・サイクルでのみデータを入力する。

マルチプレクサ７ｏの入力はバス制御３８の出力に接続
され、レジスタ・ファイル３４又は３６から成分Ａ　及
びＡ１を受け取る。高速加算器６４及び６６はラッチ入
力を有し、パイプライン・アレー乗算器２６の一つ置き
のサイクルでのみ入力を受け取る。

＾速用算器６４はレジスタ７２の入力及びレジスタ７４
の入力に接続した出力を有し、その結果を記憶する。レ
ジスタ７２は（３）式の加算処理を記憶し、またレジス
タ７４は（４）式の加算処理を記憶する。同様に、高速
加算器６６の出力はレジスタ７６及びレジスタ７８に入
力され、かつレジスタ７６は（３）式の引算処理を含み
、レジスタ７８は（４）式の引算処理を含む。レジスタ
７２及び７６の出力は３２ビツトのバス８ｏ上で組合わ
せられ、マルチプレクサ８２の一方の入力に供給される
。レジスタ７４及び７８の出力は３２ビツトのバス８４
上で組合わせられ、マルチプレクサ８２の他方の入力に
供給される。マルチプレクサ８２の出力はバス制御回路
３８を介してレジスタ・ファイル３４及び３６の入力に
接続される。マルチプレクサ８２は（３）及び（４）式
の加算及び引算処理を組合わせる動作が可能であり、３
２ビツト・ワードとしてレジスタ・ファイル３４か、又
はレジスタ・ファイル３６に記憶する。

動作において、■８は高速加算＠６４及び６６の第１の
入力であり、その出力はレジスタ７２及び７６に記憶さ
れる。パイプライン・アレー乗算器２６は、以下で説明
するように、インターリーブ構造であり、高速加締器６
４及び６６の動作に対して１ビツト遅延させる。これに
よって高速加算器６４及び６６はパイプライン・アレー
乗算器２６の１７２速度で動作することができる。パイ
プライン・アレー乗算器２６の最初の計算により、ＺＲ
を発生して高速加算器６４及び６６に入力し、それぞれ
入力ベクトルＡとの加算及び入カベ・クトルＡからの引
算をする。１ビツトの遅延後に、その結果がレジスタ７
２及び７６に記憶されると共に、ｚｌの値が高速加算器
６４及び６６に入力されてその結果がレジスタ７４及び
７８に記憶される。パイプライン・アレー乗算器２６を
介するデータの流れがアイドル時間なしに一定であるこ
とは、本発明の重要な特徴である。以下で説明するイン
ターリーブ構造によって、パイプライン・アレー乗算器
２６を介するデータの流れでは高速加算器６４及び６６
のいずれにもアイドル時間がなく、両者の処理速度の２
倍である。更に、ＲＯＭ１２は、各位ｎからＷＲ及びＷ
ｌの値をアクセスするので、パイプライン・アレー乗算
器２６の１／４速度でアクセスするだけでよい。

パイプライン・アレー乗剪器２６による被乗数のＢＲ及
びＢ１、及び乗数のＷＲ及びＷｌの処理では、複数の部
分積を形成してこれらを加算する必要がある。この実施
例では、以上で説明したように、使用した乗算構造が修
飾したブース・アルゴリズムである。この修飾したブー
ス・アルゴリズムでは、ビットを各グループで重畳して
いる１ビツトと、右の最下位ビットに割り付けたビット
とを有する３グループに区分することによって、遅延線
４８の乗数ビット出力を分析することが必要である。従
って、１６ビツトの乗数は８Ｘ３ビツト・グループとな
る。各グループは一つの部分積に対応し、かつ１６ビツ
トの乗数は８つの部分積を発生しなければならない。こ
れらの部分積を発生するためには先ず「修飾したブース
演算子」を判断して処理を決定すること゛が必要であり
、この処理はそれぞれの部分積を発生するために与えら
れた被乗数に基づいて実行されなければならない。修飾
したブース演算子は°“Ｏ１１，１１＋１１＋、“−１
″、“＋２″及び゛−２パである。−″を付けたものは
被乗数の２の補数を発生する必要があり、２′′を付け
たものは被乗数を１ビットだけ左ヘシフトすることが必
要であり、１１１　Ｉ＋があるものはシフトを必要とし
ない。従って、部分積は最大１桁だけ左ヘシフトした被
乗数又はその２の補数からなる。“ＯＩ＋の修飾したブ
ース演算子は全論理ビットが論理″゛０″の部分積とな
る。

この実施例では１の補数及び入力加算器の初期キャリー
を使用している。

部分積は、生成された後、２桁だけ逐次シフトされ、前
の部分積に加算される。これには、先ずパイプライン・
アレー乗算器２６により第１の部分積を発生すること、
次に第２の部分積を発生して第１の部分積と加算するこ
とが必要となる。従って、残りの部分積を発生して中間
和に加算する。

第３図を参照すると、パイプライン・アレー乗算器２６
及びブース・デコーダ５ｏの拡大ブロック図が示されて
いる。パイプライン・アレー乗算器２６は８段からなり
、各段は１列のレジスタ（ＲＥＧＩ〜ＲＥＧ９）と、１
列のブース加算器セル（Ｂ　　ＣＥＬＬ１〜Ｂ　　ＣＥ
ＬＬ８）とを有する。各列のブース加Ｉｉｉ［ｒＡセル
はそれぞれ１６ブース・マルチプレクサと、関連する全
加算器とからなる。それぞれの和及びキャリーに加えて
、先ずＢ値を各レジスタに記憶し、次にブース演算子が
入力される次段の加算器により加算し、特定の処理を決
定してそれぞれの部分積を発生する。次に、この部分積
を出力し、次段のレジスタに記憶する。修飾したブース
演算子は、以下で説明するように、与えられたブース加
算器セルに対する被乗数（Ｂ　又はＢＲ）の特定ビット
について実行！ すべき処理を決定する。

パイプライン・アレー乗算器２６を介する乗数及び被乗
数の１バスの場合は、先ず１６ビツトのＢ値をＲＥＧｌ
に記憶してＢ−ＣＥＬＬｌに入力する。乗数の最初の２
ビツトはグループ８６を形成し、その１ビツトを８−Ｃ
ＥＬＬＩのブース演算子を決定するために割り付る。次
に Ｂ−ＣＥＬＬｌの出力はパイプライン・アレー乗算器２
６の第２のクロック・サイクルでＲＥＧ２に入力され、
これに記憶される。この第２のクロック・サイクルにお
いて、乗数の次の２ビツトはブース・デコーダ５０に入
力される。これによって、グループ８６の最上位ビット
と組合わせてグループ８８を形成する。グループ８８を
形成するためには、ブース・デコーダ５ｏに前のグルー
プにおける最上位ビットに対する１ビツトの遅延を付加
してこのビットを保持することが必要である。

次に、これらの３ビツトを調べて、 Ｂ−ＣＥＬＬ２に対する修飾したブース演算子を決定す
る。次いで、第２の部分積を形成して、前の部分積及び
第３のクロック・サイクルでＲＥＧ３に出力を記憶する
。これより和及びキャリーが出力されるまで、更に５ク
ロツク・サイクルだけこの動作を継続する。従って、パ
イプラインに配置された各被乗数について、遅延線４８
へ乗数を入力するので、各部分積についてブース演算子
を発生するために必要とする３ピツトが適当なタイミン
グでブース・デコーダ５０の入力に供給される。これに
よってその部分積及び和を連続的に発生することができ
る。

乗綽処理では、ＷＲの値が遅延線４８に入力され、ＢＲ
の値がバス２８に送出される。第１段のＢ−ＣＥＬＬＩ
では、ＷＲＢＲの第１の部分積が形成され、これをビッ
ト“Ｏ”及び“１″の部分積と呼ぶ。次いで、１ビツト
の遅延をし、Ｗｌを遅延線４８に入力し、ＢＲをパイプ
ライン・７レ一乗算器２６に入力する。これにより“ｉ
″サイクル第１バスが開始される。前のサイクル、即ち
ｉ−１”サイクルの第２バスによりデータがインターリ
ーブされる。

乗算器を介するデータの流れを第１表及び第２表に示す
。第１表にはＢを一定とした実数及び虚数部の変形を示
し、また第２表にはＷを一定とした実数及び虚数部の変
形を示す。

次式が成立する。

ＷＲＢＲ＝ＲＲ（５） ＷＲＢ１＝Ｒｒ　　　　　　　　　　　　　　＋６）Ｗ
、ＢＲ＝ＩＲ＋７） Ｗ、Ｂ、＝ＩＩ　　　　　　　　　　　　　　＋８）各
ビット対Ｏ〜１．２〜３１．、．１４〜１５について各
部分積を発生し、前の中間積と加算する。

Ｎ口の一一一臂へ臂へ−ｎ哨υΦ ニー匡−（！　−Ｑｌ：　−Ｃｅ：　−（ｅ：　−Ｑニ
ー１！Ｎ口り一の一臂Ｎ彎Ｎ−の−りψ −ＣＩ；Ｃｅ：　−−（！ご一−ＣＩ：Ｃ？　−−Ｃｅ
：Ｃ１：つ−Ｃ％Ｊの寸りＯトの■Ｑ　ｙ　Ｃ％Ｊの寸
ｒ　ｒ　ｒ　ｒ　ｒ　ｒ　ｒ　ｒ−へへへ〜Ｎｚｌ ＋１１１１１１１１１１ 、＝″１ ｃａｌ　　ロ１　　ロｌ　　咄　−Ｉ　　ＮＣＩ　Ｎ：
　　　　−ご　　　　−ご　−− １＋　　　１　　　・　　―　　・　　　拳　　　・　
　　ｅ　　　・　　　・　　　・　　　場　　　・電 ＩＩ働−Φ・・・・・ｅ＋ｅ＋ １・−・・骨・・・・・・・・ 第１表において、見出し’ＣＬＫ”（クロック）の下の
左欄にアレー乗算器のクロック・サイクルを示す。クロ
ックＩＩ　ＯＩ＋はシステムがスタートして最初の計算
を実行したときの初期クロックに対応する。これを「ラ
ンピング・アップ（ｒａｍｐｉｎａｕｐ）　Ｊと呼ぶ。

初期のクロック“０”において、ＦＦ’Ｔ係数Ｗの最初
の値をＲ８と呼ぶ。最初の８入力データ・ベクトルの実
数部をＲ８と呼ぶ。遅延線４８のＷ入力に、Ｒの値を入
力し、Ｒｏの値をバス２８に出力する。このため、バイ
ブライン・アレー乗算器２６の“０゛′段においてビッ
ト１１０　ＩＴ〜゛１についての部分積がＲＲｏどなる
。

第ｉａ＋はＷ値を示し、第２欄はＢ値を示し、下付き文
字“０”は第１の入力データ・ベクトル“０″〜“”１
６”についての第１の入力データ・ベクトルと、関連す
るＦＦＴ係数Ｗとを示す。クロック１１１　Ｉ＋では、
乗算器に何も入力されず、第２段でＲＲｏの値を計算し
、ピッド２″及び３″のときに出力する。クロック゛２
パではＢ入カベクトル成分Ｒの実数部と、Ｗ係数Ｉ　、
の虚数部を乗算器に入力し、パイプライン・アレー乗算
器２６の第１段に積ＩＲｏを得る。

部分積ＲＲｏはパイプライン・アレー乗算器２６を伝搬
してクロック“７″で出力される。同様にして、積ＩＲ
を部分積ＲＲｏから１クロック遅れ、クロック″９”で
出力される。以上で説明したように、部分積ＲＲｏは第
１のＢ入力ベクトルに対するＷ　に対応する。ＲＲｏ及
びＩＲｏがパイプライン・アレー乗算器２６から出力さ
れると、第１バスが形成される。同様にして、クロック
“４″及び゛６”で開始された第２のＢ入力ベクトルは
クロック゛’１１’及びクロック゛１３パで完了する。

クロック“９″では、部分積ＲＲｏが２ビツト遅延５２
により遅延されてバイブライン・アレー乗算器２６の和
及びキャリー入力にフィードバックされる。同様に、Ｗ
係数■。の虚数部と、第１のＢ入力ベクトルに関する８
入カベクトル■。はバイブライン・アレー乗算器２６に
入力され、これを伝搬する。この動作では、値ＷＩＢ１
を前の部分積ＷＲＢＲから引算する。これを部分積■Ｉ
ｏの前の−゛′により表わす。これは被乗数の単純な２
の補数により実行される。この２の補数を取る回路は図
示されていないが、これに対しては通常の回路を用いる
ことができる。

クロック゛′９”は第１バスによる第２バスのインター
リーブの開始を表わず。例えば、第３のＢ入力ベクトル
成分Ｂ２に対する第１バスはクロック゛８”で入力され
るＷ係数Ｒ２の実数及びクロック”　１０　”でＷ係数
Ｉ２の虚数部に８入力ベクトルの実数部を有する。従っ
て、部分積ＲＲｏはパイプライン・アレー乗算器２６を
伝搬してクロック゛１５″で出力され、値ＩＩｏは伝搬
によりりＯツク“１６″で出力される。部分積の前の″
“−″及び“＋”の表示は乗算器を介する第２バスを表
わす。従って、第２バスは他の処理の第１バスとインタ
ーリーブされる。

クロック“１６ｎの終端で、第１のＢ入力ベクトル成分
に対応するＷ係数及び被乗数を用いる第１の複素乗算を
出力する。これはＺＲに対応する。

同様にして、Ｚｌの値はクロック“１８”で出力される
。これは、ＩＲｏの値が２ビツト遅延５２を介して戻さ
れて「取り込」まれ、クロック゛１３”でアレーに入力
され、Ｗ係数Ｉ。の虚数部のＲ及びＢ入力ベクトルのＷ
係数Ｉ。と加算される 一ＩＩｏを出力したときは、六入カベクトルの実数部に
加算され、またこれから引算される。これを欄Ａ　及び
Ａ２に示す。１ＩＩＡ１において、こと値を高速加算器
６４により加算して和を得ると共に、引算を高速加算器
６６により実行する。

ＲＡＯ＋は第１の８入カベクトルのＡの実数部に対する
加算処理を表わす。同様にして値ＲＡＯ−を出力して引
算処理を表わす。この値はクロック“１７″で出力され
る。同様にして、虚数部及び引算はクロック“°１９”
で出力されることが分かる。高速加算器は加算器の２つ
のクロック・サイクルに亙っで動作し、これによって高
速加算器６４及び６６を低速度で動作させている。

クロック“１５”パイプライン・アレー乗算器２６が「
Ｒ終段階に達する」と、全段がフルとなり、データを連
続処理している状態になる。パイプライン・アレー乗算
器２６がフルでないのは、初期のクロック・サイクルの
ときだけである。

更に、第１表、及びＷ係数及び８入カベクトルの実数及
び虚数部がパイプライン・アレー乗算器２６に入力され
るシーケンスを参照すると、クロック“ＯＮ及び“２″
に対してＢ入カベクトル成分Ｂ　の最初の値をアクセス
し、Ｒｏの値を供給することは明らかである。従って、
クロック゛９”及び”　１１　”まで、虚数１゜に値を
必要としない。

従って、これらはレジスタに記憶され、クロック“９″
及び“１１”で用られる。

適当なタイミングを得るために、８入力ベクトルは、レ
ジスタに実数部Ｒｎを記憶し、かつ遅延回路に虚数部を
入力してこれを１０クロツク・サイクル遅延して第２の
レジスタに記憶することが必要である。従って、実数部
Ｒ１を４クロツク・サイクルだけレジスタに記憶し、伯
の４クロツク・サイクルで次の実数ＩＲの値をレジスタ
にｎ＋１ ０−ドする。他のクロック・サイクルでＲｎレジスタと
Ｒレジスタとの間での選択をするためにマルチプレクサ
（図示なし）が備えられている。

例えば、クロック・サイクル゛８”では、Ｒ２の値を出
力し、次いで■。の値を出力する。次のクロック・サイ
クルでは、Ｒの次にｒ。を再び出力する。これによって
、８入カベクトル入力をパイプライン・アレー乗算器２
６に対するクロック速度の１／４でアクセスさせる。

Ｗ係数はＷ係数出力に対して実数Ｒ１及び虚数部］。を
有し、レジスタに記憶されている。更に、実数Ｒ１及び
虚数部■。は遅延回路に入力され、この遅延回路は８ク
ロツク・サイクルだけこれらの値を遅延して実数Ｒ及び
虚数部■　　を出ｎ−１ｎ−２ 力する。動作では、予め定めたパターンに従ってＲ、Ｉ
　　、Ｒ及び１　　間での選択をするｎ　　　ｎ　　　
ｎ−２ｎ−ま ためのマルチプレクサを備える。マルチプレクサは先ず
Ｒ１次に１１更にＲ＠選択をする。

ｎ　　　　　ｎ　　　　　ｎ−２ 次にＲ及び■。の新しい値を第１のレジスタに入力して
、Ｒ及びＩ　　の値を得る。第１表ｎ−２０−２ を参照すると、クロック“８′″と、クロック゛１１”
との間でＲ及びＩ２の値が第１のレジスタに記憶され、
またＩ　及びＲ８の値が遅延レジスタに記憶されること
は、明らかである。次に、Ｒ２及びＩ２の値は８クロツ
ク・サイクルだけ遅延されるので、クロック“’　１６
　”とクロック゛１９ｎとの間で選択することができる
。従って、必要とするのはパイプライン・アレー乗算器
２６のクロック速度の１７４でＷ係数を出力することだ
けである。

第２表は、シーケンスのみ異なっており、このシーケン
スはＷ係数数及びＢ入力ベクトルが逆になっている。即
ちＷ係数の実数及び虚数部が４つのクロック・サイクル
について設けられ、これに対してＢ入力ベクトルの対応
する実数入力部が４クロツク・サイクル中に変更される
。

結果が得られ、これをレジスタ７２〜７８に記憶した後
は、その出力をレジスタ・ファイル３４か、又はレジス
タ・ファイル３６かに記憶することができる。動作にお
いて、レジスタ・ファイル３４及び３６は、結果を記憶
するファイルと、データを記憶するファイルとの間で「
交番」する。

データの処理は、最終結果が得られるまで、結果を入力
ベクトルとしてパイプラインを介して前のサイクルに戻
す。従って、パイプライン・アレー乗算器２６の１サイ
クルにおいて、レジスタ・ファイル３４は入力データを
保持することができ、かつレジスタ・ファイル３６はそ
の結果を記憶する。次のバスでは、これらの結果は入力
データとなり、かつレジスタ・ファイル３４は結果を記
憶する。従って、レジスタ・ファイル３４及び３６は、
タイム・テーブル、及び周波数サンプルを表わす処理デ
ータからなる入力データの一時記憶として用いられる。

これは１６（列）Ｘ３２（列）アレーとして編成されて
いる。２つのレジスタ・ファイル３４及び３６を各サイ
クルにおいて「交番」する前に、１６変換を必要とする
のみである。

これによって、乗算器アレーが高速のクロック速度で動
作し、同時にレジスタ・ファイルが遅いクロック速度で
ロード及びアンロードすることができる。

第４図を参照すると、第１列に３個のブース・セル、ま
た隣接する列に１個のブース・セルを示すパイプライン
・アレー乗算器２６の２段のブロック図が示されている
。第１列はＢ、ビットを処理するブース・セル９０と、
Ｊ−１ビツトを処理するブース・セル９２と、Ｂ１＋１
ビツトを処理するブース・セル９４とからなる。第２の
列はＪ＋１ピットを処理するブース・セル９６とからな
る。ブース・セル９２〜９６はそれぞれ入力総和結果を
記憶するＳレジスタ９８と、Ｂ入力ベクトル・データを
記憶するＢレジスター００と、キャリー人カデータを記
憶するＣレジスター０２とを有する。ブース・セル９２
〜゛９６はそれぞれＳレジスタ９８の内容と、Ｃレジス
ター０２の内容とを受け取る入力を有する。更に、Ｂレ
ジスター００はＢベクトル・ビットの真及び補数形式を
記憶し、ブース・セル９２〜９６の対応する１つに入力
する。更に、ブース・セル９２〜９６に対する入力はＢ
の値、例えばＢｉ＋１の値をシフトした真及び補数形式
であり、その反転形式はブース・セル９０に入力される
。

第１列のブース・セル９０〜９４はバス・ライン１０４
により制御されており、以下で説明するように、これに
は前の和及びキャリーに加算される値を決定するブース
・デコーダ５ｏが発生した修飾したブース演算子が含ま
れる。第２列のブース・セル９６はバス１０６を介して
入力される修飾したブース演算子により制御される。

動作では、Ｂ、の値がブース・セル９０に関連しだＢレ
ジスター００に入力される。修飾したブース演算子はＢ
、の値、Ｂ、の補数、Ｂｉ＋１の値、又はＢ１＋１の補
数若しくはキャリーＣ１の値と和Ｓｉの値とを加算した
ものを選択する。ブース・セル９０はＳ、　及びＣ１＋
２の値を発生すると共１＋２ に、Ｂ、の値を通過させる。第２列では、ブースト セル９４からＢｉ＋１の値がブース・セル９６に関連す
るＢレジスター００に入力される。しかし、前の処理に
おける和の値は前の部分積の中間和を表わし、Ｃレジス
ター０２に記憶された値と共にブース・セル９２からシ
フトされる。各列に対しては、修飾したブース・アルゴ
リズムに従ってシフトを行なう。

第５図を参照すると、Ｓレジスタ９８、Ｓレジスタ１０
０及びＣレジスタ１０２に加え、ブース・セル９２〜９
６のうち１について更に詳細なブロック図が示されてい
る。修飾したブース・セルはマルチプレクサ１０８から
なり、マルチプレクサ１０８はＢレジスタ１０ｏの真及
び補数出力と、次の段のＢｉ＋１の真及び補数出力とを
入力している。マルチプレクサ１０８は修飾したブース
演算子を表わす４本のライン１１０により制御されてい
る。以上で説明したように、この実施例では、修飾した
ブース演算子は′−２”、“−１″、１１０１１、＋１
”及び“＋２”である。従って、ライン１１０のいずれ
かにおけるハイ状態は、“ＯＩＩを除き、全て修飾した
ブース演算子を表わしている。このハイ状態は、ライン
１１０の全てが論理０のときに現れる。論理０のときは
、°゛０″の値をマルチプレクサ１０８からライン１１
０に出力する。“＋１”の値のときは、Ｂｉ＋１の値を
出力する。１１　１１１及び１１　２　ＩＩのときは、
Ｂｉ及びＢ　、、１の反転形式を出力する。

マルチプレクサ１０８の出力、Ｓレジスタ９Ｂの出力及
びＣレジスタ１０２の出力は全加算器１１２に入力され
る。即ち、全加算器１１２のＡ及びＢ入力はＳレジスタ
９８の出力及びライン１１１にそれぞれ接続され、その
キャリー入力はＣレジスタ１０２の出力に接続されてい
る。全加算器については１．畦　術者のためのＴＴＬ−
一タ・ブック（１９７６年１０月、テキサス・インスツ
ルメンツ（株）発行、第２版、第７頁〜第５４頁）、及
びＪ、Ｌヘンリーに対して１９８４年５月１５日に発行
された米国特許出願筒４．４４９゜１９７号に詳細に説
明されている。全加算器１１２はキャリーＣ１＋２の値
及び和Ｓｉ＋２の値を出力する。更に、Ｂ１の真値も出
力する。

Ｓレジスタ９８〜Ｃレジスタ１０２はライン１１４の単
一クロック信号によりりＯツク駆動される。ライン１１
４のクロック信号を与えられた列の全ブース・セルに供
給することによって、８入力ベクトルの全ビットをパイ
プラインを介し、同期してクロック駆動させる。

第６図を参照すると、第５図のブース・セルのブロック
図が示されている。各図で同一の符号は同様の部分を表
わしている。マルチプレクサ１０８は４つのＡＤＮゲー
ト１１８．１２０１１２２及び１２４の出力端に相互接
続されている４入力のＮＯＲゲート１１６からなる。Ａ
ＮＤゲート１１８．１２０．１２２及び１２４はそれぞ
れの一方の反転入力をライン１１０の一つに個別的に接
続している。ＡＮＤゲート１１８の使方の反転入力はＳ
レジスタ１００の非反転出力に接続される。

またＡＮＤゲート１２０の他方の反転入力はＳレジスタ
１００のコンプリメンタリ出力に接続されている。ＡＮ
Ｄゲート１２２の他方の反転入力はＢ１＋１の反転出力
に接続され、ＡＮＤゲート１２４の使方の反転入力はＢ
ｉ＋１に接続されている。

全加算器１１２は、和Ｓｉ＋２を出力する４入力のＮＯ
Ｒゲート１２６と、キャリーＣ１，２を出力する３入力
のＮＯＲゲート１２８とから形成されている。ＮＯＲゲ
ート１２６の４入力はそれぞれ４つのＡＮＤゲート１３
０．１３２．１３４及び１３６のうちの一つの出力に接
続されている。

ＡＮＤゲート１３０，１３２．１３４及び１３６はいず
れも反転入力を有する。ＡＮＤゲート１３０の一方の反
転入力はＳレジスタ９８の出力に接続され、その他方の
反転入力はＡＮＤゲート１３８の出力に接続されている
。ＡＮＤゲート１３２の一方の反転入力はＣレジスタ１
０２の出力に接続され、その使方の反転入力はＡＮＤゲ
ート１４０の出力に接続されている。ＡＮＤゲート１３
４の一方の反転入力はＮＯＲゲート１１６の出力に接続
され、その他方の使方の反転入力はＡＮＤゲート１４２
の出力に接続されている。ＡＮＤゲート１３６は３入力
を有し、その第１がＳレジスタ９８の出力に接続され、
その第２がＣレジスタ１ｏ２の出力に接続され、その第
３がＮＯＲゲート１１６の出力に接続されている。ＮＯ
Ｒゲート１２８は３入力を有し、それぞれＡＮＤゲート
１３８〜１４２の出力に接続されている。

第７図を参照すると、それぞれ幅３２ビット×深さ３２
ワードのバッファＡ及びバッファＢと呼ぶ第２図のレジ
スタ・ファイル３４及び３６の配列が示されている。Ｒ
ＯＭ１２はＷファイルにより表わされ、幅３２ビット×
深さ３２ワードである。各ワードの第１の１６ビツトは
実数値であり、第２の１６ビツトは虚数値である。Ｗ係
数は入力されるデータをそれぞれ変換するときに用いる
フーリエ係数である。この実施例では、基数２のＦＦＴ
の場合にデータを４回処理しなければならない１６デ一
タ点が用意され、これがデータの点数の基数２に対する
アルゴリズムとなっている。

もし、１０２８データ点あるときは、これには１０回演
算装置を介する必要があり、かつ１０２８個のＷ係数を
必要とすることになる。

バッファＡは上部及び下部の２部分に分割される。上部
の１６６位置それぞれ３２ビツトのデータ・ワードを有
し、六入カベクトルの実数及び虚数部を表わしている。

下部の１６６位置それぞれ３２ビツトのデータ・ワード
を有し、８入カベクトルの実数及び虚数部を表わしてい
る。バッファＢは６４通りの結果によりロードされる。

これらは、最初の位置が３２ビツトのワードのうちの最
初の１６ビツトに結果ＡＲ＋ＺＲを含み、また３２ビツ
トのデータ・ワードのうちの第２の１６ビツトに結果Ａ
　　−ＺＲを含む。第２の位置では、Ａ・及びＺｉによ
る結果を記憶する。バッファＢ■ における最初の２位置はバッファＡの最初の位置及び上
部に対応し、またバッファＡの下部における最初の位置
は次のサイクルのＡ及びＢ入力ベクトルを形成する。

動作では、バッファＡは先ず上部及び下部のＡ及びＢ入
力ベクトルによりロードされる。演算装置を介する最初
のサイクルでは、バッファΔのデータを処理してその結
果をバッファＢに記憶する。

次に、バッファ已にある結果はＡ及びＢ入力ベクトルと
なって処理され、その結果がバッファＡに記憶される。

バッファＡの情報を入力データ・ベクトルとして再び処
理し、バッファＢに記憶するので、１６デ一タ点には更
に２サイクルが必要であり、バッファＢにあるその結果
は入力データ・ベクトルとして処理され、その結果がバ
ッファＡに記憶される。この時点で、バッファＡの結果
はデータ入出力バス２２に出力され、新しいデータがバ
ッファＢに記憶される。最初にデータを記憶するのがバ
ッファＡか、バッファＢかということは重要ではなく、
動作は最初のバッファで開始され、これに新しいデータ
を記憶する。

ここで第８図を参照すると、第２図のレジスタ・ファイ
ル３４．３６及びバス制御回路３８を拡大したブロック
図が示されている。バッファＡには付加的なレジスタ・
ファイル３４′が付加され、バッファＢには付加的なレ
ジスタ・ファイル３６′が付加される。動作において、
データは最初、バッファＡのレジスタ・ファイル３４に
ロードされ、また結果はバッファＢのレジスタ・ファイ
ル３６に記憶される。第７図を参照して先に説明したよ
うに、レジスタ・ファイル３４に最初に記憶したデータ
点のＦＦＴについて全てのデータを処理するまで、これ
らの２つのバッファＡ及びＢは４サイクルだけ交番され
る。しかし、変換する次の集合のデータ点を準備するた
めに、最初に入力データを保持するレジスタ・ファイル
３４′を備える。次の処理サイクルにおいて、レジスタ
・ファイル３４′は入力データを保持し、レジスタ・フ
ァイル３６′は結果を記憶し、かつレジスタ・ファイル
３４′とレジスタ・ファイル３６′との間でデータを授
受するように動作可能である。この処理モードではレジ
スタ・ファイル３４′及び３６′を用いたが、データの
処理の流れを中断させることなく、レジスタ・ファイル
３４か、又は３６かに記憶したデータを出力し、また新
しい入力データを２つのレジスタ・ファイル３４′及び
３６′のうちの一方に入力することができる。この実施
例では、レジスタ・ファイル３４．３４′、３６．３６
′はメモリ・マツプ化された１メモリである。基本的に
必要とすることは、アドレスを処理して外部レジスタに
供給し、又はラッチしてそのアドレス指定後に情報を保
持することだけである。この１メモリのメモリ・マツピ
ングは、メモリの異なる位置をアクセスするときは、ア
ドレスの１ビツトを変更するだけでよい。

次の処理用のメモリを得るために、バス制御回路３８は
多重化された２つのレジスタ２９及び３１を備えている
。レジスタ２９及び３１のうちの一方は第１表の実施例
に従って２クロツク・サイクルで８入カベクトルの虚数
部を遅延し、被乗数のＲ及び■　　を得る。これに対し
て、レジスｎ　　　　ｎ−２ り２９及び３１のうちの一方は、２クロツク・サイクル
でＢ入力ベクトルの実数及び虚数部を遅延し、第２表の
実施例に従って被乗数のＲ１−２及びＩ　　を得ると共
に、他方のレジスタはＲ１及びｒ、を得る。

第９図を参照すると、第１図のＲＡＭ２４からプロセッ
サに新しいデータ・ベクトルをロードするフローチャー
トが示されている。図において、バッファはレジスタ・
フィル３４及び３４′に対応するバッファＡ及びＡ′と
して、またレジスタ・ファイル３６及び３６′に対応す
るバッファＢ及びＢ′としてそれぞれ定義されている。

このプログラムはスタート・ブロック１５０で開始され
、機能ブロック１５２に進み、新しいデータ・ベクトル
をロードする。これによって、ＲＡＭ２４からデータを
アクセスしてレジスタ・ファイル１６に入力する処理が
開始される。次に、プログラムは判断ブロック１５４に
進み、ＡＢフラグがセットされているか否かを判断する
。このＡＢフラグはバッファＡが入力ファイルであるか
、又はバッファＢが入力ファイルであるかを決定する。

次にフラグの状態に基づいて、プログラムは機能ブロッ
ク１５６又は１５８に進み、入力としてバッファＡ及び
Ａ′、又はバッファ８及び８′を決定する。次いで、プ
ログラムは判断ブロック１６０に進み、第１フラグがセ
ットされている否かを判断する。第１フラグは、バッフ
ァＡ又はバッファＢにおけるレジスタ・ファイルのうち
の特定の一つを指定して、ＲＡＭ２４からのデータを受
け取るかを決定するものである。次に、第１フラグの状
態に基づいて、プログラムは機能ブロック１６２に進み
、バッファＡ若しくはバッファＢを入力データ・バッフ
ァとして指定し、又は機能ブロック１６４に進み、バッ
ファ八′又はＢ′を指定する。

機能ブロック１６２及び１６４はＡＢフラグに設定に基
づいている。次に、プログラムはリターン・ブロック１
６６に進み、メイン・プログラムに戻る。従って、新し
いデータをロードするときは、ＡＳフラグ及び第１フラ
グの設定により、バッファＡ、Ａ’　、Ｂ、又はＢ′を
入力データ・バッファとして指定するか否かを判断する
。結果をアンロードするためのプログラムは第９図のフ
ローチャートのものと同一の機構を用いており、いずれ
の登録ファイルがアンロードすべき出力データを含んで
いるのかを判断する。゛データのロード中及びアンロー
ド中は、プロセッサは指定していないレジスタ・ファイ
ルによりデータを処理し続ける。

ここで第１０図を参照すると、レジスタ・ファイル１６
にロードした後、アレー・プロセッサにおけるデータを
処理するフローチャートが示されている。このプログラ
ムはスタート・ブロック１６８で開始した後、判断ブロ
ック１７０に進み、内部カウンタが４カウントに等しい
値になっているか否かを判断する。この実施例では、１
６デ一タ点に基数２のＦＦＴを用いる。カウンタが４に
等しくなっていないときは、プログラムは機能ブロック
１７２に進んでカウントを増加させた後、判断ブロック
１７４に進み、ＡＳフラグがセットされているか否かを
判断する。セットされているときは、プログラムは判断
ブロック１７６に進み、判断ブロック１７６及び１７８
により第１フラグがセットされているか否かを判断する
。判断ブロック１７８における第１フラグの状態により
、プログラムを機能ブロック１８０にセットし、バッフ
ァＢを処理入力バッファとして指定するか、又はバッフ
ァＢを機能ブロック１８２にセットしてバッファＢ′を
処理入力バッファとして指定する。

判断ブロック１７８の第１フラグにより、プログラムは
機能ブロック１８４に進み、処理入力バッファとしてバ
ッファＡを指定させるか、又は機能ブロック１８６に進
み１、処理入力バッファとしてバッファＡ′を指定させ
る。処理入力バッファを判断した後、プログラムは機能
ブロック１８８に進み、パイプラインを介してこのバッ
ファからのデータを処理した後、機能ブロック１９０に
より示すように、結果を処理の出力バッファに記憶する
。

結果を出力バッファに記憶した後、第１フラグは機能ブ
ロック１９２に進み、ＡＢフラグの状態を変化させる。

例えば、バッファＡを１サイクルだけ処理の入力バッフ
ァとして設定したときは、次のサイクルの入力バッファ
としてバッファＢを設定する必要があり、同時にバッフ
ァＡは次のサイクルにおける処理の出力バッファとなる
。次に、プログラムは判断ブロック１７０の入力に戻り
、パイプラインを介して１６デ一タ点を再び処理する。

第１フラグの状態は変化していないので、第１バツフア
は、外部のＲＡＭ２４から新しいデータを受番プ取るか
、又はこれに結果を出力するかが指定される。

４バスの後に、プログラムは判断ブロック１７０からｖ
ｓ能アブロック１９４進み、書き込み又はリセット機能
を実行することにより、ＦＦＴアルゴリズムにより１６
デ一タ点を処理したことをＲＡＭに書き込む。次に、プ
ログラムは機能ブロック１９６に進んで第１フラグを変
更し、機能ブロック１７０の入力に戻る。これによって
、バッファＡ′及びＢ′を処理の入力バッファ及び出力
バッファとして指定し、結果を保持しているバッファＡ
又はＢからデータをアンロードさせて、２つのバッファ
のうちの他方に新しいデータをロードする。この処理は
データの処理速度よりもずっと遅い速度で生起する可能
性がある。

要約すると、シストリック・アレー乗算器を用いるプロ
セッサが備えられた。シストリック・アレー乗算器は修
飾したブース演算子に従って加算器のアレーにより被乗
数を処理するシストリック・アレーからなる。複素数に
関する乗算処理の一部をパイプラインにより進め、次い
で前の計算の乗算を実行するようにパイプラインを介す
る流れをインターリーブさせている。パイプラインから
出力される最終的な結果を全加算器入力して他の項と加
算することができるように、パイプラインを介する２バ
スが必要である。データをインターリーブすることによ
り、全加算器はシストリック・アレーの速度の１／２で
動作することができ、シストリック・アレーの１サイク
ル置きに出力結果が得られる。更に、シストリック・ア
レー乗算器はシストリック・アレーを介するデータの流
れの速度の１／２でアクセスされるだけでよい。

本発明の他の実施例においては、高速フーリエ変換処理
の入力データ・ベクトルが第１のバッファに入力される
と共に、プロセッサの各サイクルの出力結果が同一のバ
ッファに記憶される。処理においては、バッファの入出
力機能を交番させるように、結果を入力ベクトルとして
演算装置を介して戻す処理をし、結果を他のバッファに
記憶させる。付加的なバッファを備え、外部メモリから
の入力データのバッファ動作をし、かつ出力結果のバッ
ファ動作をすることにより、外部メモリとのインタフェ
ースを行なう。高速フーリエ変換演算装置を介して与え
られた一組のデータ点を処理したときは、結果を記憶し
ているバッファを出力バッファとして指定し、かつ新し
いデータを記憶しているバッファを入力バッファとして
指定することにより、高速フーリエ変換演算装置におい
て処理されているデータは、中断されることなく、外部
メモリ装置へ結果を入力又はこれより出力させる。

好ましい実施例について詳細に説明したが、特許請求の
範囲により定める発明の精神及び技術範囲から逸脱する
ことなく、種々の変形、置換及び変更が可能であること
は、理解すべきである。

以上の説明に関連して以下の項を開示する。

（１）２つの複素ベクトルを乗算して複素積を得る複素
乗算器において、 乗数及び被乗数を受け取り、その積を表わす和及びキャ
リーを出力するｎ段のキャリー・セーブ・シストリック
・アレーと、 前記キャリー・セーブ・シストリック・アレーの和及び
キャリー出力を前記キャリー・セーブ・シストリック・
アレーのキャリー及び和入力に選択的にフィードバック
するフィードバック手段と、前記乗数を記憶する第１の
レジスタ手段と、前記被乗数を記憶する第２のレジスタ
手段と、前記第１及び第２のレジスタ手段、及び前記フ
ィードバック手段を制御し、前記シストリック・アレー
乗算器を介する第１バスで前記複素績の実数部における
積のうちの一つ及び前記複素績の虚数部における積のう
ちの一つを処理することにより、２つの前記積を逐次処
理するようにした制御手段と、 第２バス後に前記キャリー・セーブ・シストリック・ア
レーの和及びキャリー出力を加算して複素和を形成する
加算手段とを備えると共に、前記フィードバック手段は
前記第１バスにおいて２つの前記積から和及びキャリー
を前記キャリー・セーブ・シストリック・アレーの和及
びキャリー入力にフィードバック可能に機能し、前記複
素績の実数部における残りの積及び前記複素績の虚数部
における残りの積を加算させ、前記キャリー・セーブ・
シストリック・アレーを介する前記２バスで前記複素績
に対する和及びキャリーを形成させることを特徴とする
複素乗算器。

（２）　　第１項記載の複素乗算器において、前記、制
御手段は与えられた複素績と関連する各バスで前記キャ
リー・セーブ・シストリック・アレーにより処理された
積の間で１段の遅延を挿入すると共に、前記キャリー・
セーブ・シストリック・アレーの前記１段の遅延のそれ
ぞれを介して和及びキャリーを処理するために必要とす
るＸクロック・サイクルにより前記フィードバック手段
から和及びキャリーを遅延する遅延手段を更に備え、 前記１ＩＩＩＩ１１手段は前記キャリー・セーブ・シス
トリック・アレーを介する第２のバスにおける前記複素
績の実数及び虚数部の和及びキャリーを前記キャリー・
セーブ・シストリック・アレーの１つ置きのクロック・
サイクルで出力するように、次の前記複素績の処理の第
１バスを現在複素積の処理の第２バスとインターリーブ
させると共に、連続的なデータを前記キャリー・セーブ
・シストリック・アレーに入力し、前記加算手段は前記
キャリー・セーブ・シストリック・アレーの速度の１／
２で動作することを特徴とするシストリック複素乗算器
。

（３）　　第１項記載の複素乗算器において、前記キャ
リー・セーブ・シストリック・アレーの第１バスにより
処理された積の和及びキャリーは共通の乗数又は被乗数
を有することを特徴とする複素乗算器。

（４）　　第１項記載の複素乗算器において、前記和手
段は高速加算器を有することを特徴とする複素乗算器。

（５）　　第１項記載の複素乗算器において、入力デー
タ・ベクトルを記憶して前記複素績により前記複素和及
び前記引算を実行する第３のレジスタ手段を有し、 前記加算手段は前記第１及び第２の高速加算器を有し、
前記第１の高速加算器は加算処理のために配置され、か
つ前記第２の高速加締器は引算処理のために配置され、 前記制御手段は前記第３のレジスタ手段を制御して、入
力データ・ベクトルの実数部と前記複素績の実数部との
間で加算及び引算処理を実行し、かつ入力データ・ベク
トルの虚数部と前記複素績の虚数部との間で加算及び引
算処理を実行するように、前記第２バスのキャリー・セ
ーブ・シストリック・アレーから出力される和及びキャ
リーに加えて、前記第１及び第２の高速加算器に対して
前記第３のレジスタ手段における前記入力データ・ベク
トルの実数及び虚数部のうちの一つを入力選択すること
を特徴とする複素乗算器。

（６）２つの複素ベクトルを乗算して複素績を得る複素
乗算器において、 乗数及び被乗数を受け取り、その積を表わす和及びキャ
リーを出力すると共に、予め定めたクロック速度で動作
するｎ段のキャリー・セーブ・シストリック・アレーと
、 前記キャリー・セーブ・シストリック・アレーの和及び
キＶり一出力を前記キャリー・セーブ・シストリック・
アレーのキャリー及び和入力に選択的にフィードバック
するフィードバック手段と、Ｘクロック・サイクルによ
り前記フィードバック手段からフィードバックされた前
記和及びキャリーを遅延する遅延手段と、 前記キャリー・セーブ・シストリック・アレーの前記和
及びキャリーから選択した一つを加算する加算手段と、 前記乗数を記憶する第１のレジスタ手段と、前記被乗数
を記憶する第２のレジスタ手段と、前記フィードバック
手段の前記第１及び第２のレジスタ手段を制御して前記
シストリック・アレー乗算器に複数の乗数及び複数の被
乗数を入力して処理することにより、前記複素槽の実数
及び虚数部のそれぞれにおける前記複素槽のうちの一つ
に対する和及びキャリー・セーブ・シストリック・アレ
ーにより先ず処理し、かつｎ段のうちの一つにより離し
て配置して、ｎクロック・サイクルで前記キャリー・セ
ーブ・シストリック・アレーを介する第１バスを得る制
御手段とを備え、前記制御手段はｎ＋ｘクロック・サイ
クル後に前記複素槽のうちのそれぞれに対してフィード
バックされた前記和及びキャリーに加え、前記複素槽の
実数及び虚数部における他の積に対する乗数及び被乗数
を前記キャリー・セーブ・シストリック・アレーに入力
し、かつｎ段のうちの一つにより離れて配置され、前記
キャリー・セーブ・シストリック・アレーを介する第２
のバスを形成して前記複素槽の実数及び虚数部の和及び
キャリーを発生すると共に、 前記加算手段は各前記複素槽の第２バスの終りで前記和
及びキャリーを加算するように制御され、前記複素槽の
実数及び虚数部を出力し、前記制御手段はある複素槽の
実数及び虚数部の和及びキャリーを前記キャリー・セー
ブ・シストリック・アレーの一つ置きのクロック・サイ
クルで出力し、前記加算手段を前記キャリー・セーブ・
シストリック・アレーを介するデータの連続的な流れに
より前記キャリー・セーブ・シストリック・アレーのク
ロック速度の１／２で動作させるように、第１の複素槽
に対する乗数及び被乗数の第１バスを前の複素槽に対す
る乗数及び被乗数の第２バスによりインターレースする
ことを特徴とする複素乗算器。

（１）　　第６項記載の複素乗算器において、前記キャ
リー・セーブ・シストリック・アレーは修飾したブース
演算子に従って動作すると共に、被乗数の長さは２ｎに
等しいことを特徴とする複素乗算器。

（８）　　第７項記載の複素乗算器において、前記キャ
リー・セーブ・シストリック・アレーは 各行を被乗数のうちの１ビツトに対応させ、各列を部分
積に対応させて複数の行列を形成すると共に、その入力
に和レジスタ、キャリー・レジスタ及びデータ・レジス
タに関連させ、処理した和及びキャリーと関連する被乗
数ビットとをそれぞれ記憶する加算器のアレーと、 前記加算器のそれぞれと関連され、ブース演算子の制御
信号に従って被乗数についてのブース演算の実行を判断
するブース演算手段と、各列に関連した被乗数ビットを
調べ、関連する部分積を形成するために必要なブース演
算子を判断して前記ブース演算子の制御信号を発生し、
前記ブース演算手段に入力するデコード手段と、部分積
を発生して中間的な部分和と加算するときは適当な複数
のビットを出力するように、前記列のそれぞれと関連し
た乗数の複数のビットを遅延させる遅延手段とを備える
と共に、 前記加算器は和、キャリー及び修飾した被乗数ビットを
入力し、前記和及びキャリーを修飾したブース演算子に
従ってシフトさせて出力し、次の列に入力させることを
特徴とする複素乗算器。

（９）　　第７項記載の複素乗算器において、前記和手
段は高速加算器を有することを特徴とする複素乗算器。

（１０）第７項記載の複素乗算器において、前記遅延手
段は前記フィードバック手段からフィードバックされた
和及びキャリーを２クロツク・サイクルだけ遅延させる
ことを特徴とする特許乗算器。

（１１）第７項記載の複素乗算器において、前記複素部
と複素加算及び引算をするのための入力ベクトルを記憶
する第３のレジスタ手段と、前記複素部及び引算の結果
を記憶するメモリ手段とを更に備え、 前記和手段は加算のために配列された第１の高速加算器
と、引算のために配列されに第２の高速加算器とを備え
、かつ前記第１及び第２の高速船ｉ３は前記キャリー・
セーブ・シストリック・アレーを介する前記第２バスで
前記複素部の実数及び虚数部のみを受け取り、 前記制御手段は前記第３のレジスタ手段を制御し、前記
複素部の実数部に対す°る和及びキャリーと加算及び引
算をするための前記入力ベクトルの実数部と、前記複素
部の虚数部に対する和及びキャリーと加算及び引算する
ための前記入力ベクトルの虚数部とを出力することを特
徴とする複索乗算器。

（１２）複素乗算を必要とする高速フーリエ変換バタフ
ライを処理して前記複素部を形成した後に前記複素加算
及び引算をする複素乗算器において、複素乗算の乗数と
して複素フーリエ係数を記憶する第１のメモリ手段と、 複素乗算の被乗数として入力ベクトルを記憶する第２の
メモリ手段と、 複素部と複素加算及び引算をするための入力ベクトルを
記憶するメモリ手段と、 前記第１の及び第２のメモリ手段からの前記入力ベクト
ル及び乗数の複素部のうちの一つをそれぞれ受け取り、
予め定めた乗算アルゴリズムに従って部分積を逐次発生
し、かつ予め定めた数のパイプライン・クロック・サイ
クルにおいて通過させるようにしたそれぞれのバスにお
いて形成される積に対する和及びキャリーと加算するｎ
段のパイプライン加算手段と、 前記パイプライン加算手段により、前記和及びキャリー
出力を前記パイプライン加算手段の第１段における第１
の部分積に選択的に加算するフィードバック手段と、 前記パイプライン加算手段からの前記和及びキャリー出
力と、前記第３のメモリ手段からの入力ベクトルの実数
及び虚数部とを選択的に受け取り、その結果のバタフラ
イ成分を出力する高速加算手段と、 前記パイプライン加算手段の前記第１及び第２のメモリ
手段を制御して乗数及び被乗数を入力し、前記パイプラ
イン加算手段を介する前記第１バスで前記第１の積と、
前記第１の積から１段だけ遅延した第４の積とを発生す
ると共に、１バイブライン・クロック信号により遅延す
るように制御され、かつ前記第２の積から引算するため
の前記第１の積と、前記パイプライン加算手段における
前記第３の積と加算するための前゛２第４の積とをフィ
ードバックする前記フィードバック手段によって、第２
バスで前記第２及び第３の積を発生し、前記第２バス後
に前記複素部の実数及び虚数部を発生し、前記パイプラ
イン加算手段に１段だけ分離して出力する制御手段とを
備え、 前記複素乗算は第１、第２、第３及び第４の積の発生を
必要とし、前記第１及び第２の積の引算は前記複素乗算
の実数部を形成し、前記３及び第４の積の加算は前記部
分積の虚数部を形成し、前記制御手段は前のバタフライ
計算の第２バス中にバタフライ計算の第１バスに対する
前記第１及び第２のメモリ手段から出力する複数の乗数
及び被乗数を制御してインターリーブし、前記高速加算
手段は前記制御手段により制御さしれて、一つ置きのク
ロック・サイクルで前記複素部の実数及び虚数部に対す
る和及びキャリーを受け取り、前記第３のメモリ手段の
入力ベクトルと複素加算及び引算を実行することを特徴
とする複素乗算器。

（１３）第１２項記載の複素乗算器において、前記パイ
プライン加算手段はキャリー・セーブ・シストリック・
アレーを有することを特徴とする複素乗算器。

（１４）第１２項記載の複素乗算器において、前記バイ
ブライン加算器手段は修飾したブース演算子を用いるこ
とを特徴とする複素乗算器。

（１５）第１４項記載の複素乗算器において、前記パイ
プライン加算器手段は 複数段の加算器を備え、そのうちの第１段はそれぞれ発
生した部分積と関連され、かつ複数段の加算器はそれぞ
れ 被乗数の各ビットと関連する全加算器と、入力される複
数のパラメータを記憶する複数の入力レジスタと、 修飾したブース・アルゴリズムに従って関連する被乗数
ビットを修飾するブース修飾器と、前記複数段の加算器
にそれぞれ関連され、関連する複数の被乗数ビットを受
け取り、修飾した前記ブース演算子を発生して前記複数
段の加算器における前記ブース修ｆＩｉ器に入力するブ
ース・デコード手段と、 前記ブース・デコード手段のそれぞれと関連されて前記
乗数を受け取る遅延手段とを備えると共に、 前記第２のメモリ手段は関連する前記部分積の発生と同
期して前記ブース・デコード手段に前記乗数を入力する
ように、前記乗数のうちの関連する乗数を遅延し、前記
乗数の全ビットを全ての前記遅延手段に同時に入力し、 前記複数段の加算器は和及びキャリーを伝搬させるよう
にされ、一つの和及びキャリーを出力することを特徴と
する複素乗算器。

（１６）　　第１５項記載の複素乗算器において、前記
フィードバック手段は第１段の前記加算器の和及びキャ
リー入力に前記第及びキャリーをフィードバックすると
共に、１パイプライン・クロック・ナイクルによりフィ
ードバックされた和及びキャリーを遅延させる手段を有
することを特徴とする複素乗算器。

（１１）第１２項記載の複素乗算器゛において、前記高
速加算器は 前記パイプライン加算手段の出力と、加算処理を実行す
る前記第３のメモリ手段に記憶されている入力ベクトル
の実数又は虚数部とを選択的に受け取って加算処理を実
行する第１の高速加算器と、前記パイプライン加算手段
の出力と、前記第３のメモリ手段に記憶されている入力
ベクトルの実数又は虚数部とを選択的に受け取り、前記
第３のメモリ手段に記憶されている前記入力ベクトルの
実数又は虚数部から前記複素積の実数又は虚数部を引算
する引算処理を実行する第２の高速加算器と を備えることを特徴とする複素乗算器。

（１８）第１７項記載の複累乗Ｗ器において、前記第１
及び第２の高速加算器により出力された結果を記憶する
第４のメモリ手段を更に備えることを特徴とする複素乗
算器。

（１９）第１７項記載の複素乗算器において、８入カベ
クトルは前記第３のメモリ手段に記憶され、 六入カベクトルは前記第１のメモリ手段に記憶され、 複素Ｗ係数は前記第２のメモリ手段に記憶されると共に
、前記複素積は ＺＲ＝ＷＲＢｌｌ−ＷｌＢＩ Ｚ、＝ＷＸＢＲ−Ｗ、８゜ による実数部２　及び虚数部Ｚ１からなる共に、ＷＲを
前記バイブライン加算器手段を介する第１バスに用い、
Ｗｌを前記バイブライン加算器手段を介して第２バスに
用いることにより、Ｗｌを２つの乗算について１回アク
セスのみ必要とするものてし、かつＷＲを２つの乗算に
ついて１回だけアクセスを必要とするものとし、ＷＲＢ
Ｒを第１の積、ＷＢ　　を第２の積、ＷｌＢＲを第３の
積、Ｉ ＷＲＢｌを第４の積とし、 前記八人カデータ・ベクトルとの前記複素加算を ＡＲ十／−ＺＲ Ａ、＋／−Ｚ。

とすると共に、前記高速手段により最初にｚＲとＡＲの
引算及び加算処理を実行し、次に八〇とｚｌの引算及び
加算処理を実行するものとすることを特徴とする複素乗
算器。

（２０）　　２つのベクトルを乗算して複素積を得る複
素乗算方法において、 ｎ段のキャリー・セーブ・シストリック・アレ−を備え
て乗数及び被乗数を受け取り、その積を表わす和及びキ
ャリーを出力するステップと、前記キャリー・セーブ・
シストリック・アレーを介する前記複素槽の実数及び虚
数部のそれぞれに対する前記績のうちの一方を逐次処理
してその和及びキャリーを逐次出力し、キャリー・セー
ブ・シストリック・アレーを介する第１バスを形成する
ステップと、 前記第１バスにおいて前記績に対する前記和及びキャリ
ーを前記キャリー・セーブ・シストリック・アレーの和
及びキャリー入力に逐次フィードバックするステップと
、 逐次フィードバックされた前記和及びキャリーとの前記
複素槽の実数及び虚数部のそれぞれの積のうちの他方を
逐次処理して、前記キャリー・セーブ・シストリック・
アレーを介する第２バスにおいて前記複素槽に対する和
及びキャリーを出力するステップと、 前記第２バスにおいて前記複素槽の和及びキャリーを加
算して前記複素槽を出力する加算ステップと を備えていることを特徴とする複素乗算方法。

（２１）第２０項記載の複素乗算方法において、キャリ
ー・セーブ・シストリック・アレーの第１バスで処理し
た２つの積のうちの第２のものを１段だけ遅延するステ
ップと、 前記キャリー・セーブ・シストリック・アレーの２クロ
ツク・サイクルにより前記キャリー・セーブ・シストリ
ック・アレーの和及びキャリー入力に前記和及びキャリ
ーをフィードバックすると共に、その１クロツク・サイ
クルをｎ段の前記キャリー・セーブ・シストリック・ア
レーのうちの一つを介する和及びキャリーを処理する時
間としたステップと、 前記複素槽の和及びキャリーを前記キャリー・セーブ・
シストリック・アレーの一つ置きに出力するように、次
の複素槽の計算の第１バスにおける積を現在処理のキャ
リー・セーブ・シストリック・アレーを介する第２バス
によりインターリーブするステップとを更に備え、 °前記加算ステップは前記シストリック・アレーのクロ
ック速度の１／２で動作することを特徴とする複素乗算
方法。

（２２）第２０項記載の複素乗算方法において、更に、
前記入力ベクトルの実数部を前記複素槽の実数部に加算
し、前記入力ベクトルの実数部から前記複素槽の実数部
を引算し、前記入力ベクトルの虚数部を前記複素槽の虚
数部に加算し、前記入力ベクトルの虚数部から前記複素
槽の虚数部を引算して複素和及び複索引算を得ると共に
、前記入力ベクトルの実数部及び前記入力ベクトルの虚
数部についての処理は前記複素槽のそれぞれの部分の和
及びキャリーの和と一致することを特徴とする複素乗算
方法。

【図面の簡単な説明】

第１図は演算装置及び制御部を示すＦＦＴ複累乗痺乗算
ブロック図、 第２図は演算装置及びバッファ・ファイル・レジスタの
ブロック図、 第３図はパイプライン・アレーの概要ブロック図、 第４図はアレー・セルの一２列についてのブロック図、 第５図はパイプライン・アレーの１セルについてのブロ
ック図、 第６図は第５図のパイプライン・アレーのセルのブロッ
ク図、 第７図はバッファ・ファイル・レジスタのメモリ配列を
示す図、 第８図はバッファ・ファイル・レジスタのブロック図、 第９図はバッファ・ファイル・レジスタに新しいデータ
をロードするためのフローチャート、第１０図は１組の
データの変換によりサイクルするフローチャートである
。

Claims (2)

【特許請求の範囲】
1. （１）２つの複素ベクトルを乗算して複素積を得る複素
   乗算器において、 乗数及び被乗数を受け取り、その積を表わす和及びキャ
   リーを出力するｎ段のキャリー・セーブ・シストリック
   ・アレーと、 前記キャリー・セーブ・シストリック・アレーの和及び
   キャリー出力を前記キャリー・セーブ・シストリック・
   アレーのキャリー及び和入力に選択的にフィードバック
   するフィードバック手段と、前記乗数を記憶する第１の
   レジスタ手段と、前記被乗数を記憶する第２のレジスタ
   手段と、前記第１及び第２のレジスタ手段、及び前記フ
   ィードバック手段を制御し、前記シストリック・アレー
   乗算器を介する第１バスで前記複素積の実数部における
   積のうちの一つ及び前記複素積の虚数部における積のう
   ちの一つを処理することにより、２つの前記積を逐次処
   理するようにした制御手段と、 第２バス後に前記キャリー・セーブ・シストリック・ア
   レーの和及びキャリー出力を加算して複素和を形成する
   加算手段とを備え、 前記フィードバック手段は前記第１バスにおいて２つの
   前記積から和及びキャリーを前記キャリー・セーブ・シ
   ストリック・アレーの和及びキャリー入力にフィードバ
   ック可能に機能し、前記複素積の実数部における残りの
   積及び前記複素積の虚数部における残りの積を加算させ
   、前記キャリー・セーブ・シストリック・アレーを介す
   る前記２バスで前記複素積に対する和及びキャリーを形
   成させることを特徴とする複素乗算器。
2. （２）２つのベクトルを乗算して複素積を得る複素乗算
   方法において、 ｎ段のキャリー・セーブ・シストリック・アレーを備え
   て乗数及び被乗数を受け取り、その積を表わす和及びキ
   ャリーを出力するステップと、前記キャリー・セーブ・
   シストリック・アレーを介して前記複素積の実数及び虚
   数部のそれぞれに対する前記積のうちの一つを逐次処理
   してその和及びキャリーを逐次出力し、キャリー・セー
   ブ・シストリック・アレーを介する第１バスを形成する
   ステップと、 前記第１バスの積に対する前記和及びキャリーを前記キ
   ャリー・セーブ・シストリック・アレーの和及びキャリ
   ー入力に逐次フィードバックするステップと、 逐次フィードバックされた前記和及びキャリーと共に前
   記複素積の実数及び虚数部のそれぞれの積の他方を逐次
   処理して、前記キャリー・セーブ・シストリック・アレ
   ーを介する第２バスの複素積に対する和及びキャリーを
   出力するステップと、前記第２バスの前記複素積の和及
   びキャリーを加算するステップと を備えていることを特徴とする複素乗算方法。