JPH0113580B2

JPH0113580B2 -

Info

Publication number: JPH0113580B2
Application number: JP55151808A
Authority: JP
Inventors: Akira Kanemasa
Original assignee: Nippon Electric Co Ltd
Current assignee: NEC Corp
Priority date: 1980-10-29
Filing date: 1980-10-29
Publication date: 1989-03-07
Also published as: JPS5775372A

Description

【発明の詳細な説明】本発明は離散的フーリエ変換を高速に処理する
ための高速フーリエ変換処理回路に関する。

デイジタル信号処理において離散的フーリエ変
換の果す役割は極めて大きい。特に計算時間の大
幅な短縮を可能とする高速フーリエ変換の算法は
サンプル値系列のパワースペクトル密度、相関、
たたみ込み等の計算に応用されている。

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

第１図は、時間の間引きを用いた高速フーリエ
変換のフローチヤートを示したものである。ただ
し例としてデータ点数Ｎが16の場合を示してい
る。同図においてX₀，X₁，X₂…，X₁₅は入力複
素データ、X₀，X₁，X₂…，X₁₅は出力複素デー
タである。また、、、およびは端子、
はバタフライ演算回路を示している。Ｎ＝2^m（ｍ
は整数）とした時ｍ＝４であるから第１図に示す
ように第１〜第４までの４個のステージで構成さ
れている。バタフライ演算回路で代表される白
丸印はすべてバタフライ演算回路を示しており、
端子，，およびを含む黒丸印はすべて端
子を示している。バタフライ演算回路は端子
およびのデータを入力し、端子およびにデ
ータを出力する。同様に、白丸印のバタフライ演
算回路はすべて左側に接続された２個の端子のデ
ータを入力し、右側に接続された２個の端子にデ
ータを出力する。各ステージは共に８個のバタフ
ライ演算回路から構成されており、第１ステージ
から順に演算が行なわれ第４ステージ終了後出力
データX₀，X₁，X₂，…，X₁₅が得られる。入力
データは同図に示すようにいわゆるビツト逆順に
なつている。

第２図は周波数の間引きを用いて16点高速フー
リエ変換のフローチヤートを示したものである。
同図においてX₀，X₁，X₂，…，X₁₅は入力複素
データ、X₀，X₁，X₂，…，X₁₅は出力複素デー
タをそれぞれ示す。またに代表される黒丸印は
すべて端子を表わしており、に代表される白丸
印はすべてバタフライ演算回路を表わす。第２図
において、ｍ＝４であるから第１〜第４ステージ
の４個のステージから構成されているが以下の点
で第１図と異なつている。第１は、入力データは
添字の順番通りであるが、出力がビツト逆順にな
つていること、第２はバタフライ演算回路におけ
る入出力端子の組合せ方法がステージに関して逆
順になつていること、第３に、バタフライ演算回
路の構成が異なつていることの３点である。バタ
フライ演算回路の構成の相違については後述す
る。

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

そこで本発明の目的はハードウエアの小さな高
速フーリエ変換処理回路を提供することにある。

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

次に図面を参照して本発明を詳細に説明する。
第３図は本発明の一実施例を示したものである。
同図において、１₁および１₂は入力端子、２は選
択回路、３はバタフライ演算回路、４₁および４₂
は遅延素子、５，６および７は配列変換回路、５
_１，５₂，６₁，６₂，７₁および７₂は遅延素子、５
_３，６₃および７₃はスイツチ回路、８は係数発生
回路、８₁は複素係数出力、９は制御信号発生回
路、９₁，９₂，９₃および９₄は選択信号、１０₁お
よび１０₂は帰還複素データ系列、１１₁および１
１₂は選択回路２の複素データ出力系列、１２₁お
よび１２₂は出力端子である。第３図におけるバ
タフライ演算回路３と、配列変換回路５，６およ
び７の詳細ブロツク図をそれぞれ第４図および第
５図に示す。第３図のブロツク図の動作を説明す
る前に第４図および第５図について詳細に説明す
る。

第４図においてａは時間の間引きを行なう場合
のバタフライ演算回路、ｂは周波数の間引きを行
なう場合のバタフライ演算回路である。第４図
ａ，ｂにおいて３₁，３₂および３₅は入力端子、
３₅および３₄は出力端子、３₆は複素乗算器、３₇
は複素加算器、３₈は複素減算器である。複素乗
算器３₆は実乗算器４個および実加算器２個から
構成される。また複素加算器３₇は実加算器２個
で、複素減算器３₈は実減算器２個でそれぞれ構
成されている。

第４図ａにおいて、入力端子３₁および３₂には
それぞれ複素データが入力される。入力端子３₂
から入力された複素データと、入力端子３₅から
入力される複素係数とが複素乗算器３₆において
乗算される。乗算された結果は複素加算器３₇お
よび複素減算器３₈に同時に入力される。一方入
力端子３₁から入力された複素データは複素加算
器３₇および複素減算器３₈に同時に入力される。
複素加算器３₇および複素減算器３₈の出力はそれ
ぞれ出力端子３₃および３₄に複素データとして現
われる。この回路は時分割多重された複素入力デ
ータに対しても取扱うことができる。この時入力
端子３₅から入力される複素係数も時分割に変化
するものとする。

第４図ｂのブロツク図において、第４図ａと同
一の参照数字は同一の機能を示している。第４図
ｂでは第４図ａと異なり、複素加減算器３₇およ
び３₈と複数乗算器３₆の位置が逆になつている。

次に、第５図は配列変換回路を示すブロツク図
で、同図において、２０₁，２０₂および２２は入
力端子、２１₁および２１₂は出力端子、５６７₁
および５６７₂は遅延素子、５６７₃はスイツチ回
路、５６７₄および５６７₅はスイツチ回路５６７
_３の複素データ入力系列、５６７₆および５６７₇
はスイツチ回路５６７₃の複素データ出力系列で
ある。入力端子２０₁および２０₂から入力される
時分割多重された複素データ系列は、それぞれ複
素データ入力系列５６７₄および遅延素子５６７₂
を介して複素データ入力系列５６７₅としてスイ
ツチ回路５６７₃に入力される。２入力２出力の
スイツチ回路５６７₃では、第５図に示したよう
に、入力端子２２から入力される選択信号が
“Ｌ”の時には複素入力データ系列５６７₄および
５６７₅はそれぞれ複素データ出力系列５６７₆お
よび５６７₇として出力される。また、入力端子
２２から入力される選択信号が“Ｈ”の時には、
複素データ入力系列５６７₄および５６７₅はそれ
ぞれ複素データ出力系列５６７₇および５６７₆と
して出力され、データの交換が行なわれる。さら
に複素データ出力系列５６７₆は遅延素子５６７₁
を介して、複素データ出力系列５６７₇は直接に
それぞれ出力端子２１₁および２１₂に現われる。

次に第３図のブロツク図について第６図のタイ
ミングチヤートを参照して詳細に説明する。今、
説明を簡単にするために、データ点数Ｎ＝16を例
として挙げ、時間の間引きについて考える。従つ
て第３図におけるバタフライ演算回路３は第４図
ａに示した構成であるものとする。第３図におい
て入力端子１₁および２₂にはそれぞれ時分割多重
された複素データ系列が入力される。その様子を
第６図１に示す。すなわち１マルチフレームは４
フレームから構成され、１フレームは８ワードか
ら構成されており入力端子１₁および１₂に入力さ
れる複素データ系列は１マルチフレームの中の１
フレームのみ（ここでは第１フレーム）高速フー
リエ変換すべきデータが収容されている。第６図
１の上段および下段の複素データ系列はそれぞれ
第３図入力端子１₁および１₂に入力されるデータ
に対応している。また第６図においてタイミング
チヤート上の数字はワード区別するために用いら
れている。

第６図１において、複素データ０および複素デ
ータ１は第１図の16点高速フーリエ変換のフロー
チヤートにおけるx₀およびx₃に対応しており、第
１ステージのバタフライ演算を行なうべき入力ペ
アを示す。また複素データ２および複素データ３
は第１図のx₄およびx₁₂に対応しており、第１ス
テージのバタフライ演算を行なうべき入力ペアを
示す。同様に第６図１に示す複素入力データ系列
は、第１図の第１ステージの８個のバタフライ演
算を縦方向に上から下まで時分割多重で処理でき
るように配列されているものとする。このように
配列された複素データ入力系列ペアである第６図
１は第３図の入力端子１₁および１₂に入力され、
それぞれ選択回路２の第１の入力となる。選択回
路２では制御信号発生回路９より出力される選択
信号９₁により入力端子１₁および１₂から入力さ
れるデータのうち第１フレームのデータのみを選
択してまた第２、第３および第４フレームにおい
ては帰還複数データ系列１０₁および１０₂を選択
し複素データ系列１１₁および１１₂として出力す
る。この様子を第６図２に示す。

選択回路２の複素データ系列１１₁，１１₂はバ
タフライ演算回路３に入力される。一方係数発生
回路８より出力される複素係数８₁もバタフライ
演算回路３に入力され、バタフライ演算が時分割
多重で行なわれる。今、バタフライ演算は遅延な
しで行なわれるものと仮定する。バタフライ演算
回路の複素データ出力系列ペアはそれぞれ１ワー
ド遅延素子４₁および４₂に入力されて１ワードの
遅延を受けた後共に配列変換回路５に入力され
る。第６図(3)は１ワード遅延素子４₁および４₂の
複素データ出力系列を示したものである。ただし
上段および下段はそれぞれ１ワード遅延素子４₁
および４₂の出力を示す。

第３図において配列変換回路５の遅延素子５₁
および５₂は共に１ワード分の遅延量に、配列変
換回路５の遅延素子６₁および６₂は共に２ワード
分の遅延量に、配列変換回路７の遅延素子７₁お
よび７₂は共に４ワード分の遅延量にそれぞれ設
定されているものとする。制御信号発生回路９の
出力である選択信号９₂，９₃および９₄はそれぞ
れ配列変換回路５，６および７のスイツチ回路５
_３，６₃および７₃に入力されている。選択信号９
_２，９₃および９₄のタイミングチヤートをそれぞ
れ第６図４，６および８に示す。さらに配列変換
回路５，６および７の複素データ出力系列ペアの
タイミングチヤートをそれぞれ第６図５，７およ
び９に示す。第６図５，７および９において上段
の複素データ系列はそれぞれ遅延素子５₁，６₁お
よび７₁の出力を示しており、また下段の複素デ
ータ系列はそれぞれスイツチ回路５₃，６₃および
７₃の下側の出力を示している。

第３図において、バタフライ演算回路３は第６
図２に示すように第１フレームでは第１ステージ
の、第２フレームでは第２ステージの、第３フレ
ームでは第３ステージの、第４フレームでは第４
ステージのそれぞれ８個のバタフライ演算を時分
割に多重処理している。配列変換回路５では第１
フレームすなわち第１ステージのバタフライ演算
終了後のデータに対して、第２ステージのバタフ
ライ演算が可能なようにスイツチ回路５₃および
選択信号９₂によりデータの配列変換を行なうが
（この時同時に１ワードの遅延を生じる）、第２、
第３第および第４フレームのデータに対しては単
に11ワードの遅延を与える働きを行なう。同様に
配列変換回路６では第２フレームすなわち第２ス
テージのバタフライ演算終了後のデータに対して
第３ステージのバタフライ演算が可能なようにス
イツチ回路６₃および選択信号９₃によりデータの
配列変換を行なうが（この時同時に２ワードの遅
延を生じる）、第１，第３および第４フレームの
データに対しては単に２ワードの遅延を与える働
きをする。さらに配列変換回路７では第３フレー
ムすなわち第３ステージのバタフライ演算終了後
のデータに対して第４ステージのバタフライ演算
が可能なように、スイツチ回路７₃および選択信
号９₄によりデータの配列変換を行なうが（この
時同時に４ワードの遅延を生じる）、第１，第２
および第４フレームのデータに対しては単に４ワ
ードの遅延を与える働きをする。従つてバタフラ
イ演算回路３から出力される複素データ系列ペア
は遅延素子４₁および４₂および配列変換回路５，
６および７を通して、丁度１フレームすなわちこ
の場合８ワードの遅延を受けて複素データ系列１
０₁および１０₂として現われる。この様子を第６
図９に示す。複素データ系列１０₁および１０₂は
共に選択回路２の第２の入力データとして入力さ
れる。選択回路２では選択信号９₁により第１フ
レームは入力端子１₁および１₂から入力される高
速フーリエ変換すべき複素データ系列ペアを、第
２フレーム、第３フレームおよび第４フレームで
は、それぞれ第１ステージ、第２ステージ、第３
ステージのバタフライ演算終了後の複素データ系
列１０₁および１０₂を選択して複素データ系列ペ
ア１１₁および１１₂として出力する。

以上述べた第３図のブロツク図の動作を第１図
のフローチヤートに対応させて説明すると以下の
ようになる。すなわち第１図に示したバタフライ
演算はすべて各ステージの一番上のバタフライ演
算から順に一番下のバタフライ演算まで１フレー
ムの時間内に時分割に処理する。さらに第１、第
２、第３および第４ステージの８個のバタフライ
演算は、それぞれ第１，第２，第３および第４フ
レームの時間内に時分割に処理されることにな
る。高速フーリエ変換された最終出力は第３図に
おいて、バタフライ演算回路３の複素データ出力
系列ペア、または遅延素子４₁および４₂の複素デ
ータ出力系列、または配列変換回路５の複素デー
タ出力系列ペア、または配列変換回路６の複素デ
ータ出力系列ペア、または配列変換回路７の出力
である複素データ系列１０₁および１０₂のいずれ
かの複素データ系列ペアの第４フレームとして取
り出すことにより得ることができる。第３図では
例として複素データ系列１０₁および１０₂を出力
端子１２₁および１２₂に得るような構成となつて
いる。

第３図において、ブロツク図の動作原理から明
らかなように、遅延素子４₁および４₂から成るブ
ロツクと配列変換回路５と配列変換回路６と配列
変換回路７は、互いにその位置を任意に置き換え
ても前記説明と同様に高速フーリエ変換回路を構
成することができる。この場合、第６図において
４，６および８の選択信号をそれぞれ、配列変換
回路５，６および７の挿入位置に応じてタイミン
グをずらせば容易に実現可能となる。またこれま
での説明ではバタフライ演算回路３の入出力デー
タは遅延がないものと仮定してきたが、実際にハ
ードウエアを実現する時には遅延が生じる場合も
あり、この場合遅延が１ワード以下であれば、１
ワード遅延素子４₁および４₁の遅延量をバタフラ
イ演算回路の遅延量だけ短かくすることにより解
決することが可能となる。さらに第３図において
遅延素子４₁，４₂，５₁，５₂，６₁，６₂，７₁およ
び７₂はすべて複素データ系列に対して遅延を与
えるものであり、実際には実数部データ系列およ
び虚数部データ系列の各々に対し遅延素子が用意
されているものとする。

これまで説明を簡単にするために、高速フーリ
エ変換のデータ点数Ｎを16と仮定してきたが、本
発明は２の冪乗であるいかなるＮに対しても適用
することが可能である。すなわちＮ＝2^mの場合に
は第３図においては３個となつている配列変換ブ
ロツクを（ｍ−１）個とすることにより実現する
ことが可能となる。この時（ｍ−１）個の配列変
換ブロツク内の遅延素子の遅延量はそれぞれ2⁰ワ
ード，2¹ワード，…，2^m-2ワードに設定しておけ
ばよい。さらに今までの説明では時間の間引きを
仮定していたが、以下に述べる理由から明らかな
ように本発明は周波数の間引きに対しても適用す
ることが可能である。第１図の時間の間引きに対
するフローチヤートと第２図の周波数の間引きに
対するフローチヤートから明らかなように、ステ
ージ間の配列変換を行なう順序を今までの説明と
は逆に行なえばよい。すなわち第３図において、
配列変換回路７は第３フレームに対してのみデー
タの配列変換を行なつていたが、これを第１フレ
ームに対してのみデータの配列変換を行なうこと
にすればよい。また配列変換７は変更しないでよ
い。さらに配列変換回路５は、第１フレームに対
してのみデータの配列変換を行なつていたが、こ
れを第３フレームに対してのみデータの配列変換
を行なうよう変更する。従つて配列変換回路５お
よび７に入力されている選択信号９₂および９₄の
み上記の動作が可能なように変更すること、また
バタフライ演算回路３として第４図ｂを用いるこ
とで実現できる。またデータ点数Ｎが２の冪乗で
ある任意のＮに対して同様に適用することが可能
である。

以上述べたように本発明を用いれば、制御が簡
単で、ハードウエアの小さい高速フーリエ処理回
路を提供することができる。

【図面の簡単な説明】

第１図および第２図はそれぞれ時間の間引きお
よび周波数の間引きに対する16点高速フーリエ変
換のフローチヤートを示し、第３図は本発明の一
実施例を示したブロツク図であり、同図において
１は入力端子、２は選択回路、３はバタフライ演
算回路、４は遅延素子、５，６および７は配列変
換回路、８は係数発生回路、９は制御信号発生回
路である。第４図は第３図に示したバタフライ演
算回路３の詳細ブロツク図で、ａおよびｂはそれ
ぞれ時間の間引きおよび周波数の間引きに応対し
たバタフライ演算回路であり、３₁，３₂および３
_５は入力端子、３₃および３₄は出力端子、３₆は複
素乗算器、３₇は複素加算器、３₈は複素減算器で
ある。第５図は第３図に示した配列変換回路の詳
細ブロツク図で、２０および２２は入力端子、２
１は出力端子、５６７₁および５６７₂は遅延素
子、５７６₃はスイツチ回路である。第６図は第
３図を説明するためのタイミングチヤートであ
る。

Claims

【特許請求の範囲】

１１個の乗算器と２個の複素加減算器とから成
り複素データ系列ペアを入出力とする１個のバタ
フライ演算回路を時分割多重してＮ（＝2^m、ただ
しｍは２以上の整数）点高速フーリエ変換回路を
実現する際に、前記バタフライ演算回路の出力複
素データ系列ペアを受け予め定められた量の遅延
を与える遅延素子ペアと、該遅延素子ペア出力を
受け制御信号により複素データ系列ペア間のデー
タの配列変換を行なう縦続接続された（ｍ−１）
個の配列変換回路と、該縦続接続された（ｍ−
１）個の配列変換回路の最終出力複素データ系列
ペアを第１の入力とし高速フーリエ変換すべき複
素データ系列ペアを第２の入力とする選択回路
と、該選択回路の出力を受ける前記バタフライ演
算回路とを少なくとも具備し、前記制御信号によ
り動作するスイツチと複素データ系列を遅延させ
る第１及び第２の遅延素子とから成る前記配列変
換回路の各々において、入力される複素データ系
列ペアのうち予め定められた一方のみを前記第１
の遅延素子を介して出力し他方と組合わせて前記
スイツチの入力複素データ系列ペアとし、前記ス
イツチの出力複素データ系列ペアのうち予め定め
られた一方のみを前記第２の遅延素子を介して出
力し、他方と組合わせて前記配列変換回路の出力
複素データ系列となるよう構成すると共に、前記
（ｍ−１）個の各配列変換回路内の第１及び第２
の遅延素子の遅延量を等しくそれぞれ２⁰ワード、
２¹ワード、…、２^m-2ワードとなるように設定
し、これら遅延量に対応して前記配列変換回路内
のスイツチを制御するための制御信号として
各々、２⁰ワード、２¹ワード、…、２^m-2ワード
のオン／オフの繰返しパターンを挿入するように
したことを特徴とするＮ点高速フーリエ変換回
路。