数字信号处理习题第六章快速傅里叶变换(FFT)1.如果一台通用计算机的速度为平均每次复乘需100s,每次复加需20s,今用来计算N=1024点的DFT[x(n)],问用直接运算需要多少时间,用FFT运算需要多少时间。解:ssFFTssFFTNNaNNNmssDFTsDFTDFTNamFFTFFTDFTDFT23221027682666221020482010241051210512010240log),10242(,5120log210820104,10410104,104104102444作复加所需时间作复乘所需时间作复加所需时间作复乘所需时间作复乘2.用图6.8所示流程图验证图6.7所示的8点变址运算。证明:由图6.8知取A=x(0),B=x(4)N=8X(k)=12/,,1,0),()(21NkkXWkXkNX(N/2+k)=12/,,1,0),()(21NkkXWkXkN5.试证实以下流图是一个N=8的FFT流图.其输入是自然顺序的,而输出是码位倒置顺序的,试问这个流图是属与时间抽取法还是频率抽取法?并比较与书中哪一个流图等效。解:这个流图属于频率抽取法。6.试设计一个频率抽取的8点FFT流图,需要输入是按码位倒置顺序而输出是按数字信号处理习题自然顺序的。解:设计的流图为第五题的流图左右翻转180度。1202/21202/1)()12()()2(NkkrNNkkrNWkxrXWkxrX7.试用图6.14(a)中的蝶形运算设计一个频率抽取的8点IFFT流图。解:X(0)1/2x(0)X(4)x(1)X(2)x(2)X(6)x(3)X(1)x(4)X(5)x(5)X(3)x(6)X(7)x(7)9.试作一个N=12点的FFT流图,请按N=2,2,3分解,并问可能有几种形式?解:可能有三种先分成2组,每组有6各点,后每组内再分成两组322N数字信号处理习题时间顺序为x(0),x(4),x(8),x(2),x(6),x(10),x(1),x(5),x(9),x(7),x(11)频域顺序为X(0),X(1),X(2),X(3),X(4),X(5),X(6),X(7),X(8),X(9),X(10),X(11)流图如图6.18解:由题可得102210)(|)(1,,1,0,)()(NnknNjzzkNjkNnnenxzXNkezzznxzXk由于(a)将M点序列分成若干段N点序列,设段数为k即NkMkN)1(并令knNjNnkiizzkenyzXNnNkMNkMnNknxnyNnxnynxnyk21010110)]([[|)(11)1(,01)1(0],)1([)()()()()(若用N点FFT计算)(kzX先由x(n)形成)(nyi,再计算10)(kiiny的N点FFT即可(b)先将序列添加一点等于零的点,使得1,010),()(0NnMMnnxnx数字信号处理习题再计算)(0nx的N点FFT即10,)(|)(20NkenxzXknNjzzk即可13.已知X(K),Y(K)是两个N点实序列x(n),y(n)的DFT值,今需要从X(K),Y(K)求x(n),y(n)值,为了提高运算效率试设计用一个N点IFFT运算一次完成。解:构成Z(k)=X(k)+jY(k),由于X(k),Y(k)都为实序列所以z(n)是唯一的,x(n)=Re[z(n)]y(n)=Im[z(n)]对Z(k)作FFT14.已知X(K),K=0,1…,2N-1,是2N点实序列x(n)的DFT值,现在需要由X(K)求x(n)值,为了提高运算效率,试设计一个N点IFFT运算一次完成。解:])()([21)(21)2(),12(),2()()(21)(10)(101201202NkNKmNNkKmNNkkmNNKKnNWKNXWKXNWKXNmxnmxnmxnxWKXNnx奇数偶数10)]()([2121NKmKNWNKXKXN15.若一个FIR滤波器处理机,用FFT算法分段过滤信号,每段运算N=1024点,运算一遍需要0.2秒,处理机具有两组1024个单元的复数存储器可供交替使用,一组供运算时,另一组可以用来存贮实时输入的信号序列。用该处理机并配以采样器及A/D变换器作连续信号的实时过滤,试问数字信号处理习题(a)采样频率最高是多少?(b)若作两路信号同时过滤时,采样频率最高是多少?(c)在这两种情况下最高可以处理多高频率的信号?解:一次蝶形时间sTB,则总的运算NNTB2log2HzfsTTTTTsBBBBB9.568809.0/512,09.0,512log25121024log210241024log21024512log2512122212221a)中最高信号频率Hzf25602/5120maxb)中最高信号频率Hzf4.28442/9.5688max