VLSI array synthesis for polynomial GCD computation and application to finite field division
Authors:
- Yong-Jin JeongYJYong-Jin Jeong
- 1 January 1994
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Circuits and Systems I: Regular Papers
- Vol. 41 (12) , 891-897
Abstract
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 m0+n 0+1 processing elements, where m0 and n0 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 codesKeywords
This publication has 4 references indexed in Scilit:
- Synthesizing systolic arrays with control signals from recurrence equationsDistributed Computing, 1989
- On the VLSI design of a pipeline Reed-Solomon decoder using systolic arraysIEEE Transactions on Computers, 1988
- VLSI Architectures for Computing Multiplications and Inverses in GF(2m)IEEE Transactions on Computers, 1985
- Systolic VLSI Arrays for Polynomial GCD ComputationIEEE Transactions on Computers, 1984