基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，

2、用 stem（X）显示频谱图形。 三、主要仪器设备 用 MATLAB。 四、操作方法和实验步骤 （参见 “二、实验内容和步骤 ”） 五、实验数据记录和处理 5.1基 4-FFT算法思路、流图结构简述如下 5.1.1. 算法思路： 在时域上按 n 的特点对序列 x（n）进行不断的以 4 为基数的分组以及位序调整，进而通过 逐级的蝶形复合处理，间接地完成高点数 DFT的计算，由此达到降低运算量以及节省存储空 间的目的。 令序列 x(n)的N点DFT结果为 X(k)，且有，按 的结果对序列 x(n)分组如下： 则有： 经过 5.1.2 蝶形图如下： 对于 N/4 个点继续进行分组和蝶形复合处理， 由

3、原序列 x(n)出发，完成位序调整后， m 级蝶形复合便可求得序列 X(k)。总体过程如下图： 2 / 6. -1- j j -1j -j 5.2 16点基 4-FFT算法的流图绘出如下(后面省略了系数 -1，-j，j，具体系数对应项见上一蝶 形图) 5.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 ); a

4、xis(0 17 0 10); figure(2) stem(n,X, filled ); title( Output Sequence ); axis(0 17 -20 60); figure(3) 3 / 6. stem(n,X1, filled ); title(Output FFT Sequence axis(0 17 -20 60); function X=fft4_16(x) X=zeros(1,16); N=16; ); %初始化输出的频谱序列 W4=dftmtx(4); %求出蝶形运算的系数矩阵 x0=x(1);x(5);x(9);x(13); % 先对原序列进行位序调整 x1

5、=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 %第二级蝶形运算 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); end 5.4 用自己的学号构成的输入序列为（列出数值，插入图形） x

6、1=1,9,9,5,0,3,2,5,3,0,1,0,4,7,2,3; 4 / 6. W=exp(-1j*2*pi/N); 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 六、实验结果与分析 5 / 6. 1. 基 4-FFT计算结果与 matlab 自带 fft 函数计算结果对比 以下是 matlab 自带 fft 函数的计算结果 由上述序列和图像比较可以看到， matlab 自带的函数 fft 所得结果与我的基