毕业设计（论文）-基于FPGA的FFT算法实现.doc

毕业论文 基于基于 FPGAFPGA 的的 FFTFFT 算法实现算法实现 摘要 快速傅立叶变换快速傅立叶变换(FFT)(FFT)作为时域和频域转换的基本运算，是数字谱分析的必要前提。传统的作为时域和频域转换的基本运算，是数字谱分析的必要前提。传统的 FFTFFT 使用软使用软 件或件或 DSPDSP 实现，高速处理时实时性较难满足。实现，高速处理时实时性较难满足。FPGAFPGA 是直接由硬件实现的，其内部结构规则简单，通常可以容纳很多是直接由硬件实现的，其内部结构规则简单，通常可以容纳很多 相同的运算单元，因此相同的运算单元，因此 FPGAFPGA 在作指定运算时，速度会远远高于通用的在作指定运算时，速度会远远高于通用的 DSPDSP 芯片。芯片。FFTFFT 运算结构相对比较简单和固定，运算结构相对比较简单和固定， 适于用适于用 FPGAFPGA 进行硬件实现，并且能兼顾速度及灵活性。本文介绍了一种通用的可以在进行硬件实现，并且能兼顾速度及灵活性。本文介绍了一种通用的可以在 FPGAFPGA 上实现上实现 512512 点点 FFTFFT 变换变换 的方法。主要对的方法。主要对 quartusquartus IIII 中的中的 ramram，romrom，fftfft，基本运算等宏模块进行调用。并且通过，基本运算等宏模块进行调用。并且通过 vgavga 控制模块，和键盘等控制模块，和键盘等 控制模块，实现对信号的产生和频谱的测量和显示等工作。实验果表明，设计完成的系统能够在保证运算精度和实控制模块，实现对信号的产生和频谱的测量和显示等工作。实验果表明，设计完成的系统能够在保证运算精度和实 现复杂度的同时，切实可行地完成设计的总体要求。现复杂度的同时，切实可行地完成设计的总体要求。 关键词FPGAFPGA；VGAVGA ；FFTFFT；ipip 核核 Implementation of FFT algorithm based on FPGA Abstract: Fast Fourier Transform (FFT) as a time domain and the frequency domain conversion of the basic operation, the digital spectrum analysis prerequisite. The traditional FFT implemented using software or DSP, real- time high-speed processing more difficult to meet. FPGA is a direct hardware implementation, and its internal structure rules are simple, you can usually accommodate many of the same arithmetic unit, thus making the assignment operator FPGA, the speed will be much higher than the general-purpose DSP chips. FFT operation is relatively simple and fixed structure, suitable for hardware implementation using FPGA and can both speed and flexibility. This paper describes a generic that can be implemented on FPGA 512-point FFT transform method. Mainly quartus II of ram, rom, fft, basic operations such as macro block calls. And through vga control module, and keyboard control module enables the signal generation and spectrum measurement and display work. Experimental results show that the design is completed the system to ensure the accuracy and computing implementation complexity while practicable to complete the design of the overall requirements. Key words: FPGA; VGA; FFT; ip nuclear 目录目录 1 1 引言引言.1 2 2 设计原理设计原理.3 2.12.1 基基 2-FFT2-FFT 算法原理算法原理.3 2.22.2 基基 4-FFT4-FFT 算法原理算法原理 .8 2.32.3 IPIP 核实现原理核实现原理 .8 3 3 FFTFFT 设计实现设计实现.13 3.13.1 总体结构设计总体结构设计.13 3.2 FFT IPCORE的建立的建立.14 3.33.3 测试信号的产生测试信号的产生.18 3.3.13.3.1 ddsdds 原理原理.18 3.3.23.3.2 ddsdds 的实现的实现.18 3.3.33.3.3 测试信号的仿真测试信号的仿真.19 3.43.4 显示模块设计显示模块设计.19 3.4.13.4.1 vgavga 显示原理显示原理.19 3.4.23.4.2 vgavga 的实现的实现.22 3.4.33.4.3 vgavga 的仿真测试的仿真测试.23 3.53.5 存储单元设计存储单元设计 .23 4 4 系统调试系统调试.25 4.1 安装安装 BYTEBLASTER II 下载电缆下载电缆.25 4.1.14.1.1 驱动程序安装驱动程序安装.25 4.1.24.1.2 硬件下载硬件下载.26 4.1.34.1.3 软件实现过程软件实现过程.26 4.24.2 FFTFFT 算法测试算法测试 .29 4.2.1 正弦信号的正弦信号的 FFTFFT 测试测试.29 4.2.24.2.2 方波信号的方波信号的 FFTFFT 测试测试.30 总结与展望总结与展望.32 致谢致谢.33 参考文献参考文献.34 附录附录.35 源程序源程序.41 1 1 引言引言 在数字化高速发展的今天，对数字信号处理高速实时的要求也不断提高。因此为了满足这些要在数字化高速发展的今天，对数字信号处理高速实时的要求也不断提高。因此为了满足这些要 求，国内外都在研究实现数字信号处理的新方法，本论文主要研究基于求，国内外都在研究实现数字信号处理的新方法，本论文主要研究基于 FPGAFPGA 的方法来实现的方法来实现 FFTFFT 算算 法，并通过对算法结构的内部优化设计使其相较于传统的实现方法更具优势。法，并通过对算法结构的内部优化设计使其相较于传统的实现方法更具优势。 FPGA 技术的五大优势技术的五大优势 （1 1）性能：利用硬件并行的优势，）性能：利用硬件并行的优势，FPGAFPGA 打破了顺序执行的模式，在每个时钟周期内完成更多打破了顺序执行的模式，在每个时钟周期内完成更多 的处理任务，超越了数字信号处理器（的处理任务，超越了数字信号处理器（DSPDSP）的运算能力。）的运算能力。 著名的分析与基准测试公司著名的分析与基准测试公司 BDTIBDTI，发，发 布基准表明在某些应用方面，布基准表明在某些应用方面，FPGAFPGA 每美元的处理能力是每美元的处理能力是 DSPDSP 解决方案的多倍。解决方案的多倍。2 2 在硬件层面控制输在硬件层面控制输 入和输出（入和输出（I/OI/O）为满足应用需求提供了更快速的响应时间和专业化的功能。）为满足应用需求提供了更快速的响应时间和专业化的功能。 （2 2）上市时间：尽管上市的限制条件越来越多，）上市时间：尽管上市的限制条件越来越多，FPGAFPGA 技术仍提供了灵活性和快速原型的能力。技术仍提供了灵活性和快速原型的能力。 用户可以测试一个想法或概念，并在硬件中完成验证，而无需经过自定制用户可以测试一个想法或概念，并在硬件中完成验证，而无需经过自定制 ASICASIC 设计漫长的制造过设计漫长的制造过 程。程。3 3 由此用户就可在数小时内完成逐步的修改并进行由此用户就可在数小时内完成逐步的修改并进行 FPGAFPGA 设计迭代，省去了几周的时间。设计迭代，省去了几周的时间。 商用商用 现成（现成（COTSCOTS）硬件可提供连接至用户可编程）硬件可提供连接至用户可编程 FPGAFPGA 芯片的不同类型的芯片的不同类型的 I/OI/O。 高层次的软件工具的日高层次的软件工具的日 益普及降低了学习曲线与抽象层，并经常提供有用的益普及降低了学习曲线与抽象层，并经常提供有用的 IPIP 核（预置功能）来实现高级控制与信号处核（预置功能）来实现高级控制与信号处 理。理。 （3 3）成本：自定制）成本：自定制 ASICASIC 设计的非经常性工程（设计的非经常性工程（NRENRE）费用远远超过基于）费用远远超过基于 FPGAFPGA 的硬件解决方案的硬件解决方案 所产生的费用。所产生的费用。 ASICASIC 设计初期的巨大投资表明了原始设备制造商每年需要运输数千种芯片，但更设计初期的巨大投资表明了原始设备制造商每年需要运输数千种芯片，但更 多的最终用户需要的是自定义硬件功能，从而实现数十至数百种系统的开发。多的最终用户需要的是自定义硬件功能，从而实现数十至数百种系统的开发。 可编程芯片的特性可编程芯片的特性 意味着用户可以节省制造成本以及漫长的交货组装时间。意味着用户可以节省制造成本以及漫长的交货组装时间。 系统的需求时时都会发生改变，但改变系统的需求时时都会发生改变，但改变 FPGAFPGA 设计所产生的成本相对设计所产生的成本相对 ASCIASCI 的巨额费用来说是微不足道的。的巨额费用来说是微不足道的。 （4 4）稳定性：软件工具提供了编程环境，）稳定性：软件工具提供了编程环境，FPGAFPGA 电路是真正的编程电路是真正的编程“硬硬”执行过程。执行过程。 基于处基于处 理器的系统往往包含了多个抽象层，可在多个进程之间计划任务、共享资源。理器的系统往往包含了多个抽象层，可在多个进程之间计划任务、共享资源。 驱动层控制着硬件驱动层控制着硬件 资源，而操作系统管理内存和处理器的带宽。资源，而操作系统管理内存和处理器的带宽。 对于任何给定的处理器内核，一次只能执行一个指对于任何给定的处理器内核，一次只能执行一个指 令，且基于处理器的系统时刻面临着严格限时的任务相互取占的风险。令，且基于处理器的系统时刻面临着严格限时的任务相互取占的风险。 而而 FPGAFPGA 不使用操作系统，不使用操作系统， 拥有真正的并行执行和专注于每一项任务的确定性硬件，可减少稳定性方面出现问题的可能。拥有真正的并行执行和专注于每一项任务的确定性硬件，可减少稳定性方面出现问题的可能。 （5 5）长期维护：正如上文所提到的，）长期维护：正如上文所提到的， FPGAFPGA 芯片是现场可升级的，无需重新设计芯片是现场可升级的，无需重新设计 ASICASIC 所涉及所涉及 的时间与费用投入。的时间与费用投入。 举例来说，数字通信协议包含了可随时间改变的规范，而基于举例来说，数字通信协议包含了可随时间改变的规范，而基于 ASICASIC 的接口可的接口可 能会造成维护和向前兼容方面的困难。能会造成维护和向前兼容方面的困难。 可重新配置的可重新配置的 FPGAFPGA 芯片能够适应未来需要作出的修改。芯片能够适应未来需要作出的修改。 随着产品或系统成熟起来，用户无需花费时间重新设计硬件或修改电路板布局就能增强功能。随着产品或系统成熟起来，用户无需花费时间重新设计硬件或修改电路板布局就能增强功能。 快速傅立叶变换快速傅立叶变换(FFT)(FFT)是是 DFTDFT 的快速算法的快速算法, ,是数据从时域到频域变换的基本运算。它是频谱分析是数据从时域到频域变换的基本运算。它是频谱分析 的必要前提，是数字信号处理的核心工具之一。所以的必要前提，是数字信号处理的核心工具之一。所以 FFTFFT 在众多学科领域，例如数字语音编码、雷在众多学科领域，例如数字语音编码、雷 达信号处理、声纳信号分析、数字滤波、射电干涉等都有着十分广泛的应用。尤其是在要求较高的达信号处理、声纳信号分析、数字滤波、射电干涉等都有着十分广泛的应用。尤其是在要求较高的 信号处理系统中，信号处理系统中，FFTFFT 的处理速度往往是整个系统设计性能的关键。的处理速度往往是整个系统设计性能的关键。 软件实现软件实现 FFTFFT 运算速度慢，无法满足实时高速的系统性能要求。硬件实现运算速度慢，无法满足实时高速的系统性能要求。硬件实现 FFTFFT 的方式主要有三的方式主要有三 种：通用数字信号处理器种：通用数字信号处理器(DSP)(DSP)、专用的、专用的 FFTFFT 芯片芯片(ASIC)(ASIC)、可编程逻辑器件、可编程逻辑器件( (以以 FPGAFPGA 为代表为代表) )。采用。采用 DSPDSP 方案通过软件编程来实现运算，虽然灵活性强，但是受到方案通过软件编程来实现运算，虽然灵活性强，但是受到 DSPDSP 本身性能及程序指令顺序执行的本身性能及程序指令顺序执行的 限制难以实现高速、大规模的限制难以实现高速、大规模的 FFTFFT 运算，同时也存在速度和精度之间的矛盾：若采用定点运算，舍运算，同时也存在速度和精度之间的矛盾：若采用定点运算，舍 入误差会降低最终处理结果的精度；若采用浮点运算，可以消除动态范围局限的问题，但由于实现入误差会降低最终处理结果的精度；若采用浮点运算，可以消除动态范围局限的问题，但由于实现 结构复杂使处理速度难以达到要求，而且系统造价较高。采用结构复杂使处理速度难以达到要求，而且系统造价较高。采用 ASICASIC 芯片虽然可以达到较高的处理芯片虽然可以达到较高的处理 速度，但是灵活性差，特别是使用定制的大规模集成电路的时候，需要较高的开发和研制费用，不速度，但是灵活性差，特别是使用定制的大规模集成电路的时候，需要较高的开发和研制费用，不 易扩展。随着超大规模可编程门阵列的迅速发展，新一代易扩展。随着超大规模可编程门阵列的迅速发展，新一代 FPGAFPGA 内部有高速数字信号处理内部有高速数字信号处理(DSP)(DSP)模块模块 和大容量、高速和大容量、高速 RAMRAM 模块，这为利用模块，这为利用 FPGAFPGA 实现实现 FFTFFT 处理成为可能，既避免了软件方式所带来的速处理成为可能，既避免了软件方式所带来的速 度方面的限制，又可以降低开发的成本和周期，是一种较为理想的开发方式。度方面的限制，又可以降低开发的成本和周期，是一种较为理想的开发方式。FPGAFPGA 以高性能、高以高性能、高 灵活性、友好的开发环境、在线可编程等特点可以使基于灵活性、友好的开发环境、在线可编程等特点可以使基于 FPGAFPGA 的设计满足实时数字信号处理的要的设计满足实时数字信号处理的要 求。求。 高速实时数字信号处理对系统性能要求甚高，因此，几乎所有的通用高速实时数字信号处理对系统性能要求甚高，因此，几乎所有的通用 DSPDSP 都难以实现这一要求。都难以实现这一要求。 可编程逻辑器件允许设计人员利用并行处理技术实现高速信号处理算法，并且只需单个器件就能实可编程逻辑器件允许设计人员利用并行处理技术实现高速信号处理算法，并且只需单个器件就能实 现期望的性能。在数据通信这样的应用中，常常需要进行高速、大规模的现期望的性能。在数据通信这样的应用中，常常需要进行高速、大规模的 FFTFFT 及其逆变换及其逆变换 IFFTIFFT 运运 算。当通用的算。当通用的 DSPDSP 无法达到速度要求时，唯一的选择是增加处理器的数目，或者采用定制门阵列产无法达到速度要求时，唯一的选择是增加处理器的数目，或者采用定制门阵列产 品。现在，随着微电子技术的发展，采用现场可编程门阵列品。现在，随着微电子技术的发展，采用现场可编程门阵列(FPGA)(FPGA)进行数字信号处理发展迅猛。采进行数字信号处理发展迅猛。采 用现场可编程器件不仅加快了产品上市时间，还可满足现在和下一代便携式设计所需要的成本、性用现场可编程器件不仅加快了产品上市时间，还可满足现在和下一代便携式设计所需要的成本、性 能、尺寸等方面的要求，并提供系统级支持。能、尺寸等方面的要求，并提供系统级支持。FPGAFPGA 是直接由硬件实现的，其内部结构规则简单，是直接由硬件实现的，其内部结构规则简单， 通常可以容纳很多相同的运算单元，因此通常可以容纳很多相同的运算单元，因此 FPGAFPGA 在作指定运算时，速度会远远高于通用的在作指定运算时，速度会远远高于通用的 DSPDSP 芯片。芯片。 FFTFFT 运算结构相对而言比较简单和固定，适于用运算结构相对而言比较简单和固定，适于用 FPGAFPGA 进行硬件实现，并且能兼顾其速度及灵活性。进行硬件实现，并且能兼顾其速度及灵活性。 而采用而采用 DSPDSP 方式有很大的浪费，同时方式有很大的浪费，同时 DSPDSP 芯片内部的乘法器资源十分有限，芯片内部的乘法器资源十分有限，FFTFFT 算法中乘法量较大，算法中乘法量较大， 在实现实时处理方案时必须使用多个在实现实时处理方案时必须使用多个 DSPDSP 芯片，从而提高了价格、增加了功耗和体积。而选择内部芯片，从而提高了价格、增加了功耗和体积。而选择内部 嵌有多个乘法器内核的嵌有多个乘法器内核的 FPGAFPGA 芯片就可以很轻易地消除这一严重的资源浪费现象。尤其是近年来，芯片就可以很轻易地消除这一严重的资源浪费现象。尤其是近年来， 高密度的可编程逻辑器件高密度的可编程逻辑器件 FPGAFPGA 的集成度、速度不断提高，设计、调试手段更加完善，因而得到更的集成度、速度不断提高，设计、调试手段更加完善，因而得到更 为广泛的应用。为广泛的应用。 本论文就是在这样一个背景下提出一种基于本论文就是在这样一个背景下提出一种基于 FPGAFPGA 的的 512512 点基点基 2-FFT2-FFT 算法的具体实现方法。旨算法的具体实现方法。旨 在设计出用在设计出用 FPGAFPGA 实现的、具有高速特点的、可实现定点实现的、具有高速特点的、可实现定点 FFTFFT 运算的运算的 IPIP 核，从而满足系统要求。核，从而满足系统要求。 2 2 设计原理设计原理 2.12.1 基基 2-FFT2-FFT 算法算法原理原理 长度为长度为 N N 的有限长序列的有限长序列 x(n)x(n)的的 DFTDFT 的表达式为的表达式为 (2-1)(2-1)1.1 , 0,)()( 1 0 NkWnxkX N n kn N x(n)x(n)在一般情况下是为复数序列的。如果直接按在一般情况下是为复数序列的。如果直接按(2-1)(2-1)式计算式计算 X(k)X(k)值，那么对于某一个值，那么对于某一个 k k 值而言值而言, , 需要需要 N N 次复数乘法和次复数乘法和(N-1)(N-1)次复数加法。那么对于次复数加法。那么对于 N N 个个 k k 值，一共需要值，一共需要 N(N-1)N(N-1)次复数加法运算。当次复数加法运算。当 N1N1 时，时，N(N-1)N(N-1)。从上面的说明中可以看出，。从上面的说明中可以看出，N N 点点 DFTDFT 的乘法和加法运算次数均与成正比。当的乘法和加法运算次数均与成正比。当 N N 较大时，运算量是十分庞大的。如果较大时，运算量是十分庞大的。如果 N N 取取 3232，那么将达到，那么将达到 10241024。如此巨大的计算量对于实时信号。如此巨大的计算量对于实时信号 处理来说其运算速度是难以达到的。所以要想使得处理来说其运算速度是难以达到的。所以要想使得 DFTDFT 在各种科学和工程计算中得到广泛的应用就在各种科学和工程计算中得到广泛的应用就 必须想办法减少其运算量。必须想办法减少其运算量。 在前面已经讲到，在前面已经讲到，N N 点点 DFTDFT 的复乘次数等于。其实一个的复乘次数等于。其实一个 N N 点点 DFTDFT 可以看做是由几个较短的可以看做是由几个较短的 DFTDFT 组成的。基于这一思想，可以将组成的。基于这一思想，可以将 N N 点点 DFTDFT 分解为几个较短的分解为几个较短的 DFTDFT，这样一来乘法次数将大大减少，这样一来乘法次数将大大减少， 能够非常明显地降低能够非常明显地降低 DFTDFT 的运算量。此外，旋转因子具有明显的周期性和对称性。其周期性表现为：的运算量。此外，旋转因子具有明显的周期性和对称性。其周期性表现为： （2-2） 22 ()jm lNjm m lNm NN NN WeeW 其对称性表现为其对称性表现为 （2-32-3） 不断的把长序列的不断的把长序列的 DFTDFT 分解成几个短序列的分解成几个短序列的 DFTDFT，并且利用的周期性和对称性来减少，并且利用的周期性和对称性来减少 DFTDFT 的运的运 算次数，这就是算次数，这就是 FFTFFT 算法的基本思想。比较常用的算法的基本思想。比较常用的 FFTFFT 算法有基算法有基-2-2 FFTFFT 和基和基 4FFT4FFT 两种。基两种。基-2-2 FFTFFT 中的基中的基 2 2 指的是指的是 N=N=，即有限长序列的长度，即有限长序列的长度 N N 要到等于要到等于 2 2 的整数次幂。下面就以的整数次幂。下面就以 8 8 点的点的 FFTFFT 为例详为例详 细分析基细分析基-2-2 FFTFFT 算法。算法。 2.1.12.1.1 基基-2-2 FFTFFT 算法基本原理算法基本原理 基基-2-2 FFTFFT 算法基本上分为时域抽取法算法基本上分为时域抽取法 FFT(DIT-FFT)FFT(DIT-FFT)和频域抽取法和频域抽取法 FFT(DIF-FFT)FFT(DIF-FFT)两大类。由于两大类。由于 这两种算法的基本原理是相同的，所以下面主要介绍这两种算法的基本原理是相同的，所以下面主要介绍 DIT-FFTDIT-FFT 算法。本课题采用的就是算法。本课题采用的就是 DIT-FFTDIT-FFT 这这 一算法。一算法。 设序列设序列 x(n)x(n)的长度为的长度为 N N，并且有以下的条件成立，并且有以下的条件成立 ,M,M 为自然数为自然数 (2-4)(2-4) x x1 1(r)(r)和和 x x2 2(r)(r)是是 x(n)x(n)按按 n n 的奇偶性分解成的两个的奇偶性分解成的两个 N/2N/2 点的子序列，如下式所示点的子序列，如下式所示 ， (2-5)(2-5) ， (2-6)(2-6) 那么那么 x(n)x(n)的的 DFTDFT 为为 ( )( )( ) knkn NN nn X kx n Wx n W /2 1/2 1 2(21) 00 (2 )(21) NN krkr NN rr xr WxrW (2-7)(2-7) /2 1/2 1 2 12 00 ( )( ) NN kkr NN rr x rWx r W 由于由于 (2-8)(2-8) 2 2 2 22 2 /2 jkr N jkr krkr N NN WeeW 所以所以 (2-9)(2-9) /2 1/2 1 1/22/212 00 ( )( )( )( )+W( ) NN krkkrk NNNN rr X kx r WWx r WX kXk =0,1,N-1=0,1,N-1 其中其中 X1(k)X1(k)和和 X2(k)X2(k)分别为分别为 x1(r)x1(r)和和 x2(r)x2(r)的的 N/2N/2 点点 DFTDFT，即，即 (2-10)(2-10) /2 1 11/21 0 ( )( )( ) N kr N r X kx r WDFT x r (2-11)(2-11) /2 1 22/22 0 ( )( )( ) N kr N r Xkx r WDFT x r 又由于又由于 X1(k)X1(k)和和 X2(k)X2(k)都是以都是以 N/2N/2 为周期，且为周期，且 (2-12)(2-12) 所以所以 X(k)X(k)又可以表示为如下所示的表达式又可以表示为如下所示的表达式 (2-13)(2-13) (2-14)(2-14) 12 ()( )( ) 2 k N N X kX kW Xk 这样一个这样一个 N N 点的点的 DFTDFT 就被拆分成为了两个就被拆分成为了两个 N/2N/2 点的点的 DFTDFT。式。式(3-7)(3-7)和式和式(3-8)(3-8)说明了原说明了原 N N 点的点的 DFTDFT 和这两个和这两个 N/2N/2 点的点的 DFTDFT 之间的关系。通常为了后续说明的方便，和其它许多文献一样，在本文之间的关系。通常为了后续说明的方便，和其它许多文献一样，在本文 中也将式中也将式(3-13)(3-13)和式和式(3-14)(3-14)的运算用图的运算用图 2.12.1 所示的一个流图符号表示。因为这个流图符号形状酷似所示的一个流图符号表示。因为这个流图符号形状酷似 一只蝴蝶，所以称其为蝶形运算符号。一只蝴蝶，所以称其为蝶形运算符号。 A B C A+BC A-BC 图图 2.12.1 蝶形运算符号蝶形运算符号 采用蝶形运算符号的这种图示方法，可以用图采用蝶形运算符号的这种图示方法，可以用图 2.22.2 来表示前面所讲到的运算。在图来表示前面所讲到的运算。在图 3.23.2 中，中， N=8N=8，式，式(3-13)(3-13)给出了给出了 X(0)X(0)X(3)X(3)的计算方法，而式的计算方法，而式(2-14)(2-14)给出了给出了 X(4)X(4)X(7)X(7)的计算方法。的计算方法。 图图 2.2N2.2N 点点 DFTDFT 的一次时域抽取分解图的一次时域抽取分解图(N=8)(N=8) 由图由图 3.13.1 可以看出，要完成一个蝶形运算，需要一次复数乘法和两次复数加法运算。由图可以看出，要完成一个蝶形运算，需要一次复数乘法和两次复数加法运算。由图 3.23.2 可以看出，经过一次分解后，计算一个可以看出，经过一次分解后，计算一个 N N 点点 DFTDFT 共需要计算两个共需要计算两个 N/2N/2 点点 DFTDFT 和和 N/2N/2 个蝶形运算。由个蝶形运算。由 前面的说明可以知道，计算一个前面的说明可以知道，计算一个 N/2N/2 点点 DFTDFT 需要次复数乘法和需要次复数乘法和 N/2(N/2-1)N/2(N/2-1)次复数加法。那么按图次复数加法。那么按图 3.23.2 计算计算 N N 点点 DFTDFT 共需要共需要+N/2=N(N+1)/2/2(N1)+N/2=N(N+1)/2/2(N1)次复数乘法和次复数乘法和 N(N/2-1)+2N/2=/2N(N/2-1)+2N/2=/2 次复数加法运算。次复数加法运算。 通过对比可以看出，只进行过这样的一次分解就使得运算量减少了近一半，充分说明了这样分解对通过对比可以看出，只进行过这样的一次分解就使得运算量减少了近一半，充分说明了这样分解对 减少减少 DFTDFT 的运算量是十分有效的。由于这里的运算量是十分有效的。由于这里 N=N=，N/2N/2 仍然是偶数，为了使得计算量能够得到进一步仍然是偶数，为了使得计算量能够得到进一步 的减少，可以仿效前面的做法对的减少，可以仿效前面的做法对 N/2N/2 点点 DFTDFT 再做进一步分解。再做进一步分解。 与第一次分解相同，与第一次分解相同，x3(l)x3(l)和和 x4(l)x4(l)为为 x1(r)x1(r)按奇偶分解成的两个长为按奇偶分解成的两个长为 N/4N/4 的子序列，即的子序列，即 （2-152-15） 32 41 ( )(2 ) ,0,1,1 ( )(21)4 x lxl N l x lxl 那么，那么，X1(k)X1(k)又可表示为又可表示为 )12( 2/ 14/ 0 1 2 2/ 14/ 0 11 ) 12()2()( lk N N i kl N N i WlxWlxkX = = kl N N i k N kl N N i WlxWWlx 4/ 14/ 0 42/4/ 14/ 0 3 )()( = = (2-16)(2-16)12/, 1 , 0),()( 42/3 NkkXWkx k N 其中其中 (2-17)(2-17)()()( 34/ 14/ 0 33 lxDFTWlxkx kl N N i (2-18)()()( 44/ 14/ 0 44 lxDFTWlxkx kl N N i 同理，由同理，由 X X3 3(k)(k)和和 X X4 4(k)(k)的周期性和的对称性最后得到：的周期性和的对称性最后得到： (2-19)(2-19)14/, 1 , 0, )()()4/( )()()( 42/31 42/31 Nk kXWkXNkX kXWkXkX k N k N 同理可得同理可得 (2-20)(2-20)14/, 1 , 0, )()()4/( )()()( 62/52 62/52 Nk kXWkXNkX kXWkXkX k N k N 其中有其中有 (2-21)(2-21)()()( 54/ 14/ 0 55 lxDFTWlxkX kl N N i (2-22)(2-22)()()( 64/ 14/ 0 66 lxDFTWlxkX kl N N i (2-23)(2-23)14/1 , 0, ) 12()( )2()( 26 25 Nl lxlx lxlx 这样，如图这样，如图 2.32.3 所示，经过第二次的分解，一个所示，经过第二次的分解，一个 N/2N/2 点的点的 DFTDFT 就被拆分成为了两个就被拆分成为了两个 N/4N/4 点的点的 DFTDFT 了。式了。式(3-10)(3-10)和式和式(3-11)(3-11)说明了原说明了原 N/2N/2 点的点的 DFTDFT 和这两个和这两个 N/4N/4 点的点的 DFTDFT 之间的关系。依次类推，之间的关系。依次类推， 经过经过 M-1M-1 次分解，最后将次分解，最后将 N N 点点 DFTDFT 分解成分解成 N/2N/2 个个 2 2 点点 DFTDFT。将前面两次分解的过程综合起来，就得。将前面两次分解的过程综合起来，就得 到了一个完整的到了一个完整的 8 8 点点 DIT-FFTDIT-FFT 运算流图，如图运算流图，如图 2.42.4 所示。图中用到关系式。图中的输入序列不是顺所示。图中用到关系式。图中的输入序列不是顺 序的，但是后面会看到，其排列是有规律的。序的，但是后面会看到，其排列是有规律的。 图图 2.32.3 N N 点点 DFTDFT 的第二次时域抽取分解图（的第二次时域抽取分解图（N=8N=8） 图图 2.42.4 N N 点点 DIT-FFTDIT-FFT 运算流图（运算流图（N=8N=8） (3)DIT-FFT(3)DIT-FFT 算法与直接计算算法与直接计算 DFTDFT 运算量的比较由运算量的比较由 DIT-FFTDIT-FFT 算法的分解过程及图算法的分解过程及图 2.42.4 可见，可见，N=N= 时，其运算流图应该有时，其运算流图应该有 M M 级蝶形，每一级都由级蝶形，每一级都由 N/2N/2 蝶形运算构成。每一级运算都需要蝶形运算构成。每一级运算都需要 N/2N/2 次复数乘次复数乘 和和 N N 次复数加次复数加( (每个蝶形需要两次复数加法每个蝶形需要两次复数加法) )。所以，。所以，M M 级运算总共需要的复数乘次数为级运算总共需要的复数乘次数为 (2-24)(2-24) 复数加次数为复数加次数为 (2-25)(2-25) 而由前面的介绍，直接计算而由前面的介绍，直接计算 N N 点的点的 DFTDFT 需要次复数乘法以及需要次复数乘法以及 N(N-1)N(N-1)次复数加法运算。当次复数加法运算。当 N1N1 时，时，N(N-1)N(N-1)是约等于的。当是约等于的。当 N=1024N=1024 时，可以求得直接计算时，可以求得直接计算 N N 点的点的 DFTDFT 和使用基和使用基-2-2 DIT-FFTDIT-FFT 算法算法 的所需乘法次数的比值为的所需乘法次数的比值为 (2-26)(2-26) 8 . 204 5120 1048576 log)2/( 2 2 NN N 这样，运算效率就提高了这样，运算效率就提高了 200200 多倍。图多倍。图 2.52.5 为为 FFTFFT 算法与直接计算算法与直接计算 DFTDFT 所需乘法次数的比较曲所需乘法次数的比较曲 线。由此图更加直观地看出线。由此图更加直观地看出 FFTFFT 算法的优越性，从图算法的优越性，从图 3-53-5 可以明显的看出，可以明显的看出，N N 越大时，优越性就越越大时，优越性就越 明显。明显。 图图 2.52.5 FFTFFT 算法与直接计算算法与直接计算 DFTDFT 所需乘法次数的比较曲线所需乘法次数的比较曲线 2.22.2 基基 4-FFT4-FFT 算法原理算法原理 在在 FFTFFT 各类算法中，基各类算法中，基 2-FFT2-FFT 算法是最简单的一种，但其运算量与基算法是最简单的一种，但其运算量与基 4-FFT4-FFT 算法相比则大得多，算法相比则大得多， 分裂基算法综合了基分裂基算法综合了基 4 4 和和 基基 2 2 算法的特点，虽然具有最少的复乘运算量，但其算法的特点，虽然具有最少的复乘运算量，但其 L L 蝶形运算控制的蝶形运算控制的 复杂性也限制了其在硬件上的实现，因此，本设计采用了基复杂性也限制了其在硬件上的实现，因此，本设计采用了基 4-FFT4-FFT 算法结构。算法结构。 基基 4-FFT4-FFT 算法的基本运算是算法的基本运算是 4 4 点点 DFTDFT。一个。一个 4 4 点的点的 DFTDFT 运算的表达式为：运算的表达式为： 03 02 0 0 )3( )2( ) 1 ( )0( 11 11 1111 1111 )3( ) 1 ( )2( )0( K N k N K N N WX