原创 FFT兆核函数

无聊的时候翻译了Altera的FFT核UG，英文水平有限，错漏难免

一、FFT兆核函数的应用<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />

1.     系统要求

本文主要以FFT<?xml:namespace prefix = st1 ns = "urn:schemas-microsoft-com:office:smarttags" />2.2.1为基础，该版本兆核函数需要下列硬件和软件配置：

l         装有Windows 2000/XP，企业版Red Hat Linux3 WS操作系统的PC；或装有Solaris8或9操作系统。

l         QuartusII6.0或更高版本。

l         Altera支持的VHDL或Verilog HDL仿真器（可选）。

2.     下载并安装FFT

客户可以从Internet上下载Altera的IP核，也可以从Altera的QuartusII安装软件随附的MegaCore光盘中得到。具体下载过程从略。

图1给出了安装FFT兆核函数文件后生成的目录结构，只中<path>表示FFT兆核函数安装目录。

  <?xml:namespace prefix = v ns = "urn:schemas-microsoft-com:vml" />                  图1   FFT兆核函数安装目录结构

3.     FFT兆核函数设计应用

这里介绍如何在Windows操作系统下使用QuartusII软件和IP工具台创建一个FFT兆核函数的用户变量。当产生FFT兆核函数用户变量以后，设计者即可将其加入到总的工程设计中使用。

1)      建立一个新的QuartusII工程

建立一个新的QuartusII工程文件时，可以使用QuartusII New Project Wizard工程向导为工程文件设置工作目录，分配工程名称，指定顶层设计输入的文件名，同时必须指定FFT兆核函数用户库。建立新工程的操作步骤如下：

（1）启动QuartusII软件。

（2）选择File>New Project Wizard命令。

（3）指定新建工程文件的工作目录。

（4）指定工程文件名。

（5）点击Next按钮。

（6）点击User Library Pathnames按钮。

（7）在Library name 栏中指定<path>\fft-2.2.1<version>\lib\，其中<path>表示安装FFT兆核函数的目录，默认按照目录为c:\MegaCore。点击Add按钮添加用户库，点击OK按钮确定。

（8）连续点击两次Next按钮，在指定目标器件系列中选择具体器件系列。

（9）点击Next按钮，选择目标器件。

（10）点击Finish按钮完成建立新工程。

2)      启动IP工具台

根据下面的操作步骤，在QuartusII软件中启动IP工具台：

（1）选择Tools>MegaWizard Plug-In Magnager 命令运行MegaWizard Plug-In管理器，弹出MegaWizard Plug-In Magnager 对话框。

（2）选择Create a new customer megafunction variation 选项并点击Next按钮。

（3）在Installed Plug-Ins中点击DSP文件夹前面的加号“＋”展开，同样展开里面的Transforms文件夹。

（4）选择FFTv2.2.1。

（5）指定输出文件类型，如AHDL、VerilogHDL或VHDL。

（6）指定输出文件目录及文件名，如图2所示。

（7）点击Next按钮，QuartusII软件启动FFT兆核函数IP工具台，如图3所示。

    图2 MegaWizard Plug-In Manager对话框

图3 FFT兆核函数IP工具台

3)      确定参数

使用FFT兆核函数IP工具台创建一个FFT兆核函数用户变量，步骤如下：

（1）点击FFT兆核函数IP工具台上的Step1：Parameterize按钮，弹出Parameterize-FFT MegaCore（兆核函数参数设置）对话框，选择Parameters标签页，如图4所示。

                图4 FFT兆核函数参数设置对话框的Paraneters标签页

（2）从Target Device Family列表中选择目标器件系列。

（3）分别从Transform Length、Data Precision和Twiddle Precision列表中选择转换长度、数据精度和旋转因子精度。

注意：旋转因子精度必须小于或等于数据精度。

（4）设置好FFT兆核函数参数设置对话框的Parameters标签页以后，选择Architecture标签页，如图5所示。

            图5 FFT兆核函数参数设置对话框的Architecture标签页

（5）在I/O Data Flow中选择Buffered Burst，然后在Engine Options栏的FFT Engine Architecture列表中选择Quad Output，在Number of Parallel FFT Engines列表中选择2。

       如果在I/O Data Flow 中选择Streaming，FFT兆核函数生成一个具有最少Quad Output FFT引擎的设计来满足所需的I/O吞吐量。

       注意：一个单FFT引擎结构可以达到点数为1024的Streaming I/O数据流FFT的足够性能。

       对于Buffered Burst 和Burst I/O数据流结构，可以在1、2和4个Quad Output FFT引擎之间选择并行工作；也可以在FFT Engine Architecture 列表中选择Single Output FFT引擎结构，则可以选择1或2个引擎并行工作。如果可以在器件资源和数据吞吐量之间进行折中选择，则选择多个并行引擎可以在牺牲器件资源的情况下减少FFT兆核函数的转换时间。

       （6）设置好FFT兆核函数参数设置对话框的Architecture标签页以后，选择Implementation Options标签页，如图6所示。

         图6 FFT兆核函数参数设置对话框的Implementation Options 标签页

       （7）在Complex Multiplier Implementation 选择栏中的Structure列表中选择期望的复数乘法器结构。

       复数乘法器可以使用4个实数乘法器和2个加法/减法器完成，或使用3个乘法器、5个加法器和一些附加的延时单元完成。在StratixII、StratixGX和Stratix器件中选择4个乘法器和2个加法器可以最大化DSP模块的使用并最小化逻辑单元（LE）的使用。

       （8）在Implement Multipliers in列表中选择在器件资源中如何实现乘法器，包括DSP Block/Logic Cells、LogicCells ONLY 和DSP Blocks ONLY三个选项。

      每个实数乘法器可以仅由DSP Blocks或逻辑单元（LEs）实现，或使用两者组合共同实现。如果选择使用DSP Blocks 和LEs组合实现，FFT兆核函数将使用逻辑单元扩展DSP模块的18×18乘法器资源。

       （9）在Memory Options栏中指定存储器选项。

       高吞吐量FFT参数设置将增加存储旋转因子的ROM需求。如果选择的目标器件系列支持M512RAM模块，则设计者可以通过设置Twiddle ROM Distribution滑动条，在M4K RAM和M512 RAM模块之间分配所需的ROM存储空间。设置滑动条位置到最左端，意味着完全在M4K RAM模块中实现ROM存储；设置滑动条位置到最右端，意味着完全在M512 RAM模块中实现ROM存储；设置滑动条在中间位置，意味着使用M4K和M512 RAM模块实现ROM存储。

       （10）完成Implementation Options中的选项设置后点击Finish按钮完成参数设置。

4)      建立仿真

IP功能仿真模型是由QuartusII软件产生的周期精确（Cycle-Accurate）的VHDL或Verilog HDL模型文件。该仿真模型允许使用工业标准的VHDL和Verilog HDL仿真器进行IP快速功能仿真。

使用下面的步骤为FFT兆核函数产生IP功能仿真模型：

（1）点击图3所示的FFT兆核函数IP工具台上的Step2：Set Up Simulation按钮。

（2）选择Set Up Simulatior-FFT MegaCore对话框中的Generator Simulation Model选项，如图7所示。

        图7 FFT兆核函数仿真器设置对话框

（3）在Language列表中选择兆核函数输出文件语言类型。

（4）点击OK按钮完成设置。

5)      产生兆核函数

指定参数值和IP功能仿真模型选项以后，即可产生用户FFT兆核函数。

（1）点击图3所示的FFT兆核函数IP工具台上的Step3：Generate按钮。

       （2）弹出IP测试台设计文件报告列表窗口，如图8所示，点击Exit按钮关闭该窗口。

                             图8 IP测试台设计文件报告列表窗口

IP测试台产生文件的描述从略，表1列出了FFT兆核函数输出文件的描述。

    表1 FFT兆核函数输出文件描述

       表中的<variation_name>表示FFT兆核函数变量文件名，如fft_example

       （3）查看完生成报告以后，点击生成报告窗口的Exit按钮关闭IP工具台并返回到QuartusII软件。

4．设计仿真

使用IP工具台生成的IP功能仿真模型完成设计仿真。IP功能仿真模型是VO或VHO文件，由建立仿真中的设置决定。这些文件在用户指定的工作目录中产生，在仿真环境中编译该IP功能仿真模型完成用户FFT兆核函数变量的功能仿真。

下面的步骤是在ModelSim软件中完成仿真的过程，也可以在任何Altera支持的VHDL或Verilog HDL仿真器上仿真FFT兆核函数。

在ModelSim软件中使用MegaWizard Plug-In设计向导产生的ModelSim Tcl脚本完成仿真过程如下：

（1）启动ModelSim仿真器软件。

（2）在仿真器中，选择File-〉Change Directory命令，改变工作目录为当前生成的FFT兆核函数变量工作目录。

（3）在仿真器命令提示符中执行Tcl命令脚本。

如果功能仿真语言选择的是VHDL，则执行<variation_name>_vho_msim.tcl脚本文件；

如果功能仿真语言选择的是Verilog HDL，则执行<variation_name>_vo_msim.tcl脚本文件。

Tcl脚本建立ModelSim工程，完成库映射，编译顶层设计和相关测试台，然后在波形观察窗口中给出仿真结果波形。

5．设计编译

使用QuartusII软件对设计进行综合、布局和布线，完成用户FFT兆核函数变量的编译步骤如下：

（1）在QuartusII软件中选择Assignments→Settings命令，弹出Settings对话框。

（2）在Category中选择Files页面，点击Add按钮。

（3）添加<FFT兆核函数安装路径>\fft-v2.2.1\lib目录下面的fft_pack.vhd文件到QuartusII工程中（一般会自动加到工程中，如果没有则可以手动添加）。

（4）点击OK按钮确定。

       （5）在QuartusII软件中选择Processing→Start Compilation命令启动编译。

二、FFT兆核函数规范

1.       功能描述

长度为N的离散傅立叶变换（DFT）是计算单位圆上N点均匀分布的离散时间序列（，k=0,… ，N-1）的取样傅立叶变换。

序列x（n）的N点DFT由（1）式给出：

      k=0，1,… ,N-1              （1）

N点IDFT由（2）式给出：

  k=0，1,… ,N-1                   （2）

DFT直接计算的复杂性可以通过快速傅立叶变换（FFT）算法大大降低。FFT算法基于（1）和（2）式中丘壑运算的嵌套分解以及复数乘法的对称性得以实现。其中一类FFT算法为库利-图基（Cooley-Tukey）基-r按频率抽选（decimation-in-frequency，缩写为DIF）法，将输入序列循环分解为N/r个长度为r的序列，并需要级运算。

每一级分解由同一个硬件单元完成，包括数据从存储器中取出、通过FFT处理器以及写入存储器的过程。每次通过FFT处理器需要完成次运算。通常基数选择r=2、4和16，增加分解基数r，可以牺牲器件资源的情况下减少通过FFT处理器的次数。

将输入序列循环分解为4点序列的基-4分解，使用4点FFT在乘法运算上具有更大优势，这也是Altera FFT兆核函数所选择的分解基数，是可以获得最大数据吞吐量的分解，这种分解仅在蝶形运算之后乘旋转因子中才有复数乘法。在N是2的奇数幂的情况下，FFT兆核自动在完成转换的最后使用基-2运算。

为了在整个转换计算过程中保持高信噪比（SNR），FFT兆核函数采用块浮点（Block-floating-point）结构，这种结构是定点（Fixed-point）与全浮点（Full-floating-point）结构之间的平衡。

在定点结构中，数据净度必须足够大才能充分表示整个转换计算过程中所有的中间计算结果。在执行定点FFT过程中，经常会出现数据位过大或精度损失的现象。

在浮点结构中，每个数用单独的指数和尾数来表示，虽然这样可以极大提高数据精度，但浮点运算需要占用更多的器件资源。

在块浮点结构中，每个数据模块中所有的数值都有一个独立的尾数，但共享一个公共的指数，输入到FFT函数的数据作为定点复数。

块浮点结构保证了在FFT函数和整个转换过程中数据位数的完整使用。每次通过基-4 FFT运算以后，数据位数最大可能增加4√2=5.65位，根据前面输出数据模块动态范围的测量进行按比例换算，换算过程中累计的移位次数被作为整个模块的指数输出。这种移位方法保证最低位（LSB）的最小值在乘法运算后的输出进行舍入操作之前就被丢弃。实际上，块浮点表示法起到了数字自动增益控制（AGC）的作用。为了在连续输出模块中产生同一的比例，必须用最终的指数对FFT函数输出进行比例换算。

注意：Altera FFT兆核函数的块浮点输出与Matlab这种全精度FFT的输出相比，应该用进行比例换算来解决转换过程中最低位（LSB）被丢弃的影响。其中exponent_out表示指数输出。

2.       FFT处理器引擎结构

FFT兆核函数可以通过定制参数来使用两种不同的引擎结构：四输出（Quad-output）或单输出（Single-output）引擎结构。为了增加FFT兆核函数的总吞吐量，也可以在一个FFT兆核函数变量中使用多个并行引擎。

1）四输出FFT引擎结构

       对于需要最少转换时间的应用，四输出FFT引擎结构是最佳选择。四输出（Quad-output）指的是内部FFT蝶形处理器的吞吐量，这种引擎实现结构在一个单时钟周期内计算所有四个基-4蝶形复数输出。图9给出了四个输出FFT引擎结构的框图。

                          图9 四输出FFT引擎结构

       复取样数据x[k，m]从内部存储器并行读出，并由变换开关（SW）重新排序。紧接着，排序后的取样数据由基-4处理器处理并得到复数输出G[k，m]。由于基-4按频率抽选（DIF）分解方法固有的数学特点，在蝶形处理器输出上仅需要3个复数乘法器完成3次乘旋转因子（有一个旋转因子为1，不需要乘）计算。为了辨别取样数据的最大动态范围，四个输出由块浮点单元（BFPU）并行估计，丢弃适当的最低位（LSB），在写入内部存储器之前对复数值进行四舍五入并重新排序。

       2）单输出FFT引擎结构

       在需要最小尺寸FFT函数应用中，单输出引擎最适合。单输出也指的是内部FFT蝶形处理器的吞吐量。在这种引擎结构中，每个时钟周期计算一个单蝶形输出，需要一个单独的复数乘法器，其引擎结构如图10所示。 

    图10 单输出FFT引擎结构

3.       I/O数据流结构

FFT兆核函数支持的I/O数据流结构选项包括：流（Streaming）、缓冲突发（Buffered Burst）和突发（Burst）。

1）流（Streaming）I/O数据流结构

       流I/O数据流结构允许输入数据连续处理，并输出连续的复数数据流，这个过程中不需要停止FFT函数数据流的进出。图11给出了一个这种数据流的仿真结果。

       图11 FFT Streaming数据流结构仿真波形

       FFT兆核函数采用Altera Atlantic接口I/O协议，输入接口为主设备汇端（Master Sink），而输出接口为主设备源端（Master Source）。

       在系统复位信号（reset）变为低电平后，数据源将master_sink_dav信号置为高电平，对于FFT函数来说这表明在输入端至少有N个复数据样点可以输入。作为回应，FFT函数将master_sink_ena信号置高电平，表明有能力接收这些输入信号。数据源加载第一个复数据样点到FFT函数中，同时将master_sink_sop信号置高电平，表示输入模块的开始。

       在下一个时钟周期，master_sink_sop信号被复位，并以自然顺序加载数据样点。图12详细说明了输入信号流程控制时序，图中xr（n）表示输入复数据实部，xi（n）表示输入复数据虚部。

    图12 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_source_dav信号置高电平（表示数据从设备接收器可以接收输出数据模块）时，FFT将master_source_ena信号置高电平，并且以自然顺序输出复数变换域数据模块。FFT函数在master_source_sop信号上输出一个高电平脉冲表示第一个输出样点，如图13所示。图13详细说明了输出流程控制时序。

                图13 FFT Streaming数据流结构输出流程控制时序

       N个时钟周期以后，master_source_eop信号被置为高电平，表示转换输出数据块结束，如图10所示。

2）缓冲突发（Buffered Burst）I/O数据流结构

       缓冲突发I/O数据流结构的FFT需要的存储器资源比流动I/O数据流结构少，但平均模块吞吐量减少。图14给出了一个缓冲突发I/O数据流结构的仿真波形实例。

                            图14 FFT缓冲突发数据流结构仿真波形

       在系统复位信号（reset）变为低电平后，数据源将master_sink_dav信号置为高电平，对于FFT函数来说这表明在输入端至少有N个复数样点可以输入。作为回应，FFT函数将master_sink_ena信号置高电平，表明有能力接收这些输入信号。

       数据源加载第一个复数样点到FFT函数中，同时将master_sink_sop信号置高电平，表示输入模块的开始。在下一个时钟周期，master_sink_sop信号复位，并以自然顺序加载后面的N-1个复输入数据样点。

       当完全载入输入模块时，FFT函数复位master_sink_ena信号，表示FFT不再接收其他输入数据。此时，FFT函数开始计算输入数据模块的变换结果。图15详细说明了输入信号流程控制时序。

                图15 FFT缓冲突发数据流结构输入信号流程控制时序

       在FFT处理器从内部输入缓冲区读取输入样点之后，FFT将master_sink_ena信号重新置为高电平，准备读取下一个输入模块。下一个输入模块的起点由master_sink_sop脉冲确定。

       当FFT完成输入模块的变换，并且从设备汇端（Slave Sink）置master_source_dav信号为高电平（表示数据从设备接收器可以接收输出数据模块）时，FFT将master_source_ena信号置高电平，并以自然顺序输出复数变换域数据模块。图16说明了输出信号流程时序。

       信号master_source_sop和master_source_eop分别表示输出模块数据包的起点（start-of-packet）和终点（end-of-packet），如图14所示。

图16 FFT缓冲突发数据流结构输出信号流程时序