ディジタル信号処理 Digital Signal Processing 第１７講 ＦＦＴ Fast Fourier transform 高速フーリエ変換

高速フーリエ変換 高速フーリエ変換（ Fast Fourier Transform, FFT）とは、離散フーリエ変換 (Discrete Fourier Transform, DFT) を計算機上で高速に計算するアルゴリズム。 　　逆変換をIFFT (Inverse FFT) という。 高速フーリエ変換といえば一般的には1965年、ジェイムズ・クーリー (J. W. Cooley) とジョン・テューキー (J. W. Tukey) が発見したとされ，Cooley-Tukey型FFTアルゴリズムを呼ぶ。しかし、1805年ごろにガウスが同様のアルゴリズムを独自に発見していたといわれている。

信州大学工学部・井澤裕司先生 URL: http://laputa. cs. shinshu-u. ac 信州大学工学部・井澤裕司先生 URL: http://laputa.cs.shinshu-u.ac.jp 　　/~yizawa/InfSys1/basic/chap7 　　/index.htm わかりやすい記事が載っています 先頭ページは 　　　http://laputa.cs.shinshu-u.ac.jp 　　　　　/~yizawa/InfSys1/basic 　　　　　/index.htm

原理の簡単な説明(Wikipedia) 離散フーリエ係数は、exp( -2 π ｊ / N ) を使うと、次のように表せる。 3．2式に当る 記号はテキストと違う 例えば、N = 4 のとき、離散フーリエ係数は行列を用いて表現すると

2行目と3行目行の入れ替え（係数列はこうなる） 入力列を添字の偶奇で分けて、以下のように変形する。 2行目と3行目行の入れ替え（係数列はこうなる） すると、サイズ2のFFTの演算結果を用いて表現でき、サイズの分割ができる。

また、この分割手順を図にすると蝶のような図になることから、バタフライ演算とも呼ばれる。 バタフライ演算は、計算機上ではビット反転で実現される。DSPの中には、このバタフライ演算のプログラムを容易にするため、ビット反転アドレッシングを備えているものがある。

5.4 高速フーリエ変換 （FFT : Fast Fourier Transform）

5.4.1 基数２のFFT DFTの式

■ビット反転の関係

5.4.2　混合基数FFT

5.4.3　高速フーリエ逆変換

計算の高速化 計算量を減せば早く答が得られる 式をそのまま行うと膨大な計算量になる 計算量を大幅に減少させるアルゴリズムを高速フーリエ変換（fast Fourier transform : FFT ）という 基本的な考え方： 　①　データ数 Ｎ を ２p にする 　②　計算順序を変える ③　偶数番のデータと奇数番のデータ (n=1,2,3,・・・・,N/2-1) x0(n)=x(2n)　　 ・・・偶数番 　　x1(n)=x(2n+1)　・・・奇数番

高速フーリエ変換の計算手数 データの並べ替えは無視する 積和演算の回数は，r個の積和演算をq回行い，さらにこれをp回繰り返すことになる N＝q･r＝２pであるから，Nだけで表すと演算回数＝N･log2N 演算回数比η＝FFT／DFT＝ N･log2N／N2 Nが大きいときFFTの高価は顕著に表れる

高速フーリエ変換のメリット 次の例で考えてみる Ｎ＝８ 鋸歯状波 離散時間信号 x(0)=0,x(1)=1,x(2)=2,x(3)=3, 　x(4)=4,x(5)=5,x(6)=6,x(7)=7　 離散フーリエ変換の式（３．２）式・・標準式 X（ｋ）・・・ｋ＝０～７を求める操作を考える 離散フーリエ変換では

X(k)の計算 X(k)=Σx(n)･exp(-j･2･π･k･n / N)を展開して Ｘ(k)={ｘ(0)･exp(-j･2･π･k･0 / 8) 　+ｘ(1)･exp(-j･2･π･k･１ / 8) 　+ｘ(2)･exp(-j･2･π･k･2 / 8) 　+ｘ(3)･exp(-j･2･π･k･3 / 8) 　+ｘ(4)･exp(-j･2･π･k･4 / 8) 　+ｘ(5)･exp(-j･2･π･k･5 / 8) 　+ｘ(6)･exp(-j･2･π･k･6 / 8) 　+ｘ(7)･exp(-j･2･π･k･7 / 8)} Ｃ言語では，複素計算ができないので， 　　exp(-j2πkn/N)=cos(2πkn/N)-jsin(2πkn/N) 　と実数部，虚数部別々に計算しなければならない

Ｘ(k)にオイラーの公式を当てはめ Ｘ(k)={ｘ(0)･exp(-j2πk0/8)+ｘ(1)･exp(-j2πk１/8)+ｘ(2)･exp(-j2πk2/8) 　+ｘ(3)･exp(-j2πk3/8)+ｘ(4)･exp(-j2πk4/8)+ｘ(5)･exp(-j2πk5/8) 　+ｘ(6)･exp(-j2πk6/8)+ｘ(7)･exp(-j2πk7/8)} 　　= [ｘ(0)･{cos(2πk0/8)-j･sin(2πk0/8)} 　　+ｘ(1)･{cos(2πk1/8)-j･sin(2πk1/8)} 　　+ｘ(2)･{cos(2πk2/8)-j･sin(2πk2/8)} 　　+ｘ(3)･{cos(2πk3/8)-j･sin(2πk3/8)} 　　+ｘ(4)･{cos(2πk4/8)-j･sin(2πk4/8)} 　　+ｘ(5)･{cos(2πk5/8)-j･sin(2πk5/8)} 　　+ｘ(6)･{cos(2πk6/8)-j･sin(2πk6/8)} 　　+ｘ(7)･{cos(2πk7/8)-j･sin(2πk7/8) }]

Ｘ(0)の計算 k=0だから・・・cos(0)=1,sin(0)=0となり， 簡単に計算できて 　簡単に計算できて 　　Ｘ(0)= { 28+j 0 } = + 28.0 + j 0.00 　　|Ｘ(0)|= 28.0 　となる 同様にＸ(1)～Ｘ(7)を求めると

Ｘ(1)～Ｘ(7)を計算すると Ｘ(0)= + 28.0 + j 0.00 |Ｘ(０)|= 28.0

これまでに要した計算回数 x(n)=0の場合もカウントして Ｘ(0)の実部・・・cosをN回，N項の和，1/N倍 Ｘ(0)の虚部・・・sinをN回，N項の和，1/N倍 これをk=0～N-1までＮ回繰り返し計算する 合計 cos を N×Ｎ回 sin を N×Ｎ回 和 を ２×N×Ｎ回 1/N倍 を ２×Ｎ回

ＦＦＴでは N=2p =qr Nが 2p となるようにすると 2分割 → ４分割 → ・・・ すべてのkについて集計すると 2分割　→　４分割　→　・・・ すべてのkについて集計すると cos を (N×N)/2＋N回 sin を (N×N）/2＋N回 和 を (N×N)回 1/2倍 を (２×N)回

計算量（積和演算回数）の比較 N=２pの場合 DFT　:　N2回 FFT　：　N（log2N）/2回 計算回数比＝DFT/FFT

FFTアルゴリズム そのまえにアルゴリズムってなーに algorithm：算法 ある特定の問題を解いたり、課題を解決したりするための計算手順や処理手順のこと。これを図式化したものがフローチャートであり、コンピューターで処理するための具体的な手順を記述したものがプログラムである。イランの数学者・天文学者、アル＝フワーリズミーにちなむ。

再帰性アルゴリズム そのまえに再帰性ってなーに 再帰: recursion ①あるものについて記述する際に、記述しているものそれ自身への参照が、 　　その記述中にあらわれることをいう。定義において、再帰があらわれている 　　ものを再帰的定義という。数学的帰納法との原理的な共通性から、数学で 　　は「帰納」を使うことがある。 ②他にrecurrenceの訳や、reflectionの訳（再帰代名詞、再帰動詞。 ③また、社会学で、対象に対する言及がその対象自体に影響を与えることとして「再帰」が使われることがある。 recursive [形] 1 繰り返し用いられる, 回帰できる. 2 《数》帰納［再帰］的な. 再帰呼出し recursive call リカーシブルコール プログラミング技法の一。コンピュータのプログラムを実行中に、あるルーチンや関数が自分自身を呼び出して実行すること。無限に自分自身を呼び出さないよう、正常に機能させる手続きを必要とする。階乗やフィボナッチ数列の計算などに利用される。

X(q区分,r点データ列)を与えて，q区分のr点DFT列X’を作成する N=qrとする

非再帰性アルゴリズム

質問はありませんか？ 今日はここまで ごきげんよう