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

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

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

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

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

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

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

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

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

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

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

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