离散时间信号处理：第5章 离散傅立叶变换与快速算法2(FFT)

1、15.2DFT的快速计算(FFT)一、DFT存在的问题及改进的途径二、戈泽尔算法三、时域抽取基-2算法（库利-图基算法）四、频域抽取基-2算法（桑德-图基算法）五、线性调频Z变换2N点有限长序列，其DFT变换对为： 可以看出，变换与反变换的差别仅在于 的指数符号和常数乘因子1/N。实际上： 因而我们只讨论DFT正变换的运算量，反变换的运算量是完全相同的。 5.2.1DFT存在的问题及改进途径3一般来说 和 都是复数，每一个 值的计算，需要N次复数乘法以及（N-1）次复数加法，完成整个DFT运算总需要 次复数乘法和N（N-1）次复数加法。DFT直接计算的运算量4复数运算实际上是由实数运算来完成的

2、，如：一次复数乘法需用：四次实数乘法二次实数加法；一次复数加法则需：二次实数加法。整个DFT运算总共需要：4N2次实数乘法 次实数加法。5上述统计与实际的运算次数有少许出入，某些因子不能按照一般的复数来计算运算量,如:当N很大时，这种特例很小。 直接计算DFT运算量是很可观的:N=8时，DFT需64次复乘，N=1024时，DFT所需复乘为1 048 576次，对实时性很强的信号处理来说，对硬件的计算速度要求是太高了。为了实用的需要，需要改进DFT的计算方法，减少运算次数。6如何才能减少运算量？仔细观察DFT的运算就可看出，其变换系数 的具有如下特性：（1） 的对称性（2） 的周期性 = =（3

3、） 的可约性 由此可得:变换基底的特性7（1）利用 的对称性，合并DFT运算中某些项，并且可以计算反变换；（2）由于DFT的运算量是与 成正比，利用 周期性和可约性将长序的DFT分解为短序列的DFT。FFT基本可以分成两大类按时间抽取(Decimation-in-time,DIT）按频率抽取(Decimation-in-frequency,DIF）。FFT的基本出发点85.2.1 戈泽尔算法戈泽尔算法是一个利用复变换基W的周期性减少运算量的典型例子可以用于单离散频点或少数任意离散频点场合（如DTMF辨识）的有效计算9变形10推论：如果构造冲击响应h(n)为 的系统，则该系统对有限长输入在 时刻

4、的响应即为 。 下图给出了该系统的计算流图：11由上图可以看出计算一个X(k)需要N次复乘和N次复加，即4N次实乘和4N次实加。比直接计算DFT的运算量稍大一些，但是却避免了计算或存储复系数 。另外，立足于上面用卷积实现DFT的方法，我们是有可能通过某种变形将上面的运算量减小一半。 12注意到系统函数：13利用迭代实现了复因子的计算如果输入序列是复数，由于系数是实数并且-1不必作乘法运算，所以计算一个X(K)只需要2N次实数乘法和4N次实数加法。戈泽尔算法还有另外一个优点是只需要将前馈环节中的复因子取共轭就可以计算X(N-K)，可以将运算量再次减半。戈泽尔算法虽然比直接运算有效的多，但是无论如

5、何变形，其运算量将仍然正比于N2。戈泽尔算法特点14一、算法原理 假设序列点数为 ,L为整数。如果不满足，可以人为加上若干零值点，使之达到这一要求。这种N为2的整数幂的FFT也称基-2 FFT。 将 的序列按n的奇偶分成两组： r=0,1,N/2-15.2.2 DIT的2MFFT(库利-图基算法)1516利用 的可约性：式中 与 均为N/2点DFT：一分为二17但 以及 ， 都是N/2点的序列，即而 却有N点，因而计算全部的 ，必须应用DFT隐含的周期性扩展：定义的扩展18同时考虑到 的以下性质 这样就可将 表达为前后两部分： 1920 上面的运算可以抽象为下面的蝶形信号流图单元： 可以看出，

6、每个蝶形运算需要一次复数乘法 及两次复数加（减）法。21N/2点DFT复乘: 复加:蝶形运算 复乘: 复加:总运算量 复乘: 复加:直接N点DFT复乘: N2 复加:N(N-1)运算量-减少一半22既然如此，由于 ，因此N/2仍是偶数，可以进一步按时间的奇偶性分解，并且一直进行下去。由于这种方法每一步都是按输入序列时间的奇、偶性分解为两个更短的子序列，所以称为“按时间抽选法”（DIT）。分解过程如下：231、原位运算，2、倒位序，3、叠型间距24由按时间抽选法FFT的流图可见，当 时，共有：L级蝶形，每级都由N/2个蝶形运算组成每个蝶形有一次复乘、二次复加，因而每级运算都需N/2次复乘和N次复

7、加L级FFT运算总共需要： 复乘数： (DFT: ) 复加数： (DFT: )二、运算量25由于计算机上乘法运算所需时间比加法运算所需时间多得多，所以乘法是主要的运算量。直接计算DFT与FFT算法计算量之比为:2627三、DIT算法的特点1、原位运算（同址运算）每级（每列）都由N/2个蝶形运算构成每一个蝶形结构完成下述基本迭代运算： m表示第m级迭代， k、j为数据所在行28按原位计算时，FFT的输出 是按正常顺序排列在存储单元中: X（0），X（1），X（7），但是输入 却不是按自然顺序存储的:看起来好像是“混乱无序”，实际是有规律的，称之为倒位序。造成倒位序的原因是输入 按标号n的奇、偶性

8、的不断分组造成。倒位序的实现2、倒位序规律293、蝶形运算两结点的“距离”由8点FFT的信号流图可以看出，其输入是倒位序的，输出是自然顺序。第一级每个蝶形的两节点间“距离”为1，第二级每个蝶形的两节点“距离”为2，第三级每个蝶形的两节点“距离”为4，由此类推得，对N2L ，当输入为倒位序，输出为正常顺序时，其第m级运算，每个蝶形的两节点“距离”为 。30四、DIT算法的其他形式流图对于任何流图，只要保持各节点所连的各支路及其传输系数不变，则不论节点位置怎么排列所得流图总是等效所得最后结果都是DFT的正确结果，只是数据的提取和存放的次序不同而已。3132335.2.3 DIF的2M FFT(桑德

9、-图基算法)频率抽选（DIF）的FFT算法，是把频域序列（也是N点）按K的奇偶性分解为越来越短的序列。 一、算法原理假设序列点数为 ，L为整数。在将 按k的奇偶分组之前，先把输入按n的顺序分成前后两半3435由于 ，故 ，可得： k=0,1,N-1当k为偶数时， ； k为奇数时， 。因此，按 k的奇偶可将 分为两部分。 36令 则：37令 则：38DIF运算关系的基本蝶形39N=8点DIF FFT结构40二、DIT与DIF的异同形式上的区别是：DIF输入是自然顺序，输出是倒位序的，与DIT正好相反。但这不是实质性的区别，因为DIF与DIT都可将输入或输出按照要求进行重排。实质性的区别是：DIF

10、的基本蝶形与DIT的基本蝶形不同。414243作业：9.69.7 9.149.179.269.27五、chirp Z变换对非单位圆上的抽样感兴趣语音信号处理中往往需要知道极点所在处的复频率，如果极点位置离单位圆较远，只利用单位圆上的频谱，就很难知道极点所在处的复频率。z变换采用螺线抽样就适应于这些需要，称为线性调频z变换(CZT)4445已知 是有限长序列，其z变换为：为适应z可以沿Z平面更一般的路径取值，沿z平面上的一段螺线作等分角的抽样，z的这些抽样点zk为:一、算法的基本原理46 M为所要分析的复频谱的点数，不一定等于N，A和W都是任意复数:47当 各zk就均匀等间隔地分布在单位圆上，这

11、时就是求序列的DFT。48CZT的快速算法直接计算这一公式，与直接计算DFT相似，总共算出M个抽样点，需要NM次复数乘法与（N-1）M次复数加法，当N，M较大时，运算量将很大。49采用布鲁斯坦（Bluestein）提出的等式，可以将以上运算转换为卷积和形式，进而采用FFT算法，提高运算速度。布鲁斯坦所提出的等式为： 由此可得：5051CZT变换可以通过求g(n)与h(n)的线性卷积，然后乘上1/h(n)而得到，即：h(n)为角频率随时间线性增长的复指数序列，称为线性调频信号（Chirp signal），因此，称为线调频z变换。 52线性系统h(n)是非因果的。当n取值为0到N-1，k取值为0，1，M-1时，则 h(n)的定义区间为 ，可以看作有限长序列二、Chirp-Z变换的快速计算53由于输入信号g(n)也是长度为N有限长序列，所以g(n)*h(n)的点数为2N+M-2因而用圆周卷积代替线性卷积不产生混叠失真的条件是圆周卷积的点数（周期）应大于或等于2N+M-2但是我们只需要前M个值 ，对其他值是否有混叠失真并不感兴趣，这样有可能将圆周卷积的点数缩减到最小为N+M-1。54g(n)h(n)5556CZT快速运算的实现步骤：（1）选择一个最小的整数L，使其满足LN+M-1，同时以便采用