【正文】 ， N=4096時，三類碟形單元運算的乘法次數(shù)為一類碟形單元運算的 75% 1mNW ??(1 j) 2 / 2mNW ??mNWj??第 4章 快速傅里葉變換 (FFT) 在 FFT運算中，旋轉(zhuǎn)因子 ，求正弦和余弦函數(shù)值的計算量是很大的。所以編程時，產(chǎn)生旋轉(zhuǎn)因子的方法直接影響運算速度。 一種方法是在每級運算中直接產(chǎn)生；另一種方法是在 FFT程序開始前預先計算出 ， m = 0，1， … ， N/2－ 1， 存放在數(shù)組 中，作為旋轉(zhuǎn)因子表，在程序執(zhí)行過程中直接查表得到所需旋轉(zhuǎn)因子值，不再計算。 這樣使運算速度大大提高，其不足之處是占 ?? )/π2c o s ( NmW mN)/π2s i n (j Nm?mNW第 4章 快速傅里葉變換 (FFT) 實序列的 FFT算法 在實際工作中，數(shù)據(jù) x(n)常常是實數(shù)序列。如果直接按 FFT運算流圖計算，就是把 x(n)看成一個虛部為零的復序列進行計算，這就增加了存儲量和運算時間。 處理該問題的方法有兩種。 早期提出的 方法是用一個 N點FFT計算兩個 N點實序列的 FFT，一個實序列作為 x(n)的實部，另一個作為虛部，計算完 FFT后，根據(jù) DFT的共軛對稱性，由輸出 X(k)分別得到兩個實序列的 N點 DFT（例題 ）。 第二種方法是用 N/2點 FFT計算一個 N點實序列的 DFT。 第 4章 快速傅里葉變換 (FFT) 設(shè) x(n)為 N點實序列，取 x(n)的偶數(shù)點和奇數(shù)點分別作為新構(gòu)造序列 y(n)的實部和虛部，即 對 y(n)進行 N/2點 FFT，輸出 Y(k)，則 1210)(j)()(1210)12()()2()(2121?????????NnnxnxnyNnnxnxnxnx，，，，，??? ?? ?1122( ) D F T ( ) ( )0 1 12( ) D F T ( ) ( )epopX k x n Y kNkX k x n jY k????????? ? ??， ， ， ，第 4章 快速傅里葉變換 (FFT) 根據(jù) DITFFT的思想及式 ()和 ()，可得到 X(k)的前 個值： 式中， 。由于 x(n)為實序列， 因此 X(k)具有共軛對稱性， X(k)的后 N/2點的值為 12?N)0(2 ),0(2 2211 XNXXNX ??????????????1210)()( * ???? NkkXkNX ，， ?210)()()( 21NkkXWkXkX kN ，， ????（ ） 第 4章 快速傅里葉變換 (FFT) 計算 N/2點 FFT的復乘次數(shù)為 N(M1)/4，計算式()的復乘次數(shù)為 N/2，所以用這種算法 , 計算 X(k)所需復數(shù)乘法次數(shù)為 。相對一般的 N點FFT算法，上述算法的運算效率為 ?當 N=2M=210時， η=20/11，運算速度提高近 1 )1(42)1(4 ???? MNNMN)1/(2)1(4/2 ???? MMMNMN?第 4章 快速傅里葉變換 (FFT) 其他快速算法簡介 快速傅里葉變換算法是信號處理領(lǐng)域重要的研究課題。 本章僅介紹算法最簡單、編程最容易的基 2FFT算法原理及其編程思想，使讀者建立快速傅里葉變換的基本概念，了解研究 FFT算法的主要途徑和編程思路。例如，分裂基 FFT算法、離散哈特萊變換 (DHT)、基 4FFT、基8FFT、基 rFFT、混合基 FFT，以及進一步減少運算量的途徑等內(nèi)容，對研究新的快速算法都是很有用的。本節(jié)簡要介紹其他幾種快速算法的運算量及其主要特點，以 第 4章 快速傅里葉變換 (FFT) 從理論上講，不同基數(shù)的 FFT算法的運算效率不同，實際中最常用的是基 2FFT、 基 4 FFT、分裂基 FFT和DHT。為此，下面簡要 介紹后三種 FFT算法的特點 ,以擴展讀者的視野。 ?在基 rFFT算法中，基 4FFT算法運算效率與基 8FFT很 接近，但基 4FFT算法實現(xiàn)程序簡單，且判斷開銷少。 可以證明， 當 FFT的基大于 4時，不會明顯降低計算量。 第 4章 快速傅里葉變換 (FFT) ?分裂基 FFT算法 是將基 2分解和基 4分解糅合提出的， 其 復數(shù)乘法次數(shù)接近 FFT理論最小值 ，但其運算流圖 卻與基 2FFT很相似，編程簡單，運算程序也很短，是 一種很實用的高效算法 。 ?但是，對實序列 x(n)，上述各種 FFT算法仍將其看成虛 部為零的復序列存儲和計算。而一次復數(shù)乘法需要四 次實數(shù)乘法和二次實數(shù)加法。所以， 必然浪費存儲資 源和增加多余的運算量 。 第 4章 快速傅里葉變換 (FFT) 我們知道，實序列的 N點 DFT具有共軛對稱性，即 *( ) ( ) , 0 , 1 , 2 , , 1X N k X k k N? ? ? ?所以， 只要計算出 X（ k）的前面 N/2個值，則其后面的 N/2個值可以由對稱性求得 。因此， FFT算法得到的 N個 X（ k）值有一半是多余的。 ?所以，對實序列一定存在更高效的快速算法。 離散哈特 萊變換（ DHT）就是針對實序列的一種高效變換算法 ，相 對一般的 FFT算法， DHT的快速算法 FHT可以減少近一半 的計算量。 第 4章 快速傅里葉變換 (FFT) ?應當說明， DHT是與 DFT不同的變換，所以要想得到 實序列 DFT，還要根據(jù)二者的關(guān)系式進行轉(zhuǎn)換。下面 DHT具有以下 主要特點 (1) DHT是實數(shù)變換，在對實信號進行處理時避免了復數(shù)運算，運算效率高。 (2) DHT的正、逆變換（除了因子 1/N外）具有相同的形式。 N點 DHT定義如下： 第 4章 快速傅里葉變換 (FFT) N點逆 DHT變換定義為 (3) DHT滿足循環(huán)卷積定理，所以，可以直接用 FHT實現(xiàn)實序列的快速卷積，大大提高處理速度。 （ ） (4) DHT與 DFT之間的關(guān)系非常簡單，容易實現(xiàn)二者之間 的轉(zhuǎn)換，關(guān)系式如下： H H H H11( ) [ ( ) ( ) ] j [ ( ) ( ) ]22X k X k X N k X k X N k? ? ? ? ? ?（ ） 對實信號 x(n)進行譜分析時，可以先對 x(n)進行 FHT， 然后再將 Ｘ H(k)轉(zhuǎn)換成 X(k)，這樣可以提高分析速度