数字信号处理-2.pptVIP

2.5.3频率抽取基-2 FFT算法 最终可以分解为： 2-6离散傅立叶反变换（IFFT）的运算方法 FFT算法同样可以用于IDFT运算，简称IFFT，即快速傅立叶反变换。IDFT的定义为： 而DFT的定义为: 比较上面二式，只要把FFT运算中的每一个系数 改为 并在最后再乘以常数1/N，那么所有上节所讨论的FFT算法就可以用来运算IDFT。如图所示 方法一、利用蝶形运算和定义 2-6离散傅立叶反变换（IFFT）的运算方法 FFT的定义为： IFFT的定义为： 2-6离散傅立叶反变换（IFFT）的运算方法 2-6离散傅立叶反变换（IFFT）的运算方法 可以直接利用FFT程序来完成IDFT的运算 即先将X(k)取共轭，然后可直接使用FFT子程序，最后再对运算结果取一次共轭变换，并乘以常数1/N即得x(n)值。 方法二 对X（K）取共轭后进行FFT，然后再除N 2-6离散傅立叶反变换（IFFT）的运算方法 直接利用FFT的另外一种方法为： 令X（K）的FFT为x1(n)，如下 直接对X(k)进行FFT运算，然后将结果顺序倒排(第0个结果不动)，再乘以常数1/N即可完成IDFT的计算。 方法三 直接对X（K）进行FFT，然后再倒序并除N 2-7任意基数的FFT算法 如果序列的长度为 或通过补零变为 ，这时可以用FFT计算。 但是如果长度N不能人为确定，且N既不满足2的整数幂，又因运算量限制而不能增加过多的零点（意味着可以增加不多的零点），却要求准确地计算DFT值时，便可采用任意基数的FFT算法来计算。 如果N是合数，且可以分解为两个整数p与q的乘积，即有N=pq，则可将N点DFT分解为p个q点DFT或q个p点的DFT，以减少运算量。 问题的提出 解决的思路 2-7任意基数的FFT算法 即 可得 2-7任意基数的FFT算法 1 2 3 P 2-3 DFT的几个问题：5. 和Z变换的关系 因为一个有限长序列x(n)，满足收敛条件时，则有 Z变换是在Z平面上对x(n)的一些特性进行分析的的工具，当取Z平面的单位圆时，成为对x(n)的频率响应的分析，为了便于使用计算机来处理，ω就需要离散化，最简单的是在ω=0到2π的范围内N等分，得到x(n)的DFT形式，所以 DFT和Z变换的关系为： 所以，DFT相当于在单位圆上对Z变换进行等分采样，见下页图 2-3 DFT的几个问题：5. 和Z变换的关系 需要说明的是，这里的采样是“理论采样”，不是利用器件采样。 2-4 频率采样理论 在上一节中,我们看到采用DFT后，实现了频域的采样.那么对于任意一个频率特性,是否均能用频域采样的办法来逼近呢？ 一个任意序列x(n)，满足收敛条件，它的Z变换为 对X(Z)在单位圆上N个等分点上进行采样,有 进行IDFT，得长度为N点的有限长序列 ，即 2-4 频率采样理论 当m-n=rN，即m=n+rN时，有 根据 正交性，即 2-4 频率采样理论 这就是频域采样定理。 对于有限长序列x(n)，在满足频域采样定理的前提下，N点频域采样X(k)就足以不失真地代表序列的特性。因此，由N个采样值X(k)能够完全地表达整个X(Z)函数及频率特性 。即由N点X(k)可以内插恢复出X(Z)或 。 可见， 是x(n)以N为周期进行周期延拓后所取主值序列。 如果x(n)是有限长序列，序列长度为M，频率采样不失真条件为N≥M；当N＜M时，就会产生混叠失真。 2-5快速傅立叶变换（FFT） 快速傅立叶变换（简称FFT）是快速计算DFT的有效算法。离散傅立叶变换实现了频域离散化，在数字信号处理中起着极其重要的作用，分析信号的频谱、计算滤波器频率响应，以及实现信号通过线性系统的卷积运算，都离不开FFT，在数字信号处理中应用得相当广泛。 早在1965年库利和图基首次发现了计算DFT的一种快速算法，人们开始认识到DFT运算的一些内在规律，很快地发展和完善了一套高效的运算方法，FFT方法不仅对用计算机处理信号带来好处,而且对信号的实时处理影响重大,使DFT的运算在实际中得到了广泛的应用。 2.5.1 DFT运算特点 一个长度为N点的有限长序列x(n)的离散傅立叶变换为: 按定义直接计算，则： 1个点－－N次复数相乘运算，(N-1)次复数相加运算 N个点－－N×N次复数相乘运算，N×(N-1)次复数相加