R22FFT算法的FPGA硬件结构优化设计与实现

doi:10.11772/j.issn.1001-9081.2024071010

《计算机应用》唯一官方网站 ›› 2025, Vol. 45 ›› Issue (8): 2637-2645.DOI: 10.11772/j.issn.1001-9081.2024071010

• 先进计算 • 上一篇

R2²FFT算法的FPGA硬件结构优化设计与实现

肖海林¹(), 杨昱东², 杨紫伊², 刘海龙¹, 王玉¹, 张中山³, 戴晓明⁴

^1.湖北大学计算机与信息工程学院，武汉 430062
^2.湖北大学人工智能学院，武汉 430062
^3.北京理工大学信息与电子学院，北京 100081
^4.北京科技大学计算机与通信工程学院，北京 100083

收稿日期:2024-07-17 修回日期:2024-10-18 接受日期:2024-10-21 发布日期:2024-11-19 出版日期:2025-08-10
通讯作者: 肖海林
作者简介:杨昱东（1999—），男，湖北荆门人，硕士研究生，主要研究方向：数字图像处理、现场可编程门阵列
杨紫伊（1999—），女，四川成都人，硕士研究生，主要研究方向：车载通信、智能反射面辅助通信
刘海龙（1989—），男，湖北随州人，讲师，博士，主要研究方向：嵌入式系统、硬件安全
王玉（1998—），女，河南信阳人，硕士研究生，主要研究方向：信息隐藏、信息加密
张中山（1974—），男，河北遵化人，教授，博士，主要研究方向：5G与B5G通信
戴晓明（1973—），男，湖南岳阳人，教授，博士，主要研究方向：宽带无线通信、音信号处理、芯片设计。
基金资助:
国家自然科学基金项目(61872406);广西科技重大专项(桂科AA24263034);广西重点研发计划项目(桂科AB25069340);湖北省高等学校优秀中青年科技创新团队计划项目(T2021001)

Design and implementation of FPGA hardware structure optimization based on R2²FFT algorithm

Hailin XIAO¹(), Yudong YANG², Ziyi YANG², Hailong LIU¹, Yu WANG¹, Zhongshan ZHANG³, Xiaoming DAI⁴

^1.School of Computer Science and Information Engineering，Hubei University，Wuhan Hubei 430062，China
^2.School of Artificial Intelligence，Hubei University，Wuhan Hubei 430062，China
^3.School of Information and Electronics，Beijing Institute of Technology，Beijing 100081，China
^4.School of Computer and Communication Engineering，University of Science and Technology Beijing，Beijing 100083，China

Received:2024-07-17 Revised:2024-10-18 Accepted:2024-10-21 Online:2024-11-19 Published:2025-08-10
Contact: Hailin XIAO
About author:YANG Yudong， born in 1999， M. S. candidate. His research interests include digital image processing， field programmable gate array.
YANG Ziyi， born in 1999， M. S. candidate. Her research interests include in-vehicle communication， intelligent reflecting surface assisted communication.
LIU Hailong， born in 1989， Ph. D.， lecturer. His research interests include embedded systems， hardware security.
WANG Yu， born in 1998， M. S. candidate. Her research interests include information hiding， information encryption.
ZHANG Zhongshan， born in 1974， Ph. D.， professor. His research interests include 5G and B5G communications.
DAI Xiaoming， born in 1973， Ph. D.， professor. His research interests include broadband wireless communication， audio signal processing， chip design.
Supported by:
National Natural Science Foundation of China(61872406);Guangxi Science and Technology Major Project(Guike AA24263034);Guangxi Key Research and Development Program(Guike AB25069340);Hubei Provincial Colleges and Universities Outstanding Young and Middle-aged Science and Technology Innovation Team Program(T2021001)

摘要/Abstract

摘要：

针对快速傅里叶变换（FFT）算法处理大规模数据时因消耗大量资源和时间而导致运算速度慢的问题，提出一种基2²快速傅里叶变换（R2²FFT）算法的现场可编程门阵列（FPGA）硬件结构优化设计与实现方法。首先，采用R2²FFT算法构建一种序列转换功能与流水线结构相结合的Y形双并行阵列结构，在有效降低硬件乘法器使用数量的同时，增大硬件结构的吞吐量，提高FFT算法在FPGA上的运算速度；其次，通过在R2²FFT流水线的单级运算中利用旋转因子的相关特性，优化片上存储的资源消耗，使存储空间降低约50.00%；最后，在完成N点R2²FFT算法结构优化的基础上，进一步提高硬件结构的可扩展性，即实现 $2 N$ 点和 $4 N$ 点的扩展运算。采用Verilog HDL语言完成硬件设计，并通过Modelsim仿真，使用Vivado2018.3软件将所提方法综合并布局布线，并分析所提方法的性能。实验结果表明，与4种改进的FFT硬件实现方法的运算时间相比，所提方法的运算时间分别降低了75.10%、95.34%、38.49%和49.20%，可见所提方法显著提高了运算速度。同时，所提方法资源消耗适中，消耗占比低，且具有运行功耗低以及可扩展性强的特点。

关键词: Y形双并行阵列结构, 现场可编程门阵列, 基2²快速傅里叶变换, 多路径延迟交叉结构流水线, 蝶形运算

Abstract:

A design and implementation method of Field Programmable Gate Array （FPGA） hardware structure optimization based on Radix 2² Fast Fourier Transformation （R2²FFT） algorithm was proposed to solve the problem that Fast Fourier Transformation （FFT） algorithm requires a lot of resources and time to process large-scale data and thus leading to a low operation speed. Firstly， by using R2²FFT algorithm， a Y-shaped dual parallel array structure combining a sequence conversion function and a pipeline structure was constructed， which reduced the usage number of hardware multipliers and increases throughput of hardware structure， so as to improve operation speed of FFT algorithm on FPGA. Secondly， correlation characteristics of the twiddle factors were adopted in single-stage operation of the R2²FFT pipeline to optimize the on-chip storage resource consumption and reduce storage space by about 50.00%. Finally， scalability of hardware structure was further improved in realizing expansion operations such as $2 N$ points and $4 N$ points based on optimization of N-point R2²FFT algorithm structure. Verilog HDL language and Modelsim were utilized to implement hardware design and simulation， respectively. Then， the proposed method was synthesized and placed-and-routed by using Vivado2018.3 software， and performance analysis was carried out. Experimental results show that compared with four improved FFT hardware implementation methods， the proposed method reduces the operation time by 75.10%， 95.34%， 38.49%， and 49.20%， respectively， which shows significant improvement of the method in operation speed. At the same time， the resource consumption of the proposed method is reasonable and the consumption proportion of the method is low， and the method has characteristics of low operation power consumption and strong scalability.

Key words: Y-shaped dual parallel array structure, Field Programmable Gate Array (FPGA), Radix 2² Fast Fourier Transformation (R2²FFT), Multi-path Delay Cross (MDC) structure pipeline, butterfly operation

中图分类号:

TP332

肖海林, 杨昱东, 杨紫伊, 刘海龙, 王玉, 张中山, 戴晓明. R2²FFT算法的FPGA硬件结构优化设计与实现[J]. 计算机应用, 2025, 45(8): 2637-2645.

Hailin XIAO, Yudong YANG, Ziyi YANG, Hailong LIU, Yu WANG, Zhongshan ZHANG, Xiaoming DAI. Design and implementation of FPGA hardware structure optimization based on R2²FFT algorithm[J]. Journal of Computer Applications, 2025, 45(8): 2637-2645.

图/表 18

表1 R2FFT与R22FFT运算量对比

Tab.1 Comparison of computational complexity between R2FFT and R22FFT

算法	复数乘法次数	复数加法次数
R2FFT	$N / 2 * l b N - (N - 1)$	$N * l b N$
R2²FFT	$3 N / 4 * l o g 4 N - (N - 1)$	$N * l b N$

表1 R2FFT与R22FFT运算量对比

Tab.1 Comparison of computational complexity between R2FFT and R22FFT

算法	复数乘法次数	复数加法次数
R2FFT	$N / 2 * l b N - (N - 1)$	$N * l b N$
R2²FFT	$3 N / 4 * l o g 4 N - (N - 1)$	$N * l b N$

图1 FPGA硬件结构

Fig. 1 FPGA hardware structure

图2 Y形双并行阵列结构

Fig. 2 Y-shaped double parallel array structure

图3 R22FFT单级模块

Fig. 3 R22FFT single-stage module

图4 复数乘法器模块

Fig. 4 Multi-multiplier module

图5 N=16点的Y形双并行阵列结构设计

Fig. 5 Y-shaped dual parallel array structure design with N=16 points

图6 N=1?024点的R22FFT扩展模块

Fig. 6 R22FFT expansion module with N=1?024 points

图7 N=1?024点的R2SDF-FFT硬件实现方法的Modelsim仿真

Fig. 7 Modelsim simulation of R2SDF-FFT hardware implementation method with N=1?024 points

图8 N=1?024点的所提方法的Modelsim仿真

Fig. 8 Modelsim simulation of proposed method with N=1?024 points

图9 N=1?024点时理想频谱和所提方法频谱的对比

Fig. 9 Comparison of ideal spectrum and proposed method spectrum with N = 1 024 points

图10 N=2?048点时理想频谱和所提方法频谱的对比

Fig. 10 Comparison of ideal spectrum and proposed method spectrum with N = 2 048 points

图11 虚部误差

Fig. 11 Imaginary part error

图12 实部误差

Fig. 12 Real part error

图13 综合与布局布线结果

Fig. 13 Synthesis and place-and-route results

表2 电路资源消耗报告

Tab. 2 Circuit resource consumption report

资源类型	资源消耗	资源总数	利用率%
LUT	8 176.00	254 200	3.22
LUTRAM	1 450.00	90 600	1.60
FF	3 098.00	508 400	0.61
BRAM	4.50	795	0.57
DSP	114.00	1 540	7.40

图14 FFT硬件电路的运行功耗

Fig. 14 Operating power consumption of FFT hardware circuit

图15 硬件电路时序报告

Fig. 15 Hardware circuit time sequence report

表3 本文方法与其他优化方法的对比

Tab. 3 Comparison of proposed method and other optimization methods

方法	算法基	算法结构			可扩展性	硬件平台
R2SDF-FFT	R2FFT	SDF			否	xc7k410tffg900-2
文献［6］方法	R4FFT	4路并行			否	Virtex-7XC7VX330T
文献［7］方法	R2FFT	14级流水线			是	ZynqXCZU5EV
文献［8］方法	R2²FFT	MDC流水线			是	Virtex-6
本文方法	R2²FFT	Y形双并行阵列结构			是	xc7k410tffg900-2
						Virtex-7XC7VX330T
						Virtex-6
方法	功耗/W	Slice	LUT	LUTRAM	FF	BRAM	DSP	BUFG	计算时间/μs（1 024点）
R2SDF-FFT	—	—	6 398	2 211	1 338	0.0	160	1	41.14
文献［6］方法	—	—	6 248	—	—	12.0	—	—	220.00
文献［7］方法	4.180	—	52 302	1 792	32 449	53.5	—	3	16.65
文献［8］方法	—	4 665	4 317	—	6 280	11.0	—		20.16
本文方法	0.472	2 323	8 176	1 450	3 098	4.5	114	1	10.24
	0.334	2 378	8 176	1 449	3 098	4.5	114	1	10.24
	—	2 043	7 225	—	2 672	—	114	1	10.24

参考文献 17

[1]	洪钦智，王志君，郭一凡，等. 一种支持多数据块混合处理的FFT优化方法［J］. 西安电子科技大学学报， 2022， 49（6）： 42-50.
	HONG Q Z， WANG Z J， GUO Y F， et al. Multi-data mixed FFT processing optimization method［J］. Journal of Xidian University， 2022， 49（6）： 42-50.
[2]	高媛，赵禹，王厚军，等. 数字示波器中FPGA间高速信号传输同步方法［J］. 电子科技大学学报， 2024， 53（2）： 219-226.
	GAO Y， ZHAO Y， WANG H J， et al. High-speed signal transmission synchronization method between FPGAs in digital oscilloscopes［J］. Journal of University of Electronic Science and Technology of China， 2024， 53（2）： 219-226.
[3]	INGEMARSSON C， KÄLLSTRÖM P， QURESHI F， et al. Efficient FPGA mapping of pipeline SDF FFT cores［J］. IEEE Transactions on Very Large Scale Integration （VLSI） Systems， 2017， 25（9）： 2486-2497.
[4]	KANDERS H， MELLQVIST T， GARRIDO M， et al. A 1 million-point FFT on a single FPGA［J］. IEEE Transactions on Circuits and Systems I： Regular Papers， 2019， 66（10）： 3863-3873.
[5]	GHOUWAYEL A AL， LOUET Y. FPGA implementation of a re-configurable FFT for multi-standard systems in software radio context［J］. IEEE Transactions on Consumer Electronics， 2009， 55（2）： 950-958.
[6]	SANKARAN A， REDDY M S， ARUNKUMAR K R， et al. Design and implementation of 1024 point pipelined radix 4 FFT processor on FPGA for biomedical signal processing applications［C］// Proceedings of the 2020 IEEE International Symposium on Smart Electronic Systems. Piscataway： IEEE， 2020： 1-6.
[7]	王海淼. 基于FPGA的实时FFT分析方法研究［D］. 哈尔滨：哈尔滨工业大学， 2021： 17-33.
	WANG H M. Research on FPGA-based real-time FFT analysis［D］. Harbin： Harbin Institute of Technology， 2021： 17-33.
[8]	杨苗苗，郭锋，张永亮. 多路并行流水线型基2²FFT算法实现［J］. 陆军工程大学学报， 2023， 2（2）： 54-59.
	YANG M M， GUO F， ZHANG Y L. Implementation of multi-path parallel-pipelined radix 2²FFT algorithm［J］. Journal of Army Engineering University of PLA， 2023， 2（2）： 54-59.
[9]	才华，陈广秋，刘广文，等. 基于FPGA架构的可变点FFT处理器设计与实现［J］. 吉林大学学报（理学版）， 2018， 56（1）： 151-158.
	CAI H， CHEN G Q， LIU G W， et al. Design and implementation of variable points FFT processor based on FPGA architecture［J］. Journal of Jilin University （Science Edition）， 2018， 56（1）： 151-158.
[10]	SEKHAR B R， PRABHU K M M. Radix-2 decimation-in-frequency algorithm for the computation of the real-valued FFT［J］. IEEE Transactions on Signal Processing， 1999， 47（4）： 1181-1184.
[11]	YU C， YEN M H. Area efficient 128- to 2048/1536-point pipeline FFT processor for LTE and mobile WiMAX systems［J］. IEEE Transactions on Very Large Scale Integration （VLSI） Systems， 2015， 23（9）： 1793-1800.
[12]	SIU T W， SHAM C W， LAU F C M. Operating frequency improvement on FPGA implementation of a pipeline large-FFT processor［C］// Proceedings of the 19th International Conference on Advanced Communication Technology. Piscataway： IEEE， 2017： 5-9.
[13]	MACTAGGART I R， JACK M A. A single chip radix-2 FFT butterfly architecture using parallel data distributed arithmetic［J］. IEEE Journal of Solid-State Circuits， 1984， 19（3）： 368-373.
[14]	LE BA N， KIM T T H. An area efficient 1024-point low power radix-2² FFT processor with feed-forward multiple delay commutators［J］. IEEE Transactions on Circuits and Systems I： Regular Papers， 2018， 65（10）： 3291-3299.
[15]	GYANENDRA， RAMAN B， KAUSHIK B K. Novel bit-reordering circuit for continuous-flow parallel FFT architectures［J］. IEEE Transactions on Circuits and Systems Ⅱ： Express Briefs， 2020， 67（12）： 3392-3396.
[16]	RAFFERTY C， O’NEILL M， HANLEY N. Evaluation of large integer multiplication methods on hardware［J］. IEEE Transactions on Computers， 2017， 66（8）： 1369-1382.
[17]	LI B， YAN Y F， WEI Y X， et al. Scalable and parallel optimization of the number theoretic transform based on FPGA［J］. IEEE Transactions on Very Large Scale Integration （VLSI） Systems， 2024， 32（2）： 291-304.

R2²FFT算法的FPGA硬件结构优化设计与实现

Design and implementation of FPGA hardware structure optimization based on R2²FFT algorithm

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 18

参考文献 17

相关文章 15

编辑推荐

Metrics

[1]	申云飞, 申飞, 李芳, 张俊. 基于张量虚拟机的深度神经网络模型加速方法[J]. 《计算机应用》唯一官方网站, 2023, 43(9): 2836-2844.
[2]	马英杰, 肖靖, 赵耿, 曾萍, 杨亚涛. 可控网格多涡卷混沌系统族及其硬件电路实现[J]. 《计算机应用》唯一官方网站, 2023, 43(3): 956-961.
[3]	宋斌威, 王耀. 面向FPGA 知识产权保护的低开销按次付费授权方案[J]. 《计算机应用》唯一官方网站, 2023, 43(10): 3142-3148.
[4]	许英鑫, 孙磊, 赵建成, 郭松辉. 基于蚁群优化算法的虚拟现场可编程门阵列部署策略[J]. 计算机应用, 2020, 40(3): 747-752.
[5]	雷小康, 尹志刚, 赵瑞莲. 基于FPGA的卷积神经网络定点加速[J]. 计算机应用, 2020, 40(10): 2811-2816.
[6]	谭海清, 陈正国, 陈微, 肖侬. 基于FPGA的DDR3协议解析逻辑设计[J]. 计算机应用, 2017, 37(5): 1223-1228.
[7]	麦涛涛, 潘晓中, 王亚奇, 苏阳. 基于预定义类的紧凑型正则表达式匹配算法[J]. 计算机应用, 2017, 37(2): 397-401.
[8]	薛俊, 段发阶, 蒋佳佳, 李彦超, 袁建富, 王宪全. 基于Matlab的并行循环冗余校验Verilog代码自动生成方法[J]. 计算机应用, 2016, 36(9): 2503-2507.
[9]	卓艳男, 刘强, 姜磊, 戴琼. 基于FPGA改进电路的高性能正则表达式匹配算法[J]. 计算机应用, 2016, 36(4): 927-930.
[10]	辛小霞, 王奕, 李仁发. 基于现场可编程门阵列的SMS4故障检测实现[J]. 计算机应用, 2015, 35(2): 420-423.
[11]	段小虎崔爽. 通用嵌入式串行时间码采集系统设计[J]. 计算机应用, 2014, 34(4): 1222-1226.
[12]	李凯何松华欧建平. Virtex-5 GTP和Virtex-6 GTX间匹配通信研究及应用[J]. 计算机应用, 2014, 34(2): 325-328.
[13]	张文凯关桂霞赵海盟王明志吴太夏晏磊. 小卫星模拟系统中多路串行通信系统设计[J]. 计算机应用, 2013, 33(12): 3477-3481.
[14]	琚小明张皆浩张逸中. 基于FPGA实时错误检测技术[J]. 计算机应用, 2013, 33(05): 1459-1462.
[15]	杜双枝王勇陶晓玲. 基于多片FPGA的双优先级动态调度算法[J]. 计算机应用, 2013, 33(03): 862-865.