Design and implementation of code acquisition using sparse Fourier transform

doi:10.23919/JSEE.2024.000015

Journal of Systems Engineering and Electronics ›› 2024, Vol. 35 ›› Issue (5): 1063-1072.doi: 10.23919/JSEE.2024.000015

• ELECTRONICS TECHNOLOGY • Previous Articles Next Articles

Design and implementation of code acquisition using sparse Fourier transform

Chen ZHANG¹(), Jian WANG²^,*(), Guangteng FAN²(), Shiwei TIAN²()

¹ College of Electronic Science and Technology, National University of Defense Technology, Changsha 410073, China
² National Innovation Institute of Defense Technology, Academy of Military Science, Beijing 100071, China

Received:2022-03-15 Accepted:2023-12-12 Online:2024-10-18 Published:2024-11-06
Contact: Jian WANG E-mail:zhangchen@nudt.edu.cn;wangjian710108@126.com;fanguangteng@163.com;wxzd2018@126.com
About author:
ZHANG Chen was born in 1978. She received her B.S., M.S., and Ph.D. degrees from the National University of Defense Technology (NUDT), China, in 2000, 2002 and 2006, respectively. She is currently an associate professor of College of Electronic Science and Technology, NUDT. Her main research interests include wireless communication and network security. E-mail: zhangchen@nudt.edu.cn

WANG Jian was born in 1990. He received his Ph.D. degree from National University of Defense Technology, Changsha, China in 2017. From September 2015 to September 2016, he was a visiting scholar at the Integrated Systems Laboratory, Swiss Federal Institute of Technology, Zurich, Switzerland. Since 2018, he has been a research associate at National Innovation Institute of Defense Technology, Academy of Military Science, Beijing, China. His research interests are in the area of digital signal processing and special-purpose VLSI processor architectures. E-mail: wangjian710108@126.com

FAN Guangteng was born in 1988. He received his Ph.D. degree from the College of Electronic Science and Engineering, National University of Defense Technology, Changsha, China, in 2016. He is currently an associate professor of the National Innovation Institute of Defense Technology, Academy of Military Science, Beijing, China. His main research interests include global navigation satellite system signal acquisition and tracking. E-mail: fanguangteng@163.com

TIAN Shiwei was born in 1987. He received his B.S. degree in electronic information engineering from Xidian University, Xian, in 2008, and M.S. and Ph.D. degrees in communication and information system from the Army Engineering University of PLA, Nanjing, in 2011 and 2015, respectively. Since 2015, he has been an assistant professor with the College of Communications Engineering, Army Engineering University, and since 2021, he has worked in National Innovation Institute of Defense Technology. His main research interests are satellite navigation, satellite communication, and cooperative positioning. E-mail: wxzd2018@126.com
Supported by:
This work was supported by the National Natural Science Foundation of China (61801503).

Abstract

Abstract:

Code acquisition is the kernel operation for signal synchronization in the spread-spectrum receiver. To reduce the computational complexity and latency of code acquisition, this paper proposes an efficient scheme employing sparse Fourier transform (SFT) and the relevant hardware architecture for field programmable gate array (FPGA) and application-specific integrated circuit (ASIC) implementation. Efforts are made at both the algorithmic level and the implementation level to enable merged searching of code phase and Doppler frequency without incurring massive hardware expenditure. Compared with the existing code acquisition approaches, it is shown from theoretical analysis and experimental results that the proposed design can shorten processing latency and reduce hardware complexity without degrading the acquisition probability.

Key words: code acquisition, hardware structure, sparse Fourier transform (SFT), code phase estimation, Doppler frequency estimation

Chen ZHANG, Jian WANG, Guangteng FAN, Shiwei TIAN. Design and implementation of code acquisition using sparse Fourier transform[J]. Journal of Systems Engineering and Electronics, 2024, 35(5): 1063-1072.

Figures/Tables 14

Fig 1

Fig 2

Fig 3

Fig 4

Fig 5

Fig 6

Fig 7

Fig 8

Table 1

Fig 9

Fig 10

Table 2

Fig 11

Table 3

References 31

1	PETERSON R L, ZIEMER R E, BORTH D E. Introduction to spread-spectrum communications. New Jersey: Prentice hall, 1995: 221−308.
2	QIU W Q, ZENG Q X, GAO C, et al Fine Doppler shift acquisition algorithm for BeiDou software receiver by a look-up table. Journal of Systems Engineering and Electronics, 2020, 31 (3): 612- 625.
3	PAUN A F, RUSU-CASANDRA A. On the reduced complexity FFT acquisition for Galileo E1 signal. Proc. of the IEEE International Symposium on Electronics and Telecommunications, 2018. DOI: 10.1109/ISETC.2018.8583908.
4	PAN Y, ZHANG S, WANG X, et al A fine acquisition algorithm based on fast three-time FRFT for dynamic and weak GNSS signals. Journal of Systems Engineering and Electronics, 2023, 34 (2): 259- 269.
5	TONG G Y, LI M Q Quickly acquisition technology of spectrum spread signals. Guidance & Fuze, 2017, 38 (1): 48- 51.
6	CUI S L, WANG D C, HOLTKAMP B, et al. A multi-frequency acquisition algorithm for a GNSS software receiver. Proc. of the IEEE International Geoscience and Remote Sensing Symposium, 2018: 1082−1085.
7	XU Y, XU L J, YUAN H, et al Direct P-code acquisition algorithm based on bidirectional overlap technique. Journal of Systems Engineering and Electronics, 2014, 25 (4): 538- 546.
8	BORNA M, MADANI M H New methods for enhancing fine acquisition in dual folding algorithm of long pseudo noise codes. International Journal of Communication Systems, 2018, 31 (1): e3377. doi: 10.1002/dac.3377
9	IWEN M A. A deterministic sub-linear time sparse Fourier algorithm via non-adaptive compressed sensing methods. Proc. of the 19th Annual ACM-SI AM Symposium on Discrete Algorithms, 2008: 20−29.
10	PLONKA G, WANNENWETSCH K, CUYT A, et al Deterministic sparse FFT for M-sparse vectors. Numerical Algorithms, 2018, 78 (1): 133- 159. doi: 10.1007/s11075-017-0370-5
11	HASSANIEH H, INDYK P, KATABI D, et al. Simple and practical algorithm for sparse Fourier transform. Proc. of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, 2012: 1183−1194.
12	JIANG Z K, CHEN J, LI B Empirical evaluation of typical sparse fast Fourier transform algorithms. IEEE Access, 2021, 9, 97100- 97119. doi: 10.1109/ACCESS.2021.3095071
13	WANG S D, PATEL V M, PETROPULU A Multidimensional sparse Fourier transform based on the Fourier projection-slice theorem. IEEE Trans. on Signal Processing, 2018, 67 (1): 54- 69.
14	WEI D, HU H Sparse discrete linear canonical transform and its applications. Signal Processing, 2021, 183, 108046. doi: 10.1016/j.sigpro.2021.108046
15	SONG Z, SUN B C, WEINSTEIN O, et al. Sparse Fourier transform over lattices: a unified approach to signal reconstruction. http://arxiv.org/abs/2205.00658.
16	BIN L, JIANG Z K, CHEN J. On performance of the multiscale sparse fast Fourier transform algorithm. Circuits, Systems, and Signal Processing, 2022, 41: 4547−4569.
17	ZHANG H S, SHAN T, LIU S H, et al. Parameter optimization of sparse Fourier transform for radar target detection. Proc. of the IEEE Radar Conference, 2020. DOI: 10.1109/RadarConf2043947.2020.9266417.
18	ZHANG H, SHAN T, LIU S, et al Performance evaluation and parameter optimization of sparse Fourier transform. Signal Processing, 2021, 179, 107823. doi: 10.1016/j.sigpro.2020.107823
19	LI B, JIANG Z, CHEN J On performance of sparse fast Fourier transform algorithms using the aliasing filter. Electronics, 2021, 10 (9): 1117. doi: 10.3390/electronics10091117
20	ZHANG H C, SHAN T, LIU S H, et al Optimized sparse fractional Fourier transform: principle and performance analysis. Signal Processing, 2020, 174, 107646. doi: 10.1016/j.sigpro.2020.107646
21	YU X H, CHEN X L, HUANG Y, et al Fast detection method for low-observable maneuvering target via robust sparse fractional Fourier transform. IEEE Geoscience and Remote Sensing Letters, 2019, 17 (6): 978- 982.
22	XU B, HAN T L, ZHANG Z, et al. Research on sub-Nyquist rate sampling method based on sparse Fourier transform theory. Proc. of the IEEE 4th International Conference on Electronics Technology, 2021: 742−747.
23	PANG C S, LIU S H, HAN Y High-speed target detection algorithm based on sparse Fourier transform. IEEE Access, 2018, 6, 37828- 37836. doi: 10.1109/ACCESS.2018.2853180
24	YU X H, CHEN X L, HUANG Y, et al Radar moving target detection in clutter background via adaptive dual-threshold sparse Fourier transform. IEEE Access, 2019, 7, 58200- 58211. doi: 10.1109/ACCESS.2019.2914232
25	LU J N, TAN Z W, LAU A P T, et al Modulation format identification assisted by sparse-fast-Fourier-transform for hitless flexible coherent transceivers. Optics Express, 2019, 27 (5): 7072- 7086. doi: 10.1364/OE.27.007072
26	LU J N, WU Q, JIANG H X, et al Efficient timing/frequency synchronization based on sparse fast Fourier transform. Journal of Lightwave Technology, 2019, 37 (20): 5299- 5308. doi: 10.1109/JLT.2019.2932075
27	HU J X, WANG Z, QIU Q, et al. Sparse fast Fourier transform on GPUs and multi-core CPUs. Proc. of the IEEE 24th International Symposium on Computer Architecture and High Performance Computing, 2012: 83−91.
28	LIU Y F, GONG H H, ZHOU Y H. Sparse fast Fourier transform implementation on multicore DSP. Proc. of the 2nd International Conference on Electromechanical Control Technology and Transportation, 2017: 301−304.
29	KORTLI Y, GABSI S, JRIDI M, et al Hw/Sw co-design technique for 2D fast Fourier transform algorithm on Zynq SoC. Integration, 2022, 82, 78- 88. doi: 10.1016/j.vlsi.2021.09.005
30	GARRIDO M. A survey on pipelined FFT hardware architectures. Journal of Signal Processing Systems, 2021, 56(12): 2634−2643.
31	WANG C H, GAO F. Low complexity DSSS acquisition method of LEO satellite communication ASIC. Proc. of the IEEE 2nd International Conference on Electronic Information and Communication Technology, 2019: 84−88.

Hardware module	FFT-based acquisition [5]			SFT-based acquisition
Hardware module	Complex adder	Complex multiplier	Memory/bits	Complex adder	Complex multiplier	Memory/bits
FFT	$2{\log _2}N$	${\log _2}N$	$4N{w_Y}$	$2{\log _2}N$	${\log _2}N$	$2N{w_Y}$
Sequence multiplication and caching	—	$p$	$(4p + 2){w_Y}$	$p$	$p$	$ 8N{w_Y} + 4(p - 1)N{w_\Delta } + N{w_Y} + 2L{w_Y} $
IFFT	$2p{\log _2}N$	$p{\log _2}N$	—	$2{\log _2}B$	${\log _2}B$	$2B{w_Y}$
Parameter estimation	—	—	—	$3\beta $	$\beta $	$N{w_C}$

FPGA resource	FFT-based acquisition [5]		SFT-based acquisition
FPGA resource	$p = 4$	$p = 8$	$p = 4$	$p = 8$
Slice registers	24366	46632	8545	9134
Slice LUTs	22875	41998	7878	8762
DSP48Es	147	267	51	63
BRAM (18 kB)	44	76	15	19

Hardware scheme	CMOS technology/nm	Area//mm²	Gate count
SFT-based design	SMIC 40	2.2×1	327000
The work of [31]	SMIC 130	5×5	450000

[1]	Chao Wu, Luping Xu, Hua Zhang, and Wenbo Zhao. Code acquisition method based on wavelet transform filtering [J]. Systems Engineering and Electronics, 2015, 26(6): 1169-1176.
[2]	Lingyun,Xiaofei Zhang and Miao Yu. Fast multi-parameter estimation and localization for MIMO radar [J]. Systems Engineering and Electronics, 2015, 26(3): 486-492.
[3]	Xiaojun Jin, Zhonghe Jin, Chaojie Zhang*, Jianwen Jiang, and Yangming Zheng. Modified pseudo-noise code regeneration method [J]. Journal of Systems Engineering and Electronics, 2010, 21(3): 370-374.

Design and implementation of code acquisition using sparse Fourier transform

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 14

References 31

Related Articles 3

Recommended Articles

Metrics

Comments