第四章 快速付里叶变换(FFT) Fast Fourier Transforming
41引言 ●快速付里叶变换FFT ◆有限长序列通过离散傅里叶变换(DFT)将其频域离散化成有限 长序列。但其计算量太大(与N的平方成正比),很难实时地 处理问题,因此引出了快速傅里叶变换(FFT)。 ◆FFT并不是一种新的变换形式,它只是D「T的一种快速算法, 并且根据对序列分解与选取方法的不同而产生了FT的多种算 法 ◆FFT在离散傅里叶反变换、线性卷积和线性相关等方面也有重 要应用
4.1引言 ●产生故事 1965(COy].M)和图基( N Turkey)在 《 Mathematic of Computation》杂志上发表了著名的“机器 计算付里级数的一种算法”文章,提出一种快速计算DFT的 方法和计算机程序-揭开了FFT发展史上的第一页
41引 ●本章主要内容 ◆直接计算DFT算法存在的问题及改进途径。 ◆多种DFT算法(吋间抽取算法DIT算法,频率抽取算法DIF算 法,线性调频Z变换即CzT法) ◆FT的应用
42基2F算法 ●DFT计算存在的问题及改进途径 ◆问题提出:设有限长序列X(n),非零值长度为N计算 对x(n)进行一次DFT运算,共需多大的运算工作量?