文档章节

快速傅里叶变换(FFT)的原理及公式

h
 houj
发布于 2015/04/24 14:18
字数 783
阅读 602
收藏 1

快速傅里叶变换(FFT)的原理及公式

原理及公式

  非周期性连续时间信号x(t)的傅里叶变换可以表示为

  式中计算出来的是信号x(t)的连续频谱。但是,在实际的控制系统中能够得到的是连续信号x(t)的离散采样值x(nT)。因此需要利用离散信号x(nT)来计算信号x(t)的频谱。
  有限长离散信号x(n),n=0,1,…,N-1的DFT定义为:

  可以看出,DFT需要计算大约N2次乘法和N2次加法。当N较大时,这个计算量是很大的。利用WN的对称性和周期性,将N点DFT分解为两个N/2点的 DFT,这样两个N/2点DFT总的计算量只是原来的一半,即(N/2)2+(N/2)2=N2/2,这样可以继续分解下去,将N/2再分解为N/4点 DFT等。对于N=2m 点的DFT都可以分解为2点的DFT,这样其计算量可以减少为(N/2)log2N次乘法和Nlog2N次加法。图1为FFT与DFT-所需运算量与计算点数的关系曲线。由图可以明显看出FFT算法的优越性。

  将x(n)分解为偶数与奇数的两个序列之和,即

  x1(n)和x2(n)的长度都是N/2,x1(n)是偶数序列,x2(n)是奇数序列,则

  其中X1(k)和X2(k)分别为x1(n)和x2(n)的N/2点DFT。由于X1(k)和X2(k)均以N/2为周期,且WN k+N/2=-WN k,所以X(k)又可表示为:

  上式的运算可以用图2表示,根据其形状称之为蝶形运算。依此类推,经过m-1次分解,最后将N点DFT分解为N/2个两点DFT。图3为8点FFT的分解流程。


  FFT算法的原理是通过许多小的更加容易进行的变换去实现大规模的变换,降低了运算要求,提高了与运算速度。FFT不是DFT的近似运算,它们完全是等效的。

关于FFT精度的说明:

  因为这个变换采用了浮点运算,因此需要足够的精度,以使在出现舍入误差时,结果中的每个组成部分的准确整数值仍是可辨认的。为了FFT的舍入误差,应该允许增加几倍log2(log2N)位的二进制。以256为基数、长度为N字节的数可以产生大到(256)2N阶的卷积分量,所以为了正确存储,需要16+log2N位精度,若数i是浮点尾数的二进制位数,则有条件: 
  如果i=24,对于任意感兴趣(N>256)的N值,单精度是不合适的;如果i=53,也就是采用双精度,则允许N大于106,相当于几百万十进制位。所以,用FFT作大数乘法时,向量数组选用双精度类型。

本文转载自:http://www.cnblogs.com/Lyush/articles/3219196.html

h
粉丝 9
博文 81
码字总数 57985
作品 0
长沙
技术主管
私信 提问
傅里叶变换期权定价的数值方法

0.通过傅里叶变换计算BSM 定价的call 期权 Carr/Madan payoff 傅立叶变换法 underlying asset X : 的特征方程为 期权价格的 如果使用特定的特征方程,就可以得到对应的随机过程下的定价, 这里...

侯亮
2017/12/11
0
0
(三)OpenCV中的图像处理之图像变换及模板匹配

注释:本文翻译自OpenCV3.0.0 document->OpenCV-Python Tutorials,包括对原文档种错误代码的纠正 3.10 OpenCV中的图像变换 第一节:傅里叶变换(Fourier Transform) 1.目标 使用OpenCV查找图...

u014403318
2018/05/30
0
0
【工具使用系列】关于 MATLAB 图像变换,你需要知道的事

如何进行图像变换(频域处理) 正交变换 傅里叶变换 二维连续傅里叶变换 二维离散傅里叶变换(DFT) 快速傅里叶变换(FFT) 离散余弦变换 一维离散余弦变换 二维离散余弦变换 离散正弦变换 ...

AllenMoore
2018/01/26
47
0
[Python图像处理] 二十二.Python图像傅里叶变换原理及实现

版权声明:本文为博主原创文章,转载请注明CSDN博客源地址!共同学习,一起进步~ https://blog.csdn.net/Eastmount/article/details/89474405 该系列文章是讲解Python OpenCV图像处理知识,前...

Eastmount
04/23
0
0
功率谱和频谱的区别、联系

功率谱:信号先自相关再做FFT。 频 谱:信号直接做FFT。 一. 区别 1. 一个信号的频谱,只是这个信号从时域表示转变为频域表示,只是同一种信号的不同的表示方式而已,而功率谱是从能量的观点...

天蚕宝衣
2017/04/10
427
0

没有更多内容

加载失败,请刷新页面

加载更多

kibana汉化

kibana5 / 6 需要下载补丁包,https://github.com/anbai-inc/Kibana_Hanization 其中 v6 版本原生支持国际化,只需要添加资源文件并且配置即可 kibana7 v7版本官方内置汉化资源,在配置文件 ...

细肉云吞
10分钟前
2
0
spring boot 自定义日志 log4j2

使用默认的日志在实际开发中会存在很多问题,比如备份文件名称无法自动重命名、各个等级的日志被放在一个文件中等,所以实际开发中为了更好满足我们的需求,我们一般都会自定义采用配置的方式...

雷开你的门
14分钟前
1
0
PCB设计-Allegro软件入门系列-设计参数配置(上)

前言 经历了导入网表,和放置器件后,我们就要画板子了,但是必要的设计参数也要先准备好,磨刀不误砍柴工。 《一》显示参数 这里主要设置DRC报错标志大小和飞线显示类型 (1)DRC标志可以适当...

demyar
15分钟前
2
0
js实现微博、微信分享

html <!-- 分享 --><div class="share-box"> <b style="vertical-align: middle;">分享到:</b> <a title="分享到新浪微博" class="shareSina"><span class="share-icon"></span><......

张兴华ZHero
31分钟前
3
0
创龙TMS320DM8168浮点DSP C674x + ARM Cortex-A8的CPU、NAND FLASH、NOR FLASH

TL6678-EasyEVM是广州创龙基于SOM-TL6678核心板而研发的一款多核高性能DSP开发板。开发板采用核心板+底板方式,底板采用沉金无铅工艺的四层板设计,尺寸为200mm*106.65mm,它为用户提供了SOM...

Tronlong创龙
34分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部