当前位置:   article > 正文

第四章快速傅里叶变换FFT_fft算法

fft算法

一、基2FFT算法

1.直接计算DFT的特点

  • 对于N点DFT的乘法和加法运算次数均为N^2(运算量较大)
  • 减少运算量的基本途径:将N点DFT分解成多个较短的DFT
  • 旋转因子具有

        周期性:W_{N}^{m}=W^{m+lN}_{N}

        对称性:W_{N}^{-m}=W_{N}^{N-m}[W^{N-m}_{N}]^{*}=W_{N}^{m}又或者W_{N}^{m+N/2}=-W_{N}^{m}

2.时域抽取法基2FFT基本原理

  • 分类:基2FFT分为时域抽取法FFT(DIT-FFT)和频域抽取法FFT(DIF-FFT)
  • 设x(n)长度为N且满足N=2^M(M为自然数),按n的奇偶数把x(n)分解为两个N/2点的子序列(时域不断奇偶分组)

         (注意X1(k)和X2(k)分别为x1(r)和x2(r)的N/2点DFT,即以N/2为周期)

  • 蝶形运算符

  •  若N=8则8点DFT一次时域抽取分解运算流程图(输入倒序输出正序࿰
本文内容由网友自发贡献,转载请注明出处:https://www.wpsshop.cn/w/羊村懒王/article/detail/704757
推荐阅读
相关标签
  

闽ICP备14008679号