Design and implementation of FPGA hardware structure optimization based on R22FFT algorithm

doi:10.11772/j.issn.1001-9081.2024071010

Journal of Computer Applications ›› 2025, Vol. 45 ›› Issue (8): 2637-2645.DOI: 10.11772/j.issn.1001-9081.2024071010

• Advanced computing • Previous Articles

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)

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

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

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

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

Abstract

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

摘要：

针对快速傅里叶变换（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²快速傅里叶变换, 多路径延迟交叉结构流水线, 蝶形运算

CLC Number:

TP332

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.

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

Figures/Tables 18

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$

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$

Fig. 1 FPGA hardware structure

Fig. 2 Y-shaped double parallel array structure

Fig. 3 R22FFT single-stage module

Fig. 4 Multi-multiplier module

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

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

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

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

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

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

Fig. 11 Imaginary part error

Fig. 12 Real part error

Fig. 13 Synthesis and place-and-route results

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

Fig. 14 Operating power consumption of FFT hardware circuit

Fig. 15 Hardware circuit time sequence report

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

References 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.