JPH0214363A - 高速フーリエ変換方法及びその演算装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 り産業上の利用分野〕 本発明は、−組のディジタルデータのフーリエ変換を実
行する方法および装置に関するものである。特に、連続
的に受信した電気信号からサンプリングした個別信号を
高速フーリエ変換（ＦＦＴ）するプロセッサに関するも
のである。

〔従来の技術〕

このようなＦＦＴ　（高速フーリエ変換）技術には、マ
ルチプルディスクリートフーリエ変換（ＤＦＴｓ）の高
速演算が包含されている。このＤＦＴは、これら個別（
ディスクリート）信号の時間領域と周波数領域との間の
関係について説明するためのツール（手段）として使用
される。この高速フーリエ変換を行なう装置および方法
によって変換すべきデータワードの数量と、ＤＦＴ（Ｎ
２）を演算するために必要な操作の回数との関係から、
これの効率が決定される。

大規模なりＦＴをマルチプル小規模ＤＦＴｓ　（例えば
、２または４の基数Ｒで）代用できるならば、必要な操
作回数を相当程度減少させることができる。

更に、このマルチプル小規模ＤＦＴｓの演算は、各ステ
ップが類似のステップの多段プロセスより成っている。

このことによって、プロセッサは、より少ない特有のコ
ンポーネントを有するＦＦＴを演算することが可能とな
る。これらステージ（段）Ｂの数は、サンプルのサイズ
と基数とに基いてＢ＝ＬｏｇＦＬＮで関連付けられてい
る。

しかし乍ら、演算ステージ数が大きくなると、丸めの誤
差のために演算が複雑化すると共に、演算結果の精度が
低下してしまう欠点がある。従ってサンプルサイズ１１
　Ｎ　Ｉ＋が増大した場合の処理効率を向上させるため
に、ＦＦＴ演算方法は、ＤＦＴ基数基数上び演算段Ｂの
数量との間の妥協によって得られるもので、一般に基数
はデータバスにおけるスイッチングコストと複雑度によ
って４または８に限定されている。

従来、ＦＦＴを演算する数種類の独特な方法が提案され
ており、これら演算をハードウェアで実行した場合には
異なったアーキテイクチェアで実現されている。先ず、
第１の従来例は、Ｃｏｏｌｅｙおよび７ｕｋｅｙ氏らに
よろもので、”Ｍａｔｈ　Ｃｏｍｐｕｔｅｒ’″１９６
５年４月ｖｏｌ　１９．第２９７〜３０１頁の“Ａｎ　
Ａｌｇｏｒｉｔｈｍ　ｆｏｒｔｈｅ　Ｍａｃｈｉｎｅ　
Ｃａ１ｃｕｌａｔｉｏｎ　ｏｆ　Ｃｏｍｐｌｅｘ　Ｆｏ
ｕｒｉｅｒＳｅｒｉｅｓ”に開示されている。このタイ
プのものには″可変幾何学″が包含されており、これは
、データアドレス動作がステージからステージで変化す
ることを意味する。

また、第２のタイプのものは、Ｐｅａｓｅ氏によって紹
介された″一定幾何学”タイプのもので、′″Ｊｏｕｒ
ｎａｌ　ｏｆ　ｔｈｅ　Ａｓ５ｏｃｉａｔｉｏｎ　ｆｏ
ｒ　Ｃｏａ＋ｐｕｔｉｎｇ　Ｍａｃｈｉｎｅｒｙ”１９
６８年４月ｖｏｌ　１５．第２５２−２６４頁の“Ａｄ
ａｐｔａｔｉｏｎ　ｏｆ　ｔｈｅ　Ｆａｓｔ　Ｆｏｕｒ
ｉｅｒ　Ｔｒａｎｓｆｏｒｍ　ｆｏｒ　Ｐａｒａｌｌｅ
ｌ　ｆ”ｒｏｃｅｓｓｉｎｇ”に３己載されている。こ
こでデータのアドレス動作はステージからステ、−ジま
では同一のままである。このハードウェアの簡素化の実
現は、可変幾何学タイプのものに関する″回転要素”Ｒ
ＯＭの順序における変化である。これら両方のタイプの
ものにおいて、ＲＯＭ要素の順序はステージ毎に変化す
ると共に、一般に、これはアドレスカウンターで取扱わ
わる。

最近の開発によれば、パイプラインプロセッサの導入で
ある。このアーキティクチェアによって。

演算負荷を順次のパラレルステージに分割するので、Ｒ
チャンネルの同時の処理が可能となる。可変幾何学アー
キティクチェアにおけるパイプラインプロセッサの周知
の一例は、ＭｃＣｌｅｌｌａｒおよびＰｕｒｄｙ氏らに
よる”Ａｐｐｌｉｃａｔｉｏｎｓ　ｏｆ　Ｄｉｇｉｔａ
ｌ　Ｓｉｇｎａｌ　Ｐｒｏｃｅｓｓｉｎｇ”　１９７８
年Ｐｒｅｎｔｉｃｅ　）ｔａ１１社のＡｌａｎ１／、Ｏ
ｐｐｅｎｈｅｉｍｉ集者、第２６８−２７８頁に記載さ
れている。データの並列入力率を遅延させないために、
各ステージにおける演算素子自身は２段の４ポインｌ−
ＦＦＴ　（ＤＦＴＳの代りに）であり、各ポイントは、
−段当り４個の演算プロセッサより構成されている。

しかし乍ら、基数が８またはそれ以上に増加して更に並
列化すると、コミュテータまたはクロスバ−スイッチの
数が増加することによって、かなり高価なものとなって
しまう問題点がある。

一定幾何学アーキティクチェアを利用したパイプライン
化ＦＦＴプロセッサがＣｏｒｉｎｔｈｉｏｓ氏によって
開発され、ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ
　Ｃｏｍｐｕｔｅｒｓ。

１９７１年６月　ｖｏｌ、ｃ−２０，“Ｔｈｅ　Ｄｅｓ
ｉｇｎ　ｏｆ　ａ　Ｃ１ａｓｓ　。

ｆ　Ｆａｓｔ　Ｆｏｕｒｉｅｒ　Ｔｒａｎｓ　ｆｏｒｍ
　Ｃｏｍｐｕｔｅｒｓ”、第６１７〜６２３頁に開示さ
れている。このアーキティクチェアでも、クロスチャン
ネル通信の目的のためにスイッチングおよびゲート作用
が要求されている。

このようなプロセッサでは同様に、複雑で大規模なメモ
リが要求され、これによって基数が増大するにつれて、
更に、扱いにくくなる（即ち、メモリ長はＮ／Ｒ”の関
数であるので、所望のメモリユニットの数はＲ２となる
からである）、このプロセッサに関する技術が米国特許
（ｃｏｒｉｎｔｈｉｏｓ発明）第３，７５４，１２８号
、１９７３年８月２１日に開示されると共に、ＩＥＥ　
Ｔｒａｎｓａｃｔｉｏｎ　Ｏｎ　Ｃｏｍｐｕｔｅｒｓ、
　１９７５年Ｉ月ｖｏ１．ｃ−２４．第８０−９２頁の
“Ａ　Ｐａｒａｌｌｅｌ　Ｒａｄｉｘ４　Ｆａｓｔ　Ｆ
ｏｕｒｉｅｒ　Ｔｒａｎｓｆｏｒｍ　Ｃｏｍｐｕｔｅｒ
”にも記載されている。

他の開発は、上述した装置よおび方法の特定の特徴に関
するものである。Ｐｅｒｒｙの米国特許第４，１５９．
５２８号（１９７９年６月２６日）には、フーリエ変換
によって導入された位相シフトの補正が記載されている
。この技術によれば、バーレルスイッチおよび遅延素子
を利用して、小規模なりＦＴｓからの出力に対して適当
な位相補正をこれら出力を大規模なフーリエ変換に組込
む前に実行する。また、ＭｃＧｅｅ氏の米国特許第４，
５３４，００９号（１９８５年８月６日）によれば、前
述のＭｃＣｌａｌａｎおよびＰｕｒｄｙ氏のアーキティ
クチェアを実行し、スイッチとシフトレジスタを利用し
て演算ユニットの演算効率を向上させている。

これら上述した単一チャンネルおよびマルチチャンネル
ＦＦＴプロセッサアーキティクチェアのすべてのものは
、スイッチを利用した相互チャンネル通信路のあるタイ
プのものが必要となる。これら通信路は可変幾何学のケ
ースにおいて時間およびステージと共に大幅に変化して
しまうものである。

〔発明の目的〕

従って、本発明の目的は、クロスチャンネル通信路にお
いて、スイッチを用いずデジタルデータのＦＦＴ　（高
速フーリエ変換）を実行する装置を提供することである
。

また、本発明の他の目的は、ステージ間構造が実質的に
二重化されている新規な収縮性幾何学方法を実行するこ
とによって、デジタルデータのＦＦＴを演算する装置を
提供することである。

更に１本発明の他の目的は、基数サイズがスイッチング
構成の複雑度および／またはコストによって制限を受け
ないで、デジタルデータのＦＦＴ演算する装置を提供す
ることである。

本発明の他の目的は、フーリエ変換の位相シフト特性を
データシャフリング（振るわし）の一部分に利用してデ
ジタルデータのＦＦＴ演算する装置を提供することであ
る。

また、更に、本発明の目的は、クロスチャンネル通信路
においてスイッチングデータのステップ無しで、デジタ
ルデータのＦＦＴ演算を実行できる装置を提供すること
である。

〔実施例〕

以下１図面を参照し乍ら本発明を詳述する。

先ず、本発明は、高速フーリエ変換（以下、ＦＦＴと称
す）を実行する装置および方法であり、これは前述のＰ
ｅａｓｅ氏による一定幾何学方法から得られる新規な収
縮性幾何学方法を演算するものである。デジタルデータ
がＮ個の複素数データワードから成るウィンドウで受信
されると共に、Ｒ個の独立した並列チャンネル内に記憶
される。

次に、これらデータはＬｏｇＲＮ個、直列に配列された
ステージ内に順序付けされる。各ステージは、データア
ドレスオペレータ（作用素）（Ｎ×Ｎ個のマトリックス
は、ＲＡＭシャフル（振わし）オペレータとして既知で
ある）と、ＦＦＴまたはＤＦＴ（核として既知である）
である演算素子を有するフーリエ変換オペレータと、各
チャンネルに対するＲＡＭと、クロスチャンネル通信を
行わず変換すべきデータを変形する回転ファクタオペレ
ータならびに新規な位相システムオペレータとを有して
いる。

概念的に考察して、このオペレーションは、この汎用の
ＦＦＴプロセッサ（前述のＰｅａｓｅおよびＣｏｒｉｎ
ｔｈｉｏｓを参照のこと）に使用されている、各ステー
ジ用の標準のグローバル（全方位）シャフルオペレータ
を３つの置換オペレータへ因数分解することによって達
成される。

これら置換オペレータの第２番目を、各チャンネル中の
１個のデータエレメント上に強制的に作用させるいこれ
によって２番目のオペレータを適当な核に与える。例え
ば、基数４の実施例において、これは以下のような４つ
のデータワードを意味する。即ち、４つのチャンネルの
各々からの４つのデータワードを各ステージで４ポイン
トＦＦＴ核に同時に表現することである。

また、第１および第３番目の置換オペレータを位相シフ
トオペレータに変換する。これ、らオペレータによって
、各チャンネルそれぞれにおいて複素数データワードに
位相回転を行わせることによってデータワードのスイッ
チングと等価な作用となる（核に対する表現と一緒に適
当なデータワードを得ること）。このような方法におい
て、各チャンネル内のＲＡＭの比較的直接的な前方アド
レス作用を利用することによって、従来例に開示された
ようなスイッチを利用する代わりに、適当なデータワー
ドを得ることができる。

本例においては、Ｎ＝６４でＲ＝４（即ち、３ステージ
生じる）の条件の下で実施され、特に説明したものは例
外とする。これらの値は１例えば例示目的のみであり、
決して限定するためのものではない。一般にこれらＮと
Ｒとは２の整数のべき数であるが、本発明の方法はあら
ゆる基数ＲおよびサンプルサイズＮに適用できるもので
ある。

従来の一定幾何学ＦＦＴ演算方式は以下のマトリックス
で表わすことができる（マトリックスのオペレーション
の順序は右側から左側へ読む）；Ｆ、、Ｘ　＝　Ｆ４Ｓ
、／、Ｇ　Ｉ　Ｄ、、Ｆ、Ｓ、／、ＧＩ　Ｄ６４Ｆ４Ｓ
、／、６Ｘステージ３　　ｊステージ２１　ステージ１
ここで、 Ｘ：Ｎ＝６４の複素数データワードの入力行データベク
トル。

Ｓ４／、＆：シャフルオペレータで、これにって４デー
タロツドを入力ベクトルから 離間した１６デ一タワード対面させて 選択させると共に、これらデータを 一緒にグループ化してフーリエ変換 オペレータ用の入力とする。

Ｆ４：フーリエ変換オペレータであり、Ｎ×Ｎ個の正方
ブロックマトリックス で、ブロック項に沿って４ポイントＤ ＦＴｓを包含する。

Ｄ６４１　Ｄｔｓ　：後述する回転要素（ｔｗｉｄｄｌ
ｅ　ｆａｃｔｏｒｓ）Ｆ６４：桁反転順序で列を有する
ＤＦＴマトリックス。

上述したＳ４／、、シャフルオペレータによって、行ベ
クトル中のデータの順序を、　Ｏ，Ｌ、２．・・・、Ｎ
−１ノシーケンスをＯ、Ｎ／Ｒ，２Ｎ／Ｒ，−、（Ｒ−
Ｌ）Ｎ／Ｒｊｌ。

（Ｎ／Ｒ）　＋１　、・［（Ｒ−１）Ｎ／Ｒｊ＋１．・
・　（Ｎ／Ｒ）−１、・・・Ｎ−１に変化する。同一の
効果が隣接チャンネルに関連するＲ個のパラレル入力チ
ャンネルＮ／［（データワードをシフトさせることによ
って達成される。

Ｎ＝６４とＲ＝４に対して、０，１，２．・・、６３の
入カシケンスが以下のように変えられる ０、　１．２．・・・・・・・・・、１５１６．１７，
１８．・・・・・・・・・、３１３２．３３，３４．・
・・・・・・・・、４７４８．４９，５０．・・・・・
・・・・、５３オペレータＦ４は更に正確に記述すれば
（Ｉｘ＋、×Ｆ４）となる。ここで×は２つのマトリッ
クスのクロネツカー積（にｒｏｎｅｃｋｅｒ　ｐｒｏｄ
ｕｃｔ）である。オペレータとしてこの７１−リックス
は、４つのデータワドに対する４ポイン１−フーリエ変
換に相等するもので、これらワードはその入力に表現さ
れると共に、完全なパスがＮ個の複素数データワードの
ウィンドウを通って形成されるまで４個のデータワード
の連続グループに対する処理を繰返すようになる。Ｎ＝
６４に対して１６回繰返えすオペレーションが実行され
る。

前述の゛′回転要素′″がＰｅａｓｅ特許に開示されて
おり以下のように規定される。

Ｄ、４　＝Ｄｉａｇ（Ｉｔｓ　＋　ｏｌｌｆ　ｔ　ＤＬ
ｓ　ｚ　Ｄｘｔ’）ここで、 これら回転要素は、前述のｐｅａｓｅによる一定幾何学
ＦＦＴの導出結果から得られた係数である。これら値は
、上述の等式から演算可能であると共に。

与えられたＮおよびＲに対して一定なものである。

ベクトルＸを便宜上、後述の論議から削除するものとす
る。このようにして得られたち、のはＤＦＴマトリック
スのマトリックス因子Ｆ□である。

上述した従来例の考察によれば、同様なシャフルオペレ
ータおよびフーリエ変換オペレータが各ステージ毎に存
在する。回転要素のみ各ステージにおいて独特なもので
ある。更に、シャフルオペレータは全体的なもので、こ
れらによってすべてのチャンネルからのデータをアドレ
スし、６４データワードのウィンドウの時より大きな時
間間隔でアドレス動作する。このような特徴によって、
ハードウェア構造がシングルチャンネル動作に強制され
る傾向にある。

データワードが第２ステージに入ると、これらデータワ
ードが同一データチャンネル内に存在するために、次の
Ｓ４／１Ｇオペレータ用の適当なシーケンスとは最早な
っていない、これらデータを操作して第２ステージに適
当なシーケンスで表われるようにする必要がある。第１
図に関連して、フーリエ変換オペレータ１０からのデー
タワードが図示の数で表わされた順序で４つのチャンネ
ルＡ〜Ｄ中に出力される。しかし乍ら、次のステージへ
の入力データが循環数で表示された４つのデータワード
のグループで必要となる。これらデータワードをそれ自
身の適切なチャンネルに整列させるために、クロスチャ
ンネル通信が要求される。

従来例ではこのことはスイッチを利用することによって
達成されていた。例えば、前述のＭｃＣｌｅｌｌａｎ、
　Ｐｕｒｄｙによるパイプラインアーキティクチェアに
よれば、コミュテータスイッチと遅延量の異なったＦＩ
ＦＯメモリの組合せを利用してクロスチャンネル操作を
実行している。

本発明による収縮性幾何学方法を達成する第１ステツプ
として、ならびにスイッチなしでＲ個のパラレルチャン
ネルを処理するために、従来シャフルオペレータを以下
の３つのオペレータに因数分解する。

ＳＪ工、＝ＳｐｆＳ尺Ｓｐ ここで、 ＳＰｆ　：高速循環シャフル（すべてのデータワード） ＳＰＬ：ランダムアクセスメモリ（ＲＡＭ）シャフル、
各チャンネルから１個のデ ータワードに対して演算するので、 個々のＲＡＭを各チャンネルに利用で きる。

ＳＰ　＝低速循環シャフル（すべての第４番目のデータ
ワード）。

このＳｐラシャルサイクルは、１６個のデータワードの
大きなグループ内の４つのデータワードの組である。Ｎ
＝６４で、１６個の４つのグループとなる。

１６個のデータワードの第１グループは全く変化しない
、この１６個の第２グループ内の４つのデータワードの
各組は以下に示したように１個のデータワードによって
循環される。

１６個の第３グループにおける４データワードの各々は
、２データワードによって循環すると共に。

３データワードによって第４グループ中に循環する。

前述した一定幾何学方法を利用して第２および第３ステ
ージグローバルシヤフルを以下に示すような３つの置換
オペレータで置換する（第１ステージシヤフルは変化し
ないままで残存する）Ｆ６４：Ｆ４ＳｐｆＳ　Ｓｐ１Ｄ
ｉＧＦ４ＳｐｆＳえ５ＰＩＤ６Ｊ＋５ｊｘｓこのｉｔ　
Ｄ　＋＋回転要素は、各々を（Ｓｐ−’Ｓｐ）で掛算す
ると共に、　ＳｐをＩＩ　Ｄ　Ｉ＋因数生成用ｓｐ−”
ｏｌ、’ｓρを介してＤＩＧの代りに通過させると共に
、５Ｐ−１ＤＧ４ＳｐをＤ６４の代りに通過させること
によって（最初の部分が再編成を表示）再編成される。

次に、各５ｐ−１を隣接チャンネルからＳｐと一緒に溶
は込ませ、次にこれらをキャンセルして以トの式を形成
する。

ＦＧ４＝ＦｉＳｐｆＳＦＬＩ　ＤＩ　Ｇ　’　５ＰＦ４
ｓＰｔ’ｓＲ＋　［）Ｇ４　’　５ＰＦ４Ｓ＋７１ＧＳ
ｐｆおよびｓｐはＦ４を通って通過し、このＦ４を変形
しないと共に、位相シフトオペレータとＤｐ　ｏｐ　’
を生成させ、更に、本発明の基本的な収縮性幾何学方法
を形成する。

Ｆｓ４”ＤＰＨＦ４ＳＢＩＤｘｉ’ＤＰＩ４Ｆ＊ＤＰＨ
’Ｓ　ＩＤ５４’Ｆ＋ＤＰＨ５＊／１ｇ一定幾何学的ア
ーキティクチュアの大部分を。

回転要素および位相回転オペレータに現われる差と共に
保持する。また、第１ステージシヤフルオペレータも保
持する。

位相シフトオペレータＤｐとＤｐ＋によってクロスチャ
ンネルスイッチングと等価なものが達成され、これには
複素数データワードの係数を変形させている。これら位
相シフトオペレータによって各チャンネル中の複素数デ
ータワードのＲの位相を、３６０／　Ｒ度の倍数だけシ
フトさせる（例えば、Ｒ＝４に対して、位相シフトは第
１チヤンネルに対してＯであり、第２チヤンネルに対し
てπ／２であり、第３チヤンネルに対してπであり、第
４チヤンネルに対して３π／２である。即ち、１゜Ｊｙ
　　１＋　　Ｊで掛算することに等価である）。

これらのオペレータによってＤＦＴ核の“シフト”特性
が利用され、ここで、入力領域（ドメイン）における循
環環シフトは変換領域における複素指数による掛算に相
等するものである。これらシフトによってデータワード
を他のチャンネルからのデータワードを利用しないで適
当なシーケンスで配置でき、これによってクロスチャン
ネルスイッチングの必要性を除去できる。

第２図において、本発明によれば、フーリエ変換オペレ
ータ１０を導入するデータの位相を、前述したように位
相シフトユニット５内でシフトする。このＦＦＴｌ０を
出力するデータワードが図示した番号の順序で４つのチ
ャンネルＡ−Ｄ中に出力される。第１図に示したデータ
ワードの順序とは対比されて、上述の前段ＦＦＴシフト
によって次ステージへの入力に必要なデータワードが別
個のチャンネル中に現在現われるようになる（次のステ
ージは円で表示されている）。四角で表わされた次のス
テージへの次の入力セットを同様に配列する。これらチ
ャンネルからの４つの入力のこれら選択および次の組が
ＲＡＭアドレスユニット２０を介して実現される。

もう一つの位相シフト処理が、以下の理由によって、デ
ータが各ステージのＦＦＴに存在した後で実行される。

即ち、第２図を更に参照してデータポイント（１３，１
７，３３および４９）の第２の組が並列であるが、これ
らの適当な宛先ＲＡＭから１つシフトするからである。

再び、スイッチングデータ通路の代りに、シフト特性を
利用し、（今回は逆方向で）更に、以下のステージのＦ
４演算ユニット出力を適当な掛算子（１＋　Ｊ＋　　１
＋　　ＪがＲ＝４に対して準備）を項毎に掛算すること
によって、これと同じ効果を達成させる。これらは簡単
な位相シフトであり、これをＲＯＭ保持係数ＯｓＧ′と
ＤＧ４’に吸収することができ、これらは通常、各Ｆ、
の後の基数４変換で実現される。

このような収縮性幾何学方法における簡素化は、位相シ
フトオペレータを回転要素で溶込ませることによって実
現できる。このことによって演算負荷を減少でき、これ
は各チャンネルにおけるデータの単一の複素乗算を確立
すると共に、回転要素および位相シフトオペレータに必
要な２つの複素乗算を置換することによって減少できる
１合併（溶込んだ）オペレーションはＲＯＭユニットに
よって処理される。

このような合併（溶込み）動作は直接溶造みまたはＲＡ
ＭシャフルオペレータＳ、を介して位相シフトオペレー
ションＤＰＨ’を以下のように通過させることによって
実現できる。

１溶込み　溶込み１ ＦＧ４”ＤＰｌ−ＩＦ４Ｓｌｔ　　Ｄｔｓ″ＤＰＭＦ４
ＤＰＨ″Ｓ艮ｌＤ＆４’ＦｎＤＰＨ３Ｊ工。

ステージ１１　ステージ２　１　ステージ３最終結果は
減少した収縮性幾何学方法である。

Ｆｅ２”ＤＰ？１Ｆ４ＳＩＬ　　ＤＰＨ２Ｆ４Ｓえ　Ｄ
ＰＨｔＦ４Ｄ四Ｓｊ、ｓステージ１１ステ！−ジ２１　
ステージ３ここで。

Ｄｐ）１□”Ｄｔｓ’ＤＰＳ および ｏｐＨ□＝ＤＰＨ″ＤＩ、４ （ＤｐＨ″はＤＰＨ’を再編成 させたものである。） 次に、第３図を参照にし乍らＮ＝６４．Ｒ＝４゜３ステ
ージＦＦＴ装置によって本発明の収縮性方法を実施する
動作を説明する。データの流れは左から右へ移るものと
する。

シャフルユニット１０はデータワード９０を受信すると
共に、これらを４つのチャンネルＡ−Ｄへ配列する。こ
のシャフルユニット１００によって前述したＳ４／０．
シャフルを実行するものと仮定すると、データがＳ、／
工、シャフルによって与えられた順序ですでに与えられ
ているこのシャフルユニットを取除くことができる６位
相回転器１１０は掛算ユニットであり、これによってデ
ータワードの位相をシフトさせるので、この結果、第２
図に示した順序が次のフーリエ変換オペレーションの後
に得られる。基数４に対しては、この位相回転器１１０
は各チャンネルをｊのべき数で簡単に掛算し。

例えば、チャンネルＡは１（ｊ’）で、チャンネルＢは
ｊ　（ｊｌ）で、Ｃは−１（ｊ”）で、更にＤは−ｊ（
ｊ３）で掛算する。もっと高い基数オペレーションに対
しては、この掛算は更に複雑なものである（例えば、基
数８に対しては、８のチャンネルの各々の位相を４５°
だけシフトさせる必要がある）。フーリエ変換オペレー
タ１２０によってＤＦＴオペレーションを実行し、４デ
ータワードの組を各チャンネルから得てこれにフーリエ
変換する。回転エレメント１３０には、予じめ決められ
た係数を記憶するメモリと、これらデータワードをこれ
ら係数で掛算する掛算器とが設けられている。ＲＡＭユ
ニット１４０によってＲＡＭシャフル（ＳＲ）を実行す
ると共に、ステージ間でデータインターフェイスとして
作用する。

６４より大きなＮに対しては、ステージ２を繰返すが、
第２ステージおよび次のステージに、各前段ＦＦＴ位相
回転器１１０の前の後段ＦＦＴが設けられているのが例
外である。前述したように、後段ＦＦＴ位相回転器によ
って、　ＲＡＭから適当に受信されるべき第２のデータ
組が得られる。Ｎ＝６４に対しては、この関数は再編成
された回転要素Ｄ１％ｌＤ□に吸収されていた。

前述した減少型収縮性幾何学法が第４図に具現化されて
おり、ここで、識別番号は第３図のものに対応する。位
相回転器１５０が、位相シフト乗算子と合併された回転
係数を包含した合併オペレータである。

第４図のデバイスのステージ毎の対称性が、第３ステー
ジの位相回転器１１０を１個の回転オペレータで合併さ
せると共に、第１ステージの位相回転器１１０のオペレ
ータをＲＡＭエレメントでアドレス付けすることによっ
て更に強調される。これらの変化によって各ステージが
ＲＡＭエレメントと、フーリエ変換オペレータと、プロ
グラマブルＲＯＭ　（ＰＩｔＯＭ）の調整された回転係
数を有するデバイスを創作する。

第５図には、ＦＦＴプロセッサユニットが図示されてお
り、このユニットをマルチステージ（多段）ＦＦＴ装置
におけるステージとして使用すると共に、これら３つの
要素を包含している。Ｎ＝６４およびＲ＝４に対しては
３つのＦＦＴプロセッサユニットが必要となる。

第５図に示したＦＦＴプロセッサユニット２００を７つ
のエレメントで構成でき、これらはＩ１０ＲＡＭエレメ
ント２２０．　ＲＡＭアドレスエレメント２４０１回転
メモリエレメント２６０２回転アドレスエレメント２８
０．　ＦＦＴ演算エレメント３００２組込テスト（ＢＩ
ＴＥ）エレメント３２０とコントロールニレメン１へで
ある。

Ｉ１０ＲＡＭエレメント２２０は順次のステージ間のデ
ータインターフェイスである。このエレメント２２０は
曲設（即ち、ステージ１に対しては、図示しないシャフ
ルオペレータのようなエレメントを介してシステム入力
から）人力データ２２５を受信する。これらデータは２
つの１６ビツトコンポーネントを有しており、位相を有
する複素データワードを構成している。Ｉｌｏ）ＩＡＭ
エレメント２２０を４つの同一ボートに分離することが
でき、これらボートは演算エレメント３００の４つのボ
ートと直接インターフェイスしている。各ボートは、再
帰性データバッファおよびダブルバッファＲＡＭモジュ
ールより構成することができる。

これら４つのＲＡＭモジュールの各々を、マルチプレッ
クス処理された入力および出力を有するマルチプルＲＡ
Ｍ　（例えば、Ｎ　：４０９６に対して２個の２ｋＸ　
１Ｓ　ＲＡＭ）より構成することができる。この結果新
たな入力データを、データがＲＡＭから読出された時と
同時にＲＡＭ内に書込むことができる。

このような方法において、ＦＦＴプロセッサユニットを
１００％利用できる。　ＲＡＭエレメント２２０によっ
てバス２２７内の書込みアドレスコマンドを受信すると
共に、ＲＡＭアドレスエレメント２４０からバス２２９
内の読取リアドレスコマンドを受信する。バス２３５中
の出力データをＦＦＴ？′ｉＬ算エレメント３００に供
給する。

このＲＡＭアドレスエレメント２４０をマルチプルＰＲ
ＯＭ　（例えば、Ｎ＝４０９６に対して４つの２　Ｘ　
ｓ　ＰＲＯＭ）より構成できるＲＡＭアドレスを読取り
書込みアドレスならびに複素数／実数アドレスに分割す
る。

複素数アドレス部分によって読取りまたは書込みアドレ
スを利用し、複素数データ値を記憶する。

実数アドレスによってＬＳＢを複素数アドレスに加算し
、このアドレスによって各複素数データ値の同相成分お
よび直交成分にアクセス制御する。例えば、ＯのＬＳＢ
値を同相、即ち、実数成分に対応させ、ｌのＬＳＢ値を
直交、即ち、虚数成分、に対応させる。これによって、
ＦＦＴデータを、複素数アドレスを利用して、ＬＳＢ値
によって実数または虚数成分を決定する固有の認識に基
いて複素データとして参照できる。

すべてのＲＡＭ書込みアドレスを、ＦＦＴステージ毎の
特定の複素数フーリエ変換演算に相当する計数値によっ
て順次ドライブする。順次の複素数ポイントを、最初、
実数コンポーネントならびに次に虚数コンポーネントで
順次書込む、従って、実数カウンタによってＩ１０ＲＡ
Ｍエレメント２２０をアドレスできる。このようなシー
ケンシャル計数が４つのボートの各々に対して同時に実
行されると共に、その後、単一バス２２７に残存するよ
うになる。

読取リアドレス作動は、ＦＦＴ演算エレメント３００へ
の入力データのＲＡＭシャフル（Ｓ、）のために、書込
みアドレス動作よりかなり多く包含されている。

データがその適当なチャンネルのＲＡＭに順番に書込ま
九るので、読取り（読出し）アドレスによって、各フー
リエ変換オペレーションに対する必要なデータワードを
選択する必要がある。この読出しアドレス動作は、ＦＲ
ＯＭメモリ内のインストラクション（命令）によって実
行され、このメモリは、最新の複素数フーリエ変換演算
数をトラッキングするシーケンシャルカウンタによって
アドレス付けられる。工／○ＲＡＭエレメント２２０中
の４個のＲＡＭの各々には、バス２２９内において並列
に独立したアドレス動作が必要となる。

回転メモリエレメント２６０をマルチプルＰＲＯＭで構
成することができ（例えば、Ｎ＝４０９６に対して、８
個の２　ｋＸ　８ＦＲＯＭ）　、これらＰＲＯＭには、
ＦＦＴ演算エレメント３００に供給される回転要素係数
が含まれている。これにデータを４個のパラレル１６ビ
ツトボートを介してバス２６５に送給する。

後述するように、実際に記憶された回転要素が、予じめ
決められたＮおよびＲに対する変換の１ステージに必要
となる。この記憶されたデータから、回転アドレスエレ
メント２８０内の回転アドレススキーム（予定）によっ
て正しい係数が、特定のステージおよび変換サイズ当り
のフーリエ変換オペレーションに対して選択されるよう
になる。

回転アドレスエレメント２８０をマルチプルＰＲＯＭ（
例えば、Ｎ＝４０９６に対して３個の２　ｋ　Ｘ　８　
ＦＲＯＭ）より構成でき、これらＦＲＯＭを、ＲＡＭア
ドレスエレメント２４０内のような複素数フーリエ変換
オペレーション番号をトラッキングするカウンタによっ
て制御する。このエレメントによって、アドレスが適当
な値だけインクレメントされて異なった通過量や変換サ
イズを補償するようなマスキングスキームを利用する。

インストラクションがライン２７５を介して回転メモリ
エレメント２６０に送給される。

コントロールエレメント３４０によって、他のエレメン
トに対してボード上のコントロール信号を発生させると
共に、クロック・イン信号３５５を供給してすべてのＩ
１０データワードと係数とを同期化する。

ＢＩＴＥエレメント３２０によって出力データ３０５を
ライン３１５を利用してテストデータ用のソースとして
引き上げる６例えば、出力データ３０５の１つのポート
を引き上げることによって、このＢＩＴＥエレメント３
２０によって１６−１にするデータマルチプレックサお
よび外部コントロール３２５を利用でき、これによって
、ライン３３５を介して外部のモニタ用の１６ビツトの
内の１つを選択する。

また、ＦＦＴ演算エレメント（ＦＦＴＣＥ）　３００に
ついて第６図を参照し乍ら説明する。先ず、同図におい
て、識別番号は第５図のものと同一のものを使用した。

このＦＦＴＣＥ３００をシングルチップの独特なデザイ
ンとすることができ、この機能を、例えば。

ＩＢＭ　ＳＰＥチップのような現存のチップをカスケー
ド接続することによって実現できる。このＦＦＴＣＨの
機能は、ＦＦＴマトリックスオペレーションを演算する
と共に、アレイスケーリングおよびラウンディングが得
られる。バス２３５を介して入力データを受信し、更に
、バス２６５から回転係数を受信し、ライン３４５を介
してコントロールファンクションならびにライン３５５
のクロック・イン信号を受信する。出力データをバス３
０５を介して供給する（第５図の各ポートまたはバスに
隣接した数はポートまたはバス当りのライン数を表わす
）。

このＦＦＴＣＥ３００によって基数４の４ポートＤＦＴ
が以下の式を解くことによって演算されるＴ（に）＝Ｃ
Ｈ（ｋ）＋Ｄ（ｋ＋１）＋Ｄ（ｋ＋２）＋Ｄ（ｋ＋３）
］　ｘ　ｃ（ｋ）Ｔ　（ｋ＋　１　）＝［Ｄ　（ｋ）−
ｊＤ　（ｋ＋１）−Ｄ　（ｋ＋２）＋ｊＤ　（ｋ＋３）
　］　Ｘ　Ｃ（ｋ＋　１）Ｔ（ｋ＋２）＝［Ｄ（ｋ）−
Ｄ（ｋ＋１）十〇（ｋ＋２）−〇（ｋ＋３）］　ｘｃ（
ｋ＋２）Ｔ　（ｋ＋３）＝ＣＨ（ｋ）＋ｊＤ　（ｋ＋　
１）−Ｄ　（ｋ＋　２）−ｊＤ　（ｋ＋３）　］　Ｘ　
Ｃ（ｋ＋３）ｋ＝ｏ、４．８・・・、Ｎ−４に対してこ
こで、 Ｔ　（ｉ）　：出力ベクトル Ｄ（ｉ）：データ入力ベクトル Ｃ（ｉ）：回転係数または位相回転ベクトルｊニー１の
２乗根 但し、これは基数４であるので、位相回転オペレーショ
ンが、Ｃ（ｉ）ベクトルを加えることによってこれら等
式中に包含されている。高次の基数オペレーションでは
、位相回転オペレーションは、個別の複素数乗算オペレ
ーション（図示せず）が必要となる。この代りに、位相
回転器を回転メモリエレメント係数と合併させて、複素
数乗算ステップを省略することもできる。

データをバス２３５を介してデータワードとして受信す
ることができる。これらデータを同相成分と直交成分と
から成る複素数とすることもできる。

各成分は１６ビツトで固定ポイントで、２の補数である
。４つのデータワードを同時に受信し、ベクトルＤ　（
ｉ）を上述した等式中に形成する。同時に、４つの回転
係数をバス２６５から４つのデータワードと同期して受
信し、ベクトルＣ（ｉ）を形成する。

本例においてＮ＝６４によって、ＦＦＴＣＥは１６個の
ベクトルＤ　（ｉ）とＣ（ｉ）とをステージを介して各
通路で受信すると共に、１６個のベクトルＴ　（ｉ）を
出力する。これらベクトルの各々は４つのデータワード
より構成される。出力をバス３０５を介して次のステー
ジに送給する。

また、第６図において、ＦＦＴＣＥ３００はコントロー
ルワード１′スケールフアクタ出力”　３４７を出力し
、これは、後続の処理中にオーバーフローすることを回
避するために必要な右側シフトの数に等しいものである
。この出力を次のステージで″スケールファクタ入力”
　３４９として受信する。

このＦＦＴＣＥのアーキティクチュアの実施例として第
７図に示すものがある。ここでは、第５図の参照番号と
同じものを使用する。ベクトルＤ　（ｉ）のデータワー
ドがバス２３５中に入力されると共に、適当にスケール
処理される。演算論理ユニット（ＡＬＵ）３１２．遅延
３１４．　　′ｊ”マルチプライヤ（乗算器）３１６お
よびバス２６５からのＣ（ｉ）ベクトルを利用した複素
数マルチプライヤ３１８によって、バス３０５より出力
されるベクトルＴ　（ｉ）が得られる。

Ｎ＝６４．Ｒ＝４の収縮性幾何学ＦＦＴプロセッサユニ
ットの回転メモリエレメント（第４図の２６０）中に記
憶されたベクトルＣ（ｉ）に対する値が第８図に示され
ている。フーリエ変換演算の計数が列Ａに図示されてい
る。各ステージのベクトルＣ（ｉ）の４つの値が列Ｂ−
Ｄに示されている。各値は項ｅｘｐ（ｊ２　ｔｃ　ｍ／
Ｎ）の”　ｍ　”を表わし、Ｎ＝６４である。

ステージ２の回転係数値がステージ１の回転係数値のサ
ブセットであるように見られる。より大きなＮに対して
この関係は後段に発展する。五位相回転器のべき数が回
転要素と合併した場合には、繰返性が破壊される。図示
のステージ３は、ｊマルチプライヤのべき数をステージ
３のユニット回転要素と合併した結果である。ｊマルチ
プライヤのべき数がステージ３の回転要素と合併しない
場合には、ステージ３のすべての回転要素値は零となる
。

ＲＯＭの要求度は、第８図に示したような回転係数を組
合せることによって更に減少できる。回転係数エレメン
ト（第４図の２８０）中のハードワイヤ処理したアドレ
ススキームによって、適当なＣ（ｉ）値を、フーリエ変
換演算数およびステージ数を利用して選択する。最後の
ステージにおいて。

円が付けられた値のみアクセスされる。更に高いＮにつ
いては、パターンは類似しており、但し、円が付けられ
たグループの変動が繰返えされる。

例えば、Ｎ＝２５６で、各列には（０，６４，１２８，
１９２）の４つの連続的な繰返しが包含される。

上述した方法のソフトウェアシュミレーションによって
基数が２．４．８またはそれより高次の基数のパイプラ
インＦＦＴで利用できることが表わされる。基数が増大
するにつれて、スループットレートも上昇する。これは
、ＦＦＴ演算プロセッサ（各ステージにおける）を、高
いスルーグツ１−レトが起るようにそれ自身の内部アー
キテイクチュア内で十分な量のパラレリズム（数似性）
で構成できるならば相当程度のパラレリズムのために上
昇する。所望の処理スピードに依存して、高次基数アー
キティクチェアによってＦＦＴ演算エレメント（例えば
、８ポイントＦＦＴ等）内にパイプラインプロセッサを
必要とする。

上述した方法は、周波数の１／１０を取る（ＤＩＦ）タ
イプのものであったが、時間の１／１０を取る（ＤＩＴ
）タイプのバージョンをＤＩＦ方法から発生させること
ができ、この場合、ＯＦＴマトリックスが対称形の時に
、ＤＦＴマトリックスのマトリックス配置Ｆ　Ｇ　４を
実行することによって発生させる。このＦ　６４は、シ
ャフルマトリックスＳ４／１ｇで掛算することによって
対称形にでき、このマトリックスによって、Ｆ＠４の行
を自然の順序（周波数を増大して）に逆変換する。この
ＤＩＴバージョンは以下に与えられる（ＤＩＦバージョ
ンをＳＪ、、によって掛算すると共にその結果を変換し
た後に）、Ｆ、　、　Ｔ＝Ｓ工ｓ／＊Ｄｐ　Ｆ４ＤＰ　
ｔｓ　ＴＦ４ＤρｚＳ　ＴＦ４Ｕｐ　Ｓｔｓ八ここで、 Ｓ□６へ＝ＳＪ工、Ｔ ＳζはＳビの配置行列であり、 Ｆｓ４ＴはＤＩＴ　ＤＦＴマトリックスである。

Ｆ４が対角線に沿って４ポイント核叶Ｔを包含するブロ
ック正方行列であると共に、各ＤＦＴが自然の順序であ
るものと仮定し、従って対称の４Ｘ４マトリツクスであ
るので、このマトリックスＦ。

が対称形であると共に、配置行列によって変化しないも
のである。位相回転および回転要素を包含するＩＩ　ｐ
　Ｉ＋マトリックスのすべてがすでに正方形であり、こ
れによって対称形となる。シャフルマトリックスＳ４／
ＩＧおよびＳＦＬが配置行列オペレーションによって変
化する。但し、回転要素マトリックスは、現在Ｆ４マト
リックスに先行するもので、これは、時間の１／１０を
取るプロセラ、すの特性および方法である。

また、変形例によれば、位相シフトオペレータの機能を
循環性コミュテータスイッチで実施できる。クロスチャ
ンネル通信を導入するｍ、ＦＦｒ演算エレメントの外側
で行なう。このような実施例は低速の低次の基数オペレ
ーションにとって好都合である。

前述した技術を再帰性ＦＦＴプロセッサにも応用できる
ものである。同じハードウェアが繰返して利用できる再
帰性プロセッサの応用例は、低処理速度が受入れられる
ならば、適切なものである。

本発明の種々の実施例を詳述したが、当業者によれば変
形や変更を加え得ることは容易である。

従って、上述した実施例は単に一例にすぎず、本発明の
技術的思想を限定するものではなく、添付したすべての
クレームおよびそれらの均等物によって規定されるもの
である。

【図面の簡単な説明】

第１図は、従来のＦＦＴプロセッサでのデータワードに
ついての説明図； 第２図は、本発明のＦＦＴプロセッサでのデータワード
の位相シフトされた順序についての説明図第３図は、第
２図の位相シフトスキームを包含する３ステージＦＦＴ
プロセツサの構成図；第４図は、第３図のデバイスの減
少型収縮性幾何学バージョンの構成図； 第５図は、第４図のプロセッサの単一ステージの構成図
； 第６図は、第５図のＦＦＴ演算エレメントのブロック図
； 第７図は、第６図のエレメントの演算アーキテイクチュ
ア； 第８図は、第７図のエレメントで使用される回転係数を
表わす図、および 第９図は、第８図で示した回転係数の小さなＲＯ阿バー
ジョンである。 ５・・・位相シフトユニット １０・・・フーリエ変換オペレータ ２０・・アドレスユニット １００・・・シャフルユニット １１０・・・位相回転器 ２００・・・ＦＦＴ　フロセッサユニット２８０・・・
回転アドレスエレメント ３４７・・・スケールファクタ出力 ３４９・・・スケールファクタ入力

Claims (1)

1. 【特許請求の範囲】 １　複素数データワードを高速フーリエ変換演算するに
   当り、これらデータワードを受信すると共に、これらデ
   ータワードをＲ個のチャンネル中に配列し、これらＲ個
   チャンネルに対応したＲ個の出力を有する入力メモリ手
   段と； 前記データワードを変換する、複数個の直列接続された
   ステードと、ここでこれらステージの第１番目のものに
   よってＲ個のチャンネル内の前記データワードを前記入
   力メモリ手段より受信するようにし； これら直列接続されたステージの最後に接続され、前記
   データワードを出力する出力メモリ手段とを具え、 前記ステージの各々には、これらステージ間を接続する
   ための前記Ｒ個チャンネルに対応したＲ個の入力手段お
   よび出力手段と、 前記データワードのＲをベクトル内に時間的に整列させ
   るＲ個のシャフル手段と、ここではこれらベクトルの各
   々には前記チャンネルの各々からの前記データワードの
   １つが設けられ、 これらベクトルの各々にフーリエ変換するためのフーリ
   エ変換オペレータ（作用素）と；これらデータワードが
   前記フーリエ変換オペレータに入力される前に、これら
   ワードの位相をシフトするＲ個の第１マルチプライヤ手
   段と、これらデータワードをこのフーリエ変換オペレー
   タへ出力した後で、これらワードの位相をシフトするＲ
   個の第２マルチプライヤ手段と、ここで前記第２マルチ
   プライヤ手段は前記直列配置ステージの第１ステージで
   ないものとし、 これらデータワードの各々に予じめ決められた係数を与
   えるＲ個の第３マルチプライヤ手段とを設け、前記チャ
   ンネルの１つの前記入力メモリおよび出力メモリデータ
   ワードを、このチャンネルの他方に、前記フーリエ変換
   オペレータ以内で行なうことを除いて伝送しないように
   したことを特徴とする高速フーリエ変換演算装置。 ２　前記Ｒ個の第３マルチプライヤ手段の１つを前記Ｒ
   個の第１マルチプライヤ手段の１つに合併させたことを
   特徴とする請求項１項記載の演算装置。 ３　前記第３マルチプライヤ手段の１つを、前記第２マ
   ルチプライヤ手段の１つに合併させたことを特徴とする
   請求項１項記載の演算装置。 ４　前記フーリエ変換オペレータに、ブロック正方行列
   を設け、これにブロックの対角線に沿ってＲ個のポイン
   トフーリエ変換が設けられたことを特徴とする請求項１
   項記載の演算装置。 ５　前記第１マルチプライヤ手段に、前記データワード
   の位相を、３６０／Ｒ度の整数倍でシフトするマルチプ
   ライヤ手段を設けたことを特徴とする請求項１項記載の
   演算装置。６　前記第３マルチプライヤ手段の各々には
   ；前記予じめ決められた係数を包含する１個またはそれ
   以上のプログラマブルＲＯＭ手段と、前記フーリエ変換
   オペレータによって実行されたオペレーション回数を計
   数するトラッキング手段と、 このトラッキング手段を利用して、前記プログラマブル
   ＲＯＭ手段から前記係数を選択するアドレスエレメント
   とを設けたことを特徴とする請求項１記載の演算装置。 ７　それぞれ位相を有する、Ｎ個のデジタルデータワー
   ドの入力ストリームにフーリエ変換するに当り、 これらデータワードをＲ個のチャンネルで受信するため
   の受信手段と； 前記データロードをＬｏｇ＿ＲＮ個の直列接続したステ
   ージ内で処理する処理手段とを具え、これらステージの
   各々に、 前記データワードのＲをベクトル中で時間的に整列させ
   るＮ×Ｎマトリックスを有するシャフル手段と、ここで
   これらベクトルの各々には、Ｎ個のデジタルデータワー
   ドの前記ストリームからＮ／Ｒのインターバルで引かれ
   た前記Ｒ個のチャンネルの各々からの前記データワード
   の１つが設けられ、 これらデータワードをチャンネル間で伝送することなく
   変形する位相シフト手段と前記チャンネルの各々にＲ個
   のデータワードの位相を３６０／Ｒ度の整数倍でシフト
   するようにし、 更に、前記ベクトルの各々にフーリエ変換し、基数Ｒの
   複数個のマトリックスオペレータを有するフーリエ変換
   手段とを設けたことを特徴とするフーリエ変換装置。 ８　位相を有するディジタルデータワードに高速フーリ
   エ変換を行なうに当り、 複数のチャンネルを有し、これらデータワードのグルー
   プにフーリエ変換する複数個の直列接続されたフーリエ
   変換手段と、 このフーリエ変換手段に先立って前記データワードを変
   形する複数個の位相シフト手段とを具え、これら位相シ
   フト手段の各々によって、これらデータワードを、前記
   フーリエ変換手段の次段のための適当な順序で配置し、
   これはこれらデータワードを前記チャンネル間で伝送し
   ないようにしたことを特徴とするプロセッサ。 ９　複数個のデータチャンネルと、ディジタルデータを
   再配列する複数個のシャフルオペレータとを具え、 これらシャフルオペレータの各々によって前記データチ
   ャンネルの１つのチャンネルのみからのデータを再配列
   するようにしたことを特徴とするディジタルデータの高
   速フーリエ変換演算装置。 １０　各々が位相を有するディジタルデータワードを高
   速フーリエ変換するに当り、 複数個のデータチャンネルと； これらデータワードのグループのフーリエ変換を演算す
   る複数個の直列接続されたフーリエ変換手段と、これら
   グループには前記チャンネルの各々からのデータワード
   の１つが設けられ、前記フーリエ手段に先立って前記チ
   ャンネル内の１つのデータワードの位相を変形する複数
   個の位相シフト手段と；更に、 前記フーリエ変換手段に先立って、前記チャンネルの１
   つの内のデータワードを配列する複数個のシャフル手段
   とを具え、前記チャンネルの１つの内の前記データワー
   ドを、もう１つのチャンネルに伝送しないようにしたこ
   とを特徴とする高速フーリエ変換装置。 １１　前記フーリエ変換手段に、ブロック正方行列を設
   け、これにはブロックの対角線に沿ってフーリエ変換が
   設けられたことを特徴とする請求項第１０項記載の変換
   装置。 １２　Ｒ個の前記データチャンネルを設け、前記位相シ
   フト手段の各々に、前記データワードの位相を３６０／
   Ｒ度の整数倍だけシフトするマルチプライヤ手段を設け
   たことを特徴とする請求項１１項記載の変換装置。 １３　複数個のデータチャンネルと、複数のディジタル
   データのグループのフーリエ変換を演算する手段とを具
   え、これらグループの各々に前記チャンネルの各々から
   の前記データワードの１を設け、これらデータワードを
   前記チャンネル間で伝送しないようにしたことを特徴と
   する高速フーリエ変換装置。 １４　複数個のステージを有するプロセッサと、ディジ
   タルデータ用の複数個のチャンネルとを具え、これらチ
   ャンネルの各々における前記ディジタルデータ用の通路
   を固定してスイッチを設けないようにしたことを特徴と
   するディジタルデータのフーリエ変換装置。１５　複数
   個のチャンネルと、複素数データワードのフーリエ変換
   を演算する複数個接続したステージとを有し、更に、こ
   れらデータワードを変形する位相シフト手段とを設け、
   前記ステージの１つにおける前記データワードを配列す
   ることによって、これらワードが次のステージ用の予じ
   め決められた順序となり、これらチャンネル間にデータ
   を伝送しないようにしたことを特徴とするデータワード
   変形装置。 １６　前記チャンネルを４個設け、前記位相シフト手段
   に、前記チャンネルの各々内のデータワードをｊのべき
   数で掛算するマルチプライヤ手段を設け、これら各チャ
   ンネル用のｊのべき数が連続し、ｊの整数べき数が０か
   ら開始するようにしたことを特徴とする請求項１５項記
   載の変形装置。 １７　前記チャンネルをＲ個設け、更に前記シフト手段
   に、このＲ個のチャンネルの各々に存在する前記データ
   ワードの位相を３６０／Ｒ度の倍数だけシフトするマル
   チプライヤ手段を設け、これらチャンネルの各々に対し
   て３６０／Ｒの倍数が零で開始する連続する整数である
   ことを特徴とする請求項１５項記載の装置。 １８　複素数データワードを高速フーリエ変換演算し、
   これらデータワードを変換する複数個の直列接続された
   ステージを有し、これらステージの各々には、 これらステージを接続し、Ｒ個のチャンネルに対応する
   Ｒ個の入力および出力手段と； これらデータワードのＲをベクトル内で時間的に整列さ
   せるＲ個のシャフル手段と、これらベクトルの各々には
   これらチャンネルの各々からのデータワードの１つが設
   けられ、 これらベクトルの１つにフーリエ変換を実行するフーリ
   エ変換オペレータと； 前記データワードがこのフーリエ変換オペレータに入力
   される前に、これらワードの位相をシフトするＲ個の第
   １マルチプライヤ手段と； 予じめ決められた係数をこれらデータワードの各々に与
   えるＲ個の第２マルチプライヤ手段とを具え、 前記入力手段と出力手段との間で、前記チャンネルの１
   つ中のデータワードを他のチャンネルに伝送しないよう
   にしたことを特徴とする高速フーリエ変換演算装置。 １９　前記Ｒ個の第２マルチプライヤ手段の１つを前記
   Ｒ個の第１マルチプライヤ手段の１つに合併させたこと
   を特徴とする請求項１８項記載の装置。 ２０　前記フーリエ変換オペレータに、ブロック正方行
   列を設け、これにはブロックの対角線に沿ってＲポイン
   トのフーリエ変換を有する請求項１８項記載の装置。 ２１　前記第２マルチプライヤ手段の各々には、予じめ
   決められた係数を包含する１個またはそれ以上のプログ
   ラマブルＲＯＭ手段と、 前記フーリエ変換オペレータによって実行されたオペレ
   ーション数を計数するトラッキング手段と、このトラッ
   キング手段を利用して、前記プログラマブルＲＯＭ手段
   から前記係数を選択するアドレスエレメントとを具えた
   ことを特徴とする請求項１８項記載の装置。２２　Ｒ個
   のチャンネルとＬｏｇ＿ＲＮ個の直列接続されたステー
   ジとを有し、Ｎ個のデジタルデータワードの入力ストリ
   ームにフーリエ変換演算するに当り、これらステージの
   各々に、 ベクトル中にこれらデジタルワードのＲを時間的に整列
   させるＮ×Ｎマトリックスと、ここで前記ベクトルの各
   々には、前記データワードストリームからＮ／Ｒのイン
   ターバルで引かれた前記Ｒ個のチャンネルの各々からの
   データワードの１つが設けられ、 前記データワードを前記チャンネル間で伝送しないで前
   記データワードを変形する位相シフト手段と； 前記ベクトルの各々にフーリエ変換するフーリエ変換手
   段とを具えたことを特徴とするフーリエ変換装置。 ２３　前記フーリエ変換手段に、ブロック正方行列を設
   け、これにブロックの対角線に沿ってＲポイントのフー
   リエ変換が設けられたことを特徴とする請求項第２２項
   記載のフーリエ変換装置。 ２４　複数個の直列配置されたフーリエ変換手段を有し
   、デジタルデータワードのフーリエ変換を行なうに当り
   、 前記フーリエ変換手段の前に、前記データワードを変形
   する複数個の位相シフト手段を設け、これら位相シフト
   手段の各々によって、前記データワードを、前記フーリ
   エ変換手段の次段用の適当なシーケンスで置いたことを
   特徴とする高速フーリエ変換プロセッサ。 ２５　複数個のデータチャンネル中のデジタルデータワ
   ードの高速フーリエ変換を演算するに当り、前記デジタ
   ルデータワードのグループのフーリエ変換を演算する、
   複数個の直列配置されたフーリエ変換手段と、これらグ
   ループに前記チャンネルの各々から前記データワードの
   １つを設け、更に、 前記フーリエ変換手段に先立って前記チャンネルの１つ
   内の前記データワードの位相を変形する、複数個の位相
   シフト手段とを具え、前記デジタルデータワードによっ
   てフォローされる通路を固定し、スイッチを設けないよ
   うにしたことを特徴とする高速フーリエ変換装置。 ２６　それぞれが位相を有するＮ個のデジタルデータワ
   ードの入力ストリームを高速フーリエ変換するに当り、 （ａ）これらデータワードをＲ個のチャンネルに区分け
   し、 （ｂ）ステップ（ｃ）〜（ｆ）までをＬｏｇ＿ＲＮ回繰
   返えし、 （ｃ）これらデータワードのＲをＮ／Ｒ個のベクトル中
   に時間的に整列させ、ここでこれらベクトルの各々内の
   前記データワードをＮ／Ｒインターバルで前記入力スト
   リームから引出すと共に、これらベクトルの各々に、前
   記チャンネルの各々からの前記データワードの１つを設
   け、 （ｄ）前記データワードの位相をシフトし、ここで各チ
   ャンネル内の前記データワードの位相を、各チャンネル
   に対して３６０／Ｒ度の倍数だけシフトし、 （ｅ）前記ベクトルの各々のフーリエ変換を演算し、更
   に、 （ｆ）予じめ決められた係数で掛算するステップから構
   成されたことを特徴とする高速フーリエ変換方法。 ２７　複数個の直列配置されたステージ内のＮ個のデジ
   タルデータワードの入力ストリームを高速フーリエ変換
   演算するに当り、これらステージの各々に、 （ａ）前記データワードのＲをＮ／Ｒ個のベクトル中に
   整列させ、これらベクトルの各々に前記チャンネルの各
   々からの前記データワードの１つを設け、 （ｂ）前記データワードの位相をシフトし、ここでこれ
   らチャンネル中のデータワードの位相を、前記チャンネ
   ルの各々に対して３６０／Ｒ度の倍数だけシフトし、更
   に、 （ｃ）前記ベクトルの各々のフーリエ変換を演算するス
   テップを設けたことを特徴とする高速フーリエ変換方法
   。