离散傅里叶变换及其快速算法.ppt

第二章离散傅里叶变换及其快速算法,1753年，Bernoulli就推断一振动的弦可以表示成正弦加权和的形式，但是他未能给出所需的加权系数。Jean-Baptiste-JosephFourier于1768年3月出生在法国的Auxerre，当他8岁时不幸成了一名孤儿，被收养在一个宗教界主办的军事学校中。在此期间，Fourier对数学产生了浓厚的兴趣。21岁那年，Fourier在巴黎学术界论述了有关数值方程解的著名论作，这一工作使他在巴黎的数学界出名。Fourier不仅是公认的大数学家，而且他还是一位杰出的教师。他灵活运用历史典故使得他的讲座非常生动。实际上，Fourier所研究的主要领域是数学史。Fourier是最早以应用的眼光来解释抽象数学概念的研究者之一。1798年，拿破仑侵略埃及，在侵略队伍中一些有名的数学家和科学家，Fourier就是其中的一位，他负责组织修建第一条从格勒诺布尔到都灵的道路。Fourier也是一个拥有独特想法的一个怪才。例如，他认为酷热是理想的环境，因此，他喜欢居住在严热的小屋里，并穿上厚厚的衣服。1801，法国决心召回自己的军队，于是Fourier才得以重返家园。回国后，Fourier被任命为格勒诺布尔伊泽尔省的长官，就是在此期间，Fourier完成了其经典之作Theorieanalytiquedelachaleur(热能数学原理)。在该著作中，他证明了任一周期函数都可以表示成正弦函数和的形式，其中正弦函数的频率为频率的整数倍。,Fourier,离散傅里叶变换不仅具有明确的物理意义，相对于DTFT他更便于用计算机处理。但是，直至上个世纪六十年代，由于数字计算机的处理速度较低以及离散傅里叶变换的计算量较大，离散傅里叶变换长期得不到真正的应用，快速离散傅里叶变换算法的提出，才得以显现出离散傅里叶变换的强大功能，并被广泛地应用于各种数字信号处理系统中。近年来，计算机的处理速率有了惊人的发展，同时在数字信号处理领域出现了许多新的方法，但在许多应用中始终无法替代离散傅里叶变换及其快速算法。,二、DFS离散付里级数的推导意义,用数字计算机对信号进行频谱分析时，要求信号必须以离散值作为输入，而且上面讨论可知：只有第四种形式(DFS)对数字信号处理有实用价值。但如果将前三种形式要么在时域上采样，要么在频域上采样，变成离散函数，就可以在计算机上应用。所以我们要先了解如何从以上三种形式推出DFS.,1.由非周期连续时间信号推出DFS,X(t)经过抽样为x(nT),对离散的时间信号进行DTFT得到周期连续频谱密度函数。再经过抽样，得到周期性离散频谱密度函数即为DFS.,x(t),t,取样,x(t),t,DTFT,X(ejT),采样,X(ejw),w,2.周期性连续时间信号函数,周期性连续时间信号函数经采样后，得到周期性的离散时间函数(DFS)。,x(t),X(ejw),t,w,采样,3.非周期离散时间信号,非周期离散时间信号经过序列付里时变换(即单位园上的Z变换)DTFT,得到周期连续谱密度函数，再经采样为周期离散频谱密度函数(DFS)。,x(t),t,X(ejT),w,X(ejw),DTFT,采样,三、推导DFS正变换,以下由第三种付里叶级数形式为例推导出离散付里叶级数变换。非周期信号x(n),其DTFT(单位园上Z变换)为其为周期连续频谱密度函数，对其进行采样，使其成为周期性离散频谱函数。设在一周期内采样N个点，则两采样点间距为：得到频间距为：代入DTFT式子中得：,四、DFS的反变换,即证：证明：已知两边同乘以,并对一个周期求和用n置换r得：,根据正交定理,回顾DFS,设x(n)为周期为N的周期序列,则其离散傅里叶级数(DFS)变换对为:正变换反变换其中:,五、离散付里叶级数性质,可以由抽样Z变换来解析DFS，它的许多性质与Z变换性质类似。它们与Z变换主要区别为：(1)与两者具有周期性，与Z变换不同。(2)DFS在时域和频域之间具有严格的对偶关系。它们主要性质分为：线性、序列移位(循环移位)、调制性、周期卷积和,(1)线性,(2)序列移位(循环、移位),时域频域,(3)调制性,(4)时域卷积,周期卷积和与以前卷积不同，它的卷积过程限在一个周期内称为周期卷积。时域卷积等于频域相乘。频域：,(5)频域卷积,时域：,证:,同理:,对于复序列其共轭序列满足,3）共轭对称性,已知序列x1(n)=R4(n),x2(n)=(n+1)R5(n),分别将序列以周期为6周期延拓成周期序列,本节涉及内容周期序列的离散傅立叶级数（DFS）正变换:反变换：,2.1.2离散傅里叶变换（DFT）,我们知道周期序列实际上只有有限个序列值有意义，因此它的许多特性可推广到有限长序列上。一个有限长序列x(n)，长为N，为了引用周期序列的概念，假定一个周期序列，它由长度为N的有限长序列x(n)延拓而成，它们的关系：,周期序列的主值区间与主值序列：对于周期序列，定义其第一个周期n=0N-1，为的“主值区间”，主值区间上的序列为主值序列x(n)。x(n)与的关系可描述为：数学表示：RN(n)为矩形序列。符号(n)N是余数运算表达式，表示n对N求余数。,例：是周期为N=8的序列，求n=11和n=-2对N的余数。因此,频域上的主值区间与主值序列：,周期序列的离散傅氏级数也是一个周期序列，也可给它定义一个主值区间，以及主值序列X(k)。数学表示：,长度为N的有限长序列x(n)，其离散傅里叶变换X(k)仍是一个长度为N的有限长序列，它们的关系为：x(n)与X(k)是一个有限长序列离散傅里叶变换对，已知x(n)就能唯一地确定X(k)，同样已知X(k)也就唯一地确定x(n)，实际上x(n)与X(k)都是长度为N的序列（复序列）都有N个独立值，因而具有等量的信息。有限长序列隐含着周期性。,DFT的矩阵方程表示,DFT特性：,以下讨论DFT的一些主要特性，这些特性都与周期序列的DFS有关。假定x(n)与y(n)是长度为N的有限长序列，其各自的离散傅里叶变换分别为：X(k)=DFTx(n)Y(k)=DFTy(n)(1)线性DFTax(n)+by(n)=aX(k)+bY(k),a,b为任意常数,(2)循环移位有限长序列x(n)的循环移位定义为：f(n)=x(n+m)NRN(n)含义：1)x(n+m)N表示x(n)的周期延拓序列的移位：2)x(n+m)NRN(n)表示对移位的周期序列x(n+m)N取主值序列,所以f(n)仍然是一个长度为N的有限长序列。f(n)实际上可看作序列x(n)排列在一个N等分圆周上，并顺时针旋转m位。,循环移位,循环移位,移位前,左移两位后,证：利用周期序列的移位特性：实际上，利用WN-mk的周期性，将f(n)=x(n+m)NRN(n)代入DFT定义式，同样很容易证明。,序列循环移位后的DFT为F（k）=DFTf（n）=x（k）,同样，对于频域有限长序列X(k)的循环移位，有如下反变换特性：IDFTX(k+l)NRN(k)=x（n）,（3）循环卷积若F（k）=X（k）Y（k）则或,证：这个卷积可看作是周期序列卷积后再取其主值序列。将F（k）周期延拓，得：则根据DFS的周期卷积公式：因0mN-1时，x(m)N=x(m)，因此经过简单的换元可证明：,这一卷积过程与周期卷积比较，过程是一样的，只是这里只取结果的主值序列，由于卷积过程只在主值区间0mN-1内进行，所以实际上就是y（m）的圆周移位，称为“循环卷积”，习惯上常用符号“”表示循环卷积，以区别于线性卷积。,同样，若f(n)=x(n)y(n)，则,（4）有限长序列的线性卷积与循环卷积（循环卷积的应用）实际问题的大多数是求解线性卷积，如信号x(n)通过系统h(n)，其输出就是线性卷积y(n)=x(n)*h(n)。而循环卷积比起线性卷积，在运算速度上有很大的优越性，它可以采用快速傅里叶变换（FFT）技术，若能利用循环卷积求线性卷积，会带来很大的方便。现在我们来讨论上述x(n)与h(n)的线性卷积，如果x(n)、h(n)为有限长序列，则在什么条件下能用循环卷积代替而不产生失真。,有限长序列的线性卷积：,假定x(n)为有限长序列，长度为N，y(n)为有限长序列，长度为M，它们的线性卷积f(n)=x(n)*y(n)也应是有限长序列。因x(m)的非零区间：0mN-1，y(n-m)的非零区间：0n-mM-1，这两个不等式相加，得：0nN+M-2，在这区间以外不是x(m)=0，就是y(n-m)=0，因而f(n)=0。因此，f(n)是一个长度为N+M-1的有限长序列。,循环卷积：,重新构造两个有限长序列x(n)、y(n)，长度均为LmaxN,M，序列x(n)只有前N个是非零值，后L-N个为补充的零值；序列y(n)只有前M个是非零值，后L-M个为补充的零值。为了分析x(n)与y(n)的循环卷积，先看x(n),y(n)的周期延拓：,根据前面的分析，f（n）具有N+M-1个非零序列值，因此，如果周期卷积的周期LN/2=4，做4点的DFT：,先将N=8DFT分解成2个4点DFT：可知：时域上：x(0),x(2),x(4),x(6)为偶子序列x(1),x(3),x(5),x(7)为奇子序列频域上：X(0)X(3)，由X(k)给出X(4)X(7),由X(k+N/2)给出,(a)比较N=8点直接DFT与分解2个4点DFT的FFT运算量,N=8点的直接DFT的计算量为：N2次(64次）复数相乘,N(N-1)次(8(8-1)=56次)复数相加.共计120次。,（b)求一个蝶形结需要的运算量,要运算一个蝶形结，需要一次乘法，两次加法。,（c）分解为两个N/2=4点的DFT的运算量,分解2个N/2点（4点）的DFT：,偶数其复数相乘为复数相加为,奇数其复数相乘为复数相加为,(d)用2个4点来求N=8点的FFT所需的运算量,再将N/2点（4点）合成N点(8点)DFT时，需要进行N/2个蝶形运算,还需N/2次（4次）乘法及次(8次）加法运算。,(e)将N=8点分解成2个4点的DFT的信号流图,4点DFT,x(0)x(2)x(4)x(6),4点DFT,x(1)x(3)x(5)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(0),X2(1),X2(2),X2(3),偶数序列,奇数序列,X(4)X(7)同学们自已写,x1(r),x2(r),(2)N/2(4点)-N/4(2点)FFT(a)先将4点分解成2点的DFT：,因为4点DFT还是比较麻烦，所以再继续分解。若将N/2(4点)子序列按奇/偶分解成两个N/4点（2点）子序列。即对将x1(r)和x2(r)分解成奇、偶两个N/4点（2点）点的子序列。,(b)求2点的DFT,（c)一个2点的DFT蝶形流图,2点DFT,2点DFT,x(0)x(4),x(2)x(6),X3(0),X3(1),X4(0),X4(1),X1(0)X1(1),X1(2)X1(3),（d)另一个2点的DFT蝶形流图,2点DFT,2点DFT,x(1)x(5),x(3)x(7),X5(0),X5(1),X6(0),X6(1),X2(0)X2(1),X2(2)X2(3),同理：,(3)将N/4（2点）DFT再分解成2个1点的DFT(a)求2个一点的DFT,最后剩下两点DFT,它可分解成两个一点DFT，但一点DFT就等于输入信号本身，所以两点DFT可用一个蝶形结表示。取x(0)、x(4)为例。,(b)2个1点的DFT蝶形流图,1点DFT,x(0),1点DFT,x(4),X3(0)X3(1),进一步简化为蝶形流图：,X3(0)X3(1),x(0),x(4),(4)一个完整N=8的按时间抽取FFT的运算流图,x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7),X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7),m=0,m=1,m=2,四、FFT算法中一些概念（1）“级”概念,将N点DFT先分成两个N/2点DFT，再是四个N/4点DFT直至N/2个两点DFT.每分一次称为“一”级运算。因为N=2M所以N点DFT可分成M级如上图所示依次m=0,m=1.M-1共M级,（2）“组”概念,每一级都有N/2个蝶形单元，例如：N=8,则每级都有4个蝶形单元。每一级的N/2个蝶形单元可以分成若干组，每一组具有相同的结构，相同的因子分布，第m级的组数为：,例：N=8=23，分3级。m=0级,分成四组,每组系数为m=1级,分成二组,每组系数为m=2级,分成一组,每组系数为,(3)因子的分布,结论：每由后向前（m由M-1-0级）推进一级，则此系数为后级系数中偶数序号的那一半。,（4）按时间抽取法,2点DFT,2点DFT,2点DFT,2点DFT,2点DFT,2点DFT,2点DFT,2点DFT,两个2点DFT,两个2点DFT,两个2点DFT,两个2点DFT,两个4点DFT,两个4点DFT,两个N/2点DFT,X1(k),.,X2(k),X(k),由于每一步分解都是基于在每级按输入时间序列的次序是属于偶数还是奇数来分解为两个更短的序列，所以称为“按时间抽取法”.,x(n),五、按时间抽取的FFT算法与直接计算DFT运算量的比较,由前面介绍的按时间抽取的FFT运算流图可见：每级都由N/2个蝶形单元构成，因此每一级运算都需要N/2次复乘和N次复加（每个结加减各一次）。这样（N=2M)M级运算共需要：复乘次数：复加次数：可以得出如下结论：按时间抽取法所需的复乘数和复加数都是与成正比。而直接计算DFT时所需的复乘数与复加数则都是与N2成正比.(复乘数md=N2,复加数ad=N(N-1)N2),例子,看N=8点和N=1024点时直接计算DFT与用基2-按时间抽取法FFT的运算量。,看出：当N较大时，按时间抽取法将比直接法快一、二个数量级之多。,作业,N=16点的FFT基2-按时间抽取流程图。,六、按时间抽取FFT算法的特点,根据DIT基2-FFT算法原理，能得出任何N=2m点的FFT信号流图，并进而得出FFT计算程序流程图。最后总结出按时间抽取法解过程的规律。1.原位运算（in-place)2.码位倒读规则,1.原位运算（in-place),原位运算的结构，可以节省存储单元，降低设备成本。定义：当数据输入到存储器以后，每一组运算的结果，仍然存放在这同一组存储器中直到最后输出。,x(0),x(4),X3(0)X3(1),例子,例：N=8FFT运算,输入:,x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7),A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7),A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7),A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7),A(0)=x(0)A(1)=x(1)A(2)=x(2)A(3)=x(3)A(4)=x(4)A(5)=x(5)A(6)=x(6)A(7)=x(7),R1,R1,R1,R1,R1,R2,R1,R1,R2,R2,R3,R4,看出：用原位运算结构运算后，A(0)A(7)正好顺序存放X(0)X(7),可以直接顺序输出。,2.码位倒读规则,我们从输入序列的序号及整序规律得到码位倒读规则。由N=8蝶形图看出：原位计算时，FFT输出的X(k)的次序正好是顺序排列的，即X(0)X(7),但输入x(n)都不能按自然顺序存入到存储单元中，而是按x(0),x(4),x(2),x(6).的顺序存入存储单元即为乱序输入，顺序输出。这种顺序看起来相当杂乱，然而它是有规律的。即码位倒读规则。,例子,以N=8为例：,01234567,000001010011100101110111,自然顺序,二进制码表示,码位倒读,码位倒置顺序,000100010110001101011111,04261537,看出：码位倒读后的顺序刚好是数据送入计算机内的顺序。,整序重排子程序,具体执行时，只须将1与4对调送入，3与6对调送入，而0，2，5，7不变，仅需要一个中间存储单元。,n01234567,n04261537,在实际运算时，先按自然顺序将输入序列存入存储单元，再通过变址运算将自然顺序变换成按时间抽取的FFT算法要求的顺序。变址的过程可以用程序安排加以实现-称为“整序”或“重排”（采用码位倒读）且注意：(1)当n=n时，数据不必调换；(2)当nn时，必须将原来存放数据x(n)送入暂存器R，再将x(n)送入x(n),R中内容送x(n).进行数据对调。(3)为了避免再次考虑前面已调换过的数据，保证调换只进行一次，否则又变回原状。nn时，调换。,作业,编写N=128点的基2-按时间抽取的FFT算法。要求用C语言编写，并将输入数据放在文件inputdata.dat中，输出数据放在outputdata.dat文件中。,七、按时间抽取的FFT算法的若干变体1.思路,对于任何流图，只要保持各节点所连续的支路及其传输系数不变，则不论节点位置怎么排列所得流图总是等效的，最后所得结果都是x(n)的离散付里叶变换的正确结果。只是数据的提取和存放的次序不同而已。,(2)输入是自然顺序而输出是乱序,将原先中与x(4)水平相邻的所有节点跟x(1)水平相邻的所有节点位置对调；将原先中与x(6)水平相邻的所有节点跟x(3)水平相邻的所有节点位置对调，其余诸节点保持不变，则可得：,x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7),X(0)X(4)X(2)X(6)X(1)X(3)X(5)X(7),它与输入是乱序，输出顺序比较，看出：相同点：运算量一样；不同点：第一是数据存入方式不同；第二是取用系数的顺序不同。,(2)输入和输出都是自然顺序,对输入自然顺序，输出乱序的第二级，第三级节点作调整，可得输入输出都是顺序，无需数据重排：,x(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),（1）它失掉了“原位运算”的性质。（2）为了变换N点数据，至少需要2N个复数单元。在内存比较紧张时，而对输入数据整序并不困难时一般不用。为了争取速度，才采取这种变体。,有一个FIR滤波器处理机，用FFT算法分段过滤信号，每段运算N=1024点，运算一遍需要0.2s,处理机具有两组1024个单元的复数存储器可供交替使用，一组供运算时，另一组可用来存储实时输入的信号序列。用该处理机并配以A/D变换器作连续信号的实时过滤，问：(1)抽样频率最高可达多少?(2)若作两路信号同时过滤时，抽样频率最高是多少?(3)在这两种情况下最高可以处理多高频率的信号?,5、Chirp-z变换,采用FFT可以算出全部N点DFT值，即z变换X（z）在z平面单位圆上的等间隔取样值，但要求N为复合数。问题的提出：不需要计算整个单位圆上z变换的取样，如对于窄带信号，只需要对信号所在的一段频带进行分析，这时,希望频谱的采样集中在这一频带内，以获得较高的分辨率，而频带以外的部分可不考虑。对其它围线上的z变换取样感兴趣，例如语音信号处理中，需要知道z变换的极点所在频率，如极点位置离单位圆较远，则其单位圆上的频谱就很平滑，如果采样不是沿单位圆而是沿一条接近这些极点的弧线进行，则在极点所在频率上的将出现明显的尖峰，由此可较准确地测定极点频率。要求能有效地计算当N是素数时序列的DFT。,算法原理：,螺旋线采样是一种适合于这种需要的变换，且可以采用FFT来快速计算，这种变换也称作Chirp-z变换。已知x（n），0nN-1令zk=AW-k，k=0，M-1，M：采样点数，A、W：任意复数其中：A0表示起始取样点的半径长度，通常A010表示起始取样点z0的相角0表两相邻点之间的等分角W0螺旋线的伸展率，W01则线外伸，W01则线内缩（反时针），W0=1则表示半径为A0的一段圆弧，若A0=1，这段圆弧则是单位圆的一部分。,图螺旋线采样,计算z变换在采样点zk的值k=0,1,M-1显然，按照以上公式计算出全部M点采样值需要NM次复乘和（N-1）M次复加，当N及M较大时，计算量迅速增加，以上运算可转换为卷积形式，从而可采用FFT进行，这样可大大提高计算速度。利用zk的表示式代入,nk可以用以下表示式来替换,则,定义：,则,上式说明，如对信号x（n）先进行一次加权处理，加权系数为，然后通过一个单位脉冲响应为h（n）的线性系统，最后，对该系统的前M点输出再作一次的加权，就可得到全部M点螺旋线采样值。系统的单位脉冲响应与频率随时间成线性增加的线性调频信号相似，因此称为Chirp-z变换。,x,x,x(n),g(n),X(zk),算法实现：由于输入信号g（n）是有限长的，长为N，但序列是无限长的，而计算0M-1点卷积g（k）*h（k）所需要的h（n）是取值在n=-（N-1）M-1那一部分的值，因此，可认为h（n）是一个有限长序列，长为L=N+M-1。所以，Chirp-z变换为两个有限长序列的线性卷积g（k）*h（k），可用圆圈卷积通过FFT来实现。h（n）的主值序列可由h（n）作周期延拓后取0nL-1部分值获得，将与g（n）作圆周卷积后，其输出的前M个值就是Chirp-z变换的M个值。这个圆周卷积的过程可在频域上通过FFT实现。,Chirp-z变换的计算步骤：,(4)G（k）=FFTg（n）,L点（5）Y（k）=G（k）H（k）,L点（6）y（n）=IFFTY（k）,L点（7）,0kM-1,(2)用FFT求的傅里叶变换:H(k)=FFT,L点,(3)对x（n）加权并补零,(1)求h（n）的主值序列,利用FFT计算Chirp-z变换,计计算量估算：乘,乘法数估计（1）（2）两步可以事先计算，不必实时计算。（3）（7）两步两次加权共计N+M次复乘,形成Y（k）需L次复乘，一个FFT与一个IFFT需Llog2L次乘，所以总乘法数：L+N+M+Llog2L，直接计算乘法数，NMN及M较大时，用FFT实现Chirp-Z变换，速度上有很大的改进。,Chirp-z变换的特点：,1）输入序列的长度N与输出序列的长度M不需要相等；2）N及M不必是高度复合数，二者均可为素数；3）相邻采样点zk之间的角间隔0是任意的，即频率分辨率是任意的；4）围线是任意的，不必是Z平面上的圆；5）起始点z0可任意选定，即可从任意频率上开始对输入数据进行窄带高分辨率分析；6）若A=1,M=N,可用Chirp-z变换计算DFT（即使N为素数）。,2.4FFT应用中的几个问题,1)IDFT的运算方法,IDFT：,DFT：,以上所讨论的FFT算法可用于IDFT运算简称为IFFT比较IDFT的定义式：,IDFT与DFT的差别：1）把DFT中的每一个系数改为，2）再乘以常数1/N，则以上所讨论的时间抽取或频率抽取的FFT运算均可直接用于IDFT运算，当然，蝶形中的系数应改为。,b）第二种方法，完全不需要改动FFT程序，而是直接利用它作IFFT。考虑到故IFFT计算分三步：将X（k）取共轭（虚部乘以-1）对直接作FFT对FFT的结果取共轭并乘以1/N，得x（n）。,2.4FFT应用中的几个问题,2）实数序列的FFT以上讨论的FFT算法都是复数运算,包括序列x(n)也认为是复数,但大多数场合,信号是实数序列,任何实数都可看成虚部为零的复数,例如,求某实信号x(n)的复谱,可认为是将实信号加上数值为零的虚部变成复信号(x(n)+j0),再用FFT求其离散傅里叶变换。这种作法很不经济,因为把实序列变成复序列,存储器要增加一倍,且计算机运行时,即使虚部为零,也要进行涉及虚部的运算,浪费了运算量。合理的解决方法是利用复数据FFT对实数据进行有效计算,下面介绍两种方法。,（1）用一个N点FFT同时计算两个N点实序列的DFT设x(n)、y(n)是彼此独立的两个N点实序列,且X(k)=DFTx(n)，Y(k)=DFTy(n)则X(k)、Y(k)可通过一次FFT运算同时获得。首先将x(n)、y(n)分别当作一复序列的实部及虚部,令g(n)=x(n)+jy(n),利用离散傅里叶变换的共轭对称性,通过FFT运算可获得g(n)的DFT值,通过g(n)的FFT运算结果G(k),由上式也可得到X(k)的值。,作一次点复序列的FFT，再通过加、减法运算就可以将X(k)与Y(k)分离出来。显然，这将使运算效率提高一倍。,（2）用一个N点的FFT运算获得一个2N点实序列的DFT设x(n)是2N点的实序列,现人为地将x(n)分为偶数组x1(n)和奇数组x2(n)x1(n)=x(2n)n=0,1,N-1x2(n)=x(2n+1)n=0,1,N-1然后将x1(n)及x2(n)组成一个复序列：y(n)=x1(n)+jx2(n),通过N点FFT运算可得到：Y(k)=X1(k)+jX2(k)，N点根据前面的讨论，得到,为求2N点x(n)所对应X(k)，需求出X(k)与X1(k)、X2(k)的关系：,而,1）由x1(n)及x2(n)组成复序列，经FFT运算求得Y(k)，2）利用共轭对称性求出X1(k)、X2(k)，3）最后利用上式求出X（k）,达到用一个N点的FFT计算一个2N点的实序列的DFT的目的。,X(k)=X1(k)+W2NkX2(k),所以,3)线性卷积的FFT算法线性卷积是求离散系统响应的主要方法之一,许多重要应用都建立在这一理论基础上,如卷积滤波等。以前曾讨论了用圆周卷积计算线性卷积的方法归纳如下:将长为N2的序列x(n)延长到L,补L-N2个零，将长为N1的序列h(n)延长到L,补L-N1个零，如果LN1+N2-1,则圆周卷积与线性卷积相等,此时,可用FFT计算线性卷积，方法如下:,a.计算X(k)=FFTx(n)b.求H(k)=FFTh(n)c.求Y(k)=H(k)X(k)k=0L-1d.求y(n)=IFFTY(k)n=0L-1可见，只要进行二次FFT,一次IFFT就可完成线性卷积计算。计算表明,L32时,上述计算线性卷积的方法比直接计算线卷积有明显的优越性,因此,也称上述循环卷积方法为快速卷积法。,上述结论适用于x(n)、h(n)两序列长度比较接近或相等的情况,如果x(n)、h(n)长度相差较多,例如,h(n)为某滤波器的单位脉冲响应,长度有限,用来处理一个很长的输入信号x(n),或者处理一个连续不断的信号，按上述方法,h(n)要补许多零再进行计算,计算量有很大的浪费，或者根本不能实现。为了保持快速卷积法的优越性,可将x(n)分为许多段,每段的长度与h(n)接近,处理方法有两种：,(1)重叠相加法由分段卷积的各段相加构成总的卷积输出,h(n),x(n),则输入序列可表为：,于是输出可分解为：,其中,假定xi(n)表示x（n）序列的第i段：,1）先对