第三章 快速付里叶变换FFT（1）.ppt

第三章快速付里叶变换(FFT)Fast Fouriet Transformer
第一节引言
一、快速付里叶变换FFT
有限长序列通过离散傅里叶变换(D F T) 将其频域离散化成有限长序列. 但其计算量太大, 很难实时地处理问题, 因此引出了快速傅里叶变换(FFT) .
FFT 并不是一种新的变换形式,它只是 DFT 的一种快速算法. 并且根据对序列分解与选取方法的不同而产生了 FFT 的多种算法.
FFT 在离散傅里叶反变换、线性卷积和线性相关等方面也有重要应用.。
二、FFT产生故事
当时加文(Garwin)在自已的研究中极需要一个计算付里叶变换的快速方法。他注意到图基()正在写有关付里叶变换的文章,因此详细询问了图基关于计算付里叶变换的技术知识。图基概括地对加文介绍了一种方法,它实质上就是后来的著名的库利(Cooley )图基算法。在加文的迫切要求下,库利很快设计出一个计算机程序。1965年库利--图基在<计算数学>、Mathematic putation 杂志上发表了著名的“机器计算付里级数的一种算法”文章,提出一种快速计算DFT的方法和计算机程序--揭开了FFT发展史上的第一页,促使FFT算法产生原因还有1967年至1968年间FFT的数字硬件制成,电子数字计算机的条件, 使DFT的运算大简化了。
三、本章主要内容
。
(时间抽取算法DIT算法,频率抽取算法DIF算法,线性调频Z变换即CZT法)

第二节直接计算DFT算法存在的问题及改进途径
一、直接计算DFT计算量
问题提出: 设有限长序列x(n),非零值长度为N,计算对x(n)进行一次DFT运算,共需多大的运算工作量?

其中x(n)为复数, 也为复数
所以DFT与IDFT二者计算量相同。
,计算DFT复数运算量
计算一个X(k)(一个频率成分)值,运算量为
例k=1则
要进行N次复数乘法+(N-1)次复数加法
所以,要完成整个DFT运算,其计算量为:
N*N次复数相乘+N*(N-1)次复数加法

复数运算要比加法运算复杂,需要的运算时间长。
一个复数乘法包括4个实数乘法和2个实数相法。
(a+jb)(c+jd)=(ac-bd)+j(bc+ad)
4次复数乘法
2次实数加法