第4章离散变换及其快速算法

《测试信号分析与处理》课程

第四章离散傅里叶变换及其

快速算法

第一节序列的傅里叶变换（DTFT）第二节离散傅里叶级数（DFS）第三节离散傅里叶变换（DFT）第四节离散傅里叶变换的性质《测试信号分析与处理》课程第五节快速傅里叶变换（FFT）第六节IDFT的快速算法（IFFT）第七节实序列的FFT高效算法第八节用FFT计算线卷积和相关运算第九节MATLAB中用于FFT计算的函数简介第一节序列的傅里叶变换一、定义已知序列的Z变换为如X(Z)在单位圆上是收敛的，则将在单位圆上的Z变换定义为序列的傅里叶变换，即由于序列的傅里叶变换定义为单位圆上的Z变换，因此其同Z变换具有相同的性质。第一节序列的傅里叶变换二、物理意义与存在条件连续信号的傅里叶反变换为Z反变换的围线积分公式为将积分围线c取在单位圆上，则有第一节序列的傅里叶变换两者相比前者是连续信号不同频率的复指数分量，后者是序列不同频率的复指数分量；两者都是频域中频率的概念，

ω表示模拟角频率，Ω表示数字角频率；前者是连续信号在时域的表示，可以分解为一系列不同频率的复指数分量的叠加，分量的复振幅为

，后者是序列在时域的表示，可以分解为一系列不同数字角频率分量的叠加，分量的复振幅为。第一节序列的傅里叶变换前者有连续信号频谱密度的意义，是频谱的概念，后者是序列的傅里叶变换，可以看作是序列的频谱。ω是模拟角频率，变化范围是没有限制的，高频部分可以趋于∞；而数字角频率Ω的变化虽然是连续的，但变化范围限制在±π内序列的傅里叶变换对第一节序列的傅里叶变换

序列的傅里叶变换既然定义为单位圆上的Z变换，所以它的存在条件是序列的Z变换必须在单位圆上是收敛的，即

上式说明序列的傅里叶变换存在的条件是序列必须绝对可和。第一节序列的傅里叶变换

三、特点与应用非周期序列的傅里叶变换（频谱）的特点在于它是的连续周期函数，其周期为。序列x(n)与其傅里叶变换两者正好是互为傅里叶级数的变换关系。第一节序列的傅里叶变换

序列可以表示为复指数序列分量的叠加，适用于叠加原理在线性时不变系统的分析。这种系统对复指数序列的响应完全由系统的频率响应确定。一个线性时不变系统对于输入的输出响应，就是对它的每个复指数序列分量的响应的叠加，则输出响应应为则输出的傅里叶变换为第二节离散傅里叶级数（DFS）一、傅里叶变换在时域和频域中的对称规律a)时域上的非周期性对应频域上的连续性第二节离散傅里叶级数（DFS）b)时域上的周期性将产生频域的离散性。第二节离散傅里叶级数（DFS）c)时域上的离散性将产生频谱的周期性。

第二节离散傅里叶级数（DFS）d)时域上的离散周期信号，其频谱是周期离散的。

第二节离散傅里叶级数（DFS）一个域中（时域或频域）是连续的，对应另一个域中（频域或时域）是非周期的。一个域中（时域或频域）是离散的，对应另一个域中（频域或时域）是周期的。

第二节离散傅里叶级数（DFS）二、离散傅里叶级数离散周期信号的频谱，即离散傅里叶级数(DFS)。离散傅里叶级数的变换对表达式其中

第三节离散傅里叶变换（DFT）一、离散傅里叶变换DFT定义式离散傅里叶变换就是对有限长序列进行傅里叶变换的表示式。主值序列：对于一个周期序列，定义它的第一个周期的有限长序列值为此周期序列的主值序列，用表示为主值序列也可以表示为周期序列和一个矩形序列相乘的结果，即第三节离散傅里叶变换（DFT）

周期序列也可以看作是长度为N的有限长序列以N为周期延拓而形成了。有了主值序列的概念，再来考察DFS的定义式，只需用主值序列，即可求出并完全地表达周期无限长序列，，这样就得到了任意有限长序列的离散傅立叶变换对第三节离散傅里叶变换（DFT）矩阵形式或

第三节离散傅里叶变换（DFT）例4-1

用矩阵表示式求矩形序列的DFT，再由所得经IDFT反求，验证所求结果的正确性。解：，故

再由反变换求第三节离散傅里叶变换（DFT）

第三节离散傅里叶变换（DFT）二、DFT的物理意义设一有限长序列的长度为N点，其Z变换为因序列为有限长，满足绝对可和的条件，其Z变换的收敛域必定包含单位圆在内，则序列的傅里叶变换，即单位圆上的Z变换存在，且为第三节离散傅里叶变换（DFT）以为间隔，把单位圆均匀等分为N个点，则在第k个等分点，即点上的值为故有限长序列的离散傅里叶变换DFT是这一序列频谱（序列傅里叶变换）的抽样值。第三节离散傅里叶变换（DFT）有限长序列的DFT就是序列在单位圆上的Z变换（即有限长序列的傅里叶变换或频谱）以为间隔的抽样值

第四节离散傅里叶变换的性质线性特性

若，则式中a、b为任意常数。如果两个序列的长度不相等，以最长的序列为基准，对短序列要补零，使序列长度相等，才能进行线性相加，经过补零的序列频谱会变密，但不影响问题的性质。第四节离散傅里叶变换的性质时移特性

1）圆周移位序列将长度为N的序列进行周期延拓，周期为N，构成周期序列，然后对周期序列作m位平行移位处理，得移位序列，再取其主值序列（与一矩形序列相乘），得到的就是圆周移位序列。第四节离散傅里叶变换的性质

第四节离散傅里叶变换的性质2）时移定理若

则时移定理表明，序列在时域上圆周移位，频域上将产生附加相移，对上式进行反变换可以得到

第四节离散傅里叶变换的性质频移特性

若则上述特性说明，若序列在时域上乘以复指数序列，则在频域上将圆周移位，这可以看作调制信号的频谱搬移，因而又称为“调制定理”。第四节离散傅里叶变换的性质圆周卷积特性1）时域圆周卷积若对N点序列有，，，则2）频域圆卷积若第四节离散傅里叶变换的性质实数序列奇偶性（对称性）设x(n)是实序列，则X(k)的幅度和相位分别为他们分别为k的偶函数和奇函数，并分别具有半周期偶对称和奇对称的特点。第四节离散傅里叶变换的性质帕斯瓦尔定理若，则式左端代表离散信号在时域中的能量，右端代表在频域中的能量，该式表明变换过程中能量是守恒的。第五节快速傅里叶变换一、DFT运算的特点1.DFT直接运算的工作量

N点序列x(n)的DFT为按定义计算DFT时，需作次复数乘和次复数加。由于直接计算量非常大，不可能实现信号的实时处理，因此必须改进DFT的算法。第五节快速傅里叶变换2.DFT运算特点

1)的周期性2)的对称性

因为故第五节快速傅里叶变换3)的可约性第五节快速傅里叶变换利用上述结果，如对应于N=4的矩阵W可以简化为上式右端的矩阵中的元素有许多是相等的，计算量明显减少。由原来的16个元素变成只有两个独立元素需要计算。

第五节快速傅里叶变换二、基2时析型FFT算法（时间抽取法）1.算法原理

对长度为（L为正整数，若原序列的长度不满足此条件，则可用零补足）的序列x(n),按序列各项序号的奇偶将序列分成两个子序列（大点数化为小点数），有偶序号序列奇序号序列其中，两序列的长度均为N/2。且其DFT分别为第五节快速傅里叶变换上式中，右边即为x(n)的前一半DFT值第五节快速傅里叶变换对于另外N/2个点的DFT,即的

，可表示为根据周期性，有由对称性，有

第五节快速傅里叶变换x(n)的DFT最后结果

x(n)的DFT可由奇偶对分序列的DFT合成而获得。该计算关系可用右图来表示。由于图形酷似蝴蝶，所以称之为蝶形图（或蝶形单元）。上式也因而称为蝶形算法。第五节快速傅里叶变换2.算法的具体实现对于长度为的序列逐次奇偶对分，则最后一定能得到N个单项序列（序列的长度为1），而单项序列的DFT就是其本身。因此根据蝶形图，计算N项序列的DFT，只需要按照蝶形算法逐次合成，即由N个1点长序列的DFT合成N/2个2点长序列的DFT，再由N/2个2点长序列的DFT合成N/4个4点长序列的DFT，如此继续下去，最后由两个N/2点长序列的DFT合成N点长序列的DFT。第五节快速傅里叶变换第五节快速傅里叶变换当序列的长度为时，根据基2时析型FFT的算法，可画出如下蝶形图，求出序列的DFT值。第五节快速傅里叶变换3.流程图规律1)蝶形图参数蝶群序号蝶距（序号差）蝶群宽（点数）蝶群数第一级（2点DFT）

第i级（点DFT)第L级（点DFT)第五节快速傅里叶变换2）每个蝶形单元的运算，都包括乘，并与相应的DFT结果加减各一次3）同一级中，的分布规律相同第一级（2点DFT）：

第二级（4点DFT）：；；

第i级(点DFT):;;...;第五节快速傅里叶变换序列输入的自然顺序十进制二进制码码位倒置结果（二进制码）乱序十进制序列乱序的输入顺序4）输入重排

第五节快速傅里叶变换4.运算量比较N（）点的FFT总运算量为复数乘复数加利用基2时析型FFT求序列的DFT同直接计算序列的DFT的复数乘运算次数之比为第六节IDFT的快速算法（IFFT）利用FFT的程序求IFFT的方法先对DFT和IDFT两者的定义式进行比较，二者没有本质上的区别，可以利用FFT流图（蝶形图）来计算IFFT。第六节IDFT的快速算法（IFFT）对DFT的反变换取共轭，有与DFT的正变换式比较可知，完全可以利用FFT的计算程序，只需将作为输入序列，并将最后结果取共轭，再除以N就得到了第七节实序列的FFT高效算法一、同时计算两组实序列的DFT

设有两组长度均为N的实序列和，构成新序列，根据DFT定义因为，，有因此第七节实序列的FFT高效算法解得由此说明用FFT子程序求得的DFT后，

和的DFT（、）可由的DFT()分离出来。第七节实序列的FFT高效算法二、用N点序列的DFT结果获得2N点长实序列的DFT结果将一个2N点的实序列按奇偶顺序对分成两个序列再将和组合成N点的复序列可用N点FFT程序求出y(n)的DFT结果，然后从中分离出实数序列和的DFT结果第七节实序列的FFT高效算法

由于和是的奇偶对分序列，所以的DFT可用蝶形算法合成本节将讨论两有限长序列的圆卷积与线卷积的等价条件，从而将圆卷积的快速算法应用于线性卷积和相关的快速算法中。

第八节用FFT计算线卷积和相关运算

主要内容圆卷积的计算方法一圆卷积与线卷积的关系二用FFT计算有限长序列的线卷积三分段快速卷积——重叠相加法四离散时间序列的相关运算五一、圆卷积的计算方法两个长度均为（如长度不等，将短序列补零至等长）的有限长序列、，其圆卷积定义为

或(5-13)(5-14)

其主要计算方法有下面几种。

一、圆卷积的计算方法1．公式法（解析法）直接利用圆卷积的上述定义式来求解，如下例所述。例5-1设，，计算5点长圆卷积。解：为4点长序列，在其尾部补零使其成为5点长序列，然后进行圆卷积。根据卷积定义式，5点长序列的圆卷积为一、圆卷积的计算方法则时则时一、圆卷积的计算方法同理；；。因此，。

一、圆卷积的计算方法2．图形法先变量置换，然后保持其中的一个序列不动，将另外一个序列进行反折、圆移位，最后将两个序列对应的元素相乘、求和。一、圆卷积的计算方法

由于圆移位的特点，还可以利用同心圆法求圆卷积，如图5-8所示。将、分别分布在两个同心圆上，内圆按顺时针方向刻度，外圈按逆时针方向刻度，并使与对齐。然后将两个圆上的对应值相乘并相加，则得到。再将外圆按顺时针方向旋转一位，对应值相乘并相加，得到，如此下去，直到求出。

一、圆卷积的计算方法

图5-8用同心圆作图求圆卷积

一、圆卷积的计算方法3．矩阵法利用矩阵相乘来计算圆卷积。根据圆卷积的定义，式（5-14）可用矩阵表示为即（5-15）一、圆卷积的计算方法注意:式（5-15）表示序列不动，序列对进行了求模运算。为循环矩阵，其元素排列是有规律的，第一行表示的是原点（）不动时，序列的反折（倒序）；接下来的各行分别是上一行序列的循环右移。一、圆卷积的计算方法4．时域圆卷积定理法利用DFT的一个重要性质――时域圆卷积定理来计算圆卷积。若，则 二、圆卷积与线卷积的关系

线卷积具有明确的物理意义，直接计算比较复杂。对于两个有限长序列求线卷积能否用圆卷积来代替，即采用FFT计算线卷积而使两者结果又完全相同呢？答案是肯定的，但需要满足一个条件：就是将进行线卷积的两序列的长度（设两序列的点数分别为）均通过补零的办法，加长至，然后再进行N点的圆卷积，则圆卷积的结果与线卷积的结果相同。二、圆卷积与线卷积的关系设分别由点通过补零，加长至N点，其线卷积为，可表示为计算结果的长度要多出一些零值，但非零值长度仍为点。

其圆卷积为，可表示为二、圆卷积与线卷积的关系而可得（5-16）式中，下标p表示序列的周期化；是指对线卷积进行周期为N的延拓后得到的周期序列；两序列的圆卷积的结果，是的主值序列。

二、圆卷积与线卷积的关系上述过程说明:加长至N点长的、两序列的圆卷积与线卷积作周期延拓所得到的序列的主值序列相同。在这个条件下（两序列均加长至N点），就可以通过计算序列的圆卷积来求解线卷积。从式（5-16）的推导过程还可以看出，如果两序列不加长至N，其线卷积的周期延拓序列将发生重叠或混叠现象（因为线卷积长度为），相应计算出的圆卷积也将产生失真，圆卷积的主值序列和线卷积就不相同。三、用FFT计算有限长序列的线卷积根据上述圆卷积与线卷积的关系，可以得出用FFT求解两序列线卷积的原理框图，如图5-9所示。其计算的具体步骤如下1）若两序列、的长度为N，将序列加长至2N－1，并应修正为2的幂次（基2算法）；2）计算、；3）计算；4）计算。图5-9用FFT求线性卷积三、用FFT计算有限长序列的线卷积在MATLAB中直接实现线卷积计算的函数有conv,conv2,convn。其中conv2和convn分别用于2维、n维的卷积运算。conv则用于向量卷积与多项式乘的计算，调用的格式为c＝conv（a，b）。式中，a、b表示两个序列，c＝a*b。在MATLAB中，序列可用向量来表示，若向量a的长度为na，向量b的长度为nb，则向量c的长度为na＋nb－1。

四、分段快速卷积——重叠相加法分段快速卷积的方法:将长序列分成若干小段，每小段分别与短序列作卷积运算，然后将所有的分段卷积结果相叠加，就是线卷积的最后结果，这种方法又称为重叠相加法。

四、分段快速卷积——重叠相加法设的长度为M，为一长序列，将进行分段，每段的长度为，将每一段分别与进行线卷积，然后将结果重叠相加，如图5-10所示。图5-10叠加相加法的分段以及的重叠情况

四、分段快速卷积——重叠相加法设将分为第段表示为（5-17）则

（5-18）四、分段快速卷积——重叠相加法由于长度为，的长度为M，故的长度为，即的范围为（5-19）将式（5-19）与式（5-17）的范围比较，显然比长点，而的范围是（5-20）四、分段快速卷积——重叠相加法将式（5-19）与式（5-20）比较，可知的后部分与的前部分，有个点发生重叠。这样，对于在此范围的每一个值，原序列和的卷积之值应为 （5-21）这就是说，式（5-18）中的求和并不是将各段线卷积的结果简单地拼接在一起，在某些点上是需要前后两段的结果重叠相加的。五、离散时间序列的相关运算设序列，，（），称下述运算

为序列和的线性相关。 对和均为实序列的情形，由式（5-22）可以得到

(5-22)

（5-23）

五、离散时间序列的相关运算若序列和是不同的两个序列，则称相关为互相关，若＝，则称相关为自相关。注意：相关和卷积是两个不同的概念，它们的区别是明显的。除了形式上的差异，它们还有一些其他的不同。例如，对相关运算来说，既不具有交换性，也不具有结合性。一般来说，，第九节MATLAB中用于FFT计算的函数简介

MATLAB中提供了多种实现快速变换的函数，如fft，ifft，fft2，ifft2，fftn，ifftn，fftshift，ifftshift等函数。由于MATLAB中没有零下标，因此，它采用的公式上、下标都相应右