基于FPGA的FFT处理器设计

摘要：在火车车轮的振动式擦伤检测系统中，经常需要对振动信号进行频谱分析，为实现振动频谱信号的及时输出，在此根据FFT算法中的一种变形运算流图，提出一种基于FPGA的FFT流水线结构，总结了利用流水线结构实现这种FFT运算流图的数据存取规律，并按此结构利用Verilog语言设计了64点数据的6级流水线运算结构。利用振动信号测试数据进行仿真实验，结果表明该设计方法的正确可靠。
关键词：FFT算法；FPGA；流水线结构；蝶形运算；流图

    在火车车轮的振动式擦伤检测系统中，根据车轮与钢轨接触时产生的振动信号可以对车轮状态进行检测。有擦伤的车轮与钢轨接触时产生的振动信号具有特定的频谱特征，因此若将检测设备采集到的信号变换到频域进行分析，将有助于判断车轮是否有擦伤。为实现信号的快速变换，采用FPGA实现的FFT处理器对信号进行变换。
    FFT是离散傅里叶变换(DFT)的一种快速算法，当DFT的计算点数N很大时，FFT算法相对于直接计算DFT时的运算量会显著减少，因此其在数字信号处理领域有着广泛的应用，大大推动了数字信号处理技术的发展。FFT算法可以通过计算机软件、DSP处理器、FPGA器件和ASIC等方式来实现，目前对各种方式的分析和比较，相关文献已有介绍。在此提出的FFT算法，其FPGA结构具有模块化、流水线、可扩展的特点，因此用它可以提高计算速度，在芯片容量允许的情况下进行多点数、多级流水线结构的FFT运算。

1 算法原理及分析
1．1 FFT算法原理
    由DFT的定义可知，如果信号为x(n)，则对x(n)做N点DFT的计算表达式为：
    
    FFT算法即是对式(1)的一种快速算法。按抽取方式FFT算法可分为时域抽取(DIT)和频域抽取(DIF)；按基数(radix)不同FFT算法又可分为基-2、基-4等算法。在此采用基-2时域抽取法。对式(1)，利用基-2时域抽取法运算，可将x(n)按n的奇偶分成2组后分别求出各组的N／2点DFT，得到X1(k)和X2(k)，并根据旋转因子的周期性和对称性，最终得到表达式：
    
    由式(2)可以看出，要计算x(n)的N点DFT，可将x(n)按n的奇偶分成两组后所求出的N／2点DFT结果X1(k)和X2(k)，按照式(2)求出全部N点DFT结果。由式(2)确定的运算即为蝶形运算法，如图1所示，图2表示了连续使用这种分解方法得到最终只有两点数据进行DFT运算的共8点数据FFT运算流图的一种变形形式，这种运算结构在大型数据处理系统的FFT算法中采用较多。

1．2 运算流图分析
    对于N点的DFT，采用FFT算法可以显著减小计算量，当N越大，采用FFT算法的优势越明显。通过计算可得直接计算DFT的复数乘法次数为N2，而采用FFT计算时其次数仅为(N／2)log2N。在此，采用的流图为图2的形式，通过分析图2可得以下几点重要结论，而这些结论正是进行FPGA结构设计的依据。
    (1)输入数据为顺序输入，输出为倒序输出；
    (2)对于N点数据，可分为M=log2N级蝶形运算；
    (3)在第L级，共有2L-1组蝶形，且每组蝶形的旋转因子相同，各组旋转因子的上标k的顺序及取值为数0，1，2，…，N／2-1倒序排列后的前2L-1个；
    (4)在流水线工作方式下，在第L级的计算中，共N／2个蝶形需要计算，蝶形内数据间隔为2M-L，蝶形间数据间隔为2M-L+1；也即蝶形的两输入数据间隔为2M-L，计算下一个蝶形时需要跳跃2M-L+1个数据，但跳跃超出数据总数时需要特殊处理，这将在FPGA结构设计中阐述；
    (5)在流水线工作方式下，每级蝶形输出需要用RAM存储一半数据后再计算。在第L级的存储中，其存储寻址方式与第L-1级计算寻址方式相同(即原位计算)；也即每次需要存储一组上级输出的两个数据，其数据组间间隔为2M-L+2。组内数据间隔为2M-L+1。

2 FPGA结构设计
2．1 总体结构设计
    这里，FPGA结构设计采用了如图2所示的流图结构。分析图可以发现，对M级的运算可设计成流水线处理方式，但需要注意的是对于第L级和第L+1级之间的数据连接问题，即第L级的处理结果到第L+1级时，并不能立即处理，而需要将第L级的结果缓存一半后，第L+1级才能按一定的寻址方式开始处理数据，其寻址方式如1．2节中(4)，(5)所述。

    通过前面的分析，设计出的FPGA流水线处理结构如图3所示。图3为64点数据FFT运算结构，共6级运算单元，每个单元结构相同。各运算单元包括RAM存储单元、控制与寻址单元、蝶形运算单元和旋转因子表，其中设计重点即为蝶形运算单元、控制与寻址单元的设计。图3所示结构具有良好的扩展性，图中所示为64点数据6级结构，若要计算其他点数的FFT，则只需要增加运算单元数，如1 024点可用10级运算单元来实现，而每个运算单元的结构和功能是相似的。数据处理流程为通过输入端口输入数据到第1级RAM缓存一半数据(本文中为32个数据)，然后在寻址和控制单元的控制下开始蝶形运算；第2级再缓存第1级的输出结果，然后按相同的处理方式处理数据；由图3可知，最后一级的输出结果是倒序存放的，因此在最终数据输出时需通过倒序单元将处理结果排列为正序数据。
2．2 蝶形运算单元设计
    蝶形运算单元根据蝶形运算的特点进行设计。由图1可知，其运算包括复数乘法器和加法器，设计形成的蝶形运算单元框图如图4所示。

    对图4中需要说明的是复数乘法器的实现，相关文献中已详细介绍了其实现方式，在这里需要对输入／输出数据的格式和表示方法给予特别关注。现以本文为例，所有数据均以有符号16位Q10格式表示，两输入数据在经过乘法器运算后将得到32位Q20格式的数据，但为了能与后级数据格式兼容，需将32位Q20格式的数据处理成16位Q10格式数据。可将乘法结果右移10位后，通过保留原数据的符号位和移位后，由数据的低15位组成16位Q10格式的最终乘法结果，但该处理过程会给运算带来误差，在后面的实验中将会看到。
2．3 数据读取与存储寻址控制
    在1．2节中第(4)，(5)点已对数据的读取和存储寻址方式进行了总结，因此寻址的关键问题在于各级蝶形处理单元的读取和存储地址应该如何产生。通过图2和1．2节中第(5)点可知：
    (1)在第1级处理单元中，首先将输入数据依次存到第一级RAM中，当数据达到1／2时，则开始按存储顺序依次读出RAM数据，并与后半输入数据送到第1级蝶形运算单元进行处理。
    (2)在第L(1<L<7)级处理单元中，首先要将第L-1级输出数据的前半部分存储到第L级RAM，第L-1级的每次蝶形运算将输出2个数据，这两个数据存储时地址间隔为2M-L+1，每次需要跳跃2M-L+2个数据。但当跳跃个数超出数据总数时，需要特殊处理，这里给出了一种处理方法：地址位数用M=log2 N位来表示，存储时地址从0开始，每次存储时地址增加跳跃间隔2M-L+2。若产生进位，则将进位加到最低位形成下个地址，如此循环直到存储完全部数据。

3 仿真实验
    完成了FFT处理器结构设计后，需要对其正确性进行测试。本实验采用Verilog语言完成了FFT处理器的FPGA设计，仿真工具是ModelSim 6.1f。图5中(a)，(b)分别是振动信号及其幅度谱的Matlab绘图表示，已知擦伤振动信号的振动频率在2.5kHz附近，系统采样频率为15kHz。

    对振动信号通过ModelSim仿真进行测试，由于处理过程为流水线处理，各级将依次处理数据，且在时间上可以有重叠，使总的处理时间减少。如图6为ModelSim仿真图。最终得到的数据经过倒序输出后在Matlab中进行了绘图表示，图7(a)，图7(b)分别表示经过处理后的FFT变换结果的实部和虚部。对处理后数据的实部和虚部进行运算后得到最终的输入信号幅度谱如图8所示。

4 结语
    通过对比Matlab处理结果图5(b)和FPGA仿真结果图8可知：
    (1)在该实验中，设计方案能够正确地对64点数据进行FFT运算，幅度谱峰值位于Matlab结果的第13点和第21点处，它们对应的频率分别是2．8 kHz和4．7 kHz。其中，2．8 kHz可判断为擦伤信号频率，而4．7 kHz可视为高频噪声，因而需要滤波器处理；
    (2)FPGA处理结果存在噪声，这些噪声的产生原因在2．2节中已进行了初步分析。这是由于用硬件处理数据时由于数据的表示位数有限，且在乘法器的输出过程中对数据进行了截断处理所造成的。在此，仿真测试是基于64点数据进行的，但该设计方法可以方便地扩展到其他数据点数的处理中去，只需要增减运算级数，修改旋转因子表和修正各级控制与寻址参数即可。