VLSI array synthesis for polynomial GCD computation and application to finite field division
Yong-Jin Jeong, Wayne P. Burleson · IEEE Transactions on Circuits and Systems I Fundamental Theory and Applications · 1994
Many practical algorithms have dynamic (or data-dependent) dependency structure in their computation, which is not desirable for VLSI hardware implementation. Polynomial GCD computation by Euclid's algorithm is a typical example of dynamic dependency. In this paper, we use an algorithmic transformation technique to derive static (or data-independent) dependencies for Euclid's GCD algorithm. The resulting algorithm is mapped to a linear systolic array which is area-efficient and achieves maximum throughput with pipelining. It has m/sub 0/+n/sub 0/+1 processing elements, where m/sub 0/ and n/sub 0/ are degrees of two polynomials. We have applied the technique to the extended GCD algorithm and developed a systolic finite field divider, which can be efficiently used in decoding a variety of error correcting codes.>