数字信号处理实验一：FFT算法的应用

实验题目：实验1 FFT算法的应用

姓 名： 学 号： 上课时间： FFT算法的应用

1． 实验目的：

离散傅氏变换（DFT）的目的是把信号由时域变换到频域，从而可以在频域分析处理信息，得到的结果再由逆DFT变换到时域。FFT是DFT的一种快速算法。在数字信号处理系统中，FFT作为一个非常重要的工具经常使用，甚至成为DSP运算能力的一个考核因素。

本实验通过使用MATLAB函数中的FFT命令计算离散时间信号的频谱，以加深对离散信号的DFT的理解及其FFT算法的运用。

2． 实验要求：

对实验内容中给定的序列求给定点数N的FFT和IFFT，利用MATLAB编程完成计算，绘出相应图形。并与理论计算相比较，说明实验结果的原因。

3． 实验原理：

一．数字滤波器设计：

（一）基—2按时间抽取FFT算法

对于有限长离散数字信号{x[n]}，0 ? n ? N-1，其离散谱{x[k]}可以由离

X?k???x[n]en?0N?1?j(2?)nkNk?0,1,...,N?1散付氏变换（DFT）求得。DFT的定义为

可以方便的把它改写为如下形式： 不难看出，WN是周期性的，且周期为N，即

N?1nlN?0(n?mN)(k?)nkWN?WNnkX?k???x[n]WNk?0,1,...,N?1m,l?0,?1,?2...WN的周期性是DFT的关键性质之一。为了强调起见，常用表达式WN取代W以便明确其周期是N。

由DFT的定义可以看出，在x[n]为复数序列的情况下，完全直接运算N点DFT需要（N-1）2次复数乘法和N（N-1）次加法。因此，对于一些相当大的N值（如1024）来说，直接计算它的DFT所作的计算量是很大的。FFT的基本思想在于，将原有的N点序列序列分成两个较短的序列，这些序列的DFT可以很简单的组合起来得到原序列的DFT。例如，若N为偶数，将原有的N点序列分成两个（N/2）点序列，那么计算N点DFT将只需要约[(N/2)2 ·2]=N2/2次复数乘法。即比直接计算少作一半乘法。因子（N/2）2表示直接计算（N/2）点DFT所需要的乘法次数，而乘数2代表必须完成两个DFT。上述处理方法可以反复使用，即（N/2）点的DFT计算也可以化成两个（N/4）点的DFT（假定N/2为偶数），从而又少作一半的乘法。这样一级一级的划分下去一直到最后就划分成两点的FFT运算的情况。比如，一个N = 8点的FFT运算按照这种方法来计算FFT可以用下面的流程图来表示：

x(0)W0x(1)W0x(2)W0x(3)x(4)W0x(5)W0x(6)W0x(7)W2X(7)W3X(6)W2X(5)W2W0W1X(3)X(4)X(2)X(1)X(0)

关于蝶形结运算的具体原理及其推导可以参照讲义，在此就不再赘述。按频率抽取的FFT的原理也可查阅相关资料，这里就不再推导了。

二．使用到的MATLAB命令：

函数fft(x)可以计算R点序列的R点DFT值；而fft(x,N)则计算R点序列的N点DFT，若R>N，则直接截取R点DFT的前N点，若R

4．实验内容：

(1) 计算一个实数序列x[n]?1,0?n?256的1024点FFT，注意使用将此序列组

合成一复数序列后再计算的方法。 (1)实验分析：

求某实信号y(n)的复谱,可认为是将实信号加上数值为零的虚部变成复信号(x(n)+j0),再用FFT求其离散付里叶变换。这种作法很不经济,因为把实序列变成复序列,存储器要增加一倍,且计算机运行时,即使虚部为零,也要进行涉及虚部的运算,浪费了运算量。合理的解决方法是利用复数据FFT对实数据进行有效计算。

用一个N点的FFT运算获得一个2N点实序列的DFT

设x(n)是2N点的实序列,现人为地将x(n)分为偶数组x1(n)和奇数组x2(n)

x1(n)=x(2n) n=0,1,…,N-1 x2(n)=x(2n+1) n=0,1,…,N-1

然后将x1(n)及x2(n)组成一个复序列y(n)=x1(n)+jx2(k) 通过N点FFT运算可得到 Y(k)=X1(k)+jX2(k) 根据前面的讨论，得到

为求2N点x（n）所对应的X（k），需求出X（k）与X1（k），X2（k）的关系

而

nk所以 X(k)=X1(k)+WNX2(k)。

这样，由x1(n)及x2(n)组成复序列，经FFT运算求得Y(k)后，再利用共轭对称性求出X1(k),X2(k)，最后利用上式求出X(k),从而达到了用一个N点的FFT计算一个2N点实序列DFT的目的。 (2)matlab源程序：

function [ xk ] = gongshijun2( )

x1=[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0];

x2=[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]; yn=x1+1i*x2; yk=fft(yn,512); x3=x1(end:-1:1); x4=x2(end:-1:1); yn=x3+1i*x4;

ynk=fft(yn,512); x1k=0.5*(yk+conj(ynk)); x2k=-(1i)*0.5*(yk-conj(ynk)); xk=x1k+x2k*exp(1i*360/1024*512); m=0:length(xk)-1; plot(m,xk,'b-'); end

(3)实验结果截图：

(4)实验图截图：

(2) 分别计算两个实数序列

x(n)?sinx(n?)5?cno?sn?16,和01285?n,0?n?128的128点FFT，注意使用将此二序列组合成一复16数序列后再计算的方法。 (1)实验分析：

一个N点FFT同时计算两个N点实序列的DFT

设x1(n),x2(n)是彼此独立的两个N点实序列,且X1(k)=DFT[x1(n)]，X2(k)=DFT[x2(n)]

可通过一次FFT运算同时获得X1(k),X2(k)。算法如下： 首先将x1(n),x2(n)分别当作一复序列的实部及虚部,令 x(n)=x1(n)+jx2(n)

通过FFT运算可获得x(n)的DFT值

X(k)=DFT[x1(n)]+jDFT[x2(n)]=X1(k)+jX2(k) 利用离散付里叶变换的共轭对称性

有了x(n)的FFT运算结果X(k),由上式即可得到X1(k),X2(k)的值。 则，由题目的设

x1(n)=x(n)?cos5?5?n,0?n?128,x2(n)=x(n)?sinn,0?n?128 1616组合成复数序列x(n)=cos求得相应的结果。 (2)matlab源程序：

5?5?n?jsinn,0?n?128，根据实验原理就可以1616function [gg,aa] = gongshijun1() n=0:128;

xn=cos(56.25*n)+1i*sin(56.25*n); xk=fft(xn,128);

xnk=cos(56.25*(128-n))+1i*sin(56.25*(128-n)); xnkk=fft(xnk,128); gg=0.5*(xk+conj(xnkk)); aa=-(1i)*0.5*(xk-conj(xnkk)); m=0:length(gg)-1;

plot(m,gg,'k:',m,aa,'b-'); end

(3)实验结果截图：

（4）实验图截图：

(3) 利用DFT的方式计算下面两序列的线性卷积：

g[n]={3, 4, -2, 0, 1, -4},h[n]={1, -3, 0, 4, -2, 3}

(1)实验分析：

用FFT法也就是用圆周卷积来代替线性卷积，为了不产生混跌，其必要条件是使用g(n),h(n)都补零值点，补到至少N=M+L-1(M=6，L=6)，即

h(n),0?n?5 g(n)?{,h(n)?{

0,6?n?110,6?n?11然后计算圆周卷积

y(n)?x(n)?h(n) 这时，y(n)就能代表线性卷积的结果。 用FFT计算y(n)值得步骤如下： (1)求H(k)=DFT[h(n)],N点； (2)求G(k)=DFT[g(n)],N点；

g(n),0?n?5(3)计算Y(k)=H(k)G(k)； (4)求y(n)=IDFT[Y(k)],N点。 (2)matlab源程序：

function gg = gongshijun( ) g= [3,4,-2,0,1,-4,0,0,0,0,0,0]; h= [1,-3,0,4,-2,3,0,0,0,0,0,0]; Gk= fft(g,11); Hk= fft(h,11); Yk= Gk.*Hk; gg= ifft(Yk,11); n=0:length(gg)-1; plot(n,gg,'k.'); (2)实验结果和实验图截图：

本文来源：https://www.bwwdw.com/article/01bg.html