基4-FFT算法编程

1、实验报告课程名称： 数字信号处理 指导老师： 刘英 成绩：_实验名称： 基4-FFT算法编程 实验类型：_设计_ 同组学生姓名：_一、实验目的和要求FFT是快速计算DFT的一类算法的总称。通过序列分解，用短序列的DFT代替长序列的DFT，使得计算量大大下降。基4-FFT是混合基FFT的一个特例。通过编写基4-FFT算法程序，加深对FFT思路、算法结构的理解。二、实验内容和步骤编写16点基4-FFT算法的MATLAB程序（studentname.m文件）。产生16点输入序列x，出生年月日（8位）+自己学号后八位产生。算出16点频谱序列X，用stem(X)显示频谱图形。三、主要仪器设备用MATLA

2、B。四、操作方法和实验步骤（参见“二、实验内容和步骤”）五、实验数据记录和处理5.1基4-FFT算法思路、流图结构简述如下5.1.1. 算法思路：在时域上按n的特点对序列x(n)进行不断的以4为基数的分组以及位序调整，进而通过逐级的蝶形复合处理，间接地完成高点数DFT的计算，由此达到降低运算量以及节省存储空间的目的。令序列x(n)的N点DFT结果为X（k），且有N=4m，按(n)4的结果对序列x(n)分组如下：x0n=x4n X0k=DFT4m-1x0(n)x1n=x(4n+1)X1k=DFT4m-1x1(n)x2n=x(4n+2)X2k=DFT4m-1x2(n)x3n=x(4n+3) X3k

3、=DFT4m-1x3(n)0nN4-10kN-1=4m-1则有：Xk=X0k+WNkX1k+WN2kX2k+WN3kX3kXk+4m-1=X0k-jWNkX1k-WN2kX2k+jWN3kX3kXk+24m-1=X0k-WNkX1k+WN2kX2k-WN3kX3kXk+34m-1=X0k+jWNkX1k-WN2kX2k-jWN3kX3k5.1.2蝶形图如下： 对于N/4个点继续进行分组和蝶形复合处理，由原序列x(n)出发，完成位序调整后，经过m级蝶形复合便可求得序列X(k)。总体过程如下图：5.2 16点基4-FFT算法的流图绘出如下（后面省略了系数-1，-j，j，具体系数对应项见上一蝶形图）

4、-j-1j-1-1j-1-j5.3 16点基4-FFT算法的MATLAB程序（studentname.m）列出如下x=1,9,9,5,0,3,2,5,3,0,1,0,4,7,2,3;X=fft4_16(x);X1=fft(x);n=1:1:16;figure(1)stem(n,x,filled);title(Input Sequence);axis(0 17 0 10);figure(2)stem(n,X,filled);title(Output Sequence);axis(0 17 -20 60);figure(3)stem(n,X1,filled);title(Output FFT Se

5、quence);axis(0 17 -20 60);function X=fft4_16(x)X=zeros(1,16); %初始化输出的频谱序列N=16; W=exp(-1j*2*pi/N); W4=dftmtx(4); %求出蝶形运算的系数矩阵 x0=x(1);x(5);x(9);x(13); %先对原序列进行位序调整x1=x(2);x(6);x(10);x(14);x2=x(3);x(7);x(11);x(15);x3=x(4);x(8);x(12);x(16); X0=W4*x0; %第一级蝶形运算X1=W4*x1;X2=W4*x2;X3=W4*x3; for k=0:3 %第二级蝶形

6、运算 t=W4*X0(k+1);(Wk)*X1(k+1);(W(2*k)*X2(k+1);(W(3*k)*X3(k+1); X(k+1)=t(1); X(k+4+1)=t(2); X(k+2*4+1)=t(3); X(k+3*4+1)=t(4);end5.4用自己的学号构成的输入序列为（列出数值，插入图形）x1=1,9,9,5,0,3,2,5,3,0,1,0,4,7,2,3;5.5对应的输出频谱序列为（列出数值，插入图形）X = 54.0000 + 0.0000i 13.5682 - 6.7903i 1.4142 - 3.1716i -13.2930 -19.4368i -6.0000 - 6.0000i -2.0207 - 0.1231i -1.4142 + 8.8284i -6.2545 - 3.4765i -10.0000 - 0.0000i -6.2545 + 3.4765i -1.4142 - 8.8284i -2.0207 + 0.1231i -6.0000 + 6.0000i -13.2930 +19.4368i 1.4142 + 3.1716i 13.5682 + 6.7903i六、实验结果与分析1. 基4-FFT计算结果与matlab自带fft函数计算结果对比以下是matlab自带fft函数的计算结果由上述序列和图像比较可以看到，m