Area-Delay-Efficeint FPGA Design of 32-bit Euclid's GCD based on Sum of Absolute Difference
This work addresses the need for area-delay-efficient hardware implementations of GCD calculations, which are crucial in fields like cryptography and error correction, but it is incremental as it builds on existing Euclidean algorithm methods with a specific optimization.
The paper tackled the problem of efficiently computing the greatest common divisor (GCD) of two 32-bit numbers using Euclid's algorithm on FPGAs, resulting in a design called Optimized_GCDSAD that outperforms previous methods in metrics like latency, area delay product, and slice usage.
Euclids algorithm is widely used in calculating of GCD (Greatest Common Divisor) of two positive numbers. There are various fields where this division is used such as channel coding, cryptography, and error correction codes. This makes the GCD a fundamental algorithm in number theory, so a number of methods have been discovered to efficiently compute it. The main contribution of this paper is to investigate a method that computes the GCD of two 32-bit numbers based on Euclidean algorithm which targets six different Xilinx chips. The complexity of this method that we call Optimized_GCDSAD is achieved by utilizing Sum of Absolute Difference (SAD) block which is based on a fast carry-out generation function. The efficiency of the proposed architecture is evaluated based on criteria such as time (latency), area delay product (ADP) and space (slice number) complexity. The VHDL codes of these architectures have been implemented and synthesized through ISE 14.7. A detailed comparative analysis indicates that the proposed Optimized_GCDSAD method based on SAD block outperforms previously known results.