ディジタル信号処理 Digital Signal Processing 第17講 FFT 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.jp /~yizawa/InfSys1/basic/chap7 /index.htm • わかりやすい記事が載っています • 先頭ページは http://laputa.cs.shinshu-u.ac.jp /~yizawa/InfSys1/basic /index.htm 原理の簡単な説明(Wikipedia) • 離散フーリエ係数は、exp( -2 π j / N ) を使うと、次のように 表せる。 3.2式に当る 記号はテキスト と違う 例えば、N = 4 のとき、離散フーリエ係数は行列を用いて表現すると 入力列を添字の偶奇で分けて、以下のように変形する。 2行目と3行目 行の入れ替え (係数列はこう なる) すると、サイズ2のFFTの演算結果を用いて表現でき、サイズの分割ができる。 また、この分割手順を図にすると蝶のような図になることから、バタフライ演算と も呼ばれる。 バタフライ演算は、計算機上ではビット反転で実現される。DSPの中には、この バタフライ演算のプログラムを容易にするため、ビット反転アドレッシングを備え ているものがある。 5.4 高速フーリエ変換 (FFT : Fast Fourier Transform) 5.4.1 基数2のFFT DFTの式 ■ビット反転の関係 5.4.2 混合基数FFT 5.4.3 高速フーリエ逆変換 計算の高速化 計算量を減せば早く答が得られる • 式をそのまま行うと膨大な計算量になる • 計算量を大幅に減少させるアルゴリズムを高速フー リエ変換(fast Fourier transform : FFT )という • 基本的な考え方: ① データ数 N を 2p にする ② 計算順序を変える ③ 偶数番のデータと奇数番のデータ (n=1,2,3,・・・・,N/2-1) x0(n)=x(2n) ・・・偶数番 x1(n)=x(2n+1) ・・・奇数番 高速フーリエ変換の計算手数 • データの並べ替えは無視する • 積和演算の回数は,r個の積和演算をq回行い,さら にこれをp回繰り返すことになる • N=q・r=2pであるから,Nだけで表すと演算回数= N・log2N • 演算回数比η=FFT/DFT= N・log2N/N2 • Nが大きいときFFTの高価は顕著に表れる 高速フーリエ変換のメリット 次の例で考えてみる • N=8 • 鋸歯状波 • 離散時間信号 x(0)=0,x(1)=1,x(2)=2,x(3)=3, x(4)=4,x(5)=5,x(6)=6,x(7)=7 • 離散フーリエ変換の式(3.2)式・・標準式 • X(k)・・・k=0~7を求める操作を考える • 離散フーリエ変換では X(k)の計算 • X(k)=Σx(n)・exp(-j・2・π・k・n / N)を展開して • X(k)={x(0)・exp(-j・2・π・k・0 / 8) +x(1)・exp(-j・2・π・k・1 / 8) +x(2)・exp(-j・2・π・k・2 / 8) +x(3)・exp(-j・2・π・k・3 / 8) +x(4)・exp(-j・2・π・k・4 / 8) +x(5)・exp(-j・2・π・k・5 / 8) +x(6)・exp(-j・2・π・k・6 / 8) +x(7)・exp(-j・2・π・k・7 / 8)} • C言語では,複素計算ができないので, exp(-j2πkn/N)=cos(2πkn/N)-jsin(2πkn/N) と実数部,虚数部別々に計算しなければならない X(k)にオイラーの公式を当てはめ X(k)={x(0)・exp(-j2πk0/8)+x(1)・exp(-j2πk1/8)+x(2)・exp(-j2πk2/8) +x(3)・exp(-j2πk3/8)+x(4)・exp(-j2πk4/8)+x(5)・exp(-j2πk5/8) +x(6)・exp(-j2πk6/8)+x(7)・exp(-j2πk7/8)} = [x(0)・{cos(2πk0/8)-j・sin(2πk0/8)} +x(1)・{cos(2πk1/8)-j・sin(2πk1/8)} +x(2)・{cos(2πk2/8)-j・sin(2πk2/8)} +x(3)・{cos(2πk3/8)-j・sin(2πk3/8)} +x(4)・{cos(2πk4/8)-j・sin(2πk4/8)} +x(5)・{cos(2πk5/8)-j・sin(2πk5/8)} +x(6)・{cos(2πk6/8)-j・sin(2πk6/8)} +x(7)・{cos(2πk7/8)-j・sin(2πk7/8) }] X(0)の計算 • k=0だから・・・cos(0)=1,sin(0)=0となり, 簡単に計算できて X(0)= { 28+j 0 } = + 28.0 + j 0.00 |X(0)|= 28.0 となる • 同様にX(1)~X(7)を求めると X(1)~X(7)を計算すると • • • • • • • • X(0)= + 28.0 + j 0.00 X(1)= - 40.0 + j 9.68 X(2)= - 40.0 + j 4.0 X(3)= - 40.0 + j 1.68 X(4)= - 40.0 + j 0.00 X(5)= - 40.0 - j 1.68 X(6)= - 40.0 - j 4.0 X(7)= - 40.0 - j 9.68 |X(0)|= 28.0 |X(1)|= 41.2 |X(2)|= 40.2 |X(3)|= 40.0 |X(4)|= 40.0 |X(5)|= 40.0 |X(6)|= 40.2 |X(7)|= 41.2 これまでに要した計算回数 x(n)=0の場合もカウントして • X(0)の実部・・・cosをN回,N項の和,1/N倍 • X(0)の虚部・・・sinをN回,N項の和,1/N倍 • これをk=0~N-1までN回繰り返し計算する • • • • • 合計 cos を N×N回 sin を N×N回 和を 2×N×N回 1/N倍 を 2×N回 p FFTでは N=2 =qr • Nが 2p となるようにすると • 2分割 → 4分割 → ・・・ • • • • • すべてのkについて集計すると cos を (N×N)/2+N回 sin を (N×N)/2+N回 和を (N×N)回 1/2倍 を (2×N)回 計算量(積和演算回数)の比較 N=2pの場合 • 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とする 非再帰性アルゴリズム • 質問はありませんか? • 今日はここまで • ごきげんよう
© Copyright 2025 ExpyDoc