Article

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

Authors:

Abusaleh M. Jabir,

Dhiraj K. Pradhan,

Jimson MathewAuthors Info & Claims

ICCAD '06: Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design

Pages 151 - 157

https://doi.org/10.1145/1233501.1233532

Published: 05 November 2006 Publication History

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. Dur and J. Grabmeier. Applying Coding Theory to Sparse Interpolation. SIAM J. Computing, 22(4):695--703, Aug. 1993.

Digital Library

[2]

A. Halbutogullari and çetin K. Koç. Mastrovito Multiplier for General Irreducible Polynomials. IEEE Trans. Comput., 49(5):503--518, May 2000.

Digital Library

[3]

A. Jabir and D. Pradhan. MODD: A New Decision Diagram and Representation for Multiple Output Binary Functions. In Des. Automat. Test. in Europe (DATE'04), pages 1388--1389, Paris, France, Feb. 2004.

Digital Library

[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.

Digital Library

[6]

R. Blahut. Fast Algorithms for Digital Signal Processing. Addison-Wesley, Reading, Mass., 1984.

Digital Library

[7]

R. Bryant. Graph-Based Algorithms for Boolean Function Manipulation. IEEE Trans. Comput., C-35(8):677--691, Aug. 1986.

Digital Library

[8]

C. Paar, P. Fleischmann, and P. Soria-Rodriquez. Fast Arithmetic for Public-key Algorithms in Galois Fields with Composite Exponents. IEEE Trans. Comp., 48(10):1025--1034, Oct. 1999.

Digital Library

[9]

C. Wang, V. Singal, and M. Ciesielski. BDD Decomposition for Efficient Logic Synthesis. In Int. Conf. Comput. Aided Design (ICCAD), pages 626--631, 1999.

Digital Library

[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]

C. H. Wu, C. M. Wu, M. D. Sheih, and Y. T. Hwang. High-Speed, Low-Complexity Systolic Design of Novel Iterative Division Algorithm in GF(2^m). IEEE Trans. Comput., 53:375--380, Mar. 2004.

Digital Library

[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. M. Miller and R. Drechsler. On the Construction of Multiple-Valued Decision Diagrams. In Proc. 32nd ISMVL, pages 245--253, Boston, USA, 2002.

Digital Library

[14]

D. Y. Grigoriev and M. Karpinski. Fast Parallel Algorithms for Sparse Multivariate Polynomials Over Finite Fields. SIAM J. Computing, 19(6):1059--1063, Dec. 1990.

Digital Library

[15]

H. Wu and M. A. Hasan. Efficient Exponentiation of a Primitive Root in GF(2^m). IEEE Trans. Comp., 46(2):162--172, Feb. 1997.

Digital Library

[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]

J. L. Imaña, J. M. Sánches, and F. Tirado. Bit Parallel Finite Field Multipliers for Irreducible Trinomials. IEEE Trans. Comp., 55(5):520--533, May 2006.

Digital Library

[18]

M. Abramovici, M. Breuer, and A. Friedman. Digital Systems Testing and Testable Design. IEEE Publications, 1994.

[19]

M. Ben-Or and P. Tiwari. A Deterministic Algorithm for Sparse Multivariate Polynomial Interpolation. In Proc. 20th Symp. Theory of Computing, pages 301--309, Apr. 1988.

Digital Library

[20]

M. Clausen, A. Dress, J. Grebmeier, and M. Karpinski. On Zero-Testing and Interpolation of k-Sparse Polynomials over Finite Fields. Theoretical Comp. Sci., 84(2):151--164, Jan. 1991.

Digital Library

[21]

M. J. Ciesielski, P. Kalla, Z. Zeng, and B. Rouzeyere. Taylor Expansion Diagrams: A Compact, Canonical Representation with Applications to Symbolic Verification. In Design Automation and Test in Europe, Mar. 2002.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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]

S. Wicker. Error Control Systems for Digital Communication and Storage. Prentice Hall, Englwood Cliffs, N.J., 1995.

Digital Library

[27]

Z. Zilic and Z. Vranesic. A Multiple-Valued Reed-Müller Transform for Incompletely Specified Functions. IEEE Trans. Comp., 44(8):1012--1020, Aug. 1994.

Digital Library

[28]

Z. Zilic and Z. G. Vranesic. A Deterministic Multivariate Interpolation Algorithm for Small Finite Fields. IEEE Trans. Comput., 51(9):1100--1105, Sept. 2002.

Digital Library

Cited By

Mathew JJabir ARahaman HArgyrides CPradhan D(2009)On the synthesis of bit-parallel Galois field multipliers with on-line SEC and DEDInternational Journal of Electronics10.1080/0020721090316834896:11(1161-1173)Online publication date: Nov-2009
https://doi.org/10.1080/00207210903168348

Index Terms

An efficient technique for synthesis and optimization of polynomials in GF(2^m)
1. Hardware
  1. Electronic design automation
    1. High-level and register-transfer level synthesis
    2. Logic synthesis
      1. Circuit optimization
  2. Hardware validation
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
  2. Mathematical analysis
    1. Numerical analysis
      1. Number-theoretic computations

Recommendations

A Systolic Power-Sum Circuit for GF(2/sup m/)

A systolic power-sum circuit designed to perform AB/sup 2/+C computations in the finite field GF(2/sup m/) is presented, where A, B, and C are arbitrary elements of GF(2/sup m/). This new circuit is constructed by m/sup 2/ identical cells, each of which ...
GF(4) Based Synthesis of Quaternary Reversible/Quantum Logic Circuits
ISMVL '07: Proceedings of the 37th International Symposium on Multiple-Valued Logic

Galois field sum of products (GFSOP) has been found to be very promising for reversible/quantum implementation of multiple-valued logic. In this paper, we show ten quaternary Galois field expansions, using which quaternary Galois field decision diagrams ...
Low Complexity Bit-Parallel Multiplier for GF(2^m) Defined by All-One Polynomials Using Redundant Representation

This paper presents a new bit-parallel multiplier for the finite field GF(2^m) defined by an irreducible all-one polynomial. In order to reduce the complexity of the multiplier, we introduce a redundant representation and use the well-known ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

ICCAD '06: Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design

November 2006

147 pages

ISBN:1595933891

DOI:10.1145/1233501

General Chair:
Soha Hassoun
Tufts Univ., Medford, MA

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IEEE-CAS: Circuits & Systems
IEEE-CS: Computer Society

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 November 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ICCAD06

Sponsor:

SIGDA
IEEE-CAS
IEEE-CS

ICCAD06: The International Conference on Computer-Aided Design 2006

November 5 - 9, 2006

California, San Jose

Acceptance Rates

Overall Acceptance Rate 457 of 1,762 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
233
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)1

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Mathew JJabir ARahaman HArgyrides CPradhan D(2009)On the synthesis of bit-parallel Galois field multipliers with on-line SEC and DEDInternational Journal of Electronics10.1080/0020721090316834896:11(1161-1173)Online publication date: Nov-2009
https://doi.org/10.1080/00207210903168348

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten