DSP_14離散傅立葉變換-FFT_2

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

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

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

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

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

6、分別存入計算機(jī)的存儲單元分別存入計算機(jī)的存儲單元中。首先，存儲單元中。首先，存儲單元 中的數(shù)據(jù)中的數(shù)據(jù) 進(jìn)入運算器進(jìn)入運算器并進(jìn)行蝶形運算，并進(jìn)行蝶形運算，由于以后的運算不需要用到這兩個數(shù)據(jù)，因而不需由于以后的運算不需要用到這兩個數(shù)據(jù)，因而不需要保留要保留。這樣，蝶形運算后的結(jié)果便可以送到這樣，蝶形運算后的結(jié)果便可以送到 存儲起來。存儲起來。類似地，類似地， 中的中的 進(jìn)入運算器進(jìn)行蝶形運算后送進(jìn)入運算器進(jì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ù)字信號處理 陳鵬 32993409蝶形的同址蝶形的同址(原位原位)計算計算第二級運算與第一級類似，不過，第二級運算與第一級類似，不過， 存儲單元中的數(shù)據(jù)存儲單元中的數(shù)據(jù)進(jìn)行蝶形運算后的結(jié)果被送回到進(jìn)行蝶形運算后的結(jié)果被送回到 保存，保存， 中的數(shù)據(jù)進(jìn)行蝶形運算后結(jié)果送回到中的數(shù)據(jù)進(jìn)行蝶形運算后結(jié)果送回到 保存，等等。保存，等等。這樣一直到最后一級的最后一個蝶形運算完成?？梢钥闯觯@樣一直到最后一級的最后一個蝶形運算完成。可以看出，每一每一級的蝶形的輸入與輸出在運算的前后可以存儲在同一地址級的蝶形的輸入與輸出在運算的前后可以存儲

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

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

10、變址計算碼位倒置順序碼位倒置順序自然順序自然順序二進(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ù)字信號處理 陳鵬 329934012實現(xiàn)由自然順序存儲到碼位倒置順序存儲的過程如下圖所示。實現(xiàn)由自然順序存儲到碼位倒置順序存儲的過程如下圖所示。圖中用圖中

11、用 表示自然順序的標(biāo)號，用表示自然順序的標(biāo)號，用 表示碼位倒置的標(biāo)號。表示碼位倒置的標(biāo)號。變址計算變址計算 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存儲單元變址自然順序輸入碼位倒置順序碼位倒置的變址處理nl2022-3-6數(shù)字信號處理 陳鵬 329934013變址計算變址計算當(dāng)當(dāng) 時，時， 和和 不必互相調(diào)換；不必互相調(diào)換；當(dāng)當(dāng) 時，將時，將 和和 進(jìn)行調(diào)換；進(jìn)行調(diào)換；當(dāng)當(dāng) 時，時， 和和 不能再進(jìn)行調(diào)換，因為前面已經(jīng)將不能再進(jìn)行調(diào)換，因為前面已經(jīng)將它們調(diào)換了一次了。它們調(diào)換了

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

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

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

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

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

17、2/012/0212/012/12/01021212NnknNkNnknNkNnknNNnknNNkNNnknNNNnknNNnknNNnnkNWNnxnxWNnxWnxWNnxWWnxWnxWnxWnxkX2022-3-6數(shù)字信號處理 陳鵬 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ù)項和奇數(shù)項，

18、則有 /2 121210/2 1/2012 ,0,1,2,122NrnrNnNnnrNNnNx nWNNx nx nW Wr 2022-3-6數(shù)字信號處理 陳鵬 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令得到上兩式所表示的是點的。在實際計算中， ,DFT2DFTnnNNg nh nNh n Wg nh n W首先形成序列和然后計算最后計算和的點的，便得到偶數(shù)輸出點和奇數(shù)輸出點的

19、。計算流程圖如下圖所示。2022-3-6數(shù)字信號處理 陳鵬 329934022頻率抽取頻率抽取基基2 FFT算法算法1111DFT2點NDFT2點N 0 x 2x 4x 6x 1x 3x 5x 7x 0X 4X 2X 6X 7X 1X 5X 3X3NW2NW1NW0NW)8(DFT2/DFTNNN計算的頻率抽選流程圖點的分解成兩個點2022-3-6數(shù)字信號處理 陳鵬 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分為前后兩組，得到將：來求得。推導(dǎo)過程如下點的成兩個可以分解點的數(shù)組，也就是將輸出再分為偶數(shù)組和奇的點仍是偶數(shù)，可以將的整數(shù)冪，所以是由于2022-3-6數(shù)字信號處理 陳鵬 329934024頻率抽取頻率抽取基基2 FFT算法算法NjNeW2 的流程圖。點的個繼續(xù)分解成的將兩個。這樣可得到下圖所示點的是上面式子表示的計算都通過類似的推導(dǎo)可得率的偶數(shù)項為再進(jìn)行奇偶分，則得頻對頻率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ù)字信號處理 陳鵬 329934025頻率抽取頻率抽取基基2 FFT算法算法11111111DFT4點N 0 x 2x 4x 6x 1x 3x 5x 7x 0X 2X 4X 6X 7X 1X 3X 5X3NW2NW1NW0NWDFT4點NDFT4點NDFT4點N0NW2NW0NW2NW)8(DFT4/DFTNNN的頻率抽選點的經(jīng)兩次分解成四個點2022-

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

23、輸入為正序輸入為正序排列，輸排列，輸出為碼位倒置排列，因此，出為碼位倒置排列，因此，輸出要進(jìn)行變址計算輸出要進(jìn)行變址計算。2022-3-6數(shù)字信號處理 陳鵬 329934027蝶形單元對比 pXm qXm1kNW pXm 1 qXm 110NW pXm qXm pXm 1 qXm 1時間抽取的方法時間抽取的方法頻率抽取的方法頻率抽取的方法2022-3-6數(shù)字信號處理 陳鵬 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ù)字信號處理 陳鵬 329934029頻率抽取頻率抽取基基2 FFT算法算法元頻率抽選的堞形運算單 rNmmmmmmWqXpXqXqXpXpX11 FFT流程圖，滿足以下關(guān)系算法的一般化的右圖所示的是頻率抽選的計算量是一樣的。選的算法的計算量與時間抽頻率抽選的復(fù)數(shù)加法次數(shù)：，復(fù)數(shù)乘法次數(shù)：量為個蝶形。因此，總計算級迭代運算，每級有共有個流程圖次復(fù)數(shù)加法。圖示的整次復(fù)數(shù)乘法和括顯然，一個堞形計算包FFTFFTlog log2 2log 2 1 222NNNNNNFF10NW pXm qXm pXm 1 qXm 12022-3-6數(shù)字信號處理 陳鵬 329934030IFFT的計算的計算FFT算法同樣可以用于算法同樣可以用于IDFT的計算，稱為的計算，稱為快速傅里葉反變換快速傅里葉反變換，簡寫為，簡