【文章內容簡介】 下面討論減少運算量的方法。觀察DFT的運算形式可看出，利用系數的以下特性，就可以減少DFT的運算量：的共軛對稱性的周期性的可約性，由此可得出，這樣，通過這些性質，使DFT運算中有些項合并；利用的對稱性，周期性及可約性,將較長序列的DFT分解成較短序列的DFT，從而使DFT計算過程轉化成許多迭代運算過程。而前面已經說到，DFT的運算量是與成正比的，所以N越小，運算量越低?？焖俑道锶~變換算法正是基于此而發(fā)展起來的。它的運算基本上可以分成兩大類，即按時間抽選法和按頻率抽選法。根據論文要求，我們只考慮前一種方法。 按時間抽選（DIT）的基2FFT算法（庫利圖基算法） 算法原理 取序列點數，L為正整數。如果不滿足這個條件，可以加上若干零值點，使達到這一要求，即為基2FFT。對N點序列，將按n的奇偶性分組：， ，其中r=0,1,…, 則DFT轉化成 （33）利用系數的可約性，即，則 （34）式中與分別是及的N/2點DFT： （35） （36）由式（34）可以看出，一個N點DFT分解成兩個N/2點的DFT，它們按（34）式又可組合成一個N點DFT。但是，以及，都是N/2點的序列，即r,k滿足r,k=0,1,…,。而X(k)卻有N點，而用式（34）只得X(k)前一半，要用，來表式全部X(k)值，還需利用系數的周期性質，即 這樣可得到 （37）同理可得 （38）式（37）、式（38）表明后半部段k值所對應的，與前半部段k值所對應的，分別相等。在考慮的性質： （39）這樣，將式（37）、式（38）、式（39）帶入式（34）中，就可將X(k)表示成前后兩段：前半部分X(k)，(k=0,1,…,) （310）后半部分X(k)，(k=0,1,…,) ，k=0,1,…, （311）這樣，只要求出0到()區(qū)間的所有，值，即可求出0到(）區(qū)間內的所有值，這就大大節(jié)省了運算。式（310）、（311）的運算可以用如下的蝶形信號流圖31表示。圖31蝶形運算流圖采用這種表示法，其過程可圖32說明。圖32表示N=8的情況，輸出值X(0)到X(3)是由式（310）給出的，輸出值X（4）到X（7）是由式（311）給出。據此，一個N點DFT分成兩個點DFT時，若直接計算點DFT，則每個點DFT只需要次復數乘法，次復數加法。同時，把兩個點DFT合成為一個DFT時，有個蝶形運算，還需要次復數乘法及N次復數加法。因而通過這第一步分解后，工作量總體得到大幅降低。 既然如此，由于，因而仍是偶數，可以更進一步把每個點子序列按其奇偶性再分成兩個點子序列。先將進行分解： （312）其中，l=0,1,…, ，k=0,1,…, 且 ，k=0,1,…,其中 （313） （314）點DFT點DFT圖32 將N點DFT分為兩個點的DFT圖圖33給出N=8時，將一個點的DFT分成兩個點DFT，由這兩個點DFT組合成一個點DFT流圖。同時，也可以進行同樣的分解，得到其中 （315） （316）最后將系數統(tǒng)一為，則一個N=8點DFT就可分成四個2點DFT，這樣就可得到34圖。點DFT點DFT圖33 由兩個點DFT組合成一個點DFT 根據上面同樣的分析知道，最后剩下的是2點DFT，對于此例N=8，就是四個2點DFT，其輸出為，， (k=0,1)，這由式（313）至（316）可以計算出來。由此可得出一個按時間抽選運算的大致的8點DFT流圖，如圖35所示。點DFT 點DFT 點DFT 點DFT 圖34 將一個N點DFT分成四個點DFT 由圖35可知，當時(L表示級數)，每級都由個蝶形運算組成，每個蝶形運算有一次復乘，二次復加，因而每級運算都需次復乘和N次復加，因此L級運算共需復乘數 復加數 因為，這幾個系數都不用乘法運算。此外，當N較大時，這些特例相對而言就很少。直接DFT算法運算量，復數乘法：，復數加法：。直接計算DFT與FFT算法的計算量之比為。x(0)x(4)x(6)x(1)x(5)x(2)x(3)x(7)X(0)X(1)X(2)X(3)X(4)X(6)X(5)X(7)圖35 N=8按時間抽選FFT運算流圖 按時間抽選FFT算法的特點(1)原位運算（同址運算） 從上圖可以看出該運算是有規(guī)律可循的，其每級運算都是由個蝶形運算構成，下述迭代運算由每一個蝶形結構實現： （317）式（317）的蝶形運算如圖36所示。從圖35中看出，某一列的任何兩點k和j的運算后，得到結果為下一列k,j兩節(jié)點的變量，而與其他節(jié)點變量無關，通過原位運算，經過蝶形運算，其結果為另一列數據，它們以蝶形為單位仍存儲在這一組存儲器中，中間無需其他存儲器。這樣只需N個存儲結構單元，雖然進入蝶形的組合關系有差異，但下一級的運算也可采用這種運算方式。這種結構只需少量存儲單元，從而降低設備成本。圖36 蝶形運算結構 (2)倒位序規(guī)律按照原位計算，FFT的輸出X(k)在存儲單元中按順序排列，即X(0),X(1)，...，X(7)的順序排列，但是這時輸入x(n)卻不是按自然順序存儲的，按x(0),x(4)，...，x(7)的順序依次存入存儲單元，看起來好像是“雜亂無序”的，實際是有規(guī)律可循的，即倒位序。 造成該原因是由輸入x(n)按標號n的偶奇的不斷分組引起。這種不斷分成奇偶子序列的過程可用二進制樹狀圖37來描述。這就是DIT的FFT算法輸入序列的序數成為倒位序的原因。(3)倒位序的實現一般實際運算中，總是先向存儲單元中按順序輸入序列，為形成倒位序的排列，這通過變址來完成。若序列序號n用二進制數表示，順序為，那么其倒位序二進制數應當是。表31列出了N=8時自然順序以及相應的倒位序的二進制數。(4)蝶形運算節(jié)點的“距離” 仍以N=8時FFT運算流圖為例，其輸入是倒位序的，輸出是自然順序的，第一級每個蝶形兩節(jié)點間“距離”是4，由此類推得，對點FFT，當輸出為正常順序，輸入為倒位序時，其第ｍ級運算，每個蝶形兩節(jié)點“距離”則為。(5)的確定對第m級，一個蝶形運算兩節(jié)點的“距離”為，于是第m級的一個蝶形計算可寫成x(000)x(100)x(010)x(110)x(111)x(011)x(101)x(001)01010101010101圖37 描述倒位序的樹狀圖表31 自然順序及相應的倒位序自然順序二進制數倒位序二進制數倒位序順序0000000010011004201001023011110641000011510110156110011371111117 4 數字信號處理 MATLAB實現的基本知識