快速傅立葉變換

1、第四章 快速傅立葉變換一、 計算DFT效率及其改善途徑填空題：1如果一臺通用機算計的速度為：平均每次復乘需100，每次復加需20，今用來計算N=1024點的DFT。問直接運算需（ ）時間，用FFT運算需要（ ）時間。解：（1）直接運算：需復數乘法次，復數加法次。直接運算所用計算時間為（2）基2FFT運算：需復數乘法次，復數加法次。用FFT計算1024點DTF所需計算時間為2N點FFT的運算量大約是（ ）。 解：次復乘和次復加3快速傅里葉變換是基于對離散傅里葉變換 _和利用旋轉因子的_ 來減少計算量，其特點是 _,_和_。解：快速傅里葉變換是基于對離散傅里葉變換 長度逐次變短 和利用旋轉因子的

2、周期性、對稱性來減少計算量，其特點是 蝶形計算、 原位計算 和 碼位倒置。簡答題：4FFT主要利用了DFT定義中的正交完備基函數的周期性和對稱性，通過將大點數的DFT運算轉換為多個小數點的DFT運算，實現(xiàn)計算量的降低。請寫出的周期性和對稱性表達式。答： 周期性： 對稱性：5基2FFT快速計算的原理是什么？它所需的復乘、復加次數各是多少？解：原理：利用的特性，將N點序列分解為較短的序列，計算短序列的DFT，最后再組合起來。復乘次數：，復加次數：二、 按時間抽取FFT算法簡答題：1簡略推導按時間抽取基2-FFT算法的蝶形公式，并畫出N=8時算法的流圖，說明該算法的同址運算特點。解：答案略。作圖題：

3、3畫出基2 時間抽取的FFT流圖，并利用該流圖計算序列的DFT。解：答案略。4對于長度為8點的實序列，試問如何利用長度為4點的FFT計算的8點DFT？寫出其表達式，并畫出簡略流程圖。解： 按照式和式可畫出如下圖所示的流程圖。三、按頻率抽取FFT算法計算題：1是N點序列的DFT，N為偶數。兩個點序列定義為 和分別表示序列和的點DFT，試由和確定的點DFT。解： DFT （為偶數） DFT（為奇數） 解上述方程可得簡答題：1 簡略推導按頻率抽取基2-FFT算法的蝶形公式，并畫出時算法的流圖，說明該算法的同址運算特點?！敬鸢浮科渫愤\算特點為輸入按自然順序存放，輸出序列按碼位顛倒順序存放。作圖題：2

4、 畫出基2 時域抽取4點FFT的信號流圖。解：答案略。四、 其它FFT算法簡答題：1已知兩個N點實序列和得DFT分別為和，現(xiàn)在需要求出序列和，試用一次N點IFFT運算來實現(xiàn)。解：依據題意 取序列 對作N點IFFT可得序列。又根據DFT性質 由原題可知，都是實序列。再根據，可得 2已知長度為2N的實序列的DFT的各個數值，現(xiàn)在需要由計算，為了提高效率，請設計用一次N點IFFT來完成。解：如果將按奇偶分為兩組，即令 那么就有 其中、分別是實序列、的N點DFT，、可以由上式解出： 由于是已知的，因此可以將前后分半按上式那樣組合起來，于是就得到了和。到此，就可以像4.9題那樣來處理了，也即令根據、，做一次N點IFFT運算，就可以同時得到和，它們分別是的偶數點和奇數點序列，于是序列也就求出了。五、 快速傅立葉變換應用簡答題：1 采用FFT算法，可用快速卷積完成線性卷積。現(xiàn)預計算線性卷積，試寫采用快速卷積的計算步驟（注意說明點數）。答：如果，的長度分別為,那么用長度的圓周卷積可計算線性卷積。用FFT運算來求值（快速卷積）的步驟如下：（1） 對序列，補零至長為N，使