《数字电子技术课件——张瑜慧——第4章 (2)》由会员分享，可在线阅读，更多相关《数字电子技术课件——张瑜慧——第4章 (2)（63页珍藏版）》请在金锄头文库上搜索。
1、第4章 快速傅里叶变换(FFT)引言DFT是数字信号分析与处理中的一种重要变换。但直接计算DFT的计算量太大，所以在快速傅里叶变换FFT(Fast Fourier Transform)出现以前，直接用DFT算法进行谱分析和信号的实时处理是不切实际的。直到1965年提出DFT的一种快速算法以后，情况才发生了根本的变化。4.2 基2FFT算法一、DFT的计算工作量以正变换为例：计算所有的X(k)就要N 2次复数乘法运算, N(N-1)N 2次复数加法运算。当N很大时,运算量将是惊人的,如N=1024,则要完成 1048576 次(一百多万次)运算。这样,难以做到实时处理。通常x(n)和 都是复数,
2、所以计算一个X(k) 的值需要N 次复数乘法运算,和N-1次复数加法运算 。l算法基本思想：FFT算法就是不断地把长序列的DFT分解成几个短序列的DFT，并利用 的周期性和对称性来减少DFT的运算次数。回顾： 的性质有关系数关系：利用这些性质可大大减少DFT的计算量，用这 种方法计算DFT称为快速傅里叶变换（FFT)。FFT分按时间抽取(DIT)和按频率抽取(DIF)两大类。二、 按时间抽取法基2 FFT算法原理(一) N/2点DFT1、先将x(n)按n的奇偶分为两组作DFT，设N=2L ,不足时可补零。这样有:n为偶数时:n为奇数时:下面用x1(r)和x2 (r)来求x(n)的DFT。(一)
3、 N/2点DFT2、两点结论:(1) 、 均为N/2点的DFT。(2) 只能确定出 的N/2个值（即前一半的结果）(一) N/2点DFT(一) N/2点DFT3、X(k)的后一半的确定由于 （周期性）,所以:(一) N/2点DFT可见, X(k)的后一半，也完全由X1(k), X2 (k)确定。N点的DFT可由两个N/2点的DFT来计算.(一) N/2点DFT4、蝶形运算蝶形运算，运算结构如下：(一) N/2点DFT例如 N=8时的DFT,可以分解为两个N/2=4点的DFT 。具体方法如下: (1)n为偶数时,即 分别记作:(一) N/2点DFT(2) n为奇数时,分别记作:(一) N/2点D
4、FT整个过程如下图所示:X1(0)X1(1) X1(2)X1(3)X2(0) X2(1)X2(2)X2(3)x1(0)=x(0) x1(1)=x(2) x1(2)=x(4)x1(3)=x(6) x2(0)=x(1) x2(1)=x(3) x2(2)=x(5) x2(3)=x(7) N/2点 DFTN/2点 DFTW0 NX(0)X(4)W1 NX(1)X(5) W2 NX(2)X(6) W3 NX(3)X(7)(1)N/2点的DFT运算量: 复乘次数:复加次数: (2)两个N/2点的DFT运算量:上述次数的2倍； (3)N/2个蝶形运算的运算量:复乘次数: 复加次数: (一) N/2点DFT5
5、、运算量分析按奇、偶分组后的计算量：(一) N/2点DFT总共运算量:复乘 :复加:比较N点DFT的运算量，N点DFT的复乘为N 2 ;复加N(N-1);与分解后相比可知,计算工作量差不多减少一半。 (二) N/4点DFT由于N=2L ,所以 N/2仍为偶数,可以进一步把每个N/2点的序列再按其奇偶部分分解为两 个N/4的子序列。例如，n为偶数时的 N/2点分解为:分解后的每个序列进行N/4点的DFT,得到(二) N/4点DFT从而有：(二) N/4点DFT同样对n为奇数时，N/2点分为两个N/4点 的序列:分解后的每个序列进行N/4点的DFT,得到(二) N/4点DFT从而有：(二) N/4
6、点DFT利用可约性： 可将系数 化为统一的点数。 如下所示：(二) N/4点DFT例如，N=8时的DFT可分解为四个N/4的 DFT， 具体步骤如下:（1）序列分解(二) N/4点DFT同样：分别构成4个N/4点DFT，从而得到X3(0)、X3(1) 、X4(0)、X4(1) 、X5(0)、X5(1) 、X6(0)、X6(1) 。(二) N/4点DFT（2）蝶形运算由 X3(0), X3(1), X4(0), X4(1)进行碟形运 算, 得到X1(0), X1(1), X1(2), X1(3)。由 X5(0), X5(1), X6(0), X6(1)进行碟形运算, 得到X2(0), X2(1)
7、, X2(2), X2(3)。由X1(0), X1(1), X1(2), X1(3) ， X2(0), X2(1), X2(2), X2(3)再进行碟形运算, 得到X(0), X(1), X(2), X(3) X(4), X(5), X(6), X(7)(二) N/4点DFT(二) N/4点DFT这样,又一次分解,得到四个N/4点DFT,两级蝶形 运算,其运算量又大约减少一半。对于N=8时DFT,N/4点即为两点DFT,也可以用蝶形 运算实现，如下所示： (二) N/4点DFT也即：8点DIT-FFT运算流图这种FFT算法,是在时间上对输入序 列次序的奇偶性进行分 解的，所以 称作按时间抽取的
8、算法（DIT）三、DIT-FFT与DFT运算量的比较N=8需三级蝶形运算 N=23=8，由此可知，N=2M 共需M级蝶形运算, 而且每级都由N/2个蝶形运算 组成，每个蝶 形运算有一次复乘，两次复加。N点的FFT的运算量为：复乘次数： (N/2)*M=(N/2) log2 N复加次数：N*M=Nlog2 NN点的DFT直接计算的运算量为：复乘次数： N*N复加次数：N*（N-1）三、DIT-FFT与DFT运算量的比较四、 DIT-FFT的运算规律及编程思想1、原位运算输入数据、中间运算结果和最后输出均用同一存储器由运算流图可知，基2 FFT算法一共有 log2 N=M级蝶形运算，每一级共N/2
9、个蝶形运 算，而且每个蝶形仅与蝶形的2个输入有关， 也仅有2个输出值，这4个值均与其它蝶形运 算无关，而且2个输入值在计算完输出值后没 有其它用途。因此，可用2个输入单元保存2个输出值。即实现所谓原位运算。四、 DIT-FFT的运算规律及编程思想l2、旋转因子的变化规律N点DIT-FFT运算流图中，每级都有N/2个蝶形 。每个蝶形都要乘以旋转因子 ，p为旋转因 子的指数。但各级的旋转因子和循环方式都有 所不同。为了编写计算程序，应先找出旋转因 子与运算级数的关系。用L表示从左到右的运算 级数(L=1，2，M)。第L级共有2L1个不同 的旋转因子。N=23=8时的各级旋转因子表示如 下：四、 D
10、IT-FFT的运算规律及编程思想对N=2M的一般情况，第L级的旋转因子为四、 DIT-FFT的运算规律及编程思想因为 所以 按上两式确定第L级运算的旋转因子(实际编程序时，L为最外层循环变量)。四、 DIT-FFT的运算规律及编程思想3 蝶形运算规律设序列x(n)经倒序后，存入数组A中。如果蝶形运算的两个输入数据相距B个点，应用原位计算，则蝶形运算可表示成如下形式： 式中下标L表示第L级运算，AL(J)则表示第L级运算后的数组元素A(J)的值（即第L级蝶形的输出数据）。而AL1(J)表示第L级运算前A(J)的值（即第L级蝶形的输入数据）。四、 DIT-FFT的运算规律及编程思想4、编程思想 运
11、算规律：l第L级中，每个蝶形的两个输入数据相距B=2L 1个点；l每级有B个不同的旋转因子；l同一旋转因子对应着间隔为2L点的2ML个蝶形 。四、 DIT-FFT的运算规律及编程思想5、 序列的倒序由图可知，输出X(k)按正常顺序排列 在存储单元，而输入是按顺序:这种顺序称作倒序。造成这种排列的原因是序列按下标是 否奇偶数抽取而引起的。四、 DIT-FFT的运算规律及编程思想形成倒序的树状图n =00n =10n =01n =11n =01n =110 10 10 10 1(n2) x(000) 0 x(100) 4 x(010) 2 x(110) 6x(001) 1 x(101) 5 x(0
12、11) 3 x(111) 7（偶）（奇）四、 DIT-FFT的运算规律及编程思想0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 4 2 0 1 0 0 1 0 2 3 0 1 1 1 1 0 6 4 1 0 0 0 0 1 1 5 1 0 1 1 0 1 5 6 1 1 0 0 1 1 3 7 1 1 1 1 1 1 7 自然顺序n 二进制n n n 倒位序二进制n n n 倒位顺序n2 1 0 0 1 2四、 DIT-FFT的运算规律及编程思想一、算法原理 1. N点DFT的另一种表达形式五、频域抽取法FFT(DIF-FFT)由于 故 因此 X(k)可表为五、频域抽取法FFT(D
13、IF-FFT)2.N点DFT按k的奇偶分组可分为两个N/2点 DFT当k为偶数,即 k=2m时,(-1)k =1当k为奇数,即 k=2m+1 时 (-1)k =-1这时 X(k)可分为两部分：k为偶数时：五、频域抽取法FFT(DIF-FFT)k为奇数时：令五、频域抽取法FFT(DIF-FFT)3.蝶形运算X(k)按奇偶k值分为两组，其偶数组是x1(n)的 N/2点DFT，奇数组则是x2(n)的N/2点DFT。五、频域抽取法FFT(DIF-FFT)4.N=8时,按k的奇偶分解过程先蝶形运算，后DFT:五、频域抽取法FFT(DIF-FFT)再将N/2点DFT按k的奇偶分解为两个N/4点 的DFT,
14、如此进行下去,直至分解为2点DFT。例如 N=8时DIF的FFT流图如下：五、频域抽取法FFT(DIF-FFT)5、DIF法与DIT法的异同 相同点：(1)进行原位运算；(2)运算量相同复乘：（N/2) Log2N次,复加：N Log2N次 。 不同点：(1)DIT输入为倒序,输出为自然顺序；DIF 正好与此相反。(2)蝶形运算不同。五、频域抽取法FFT(DIF-FFT)六、IDFT算法方法1：比较两者差别：（1）把DFT中的每一个系数 改为 ，（2）再乘以常数 1/N 。方法2： 由故 将X(k)取共轭（虚部乘以-1） 对 直接作FFT 对FFT的结果取共轭并乘以1/N，得x(n)六、IDFT算法七、FFT的应用实数序列的FFT以上讨论的FFT算法都是复数运算,包括 序列x(n)也认为是复数，但实际存在的信号是 实数序列。 如果把实信号看成虚部为零的复信号 (x(n)+j0), 再用FFT求其离散傅里叶变换。这 种作法也可以，但很不经济，因为把实序列变 成复序列，存储器要增加一倍，且计算机运行 时，即使虚部为零，也要进行涉及虚部的运算 ，浪费了运算量。合理的解决方法是利用复数FFT对实数进 行有效计算，下面介绍两种方法。（1）用一个N点FFT同时计算两个N点
