实验四 离散傅里叶变换及其快速算法
一、 实验目的
掌握快速傅立叶变换的应用方法；
二、 实验仪器：电脑一台，MATLAB6.5或更高级版本软件一套。 三、 实验原理和实例分析 （一）离散傅里叶变换
离散傅立叶级数变换是周期序列，仍不便于计算机计算。但离散傅立叶级数虽是周期序列，却只有N个独立的数值，所以它的许多特性可以通过有限长序列延拓来得到。对于一个长度为N的有限长序列x(n)，也即x(n)只在
n?0~(N?1)个点上有非零值，其余皆为零，即
?x(n),0?n?N?1x(n)??其他?0,
把序列x(n)以N为周期进行周期延拓得到周期序列x(n)，则有：
~??x(n)??x(n),0?n?N?1?其他?0,
~所以，有限长序列x(n)的离散傅立叶变换(DFT)为：
?knX(k)?DFT[x(n)]??x(n)WN,0?n?N?1n?0N?1
逆变换为：
1N?1?knx(n)?IDFT[X(k)]??X(k)WN,0?n?N?1Nn?0
若将DFT变换的定义写成矩阵形式，则得到： X=A﹒x，其中DFT变换矩阵A为
1?1?1W1?NA??...?...N?1?1WN?.........1WNN?1...2(N?1)...WN
Dftmtx 函数：用来计算DFT变换矩阵A的函数
调用方式
A＝dftmta（n）：返回n×n的DFT变换矩阵A。若x为给定长度的行向量，则y＝x*A，返回x的DFT变换y。
Ai＝conj（dftmtx（n））/n；返回n×n的IDFT变换矩阵Ai。 【实例4-1】 >> A=dftmtx(4) >> Ai=conj(dftmtx(4))/4 运行结果
A =
1.0000 1.0000 1.0000 1.0000 1.0000 0 - 1.0000i -1.0000 0 + 1.0000i
1.0000 -1.0000 1.0000 -1.0000 1.0000 0 + 1.0000i -1.0000 0 - 1.0000i Ai =
0.2500 0.2500 0.2500 0.2500 0.2500 0 + 0.2500i -0.2500 0 - 0.2500i
0.2500 -0.2500 0.2500 -0.2500 0.2500 0 - 0.2500i -0.2500 0 + 0.2500i
【实例4-2】如果x(n)?sin(n?/8)?sin(n?/4)是一个N＝16的有限序列，用MATLAB求其DFT的结果，并画出其结果图，如图4－1所示。 % 程序 N=16;
n=0:1:N-1; %时域采样 xn=sin(n*pi/8)+sin(n*pi/4); k=0:1:N-1; %频域采样 WN=exp(-j*2*pi/N); nk=n'*k; WNnk=WN.^nk; Xk=xn*WNnk; subplot(2,1,1) stem(n,xn); subplot(2,1,2)
stem(k,abs(Xk));
运算结果
Xk =
Columns 1 through 5
0.0000 -0.0000 - 8.0000i -0.0000 - 8.0000i 0.0000 - 0.0000i 0.0000 - 0.0000i
Columns 6 through 10
-0.0000 - 0.0000i 0.0000 - 0.0000i 0.0000 - 0.0000i 0.0000 - 0.0000i 0.0000 - 0.0000i
Columns 11 through 15
0.0000 - 0.0000i 0.0000 - 0.0000i 0.0000 - 0.0000i 0.0000 - 0.0000i 0.0000 + 8.0000i
Column 16
0.0000 + 8.0000i
图 4-1 有限长序列的DFT结果图
思考：当N=8，16，24，48，分别执行程序，得出什么结论？
频谱的误差主要是由于时域中对信号的非整周期截断产生的频谱泄漏。
（二） 快速傅立叶变换（FFT）
快速离散傅里叶变换是计算离散傅里叶变换的一种快速算法，为了提高运算速度，FFT将DFT的计算逐次分解成较小点数的DFT。按时间抽取Decimation-In-Time(DIT)FFT算法把输入序列x(n)按其n值为偶数或是奇数分解成越来越短的序列。按频域抽取（Decimation-In-Frequency(DIF)FFT算法是