数字信号处理第三章FFT.pptVIP

2、分解方法不唯一，算法程序（流图）随之不同 如：N = 12 = 4×3 = 2×2×3 ＝ 2×3×2 ＝ 3×2×2 ＝ 3×4 1、因子多时，逐步分解 五、算法说明 3、适应性与运算量的节省 混合基最优 基2需补零 4、程序与控制（硬件实现时） 基 2 最简单 *3.4.4 N 为复合数的 FFT 算法 基4 FFT是混合基FFT的一个特例 混合基FFT算法 补充材料见课程主页 DFT IDFT N 点FFT 共轭 共轭 3.4.5 IDFT的快速计算方法 N 点FFT 3.5 FFT 的应用 3.5.1 线性卷积的快速计算 线性卷积是数字信号处理中最有用、最常用的运算， 非常需要以低运算量的方法来实现。 （1）有限长序列的线性卷积 直接计算线性卷积，需 NM 次复乘，以及复数加法 M N N N n 0 1 2 … … … … … … … N+M-2 乘法次数 1 2 3… N-1 N … N N-1 … 3 2 1 … 计算量？ 3.5.1 线性卷积的快速计算 线性卷积和周期卷积的关系 线性卷积的快速计算 ② ④ ③ 复乘次数 复加次数 L 0 计算量 ① 补零 快速计算线性卷积，做 3个 L 点 FFT ，频域 L 点复数乘。 用 FFT 快速计算线性卷积 3.5.1 线性卷积的快速计算 （1）有限长序列的线性卷积（续） 例2、 N = M = 32 1024 640 在什么情况下，快速卷积法的运算量低于直接计算线性卷积？ 直接计算线性卷积 快速卷积（用基2FFT） 例1、 N = M = 16 乘法 NM = 256次 乘法 取 需 取 需 取 需 取 需 例3、 N= M = 64 4096 1472 例4、 N = 240，M = 10 2400 3328 N 与 M 接近，两者均较大 此时，L 越大，降低运算量的效果越明显 哪个计算量小？ 3.5.1 线性卷积的快速计算 直接卷积 快速卷积 N 与 M 接近，两者均较大时，快速卷积法的运算量低于直接计算线性卷积； L 越大，降低运算量的效果越明显 复数乘次数之比 为了做基2 FFT，取 大于1，快速卷积的运算量低于直接卷积 越大，快速卷积的优越性越明显 3.5.1 线性卷积的快速计算 h(n) 长 M ，x(n) 很长（ N M ）或无限长（N ? ?）时。 将x(n)分段，使得 N 与 M 接近；每一段做快速卷积；组合。 2、分段卷积 已知h(n)的长度M，自定 N 和 L。如何定？ 如何使计算高效、占用存储单元少、输入与输出之间的时间延迟小（实时性好）？ 必须满足 L ? M 为运用基2-FFT，要 L=2r 作业（要求：写出推导、证明过程） 3.24 （直接计算DFT、用基2 DIT-FFT计算DFT的计算量） 3.25 （直接计算8点DFT。要求：写出过程） 3.26 （用8点基2 DIT。要求：公式推导，画出流图，算出每列每点处的数值） 3.28? （提示：用两个实序列构成一个复序列，再利用DFT的性质之一） 3-A 独立地推导16点基4 FFT，写出公式；画出16点基4 FFT流图，标出所有系数。 3-B 推导N＝3x4的混合基FFT。画出流图，箭头上标出系数。 数字信号处理Digital Signal Processing 3.4 快速傅里叶变换 （1）DFT 计算量大，妨碍其实际应用。 反变换 正变换 计算任一个 X(k) 需复数乘法 N 次，复数加法 N－1 次 全部 X (k) N 2 次， N ( N － 1)次 减少运算量，是 DFT 走向实际应用的关键 与正变换形式相似，只差常数 1/N，计算量几乎相同 工程上一般取 N = 1024，则需 N 2 ＝220 次复乘 计算量和 N 2 成正比 百万次 一次复乘需 4 次实乘和 2 次实加 可约性 （2）系数 的