虚拟信号发生器的设计

学士学位论文 I 摘 要 随着信息技术和计算机技术的高速发展，数字信号处理作为一门新兴的学科，其重要性日益在各个领域的应用中体现出来。本课题是采用虚拟仪器的设计方法对离散信号与系统进行分析与处理，利用 LabVIEW 这一功能强大的虚拟仪器开发工具，设计相关的虚拟仪器，实现相关的功能。 虚拟仪器将传统仪器由硬件实现的数据分析处理与显示功能，改由功能强大的计算机来完成。以这种方式构成的虚拟仪器实质上是计算机仪器系统，是今后仪器发展的主流方向。从某种意义上说， 软件就是仪器 。 本设计内容包括 6 项，分别为： 1、 虚拟信号发生器的设 计，产生各种常见的离散信号。 阐述离散信号发生器的设计原理设计实现。 2、 阐述 快速傅立叶变换 (FFT)的基本原理及实现方法， 着重讨论 FFT 的算法。 3、 离散卷积的实现，讲述了卷积和的计算方法以及离散卷积的实现方法。 4、 虚拟数字滤波器的设计，阐述它的分类、原理以及实现。 5、 离散信号与系统的时域分析与设计， 包括基本原理，设计框图及结果分析。 6、 离散信号与系统的 Z 域分析与设计， 包括基本原理，设计框图及结果分析。 本文主要阐述这六部分的基本原理及虚拟仪器开发的相关程序。 关键词 ： 离散 信号； 虚拟仪器 ； LABVIEW 学士学位论文 II ABSTRACT With the rapid development of information technology and the computer technology, the digital signal processing takes an emerging discipline, its importance displays day by day in each domain application. The topic is to analyze and process to the discrete signal and system with the design method of virtual instrument, adopting the LabVIEW which is a virtual instrument development kit to design the related virtual instrument and to realize the related function. Virtual instrument changes the function of data analysis that the traditional instrument is realized by the tradition hardware to be finished by the computer software with strong function. In fact, the virtual instrument formed by this way is the instrument system of the computer. It is the direction of mainstream in which the instrument will be developed in the future. In a sense, The software is an instrument. This design includes the following 6 parts: 1、 The design of Virtual Signal Generator, it produces various kinds of signals. Expounded discrete signal generator design principle and achieve. 2、 Expounding the basic principles and method of Fast Fourier Transform (FFT) ,focused on the FFT algorithm. 3、 The realization of discrete convolution, introducing convolution and the calculation method and the discrete convolution method. 4、 The Design of Virtual Digital Filter, describing the classification, and the realization of the principle. 5、 Discrete signal and the time-domain analysis and design, including the basic principles of design and analysis diagram. 6、 Discrete signal and the Z-domain analysis and design, including the basic principles of design and analysis diagram. This thesis mainly explains the basic principles of these six parts and the procedure of the virtual instrument design. Keyword: Discrete signal； Virtual instrument； LabVIEW 学士学位论文 III 目 录 1 绪论 . 1 1.1 课题的依据和意义 . 1 1.2 图形化编程语言 LabVIEW. 1 1.2.1 什么是 LabVIEW. 2 1.2.2 LabVIEW 软件的特点与优点 . 2 1.2.3 LabVIEW 的调试与运行 . 2 1.3 虚拟仪器概述 . 3 1.3.1 什么是虚拟仪器 . 3 1.3.2 虚拟仪器的优点 . 4 1.3.3 虚拟仪器的设计方法 . 5 2 信号发生器的设计 . 6 2.1 引言 . 6 2.2 离散信号发生器的设计原理及设计实现 . 6 2.2.1 常用离散信号发生器的设计原理及设计实现 . 6 2.2.2 基于 LabVIEW 的常用信号发生器的虚拟仪器仿真实现 . 11 3 快速傅立叶变换 . 13 3.1 引言 . 13 3.2 快速傅立叶变换的基本原理及实现方法 . 13 3.2.1 直接计算 DFT 的特点及减少运算量的基本途径 . 14 3.2.2 时域抽取法基 2 FFT 基本原理 . 14 3.2.3 DIT-FFT 算法与直接计算 DFT 运算量的比较 . 17 3.3 DIT-FFT 的算法及编程实现 . 18 4 离散卷积 . 25 4.1 引言 . 25 4.2 离散卷积的设计原理 . 25 4.3 离散卷积积分的设计实现 . 26 4.4 离散卷积的应用举例 . 27 5 虚拟数字滤波器的设计 . 28 学士学位论文 IV 5.1 引言 . 28 5.2.1 F1R 滤波器的设计原理 . 28 5.2.2 综合的 FIR 数字滤波器的前面板和相应的框图 . 32 5.3 无限冲激响应（ IIR）数字滤波器 . 34 5.3.1 功能描述及设计原理 . 34 5.3.2 设计步骤 . 35 5.3.3 IIR 数字滤波器的前面板和后面板的设计 . 39 6 离散时间系统的时域分析 . 41 6.1 引言 . 41 6.2 基本原理 . 41 6.3 设计实现 . 42 6.3.1 设计内容 . 42 6.3.2 设计框图及结果分析 . 44 7 离散时间系统的 Z 域分析 . 48 7.1 引言 . 48 7.2 利用系统函数 H(Z)求解离散时间系统的零状态响应 . 48 7.3 离散时间系统的稳定性分析 . 50 结 论 . 53 致 谢 . 54 参考文献 . 55 附录 A 英文原文 . 56 附录 B 汉语翻译 . 64 学士学位论文 1 1 绪论 1.1 课题的依据和意义 随着信息技术和计算 机技术的高速发展，数字信号处理作为一门新兴的学科，其重要性日益在各个领域的应用中体现出来。本课题是采用虚拟仪器的设计方法对离散信号与系统进行分析与处理，利用 LabVIEW 这一功能强大的虚拟仪器开发工具，设计相关的虚拟仪器，实现相关的功能。在虚拟仪器软件平台 LabVIEW 上构建的虚拟滤波器实验系统充分发挥了虚拟仪器优势。其设计思想有广泛的应用范围。虚拟仪器技术的出现彻底打破了传统仪器由厂家定义，用户无法改变的模式，给用户一个充分发挥自己才能、想象力的空间。用户可以根据自己的要求，设计自己的仪器系统，满足多样的 应用需求。 虚拟仪器是全新概念的最新一代测量仪器。自 1987 年诞生以来，这一技术与前几代测试仪器相比，以前所未有的速度迅猛发展。虚拟仪器的功能与计算机技术同步发展。这是因为计算机是虚拟仪器的核心设备，该仪器的功能是通过软件仿真实现的。它将传统仪器由硬件电路实现的数据分析处理与显示功能，改由功能强大的计算机来执行。当计算机与适当的 I/O 接口设备配置完毕，虚拟仪器的硬件平台就被确定，此后软件就称为仪器的关键，也就是 软件就是仪器 之说的来由。这意味着只要按照测量原理，采用适当的信号分析技术与处理技术，编制某种测 量功能的软件就可构成该种功能的测试仪器。虚拟仪器发展的特点是它的队伍宏大，规模壮阔。如果建立了虚拟仪器平台，那么只要按照测量原理，借助信号分析与处理技术编制软件程序，就能自己设计建造自己的测试仪器。 信号分析与处理技术是实现测量功能软件编程的基石。基于数字滤波、快速傅立叶变换等常用信号分析与处理技术，以建造了数字滤波器等各种虚拟仪器。这些仪器是传统观念上的 高级贵族式 仪器。因为它们采用硬件来实现，且电路复杂、昂贵，以往是很难实现的。今天 软件就是仪器 的虚拟仪器时代，使那些 贵族仪器 走出 贵族经院 ，得 到普及。 1.2 图形化编程语言 LabVIEW 本文所选用的软件 LabVIEW 是美国 NI 仪器公司的创新软件产品， LabVIEW 是学士学位论文 2 应用最广泛、发展最快、功能最强的图形化软件开发环境。它具有开发周期短、运行速度快、可重用性、使用方便灵活等优点。 1.2.1 什么是 LabVIEW LabVIEW（ Laboratory Virtual Instrument Engineering Workbench，实验室虚拟仪器工程平台）是美国 NI(National Instrument Company)推出 的一种基于 G 语言（ Graphics Language，图形化编程语言）的虚拟仪器软件开发工具。 用 LabVIEW 设计的虚拟仪器可脱离 LabVIEW 开发环境，最终用户看见的是和实际的硬件仪器相似的操作面板。 1.2.2 LabVIEW 软件的特点与优点 LabVIEW 软件工具的特点可归纳为： （ 1） 图形化的编程方式，无需写任何文本格式的代码，是真正的工程师语言。 （ 2） 提供了丰富的数据采集、分析及存储的库函数。 （ 3） 既提供了传统的程序调试手段，如设置断点、单步运行，同时提供有独到的高亮执行工具，使程序动画式运行，利于设计者 观察程序运行的细节，使程序的调试和开发更为便捷。 （ 4） 32bit 的编译器编译生成 32bit 的编译程序，保证数据采集、测试和测量方案的高速执行。 （ 5） 囊括了 DAQ、 GPIB、 PXI、 VXI 在内的各种仪器通信总线标准的所有功能函数，使得不懂总线标准的开发者也能够驱动不同总线标准接口设备与仪器。 （ 6） 提供大量与外部代码或软件进行连接的机制，诸如 DLLs（动态连接库）、 DDE（共享库）、 ActiveX 等。 1.2.3 LabVIEW 的调试与运行 调试在一个工程中十分重要，在 LabVIEW 中调试是十分方便的。在 LabVIEW 的运行环境中，有一种特有的调试手段，它可以实时显示数据流，它可使用户更加清楚地观察程序运行的每一个细节，为查找错误，修改和优化程序提供了有效的手段和依据。下面简要介绍一下 LabVIEW 程序的调试技术。 学士学位论文 3 （ 1） 找出语法错误 如果一个 VI 程序存在语法错误，则在面板工具条上的运行按钮将会变成一个折断的箭头，表示程序不能被执行。点击箭头， LabVIEW 将弹出错误清单窗口，点击其中任何一个错误，选用 Find 功能，则出错的对象就会变成高亮。 （ 2） 执行程序高亮 在 LabVIEW 的工具条上有一个画着灯泡的按钮， 这个按钮叫 高亮执行 按钮。点击这个按钮使该按钮图标变成高亮形式，再点击运行按钮， VI 程序就以较慢的速度运行，没有被执行的代码用灰色显示，执行后的代码用高亮显示。 （ 3）断点与单步执行 为了查找程序中的逻辑错误，我们可使框图程序逐个节点地执行。使用断点工具可以在程序的某一地点中止程序执行，用探针或单步方式查看数据。 （ 4） 数据探针 我们可以用探针工具来查看当框图程序流经某一根连接线时的数据值。从 Tools 工具模板选择探针工具，再用鼠标左击希望放置探针的连接线。 1.3 虚拟仪器概述 虚拟仪 器是计算机技术和传统的仪器仪表技术相结合的产物 ,它是在以计算机为核心的硬件平台上 ,由用户设计和定义其功能 ,具有虚拟面板 . 虚拟仪器技术具有高效、易用、开放、灵活、更新快、功能强大、性价比高、用户定义等诸多优点 . 目前在我国应用的虚拟仪器开发平台主要有美国 NI 公司的 LabVIEW及其相应组件和 Agilent 公司的HP - VEE ,其中 NI 的 LabVIEW 系列产品在我国使用比较广泛 .LabVIEW是当前用于数据采集、信号处理和虚拟仪器开发的一个标准工具 ,而且是一个基于图形化编程语言的虚拟仪器软件开发工 具 ,设计者可利用它方便快捷地建立自己的虚拟仪器程序而无需复杂的程序代码编写 . 它适用于多种操作系统 ,用 LabVIEW设计的虚拟仪器程序可以脱离LabVIEW开发环境 ,最终用户看见的是和实际的硬件仪器相似的操作面板。 1.3.1 什么是虚拟仪器 所谓虚拟仪器，就是在通用计算机为核心的硬件平台上，由用户设计定义、具有虚拟面板、测试功能由测试软件实现的一种计算机仪器系统。使用者用鼠标点击虚拟面板，就可操作这台计算机系统硬件平台，就如同使用一台专用测量仪器一样。 学士学位论文 4 虚拟仪器的 虚拟 二字主要包含以下两个方面的含义： 第一， 虚拟仪器的面板是虚拟的。 虚拟仪器面板上的各种 控件 与传统仪器面板上的各种 器件 所完成的功能是相同的。如由各种开关、按键、显示器等实现仪器电源的： 通 、 断 ；被测信号的 输入通道 、 放大倍数 等参数的设置；测量结果的 数值显示 、 波形显示 等。传统仪器面板上的器件都是 实物 ，而且是由 手动 、 触摸 、来进行操作的，而虚拟仪器面板控件是外形与实物相象的 图标 ，每个图标的 通 、 断 、 放大 等，对应着相应的软件程序。这些软件已经设计好，我们只需选用代表该种软件程序的图形 控件 即可。因此 ，设计虚拟仪器前面板 ,就是在前面板设计窗口中摆放所需的图标，然后对图标的属性进行设置。 第二， 虚拟仪器测量功能是通过对图形化软件流程图的编程来实现的。 以 PC 计算机为核心组成的硬件平台支持下，通过软件编程来实现仪器的功能的。因为可以通过不同测试功能软件模块的组合来实现多种测试功能，所以，在硬件平台确定后，就有 软件就是仪器 的说法。 1.3.2 虚拟仪器的优点 虚拟仪器最突出的特点之一是用户能够自己定义仪器功能。用户之所以能够根据自己的需要随心所欲地定义仪器功能，是由于虚拟仪器开发软件的灵活性。虚拟仪器中的仪器 卡主要用于数据的采集、输入和生成，至于如何去控制仪器卡的工作，怎样进行数据处理，以及生成什么样的仪器面板等，这些工作都是由软件完成的。一台虚拟仪器性能的好坏，在很大程度上取决于软件水平的高低。因此有人认为，对虚拟仪器系统而言，“软件就是仪器”。 虚拟仪器的硬、软件都具有开放性、模块化、可重复使用及互换性等特点。因此，用户可以根据自己的需要灵活组建仪器，这样大大提高了使用仪器的效率，减少了投资，克服了传统仪器的缺点。 综上所述，虚拟仪器一般具有以下的性能特点： （ 1）用户定义测量功能。虚拟仪器是一种软件化的 测量装置，软件的灵活性和复用性使用户可以按自己的需要定义（设置）测量功能。 （ 2）便于组成自动测试系统。结构与组成的模块化和规范化，为虚拟仪器组建自动测试系统提供了极大便利。人们只要在计算机主机箱或扩展机箱的插槽内插入所需的仪器卡，就组成了所需的自动测试系统。 学士学位论文 5 （ 3）减少了开关和电缆。由于所有信号具有一个公用的量化通道，故允许各种测量使用同一校准和修正因子，这样就减少了复杂的开关矩阵和信号电缆。 （ 4）强大的数据处理功能。信号处理理论的不断完善以及计算机运算速度的大大提高，为虚拟仪器快速、准确处理数据 提供了良好基础。 （ 5）系统组建时间短。模块化的仪器卡支持相同的公用硬件平台。当希望测试系统增加一个新的测量功能时，只需增加软件来执行新的功能或增加一个通用模块来扩展系统的测量范围。因此，缩短了系统的组建时间。 （ 6）便于扩展。为提高测试系统的性能，可以方便地加入一通用仪器卡或更换一仪器卡（而不用购买一个新的系统），这样有利于系统的扩展。 （ 7）测量速度高。测量输入信号的多个特性（如电压、频率、上升时间）只需一个量化的数据模块，这种将多种测试集于一体的方法缩短了测试时间，从而提高了测试速度。 （ 8） 有更好的测量准确度和可重复性。在传统的自动测试系统中，必须把信号连接到每一台仪器上以完成对各种参数的测量。这样，测量往往受电缆长度、阻抗、仪器校准和修正因子差异等的影响。而虚拟仪器受这些因素的影响较小，从而提高了测量的准确度和可重复性。 （ 9）技术更新快。由于虚拟仪器技术是建立在当今世界最新的计算机技术、数据采集技术和通信技术基础上的，因而技术更新速度快于传统仪器。 1.3.3 虚拟仪器的设计方法 虚拟仪器的设计方法包括以下三个部分： （ 1）仪器前面板的设计 仪器前面板的设计主要是指在虚拟仪 器开发平台上，利用各类子模板图标创建用户界面，即虚拟仪器的前面板。 （ 2）仪器流程和算法的设计 仪器流程和算法的设计主要是指根据仪器功能要求，利用虚拟仪器开发平台所提供的各类子模板，确定程序的流程图、主要处理算法和所实现的技术方法。 （ 3） I/O 接口仪器驱动程序的设计 根据仪器的功能要求，确定仪器的接口标准。 I/O 接口仪器驱动程序是控制硬件设备的驱动程序，是连接主控计算机与仪器设备的纽带。如果没有设备驱动程序，则必须针对 I/O 接口仪器设备编写驱动程序。 学士学位论文 6 2 信号发生器的设计 2.1 引言 自然界各种各样 的物质是千差万别的，信号也是千差万别的 。所谓信号，是信息的物理表现形式，或者说是传递信息的函数。根据载体的不同，信号可以是电的、磁的、声的、光的、热的等各种信号。信号可从不同的角度进行分类，有确定信号与随机信号、周期信号与非周期信号、连续时间信号与离散时间信号、一维信号与多维信号等。 按照时间信号函数取值的连续性与离散性可将信号划分为连续时间信号与离散时间信号。下面重点讲述一下离散时间信号的发生过程。 2.2 离散信号发生器的设计原理及设计实现 根据传统信号发生器面板控键的功能，利用 LABVIEW 中的控 制模板，分别在设计面板上放入模拟实际信号发生器控键的数据输入控键、显示器、数据输出控件、开关、选择器 . 显示器用于显示输出的信号波形 ,数据输入控键用于输出信号的信号频率、采样频率、采样数、振幅和相位 ,数据输出控键则用于选择信号类型 . 当只需要一定信号波形发生和显示时，可以利用 G 语言编程得到虚拟仪器，即用软件实现硬件的功能。 LabVIEW 公式运算节点 (formula node)是一种传统的基于文字输入的节点，用于 Block Diagram 里。用户进行数学运算时，就像在验算纸上写字一样输入函数公式 ，再 加上显示部分即可实现函数波形显示，即用公式实现的函数发生与显示的程序，其中内部粗框为公式节点 ，在公式节点边框上单击鼠标右键分别添加输入变量和输出变量。输入变量可根据用户需求自己设置。在前面板输入振幅变量等的具体数值，通过图形显示 Waveform Graph 控件来显示波形。对应程序前面板即虚拟仪器前面板中输入相应的变量，运行即可得到所需的波形。因此，用公式节点来产生波形非常方便，一些不易获得的被测数据都可以用此法进行测量和显示。 2.2.1 常用离散信号发生器的设计原理及设计实现 信号发生器 是一种应用极为广泛的仪器，它通常作为标准信号发生器，用于电子电路的性能试验或参数测量。传统的信号发生器价格昂贵，操作复杂，不易开发，维护和升级，而使用基于 LABVIE 图形化编程语言开发的虚拟信号发生器，具有编程简单，直学士学位论文 7 观，操作方便等特点。而且，可以通过不同的信号。 1 单位样值序列 （ 2.1） 此序列只在 n=0 处取单位值 1，其余样点上都为零，也称为 单位取样 、 单位函数 、单位脉冲 或 单位冲激 。它在离散时间系统中的作用，类似于连续时间系统中的 单位冲激函数 )t( 。 图 2.1 单位样值序列的图形 图 2.2 单位样值序列的框图 2 单位延迟阶跃序列 01)n(u nNnN( 2.2 ) 类似于连续时间系统中的单位阶跃信号 u(t)。 图 2.3 单位 延迟阶跃序列的图形 1000() nnn 学士学位论文 8 图 2.4 单位延迟阶跃序列的框图 3. 矩形序列 01)n(R N( 1 1 )( 1 , )M n Nn M n N ( 2.3 ) 它从 n=M-1 开始，到 n=N-1，共有 N-M 个幅度为 1 的数值，其余各点皆为零。类似于连 续时间系统中的矩形脉冲。 显然，矩形序列取值为 1 的范围也可以 n=m 到n=m+N-1。这种序列可写作 )mn(RN 。 图 2.5 矩形序列的图形 图 2.6 矩形序列的框图 4正弦序列 x（ n） =sin(n0) ( 2.4 ) 式中0是正弦序列的频率，它反映序列值依次周期性重复的速率。 学士学位论文 9 图 2.7 正弦序列的图形 图 2.8 正弦序列的框图 5 指数序列 x(n)= )n(uan ( 2.5 ) 当 a 1 时序列是发散的， a 0 序列都取正值， a Wavefovmgraph ,作为信号发生器的显示器 。 在显示器模板上点击鼠标右键 ,对其进行属性设置 ,如根据被显示波形的频率与幅度值的变化 ,利用工具模板中的文字工具 ,对显示器横 (时间 ) 、纵 (幅度 ) 坐 标的刻度重新设置 . 用 Graph 控键设计的显示器是完全同步的 ,波形稳定 。编制各种信号的过程中，应尽量采用模块化编程的思想，建立子 VI，这样可以简化 VI 框图程序的结构，使其更加简洁，易于理解，以提高 VI 的运行效率。 下面是常用信号发生器的前面板图形和程序框图 ,只要我们在前面板的信号类型和请选择信号中选择一种 ,就能显示出所选信号的波形。 图 2.13 常用信号发生器的前面板图形 学士学位论文 12 图 2.14 常用信号发生器的程序框图 程序中各控件功能： （ 1） 选择输出，当输入 s 值为 ture 时，节点将输入端口 t 中的内容送 至输出端口；当输入 s 值为 false 时，节点将输入端口 f 中的内容送至输出端口。 （ 2） for 循环由循环框架， 重复端口， 计数端口组成。 （ 3） 移位寄存器，功能是将第 i-1， i-2 次循环的结果保存在 for 循环的缓冲区内，并在第 i 次循环时将这些数据从循环框架左侧的移位寄存器中送出，供循环框架内的节点使用。 （ 4） 正弦波 （ 5） 真常量， 假常量。布尔常数，在编辑状态下，用数据操作工具单击节点图标可改变布尔常数的值。 （ 6） Bundle 打包 .将相互关联的不同数据类型的数据组成一个簇 ,或给簇 中的某一个元素赋值。 学士学位论文 13 3 快速傅立叶变换 3.1 引言 快速傅氏变换（ FFT）是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。 设 x(n)为 N 项的复数序列，由 DFT 变换，任一 X（ m）的计算都需要 N 次复数乘法和 N-1 次复数加法，而一次复数乘法等于四次实数乘法和两次实数加法，一次复数加法等于两次实数加法，即使把一次复数乘法和一次复 数加法定义成一次 运算 （四次实数乘法和四次实数加法），那么求出 N 项复数序列的 X（ m） ,即 N 点 DFT 变换大约就需要 N2 次运算。当 N=1024 点甚至更多的时候，需要 N2=1048576 次运算，在 FFT 中，利用 knw的周期性和对称性，把一个 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%的运算量。而如果我们将这种 一分为二 的思想不断进行下去，直到分成两两一组的 DFT运算单元，那么 N 点的 DFT 变换就只需要 Nlog2N 次的运算， N 在 1024 点时，运算量仅有 10240 次，是先前的直接算法的 1%，点数越多，运算量的节约就越大，这就是 FFT的优越性。 3.2 快速傅立叶变换的基本原理及实现方法 FFT 算法的基本思想 :可以将一个长度为 N 的序列的离散傅里叶变换逐次分解为较短的离散傅里叶变换来计算，这些短序列的 DFT 可重新组合成原序列的 DFT，而总的运算次数却比直接的 DFT 运算量少得多，从而达到提高速度的目的。 快速傅立叶变换就是利用 knw的特性，逐步地将 N 点序列分解成较短的序列，计算短序列的 DFT,然后组合成原序列的 DFT，使运算量显著减少。这种分解基本上可分为两类，一类是将时间序列 x(n)进行逐次分解，称为按时间抽取算法 (Decimation In Time);另一类将傅立叶变换序列 X(k)进行分解，称为按频率抽取算法 (Decimation In Frequency)。本文主要介绍了按时间抽取基 2 FFT 算法。 学士学位论文 14 3.2.1 直接计算 DFT 的特点及减少运算量的基本途径 长度为 N 的有限长序列 x(n)的 DFT 为 (3.1) 考虑 x(n)为复数序列的一般情况 ,对某一个 k 值 ,直接按 (3.1)式计算 X(k)的值需要 N 次复数乘法、 (N-1)次复数加法。因此 ,对所有 N 个 k 值 ,共需 2N 次复数乘法及 N(N-1)次复数加法运算。当 N1 时 ,N(N-1) 2N 。由上诉可见 ,N 点 DFT 的乘法和加法运算次数均成正比。当 N 较大时 ,运算量相当可观。例如 N=1024 时 , 2N =1048576。这对于要求实时信号处理来说 ,必将对计算速度提出难以实现的要求。所以 ,必须减少其运算量 ,才能使 DFT 在各种科学和工程计算中得到应用。 如前所述 ,N 点 DFT 的复乘次数等于 2N ,显然 ,把 N 点 DFT 分解为几个较短的 DFT,可使乘法次数大大减少。另外 ,旋转因子 mNW具有明显的周期性和对称性 .其周期性表现为 mNmN2j)lNm(N2jlNmN WeeW (3.2) 其对称性表现为 mNmN WW 或者 mNmNN WW (3.3) mN2NmN WW FFT 算法就是不断地把长序列的 DFT 分解成几个短序列的 DFT,并利用 knNW的周期性和对称性来减少 DFT 的运算次数。最常用的是基 2FFT(即 N= M2 的 FFT)。 3.2.2 时域抽取法基 2 FFT 基本原理 设序列 x(n)的长度为 N,且满足 ,2N M M 为自然数 按 n 的奇偶把 x(n)分解为两个 N/2 点的子 序列 ),r2(x)r(x 1 12N,.,1,0r ),1r2(x)r(x 2 12N,.,1,0r 且 x(n)的 DFT 为 10( ) ( ) , 0 , 1 , . . . , 1N knNnX k x n W k N ( ) ( ) ( )k n k nNNnnX k x n W x n W偶 数 奇 数学士学位论文 15 由于 kr 2/Nkr2N2jkr2N2jkr2N WeeW 所以 )k(XW)k(XW)r(xWW)r(x)k(X 2kN112/N0rkr 2/N2kN12/N0rkr 2/N1 1N,.,1,0k （ 3.4） 其中 )k(X1 和 )k(X2 分别为 )k(x1 和 )k(x2 的 N/2 点 DFT,即 )r(xD F TW)r(x)k(X112/N0rkr 2/N11 （ 3.5） )r(xD F TW)r(x)k(X 212/N0rkr 2/N22 （ 3.6） 由于 )k(X1 和 )k(X2 均以 N/2 为周期 ,且 kN2NkN WW ,所以 X(k)又可表示为 )k(XW)k(X)k(X2kN1 , 12N,.,1,0k （ 3.7） )k(XW)k(X)2Nk(X 2kN1 , 12N,.,1,0k （ 3.8） 这样 ,就将 N 点 DFT 分解为两个 N/2 点的 DFT 和 (3.7)式以及 (3.8)式的运算。 (3.7)式和 (3.8)式的运算可用图 3.1 所示的流图符号表示 ,根据其形状称之为蝶形运算符号 .采用这种图示法 ,可将上述分解运算表示于图 3.2 中 ,图中 ,N=23=8,X(0)X(3)由 (3.7)式给出 ,而X(4)X(7)则由 (3.8)式给出 10。 图 3.1 蝶形运算符号 图 3.2 N 点 DFT 的一次时域抽取分解图 (N=8) / 2 1 / 2 12 ( 2 1 )00( 2 ) ( 2 1 )NNk r k rNNrrx r W x r W / 2 1 / 2 1221200( ) ( )NNk r k k rN N Nrrx r W W x r W学士学位论文 16 由图 3.1