首页 » 学习 » 快速傅里叶变换算法

快速傅里叶变换算法

  1. 欧拉公式
  2. 连续时间周期信号的傅里叶级数表示
  3. 连续时间傅里叶变换
  4. 离散时间周期信号的傅里叶级数表示与离散时间傅里叶变换
  5. 离散时间信号的频域采样和重建
  6. 用分而治之的方法计算DFT
  7. 基2 FFT算法
  8. 基4 FFT算法
  9. 参考资料

欧拉公式

欧拉公式提出 eix = cosx + sinx 其中e是自然对数的底数,i是虚数单位。

欧拉公式将三角函数与复指数函数联系起来。使用傅里叶变换可以将任意函数展开为三角级数。但三角函数不方便运算,使用欧拉公式变换成复指数函数后虽然不再形象却更加方便数学运算。换句话说,欧拉公式使我们可以使用方便进行数学运算的复指数函数来处理三角函数。

可以使用求导法证明欧拉公式

连续时间周期信号的傅里叶级数表示

将连续时间周期信号用不同频率的信号表示

其中w0为基频频率。将一个周期信号用上式形式表示,则称为傅里叶级数表示。

下面要确定系数ak

并不是所有周期信号都可以用傅里叶级数表示。当然所有所有周期信号都可以用上面推导得到的式子计算an,但在某些情况下,式子中积分的结果可能不收敛。这里给出周期信号x(t)可以用傅里叶级数表示的条件(狄里赫利条件)不做证明。

  1. 在任意周期内,x(t)必须绝对可积。
  2. 任意有限区间内,x(t)具有有限个起伏变化,即最大值和最小值数目有限。
  3. 在x(t)的任意有限区间内,只有有限个不连续点,而且这些不连续点上的函数值是有限值。

连续时间傅里叶变换

对于非周期信号,可以把其当成一个周期信号在周期任意大时的极限看待,这样可以用傅里叶级数表示。

离散时间周期信号的傅里叶级数表示与离散时间傅里叶变换

离散与连续时间周期信号的一个重要区别是其傅里叶级数是有限项级数,而连续时间周期信号的是一个无穷级数。这导致了离散时不存在上面提到的存在性问题。

这里直接给出有关结果,其证明过程与连续时间情况下类似。

离散时间信号的频域采样和重建

用分而治之的方法计算DFT

快速傅里叶变换算法的核心思路是:将N点DFT分解为更短的DFT来计算。

将N分解为两个整数的乘积(N=L·M),将数据依次填入L行M列的表格中,记坐标为(l,m),这样每个数据就得到了一个新的序号:mL+l。同样将结果也分别填入表格中也会得到一个新的序号,记为Mp+q。

基2 FFT算法

上节中将N分解为两个整数,当N为多个质数的乘积时,这种方法会更有效率。特别是在这些数相等,即 N = rv ,这时将长度r称为FFT算法的基数。广泛使用的是基2和基4FFT算法。

基4 FFT算法

当数据长度N是4的幂时,虽然也可以以2为基数进行计算,但是用4为基数算法效率将更高。

参考资料

信号与系统 (第二版) Alan V. Oppenheim 等著 刘树棠 译 电子工业出版社

数字信号处理——原理、算法与应用 John G. Proakis 等著 方艳梅等译 电子工业出版社

发表评论

电子邮件地址不会被公开。 必填项已用*标注