详解FFT(快速傅里叶变换FFT
第四章 快速傅里叶变换
有限长序列可以通过离散傅里叶变换(DFT)将其频域也离散化成有限长 序列.但其计算量太大,很难实时地处理问题,因此引出了快速傅里叶变换 (FFT). 1965 年，Cooley 和 Tukey 提出了计算离散傅里叶变换（DFT）的快 速算法，将 DFT 的运算量减少了几个数量级。从此，对快速傅里叶变换（FFT） 算法的研究便不断深入，数字信号处理这门新兴学科也随 FFT 的出现和发 展而迅速发展。根据对序列分解与选取方法的不同而产生了 FFT 的多种算 法，基本算法是基２DIT 和基２DIF。FFT 在离散傅里叶反变换、线性卷积 和线性相关等方面也有重要应用。
快速傅里叶变换（FFT）是计算离散傅里叶变换（DFT）的快速算法。 DFT 的定义式为
N 1
kn
X (k ) = ∑ x(n)WN RN (k )
n =0
kn 在所有复指数值 W N的值全部已算好的情况下，要计算一个 X (k ) 需要 N
次复数乘法和 N－1 次复数加法。算出全部 N 点 X (k ) 共需 N 次复数乘法
2
和 N ( N 1) 次复数加法。即计算量是与 N 2 成正比的。
FFT 的基本思想：将大点数的 DFT 分解为若干个小点数 DFT 的组合， 从而减少运算量。
WN 因子具有以下两个特性，可使 DFT 运算量尽量分解为小点数的 DFT
运算：
（1） 周期性： W ( k + N ) n
N
kn
= W = W ( n + N ) k
N
N
（2） 对称性：W
( k + N / 2 )
= W
k
N N
利用这两个性质，可以使 DFT 运算中有些项合并，以减少乘法次数。例子： 求当 N＝4 时，X(2)的值
你可能喜欢
- 傅里叶变换公式
- 傅里叶变换ppt
- 快速傅里叶变换原理
- 傅里叶变换应用
- FFT算法
- 常用傅里叶变换
- 工程分析
- 常用傅里叶变换、拉普拉斯变换、极坐标变换、达朗贝尔公式6页
- 傅里叶变换的由来及复数下的傅里叶变换公式证明4页
- 傅里叶变换公式23页
- 傅里叶变换本质及其公式解析7页
- 信号与系统公式&常用的连续傅里叶变换2页
- 信号与系统公式+常用的连续傅里叶变换2页
- 傅里叶变换__经典ppt57页
- 傅里叶变换__经典ppt57页
- §8.9序列的傅里叶变换(DTFT) .ppt9页
- 傅里叶变换特性实例ppt42页
- 复变函数与积分变换第8章 傅里叶变换ppt30页
- 傅里叶变换__经典ppt61页
- 《数字信号处理——原理、实现及应用》第三章 离散傅里叶变换(DFT)及其快速算法(FFT)88页
- 快速傅里叶变换(FFT) 原理 介绍3页
- 快速傅里叶变换的原理与方法3页
- 快速傅里叶变换原理及其应用13页
- 快速傅里叶变换的原理与方法3页
- 《数字信号处理——原理、实现及应用》第三章_离散傅里叶变换(DFT)及其快速算法(FFT)88页
- 数字信号处理 离散傅里叶变换的性质及应用9页
- Chapter6-傅里叶变换的应用47页
- 第六章-傅里叶变换的应用14页
- dsp实验三 快速傅里叶变换及其应用10页
- 快速傅里叶变换FFT的matlab实现和FFT的简单应用10页
- 《数字信号处理——原理、实现及应用》第三章 离散傅里叶变换(DFT)及其快速算法(FFT)88页
- 实验4 FFT算法应用6页
- 基于FPGA的FFT算法研究4页
- FFT快速算法C程序7页
- 傅里叶变换FFT算法的介绍及其在微机继电保护中的应用 陆志强19页
- 基于FPGA实现高速流水线FFT算法8页
- 基于DSP的FFT算法实现4页
