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

離散傅里葉變換的矩陣表示及其運(yùn)算量第1頁，共50頁，2023年，2月20日，星期二離散傅里葉變換對為：

(4.1) (4.2)式中

。

下面要用矩陣來表示DFT關(guān)系。

第2頁，共50頁，2023年，2月20日，星期二

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

第3頁，共50頁，2023年，2月20日，星期二顯然，直接計算N點(diǎn)的IDFT所需的復(fù)乘和復(fù)加的次數(shù)也是這么多。當(dāng)N足夠大時，N2≈N(N-1),因此，DFT與IDFT的運(yùn)算次數(shù)與N2成正比，隨著N的增加，運(yùn)算量將急劇增加，而在實(shí)際問題中，N往往是較大的，因此有必要對DFT與IDFT的計算方法予以改進(jìn)。第4頁，共50頁，2023年，2月20日，星期二

4.1.2因子的特性

DFT和IDFT的快速算法的導(dǎo)出主要是根據(jù)因子的特性。

1．周期性：

對離散變量n有同樣的周期性。第5頁，共50頁，2023年，2月20日，星期二

2．對稱性：

或

3.其它:

第6頁，共50頁，2023年，2月20日，星期二4.2基2時間抽選的FFT算法

4.2.1算法推導(dǎo)

已經(jīng)知道：

令DFT的長度N=2M，M為正整數(shù)。第7頁，共50頁，2023年，2月20日，星期二令：

于是有：第8頁，共50頁，2023年，2月20日，星期二其中，

是由x(n)的偶數(shù)抽樣點(diǎn)形成的DFT；而

第9頁，共50頁，2023年，2月20日，星期二是由x(n)的奇數(shù)抽樣點(diǎn)形成的DFT。但是這兩個式子并不完全是N/2點(diǎn)的DFT，因?yàn)閗的范圍仍然是由0到N-1，因此，還應(yīng)該進(jìn)一步考慮k由N/2到N-1范圍的情況。第10頁，共50頁，2023年，2月20日，星期二現(xiàn)在令，故對于后半段有：

同理：

又知：

第11頁，共50頁，2023年，2月20日，星期二

圖

4.1N點(diǎn)DFT分解為兩個N/2點(diǎn)的DFT(N=8)第12頁，共50頁，2023年，2月20日，星期二

圖

4.2N/2點(diǎn)的DFT分解為兩個N/4點(diǎn)的DFT(N=8)第13頁，共50頁，2023年，2月20日，星期二綜上所述，可以得到：

其中G(k)、P(k)分別是x(n)的偶數(shù)點(diǎn)和奇數(shù)點(diǎn)的N/2點(diǎn)DFT。

第14頁，共50頁，2023年，2月20日，星期二

這樣，我們就將一個N點(diǎn)的DFT分解成了兩個N/2點(diǎn)的DFT，由于DFT的運(yùn)算量與其點(diǎn)數(shù)的平方成正比，因此使運(yùn)算量減少了。但是，還應(yīng)該將每一個N/2點(diǎn)的DFT再分解為兩個N/4點(diǎn)的DFT，如此下去，直到分解為2點(diǎn)的DFT為止，總共需要進(jìn)行l(wèi)og2N-1=log2(N/2)次分解。第15頁，共50頁，2023年，2月20日，星期二圖

4.32點(diǎn)

DFT信號流圖（蝶形圖）第16頁，共50頁，2023年，2月20日，星期二對于2點(diǎn)DFT，有：

所以2點(diǎn)DFT的運(yùn)算只需一次加法和一次減法，這樣的運(yùn)算叫做蝶形運(yùn)算，這樣的信號流圖叫做蝶形圖。第17頁，共50頁，2023年，2月20日，星期二該算法每次分解都是將時域序列按奇偶分為兩組，因此要求N等于2的正整數(shù)冪，故將這種FFT算法叫做基2時間抽選法。第18頁，共50頁，2023年，2月20日，星期二

4.2.2算法特點(diǎn)

1.倒序重排這種FFT算法的每次分解都是將輸入序列按照奇偶分為兩組，故要不斷地將每組輸入數(shù)據(jù)按奇偶重排，直到最后分解為2點(diǎn)的DFT，輸入數(shù)據(jù)才不再改變順序。這樣做的結(jié)果，使得作FFT運(yùn)算時，輸入序列的次序要按其序號的倒序進(jìn)行重新排列。

第19頁，共50頁，2023年，2月20日，星期二現(xiàn)在將圖4.4中輸入序號以及重排后的序號按二進(jìn)制寫出如下（注：下標(biāo)“2”表示二進(jìn)制數(shù)）?？梢钥闯觯瑢⑤斎胄蛱柕亩M(jìn)制表示（n2n1n0）位置顛倒，得到（n0n1n2），就是相應(yīng)的倒序的二進(jìn)制序號。因此，輸入序列按倒序重排，實(shí)際上就是將序號為（n2n1n0）的元素與序號為（n0n1n2）的元素的位置相互交換。第20頁，共50頁，2023年，2月20日，星期二第21頁，共50頁，2023年，2月20日，星期二

2.同址計算

從圖4.4可以看出，整個算法流圖可以分為四段，（0）段為倒序重排，后面3段為3(log28=3)次迭代運(yùn)算：首先計算2點(diǎn)DFT，然后將2點(diǎn)DFT的結(jié)果組合成4點(diǎn)DFT，最后將4點(diǎn)DFT組合為8點(diǎn)DFT。因此，對于N點(diǎn)FFT，只需要一列存儲N個復(fù)數(shù)的存儲器。

第22頁，共50頁，2023年，2月20日，星期二

3.運(yùn)算量觀察圖4.4可知，圖4.3所示的蝶形圖實(shí)際上代表了FFT的基本運(yùn)算，它實(shí)際上只包含了兩次復(fù)數(shù)加法運(yùn)算。一個N(N=2M)點(diǎn)的FFT，需要進(jìn)行M=log2N次迭代運(yùn)算。每次迭代運(yùn)算包含了N/2個蝶型，因此共有N次復(fù)數(shù)加法；此外，除了第一次的2點(diǎn)DFT之外，每次迭代還包括了N/2次復(fù)數(shù)乘法（即乘WN的冪）。因此，一個N點(diǎn)的FFT共有復(fù)數(shù)乘法的次數(shù)為：第23頁，共50頁，2023年，2月20日，星期二

復(fù)數(shù)加法的次數(shù)為：

因此，F(xiàn)FT算法比直接計算DFT大大減少了運(yùn)算量，尤其是當(dāng)N較大時，計算量的減少更為顯著。比如，當(dāng)N=1024時，采用FFT算法時復(fù)數(shù)乘法的次數(shù)，不超過直接計算DFT時復(fù)乘次數(shù)的千分之五。

第24頁，共50頁，2023年，2月20日，星期二4.3基2頻率抽選的FFT算法

時間抽選法是在時域內(nèi)將輸入序列x(n)逐次分解為偶數(shù)點(diǎn)子序列和奇數(shù)點(diǎn)子序列，通過求子序列的DFT而實(shí)現(xiàn)整個序列的DFT。而頻率抽選法則是在頻域內(nèi)將X(k)逐次分解成偶數(shù)點(diǎn)子序列和奇數(shù)點(diǎn)子序列，然后對這些分解得越來越短的子序列進(jìn)行DFT運(yùn)算，從而求得整個的DFT。當(dāng)然，同樣要求N為2的正整數(shù)冪。

第25頁，共50頁，2023年，2月20日，星期二

設(shè)，則可以分別表示出k為偶數(shù)和奇數(shù)時的X(k)。

其中，

第26頁，共50頁，2023年，2月20日，星期二第27頁，共50頁，2023年，2月20日，星期二其中，

顯然，X(2r)為g(n)的N/2點(diǎn)DFT，X(2r+1)為p(n)WNn

的N/2點(diǎn)DFT。這樣，一個N點(diǎn)的DFT分解為兩個N/2點(diǎn)的DFT。將分解繼續(xù)下去，直到分解為2點(diǎn)的DFT為止。當(dāng)N=8時，基2頻率抽選的FFT算法的整個信號流圖如圖4.6所示。第28頁，共50頁，2023年，2月20日，星期二將圖4.6與圖4.4比較，可知頻率抽選法的計算量與時間抽選法相同，而且都能夠同址計算。時間抽選法是輸入序列按奇偶分組，故x(n)的順序要按倒序重排，而輸出序列按前后分半，故X(k)的順序不需要重排；頻率抽選法則是輸出序列按奇偶分組，故X(k)的順序要按倒序重排，而輸入序列按前后分半，故x(n)不需要重排。第29頁，共50頁，2023年，2月20日，星期二

4.5快速傅里葉反變換（IFFT）IFFT是IDFT的快速算法。由于DFT的正變換和反變換的表達(dá)式相似，因此IDFT也有相似的快速算法?？梢杂萌N不同的方法來導(dǎo)出IFFT算法。方法1

設(shè)

，

則有：，n=0,1,┅,N-1第30頁，共50頁，2023年，2月20日，星期二根據(jù)基2FFT的時間抽選法的第一次分解的結(jié)果：第31頁，共50頁，2023年，2月20日，星期二可以得到：第32頁，共50頁，2023年，2月20日，星期二

圖

4.8由

X(k)、X(k+N/2)得到

G(k)、P(k)第33頁，共50頁，2023年，2月20日，星期二再由N/2點(diǎn)的DFT求得N/4點(diǎn)的DFT，依次類推下去，就可推到求出x(n)的各點(diǎn)，如圖4.9所示。將此流圖與圖4.4比較，相當(dāng)于整個流向反過來，此外，因子WNk成為WN-k，還增加了因子1/2。但是，圖4.9的IFFT算法不能直接利用按照圖4.4編寫的FFT算法程序，卻可以利用圖4.6的頻率抽選FFT算法的程序，只需要將X(k)作為輸入序列，因子WNk變?yōu)閃N-k，并且將最后所得的輸出序列的每個元素都除以N。第34頁，共50頁，2023年，2月20日，星期二方法2

將DFT的正變換式：

與其反變換式：

第35頁，共50頁，2023年，2月20日，星期二比較，很容易知道，可以利用FFT算法的程序來計算IFFT，只需要將X(k)作為輸入序列，x(n)則是輸出序列，另外將因子WNk

變?yōu)閃N-k，

當(dāng)然，最后還必須將輸出序列的每個元素除以N。第36頁，共50頁，2023年，2月20日，星期二

方法3

對DFT的反變換式取共軛，有：

第37頁，共50頁，2023年，2月20日，星期二與DFT的正變換式比較，可知完全可以利用FFT的計算程序，只需要將X*(k)作為輸入序列，并將最后結(jié)果取共軛，再除以N就得到x(n)。第38頁，共50頁，2023年，2月20日，星期二4.7.1兩個長度相同的實(shí)序列

可以將兩個長度相同的實(shí)序列組合成一個復(fù)序列來進(jìn)行FFT運(yùn)算，從而一次完成這兩個實(shí)序列的FFT，減少了總的計算量。第39頁，共50頁，2023年，2月20日，星期二

設(shè)p(n)和g(n)是兩個長度均為N的實(shí)序列，并設(shè)：

又設(shè)

，

，

則由DFT的線性有：(4.36)第40頁，共50頁，2023年，2月20日，星期二P(k)和G(k)這兩個復(fù)序列的實(shí)部都是周期性的偶序列，而其虛部都是周期性的奇序列。

對復(fù)序列Y(k)又有

(4.37)這里下標(biāo)r、i分別表示實(shí)部和虛部，Y(k)與其實(shí)部、虛部的長度都為N。現(xiàn)將(4.37)式中各序列作周期延拓，有

(4.38)第41頁，共50頁，2023年，2月20日，星期二由周期性有： (4.39)

(4.40)第42頁，共50頁，2023年，2月20日，星期二現(xiàn)在將序列

與

作如下分解：

(4.41)

(4.42)第43頁，共50頁，2023年，2月20日，星期二由（4.39）式和（4.40）式，容易證明在(4.41)和(4.42)這兩個式子中，前一項(xiàng)都是偶序列，而后一項(xiàng)都是奇序列。將（4.