JPS593790B2 - Ｆｆｔ エンサンシヨリソウチ - Google Patents

Description

【発明の詳細な説明】 本発明は通信や信号処理の諸分野でよく使用されるＦＦ
Ｔ（高速フーリエ変換）またはそれと類似の演算を行な
う演算装置に関する。

Ｎ個の入カデーメ｛ｘｋ］（に＝０、１、２、・・・・
・・Ｎ−１）から離散的フーリエ変換（ＤＦＴ）（Ｘｌ
１（ｌ−０、１、２ ・・・・・・、Ｎ−１）を求める
にはＮ２回の乗算が必要であるが、この乗算回数を大幅
に低減できる計算手法としてＦＦＴ（高速フーリエ変換
）が知られている。

多くの場合上記の入カデーメ｛ｘｋ］は直列に順次入り
これにＦＦＴを行なつて（Ｘｌ］を求める必要がある。
このような場合に用（・られる演算装置は従来も知られ
ていたが、回路構成は必ずしも単純ではなく、その制御
もかなり複雑であるという欠点があつた。本発明の目的
は、直列入カデーメに対してＦＦＴの演算を行なうのに
適した演算装置を提供することにある。

本発明の他の目的は回路規模が小さく、構成および制御
が簡単な上記演算装置を提供することにある。ただし、
本発明は必ずしもＦＦＴのみを対象としたものではなく
、例えば逆ＦＦＴなどの類似の演算を行なう装置にも適
用可能である。以下ＦＦＴを行なう場合を例にとつて数
式および図面を用いて詳細に説明する。

Ｎ点の入カデーメ系列（ｘｋ］ （に＝０、１、２、・
・・・・・、Ｎ−１）からＮ点のＤＦＴ（Ｘ１］（ｌ−
０、１、２、・・・・・・、Ｎ−１）を求める演算は次
のマトリクス表示で表現できる。

ただし 式（１）を２つのグループに分解する方法と４つのグル
ープに分解する方法とが考えられるが、以下では主とし
て４つのグループに分解する場合を詳しく説明する。

いま、データ点数Ｎが４の倍数であるとすると、式（１
）は次のようにｎ（−０、１、２、３、）を添字とする
４つのグループに分解できる。但し ｎ−０、１、２、
３ ただし 式（４）を簡単のため と表わす。

ＢｎはＭ＞＜Ｎのマトリクスであり、これを変形すると
更にマトリクスＣｎを変形すると、 即ち式（６）は となる。

式（９）において、 である。

ここで゛ とおく。

第１図は上記マトリクスＤｎに相当する操作を実現する
回路の一実施例である。

第１図において、入力データｘ（複素数）は直列に順次
入力端子１００に加えられ、Ｍ（一一）ワード分の直列
遅延素子１０３および（ｊ）ｎ（ｎ−０、１、２、３）
の係数を乗する乗算器１０５を通つて加算器１０１に帰
還される信号と加算されて信号１０２となる。

データはすべて複素数と考えているので、実際には実数
部と虚数部とに分かれて演算遅延が行なわれるが、図に
おいては便宜上分けずに描いてある。

端子１０６には乗算器１０５の出力信号が現われるが、
式（自）からもわかるように、意味のあるデータＹｎは
Ｎ個の入力データのうち最後の−個のデータが入力され
ている時間の出力のみである。さらに、ここで注意すべ
きことは、第１図の回路に挿入されている乗算器では係
数（ｊ）ｎ即ち１、ｊ、−１、−ｊを乗算するだけであ
り、通常の乗算器は不要であることである。例えばある
複素データに（−ｊ）を乗算するには、もとのデータの
実数部と虚数部を入れ換え、その後で虚数部の符号を反
転してやればよいから、極めて簡単な回路で実現できる
。一般に乗算器は多数のフリツプフロツプ、加算器ゲー
トなどで構成される複雑な回路であるからこれが不要に
なることは、ハードウエア規模縮小の点で極めて有利で
ある。また、直列遅延素子１０３と乗算器１０５の順序
を入れかえても第１図のループの伝達関数は変らないか
ら、上記２つの順序を入れかえることもできる。

その場合、出力端子１０６は乗算器１０５の出力をとり
出すように構成できる。つぎに、とするとＦｎは式（８
）で与えられる対角行列でありＹｎに係数ＷＯ、Ｗｎ．
．ｗ２ｎｌ・・・・・・ｗ（Ｍ−１）ｎを順次乗算する
ことに相当する。

第２図はこの操作を実現する回路の一実施例を示し、デ
一汐Ｙｎは入力端子２００から直列に順次入力され、乗
算器２０１で所定の係数を乗じられて出力端子２０２に
出力される。乗算器２０１ではＹｎのＭ個のデータ（Ｙ
Ｏ．ｙｌ、Ｙ２、・・・・・・、ＹＭ−，）に順次に係
数ＷＯ．．ｗｎ．．ｗ２ｎ・・・・・・ｗ（Ｍ−１）ｎ
を乗算する。ＴＸｎ＝Ｅｎ′Ｔｕｎ ・・・・・・・・・・・・・・・（自） であり、式（８）で与えられるＥｎは式（自）のように
変形できる。

Ｅｎ ｗＯＷＯ．．．．．．．．．．．．．．．ＷＯｗ−４Ｍ
ｗ−４（Ｍ−１）・・・・・・Ｗ−４ｗ−８ＭＷ−８（
Ｍ−１）・・・・・・Ｗ−８Ｗ−４（．Ｍ−１）Ｍ．．
．．．．．．．．．．ｗ−４（Ｍ−１）・・・・・・・
・・・・・・・・（自）第３図はマトリクスＥｎの操作
を実現する回路の一実施例を示す図である。

入力信号Ｕｎは入力端子３００に直列に順次入力され、
それぞれ加算器３０１、１ワード分の遅延素子３０３、
乗算器３０４で構成されるＭ個の帰還演算路で演算処理
され、結果Ｘｎは出力端子３０５−１〜３０５Ｍにあら
れれる。また、遅延素子３０３と乗算器３０４の順序は
入れかえても各ループの伝送関数は変わらない。

（ 入力データベクトルＸから出力ベクトルＸｎ（ｎ−
０、１、２、３）を求めるには第１図、第２図、第３図
の回路を縦続に接続してやればよい。

ところで第１図の回路にはＮ−４Ｍ個のデータが入力さ
れるが、意味のある出力信号が出ているのは最後のＭ個
のデータが入力されている間だけであり、それ以外の時
間では第１図の回路の出力は必要でない。従つて第２図
の（乗算器）は上記の時間以外は動作しなくてもよい。
そこでこの遊んでいる時間を利用すれば、ｎ＝０、１、
２、３の全てのグループに対して第２図の乗算器を共通
できる。さてマトリクスＡとマトリクスＥｎとを比較す
ると、ＥｎはＡの行・列を３つおきに取り出してＮ構成
したＭ（一一）×Ｍのマトリクスに他ならない〜 もしＭが再び４の倍数であつたとするとマトリクスＥｎ
は上記の操作をもう一度行なうことにより更に−の大き
さのマトリクスで表わされる４つのグループに分解でき
る。

Ｎ−４ｑＸＰ（Ｐ＼４の倍数）ならば、上記の操作はｑ
回続けて行なえ次々に一のサイズのマトりクズに分解で
きて最後に残るマトリクスは、式（８）に対応して、式
（自）のようになる。

第４図はこのような考え方に基づいて構成した本発明の
一実施例を示す図である。第４図において、入力データ
ｘは順次直列に入力端子４００に入力され、加算器４０
４−１，Ｎ４０８−１４１２−１４１６−Ｌ−データ）
５ ）４ 分の直列遅延素子４０５−１，４０９−１，４１３−１
，４１７−Ｌおよびそれぞれ＋１、ｊ、−１、−ｊを乗
算する乗算器４０６−１，４１０−１４１４−１４１８
−１とから成るＪｊ４つの演算回路で処理される。

ただし、前記のように、これらの係数の乗算には通常の
乗算器は不要である。第４図では上記の４つの演算回路
の間Ｎには−データ分の遅延素子４０１−１４０２４ラ
１４０３−１が挿入されている。

これはＮ個のＤＦＴ｛Ｘ１］（１−０、１、・・・・・
・Ｎ−１）をすべて同一の入力データから求めたい場合
には必要であるが、連続的に入力されるデ一汐の周波数
分析をしたいようなときには必ずしも同一の入力データ
を用いなくてもよい場合が多くその時には上記遅延素子
は不要となる。４つの演算回路の出力信号はそれぞれ端
子４０７−１，４１１−１，４１５−１４１９−１にあ
られれスイツチ４２０−１で順次とり出されて乗算器４
２１−１に入力される。

乗算器４２１−１ではこれらのデータに順に係数ＷＯ、
Ｗｎ．ｗ２ｎ、・・・・・・、ｗ（Ｍ−１）ｎが乗算さ
れる。第４図ではここまでを第１段としている。第２段
は第１段と同様の構成をしているが異なる所は、遅延素
子４０１−２，４０２−２，４０３−２、および４０５
−２，４０９−２４１３−２４１７−２の長さがそ９ｊ
Ｎ れぞれーデーノ分であることと、乗算器４２１２で乗ぜ
られる係数が、ＷＯ、Ｗ４ｎ．ｗ３ｎ・・・・・・、ｗ
（札−１）ｎであることである。

以下同様にして第ｑ段までが構成できる。最後の第（ｑ
＋１）段目は加算器４０４−（ｑ＋１）１デ一汐分の遅
延素子４０５−（ｑ＋１）、乗算器４０６−（ｑ＋１）
から成る演算回路をｐ個並列に並べた構成であり、各乗
算器で乗せられる係数は式（自）かられかるように１Ｐ
である。出力端子４０７−（ｑ＋１）（ｐ個ある）には
順次ＤＦＴの結果があられれる。第４図の各帰還演算回
路を構成している加算器（例えば４０４−１）、遅延素
子（例えば４０５１）、乗算器（例えば４０６−１）の
うち、後二者は順序を入れかえても、各帰還演算器の伝
送関数は変化しない。

従つて、加算器（例えば４０４−１）→乗算器（例えば
４０６−１）→遅延素子（例えば４０５−１）の順に接
続した帰還演算路を構成し、乗算器の出力を各スイツチ
（例えば４２０−１）への入力としてもよい。第４図の
回路はすべて直列演算、直列遅延要素で実現でき制御や
汐イミング等はきわめて容易で回路構成も簡単である。

乗算器は各段あたり１個づつと最終段にｐ−１個、総計
ｐ＋ｑ−１個である。これらの乗算器としてはいわゆる
パイプライン乗算器が適しており、演算速度はデータの
入力速度と等しくてよい。従来から知られているこの種
のＦＦＴ演算処理装置としては、文献１（エイチ・エム
・ハルペーン、アール・ピ一・ペリイ著［ディジタル
マツチド プール汐ズ エージング フアスト フーリ
エ トランスフオームズ」、Ｈ．．Ｍ．．Ｈａｌｐｅｒ
ｎａｎｄＲ．．Ｐ．Ｐｅｒｒｙｌ゛ＤｉｇｉｔａｌＭａ
ｔｃｈｅｄＦｉｌｔｅｒｓＵｓｉｎｇＦａｓｔＦＯｕｒ
ｉｅｒＴｒａｎｓｆＯｒｍｓＪ′ＰｒＯｃ．ＥＡＳＣＯ
Ｎ′７１、ＰＰ、２２２−２３０）があるが、この方法
はかなり複雑な制御を必要とする上、ハードウエアの規
模の点からも本発明の方が有利である。

例としてデータ点数Ｎ−４ｑの場合について両者の比較
を表１に示す。第４図においては、本発明の好ましい実
施例として±１、±ｊを係数とする４つの帰還演算器、
スイツチおよび乗算器とからなる演算処理段を縦続に接
続した構成を示してあるが、上記演算処理段を少くとも
１つ設け、他は等価な演算を別の・・−トウエア構成に
よつて実行することも勿論可能である。

また本文ではＤＦＴのマトリクス表示の式（１）を式（
４）のように４つのグループに分けたため、第４図に一
実施例を示した演算処理装置が得られたがこれはいわゆ
るＲａｄｉｘ−４のＦＦＴに対応する。

一方、式（１）を次のように２つのグループに分解する
こともできる。この式をもとに本文と同様の操作を行な
うと、Ｒａｄｉｘ−２ＦＦＴ演算処理装置ができる。

途中の式は重複するところが多いので詳細は省くが、第
５図はこのようにして構成したＦＦＴ演算処理装置の一
実施例を示す図である。第５図において入力データｘは
順次直列に入力端子５００に入力され、加算器５０２−
１５０５−１データ分の直列遅延素子５０３−１，５０
６−Ｌおよびそれぞれ＋１、−１を乗算する乗算器５０
４−１５０７−１とから成る２つの演算回路で処理され
る。

勿論既に述べたようにこれらの乗算器はきわめて簡単な
回路でよい。また−データ分の遅延素子５０１−１は場
合によつてはとり去つてもよい。上記２つの演算回路の
出力信号はそれぞれ端子５０８−１．５０９−１にあら
れれスイツチ５１０−１でＮ１で−データづつ交互にと
り出 されて乗算器５１１−１に入力される。

この乗算器では係数ＷＯ、Ｗｎ．ｗ２ｎ・・・・・・、
ｗ（丁−１）ｎ（ｎ−０、１）が乗ぜられる。第５図で
はここまでを第１段として描いてある。以下同様に第２
段、第３段、・・・・・・、第２ｑ段までが構成できる
。最終の第（２ｑ＋１）段目は第４図の第（ｑ＋１）段
目と同一の構造をもつている。第５図の回路は第４図の
回路と同様に、すべて直列形成の構成であり、制御も容
易であるという特徴がある。

以上説明したように、本発明によれば、ハードウエア規
模が小さく、また演算素子、遅延素子ともにすべて直列
形成のものを用いることができ、かつ回路構成・制御と
もに簡単なＦＦＴ演算処理装置を提供できる。

なお、本文では特にＦＦＴを行なう演算処理装置を例に
とつて詳しく説明したが、これは代表例にすぎず、他の
類似の演算を行なう場合にも勿論適用可能である。

【図面の簡単な説明】

第１図、第２図および第３図はそれぞれ本発明のＦＦＴ
演算処理装置の部分回路の一実施例を示す図である。 １００・・・・・・入力端子、１０１・・・・・・加算
器、１０３・・・・・・遅延素子、１０５・・・・・・
簡易乗算器、１０６・・・・・・出力端子、２０１・・
・・・・乗算器、３０１−１〜Ｍ・・・・・・加算器、
３０３−１〜Ｍ・・・・・・遅延素子、３０４−１〜Ｍ
・・・・・・乗算器。 第４図は本発明の一実施例を示す図である。 ４００・・・・・・入力端子、４０１，４０２，４０３
，４０５，４０９，４１３，４１７・・・・・・遅延素
子、４０６，４１０，４１４，４１８・・・・・・簡易
乗算器、４２０・・・・・・スィツチ、４２１・・・・
・・乗算器。 第５図は本発明の他の実施例を示す図である。５００・
・・入力端子、５０１，５０３，５０６・・・遅延素子
、５０２，５０５・・・・・・加算器、５０４，５０７
・・・・・・簡易乗算器、５１０・・・・・・スィツチ
、５１１・・・・・・乗算器。

Claims (1)

【特許請求の範囲】
1. １ 第１の入力端子に直列入力データが入力される加算
   手段及び前記加算手段の出力信号に（ｊ）＾ｎ（ｊ＝√
   −１、ｎ＝０、１、２、３）を乗するとともにＭ（あら
   かじめ定められた整数）データ分の遅延を与える演算を
   行い、演算結果を前記加算手段の第２の入力端子に入力
   する第１の乗算手段とから構成される帰還演算路を複数
   個設け、予め定めた係数を乗する第２の乗算手段と、前
   記複数の帰還演算路の出力信号を順次選択し前記第２の
   乗算手段に接続するスイッチとを有する演算回路段を少
   くとも１つ備えたことを特徴とするＦＦＴ演算処理装置
   。