DFT的快速算法分析及FFT的DSP实现

《DFT的快速算法分析及FFT的DSP实现》由会员分享，可在线阅读，更多相关《DFT的快速算法分析及FFT的DSP实现（24页珍藏版）》请在金锄头文库上搜索。

1、课程设计报告设计题目 DFT 的快速算法分析及 FFT 的 DSP 实现目录第 1 章 绪论1.1 设计背景1.2 数字信号处理技术现状1.3设计思路简介 第 2 章 系统开 发平台与环境2.1 CCS 开发环境2.2 ICETEKDSP 教学实验箱第 3 章 DFT 的快速算法分析与研究3.1 快速傅立叶变换原理3.2 FFT 快速算法分析3.2.1按时间抽取的基2DIT-FFT3.2.2 按频率抽取的基 2DIT-FFT3.2.3 按频率抽取的基 2DIT-FFT 第 4 章 系统软件设计 .4.1 DFT的编程思想4.2 程序源代码第 5 章 系统仿真5.1 仿真设置5.2 仿真图第 6

2、 章 总结10.10121212151517- 18 -第 1 章 绪论1.1 设计背景快速傅氏变换(FFT)是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、 虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理论并 没有新的 发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说 是进了一大 步。设x(n)为N项的复数序列，由DFT变换，任一X (m的计算都需要N次复数乘法和N- 1 次复数加法，而一次复数乘法等于四次实数乘法和两次实数加法，一次复数加法 等于两次 实数加法，即使把一次复数乘法和一次复数加法定义成一次“运算”(四次实 数乘法和四次实 数加

3、法)，那么求出N项复数序列的X( m，即N点DFT变换大约就需要N2次运算。当 N=1024点甚至更多的时候，需要N2=1048576次运算，在FFT中，利用WN勺周期性和对 称性，把一个N项序列(设N=2k,k为正整数)，分为两个N/2项的子序列，每个N/2点DFT 变换需要(N/2) 2次运算，再用N次运算把两个N/2点的DFT变换组合成一个N点的DFT 变换。这样变换以后，总的运算次数就变成 N+2(N/2) 2=N+N2/2 继续上面的例子， N=1024 时，总的运算次数就变成了 525312次，节省了大约 50%勺运 算量。而如果我们将这种“一 分为二”的思想不断进行下去，直到分成

4、两两一组的DFT运算单元，那么N点的DFT变换 就只需要 Nlog2N 次的运算， N 在 1024点时，运算量仅 有 10240 次，是先前的直接算法的 1%，点数越多，运算量的节约就越大，这就是FFT的优越性。数字信号处理器(DSP)是一种可编程的高性能处理器，近年来发展很快它不仅适用于 数字信号处理，而且在图像处理、语音处理、通信等领域得到了广泛的应用通用 的微处理 器在运算速度上很难适应信号实时处理的要求 联沪处理器中集成有高速的乘 法器硬件，能 快速地进行大量数据的乘法和加法运算。快速傅里叶变换(FFT )的出现使得 DFr 在实际应用中得到了广泛的应用.12 数字信号处理技术现状信

5、号处理 (slgnal Processing) 的本质是信息的安排和提取，将信息通过模拟、数 字或 光学的方法从各种噪声、干扰的环境中提取出来，并变换为一种便于人或计算机所 使用的形 式。通常的待测信号大多是模拟信号，数字信号处理技术先将模拟信号数字化 后(包括时域的 离散化和幅值的量化处理 )，再进行数字处理，最后还原成模拟信号，相 对于传统的模拟处 理技术，数字信号处理的突出优点是精度高、灵活性强、可靠性高、 易于大规模集成等等。在当前信息、 控制等很多应用领域都涌现出了所谓的 “实时系统” (Real time system) ，其 特点在于系统的输入、处理和输出等各个阶段都具有绝对的时

6、 间限制，若超过所限定的时 间，系统将被认为不起作用而失败。因此处理单元的速度必 须要足够快，以满足操作的实时 性限制。如电话网上的一个用于回音消除的语音信号处 理系统，处理数据的吞吐率必须要跟 得上语音信号的输入和输出速率，否则通信信道将 无法工作。实时数字信号处理问题的结构 层次划分如图卜 3 所示，总的可以分为算法的 开发和硬件体系结构的开发。50年代末期在时 域上发展了离散傅立叶变换(DFT)、相关等处理算法，这类算法的复杂度为0(W2)。根据当 时计算机的处理速度是做不到实时性 的。到了 70年代，大规模集成电路 (LsI) 技术的发展， 产生了微处理器(Micro processo

7、r unit, MPu和各种基于快速傅立叶变换(FFT)算法的实时 信号处理硬件，如高速并行乘 法器等；同时，1965年J. w. Colley和J w. Tukey提出的 FFT，将DFT算法的复杂度降为0( IV log : W)。以FFT为标志的使用快速算法的提出，促 进了专门用来实现数字信号处理的一类MPu的分化和发展，并在此基础上出现了面向实时 性、重复性、数值运 算密集型的特殊MPu即所谓的DsPDsP 为实时数字信号处理提供了廉价、高效、灵活的工具，促进了器件实用化和推 广。 DsP是实时数字信号处理技术的核心和标志，从功能上DSP可分为专用和通用两大类，专用DSP-般采用定点的

8、数据格式，结构简单，速度很快；通用DsP的灵活性好、功能 强，但处理速度有所降低。通用DsP片内取指、译码、执行等都采用流水线(Pipeline)技术， 缩短了执行时间；针对滤波、矩阵运算、FFT等需要大量乘加法运算的特点，DsP内部配有独 立的乘法器和加法器；许多DsP带有直接数据传输(DMA)通道控制器和多种 外设接，提高 了数据块传输的速度；DSP还普遍带有中断控制器和定时器，有的甚至还有A/ D D/A、 PwM调制解调器(Modem)等，方便了实时处理系统的构建。随着近20年来超大规模集成电 路(VLsI)技术的发展，DsP的处理速度越来越块，内存越来越大，功能越来越复杂，价格也 越

9、来越低，出现了面向通讯、图像处理、多媒体、仪器仪表等 各个领域、各个应用层次的产 品，成为了电子技术的主要热点。数字信号处理的应用领域是多种多样的，各种应用的抽样率变化范围很大，但数 字信 号处理基本上从两个方面来解决信号的处理问题:一个是时域方法，即数字滤波； 另一个是频 域方法，即频谱分析。数字信号处理的任务大致分为三类:1 卷积:用于各种滤波器， 对给定频率范围的原始信号进行加工 (通过或滤除 )来提高 信 噪比。2 相关:用于信号比较，去除随机事件而放大重复的信号。3变换:用于分析信号的频率内容，寻找特征“指纹”。这些信号处理算法的主要特点是:1包含大量数据。2 同样数据多次使用。3

10、存在反馈路径。4 都有快速乘加这样的基本运算。5 大量中间数据需要存储和管理。6 涉及大量地址产生。7 算法基本上针对并行运算。1.3 设计思路简介快速傅立叶变换(FFT)是实现离散傅立叶变换的快速算法，它在信号分析与处理领域 有着十分广泛的应用，是数字信号处理中最为重要的工具之一。高速F”处理技术是FFT技 术应用的一个主要方向。发展高速FFT处理技术是十分必要，因为：1 FFT 作为时域和频域转换的基本运算，是数字谱分析的必要条件，在通信等数字处理 领域 有着极为广泛的应用，部分应用更有高速实时运算的要求。2处理场合要求实时快速进行FFT运算，如电力系统中电压电流信号的谐波分析、数字滤 波

11、、振动分析和故障诊断和图像处理等方面，这些都需要使用专用的FFT计算设备进行实时处理。通常，提高FFT的运算速度有两种途径：一种是改进运算工具；另一种是改进 FFT算法本身。所以在实际的应用系统中，一方面我们要通过优化算法来提高运算速度，另 方面选取高效、快速、实用的FFT计算平台也十分关键。目前，实现FFT算法的计算平台主要有以下三种：1) 利用单片机通过软件编程来实现这种方法实现起来具有很大的灵活性，但是受到单片机本身性能的限制，例如没有专门的乘法运算部件，所以难以实现高速、大规模的 FFT计算。2) 应用专用FFT芯片或用户定制的大规模集成电路来实现这种方法可以实现很高的运行速度，但是使

12、用中灵活性较差，特别是在使用用户定制的 大规 模集成电路时，需要很高的开发、研制费用。3) 利用专门的 DSP 芯片通过软件编程实现这种方法作为FFT计算的平台具有十分突出的优势。上个世纪八十年代，专用数字信号处理器(DsP)诞生，用于实现数字信号处理的计算机结构发生了重大变化。它们大都具备了硬件乘法器，执行一次乘法运算所需的时间与加法相同：采用多级流水线操作，取 指、译码、 读数、执行等步骤并行进行； DSP 的程序总线和数据总线分开，访问数据和 读取程序能够同时进行：并可在一个指令周期内进行多个操作数的读取等等。总之，DsP技术的迅猛发展使其以优良的性能价格比和优化的结构为 FFT 的实现

13、提供了一个有效的 平台。正是由于采用DsP实现快速傅立叶变换（FFT）的上述优越性，本论文采用TI公司的 32位浮点DsP-TMs320Vc33为核心处理单元来实现了 FFT算法程序。该芯片具有快 速的指 令周期，高精度的浮点运算能力，具有专用的硬件乘法器可以在一个指令周期内 完成一次乘 法和一次加法，满足了 FFr 算法中有大量的乘法运算的需求，这样大大提高 了程序的执行效 率，同时，vC33为浮点DsP,在田运算中不需要考虑溢出问题，因而具有比定点DsP具有 更高的精确度，此外，它还有反序间接寻址指令，它是专门为n 叮的变换寻址而设计的，这样可以大大提高程序的执行效率。本课程设计主要是实现

14、了对各种FFT算法的研究、分析和比较。编写各种算法实现程 序，这些程序可以方便地作为子函数调用，以满足各种应用需要。第 2 章系统开发平台与环境2.1 CCS 开发环境CCS 提供了配置、建立、调试、跟踪和分析程序的工具，它便于实时、嵌入式信号 处理 程序的编制和测试，它能够加速开发进程，提高工作效率。CCS 提供了基本的代码生成工具，它们具有一系列的调试、分析能力。 CCS 支持如下图 1.1 所示的开发周期的所有阶段。图 1.12.2 ICETEK DSP 教学实验箱实验箱部分：一个数字信号发生器，可同时提供四种波形、三路输出；信号的波形、频率、幅度可 调。 -频率调整：在每个频率段范围内

15、进行频率调整。-波形切换：提供 4 种波形(方波，三角波，正弦波，白噪声)，可通过拨动开关进行选 择。-幅值微调：0 3.3V平滑调整。-信号接插孔：4路A/D输入(ADCIN0-3), 4路D/A输出(DAC0UT1),每路均提供 信号和 地。多种直流电源输出。+5V(5A), +12V(1A), +9V(0.5A)，地。 底板提供插座，可使用插座完成 DSP 评估板上的 A/D 信号输入和 D/A 输出。测试模块：提供14个测试点，可以测量PWM俞出、AD输入和DA输出波形。双信号发生器设计，更加贴近 DSP 的实际应用，许多实际的情况都是需要对两个信号 进 行相关分析。通用 DSP 开发系统部分：USB2.0 接口开发系统，支持 C2000/VC33/C5000/C6000 的开发应用。支持CCS通用开发系统和 DSP 控制板分离，有利于将来 DSP 的升级。同时，也可以脱离实验箱 单 独从事科研开发使用。通用控制模块部分：显示输出：-液晶显示(LCD):128X 64点阵图形显示屏，可调整显示对比度。-发光二极管显示阵列： 8X 8 点阵。-发光二极管。音频输出：可由DSP/O脚控制的蜂鸣器；D/A输出提供音频插座，可直接接插耳机。键 盘： 17 键数字键盘(标准 PS2 接口)。步进电机：四相步进电机，步距角5.625,起动