高速 64 点 FFT 芯片设计技术 引言 FFT(快速傅里叶变换)广泛应用于现代数字信号处理的各个领域，如雷达信号处 理、卫星通信、无线通信等，而专用 FFT 处理芯片已成为其中的关键部件之一， 对系统性能影响较大。本文针对 64 点 FFT 处理器，探讨和研究了采用标准 CMOS 数字工艺库研制 FFT 处理 ASIC(专用集成电路)芯片的若干问题，成果可引伸到 更大点数的 FFT 处理芯片的设计中。 本文介绍了按照固定几何结构 FFT 算法， 采用并行及流水线结构的 FFT 处理器的 原理与电路实现。FFT 处理器主要包括 IO 缓存、数据缓存、旋转因子存储器、 蝶形运算单元、地址产生器、IO 控制器和系统控制器等模块。内部数据采用 IEEE754 标准的单精度浮点格式，实现高精度数据处理。为进一步提高系统数据 吞吐率，FFT 处理器采用双 IO 缓存，可同步进行数据变换和 IO 操作。 1 FFT1 FFT 原理及运算流图的改进原理及运算流图的改进 DFT(离散傅里叶变换)满足以下关系式： 式中： 序列 x(n)及 X（k）均是复数表示。Cooly 和 Tukey 提出的的 FFT 算法利用系数 WknN 的对称性和周期性，大大减小了 DFT 的运算量。 G(k)仪包含 x(n)中偶数点序列，而 H(k)仅包含 x(n)中奇数点序列，考虑 G(k)、 H(k)的周期性，得到： 经典 FFT 运算流图的缺点是每级蝶形运算数据寻址方式都不同，FFT 处理器寻址 电路设计复杂。本文采用了一种固定几何结构的 FFT 运算方法，每级运算采用相 同寻址电路，简化了电路设计。 下面以 16 点 FFT 运算为例，分析固定几何结构 FFT 运算流图。如图 1 所示，固 定几何结构的 FFT 运算流图中，每级蝶形运算寻址结构相同，序列中每相隔 N 2 的两个数据送入一个蝶形运算单元进行处理，输出结果顺序排列。由于该流图 数据处理具有倒序的特点，所以旋转因子也采用倒序输入，并且，得到的变换结 果也为倒序排列。 本文采用 C 语言对该流图算法进行模拟，证明该结构正确可行。 2 FFT2 FFT 处理器的结处理器的结构与模块划分构与模块划分 FFT 处理器主要包括蝶形运算单元、数据缓存、IO 缓存、地址生成器、运算控 制器，IO 控制器。 为实现高速处理，本文采用并行结构处理数据，并用流水线结构实现蝶形运算单 元。为进一步提高系统工作效率，采用双缓存分别用作数据缓存及 IO 缓存， 进行 FFT 操作的同时，读入新的待处理数据，输出之前的处理结果，实现数据处 理和 IO 操作的并行。由于 FFT 运算按特定方式寻址，且变换结果倒序排列， 因此，需要一组地址生成器用于数据处理及 IO 操作的寻址。运算控制器和 I O 控制器共同控制系统各模块协同工作。 3 3 流水流水线结构蝶形运算单元的实现线结构蝶形运算单元的实现 蝶形运算单元的性能直接影响到处理器的工作速度。 由于数据采用 IEEE754 标准 单精度浮点格式， 因此蝶形运算单元的浮点加法器及浮点乘法器是电路设计的难 点之一。 如图 2 蝶形结所示，蝶形运算的一次复数乘法包含 4 次乘法和 2 次加减法，若 将旋转因子 W 对应的 C，C+S，C-S 预先存入 ROM，采用 则如式(4)、(5)所示，一次复数乘法只需要 3 次乘法和 3 次加减法。用 1 次减 法取代乘法，降低了电路的面积和功耗。 因此，可以根据各数据的运算顺序，采用并行处理和流水线结构实现蝶形运算单 元，其结构见图 3。 3.1 3.1 浮点加法器的设计实现浮点加法器的设计实现 由于 FFT 为复数运算，因此数据的实部、虚部均采用 IEEE754 标准 32bit 单精度 浮点格式，字长为 64 bit。 如图 4 所示，浮点加法器可分为 3 部分。首先通过 data_man 模块，将数据的符 号位、指数、尾数分离，并进行预处理；然后根据指数的差值，将尾数部分移位 对齐，并在 26 bit 位宽的 CSA(进位选择加法器)_26 中进行相加；最后将数据处 理成为 IEEE 754 标准格式。 2624 bit 移位电路 shiftAB 以及 26 bit 加法器是影响浮点加法器性能的关 键电路。 图 5 为 26 bit 尾数移位对齐电路，其利用移位位数 diffA7：0的各比特作为 控制信号，通过 6 个 26 bit 的 2：1 选择器实现移位，具有较高的速度和稳定性。 图 6 为进位选择全加器 AFCS 示意图。 进位选择加法器 AFCS 的逻辑表达式为： 此全加器同时进行进位为 0 和 1 的全加运算，通过进位选择全加器运算结果，节 省了等待前级运算进位的时间。 图 7 为由 6 个 AFCS 构成的 6 bit 进位选择加法器 AF_6，图 8 为由 AF_6AF_8 构成的 26 bit 两级进位选择加法器 CSA_26。 在浮点加法器的基础上，实现浮点减法器只要将减数的符号位取反后，再与被减 数相加即可。 3.2 3.2 浮点乘法器的设计实现浮点乘法器的设计实现 浮点乘法器也可分为 3 部分。首先，将数据的符号位、指数、尾数分离，并进行 预处理。然后，将尾数在 24 bit 位宽进位保留阵列乘法器 CSM_24 中相乘，并将 指数相加。最后，将尾数乘积、指数和以及符号位处理成 IEEE 754 标准格式。 浮点乘法器结构见图 9。 浮点乘法器中 24 bit 位宽乘法器 CSM_24 是影响整个浮点乘法器速度的关键电 路。 本文采用进位保留阵列乘法器来实现 24 bit 位宽乘法，图 10 以 12 bit 乘法为 例说明 CSM_24 的结构。Ai 表示被乘数与乘数每比特相乘的部分积， Si 表示一次 求和的结果，Ci 表示每次求和时保留的进位值。乘法器阵列采用华莱土树结构， 由 HA(半加器)实现 2 点加法，FA(全加器)实现 3 点加法，12 个加法器(HAFA) 并行求和，进位值保留到下一次求和时再进行相加，省去了每次求和时等待串行 进位的时间，大大提高了乘法器速度。 4 4 数据缓存设计方案数据缓存设计方案 为提高处理器速度，本文采用 ping-pang 结构的数据存储器。由于采用 2 个蝶形 运算单元并行处理，所以将 ping-pang 结构的存储器每组再分为 2 块。每组存储 器的 2 块 RAM 并行输出或写入 2 个蝶形运算单元处理前后的数据。 由于流水线结构实现的蝶形运算单元存在等待周期， 所以会出现对一组 RAM 同时 读写的情况，因此本文中 RAM 采用双端口输入输出结构。 在对一组 RAM 同时读写时，要确保 RAM 中还未处理的数据不被写入的数据覆盖， 根据数据寻址特点，在本文设计中，蝶形运算单元的流水线级数不应超过 FFT 序列长度的 14。随着处理序列点数的增加，可增加蝶形运算单元流水线级数， 实现更高处理速度。 根据固定几何结构 FFT 算法特点，由于每块 RAM 读写寻址具有相同的规律，数据 缓存的 4 块 RAM 可共用一组生成地址器。 旋转因子数值预先存入 1 块 ROM，由旋转因子地址发生器进行寻址。 5 I5 IO O 设计方案设计方案 5.1 I5.1 IO O 端口设计端口设计 外部输入信号包括：时钟同步复位信号 RESET、64 bit 待处理数据信号 dataIn 以及外部 IO 设备准备就绪信号 IOBR。 处理器输出信号包括：64 bit 处理结果数据 dataOut 以及 IO 缓存准备就绪信 号 IO_ready。 当 IOBR 和 IO_ready 同时为高电平，表示外部输入输出设备及 IO 缓存均准备 就绪，可以进行 IO 操作。当 IO 操作开始后，IOBR 和 IO_ready 又重新置为 低电平。 5.2 I5.2 IO O 缓冲存储器缓冲存储器 FFT 处理器采用双缓存结构同时进行数据处理和 IO 操作。IO 缓存中，存有 上一次变换结果的一组 RAM 向外设输出数据， 另一组 RAM 从外设读入新的待处理 数据。当数据处理与 IO 操作均完成后，两组缓存进行功能交换，准备进行新 一轮操作。 6 FFT6 FFT 运算控制器与运算控制器与 I IO O 控制器控制器 FFT 运算控制器用于控制进行 FFT 运算的各模块工作， IO 控制器用于控制数据 输入输出以及与外部设备的通信，2 个控制器相互通信，共同控制处理器各模块 协同工作。 IO 控制器和 FFT 运算控制器分别对 2 组缓存中的每块 RAM 产生 IO 及读写使 能控制信号，控制 2 组缓存交替用于 IO 和运算操作，并控制具体操作中每块 RAM 的读写工作模式。 当处理器中数据运算或 IO 操作完成时，对应控制器产生一个完成信号 FFT_done 或 IO_done，输入到另一个控制器，当 2 个控制器均检测到对方输出 的操作完成信号，则表示一次数据运算及 IO 操作完成。此时，2 个控制器重 置 2 组缓存的使能信号，交换 2 组缓存功能，开始新一轮 FFT 运算及 IO 操作。 7 7 各关键模块各关键模块 Verilog HDLVerilog HDL 电路描述的逻辑仿真与验证电路描述的逻辑仿真与验证 本文采用 Verilog HDL 语言对 FFT 处理器的各个模块进行 RTL(寄存器传输级)设 计，采用 ModelSim 仿真软件，对整个系统及各关键模块进行逻辑仿真与验证。 由于系统中定义的信号数目庞大，因此，按各关键模块的功能要求，分别给出其 逻辑仿真波形图。 图 11、图 12 和图 13 分别为浮点加法器、浮点乘法器和蝶形运算单元模块在 ModelSim 中的仿真波形，信号波形与 Matlab 中计算得到的参考数据相符，表明 模块功能正确。 图 14 为 IO 控制器模块输出的 IO 缓存使能控制信号波形，在连续的 FFT 处 理中，两组缓存交替用做数据处理缓存和 IO 缓存，信号波形表明模块设计功 能正确。 由于处理器采用 ping-pang 结构的数据缓存， 缓存的 2 组 RAM 交替进行处理数据 的读写，因此，64 点 FFT 包含 6 级蝶形运算，每组数据存储器分别交替进行 3 次渎写。图 15 为数据缓存读写使能控制信号仿真波形，仿真波形表明 FFT 运算 控制器模块功能正确。 同时，根据整个系统工作的仿真波形及时间轴参考，预计系统完成一次 FFT 以及 IO 操作需要约 100 个时钟周期，与根据 FFT 运算流图估计所需的时钟周期数 目相符。 8 8 结束语结束语 本设计采用并行结构及流水线方式实现 FFT 处理器电路， 并通过双缓存实现数据 处理与 IO 操作并行工作，提高了系统的工作效率及灵活性。同时，对蝶形运 算单元中高速浮点加法器乘法器的实现进行了设计分析。 本文从系统的整体结 构、 工作模式以及具体模块的硬件电路实现等方面对高速 FFT 处理器的设计进行 了探索研究。