第三章_FFT_2014S

1、1第三章第三章 離散傅里葉變換離散傅里葉變換DFTDFT及快速算法及快速算法nFFTFFTu 基基2 2時域抽取的時域抽取的FFTFFT算法算法 u 基基2 2頻域抽取的頻域抽取的FFTFFT算法算法nIFFTIFFTu 基基2 2時域抽取的時域抽取的IFFTIFFT算法算法u 基基2 2頻域抽取的頻域抽取的IFFTIFFT算法算法2直接計算直接計算DFTDFT的運算量分析的運算量分析N N 點有限長序列點有限長序列 x(n)x(n)的的 DFT DFT 變換對的定義為：變換對的定義為：10( )( )NnkNnX kx n W 0,1kN 2jNNWe 101( )( )NnkNkx nX

2、k WN 0,1nN 其中其中假設(shè)假設(shè) x(n) 是復(fù)序列，是復(fù)序列， 同時同時 X(k) 一般也是復(fù)數(shù)一般也是復(fù)數(shù)3如如 N=512、1024 和和 8192 時，時，DFT 的乘法運算的乘法運算 5122 = 218 = 262144（26萬次）萬次） 10242 = 220 = 1048576（105萬次）萬次） 81922 = 226 = 67108864（6千千7百萬次）百萬次）對于大對于大 N，在實際中是不能接受的，無法，在實際中是不能接受的，無法“實時實時”應(yīng)用應(yīng)用 DFTCooley 與與 Turkey 提出的提出的 FFT 算法，大大減少算法，大大減少了計算次數(shù)。如了計算次數(shù)

3、。如 N =512 時，時，F(xiàn)FT 的乘法次數(shù)約的乘法次數(shù)約為為 2000 次，提高了約次，提高了約 128 倍，而且倍，而且簡化隨簡化隨 N 的增加而巨增的增加而巨增，因而，用數(shù)值方法計算頻譜得到因而，用數(shù)值方法計算頻譜得到實際應(yīng)用實際應(yīng)用直接計算直接計算DFTDFT的運算量分析的運算量分析4 nkmnkNmNWW 可可約約性性/nknk mNN mWW / 2(/ 2)01 1kNkNNNNNWWWW 特特殊殊點點：2jnknkNNWe 2jmnkmNe *()() ()nknkN n kn N kNNNNWWWW 對對稱稱性性NknkNNWW nNnkNNWWW WN Nknkn的性質(zhì)的

4、性質(zhì)()() nkNn kn NkNNNWWW周周期期性性5u以四點DFT為例： 直接計算需要直接計算需要：42 = 16 次復(fù)數(shù)乘次復(fù)數(shù)乘) 3 () 2() 1 () 0(111111111111) 3 () 2() 1 () 0(14141414xxxxWWWWXXXX) 3() 2() 1 () 0() 3() 2() 1 () 0(94643404644424043424140404040404xxxxWWWWWWWWWWWWWWWWXXXX 1414) 3 () 1 () 2() 0() 3 () 3 () 1 () 2() 0() 2() 3 () 1 () 2() 0() 1

5、() 3 () 1 () 2() 0() 0(WxxxxXxxxxXWxxxxXxxxxX只需要 1 次復(fù)數(shù)乘)3() 1 ()2()0(111111111111)3()2() 1 ()0(14141414xxxxWWWWXXXX6基本思路基本思路：通過迭代運算，利用通過迭代運算，利用 的周期的周期性和對稱性，用低點數(shù)的性和對稱性，用低點數(shù)的DFT完成高點數(shù)的完成高點數(shù)的DFT計算計算 knNjknNeW)2(DFTDFT的改進途徑的改進途徑1. 時間抽?。〞r間抽?。―ecimation-in-Time） FFT算法算法將序列將序列x(n) 逐次分解為較短的子序列進行逐次分解為較短的子序列進行

6、DFT計算計算2. 頻率抽?。l率抽取（Decimation-in-Frequency）FFT算法算法將離散傅里葉變換系數(shù)序列將離散傅里葉變換系數(shù)序列X(k)分解為較短的子序列分解為較短的子序列7基基2 2時間抽選法（時間抽選法（R2-DITR2-DIT）1, 1 , 0,)()(10NkWnxkXNnknN設(shè)設(shè)x(n)序列點數(shù)序列點數(shù) N = 2L，L 為整數(shù)。若不滿足，則補零為整數(shù)。若不滿足，則補零N 為為 2 的整數(shù)冪的的整數(shù)冪的 FFT 算法稱基算法稱基-2 FFT算法算法 將序列將序列 x(n) 按按 n 的的奇偶奇偶分成兩組：分成兩組：即一組由偶數(shù)序號組成，另一組由奇數(shù)序號組成即一

7、組由偶數(shù)序號組成，另一組由奇數(shù)序號組成12( )(2 )0,1,12( )(21)x rxrNrx rxr 偶偶數(shù)數(shù)組組奇奇數(shù)數(shù)組組8120) 12(120)2(10) 12()2()()(NrrkNNrrkNNnknNWrxWrxWnxkX11222200( )( )( )( )kNNNkrkkrNNNrra r WWb r WWA kB k 22k rkrNNWW12021202) 12()2(NrkrNkNNrkrNWrxWWrx9分解定理分解定理 、 是是N/2點的點的DFT 而而X(k)中中k的范圍為的范圍為 ，還應(yīng)進一步考慮還應(yīng)進一步考慮 的情況，即的情況，即 121 , 0Nk)

8、(kA)(kB10N12NN2()()2)(2(2)NkNWNX kNA kkNB 10分解定理分解定理nkNW)(222NkrNrkNWW利用利用 的周期性：的周期性：)()()()()2(12021202120)2(222kAWraWWraWrakNANrrkNNrrkNrNrkNrNNN)()2(kBkNBkNkNNNkNNWWWW2)2(2()()()()22(2)NkNkNNNNXA kkA kWkWB kB 121 , 0Nk同理同理又又所以所以11分解定理分解定理( )( )( )()( )( )2kkNN X kA kB kNX kA kB kWW 12, 1 , 0Nk因此：

9、因此：X(k)與與A(k)、B(k)的關(guān)系可用的關(guān)系可用蝶形信號流圖蝶形信號流圖表示表示1)(kA)(kBkNW)()(kBWkAkN)()(kBWkAkN整個整個 的計算，可以分解為的計算，可以分解為前、后半部分的運算前、后半部分的運算。而只要。而只要求出前一半，就可以求出整個序列。求出前一半，就可以求出整個序列。)(kX12分解定理分解定理 例例 N=23=8； k=0,1,2,313分解定理分解定理114442/400(4 )(42)NNklkklNNNllx l WWx lW 1202)2()(NrkrNWrxkA 我們可以再按奇、偶數(shù)把我們可以再按奇、偶數(shù)把A(k), B(k)進一步

10、分解為進一步分解為 兩個兩個N/4點的點的DFT 令令 則則 ) 12 (2l lr及LN21144(2 )(21)2200( )(4 )(42)NNklklNNllA kx l Wx lW 14, 1 , 0NkN2()kWCD kk14分解定理分解定理1404/221404140)(4/)(2140)(4)24()4()24()4()4(4444NlklNNkNNlklNNllkNkNNllkNWlxWWWlxWlxWWlxNkANNNN14, 1 , 0Nk2( )( )kNkWC kD2N( )( )kCkWkD 142/242jNNjNNeeW15分解定理分解定理 2 點點 DFTx

11、(0)x(2)x(4)x(6) 2 點點 DFTx(6)x(4)x(2)x(0)A(0)A(1)A(2)A(3)C(0)C(1)D(0)D(1)W80W82-1-1由兩個由兩個N/4點點DFT組合成一個組合成一個N/2點點DFT2N2N( )( )( )()( )( )4kkA kC kD kNA kC kD kWW14, 1 , 0Nk16分解定理分解定理因為因為N N為為2 2的正整數(shù)次冪的正整數(shù)次冪, ,可以繼續(xù)分解，直到最后可以繼續(xù)分解，直到最后分解為分解為2 2點點DFTDFT 2 點點 DFTx(0)x(2)x(4)x(6) 2 點點 DFTx(6)x(4)x(2)x(0)A(0)

12、A(1)A(2)A(3)C(0)C(1)D(0)D(1)W80W82-1-1x(0)x(2)x(4)x(6)x(6)x(4)x(2)x(0)A(0)A(1)A(2)A(3)C(0)C(1)D(0)D(1)W80W82-1-1-1-117分解定理分解定理對于分解到最后的對于分解到最后的2 2點點DFTDFT的信號流圖的信號流圖蝶形圖蝶形圖 -1) 0( x) 4( x01NW (0)(0)(4)Cxx(1)(0)(4)Cxx（只需要一次加法，一次減法）（只需要一次加法，一次減法） 18分解定理分解定理N=8時，基時，基2時間抽選法時間抽選法FFT的信號流圖的信號流圖)0(X)7(X)6(X)5(

13、X)4(X)3(X)2(X)1 (X)0(x)7(x)6(x)5(x)4(x)3(x)2(x)1 (x)0(x)1 (x)2(x)3(x)4(x)5(x)6(x)7(x點24點42點8111111111111108W28W08W28W08W18W38W28W1m2m3m08W08W08W08W19例例 使用基使用基 2 時間抽選法時間抽選法 FFT 流圖，計算下列流圖，計算下列數(shù)據(jù)的數(shù)據(jù)的 8點點 DFT：x=4,-3,2,0,-1,-2,3,112()/j4-320-1-23142-13-30-214-123-3-201355-1-5-11-1355j-5-11j85+j-25-j-4-1+

14、j-6-1-j85+j-25-j-4j26jj245+j+ j2-2+6j5-j+ j2125+j- j2-2-6j5-j- j2j12() /j128Wj 081W28Wj 081W1 1 1 1 1 1 1 1 1 1 1 1 20蝶形計算蝶形計算 任何一個任何一個N=2M的的DFT，都可以通過都可以通過M次分解，最后成為次分解，最后成為2點點的的 DFT來計算。來計算。M次分解構(gòu)成了從次分解構(gòu)成了從x(n)到到X(k)的的M級迭代計級迭代計算，算，每級由每級由N/2個蝶形組成個蝶形組成。計算時總是上節(jié)點的值和下。計算時總是上節(jié)點的值和下節(jié)點的值乘以節(jié)點的值乘以 然后相加減，形成下一級兩個

15、節(jié)點值，這然后相加減，形成下一級兩個節(jié)點值，這種計算的基本關(guān)系是種計算的基本關(guān)系是：rNW)()()(1qxWpxpxmrNmm)()()(1qxWpxqxmrNmm)()(1上節(jié)點pxm)()(1下節(jié)點qxm)(pxmrNWmqx)(1m m級級m+1m+1級級（總的蝶形數(shù)目總的蝶形數(shù)目= = MN/2MN/2個個）21蝶形運算自成獨立單元蝶形運算自成獨立單元 蝶形運算自成獨立單元，即蝶形運算自成獨立單元，即 ， 只只 與與 ， 有關(guān)，而與其他節(jié)點的值無關(guān)，同時有關(guān)，而與其他節(jié)點的值無關(guān)，同時 也不參與另外的蝶形運算。因此，就可把計算結(jié)也不參與另外的蝶形運算。因此，就可把計算結(jié)果果 ， 放入

16、計算前放入計算前 的存儲單元中，的存儲單元中，而不用再建新的存儲單元而不用再建新的存儲單元 同址計算同址計算(原位計算原位計算)(1pxm)(1qxm)(pxm)(qxm)(1pxm)(1qxm)(),(qxpxmm同址計算同址計算同址計算所需存儲量僅同址計算所需存儲量僅等于等于給定數(shù)據(jù)所需的存儲量，給定數(shù)據(jù)所需的存儲量，這可大大節(jié)省存儲單元這可大大節(jié)省存儲單元22運算量的減少運算量的減少（1）每個蝶形運算包含兩次復(fù)數(shù)加法，一次復(fù)數(shù)乘每個蝶形運算包含兩次復(fù)數(shù)加法，一次復(fù)數(shù)乘 法法（第一級的第一級的2 2點點DFTDFT可除外可除外）（2）N點點FFT需進行需進行 次迭代運算次迭代運算（3）每次

17、迭代運算包括每次迭代運算包括N/2個蝶形個蝶形NM2log 復(fù)數(shù)加法的次數(shù)為：復(fù)數(shù)加法的次數(shù)為： 復(fù)數(shù)乘法的次數(shù)為：復(fù)數(shù)乘法的次數(shù)為：222loglog2FNANNN 221log Nlog22FNNMN -1rNW23運算量的減少運算量的減少N點點DFT： 次復(fù)數(shù)乘法和次復(fù)數(shù)乘法和N(N-1)次復(fù)數(shù)加法次復(fù)數(shù)加法N點點FFT： 次復(fù)數(shù)乘法，次復(fù)數(shù)乘法， 次復(fù)數(shù)加法次復(fù)數(shù)加法2log2NNNN2log2N當當N N越大，越大，F(xiàn)FTFFT優(yōu)勢越明顯優(yōu)勢越明顯24FDMM/FFTFFT算法與算法與DFTDFT算法復(fù)數(shù)乘法次數(shù)比較算法復(fù)數(shù)乘法次數(shù)比較25倒置重排倒置重排輸入輸入x(n)是是“混序混

18、序”排列排列的，的，“混混 序序”并不是說輸入是并不是說輸入是雜亂無章的，實際上它是有規(guī)律的。如果輸入雜亂無章的，實際上它是有規(guī)律的。如果輸入x(n)的序號的序號用二進制碼來用二進制碼來 表示，就可以發(fā)現(xiàn)輸入的順序恰好是正序表示，就可以發(fā)現(xiàn)輸入的順序恰好是正序輸入的輸入的“碼位倒置碼位倒置”26倒置重排倒置重排FFT的時間抽選法按的時間抽選法按n的奇偶分離而形成倒置重排的原理如圖：的奇偶分離而形成倒置重排的原理如圖：2 100 12()()x n nnx n nn輸入序列重排實際上就是輸入序列重排實際上就是 相互交換相互交換在在C語言中，位操作中循環(huán)左移（右移）語言中，位操作中循環(huán)左移（右移）

19、2 1 0210()()(000)(0)(001)(1)(010)(2)(011)(3)(100)(4)(101)(5)(110)(6)(111)(7)n n nxxxxxxxxxxxxxxxxxn n nx 十十進進制制01010101(000)(0)(100)(4)(010)(2)(110)(6)(001)(1)(101)(5)(011)(3)(111)(7)xxxxxxxxxxxxxxxx010011n0n1n2271)流程圖的每一級的基本計算單元都是一個蝶形；流程圖的每一級的基本計算單元都是一個蝶形； 2)輸入輸入x(n)不按自然順序排列，稱為不按自然順序排列，稱為“混序混序”排列，而

20、排列，而輸輸 出出 X(k)按自然順序排列，稱為按自然順序排列，稱為“正序正序”排列，因而排列，因而要要 對輸入進行對輸入進行“變址變址”；3)由于流程圖的基本運算單元為蝶形，所以可以進行由于流程圖的基本運算單元為蝶形，所以可以進行 “同址同址”計算計算R2-DITR2-DITFFTFFT總結(jié)總結(jié)28基基 2 時間抽選法信號流圖（時間抽選法信號流圖（N=8）x-1W8218點點24點點42點點x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)-1-1-1

21、-1-1-1-1-1-1-1-1W80W80W82W80W81W82W83(4)8F(8)8F(2)8F8PC(0)C(1)D(0)D(1)E(0)E(1)F(0)F(1)A(0)A(1)A(2)A(3)B(0)B(1)B(2)B(3)m = 0 級m = 1級m = 2 級位序重排XDIT-FFT重重排排序序29Matlab Matlab 的實現(xiàn)的實現(xiàn) Matlab 提供了內(nèi)建的提供了內(nèi)建的 X = fft(x, N) 函函數(shù)來計算矢量數(shù)來計算矢量 x 的的 DFT30算法原理：算法原理：時間抽選法時間抽選法：是把輸入是把輸入 x(n) 按奇偶分按奇偶分解解成兩個子序列，而對應(yīng)的輸出是按成兩

22、個子序列，而對應(yīng)的輸出是按自自然順序排列的然順序排列的X(k)的前、后兩半的前、后兩半頻率抽選法頻率抽選法：是把輸入是把輸入 x(n) 按照自然按照自然順序前后對半分開順序前后對半分開，而輸出，而輸出 X(k) 逐項逐項分解成偶數(shù)點子序列和奇數(shù)點子序列分解成偶數(shù)點子序列和奇數(shù)點子序列3.4.3 3.4.3 基基2 2頻率抽選法頻率抽選法 (DIF-FFT)(DIF-FFT)31基基2 2頻率抽選法頻率抽選法FFTFFTDIFDIF2 1102( )( )( )NnkkNnnnNNNX kx n Wx n W 2 12 1()0022( )()NNnkkNNnnnNx n Wx nWN ()2

23、120 ( )()2NkNnkNnNNx nx nWW 0 (1)2Nn DFT： 如果將求和分成兩部分，一部分是如果將求和分成兩部分，一部分是 ，另一，另一部分是部分是 ，則可得：，則可得： 10)()(NnnkNWnxkX (1)2NnN32基基2 2頻率抽選法頻率抽選法因為因為按按k的奇偶性的奇偶性將將 分解為分解為偶數(shù)組偶數(shù)組和和奇數(shù)組奇數(shù)組：12NNW為奇數(shù)為偶數(shù)kkWkkNN, 1, 1) 1()2(2 1012NnkNnkNX kx nx nW( ) ( ) ()() )(kX1202)2()()2(NnnrNWNnxnxrX1202)2()(NnnrNWNnxnx12()021

24、(21) ( )()2NnrNnNX rx nx nW 1202)2()(NnnrNnNWWNnxnx所以：所以：0,1,.12Nr 33基基2 2頻率抽選法頻率抽選法若令若令則下式表示兩個則下式表示兩個N/2點點DFT運算：運算：( )( )()2Ng nx nx n ( )( )()2Nhnx nx n 12, 0Nn12201220(2 )(2( )(1)NnrNnNnNnrnNg nhXrWXrWn W -1)(nx)2(NnxnNW( )( )()2Ng nx nx n( ) ( )()2nnNNNh nWx nx nW0,1,.12Nr 34N/2-1)(nx)2(NnxnNW(

25、)( )()2Ng nx nx n( ) ( )()2nnNNNh nWx nx nW-11( )X k2( )XknNW12(2 )( )( )XkX kXk12(21) ( )( )nNXkX kX k W求求N/2點點DFT35基基2 2頻率抽選法頻率抽選法將將N點點DFT分解為兩個分解為兩個N/2點點DFT（N8）()()()2Ng nx nx n ()()()2Nh nx nx n 4 4點點DFTDFT 4 4點點DFTDFT1)0( x) 1 ( x)2( x) 3( x)4( x)5( x)6( x)7( x)0(X) 1 (X(4)X(5)X(2)X(3)X)6(X)7(X0

26、8W18W28W38W111(0)g(1)g(2)g(3)g(0)h(1)h(2)h(3)h36繼續(xù)分解繼續(xù)分解37m=0m=1m=2) 0( x) 1 ( x) 2( x) 3 ( x) 4( x) 5 ( x) 6( x) 7( x) 7(X) 6(X) 5 (X) 4(X) 3 (X) 2(X) 1 (X) 0(X) 0(X) 4(X) 2(X) 6(X) 1 (X) 5 (X) 3 (X) 7(X11111111111108W38W28W18W08W28W28W08WN=8N=8時，基時，基2 2頻率抽選法的整個信號流圖如下：頻率抽選法的整個信號流圖如下：直到分解為直到分解為2點點DF

27、T為止為止重重排排序序38時間抽選法和頻率抽選法的異同時間抽選法和頻率抽選法的異同 蝶形計算蝶形計算 時間抽選法、頻率抽選法都是把一個N（ ）點DFT先分解成兩個N/2（ ）點DFT，再分解成四個N/4點DFT，直到最后分解為N/2個2點DFT 最基本的運算是蝶形運算。時間抽選法和頻率時間抽選法和頻率抽選法的蝶形運算不同：抽選法的蝶形運算不同：m212m39DIT: 先復(fù)乘后加減，先復(fù)乘后加減，W 因子在上下節(jié)點都有體現(xiàn)因子在上下節(jié)點都有體現(xiàn)DIF: 先減后復(fù)乘，先減后復(fù)乘，W因子僅體現(xiàn)在下節(jié)點因子僅體現(xiàn)在下節(jié)點DIT-FFT和和DIF-FFT區(qū)別區(qū)別11( )( )( )( )( )( )m

28、mmmkNkNmmxpxpxqxqxpxWqW11( )( )( ) ( )( )( )mnmmmNmmxpWxpxpxqxxqq)()(1上節(jié)點pxm)()(1下節(jié)點qxm)(pxmrNmWqx)(1m級m+1級()mxqnNW4022logFNmN乘乘法法：2logFaNN加加法法：運算量相同運算量相同時間抽選法和頻率抽選法的異同時間抽選法和頻率抽選法的異同DIT 輸入重排，輸入重排，DIF 輸出重排，即輸出重排，即1210011()()倒倒置置MMX nn nnX n nn41時間抽選法和頻率抽選法的異同時間抽選法和頻率抽選法的異同頻率抽選法實現(xiàn)的另一方法頻率抽選法實現(xiàn)的另一方法信號流圖

29、轉(zhuǎn)置定理信號流圖轉(zhuǎn)置定理：若流圖全部支路方向反向，支：若流圖全部支路方向反向，支 路增益不變，輸入輸出變量交路增益不變，輸入輸出變量交 換位置，則傳輸函數(shù)保持不變換位置，則傳輸函數(shù)保持不變)(nxca1z)(ny11)(aczczH)(ny)(nxca1z11)(aczczH42DIT 和和 DIF 的基本蝶形互為的基本蝶形互為信號流圖轉(zhuǎn)置信號流圖轉(zhuǎn)置DITDIF時間抽選法和頻率抽選法的異同時間抽選法和頻率抽選法的異同(0)x(2)x(1)x(3)x1 1 1 1 (0)X(1)X(2)X(3)X04W14W1 1 1 1 (0)x(1)x(2)x(3)x(0)X(2)X(1)X(3)X04W

30、14W輸入倒位序，輸出自然序（輸入倒位序，輸出自然序（DITDIT）輸入自然序，輸出倒位序（輸入自然序，輸出倒位序（DIFDIF）43除了基除了基 2 的的 FFT 算法外，還有基算法外，還有基 R （R=3，4，）的快速算法。原理和基）的快速算法。原理和基 2 的類似，可以進一步降低復(fù)數(shù)乘次數(shù)的類似，可以進一步降低復(fù)數(shù)乘次數(shù)基基4算法原理（自學(xué)）算法原理（自學(xué)）基基4 4時間抽選法時間抽選法N = RVN = 2V44IDFTIDFT的快速算法的快速算法IFFTIFFT由于由于DFT變換對的對稱性，變換對的對稱性，IFFT的算法與前面所的算法與前面所求的求的FFT算法幾乎完全相同：算法幾乎完

31、全相同： 10:()()n kNNnD F TXkx n W101:( )( )NNnkkIDFTx nXk WN FFT 算法中的分組方式、排序方式以及蝶形運算結(jié)構(gòu)算法中的分組方式、排序方式以及蝶形運算結(jié)構(gòu)都可用于都可用于IFFT 算法的設(shè)計，而這就是可算法的設(shè)計，而這就是可依據(jù)現(xiàn)有的依據(jù)現(xiàn)有的 FFT 算法直接得出算法直接得出 IFFT 算法算法的原因。的原因。 DFT 和和 IDFT 的的區(qū)別區(qū)別： 因子因子 W 的指數(shù)相差一個負號；的指數(shù)相差一個負號； 相差一個因子相差一個因子 1/N。45設(shè)有序列 x(n)，其 DFT 為 X(k)，則 IDFT 為:12122( )( )( )()

32、( )( )kNkN X kX kWXkNX kX kWXk 在在 FFT FFT 的的時間抽選時間抽選法中法中: : DIT-IFFT 對于對于 IFFT 算法，輸入是算法，輸入是 X(k) 和和 X(k+N/2)，輸出是，輸出是 X1(k) 和和 X2(k)。解上式可以得到解上式可以得到 X1(K)、X2(K) ：12122212( )( )()( )( )()kNN X kX kX kNXkWX kX kX(k)X(k+N/2)X1(k)X2(k)-11/2kN1W2101( )( )NnkNkx nX k WN468 點點 DIT-IFFT 算法算法-1x(0)x(1)x(2)x(3)

33、x(4)x(5)x(6)x(7)x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)-1-1-1-1-1-1-1-1-10.5W8-00.5W8-20.5W8-00.5W8-10.5W8-20.5W8-3-1-10.5W8-00.5W8-2121 21 21 說明：說明：1）分組過程是按時間序列分組過程是按時間序列 x(n) 的奇的奇偶性在時域上展開的，故稱此法為時間抽選偶性在時域上展開的，故稱此法為時間抽選算法算法 DIT-IFFT；2）1/N 的分解，的分