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 [73, 77, 79, 96].

Go to next publication

Return to Richard Brent's index page