第六章 快速傅里叶变换.ppt

Digital Signal Processing 第六章 快速傅里叶变换 一个算法能否被广泛应用，不但取决于算法本身的质量，还取决于是否存在高效或快速实现方法。DFT变换有许多优良特性 6．1DFT变换分析 DFT变换的计算复杂性 一点 ，需要4N次实数乘法，2（2N+1）次实数加法 DFT运算（共N点）需要4N2次实数乘法，(4N2-2N)次实数加法 DFT变换的对称性和周期性 FFT算法的基本思想 FFT算法 Winograd傅里叶变换算法（WFTA） 数论变换（NNT）算法 DFT变换的快速算法 充分利用变换核的周期性和对称性 长序列DFT变换分解为多个短序列DFT变换提高计算效率 6．2基2时间抽取FFT算法 序列的一次奇偶抽取 序列的一次奇偶抽取计算量 N/2 点 DFT N/2 点 DFT 序列的多级奇偶抽取(N=8) 基2时间抽取FFT算法的计算量 基2时间抽取FFT算法的特性 码位倒置特性 同址运算 每一级每只蝶的输出仅与本蝶的输入及本蝶所处的位置相关 输入输出序列共亨存储单元 每级N/2只蝶可并行运算 蝶形运算 M级，第m级蝶可分成 组，每组 只蝶 第m级、第i组、第j只蝶 6．3其它Cooley-Turkey类FFT算法 基2频率抽取（DIF）FFT算法 基4时间或频率抽取FFT算法 分裂基FFT算法 6．4实数序列的FFT算法 两个N点实数序列的FFT算法 单个2N点实数序列的FFT算法 6．5 IFFT算法 FFT算法修正 两者主要区别是变换核不同，使用FFT算法时蝶形公式可能需要修正 共轭变换法 系数N分解为 ，在每一级（共M级）蝶形运算乘1/2，防止定点运算过程可能出现溢出，提高数值计算的稳定性 6．6快速卷积和快速相关 快速卷积算法 线性卷积 线性卷积的乘法次数： 快速卷积 快速卷积的乘法次数： 快速卷积关于线性卷积乘法改善比 ： 快速卷积关于线性卷积乘法改善比统计 有限长序列和无限长序列的卷积 重叠相加法 重叠相加法 第i段线性卷积yi(n)的取值范围为： 第i+1段线性卷积yi+1(n)的取值范围为： yi(n)的后M点和yi+1(n)的前M点重叠 重叠保留法 0 补M个零 M 丢弃M个 保留 M M 丢弃M个 保留 丢弃M个 保留 快速相关算法 6．7线性调频z变换算法 DFT 和z变换的关系 在单位圆 区间以 间隔对 均匀采样 DFT： DFT 变换在一些应用中局限性 整个频率范围均匀采样，不适合分析窄频带分析 当x(z)的零极点离单位圆远时，谱峰不明显 线性调频z变换（CZT）算法 线性调频z变换（CZT）算法 注意补零方法 6．8其它离散正交变换 DCT变换 DHT变换 WHT变换 WHT变换主要在移动通信的CDMA（Carrier Division Multiple Access）技术中得到应用 DWT变换和KLT变换 KLT变换是一种最优变换。它根据信号的概率分布，使变换后的能量最大限度地集中在少数几个变换系数中，KLT变换可最大程度地对信号进行压缩。但是，KLT变换没有快速算法，使其应用受到了很大的限止。 当、信号属于高斯—马尔可夫过程时，DCT变换与KLT变换很接近，这也是DCT变换为何适合于视频信号压缩的理论依据 Digital Signal Processing