離散傅里葉變換的矩陣表示及其運(yùn)算量

1、 第第4 4章章 FFTFFT 4.1 4.1 引言引言 4.1.1 離散傅里葉變換的矩陣表示及其運(yùn)算量離散傅里葉變換的矩陣表示及其運(yùn)算量 n DFT在數(shù)字信號處理中起著非常重要的作用，在數(shù)字信號處理中起著非常重要的作用， 這是與這是與DFT存在著高效算法，存在著高效算法， 即快速傅里葉變換即快速傅里葉變換(FFT) 分不開的。快速分不開的。快速運(yùn)算的關(guān)鍵是減少運(yùn)算量。運(yùn)算的關(guān)鍵是減少運(yùn)算量。n離散傅里葉變換對為：離散傅里葉變換對為： (4.1) (4.2)n式中式中 。 下面要用矩陣來表示下面要用矩陣來表示DFT關(guān)系。關(guān)系。 101, 1 , 0,)()(:NnnkNNkWnxkXDFT1,

2、 1 , 0,)(1)(:10NnWkXNnxIDFTNknkNNjNeW2n 一般情況下，信號序列一般情況下，信號序列x(n) 及其頻譜序列及其頻譜序列X(k) 都是用復(fù)數(shù)都是用復(fù)數(shù)來表示的，來表示的，WN當(dāng)然也是復(fù)數(shù)。因此，計(jì)算當(dāng)然也是復(fù)數(shù)。因此，計(jì)算DFT的一個(gè)值的一個(gè)值X(k) 需要進(jìn)行需要進(jìn)行N次復(fù)數(shù)乘法（與次復(fù)數(shù)乘法（與1相乘也包括在內(nèi)）和相乘也包括在內(nèi)）和N-1次復(fù)數(shù)次復(fù)數(shù)加法；所以，直接計(jì)算加法；所以，直接計(jì)算N點(diǎn)的點(diǎn)的DFT需要進(jìn)行需要進(jìn)行N2 次復(fù)數(shù)乘法和次復(fù)數(shù)乘法和N(N-1) 復(fù)數(shù)加法。復(fù)數(shù)加法。 n顯然，直接計(jì)算顯然，直接計(jì)算N點(diǎn)的點(diǎn)的IDFT所需的復(fù)乘和復(fù)加的次數(shù)也

3、是這所需的復(fù)乘和復(fù)加的次數(shù)也是這么多。當(dāng)么多。當(dāng)N足夠大時(shí)，足夠大時(shí)，N2 N(N-1), 因此，因此，DFT與與IDFT的運(yùn)的運(yùn)算次數(shù)與算次數(shù)與N2 成正比，隨著成正比，隨著N的增加，運(yùn)算量將急劇增加，而的增加，運(yùn)算量將急劇增加，而在實(shí)際問題中，在實(shí)際問題中，N往往是較大的，因此有必要對往往是較大的，因此有必要對DFT與與IDFT的計(jì)算方法予以改進(jìn)。的計(jì)算方法予以改進(jìn)。 4.1.2 因子的特性因子的特性n DFT和和IDFT的快速算法的導(dǎo)出主要是根據(jù)的快速算法的導(dǎo)出主要是根據(jù) 因子的特因子的特性。性。 1周期性：周期性： n對離散變量對離散變量n有同樣的周期性。有同樣的周期性。nkNnNNn

4、kNNknNWWWW)(nkNWnkNW 2對稱性：對稱性： n或或 3. 其它其它: knNNknNnkNnkNWWWW)()(*nkNNnkNknNnkNWWWW)()(*kNNNjkNNNkNNkNWeWWWW222)2(kNkNjkNjkNWeeW 2222224.2 4.2 基基2 2時(shí)間抽選的時(shí)間抽選的FFTFFT算法算法 4.2.1 算法推導(dǎo)算法推導(dǎo)n 已經(jīng)知道：已經(jīng)知道： n令令DFT的長度的長度N=2M，M為正整數(shù)。為正整數(shù)。1-N,0,1,k )()()(10nkNNnWnxnxDFTkXn令：令： n于是有：于是有：12N,0,1,r ) 12()()2()(rxrprx

5、rg1-N,0,1,k )()()()() 12()2()(120rk 2/120 2/120)12(1202kPWkGWrpWWrgWrxWrxkXkNNrNkNNrrkNNrkrNNrrkNn其中，其中， n是由是由x(n)的偶數(shù)抽樣點(diǎn)形成的的偶數(shù)抽樣點(diǎn)形成的DFT；而；而 kr 2/120120kr 2/)2()()(NNrNrNWrxWrgkG120kr 2/kr 2/120) 12()()(NrNNNrWrxWnpkPn是由是由x(n)的奇數(shù)抽樣點(diǎn)形成的的奇數(shù)抽樣點(diǎn)形成的DFT。但是這兩個(gè)式子并不完。但是這兩個(gè)式子并不完全是全是N/2點(diǎn)的點(diǎn)的DFT，因?yàn)?，因?yàn)閗的范圍仍然是由的范圍仍

6、然是由0到到N-1，因此，還，因此，還應(yīng)該進(jìn)一步考慮應(yīng)該進(jìn)一步考慮k由由N/2到到N-1范圍的情況。范圍的情況。n現(xiàn)在令現(xiàn)在令 ，故對于后半段有：，故對于后半段有： n同理：同理： n又知：又知： 12, 1 , 0Nk)()()()()2(120kr 21202120)2(2/22kGWrgWWrgWrgNkGNrNNrrkNrNrNkrNNN)()2(kPNkPk 2NNkNWW 圖圖 4.1 N點(diǎn)點(diǎn)DFT分解為兩個(gè)分解為兩個(gè)N/2點(diǎn)的點(diǎn)的DFT (N=8) 圖圖 4.2 N/2 點(diǎn)的點(diǎn)的DFT 分解為兩個(gè)分解為兩個(gè)N/4點(diǎn)的點(diǎn)的DFT (N=8)n綜上所述，可以得到：綜上所述，可以得到：

7、 n其中其中G(k)、P(k) 分別是分別是x(n)的偶數(shù)點(diǎn)和奇數(shù)點(diǎn)的的偶數(shù)點(diǎn)和奇數(shù)點(diǎn)的N/2點(diǎn)點(diǎn)DFT。 )()()2()()()(kPWkGNkXkPWkGkX kNkN12, 1 , 0Nkn 這樣，我們就將一個(gè)這樣，我們就將一個(gè)N點(diǎn)的點(diǎn)的DFT分解成了兩個(gè)分解成了兩個(gè)N/2點(diǎn)的點(diǎn)的DFT，由于由于DFT的運(yùn)算量與其點(diǎn)數(shù)的平方成正比，因此使運(yùn)算量減的運(yùn)算量與其點(diǎn)數(shù)的平方成正比，因此使運(yùn)算量減少了。但是，還應(yīng)該將每一個(gè)少了。但是，還應(yīng)該將每一個(gè)N/2點(diǎn)的點(diǎn)的DFT再分解為兩個(gè)再分解為兩個(gè)N/4點(diǎn)的點(diǎn)的DFT，如此下去，直到分解為，如此下去，直到分解為2點(diǎn)的點(diǎn)的DFT為止，總共需為止，總共需

8、要進(jìn)行要進(jìn)行l(wèi)oglog2 2N-1=logN-1=log2 2(N/2)(N/2)次分解。次分解。圖圖 4.3 2 點(diǎn)點(diǎn) DFT 信號流圖（蝶形圖）信號流圖（蝶形圖）n對于對于2點(diǎn)點(diǎn)DFT，有：，有： n所以所以2點(diǎn)點(diǎn)DFT的運(yùn)算只需一次加法和一次減法，這樣的運(yùn)算的運(yùn)算只需一次加法和一次減法，這樣的運(yùn)算叫做蝶形運(yùn)算，這樣的信號流圖叫做蝶形圖。叫做蝶形運(yùn)算，這樣的信號流圖叫做蝶形圖。1111111122WTn該算法每次分解都是將時(shí)域序列按奇偶分為兩組，因此要求該算法每次分解都是將時(shí)域序列按奇偶分為兩組，因此要求N等于等于2的正整數(shù)冪，故將這種的正整數(shù)冪，故將這種FFT算法叫做基算法叫做基2時(shí)間

9、抽選法。時(shí)間抽選法。 4.2.2 算法特點(diǎn)算法特點(diǎn) 1. 倒序重排倒序重排n這種這種FFT算法的每次分解都是將輸入序列按照奇偶分為兩組，算法的每次分解都是將輸入序列按照奇偶分為兩組，故要不斷地將每組輸入數(shù)據(jù)按奇偶重排，直到最后分解為故要不斷地將每組輸入數(shù)據(jù)按奇偶重排，直到最后分解為2點(diǎn)的點(diǎn)的DFT，輸入數(shù)據(jù)才不再改變順序。這樣做的結(jié)果，使得，輸入數(shù)據(jù)才不再改變順序。這樣做的結(jié)果，使得作作FFT運(yùn)算時(shí)，輸入序列的次序要按其序號的倒序進(jìn)行重新運(yùn)算時(shí)，輸入序列的次序要按其序號的倒序進(jìn)行重新排列。排列。 n現(xiàn)在將圖現(xiàn)在將圖4.4中輸入序號以及重排后的序號按二進(jìn)制寫出如下中輸入序號以及重排后的序號按二進(jìn)

10、制寫出如下（注：下標(biāo)（注：下標(biāo)“2”表示二進(jìn)制數(shù)）。可以看出，將輸入序號表示二進(jìn)制數(shù)）?？梢钥闯觯瑢⑤斎胄蛱柕亩M(jìn)制表示（的二進(jìn)制表示（n2n1n0）位置顛倒，得到（）位置顛倒，得到（n0n1n2），就是），就是相應(yīng)的倒序的二進(jìn)制序號。因此，輸入序列按倒序重排，實(shí)相應(yīng)的倒序的二進(jìn)制序號。因此，輸入序列按倒序重排，實(shí)際上就是將序號為（際上就是將序號為（n2n1n0）的元素與序號為（）的元素與序號為（n0n1n2）的）的元素的位置相互交換。元素的位置相互交換。 2. 同址計(jì)算同址計(jì)算 n 從圖從圖4.4可以看出，整個(gè)算法流圖可以分為四段，（可以看出，整個(gè)算法流圖可以分為四段，（0）段）段為倒序重排

11、，后面為倒序重排，后面3段為段為3(log28=3)次迭代運(yùn)算：首先計(jì)算次迭代運(yùn)算：首先計(jì)算2點(diǎn)點(diǎn)DFT，然后將，然后將2點(diǎn)點(diǎn)DFT的結(jié)果組合成的結(jié)果組合成4點(diǎn)點(diǎn)DFT，最后將，最后將4點(diǎn)點(diǎn)DFT組合為組合為8點(diǎn)點(diǎn)DFT。因此，對于。因此，對于N點(diǎn)點(diǎn)FFT，只需要一列存儲，只需要一列存儲N個(gè)復(fù)數(shù)的存儲器。個(gè)復(fù)數(shù)的存儲器。 3. 運(yùn)算量運(yùn)算量n觀察圖觀察圖4.4可知，圖可知，圖4.3所示的蝶形圖實(shí)際上代表了所示的蝶形圖實(shí)際上代表了FFT的基的基本運(yùn)算，它實(shí)際上只包含了兩次復(fù)數(shù)加法運(yùn)算。一個(gè)本運(yùn)算，它實(shí)際上只包含了兩次復(fù)數(shù)加法運(yùn)算。一個(gè)N(N=2M) 點(diǎn)的點(diǎn)的FFT，需要進(jìn)行，需要進(jìn)行M=log2

12、N次迭代運(yùn)算。每次迭次迭代運(yùn)算。每次迭代運(yùn)算包含了代運(yùn)算包含了N/2個(gè)蝶型，因此共有個(gè)蝶型，因此共有N次復(fù)數(shù)加法；此外，除次復(fù)數(shù)加法；此外，除了第一次的了第一次的2點(diǎn)點(diǎn)DFT之外，每次迭代還包括了之外，每次迭代還包括了N/2次復(fù)數(shù)乘法次復(fù)數(shù)乘法（即乘（即乘WN的冪）。因此，一個(gè)的冪）。因此，一個(gè)N點(diǎn)的點(diǎn)的FFT共有復(fù)數(shù)乘法的次共有復(fù)數(shù)乘法的次數(shù)為：數(shù)為： n復(fù)數(shù)加法的次數(shù)為：復(fù)數(shù)加法的次數(shù)為： n因此，因此，F(xiàn)FT算法比直接計(jì)算算法比直接計(jì)算DFT大大減少了運(yùn)算量，尤其是大大減少了運(yùn)算量，尤其是當(dāng)當(dāng)N較大時(shí)，計(jì)算量的減少更為顯著。比如，當(dāng)較大時(shí)，計(jì)算量的減少更為顯著。比如，當(dāng)N=1024時(shí)，時(shí)

13、，采用采用FFT算法時(shí)復(fù)數(shù)乘法的次數(shù)，不超過直接計(jì)算算法時(shí)復(fù)數(shù)乘法的次數(shù)，不超過直接計(jì)算DFT時(shí)復(fù)時(shí)復(fù)乘次數(shù)的千分之五。乘次數(shù)的千分之五。 2log2) 1(log2222NNNNMcNNNNAc222loglog224.3 4.3 基基2 2頻率抽選的頻率抽選的FFTFFT算法算法n 時(shí)間抽選法是在時(shí)域內(nèi)將輸入序列時(shí)間抽選法是在時(shí)域內(nèi)將輸入序列x(n)逐次分解為偶數(shù)點(diǎn)逐次分解為偶數(shù)點(diǎn)子序列和奇數(shù)點(diǎn)子序列，通過求子序列的子序列和奇數(shù)點(diǎn)子序列，通過求子序列的DFT而實(shí)現(xiàn)整個(gè)序而實(shí)現(xiàn)整個(gè)序列的列的DFT。而頻率抽選法則是在頻域內(nèi)將。而頻率抽選法則是在頻域內(nèi)將X(k)逐次分解成偶逐次分解成偶數(shù)點(diǎn)子序

14、列和奇數(shù)點(diǎn)子序列，然后對這些分解得越來越短的數(shù)點(diǎn)子序列和奇數(shù)點(diǎn)子序列，然后對這些分解得越來越短的子序列進(jìn)行子序列進(jìn)行DFT運(yùn)算，從而求得整個(gè)的運(yùn)算，從而求得整個(gè)的DFT。當(dāng)然，同樣要。當(dāng)然，同樣要求求N為為2的正整數(shù)冪。的正整數(shù)冪。 n 設(shè)設(shè) ，則可以分別表示出，則可以分別表示出k為偶數(shù)和奇數(shù)時(shí)為偶數(shù)和奇數(shù)時(shí)的的X(k)。 n其中，其中， 12, 1 , 0Nr120rn 2/120rn 2/120rn 2/120120)2(22102)()2()()2()()()2(NnNNnrNNNNnNNnNnrNnNnrNNnrnNWngWWNnxWnxWNnxWnxWnxrX11)2()()(2N,

15、0,n Nnxnxng120rn 2/120rn 2/120rn 2/12022120rn 2/120120)2)(12(2)() 1()2()()2()()2()() 12 (NnNnNNnnNNNnnNNNnNNrNNnNnrNNnnNNNnNnNnrNnNnrNWWnpWWNnxWWnxWWWWNnxWWnxWNnxWWnxrXn其中，其中， n 顯然，顯然，X(2r) 為為g(n) 的的N/2點(diǎn)點(diǎn)DFT，X(2r+1) 為為p(n)WNn 的的N/2點(diǎn)點(diǎn)DFT。這樣，一個(gè)。這樣，一個(gè)N點(diǎn)的點(diǎn)的DFT分解為兩個(gè)分解為兩個(gè)N/2點(diǎn)的點(diǎn)的DFT。將分解繼續(xù)下去，直到分解為將分解繼續(xù)下去，直到

16、分解為2點(diǎn)的點(diǎn)的DFT為止。當(dāng)為止。當(dāng)N=8時(shí)，時(shí)，基基2頻率抽選的頻率抽選的FFT算法的整個(gè)信號流圖如圖算法的整個(gè)信號流圖如圖4.6所示。所示。11)2()()(2N,0,n Nnxnxnpn將圖將圖4.6與圖與圖4.4比較，可知頻率抽選法的計(jì)算量與時(shí)間抽選比較，可知頻率抽選法的計(jì)算量與時(shí)間抽選法相同，而且都能夠同址計(jì)算。時(shí)間抽選法是輸入序列按奇法相同，而且都能夠同址計(jì)算。時(shí)間抽選法是輸入序列按奇偶分組，故偶分組，故x(n)的順序要按倒序重排，而輸出序列按前后分的順序要按倒序重排，而輸出序列按前后分半，故半，故X(k) 的順序不需要重排；頻率抽選法則是輸出序列按的順序不需要重排；頻率抽選法則

17、是輸出序列按奇偶分組，故奇偶分組，故X(k) 的順序要按倒序重排，而輸入序列按前后的順序要按倒序重排，而輸入序列按前后分半，故分半，故x(n) 不需要重排。不需要重排。 4.5 4.5 快速傅里葉反變換（快速傅里葉反變換（IFFTIFFT）nIFFT是是IDFT的快速算法。由于的快速算法。由于DFT的正變換和反變換的表的正變換和反變換的表達(dá)式相似，因此達(dá)式相似，因此IDFT也有相似的快速算法?？梢杂萌N不也有相似的快速算法。可以用三種不同的方法來導(dǎo)出同的方法來導(dǎo)出IFFT算法。算法。n方法方法1n 設(shè)設(shè) ， 則有：則有： ， n=0,1,N-1n=0,1,N-1)()(kXnxDFT 10)(

18、1)(NknkNWkXNnxn根據(jù)基根據(jù)基2 FFT的時(shí)間抽選法的第一次分解的結(jié)果：的時(shí)間抽選法的第一次分解的結(jié)果：)()()2()()()(kPWkGNkXkPWkGkX kNkN12, 1 , 0Nkn可以得到：可以得到：)2()(21)()2()(21)(NkXkXWkPNkXkXkG kN12, 1 , 0Nk 圖圖 4.8 由由 X(k)、X(k+N/2) 得到得到 G(k)、P(k)n再由再由N/2點(diǎn)的點(diǎn)的DFT求得求得N/4點(diǎn)的點(diǎn)的DFT，依次類推下去，就可推，依次類推下去，就可推到求出到求出x(n)的各點(diǎn)，如圖的各點(diǎn)，如圖4.9所示。將此流圖與圖所示。將此流圖與圖4.4比較，相

19、比較，相當(dāng)于整個(gè)流向反過來，此外，因子當(dāng)于整個(gè)流向反過來，此外，因子WNk成為成為WN-k-k，還增加了，還增加了因子因子1/2。但是，圖。但是，圖4.9的的IFFT算法不能直接利用按照圖算法不能直接利用按照圖4.4編編寫的寫的FFT算法程序，卻可以利用圖算法程序，卻可以利用圖4.6的頻率抽選的頻率抽選FFT算法的算法的程序，只需要將程序，只需要將X(k)作為輸入序列，因子作為輸入序列，因子WNk變?yōu)樽優(yōu)閃N-k-k，并，并且將最后所得的輸出序列的每個(gè)元素都除以且將最后所得的輸出序列的每個(gè)元素都除以N。n方法方法2n 將將DFT的正變換式：的正變換式： n與其反變換式：與其反變換式： 10)(

20、)(NnnkNWnxkX10)(1)(NknkNWkXNnxn比較，很容易知道，可以利用比較，很容易知道，可以利用FFT算法的程序來算法的程序來計(jì)算計(jì)算IFFT，只需要將，只需要將X(k) 作為輸入序列，作為輸入序列，x(n) 則則是輸出序列，另外將因子是輸出序列，另外將因子WNk 變?yōu)樽優(yōu)閃N-k-k， 當(dāng)然，當(dāng)然，最后還必須將輸出序列的每個(gè)元素除以最后還必須將輸出序列的每個(gè)元素除以N。n 方法方法3n 對對DFT的反變換式取共軛，有：的反變換式取共軛，有： 1, 1 , 0, )(1)(1)(10*10*NnWkXNWkXNnxNknkNNknkNn與與DFT的正變換式比較，可知完全可以利

21、用的正變換式比較，可知完全可以利用FFT的計(jì)算程序，只需要將的計(jì)算程序，只需要將X*(k) 作為輸入序列，并將作為輸入序列，并將最后結(jié)果取共軛，再除以最后結(jié)果取共軛，再除以N就得到就得到x(n)。4.7.1 兩個(gè)長度相同的實(shí)序列兩個(gè)長度相同的實(shí)序列n 可以將兩個(gè)長度相同的實(shí)序列組合成一個(gè)復(fù)序列來進(jìn)行可以將兩個(gè)長度相同的實(shí)序列組合成一個(gè)復(fù)序列來進(jìn)行FFT運(yùn)算，從而一次完成這兩個(gè)實(shí)序列的運(yùn)算，從而一次完成這兩個(gè)實(shí)序列的FFT，減少了總，減少了總的計(jì)算量。的計(jì)算量。n 設(shè)設(shè)p(n) 和和g(n) 是兩個(gè)長度均為是兩個(gè)長度均為N的實(shí)序列，并設(shè)：的實(shí)序列，并設(shè)： n又設(shè)又設(shè) n ， ， n則由則由DFT

22、的線性有：的線性有： (4.36)()()(njgnpny)()(kPnpDFT )()(kGngDFT )()(kYnyDFT )()()(kjGkPkYnP(k) 和和G(k) 這兩個(gè)復(fù)序列的實(shí)部都是周期性的偶序列，而這兩個(gè)復(fù)序列的實(shí)部都是周期性的偶序列，而其虛部都是周期性的奇序列。其虛部都是周期性的奇序列。n 對復(fù)序列對復(fù)序列Y(k) 又有又有 (4.37)n這里下標(biāo)這里下標(biāo) r、i 分別表示實(shí)部和虛部，分別表示實(shí)部和虛部，Y(k) 與其實(shí)部、虛部與其實(shí)部、虛部的長度都為的長度都為 N?，F(xiàn)將。現(xiàn)將 (4.37) 式中各序列作周期延拓，有式中各序列作周期延拓，有 (4.38)(4.38)(

23、)()(kjYkYkYir)()()(kYjkYkYirn由周期性有：由周期性有： (4.39) (4.40)()(),()(kNYkY kNYkYrrrr)()(),()(kNYkY kNYkYiiiin現(xiàn)在將序列現(xiàn)在將序列 與與 作如下分解：作如下分解： (4.41) (4.42)(kYr)(kYi)()(21)()(21)(kNYkYkNYkYkYrrrrr)()(21)()(21)(kNYkYkNYkYkYiiiiin 由（由（4.394.39）式和（）式和（4.404.40）式，容易證明在）式，容易證明在(4.41)(4.41)和和(4.42)(4.42)這兩個(gè)式子中，前一項(xiàng)都是偶序列，而后一項(xiàng)都是奇序列。這兩個(gè)式子中，前一項(xiàng)都是偶序列，而后一項(xiàng)都是奇序列。n 將（將（4.414.41）式和（）式和（4.424.42）式代入（）式代入（4.384.38）式，并將各項(xiàng)）式，并將各項(xiàng)進(jìn)行重新組合，得到：進(jìn)行重新組合，得到：)( )( )()(21)()(21)()(21)()(21)(kGjkPkNYkYjkNY