论文部分内容阅读
[摘要]FFT算法是一种实现数字脉冲压缩的高效、灵活的方法，也是实现数字数字信号中重要技术。利用并行存储器和流水设计改进了FFT模块，运用FPGA实现1024点的FFT运算。另外，应用的乒乓存储技术使该模块提高了数据传输的效率，很好的满足了系统实时性和精度要求。
[关键词]FPGAFFT 流水方式 数字脉冲压缩
中图分类号：TP2 文献标识码：A 文章编号：1671－7597(2008)0520025－01
一、引言
众所周知，FFT算法是一种实现数字脉冲压缩系统中的一种高效、快速、核心的方法。但是，目前现有数字压缩系统中的FFT模块一般只采用递归结构，对实际的数据处理速度是不够的。另外，当前基于DSP技术的FFT模块的功耗和体积较大，价格较高，而且速度不够，从而限制了其在数字信号处理中的应用。
本文以时间基-2FFT为基础，在理论上分析了FFT模块硬件实现的资源占用问题。采用了级联结构，并在该结构当中加入了流水和乒乓存储结构，改进并大大提高了FFT的处理性能。最后给出了模块详细的实现方法和性能分析。
二、硬件资源占用分析
由上式可以看出，一个基2蝶形算法由1个复乘和2个复加组成，转化为实数表示则要进行4次实数乘法和6次实数加法运算。综合考虑，处理器选用基2蝶算的基于时间抽取的FFT(DIT-FFT)处理器结构是比较合理的。
三、1024点FFT模块的总体结构
（一）1024点FFT模块的总体结构框图如图1所示
由于采用了流水结构，每个时钟周期都能取2个数据做蝶形运算，并将运算好的2个结果送到下一级存储单元。10级流水结构都按这样的方式处理，因此，运算1024点的FFT只需要1024/2=512个时钟周期。
由于存储和运算同时进行，故采用乒乓模式。同一级存储器中，一组（A）用于寄存前一级的输入数据，另一组（B）存储器向下一级输出数据，当该级1024点运算结束后，两组存储器功能交换。
（二）单级模块主要由6部分组成
（1）基-2蝶形运算单元。每级蝶形运算单元采用6路并行输入方式，其中4路为输入信号的实部和虚部，另外2路是旋转因子的实部和虚部；输出为4路，对应了输出数据的实部和虚部。内部采用流水方式，先运算复数乘法部分，再运算复数加法部分，加快了数据处理速度。
（2）地址产生器。即addr，控制产生3组地址:上级数据存入RAM的地址、旋转因子ROM的地址、本级数据读取RAM地址。其中上级数据存入地址和本级数据读取RAM地址通过地址多路器进行多路选择后，输入RAM相应的地址端口。
（3）控制信号产生器。产生RAM的读写使能脉冲，并对中间结果RAM组输出进行多路选择。另外还要产生对RAM读写地址的多路选择控制信号。
（4）多路选择器。多路选择器分为地址多路器和数据选择器。地址多路器对地址产生器产生的地址进行多路选择，分别输出RAM读取地址和写入地址；数据选择器对RAM输出结果进行多路选择，再将结果送入蝶形运算单元。
（5）乒乓存储器组。由于每次取出或写入两个数据，数据又分为实部和虚部，即产生4路输入或输出，故每一存储器组(A或B)由2个双端口存储器（DPRAM）组成，其一存储两个数据实部，另一个存储两个数据的虚部。由于是乒乓模式，每一级需要4个DPRAM，每个DPRAM的大小为1024×16 bit。在512个时钟周期后，两组存储器功能交换。
（6）旋转因子存储器组。旋转因子采用ROM进行存储，旋转因子的实部和虚部分别存储在两个单口ROM中，这样容易利用同址方式进行读取，最大ROM为512×16 bit。
四、1024点FFT模块的仿真结果及性能分析
（一）仿真结果
由于QuartusII 5.0仿真波形输入复杂，且输出波形并不直观，所以本文选择了Matlab与QuartusII 5.0进行联合仿真。对FFT模块输出的信号实部与Matlab计算的实部数值；FFT模块输出信号虚部与Matlab计算的虚部数值进行了比较。图略。
通过测试，系统由于由于采用的定点运算方式及截尾处理，误差是不可避免的。通过与理论值的比较，信号通过FFT计算后的输出能够保持理论上的频率特性，因此系统设计是可行的。
（二）性能分析
单级蝶形稳定运行在103.27M，FFT模块稳定运行在62.34M，仿真采用60M系统主频，从第一组数据输入，到结果输出，延时101.37µs，每完成1024点FFT运算需要9.31µs，完全满足了实时性要求。
对EP1S40器件资源占用情况为:逻辑单元使用11%，内部存储器使用23%，专用DSP使用42%。总体来说资源耗费适中，为后续系统整合在同一块FPGA内预留了空间。
（三）误差的分析与控制
（1）乘法截断误差。2个16位的数据相乘得到32位的积，把该积舍入为16位就会产生误差。去掉次高位多余的符号位并截去后15位。当被截去的各位是‘1’的时候，误差最大;被截去的各位为‘0’时，没有误差。对被截去的部分作类似4舍5入的处理，第18位为‘1’则向上进位，为‘0’则直接舍去，可以有效减小误差。
（2）加减法溢出误差。2个16位的数据相加减得到17位的结果，在进行下一级运算之前，必须舍去1位，对舍弃的这1位也进行上述的4舍5入运算。2个小数的加减运算而言，把结果全部右移1位就可以防止溢出。
五、结论
FPGA是当今数字电路系统设计的重要技术之一，FFT是一种实现数字脉冲压缩的高效的方法，其运算结构相对比较简单和固定，适于用FPGA进行硬件实现。本文介绍了如何将改进1024点FFT算法用FPGA模块化设计。设计和测试结果表明，改进的精度以及实时性都满足了应用要求，具有很强的应用价值。
参考文献:
[1]奥本海姆AV，谢弗R W.数字信号处理[M].北京:科学出版社，1980.
[2]赵树杰，史林.数字信号处理[M].西安:西安电子科技大学出版社，1997.
[3]Ian O’Donnell，Dennis Yee.FFT Implementation Exploration[EB/OL].
Http://infopad.Eecs.berkeley.edu/ian/ee225c/report.htm.
[4]刘朝晖，韩月秋.用FPGA实现FFT的研究[J].北京理工大学学报，1999，19(2):234-238.
[5]Altera Company Data Sheet. Fast Fourier Transform[DB]. 1997.
[关键词]FPGAFFT 流水方式 数字脉冲压缩
中图分类号：TP2 文献标识码：A 文章编号：1671－7597(2008)0520025－01
一、引言
众所周知，FFT算法是一种实现数字脉冲压缩系统中的一种高效、快速、核心的方法。但是，目前现有数字压缩系统中的FFT模块一般只采用递归结构，对实际的数据处理速度是不够的。另外，当前基于DSP技术的FFT模块的功耗和体积较大，价格较高，而且速度不够，从而限制了其在数字信号处理中的应用。
本文以时间基-2FFT为基础，在理论上分析了FFT模块硬件实现的资源占用问题。采用了级联结构，并在该结构当中加入了流水和乒乓存储结构，改进并大大提高了FFT的处理性能。最后给出了模块详细的实现方法和性能分析。
二、硬件资源占用分析
由上式可以看出，一个基2蝶形算法由1个复乘和2个复加组成，转化为实数表示则要进行4次实数乘法和6次实数加法运算。综合考虑，处理器选用基2蝶算的基于时间抽取的FFT(DIT-FFT)处理器结构是比较合理的。
三、1024点FFT模块的总体结构
（一）1024点FFT模块的总体结构框图如图1所示
由于采用了流水结构，每个时钟周期都能取2个数据做蝶形运算，并将运算好的2个结果送到下一级存储单元。10级流水结构都按这样的方式处理，因此，运算1024点的FFT只需要1024/2=512个时钟周期。
由于存储和运算同时进行，故采用乒乓模式。同一级存储器中，一组（A）用于寄存前一级的输入数据，另一组（B）存储器向下一级输出数据，当该级1024点运算结束后，两组存储器功能交换。
（二）单级模块主要由6部分组成
（1）基-2蝶形运算单元。每级蝶形运算单元采用6路并行输入方式，其中4路为输入信号的实部和虚部，另外2路是旋转因子的实部和虚部；输出为4路，对应了输出数据的实部和虚部。内部采用流水方式，先运算复数乘法部分，再运算复数加法部分，加快了数据处理速度。
（2）地址产生器。即addr，控制产生3组地址:上级数据存入RAM的地址、旋转因子ROM的地址、本级数据读取RAM地址。其中上级数据存入地址和本级数据读取RAM地址通过地址多路器进行多路选择后，输入RAM相应的地址端口。
（3）控制信号产生器。产生RAM的读写使能脉冲，并对中间结果RAM组输出进行多路选择。另外还要产生对RAM读写地址的多路选择控制信号。
（4）多路选择器。多路选择器分为地址多路器和数据选择器。地址多路器对地址产生器产生的地址进行多路选择，分别输出RAM读取地址和写入地址；数据选择器对RAM输出结果进行多路选择，再将结果送入蝶形运算单元。
（5）乒乓存储器组。由于每次取出或写入两个数据，数据又分为实部和虚部，即产生4路输入或输出，故每一存储器组(A或B)由2个双端口存储器（DPRAM）组成，其一存储两个数据实部，另一个存储两个数据的虚部。由于是乒乓模式，每一级需要4个DPRAM，每个DPRAM的大小为1024×16 bit。在512个时钟周期后，两组存储器功能交换。
（6）旋转因子存储器组。旋转因子采用ROM进行存储，旋转因子的实部和虚部分别存储在两个单口ROM中，这样容易利用同址方式进行读取，最大ROM为512×16 bit。
四、1024点FFT模块的仿真结果及性能分析
（一）仿真结果
由于QuartusII 5.0仿真波形输入复杂，且输出波形并不直观，所以本文选择了Matlab与QuartusII 5.0进行联合仿真。对FFT模块输出的信号实部与Matlab计算的实部数值；FFT模块输出信号虚部与Matlab计算的虚部数值进行了比较。图略。
通过测试，系统由于由于采用的定点运算方式及截尾处理，误差是不可避免的。通过与理论值的比较，信号通过FFT计算后的输出能够保持理论上的频率特性，因此系统设计是可行的。
（二）性能分析
单级蝶形稳定运行在103.27M，FFT模块稳定运行在62.34M，仿真采用60M系统主频，从第一组数据输入，到结果输出，延时101.37µs，每完成1024点FFT运算需要9.31µs，完全满足了实时性要求。
对EP1S40器件资源占用情况为:逻辑单元使用11%，内部存储器使用23%，专用DSP使用42%。总体来说资源耗费适中，为后续系统整合在同一块FPGA内预留了空间。
（三）误差的分析与控制
（1）乘法截断误差。2个16位的数据相乘得到32位的积，把该积舍入为16位就会产生误差。去掉次高位多余的符号位并截去后15位。当被截去的各位是‘1’的时候，误差最大;被截去的各位为‘0’时，没有误差。对被截去的部分作类似4舍5入的处理，第18位为‘1’则向上进位，为‘0’则直接舍去，可以有效减小误差。
（2）加减法溢出误差。2个16位的数据相加减得到17位的结果，在进行下一级运算之前，必须舍去1位，对舍弃的这1位也进行上述的4舍5入运算。2个小数的加减运算而言，把结果全部右移1位就可以防止溢出。
五、结论
FPGA是当今数字电路系统设计的重要技术之一，FFT是一种实现数字脉冲压缩的高效的方法，其运算结构相对比较简单和固定，适于用FPGA进行硬件实现。本文介绍了如何将改进1024点FFT算法用FPGA模块化设计。设计和测试结果表明，改进的精度以及实时性都满足了应用要求，具有很强的应用价值。
参考文献:
[1]奥本海姆AV，谢弗R W.数字信号处理[M].北京:科学出版社，1980.
[2]赵树杰，史林.数字信号处理[M].西安:西安电子科技大学出版社，1997.
[3]Ian O’Donnell，Dennis Yee.FFT Implementation Exploration[EB/OL].
Http://infopad.Eecs.berkeley.edu/ian/ee225c/report.htm.
[4]刘朝晖，韩月秋.用FPGA实现FFT的研究[J].北京理工大学学报，1999，19(2):234-238.
[5]Altera Company Data Sheet. Fast Fourier Transform[DB]. 1997.