FPGA-based Low Latency Square Root CORDIC Algorithm

• Autorzy: Węgrzyn Mariusz , Voytusik Stepan , Gavkalova Natalia

Identyfikatory

DOI

10.26636/jtit.2025.1.1950

• Języki publikacji: EN

Abstrakty

EN

The coordinate rotation digital computer (CORDIC) algorithm is a popular method used in many fields of science and technology. Unfortunately, it is a time-consuming process for central processing units (CPUs) and graphics processing units (GPUs), and even for specialized digital signal processing (DSP) solutions. The CORDIC algorithm is an alternative for Newton-Raphson numerical calculation and for the FPGA based resource-expensive look-up-table (LUT) method. Various modifications of the CORDIC algorithm allow to speed up the operation of hardware in edge computing devices.With that context taken into consideration, this article presents a fast and accurate square root floating point (SQRT FP) CORDIC function which can be implemented in field programmable gate arrays (FPGAs). The proposed algorithm offers low-complexity, decent accuracy and speed, and is sufficient for digital signal processing (DSP) applications, such as digital filters, accelerators for neural networks, machine learning and computer vision applications, and intelligent robotic systems.

Słowa kluczowe

EN

computer vision; CORDIC algorithm; FPGA; numerical methods; reconfigurable computing systems

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2025
• Tom: nr 1
• Strony: 21--29
• Opis fizyczny: Bibliogr. 33 poz., rys., tab., wykr.

Twórcy

autor

Węgrzyn Mariusz

• Cracow University of Technology, Cracow, Poland

• https://orcid.org/0000-0002-6938-2954

autor

Voytusik Stepan

• Lviv Polytechnic National University, Lviv, Ukraine

• https://orcid.org/0000-0003-4234-3303

autor

Gavkalova Natalia

• Warsaw University of Technology, Warsaw, Poland

• https://orcid.org/0000-0003-1208-9607

Bibliografia

• [1] L. Moroz, V. Samotyy, M. Wegrzyn, and U. Dzelendzyak, “Efficient Floating-point Square Root and Reciprocal Square Root Algorithms”, 11th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications, Cracow, Poland, 2021 (https://doi.org/10.1109/IDAACS53288.2021.9660872).
• [2] A. Hasnat et al., “A Fast FPGA Based Architecture for Computation of Square Root and Inverse Square Root”, Devices for Integrated Circuit (DevIC), Kalyani, India, 2017 (https://doi.org/10.1109/DEVIC.2017.8073975).
• [3] Z. Kokosinski et al., “Fast and Accurate Approximation Algorithms Computing Floating Point Square Root”, Numerical Algorithms, 2024 (https://doi.org/10.1007/s11075-024-01932-7).
• [4] S. Mopuri, S. Bhardwaj, and A. Acharyya, “Coordinate Rotation-based Design Methodology for Square Root and Division Computation”, IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 66, pp. 1227–1231, 2019 (https://doi.org/10.1109/TCSII.20 8.2878599).
• [5] R. Shukla and K.C. Ray, “Low Latency Hybrid CORDIC Algorithm”, IEEE Transactions on Computers, vol. 63, pp. 3066–3078, 2014 (https://doi.org/10.1109/TC.2013.173).
• [6] M.D. Ercegovac and T. Lang, Division and Square Root Digitrecurrence Algorithms and Implementations, Norwell: Kluwer Publishers, 240 p., 1994 (ISBN 9780792394389).
• [7] Y.H. Hu and S.Naganathan, “An Angle Recoding Method for CORDIC Algorithm Implementation”, IEEE Transactions on Computers, vol. 42, pp. 74–79, 1993 (https://doi.org/10.1109/12.192217).
• [8] E. Antelo, T. Lang, and J. Bruguera, “Very-high Radix Circular CORDIC: Vectoring and Rotation/vectoring”, IEEE Transactions on Computers, vol. 49, pp. 727–739, 2000 (https://doi.org/10.1109/12.863043).
• [9] E. Antelo, J. Villalba, J.D. Bruguera, and E. Zapata, “High Performance Rotation Architectures Based on Radix-4 CORDIC Algorithm”, IEEE Transactions on Computers, vol. 46, pp. 855–870, 1997 (https://doi.org/10.1109/12.609275).
• [10] T.-J. Kwon and J. Draper, “Floating-Point Division and Square Root Implementation using a Taylor-series Expansion Algorithm with Reduced Look-up Tables”, 2008 51st Midwest Symposium on Circuits and System, Knoxville, USA, 2008 (https://doi.org/10.1109/MWSCAS.2008.4616959).
• [11] Martín Vázquez, Marcelo Tosini, Lucas Leiva., “Radix-10 Restoring Square Root for 6-input LUTs Programmable Devices”, Circuits Systems and Signal Processing, vol. 40, pp. 2335–2360, 2021 (https://doi.org/10.1007/s00034-020-01571-y).
• [12] J.E. Volder, “The CORDIC Trigonometric Computing Technique”, IEEE Transactions on Electronic Computers, vol. EC-8, no. 3, pp. 330–334, 1959 (https://doi.org/10.1109/TEC.1959.5222693).
• [13] J.-G. Mailloux, S. Simard, and R. Beguenane, “FPGA Implementation of Induction Motor Vector Control using Xilinx System Generator”, 6th WSEAS International Conference on Circuits, Systems, Electronics, Control & Signal Processing, Cairo, Egypt, 2007.
• [14] M. Garrido, P. Källström, M. Kumm, and O. Gustafsson, “CORDIC II: A New Improved CORDIC Algorithm”, IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 63, pp. 186–190, 2016 (https://doi.org/10.1109/TCSII.2015.2483422).
• [15] S. Srinivasan et al., “Split-path Fused Floating Point Multiply Accumulate (FPMAC)”, 21th IEEE Symposium on Computer Arithmetic, Austin, USA 2013 (https://doi.org/10.1109/ARITH.2013.32).
• [16] J.S. Walther, “A Unified Algorithm for Elementary Functions”, Proc. of AFIPS Joint Computer Conferences, vol. 38, pp. 385–389, 1971 (https://doi.org/10.1145/1478786.1478840).
• [17] S. Wang, V. Piuri, and E.E. Swartzlander, “Hybrid CORDIC Algorithms”, IEEE Transactions on Computers, vol. 46, no. 11, pp. 1202–1207, 1997 (https://doi.org/10.1109/12.644295).
• [18] P.-T. Vo-Thi, T.-T. Hoang, C.-K. Pham, and D.-H. Le, “A Floatingpoint FFT Twiddle Factor Implementation Based on Adaptive Angle Recoding CORDIC”, 2017 International Conference on Recent Advances in Signal Processing Telecommunications & Computing (SigTelCom), Da Nang, Vietnam, 2017 (https://doi.org/10.1109/SIGTELCOM.2017.7849789).
• [19] A. Madisetti, A.Y. Kwentus, and A.N. Willson, “A 100 MHz, 16-b, Direct Digital Frequency Synthesizer with 100-dBc Spurious-free Dynamic Range”, IEEE Journal of Solid-State Circuits, vol. 34, no. 8, pp. 1034–1043, 1999 (https://doi.org/10.1109/4.777100).
• [20] D. Timmermann, H. Hahn, and B. Hosticka, “Low Latency Time CORDIC Algorithms”, IEEE Transactions on Computers, vol. 41, pp. 1010–1015, 1992 (https://doi.org/10.1109/12.156543).
• [21] M. Woźniak et al., “Radix 4 CORDIC Algorithm Based Low Latency and Hardware Efficient VLSI Architecture for Nth Root and Nth Power Computations”, Scientific Reports, vol. 13, art. no. 20918, 2023 (https://doi.org/10.1038/s41598-023-47890-3).
• [22] R. Dutt and A. Acharyya, “Low-complexity Square-root Unscented Kalman Filter”, Circuits, Systems, and Signal Processing, vol. 42, pp. 6900–6928, 2023 (https://doi.org/10.1007/s00034-023-02437-9).
• [23] B. Li et al., “A Unified Reconfigurable Architecture Based on CORDIC Algorithm Floating-point Arithmetic”, 2017 International Conference on Field Programmable Technology (ICFPT), Melbourne, Australia, 2017 (https://doi.org/10.1109/FPT.2017.8280166).
• [24] S. Mopuri and A. Acharyya, “Low-complexity and High-speed Architecture Design Methodology for Complex Square Root”, Circuits, Systems, and Signal Processing, vol. 40, pp. 5759–5772, 2021 (https://doi.org/10.1007/s00034-021-01738-1).
• [25] S. Suresh, S.F. Beldianu, and S.G. Ziavras, “FPGA and ASIC Square Root Designs for High Performance and Power Efficiency”, 2013 IEEE 24th International Conference on Application-Specific Systems, Architectures and Processors, Washington, USA, 2013 (https://doi.org/10.1109/ASAP.2013.6567588).
• [26] M.A. Darshan, “A High Performance and Low Latency FPGA Implementation of CORDIC Algorithm”, International Journal of Scientific & Engineering Research, vol. 4, no. 8, 2013 (ISSN 22295518).
• [27] T.-B. Juang, S.-F. Hsiao, and M.-Y. Tsai, “Para-CORDIC: Parallel CORDIC Rotation Algorithm”, IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 51, pp. 1515–1524, 2004 (https://doi.org/10.1109/TCSI.2004.832734).
• [28] T. Juang, “Low Latency Angle Recoding Methods for the Higher Bitwidth Parallel CORDIC Rotator Implementations”, IEEE Transactionson Circuits and Systems II: Express Briefs, vol. 55, pp. 1139–1143, 2008 (https://doi.org/10.1109/TCSII.2008.2002566).
• [29] Xilinx, “CORDIC v6.0 LogiCORE IP Product Guide”, 2021.
• [30] F. de Dinechin, M. Joldes, B. Pasca, and G. Revy, “Multiplicative Square Root Algorithms for FPGAs”, 2010 International Conference on Field Programmable Logic and Applications, Milan, Italy, 2010 (https://doi.org/10.1109/FPL.2010.112).
• [31] AMD Xilinx, “7 Series FPGAs Data Sheet: Overview DS180 (v2.6.1)”, product specification, 2020.
• [32] AMD Xilinx, “Zynq UltraScale+ MPSoC Data Sheet: Overview DS891 (v1.10)”, product specification, 2022.
• [33] M. Qin et al., “A Low-latency RDP-CORDIC Algorithm for Real-time Signal Processing of Edge Computing Devices in Smart Grid Cyberphysical Systems”, Sensors, vol. 22, art. no. 7489, 2022 (https://doi.org/10.3390/s22197489).