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

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

(4.1) (4.2)式中

。

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

第2頁(yè)，共50頁(yè)，2023年，2月20日，星期二

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

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

4.1.2因子的特性

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

1．周期性：

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

2．對(duì)稱(chēng)性：

或

3.其它:

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

4.2.1算法推導(dǎo)

已經(jīng)知道：

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

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

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

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

同理：

又知：

第11頁(yè)，共50頁(yè)，2023年，2月20日，星期二

圖

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

圖

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

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

第14頁(yè)，共50頁(yè)，2023年，2月20日，星期二

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

4.32點(diǎn)

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

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

4.2.2算法特點(diǎn)

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

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

2.同址計(jì)算

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

第22頁(yè)，共50頁(yè)，2023年，2月20日，星期二

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

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

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

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

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

第25頁(yè)，共50頁(yè)，2023年，2月20日，星期二

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

其中，

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

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

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

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

設(shè)

，

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

圖

4.8由

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

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

將DFT的正變換式：

與其反變換式：

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

變?yōu)閃N-k，

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

方法3

對(duì)DFT的反變換式取共軛，有：

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

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

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

又設(shè)

，

，

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

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

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

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

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

與

作如下分解：

(4.41)

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