3离散傅立叶变换与快速傅立叶变换II.ppt

徐科军 主编《信号分析与处理》配套课件 合肥工业大学 陈强 制作 数字信号处理 第2章 离散傅立叶变换和 快速傅立叶变换（II） 内容提要 快速傅立叶变换 FFT的基本思想 时间抽取基－2FFT算法 频率抽取基－2FFT算法 快速傅立叶逆变换 快速傅立叶变换的应用 FFT的基本思想 快速傅里叶变换（Fast Fourier Transform，FFT）不是一种新的变换，而是DFT的快速算法，使DFT的运算简化，得以实用 DFT的运算量 设x(n)是复序列，则N点DFT运算需要N2此复数乘法和N(N-1)次复数加法 当N较大时，运算量很大，限制了DFT的使用 快速傅里叶变换减少运算量的原因 不断把长序列的离散傅里叶变换分解为短序列的离散傅里叶变换 利用系数WN的对称性和周期性 时间抽取基-2FFT算法（DIT） 频率抽取基-2FFT算法（DIF） DIT与DIF算法 差别 顺序：DIT时域输入倒序，频域输出正序；DIF时域输入正序，频域输出倒序 蝶形运算：DIT中复数乘法出现在加（减）法运算之前，DIF中复数乘法出现在加（减）法运算之后 相同 二者的运算量相等 二者均为同址运算 快速傅里叶逆变换 只要将序列X(k)取共轭，然后用FFT程序计算DFT，将结果取共轭并乘以1/N，即可计算x(n) 快速傅里叶变换的应用 快速卷积 由卷积公式，两个N点序列的卷积需N2次乘法 如果用循环卷积，就可以利用FFT技术大幅减少运算量 快速相关 与卷积运算类似，可以用FFT加速相关运算 * * 设序列长度 将x(n)分为奇、偶序列 8点DFT的奇偶分解 X(k)被分解为A(k)和B(k) A(k)和B(k)可以继续被分解 令 8点DFT的进一步分解 2点DFT无需乘法 每一次奇偶分解，称为一“级”运算 N=2M点DFT可分成M级 蝶形单元 每个蝶形单元只需一次复数乘、两次复数加 每个蝶形运算不涉及其他单元，“同址运算” 输出按自然顺序，输入按“码位倒置”规律 输出0(000),1(001),2(010),3(011),4(100),5(101),6(110),7(111) 输入0(000),4(100),2(010),6(110),1(001),5(101),3(011),7(111) 复数乘法 复数加法 直接计算 复数乘法 复数加法 VS. 时间抽取基-2FFT算法 输入序列反复按时间奇偶规律抽取，故名 计算量 每一级有N/2个蝶形运算 每个蝶形单元只需一次复数乘、两次复数加 长序列DFT的分解方法不止一种，除了按奇偶抽取外，还可以按前后分解 分解可以继续进行，直到分解为若干2点DFT 两个N/2点的DFT 输入x(n)为原次序，输出X(k)为奇偶抽取次序 序列 相乘 次乘法 N次乘法 序列 相乘 次乘法 N次乘法 共轭 * * * * *