数字信号处理(丁玉美版)教案第4章.ppt

第四章 快速傅立叶变换 （FFT） Fast Fourier Transform 数字信号处理 1 4.1 引言 DFT 是数字信号处理的基础，是 一种重要变换。 快速算法的引出，使数字信号处 理技术得到广泛应用。 各种快速算法不断被采用 2 数字计算机 N足够大 .1.1 DFT提供了计算机处理的可能性 模拟信号的频谱分析 4.1.2 DFT的运算量 k=0,1,2,N1 计算机运算时： 3 N项 N 个 计算一个 N点DFT ，共需次复乘。以做 一次复乘1s计，若N =4096，所需时间为 由于计算量大，且要求相当大的内存， 难以实现实时处理，限制了DFT的应用。 4 长期以来，人们一直在寻求一种能提高 DFT运算速度的方法。FFT便是Cooley N=length(X); x=fft(conj(X),N); x=conj(x/N) 39 Example : 用FFT算法计算下面信号的 8点DFT； x(n)=4 3 2 0 1 2 3 1 然后，再用 IFFT恢复原信号。 40 solution: 2 2 2 2 2 2 41 IFFT(X)=1/NFFT(X*)* 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 乘以1/N=1/8 得原序列 42 4.2.4 FFT的计算成本 最简单的FFT 是Cooley-Tukey法 因为 N点DFT有M级蝶形运算，每一级都有N/2个 蝶形运算结构； 每个蝶形运算结构都有1次复数乘和2次复数 加； 43 44 所以，M级蝶形运算有复数乘 M级蝶形运算有复数加 45 直接DFT的复数乘和复数加均近似为 。当 N1时， 所以DIT-FFT大大减少了运算次数。 46 Example : for N=8 Solution : M= =3 stages（三级） for FFT, the total cost is （FFT的总计算成本是） MN/2=38/2=12 complex multiplications （复数乘） 47 for directly DFT, the total cost is （直接计算DFT的成本是） N=8=64 (complex multiplications) The ratio is: （比值是） 实际上，当N=2048时，直接运算与 FFT算法的计算量之比为372.4 48 4.2.5 DIT-FFT的运算规律及编程思想 1、原位运算： 利用同一单元存储蝶形计算的输入、输出 数据。 每个蝶形的输入和输出均为相同位数。 原位运算可节省大量内存，因而硬件成本低。 2、旋转因子的变化规律： N点DFT，共有M级蝶形运算，每级有N/2 个蝶形。 49 称为旋转因子，p称为旋转因子的指数。 为了编写程序，应找出旋转因子 与运算 级数的关系。 设L=1，2，M，表示从左到右的运算 级数，第L级有 个不同的旋转因子， 50 对于 ，各级的旋转因子表示为 L=1时， L=2时， L=3时， 51 对于 的一般情况，第L级的旋转因子为 ， 由于 52 所以 通过上式，可以计算第L级运算的旋转因子。 53 3、蝶形运算规律 设序列x（n）经过时域倒序存入数组X 如蝶形运算的两个输入数据相距B个点， 应用原位运算，可得： 54 4、编程思想及程序框图 其它运算规律： 第L级中，每个蝶形的两个输入数据相距 个点； 同一旋转因子对应着间隔为 点的 个蝶形（对应第几组蝶形） 55 8点DIT-FFT运算流图 56 编程的运算方法： 从输入端（第1级）开始，逐级进行，共 进行M级运算。 在进行第L级运算时，依次求出 个不同的 旋转因子，然后计算其对应相同的旋转因子的 个蝶形。 可用三重循环程序实现DIT-FFT运算。 57 (3) 58 5、序列的倒置（bit reversal） 倒序是有规律的。 由于 ，所以顺序数可用M位二进制 数（ ）表示。 59 用硬件电路和汇编语言程序产生倒序很容易 ，用高级语言倒序的规律为： 倒序数是在M位二进制数最高位加1， 逢2向右进位。 60 4.2.6 频率抽取法FFT(DIF-FFT) 设序列x（n）长度为 ，将其前后 对半分开，得： 61 式中 62 再将X（k）分解成偶数组和奇数组 k为偶数时： 63 k为奇数时： 64 令 65 得 66 DIF-FFT蝶形运算流图 - + 67 N=8时，DIF-FFT蝶形运算流图 68 注意：DIT-FFT和DIF-FFT的算法流图不 是唯一的。 其变形运算流图见P108。 69 4.3 进一步减少运算量的措施 以程序的复杂度换取计算量的进一步提高。 4.3.1 多类蝶形单元运算 第一级旋转因子可简化： 第二级旋转因子可简化： 称为无关紧要的旋转因子。 70 其复数乘法次数可减少为： CM（2）=（M-2）*N/2 当L=3时，第三级蝶形有两个无关紧要旋转 因子，同一因子对应2(M-L)=N/2L级蝴 蝶结,所以第三级共有(书110页) 71 依次类推，从L=3到L=M共可减少复数乘 法次数为： DIT-FFT的复数乘法次数为： 72 另外， 也可用实数乘法减少计算量。 包含所有旋转因子称为一类蝶形单元运算； 去掉 为二类； 去掉 为三类； 依次类推，称为多类蝶形单元运算。 N=4096时，三类与一类比，仅75%。 73 4.3.2 旋转因子的生成 直接查表，提高速度，多占内存。 4.3.3 实序列的FFT算法 两个实序列，构造序列y（n） 74 由于x（n）为实序列，所以X（k）具有共轭 对称性： 75 4.4 分裂基FFT算法 任意基： 基较大，则程