FPGA Implementation of an Extended Binary GCD Algorithm for Systolic Reduction of Rational Numbers

Bogdan Mătăsaru⁶ &
Tudor Jebelean⁶

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 1896))

Included in the following conference series:

International Workshop on Field Programmable Logic and Applications

718 Accesses

Abstract

We present the FPGA implementation of an extension of the binary plus-minus systolic algorithm which computes the GCD (greatest common divisor) and also the normal form of a rational number, without using division. A sample array for 8 bit operands consumes 83.4% of an Atmel 40K10 chip and operates at 25 MHz.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Low Power Semi-systolic Architectures for Polynomial-Basis Multiplication over GF(2^m) Using Progressive Multiplier Reduction

Article 19 April 2015

A Scalable and Systolic Architectures of Montgomery Modular Multiplication for Public Key Cryptosystems Based on DSPs

Article 01 September 2017

Systolic Design Space Exploration of Polynomial Division over $$GF(3^m)$$

References

R. P. Brent and H. T. Kung, A systolic algorithm for integer GCD computation, Symp. on Computer Arithmetic (K. Hwang, ed.), IEEE Computer Society, 1985.
Google Scholar
B. Buchberger, Grö bner Bases: An Algorithmic Method in Polynomial Ideal Theory, Recent trends in Multidimensional Systems (Bose and Reidel, eds.), D. Reidel Publishing, 1985, pp. 184–232.
Google Scholar
P. Henrici, A subroutine for computations with rational numbers, Journal of the ACM 3(1956), 6–9.
Article MathSciNet Google Scholar
T. Jebelean, Systolic normalization of rational numbers, ASAP’93 (L. Dadda and B. Wah, eds.), IEEE Computer Society, 1993, pp. 502–513.
Google Scholar
Rational arithmetic using FPGA, More FPGAs (W. Luk and W. Moore, eds.), Abingdon EE&CS Books, Oxford, 1994, pp. 262–273.
Google Scholar
D. E. Knuth, The art of computer programming, vol. 2, Addison-Wesley, 1981.
Google Scholar
W. Krandick and T. Jebelean, Bidirectional exact integer division, Journal of Symbolic Computation 21 (1996), 441–455.
Article MATH MathSciNet Google Scholar
B. Mătăsaru, An extension of the binary GCD algorithm for systolic parallelization, Tech. Report 99-47, RISC-Linz, 1999, http://www.risc.uni-linz.ac.at
J. Stein, Computational problems associated with Racah algebra, J. Comp. Phys. 1 (1967), 397–405.
Article MATH Google Scholar
K. Weber, The accelerated integer GCD algorithm, ACM Trans. on Math. Software 21 (1995), no. 1, 111–122.
Article MATH Google Scholar

Download references

Author information

Authors and Affiliations

RISC-Linz, A-4040, Linz, Austria
Bogdan Mătăsaru & Tudor Jebelean

Authors

Bogdan Mătăsaru
View author publications
You can also search for this author in PubMed Google Scholar
Tudor Jebelean
View author publications
You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

Computer Science Department, University of Kaiserslautern, P. O. Box. 30 49, 67653, Kaiserslautern, Germany
Reiner W. Hartenstein
Carinthia Tech Institute, Richard-Wagner-Str. 19, 9500, Villach, Austria
Herbert Grünbacher

Rights and permissions

Reprints and permissions

Copyright information

About this paper

Cite this paper

Mătăsaru, B., Jebelean, T. (2000). FPGA Implementation of an Extended Binary GCD Algorithm for Systolic Reduction of Rational Numbers. In: Hartenstein, R.W., Grünbacher, H. (eds) Field-Programmable Logic and Applications: The Roadmap to Reconfigurable Computing. FPL 2000. Lecture Notes in Computer Science, vol 1896. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44614-1_91

Download citation

DOI: https://doi.org/10.1007/3-540-44614-1_91
Published: 12 April 2002
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67899-1
Online ISBN: 978-3-540-44614-9
eBook Packages: Springer Book Archive

Publish with us

Policies and ethics