基于fpga的fft算法实现毕业论文(编辑修改稿)

基于fpga的fft算法实现毕业论文(编辑修改稿)内容摘要：

Ni   (218) 同理，由 X3(k)和 X4(k)的周期性和 2NWm 的对称性 /4/2 /2k N kNNWW  最后得到： 基于 FPGA的 FFT算法实现 第 6 页 共 41 页 14/,1,0,)()()4/( )()()(42/3142/31   NkkXWkXNkX kXWkXkX kNkN  (219) 同理可得 14/,1,0,)()()4/( )()()(62/5262/52   NkkXWkXNkX kXWkXkX kNkN  (220) 其中有 )]([)()( 54/14/ 0 55 lxD F TWlxkX klNN i    (221) )]([)()( 64/14/ 0 66 lxD F TWlxkX klNN i    (222) 14/1,0,)12()( )2()( 26 25   Nllxlx lxlx  (223) 这样，如图 ，经过第二次的分解，一个 N/2点的 DFT就被拆分成为了两个 N/4点的 DFT了。 式 (310)和式 (311)说明了原 N/2 点的 DFT 和这两个 N/4点的 DFT之间的关系。 依次类推，经过 M1次分解，最后将 N 点 DFT 分解成 N/2 个 2 点 DFT。 将前面两次分解的过程综合起来，就得到了一个完整的 8点 DITFFT运算流图，如图。 图中用到关系式 /k mkN m NWW。 图中的输入序列不是顺序的，但是后面会看到，其排列是有规律的。 图 N 点 DFT 的第二次时域抽取分解图（ N=8） 基于 FPGA的 FFT算法实现 第 7 页 共 41 页 图 N点 DITFFT运算流图（ N=8） (3)DITFFT算法与直接计算 DFT运算量的比较由 DITFFT算法的分解过程及图 ， N=2M时，其运算流图应该有 M级蝶形，每一级都由 N/2 蝶形运算构成。 每一级运算都需要 N/2次复数乘和 N次复数加 (每个蝶形需要两次复数加法 )。 所以， M级运算总共需要的复数乘次数为 NNMNC M 2lo g22)2(  (224) 复数加次数为 NNMNC A 2lo g)2(  (225) 而由前面的介绍，直接计算 N点的 DFT需要 2N 次复数乘法以及 N(N1)次复数加法运算。 当 N1时， N(N1)是约等于 2N 的。 当 N=102 =1024时，可以求得直接计算 N点的 DFT和使用基 2 DITFFT算法的所需乘法次数的比值为 2020 4857 6log)2/( 22 NN N (226) 这样，运算效率就提高了 200 多倍。 图 FFT 算法与直接计算 DFT所需乘法次数的比较曲线。 由此图更加直观地看出 FFT 算法的优越性，从图 35 可以明显的看出， N 越大时，优越性就越明显。 图 FFT 算法与 直接计算 DFT 所需乘法次数的比较曲线 基于 FPGA的 FFT算法实现 第 8 页 共 41 页 基 4FFT算法原理 在 FFT各类算法中，基 2FFT算法是最简单的一种，但其运算量与基 4FFT算法相比则大得多，分裂基算法综合了基 4和 基 2算法的特点，虽然具有最少的复乘运算量，但其 L蝶形运算控制的复杂性也限制了其在硬件上的实现，因此，本设计采用了基 4FFT算法结构。 基 4FFT算法的基本运算是 4点 DFT。 一个 4点的 DFT运算的表达式为： 030200)3()2()1()0(111111111111)3(39。 )1(39。 )2(39。 )0(39。 KNkNKNNWXWXWXWXjjjjXXXX 式 (1)对于输出变量进行了二进制倒序，便于在运算过程中进行同址运算，节省了运算过程中所需存储器单元的数量。 按 DIT(时间抽取 )的 1 024 点的基 4FFT共需 5 级蝶形运算，每级从 RAM 中读取的数据经过蝶形运算后原址存入存储单元准备下一级运算。 算法的第 1 级为一组 N=1024 点的基 4 蝶形运算，共256个蝶形，每个蝶形的距离为 256点；第 2级为 4组 N=256点的基 4蝶形运算，每组 64个蝶形，每个蝶形的距离为 64点。 后 3级类推。 这种算法每一级 的运算具有相对独立性，每级运算都采用同址运算，因此，本设计只使用了 2个 1 k 16 bits的 RAM单元。 运算过程中所需的旋转因子的值经过查询预设的正弦与余弦 ROM表得到。 IP 核实现原理 1) FFT兆核函数功能描述 长度为 N 的离散傅里叶变换 (DFT)是计算单位圆上 N 点均匀分布的离散时间序列（ w=2πk=0， ...NI）的采样傅里叶变换。 序列 r(n)的 N点 DFT如下所示： 1. . . .1,0)()( /)22(10   NkenxakX NpnkjNn (227) N点 IDFT如下所示： 1. . . . . . ,1,0][1)( /210   NnekXaNnx NpnkjNk (228) DFT 直接计算的复杂性可以通过快速傅里叶变换 (FFT)算法大大降低。 FFT 算法可基于式 ( 51)和式 (52)中求和运算的嵌套分解以及复数乘法的对称性来实现。 其中一类 FFT 算法为库利 图基( CooleyTukey)基 r 按频率抽选（ Decimationin Frequency，缩写 DIF）法将输入序列循环分解为 N/r个长度为 r的序列，并需要 Nlogr级运算。 每一级分解由同一个硬件单元完成，包括数据从 存储器中抽取、通过 FFT 处理器以及入存储器的过程。 每次通过 FFT 处理器都要完成 Nlogr次运算。 通常基数 r 选择 4 和 16， ,增加分解基数r，可以通过牺牲硬件的资源来减少 FFT 处理器的运算次数。 基于 FPGA的 FFT算法实现 第 9 页 共 41 页 将输入序列循环分解为 4点序列的基 4分解，使用 4点 FFT在乘法运算上具有更大优势， Altera公司的 FFT兆核选用的就是基 4运算，在 N是 2的奇数幂的情况下， FFT IP核，自动在完成转换的最后使用基 2运算。 为了在整个转换计算过程中保持高信噪比 (SNR)， FFT 兆核函 数采用块浮点 (Block floatingpoint)结构，这种结构是定点 (Fixedpoint)与全浮点 (Fullfloatingpoint)结构之 M平衡 在块浮点结构中，每个数据模块中所有的数值都有一个独立的尾数，但共享一个公共的指数，输入到 FFT函数的数据作为定点复数。 块浮点结构保证了在 FFT 函数和整个转换过程中数据位数的完整使用。 每次通过基 4FFT 运算以后，数据位数最大可能增加缩位，根据前面输出数据模块动态范围的测量按比例进行运算，换算过程中累计的移位次数被作为整个模块的指数输出。 这种移 位方法保证最低位 (LSB)的最小值在乘法运算后的输出进行舍入操作之前就被丢弃。 实际上，块浮点表示法起到了数字自动增益控制的作用。 为了在连续输出模块中产生统一的比例，必须用最终的指数对 FFT函数输出进行比例换算。 2) FFT处理器引擎结构 FFT 兆核函数可以通过定制参数来使用两种不同的引擎结构：四输出 (Quadoutput)或单输出( Quadoutput)引擎结构。 为了增加 FFT兆核函数的总吞吐量，也可以在一个 FFT 兆核函数变量中使用多个并行引擎。 (1)四输出 FFT 引擎结构 对于需要最少转换时 间的应用，四输出 FFT 引擎结构是最佳选择。 四输出 (Quadoutput)指的是内部 FFT 蝶形处理器的吞吐量，这种引擎实现结构可以在一个单时钟周期内计算所有四个基 4 蝶形复数输出。 四输出引擎结构的构图如图。 复数采样数据 x[k， m]从内部存储器并行读出，并由变换开关 (SW)重新排序’排序后的取样 数据由基 4处理器处理并得到复数输出 G[k， m]，由于基 4按频率抽选 (DIF)分解方法固有的数字特点，在蝶形处理器输出上仅需要 3 个复数乘法器完成 3 次乘旋转因子（有一个旋转因予为 1，不需要乘）计算。 为了辨别采 样数据的最大动态范围， 4 个输出由块浮点单元 (BFPU)并行估计，丢弃适当的最低位 (LSB)，在写入内部存储器之前对复数值进行四舍五人并重新排序。 图 四输出 F 订引擎结构 (2)单输出 FFT引擎结构 在需要最小尺寸 FFT 函数的应用中，单输出引擎最适合。 单输出也指的是内部 FFT 蝶形处理器的吞吐量。 在这种引擎结构中，每个时钟周期计算一个单蝶形输出，需要一个单独的复数乘法器，其引擎结构如图。 基于 FPGA的 FFT算法实现 第 10 页 共 41 页 R A MR A MB F P UX [ k , 0 ]X [ k , 1 ]X [ k , 2 ]X [ k , 3 ]G [ k , 0 ]G [ k , 1 ]G [ k , 2 ]G [ k , 3 ]R O MH [ k , m ]F F T E n g i n e 图 单输出 FFT 引擎结构 (3) FFT兆核 I/O数据流结构 FFT 兆核函数支持的 I/O 数据流包括：流 (Streaming)、缓冲突发 (Buffered Burst)和突发(Burst)。 1)流 (Streaming)I/0数据流结构 流 I/O数据流结构允许输入数据连续处理，并输出连续的复数据流，这个过程中不需要停止 FFT数据流进出。 这种数据流结构的仿真结果如图。 FFT兆核函数采用 Altera Atlantic接口I/O协议，输入接口为主设备汇端 (MasterSink)．而输出接口为主设备源端 (Master Source)。 图 FFT streaming 数据流仿真结果 在系统复位信号 ( Reset)变为低电平后，数据源将 master— sink— dav 信号置为高电平，对于FFT函数束说这表明在输入端至少有 N个复数据样点可以输入。 作为回应， FFT函数将 Masterink_ena信号置为高电平，表明有能力接收这些输人信哆。 数据源加载第一个复数据样点到 FFT 函数中，同时将 master_sink_sop信号置为高电平，表示输入模块的开始。 在下一时钟周期， master_sink_sop信号被复位，并以 自然顺序加载数据样点。 如图 ，图中z，（ n）表示输入复数据实部， z．（ n）表示输入复数据虚部。 基于 FPGA的 FFT算法实现 第 11 页 共 41 页 图 FFT Streaming 数据流结构输入流程控制时序 在 streaming数据流结构中， FFT函数希望输入端的输人数据连续可用，因此， mastersink_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 号上输出一个高电平咏冲表示第一个输出样点，如图 ，图中详细表明了输出流程制时序。 在 N 个时钟周期之后， master_source_eop信号被置为高电平，表示转换输出数据块结束如图。