DSP-5-2013案例.pptx

第五章 快速傅里叶变换(FFT) 数字信号处理 Digital Signal Processing 中国民航大学 航空自动化学院 本章主要内容 引言 基2FFT算法 进一步减少运算量的措施 2017-4-10 2 FFT：引言 FFT: Fast Fourier Transform 1965 年，James W. Cooley 和 John W. Tukey 在《计算数学》（《Mathematics of Computation》）上发表了“ 一种用机器计算复序列傅立叶级数的算法（An algorithm for the machine calculation of complex Fourier series）” 论文。 自此之后，新的算法不断涌现。一种是对N等于 2 的整数次幂的算法，如基 2 算法，基 4 算法。另一种是N不等于 2 的整数次幂的算法，例如 Winagrad 算法，素因子算法。 Dr. James W. Cooley Worked at IBM Watson Research Center in Yorktown Heights, N.Y..After his retirement from IBM in 1991, he joined the Electrical Engineering Department at the University of Rhode Island. 2017-4-10 3 FFT：直接计算 DFT 的运算量分析 N 点有限长序列 x(n) 的 DFT 变换对的定义为： 其中 假设 x(n) 是复序列， 同时 X(k) 一般也是复数。 FFT：直接计算 DFT 的运算量分析 FFT：直接计算 DFT 的运算量分析 FFT：直接计算 DFT 的运算量分析 计算量分析 N2次复数相乘 N（N-1）次复数相加 如 N=512、1024 和 8192 时，DFT 的乘法运算 N2 = 5122 = 218 = 262144（26万次） N2 = 10242 = 220 = 1048576（105万次） N2 = 81922 = 226 =6千7百万次） N2次复数相乘 N（N-1）次复数相加 一次复数乘法需四次实数乘法和二次实数加法 一次复数加法需两次实数加法 FFT：直接计算 DFT 的运算量分析 采用通用计算机，速度为平均每次复乘为5μs，每次复加为1 μs，所用时间:T=5*10-6 *10242+ 10-6 *1024*1023=6.290s 对于大 N，在实际中是不能接受的，无法“实时”应用 DFT。 一般地，在计算机中，一次加法比一次乘法所需时间要短; 在DSP中，由于乘法用特殊的硬件电路专门完成，因此乘法和加法所需机器周期相同。 Cooley 与 Turkey 提出的 FFT 算法，大大减少了计算次数。如 N =512 时，FFT 的乘法次数约为 2000 次，提高了约 128 倍，而且简化随 N 的增加而巨增，因而，用数值方法计算频谱得到实际应用。 FFT：直接计算 DFT 的运算量分析 FFT：旋转因子的特点 DFT高效运算的可能性分析： 假定x(n)为4点长的信号，对其做4点DFT： 利用旋转因子的4个特点： 计算量？ 计算量？ FFT：旋转因子的特点 显然N值越小越有利！ FFT 算法分类: 时间抽选法 DIT: Decimation-In-Time 频率抽选法 DIF: Decimation-In-Frequency 基本思路： 虽然存在不同的 FFT 方法，但其核心思想大致相同，即通过迭代，反复利用低点数的 DFT 完成高点数的 DFT 计算，以此达到降低运算量的目的。 迭代：利用 WNkn 的周期性、特殊点和对称性，合并 DFT 计算中很多重复的计算，达到降低运算量的目的。 低点数：将傅氏变换 DFT 分解成相继小的DFT计算，即 N 变小，而计算量与 N2 成正比。 FFT：基本思想 FFT：基2时间抽选法-算法原理 算法原理 设序列点数 N = 2M，M 为整数。若不满足，则补零。 将序列 x(n) 按 n 的奇偶分成两组： N 为 2 的整数幂的 FFT 算法称基-2 FFT算法。 即一组由偶数序号组成，另一组由奇数序号组成。 注意其长度为 N/2 注意：这里的k的取值范围为0，1，…，N-1 FFT：基2时间抽选法-算法原理 偶数取样点DFT为： 奇数取样点DFT为： ① k 的整个范围为 0～(N-1)，而X1(k)、X2(k) 是由 N/2 个样点形成的 DFT，x(2r) 和 x(2r＋1）的长度为 N/2； ② 由这两个偶数和