基于FPGA的FFT算法实现毕业论文.doc

基于 fpga 的 fft 算法实现 第 i 页 共 41 页 毕业论文毕业论文 基于基于 fpgafpga 的的 fftfft 算法实现算法实现 摘要 快速傅立叶变换(fft)作为时域和频域转换的基本运算，是数字谱分析的必要前提。传统的 fft 使用软 件或 dsp 实现，高速处理时实时性较难满足。fpga 是直接由硬件实现的，其内部结构规则简单，通常可以容纳很多 相同的运算单元，因此 fpga 在作指定运算时，速度会远远高于通用的 dsp 芯片。fft 运算结构相对比较简单和固定， 适于用 fpga 进行硬件实现，并且能兼顾速度及灵活性。本文介绍了一种通用的可以在 fpga 上实现 512 点 fft 变换 的方法。主要对 quartus ii 中的 ram，rom，fft，基本运算等宏模块进行调用。并且通过 vga 控制模块，和键盘等 控制模块，实现对信号的产生和频谱的测量和显示等工作。实验果表明，设计完成的系统能够在保证运算精度和实 现复杂度的同时，切实可行地完成设计的总体要求。 关键词fpga；vga ；fft；ip 核 基于 fpga 的 fft 算法实现 第 ii 页 共 41 页 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 基于 fpga 的 fft 算法实现 第 i 页 共 41 页 目录目录 1 1 引言引言1 2 2 设计原理设计原理3 2.1 基 2-fft 算法原理3 2.2 基 4-fft 算法原理 .8 2.3 ip 核实现原理 8 3 3 fftfft 设计实现设计实现13 3.1 总体结构设计13 3.2 fft ipcore的建立14 3.3 测试信号的产生18 3.3.1 dds 原理18 3.3.2 dds 的实现18 3.3.3 测试信号的仿真.19 3.4 显示模块设计19 3.4.1 vga 显示原理19 3.4.2 vga 的实现22 3.4.3 vga 的仿真测试23 3.5 存储单元设计 .23 4 4 系统调试系统调试25 4.1 安装 byteblaster ii 下载电缆25 4.1.1 驱动程序安装25 4.1.2 硬件下载26 4.1.3 软件实现过程26 基于 fpga 的 fft 算法实现 第 ii 页 共 41 页 4.2 fft 算法测试 29 4.2.1 正弦信号的 fft 测试29 4.2.2 方波信号的 fft 测试.30 总结与展望.32 致谢.33 参考文献.34 附录附录.35 源程序.41 基于 fpga 的 fft 算法实现 第 1 页 共 41 页 1 引言 在数字化高速发展的今天，对数字信号处理高速实时的要求也不断提高。因此为了满足这些要 求，国内外都在研究实现数字信号处理的新方法，本论文主要研究基于 fpga 的方法来实现 fft 算 法，并通过对算法结构的内部优化设计使其相较于传统的实现方法更具优势。 fpga 技术的五大优势 （1）性能：利用硬件并行的优势，fpga 打破了顺序执行的模式，在每个时钟周期内完成更多 的处理任务，超越了数字信号处理器（dsp）的运算能力。 著名的分析与基准测试公司 bdti，发 布基准表明在某些应用方面，fpga 每美元的处理能力是 dsp 解决方案的多倍。2 在硬件层面控制输 入和输出（i/o）为满足应用需求提供了更快速的响应时间和专业化的功能。 （2）上市时间：尽管上市的限制条件越来越多，fpga 技术仍提供了灵活性和快速原型的能力。 用户可以测试一个想法或概念，并在硬件中完成验证，而无需经过自定制 asic 设计漫长的制造过 程。3 由此用户就可在数小时内完成逐步的修改并进行 fpga 设计迭代，省去了几周的时间。 商用 现成（cots）硬件可提供连接至用户可编程 fpga 芯片的不同类型的 i/o。 高层次的软件工具的日 益普及降低了学习曲线与抽象层，并经常提供有用的 ip 核（预置功能）来实现高级控制与信号处 理。 （3）成本：自定制 asic 设计的非经常性工程（nre）费用远远超过基于 fpga 的硬件解决方案 所产生的费用。 asic 设计初期的巨大投资表明了原始设备制造商每年需要运输数千种芯片，但更 多的最终用户需要的是自定义硬件功能，从而实现数十至数百种系统的开发。 可编程芯片的特性 意味着用户可以节省制造成本以及漫长的交货组装时间。 系统的需求时时都会发生改变，但改变 fpga 设计所产生的成本相对 asci 的巨额费用来说是微不足道的。 （4）稳定性：软件工具提供了编程环境，fpga 电路是真正的编程“硬”执行过程。 基于处 理器的系统往往包含了多个抽象层，可在多个进程之间计划任务、共享资源。 驱动层控制着硬件 资源，而操作系统管理内存和处理器的带宽。 对于任何给定的处理器内核，一次只能执行一个指 令，且基于处理器的系统时刻面临着严格限时的任务相互取占的风险。 而 fpga 不使用操作系统， 拥有真正的并行执行和专注于每一项任务的确定性硬件，可减少稳定性方面出现问题的可能。 （5）长期维护：正如上文所提到的， fpga 芯片是现场可升级的，无需重新设计 asic 所涉及 的时间与费用投入。 举例来说，数字通信协议包含了可随时间改变的规范，而基于 asic 的接口可 能会造成维护和向前兼容方面的困难。 可重新配置的 fpga 芯片能够适应未来需要作出的修改。 随着产品或系统成熟起来，用户无需花费时间重新设计硬件或修改电路板布局就能增强功能。 快速傅立叶变换(fft)是 dft 的快速算法,是数据从时域到频域变换的基本运算。它是频谱分析 的必要前提，是数字信号处理的核心工具之一。所以 fft 在众多学科领域，例如数字语音编码、雷 达信号处理、声纳信号分析、数字滤波、射电干涉等都有着十分广泛的应用。尤其是在要求较高的 信号处理系统中，fft 的处理速度往往是整个系统设计性能的关键。 软件实现 fft 运算速度慢，无法满足实时高速的系统性能要求。硬件实现 fft 的方式主要有三 种：通用数字信号处理器(dsp)、专用的 fft 芯片(asic)、可编程逻辑器件(以 fpga 为代表)。采用 dsp 方案通过软件编程来实现运算，虽然灵活性强，但是受到 dsp 本身性能及程序指令顺序执行的 限制难以实现高速、大规模的 fft 运算，同时也存在速度和精度之间的矛盾：若采用定点运算，舍 入误差会降低最终处理结果的精度；若采用浮点运算，可以消除动态范围局限的问题，但由于实现 结构复杂使处理速度难以达到要求，而且系统造价较高。采用 asic 芯片虽然可以达到较高的处理 速度，但是灵活性差，特别是使用定制的大规模集成电路的时候，需要较高的开发和研制费用，不 易扩展。随着超大规模可编程门阵列的迅速发展，新一代 fpga 内部有高速数字信号处理(dsp)模块 和大容量、高速 ram 模块，这为利用 fpga 实现 fft 处理成为可能，既避免了软件方式所带来的速 度方面的限制，又可以降低开发的成本和周期，是一种较为理想的开发方式。fpga 以高性能、高 灵活性、友好的开发环境、在线可编程等特点可以使基于 fpga 的设计满足实时数字信号处理的要 求。 基于 fpga 的 fft 算法实现 第 2 页 共 41 页 高速实时数字信号处理对系统性能要求甚高，因此，几乎所有的通用 dsp 都难以实现这一要求。 可编程逻辑器件允许设计人员利用并行处理技术实现高速信号处理算法，并且只需单个器件就能实 现期望的性能。在数据通信这样的应用中，常常需要进行高速、大规模的 fft 及其逆变换 ifft 运 算。当通用的 dsp 无法达到速度要求时，唯一的选择是增加处理器的数目，或者采用定制门阵列产 品。现在，随着微电子技术的发展，采用现场可编程门阵列(fpga)进行数字信号处理发展迅猛。采 用现场可编程器件不仅加快了产品上市时间，还可满足现在和下一代便携式设计所需要的成本、性 能、尺寸等方面的要求，并提供系统级支持。fpga 是直接由硬件实现的，其内部结构规则简单， 通常可以容纳很多相同的运算单元，因此 fpga 在作指定运算时，速度会远远高于通用的 dsp 芯片。 fft 运算结构相对而言比较简单和固定，适于用 fpga 进行硬件实现，并且能兼顾其速度及灵活性。 而采用 dsp 方式有很大的浪费，同时 dsp 芯片内部的乘法器资源十分有限，fft 算法中乘法量较大， 在实现实时处理方案时必须使用多个 dsp 芯片，从而提高了价格、增加了功耗和体积。而选择内部 嵌有多个乘法器内核的 fpga 芯片就可以很轻易地消除这一严重的资源浪费现象。尤其是近年来， 高密度的可编程逻辑器件 fpga 的集成度、速度不断提高，设计、调试手段更加完善，因而得到更 为广泛的应用。 本论文就是在这样一个背景下提出一种基于 fpga 的 512 点基 2-fft 算法的具体实现方法。旨 在设计出用 fpga 实现的、具有高速特点的、可实现定点 fft 运算的 ip 核，从而满足系统要求。 基于 fpga 的 fft 算法实现 第 3 页 共 41 页 2 设计原理 2.12.1 基基 2-fft2-fft 算法算法原理原理 长度为 n 的有限长序列 x(n)的 dft 的表达式为 (2-1)11 , 0,)()( 1 0 nkwnxkx n n kn n x(n)在一般情况下是为复数序列的。如果直接按(2-1)式计算 x(k)值，那么对于某一个 k 值而言, 需要 n 次复数乘法和(n-1)次复数加法。那么对于 n 个 k 值，一共需要 n(n-1)次复数加法运算。当 n1 时，n(n-1)。从上面的说明中可以看出，n 点 dft 的乘法和加法运算次数均与成正 2 n 2 n 比。当 n 较大时，运算量是十分庞大的。如果 n 取 32，那么将达到 1024。如此巨大的计算量 2 n 对于实时信号处理来说其运算速度是难以达到的。所以要想使得 dft 在各种科学和工程计算中得到 广泛的应用就必须想办法减少其运算量。 在前面已经讲到，n 点 dft 的复乘次数等于。其实一个 n 点 dft 可以看做是由几个较短的 2 n dft 组成的。基于这一思想，可以将 n 点 dft 分解为几个较短的 dft，这样一来乘法次数将大大减 少，能够非常明显地降低 dft 的运算量。此外，旋转因子具有明显的周期性和对称性。其周 m w n 期性表现为： （2-2） 22 ()jm lnjm m lnm nn nn weew 其对称性表现为 （2-3） mn m nn ww n mm nn ww 不断的把长序列的 dft 分解成几个短序列的 dft，并且利用的周期性和对称性来减少 m w n dft 的运算次数，这就是 fft 算法的基本思想。比较常用的 fft 算法有基-2 fft 和基 4fft 两种。 基-2 fft 中的基 2 指的是 n=，即有限长序列的长度 n 要到等于 2 的整数次幂。下面就以 8 点的2m fft 为例详细分析基-2 fft 算法。 2.1.1 基-2 fft 算法基本原理 基-2 fft 算法基本上分为时域抽取法 fft(dit-fft)和频域抽取法 fft(dif-fft)两大类。由于 这两种算法的基本原理是相同的，所以下面主要介绍 dit-fft 算法。本课题采用的就是 dit-fft 这 一算法。 设序列 x(n)的长度为 n，并且有以下的条件成立 ,m 为自然数 (2-4)2mn x1(r)和 x2(r)是 x(n)按 n 的奇偶性分解成的两个 n/2 点的子序列，如下式所示 ， (2-5) 1( ) (2 )x rxr0,1,1 2 n r ， (2-6) 2( ) (21)x rxr0,1,1 2 n r 基于 fpga 的 fft 算法实现 第 4 页 共 41 页 那么 x(n)的 dft 为 ( )( )( ) 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 1/2 1 2 12 00 ( )( ) nn kkr nn rr x rwx r w 由于 (2-8) 2 2 2 22 2 /2 jkr n jkr krkr n nn weew 所以 (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 k 其中 x1(k)和 x2(k)分别为 x1(r)和 x2(r)的 n/2 点 dft，即 (2-10) /2 1 11/21 0 ( )( )( ) n kr n r x kx r wdft x r (2-11) /2 1 22/22 0 ( )( )( ) n kr n r xkx r wdft x r 又由于 x1(k)和 x2(k)都是以 n/2 为周期，且 (2-12) 2 n k k nn ww 所以 x(k)又可以表示为如下所示的表达式 (2-13) 12 ( )( )( ) k n x kx kw xk0,11 2 n k (2-14) 12 ()( )( ) 2 k n n x kx kw xk0,11 2 n k 这样一个 n 点的 dft 就被拆分成为了两个 n/2 点的 dft。式(3-7)和式(3-8)说明了原 n 点的 dft 和这两个 n/2 点的 dft 之间的关系。通常为了后续说明的方便，和其它许多文献一样，在本文 中也将式(3-13)和式(3-14)的运算用图 2.1 所示的一个流图符号表示。因为这个流图符号形状酷似 一只蝴蝶，所以称其为蝶形运算符号。 a b c a+bc a-bc 基于 fpga 的 fft 算法实现 第 5 页 共 41 页 图 2.1 蝶形运算符号 采用蝶形运算符号的这种图示方法，可以用图 2.2 来表示前面所讲到的运算。在图 3.2 中，n= =8，式(3-13)给出了 x(0)x(3)的计算方法，而式(2-14)给出了 x(4)x(7)的计算方法。 3 2 图 2.2n 点 dft 的一次时域抽取分解图(n=8) 由图 3.1 可以看出，要完成一个蝶形运算，需要一次复数乘法和两次复数加法运算。由图 3.2 可以看出，经过一次分解后，计算一个 n 点 dft 共需要计算两个 n/2 点 dft 和 n/2 个蝶形运算。由 前面的说明可以知道，计算一个 n/2 点 dft 需要次复数乘法和 n/2(n/2-1)次复数加法。那 2 (/ 2)n 么按图 3.2 计算 n 点 dft 共需要+n/2=n(n+1)/2/2(n1)次复数乘法和 n(n/2-1) 2 2(/ 2)n 2 n +2n/2=/2 次复数加法运算。通过对比可以看出，只进行过这样的一次分解就使得运算量减少了 2 n 近一半，充分说明了这样分解对减少 dft 的运算量是十分有效的。由于这里 n=，n/2 仍然是偶2m 数，为了使得计算量能够得到进一步的减少，可以仿效前面的做法对 n/2 点 dft 再做进一步分解。 与第一次分解相同，x3(l)和 x4(l)为 x1(r)按奇偶分解成的两个长为 n/4 的子序列，即 （2-15） 32 41 ( )(2 ) ,0,1,1 ( )(21)4 x lxl n l x lxl 那么，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)12/, 1 , 0),()( 42/3 nkkxwkx k n 其中 (2-17)()()( 34/ 14/ 0 33 lxdftwlxkx kl n n i (2-18)()()( 44/ 14/ 0 44 lxdftwlxkx kl n n i 基于 fpga 的 fft 算法实现 第 6 页 共 41 页 同理，由 x3(k)和 x4(k)的周期性和的对称性最后得到： 2n wm /4 /2/2 k nk nn ww (2-19)14/, 1 , 0, )()()4/( )()()( 42/31 42/31 nk kxwkxnkx kxwkxkx k n k n 同理可得 (2-20)14/, 1 , 0, )()()4/( )()()( 62/52 62/52 nk kxwkxnkx kxwkxkx k n k n 其中有 (2-21)()()( 54/ 14/ 0 55 lxdftwlxkx kl n n i (2-22)()()( 64/ 14/ 0 66 lxdftwlxkx kl n n i (2-23)14/1 , 0, ) 12()( )2()( 26 25 nl lxlx lxlx 这样，如图 2.3 所示，经过第二次的分解，一个 n/2 点的 dft 就被拆分成为了两个 n/4 点的 dft 了。式(3-10)和式(3-11)说明了原 n/2 点的 dft 和这两个 n/4 点的 dft 之间的关系。依次类推， 经过 m-1 次分解，最后将 n 点 dft 分解成 n/2 个 2 点 dft。将前面两次分解的过程综合起来，就得 到了一个完整的 8 点 dit-fft 运算流图，如图 2.4 所示。图中用到关系式。图中的输 / kmk n mn ww 入序列不是顺序的，但是后面会看到，其排列是有规律的。 图 2.3 n 点 dft 的第二次时域抽取分解图（n=8） 基于 fpga 的 fft 算法实现 第 7 页 共 41 页 图 2.4 n 点 dit-fft 运算流图（n=8） (3)dit-fft 算法与直接计算 dft 运算量的比较由 dit-fft 算法的分解过程及图 2.4 可见，n= 时，其运算流图应该有 m 级蝶形，每一级都由 n/2 蝶形运算构成。每一级运算都需要 n/2 次复2m 数乘和 n 次复数加(每个蝶形需要两次复数加法)。所以，m 级运算总共需要的复数乘次数为 (2-24)n n m n cm 2 log 22 )2( 复数加次数为 (2-25)nnmnca 2 log)2( 而由前面的介绍，直接计算 n 点的 dft 需要次复数乘法以及 n(n-1)次复数加法运算。当 2 n n1 时，n(n-1)是约等于的。当 n=1024 时，可以求得直接计算 n 点的 dft 和使用基-2 2 n 10 2 dit-fft 算法的所需乘法次数的比值为 (2-26) 8 . 204 5120 1048576 log)2/( 2 2 nn n 这样，运算效率就提高了 200 多倍。图 2.5 为 fft 算法与直接计算 dft 所需乘法次数的比较曲 线。由此图更加直观地看出 fft 算法的优越性，从图 3-5 可以明显的看出，n 越大时，优越性就越 明显。 图 2.5 fft 算法与直接计算 dft 所需乘法次数的比较曲线 基于 fpga 的 fft 算法实现 第 8 页 共 41 页 2.22.2 基基 4-4-fftfft 算法原理算法原理 在 fft 各类算法中，基 2-fft 算法是最简单的一种，但其运算量与基 4-fft 算法相比则大得多， 分裂基算法综合了基 4 和 基 2 算法的特点，虽然具有最少的复乘运算量，但其 l 蝶形运算控制的 复杂性也限制了其在硬件上的实现，因此，本设计采用了基 4-fft 算法结构。 基 4-fft 算法的基本运算是 4 点 dft。一个 4 点的 dft 运算的表达式为： 03 02 0 0 )3( )2( ) 1 ( )0( 11 11 1111 1111 )3( ) 1 ( )2( )0( k n k n k n n wx wx wx wx jj jj x x x x 式(1)对于输出变量进行了二进制倒序，便于在运算过程中进行同址运算，节省了运算过程中 所需存储器单元的数量。 按 dit(时间抽取)的 1 024 点的基 4-fft 共需 5 级蝶形运算，每级从 ram 中读取的数据经过蝶 形运算后原址存入存储单元准备下一级运算。算法的第 1 级为一组 n=1024 点的基 4 蝶形运算，共 256 个蝶形，每个蝶形的距离为 256 点；第 2 级为 4 组 n=256 点的基 4 蝶形运算，每组 64 个蝶形， 每个蝶形的距离为 64 点。后 3 级类推。这种算法每一级的运算具有相对独立性，每级运算都采用 同址运算，因此，本设计只使用了 2 个 1 k16 bits 的 ram 单元。运算过程中所需的旋转因子的 值经过查询预设的正弦与余弦 rom 表得到。 2.32.3 ipip 核实现原理核实现原理 1) fft 兆核函数功能描述 长度为 n 的离散傅里叶变换(dft)是计算单位圆上 n 点均匀分布的离散时间序列 （w=2k=0，.n-i）的采样傅里叶变换。 序列 r(n)的 n 点 dft 如下所示： (2-27) 11 , 0)()( / )22( 1 0 nkenxakx npnkj n n n 点 idft 如下所示： 1,1 , 0 1 )( /2 1 0 nnekxa n nx npnkj n k (2-28) dft 直接计算的复杂性可以通过快速傅里叶变换(fft)算法大大降低。fft 算法可基于式( 5-1) 和式(5-2)中求和运算的嵌套分解以及复数乘法的对称性来实现。其中一类 fft 算法为库利-图基( cooley-tukey)基 r 按频率抽选（decimation-in frequency，缩写 dif）法将输入序列循环分解为 n/r 个长度为 r 的序列，并需要级运算。 n logr 每一级分解由同一个硬件单元完成，包括数据从存储器中抽取、通过 fft 处理器以及入存储 器的过程。每次通过 fft 处理器都要完成次运算。通常基数 r 选择 2、4 和 16，,增加分解基 n logr 数 r，可以通过牺牲硬件的资源来减少 fft 处理器的运算次数。 基于 fpga 的 fft 算法实现 第 9 页 共 41 页 将输入序列循环分解为 4 点序列的基 4 分解，使用 4 点 fft 在乘法运算上具有更大优势， altera 公司的 fft 兆核选用的就是基 4 运算，在 n 是 2 的奇数幂的情况下，fft ip 核，自动在完 成转换的最后使用基 2 运算。 为了在整个转换计算过程中保持高信噪比(snr)，fft 兆核函数采用块浮点(block floating- point)结构，这种结构是定点(fixed-point)与全浮点(full-floating-point)结构之 m 平衡 在块浮点结构中，每个数据模块中所有的数值都有一个独立的尾数，但共享一个公共的指数， 输入到 fft 函数的数据作为定点复数。 块浮点结构保证了在 fft 函数和整个转换过程中数据位数的完整使用。每次通过基 4fft 运算 以后，数据位数最大可能增加缩位，根据前面输出数据模块动态范围的测量按比例进行运算，换算 过程中累计的移位次数被作为整个模块的指数输出。这种移位方法保证最低位(lsb)的最小值在乘 法运算后的输出进行舍入操作之前就被丢弃。实际上，块浮点表示法起到了数字自动增益控制的作 用。为了在连续输出模块中产生统一的比例，必须用最终的指数对 fft 函数输出进行比例换算。 2) fft 处理器引擎结构 fft 兆核函数可以通过定制参数来使用两种不同的引擎结构：四输出(quad-output)或单输出( quad-output)引擎结构。为了增加 fft 兆核函数的总吞吐量，也可以在一个 fft 兆核函数变量中使 用多个并行引擎。 (1)四输出 fft 引擎结构 对于需要最少转换时间的应用，四输出 fft 引擎结构是最佳选择。四输出(quad-out-put)指的 是内部 fft 蝶形处理器的吞吐量，这种引擎实现结构可以在一个单时钟周期内计算所有四个基 4 蝶 形复数输出。四输出引擎结构的构图如图 2.8 所示。 复数采样数据 xk，m从内部存储器并行读出，并由变换开关(sw)重新排序排序后的取样 数据由基 4 处理器处理并得到复数输出 gk，m，由于基 4 按频率抽选(dif)分解方法固有的数字 特点，在蝶形处理器输出上仅需要 3 个复数乘法器完成 3 次乘旋转因子（有一个旋转因予为 1，不 需要乘）计算。为了辨别采样数据的最大动态范围，4 个输出由块浮点单元(bfpu)并行估计，丢弃 适当的最低位(lsb)，在写入内部存储器之前对复数值进行四舍五人并重新排序。 图 2.8 四输出 f 订引擎结构 (2)单输出 fft 引擎结构 在需要最小尺寸 fft 函数的应用中，单输出引擎最适合。单输出也指的是内部 fft 蝶形处理器 的吞吐量。在这种引擎结构中，每个时钟周期计算一个单蝶形输出，需要一个单独的复数乘法器， 其引擎结构如图 2.9 所示。 基于 fpga 的 fft 算法实现 第 10 页 共 41 页 ram rambfpu xk,0 xk,1 xk,2 xk,3 xk,0 xk,1 xk,2 xk,3 gk,0 gk,1 gk,2 gk,3 rom hk,m fft engine 图 2.9 单输出 fft 引擎结构 (3) fft 兆核 i/o 数据流结构 fft 兆核函数支持的 i/o 数据流包括：流(streaming)、缓冲突发(buffered burst)和突发 (burst)。 1)流(streaming)i/0 数据流结构 流 i/o 数据流结构允许输入数据连续处理，并输出连续的复数据流，这个过程中不需要停止 fft 数据流进出。这种数据流结构的仿真结果如图 2.10 所示。fft 兆核函数采用 altera atlantic 接口 i/o 协议，输入接口为主设备汇端(mastersink)而输出接口为主设备源端(master source)。 图 2.10 fft streaming 数据流仿真结果 在系统复位信号( reset)变为低电平后，数据源将 mastersinkdav 信号置为高电平，对于 fft 函数束说这表明在输入端至少有 n 个复数据样点可以输入。作为回应，fft 函数将 master- ink_ena 信号置为高电平，表明有能力接收这些输人信哆。数据源加载第一个复数据样点到 fft 函 数中，同时将 master_sink_sop 信号置为高电平，表示输入模块的开始。在下一时钟周期， master_sink_sop 信号被复位，并以自然顺序加载数据样点。如图 2.11 所示详细表明了输入信号 基于 fpga 的 fft 算法实现 第 11 页 共 41 页 流程控制时序，图中 z， （n）表示输入复数据实部，z （n）表示输入复数据虚部。 图 2.11 fft streaming 数据流结构输入流程控制时序 在 streaming 数据流结构中，fft 函数希望输入端的输人数据连续可用，因此，master- sink_ena 会一直保持高电平，除非系统复位，或 master_sink_dav 信号复位显示输人数据模块完 整，或由于 master _sink_sop 信号置高电平失败，master_sink_ena 信号才复位。 如果要在一个输入模块的边界上停止模块数据流，master_sink_sop 信号将在前一模块后数据 样点输入以后保持低电平。fft 函数复位 master_sink_ena 信号，并继续处理已入的数据模块。 fft 函数中的流水线已经清除以后，master_sink_ena 重新置为高电平，在下一个输入模块流的第 一个输入数据样点上置位 master_sink_sop 信号来对下一个输块的读取进行初始化。 当 fft 已经完成了输入模块的变换，并且从设备汇端(slave sink)将 master_sourcedav 号 置高电平（表示数据从设备接收器可以接收输出数据模块）时，fft 将 mastersourceena 号置 高电平，并且以自然顺序输出复数变换域数据模块。fft 函数在 mastersourcesop 号上输出一 个高电平咏冲表示第一个输出样点，如图 2.9 所示，图中详细表明了输出流程制时序。在 n 个时钟 周期之后，master_source_eop 信号被置为高电平，表示转换输出数据块结束如图 2.8 所示。 2)缓冲突发(burst)i/o 数据流结构 缓冲突发 i/o 数据流结构的 fft 需要的存储器资源比流动 1/0 数据流结构少，但平均模块吞 吐量减少。这种数据流结构的仿真结果如图 2.9 所示。在系统复位信号( reset)变为低电平后，数 据源将 master_ sink_ dav 信号置为高电平，对于 fft 函数来说这表明在输入端至少有 n 个复数数 据样点可以输入。作为回应，fft 函数将 mastersinkena 信号置高电平，表明有能力接收这些 输入信号。数据源加载第一个数数据样点到 fft 函数中，同时将 master_ sink_ sop 信号置高电平， 表示输入模块的开始。在下一个时钟周期，mastersink_sop 信号被复位，并以自然顺序加载后 面的 n-1 个复输数据样点。 当完全载入输入模块时fft 函数复位 mastersink_ena 信号，表示 fft 不再接收其他输入 数据并开始计算输入数据模块的变换结果。如图 2.10 所示为输入信号流程控制时序。在 fft 处理 器内部输入缓冲区读取输入样点之后，fft 将 master sinkena 信号重新置为高电平，并准备读 取下一个输入模块。下一个输入模块的起点由 master-sink-sop 脉冲确定。 基于 fpga 的 fft 算法实现 第 12 页 共 41 页 图 2.12 fft 缓冲突发数据流结构输出信号流程控制时序 信号 master_source_sop 和 master _source_eop 分别表示输出模块数据包的起点和终点如图 2.8 所示。 3)突发(burst)i/o 数据流结构 突发 i/o 数据流结构的执行过程和缓冲突发结构相同，不同的是，对于给定参数设置突发结构 在降低平均吞吐量的前提下需要更少的存储资源。其仿真结构图如图 2.13 所示 图 2.13 fft 缓冲突发数据流结构输出信号流程控制时序的仿真结构圈 在突发 i/o 数据流结构中，载人一个有效输入模块以后，master _sink_ena 信号被复位，直 到 fft 函数完成转换并且输出数据模块被完全读出为止，master_sink_ena 信号才被重新置位，准 备下一个输入模块的载入。 基于 fpga 的 fft 算法实现 第 13 页 共 41 页 3 fft 设计实现 3.13.1 总体结构总体结构设计设计 设计的总体方框结构图如图 3.1 所示。主要包括 a/d 采样控制模块(sample)、fft 运算前数据 存储模块(sample_dpram)、fft ip 核(fft)、缩放求模运算模块、fft 运算后数据存储模块( display_dpram)、波形显示控制模块(disp_ controller)、vga 显示驱动模块( vga)、采样频率控 制模块(div_freq)、键盘显示控制模块(key_board)和数据加载模块。dds 模块是为了方便测试 （产生正弦信号）而增设的。按功能可以划分为 4 部分：信号采样部分、fft 运算部分、波形显示 部分和键盘控制部分。信号采样部分会定时采样数据并进行存储；fft 运算部分负责对采样数据进 行换算，并将换算后的数据存人双口 ram;波形显示部分只管从双口 ram 读数据并送往 vga 接口显 示；键盘显示部分主要是控制更改采样频率、dds 输出频率及数码显示等操作。 a/d采样控制模块 fft ip核核 双端口ram1 数据加载模块1 双端口ram2 数据加载模块2 缩放运算求模运算 波形显示控制模块 vga显示控制模块 dds信号发生器 sink- ena source- sop 至vga 显示器 sink-sop 图 3.1 方框结构图 各模块简介 各模块功能简介如表 3.1 所列 基于 fpga 的 fft 算法实现 第 14 页 共 41 页 表 3.1 各模块功能 3.2 fft ipcore 的建立的建立 安装 megacore。megacore 可以在 quartus ii 开发环境中使用，本实验的 fft megacore 是 fft v 2.1.3，即 2.1.3 版本的 fft 编译器。megacore 不附带在 quartus ii 软件中，需要单独向 altera 公司购买或申请试用版。在这里我们安装的是 megacore ip librar 图 3.2 megawizard page1 模块名称功能描述备注 pll 产生 loo mhz 系统时钟25 mhz vga 驱动动时序兆功能模块 dds 正弦信号发生器产生被测模拟信号 sample 信号采集模块，负责采集数据并存储 sample_dpram 采样存储模块(双端口 ram)兆功能模块 fft_load_data 数据装载模块，将 sample_dpram 中的敷据送基 fft ip 核 fft fft 运算模块，进行 fft 变换fft ip 核 fft_data_switch 数据转换模块，对 fft 输出数据进行缩放运算（指数运 mult add 乘加运算模块兆功能模块 sqrt 求方根模块，完成x 运算兆功能模块 display_load_data 数据装载模块，将 fft 处理后的数据装载到显存(dis- play_dpram)中 display_dpram fft 运算处理后的数据存储模块(双端口 ram兆功能模块 disp_controller 频谱显示控制模块，将频谱数据送 vga 驱动模块 vga vga 驱动模块，驱动 vga 显示器显示频谱信号 div_freq 采样信号分频模块，控制采样频率 key_board 键盘显示模块，控制分频模块、dds 和数码管显示 基于 fpga 的 fft 算法实现 第 15 页 共 41 页 打开 fft 编译器。在 quartus ii 主界面中选择 toolmegawizard plug-in managc 打开添加 宏单元的向导，选择 create a new custom megafunction variation 新建宏单元模块然后在新建 宏单元模块窗口中选择 dsp- transforms-fft v2.11 3 并命名为 fft。 图 3.3 megawizard page1 设置 fft 的参数。在 quartus ii 主界面中，在 fft 兆核函数向导中单击“step 1：parameterize”打开 fft 参数设置对话框，具体参数设置如下： (a)在 parameters 选项卡设置 fft 变换长度(transform length)为 512，数据精度(data precision)和旋转因子精度(twiddle precision)为 8 位，如图 3.4 所示。 图 3.4 megawizard parameters 基于 fpga 的 fft 算法实现 第 16 页 共 41 页 (b)在 architecture 选项卡选择突发结构(burst)为 i/o 数据流，单输出 fft 引擎结构(single output)，并行 fft 引擎个数为“l” ，如图 3.5 所示。 图 3.5 megawizard architecture (c)在 implementation options 选项卡选择复数乘法器结构(structure)为 4/mults2adders，如图 3.6 示。 图 3.6 megawizard implementation 基于 fpga 的 fft 算法实现 第 17 页 共 41 页 d)最后单击 finish 按钮完成参数设置。 生成 fft 模块。在 fft 兆核函数向导中单击“step 2：set up simulation”按钮百以打开生 成仿真文件的对话框，这里不需要生成仿真文件，所以可以跳过此步，直接单“step 3：generate” 按钮，就可以生成所需要的 fft 模块。 图 3.7 generate 3.33.3 测试信号的产生测试信号的产生 3.3.13.3.1 ddsdds 原理原理 设计采用目前使用最广泛的一种 dds 方式是利用高速存储器作查找表，然后通过高速 dac 输 出已经用数字形式存储的波形。 累累加加器器 相相位位寄寄存存 器器 加加法法器器 正正弦弦查查找找 表表 daclpf 频频率率控控制制 字字 时时钟钟源源 相相位位控控制制字字 输输出出频频率率 fc m 图 3.8 dds 系统的基本原理图 基于 fpga 的 fft 算法实现 第 18 页 共 41 页 图 3.8 中虚方框部分是 dds 的核心单元，它可以采用 cpld/fpga 来实现。图中的相位累加器 由位全加器和位累加寄存器级联而成，可对频率控制字的二进制码进行累加运算，是典型的反 馈电路。 频率控制字 m 和相位控制字分别控制 dds 输出正(余)弦波的频率和相位。每来一个时钟脉冲， 相位寄存器以步长 m 递增。相位寄存器的输出与相位控制字相加，其结果作为正(余)弦查找表的地 址。正(余)弦查找表的数据存放在 rom 中，内部存有一个周期的正弦波信号的数字幅度信息，每个 查找表的地址对应于正弦波中 0360范围内的一个相位点。查找表把输入的址信息映射成正 (余)弦波的数字幅度信号，同时输出到数模转换器 dac 的输入端，dac 输出的模拟信号经过低通滤 波器 (lpf)，可得到一个频谱纯净的正(余)弦波。 dds 具体工作过程如下：每来一个时钟脉冲 clk，n 位全加器将频率控制数据 m 与累加寄存器 输出的累加相位数据 n 相加，把相加后的结果送至累加寄存器的输入端。累加寄存器一方面将上 一时钟周期作用后所产生的新的数据反馈到加法器的输入端，以使加法器在下一时钟的作用下继续 与频率控制数据 m 相加；另一方面将这个值作为取样地址值送入幅度/相位转换电路，此电路根据 取样地址输出相应的波形数据。最后经 d/a 转换器和低通滤波器将波形数据转换成所需要的模拟 波形。 dds 输出信号的频率由下式决定：q=()clk (代表取样点数 m 为频率控制字、 nm 2/2 m 2 代表存储器中存储数据的多少，n 代表累加器的位数，clk 代表基准时钟频率) 。调节 m