信号分析与处理 教学课件 作者 杨西侠 柯晶 3 4FFT.ppt

3.6 快速傅里叶变换（FFT） 3.7 IDFT的快速算法 3.7 离散傅立叶变换的应用 无法满足计算机进行数字处理的要求。若要用FFT进行分析和处理，必须在时域进行有限化和离散化处理 1. 时域的有限化 对连续信号进行抽样。若抽样周期为T，则t ? nT，dt ? T，积分变求和，处理后的频谱密度X( j? )近似表示为 2. 时域的有限化 对连续信号沿时间轴进行截断，限定为[0 T1]，包含有N个样点， T1 = NT = T ? DFT[ x(n) ] = T ? X(k) 把对连续信号xa(t)的谱分析用xa(nT)的谱分析来逼近，从而采用FFT。 3. 为了数值计算，在频域上也要离散化即在频域的一个周期（fs）中也分成N段，即取N个样点，每个样点间的间隔为?1 ，则有 ? = k?1 （k = 0, 1, 2 ,…, N ?1） 则 对连续非周期信号的数字谱分析，实质是信号在有限化的基础上，对波形与频谱进行抽样，采样点越密，分析的结果和原信号越接近，近似的程度越好。但总会存在误差。 4. 误差分析 混叠误差(抽样) 截断误差（频谱泄漏） 栅栏效应 栅栏效应 因为DFT计算频谱只限制在离散点上的频谱，只能观察到有限（N）个频谱值，而不是连续频率函数，这就像通过一个“栅栏”观看一个景物一样，只能在离散点的地方看到真实景物，把这种现象称为“栅栏效应”。 减小栅栏效应的一个方法就是使频域抽样更密，即增加频域抽样点数N，使样点间距更近，谱线更密，谱线变密后原来看不到的谱分量就有可能看到了。 * 3.6.1 DFT运算的特点 1. DFT计算工作量 将x(n)与WNnK两两相乘再取和即可得到X(k)。每计算一个X(k)值需要进行N次复数相乘，和N?1次复数相加。对于N个X(k)点，应重复N次上述运算。因此，要完成全部DFT运算共需 N2次复数乘法和N ( N ?1)次复数加法。 例如N = 4，需 N2 = 16次乘法和N ( N ?1) = 12次加法。例如N = 10，需N2 = 100次乘法和N ( N ?1) = 99次加法。而N = 1024，就需要1048576次乘法运算。 随着N值加大，运算工作量将迅速增长，按照这种规律，如果在N较大的情况下，要求对于信号进行实时处理，所需的运算速度就难以实现。 为了改进算法，减少运算工作量。考虑系数WnK 的周期性与对称性，合理安排重复出现的相乘运算，将使计算工作量显著减少。 2. 改进思路 1）W nk的周期性 WNnk = WN (n +lN)(k+mN) 例 N = 4 W46 = W42 W49 = W41 等等 2）W nk的对称性 WN (nk+N/2) = ? WN nk WNN/2 = ? 1 例 N = 4 W43 = ? W41 W42 = ? W40 等等 ------周期性 ----对称性 W矩阵与x(n)相乘过程中，存在着不必要的重复计算。 3.6.2 基2按时间抽取的FFT算法（时析型） 1. 原理 把N点DFT运算分解为两组N/2点的DFT运算，然后取和。对序列x(n)取N点DFT，假定N是2的整数次方 N = 2M 把x(n)取N点DFT运算按n为偶数和奇数分解为两部分 以符号2r表示偶数n，以符号2r + 1 示奇数n， r = 0, 1, …，N/2 ? 1 式中WN2 转换为WN/2，且记 g(r) = x(2r) ， h(r) = x(2r+1)。 一个N点的DFT已被分解为两个N/2点的DFT。注意G(k)和H(k)只有N/2个点，r = 0, 1, …, N/2 ? 1，而X(k)需要N个点，k = 0, 1, …, N ? 1，如果以G(k)，H(k)表达全部X(k)，应利用G(k) 与H(k) 的两个重复周期。 G(k + N/2) = G(k) H(k + N/2) = H(k) WN(k+N/2) = WNN/2 ?WNk = ? WNk 全部关系式