An efficient technique for synthesis and optimization of polynomials in GF(2m)

ABSTRACT

This paper presents an efficient technique for synthesis and optimization of polynomials over GF(2^m), where m is a non-zero positive integer. The technique is based on a graph-based decomposition and factorization of polynomials over GF(2^m), followed by efficient network factorization and optimization. A technique for efficiently computing coefficients over GF(p^m), where p is a prime number, is first presented. The coefficients are stored as polynomial graphs over GF(p^m). The synthesis and optimization is initiated from this graph based representation. The technique has been applied to minimize multipliers over all the 51 fields in GF(2^k), k = 2...8 in 0.18 micron CMOS technology with the help of the Synopsys® design compiler. It has also been applied to minimize combinational exponentiation circuits, and other multivariate bit- as well as word-level polynomials. The experimental results suggest that the proposed technique can reduce area, delay, and power by significant amount.

REFERENCES

• 1: A. Dür , J. Grabmeier, Applying coding theory to sparse interpolation, SIAM Journal on Computing, v.22 n.4, p.695-704, Aug. 1993 [doi>10.1137/0222046]
• 2: A. Halbutoğullari , Çetin K. Koç, Mastrovito Multiplier for General Irreducible Polynomials, IEEE Transactions on Computers, v.49 n.5, p.503-518, May 2000 [doi>10.1109/12.859542 ]
• 3: Abusaleh M. Jabir , Dhiraj K. Pradhan, MODD: A New Decision Diagram and Representation for Multiple Output Binary Functions, Proceedings of the conference on Design, automation and test in Europe, p.21388, February 16-20, 2004
• 4: A. Jabir and D. Pradhan. An Efficient Graph Based Representation of Circuits and Calculation of Their Coefficients in Finite Field. In Proc. Int. Workshop on Logic and Synth. (IWLS'05), pages 218--225, California, USA, June 2005.
• 5: A. Reyhani-Masoleh and M. A. Hasan. Low Complexity Bit Parallel Architectures for Polynomial Basis Multiplication over GF(2^m). IEEE Trans. Comp., 53(8):945--959, Aug. 2004.
• 6: Richard E. Blahut, Fast Algorithms for Digital Signal Processing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1985
• 7: Randal E. Bryant, Graph-Based Algorithms for Boolean Function Manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, August 1986 [doi>10.1109/TC.1986.1676819]
• 8: Christof Paar , Peter Fleischmann , Pedro Soria-Rodriguez, Fast Arithmetic for Public-Key Algorithms in Galois Fields with Composite Exponents, IEEE Transactions on Computers, v.48 n.10, p.1025-1034, October 1999 [doi>10.1109/12.805153 ]
• 9: BDD Decomposition for Efficient Logic Synthesis, Proceedings of the 1999 IEEE International Conference on Computer Design, p.626, October 10-13, 1999
• 10: C. H. Liu, N. F. Huang, and C. Y. Lee. Computation of ab² Multiplier in GF(2^m) Using an Efficient Low Complexity Cellular Architecture. IEICE Trans. Fund. Electron. Comm. Comp. Sci., E83-A(12):2657--2663, 2000.
• 11: Chien-Hsing Wu , Chien-Ming Wu , Ming-Der Shieh , Yin-Tsung Hwang, High-Speed, Low-Complexity Systolic Designs of Novel Iterative Division Algorithms in GF(2^m), IEEE Transactions on Computers, v.53 n.3, p.375-380, March 2004 [doi>10.1109/TC.2004.1261843]
• 12: D. K. Pradhan and A. M. Patel. Reed-Müller Like Canonic Forms for Multivalued Functions. IEEE Trans. Comp., C-24(2):206--210, Feb. 1975.
• 13: D. Michael Miller , Rolf Drechsler, On the Construction of Multiple-Valued Decision Diagrams, Proceedings of the 32nd International Symposium on Multiple-Valued Logic (ISMVL'02), p.245, May 15-18, 2002
• 14: Dima Yu Grigoriev , Marek Karpinski , Michael F. Singer, Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields, SIAM Journal on Computing, v.19 n.6, p.1059-1063, Dec. 1990 [doi>10.1137/0219073]
• 15: Huapeng Wu , M. Anwarul Hasar, Efficient Exponentiation of a Primitive Root in GF(2m), IEEE Transactions on Computers, v.46 n.2, p.162-172, February 1997 [doi>10.1109/12.565591 ]
• 16: J. C. Jeon and K. Y. Yoo. Low Power Exponent Architecture in Finite Field. IEE Proc. Part-E, 152(6):573--578, Dec. 2005.
• 17: Jose Luis Imana , Juan Manuel Sanchez , Francisco Tirado, Bit-Parallel Finite Field Multipliers for Irreducible Trinomials, IEEE Transactions on Computers, v.55 n.5, p.520-533, May 2006 [doi>10.1109/TC.2006.69]
• 18: M. Abramovici, M. Breuer, and A. Friedman. Digital Systems Testing and Testable Design. IEEE Publications, 1994.
• 19: Michael Ben-Or, A deterministic algorithm for sparse multivariate polynomial interpolation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.301-309, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62241]
• 20: Michael Clausen , Andreas Dress , Johannes Grabmeier , Marek Karpinski, On zero-testing and interpolation of k -sparse multivariate polynomials over finite fields, Theoretical Computer Science, v.84 n.2, p.151-164, July 29, 1991 [doi>10.1016/0304-3975(91)90157-W ]
• 21: M. Ciesielski , P. Kalla , Z. Zeng , B. Rouzeyre, Taylor Expansion Diagrams: A Compact, Canonical Representation with Applications to Symbolic Verification, Proceedings of the conference on Design, automation and test in Europe, p.285, March 04-08, 2002
• 22: N. Iliev, J. E. Stine, and N. Jachimiec. Parallel Programmable Finite Field GF(2^m) Multipliers. In Proc. IEEE Comp. Soc. Annual Symp. VLSI Emerging Trends (ISVLSI'04), pages 299--302, Feb. 2004.
• 23: D. Pradhan. A Theory of Galois Switching Functions. IEEE Trans. Comp., C-27(3):239--249, Mar. 1978.
• 24: T. Sasao and F. Izuhara. Exact Minimization of FPRMs Using Multi-Terminal EXOR TDDs. In T. Sasao and M. Fujita, editors, Representations of Discrete Functions, pages 191--210. Kluwer Academic Publishers, 1996.
• 25: U. Kebschull and W. Rosenstiel. Efficient graph-based computation and manipulation of functional decision diagrams. In Proc. European Design Automation Conf., pages 278--283, Feb. 1993.
• 26: Stephen B. Wicker, Error control systems for digital communication and storage, Prentice-Hall, Inc., Upper Saddle River, NJ, 1994
• 27: Zvonko G. Vranesic , Zeljko Zilic, A Multiple-Valued Reed-Muller Transform for Incompletely Specified Functions, IEEE Transactions on Computers, v.44 n.8, p.1012-1020, August 1995 [doi>10.1109/12.403717 ]
• 28: Zeljko Zilic , Zvonko G. Vranesic, A Deterministic Multivariate Interpolation Algorithm for Small Finite Fields, IEEE Transactions on Computers, v.51 n.9, p.1100-1105, September 2002

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Automatic synthesis

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Optimization
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids
  B.m MISCELLANEOUS
      Subjects: Design management

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Design, Performance