JPS583068A - フ−リエ変換処理装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 本発明はフーリエ変換処理装置に係り、４１に離散的フ
ーリエ変換を高速に処理するためのＮ点高速フーリエ変
換処温回路に関する。

ディジタル信号処理に詔いて離散的フーリエ変換の果す
役割は極めて大きい、４１１に計算時間の大幅な短縮を
可能とする高速フーリエ変換の算法は、サンプル値系列
のパワースペクトル密度、相ｍ。

たたみ、込み等の計算に応用されている。

高速フーリエ変換に関しては、既に数多くの参考文献が
あり１例えば電子通信学会発行の単行本“ディジタル信
号処理“、ＰＰ５Ｏ−７０に詳細な記載がなされている
。高速フーリエ変換のアルゴリズムには２通りの構成が
あり、それぞれ時間の開引き及び周波数の間引きと呼ば
れている。

第１Ｅは時間の間引きを用いた高速フーリエ変換のフロ
ーチャートを示したものである。但し。

例としてデータ点数Ｎが１６の場合を示している。

同図においてＸ、、！、、Ｘ、、・・・・・・、ｘｌ、
は入力複素データ、Ｘ、、Ｘユ、Ｘ、・・・・・・、Ｘ
、は出力複素データである。また、ＴＩ、Ｔ２．Ｔ４及
ｒＪＴ５は端子、３は、バタフライ演算回路を示してい
る。

データ点数Ｎ　＝　２　”　（ｍは整数）とした時、ｍ
＝４であるから、第１図番こ示すように、第１乃至第４
１での４個のステージで構成されている。バタフライ演
算回路３で代表される白丸印（合計３２ある）は、すべ
てバタフライ演算回路を示しており、端子ＴＩ、Ｔ２．
Ｔ４及びＴ５を含む黒丸印（合計８０ある）はすべて端
子を示している。バタフライ演算回路３は、端子〒１及
びＴ２のデータを入力し、端子Ｔ４及びＴ５にデータを
出力する。

同様に、白丸印のバタフライ演算回路はすべて。

左側に接続された２個の端子のデータを入力し。

右側に接続された２個の端子番こデータを出力する。

第１乃至第４の各ステージは共に８個のバタフライ演算
回路から構成されており、第１ステージから順に演算が
行なわれ、第４ステージ終了後に出力データＸ、、Ｘ１
．Ｘ、、・・・・・・、Ｘｌ、が得られる。

入力データ”ｅｔＸｔｔ”ｓ・・・・・・、翼１．は、
同図に示すようにいわゆるビット逆順になうている。

−リエ変換のフローチャートを示したものである。

同図において、＊　＠、１１　Ｂ　Ｘ　Ｂｇ・・・・・
・、！□、は入力複素データ、Ｘ　　Ｘ　　Ｘ　　・・
・・・・、Ｘ８．は出１　　１９　　　廊− 力複素データをそれぞれ示す、またＴ１に代表される黒
丸印はすべて端子を表わしており、３′に代、表される
白丸印はすべてバタフライ演算回路を表わす。第２図に
おいてｌｍ＝４であるから、第１乃至＠４ステージの４
個のステージから構成されているが、以下の点で第１図
と異なっている。第１は入力データは添字の順番通りで
あるが、出力がビット逆順になっていること、第２はバ
タフライ演算回路における入出力端子の組合せがステー
ジに関して逆順になっている仁と、ｌｌ５３にバタフラ
イ演算回路の構成が異なっていることの計３点である。

バタフライ演算回路の構成の相違については後述する。

第１図、第２図では共に１６点高速フーリエ変換のフロ
ーチャートを示したが１点数が２のベキ乗の時には同様
に考えることが可能である。このようなフローチャート
に基づいた高速フーリエ変−のハードウェアを実現する
際にそれ１高速処理を要求されない場合には１時分割多
重処理を行なうバタフライ演算回路とメモリ回路とから
構成される。この時、従来の高速フーリエ賓換ＩＩ＆ｌ
ＩＩ回路は、特にランダム・アクセス・メモリ（ＲＡＭ
）とアドレス・ジェネレータとから成るメモリ回路にお
いて、データの書き込み及び読み出しの制御が複雑であ
り、従ってハードウェア規模が大きくなるという欠点が
ありた。

そこで本発明の目的は、前記欠点を郷決した。

ハードウェア規模の小さい高速のフーリエ変換処理装置
を提供することにある。

本発明の他の目的は制御め簡単な高速のフーリエ変換処
理装置を提供することにある。

本発明によると１つのバタフライ演算回路を時分割多重
使用することによりＮ（＝２”、ｍは２以上の整数）点
フーリエ変換を実現する際に、入力制御信号により時分
割的にデータの変換及び遁砥機能の切換え可能な複数の
配列変換回路と遅延素子とから成り前記バタフライ演算
回路の出力を受けるバッファー回路において、ｍ記複数
の配列変換回路のうち予め定められた１つの特定の配列
変換回路を除く残りの配列変換回路と前記遅延素子とか
ら成る回路の一部分のデータの流れを前記特定の配列変
換回路の方に時分割的に切換える手段と、前記バッファ
回路の出力を、前記バタフライ回路に帰還する手段を有
することを特徴とするフーリエ変換処理装置が得られる
。

次に図面を参照して１本発明をさらに詳細に説明する。

第３図は本発明の一実施例を示したものである。同図に
おいて、１１及び！、は入力端子。

０１及びＯｓは出力端子、２及び８は選択回路。

３はバタフライ演算回路、４及び５は遅延ブロック、４
１，４２，５１及び５２は遅延素子、６，７及び９は第
１．第２及び第３の配列変換回路、６１ｔ６２．７１，
７２．９１及び９２は遅弧素子、６３．フ３及び９３は
スイッチ回路、１０は係数発生回路。

１０１は複素係数出力、１１は制御信号発生回路。

１１１．１１２，１１３，１１４及び１１５は選択信号
、１３１及び１３２は選択回路２の複素データ出力系列
、１４１及び１４２は帰還複素データ系列である。第３
図におけるバタフライ演算回路３と、第１乃至第３の配
列変換回路６，７及び９との詳細プロ、り図をそれぞれ
第４図（ａ）、第４図（ｂ）及び第５図に示す、第３図
のブロック図の動作を説明する前に第４図（ａ）、第４
図（ｂ）及び第５図について詳細に説明する。

第４図（１）は１時間の間引を行なう場合のバタフライ
演算回路、第４図（切は周波数の間引きを行なう場合の
バタフライ演算回路である。同図において、３１．３２
及び３５は入力端子、３３及び。

３４は出力端子、３６は複素乗算１）、３７は複素加算
器、３８は複素減算器である。複素乗算器３６は、実乗
算器４個及び実加算器２個から構成される。また複素加
算器３７は実加算器２個で、複素減算器３８は夷減算器
２個でそれぞれ構成される。

第４図（畠）において、入力端子３１及び３２に。

それぞれ複素データが入力される。入力端子３２から入
力された複素データと、入力端子３５から入力される複
素係数とが、複素乗算器３６において乗算される０乗算
された結果は複素加算器３７及び複素減算器３８に同時
に入力される。一方。

入力端子３１から入力された複素データは、複素加算器
３７及び複素減算ｗｋ３８＃こ同時に入力される。複素
加算器３７及び複素減算器３８の出力は。

それぞれ出力端子３３及び３４に複素データとして現わ
れる。この回路は、時分割多重された複素入力データに
対しても取扱うことができる。この時、入力端子３５か
ら入力される複素係数も時分割に変化するものとする。

第４図（ｂ）のブロック図において、第４図（ａ）と同
一の参照数字は、同一の機能を示している。第４図（ｂ
）は、第４図（ａ）と異なり、複素加減算器３７及び３
８と複素乗算器３６との位置が逆になっている。

次に第５図は、配列変換回路を示すブロック図である。

同図において、２０，２ゲ及び２２は入力端子、２１及
び２ｆは出力端子、５６７及び５６７′は遅延素子、５
６７’はスイッチ回路、Ｄｌ及びＤ２はスイッチ回路５
６７′の複素データ入力系列、Ｄ３及びＤ４はスイッチ
回路５６？＃の複素データ出力系列である。入力端子２
０及び２σから入力される時分割多重された複素データ
系列は、それぞれ複素データ入力系列Ｄ１．及び遷延素
子５６１を介した複素データ入力系列Ｄ２としてスイッ
チ回路５６τに入力される。２人力２出力のスイッチ回
路５６？’では、第５図に示したように、入力端子２２
から入力される選択信号が論理値“Ｌ“（ローレベル）
の時には、複素入力データ系列Ｄ１及びＤ２は、それぞ
れ複素データ出力系列Ｄ３及びＤ４として出力される。

また、入力端子２２から入力される選択信号が論理値“
Ｈ′″（ハイレベル）の時には、複素データ入力系列Ｄ
１及びＤ２はそれぞれ複素データ出力系列Ｄ４及びＤ３
として出力され、データの交換が行なわれる。さらに。

複素データ出力系列Ｄ３は、遅画素子５６７を介して、
複素データ出力系列Ｄ４は直接に、それぞれ出力端子２
１及び２１′に現われる。

次に第３図のブロック図について第６図（２）乃至第６
図（Ｉ）のタイミングチャートを参照しながら詳細に説
明する。今、説明を簡単にするために、データ点数Ｎ＝
１６を例として挙げ１時間の間引について考える。ｌ！
りで第３図におけるバタフライ演算回路３は第４図（Ｉ
ｌｌ）に示した構成であるものとする。第３図において
入力端子１１及びＩＳにはそれぞれ時分割多重された複
素データ系列が入力される。その様子を第６図（２）に
示す。即ち１マルチフレームは、４フレームから構成さ
れｌフレームは８ワードから構成されており、入力端子
Ｔ１及びＩｓに入力される複素データ系列は、１マルチ
フレームの中の１フレームのみ（ここでは第１フレーム
）高速フーリエ変換すべ舎データが収容されている。第
６図（５）の上段及び下段の複素データ系列は、それぞ
れ第３図入力端子１１及び′Ｘｍに入力されるデータに
対応している。また第６図に）岬において、タイ文ング
チャート上の数字はワード区別するために用いられてい
る。第６図に）に詔いて、複素デ〒り「０」及び複素デ
ータ「１」は第１図の１６点ＦＦＴのフローチャートに
おける入力複素データＸ、及びＸ、に対応しており、第
１ステージのバタフライ演算を行なうべ含入カペアーを
示す、また複素データｒ２Ｊ及び複素データ「３」は第
１図の入力複素データｘ４及びＸ□に対応して諺り、第
１ステージのバタフライ演算を行なうべき入力ペアーを
示す、同様にＭ６図に）に示す複素人力データ系列は、
第１図の第１ステージ（１）８個０）ハルフライ演算を
縦方向に上から下まで時分割多重で処理できるように配
列されているものとする。このよう化配列された複素デ
ータ入力系列ペアである第６図（６）は、ＩＫ３図の入
カ端子工１及び！意に入力され、それぞれ選択回路２の
第１の入力となる。この選択回路２では第３の制御信号
発生回路９より出方される選択信号１１１により、入力
端子１１及びＩＩから入力されるデータのうち第１フレ
ームのデータのみを選択して。

また、第２．第３及び第４フレームにおいては。

帰還複素データ系列１４１及び１４２を選択し。

複素データ系列１３１及び１３２として出方する。

−タ系列１３１，１３２はバタフライ演算回路３１こ入
力される。一方、係数発生回路１０より出力される複葉
係数１０１もバタフライ演算回路３に入力され、バタフ
ライ演算が時分割多重で行なわれる。今、バタフライ演
算回路３の遅延量をＸワード（但し１＜ｘく２）と仮定
する。さらに、遅延プロ、り４の中の遅延素子４１及び
４２の遅延量を（２−ｘ）ワードとすれば、遅延プロ、
り４の複素データ出力系列ペアは、バタフライ演算回路
３の入力から見て、２ワ一ド分遍砥されて出力される。

第６図（ｑは、遅延ブロック４の複素データ出力系列ペ
アを示したものである。但し、第６図（ｑの上段及び下
段は、それぞれ（２−ｘ）ワード遅延素子４１及び４２
の出力を示す。

第３図において、遅延ブロック５の遅延素子５１及び５
２は、共に１ワ一ド分の遅延量に、第１の配列変換回路
６の遅延素子６１及び６２は共に１ワ一ド分の遅雨量に
、配列変換回路７の遅延素子７１及びフ２は共に２ワ一
ド分の遅延量に。

ｇａの配列変換回路９の遅延素子９１及び９２は共に４
ワ一ド分の遅延量にそれぞれ設定されているものとする
。

制御信号発生回路１１の出力である選択信号１１！、１
１３及び１１５のタイミングチャートを、それぞれ第６
図（ト）、第６図山及び第６図（ハ）に示す、さらに、
第１．第２及び第３の配列変換回路６，７及び９の複素
データ入力系列ペアのタイミングチャートを、それぞれ
第６図（Ｑ、第６図（ト）及び第６図（ｑに、第３の配
列変換回路９の複素データ出力系列ペア１４１及び１４
２のタイミングチャートを第６図（Ｉ）に示す、第６図
（Ｑ、第６図（ト）及び第６図（ｑにおいて、上段の複
素データ系列は、それぞれスイッチ回路６，７及び９の
上段の入力を示しており、また下段の複素データ系列は
それぞれ遅延素子６Ｌ７２及び９２の入力を示している
。さらに複素データ系列１４１及び１４２はそれぞれ第
６図（ηの上段及び下段のデータに対応している。

第３図において、バタフライ演算回路３は、第６図（至
）に示すように第１フレームでは第１ステージの、第２
フレームでは第２ステージの、第３フレームでは第３ス
テージの、第４フレームでは第４ステージのそれぞれ８
個のバタフライ演算を時分割に感層しそいる。遅延プロ
、り５の内部の１ワ一ド遅延票子５１及び５２により、
その出力は第６図（ト）の゛タイミングチャートに示さ
れている。

第１の配列変換回路６では第１フレーム即ち第１ステー
ジのバタフライ演算終了後のデータに対して、第２ステ
ージのバタフライ演算が可能なようにスイッチ回路６３
及び選択信号１１２により配列変換を行なうが（この時
、同時に１ワードの遅延を生じる）、第２．第３及び第
４フレームのデータに対しては単に１９−ドの遅延を与
える働きを行なう、また、第１の配列変換回路６では　
ｇｚフレーム即ち第２ステージのバタフライ演算終了後
のデータに対して、第３ステージのバタフライ演算が可
能なようにスイッチ回路７３及び選択信号１１３により
、データの配列変換を行なうが（この時、同時に２ワー
ドの逼砥を生じる）、ｊｌｌ１、第３及び第４フレーム
のデータに対しては単に２９−ドの遅延を与える働きを
する。さらに第１及び第２の配列変換回路６及び７のそ
れぞれの複素データ出力系列ペアは２選択回路８に入力
され１選択信号１１４により、第１フレームのデータに
対しては、第１の配列変換回路６の複素データ出力系列
ペアを選択して出力し、第２フレームのデータに対して
は第２の配列変換回路７の複素データ出力系列ペアを選
択して出力す、る。第３及び第４フレームのデータに対
しては、どちらの複素データ出力系列ペアを選択しても
よい、この時の選択回路８．複素データ出力系列ペアを
第６図（ｑに示す。

第３の配列変換回路９では、第３フレーム即ち第３ステ
ージのバタフライ演算終了後のデータに対して第４ステ
ージのバタフライ演算が可能なようにスイッチ回路９３
及び選択信号１１５によりデータの配列変換を行なうが
（この時、同時に４ワードの遍砥を生じる）、第１．第
２及び第４フレームのデータに対しては単に４ワードの
遅延を以上述べたような構成により、バタフライ演算回
路３から出力される複素データ系列ペアーは。

遅延ブロック５と第１の配列変換回路６の縦続接続又は
第２の配列変換回路７を介して、第３の配列変換回路９
を通して、１度４フレーム即ちこの場合８９−ドの遅延
を受けて複素データ系列ペア１４１及び１４２として出
力端子０翼及びＯｓに現われると同時に１選択回路２の
第２の入力データとして入力される。このデータのタイ
ミングチャートを第６図（Ｉ）に示す０選択回路２では
、選択信号１１１により、第１フレームのデータに対し
ては、入力端子１１及びＩｓから入力される高速フーリ
エ変換すべき複素データ系列ペアを、第２フレーム、第
３フレーム及び第４フレームではそれぞれ第１ステージ
、第２ステージ、＃ｌＩ３ステージのバタフライ演算終
了後の複素データ系列１４１及び１４２を選択して複素
データ系列ペア１３１及び１３２として出力する。

以上述べたＩｓ３図のブロック図の動作を第１図のフロ
ーチャートに対応させて説明すると以下のようになる。

即ち、第１ｗＪｊこ示したバタフライ演算はすべて各ス
テージの一番上のバタフライ演算から順に一番下のバタ
フライ演算まで１フレームの時間内に時分割に処理する
。さらに第１．第２゜第３及び第４ステージの６個のバ
タフライ演算はそれぞれ第１．第２．第３及び１１１４
フレームの時間内に時分割に処理されることになる。高
速フーリエ変換された最終出力は、＠３図に詔いて、バ
タフライ演算回路３の複素データ出力系列ペア。

又は、遅延プロ、り５の複素データ出力系列ペア。

又は第１の配列変換回路６の複素データ出力系列ペア、
又は第２の配列変換回路７の複素データ出力系列ペア、
又は第３の配列変換回路９の出力である複葉データ系列
１４１及び１４２のいずれかの複素データ系列ペアの第
４フレームとして取り出すことにより得ることができる
。

第３図に示した本発明の一実施例では、メモリ容量が最
小となる構成となうており、遅延ブロック５及び第１の
配列変換回路６を通る信号のパスと、第２の配列変換回
路γを通る信号のパスとはその遅延量が共に等しく２ワ
ードに設定されている。また、遅延ブロック５及び第１
の配列変換回路６の位置を交換することも可能である。

但し、この時１選択信号１１２の位相をずらす必要があ
る。さらに、遅延ブロック４と、遅延プロ、り５゜第１
及び第２の配列変換回路６及び７．及び選択回路８から
構成されるプロ、りと１選択回路９との三要素の位置を
互いに任意［１１＆換えても、前記説明と同様に、高速
フーリエ変換処理回路を構成することができる。但し、
この時選択信号１１２゜１１３．１１４及び１１５の位
相を適当にずらすことにより実現できる。また、これ菫
での説明では、バタフライ演算回路３の入出力データの
遅延量は、Ｘワード（１＜ｘ＜２＞と仮定していたが。

Ｘが２ワードより大きい場合にも本発明を害鳥に適用で
きる。さらに第３図において遅延素子４１゜４２．１５
Ｌ　　５２，６Ｌ　６２，７１．γ島９１゜及び９２は
、すべて複素データ系列に対して遅延を与えるものであ
り、実際にはそれぞれ実数部デ−夕系列及び虚数部デー
タ系列の各々に対して遅延素子が用意されているものと
する。

これまで、説明を簡単にするために、高速フーリエ変換
のデータ点数Ｎを１６と仮定して會たが。

本発明はＮが２のべき乗である限り適用することが可能
である。即ち　ｐｉ　＝　２　ｆｉｌの場合には、第３
図においては、３個となっている配列変換ブロックを（
Ｉｎ−１）個とすることにより実現すること・　が可能
となる。この時、（１−１）個の配列変換ブロック内の
遅延素子の遅延量はそれぞれ２　ワード、２　ワード、
・・・・・・　２　ｍ　−１ワードに設定しておけばよ
い。

さらに今までの説明では１時間の間引きを仮定していた
が、以下に述べる理由から明らかなように１本発明は周
波数の間引きに対しても適用することが可能である。第
１図の時間の間引く対するフローチャートと、縞２図の
周波数の間引きに対するフローチャートがら明らかなよ
うに、ステージ間の配列変換を行なう順序を今までの説
明とは逆に行なえばよい、即ち、第３図において第３の
配列変換回路９は、第３フレームに対してのみデータの
配列変換を行なっていたが、これを第１フレームに対し
てのみデータの配列変換を行なうことにすればよい、ま
た第２の配列変換７は変更しないでよい、さらに第１の
配列変換回路６は、第１フレームに対してのみデータの
配列変換を行なっていたが、これを第３フレームに対し
てのみデータの配列変換を行なうよう変更する。従って
、第１及び第２の配列変換回路６及び７に入力されてい
る選択信号１１２及び１１３のみ、上記の動作が可能な
ように変更すること、またバタフライ−演算回路３とし
て第４図（ｂ）を用いることで実現Ｖ舎る。またデータ
点数Ｎが２のべき乗である任意のＮに対して同様に適用
することが可能である。

以上述べたように１本発明によれば、制御の簡単な、ハ
ードウェアの小さい高速フーリエ処理装置を実現するこ
とができる。

【図面の簡単な説明】

第１図、第２図はそれぞれ時間の間引き及び周波数の間
引きに対する１６点高速フーリエ変換のフローチャート
図である。第３図は本発明の一実施例を示したブロック
図である。第４図（ａ）、第４図（ｂ）はいずれも第３
図に示したバタフライ演算回路の詳細なブロック図であ
る。第５図は、第３図番ζ示した配列変換回路の詳細な
ブロック図であるつ嬉６図（６）乃至第６図（Ｉ）は第
３図を説明するためのタイミングチャート図である。 尚１図において、ｘ、乃至”１１は入力複素データ、Ｘ
、乃至Ｘ１．ハ出力複素データ、’ｒｌ、ＴｈｅＴ４及
びＴ５は端子、ぎはバタフライ演算回路。 １１及び工１は入力端子、２及び８は選択回路。 ３はバタフライ演算回路、４及び５は遅延プロνり、６
，７及び９はそれぞれ第１．第２及び第３の配列変換回
路、１０は係数発生回路、１１は制御信号発生回路、Ｏ
ｓ及びＯｓは出力端子、３１゜３２及び３Ｓは入力端子
、３３及び３４は出力端子、３６は複素乗算器、３７は
複素加算器、３＄は複素減算器、２０，２ゲ及び２２は
入力端子。

Claims (1)

【特許請求の範囲】
1. １つのバタフライ演算回路を時分割多重使用することに
   よりＮ（＝２ｍ、ｍは２以上の整数）点フーリエ変換を
   ！Ａｌｌする際に、入力制御信号により時分割的にデー
   タの交換及び遅延機能の切換え可能な複数の配列変換回
   路と遅蔦素子とから成り前記バタフライ演算回路の出力
   を受けるバッファー回路に右いて、前記複数の配列変換
   回路のうち予め定められた１つの特定の配列変換回路を
   除く残りの配列変換回路と、前記遅延素子とから成る回
   路の一部分のデータの流れを前記特定の配列変換回路の
   方に時分割的に切換える手段と、前記パ、ファ回−の出
   力を、前記バタフライ回路に帰還する手段を有すること
   を特徴とするフーリエ変換処理装置。