按时间抽选的基2-FFT算法.ppt

《按时间抽选的基2-FFT算法.ppt》由会员分享，可在线阅读，更多相关《按时间抽选的基2-FFT算法.ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三节第三节 按时间抽选的基按时间抽选的基2-FFT算法算法1、算法原理、算法原理 设输入序列长度为设输入序列长度为N=2M(M为正整数，将该序列为正整数，将该序列按时间顺序的奇偶分解按时间顺序的奇偶分解为越来越短的子序列，称为为越来越短的子序列，称为基基2按时间抽取的按时间抽取的FFT算法。也称为算法。也称为Coolkey-Tukey算法。算法。其中其中基基2表示：表示：N=2M，M为整数为整数.若不满足这个若不满足这个条件，可以人为地加上若干零值（条件，可以人为地加上若干零值（加零补长加零补长）使其）使其达到达到 N=2M。先将先将x(n)按按n的奇偶分为两组，作变量置换的奇偶分为两组，作

2、变量置换:当当n=偶数时，令偶数时，令n=2r;当当n=奇数时，令奇数时，令n=2r+1;分组，变量置换分组，变量置换2、算法步骤、算法步骤得到：得到：带入带入DFT中中所以所以 由于由于?X1(k)、X2(k)只有只有N/2个点，以个点，以N/2为周期；而为周期；而X(k)却有却有N个点，以个点，以N为周期。要用为周期。要用X1(k)、X2(k)表达全部的表达全部的X(k)值，还必须利用值，还必须利用WN系数的系数的周期特性周期特性。后半部分后半部分前半部分前半部分又考虑到又考虑到 的对称性：的对称性：有：有：后半部分后半部分前半部分前半部分蝶形运算流图符号蝶形运算流图符号说明：说明：(1)

3、左边两路为输入左边两路为输入(2)右边两路为输出右边两路为输出(3)中间以一个小圆表示加、中间以一个小圆表示加、减运算（右上路为相加减运算（右上路为相加 输出、右下路为相减输输出、右下路为相减输 出出)1个蝶形运算需要个蝶形运算需要1次复乘，次复乘，2次复加次复加复数乘法复数乘法复数加法复数加法一个一个N 点点DFTN 2N(N1)一个一个N/2点点DFT(N/2)2N/2(N/2 1)两个两个N/2点点DFTN 2/2N(N/2 1)一个蝶形一个蝶形12N/2个蝶形个蝶形N/2N总计总计N2/2+N/2 N2/2N(N/2-1)+N N2/2运算量减少了近一半运算量减少了近一半 分解后的运算

4、量：分解后的运算量：先将先将N=8点的点的DFT分解成分解成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)给出给出例子：求例子：求 N=23=8点点FFT变换变换 按按N=8N/2=4，做做4点的点的DFT：N=8点的直接点的直接DFT的计算量为：的计算量为：复乘：复乘：N2次次=64次次 复加：复加：N(N-1)次次=87=56次次 此外，还有此外，还有4个蝶形结，每个蝶形结

5、需要个蝶形结，每个蝶形结需要1次复乘，次复乘，2次复加。次复加。一共是：复乘一共是：复乘4次，复加次，复加8次。次。得到得到X1(k)和和X2(k)需要：需要：复乘：复乘：(N/2)2+(N/2)2次次=32次次 复加：复加：N/2(N/2-1)+N/2(N/2-1)=12+12=24次次用分解的方法得到用分解的方法得到X(k)需要：需要：复乘：复乘：32+4=36次次 复加：复加：24+8=32次次N点点DFT的一次时域抽取分解图的一次时域抽取分解图(N=8)4点点DFT4点点DFTx(0)x(2)x(4)x(6)x(1)x(3)x(5)x(7)X1(0)X1(1)X1(2)X1(3)X2(

6、0)X2(1)X2(2)X2(3)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)因为因为4点点DFT还是比较麻烦，所以再继续分解。还是比较麻烦，所以再继续分解。若将若将N/2(4点点)子序列按奇子序列按奇/偶分解成两个偶分解成两个N/4点点(2点点)子子序列。即对将序列。即对将x1(r)和和x2(r)分解成奇、偶两个分解成奇、偶两个N/4点点(2点点)点的子序列。点的子序列。那么，那么，X1(k)又可表示为又可表示为 X2(k)也可以进行相同的分解：也可以进行相同的分解：注意：通常我们会把注意：通常我们会把 写成写成 。N点点DFT的第二次时域抽取分解图的第二次时域抽取分解图

7、(N=8)2点点DFT2点点DFT2点点DFT2点点DFTx(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)X3(0)X3(1)X4(0)X4(1)X5(0)X5(1)X6(0)X6(1)X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)4点点DFT4点点DFTx(0)x(2)x(4)x(6)x(1)x(3)x(5)x(7)X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)88X3(0)X3(1

8、)x(0)=x3(0)x(4)=x3(1)N点点DITFFT运算流图运算流图(N=8)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)3、DITFFT算法与直接计算算法与直接计算DFT运算量的比较运算量的比较1)、N=2M的的DFT运算可分成运算可分成M级，每一级有级，每一级有N/2个蝶形个蝶形 ，每个蝶形有一次复乘两次复加。，每个蝶形有一次复乘两次复加。2)、所以、所以M级共有级共有 次复乘和次复乘和 次复加。次复加。3)、若直接计算、若直接计算DFT，需需N2次复乘和次复乘和N(N-1)次复加。次复加。显然，当

9、显然，当N较大时，有：较大时，有：例如，例如，N=210=1024时时FFT算法与直接计算算法与直接计算DFT所需乘法次数的比较曲线所需乘法次数的比较曲线4、DITFFT的运算规律及编程思想的运算规律及编程思想 FFT的每级（列）计算都是由的每级（列）计算都是由N个复数数据（输入）两个复数数据（输入）两两构成一个蝶型（共两构成一个蝶型（共N/2个蝶形）运算而得到另外个蝶形）运算而得到另外N个复数个复数数据（输出）。数据（输出）。当数据输入到存储器以后，每一组运算的结果，当数据输入到存储器以后，每一组运算的结果，仍然存仍然存放在这同一组存储器中放在这同一组存储器中直到最后输出。直到最后输出。例：

10、将例：将x(0)放在单元放在单元A(0)中，将中，将x(4)放在单元放在单元A(1)中，中，W80 放在一个暂存器中。放在一个暂存器中。将将x(0)+W80 x(4)送回送回A(0)单元单元将将x(0)-W80 x(4)送回送回A(1)单元单元X3(0)X3(1)x(0)x(4)1）原位运算原位运算 (亦称同址计算亦称同址计算)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)回顾：回顾：N点点DITFFT运算流图运算流图(N=8)如上所述，如上所述，N点点DITFFT运算流图中，每级都有运算流图中，每级都有N/2个

11、蝶形。每个蝶形都要乘以因子个蝶形。每个蝶形都要乘以因子WNP，称其为称其为旋旋转因子转因子，p称为旋转因子的指数。称为旋转因子的指数。2)旋转因子的变化规律旋转因子的变化规律 观察观察FFT运算流图发现，第运算流图发现，第L级共有级共有2L-1个不同的个不同的旋转因子。旋转因子。N=23=8时的各级旋转因子表示如下：时的各级旋转因子表示如下：L=1时，时，WNp=WN/4J，N/4=21=2L，J=0L=2时，时，WNp=WN/2J，N/2=22=2L，J=0，1L=3时，时，WNp=WNJ，N =23=2L，J=0，1，2，3对对N=2M的一般情况，第的一般情况，第L级的旋转因子为：级的旋转

12、因子为：设序列设序列x(n)经时域抽选经时域抽选(倒序倒序)后，存入数组后，存入数组X中。中。如果蝶形运算的两个输入数据相距如果蝶形运算的两个输入数据相距B个点，应用原位个点，应用原位计算，则蝶形运算可表示成如下形式：计算，则蝶形运算可表示成如下形式：下标下标L表示第表示第L级运算，级运算，XL(J)则表示第则表示第L级运算级运算后数组元素后数组元素X(J)的值。的值。3)编程思想及流程图编程思想及流程图开始开始送入送入x(n)和和N=2M调整输入调整输入x(n)的顺序的顺序for(L=1;L=M;L+)B=2L-1for(J=0;J=B-1;J+)p=J2M-Lfor(k=J;k=N-1;k

13、=k+2L)输出结果输出结果结束结束4）码位倒序码位倒序 由由N=8蝶形图看出：原位计算时，蝶形图看出：原位计算时，FFT输出的输出的X(k)的次序正好是顺序排列的，即的次序正好是顺序排列的，即X(0)X(7),但输但输入入x(n)都不能按自然顺序存入到存储单元中，而是都不能按自然顺序存入到存储单元中，而是按按x(0),x(4),x(2),x(6),x(1),x(5),x(3),x(7)的顺序存入的顺序存入存储单元存储单元，即为乱序输入，顺序输出。即为乱序输入，顺序输出。这种顺序看起来相当杂乱，然而它是这种顺序看起来相当杂乱，然而它是有规律有规律的。的。即即码位倒读规则码位倒读规则。自然顺序自

14、然顺序n二进制码表示二进制码表示码位倒读码位倒读码位倒置顺序码位倒置顺序n以以N=8为例：为例：0123456700000101001110010111011100010001011000110101111104261537看出：看出：码位倒读后码位倒读后的顺序刚好是数据送入计算机内的顺序。的顺序刚好是数据送入计算机内的顺序。倒序规律倒序规律 对于数对于数对于数对于数N N，在其二进制最高位加在其二进制最高位加在其二进制最高位加在其二进制最高位加1 1，等于加，等于加，等于加，等于加N/2N/2。若已知某个反序号为若已知某个反序号为若已知某个反序号为若已知某个反序号为J J，为求下一个反序号，

15、可先为求下一个反序号，可先为求下一个反序号，可先为求下一个反序号，可先判判判判J J的最高位：的最高位：的最高位：的最高位：1)1)若为若为若为若为0 0，则把该位变成，则把该位变成，则把该位变成，则把该位变成1 1（即加（即加（即加（即加N/2N/2）就得到下就得到下就得到下就得到下 一个反序号，一个反序号，一个反序号，一个反序号，2)2)若为若为若为若为1 1，则需判断次高位：，则需判断次高位：，则需判断次高位：，则需判断次高位：若次高位为若次高位为若次高位为若次高位为0 0，则把最高位变，则把最高位变，则把最高位变，则把最高位变0 0（相当减去（相当减去（相当减去（相当减去 N/2 N/2）后，再把次高位变后，再把次高位变后，再把次高位变后，再把次高位变1 1（即加（即加（即加（即加N/4N/4）。）。）。）。若次高位为若次高位为若次高位为若次高位为1 1，则需判断次次高位，则需判断次次高位，则需判断次次高位，则需判断次次高位分析：分析：分析：分析：倒倒序序排排列列算算法法的的流流程程图图正序序列已在数组正序序列已在数组A 中，输中，输 入入 NLH=N/2 ,J=LH ,N1=N-2J=J-kk=k/2 k=LHJkJ=J+k T=A(I)A(I)=A(J)A(J)=Tfor(i=1;i=N1;i+)i JN NY YY YN N