Systolic VLSI arrays for polynomial GCD computation

73. R. P. Brent and H. T. Kung, Systolic VLSI arrays for polynomial GCD computation, IEEE Transactions on Computers C-33 (1984), 731-736.

Abstract: dvi (3K), pdf (83K), ps (29K).

Paper: pdf (1031K).


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 VLSI solutions to both the GCD problem and the extended GCD problem.


For related work see [79, 82]. The (more difficult) integer GCD problem is discussed in [77, 79, 96].

Go to next publication

Return to Richard Brent's index page