实验1 基2-FFT算法实现
姓名：明眸皓齿王师傅
班级：******* 学号：**********
实验时间：第十周周三下午第二大节
一、实验目的
1.掌握基2-FFT的原理及具体实现方法。 2.编程实现基2-FFT算法。 3.深刻理解FFT算法的特点。 二、实验设备与环境
计算机，matlab软件环境。 三． 实验原理
FFT是EDF的一种快速算法，能使DFT的计算大大简化，运算时间缩短。FFT利用了WNnk的三个固有特性。即对称性，周期性和可约性，将长序列的DFT分解为短序列的DFT，合并了DFT运算中的某些项，从而减少了DFT的运算量。
FFT算法基本上可分为两大类，即按时间抽取法和按频率抽取法。 在实现FFT算法时，要重点考虑两个问题，注意数据的读取和存储：(1)输入输出的排序；（2）蝶形运算的实现。按时间抽取算法中输入反序输出顺序，按频率抽取算法中输入顺序输出反序；运算过程中的每一级都有N/2个蝶形运算构成，每一个蝶形运算单元中，两个节点变量运算后得到的结果为下一列相同位置的节点变量，而和其他节点变量无关，可以采用原位运算，节省存储单元。另外，蝶形运算中的复系数WNnk可以存储为能及时查阅的系数表，这样可以借阅运算量，但是需要N/2哥复数存储器。
MATLAB中提供了用于计算FFT的函数fft，可将实验中所得到的结果与利用MATLAB中fft函数计算的结果相比较，以此验证结果的正确性。 四.实验内容
1.编程实现序列长度为N=8的按时间抽取的基2-FFT算法。给定一个8点序列，采用编写的程序计算其DFT，并与MATLAB中fft函数计算的结果相比较，以验证结果的正确性。 代码：
x=[0 1 2 3 4 5 6 7]
m=3 %序列长度为2的3次方 N=8
xx=bin2dec(fliplr(dec2bin([1:N]-1,m)))+1; %求倒序列 y=x(xx)
for mm=1:m %对x做基2分解 Nz=2^mm u=1
WN=exp(-i*2*pi/Nz) for j=1:Nz/2 for k=j:Nz:N kk=k+Nz/2
t=y(kk)*u %蝶形运算乘项 y(kk)=y(k)-t y(k)=y(k)+t end
u=u*WN end end
得结果： x =
1
0 1 2 3 4 5
6 7 kk = m = 8 3 t = N = 7 8 y = y = 4 -4 8 -4 6 0 4 2 6 1 5 3 -4 3 7 y = Nz = 4 -4 8 -4 6 -4
-4
2 u = 1 WN = -1.0000 - 0.0000i kk = 2 t = 4 y = 0 -4 2 3 7 y = 4 -4 2 3 7 kk = 4 t = 6 y = 4 -4 2 3 7 y = 4 -4 8 3 7 kk = 6 t = 5 y = 4 -4 8 3 7 y = 4 -4 8 3 7
6 1 6 1 -4 1 -4 1 -4 1 -4 6 10 -4 u = -1.0000 - 0.0000i Nz = 4 u = 1 WN = 0.0000 - 1.0000i kk = 5 3 t = 8 5 y = 4 -4 -4 10 -4 y = 12 -4 -4 10 -4 kk = 5 7 t = 10 5 y = 12 -4 -4 -4 -4 y = 12 -4 -4 -4 -4 u =
-4 0.0000 - 1.0000i kk = 4 -4 t = -0.0000 + 4.0000i
2
-4 6 -4 6 -4 6 -4 16 -4
-4
-4
-4
y =
Columns 1 through 5
12.0000 + 0.0000i -4.0000 -4.0000 + 0.0000i -4.0000 16.0000 + 0.0000i
Columns 6 through 8
-4.0000 + 0.0000i -4.0000 -4.0000 + 0.0000i + 0.0000i - 4.0000i
+ 0.0000i
kk = 5 t = 16 y =
Columns 1 through 5
12.0000 + 0.0000i -4.0000 -4.0000 + 0.0000i -4.0000 + 4.0000i - 4.0000i
y =
Columns 1 through 5
12.0000 + 0.0000i -4.0000 + 0.0000i 16.0000 + 0.0000i
Columns 6 through 8
-4.0000 + 0.0000i -4.0000 + 0.0000i kk = 8 t =
-0.0000 + 4.0000i y =
Columns 1 through 5
12.0000 + 0.0000i -4.0000 + 0.0000i 16.0000 + 0.0000i
Columns 6 through 8
-4.0000 + 0.0000i -4.0000 - 4.0000i y =
Columns 1 through 5
12.0000 + 0.0000i -4.0000 + 0.0000i 16.0000 + 0.0000i
Columns 6 through 8
-4.0000 + 4.0000i -4.0000 - 4.0000i u =
-1.0000 - 0.0000i Nz = 8 u = 1 WN =
0.7071 - 0.7071i
-4.0000 + 0.0000i
Columns 6 through 8
-4.0000 + 4.0000i -4.0000 + 4.0000i -4.0000 - 4.0000i
-4.0000 - 4.0000i y =
Columns 1 through 5
-4.0000 + 0.0000i
28.0000 + 0.0000i -4.0000 + 0.0000i -4.0000 + 0.0000i
Columns 6 through 8
-4.0000 + 4.0000i -4.0000 - 4.0000i u =
0.7071 - 0.7071i -4.0000 + 4.0000i kk = -4.0000 - 4.0000i
6 t =
-0.0000 + 5.6569i -4.0000 + 0.0000i
y =
Columns 1 through 5
28.0000 + 0.0000i -4.0000 + 0.0000i -4.0000 + 4.0000i -4.0000 + 0.0000i
-4.0000 - 4.0000i
Columns 6 through 8
-4.0000 - 1.6569i -4.0000 - 4.0000i -4.0000 + 0.0000i
y =
Columns 1 through 5
28.0000 + 0.0000i -4.0000 + 0.0000i -4.0000 + 0.0000i
Columns 6 through 8
-4.0000 - 1.6569i -4.0000 - 4.0000i u =
0.0000 - 1.0000i
3
-4.0000 + 0.0000i
-4.0000 + 4.0000i -4.0000 - 4.0000i
-4.0000 + 0.0000i
-4.0000 + 4.0000i -4.0000 - 4.0000i
-4.0000 + 0.0000i
-4.0000 + 9.6569i -4.0000 - 4.0000i
-4.0000 + 0.0000i
kk = kk = 7 8 t = t = -0.0000 + 4.0000i -0.0000 + 5.6569i y = y = Columns 1 through 5 Columns 1 through 5
28.0000 + 0.0000i -4.0000 + 9.6569i 28.0000 + 0.0000i -4.0000 + 9.6569i -4.0000 + 0.0000i -4.0000 - 4.0000i -4.0000 + 4.0000i -4.0000 - 4.0000i -4.0000 + 0.0000i -4.0000 + 0.0000i Columns 6 through 8 Columns 6 through 8
-4.0000 - 1.6569i -4.0000 - 4.0000i -4.0000 - 1.6569i -4.0000 - 4.0000i -4.0000 - 4.0000i -4.0000 - 9.6569i y = y = Columns 1 through 5 Columns 1 through 5
28.0000 + 0.0000i -4.0000 + 9.6569i 28.0000 + 0.0000i -4.0000 + 9.6569i -4.0000 + 4.0000i -4.0000 - 4.0000i -4.0000 + 4.0000i -4.0000 + 1.6569i -4.0000 + 0.0000i -4.0000 + 0.0000i Columns 6 through 8 Columns 6 through 8
-4.0000 - 1.6569i -4.0000 - 4.0000i -4.0000 - 1.6569i -4.0000 - 4.0000i -4.0000 - 4.0000i -4.0000 - 9.6569i u = u = -0.7071 - 0.7071i -1.0000 - 0.0000i
在原来的基础上加入 y
y1=fft(x)
得与MATLAB运算中的fft函数比较结果： y =
Columns 1 through 5
28.0000 + 0.0000i -4.0000 + 9.6569i -4.0000 + 4.0000i -4.0000 + 1.6569i -4.0000 + 0.0000i
Columns 6 through 8
-4.0000 - 1.6569i -4.0000 - 4.0000i -4.0000 - 9.6569i y1 =
Columns 1 through 5
28.0000 + 0.0000i -4.0000 + 9.6569i -4.0000 + 4.0000i -4.0000 + 1.6569i -4.0000 + 0.0000i
Columns 6 through 8
-4.0000 - 1.6569i -4.0000 - 4.0000i -4.0000 - 9.6569i
作图比较（左边为基2—FFT算法的结果，右边为fft函数的结果）：
实部： n=1:8 subplot(121) stem(n,y,'filled')
4
subplot(122) stem(n,y1,'filled')
虚部：
subplot(121) stem(y,'filled') subplot(122) stem(y1,'filled')
由上图知实验结果一致
2.编程实现序列长度为N=8的按频率抽取的基2-FFT算法。给定一个8点序列，采用编写的程序计算其DFT，并与MATLAB中fft函数计算的结果相比较，以验证结果的正确性。
v=3 n=8
x=[0 1 2 3 4 5 6 7] y2=fft(x) for m=1:v n1=2^(v+1-m)
5
u=1
WN=exp(-2j*pi/n1) for j=1:n1/2 for k=j:n1:n kp=k+n1/2 t=x(k)+x(kp)
x(kp)=(x(k)-x(kp))*u; x(k)=t end u=u*WN end end
xx=bin2dec(fliplr(dec2bin([1:n]-1,v)))+1; y=x(xx) y n=1:8 subplot(221) stem(n,y,'filled') subplot(222) stem(n,y2,'filled') subplot(223) stem(y,'filled') subplot(224) stem(y2,'filled')
结果： y = y = Columns 1 through 5 Columns 1 through 5
28.0000 + 0.0000i -4.0000 + 9.6569i 28.0000 + 0.0000i -4.0000 + 9.6569i -4.0000 + 4.0000i -4.0000 + 1.6569i -4.0000 + 4.0000i -4.0000 + 1.6569i -4.0000 + 0.0000i -4.0000 + 0.0000i Columns 6 through 8 Columns 6 through 8
-4.0000 - 1.6569i -4.0000 - 4.0000i -4.0000 - 1.6569i -4.0000 - 4.0000i -4.0000 - 9.6569i -4.0000 - 9.6569i 图像：
（左边为基2—FFT算法的结果，右边为fft函数的结果；上面为实部的值，下面为虚部的值）
6
结果正确。
3. 将上述FFT程序推广大序列长度为N=2v的情况，要求利用原位运算。 代码（不妨取n=6）： x=1;
n=6; %在这里输入2 的次方数 for s=2:2^n x=[x s]; end N=2^n;
out=bin2dec(fliplr(dec2bin([1:N]-1,n)))+1; %码位倒序 y=x(out); for mm=1:n
Nz=2^mm;u=1;
WN=exp(-1i*2*pi/Nz); for j=1:Nz/2 for k=j:Nz:N kp=k+Nz/2; t=y(kp)*u; y(kp)=y(k)-t; y(k)=y(k)+t; end u=u*WN; end end
stem(y,’filled’) 结果：
7
验证： clf
stem(fft(x),’filled’)
显然结果正确 四． 体会与收获
通过本次实验，我掌握了基2-FFT的原理及具体实现方法；通过编程来实现基2-FFT算法，锻炼了我的编程能力；通过实验我加深了对FFT算法的特点的理解，体会到了原位计算和蝶形运算的优越性。
本实验能得到的结论有：（1）FFT的特点是原位计算；（2）按时间抽取FFT算法倒序输入顺序输出；按频率抽取FFT顺序输入倒序输出。
这次实验最大的挑战是编程，因为之前的MATLAB实验只是简单地输入指令得到结果，没有过MATLAB编程经验。通过加深对FFT算法的理解以及阅读相关程序，我熟悉了MATLAB编程。这对我来说是一种鼓舞吧。
8
因篇幅问题不能全部显示，请点此查看更多更全内容