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

離散傅里葉變換的矩陣表示及其運(yùn)算量第一頁，共五十頁，2022年，8月28日離散傅里葉變換對(duì)為：

(4.1) (4.2)式中

。

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

第二頁，共五十頁，2022年，8月28日

一般情況下，信號(hào)序列x(n)及其頻譜序列X(k)都是用復(fù)數(shù)來表示的，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ù)加法。

第三頁，共五十頁，2022年，8月28日顯然，直接計(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í)際問題中，N往往是較大的，因此有必要對(duì)DFT與IDFT的計(jì)算方法予以改進(jìn)。第四頁，共五十頁，2022年，8月28日

4.1.2因子的特性

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

1．周期性：

對(duì)離散變量n有同樣的周期性。第五頁，共五十頁，2022年，8月28日

2．對(duì)稱性：

或

3.其它:

第六頁，共五十頁，2022年，8月28日4.2基2時(shí)間抽選的FFT算法

4.2.1算法推導(dǎo)

已經(jīng)知道：

令DFT的長度N=2M，M為正整數(shù)。第七頁，共五十頁，2022年，8月28日令：

于是有：第八頁，共五十頁，2022年，8月28日其中，

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

第九頁，共五十頁，2022年，8月28日是由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范圍的情況。第十頁，共五十頁，2022年，8月28日現(xiàn)在令，故對(duì)于后半段有：

同理：

又知：

第十一頁，共五十頁，2022年，8月28日

圖

4.1N點(diǎn)DFT分解為兩個(gè)N/2點(diǎn)的DFT(N=8)第十二頁，共五十頁，2022年，8月28日

圖

4.2N/2點(diǎn)的DFT分解為兩個(gè)N/4點(diǎn)的DFT(N=8)第十三頁，共五十頁，2022年，8月28日綜上所述，可以得到：

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

第十四頁，共五十頁，2022年，8月28日

這樣，我們就將一個(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)次分解。第十五頁，共五十頁，2022年，8月28日?qǐng)D

4.32點(diǎn)

DFT信號(hào)流圖（蝶形圖）第十六頁，共五十頁，2022年，8月28日對(duì)于2點(diǎn)DFT，有：

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

4.2.2算法特點(diǎn)

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

第十九頁，共五十頁，2022年，8月28日現(xiàn)在將圖4.4中輸入序號(hào)以及重排后的序號(hào)按二進(jìn)制寫出如下（注：下標(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）的元素的位置相互交換。第二十頁，共五十頁，2022年，8月28日第二十一頁，共五十頁，2022年，8月28日

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ǔ)器。

第二十二頁，共五十頁，2022年，8月28日

3.運(yù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ù)為：第二十三頁，共五十頁，2022年，8月28日

復(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ù)，不超過直接計(jì)算DFT時(shí)復(fù)乘次數(shù)的千分之五。

第二十四頁，共五十頁，2022年，8月28日4.3基2頻率抽選的FFT算法

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

第二十五頁，共五十頁，2022年，8月28日

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

其中，

第二十六頁，共五十頁，2022年，8月28日第二十七頁，共五十頁，2022年，8月28日其中，

顯然，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所示。第二十八頁，共五十頁，2022年，8月28日將圖4.6與圖4.4比較，可知頻率抽選法的計(jì)算量與時(shí)間抽選法相同，而且都能夠同址計(jì)算。時(shí)間抽選法是輸入序列按奇偶分組，故x(n)的順序要按倒序重排，而輸出序列按前后分半，故X(k)的順序不需要重排；頻率抽選法則是輸出序列按奇偶分組，故X(k)的順序要按倒序重排，而輸入序列按前后分半，故x(n)不需要重排。第二十九頁，共五十頁，2022年，8月28日

4.5快速傅里葉反變換（IFFT）IFFT是IDFT的快速算法。由于DFT的正變換和反變換的表達(dá)式相似，因此IDFT也有相似的快速算法。可以用三種不同的方法來導(dǎo)出IFFT算法。方法1

設(shè)

，

則有：，n=0,1,┅,N-1第三十頁，共五十頁，2022年，8月28日根據(jù)基2FFT的時(shí)間抽選法的第一次分解的結(jié)果：第三十一頁，共五十頁，2022年，8月28日可以得到：第三十二頁，共五十頁，2022年，8月28日

圖

4.8由

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

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

將DFT的正變換式：

與其反變換式：

第三十五頁，共五十頁，2022年，8月28日比較，很容易知道，可以利用FFT算法的程序來計(jì)算IFFT，只需要將X(k)作為輸入序列，x(n)則是輸出序列，另外將因子WNk

變?yōu)閃N-k，

當(dāng)然，最后還必須將輸出序列的每個(gè)元素除以N。第三十六頁，共五十頁，2022年，8月28日

方法3

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

第三十七頁，共五十頁，2022年，8月28日與DFT的正變換式比較，可知完全可以利用FFT的計(jì)算程序，只需要將X*(k)作為輸入序列，并將最后結(jié)果取共軛，再除以N就得到x(n)。第三十八頁，共五十頁，2022年，8月28日4.7.1兩個(gè)長度相同的實(shí)序列

可以將兩個(gè)長度相同的實(shí)序列組合成一個(gè)復(fù)序列來進(jìn)行FFT運(yùn)算，從而一次完成這兩個(gè)實(shí)序列的FFT，減少了總的計(jì)算量。第三十九頁，共五十頁，2022年，8月28日

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

又設(shè)

，

，

則由DFT的線性有：(4.36)第四十頁，共五十頁，2022年，8月28日P(k)和G(k)這兩個(gè)復(fù)序列的實(shí)部都是周期性的偶序列，而其虛部都是周期性的奇序列。

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

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

(4.38)第四十一頁，共五十頁，2022年，8月28日由周期性有： (4.39)

(4.40)第四十二頁，共五十頁，2022年，8月28日現(xiàn)在將序列

與

作如下分解：

(4.41)

(4.42)第四十三頁，共五十頁，2022年，8月28日由（4.39）式和（4.40）式，容易證明在(4.41)和(4.42)這兩個(gè)式子中，前一項(xiàng)都是偶序列，而后一項(xiàng)都是奇序列。