快速傅里葉變換FFT試題

1、第一章 快速傅里葉變換（FFT）4.1 填空題 （1）如果序列是一長度為64點的有限長序列，序列是一長度為128點的有限長序列，記（線性卷積），則為 點的序列，如果采用基算法以快速卷積的方式實現(xiàn)線性卷積，則的點數(shù)至少為 點。解：64+128-1191點; 256(2)如果一臺通用機(jī)算計的速度為：平均每次復(fù)乘需100，每次復(fù)加需20，今用來計算N=1024點的DFT。問直接運算需（ ）時間，用FFT運算需要（ ）時間。解：直接運算：需復(fù)數(shù)乘法次，復(fù)數(shù)加法次。直接運算所用計算時間為 基2FFT運算：需復(fù)數(shù)乘法次，復(fù)數(shù)加法次。用FFT計算1024點DTF所需計算時間為。(3)快速傅里葉變換是基于對離

2、散傅里葉變換 和利用旋轉(zhuǎn)因子的 來減少計算量，其特點是 _、_和_。解：長度逐次變短；周期性；蝶形計算、原位計算、碼位倒置（4）N點的FFT的運算量為復(fù)乘 、復(fù)加 。解：；4.2 選擇題1在基2DITFFT運算中通過不斷地將長序列的DFT分解成短序列的DFT，最后達(dá)到2點DFT來降低運算量。若有一個64點的序列進(jìn)行基2DITFFT運算，需要分解 次，方能完成運算。 A.32 B.6 C.16 D. 8解：B2在基2 DITFFT運算時，需要對輸入序列進(jìn)行倒序，若進(jìn)行計算的序列點數(shù)N=16，倒序前信號點序號為8，則倒序后該信號點的序號為 。 A. 8 B. 16 C. 1 D. 4解：C3在時域

3、抽取FFT運算中，要對輸入信號x(n)的排列順序進(jìn)行“擾亂”。在16點FFT中，原來x(9)的位置擾亂后信號為： 。A x(7) B. x(9) C. x(1) D. x(15)解：B4.用按時間抽取FFT計算N點DFT所需的復(fù)數(shù)乘法次數(shù)與( )成正比。A.N B.N2 C.N3 D.Nlog2N解：D5.直接計算N點DFT所需的復(fù)數(shù)乘法次數(shù)與(        )成正比。A.N         B.N2 C.N3  

4、       D.Nlog2N 解：B6.N點FFT所需的復(fù)數(shù)乘法次數(shù)為( )。A.NB.N2C.N3D.(N/2)log2N解：D7.下列關(guān)于FFT的說法中錯誤的是(     )。   A.FFT是一種新的變換   B.FFT是DFT的快速算法  C.FFT基本上可以分成時間抽取法和頻率抽取法兩類  D.基2 FFT要求序列的點數(shù)為2L(其中L為整數(shù))解：A8.不考慮某些旋轉(zhuǎn)因子的特殊性，一般一個基2 F

5、FT算法的蝶形運算所需的復(fù)數(shù)乘法及復(fù)數(shù)加法次數(shù)分別為( )。A.1和2B.1和1C.2和1D.2和2解：A9計算N=2L（L為整數(shù)）點的按時間抽取基-2FFT需要( )級蝶形運算。ALB.L/2C.ND.N/2解：A10.基-2 FFT算法的基本運算單元為( )A.蝶形運算B.卷積運算C.相關(guān)運算D.延時運算解：A11.計算256點的按時間抽取基-2 FFT，在每一級有_個蝶形。( )A.256B.1024C.128D.64解：C12.如圖所示的運算流圖符號是_基2FFT算法的蝶形運算流圖符號。( )A.按頻率抽取B.按時間抽取C.A、B項都是D.A、B項都不是解：B13.求序列x(n)的10

6、24點基2FFT，需要_次復(fù)數(shù)乘法。( )A.1024B.1024×1024C.512×10D.1024×10解：C4.3 問答題1.簡述頻域抽選法和時域抽選法的異同。 答：相同點：（1）進(jìn)行原位運算（2）運算量相同，均為次復(fù)乘、次復(fù)加；不同點：（1）時域抽選法輸入為倒位序，輸出為自然順序。頻域抽選法正好與此相反，但時域抽選法也有輸入為自然順序、輸出為倒位序的情況（2）蝶形運算不同2.回答以下問題：（1） 畫出按時域抽取點基的信號流圖。（2） 利用流圖計算4點序列（）的。（3） 試寫出利用計算的步驟。解：（1） 4點按時間抽取FFT流圖 加權(quán)系數(shù) （2） 即： （

7、3）具體步驟如下：1）對取共軛，得； 2）對做N點FFT； 3）對2）中結(jié)果取共軛并除以N。 3.已知兩個N點實序列和得DFT分別為和，現(xiàn)在需要求出序列和，試用一次N點IFFT運算來實現(xiàn)。解：依據(jù)題意 取序列 對作N點IFFT可得序列。又根據(jù)DFT性質(zhì) 由原題可知，都是實序列。再根據(jù)，可得 4.4 計算題1. 對于長度為8點的實序列，試問如何利用長度為4點的FFT計算的8點DFT？寫出其表達(dá)式，并畫出簡略流程圖。解： 按照式和式可畫出如下圖所示的流程圖。2.是N點序列的DFT，N為偶數(shù)。兩個點序列定義為 和分別表示序列和的點DFT，試由和確定點DFT。解：DFT （為偶數(shù)） DFT（為奇數(shù)）

8、解上述方程可得3.已知長度為2N的實序列的DFT的各個數(shù)值，現(xiàn)在需要由計算，為了提高效率，請設(shè)計用一次N點IFFT來完成。解：如果將按奇偶分為兩組，即令那么就有 其中、分別是實序列、的N點DFT，、可以由上式解出由于是已知的，因此可以將前后分半按上式那樣組合起來，于是就得到了和。令根據(jù)、，做一次N點IFFT運算，就可以同時得到和它們分別是的偶數(shù)點和奇數(shù)點序列，于是序列也就求出了。4-7 采用FFT算法，可用快速卷積完成線性卷積。現(xiàn)預(yù)計算線性卷積，試寫采用快速卷積的計算步驟（注意說明點數(shù)）。答：如果，的長度分別為,那么用長度的圓周卷積可計算線性卷積。用FFT運算來求值（快速卷積）的步驟如下：（1） 對序列，補零至長為N，使，并且(M為整數(shù))，即（2） 用FFT計算，的離散傅立