高速フーリエ変換装置
【課題】１ステージ分のバタフライ演算回路を用意して行う従来の方法では、処理する信号数が大きくなると回路規模が大きくなってしまう問題点があった。また、FFT演算を少ないハードウェア量で出来るだけ処理時間を短くすることに課題がある。
【解決手段】従来手法で１ステージ分のバタフライ演算回路で行っていた演算を、1個のバタフライ演算部を繰り返し使って演算することでゲート数を削減する。また、FFT演算の順番を並び替える最適化をすることで、RAMのリード回数削減と処理時間の短縮を実現する。さらに、RAMから中間データを読み出すアドレスを各ステージで共通化することでアドレス生成部を小型化し、ゲート規模の削減を図る。
【解決手段】従来手法で１ステージ分のバタフライ演算回路で行っていた演算を、1個のバタフライ演算部を繰り返し使って演算することでゲート数を削減する。また、FFT演算の順番を並び替える最適化をすることで、RAMのリード回数削減と処理時間の短縮を実現する。さらに、RAMから中間データを読み出すアドレスを各ステージで共通化することでアドレス生成部を小型化し、ゲート規模の削減を図る。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、高速フーリエ変換装置、高速フーリエ変換処理方法に関する。
【背景技術】
【０００２】
本技術分野の背景技術として、例えば、特許文献１がある。該公報の要約には、課題として、「ＦＦＴを少ないゲート数で実現するアーキテクチャ。」とあり、解決手段として、「バタフライ演算ステージをシーケンス制御回路，入力切り替え回路および順序整列回路を用いることにより１ステージ分のバタフライ演算回路のみで実現する。メモリを配置したことにより、１つの乗算器と３つの加算器を用いて８クロックでバタフライ演算を行う。」と記載されている。
また、本技術分野の背景技術として、例えば、特許文献２がある。該公報の要約には、目的として、「高速フーリエ変換処理におけるバタフライ演算に関し、ハードウェア量が少なくかつ処理時間が短いバタフライ演算方式を提供することを目的とする。」とあり、構成として、「バタフライ演算における乗算後の正規化を省略するように構成される。」と記載されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００２−１１７０１５号公報
【特許文献２】特開平５−４０７７７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
特許文献１の方法では、「１ステージ分のバタフライ演算回路のみで実現する」とあるが、このように、FFTにおけるLog2(N)（NはFFTの処理信号数）回のバタフライ演算ステージを、１ステージ分のバタフライ演算回路を用意して行う方法では、処理する信号数が大きくなると1ステージ分のバタフライ演算回路の規模が大きくなってしまう問題があった。
また、特許文献２は、「ハードウェア量が少なくかつ処理時間が短いバタフライ演算方式を提供することを目的」としているが、特許文献１と同様に、処理する信号数が増加するとハードウェア量が大幅に増加するという問題があった。
【課題を解決するための手段】
【０００５】
上記課題を解決するため、本発明ではバタフライ演算回路を1ステージ分用意せず、一つのバタフライ演算回路を繰り返し使用して演算を行い、中間演算データをRAMに保持する方法を用いる。この時、一般的なFFTのシグナルフローグラフに沿って繰り返し演算をすると、演算結果数に対してRAMリード回数が2倍の回数となり処理時間が長くなる。そこで、本発明ではRAMからリードした中間演算データを2つの演算にわたって利用できるように演算順序を並び替えることで、RAMリード回数を削減、処理時間を短縮する。
【０００６】
また、繰り返し演算時には、中間演算データをRAMにライト・リードする必要が生じるが、FFTのシグナルフローグラフに沿って演算を行う場合、リードするRAMアドレスの順番はFFT演算のステージごとに異なり、アドレス生成回路はステージごとに異なった順番のアドレスを生成する必要が生じ、回路構成が複雑、大規模化する。本発明では、FFT演算の各ステージにおいて、中間演算データをRAMからリードする際のアドレスの順番が同じとなるよう、演算順序の並び替えを行う。これにより、FFT演算のステージに関係なく同じ順番のアドレスを生成する構成で済むようになる。また、このような構成をとることで、FFTの処理信号点数が増加した場合の回路規模増加を抑えることができ、単純でゲート規模の小さなアドレス生成回路とすることができる。
【発明の効果】
【０００７】
繰り返し演算順序の並び替えによりRAMのリード回数をおよそ半分に削減でき、処理時間が短縮できる。また、RAMから中間演算データをリードするアドレスの順番を共通化することにより、ステージ数と同数必要だったリードアドレスのパターンが一つで済み、アドレス生成回路の構成を単純化でき、ゲート規模が削減できる。
【図面の簡単な説明】
【０００８】
【図１】第１の実施例における高速フーリエ変換装置のブロック構成図である。
【図２】全体制御部の状態マシンの状態定義を示した図である。
【図３】信号切り替え部の動作を示した図である。
【図４】8点FFTのシグナルフローグラフを示した図である。
【図５】入力データをRAM-Aに格納した様子を示した図である。
【図６】FFT演算ステージ1を終えた後のRAM-Bの様子を示した図である。
【図７】FFT演算ステージ2をシグナルフローグラフの順で行った場合のRAMのリードと結果の関係を示した図である。
【図８】FFT演算ステージ2の演算順序入れ替えによるリード回数削減を示した図である。
【図９】FFT演算ステージ1を演算順序入れ替えて行った後のRAM-Bの様子を示した図である。
【図１０】FFT演算ステージ2を演算順序入れ替えて行った後のRAM-Aの様子を示した図である。
【図１１】FFT演算ステージ3をシグナルフローグラフの順で行った場合のRAMのリードと結果の関係を示した図である。
【図１２】FFT演算ステージ3の演算順序入れ替えによるリード回数削減を示した図である。
【図１３】FFT演算ステージ3を演算順序入れ替えて行った後のRAM-Bの様子を示した図である。
【図１４】第２の実施例における高速フーリエ変換装置のブロック構成図である。
【発明を実施するための形態】
【０００９】
以下、本発明の実施の形態例について図面により説明する。
【実施例１】
【００１０】
図１は、第１の実施例における高速フーリエ変換装置のブロック構成図である。
図１において、1はFFT装置の制御部である。制御部1の構成要素として、外部装置（図示せず）から入力端子101に供給される処理開始トリガ信号を入力として、回転因子生成制御部3をはじめとした各部を制御する全体制御部2、全体制御部2から全体制御信号を受け、回転因子生成制御信号を生成する回転因子生成制御部3、RAM制御部4がある。さらにRAM制御部4の構成要素として、全体制御信号を入力とし、RAM-A 7、RAM-B 8のリード・ライトアドレスを生成するRAMアドレス生成部5、全体制御信号により、外部装置から入力端子102に供給される入力信号、出力端子103から外部装置へ供給する出力信号、各RAMのリード・ライトデータ、バタフライ入力データ、バタフライ演算データを切り替える信号切り替え部6がある。
【００１１】
また図１において、7、8は演算中間データと入力データを格納する2つのRAM、9は回転因子生成制御信号を受け、バタフライ演算で用いる回転因子を生成する回転因子生成部、10はバタフライ入力データと回転因子に対してバタフライ演算を行うバタフライ演算部である。
制御部1、RAM-A 7、RAM-B 8、回転因子生成部9、バタフライ演算部10によってFFT装置が構成されている。
以上のように構成された高速フーリエ変換装置について、以下、その動作を説明する。説明では例としてFFT演算対象信号8点の場合について記述する。
図４は、信号数8の場合のFFTシグナルフロー図である。図中のＳ０〜Ｓ７は入力信号を表し、Ｇ０〜Ｇ７は出力信号となるFFT演算結果を表している。Ｗ２０、Ｗ２１、Ｗ４０〜Ｗ４３、Ｗ８０〜Ｗ８７はFFT演算の回転因子を表し、実際の値は以下の式で表される。
【００１２】
eはネイピア数、ｊは虚数単位、πは円周率を表す。
【００１３】
図４のＰ０〜Ｔ１、Ｅ０〜Ｈ３は演算の中間結果を表す。また、図中左側部分のＳ０〜Ｓ７からＰ０〜Ｔ１を算出する過程をステージ1、中央部分のＰ０〜Ｔ１からＥ０〜Ｈ３を算出する過程をステージ2、右側部分のＥ０〜Ｈ３からＧ０〜Ｇ７を算出する過程をステージ3と呼ぶこととする。
図４の見方について説明する。図の左側が入力、右側が出力となっており、入力信号が矢印の向きに沿って途中で演算されながら出力される様子を表している。矢印の先が重なっている点は2つの信号を加算することを表している。また、破線の矢印は矢印の先にある回転因子を信号に乗算することを表している。例えば、図４のＰ０はＳ０＋Ｗ２０Ｓ４の演算により求まる値である。
【００１４】
FFTは図４のシグナルフロー図を演算することで実現される。図からわかるようにステージ3の演算はステージ2の結果を利用し、ステージ2の演算はステージ1の結果を利用する。したがって、ステージ1〜3は順を追って演算する必要がある。しかし、各ステージ内の演算は次のステージの演算を始める前に行うことが出来れば順番は問わない。本発明ではこのことを利用し、演算順序を並び替えることで処理時間の削減と回路規模の縮小を図る。
【００１５】
図１において、処理開始トリガ信号を全体制御部2に入力することにより本装置の動作を開始する。全体制御部2は、状態を持ち条件に沿って状態遷移する状態マシンと制御カウンタを内部に持ち、これらにより全体を制御する。
図２は、全体制御部の状態マシンの状態定義を示した図である。以下、この定義に沿って説明する。状態番号0は待機状態であり、処理を行っていない場合はこの状態である。全体制御部2に処理開始トリガ信号が入力されることで、待機状態から状態番号1のデータ入力状態に遷移する。この状態では入力信号を信号切り替え部6経由でRAM-A 7にライトする。入力データ数は8と決まっているため、全体制御部2が持つ制御カウンタの値が一定の値となった時点で入力終了と判断し、状態マシンは状態番号2のFFT演算ステージ1の状態に遷移する。
【００１６】
状態番号2 FFT演算ステージ1では、図４のステージ1の演算を行う。ステージ1の演算をＰ０、Ｐ１、・・・、Ｔ１と上から順に行うことを考える。この時、図１のRAM-A 7からデータＳ０、Ｓ４、Ｓ２、・・・、Ｓ７を順にリードする。
図５は、入力データをRAM-A 7に格納した様子を示した図である。RAM-A 7に図５のようにデータが書き込まれているとすれば、0、4、2、6、1、5、3、7という順番でリードアドレスを生成し、RAM-A 7に送ることでデータをリードできる。このリードアドレスはRAMアドレス生成部5で生成する。RAM-A 7からリードしたデータは、信号切り替え部6経由でバタフライ入力データとしてバタフライ演算部10に送る。また、バタフライ入力データとタイミングを合わせて回転因子をバタフライ演算部10へ送る。この回転因子は回転因子生成制御部3で回転因子部生成制御信号を生成し、回転因子生成部9に送ることで生成する。バタフライ演算部10ではこのバタフライ入力データと回転因子に対してバタフライ演算を順次行い、バタフライ演算データを信号切り替え部6へ送る。
【００１７】
図４における演算結果Ｐ０、Ｐ１、・・・、Ｔ１は図１におけるバタフライ演算データとして、信号切り替え部6経由でRAM-B 8にライトする。格納順は演算順とし、RAMアドレス生成部5はライトアドレス0、1、2、3、4、5、6、7を生成し、RAM-B 8に送る。これによりRAM-B 8に図６のようにステージ1の演算結果が格納される。
図６は、FFT演算ステージ1を終えた後のRAM-B 8の様子を示した図である。このライトアドレスは単純なインクリメントであり、例えばカウンタ等を用いて容易に生成できる。このようにして8個のデータを演算することで、FFT演算ステージ1が完了する。演算データ数は決まっているため、全体制御部1の制御カウンタが一定値になった時点で完了と判断し、図２に示した状態番号3のFFT演算ステージ2へ遷移する。
【００１８】
状態番号3の状態では、図４のステージ2の演算を行う。ステージ2の演算についてもステージ1と同様に図の上方から順に行うことを考える。RAM-B 8からデータをリードし、ステージ1同様バタフライ演算を行い、RAM-A 7へライトする。このときRAM-B 8リードデータと対応するアドレスをタイミングチャート状に表したものを図７に示す。
図７は、FFT演算ステージ2をシグナルフローグラフの順で行った場合のRAMのリードと結果の関係を示した図である。図７の見方について説明する。図の左から右に向かって時間の経過を表している。最上列はRAM-B 8のリードアドレスを表し、その下はリードデータを表し、最下列はバタフライ演算データを表している。矢印はバタフライ演算の入出力関係を表しており、例えば、一番左側はＰ０とＱ０からＥ０を演算することを表している。図７を見てわかるように8個の結果を得るために16回のリードが必要となり、1つのアドレスに対するRAMリードにかかる時間と演算にかかる時間が同じであれば出力は2回に1回となる。バタフライ演算結果個数に対してリード回数が倍となるため処理時間が余計にかかっている。これを改善するため、演算順の並び替えを行う。リードアドレスに着目すると、同じアドレスを2回ずつリードしている。そこで同じアドレスのデータを使う演算を連続して演算するような順番に並べ替える。
【００１９】
図７に対して並べ替えを行った結果を図８に示す。
図８は、FFT演算ステージ2の演算順序入れ替えによるリード回数削減を示した図である。図から明らかなように8個の結果に対して8回のリードで済み、処理時間が半分となる。一方、図８を見るとリードアドレスは0、2、1、3、4、6、5、7の順であり、その並びはステージ1と異なる。RAMアドレス生成部5には、ステージ1用とステージ2用のアドレス生成回路がそれぞれ必要となり回路規模が増大する。そこで、このリードアドレスの並びを同じにするため、図４に示すステージ1のＱ０とＲ０、Ｑ１とＲ１の演算順序を入れ替え、Ｐ０、Ｐ１、Ｒ０、Ｒ１、Ｑ０、Ｑ１、Ｔ０、Ｔ１の順に計算する。これによりステージ1のリードアドレスは0、4、1、5、2、6、3、7となり、RAM-B 8へのデータ格納順は図９のように変わる。
【００２０】
図９は、FFT演算ステージ1を演算順序入れ替えて行った後のRAM-B 8の様子を示した図である。ステージ1でのRAM-B 8へのデータ格納順が変わるため、ステージ2のリードアドレスも変わり、0、4、1、5、2、6、3、7となる。これはステージ1と同じであり、RAMアドレス生成部5はステージ1と2で同じアドレスを生成すればよく、アドレス生成回路の共通化が図られる。このようにして、ステージ2の演算を行うと、演算結果は図１０のようにRAM-A 7へ格納される。
図１０は、FFT演算ステージ2を演算順序入れ替えて行った後のRAM-A 7の様子を示した図である。
【００２１】
このようにFFT演算ステージ2の処理を行い、状態番号2の場合と同様に制御カウンタによって状態番号4のFFT演算ステージ3へ遷移する。
状態番号4の状態では、図４に示すステージ3の演算を行う。状態番号2の場合と同様にRAM-A 7からデータをリードし、バタフライ演算を行い、RAM-B 8へライトする処理を行う。
図１１は、FFT演算ステージ3をシグナルフローグラフの順で行った場合のRAMのリードと結果の関係を示した図である。ステージ3の演算についてもステージ1、2と同様に図４の上側から演算することを考えると、図１１に示すようにステージ2同様16回のリードが発生する。そのため、ステージ2同様に並び替えを行う。
図１２は、FFT演算ステージ3の演算順序入れ替えによるリード回数削減を示した図である。前記並び替えにより図１２に示すように、リード回数8回とし処理時間の削減を図る。さらに、図１２ではリードアドレスが0、4、2、6、1、5、3、7となっており、ステージ1、2の0、4、1、5、2、6、3、7と異なっている。そこでステージ3についてもリードアドレスを共通化するため、Ｇ１とＧ２、Ｇ５とＧ６の計算順序を入れ替え、Ｇ０、Ｇ４、Ｇ２、Ｇ６、Ｇ１、Ｇ５、Ｇ３、Ｇ７の順で計算するようにする。この計算順序の入れ替えにより、ステージ3のリードアドレスが0、4、1、5、2、6、3、7となりステージ1、2と同一になる。
図１３は、FFT演算ステージ3を演算順序入れ替えて行った後のRAM-B 8の様子を示した図である。前記したようにしてステージ3の演算を行うと、演算結果は図１３のようにRAM-B 8へ格納される。状態番号2の場合と同様に制御カウンタによって、図２に示す状態番号5のデータ出力へ遷移する。
【００２２】
状態番号5の状態では、FFT演算結果を出力する。RAM-B 8からデータをリードし、信号切り替え部6経由で出力信号とする。出力データ数は決まっているため、全体制御部2が持つ制御カウンタの値によってデータ出力終了を判断し、状態番号0の待機状態に遷移する。これにより本装置の一連の動作が完了する。
回転因子生成制御部3は全体制御部2から全体制御信号を受け、回転因子生成部制御信号を生成する。回転因子生成部制御信号生成部3は、例えば、全体制御部2から前述の状態番号と制御カウンタの値を受け、回転因子生成部制御信号を生成するデコーダにより構成する。
【００２３】
回転因子生成部9は回転因子生成制御部3から回転因子生成部制御信号を受け、バタフライ演算に使用する回転因子を生成し、バタフライ演算部10へ送る。回転因子生成部9は例えばROM(Read Only Memory)とし、アドレスとして回転因子生成部制御信号をうけ、ROMデータとした回転因子の値を出力する構成とする。
バタフライ演算部10は回転因子生成部9からの回転因子と、信号切り替え部6からのバタフライ入力データを用いてFFT演算におけるバタフライ演算を行い、バタフライ演算データとして信号切り替え部6へ送られる。
この演算は複素数の乗算と加算により構成する。回転因子をW=X+Yi、バタフライ入力データとして、P1=A+Bi、P2=C+Di、バタフライ演算データをQ=E+Fiとする。ここでiは虚数単位である。このとき、バタフライ演算部10では以下に示す演算を行う。
【００２４】
Q=P1×W+P2
複素数演算であるため実際の演算は以下に示す内容となる。
E=A×X-B×Y+C(実部)
F=A×Y+B×X+D(虚部)
信号切り替え部6は全体制御部2からの全体制御信号により、入力信号、出力信号、RAM-A 7、RAM-B 8のリード、ライトデータ、バタフライ入力データ、バタフライ演算データを切り替える。
【００２５】
例えば、全体制御部2から全体制御信号として前述の状態番号を受け、図３に示す入出力関係になるように切り替えを行う構成とする。
図３は、信号切り替え部6の動作を示した図である。
RAMアドレス生成部5は全体制御部2から全体制御信号を受け、RAMアドレスAとRAMアドレスBを生成し、RAM-A 7とRAM-B 8へ送る。
RAMアドレス生成部5は、例えば全体制御部2から全体制御信号を受け、アドレスを生成するデコーダにより構成する。この時、前述の並び替えによりFFT演算のステージ1〜3で生成するアドレスが共通化できるため、デコーダの論理が単純化でき回路規模縮小が図られる。
このような構成により、小規模な回路で処理時間を抑えつつFFT演算を実現する。
【実施例２】
【００２６】
図１４は、第２の実施例における高速フーリエ変換装置のブロック構成図である。実施例１に示す構成に対し、乗算係数生成制御部11、乗算係数生成部12、乗算処理部13を追加した点が特徴となり、そのほかの特徴は同様である。
乗算処理部13は乗算係数生成部12からの乗算係数と入力信号を乗算し乗算後信号として信号切り替え部6に送る。乗算係数生成部12は乗算係数生成制御部11からの乗算係数生成部制御信号を入力とし、乗算係数を生成し、乗算処理部13に送る。乗算係数生成部12の構成として、例えばROMによる構成とし、入力としてアドレス、ROM値としてハニング窓関数（0.5−0.5cos2πx、ただしxは0〜1の値）の値を出力するものとする。乗算係数生成制御部11は全体制御部2からの全体制御信号を受け、入力信号に合わせたタイミングで乗算係数を生成できるように乗算係数生成部制御信号を生成し、乗算係数生成部12に送る。
【００２７】
乗算係数生成制御部11の構成として、例えば、実施例１で述べた状態番号と制御カウンタの値を受け、図２に示す状態番号1データ入力の状態のとき、前述の乗算係数生成部12のROMアドレスを生成するようなデコーダとする。乗算係数生成部12で乗算係数としてハニング窓関数値を生成し、乗算処理部13で入力信号と乗算する構成とすれば、入力信号に対してハニング窓関数処理を施すことが出来、本装置を用いてハニング窓関数処理を行ったFFT演算結果を得ることが出来る。このことより、高速フーリエ変換で区間両端が不連続となることにより生じる高調波成分に対し、FFT演算結果がばらつくことを軽減する。また、乗算係数はハニング窓関数に限らず、他の窓関数にすることも出来る。
【符号の説明】
【００２８】
１：制御部、２：全体制御部、３：回転因子生成制御部、４：RAM制御部、５：RAMアドレス生成部、６：信号切り替え部、７：RAM-A、８：RAM-B、９：回転因子生成部、１０：バタフライ演算部、１１：乗算係数生成制御部、１２：乗算係数生成部、１３：乗算処理部。
【技術分野】
【０００１】
本発明は、高速フーリエ変換装置、高速フーリエ変換処理方法に関する。
【背景技術】
【０００２】
本技術分野の背景技術として、例えば、特許文献１がある。該公報の要約には、課題として、「ＦＦＴを少ないゲート数で実現するアーキテクチャ。」とあり、解決手段として、「バタフライ演算ステージをシーケンス制御回路，入力切り替え回路および順序整列回路を用いることにより１ステージ分のバタフライ演算回路のみで実現する。メモリを配置したことにより、１つの乗算器と３つの加算器を用いて８クロックでバタフライ演算を行う。」と記載されている。
また、本技術分野の背景技術として、例えば、特許文献２がある。該公報の要約には、目的として、「高速フーリエ変換処理におけるバタフライ演算に関し、ハードウェア量が少なくかつ処理時間が短いバタフライ演算方式を提供することを目的とする。」とあり、構成として、「バタフライ演算における乗算後の正規化を省略するように構成される。」と記載されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００２−１１７０１５号公報
【特許文献２】特開平５−４０７７７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
特許文献１の方法では、「１ステージ分のバタフライ演算回路のみで実現する」とあるが、このように、FFTにおけるLog2(N)（NはFFTの処理信号数）回のバタフライ演算ステージを、１ステージ分のバタフライ演算回路を用意して行う方法では、処理する信号数が大きくなると1ステージ分のバタフライ演算回路の規模が大きくなってしまう問題があった。
また、特許文献２は、「ハードウェア量が少なくかつ処理時間が短いバタフライ演算方式を提供することを目的」としているが、特許文献１と同様に、処理する信号数が増加するとハードウェア量が大幅に増加するという問題があった。
【課題を解決するための手段】
【０００５】
上記課題を解決するため、本発明ではバタフライ演算回路を1ステージ分用意せず、一つのバタフライ演算回路を繰り返し使用して演算を行い、中間演算データをRAMに保持する方法を用いる。この時、一般的なFFTのシグナルフローグラフに沿って繰り返し演算をすると、演算結果数に対してRAMリード回数が2倍の回数となり処理時間が長くなる。そこで、本発明ではRAMからリードした中間演算データを2つの演算にわたって利用できるように演算順序を並び替えることで、RAMリード回数を削減、処理時間を短縮する。
【０００６】
また、繰り返し演算時には、中間演算データをRAMにライト・リードする必要が生じるが、FFTのシグナルフローグラフに沿って演算を行う場合、リードするRAMアドレスの順番はFFT演算のステージごとに異なり、アドレス生成回路はステージごとに異なった順番のアドレスを生成する必要が生じ、回路構成が複雑、大規模化する。本発明では、FFT演算の各ステージにおいて、中間演算データをRAMからリードする際のアドレスの順番が同じとなるよう、演算順序の並び替えを行う。これにより、FFT演算のステージに関係なく同じ順番のアドレスを生成する構成で済むようになる。また、このような構成をとることで、FFTの処理信号点数が増加した場合の回路規模増加を抑えることができ、単純でゲート規模の小さなアドレス生成回路とすることができる。
【発明の効果】
【０００７】
繰り返し演算順序の並び替えによりRAMのリード回数をおよそ半分に削減でき、処理時間が短縮できる。また、RAMから中間演算データをリードするアドレスの順番を共通化することにより、ステージ数と同数必要だったリードアドレスのパターンが一つで済み、アドレス生成回路の構成を単純化でき、ゲート規模が削減できる。
【図面の簡単な説明】
【０００８】
【図１】第１の実施例における高速フーリエ変換装置のブロック構成図である。
【図２】全体制御部の状態マシンの状態定義を示した図である。
【図３】信号切り替え部の動作を示した図である。
【図４】8点FFTのシグナルフローグラフを示した図である。
【図５】入力データをRAM-Aに格納した様子を示した図である。
【図６】FFT演算ステージ1を終えた後のRAM-Bの様子を示した図である。
【図７】FFT演算ステージ2をシグナルフローグラフの順で行った場合のRAMのリードと結果の関係を示した図である。
【図８】FFT演算ステージ2の演算順序入れ替えによるリード回数削減を示した図である。
【図９】FFT演算ステージ1を演算順序入れ替えて行った後のRAM-Bの様子を示した図である。
【図１０】FFT演算ステージ2を演算順序入れ替えて行った後のRAM-Aの様子を示した図である。
【図１１】FFT演算ステージ3をシグナルフローグラフの順で行った場合のRAMのリードと結果の関係を示した図である。
【図１２】FFT演算ステージ3の演算順序入れ替えによるリード回数削減を示した図である。
【図１３】FFT演算ステージ3を演算順序入れ替えて行った後のRAM-Bの様子を示した図である。
【図１４】第２の実施例における高速フーリエ変換装置のブロック構成図である。
【発明を実施するための形態】
【０００９】
以下、本発明の実施の形態例について図面により説明する。
【実施例１】
【００１０】
図１は、第１の実施例における高速フーリエ変換装置のブロック構成図である。
図１において、1はFFT装置の制御部である。制御部1の構成要素として、外部装置（図示せず）から入力端子101に供給される処理開始トリガ信号を入力として、回転因子生成制御部3をはじめとした各部を制御する全体制御部2、全体制御部2から全体制御信号を受け、回転因子生成制御信号を生成する回転因子生成制御部3、RAM制御部4がある。さらにRAM制御部4の構成要素として、全体制御信号を入力とし、RAM-A 7、RAM-B 8のリード・ライトアドレスを生成するRAMアドレス生成部5、全体制御信号により、外部装置から入力端子102に供給される入力信号、出力端子103から外部装置へ供給する出力信号、各RAMのリード・ライトデータ、バタフライ入力データ、バタフライ演算データを切り替える信号切り替え部6がある。
【００１１】
また図１において、7、8は演算中間データと入力データを格納する2つのRAM、9は回転因子生成制御信号を受け、バタフライ演算で用いる回転因子を生成する回転因子生成部、10はバタフライ入力データと回転因子に対してバタフライ演算を行うバタフライ演算部である。
制御部1、RAM-A 7、RAM-B 8、回転因子生成部9、バタフライ演算部10によってFFT装置が構成されている。
以上のように構成された高速フーリエ変換装置について、以下、その動作を説明する。説明では例としてFFT演算対象信号8点の場合について記述する。
図４は、信号数8の場合のFFTシグナルフロー図である。図中のＳ０〜Ｓ７は入力信号を表し、Ｇ０〜Ｇ７は出力信号となるFFT演算結果を表している。Ｗ２０、Ｗ２１、Ｗ４０〜Ｗ４３、Ｗ８０〜Ｗ８７はFFT演算の回転因子を表し、実際の値は以下の式で表される。
【００１２】
eはネイピア数、ｊは虚数単位、πは円周率を表す。
【００１３】
図４のＰ０〜Ｔ１、Ｅ０〜Ｈ３は演算の中間結果を表す。また、図中左側部分のＳ０〜Ｓ７からＰ０〜Ｔ１を算出する過程をステージ1、中央部分のＰ０〜Ｔ１からＥ０〜Ｈ３を算出する過程をステージ2、右側部分のＥ０〜Ｈ３からＧ０〜Ｇ７を算出する過程をステージ3と呼ぶこととする。
図４の見方について説明する。図の左側が入力、右側が出力となっており、入力信号が矢印の向きに沿って途中で演算されながら出力される様子を表している。矢印の先が重なっている点は2つの信号を加算することを表している。また、破線の矢印は矢印の先にある回転因子を信号に乗算することを表している。例えば、図４のＰ０はＳ０＋Ｗ２０Ｓ４の演算により求まる値である。
【００１４】
FFTは図４のシグナルフロー図を演算することで実現される。図からわかるようにステージ3の演算はステージ2の結果を利用し、ステージ2の演算はステージ1の結果を利用する。したがって、ステージ1〜3は順を追って演算する必要がある。しかし、各ステージ内の演算は次のステージの演算を始める前に行うことが出来れば順番は問わない。本発明ではこのことを利用し、演算順序を並び替えることで処理時間の削減と回路規模の縮小を図る。
【００１５】
図１において、処理開始トリガ信号を全体制御部2に入力することにより本装置の動作を開始する。全体制御部2は、状態を持ち条件に沿って状態遷移する状態マシンと制御カウンタを内部に持ち、これらにより全体を制御する。
図２は、全体制御部の状態マシンの状態定義を示した図である。以下、この定義に沿って説明する。状態番号0は待機状態であり、処理を行っていない場合はこの状態である。全体制御部2に処理開始トリガ信号が入力されることで、待機状態から状態番号1のデータ入力状態に遷移する。この状態では入力信号を信号切り替え部6経由でRAM-A 7にライトする。入力データ数は8と決まっているため、全体制御部2が持つ制御カウンタの値が一定の値となった時点で入力終了と判断し、状態マシンは状態番号2のFFT演算ステージ1の状態に遷移する。
【００１６】
状態番号2 FFT演算ステージ1では、図４のステージ1の演算を行う。ステージ1の演算をＰ０、Ｐ１、・・・、Ｔ１と上から順に行うことを考える。この時、図１のRAM-A 7からデータＳ０、Ｓ４、Ｓ２、・・・、Ｓ７を順にリードする。
図５は、入力データをRAM-A 7に格納した様子を示した図である。RAM-A 7に図５のようにデータが書き込まれているとすれば、0、4、2、6、1、5、3、7という順番でリードアドレスを生成し、RAM-A 7に送ることでデータをリードできる。このリードアドレスはRAMアドレス生成部5で生成する。RAM-A 7からリードしたデータは、信号切り替え部6経由でバタフライ入力データとしてバタフライ演算部10に送る。また、バタフライ入力データとタイミングを合わせて回転因子をバタフライ演算部10へ送る。この回転因子は回転因子生成制御部3で回転因子部生成制御信号を生成し、回転因子生成部9に送ることで生成する。バタフライ演算部10ではこのバタフライ入力データと回転因子に対してバタフライ演算を順次行い、バタフライ演算データを信号切り替え部6へ送る。
【００１７】
図４における演算結果Ｐ０、Ｐ１、・・・、Ｔ１は図１におけるバタフライ演算データとして、信号切り替え部6経由でRAM-B 8にライトする。格納順は演算順とし、RAMアドレス生成部5はライトアドレス0、1、2、3、4、5、6、7を生成し、RAM-B 8に送る。これによりRAM-B 8に図６のようにステージ1の演算結果が格納される。
図６は、FFT演算ステージ1を終えた後のRAM-B 8の様子を示した図である。このライトアドレスは単純なインクリメントであり、例えばカウンタ等を用いて容易に生成できる。このようにして8個のデータを演算することで、FFT演算ステージ1が完了する。演算データ数は決まっているため、全体制御部1の制御カウンタが一定値になった時点で完了と判断し、図２に示した状態番号3のFFT演算ステージ2へ遷移する。
【００１８】
状態番号3の状態では、図４のステージ2の演算を行う。ステージ2の演算についてもステージ1と同様に図の上方から順に行うことを考える。RAM-B 8からデータをリードし、ステージ1同様バタフライ演算を行い、RAM-A 7へライトする。このときRAM-B 8リードデータと対応するアドレスをタイミングチャート状に表したものを図７に示す。
図７は、FFT演算ステージ2をシグナルフローグラフの順で行った場合のRAMのリードと結果の関係を示した図である。図７の見方について説明する。図の左から右に向かって時間の経過を表している。最上列はRAM-B 8のリードアドレスを表し、その下はリードデータを表し、最下列はバタフライ演算データを表している。矢印はバタフライ演算の入出力関係を表しており、例えば、一番左側はＰ０とＱ０からＥ０を演算することを表している。図７を見てわかるように8個の結果を得るために16回のリードが必要となり、1つのアドレスに対するRAMリードにかかる時間と演算にかかる時間が同じであれば出力は2回に1回となる。バタフライ演算結果個数に対してリード回数が倍となるため処理時間が余計にかかっている。これを改善するため、演算順の並び替えを行う。リードアドレスに着目すると、同じアドレスを2回ずつリードしている。そこで同じアドレスのデータを使う演算を連続して演算するような順番に並べ替える。
【００１９】
図７に対して並べ替えを行った結果を図８に示す。
図８は、FFT演算ステージ2の演算順序入れ替えによるリード回数削減を示した図である。図から明らかなように8個の結果に対して8回のリードで済み、処理時間が半分となる。一方、図８を見るとリードアドレスは0、2、1、3、4、6、5、7の順であり、その並びはステージ1と異なる。RAMアドレス生成部5には、ステージ1用とステージ2用のアドレス生成回路がそれぞれ必要となり回路規模が増大する。そこで、このリードアドレスの並びを同じにするため、図４に示すステージ1のＱ０とＲ０、Ｑ１とＲ１の演算順序を入れ替え、Ｐ０、Ｐ１、Ｒ０、Ｒ１、Ｑ０、Ｑ１、Ｔ０、Ｔ１の順に計算する。これによりステージ1のリードアドレスは0、4、1、5、2、6、3、7となり、RAM-B 8へのデータ格納順は図９のように変わる。
【００２０】
図９は、FFT演算ステージ1を演算順序入れ替えて行った後のRAM-B 8の様子を示した図である。ステージ1でのRAM-B 8へのデータ格納順が変わるため、ステージ2のリードアドレスも変わり、0、4、1、5、2、6、3、7となる。これはステージ1と同じであり、RAMアドレス生成部5はステージ1と2で同じアドレスを生成すればよく、アドレス生成回路の共通化が図られる。このようにして、ステージ2の演算を行うと、演算結果は図１０のようにRAM-A 7へ格納される。
図１０は、FFT演算ステージ2を演算順序入れ替えて行った後のRAM-A 7の様子を示した図である。
【００２１】
このようにFFT演算ステージ2の処理を行い、状態番号2の場合と同様に制御カウンタによって状態番号4のFFT演算ステージ3へ遷移する。
状態番号4の状態では、図４に示すステージ3の演算を行う。状態番号2の場合と同様にRAM-A 7からデータをリードし、バタフライ演算を行い、RAM-B 8へライトする処理を行う。
図１１は、FFT演算ステージ3をシグナルフローグラフの順で行った場合のRAMのリードと結果の関係を示した図である。ステージ3の演算についてもステージ1、2と同様に図４の上側から演算することを考えると、図１１に示すようにステージ2同様16回のリードが発生する。そのため、ステージ2同様に並び替えを行う。
図１２は、FFT演算ステージ3の演算順序入れ替えによるリード回数削減を示した図である。前記並び替えにより図１２に示すように、リード回数8回とし処理時間の削減を図る。さらに、図１２ではリードアドレスが0、4、2、6、1、5、3、7となっており、ステージ1、2の0、4、1、5、2、6、3、7と異なっている。そこでステージ3についてもリードアドレスを共通化するため、Ｇ１とＧ２、Ｇ５とＧ６の計算順序を入れ替え、Ｇ０、Ｇ４、Ｇ２、Ｇ６、Ｇ１、Ｇ５、Ｇ３、Ｇ７の順で計算するようにする。この計算順序の入れ替えにより、ステージ3のリードアドレスが0、4、1、5、2、6、3、7となりステージ1、2と同一になる。
図１３は、FFT演算ステージ3を演算順序入れ替えて行った後のRAM-B 8の様子を示した図である。前記したようにしてステージ3の演算を行うと、演算結果は図１３のようにRAM-B 8へ格納される。状態番号2の場合と同様に制御カウンタによって、図２に示す状態番号5のデータ出力へ遷移する。
【００２２】
状態番号5の状態では、FFT演算結果を出力する。RAM-B 8からデータをリードし、信号切り替え部6経由で出力信号とする。出力データ数は決まっているため、全体制御部2が持つ制御カウンタの値によってデータ出力終了を判断し、状態番号0の待機状態に遷移する。これにより本装置の一連の動作が完了する。
回転因子生成制御部3は全体制御部2から全体制御信号を受け、回転因子生成部制御信号を生成する。回転因子生成部制御信号生成部3は、例えば、全体制御部2から前述の状態番号と制御カウンタの値を受け、回転因子生成部制御信号を生成するデコーダにより構成する。
【００２３】
回転因子生成部9は回転因子生成制御部3から回転因子生成部制御信号を受け、バタフライ演算に使用する回転因子を生成し、バタフライ演算部10へ送る。回転因子生成部9は例えばROM(Read Only Memory)とし、アドレスとして回転因子生成部制御信号をうけ、ROMデータとした回転因子の値を出力する構成とする。
バタフライ演算部10は回転因子生成部9からの回転因子と、信号切り替え部6からのバタフライ入力データを用いてFFT演算におけるバタフライ演算を行い、バタフライ演算データとして信号切り替え部6へ送られる。
この演算は複素数の乗算と加算により構成する。回転因子をW=X+Yi、バタフライ入力データとして、P1=A+Bi、P2=C+Di、バタフライ演算データをQ=E+Fiとする。ここでiは虚数単位である。このとき、バタフライ演算部10では以下に示す演算を行う。
【００２４】
Q=P1×W+P2
複素数演算であるため実際の演算は以下に示す内容となる。
E=A×X-B×Y+C(実部)
F=A×Y+B×X+D(虚部)
信号切り替え部6は全体制御部2からの全体制御信号により、入力信号、出力信号、RAM-A 7、RAM-B 8のリード、ライトデータ、バタフライ入力データ、バタフライ演算データを切り替える。
【００２５】
例えば、全体制御部2から全体制御信号として前述の状態番号を受け、図３に示す入出力関係になるように切り替えを行う構成とする。
図３は、信号切り替え部6の動作を示した図である。
RAMアドレス生成部5は全体制御部2から全体制御信号を受け、RAMアドレスAとRAMアドレスBを生成し、RAM-A 7とRAM-B 8へ送る。
RAMアドレス生成部5は、例えば全体制御部2から全体制御信号を受け、アドレスを生成するデコーダにより構成する。この時、前述の並び替えによりFFT演算のステージ1〜3で生成するアドレスが共通化できるため、デコーダの論理が単純化でき回路規模縮小が図られる。
このような構成により、小規模な回路で処理時間を抑えつつFFT演算を実現する。
【実施例２】
【００２６】
図１４は、第２の実施例における高速フーリエ変換装置のブロック構成図である。実施例１に示す構成に対し、乗算係数生成制御部11、乗算係数生成部12、乗算処理部13を追加した点が特徴となり、そのほかの特徴は同様である。
乗算処理部13は乗算係数生成部12からの乗算係数と入力信号を乗算し乗算後信号として信号切り替え部6に送る。乗算係数生成部12は乗算係数生成制御部11からの乗算係数生成部制御信号を入力とし、乗算係数を生成し、乗算処理部13に送る。乗算係数生成部12の構成として、例えばROMによる構成とし、入力としてアドレス、ROM値としてハニング窓関数（0.5−0.5cos2πx、ただしxは0〜1の値）の値を出力するものとする。乗算係数生成制御部11は全体制御部2からの全体制御信号を受け、入力信号に合わせたタイミングで乗算係数を生成できるように乗算係数生成部制御信号を生成し、乗算係数生成部12に送る。
【００２７】
乗算係数生成制御部11の構成として、例えば、実施例１で述べた状態番号と制御カウンタの値を受け、図２に示す状態番号1データ入力の状態のとき、前述の乗算係数生成部12のROMアドレスを生成するようなデコーダとする。乗算係数生成部12で乗算係数としてハニング窓関数値を生成し、乗算処理部13で入力信号と乗算する構成とすれば、入力信号に対してハニング窓関数処理を施すことが出来、本装置を用いてハニング窓関数処理を行ったFFT演算結果を得ることが出来る。このことより、高速フーリエ変換で区間両端が不連続となることにより生じる高調波成分に対し、FFT演算結果がばらつくことを軽減する。また、乗算係数はハニング窓関数に限らず、他の窓関数にすることも出来る。
【符号の説明】
【００２８】
１：制御部、２：全体制御部、３：回転因子生成制御部、４：RAM制御部、５：RAMアドレス生成部、６：信号切り替え部、７：RAM-A、８：RAM-B、９：回転因子生成部、１０：バタフライ演算部、１１：乗算係数生成制御部、１２：乗算係数生成部、１３：乗算処理部。
【特許請求の範囲】
【請求項１】
高速フーリエ変換(FFT)装置において、
バタフライ演算を行うバタフライ演算部と、
前記バタフライ演算の際のデータを保持するRAM(Random Access Memory)と、
前記バタフライ演算部が前記RAMに前記データを書込み／読取りする際の前記RAMにおけるアドレス情報を生成するアドレス生成部とを備え、
前記バタフライ演算部は、前記RAMに中間データを書込み／読取りながら複数のステージにわたりバタフライ演算をしてFFT演算を行い、
前記アドレス生成部は、前記バタフライ演算部が前記RAMから前記データを読取る際に、前記バタフライ演算を行う複数のステージにおいて、時間軸上の順番が一致した読取りアドレスを生成する
ことを特徴とする高速フーリエ変換装置。
【請求項２】
請求項１に記載の高速フーリエ変換装置おいて、
前記演算を行うために入力された入力信号に対して、高速フーリエ変換により変換された区間の両端が不連続となることで生じる高調波成分によるFFT変換結果のばらつきを軽減するハニング窓関数を乗算する乗算部
を備えたことを特徴とする高速フーリエ変換装置。
【請求項１】
高速フーリエ変換(FFT)装置において、
バタフライ演算を行うバタフライ演算部と、
前記バタフライ演算の際のデータを保持するRAM(Random Access Memory)と、
前記バタフライ演算部が前記RAMに前記データを書込み／読取りする際の前記RAMにおけるアドレス情報を生成するアドレス生成部とを備え、
前記バタフライ演算部は、前記RAMに中間データを書込み／読取りながら複数のステージにわたりバタフライ演算をしてFFT演算を行い、
前記アドレス生成部は、前記バタフライ演算部が前記RAMから前記データを読取る際に、前記バタフライ演算を行う複数のステージにおいて、時間軸上の順番が一致した読取りアドレスを生成する
ことを特徴とする高速フーリエ変換装置。
【請求項２】
請求項１に記載の高速フーリエ変換装置おいて、
前記演算を行うために入力された入力信号に対して、高速フーリエ変換により変換された区間の両端が不連続となることで生じる高調波成分によるFFT変換結果のばらつきを軽減するハニング窓関数を乗算する乗算部
を備えたことを特徴とする高速フーリエ変換装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【公開番号】特開２０１３−２５４６８（Ｐ２０１３−２５４６８Ａ）
【公開日】平成２５年２月４日（２０１３．２．４）
【国際特許分類】
【出願番号】特願２０１１−１５８０１１（Ｐ２０１１−１５８０１１）
【出願日】平成２３年７月１９日（２０１１．７．１９）
【出願人】（０００２３３１３６）株式会社日立アドバンストデジタル (76)
【出願人】（５０４１５７０２４）国立大学法人東北大学 (2,297)
【Ｆターム（参考）】
【公開日】平成２５年２月４日（２０１３．２．４）
【国際特許分類】
【出願日】平成２３年７月１９日（２０１１．７．１９）
【出願人】（０００２３３１３６）株式会社日立アドバンストデジタル (76)
【出願人】（５０４１５７０２４）国立大学法人東北大学 (2,297)
【Ｆターム（参考）】
[ Back to top ]