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