按时间抽取的基2FFT算法分析及MATLAB实现

1、按时间抽取的基2FFT算法分析及MATLA改现按时间抽取的基2FFT算法分析及MATLA现、DIT-FFT算法的基本原理基2FFT算法的基本思想是把原始的 N点序列依 次分解成一系列短序列，充分利用旋转因子的周 期性和对称性，分别求出这些短序列对应的DFT, 再进行适当的组合，得到原 N点序列的DFT最 终达到减少运算次数，提高运算速度的目的。按时间抽取的基2FFT算法，先是将N点输入序 列x(n)在时域按奇偶次序分解成2个N/2点序 列x1(n)和x2(n),再分别进行DFT运算，求出 与之对应的X1(k)和X2(k),然后利用图1所示 的运算流程进行蝶形运算，得到原N点序列的DFT只要N是

2、2的整数次骞，这种分解就可一 直进行下去，直到其DFT就是本身的1点时域序 列。为俅*伏)=占十必治X2 3X (n+ N= * L w： x)图1 DIT-FFT蝶形运算流图、DIT-FFT算法的运算规律及编程思想1.原位计算对N=2M点的FFT共进行M级运算，每级由N/2 个蝶形运算组成。在同一级中，每个蝶的输入数 据只对本蝶有用，且输出节点与输入节点在同一 水平线上，这就意味着每算完一个蝶后，所得数 据可立即存入原输入数据所占用的数组元素 （存 储单元），经过M级运算后，原来存放输入序列 数据的N个存储单元中可依次存放 X（k）的N个 值，这种原位（址）计算的方法可节省大量内存。2.旋转

3、因子的变化规律N点DITFFT运算流图中，每个蝶形都要乘以旋转因子wNp, p称为旋转因子的指数。例如N= 8 =23时各级的旋转因子：第一级：L=1,有1个旋转因子：wNP=wN,4=w2jlJ=0第二级：L=2,有2个旋转因子：wNP=wN,2 = w；J=0,1第三级：L=3,有4个旋转因子：wNP=wN = w；lJ=0,1,2,3对于N= 2M的一般情况，第L级共有2L-1个不同的 旋转因子：wN=w2J=0,1,2,，2L-1 12l =2M 油L-M = N , 2L-M故：按照上面两式可以确定第 L级运算的旋转 因子%=%八吧=叫声一p二八2Mt j=ojzLT3、同一级中，同

4、一旋转因子对应蝶形数目第L级FFT运算中，同一旋转因子用在2M-L 个蝶形中；4、同一级中，蝶形运算使用相同旋转因子之间 相隔的“距离”第L级中，蝶距：DB；5、同一蝶形运算两输入数据的距离在输入倒序，输出原序的 FFT变换中，第L 级的每一个蝶形的2个输入数据相距：B=2l-1。6、码位颠倒输入序列x(n)经过M级时域奇、偶抽选后， 输出序列X(k)的顺序和输入序列的顺序关系为 倒位关系。将十进制顺序数用I表示，与之对应的二进制是 用旧表示，十进制倒序数用J表示，与之对应 的二进制是用JB表示。十进制顺序数I增加1, 相当于 旧最低位加1且逢2向高位进1,即相 当于JB最高位加1且逢2向低位

5、进1。JB的变 化规律反映到J的变化分为两种情况，若 JB的 最高位是0 (JN/2),则直接由加1 (J-J+N/2) 得到下一个倒序值，若 JB的最高位是1 (J三 N/2),则要先将最高位变 0 (J-J-N/2),再在 次高位加1 (J-J+N/4 ),但次高位加1时，同 样要判断0、1值，如果是0 (JN/4),则直接 加1 (J-J+N/4)，否则要先将次高位变0(J-J-N/4)再判断下一位，依次类推，直到完 成最高位加1 ,逢2向右进位的运算。I=J时不 需要交换，只对IJ时的情况进行数据交换即可， 数据倒序程序框图如如2。7、蝶形运算的规律序列经过时域抽选后，存入数组中，如果

6、蝶形运算的两个输入数据相距B个点，应用原位计算，蝶形运算可表示成如下形式：XL (J尸 XL-1(J)+ WNp X L-1J(J+B)X L-1 (J+B)/、 Xl (J) = Xl-i(J)-WnP - XL-1WNp(J+B)p=J X2M-L, J=0,1,2,2l-1- 18、DIT-FFT程序框图根据DIT-FFT原理和过程，DIT-FFT的完整程序框图如图2:(1)倒序：输入自然顺序序列x(n),根据倒序规 律，进行倒序处理； 循环层1:确定运算的级数，L=1M (N=2M)；确定一蝶形两输入数据距离B=2L-1循环层2:确定L级的B=2L-1个旋转因子；旋转 因子指数p=JM

7、M-L, J=0B-1;(4)循环层3:对于同一旋转因子，用于同一级2m-l 个蝶形运算中：k的取值从J到N-1,步长为2L(使用同一旋转因子的蝶形相距的距离)(5)完成一个蝶形运算。f开始图2数据倒序程序框图图3 DIT-FFT的完整程序框图三、程序源代码设计函数myDitFFT(xn)完成一个序列的DIT-FFT 运算:function y=myDitFFT(xn)M=nextpow2(length(xn);N=2AM;disp(调用fft函数运算的结果:),fftxn=fft(xn,N);if length(xn)Nxn=xn,zeros(1,N-length(xn); endfor m

8、=0:N/2-1;%旋转因子指数范围WN(m+1)=exp(-j*2*pi/Nm;%计算旋转因子end disp(输入到各存储单元的数据：),disp(xn);%数据倒序操作 J=0; %给倒序数赋初值 for I=0:N-1;%$序交换数据和算倒序数if I=K;J=J-K;K=K/2;endJ=J+K;enddisp(倒序后各存储单元的数据：)，disp(xn);%分级按序依次进行蝶形运算for L=1:M;%分级计算disp( 运算级次：),disp(L);B=2A(L-1);for R=0:B-1;%各级按序蝶算P=2A(M-L)*R;for K=R:2AL:N-2;%每序依次计算T=

9、xn(K+1)+xn(K+B+1)*WN(P+1);xn(K+B+1)=xn(K+1)-xn(K+B+1)*WN(P+1);xn(K+1)=T;endenddisp( 本级运算后各存储单元的数据：),disp(xn);end在主函数中调用 myDitFFT(xn)函数实现DIT-FFT并和直接DFT运算结果做对比：xn=0,1,2,3,4,5,6,7;myDitFFT(xn);调用fft函数运算的结果：1至7歹U28.0000 + 0.0000i-4.0000+ 4.0000i-4.0000+ 9.6569i-4.0000+ 1.6569i-4.0000+ 0.0000i-4.0000-4.0

10、000 - 4.0000i8列-4.0000 - 9.6569i调用myDitFFT(xn)函数运行的结果:输入到各存储单元的数据： TOC o 1-5 h z 01234567倒序后各存储单元的数据：04261537运算级次：1本级运算后各存储单元的数据：-1.6569i6-44-48-4运算级次:2本级运算后各存储单元的数据1 至7歹U12.0000+ 0.0000i-4.0000+ 0.0000i16.0000 + 0.0000i-4.0000 + 0.0000i8列-4.0000 - 4.0000i-4.0000 + 4.0000i-4.0000-4.0000i-4.0000+4.00

11、00i运算级次:3本级运算后各存储单元的数据1 至7歹U28.0000+ 0.0000i-4.0000+ 4.0000i-4.0000+ 0.0000i-4.0000 + 9.6569i-4.0000+ 1.6569i-4.0000- 1.6569i-4.0000 - 9.6569i经对比可知DIT-FFT与直接DFT勺运行结果完全 相同。四、总结经过验证可发现DIT-FFT较直接DFT运算有着明 显的优势，我们可以将这个函数运用在多个领域 以简化运算，例如计算离散时间序列的卷积或计 算IDFT时都可以应用到DIT-FFT算法，我感受 到数字信号处理中科学思想的魅力。由于对设计 思路的缺乏，我在设计程序时，在网络上查找了 很多有关DIT-FFT的资料，经过学习他人的解决 思路最后才整理出DIT-FFT的程序，在有些地方 我自己理解的还不是很透彻，比如在实现数据倒 序的程序我认为比较困难；当然即使自己想不到 能学习一下别人的思路也