快速傅立叶变换（FFT）的计算机实现
4星 · 超过85%的资源 需积分: 31 94 浏览量
2011-03-05
23:05:46
上传
评论 1
收藏 288KB DOC 举报 
快速傅立叶变换（FFT）的计算机实现
摘要:本文采用时间抽取算法,运用蝶形运算方法把长序列的 DFT 逐次分解为较
短序列的 DFT,经过多次分解最终计算出长度为 N 的序列的傅里叶变换,从而实
现快速傅立叶变换.另外还较为详细地讨论了 FFT 变换的实现条件.
关键字:FFT 算法 时间抽取算法 蝶形运算法 程序实现
正文:
一.问题背景
在数值电路的传输中，为了避免信号干扰，需要把一个连续信号 x(t)先通过
取样离散化为一列数值脉冲信号 x(0), x(1), …… ,然后再通过编码送到传输电
路中。如果取样间隔很小，而连续信号的时间段又很长，则所得到的数值脉冲
序列将非常庞大。因此，传输这个编码信号就需要长时间的占用传输电路，相
应地也需要付出昂贵的电路费用。
那么能否经过适当处理是使上述的数值脉冲序列变短，而同时又不会丧失
有用的信息？的经过研究，人们发现，如果对上述数值脉冲序列作如下的变换
处理：
(1)
则所得到的新序
列 X(0), X(1) , ……将非常有序，其值比较大的点往往集中在某一很狭窄的序
列段内，这将非常有利于编码和存储，从而达到压缩信息的目的。
公式（1）就是所谓的离散傅立叶变换，简称 DFT。现在我们来分析一下
计算 DFT 所需要的工作量。如果我们不考虑公式（7.1）中指数项的运算，那
么计算其每一个点 X (n) 需要 N 次复数乘法和 N-1 次的复数加法。显然当 N 很
大时，这个工作量也非常巨大。正是由于这个原因，使得 DFT 的应用范围在过
去很长的时间里受到了严格的限制。注意到公式（1）是非常有规律性的，那
么能否利用这种规律性来降低 DFT 的计算时间？
1965 年，凯莱和塔柯的提出了一种用于计算 DFT 的数学方法，大大减少了
1
0
/2
1,1,...,1,0,)()(
N
k
Nnki
iNnekxnX
资源评论
event7252012-12-22程序注释还是蛮详细的，可以借鉴下
