An Architecture of a High-Speed Quasi-Parallel Divider for Numbers of Arbitrary Word Length
Tsugio Nakamura, Hiroshi Kasahara · IEEJ Transactions on Electronics Information and Systems · 2000
In this paper, we propose a quasi-parallel divider for numbers of arbitrary word length, which reduces the increase in the number of pins and gates, but not failing the high-speed performance of the parallel processing, by cascading some parallel dividers and by repeating the arithmetic operations using some clock cycles. The best way in improving the speed is using the parallel hardware architecture, but it brings the increase of the number of gates, fan-ins and fan-outs as the precision is increased. The public key cryptographic techniques for information security is an good example. In this case, the power residue arithmetic for numbers more than 1, 024 bits is needed because of keeping the adequate security within the reasonable operation time. In such high precision, it will be extremely difficult to be implemented on a single chip with only the parallel architecture, if not impossible. That is why it has usually been realized in the type of sequential circuit using millions of clock cycles. A quasi-parallel divider proposed here can perform to any accuracy because it is the chip sliced configuration. When it is to be expanded by a factor of n times of the single chip precision, the increase of the number of gates are 1/n times against that of the conventional parallel architecture, and the propagation delay reduction is 1/n against that of the sequential circuit type.