基4-FFT算法编程

实验报告课程名称：数字信号处理指导老师：刘英成绩：__________________实验名称：基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)显示频谱图形。三、主要仪器设备用MATLAB。四、操作方法和实验步骤（参见“二、实验内容和步骤”）五、实验数据记录和处理5.1基4-FFT算法思路、流图结构简述如下5.1.1.算法思路：在时域上按n的特点对序列x(n)进行不断的以4为基数的分组以及位序调整，进而通过逐级的蝶形复合处理，间接地完成高点数DFT的计算，由此达到降低运算量以及节省存储空间的目的。2令序列x(n)的N点DFT结果为X（k），且有𝑁=4𝑚，按((𝑛))4的结果对序列x(n)分组如下：𝑥(0)(𝑛)=𝑥(4𝑛)𝑋(0)(𝑘)=𝐷𝐹𝑇4𝑚−1{𝑥(0)(𝑛)}𝑥(1)(𝑛)=𝑥(4𝑛+1)𝑋(1)(𝑘)=𝐷𝐹𝑇4𝑚−1{𝑥(1)(𝑛)}𝑥(2)(𝑛)=𝑥(4𝑛+2)𝑋(2)(𝑘)=𝐷𝐹𝑇4𝑚−1{𝑥(2)(𝑛)}𝑥(3)(𝑛)=𝑥(4𝑛+3)𝑋(3)(𝑘)=𝐷𝐹𝑇4𝑚−1{𝑥(3)(𝑛)}0≤𝑛≤𝑁4−10≤𝑘≤𝑁−1=4𝑚−1则有：𝑋(𝑘)=𝑋(0)(𝑘)+𝑊𝑁𝑘𝑋(1)(𝑘)+𝑊𝑁2𝑘𝑋(2)(𝑘)+𝑊𝑁3𝑘𝑋(3)(𝑘)𝑋(𝑘+4𝑚−1)=𝑋(0)(𝑘)−𝑗𝑊𝑁𝑘𝑋(1)(𝑘)−𝑊𝑁2𝑘𝑋(2)(𝑘)+𝑗𝑊𝑁3𝑘𝑋(3)(𝑘)𝑋(𝑘+2×4𝑚−1)=𝑋(0)(𝑘)−𝑊𝑁𝑘𝑋(1)(𝑘)+𝑊𝑁2𝑘𝑋(2)(𝑘)−𝑊𝑁3𝑘𝑋(3)(𝑘)𝑋(𝑘+3×4𝑚−1)=𝑋(0)(𝑘)+𝑗𝑊𝑁𝑘𝑋(1)(𝑘)−𝑊𝑁2𝑘𝑋(2)(𝑘)−𝑗𝑊𝑁3𝑘𝑋(3)(𝑘)5.1.2蝶形图如下：对于N/4个点继续进行分组和蝶形复合处理，由原序列x(n)出发，完成位序调整后，经过m级蝶形复合便可求得序列X(k)。总体过程如下图：位序调整第1级蝶形复合第2级蝶形复合第l级蝶形复合第m级蝶形复合......x(n)x0(k)x1(k)x2(k)Xl-1(k)xl(k)Xm-1(k)Xm(k)35.216点基4-FFT算法的流图绘出如下（后面省略了系数-1，-j，j，具体系数对应项见上一蝶形图）5.316点基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('InputSequence');axis([017010]);figure(2)stem(n,X,'filled');title('OutputSequence');axis([017-2060]);figure(3)stem(n,X1,'filled');title('OutputFFTSequence');axis([017-2060]);-j-1-1j-j-1j-14function[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;fork=0:3%第二级蝶形运算t=W4*[X0(k+1);(W^k)*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];55.5对应的输出频谱序列为（列出数值，插入图形）X={54.0000+0.0000i13.5682-6.7903i1.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.4368i1.4142+3.1716i13.5682+6.7903i}六、实验结果与分析1.基4-FFT计算结果与matlab自带fft函数计算结果对比以下是matlab自带fft函数的计算结果6由上述序列和图像比较可以看到，matlab自带的函数fft所得结果与我的基于4-FFT算法和代码所得结果是一直的，说明我的基于4-FFT算法和代码是正确的，此外可以看出，基于4与基于2（matlab）的FFT算法的运算结果是一致，即其本质是一致的。