Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12] [ 13] [ 14] [ 15] [ 16] [ 17] [ 18] [ 19] [ 20] [ 21] [ 22] [ 23] [ 24]

@

Journal of Information Science and Engineering, Vol. 27 No. 3, pp. 953-967 (May 2011)

Design of High-Speed Iterative Dividers in GF(2m)*

MING-DER SHIEH, WEN-CHING LIN AND CHIEN-MING WU+
Department of Electrical Engineering
National Cheng Kung University
Tainan, 701 Taiwan
+Chip Implementation Center
National Applied Research Laboratories
Hsinchu, 300 Taiwan

Fast algorithms for high-speed divider design in finite fields GF(2m) are very crucial in applications like cryptosystems. In this paper, we reformulated the conventional iterative division algorithm by changing the pre-defined variable and then updating its initial value accordingly. The reformulated division algorithm allows a restructuring of the divider architecture to further improve its operating speed without increasing latency or area cost. Using the proposed fast algorithm, we developed two high-speed iterative dividers based on the semi-systolic and bit-serial systolic architectures. Analytical results show that the cost of the initial value update and variable transformation in the reformulated algorithm is almost negligible in the hardware implementation. Our divider designs improve the critical path delay. Compared with related divider designs, the proposed designs have time and area advantages.

Keywords: division algorithm, finite field, high-speed, Stein's algorithm, systolic array

Full Text () Retrieve PDF document (201105_09.pdf)

Received October 6, 2009; revised February 26, 2010; accepted April 20, 2010.
Communicated by Chung-Ping Chung.
* This work was supported in part by the National Science Council of Taiwan, R.O.C. under contract No. NSC 96-2220-E-006-008.