第十二讲_数字信号处理-频抽取fft-ifft第十二讲_数字信号处理-频率抽取fft-ifft第十二讲_数字信号处理-频率抽取fft-ifft第十二讲_数字信号处理-频率抽取fft-ifft.ppt

第2章 DFT及其快速算法 2-1 周期序列 2-2 离散傅立叶级数 2-3 离散傅立叶变换 2-4 频率采样理论 2-5 快速傅立叶变换 2-6 离散傅立叶反变换（IDFT) 的运算 一个完整N=8的按时间抽取FFT的运算流图 x(0) x(4) x(2) x(6) x(1) x(5) x(3) x(7) X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) m=0 m=1 m=2 2.5.3 频率抽取基－2 FFT 算法（DIF) 将x(n)按前后分为两组： N/2点 DFT N/2点 DFT 前 后 将N=8点分解成2个4点的DFT的信号流图 4点 DFT x(0) x(1) x(2) x(3) 4点 DFT x(4) x(5) x(6) x(7) X(0) X(2) X(4) X(6) X(1) X(3) X(5) X(7) X1(k) 前半部分序列 后半部分序列 x1(n) x2(n) X2(k) 完整N=8的按频率抽取FFT的运算流图 x(0) x(1) x(2) x(3) x(4) x(5) x(6) x(7) X(0) X(4) X(2) X(6) X(1) X(5) X(3) X(7) m=0 m=1 m=2 DIF与DIT比较 不同之处： （1）DIF与DIT两种算法结构倒过来。 DIF为输入顺序，输出乱序。运算完毕再运行“二进制倒读”程序。 DIT为输入乱序，输出顺序。先运行“二进制倒读”程序，再进行求DFT。 （2）DIF与DIT根本区别：在于蝶形结不同。 DIT的复数相乘出现在减法之前。 DIF的复数相乘出现在减法之后。 X1(k) X2(k) DIT DIF 2-6 计算IFFT 将下列两式进行比较 一、改变FFT流图系数的方法1.思路 在IFFT的运算中，常常把1/N分解为(1/2)m，并且在M级运算中每一级运算都分别乘以1/2因子，就可得到IFFT的两种基本蝶形运算结构。（并不常用此方法） 2.IFFT的基本蝶形运算 A B A B (a)频率抽取IFFT的蝶形运算 (b)时间抽取IFFT的蝶形运算 时间抽取和频率抽取的概念要倒一下 四.直接利用FFT流图的方法1.思路 前面的两种IFFT算法，排程序很方便，但要改变FFT的程序和参数才能实现。 现介绍第三种IFFT算法，则可以完全不必改动FFT程序。 2.直接利用FFT流图方法的推导 此为DFT可用FFT程序 实序列的FFT 运算 ∵ FFT算法为同址运算，且 X(k)一般为复数， ∴存放的数组应该是复数数组，但输入序列 x(n) 通常为实序列，存放到复数数组中时，造成存储空 间及运算时间的浪费，为提高存储空间利用率及提 高运算速度： 1. 通过一个N 点FFT运算 ，同时求出两个 独立的N 点实序列的DFT 设 x(n)与y(n)为实 序列。 令 N点FFT 由傅立叶变换的奇偶虚实性 2. 用一个N点FFT运算，求一个2N点实序列 的DFT 设x(n)为2N点实序列,令g(m)=x(2m) , h(m)=x(2m+1) 且 N点FFT 再由时间抽取基－2 FFT算法 补0 IDFT DFT 补0 DFT 圆周卷积 线性 卷积 用FFT实现线性卷积 任意基数的FFT算法 N点分解为p个q点DFT或q个p点DFT 任意基数的FFT算法 N点分解为p个q点DFT或q个p点DFT