Area-efficient two-dimensional architectures for finite field inversion and division

ABSTRACT

Many high-throughput two-dimensional architectures for finite field inversion and division are based on reformulations of the extended Euclidean algorithm (EEA). These reformulated EEAs usually keep track of two pairs of data polynomials (or registers), and the operations of the reformulated EEAs are only within each pair of polynomials. In this paper, we propose a new reformulated EEA wherein the operations within the two pairs of polynomials are identical. Hence, the two pairs of polynomials in our new reformulated EEA can be concatenated into one pair. By utilizing some inherent properties of the EEA, we further reduce the computational complexity of our reformulated EEA by 25%. Based on our reformulated EEA, we propose new two-dimensional inversion and division architectures. How much hardware saving the reduced computational complexity translates into depends on how control mechanisms are implemented. Regardless of the implementation of control signals, our new architectures require smaller numbers of gates and latches while achieving comparable or better throughput, latency, and critical path delay in comparison to the best architectures in the literature.

REFERENCES

• 1: K. Araki, I. Fujita, and M. Morisue, "Fast Inverters over Finite Field Based on Euclid's Algorithm," Trans. of IEICE, vol. 72E, no. 11, pp. 1230--1234, November 1989.
• 2: J.-H. Guo and C.-L. Wang, "Hardware-efficient Systolic Architecture for Inversion and Division in GF(2m)," in IEE Proceedings on Computers and Digital Techniques, 1998, pp. 272--278.
• 3: S. Y. Kung, VLSI array processors, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 4: K. K. Parhi, VLSI Digital Signal Processing Systems, John Wiley and Sons, New York, 1999.
• 5: Y. Watanabe, N. Takagi, and K. Takagi, "A VLSI Algorithm for Division in GF(2m) Based on Extended Binary GCD Algorithm," IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E85-A, no. 5, pp. 994--999, May 2002.
• 6: C. H. Wu, C. M. Wu, M. D. Shieh, and Y. T. Wang, "Systolic VLSI Realization of a Novel Iterative Division Algorithm over GF(2m): a High-Speed, Low-Complexity Design," in Proceedings of ISCAS'01, 2001, pp. 33--36.
• 7: Zhiyuan Yan , Dilip V. Sarwate, High-speed systolic architectures for finite field inversion and division, Proceedings of the 14th ACM Great Lakes symposium on VLSI, April 26-28, 2004, Boston, MA, USA [doi>10.1145/988952.989064]
• 8: Z. Yan , D. V. Sarwate , Z. Liu, High-speed systolic architectures for finite field inversion, Integration, the VLSI Journal, v.38 n.3, p.383-398, January 2005 [doi>10.1016/j.vlsi.2004.07.006]
• 9: Zhiyuan Yan , Dilip V. Sarwate, New Systolic Architectures for Inversion and Division in GF(2^m), IEEE Transactions on Computers, v.52 n.11, p.1514-1519, November 2003

INDEX TERMS

Primary Classification:
  B. Hardware
  B.2 ARITHMETIC AND LOGIC STRUCTURES
      B.2.4 High-speed Arithmetic

General Terms:
Algorithms, Design

Keywords:
Reed-Solomon codes, arithmetic, cryptography, finite field, galois field