DFT的快速算法——快速傅里叶变换(FFT).doc

目录 前言 第一章 离散傅里叶变换DFT…………………………………………………3 1.1 DFT定义……………………………………………………………3 1.2 DFT的快速算法——快速傅里叶变换(FFT) ……………………3 第二章 基2 DIT-FFT算法…………………………………………………4 2.1 按时域抽取的基2 DIT-FFT算法…………………………………4 第三章 基于C语言设计16点基2DIT-FFT程序及运行结果 ……………6 3.1 按时间抽取的基2DIT-FFT程序 …………………………………6 3.2 程序运行结果 ……………………………………………………15 第四章 课程设计的总结 ……………………………………………………17 参考文献 ………………………………………………………………………17 前 言 信号(signal)是一种物理体现，或是传递信息的函数。而信息是信号的具体内容。模拟信号(analog signal)：指时间连续、幅度连续的信号。数字信号(digital signal)：时间和幅度上都是离散(量化)的信号。 　　数字信号可用一序列的数表示，而每个数又可表示为二制码的形式，适合计算机处理。 数字信号处理是将信号以数字方式表示并处理的理论和技术。数字信号处理与模拟信号处理是信号处理的子集。 　其目的是对真实世界的连续模拟信号进行测量或滤波。因此在进行数字信号处理之前需要将信号从模拟域转换到数字域，这通常通过模数转换器实现。而数字信号处理的输出经常也要变换到模拟域，这是通过数模转换器实现的。 数字信号处理的核心算法是离散傅立叶变换(DFT)，是DFT使信号在数字域和频域都实现了离散化，从而可以用通用计算机处理离散信号。而使数字信号处理从理论走向实用的是快速傅立叶变换(FFT)，FFT的出现大大减少了DFT的运算量，使实时的数字信号处理成为可能、极大促进了该学科的发展。 随着大规模集成电路以及数字计算机的飞速发展，加之从60年代末以来数字信号处理理论和技术的成熟和完善，用数字方法来处理信号，即数字信号处理，已逐渐取代模拟信号处理。 　　 随着信息时代、数字世界的到来，数字信号处理已成为一门极其重要的学科和技术领域。 离散傅里叶变换DFT 离散傅立叶变换（DFT）实现了信号首次在频域表示的离散化，使得频域也能够用计算机进行处理。并且这种DFT变换可以有多种实用的快速算法。使信号处理在时、频域的处理和转换均可离散化和快速化，因而具有重要的理论意义和应用价值。 1.1 DFT定义 设序列x(n)长度为M，定义x(n)的N点DFT为 式中，N称为离散傅里叶变换区间长度，要求N ≥ M。为书写简单，令 ，因此通常将N点DFT表示为 1.2 DFT的快速算法——快速傅里叶变换(FFT) DFT使计算机在频域处理信号成为可能，但是当N很大时，直接计算N点DFT的计算量非常大。快速傅里叶变换（FFT，Fast Fourier Transform）可使实现DFT的运算量下降几个数量级，从而使数字信号处理的速度大大提高，工程应用成为可能。人们已经研究出多种FFT算法，它们的复杂度和运算效率各不相同。 快速傅里叶变换就是不断地将长序列的DFT分解为短序列的DFT，并利用 的周期性和对称性及其一些特殊值来减少DFT运算量的快速算法。 FFT算法分类： 1.时间抽选法 DIT：Decimation-In-Time 2.频率抽选法 DIF：Decimation-In-Frequency 时间域抽取： 基2时间抽取(Decimation in time)DIT-FFT算法 频率域抽取： 基2频率抽取(Decimation in frequency)DIF-FFT算法 基2 DIT-FFT算法 按时间抽取的基2 DIT-FFT算法： 1、按时间抽取的基2 DIT-FFT算法原理 先设序列点数为N=2M，M为整数。如果不满足这个条件，可以人为地加上若干零值点，使之达到这一要求。这种N为2的整数幂的FFT称基-2 FFT。 设输入序列长度为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，即 有上述公式，及X1（k）、X2(k)的隐含