资源描述：
《数字电子技术课件——张瑜慧——第4章 (2).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第4章快速傅里叶变换(FFT)引言DFT是数字信号分析与处理中的一种重要变换。但直接计算DFT的计算量太大，所以在快速傅里叶变换FFT(FastFourierTransform)出现以前，直接用DFT算法进行谱分析和信号的实时处理是不切实际的。直到1965年提出DFT的一种快速算法以后，情况才发生了根本的变化。4.2基2FFT算法一、DFT的计算工作量以正变换为例：计算所有的X(k)就要N2次复数乘法运算,N(N-1)≈N2次复数加法运算。当N很大时,运算量将是惊人的,如N=1024,则要完成1048576次(一
2、百多万次)运算。这样,难以做到实时处理。通常x(n)和都是复数,所以计算一个X(k)的值需要N次复数乘法运算,和N-1次复数加法运算。算法基本思想：FFT算法就是不断地把长序列的DFT分解成几个短序列的DFT，并利用 的周期性和对称性来减少DFT的运算次数。回顾：的性质有关系数关系：利用这些性质可大大减少DFT的计算量，用这种方法计算DFT称为快速傅里叶变换（FFT)。FFT分按时间抽取(DIT)和按频率抽取(DIF)两大类。二、按时间抽取法基2FFT算法原理(一)N/2点DFT1、先将x(n)按n的奇偶分为两
3、组作DFT，设N=2L,不足时可补零。这样有:n为偶数时:n为奇数时:下面用x1(r)和x2(r)来求x(n)的DFT。(一)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
4、例如N=8时的DFT,可以分解为两个N/2=4点的DFT。具体方法如下:(1)n为偶数时,即分别记作:(一)N/2点DFT(2)n为奇数时,分别记作:(一)N/2点DFT整个过程如下图所示: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点DFTW0NX(0)X(4)W1NX(1)X(5)W2NX(2)X
5、(6)W3NX(3)X(7)(1)N/2点的DFT运算量:复乘次数:复加次数:(2)两个N/2点的DFT运算量:上述次数的2倍；(3)N/2个蝶形运算的运算量:复乘次数:复加次数:(一)N/2点DFT5、运算量分析按奇、偶分组后的计算量：(一)N/2点DFT总共运算量:复乘:复加:比较N点DFT的运算量，N点DFT的复乘为N2;复加N(N-1);与分解后相比可知,计算工作量差不多减少一半。(二)N/4点DFT由于N=2L,所以N/2仍为偶数,可以进一步把每个N/2点的序列再按其奇偶部分分解为两个N/4的子序列。例
6、如，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点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)、X
7、5(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),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点DF
8、T(二)N/4点DFT这样,又一次分解,得到四个N/4点DFT,两级蝶形运算,其运算量又大约减少一半。对于N=8时DFT,N/4点即为两点DFT,也可以用蝶形运算实现，如下所示：(二)N/4点DFT也即：8点DIT-FFT运算流图这种FFT算法,是在时间上对输入序列次序的奇偶性进行分解的，所以称作按时间抽取的算法（DIT）三、DIT-FFT与DFT运算量的比较N=8需三级
