Systolic VLSI arrays for linear-time GCD computation
82. R. P. Brent and
H. T. Kung,
Systolic VLSI arrays for linear-time GCD computation,
in VLSI 83 (edited by F. Anceau and E. J. Aas),
North-Holland, Amsterdam, 1983, 145-154.
Paper: pdf (652K).
The problem of finding a greatest common divisor (GCD) of any
two nonzero polynomials is fundamental to algebraic and
symbolic computations, as well as to the decoder implementation
for a variety of error-correcting codes. This paper describes
new systolic arrays that can lead to efficient hardware
solutions to both the GCD problem and the extended GCD problem.
The systolic arrays have been implemented on the CMU programmable
systolic chip (PSC) to demonstrate its application to the decoder
implementation for Reed-Solomon codes. The integer GCD problem
is also considered, and it is shown that a linear systolic array
of O(n) cells can compute the GCD of two n-bit
integers in time O(n).
For related work see
Go to next publication
Return to Richard Brent's index page