快速傅立葉變換

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

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

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

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