ZT与LT的关系.PPT

为节点，m：表示第m列叠代。p,q：为数据所在行数，对应信号流图下图所示： 第二节 按时间抽取FFT算法 是输入数据 注： 第二节 按时间抽取FFT算法 （1）蝶式运算的节点距离 (p,q间的距离) 以N=8为例 m 1 2 3 q-p 1 2 4 推广:基-2 DIF FFT中,第m级蝶式运算节点间距离为 蝶式运算可写成: （2） 的确定 每一级的旋转因子都不相同，但排列很有规律，下表所示。 第二节 按时间抽取FFT算法 2. 原址运算 第二节 按时间抽取FFT算法 多级蝶式运算结构会产生大量中间结果.如果运算式要保存这些中间结果,则需要耗费大量资源(存贮器)观察FFT信号流图,可以发现任何两个节点(p与q)经过蝶式运算后,其结果即为下一列p,q两节点的变量. 而每一级蝶式运算的输出,在该级运算结束之后无需 保存.因此,任何一个蝶行运算的两个输出结果仍然可 以存放两个输入值所在的存储单元中.这样,整个运算 只需要N个寄存器,他们保存输入数据,并不断对每一 级运算结果刷新,直到最后输出。其优点在于节省存储资源. 第二节 按时间抽取FFT算法 3. 倒位序 观察同址运算结构,可以发现FFT输出端X(k)正好按0~7自然顺序排列的，而输出序列x(n)不是按0~7自然顺序排列。x(n)排列表面上混乱无序，而隐含着有规律的排列，即”倒位序”存贮,以N=8点FFT结构来说明。 存储器号 数据 结论: 第二节 按时间抽取FFT算法 倒位序排列是由于不断将DFT运算分解为较小点数DFT计算造成的。序列x(n)首先分成偶数标号和奇数标号两个子序列：偶数序列出现在流图上半部,奇数序列出现在流图下半部。从形式上说,这样的划分可通过分析标号n的二进制表示 的最低位 来实现。标号为偶数，则 =0，标号为奇数，则 =1。这样 =0的标号出现在流图上半部 从中我们可以发现: 若 , 则: 第二节 按时间抽取FFT算法 =1的标号出现在下半部。下一次奇偶序列的分解又分别根据标号二进制表示的倒数第二位 开始,根据 分别将第一次分解生成的两个子序列再一次按奇偶性分开。持续该过程,直得到N个长度为1的子序列。最后的排列顺序呈”倒位序” 第二节 按时间抽取FFT算法 所以要实现FFT算法，首先必须把按自然顺序存放的数据变换成按倒序存放。这一过程称为整序，N=8时的整序过程下图所示。 第二节 按时间抽取FFT算法 * 讲座: 快速离散傅立叶变换 本讲的教学内容 改进DFT计算的方法 按时间抽取的FFT算法（DIT FFT） 按频率抽取的FFT算法（DIF FFT） 第十章 快速离散傅立叶变换 （1） FFT:Fast Fourier Transform （2）傅立叶级数和傅立叶变换理论在19世纪就已经提出,时域离散傅立叶变换理论也在20世纪初发展完善.但由于其手工计算的复杂性,在工程实践中并没有得到广泛应用.相反,在应用中使用广泛的是其它一些手工计算相对简单的数学分析手段,如沃尔什变换.直到1965年, 库利-图基提出了针对N时复合数情况的快速离散傅立叶变换算法,与传统算法相比降低了1～２个数量级,由此引发了研究快速算法的热潮.这些算法统称为FFT. FFT算法的广泛应用，不仅奠定了离散傅立叶变换在数字信号处理中的经典地位,也极大推动了数字信号处理应用与发展. 第一节 改进DFT计算的方法 衡量算法的复杂性: 乘.加法运算次数,不考虑控制调度等操作;只考虑DFT的正变换,因为: K=0,1, …,N-1 DFT正变换 DFT反变换 反变换相对正变换:输入取共扼;输出取共轭并加权. 直接计算DFT的运算量 n=0,1, …,N-1 k=0,…,N-1 复数运算 对每一个k值: 复乘: N 复加: N-1 第一节 改进DFT计算的方法 对所有k: 复乘: 复加: N(N-1) 即复数运算量与 近似成正比 (不考虑 情况) 实数运算 k=0,…,N-1 第一节 改进DFT计算的方法 对每一个固定k : 实乘: 4N 实加: 对所有k : 实乘: 4N2 实加: 2N(2N-1)= 4N2