课后习题及答案_第4章快速傅里叶变换--习题答案.pdf

1 第 4 章 快速傅里叶变换 FFT 习题答案 1 解解解解 当 N 1024 210 时 直接计算 DFT 的复数乘法运算次数为 N2 1024 1024 1 048 576 次 复数加法运算次数为 N N 1 1024 1023 1 047 552 次 直接计算所用计算时间 TD 为 TD 4 10 6 10242 1 047 552 10 6 5 241 856 s 用 FFT 计算 1024 点 DFT 所需计算时间 TF为 快速卷积时 需要计算一次 N 点 FFT 考虑到 H k DFT h n 已计算好存 入内存 N 次频域复数乘法和一次 N 点 IFFT 所以 计算 1024 点快速卷 积的计算时间 Tc约为 所以 每秒钟处理的采样点数 即采样速率 由采样定理知 可实时处理的信号最高频率为 应当说明 实际实现时 fmax还要小一些 这是由于实际中要求采样频 率高于奈奎斯特速率 而且在采用重叠相加法时 重叠部分要计算两次 重 叠部分长度与 h n 长度有关 而且还有存取数据和指令周期等消耗的时间 2 解解解解 与第 1 题同理 直接计算 1024 点 DFT 所需计算时间 TD 为 66 F 66 5 10lblb10 2 1024 5 1010 1024 10 10 2 30 72 ms N TNN N cF 21024 71680 s4 1024 s 65536 s TT 次复数乘计算时间 s 6 1024 15 625 65536 10 F 次 秒 s max 15625 7 8125 kHz 22 F f 2 TD 10 10 9 10242 10 10 9 1 047 552 20 961 28 ms 用 FFT 计算 1024 点 DFT 所需计算时间 TF为 快速卷积计算时间 Tc约为 可实时处理的信号最高频率 fmax为 由此可见 用 DSP 专用单片机可大大提高信号处理速度 所以 DSP 在数字信号处理领域得到广泛应用 机器周期小于1 ns的DSP产品已上市 其 处理速度更高 3 解解解解 因为 x n 和 y n 均为实序列 所以 X k 和 Y n 为共轭对称序列 jY k 为共轭反对称序列 可令 X k 和 jY k 分别作为复序列 F k 的共轭对称分量 和共轭反对称分量 即 F k X k jY k Fep k Fop k 计算一次 N 点 IFFT 得到 f n IFFT F k Re f n j Im f n 由 DFT 的共轭对称性可知 Re f n IDFT Fep k IDFT X k x n j Im f n IDFT Fop k IDFT jY k jy n 故 4 解解解解 本题的解题思路就是 DIT FFT 思想 1 在时域分别抽取偶数和奇数点x n 得到两个N点实序列x1 n 和x2 n x1 n x 2n n 0 1 N 1 x2 n x 2n 1 n 0 1 N 1 99 F 88 10 10lb10 10lb 2 1024 1010 101024 10 2 0 1536 ms N TNNN cF 39 21024 2 0 1536 1010 101024 0 317 44 ms TT 次复数乘计算时间 maxs c 1110241 3 1158 MHz 1 6129 MHz 222 fF T 1 2 x nf nfn 1 2j y nf nfn 3 根据DIT FFT的思想 只要求得x1 n 和x2 n 的N点DFT 再经过简单 的一级蝶形运算就可得到x n 的2N点DFT 因为x1 n 和x2 n 均为实序列 所 以根据DFT的共轭对称性 可用一次N点FFT求得X1 k 和X2 k 具体方法 如下 令 y n x1 n jx2 n Y k DFT y n k 0 1 N 1 则 2N点DFT x n X k 可由X1 k 和X2 k 得到 这样 通过一次N点IFFT计算就完成了计算2N点DFT 当然还要进行由 Y k 求X1 k X2 k 和X k 的运算 运算量相对很少 2 与 1 相同 设 x1 n x 2n n 0 1 N 1 x2 n x 2n 1 n 0 1 N 1 X1 k DFT x1 n k 0 1 N 1 X2 k DFT x2 n k 0 1 N 1 则应满足关系式 由上式可解出 由以上分析可得出运算过程如下 1 由X k 计算出X1 k 和X2 k 11ep 22ep 1 DFT 2 1 j DFT j 2 X kx nYkY kYNk Xkx nYkY kYNk 122 122 0 1 1 k N k N X kX kWXk kN X kNX kWXk L 122 122 0 1 1 k N k N X kX kWXk kN X kNX kWXk L 1 22 1 2 0 1 2 1 1 2 k N X kX kX kN kN XkX kX kN W L 4 由X1 k 和X2 k 构成N点频域序列Y k Y k X1 k jX2 k Yep k Yop k 其中 Yep k X1 k Yop k jX2 k 进行N点IFFT 得到 y n IFFT Y k Re y n j Im y n n 0 1 N 1 由DFT的共轭对称性知 由x1 n 和x2 n 合成x n 0 n 2N 1 在编程序实现时 只要将存放x1 n 和x2 n 的两个数组的元素分别依次放入 存放x n 的数组的偶数和奇数数组元素中即可 5 解解解解 本题比较简单 仿照教材中的8点基2DIT FFT和DIF FFT运算流 图很容易画出16点基2DIT FFT和DIF FFT运算流图 但画图占篇幅较大 这 里省略本题解答 请读者自己完成 6 解解解解 为了使用灵活方便 将本题所给算法公式作为函数编写 ifft46 m 如下 函数ifft46 m 按照所给算法公式计算IFET function xn ifft46 Xk N Xk conj Xk 对Xk取复共轭 xn conj fft Xk N N 按照所给算法公式计算IFFT 分别对单位脉冲序列 长度为8的矩形序列和三角序列进行FFT 并调 用函数ifft46计算IFFT变换 验证函数ifft46的程序ex406 m如下 程序ex406 m 1 22 1 2 1 2 k N X kX kX kN XkX kX kN W ep1 op2 1 Re DFT 2 1 jIm DFT j 2 y ny ny nYkx n y ny ny nYkx n 1 2 2 1 2 n xn x n n xn 偶数 奇数 5 调用fft函数计算IDFT x1n 1 输入单位脉冲序列x1n x2n 1 1 1 1 1 1 1 1 输入矩形序列向量x2n x3n 1 2 3 4 4 3 2 1 输入三角序列序列向量x3n N 8 X1k fft x1n N 计算x1n的N点DFT X2k fft x2n N 计算x2n的N点DFT X3k fft x3n N 计算x3n的N点DFT x1n ifft46 X1k N 调用ifft46函数计算X1k的IDFT x2n ifft46