场景与任务
通信、雷达和部分机载场景要把连续数据流做实时谱分析。指令流平台吞吐不够，GPU 功耗偏高，赛题要求把 FFT 做到 FPGA 上，并相对基线再提速。
返回竞赛作品
Competition · 2023
基于 FPGA 的 FFT 算法并行优化
第十二届中国软件杯 · 基 4 MDC 流水线
把基线基 2 SDF 换成 4 路并行的基 4 MDC。1024 点在同样 20 ns 时钟下从 2057 拍降到 513 拍，约 4.01 倍；末级可切基 4 / 基 8，覆盖 16 点以上的 2ⁿ 点。
国家二等奖
中国软件杯
4.01×
相对基 2 SDF
513 拍
1024 点延迟
~76 dB
定点 SNR
01
项目背景
赛题要求
赛题要求两件事：1024 点在相同时钟下相对基 2 SDF 提速 4 倍；算法能伸缩到 2048、4096。验证落在 Vivado 2018.3 + Modelsim 功能仿真，用 MATLAB 出激励和 SNR。
为什么难
- 全并行面积太大，基 2 SDF 单路吞吐又不够 4 倍。
- 纯基 4 只能算 4ⁿ 点，2048 这类 2ⁿ 点要补零，浪费拍数。
- 4 路数据必须按级对齐，换向或旋转因子错一拍，频谱就对不上。
- 定点复乘会溢出、截位，必须和 MATLAB 金标准对上。
02
系统架构
顶层按点数生成 log₄N 级流水。中间级是标准 MDC 单元，末级是基 4/8 蝶形。每级 4 路并行：蝶形 → 打拍 → 复乘 → 延迟 → 换向 → 再延迟。
第一路旋转因子恒为 1，不进复乘。控制模块用同一个计数器同时给出换向选择和旋转因子地址。
03
核心系统设计
用 R4MDC 换基线 R2SDF
问题：基 2 SDF 单路串行，1024 点要 2057 拍，到不了赛题的 4 倍。
改动：改成 4 路 Multi-path Delay Commutator，按 log₄N 级流水；1024 点 5 级。
效果：同样 20 ns 时钟，50 ns 进到 10310 ns 出，共 513 拍，相对基线 4.01 倍。
基 4 蝶形一次吃 4 点
问题：基 2 级数多，复乘次数也多。
改动：每级用基 4 加减完成复加；第 1 路 W=1 直通，另外 3 路再复乘。
效果：复乘次数大约是基 2 的 3/4，每级只留 3 个复数乘法器。
延迟换向，把 4 路对齐
问题：4 路到达时刻不同，直接进下一级会乘错旋转因子。
改动：复乘后按 D、2D、3D 延迟；换向做行列转置；再延迟收齐。控制 FSM 和一个计数器同时出 data_sel 和旋转因子地址。
效果：各级数据对得上，控制流和数据流拆开，少占一套计数逻辑。
末级基 4/8，解决伸缩
问题：传统基 4 MDC 只能算 4ⁿ 点。2048 要补零，多算很多拍。
改动：末级改成基 4/8：4ⁿ 只走基 4；2ⁿ 但非 4ⁿ 时再补一级基 2（W₈¹ / W₈³）。
效果：同一套顶层覆盖 16 点以上任意 2ⁿ，2048 / 4096 不用另开工程。
旋转因子只存 N/8+1
问题：离线存满 N 个旋转因子太占 ROM；在线生成又拉长关键路径。
改动：MATLAB 预生成前 N/8+1 点；其余按八分圆对称做保留、取反或实虚互换。
效果：存储从 N 降到 N/8+1，查表延迟仍是一拍。
定点复乘防溢出
问题：64 bit 补码乘完会超出位宽，截位不当频谱会歪。
改动：数据与旋转因子都用 32 实 + 32 虚；旋转因子走 Q 格式，复乘后右移 16 再截位。
效果：三组 1024 点双音 SNR 约 76 dB，和 MATLAB 金标准对得上。
04
仿真与验证
验证分三步：先用 Modelsim 看模块对不对，再量整条流水线从进到出的拍数，最后把输出拉回 MATLAB 对频谱和 SNR。激励是双音信号，放大 1000 倍写成 64 bit 定点。金标准是自写基 2 DIF。差值超过 200 报警。工具是 Vivado 2018.3 和 Modelsim DE-64 10.6c。
4.01×
加速比
2057 / 513，相对基 2 SDF
513 拍
1024 点延迟
时钟 20 ns，50 ns 进到 10310 ns 出
~76 dB
1024 点 SNR
三组双音，差值阈值 200
16–4096
可配点数
2048 / 4096 点 SNR 仍约 75 dB
组 1 · 1 kHz
200 + 300 Hz 等幅双音，1024 点。超阈值 0 处，SNR 75.94 dB。
组 2 · 1 MHz
200 k + 300 kHz，1024 点。超阈值 0 处，SNR 75.94 dB。
组 3 · 100 kHz
10 k + 20 kHz，幅度 1:2。超阈值 1 处，SNR 76.05 dB。
伸缩
同组 1 激励扩到 2048 / 4096 点，SNR 75.01 / 75.82 dB。
模块级波形
先确认控制、蝶形、换向和单级流水各自能跑通，再接到顶层。下面四张都是 Modelsim 功能仿真，黑底绿线是信号取值。
- 控制：data_sel 四路错开一拍，旋转因子地址跟着计数器走。
- 蝶形：data_i_en 拉高后，四路立刻拆成实虚部并算出 data_o。
- 换向：data_sel 按 0–3 循环时，四路输出完成行列转置。
- 单级：蝶形 → 复乘 → 延迟 → 换向，中间量依次出现再传到 data_o。
控制模块
基 4 蝶形
四路换向
单级流水线
顶层时序与 4 倍加速
模块接好后，用 16 点看延迟是否对得上理论；再用 1024 点量整次变换的拍数。时钟 20 ns。基线基 2 SDF 要 2057 拍，这里要压到 514 拍以内。
- 16 点：输入使能结束后再过几拍，四路输出才出现，延迟和级数相符。
- 1024 点输入：50 ns 开始灌 4 路，对应报告里的起始光标。
- 1024 点输出：约 10310 ns 收口。 (10310−50)/20 = 513 拍，2057/513 ≈ 4.01 倍。
16 点顶层
1024 点 · 输入起点
1024 点 · 输出终点
频谱对照与 SNR
硬件输出写成 test_real_out / test_imag_out，再送回 MATLAB。上面一张是金标准，下面一张是流水线 FFT。谱峰位置和相对幅度对得上，再算 SNR。
- 组 1：200 Hz 和 300 Hz 各一根谱线，两侧幅度差在小数点后，SNR 75.94 dB。
- 组 3：10 kHz / 20 kHz，幅度约 1:2，用来看定点有没有把小峰吃掉，SNR 76.05 dB。
组 1 · 等幅双音
组 3 · 幅度 1:2
05
个人职责
主责
算法负责人：把基线从 R2SDF 换成 R4MDC，推 4 倍加速对应的拍数，设计边界对齐、末级混合基和旋转因子压缩，并用 MATLAB 金标准卡 SNR。
VerilogR4MDC混合基定点VivadoModelsimMATLAB
06
证书
第十二届中国软件杯决赛国家级二等奖，点击可查看原件 PDF。
获奖证书
