数字信号处理课程设计-dft的快速算法——快速傅里叶变换(fft)

《数字信号处理课程设计-dft的快速算法——快速傅里叶变换(fft)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、燕山大学课程设计说明书目录前言第一章离散傅里叶变换DFT…………………………………………………31.1DFT定义……………………………………………………………31.2DFT的快速算法——快速傅里叶变换(FFT)……………………3第二章基2DIT-FFT算法…………………………………………………42.1按时域抽取的基2DIT-FFT算法…………………………………4第三章基于C语言设计16点基2DIT-FFT程序及运行结果……………63.1按时间抽取的基2DIT-FFT程序…………………………………63.2程序运行结果……………………………………………

2、………15第四章课程设计的总结……………………………………………………17参考文献………………………………………………………………………17共17页第17页燕山大学课程设计说明书前言信号(signal)是一种物理体现，或是传递信息的函数。而信息是信号的具体内容。模拟信号(analogsignal)：指时间连续、幅度连续的信号。数字信号(digitalsignal)：时间和幅度上都是离散(量化)的信号。　　数字信号可用一序列的数表示，而每个数又可表示为二制码的形式，适合计算机处理。数字信号处理是将信号以数字方式表示并处理的理论和技术。数字信号处理与模

3、拟信号处理是信号处理的子集。　其目的是对真实世界的连续模拟信号进行测量或滤波。因此在进行数字信号处理之前需要将信号从模拟域转换到数字域，这通常通过模数转换器实现。而数字信号处理的输出经常也要变换到模拟域，这是通过数模转换器实现的。数字信号处理的核心算法是离散傅立叶变换(DFT)，是DFT使信号在数字域和频域都实现了离散化，从而可以用通用计算机处理离散信号。而使数字信号处理从理论走向实用的是快速傅立叶变换(FFT)，FFT的出现大大减少了DFT的运算量，使实时的数字信号处理成为可能、极大促进了该学科的发展。随着大规模集成电路以及数字计算机的飞速发展，

4、加之从60年代末以来数字信号处理理论和技术的成熟和完善，用数字方法来处理信号，即数字信号处理，已逐渐取代模拟信号处理。　　随着信息时代、数字世界的到来，数字信号处理已成为一门极其重要的学科和技术领域。共17页第17页燕山大学课程设计说明书第一章离散傅里叶变换DFT离散傅立叶变换（DFT）实现了信号首次在频域表示的离散化，使得频域也能够用计算机进行处理。并且这种DFT变换可以有多种实用的快速算法。使信号处理在时、频域的处理和转换均可离散化和快速化，因而具有重要的理论意义和应用价值。1.1DFT定义设序列x(n)长度为M，定义x(n)的N点DFT为式中

5、，N称为离散傅里叶变换区间长度，要求N≥M。为书写简单，令，因此通常将N点DFT表示为1.2DFT的快速算法——快速傅里叶变换(FFT)DFT使计算机在频域处理信号成为可能，但是当N很大时，直接计算N点DFT的计算量非常大。快速傅里叶变换（FFT，FastFourierTransform）可使实现DFT的运算量下降几个数量级，从而使数字信号处理的速度大大提高，工程应用成为可能。人们已经研究出多种FFT算法，它们的复杂度和运算效率各不相同。快速傅里叶变换就是不断地将长序列的DFT分解为短序列的DFT，并利用的周期性和对称性及其一些特殊值来减少DFT运

6、算量的快速算法。FFT算法分类：1.时间抽选法DIT：Decimation-In-Time2.频率抽选法DIF：Decimation-In-Frequency时间域抽取：基2时间抽取(Decimationintime)DIT-FFT算法频率域抽取：基2频率抽取(Decimationinfrequency)DIF-FFT算法共17页第17页燕山大学课程设计说明书第一章基2DIT-FFT算法2.1按时间抽取的基2DIT-FFT算法：1、按时间抽取的基2DIT-FFT算法原理先设序列点数为N=2M，M为整数。如果不满足这个条件，可以人为地加上若干零值点，

7、使之达到这一要求。这种N为2的整数幂的FFT称基-2FFT。设输入序列长度为N=2M(M为正整数)，将该序列按时间顺序的奇偶分解为越来越短的子序列，称为按时间抽取(DIT)的FFT算法。序列x(n)的N点DFT为将上面的和式按n的奇偶性分解为令x1(l)=x(2l),x2(l)=x(2l+1)，因为，所以上式可写成上式说明，按n的奇偶性将x(n)分解为两个N/2长的序列x1(l)和x2(l)，则N点DFT可分解为两个N/2点DFT来计算。用X1(k)和X2(k)分别表示x1(l)和x2(l)的N/2点DFT，即共17页第17页燕山大学课程设计说明书

8、有上述公式，及X1（k）、X2(k)的隐含周期性得到：这样，就将N点DFT的计算分解为计算两个N/2点离散傅里叶变换X1(