中国科学技术大学：《数字信号处理》课程教学资源（实验要求）实验2 FFT 算法实现

中国科学技术大学电子工程与信息科学系 《数字信号处理》课程基本实验 实验2 FFT算法实现 2.1 实验目的 1、加深对快速傅里叶变换的理解。 2、掌握FFT算法及其程序的编写。 3、掌握算法性能评测的方法。 2.2 实验原理 一个连续信号x。()的频谱可以用它的傅立叶变换表示为 X.(Uj2)=∫x(0e严d (2-1) 如果对该信号进行理想采样，可以得到采样序列 x(n)=x(nT) (2-2) 同样可以对该序列进行z变换，其中T为采样周期 xe)=20m- (2-3) 当z=e°的时候，我们就得到了序列的傅立叶变换 Xe)=∑mem (2-4) 其中ω称为数字频率，它和模拟域频率的关系为 o=2T=2/f (2-5) 式中的∫，是采样频率。上式说明数字频率是模拟频率对采样率∫，的归一化。同模拟域的情 况相似，数字频率代表了序列值变化的速率，而序列的傅立叶变换称为序列的频谱。序列的 傅立叶变换和对应的采样信号频谱具有下式的对应关系。 e)=2x.° (2-6) 即序列的频谱是采样信号频谱的周期延拓。从式(2-6)可以看出，只要分析采样序列的频 谱，就可以得到相应的连续信号的频谱。注意：这里的信号必须是带限信号，采样也必须满

中国科学技术大学电子工程与信息科学系 《数字信号处理》课程基本实验 1 实验2 FFT 算法实现 2.1 实验目的 1、 加深对快速傅里叶变换的理解。 2、 掌握 FFT 算法及其程序的编写。 3、 掌握算法性能评测的方法。 2.2 实验原理 一个连续信号 x (t) a 的频谱可以用它的傅立叶变换表示为 X j x t e dt j t a a      ( )  ( ) （2-1） 如果对该信号进行理想采样，可以得到采样序列 x(n) x (nT)  a （2-2） 同样可以对该序列进行 z 变换，其中 T 为采样周期      n X (z) x(n)z （2-3） 当 j z  e 的时候，我们就得到了序列的傅立叶变换     j j n X e x n e   ( ) ( ) （2-4） 其中ω 称为数字频率，它和模拟域频率的关系为 s   T  / f （2-5） 式中的 s f 是采样频率。上式说明数字频率是模拟频率对采样率 s f 的归一化。同模拟域的情 况相似，数字频率代表了序列值变化的速率，而序列的傅立叶变换称为序列的频谱。序列的 傅立叶变换和对应的采样信号频谱具有下式的对应关系。      ) 2 ( 1 ( ) T m X j T X e a j   （2-6） 即序列的频谱是采样信号频谱的周期延拓。从式（2-6）可以看出，只要分析采样序列的频 谱，就可以得到相应的连续信号的频谱。注意：这里的信号必须是带限信号，采样也必须满

中国科学技术大学电子工程与信息科学系 《数字信号处理》课程基本实验 足Nyquist定理。 在各种信号序列中，有限长序列在数字信号处理中占有很重要的地位。无限长的序列也 往往可以用有限长序列来逼近。对于有限长的序列我们可以使用离散傅立叶变换(DT), 这一变换可以很好地反应序列的频域特性，并且容易利用快速算法在计算机上实现当序列的 长度是N时，我们定义离散傅立叶变换为： N-1 X(k)=DFTx(n]=∑x(n)w (2-7) =0 其中W=e,它的反变换定义为： x(n)=IDFT[X(k)]= 岁xk)w (2-8) N 根据式(2-3)和(2-7)令z=W,则有 N-1 X(=)=>x(n)W DFTIx(n)] (2-9) =0 可以得到X化=X川：=W=e户，W*是2平面单位圆上幅角为0 2元k的 点，就是将单位圆进行N等分以后第k个点。所以，X(k)是z变换在单位圆上的等距采样， 或者说是序列傅立叶变换的等距采样。时域采样在满足Nyquist定理时，就不会发生频谱混 淆：同样地，在频率域进行采样的时候，只要采样间隔足够小，也不会发生时域序列的混淆。 DFT是对序列傅立叶变换的等距采样，因此可以用于序列的频谱分析。在运用DFT进 行频谱分析的时候可能有三种误差，分析如下： (1)混淆现象 从式(2-6)中可以看出，序列的频谱是采样信号频谱的周期延拓，周期是2TT,因此 当采样速率不满足Nyquist定理，即采样频率∫，=I/T小于两倍的信号（这里指的是实信号） 频率时，经过采样就会发生频谱混淆。这导致采样后的信号序列频谱不能真实地反映原信号 的频谱。所以，在利用DFT分析连续信号频谱的时候，必须注意这一问题。避免混淆现象 的唯一方法是保证采样的速率足够高，使频谱交叠的现象不出现。这就告诉我们，在确定信 号的采样频率之前，需要对频谱的性质有所了解。在一般的情况下，为了保证高于折叠频率 的分量不会出现，在采样之前，先用低通模拟滤波器对信号进行滤波。 (2)泄漏现象 实际中的信号序列往往很长，甚至是无限长序列。为了方便，我们往往用截短的序列来 近似它们。这样可以使用较短的DT来对信号进行频谱分析。这种截短等价于给原信号序 列乘以一个矩形窗函数。而矩形窗函数的频谱不是有限带宽的，从而它和原信号的频谱进行 卷积以后会扩展原信号的频谱。值得一提的是，泄漏是不能和混淆完全分离开的，因为泄露 导致频谱的扩展，从而造成混淆。为了减小泄漏的影响，可以选择适当的窗函数使频谱的扩 散减到最小。 (3)栅栏效应 因为DFT是对单位圆上z变换的均匀采样，所以它不可能将频谱视为一个连续函数。 2

中国科学技术大学电子工程与信息科学系 《数字信号处理》课程基本实验 2 足 Nyquist 定理。 在各种信号序列中，有限长序列在数字信号处理中占有很重要的地位。无限长的序列也 往往可以用有限长序列来逼近。对于有限长的序列我们可以使用离散傅立叶变换（DFT）， 这一变换可以很好地反应序列的频域特性，并且容易利用快速算法在计算机上实现当序列的 长度是 N 时，我们定义离散傅立叶变换为：      1 0 ( ) [ ( )] ( ) N n kn n WN X k DFT x n x （2-7） 其中 N j N W e 2   ，它的反变换定义为：       1 0 ( ) 1 ( ) [ ( )] N k kn WN X k N x n IDFT X k （2-8） 根据式（2-3）和（2-7）令 k WN z   ，则有        1 0 ( ) | ( ) [ ( )] N n n k X z z W k x n WN DFT x n N （2-9） 可以得到 k N j k N X k X z z W e 2 ( )  ( ) |    , k WN  是 z 平面单位圆上幅角为 k N   2  的 点，就是将单位圆进行 N 等分以后第 k 个点。所以，X(k)是 z 变换在单位圆上的等距采样， 或者说是序列傅立叶变换的等距采样。时域采样在满足 Nyquist 定理时，就不会发生频谱混 淆；同样地，在频率域进行采样的时候，只要采样间隔足够小，也不会发生时域序列的混淆。 DFT 是对序列傅立叶变换的等距采样，因此可以用于序列的频谱分析。在运用 DFT 进 行频谱分析的时候可能有三种误差，分析如下： （1）混淆现象 从式（2-6）中可以看出，序列的频谱是采样信号频谱的周期延拓，周期是 2π /T，因此 当采样速率不满足 Nyquist 定理，即采样频率 f s 1/T 小于两倍的信号（这里指的是实信号） 频率时，经过采样就会发生频谱混淆。这导致采样后的信号序列频谱不能真实地反映原信号 的频谱。所以，在利用 DFT 分析连续信号频谱的时候，必须注意这一问题。避免混淆现象 的唯一方法是保证采样的速率足够高，使频谱交叠的现象不出现。这就告诉我们，在确定信 号的采样频率之前，需要对频谱的性质有所了解。在一般的情况下，为了保证高于折叠频率 的分量不会出现，在采样之前，先用低通模拟滤波器对信号进行滤波。 （2）泄漏现象 实际中的信号序列往往很长，甚至是无限长序列。为了方便，我们往往用截短的序列来 近似它们。这样可以使用较短的 DFT 来对信号进行频谱分析。这种截短等价于给原信号序 列乘以一个矩形窗函数。而矩形窗函数的频谱不是有限带宽的，从而它和原信号的频谱进行 卷积以后会扩展原信号的频谱。值得一提的是，泄漏是不能和混淆完全分离开的，因为泄露 导致频谱的扩展，从而造成混淆。为了减小泄漏的影响，可以选择适当的窗函数使频谱的扩 散减到最小。 （3）栅栏效应 因为 DFT 是对单位圆上 z 变换的均匀采样，所以它不可能将频谱视为一个连续函数

中国科学技术大学电子工程与信息科学系 《数字信号处理》课程基本实验 这样就产生了栅栏效应，从某种角度来看，用DFT来观看频谱就好像通过一个栅栏来观看 一幅景象，只能在离散点上看到真实的频谱。这样的话就会有一些频谱的峰点或谷点被“栅 栏”挡住，不能被我们观察到。减小栅栏效应的一个方法是在源序列的末端补一些零值，从 而变动DFT的点数。这种方法的实质是认为地改变了对真实频谱采样的点数和位置，相当 于搬动了“栅栏”的位置，从而使得原来被挡住的一些频谱的峰点或谷点显露出来。注意， 这时候每根谱线多对应的频率和原来的已经不相同了。 从上面的分析过程可以看出，DT可以用于信号的频谱分析，但必须注意可能产生的 误差，在应用过程中要尽可能减小和消除这些误差的影响。 快速傅立叶变换FFT并不是与DFT不相同的另一种变换，而是为了减少DFT运算次数 的一种快速算法。它是对变换式(2-7)进行一次次的分解，使其成为若干小点数DT的组 合，从而减小运算量。常用的FFT是以2为基数，其长度N=2“。它的运算效率高，程 序比较简单，使用也十分地方便。当需要进行变换的序列的长度不是2的整数次方的时候， 为了使用以2为基的FFT,可以用末尾补零的方法，使其长度延长至2的整数次方。FFT 一般可以通过FFT程序来完成，比较式(2-7)和(2-8)，只要对Xk)取共轭，进行FFT运 算，然后再取共轭，并乘以因子1N,就可以完成FFT。 2.3 实验内容 1、编制自己的FFT算法。 2、选取实验1中的典型信号序列验证算法的有效性。 3、对所编制FFT算法进行性能评估。 2.4 实验报告要求 1、总结自己实现F℉T算法时候采用了哪些方法减小了运算量。 2、给出自己的FFT算法与实验1中自己的DFT算法的性能比较结果。 3、给出自己的FFT算法与Matlab中FFT算法的性能比较结果。 4、总结实验中根据实验现象得到的其他个人结论

中国科学技术大学电子工程与信息科学系 《数字信号处理》课程基本实验 3 这样就产生了栅栏效应，从某种角度来看，用 DFT 来观看频谱就好像通过一个栅栏来观看 一幅景象，只能在离散点上看到真实的频谱。这样的话就会有一些频谱的峰点或谷点被“栅 栏”挡住，不能被我们观察到。减小栅栏效应的一个方法是在源序列的末端补一些零值，从 而变动 DFT 的点数。这种方法的实质是认为地改变了对真实频谱采样的点数和位置，相当 于搬动了“栅栏”的位置，从而使得原来被挡住的一些频谱的峰点或谷点显露出来。注意， 这时候每根谱线多对应的频率和原来的已经不相同了。 从上面的分析过程可以看出，DFT 可以用于信号的频谱分析，但必须注意可能产生的 误差，在应用过程中要尽可能减小和消除这些误差的影响。 快速傅立叶变换 FFT 并不是与 DFT 不相同的另一种变换，而是为了减少 DFT 运算次数 的一种快速算法。它是对变换式（2-7）进行一次次的分解，使其成为若干小点数 DFT 的组 合，从而减小运算量。常用的 FFT 是以 2 为基数，其长度 M N  2 。它的运算效率高，程 序比较简单，使用也十分地方便。当需要进行变换的序列的长度不是 2 的整数次方的时候， 为了使用以 2 为基的 FFT，可以用末尾补零的方法，使其长度延长至 2 的整数次方。IFFT 一般可以通过 FFT 程序来完成，比较式（2-7）和（2-8），只要对 X(k)取共轭，进行 FFT 运 算，然后再取共轭，并乘以因子 1/N，就可以完成 IFFT。 2.3 实验内容 1、 编制自己的 FFT 算法。 2、 选取实验 1 中的典型信号序列验证算法的有效性。 3、 对所编制 FFT 算法进行性能评估。 2.4 实验报告要求 1、 总结自己实现 FFT 算法时候采用了哪些方法减小了运算量。 2、 给出自己的 FFT 算法与实验 1 中自己的 DFT 算法的性能比较结果。 3、 给出自己的 FFT 算法与 Matlab 中 FFT 算法的性能比较结果。 4、 总结实验中根据实验现象得到的其他个人结论