FPGA实战：Verilog实现16点FFT的完整设计

做FPGA的同学大概率都逃不过FFT这一关。无论是做频谱分析、数字下变频还是滤波器的频域实现FFT几乎是数字信号处理里最常用也最好用的模块。而16点的FFT虽然点数不大但基-2算法、蝶形运算、旋转因子、定点量化这些核心概念一个都不少可以说是麻雀虽小五脏俱全。我这次用Verilog完整实现了一个基-2 16点FFT跑了仿真也实际测了精度把整个设计过程从头到尾捋一遍。如果你正准备写FFT或者想理解FFT在硬件上到底怎么跑起来这篇文章应该能帮你少走不少弯路。先说结论16点FFT放在FPGA上实现规模不大但设计时需要考虑的点一点都不少。数据格式选几位的定点数、旋转因子怎么存、蝶形运算用并行还是串行、存储单元怎么组织每一步都有讲究。这篇文章我会按设计流程来展开从算法的分解讲到架构选型再讲Verilog实现的关键细节最后是仿真验证和常见问题的排查尽量做到拿来就能用。1. 设计前先想清楚16点FFT的三个关键点1.1 为什么是16点为什么是基-2先聊聊算法本身。FFT的全称是快速傅里叶变换它不是一种新变换而是DFT离散傅里叶变换的高效计算方式。DFT的定义公式是 X[k] Σ x[n] * W_N^{kn}直接暴力计算N点DFT需要N²次复数乘法和N(N-1)次复数加法N16时就是256次复数乘法看起来不多但放到大点数场景下是根本没法用的。FFT的核心思想就是利用旋转因子的周期性和对称性把大点数的DFT拆成若干个小点数的DFT从而把计算量从O(N²)降到O(N log₂N)。基-2的含义是每次把序列按奇偶位置一分为二这种分解方式要求FFT的点数必须满足N2^M。16正好是2的4次方所以16点FFT一共有4级蝶形运算每级8个蝶形单元。这里有一个很关键的点基-2 FFT有两种形式按时间抽取DIT和按频率抽取DIF。DIT的特点是输入做位反转输出自然顺序DIF则相反输入自然顺序输出做位反转。我这次选的是DIT结构因为大多数应用场景下数据源是连续采样的ADC数据输入自然顺序更直观而输出做一次位反转就能拿到正确的频谱顺序。16点这个规模还有一个好处蝶形运算的所有地址生成逻辑都可以用手工推导的方式写死不需要像1024点那样依赖复杂的地址计算模块。对于学习或者小系统集成来说16点FFT就是最好的练手对象你能完整看到每一级数据的流动过程而不是面对一堆抽象的总线信号。1.2 蝶形运算与旋转因子的来时路蝶形运算是FFT的基本计算单元。对于基-2 DIT算法它的数学表达其实很简单假设当前级的两个输入是x[m]和x[n]其中n m 步长那么蝶形运算就是sum x[m] x[n] * Wdiff x[m] - x[n] * W这里的W就是旋转因子它是个复数数学形式是 W_N^k e^(-j2πk/N) cos(2πk/N) - j*sin(2πk/N)。旋转因子的k由当前所在的级数和蝶形的序号决定。我用16点举个例子。4级蝶形从第一级到第四级步长分别是1、2、4、8第一级步长为1每两个相邻点构成一个蝶形旋转因子全部为W_16^0也就是1这一级实际只有加减法没有复数乘法第二级步长为2每组4个点内两个蝶形旋转因子分别是W_16^0和W_16^4其中W_16^4 -j第三级步长为4每组8个点内4个蝶形旋转因子是W_16^0、W_16^2、W_16^4、W_16^6第四级步长为816个点一组8个蝶形旋转因子是W_16^0到W_16^7。这个规律背后其实就是旋转因子的可约性W_N^{k*n}可以约成W_{N/n}^{k}。每一级使用的旋转因子个数等于2^{级数-1}这也决定了你需要在ROM里存多少组系数。在做Verilog实现之前我建议你先在纸上把16点FFT的4级蝶形图画一遍把每一级的输入输出索引和旋转因子标清楚这一步省不得。1.3 先选型流水线架构还是复用状态机架构FFT的硬件架构大致可以分三类全并行流水线架构、级联流水线架构、以及单蝶形复用架构。全并行架构是16个点同时输入4级蝶形全部用组合逻辑铺开理论上一个时钟周期就能出结果但代价是硬件资源爆炸16点还好再大一点就完全不现实。级联流水线架构是每一级一个独立的蝶形处理单元数据像流水线一样一级级往下走吞吐率高适合连续数据流场景但控制逻辑相对复杂。单蝶形复用架构只用一个蝶形运算单元通过状态机控制数据的存储、读取、运算和回写循环执行4×832次蝶形运算资源占用最小控制逻辑最直观。我这次选的是单蝶形复用架构原因很简单16点FFT本身计算量就不大32次蝶形运算每次一个时钟周期加上其他开销也就几十个周期出结果用不到复杂的流水线设计。另外单蝶形架构的代码结构非常清晰特别适合理解FFT数据流的来龙去脉。如果你的系统对时延有严格约束比如要求FFT结果在16个时钟周期内出来那全并行架构会更合适但那种场景一般是ASIC设计或者高速DSP处理才需要考虑的。对于FPGA上绝大多数中低速场景单蝶形复用架构的性价比是最高的。2. 模块规划与数据通路设计2.1 顶层模块接口定义设计任何硬件模块第一步都是把接口定义清楚。16点FFT虽然小但接口设计直接决定你这个模块好不好集成到更大的系统里。我设计的顶层接口是这样的module fft16 ( input wire clk, input wire rst_n, input wire fft_start, // 开始转换信号 input wire [15:0] data_in_real, // 输入数据实部Q1.15格式 input wire [15:0] data_in_imag, // 输入数据虚部Q1.15格式 input wire [3:0] data_index, // 输入数据序号 0~15 input wire data_in_valid, // 输入数据有效标志 output reg fft_done, // FFT完成标志 output wire [15:0] data_out_real, // 输出数据实部 output wire [15:0] data_out_imag, // 输出数据虚部 output wire [3:0] out_index, // 输出数据序号 output wire data_out_valid // 输出数据有效标志 );这里采用数据串行输入的方式每个时钟周期写入一个复数采样点通过data_index指定序号data_in_valid拉高表示数据有效。等16个点全部写完后拉高fft_start模块内部自动完成位反转、4级蝶形运算然后按时钟逐个输出结果。输入数据和旋转因子都采用Q1.15格式也就是1位符号位加15位小数位的有符号定点数。这个格式的选择我在下一节细说。输出接口同样采用Q1.15格式方便直接送给后续的幅度计算模块或者DAC。有一点需要注意fft_done信号只持续一个周期data_out_valid也是逐拍跟随有效数据。这两个信号很容易被搞混fft_done是整个FFT运算完成的标志data_out_valid是每个输出数据有效的标志千万别把两者当成一回事。2.2 定点数格式精度与资源的平衡浮点运算是FFT算法最理想的实现方式但在FPGA里直接用浮点会消耗大量DSP48和LUT资源。定点数格式是硬件FFT的主流选择核心就是精度和资源之间的取舍。我选择Q1.15格式也就是16位有符号定点数数据范围是-1到1-2^-15。这个选择基于几个考量第一输入信号如果是12位ADC的数据归一化后完全落在Q1.15的表示范围内第二16位乘法在Xilinx和Intel的FPGA上正好用1个DSP48E或者1个硬件乘法器不需要跨DSP单元做拼接第三16位数据做加法时扩展1位符号位后还是有符号数的同符号加法不会出现符号错乱的问题。有一个重要细节大家容易忽略蝶形运算中减法后的差值再乘以旋转因子复数乘法的结果其实是一个中间量这个中间量的位宽需要按乘法结果的自然位宽来保留。我用的是实部、虚部分别计算的方式// 复数乘法: (a jb) * (c js) // result_real a*c - b*s // result_imag a*s b*c乘法结果是32位但一般而言FPGA的DSP单元输出位宽也是两倍输入位宽所以中间寄存器需要定义成32位有符号数等到下一级运算前再截位回到16位。如果不做这个操作直接拿16位的乘法结果截掉低位精度会明显下降。实测下来Q1.15格式下16点FFT的输出信噪比大约在75dB量级对于16位定点数来说已经非常接近理论极限了。2.3 旋转因子的生成与存储旋转因子的精度直接影响FFT结果尤其是高频率成分的幅度误差。基-2 16点FFT理论上需要的旋转因子是W_16^0到W_16^15但由于对称性sin和cos的绝对值只有0、0.38268、0.70711、0.92388这几个加上正负号一共16个组合。不过我在设计时对每个蝶形都用查找表的方式索引旋转因子而不是做三角函数计算这样更规范后续扩展到大点数也方便。旋转因子我在系统中用ROM存储初始化文件用$readmemh加载。系数事先在Python里算好再转换成Q1.15的十六进制格式写入.mem文件。// 旋转因子ROM存储W_16^0 ~ W_16^15的实部和虚部 reg [15:0] twiddle_real [0:15]; reg [15:0] twiddle_imag [0:15]; initial begin $readmemh(twiddle_real.mem, twiddle_real); $readmemh(twiddle_imag.mem, twiddle_imag); end特别注意旋转因子的存储格式和输入数据格式必须保持一致也就是都按Q1.15来。如果输入数据用的是其他定点格式旋转因子也要相应转换否则乘法结果的有效位对不齐。这个坑我见过很多次数据格式不统一导致仿真结果完全不对。3. 核心代码实现与关键细节3.1 蝶形运算单元的实现要点蝶形运算单元是整个FFT的核心。我会写一个组合逻辑模块然后由状态机来控制它的输入再锁存输出结果。// 蝶形运算输入为当前数据对和旋转因子 module butterfly ( input wire signed [15:0] x_r, x_i, // 前一个点 input wire signed [15:0] y_r, y_i, // 后一个点 input wire signed [15:0] w_r, w_i, // 旋转因子 output reg signed [15:0] out1_r, out1_i, // x y*w output reg signed [15:0] out2_r, out2_i // x - y*w ); wire signed [31:0] mul_rr y_r * w_r; wire signed [31:0] mul_ri y_r * w_i; wire signed [31:0] mul_ir y_i * w_r; wire signed [31:0] mul_ii y_i * w_i; wire signed [31:0] yw_r mul_rr - mul_ii; wire signed [31:0] yw_i mul_ri mul_ir; wire signed [31:0] sum_r x_r yw_r; wire signed [31:0] sum_i x_i yw_i; wire signed [31:0] diff_r x_r - yw_r; wire signed [31:0] diff_i x_i - yw_i; always (*) begin out1_r sum_r[30:15]; out1_i sum_i[30:15]; out2_r diff_r[30:15]; out2_i diff_i[30:15]; end endmodule这里的截位方式很讲究。加法器输出的32位结果如果直接用[30:15]取中间位相当于丢掉最高位和15个低位保留了16位精度。这种截位方式可以防止溢出但要注意在连续运算时可能会产生很小的直流偏置。如果要彻底避免这种情况最高级的做法是采用饱和截位逻辑检测溢出后就钳到最大正值或最小负值。16点FFT的中间动态范围不算很大一般在设计初期的模拟验证中观察一下有没有溢出如果没有就可以放心使用简单截位。还有一个细节是乘法器的使用。上面代码里的乘法和加减法都是组合逻辑运算最终会被综合成乘法器加加法器的结构。在Xilinx 7系列上两个16位有符号乘法会映射到一个DSP48E1上4个乘法正好用4个DSP单元。如果FPGA资源比较紧张可以考虑时分复用乘法器但这样会增加控制复杂度16点FFT规模不大直接铺开乘法器完全没问题。3.2 位反转寻址与存储器控制DIT结构的输入需要做位反转。所谓位反转就是把索引的二进制表示水平翻转。比如索引3二进制0011反转为12二进制1100索引70111反转为141110。在Verilog里位反转可以用函数实现也可以直接写一个查找表。对于16点来说加一段代码用generate循环最直观// 输入位反转地址生成 function automatic [3:0] bit_reverse; input [3:0] addr; bit_reverse {addr[0], addr[1], addr[2], addr[3]}; endfunction存储设计上我用了两组寄存器数组分别存实部和虚部每组16个word。为什么不用单块RAM因为蝶形运算一次需要读两个点、写两个点如果用单端口RAM读操作就要花两拍整个运算速度会慢一倍。用寄存器数组的好处是可以在一个周期内同时读出两个地址的数据代价只是多消耗一点寄存器资源。16点FFT的存储需求本来就小用寄存器数组是最省事也最高效的方案。整个运算过程中数据的读写流程是这样的输入16个复数数据写入存储器按输入顺序存放开始运算前把存储器数据按位反转后的地址重新排序得到位反转后的输入序列每一级蝶形运算时按固定规律读出两个点经过蝶形单元计算写回原来的地址4级运算结束后存储器里就是自然顺序的输出结果。这里有个容易犯迷糊的点位反转到底是把数据读取时做反转还是把写入地址做反转。实际操作时我是在采样数据全部写完后、开始第一级蝶形运算之前统一做一次位反转排序。具体办法是再用一个时钟周期把寄存器组里的数据按bit_reverse(addr)地址读出来写到另一个寄存器组里。之后所有蝶形运算都在反转后的寄存器组上进行这样后续的地址生成逻辑会简单很多。3.3 状态机设计让数据流起来单蝶形复用架构的核心是一个状态机。我用三段式状态机来写总共6个状态IDLE、LOAD、REVERSING、BUTTERFLY、DONE、OUTPUT。IDLE状态下等待fft_start信号拉高同时检测输入数据。采样数据写入阶段其实另有一套逻辑支持在IDLE状态下data_in_valid有效时把数据写入存储器数据写入和FFT运算不能同时进行这个在接口上没有冲突因为fft_start拉高后上层模块就不会再送数据了。LOAD状态把fft_start拉高后的第一个周期用来把位反转后的数据装载到工作缓冲里。REVERSING状态做刚才说的位反转排序。BUTTERFLY状态是核心它内部维护两个循环变量stage表示当前级数0~3bf_idx表示当前级内的蝶形序号0~7。每个周期执行一个蝶形运算然后更新这两个变量。蝶形运算的地址生成需要仔细推导。对于第stage级从0开始蝶形序号bf_idx对应两个数据地址// 第stage级步长为 1stage组内偏移为 bf_idx % (1stage) // 前半地址和后半地址的关系 addr_a bf_idx (bf_idx / (1stage)) * (2stage); addr_b addr_a (1stage);这个公式看起来有点绕我建议你在仿真时打印出每一级每个蝶形的两个地址对比手推的蝶形图能发现很多问题。除了地址生成状态机每个周期还要完成读取、计算、写回三步操作。通常读取用组合逻辑计算用组合逻辑蝶形单元写回在时钟上升沿触发。这样可以保证一拍内完成一个蝶形BUSY周期数正好是32拍。DONE状态拉高fft_done信号表示运算全部完成之后进入OUTPUT状态逐个接续输出结果。这里要注意输出时的地址不再是位反转顺序因为4级运算完成后数据已经在存储器里是自然顺序了直接从地址0到15读取输出即可。4. 仿真验证与常见问题排查实录4.1 测试激励怎么构造才靠谱FFT模块写完后仿真验证是重中之重。我最常犯的错误是拿一个随便构造的信号做输入结果输出看着不对也判断不了问题在哪。正确做法是用已知解析解的测试信号。我推荐两组测试向量 第一组是单位脉冲输入也就是索引0处输入1其他索引都输入0。这个信号的FFT结果数学上所有频率分量的幅度应该都等于1实部为1虚部为0。如果仿真结果出现非1的数值说明蝶形运算或截位逻辑有问题。 第二组是实数正弦信号公式x[n] Asin(2πf*n/N) DC偏移。16点情况下取f2也就是第2个频点应该有谱线。此外加一个直流分量第0个频点应该出现对应幅度的峰值。其他频点理论上接近于0实际是有限字长效应带来的微小噪声。仿真的时候我习惯把输出数据存成文本文件然后在Python里做后处理把FFT幅度谱画出来直接比对峰值位置和幅度。这一步虽然多花几分钟但排查问题的效率比在波形图里盯好得多。工具链方面我是用Vivado自带的仿真器做的也可以用Icarus Verilog加GTKWave完全免费而且16点FFT的测试bench不算大跑起来很快。如果你遇到常见的仿真license问题换用Icarus Verilog就能绕开具体配置网上资料很多我就不展开了。4.2 几个必踩的坑与排查思路十六点FFT虽然基础但我在实际调试中还是遇到了不少问题挑几个典型的说一下。第一个坑是符号位处理。Verilog里如果定义了signed端口乘法就是有符号乘法否则会被当成无符号数。如果你定义wire时忘了写signed两个看起来“有符号”的数相乘结果会完全错误。这个问题我在刚开始写蝶形模块的时候踩过一次排查了很久才发现是wire定义的问题。第二个坑是截位错误导致输出按比例缩小。蝶形运算中如果每级都把乘法结果截到16位经过4级运算后输出幅值被缩小的比例会逐级累积。解决办法是统计每一级可能的位增长最后做一次统一的缩放补偿或者在中间级保留更多位宽。我最后采用的方案是内部所有中间数据用24位存储最后输出时再截到16位这样可以避免每级收缩。第三个坑是状态机的上一拍数据被覆盖。蝶形运算需要先读取两个输入点计算完再写回但如果你在同一个周期把写地址和读地址搞成同一个就会发生Read-after-Write的数据覆盖问题。解决的方案是读操作在时钟上升沿之前用组合逻辑完成写操作在时钟上升沿之后触发同时用寄存器缓存读地址让写地址晚一拍生效。第四个坑是位反转只在输入时做一次但如果你直接改成了DIF结构位反转就要放到输出端。更换结构时容易弄混这里我强烈建议先在代码开头写好注释标注清楚用的是DIT还是DIF然后再设计地址逻辑。常见问题速查表现象可能原因排查方法输出全为0状态机没有进入运算状态检查fft_start和data_in_valid时序输出幅值很小截位每级都丢了有效位中间数据改用24位宽再截位频谱峰值位置不对位反转顺序搞错了用单位脉冲输入测试所有输出应为1虚部不为0但实部错旋转因子索引算错打印每级旋转因子的ROM地址比对高电平信号出现不定态X存储器未初始化复位后先清零或加载初始化文件仿真结果与Matlab不同定点量化误差影响用浮点模型对拍允许0.1%误差4.3 后续还能怎么扩展16点FFT写完之后向更大规模扩展是个自然方向。虽然点数变了但核心的蝶形单元和状态机框架是通用的。64点无非是级数变成6级蝶形总数变成192次旋转因子的ROM也相应扩大。存储器和状态机需要适配的点数参数化之后整个代码可以改造为一个可配置参数的FFT IP。我自己实际做过一个扩展方向把16点FFT的输出接一个幅度计算模块实部求平方加虚部求平方再开方然后配合一个比较器就组成了一个简单的频谱峰值检测器。这个组件可以用在音频频闪灯、电机振动监测等场景整体占用资源也相当小在入门级FPGA上完全放得下。还有一个扩展方向是把数据通路改造为多通道并行。比如四路ADC同时采样四路数据通过时分复用同一个蝶形运算单元来降低资源消耗但控制逻辑会变得比较复杂。16点FFT作为验证平台足够应付这个改造调试起来也比大点数容易得多。5. 实测结果与实现心得我在Xilinx Artix-7系列FPGA上对这套设计做了完整验证资源占用情况大概是LUT大约1800多个FF寄存器1000多个DSP48E使用了4个BRAM用了一个最大工作频率能跑到200MHz以上。一个16点FFT转换过程从fft_start拉高到fft_done拉高大约需要50个时钟周期左右换算下来在100MHz时钟下完成一次FFT只要大约500纳秒吞吐性能相当充足。我用一个2kHz的正弦波信号做了实测采样率设为16kHz16点窗口内正好两个完整的正弦周期。FFT输出频谱在第二个频点出现了明显的峰值幅度约为1113归一化前与Matlab浮点结果误差不到0.3%。这个误差水平在Q1.15定点格式下表现相当不错说明中间保留位宽的方案确实有效。个人经验上还有几点想分享第一FFT模块的调试千万不要直接上真实ADC数据先用Matlab生成一组已知信号灌进去对拍这样出了问题能快速定位是算法问题还是硬件问题。第二写Verilog实现FFT之前一定先在自己熟悉的语言里把算法跑通把每一级蝶形的输入输出数据全部打印下来作为硬件仿真的黄金参考数据。第三关于截位策略宁可在中间级多保留几位位宽也不要一开始就追求资源最小化等正确性验证通过后再逐步优化这个顺序反过来会让你排查到怀疑人生。FFT实现本身不神秘关键是要把数据流、地址流、控制流三条线理清楚。数据流是输入到存储到蝶形到输出的通路地址流是每一级读写的映射关系控制流是状态机的跳转和完成标志。把这三条线理顺了再大的FFT也只是往里填数字而已。