1、2022-3-6數(shù)字信號(hào)處理 陳鵬 32993401快速傅立葉變換快速傅立葉變換 Fast Fourier Transform (FFT)Lesson 142022-3-6數(shù)字信號(hào)處理 陳鵬 32993402復(fù)習(xí)提問(wèn)l時(shí)間抽取的時(shí)間抽取的FFT的兩條規(guī)則？的兩條規(guī)則？lFFT主要利用了什么的特性？主要利用了什么的特性？lFFT可分解多少級(jí)，每級(jí)有多少個(gè)蝶形單可分解多少級(jí)，每級(jí)有多少個(gè)蝶形單元，每個(gè)蝶形有多少次乘法和加法？元，每個(gè)蝶形有多少次乘法和加法？2022-3-6數(shù)字信號(hào)處理 陳鵬 32993403運(yùn)算量的比較運(yùn)算量的比較 pXm qXm1kNW pXm 1 qXm 1堞形計(jì)算流程圖 11

2、2DFTM2DFTMM2FFT MkmmNmkmmNmNNx nX kXpXpW XqXqXpW Xq任何一個(gè)的，都可以通過(guò)次分解最后稱為 點(diǎn)的來(lái)計(jì)算。次分解構(gòu)成了從到的級(jí)迭代計(jì)算，每級(jí)由個(gè)堞形組成。流出圖中每一個(gè)堞形的一般形式如右圖所示，其輸入和輸出之間滿足下列關(guān)系：NNMNNNMNF22log22log22FFTN，復(fù)數(shù)加法次數(shù)：復(fù)數(shù)乘法次數(shù)：計(jì)算的總運(yùn)算量為點(diǎn)的時(shí)間抽選完成此，法和兩次復(fù)數(shù)加法。因堞形計(jì)算需一次復(fù)數(shù)乘從上式看出，完成一個(gè)2022-3-6數(shù)字信號(hào)處理 陳鵬 32993404運(yùn)算量的比較運(yùn)算量的比較30/2/4/42283122411DFT NNNNNNNDNWWWjWjN

3、例如，當(dāng)時(shí)，需要 級(jí)迭代計(jì)算，共需要復(fù)數(shù)乘法次和復(fù)數(shù)加法次。考慮到，與這幾個(gè)系數(shù)相乘實(shí)際上不需要乘法運(yùn)算，所以實(shí)際的運(yùn)算量要更少。大多數(shù)情況下復(fù)數(shù)乘法所花時(shí)間最多，所以下面僅以復(fù)數(shù)乘法的計(jì)算次數(shù)為例來(lái)與直接計(jì)算進(jìn)行比較。直接計(jì)算需要的乘法次數(shù)為，于是有2222 loglog2N1024205DFTFFT205NFFTNDFDFNNNNN例如，當(dāng)時(shí)，則，即直接計(jì)算所需要復(fù)數(shù)乘法次數(shù)約為的倍，顯然， 越大，的速度優(yōu)勢(shì)越大。下表列出了不同值所對(duì)應(yīng)的兩種計(jì)算方法的復(fù)數(shù)乘法次數(shù)和它們的比值。2022-3-6數(shù)字信號(hào)處理 陳鵬 32993405運(yùn)算量的比較運(yùn)算量的比較N所需復(fù)數(shù)乘法次數(shù)所需復(fù)數(shù)乘法次數(shù)減少

4、乘法次數(shù)減少乘法次數(shù)的倍數(shù)的倍數(shù)直接計(jì)算直接計(jì)算DFT用用FFT計(jì)算計(jì)算DFT2414.041644.0864125.416256328.03210248012.864409619221.41281638444836.625665536102464.05122621442304113.8102410485765120204.82048419430411264372.42022-3-6數(shù)字信號(hào)處理 陳鵬 32993406DFT計(jì)算 0*10*00*11*11*01*11 *01 *11 *1.0011.:11.NNNNNNNNNNNNNNNWWWXxXxWWWX Nx NWWW2022-3-6數(shù)

5、字信號(hào)處理 陳鵬 32993407FFT計(jì)算計(jì)算 0 x 2x 4x 6x2NW0NW11 1x 3x 5x 7x2NW0NW113NW2NW1NW0NW1111 0X 1X 2X 3X 4X 5X 6X 7X10NW10NW10NW10NW2022-3-6數(shù)字信號(hào)處理 陳鵬 32993408蝶形的同址蝶形的同址(原位原位)計(jì)算計(jì)算FFT流程圖中包含流程圖中包含 級(jí)迭代運(yùn)算，每級(jí)由級(jí)迭代運(yùn)算，每級(jí)由 個(gè)蝶形計(jì)算構(gòu)個(gè)蝶形計(jì)算構(gòu)成。成。蝶形計(jì)算的優(yōu)點(diǎn)是可以進(jìn)行所謂的同址或原位計(jì)算蝶形計(jì)算的優(yōu)點(diǎn)是可以進(jìn)行所謂的同址或原位計(jì)算。現(xiàn)在來(lái)考慮。現(xiàn)在來(lái)考慮第一級(jí)的計(jì)算規(guī)律。設(shè)將輸入第一級(jí)的計(jì)算規(guī)律。設(shè)將輸入

6、分別存入計(jì)算機(jī)的存儲(chǔ)單元分別存入計(jì)算機(jī)的存儲(chǔ)單元中。首先，存儲(chǔ)單元中。首先，存儲(chǔ)單元 中的數(shù)據(jù)中的數(shù)據(jù) 進(jìn)入運(yùn)算器進(jìn)入運(yùn)算器并進(jìn)行蝶形運(yùn)算，并進(jìn)行蝶形運(yùn)算，由于以后的運(yùn)算不需要用到這兩個(gè)數(shù)據(jù)，因而不需由于以后的運(yùn)算不需要用到這兩個(gè)數(shù)據(jù)，因而不需要保留要保留。這樣，蝶形運(yùn)算后的結(jié)果便可以送到這樣，蝶形運(yùn)算后的結(jié)果便可以送到 存儲(chǔ)起來(lái)。存儲(chǔ)起來(lái)。類似地，類似地， 中的中的 進(jìn)入運(yùn)算器進(jìn)行蝶形運(yùn)算后送進(jìn)入運(yùn)算器進(jìn)行蝶形運(yùn)算后送回回 保存，等等。保存，等等。 7,3,5,1,6,2,4,0 xxxxxxxxN2log2/N 8,7,6,5,4,3,2,1MMMMMMMM 2,1 MM 4,0 xx 2

7、,1 MM 4,3 MM 6,2xx 4,3 MM2022-3-6數(shù)字信號(hào)處理 陳鵬 32993409蝶形的同址蝶形的同址(原位原位)計(jì)算計(jì)算第二級(jí)運(yùn)算與第一級(jí)類似，不過(guò)，第二級(jí)運(yùn)算與第一級(jí)類似，不過(guò)， 存儲(chǔ)單元中的數(shù)據(jù)存儲(chǔ)單元中的數(shù)據(jù)進(jìn)行蝶形運(yùn)算后的結(jié)果被送回到進(jìn)行蝶形運(yùn)算后的結(jié)果被送回到 保存，保存， 中的數(shù)據(jù)進(jìn)行蝶形運(yùn)算后結(jié)果送回到中的數(shù)據(jù)進(jìn)行蝶形運(yùn)算后結(jié)果送回到 保存，等等。保存，等等。這樣一直到最后一級(jí)的最后一個(gè)蝶形運(yùn)算完成。可以看出，這樣一直到最后一級(jí)的最后一個(gè)蝶形運(yùn)算完成。可以看出，每一每一級(jí)的蝶形的輸入與輸出在運(yùn)算的前后可以存儲(chǔ)在同一地址級(jí)的蝶形的輸入與輸出在運(yùn)算的前后可以存儲(chǔ)

8、在同一地址(原來(lái)位原來(lái)位置上置上)的存儲(chǔ)單元中，這種同址運(yùn)算的優(yōu)點(diǎn)是可以的存儲(chǔ)單元中，這種同址運(yùn)算的優(yōu)點(diǎn)是可以節(jié)省存儲(chǔ)單元節(jié)省存儲(chǔ)單元，從而降低對(duì)計(jì)算機(jī)存儲(chǔ)量的要求或降低硬件實(shí)現(xiàn)的成本。從而降低對(duì)計(jì)算機(jī)存儲(chǔ)量的要求或降低硬件實(shí)現(xiàn)的成本。 3,1 MM 3,1 MM 4,2 MM 4,2 MM2022-3-6數(shù)字信號(hào)處理 陳鵬 329934010變址計(jì)算變址計(jì)算從前面所示的從前面所示的FFT流程圖中可以看出，同址計(jì)算要求輸入流程圖中可以看出，同址計(jì)算要求輸入 是是“混序混序”排列的。所謂輸入為排列的。所謂輸入為“混序混序”，并不是說(shuō)輸入是雜亂無(wú)章的，并不是說(shuō)輸入是雜亂無(wú)章的，實(shí)際上它是有規(guī)律的。

9、如果輸入實(shí)際上它是有規(guī)律的。如果輸入 的序號(hào)用二進(jìn)制碼來(lái)表示，的序號(hào)用二進(jìn)制碼來(lái)表示，就可以發(fā)現(xiàn)就可以發(fā)現(xiàn)輸入的順序恰好是正序輸入的輸入的順序恰好是正序輸入的“碼位倒置碼位倒置”，下表列出了，下表列出了這種規(guī)律。這種規(guī)律。實(shí)際運(yùn)算中，按碼位倒置順序輸入數(shù)據(jù)實(shí)際運(yùn)算中，按碼位倒置順序輸入數(shù)據(jù) ，特別當(dāng)，特別當(dāng)N較大時(shí)，是較大時(shí)，是很不方便的。因此，數(shù)據(jù)總是按自然順序輸入存儲(chǔ)，然后很不方便的。因此，數(shù)據(jù)總是按自然順序輸入存儲(chǔ)，然后通過(guò)通過(guò)“變址變址”運(yùn)算將自然順序換成碼位倒置順序存儲(chǔ)運(yùn)算將自然順序換成碼位倒置順序存儲(chǔ)。 nx nx nx2022-3-6數(shù)字信號(hào)處理 陳鵬 329934011變址計(jì)算

10、變址計(jì)算碼位倒置順序碼位倒置順序自然順序自然順序二進(jìn)制表示二進(jìn)制表示碼位倒置碼位倒置碼位倒置順序碼位倒置順序x(0)x(000)x(000)x(0)x(1)x(001)x(100)x(4)x(2)x(010)x(010)x(2)x(3)x(011)x(110)x(6)x(4)x(100)x(001)x(1)x(5)x(101)x(101)x(5)x(6)x(110)x(011)x(3)x(7)x(111)x(111)x(7)2022-3-6數(shù)字信號(hào)處理 陳鵬 329934012實(shí)現(xiàn)由自然順序存儲(chǔ)到碼位倒置順序存儲(chǔ)的過(guò)程如下圖所示。實(shí)現(xiàn)由自然順序存儲(chǔ)到碼位倒置順序存儲(chǔ)的過(guò)程如下圖所示。圖中用圖中

11、用 表示自然順序的標(biāo)號(hào)，用表示自然順序的標(biāo)號(hào)，用 表示碼位倒置的標(biāo)號(hào)。表示碼位倒置的標(biāo)號(hào)。變址計(jì)算變址計(jì)算 1M 2M 3M 4M 5M 6M 7M 8M 1x 2x 3x 4x 5x 6x 7x 0 x 0 x 4x 2x 6x 1x 3x 5x 7x nx lx存儲(chǔ)單元變址自然順序輸入碼位倒置順序碼位倒置的變址處理nl2022-3-6數(shù)字信號(hào)處理 陳鵬 329934013變址計(jì)算變址計(jì)算當(dāng)當(dāng) 時(shí)，時(shí)， 和和 不必互相調(diào)換；不必互相調(diào)換；當(dāng)當(dāng) 時(shí)，將時(shí)，將 和和 進(jìn)行調(diào)換；進(jìn)行調(diào)換；當(dāng)當(dāng) 時(shí)，時(shí)， 和和 不能再進(jìn)行調(diào)換，因?yàn)榍懊嬉呀?jīng)將不能再進(jìn)行調(diào)換，因?yàn)榍懊嬉呀?jīng)將它們調(diào)換了一次了。它們調(diào)換了

12、一次了。這樣，按自然順序輸入的數(shù)據(jù)這樣，按自然順序輸入的數(shù)據(jù) 經(jīng)過(guò)變址計(jì)算后變成了碼經(jīng)過(guò)變址計(jì)算后變成了碼位倒置的順序排列，便可進(jìn)入第一級(jí)的蝶形運(yùn)算。可以位倒置的順序排列，便可進(jìn)入第一級(jí)的蝶形運(yùn)算。可以參看書(shū)參看書(shū)后附錄的后附錄的 C 語(yǔ)言程序語(yǔ)言程序?qū)崿F(xiàn)的實(shí)現(xiàn)的FFT算法。算法。nl lx nx nxnl nx lxnl nx lx2022-3-6數(shù)字信號(hào)處理 陳鵬 329934014時(shí)間抽取時(shí)間抽取基基2 FFT算法算法 0 x 2x 4x 6x2NW0NW11 1x 3x 5x 7x2NW0NW113NW2NW1NW0NW1111 0X 1X 2X 3X 4X 5X 6X 7X10NW1

13、0NW10NW10NW2022-3-6數(shù)字信號(hào)處理 陳鵬 329934015其它形式的其它形式的流程圖流程圖時(shí)間抽選時(shí)間抽選FFT算法還有另外一些形式的流程圖。對(duì)于任何流程圖，算法還有另外一些形式的流程圖。對(duì)于任何流程圖，只要只要保持各節(jié)點(diǎn)所連之路及其傳輸系數(shù)不變保持各節(jié)點(diǎn)所連之路及其傳輸系數(shù)不變，則不論節(jié)點(diǎn)位置怎樣排列，則不論節(jié)點(diǎn)位置怎樣排列，所得到的流程圖總是等效的，因而都能得到所得到的流程圖總是等效的，因而都能得到DFT的結(jié)果。把前面介紹的結(jié)果。把前面介紹的的FFT流程圖中流程圖中 x(4) 水平線和水平線和 x(1) 水平線互換，水平線互換， x(6) 水平線和水平線和 x(3) 水平

14、線互換水平線互換，其它不動(dòng)，則得到下圖所示的流程圖，顯然它的輸入是，其它不動(dòng)，則得到下圖所示的流程圖，顯然它的輸入是正序排列的，而輸出是碼位倒置排列的，所以輸出要進(jìn)行變址計(jì)算。正序排列的，而輸出是碼位倒置排列的，所以輸出要進(jìn)行變址計(jì)算。下圖所示的流程圖相當(dāng)于最初由庫(kù)利和圖基給出的時(shí)間抽選算法。下圖所示的流程圖相當(dāng)于最初由庫(kù)利和圖基給出的時(shí)間抽選算法。還有一種形式的流程圖是還有一種形式的流程圖是輸入輸出都是正序排列的輸入輸出都是正序排列的，但這類流程圖，但這類流程圖不不能進(jìn)行同址計(jì)算能進(jìn)行同址計(jì)算，它需要兩列長(zhǎng)度為，它需要兩列長(zhǎng)度為 N 的復(fù)數(shù)存儲(chǔ)器。的復(fù)數(shù)存儲(chǔ)器。2022-3-6數(shù)字信號(hào)處理

15、陳鵬 329934016“順序順序”輸入和輸入和“混序混序”輸出輸出 0 x 2x 4x 6x2NW0NW11 1x 3x 5x 7x2NW0NW113NW2NW1NW0NW1111 0X 1X 2X 3X 4X 5X 6X 7X10NW10NW10NW10NW算法流程圖另一種時(shí)間抽選FFT2022-3-6數(shù)字信號(hào)處理 陳鵬 329934017頻率抽取頻率抽取基基2 FFT算法算法2022-3-6數(shù)字信號(hào)處理 陳鵬 329934018頻率抽取頻率抽取基基2 FFT算法算法下面介紹頻率抽選基下面介紹頻率抽選基2FFT算法。這種算法簡(jiǎn)稱為頻率抽算法。這種算法簡(jiǎn)稱為頻率抽取取FFT算法。它的推導(dǎo)過(guò)程

16、遵循以下兩條規(guī)則：算法。它的推導(dǎo)過(guò)程遵循以下兩條規(guī)則：(1) 對(duì)時(shí)對(duì)時(shí)間進(jìn)行前后分解間進(jìn)行前后分解；(2) 對(duì)頻率進(jìn)行奇偶分解對(duì)頻率進(jìn)行奇偶分解。設(shè)設(shè) ，M 為正整數(shù)。為了推導(dǎo)方便，取為正整數(shù)。為了推導(dǎo)方便，取 ，即離散時(shí)間信號(hào)為即離散時(shí)間信號(hào)為kNWMN2823N 7,6,5,4,3,2,1,0 xxxxxxxxnx2022-3-6數(shù)字信號(hào)處理 陳鵬 329934019頻率抽取頻率抽取基基2 FFT算法算法按照規(guī)則按照規(guī)則(1)，將序列，將序列 分為前一半和后一半，即分為前一半和后一半，即這樣這樣 7,6,5,43,2,1,0 xxxxxxxx nxDFT式子不是注意這個(gè) 12/012/01

17、2/012/0212/012/12/01021212NnknNkNnknNkNnknNNnknNNkNNnknNNNnknNNnknNNnnkNWNnxnxWNnxWnxWNnxWWnxWnxWnxWnxkX2022-3-6數(shù)字信號(hào)處理 陳鵬 329934020頻率抽取頻率抽取基基2 FFT算法算法NjNeW2 /2 1220/2 1/20(2)0 ,2 ,4 ,61 ,3 ,5 ,7221212 ,0,1,2,12221Nrn rNnNnrNnX kX kXXXXXXXXXrXrNXrx nx nWNNx nx nWrXrx n 按照規(guī)則，將按奇偶分，即如果用和分別表示頻率的偶數(shù)項(xiàng)和奇數(shù)項(xiàng)，

18、則有 /2 121210/2 1/2012 ,0,1,2,122NrnrNnNnnrNNnNx nWNNx nx nW Wr 2022-3-6數(shù)字信號(hào)處理 陳鵬 329934021頻率抽取頻率抽取基基2 FFT算法算法NjNeW2 /2 1/20/2 1/202 ,0,1,2,1222 ,0,1,2,1221DFT2NrnNnNnrnNNnNg nx nx nNnNh nx nx nXrg n WNnXrh n WWN令得到上兩式所表示的是點(diǎn)的。在實(shí)際計(jì)算中， ,DFT2DFTnnNNg nh nNh n Wg nh n W首先形成序列和然后計(jì)算最后計(jì)算和的點(diǎn)的，便得到偶數(shù)輸出點(diǎn)和奇數(shù)輸出點(diǎn)的

19、。計(jì)算流程圖如下圖所示。2022-3-6數(shù)字信號(hào)處理 陳鵬 329934022頻率抽取頻率抽取基基2 FFT算法算法1111DFT2點(diǎn)NDFT2點(diǎn)N 0 x 2x 4x 6x 1x 3x 5x 7x 0X 4X 2X 6X 7X 1X 5X 3X3NW2NW1NW0NW)8(DFT2/DFTNNN計(jì)算的頻率抽選流程圖點(diǎn)的分解成兩個(gè)點(diǎn)2022-3-6數(shù)字信號(hào)處理 陳鵬 329934023頻率抽取頻率抽取基基2 FFT算法算法 14/02/12/4/2/42/14/02/12/4/2/14/02/41 4 DFT4/DFT2/DFT2/2/2NnknNkNNnknNkNNNnknNNNnknNNn

20、knNWNngngWNngWWngWngWngkGngNNNNN分為前后兩組，得到將：來(lái)求得。推導(dǎo)過(guò)程如下點(diǎn)的成兩個(gè)可以分解點(diǎn)的數(shù)組，也就是將輸出再分為偶數(shù)組和奇的點(diǎn)仍是偶數(shù)，可以將的整數(shù)冪，所以是由于2022-3-6數(shù)字信號(hào)處理 陳鵬 329934024頻率抽取頻率抽取基基2 FFT算法算法NjNeW2 的流程圖。點(diǎn)的個(gè)繼續(xù)分解成的將兩個(gè)。這樣可得到下圖所示點(diǎn)的是上面式子表示的計(jì)算都通過(guò)類似的推導(dǎo)可得率的偶數(shù)項(xiàng)為再進(jìn)行奇偶分，則得頻對(duì)頻率DFT44DFTDFT214, 2 , 1 , 0,41214, 2 , 1 , 0,4214, 2 , 1 , 0,41214, 2 , 1 , 0,42

21、14/04/24N14/04/4N14/04/214/04/N/N/NrWWWNnhWnhrHNrWWNnhWnhrHNrWWNngngrGNrWNngngrGkXNnrnNnNnNnNNnrnNnNnNNnrnNnNNnrnN2022-3-6數(shù)字信號(hào)處理 陳鵬 329934025頻率抽取頻率抽取基基2 FFT算法算法11111111DFT4點(diǎn)N 0 x 2x 4x 6x 1x 3x 5x 7x 0X 2X 4X 6X 7X 1X 3X 5X3NW2NW1NW0NWDFT4點(diǎn)NDFT4點(diǎn)NDFT4點(diǎn)N0NW2NW0NW2NW)8(DFT4/DFTNNN的頻率抽選點(diǎn)的經(jīng)兩次分解成四個(gè)點(diǎn)2022-

22、3-6數(shù)字信號(hào)處理 陳鵬 329934026頻率抽取頻率抽取基基2 FFT算法算法流程圖兩點(diǎn)DFT形單元有所不同。單元與時(shí)間抽選中的蝶運(yùn)算，但是這里的蝶形圖的基本運(yùn)算也是蝶形流程算法一樣，下圖所示的與時(shí)間抽選的流程圖如下圖所示。點(diǎn)的完整的流程圖代入上圖就得到示，將所有兩點(diǎn)如右圖所的，不能再分解了，兩點(diǎn)的就是兩點(diǎn)點(diǎn)的，所以上圖中因?yàn)镕FTFFT8DFTDFTDFTDFT4/8NN 0X 4X10NW與時(shí)間抽選一樣，頻率抽選與時(shí)間抽選一樣，頻率抽選FFT算法也算法也具有同址計(jì)算的優(yōu)點(diǎn)具有同址計(jì)算的優(yōu)點(diǎn)。但是，。但是，與時(shí)間抽選不同的是，頻率抽選與時(shí)間抽選不同的是，頻率抽選FFT算法的信號(hào)算法的信號(hào)

23、輸入為正序輸入為正序排列，輸排列，輸出為碼位倒置排列，因此，出為碼位倒置排列，因此，輸出要進(jìn)行變址計(jì)算輸出要進(jìn)行變址計(jì)算。2022-3-6數(shù)字信號(hào)處理 陳鵬 329934027蝶形單元對(duì)比 pXm qXm1kNW pXm 1 qXm 110NW pXm qXm pXm 1 qXm 1時(shí)間抽取的方法時(shí)間抽取的方法頻率抽取的方法頻率抽取的方法2022-3-6數(shù)字信號(hào)處理 陳鵬 329934028頻率抽取頻率抽取基基2 FFT算法算法11111111 0 x 2x 4x 6x 1x 3x 5x 7x 0X 4X 2X 6X 7X 1X 5X 3X3NW2NW1NW0NW0NW2NW0NW2NW0NW

24、0NW0NW0NW1111)8(FFTN流程圖頻率抽選的2022-3-6數(shù)字信號(hào)處理 陳鵬 329934029頻率抽取頻率抽取基基2 FFT算法算法元頻率抽選的堞形運(yùn)算單 rNmmmmmmWqXpXqXqXpXpX11 FFT流程圖，滿足以下關(guān)系算法的一般化的右圖所示的是頻率抽選的計(jì)算量是一樣的。選的算法的計(jì)算量與時(shí)間抽頻率抽選的復(fù)數(shù)加法次數(shù)：，復(fù)數(shù)乘法次數(shù)：量為個(gè)蝶形。因此，總計(jì)算級(jí)迭代運(yùn)算，每級(jí)有共有個(gè)流程圖次復(fù)數(shù)加法。圖示的整次復(fù)數(shù)乘法和括顯然，一個(gè)堞形計(jì)算包FFTFFTlog log2 2log 2 1 222NNNNNNFF10NW pXm qXm pXm 1 qXm 12022-3-6數(shù)字信號(hào)處理 陳鵬 329934030IFFT的計(jì)算的計(jì)算FFT算法同樣可以用于算法同樣可以用于IDFT的計(jì)算，稱為的計(jì)算，稱為快速傅里葉反變換快速傅里葉反變換，簡(jiǎn)寫(xiě)為，簡(jiǎn)