基于FPGA的24点离散傅里叶变换结构设计

摘要 基于Good—Thomas映射算法和ISE快速傅里叶变换IP核，设计了一种易于FPGA实现的24点离散傅里叶变换，所设计的24点DFT模块采用流水线结构，主要由3个8点FFT模块和1个3点DFT模块级联而成，并且两级运算之间不需要旋转因子，整个DFT模块仅仅需要14个实数乘法器，布局布线后仿真工作时钟频率可达200 MHz。首先根据Good—Thomas算法将并行的24路输入信号分成3组，每组8路信号，并进行并／串转换，得到3路串行信号；其次，将3路串行信号分别输入至3个FFT IP核模块进行8点FFT运算；然后，将上述3个FFT IP核模块同一时刻输出的3路信号进行3点DFT变换；最后，将得到的3路并行输出信号分别进行串／并转换，得到24路DFT输出信号。此外，设计的24点DFT结构还具有很好的扩展性，通过修改FFT IP核变换点数参数便可实现长度N=3×2n点DFT。
关键词 24点DFT；FPGA；Good—Thomas映射算法；FFT IP核

    由于具有高集成度、高速、可编程等优点，现场可编程门阵列(Field Programmable Gate Array，FPGA)已经广泛用于多种高速信号实时处理领域中。离散傅里叶变换(Discrete Fourier Transform，DFT)，尤其对应的快速傅里叶变换(Fast Fourier Transform，FFT)，是数字信号处理中的一种基本变换。基于FPGA的FFT设计和实现是众多应用中的一个重要环节，是众多FPGA芯片厂商和研究工作者一直致力研究的内容。
    目前，Altera和Xilinx公司都提供了可塑性很强的FFT IP核，只要改动相应的参数设置，就可以应用于不同产品中。国内不少大学及研究所也已经采用FPGA芯片设计开发具有自主知识产权的FFT。然而，目前绝大多数基于FPGA的FFT主要采用Cooley—Tukey映射算法实现基2和基4结构的点FFT。这在实际应用中存在以下问题：1)某些场合中所采用的DFT变换点数不一定满足，例如24点、48点等DFT无法采用上述FFT结构实现；2)采用Cooley—Tukey映射算法将高点数的DFT分解成若干个低点数DFT过程中，采用多级流水线结构实现FFT，但每一级输出结果需要乘以相应旋转因子后再进入下一级运算，从而增加了复数乘法器资源的使用。
    以Xilinx公司Virtex IV芯片为硬件平台，结合Xilinx公司ISE10．1软件提供的FFT IP核，提出一种适合FPGA实现的基于Good-Thomas算法的24点DFT结构。相对于已有的FFT结构，设计的DFT结构不仅能够充分利用FFT IP核优良特性，还能大大节约复数乘法器资源的使用。同时，该结构还能扩展至变换长度N满足N=3×2n的DFT。

1 24点DFT实现原理
1．1 Good—Thomas映射算法
    基于Cooley—Tukey映射算法和Good-Thomas映射算法的FFT均可以将长度为N=N1N2的DFT分解成N2个N1点DFT和N1个N2点DFT级联的形式。尤其基于Cooley—Tukey映射的FFT是最为通用的FFT算法，能够适应于任意N1和N2长度下的DFT。相对基于Cooley-Tukey映射的FFT，基于Good —Thomas映射的FFT只能适应于N1和N2互质情况下的DFT，但N1点DFT与N2点DFT之间的中间结果不需要采用旋转因子进行调制，从而能够大幅节约复数乘法器的使用。
    假设输入序列x(n)长度为N=N1N2，其中N1和N2互质，则基于Good—Thomas映射的FFT实现步骤如下：

    从以上步骤可以看出，基于Good—Thomas映射的FFT，虽然与基于Cooley—Tukey映射的FFT实现原理相似，但输入／输出索引映射不同，而且没有旋转因子。
1．2 24点DFT实现结构
    根据基于Good-Thomas映射的FFT适应条件，长度N=24的DFT可以按照N1=8和N2=3进行计算，其中，根据式(1)，输入序列按照n=mod(3n1+ 8n2，24)进行索引映射，如表1所示；根据式(4)，输出结果按照k=mod(9k1+16k2，24)进行索引映射，如表2所示。

    根据表1和表2的索引结果，图1给出了24点DFT实现结构示意图。如图1所示，24点DFT变换分两级实现，第一级由3个8点DFT构成，第二级由8个3点DFT构成，两级之间不需要旋转因子调制。

2 基于FPGA的24点DFT设计
    为简化设计，假设所设计24点DFT模块输入／输出信号均为24路并行信号。如图1所示，采用Good—Thomas映射算法，可将24点DFT分解成3个8点DFT和8个3点DFT模块构成。由于ISF10．1软件提供的FFT IP核模块输入／输出信号均为串行形式，并且每一个时刻3个8点FFT IP核模块输出的数据恰为1个3点DFT的输入信号。因此，为进一步节约资源，提出一种适合FPGA实现的24点DFT实现结构，如图2所示。相对于图1，改进后的24点DFT只需要3个8点FFT IP核模块和1个3点DFT模块，从而能够大幅节约资源。同时，只需相应修改FFT IP核模块相应参数以及串并转换和并串转换的路数，就可以实现长度为N=3×2n点的DFT。

    如图2所示，除了FFT IP核模块，3点DFT模块也是实现24点及N=3×2n点DFT关键模块。如果根据3点DFT变换的定义直接实现，则至少需要4个复数乘法器。为减少乘法器的使用，根据式(5)～式(7)，3点DFT可以按照如图3所示的结构实现，其中，x(0)，x(1)和x(2)表示3点DFT输入信号，y(0)，y(1)和y(2)表3点DFT运算结果。在图3中，数据乘以0．5可以用右移1位的方式实现，而乘以复数时可以采用两个实数乘法器实现，因此设计的3点DFT仅需要两个实数乘法器，从而节约了乘法器资源。同时，该结构采用流水线操作方式，也提高了实现效率。

3 仿真验证
    在ISE10．1环境下，采用VHDL完成了24点DFT模块的开发，并采用Modelsim 6．2 b软件进行仿真验证。同时，为验证设计的24点DFT模块的正确性，将Modelsim仿真结果与Maltab定点仿真程序结果进行了对比。输入信号包括24路并行数据信号、1路时钟信号和1路复位信号，输出信号包括24路并行数据信号、1路输出数据有效信号。图4给出了某一路输出信号的Matlab定点仿真结果与Modelsim仿真结果对比图，其中红色表示Modelsim仿真结果数据，蓝色表示Matlab定点仿真结果。从图4可以看出，该路Modelsim仿真结果与Matlab定点仿真结果一样。其他路输出信号Modelsim仿真结果与Matlab定点仿真结果也一样。从而得出设计的DFT模块完全正确。该模块共占用6个Block RAM，14个乘法器，时序仿真结果表明最高工作频率可达200 MHz，该模块已经成功应用于某一数字分路项目。

4 结束语
    基于Good-Thomas映射算法，并结合ISE10．1软件提供的FFT IP核，提出了一种易于FPGA实现的24点DFT设计结构，设计的24点DFT模块主要由3个8点FFT IP核模块和1个3点DFT模块构成，并且只需要14个实数乘法器。同时，24点DFT模块采用流水线结构，最高工作时钟频率可达200 MHz。该结构还具有良好的扩展性，只需修改FFT IP核模块相应的变换点数参数，就可以实现长度为点的DFT。