知識(shí)2離散傅里葉變換及其快速算法

1、 用Fourier變換來(lái)表示序列和線性時(shí)不變系統(tǒng)的頻域特征，但是頻譜是的連續(xù)函書(shū)，用計(jì)算機(jī)處理和分析頻譜是不方便的。那么就需要像時(shí)序信號(hào)那樣，通過(guò)采集把連續(xù)信號(hào)變?yōu)殡x散信號(hào)，也對(duì)連續(xù)頻譜采樣而得到離散頻譜，然后用數(shù)字電路或計(jì)算機(jī)進(jìn)行處理和分析。有限長(zhǎng)序列在應(yīng)用中有重要的作用，通過(guò)它可以導(dǎo)出另一種Fourier變換表達(dá)式，即離散傅里葉變換(DFT)，此為解決頻譜離散化的有效方法，同時(shí)DFT的高效算法快速傅里葉變換FFT。周期序列一個(gè)周期為N的周期序列，對(duì)于所有的n，應(yīng)該滿足：周期序列的周期N，一般使用最小周期作為周期。與連續(xù)時(shí)間周期函數(shù)相比，周期序列由于n及N均為整數(shù)，周期序列中應(yīng)用最廣泛的序列

2、是：（2-1）上圖就是周期序列（N=8），從n=0開(kāi)始到8取完周期內(nèi)的所有值。令k = 1時(shí)，就是一個(gè)周期序列。當(dāng)n從0依次加1到N-1時(shí)，序列取完周期內(nèi)的所有值，這些值可以看成是Z平面上以原點(diǎn)為圓心的單位圓被N等分的交點(diǎn)的的坐標(biāo)值。k為其他數(shù)值時(shí)，的最小周期也許不是N，但是N一定是的周期。的性質(zhì)很明顯：周期性：=對(duì)稱性：=正交性： 或者 一個(gè)周期為N的周期序列，在n=到n=+的范圍內(nèi)僅有N個(gè)序列值是獨(dú)立的其中一個(gè)周期內(nèi)的N個(gè)序列值足以表征整個(gè)序列的特征。而對(duì)于長(zhǎng)度為N的有限長(zhǎng)序列，只討論n=0到N-1之間的N個(gè)序列值，其余皆為0。此二者在n=0到N-1單位內(nèi)具有共同性。對(duì)于周期為n的周期序列

3、，定義n=0到N-1為主值區(qū)間，由主值區(qū)間N個(gè)序列值組成的有限長(zhǎng)序列，稱為的主值序列?？梢匀缦卤硎荆海?-2）為矩形序列，即：上一過(guò)程稱為取主值序列，有限長(zhǎng)序列：如果以N為周期進(jìn)行延拓，則有：（2-3）式2-2和2-3之間表明了周期序列和有限長(zhǎng)序列之間的處理關(guān)系。即：周期序列可以去主值序列進(jìn)行分析，然后對(duì)再周期延拓得到最后的處理結(jié)果。周期延拓的時(shí)候，延拓周期和有限長(zhǎng)序列的長(zhǎng)度不同的時(shí)候，序列可能會(huì)發(fā)生混疊。若為M長(zhǎng)的有限長(zhǎng)序列，即：（2-5）以N為周期進(jìn)行延拓，得到周期序列：再取的主值序列：（2-7）關(guān)于使（2-5）和（2-7）是否一致的問(wèn)題：（1） 當(dāng)N=M時(shí)，和是一致的，所以，周期延拓?zé)o混

4、疊失真，主值序列和原序列一致相同。（2） 當(dāng)M/2=N=M時(shí)，此時(shí)會(huì)使得至少不僅含有，還疊加有。說(shuō)明和是不一致的。因此，在M/2=N=M時(shí)會(huì)出現(xiàn)部分混疊失真，以下結(jié)論：（3） 當(dāng)N=L1，則有，上式表明，要使圓周卷積等于線性卷積而不產(chǎn)生混疊失真的充要條件是：L=M+N+1若LL12L時(shí)，圓周卷積和線性卷積的結(jié)果就會(huì)完全不一致，將產(chǎn)生全混疊失真。DFT、DTFT和Z變換如果一個(gè)有限長(zhǎng)序列的，滿足收斂條件時(shí)，則有，（2-40）（2-41）DFT相應(yīng)的形式為：（2-42）上式中的。式（2-40）是有限長(zhǎng)序列的Z變換，是在Z平面內(nèi)對(duì)的一些特性進(jìn)行分析時(shí)的工具。當(dāng)Z取單位圓的時(shí)候，亦即，則變?yōu)槭牵?-4

5、1），成為的頻域特性分析，其中的不是一個(gè)固定值，而是一個(gè)參變量，可以連續(xù)取值。為了便于計(jì)算機(jī)進(jìn)行處理，就需要離散化，簡(jiǎn)單的就是在=0到2的范圍內(nèi)N等分，得到的DFT的形式，亦即（2-42）式，它們之間的關(guān)系可以如下表示：（2-43）式（2-43）說(shuō)明N點(diǎn)的有限長(zhǎng)序列的離散傅里葉變換是它的Z變換在單位圓上N個(gè)等分點(diǎn)上（，k=0,1,2,3,.,N-1）的采樣值，也是它的傅里葉變換在0=2區(qū)間N個(gè)等分點(diǎn)上的采樣，這種關(guān)系意味著對(duì)于時(shí)間有限信號(hào)，可以像帶限信號(hào)進(jìn)行時(shí)域采集而不丟失任何信息一樣，可以在頻域上進(jìn)行采樣而不丟失任何信息，此正為傅里葉變換中時(shí)域和頻域?qū)ε缄P(guān)系的反映，有著十分重要的意義。DFT

6、實(shí)現(xiàn)了頻域的離散化，開(kāi)辟了頻域領(lǐng)域采用數(shù)字技術(shù)進(jìn)行處理的領(lǐng)域。頻率采樣理論采用DFT后實(shí)現(xiàn)了頻域的采樣，同樣可以采用頻域采樣的方法逼近任意一個(gè)頻率特性，接下來(lái)，分析一下頻率采樣的可行性以及所帶來(lái)的誤差。一個(gè)任意序列，滿足收斂條件，它的Z變換為：對(duì)在單位圓上N個(gè)等分點(diǎn)上進(jìn)行采樣，有：，對(duì)進(jìn)行IDFT，得到長(zhǎng)度為N點(diǎn)的有限長(zhǎng)序列，即：通過(guò)對(duì)上式進(jìn)行運(yùn)算，得到與的關(guān)系如下所示：可見(jiàn)，是以N為周期進(jìn)行周期延拓后所取的主值序列。和時(shí)域采樣會(huì)造成頻域周期延拓一樣，頻域采樣同樣會(huì)造成時(shí)域的周期延拓。如果是有限長(zhǎng)序列，序列的長(zhǎng)度為M，即：若N=M，即：這就是頻域采樣定理，此時(shí)即為的N點(diǎn)離散傅里葉變換。當(dāng)為無(wú)限

7、長(zhǎng)序列時(shí)，必然會(huì)產(chǎn)生存在混疊失真，只能隨著采樣點(diǎn)數(shù)N的增加，而逐漸逼近于。對(duì)于有限長(zhǎng)序列，在滿足頻域采樣定理的前提下，N點(diǎn)頻域采樣就足以不失真地代表序列的特性。因此，由N點(diǎn)采樣值能夠完全地表達(dá)整個(gè)函數(shù)及頻域特性?？焖俑道锶~變換（FFT）快速傅里葉變換（FFTFast Fourier Transform）是快速計(jì)算DFT的有效算法。離散傅里葉變換實(shí)現(xiàn)了頻域的離散化，在數(shù)字信號(hào)處理中有著重要的作用，包括分析信號(hào)的頻譜、計(jì)算濾波器頻域響應(yīng)以及實(shí)現(xiàn)信號(hào)通過(guò)線性系統(tǒng)的卷積運(yùn)算。DFT的運(yùn)算特點(diǎn)一個(gè)有限長(zhǎng)度為N的有限長(zhǎng)序列的離散傅里葉變換為：一般說(shuō)來(lái)和都是復(fù)數(shù)，按照一般定義來(lái)計(jì)算，計(jì)算一點(diǎn)值需要N次復(fù)數(shù)相

8、乘運(yùn)算，次的復(fù)數(shù)相加運(yùn)算。計(jì)算全部N點(diǎn)則需要次復(fù)數(shù)相乘運(yùn)算和次的復(fù)數(shù)相加運(yùn)算。由于一個(gè)復(fù)數(shù)運(yùn)算包含4個(gè)實(shí)數(shù)相乘和兩個(gè)實(shí)數(shù)加法，所以，計(jì)算全部的需要實(shí)數(shù)相乘運(yùn)算和次復(fù)數(shù)相加運(yùn)算。 由于DFT的運(yùn)算量和成正比，所以將長(zhǎng)序列的DFT分解成短序列的DFT計(jì)算，可是運(yùn)算量得到明顯的減少?？焖俑道锶~變換正是利用的特性，逐步將N點(diǎn)序列分解為較短的序列，計(jì)算短序列的DFT，然后再組合成原序列的DFT，使得運(yùn)算量顯著減少。FFT算法分為兩類：時(shí)間抽取法和頻域抽取法。時(shí)間抽取基-2 FFT算法設(shè)序列長(zhǎng)度N為2的整數(shù)冪次方（實(shí)際應(yīng)用中常常如此選?。?，其中M為正整數(shù)，分為兩組，偶數(shù)項(xiàng)為一組和奇數(shù)項(xiàng)為一組得到兩個(gè)點(diǎn)的

9、子序列，即：相應(yīng)的DFT運(yùn)算也可以分成兩組： （2-54） 假定、分別是和的DFT，亦即：上兩式的取值范圍為，式2-54的取值范圍為。由式子2-54可知，、分別為為主值序列的周期序列因此、應(yīng)該周期性的重復(fù)一次，所以式子2-54可以寫(xiě)成下面的形式：（2-57）式中出現(xiàn)的負(fù)號(hào)是由于。式2-57的運(yùn)算關(guān)系可用信號(hào)流圖表示成蝶形運(yùn)算的形式，左兩路為輸入，中間一個(gè)小圓點(diǎn)表示加減運(yùn)算，右上支路為相加后的輸出，右下支路為相減后的輸出，箭頭旁邊的系數(shù)表示相乘的數(shù)。因流圖形如蝴蝶，故稱為蝶形運(yùn)算。每個(gè)蝶形運(yùn)算需要一次復(fù)數(shù)相乘，兩次復(fù)數(shù)加法運(yùn)算，如下圖所示，還有8點(diǎn)DFT分解運(yùn)算過(guò)程，接下來(lái)估算一下乘法的運(yùn)算量，

10、每一個(gè)N/2點(diǎn)的DFT需要次復(fù)數(shù)相乘，兩個(gè)N/2點(diǎn)DFT共需要次復(fù)數(shù)相乘，組合運(yùn)算共需N/2個(gè)蝶形運(yùn)算，需要N/2次復(fù)數(shù)相乘，因而共需要次復(fù)數(shù)相乘，N比較大時(shí)，可以近似認(rèn)為等于，與直接計(jì)算相比節(jié)約一半的運(yùn)算量。由于，如果大于2，可繼續(xù)進(jìn)行N/2點(diǎn)序列分解成兩個(gè)N/4點(diǎn)的序列。如將分解為：有：其中，它們均為N/4點(diǎn)的DFT。這樣序列長(zhǎng)度又減為一半，對(duì)應(yīng)于8點(diǎn)的前一個(gè)N/2點(diǎn)的DFT再分解為兩個(gè)N/4點(diǎn)DFT流圖。當(dāng)然，也是如此，直到最后的兩點(diǎn)的DFT為止。2點(diǎn)的DFT同樣可用一個(gè)蝶形運(yùn)算表示。例如，8點(diǎn)的第一個(gè)2點(diǎn)DFT由和組成，就可以表示為：整個(gè)個(gè)流圖全由蝶形組成，蝶形運(yùn)算是FFT的核心，是最

11、基本的運(yùn)算。對(duì)于一個(gè)的序列，可以逐步分解為最后全為2點(diǎn)的DFT運(yùn)算。這樣就構(gòu)成了從到的M次逐級(jí)進(jìn)行運(yùn)算過(guò)程，每一級(jí)均由N/2個(gè)蝶形運(yùn)算構(gòu)成。全部的N點(diǎn)的FFT運(yùn)算共有個(gè)蝶形運(yùn)算，共需：復(fù)數(shù)乘法次數(shù)：復(fù)數(shù)加法次數(shù)：計(jì)算量顯著減小，N值愈大，減少的量更大。下面分別是序列長(zhǎng)度N為8點(diǎn)和16點(diǎn)的時(shí)間抽取FFT算法實(shí)現(xiàn)的流圖， 流圖中各蝶形運(yùn)算的輸入和輸出量是互不重疊的，任何一個(gè)蝶形運(yùn)算的兩個(gè)輸入量經(jīng)過(guò)蝶形運(yùn)算后，便失去了利用價(jià)值，不再需要保存，因此可以實(shí)現(xiàn)同址運(yùn)算，同址運(yùn)算也可以節(jié)省空間。離散傅里葉反變換（IFFT）的運(yùn)算方法FFT的算法同樣適用于IDFT運(yùn)算，簡(jiǎn)稱IFFT，即快速傅里葉反變換，IDFT定