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
本网站转载的所有的文章、图片、音频视频文件等资料的版权归版权所有人所有,本站采用的非本站原创文章及图片等内容无法一一联系确认版权者。如果本网所选内容的文章作者及编辑认为其作品不宜公开自由传播,或不应无偿使用,请及时通过电子邮件或电话通知我们,以迅速采取适当措施,避免给双方造成不必要的经济损失。
论坛活动 E手掌握
微信扫一扫加关注
论坛活动 E手掌握
芯片资讯 锐利解读
微信扫一扫加关注
芯片资讯 锐利解读
推荐阅读
全部
计算

小广播

独家专题更多

富士通铁电随机存储器FRAM主题展馆
富士通铁电随机存储器FRAM主题展馆
馆内包含了 纵览FRAM、独立FRAM存储器专区、FRAM内置LSI专区三大部分内容。 
走,跟Molex一起去看《中国电子消费品趋势》!
走,跟Molex一起去看《中国电子消费品趋势》!
 
带你走进LED王国——Microchip LED应用专题
带你走进LED王国——Microchip LED应用专题
 
电子工程世界版权所有 京ICP证060456号 京ICP备10001474号 电信业务审批[2006]字第258号函 京公海网安备110108001534 Copyright © 2005-2016 EEWORLD.com.cn, Inc. All rights reserved