离散傅里叶变换及其快速算法.ppt

离散傅里叶变换及其快速算法概述傅里叶变换实现了从时域到时域到频域的变换，广泛应用于连续信号和离散信号处理技术领域。为了用计算机计算傅里叶变换，对信号和频谱要求如下：信号和频谱的数据长度应该是离散的。本节介绍如何将傅立叶级数和傅立叶变换分析方法应用于离散时间信号，这是从傅立叶变换发展而来的一种变换方法。离散傅里叶变换和快速傅里叶变换从理论上解决了计算机进行傅里叶分析的问题。在离散时间序列中，数字计算机只能处理有限长度的数字信号。因此，连续变化的模拟信号必须先转换成有限的离散时间序列，然后才能被计算机处理。这种转换称为模拟信号数字化。X(t)的采样间隔为，x(t)的离散值在时间t=k时写为xk。xk，k=，-1，0，1，2，3，称为离散时间序列。周期序列的离散分析，连续周期函数x(t)，采样间隔T=T/N，周期序列的离散傅里叶级数，连续周期函数的傅里叶级数x(t):采样间隔T=T/N，周期函数的离散傅里叶级数：离散傅里叶级数的性质，离散傅里叶系数是由N个独立的谐波分量组成的傅里叶级数，离散傅里叶系数也是离散周期的，周期是N，离散傅里叶级数的性质， 公式上的DFS变换表明，虽然一个周期序列是一个无限序列，但只要知道一个周期的内容(一个周期中信号的变化)，根据DFS的周期性，其余周期的所有值都可以得到，所以这个无限序列实际上只有n个序列值的信息是有用的，所以周期序列与有限序列有着本质的关系。 非周期序列的离散时间傅里叶变换(DTFT)/序列的傅里叶变换，将序列x(n)的离散时间傅里叶变换(DTFT)定义为：序列x(n)的离散时间傅里叶逆变换(IDTFT)，傅里叶变换对的总结，傅里叶级数(FS)(时域：连续周期；频域：非周期性离散傅里叶变换(时域：连续非周期性；频域：非周期性连续)离散傅立叶级数(时域：离散周期；频域：周期性离散)离散时间傅立叶变换(DTFT)(时域：离散非周期性；频域：周期连续性)、离散傅立叶变换(DFT)和傅立叶变换对不适用于计算机操作。因为从数字计算的角度来看，我们对时域和频域都是离散的情况感兴趣。然而，在我们的工作中经常需要对有限长度序列进行频谱分析，这就是我们将在这里讨论的离散傅立叶变换。离散傅立叶变换可以由离散傅立叶变换定义。其思想如下：(1)将时域周期序列视为有限长序列x(n)的周期延拓；(2)将频域周期序列视为有限长序列X(k)的周期延拓；(3)这样，只要DFS定义公式的两边(时域和频域)分别取主值区间，就可以得到有限长序列在时频域的相应变换对离散傅里叶变换。离散傅里叶变换的定义和基本概念。现在，有限长序列的傅里叶分析是借助于有限差分法的概念来进行的。设x(n)是一个有限长序列：正变换：逆变换：一般来说，密度泛函简化为上述两个方程，它们可以写成矩阵形式。离散傅立叶变换和DTFT的区别在于，DTFT是任意序列的傅立叶分析，其谱是连续函数。然而，离散傅立叶变换将有限长度序列作为周期序列的一个周期。对于有限长度序列的傅立叶分析，离散傅立叶变换的特征在于在时域和频域都是有限长度序列。离散傅立叶变换提供了一种用计算机分析信号和系统的方法，特别是快速傅立叶变换，它是离散傅立叶变换的一种快速算法，已被广泛应用于科学技术的许多领域，促进了数字信号处理技术的快速发展。例如，一个4点序列的离散傅里叶变换解是用离散傅里叶变换的矩阵表达式得到的：x(n)和X(k)的波形图如下：非周期函数的离散傅里叶变换的物理和逻辑过程，(a)原始函数，(b)截断后的保留部分，(c)周期延拓，(d)离散采样，(e)离散傅里叶变换后的离散频谱，离散傅里叶变换的混叠问题，采样间隔t，采样频率。如果采样频率太小，高频部分可能与低频部分重叠，形成“混频”。fs=f，采样频率等于信号频率；恢复信号的频率为0，波形严重失真。采样频率fs=1/9f。恢复信号的频率为1/9f，波形失真。香农采样定理，如果信号中的最高频率是fmax，为了不产生混频，信号的频率分量可以被正确恢复，并且采样频率fs必须保证大于fmax的两倍，即如果采样频率fs增加，采样时间将会减少，导致频率分辨率f的粗化。信号可以通过低通滤波器使滤波后的信号中的最高频率为fmax，然后可以根据采样定理确定采样频率fs。通常fs是fmax的34倍，fN=fs/2称为奈奎斯特频率，或称混叠频率，以及离散傅里叶变换的泄漏。在实际应用中，观测到的信号通常被限制在一定的时间间隔内，也就是说，信号在时域中被截断，或者加上一个时间窗，也就是说，时间窗函数被用来乘以信号，也就是说，从卷积定理来看，时域中的乘法和频域中的卷积有时会导致能量色散，这被称为频谱泄漏。余弦信号被矩形窗口截断以形成泄漏。对于连续的周期函数，在符合采样定理的条件下，保证窗函数b(t)的周期等于截断函数的周期t的整数倍，从而使原始波形经过逆变换后能够准确恢复而不泄漏。对于随机振动信号(非周期函数)，泄漏控制方法是利用特定的窗函数来达到旁瓣控制的效果。常用窗口函数，(1)矩形窗口w (t)=1 (2) hanning窗口w (t)=1-cos (2t/t)，(3)Kaiser-Bessel w(t)=1-2.4 cos(2t/t)0.244 cos(4t/t)-0.00305 cos(6t/t)(4)平顶w(t)=1-1.93 cos(2t/t)1.29 cos(4t/t)-0.388 cos(t) 当窗长等于周期信号的整个周期时的汉宁窗：纯随机平顶窗：周期或准周期信号力窗或指数衰减窗：当用锤击法、快速傅里叶变换测量频率响应函数时的力信号和脉冲响应信号，当直接用傅里叶变换进行频谱分析时，有一个突出的矛盾，即当序列长度n大时，计算量大，计算时间长， 数据占用大量内存，用离散傅立叶变换很难进行实时处理，其应用受到很大限制。1965年，库利和图基提出了一种快速的离散傅立叶变换算法快速傅立叶变换。 快速傅里叶变换算法大大减少了计算量和计算时间，尤其是当序列长度n较大时。快速傅里叶变换不是一种新的变换形式，它只是快速傅里叶变换的一种快速算法。根据序列分解和选择方法的不同，产生了不同的快速傅里叶变换算法。快速傅里叶变换在离散傅里叶逆变换、线性卷积和线性相关中也有重要的应用。有限长序列x(n)的离散傅立叶变换是：离散傅立叶变换的定义被扩展成方程并被写入矩阵形式，并且通过向量表示的复数表示的X(k)值的计算需要N个复数乘法和(N-1)个复数加法，因此N个X(k)需要N2复数乘法和N(N-1)个复数加法。每个复数乘法包括4个实数乘法和2个实数加法，并且每个复数加法包括2个实数加法，因此计算N点的DFT需要4N2个实数乘法和(2N2个2N(N-1)个实数加法，例如，当N=2048时，计算量为419万次。快速傅立叶变换原理，快速傅立叶变换算法主要使用两个属性：分解过程遵循两个规则：对时间执行奇偶分解并按时间提取的快速傅里叶变换算法；对频率进行前向-后向分解并按频率提取的快速傅里叶变换算法；对于按时间提取的快速傅立叶变换算法，设置N=2M，m为正整数；如果N=23=8，也就是说，根据规则，离散时间信号被分成奇数和偶数组，一组序列号是偶数，另一组序列号是奇数，也就是说，它们分别被表示为，根据密度泛函的定义，由于上述公式中的G(k)和H(k)是N/2点的密度泛函，注意，G(k)和H(k)只有N/2点，而X(k)需要N点。如果所有的X(k)都由G(k)和H(k)表示，则应该使用G(k)和H(k)的两个重复周期。有：G(k)和H(k)的周期性和WN的对称性可以得到：因此，X(k)的所有关系可以由G(k)和H(k)来确定：以N=8为例，有：根据上述结论，可以得出如下的信号流程图：每个N/2点密度泛函的计算可以进一步分解为两个N/4点密度泛函的计算： 将得到