快速傅里葉變換(參考版)
2024-08-26 23:53本頁(yè)面
【正文】 H(K)] 的方法相比，那種方法求 解 y(n)的效率更高？ x(n) h(n) y(n)=x(n)*h(n) L≥N1+N21 X(k) 補(bǔ) LN1個(gè)零 x(n) L點(diǎn) DFT 補(bǔ) LN2個(gè)零 h(n) L點(diǎn) DFT L點(diǎn) IDFT y(n) = x(n)*h(n) H(k) Y(k) 直接進(jìn)行卷積（ N=10）： ?????????nmnhnxnhnxny )()()()()(乘法次數(shù)： 240 10 = 2400次 用 FFT的方法（ N=10）： 添零到 256點(diǎn)， L=256 乘法次數(shù)： 3 (L/2)log2L＋ L = 3 128 8＋ 256 = 3328次 直接進(jìn)行卷積（ N=240）： ?????????nmnhnxnhnxny )()()()()(乘法次數(shù)： 240 240 = 57600次 用 FFT的方法（ N=240）： 添零到 512點(diǎn)， L=512 乘法次數(shù)： 3 (L/2)log2L＋ L = 3 256 9＋ 512 = 7424次 。 Hzf 4 0 9 6s ?即：hff 2s ??Hzf h 2 0 4 8??2）若計(jì)算采樣信號(hào)的 4096點(diǎn) DFT， DFT系數(shù)之間 的頻率間隔是多少？ 解： (要求解的是頻譜分辨的間隔 F) Hzf 4096s ?頻譜范圍是：?40 96?N)(14 0 9 6 )(4 0 9 6s HzHzNfF ???例 長(zhǎng)度為 240點(diǎn)的序列 x(n)與長(zhǎng)度為 N點(diǎn)的 h(n)卷 積。 第五節(jié) IDFT的快速算法－ IFFT 上述 FFT算法流圖也可以用于離散傅里葉逆變換(Inverse Discrete Fourier Transform， 簡(jiǎn)稱 IDFT)。 4) 頻率抽選法和時(shí)間抽選法一樣，基本運(yùn)算也是蝶形 運(yùn)算。 設(shè)序列 x(n)長(zhǎng)度為 N=2M， 首先將 x(n)前后對(duì)半分開(kāi)，得到兩個(gè)子序列，其 DFT可表示為如下形式 ?????????1NN / 2nknN1N / 20nknN1N0nknN WnxWnxWnxX ( k) )()()(????????1N / 20n)2/(1N / 20n)2/()( NnkNknN WNnxWnx????????1N / 20n1N / 20n)2/()1()( knNkknN WNnxWnx 1,...1,0 ?? Nk? ? kjkkNNjkNN eeW 1222/ ???? ?? ??式中，? ?? ?? ?????????12/01,.. ...1,0,)2/(1)()(NnknNk NkWNnxnxkX:)(k 分為兩部分的奇偶可把按 kX?12/....2,1,0,12,2 ????? Nrrkrk 及令為偶數(shù)時(shí)，K? ? ? ?? ?????????????12/02/12/02)2/()()2/()(2NnrnNNnrnNWNnxnxWNnxnxrX為奇數(shù)時(shí)，K? ? ? ?? ???????????????12/02/12/012)2/()()2/()(12NnrnNnNNnnrNWWNnxnxWNnxnxrX）（nNW)2/()()(1 Nnxnxnx ???? ? nNWNnxnxnx )2/()()(2 ???)(nx)2/( Nnx ?? ? 1, . . . ,1,0)2/()()()2/()()(221 ???????????NnNnWNnxnxnxNnxnxnx令???????????????????nrNNnnrNNnWnxrXkXWnxrXkX2/12/0222/12/011)()12()()()2()(DIF―FFT 一次分解運(yùn)算流圖 (N=8) 4點(diǎn)DFT 4點(diǎn)DFT x(0) x(1) x(2) x(3) x(4) x(5) x(6) x(7) X(0) X(2) X(4) X(6) X(1) X(3) X(5) X(7) 3NW2NW1NW0NWx1(0) x1(1) x1(2) x1(3) x2(0) x2(1) x2(2) x2(3) DIF―FFT 二次分解運(yùn)算流圖 (N=8) N /4 點(diǎn)D F TW N0W N1W N2W N3x ( 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 )W N0W N2W N0W N2N /4 點(diǎn)D F TN /4 點(diǎn)D F TN /4 點(diǎn)D F TDIF―FFT 運(yùn)算流圖 (N=8) W N0W N1W N2W N3W N0W N2W N0W N2W N0W N0W N0W N0X ( 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 )? 時(shí)間抽取算法與頻率抽取算法的比較 1) 頻率抽選法和時(shí)間抽選法總的計(jì)算量是相同的 NN 2lo g2 NN 2lo g復(fù)乘： 復(fù)加： 2) 頻率抽取法和時(shí)間抽取法一樣，都適用于 原位運(yùn) 算 ， 即蝶形的輸入和輸出占用同一個(gè)存儲(chǔ)單元。 i=N1。 ? 若已知某個(gè)反序號(hào)為 J， 為求下一個(gè)反序號(hào)，可先判 J的最高位： 1) 若為 0，則把該位變成 1（即加 N/2） 就得到下 一個(gè)反序號(hào)， 2) 若為 1，則需判斷次高位： ① 若次高位為 0，則把最高位變 0（相當(dāng)減去 N/2） 后，再把次
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號(hào)-1