第4章 快速傅里叶变换 4.1 引言 4.2 直接计算DFT的问题及改进的途径 4.3 按时间抽取（DIT）的基2-FFT算法4.4 按频率抽取（DIF）的基2-FFT算法4.5 IDFT的高效算法 4.6 FFT的其他应用快速卷积 学习目标u理解按时间抽取的基-2FFT算法的原理、运 算流图、所需计算量和算法特点；u理解按频率抽取的基-2FFT算法的原理、运 算流图、所需计算量和算法特点；u理解IFFT算法；u理解线性卷积的FFT算法及分段卷积（即块 卷积）方法。4.1 引 言 快速傅里叶变换（FFT）并不是一种新的变换， 而是离散傅里叶变换（DFT）的一种快速算法。 在信号的频谱分析、 系统的分析、 设计和实现中都会用到DFT的计算。 DFT的计算量太大，很难对问题进行实时处理，难以实用。 1965年首次发现了DFT运算的一种快速算法以后，人们开始认识到DFT运算的一些内在规律，从而很快地发展和完善了一套高速有效的运算方法， 这就是快速傅里叶变换（FFT）的算法。 FFT出现后使DFT的运算大大简化，运算时间一般可缩短一二个数量级之多，使DFT的运算在实际中真正得到了广泛的应用。 4.2 直接计算DFT的问题及改进的途径 一、 直接计算DFT的运算量问题设x(n)为N点有限长序列，其DFT为 k=0, 1, , N-1 反变换（IDFT）为 n=0, 1, , N-1 运算量一个X(k)复数乘法复数加法NN-1N2N(N-1)N个X(k) 一次复数乘法需用四次实数乘法和二次实数加法； 一次复数加法需二次实数加法。 一个X(k)实数乘法实数加法4N2N+2(N-1)=2(2N-1)4N22N(2N-1)N个X(k)二、 改进的途径ux(n)u长序列短序列uWNkn4.3 按时间抽取（DIT）的基 -2 FFT算法 一、 算法原理1. 一次分解 NN/2设序列x(n)长度为N，且满足N=2M，M为正整数。按n的奇偶把x(n)分解为两个N/2点的子序列： k=0,1,.,N/2-1X1(k)与X2(k)分别是x1(r)及x2(r)的N/2点DFT： 一个N点DFT已分解成两个N/2点的DFT利用周期性求X(k)的后半部分N点（N=8）DFTx(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6 )X(7)X1(0)X1(1)X1(2)X1(3)X2(1)X2(2)X2(3)X2(0) -1-1-1-1WN0WN1WN2WN3N/2点DFTN/2点DFTx(0)=x1(0)x(2)=x1(1)x(4)=x1(2)x(6)=x1(3)x(1)=x2(0)x(3)=x2(1)x(5)=x2(2)x(7)=x2(3)2. 二次分解 N/2N/4X2(k)也可进行同样的分解： x(0)=x1(0)x(2)=x1(1)x(4)=x1(2)x(6)=x1(3)x(1)=x2(0)x(3)=x2(1)x(5)=x2(2)x(7)=x2(3)N/2点 DFTN/2点 DFTX1(0)X(0)X1(1)X(1)X1(2)X(2)X1(3)X(3)X2(1)X(5)X2(2)X(6)X2(3)X(7)X2(0)X(4) -1-1-1-1WN0WN1WN2WN3N/2点DFT分解为两个N/4点DFT 一个N=8点DFT分解为四个N/4点DFT N=8，四个N/4点DFT即四个2点DFT，其输出分别为：X3(k)，X4(k)，X5(k)，X6(k)，k=0, 1N=8 按时间抽取的FFT运算流图X3(0)X3(1)X4(0)X4(1)X5(0)X5(1)X6(0)X6(1)N=8时共有三级蝶形运算，每一级有N/2=4个蝶形 X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)x3(0 ) x3(1 ) x4(0)x4(1)x5(0)x5(1)x6(0)x6(1)二、 按时间抽取的FFT算法与直接计算DFT运算量的比较u N=2M时，共有M级蝶形， 每级都由N/2个蝶形运算组成；u每个蝶形需要一次复乘、 二次复加；u每级运算都需N/2次复乘和N次复加；uM级运算总共需要： 复乘数 复加数 数学符号lb=log2 以乘法为例，直接DFT复数乘法次数是N2，FFT复数乘法次数是(N/2) lbN； 直接计算DFT与FFT算法的复数乘法计算量之比为 ：当N=2048时，这一比值为372.4，即直接计算DFT的运算量是FFT运算量的372.4倍；当点数N越大时，FFT的优点更为明显。 对一个连续时间信号xa(t)采样1秒得到一个4096个采样点 的序列，若计算采样信号的4096点DFT。假定仅对200f300Hz频率范围所对应的DFT采样点感兴趣。（1）若直接用DFT，要计算这些值需要多少次复乘？MN=1014096=413696（2）若用基2的DIT-FFT计算，则需要多少次复乘？N/2log2N=4096/2log24096=24576思考题N点x(n)序列，构造新序列y(n)=x(n/2),n为偶数时，y(n)=0，n为奇数时， n=0,1,2,2N-1，求：Y(K)与X(K)的关系，K=0,1,2,. 2N-1例 题：解：由DIT-FFT可得 y(2n)= y1(n)=x(n), Y1(K)=X(K) y(2n+1)= y2(n)= 0, Y2(K)=0 n=0,1,.,N-1已知x(n)长度为N（N为偶数）。定义两个长度为N/2的 序列如下:其中，G(k)=DFTg(n), H(k)=DFTh(n),分别为N/2长。 试利用G(k)和H(k)表示出X(k)=DFTx(n)，k=0,1,N -1。补充题第3章 快速傅里叶变换 提示三、 按时间抽取的FFT算法的特点1. 原位运算（同址运算）第一级蝶形运算第二级蝶形运算 第三级蝶形运算m表示第m级迭代，k, j为数据所在行数； 某一级的两个节点k和j的节点变量进行蝶形运算后， 得到结果为下一级k, j两节点的节点变量，即每个蝶形 的输入、输出数据节点同在一条水平线上；与其他节点变量无关，即蝶形的两个输出值仍放回蝶 形的两个输入所在的存储器中； 每级的N/2 个蝶形运算全部完成后，再开始下一级的 蝶形运算；这样经过M级运算后，原存放输入数据的N个存储单 元中依次存放输出的N个值；这种利用同一存储单元存放蝶形计算输入、输出数据 的方法称为原位运算。可以节省存储单元,降低设备成 本。 2. 倒位序规律基2的DIT-FFT的输出X(k)按正常顺序排列在存储单元中，即按X(0)，X(1)，X(7)的顺序排列；输入x(n)却不是按自然顺序存储的，而是按x(0)，x(4)， ， x(7)的顺序存入存储单元，看起来好像是“混乱无序”的；实际上是有规律的，我们称之为倒位序。 n用二进制数表示为(n2n1n0)2（当N=8=23时，二进制为三位） 第一次分组，n为偶数（相当于n的二进制数的最低位n0=0）在上半部分，n为奇数（相当于n的二进制数的最低位 n0=1）在下半部分。 下一次则根据次最低位n1为“0”或是“1”来分偶奇（而不管原来的子序列是偶序列还是奇序列）， 如此继续分下去，直到最后N个长度为1的子序列。倒位序N=8时的自然顺序二进制数和相应的倒位序二进制数 自然顺序（I ） 二进制数 倒位序二进 制数 倒位序（J） 0 1 2 3 4 5 6 7000 001 010 011 100 101 110 111000 100 010 110 001 101 011 1110 4 2 6 1 5 3 7 先按自然顺序将输入序列存入存储单元， 为了得到倒位序的排列，我们通过变址运算来完成； 如果输入序列的自然顺序号I用二进制数（例如n2n1n0）表示，则其倒位序J对应的二进制数就是（n0n1n2），这样，在原来自然顺序时应该放x(I)的单元，现在倒位序后应放x(J)。000 001010011100101110111000 100010110001101011111顺序数I的起始、终止值分别为1和N-2；倒序数J的起始值为N/2；为避免重复调换，只对IN L=M+N-1M 短序列补很多零，长序列需全部输入后才能计算 存储容量大 运算时间长，处理延时很大，难于实时处理 怎么解决？块卷积（重叠相加和重叠保留法）2重叠相加法设h(n)的点数为N，将x(n)分解为很多段，每段为m点，各段互不重叠，m和N的数量级相同，用xi(n)表示x(n)的第i段： imn(i+1)m-1 其他n i=0, 1, xi(n)为m点，yi(n)为（m+N-1）点； 相邻两段输出序列必然有（N-1）个点发生重叠，即前一段的后（N-1）个点和后一段的前（N-1）个点相重叠； 将重叠部分相加再和不重叠的部分共同组成输出。 特点： x(n)分段各数据子段互不重叠； h(n)与xi(n)各子段所作为线性卷积得yi(n)； yi(n)数据间有N-1点重叠； 最后的卷积结果y(n)为各子段线性卷积yi(n)之和。3 重叠保留法将x(n)分段，每段L个点，序列中补零处不补零，而在每一段的前边补上前一段保留下来的（M-1）个输入序列值， 组成N=L+M-1点序列xi(n)；如果L+M-12m， 则可在每段序列末端补零值点，补到长度为2m；用DFT实现h(n)和xi(n)的N点圆周卷积，则其每段圆周卷积结果的前（M-1）个点的值不等于线性卷积值，必须舍去。 重叠保留法示意图 重叠保留法示意图 用保留信号代替补零后的局部混叠现象 用保留信号代替补零后的局部混叠现象 为了说明以上说法的正确性，我们来看一看图3-29。任一段xi(n)（为N点）与h(n)（原为M点，补零值后也为N点）的N点圆周卷积 N由于h(m)为M点，补零后作N点圆周移位时，在n=0,1,M-2的每一种情况下，h(n-m)NRN(m)在0mN-1范围的末端出现非零值， 而此处xi(m)是有数值存在的，图4-27（c），（d）为n=0, n=M-2的情况，所以在 0nM-2 这一部分的yi(n)值中将混入xi(m)尾部与h(n-m)NRN(m)尾部的乘积值，从而使这些点的yi(n)不同于线性卷积结果。但是从n=M-1开始到n=N-1，h(n-m)NRN(m)=h(n-m)（如图4-26（e），（f）所示），圆周卷积值完全与线性卷积值一样，yi(n)就是正确的线性卷积值。因而必须把每一段圆周卷积结果的前(M-1)个值去掉， 如图4-26（g）所示。 因此，为了不造成输出信号的遗漏，对输入分段时，就需要使相邻两段有M-1个点重叠（对于第一段，即x0(n)，由于没有前一段保留信号，则需要在序列前填充M-1 个零值点），这样，若原输入序列为x(n)（n0 时有值），则应重新定义输入序列 0nM-2 M-1n 而 0nN-1 其他n i=0, 1, 在这一公式中，已经把每一段的时间原点放在该段的起始点，而不是x(n)的原点。这种分段方法示于图4-25中，每段xi(n)和h(n)的圆周卷积结果以yi(n)表示，如图 4-25（b）所示，图中已标出每一段输出段开始的(M-1)个点，0nM-2部分舍掉不用。把相邻各输出段留下的序列衔接起来，就构成了最后的正确输出， 即 式中: M-1nN-1 其他n 这时，每段输出的时间原点放在yi (n)的起始点，而不是y(n)的原 点。