數(shù)字信號(hào)處理-課件 第5章 FFT快速傅氏變換

第5章FFT快速傅氏變換22十二月2024§5-6線性卷積的FFT算法§5-4DIF的FFT算法§5-5IFFT算法§5-2DFT的運(yùn)算量及改進(jìn)的途徑§5-1引言點(diǎn)擊進(jìn)入目錄§5-3按時(shí)間抽取(DIT)的FFT算法22十二月20245-1引言

DFT在實(shí)際應(yīng)用中很重要:可以計(jì)算信號(hào)的頻譜、功率譜和線性卷積等。直接按DFT變換進(jìn)行計(jì)算，當(dāng)序列長(zhǎng)度N很大時(shí)，計(jì)算量非常大，所需時(shí)間會(huì)很長(zhǎng)。FFT不是一種新的變換，而是DFT算法的一種改進(jìn),這種改進(jìn)實(shí)現(xiàn)了快速計(jì)算的目的

22十二月2024§5-2DFT的運(yùn)算量及改進(jìn)途徑5.2.1DFT的計(jì)算量估計(jì)兩公式基本結(jié)構(gòu)類似，其差別僅在指數(shù)的符號(hào)不同、及逆變換的因子1/N.22十二月2024

通常x(n)和 都是復(fù)數(shù),所以計(jì)算一個(gè)

X(k)的值需要N次復(fù)數(shù)乘法運(yùn)算,和 次復(fù)數(shù)加法運(yùn)算.一個(gè)X(k)的運(yùn)算量,如X(1)

計(jì)算全部X(k)就要N2次復(fù)數(shù)乘法運(yùn)算,N(N-1)次復(fù)數(shù)加法運(yùn)算.

當(dāng)N很大時(shí),運(yùn)算量將是驚人的,如N=1024,則要完成1048576次(一百多萬(wàn)次)運(yùn)算.這樣,難以做到實(shí)時(shí)處理.22十二月2024運(yùn)算量估計(jì)結(jié)論1.乘法運(yùn)算的時(shí)間是加法的一個(gè)量級(jí)以上2.DFT運(yùn)算量與成正比1)N降低運(yùn)算量的措施:2)利用的有關(guān)特性運(yùn)算量（有效途徑）22十二月20245.2.1降低運(yùn)算量的途徑

1.利用的特性得:周期性:可約性:對(duì)稱性:利用上述特性,可以將有些項(xiàng)合并.22十二月20242.將DFT分解為短序列可以有效降低運(yùn)算量,提高運(yùn)算速度.1965年,cooley和Tukey首先提出FFT算法.對(duì)于N點(diǎn)DFT,僅需(N/2)log2N次復(fù)數(shù)乘法運(yùn)算.

如:N=1024=210

，需要計(jì)算的次數(shù)是:(1024/2)log2210=512*10=5120次而5120/1048576=4.88%

速度提高20倍22十二月2024§5-3按時(shí)間抽取(DIT)FFT算法

—庫(kù)利-圖基算法算法原理按時(shí)間抽取基-2FFT算法與直接計(jì)算DFT運(yùn)算量的比較按時(shí)間抽取的FFT算法的特點(diǎn)按時(shí)間抽取FFT算法的其它形式流程圖22十二月2024§5-3按時(shí)間抽取(DIT)的FFT算法

—庫(kù)利-圖基算法5.3.1算法原理(基2-FFT)因此，n為偶數(shù)時(shí):n為奇數(shù)時(shí):1.N點(diǎn)DFT分解為兩個(gè)N/2點(diǎn)DFT(1)先將按n的奇偶分為兩組作DFT,設(shè)N=2L,不足時(shí),可補(bǔ)些零。這樣有:22十二月2024由于:(n為偶數(shù))

(n為奇數(shù))所以,上式可表示為:22十二月2024(2)兩點(diǎn)結(jié)論:①X1(k),X2(k)均為N/2點(diǎn)DFT。

其中:12kN②X(k)=X

(k)+W

X

(k)能確定出

X(k)的k=個(gè)；即前一半點(diǎn)的結(jié)果。22十二月2024(3)X(k)的后一半的確定由于（周期性）,所以:同理:22十二月2024

可見(jiàn),X(k)的后一半，也完全由X1(k),X2

(k)所確定。

N點(diǎn)DFT可由兩個(gè)N/2點(diǎn)的DFT來(lái)計(jì)算.又由于

,所以22十二月2024實(shí)現(xiàn)上式運(yùn)算的流圖稱作蝶形運(yùn)算(4)蝶形運(yùn)算（N/2個(gè)蝶形)

前一半

后一半由X1(k)、X2(k)表示X(k)的運(yùn)算是一種特殊的運(yùn)算-碟形運(yùn)算什么是蝶形運(yùn)算?22十二月2024例1(前一半)

(后一半)1111-1根據(jù)蝶形運(yùn)算算法畫(huà)出蝶形運(yùn)算圖解:22十二月2024例2以N=8為例,根據(jù)碟形圖,分析N點(diǎn)DFT經(jīng)過(guò)第一次分解,FFT計(jì)算全過(guò)程:解:1111-1先復(fù)習(xí)基本碟形運(yùn)算:因此,共N/2個(gè)蝶形運(yùn)算k=0,1,2…

均有一個(gè)碟形運(yùn)算22十二月2024N=8,從第一次分解,看FFT計(jì)算過(guò)程:(1)由x1(n)求X1(k)(2)由x2(n)求X2(k)DFTDFT乘法次數(shù):4

2乘法次數(shù):4222十二月2024(3)由X1(k),X2(k)求X(k)k=0,可求出:k=1,可求出:k=2,可求出:k=3,可求出:每個(gè)碟運(yùn)算1次乘法乘法次數(shù)N/2=422十二月2024第一次分解,稱為第一級(jí)碟形運(yùn)算X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)NW2NW1WN0-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)NW322十二月2024(1)N/2點(diǎn)的DFT運(yùn)算量:復(fù)乘次數(shù):(4)計(jì)算量分析復(fù)乘:總共運(yùn)算量:分析N點(diǎn)序列經(jīng)過(guò)一次奇、偶分組后的乘法計(jì)算量：N點(diǎn)DFT的復(fù)乘為N2;僅經(jīng)過(guò)一次分解,計(jì)算量減少近一半(2)兩個(gè)N/2點(diǎn)的DFT運(yùn)算量:復(fù)乘次數(shù):

(3)N/2個(gè)蝶形運(yùn)算的運(yùn)算量:復(fù)乘次數(shù):例4N點(diǎn)序列經(jīng)過(guò)一次奇、偶分組后成為了2個(gè)N/2點(diǎn)的序列解22十二月2024以N=8為例

DFT分解為兩個(gè)N/2=4點(diǎn)的DFT的計(jì)算過(guò)程如下.22十二月2024

由X1(k)和X2(k),計(jì)算X(k)的全過(guò)程如下:

x1(0)=x(0)

x1(1)=x(2)

x1(2)=x(4)

x1(3)=x(6)

x2(0)=x(1)

x2(1)=x(3)

x2(2)=x(5)

x2(3)=x(7)

第一次分解,稱為第一級(jí)碟形運(yùn)算N/2點(diǎn)DFT

X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)NW2NW1WN0-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)N/2點(diǎn)DFT

NW322十二月2024第一次分解之后小結(jié):一個(gè)N點(diǎn)的序列,分解成兩個(gè)N/2點(diǎn)的序列對(duì)每一個(gè)N/2點(diǎn)的序列的計(jì)算,依然采用了傳統(tǒng)的DFT算法經(jīng)一次分解之后,復(fù)數(shù)乘法次數(shù):N2/2+N/2算法量下降近一半,還需要繼續(xù)改進(jìn)算法繼續(xù)對(duì)子序列再分解按第一次分解方法類比,繼續(xù)分解直至每一序列為2點(diǎn)止.22十二月2024概念:蝶形信號(hào)線(節(jié)點(diǎn))之距離什么是蝶形信號(hào)線距離?4距離=4NW2NW1WN0NW3-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)22十二月2024例5分析N點(diǎn)(8點(diǎn))序列經(jīng)過(guò)一次奇偶分組后蝶形運(yùn)算有哪些特點(diǎn)?

x1(0)

x1(1)

x1(2)

x1(3)

N/2點(diǎn)DFT

X1(0)X1(1)X1(2)X1(3)

x2(0)

x2(1)

x2(2)

x2(3)

N/2點(diǎn)DFT

X2(0)X2(1)X2(2)X2(3)1)N個(gè)信號(hào)線,組成N/2個(gè)蝶形.2)每一蝶形節(jié)點(diǎn)之間的距離為N/2.NW2NW1WN0NW3-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)22十二月2024

由于N=2

L，因此，無(wú)論x1(n)還是x2(n),

每一個(gè)N/2點(diǎn)的序列可繼續(xù)分解為兩個(gè)N/4的子序列,以序列x1(n)為例,可以分解如下:5.3.2序列的第2次分解對(duì)N/4點(diǎn)的序列x3(n),x4(n),分別進(jìn)行DFT運(yùn)算,得到(偶中偶)(偶中奇)22十二月2024從而可得到X1(k)的前N/4點(diǎn)X1(k)的后N/4點(diǎn)為:22十二月2024第二次分解,每個(gè)N/2點(diǎn)的序列分解為2個(gè)N/4點(diǎn)的序列第2次分解后,時(shí)域序列的排列順序?第1次分解,時(shí)域序列排列順序先看序列x1(n)對(duì)應(yīng)原序列x(n)設(shè)序列x1(n)分解為x3(n)和x4(n)兩個(gè)序列22十二月2024接下來(lái),再看序列x2(n)上面的順序,對(duì)應(yīng)原序列x(n)的哪些值呢?x2(n)按序號(hào)的奇偶排隊(duì)如下:設(shè)序列x2(n)分解為x5(n)和x6(n)兩個(gè)序列x5(n)x6(n)22十二月202422十二月2024

(0)=

(0)=(0)

(1)=

(2)=(4)

(0)=

(1)=(2)

(1)=

(3)=(6)

(0)=

(0)=(1)

(1)=

(2)=(5)

(0)=

(1)=(3)

(1)=

(3)=(7)3131414152526262因此x1(n),x2(n)兩個(gè)N/2點(diǎn)的序列按碟形圖進(jìn)行計(jì)算,則有:N/2點(diǎn)DFTN/2點(diǎn)DFTWWWW0123NNNN-1-1-1-1X

(0)X

(1)X

(2)X

(3)X

(0)X

(1)X

(2)X

(3)11122221X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)-1-1-1-1N/4DFTN/4DFTN/4DFTN/4DFTX

(0)X

(1)X

(0)X

(1)334402NWWNX

(0)X

(1)X

(0)X

(1)556602NWWN22十二月2024

結(jié)論：第2次分解后,得到4個(gè)N/4點(diǎn)DFT

對(duì)于N=8點(diǎn)的DFT,N/4點(diǎn)即為2點(diǎn)DFT,因此

22十二月2024

代入展開(kāi)，可得：

X

(0)X

(1)X

(0)X

(1)3344WN0WN2-1-1X

(0)X

(1)X

(0)X

(1)5566WN0WN2-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)

(0)

(4)

(2)

(6)

(1)

(5)

(3)

(7)X

(0)X

(1)X

(2)X

(3)X

(0)X

(1)X

(2)X

(3)11121222WWWWN0N1N2N3-1-1-1-1因此,8點(diǎn)DFT的FFT的運(yùn)算流圖如下：

第三次分解第二次分解第一次分解第一級(jí)運(yùn)算第二級(jí)運(yùn)算第三級(jí)運(yùn)算-1WN0-1WN0-1WN0-1WN022十二月2024

這種FFT算法,是在時(shí)間上對(duì)輸入序列

的次序是偶數(shù)還是奇數(shù)進(jìn)行分解,故稱為按時(shí)間抽取的算法(DIT)。

22十二月20245.3.2DIT的運(yùn)算量例6FFT運(yùn)算計(jì)算量估計(jì)N=8需三級(jí)蝶形運(yùn)算

N=23=8,N=2L

共需L(L=3)級(jí)蝶形運(yùn)算

每級(jí)都由N/2個(gè)蝶形運(yùn)算組成,每個(gè)蝶形運(yùn)算有一次復(fù)乘.從一個(gè)例題開(kāi)始,分析FFT運(yùn)算量22十二月2024

因此,N點(diǎn)的FFT的運(yùn)算量為:復(fù)乘:mF

=（N/2）L=（N/2）log2N（復(fù)加:aF=N

L=Nlog2

N）DFT與FFT運(yùn)算量之比較：N2/(N/2)log2N=2N/log2N

因此，N越大，運(yùn)算量節(jié)省更明顯。如教材第5章表5-1所示。22十二月2024

1.倒位序現(xiàn)象

由圖可知,輸出X(k)按正常順序排列在存儲(chǔ)單元,而輸入是按順序:這種順序稱作倒位序,即二進(jìn)制數(shù)倒位。5.3.3DIT算法的特點(diǎn)22十二月2024

因奇偶分組造成的,以N=8為例分析如下:第1次分組第2次分組第3次分組000011110100110011010101=0=4=2=6=1=5=3=7N=8時(shí)，序號(hào)需要3位二進(jìn)制數(shù)表示22十二月202401234567自然順序n二進(jìn)制

倒位序

倒位順序n^0

0

00

0

10

1

00

1

11

0

01

0

11

1

01

1

10

0

010

00

1

011

0

0

01

1

0

10

1

11

1

104261537輸入數(shù)據(jù)、中間運(yùn)算結(jié)果和最后輸出均用同一存儲(chǔ)器。2.原位運(yùn)算22十二月2024DIT基2-FFT算法與DFT直接計(jì)算運(yùn)算量比較

DIT基-2FFT的信號(hào)流圖可知，當(dāng)N=2L時(shí)，共有

級(jí)蝶形運(yùn)算；每級(jí)都由

個(gè)蝶形運(yùn)算組成，而每個(gè)蝶形有

次復(fù)乘、

次復(fù)加，因此每級(jí)運(yùn)算都需

次復(fù)乘和

次復(fù)加。LN/2

N/2

12N22十二月2024這樣

級(jí)運(yùn)算總共需要：L復(fù)數(shù)乘法：

復(fù)數(shù)加法：

直接DFT算法運(yùn)算量復(fù)數(shù)乘法：

復(fù)數(shù)加法：

N2N(N－1)直接計(jì)算DFT與FFT算法的計(jì)算量之比為M22十二月2024FFT算法與直接DFT算法運(yùn)算量的比較NN2計(jì)算量之比MNN2計(jì)算量之比M2414.01281638444836.641644.025665536102464.0864125.45122621442304113.816256328.0102410485765120204.83210288012.82048419430411264372.464404919221.422十二月20243.蝶形運(yùn)算兩節(jié)點(diǎn)的距離:2m-1

其中,m表示第m列,且m

=1,…,L

例如N=8=23,

第一級(jí)(列)距離為21-1=1,

第二級(jí)(列)距離為22-1=2，

第三級(jí)(列)距離為23-1=4。

4.的確定

在DIT完整蝶形運(yùn)算圖中，第m級(jí)蝶形運(yùn)算兩節(jié)點(diǎn)的“距離”為2m-1，因而式（5-23）可寫(xiě)成如下形式對(duì)于程序?qū)崿F(xiàn)，r值的遞推算法如下：（1）將上式蝶形運(yùn)算兩節(jié)點(diǎn)的第1個(gè)節(jié)點(diǎn)標(biāo)號(hào)k表示成L位二進(jìn)制數(shù)；（2）將二進(jìn)制數(shù)左移L-m位，右邊空位補(bǔ)零(即乘2L-m)（3）將所得二進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)，該數(shù)即為r值。5.3.4DIT其他形式的流圖1.DIT正常算法的流程圖對(duì)于FFT算法流圖，若各節(jié)點(diǎn)的連接支路以及支路系數(shù)不變，則無(wú)論各節(jié)點(diǎn)和支路如何變形（改變空間位置），其算法和運(yùn)算量均不會(huì)改變。22十二月20242.DIT其它形式的流圖對(duì)于DIT輸出正常順序,輸入倒位序的蝶形運(yùn)算流圖，按如下兩個(gè)步驟改變支路的物理位置（不改變節(jié)點(diǎn)的鏈接支路）。（1）將第2根水平線和第5根水平線平移互換位置，即x(4)水平相連的所有節(jié)點(diǎn)和x(1)水平相連的所有節(jié)點(diǎn)（包括輸入數(shù)據(jù)和輸出數(shù)據(jù)節(jié)點(diǎn)）互換位置，（2）將第4根水平線和第7根水平線平移互換位置，即x(6)水平相連的所有節(jié)點(diǎn)和x(3)水平相連的所有節(jié)點(diǎn)互換位置，該互換也包括輸入數(shù)據(jù)和輸出數(shù)據(jù)節(jié)點(diǎn)。

可得如下所示蝶形運(yùn)算流圖。2.DIT其它形式的流圖DIT基-2FFT算法輸入自然順序、輸出倒位序的FFT流圖22十二月2024在不改變上圖各節(jié)點(diǎn)的支路連接數(shù)量和連接方式的原則下，繼續(xù)改變某些節(jié)點(diǎn)和支路的空間位置，則可以得到輸入和輸出均為正常順序的FFT蝶形運(yùn)算圖,如下所示:2.DIT其它形式的流圖

用蝶形圖計(jì)算FFT,已知序列x(n)如下：

x(n)=[1，2，1，1]x(n)為4點(diǎn)長(zhǎng)序列，根據(jù)DIT基-2算法，其完整蝶形圖如下:虛線左邊為第一級(jí)蝶形運(yùn)算，從上往下4個(gè)節(jié)點(diǎn)的結(jié)果如下：1+1=2，1-1=0，2+1=3，2-1=1虛線右邊為第二級(jí)運(yùn)算，第二級(jí)運(yùn)算結(jié)果如下：例7解:22十二月2024§5-4DIF的FFT算法(桑德—圖基算法)5.4.1算法原理1.N點(diǎn)DFT的另一種表達(dá)形式22十二月2024

因此

X(k)可表為:

22十二月2024

2.N點(diǎn)DFT按k的奇偶分組可分為兩個(gè)N/2的DFT

k為偶數(shù)時(shí)：

當(dāng)k為偶數(shù),即

k=2r時(shí),(-1)k=1；

當(dāng)k為奇數(shù),即k=2r+1時(shí)(-1)k=-1

。這時(shí)

X(k)

可分為兩部分：

22十二月2024

可見(jiàn),上面兩式均為N/2的DFT。k為奇數(shù)時(shí)：22十二月20243.蝶形運(yùn)算-1蝶形運(yùn)算圖表示法之一22十二月2024蝶形運(yùn)算圖形表示法之二22十二月20244.N=8時(shí),按k的奇偶分解過(guò)程X1(0)X1(1)X1(2)X1(3)-1-1-1-1WWWWNNNN0123先蝶形運(yùn)算，后N/2點(diǎn)DFT運(yùn)算:22十二月2024

5.類比DIT算法分解過(guò)程如此進(jìn)行下去,直至分解為2點(diǎn)DFT

將N/2點(diǎn)DFT繼續(xù)按k的奇偶分解為兩個(gè)N/4點(diǎn)的DFT22十二月2024

(0)

(1)

(2)

(3)

(4)

(5)

(6)

(7)-1WWWWNNNN0123WWWWNNNN0202N=8點(diǎn)的DIF的FFT流圖分析第一次分解第二次分解第三次分解第一級(jí)運(yùn)算第二級(jí)運(yùn)算第三級(jí)運(yùn)算-1-1-1-1-1-1-1-1-1-1-1-1X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)例8解:22十二月2024由上述分析可知,N=8需三級(jí)蝶形運(yùn)算N=23=8,由此可知,N=2L

共需L級(jí)蝶形運(yùn)算而且每級(jí)都由N/2個(gè)蝶形運(yùn)算

組成,每個(gè)蝶形運(yùn)算有一次復(fù)乘。6.DIF算法的運(yùn)算量22十二月2024

因此,N點(diǎn)的FFT的運(yùn)算量為復(fù)乘:mF=（N/2）L=（N/2）log2N（復(fù)加:aF=NL=Nlog2N）DFT與FFT運(yùn)算量之比較：N2/(N/2)log2N=2N/log2N

因此，N越大，運(yùn)算量節(jié)省更明顯。22十二月2024

1.

原位運(yùn)算

每級(jí)(列)都是由N/2個(gè)蝶形運(yùn)算構(gòu)成,即:

-1WNr5.4.2DIF算法的特點(diǎn)22十二月20242.蝶形運(yùn)算兩節(jié)點(diǎn)的距離

一般公式為2L-m=N/2m

例如N=23=8

：

(1)m=1時(shí)的距離為

8/2=4；

(2)m=2

時(shí)的距離為

8/4=2;

(3)m=3

時(shí)的距離為

8/8=1。22十二月2024r的求法：

k=(n2n1n0),左移m-1位,右邊空出補(bǔ)零,得(r)2,亦即(r)2=(k)2

2m-1.例如,N=8:(1)m=1,k=2,k=(010)2

左移0位,(r)2=(010)2=2;(2)m=2,k=1,k=(001)2

左移1位,(r)2=(010)2=2;(3)m=2,k=0,k=(001)2

左移1位,(r)2=(010)2=2.3.

的計(jì)算

由于DIF蝶形運(yùn)算的兩節(jié)點(diǎn)的距離為

N/2m,

所以蝶形運(yùn)算可表為：22十二月20241.相同點(diǎn)

(1)都要求序列長(zhǎng)度滿足條件N=2L(2)均需要L次分解，均包含L級(jí)運(yùn)算

(3)總運(yùn)算量相同,均為（N/2)

Log2N次復(fù)乘

(4)編程時(shí)都可以進(jìn)行原位運(yùn)算；5.4.3DIF與DIT算法的比較比較如下:22十二月20242.不同點(diǎn)

(1)如無(wú)特別說(shuō)明，DIT算法的輸入為倒位序,輸出為自然順序；

DIF算法正好與DIT算法相反。但經(jīng)過(guò)改進(jìn)DIT算法也有輸入為自然順序,輸出為倒位序的情況。22十二月2024(2)蝶形運(yùn)算不同用矩陣表示=11a.DIT先乘法運(yùn)算，后求和運(yùn)算22十二月2024b.DIF用矩陣表示=11先求和運(yùn)算，后乘法運(yùn)算22十二月2024(3)兩種蝶形運(yùn)算的關(guān)系

互為轉(zhuǎn)置（矩陣）；

將流圖的所有支路方向都反向,交換輸入和輸出，即可得到另一種蝶形。

a.(DIT)11b.(DFT)1122十二月20245.4.4IFFT算法1.觀察DFT和IDFT運(yùn)算的差異

22十二月2024

比較以上兩式可知，正變換和反變換差別為：

（1）正、反變換求和式指數(shù)符號(hào)不同，分別為：和

（2）反變換系數(shù)（常數(shù)）1/N，正變換系數(shù)為1。

結(jié)論：在DFT快速算法的基礎(chǔ)上，考慮以上兩點(diǎn)即可得到IDFT快速算法。

22十二月20241)可以將常數(shù)1/N分配到每級(jí)蝶型運(yùn)算中,∵,也就是每級(jí)蝶形運(yùn)算乘法運(yùn)算均乘以1/2。2.IFFT快速算法之一（以DIF為例）2)將換為，即每級(jí)蝶型運(yùn)算的乘法因子換為。正好等于IFFT快速算法中的因子1/N。22十二月2024

X(0)(0)

X(1)(4)

X(2)(2)

X(3)(6)

X(4)(1)

X(5)(5)

X(6)(3)

X(7)(7)-1-1-1-1WWWWNNNN0-1-2-3-1-1-1-1WWWWNNNN0-20-2-1-1-1-1WWWWNNNN0000N=8時(shí)IDFT流圖如下：22十二月20243.IFFT快速算法之二

22十二月20243.IFFT快速算法之二

22十二月2024

即：

1）先將X(k)取共軛,直接利用FFT程序計(jì)算DFT；

2）求得DFT后再取一次共軛；并乘以1/N,即得x(n)。結(jié)論：

1)在FFT程序的基礎(chǔ)上,在給定的已知數(shù)據(jù)處增加一組循環(huán)語(yǔ)句，求X(k)的共軛；

2)在得出結(jié)果處增加一組循環(huán)語(yǔ)句，對(duì)結(jié)果求共軛并乘以1/N;22十二月2024

§5-5

基4-FFT算法5.5.1基-4FFT算法原理

基-2FFT算法的原理是將N點(diǎn)的序列一分為二，一個(gè)N點(diǎn)DFT被分解為兩個(gè)N/2點(diǎn)DFT的組合，再將N/2點(diǎn)DFT又一分為二，分解為4個(gè)N/4點(diǎn)的DFT，直至全部分解為兩點(diǎn)DFT為止。基-4FFT的思路與基-2FFT的思路基本類似，不同點(diǎn)是將N點(diǎn)的序列一分為四，再對(duì)各子序列繼續(xù)一分為四，直至分解到全部子序列為4點(diǎn)為止。22十二月2024因此，類似于DIT基-2的分解過(guò)程，DIT基-4快速算法先將長(zhǎng)度為N=4L的序列x(n)，按如下方式分為四個(gè)子序列：因此，DFT變換公式改變?yōu)槿缦滦问?.5.1基-4FFT算法原理

22十二月20245.5.1基-4FFT算法原理

根據(jù)WN的可約性，上式可以進(jìn)一步化為

根據(jù)N/4點(diǎn)DFT公式，上式可以表示為22十二月2024其中：類似DIT基-2算法的第一次分解，上只能計(jì)算出X(k)前四分之一的值,其余值的計(jì)算需根據(jù)WN的周期性以及有限長(zhǎng)序列隱含的周期性,類似DIT基2算法的方法，可得如下公式：22十二月2024由此可得基-4算法的基本碟形圖如下：22十二月2024DIT基-4快速算法基本蝶形運(yùn)算圖。為了加深理解，可以根據(jù)DIT基-2算法原理進(jìn)行類比。為了深入理解基-4FFT算法原理，以N=16為例分析基-4快速運(yùn)算流圖的規(guī)律。由于N=16=42，即L=2，流圖如下所示：由于僅需2次分解，經(jīng)過(guò)第一次分解之后，對(duì)于4個(gè)N/4點(diǎn)的DFT，各子序列長(zhǎng)度均為4點(diǎn)，正好是DIT基-4快速運(yùn)算的基本單元。根據(jù)基-4算法的原則，四點(diǎn)長(zhǎng)的子序列DFT采用基-2FFT運(yùn)算，這是基-4FFT的最后一次分解。由此可得,當(dāng)N=16=42時(shí)基-4算法的完整碟形運(yùn)算圖如下根據(jù)原理可得第一列左上角4點(diǎn)基-4快速算法的蝶形運(yùn)算如下圖。x(n)經(jīng)2次分解后，輸入為正常順序，輸出為二進(jìn)制倒位序圖中虛線框內(nèi)為一個(gè)4點(diǎn)基-4FFT流圖的基本單元22十二月2024

§5-6

線性卷積的FFT算法5.6.1線性卷積傳統(tǒng)計(jì)算方法

設(shè)一離散線性移不變系統(tǒng)的沖激響應(yīng)為

,其