DFT的计算量

2011-08-11 10:52:29来源: 互联网 关键字:计算

    离散傅里叶变换在实际应用中是非常重要的,利用它可以计算信号的频谱、功率谱和线性卷积等。但是,如果使用定义式(3.20)来直接计算DFT,当N很大时,即使使用高速计算机,所花的时间也太多。因此,如何提高计算DFT的速度,便成了重要的研究课题。1965年库利 (Cooley)和图基(Tukey)在前人的研究成果的基础上提出了快速计算DFT的算法,之后,又出现了各种各样快速计算DFT的方法,这些方法统称为快速傅里叶变换(Fast Fourier Transform),简称为FFT。FFT的出现,使计算DFT的计算量减少了两个数量级,从而成为数字信号处理强有力的工具。
     快速傅里叶变换(FFT)是离散傅里叶变换(DFT)的快速算法。它是DSP领域中的一项重大突破,它考虑了计算机和数字硬件实现的约束条件、研究了有利于机器操作的运算结构,使DFT的计算时间缩短了1~2个数量级,还有效地减少了计算所需的存储容量,FFT技术的应用极大地推动了DSP的理论和技术的发展。
在导出FFT算法之前,首先来估计一下直接计算DFT所需的计算量。

DFT的定义

将DFT定义式展开成方程组

将方程组写成矩阵形式

用复数表示:

FFT算法是基于可以将一个长度为N的序列的离散傅里叶变换逐次分解为较短的离散傅里叶变换来计算这一基本原理的。这一原理产生了许多不同的算法,但它们在计算速度上均取得了大致相当的改善。

    在本章中我们集中讨论两类基本的FFT算法。
    第一类 称为按时间抽取(Decimation-in-Time)的基2FFT算法,它的命名来自如下事实:在把原计算安排成较短变换的过程中,序列x(n)(通常看作是一个时间序列)可逐次分解为较短的子序列。
    第二类称为按频率抽取(Decimation-in-Frequency)的基2FFT算法,在这类算法中是将离散傅里叶变换系数序列X(k)分解为较短的子序列。
   
    前面两种算法特别适用于N等于2的幂的情况。
    对于N为合数的情况,本章也将介绍两种处理方法。

关键字:计算

编辑:eeleader 引用地址:http://www.eeworld.com.cn/gykz/2011/0811/article_7987.html
本网站转载的所有的文章、图片、音频视频文件等资料的版权归版权所有人所有,本站采用的非本站原创文章及图片等内容无法一一联系确认版权者。如果本网所选内容的文章作者及编辑认为其作品不宜公开自由传播,或不应无偿使用,请及时通过电子邮件或电话通知我们,以迅速采取适当措施,避免给双方造成不必要的经济损失。

上一篇:蝶形、同址和变址计算方法及公式
下一篇:基于VB语言的机器人足球仿真比赛与对策研究

关注eeworld公众号 快捷获取更多信息
关注eeworld公众号
快捷获取更多信息
关注eeworld服务号 享受更多官方福利
关注eeworld服务号
享受更多官方福利
推荐阅读
全部
计算

小广播

独家专题更多

2017东芝PCIM在线展会
2017东芝PCIM在线展会
TI车载信息娱乐系统的音视频解决方案
TI车载信息娱乐系统的音视频解决方案
汇总了TI汽车信息娱乐系统方案、优质音频解决方案、汽车娱乐系统和仪表盘参考设计相关的文档、视频等资源
迎接创新的黄金时代 无创想,不奇迹
迎接创新的黄金时代 无创想,不奇迹
​TE工程师帮助将不可能变成可能,通过技术突破,使世界更加清洁、安全和美好。
电子工程世界版权所有 京ICP证060456号 京ICP备10001474号 电信业务审批[2006]字第258号函 京公海网安备110108001534 Copyright © 2005-2017 EEWORLD.com.cn, Inc. All rights reserved