知识2 离散傅里叶变换及其快速算法

1、 用Fourier变换来表示序列和线性时不变系统的频域特征，但是频谱是的连续函书，用计算机处理和分析频谱是不方便的。那么就需要像时序信号那样，通过采集把连续信号变为离散信号，也对连续频谱采样而得到离散频谱，然后用数字电路或计算机进行处理和分析。有限长序列在应用中有重要的作用，通过它可以导出另一种Fourier变换表达式，即离散傅里叶变换(DFT)，此为解决频谱离散化的有效方法，同时DFT的高效算法快速傅里叶变换FFT。周期序列一个周期为N的周期序列，对于所有的n，应该满足：周期序列的周期N，一般使用最小周期作为周期。与连续时间周期函数相比，周期序列由于n及N均为整数，周期序列中应用最广泛的序列

2、是：（2-1）上图就是周期序列（N=8），从n=0开始到8取完周期内的所有值。令k = 1时，就是一个周期序列。当n从0依次加1到N-1时，序列取完周期内的所有值，这些值可以看成是Z平面上以原点为圆心的单位圆被N等分的交点的的坐标值。k为其他数值时，的最小周期也许不是N，但是N一定是的周期。的性质很明显：周期性：=对称性：=正交性： 或者 一个周期为N的周期序列，在n=到n=+的范围内仅有N个序列值是独立的其中一个周期内的N个序列值足以表征整个序列的特征。而对于长度为N的有限长序列，只讨论n=0到N-1之间的N个序列值，其余皆为0。此二者在n=0到N-1单位内具有共同性。对于周期为n的周期序列

3、，定义n=0到N-1为主值区间，由主值区间N个序列值组成的有限长序列，称为的主值序列。可以如下表示：（2-2）为矩形序列，即：上一过程称为取主值序列，有限长序列：如果以N为周期进行延拓，则有：（2-3）式2-2和2-3之间表明了周期序列和有限长序列之间的处理关系。即：周期序列可以去主值序列进行分析，然后对再周期延拓得到最后的处理结果。周期延拓的时候，延拓周期和有限长序列的长度不同的时候，序列可能会发生混叠。若为M长的有限长序列，即：（2-5）以N为周期进行延拓，得到周期序列：再取的主值序列：（2-7）关于使（2-5）和（2-7）是否一致的问题：（1） 当N=M时，和是一致的，所以，周期延拓无混

4、叠失真，主值序列和原序列一致相同。（2） 当M/2=N=M时，此时会使得至少不仅含有，还叠加有。说明和是不一致的。因此，在M/2=N=M时会出现部分混叠失真，以下结论：（3） 当N=L1，则有，上式表明，要使圆周卷积等于线性卷积而不产生混叠失真的充要条件是：L=M+N+1若LL12L时，圆周卷积和线性卷积的结果就会完全不一致，将产生全混叠失真。DFT、DTFT和Z变换如果一个有限长序列的，满足收敛条件时，则有，（2-40）（2-41）DFT相应的形式为：（2-42）上式中的。式（2-40）是有限长序列的Z变换，是在Z平面内对的一些特性进行分析时的工具。当Z取单位圆的时候，亦即，则变为是（2-4

5、1），成为的频域特性分析，其中的不是一个固定值，而是一个参变量，可以连续取值。为了便于计算机进行处理，就需要离散化，简单的就是在=0到2的范围内N等分，得到的DFT的形式，亦即（2-42）式，它们之间的关系可以如下表示：（2-43）式（2-43）说明N点的有限长序列的离散傅里叶变换是它的Z变换在单位圆上N个等分点上（，k=0,1,2,3,.,N-1）的采样值，也是它的傅里叶变换在0=2区间N个等分点上的采样，这种关系意味着对于时间有限信号，可以像带限信号进行时域采集而不丢失任何信息一样，可以在频域上进行采样而不丢失任何信息，此正为傅里叶变换中时域和频域对偶关系的反映，有着十分重要的意义。DFT

6、实现了频域的离散化，开辟了频域领域采用数字技术进行处理的领域。频率采样理论采用DFT后实现了频域的采样，同样可以采用频域采样的方法逼近任意一个频率特性，接下来，分析一下频率采样的可行性以及所带来的误差。一个任意序列，满足收敛条件，它的Z变换为：对在单位圆上N个等分点上进行采样，有：，对进行IDFT，得到长度为N点的有限长序列，即：通过对上式进行运算，得到与的关系如下所示：可见，是以N为周期进行周期延拓后所取的主值序列。和时域采样会造成频域周期延拓一样，频域采样同样会造成时域的周期延拓。如果是有限长序列，序列的长度为M，即：若N=M，即：这就是频域采样定理，此时即为的N点离散傅里叶变换。当为无限

7、长序列时，必然会产生存在混叠失真，只能随着采样点数N的增加，而逐渐逼近于。对于有限长序列，在满足频域采样定理的前提下，N点频域采样就足以不失真地代表序列的特性。因此，由N点采样值能够完全地表达整个函数及频域特性。快速傅里叶变换（FFT）快速傅里叶变换（FFTFast Fourier Transform）是快速计算DFT的有效算法。离散傅里叶变换实现了频域的离散化，在数字信号处理中有着重要的作用，包括分析信号的频谱、计算滤波器频域响应以及实现信号通过线性系统的卷积运算。DFT的运算特点一个有限长度为N的有限长序列的离散傅里叶变换为：一般说来和都是复数，按照一般定义来计算，计算一点值需要N次复数相

8、乘运算，次的复数相加运算。计算全部N点则需要次复数相乘运算和次的复数相加运算。由于一个复数运算包含4个实数相乘和两个实数加法，所以，计算全部的需要实数相乘运算和次复数相加运算。 由于DFT的运算量和成正比，所以将长序列的DFT分解成短序列的DFT计算，可是运算量得到明显的减少。快速傅里叶变换正是利用的特性，逐步将N点序列分解为较短的序列，计算短序列的DFT，然后再组合成原序列的DFT，使得运算量显著减少。FFT算法分为两类：时间抽取法和频域抽取法。时间抽取基-2 FFT算法设序列长度N为2的整数幂次方（实际应用中常常如此选取）：，其中M为正整数，分为两组，偶数项为一组和奇数项为一组得到两个点的

9、子序列，即：相应的DFT运算也可以分成两组： （2-54） 假定、分别是和的DFT，亦即：上两式的取值范围为，式2-54的取值范围为。由式子2-54可知，、分别为为主值序列的周期序列因此、应该周期性的重复一次，所以式子2-54可以写成下面的形式：（2-57）式中出现的负号是由于。式2-57的运算关系可用信号流图表示成蝶形运算的形式，左两路为输入，中间一个小圆点表示加减运算，右上支路为相加后的输出，右下支路为相减后的输出，箭头旁边的系数表示相乘的数。因流图形如蝴蝶，故称为蝶形运算。每个蝶形运算需要一次复数相乘，两次复数加法运算，如下图所示，还有8点DFT分解运算过程，接下来估算一下乘法的运算量，

10、每一个N/2点的DFT需要次复数相乘，两个N/2点DFT共需要次复数相乘，组合运算共需N/2个蝶形运算，需要N/2次复数相乘，因而共需要次复数相乘，N比较大时，可以近似认为等于，与直接计算相比节约一半的运算量。由于，如果大于2，可继续进行N/2点序列分解成两个N/4点的序列。如将分解为：有：其中，它们均为N/4点的DFT。这样序列长度又减为一半，对应于8点的前一个N/2点的DFT再分解为两个N/4点DFT流图。当然，也是如此，直到最后的两点的DFT为止。2点的DFT同样可用一个蝶形运算表示。例如，8点的第一个2点DFT由和组成，就可以表示为：整个个流图全由蝶形组成，蝶形运算是FFT的核心，是最

11、基本的运算。对于一个的序列，可以逐步分解为最后全为2点的DFT运算。这样就构成了从到的M次逐级进行运算过程，每一级均由N/2个蝶形运算构成。全部的N点的FFT运算共有个蝶形运算，共需：复数乘法次数：复数加法次数：计算量显著减小，N值愈大，减少的量更大。下面分别是序列长度N为8点和16点的时间抽取FFT算法实现的流图， 流图中各蝶形运算的输入和输出量是互不重叠的，任何一个蝶形运算的两个输入量经过蝶形运算后，便失去了利用价值，不再需要保存，因此可以实现同址运算，同址运算也可以节省空间。离散傅里叶反变换（IFFT）的运算方法FFT的算法同样适用于IDFT运算，简称IFFT，即快速傅里叶反变换，IDFT定