数字信号处理课程设计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前言信号(signal)是一种物理体现，或是传递信息的函数。而信息是信号的具体内容。模拟信号(analogsignal)：指时间连续、幅度连续的信号。数字信号(digitalsignal)：时间和幅度上都是离散(量化)的信号。　　数字信号可用一序列的数表示，而每个数又可表示为二制码的形式，适合计算机处理。数字信号处理是将信号以数字

3、方式表示并处理的理论和技术。数字信号处理与模拟信号处理是信号处理的子集。　其目的是对真实世界的连续模拟信号进行测量或滤波。因此在进行数字信号处理之前需要将信号从模拟域转换到数字域，这通常通过模数转换器实现。而数字信号处理的输出经常也要变换到模拟域，这是通过数模转换器实现的。数字信号处理的核心算法是离散傅立叶变换(DFT)，是DFT使信号在数字域和频域都实现了离散化，从而可以用通用计算机处理离散信号。而使数字信号处理从理论走向实用的是快速傅立叶变换(FFT)，FFT的出现大大减少了DFT的运算量，使

4、实时的数字信号处理成为可能、极大促进了该学科的发展。随着大规模集成电路以及数字计算机的飞速发展，加之从60年代末以来数字信号处理理论和技术的成熟和完善，用数字方法来处理信号，即数字信号处理，已逐渐取代模拟信号处理。　　随着信息时代、数字世界的到来，数字信号处理已成为一门极其重要的学科和技术领域。第一章离散傅里叶变换DFT离散傅立叶变换（DFT）实现了信号首次在频域表示的离散化，使得频域也能够用计算机进行处理。并且这种DFT变换可以有多种实用的快速算法。使信号处理在时、频域的处理和转换均可离散化和快

5、速化，因而具有重要的理论意义和应用价值。1.1DFT定义设序列x(n)长度为M，定义x(n)的N点DFT为式中，N称为离散傅里叶变换区间长度，要求N≥M。为书写简单，令，因此通常将N点DFT表示为1.2DFT的快速算法——快速傅里叶变换(FFT)DFT使计算机在频域处理信号成为可能，但是当N很大时，直接计算N点DFT的计算量非常大。快速傅里叶变换（FFT，FastFourierTransform）可使实现DFT的运算量下降几个数量级，从而使数字信号处理的速度大大提高，工程应用成为可能。人们已经研究

6、出多种FFT算法，它们的复杂度和运算效率各不相同。快速傅里叶变换就是不断地将长序列的DFT分解为短序列的DFT，并利用的周期性和对称性及其一些特殊值来减少DFT运算量的快速算法。FFT算法分类：1.时间抽选法DIT：Decimation-In-Time2.频率抽选法DIF：Decimation-In-Frequency时间域抽取：基2时间抽取(Decimationintime)DIT-FFT算法频率域抽取：基2频率抽取(Decimationinfrequency)DIF-FFT算法第一章基2DIT

7、-FFT算法2.1按时间抽取的基2DIT-FFT算法：1、按时间抽取的基2DIT-FFT算法原理先设序列点数为N=2M，M为整数。如果不满足这个条件，可以人为地加上若干零值点，使之达到这一要求。这种N为2的整数幂的FFT称基-2FFT。设输入序列长度为N=2M(M为正整数)，将该序列按时间顺序的奇偶分解为越来越短的子序列，称为按时间抽取(DIT)的FFT算法。序列x(n)的N点DFT为将上面的和式按n的奇偶性分解为令x1(l)=x(2l),x2(l)=x(2l+1)，因为，所以上式可写成上式说明，

8、按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，即有上述公式，及X1（k）、X2(k)的隐含周期性得到：这样，就将N点DFT的计算分解为计算两个N/2点离散傅里叶变换X1(k)和X2(k)，再计算上式。蝶形图：2、按时间抽选的FFT算法的特点：（1） 原位运算由图4.2.4可以看出，DIT-FFT的运算过程很有规律。N=2M点的FFT共进行M级