第2章离散傅里叶变换及其快速算法.pptVIP

2.0引言2.1.1离散傅里叶级数

（DFS）则DFS变换对可写为：2.1.2离散傅里叶变换

（DFT）2.1.2:DFT性质（7）DFT形式下的Parseval定理（8）延长特性（补充）DFT运算的特点DFT运算的特点2.3.1按时间抽取的FFT按时间抽取的FFT的推导按时间抽取的FFT的8点蝶形流图时间抽取法FFT的运算特点FFT运算的应用推导2N实序列的DFT线性卷积的FFT实现步骤快速卷积法的应用(1)重叠相加法——由分段卷积的各段相加构成总的卷积输出假定N是2的整数次方，N=2M，M：正整数首先将序列x（n）分解为两组，一组为偶序数项，一组为奇序数项，r=0,1，…，N/2-1按时间抽取的FFT算法的推导其中按时间抽取的FFT算法的推导（I）以N=8为例g[n]h[n]DITFFT第1次抽取流图注意到,H(k)、G(k)有N/2个点,即k=0,1,…,N/2-1,还可以应用系数WkN的周期性和对称性,表示X(k)的N/2～N-1点：得按时间抽取的FFT算法的推导（II）可见，一个N点的DFT被分解为两个N/2点的DFT，这两个N/2点的DFT再合成为一个N点DFT.蝶形信号流图将G(k)和H(k)合成X(k)运算可归结为：按时间抽取的FFT的蝶形流图Wa+bWa-bW-W-1a+bWa-bWWabab蝶形运算的简化(a)(b)N/2=4PointsDFTG(k)N/2=4PointsDFTH(k)-1-1-1-1按时间抽取FFT(DIT)蝶形流图（N=8）图(a)为实现这一运算的一般方法，它需要两次乘法、两次加减法。考虑到-bW和bW两个乘法仅相差一负号，可将图(a)简化成图(b)，此时仅需一次乘法、两次加减法。图(b)的运算结构像一蝴蝶通常称作蝶形运算结构简称蝶形结，采用这种表示法，就可以将以上所讨论的分解过程用流图表示。按照这个办法，继续把N/2用２除，由于N=2M，仍然是偶数，可以被２整除，因此可以对两个N/2点的DFT再分别作进一步的分解。即对{G(k)}和{H(k)}的计算，又可以分别通过计算两个长度为N/4=2点的DFT，进一步节省计算量，见图。这样，一个８点的DFT就可以分解为四个２点的DFT。按时间抽取的FFT的蝶形流图N/4点N/4点N/4点N/4点由四个2点DFT组成8点DFT按时间抽取的FFT的蝶形流图最后剩下的是2点DFT，它可以用一个蝶形结表示：由于这种方法每一步分解都是按输入时间序列是属于偶数还是奇数来抽取的，所以称为“按时间抽取法”或“时间抽取法”。这样，一个8点的完整的按时间抽取运算的流图按时间抽取的8点FFT01234567蝶形运算原位计算序数重排蝶形类型随迭代次数成倍增加级数：m，共有?级m=1，2，3，。。。，?=log2N迭代公式蝶距：dm=q?p（1）蝶形运算(m–1)级WNr–1m级1次复乘权系数：WNr乘法运算加法运算m12…v-1v12……N/2N/4…21对于N=2M，总是可以通过M次分解最后成为2点的DFT运算。这样构成从x(n)到X(k)的M级运算过程。从上面的流图可看到，每一级运算都由N/2个蝶形运算构成。因此每一级运算都需要N/2次复乘和N次复加，这样，经过时间抽取后M级运算总共需要的运算：复乘而直接运算时则与N2成正比。复加乘法运算和加法运算量注：N=2?例:N=2048，N2=4194304，(N/2)log2N=11264，N2/[(N/2)log2N]=392.4。FFT显然要比直接法快得多当数据输入到存储器中以后，每一级运算的结果仍然储存在同一组存储器中，直到最后输出，中间无需其它存储器，这