Systematic design of original and modified Mastrovito multipliers for general irreducible polynomials

Tong Zhang, Keshab K. Parhi

Research output: Contribution to journalArticle

82 Scopus citations

Abstract

This paper considers the design of bit-parallel dedicated finite field multipliers using standard basis. An explicit algorithm is proposed for efficient construction of Mastrovito product matrix, based on which we present a systematic design of Mastrovito multiplier applicable to GF(2 m) generated by an arbitrary irreducible polynomial. This design effectively exploits the spatial correlation of elements in Mastrovito product matrix to reduce the complexity. Using a similar methodology, we propose a systematic design of modified Mastrovito multiplier, which is suitable for GF(2 m) generated by high-Hamming weight irreducible polynomials. For both original and modified Mastrovito multipliers, the developed multiplier architectures are highly modular, which is desirable for VLSI hardware implementation. Applying the proposed algorithm and design approach, we study the Mastrovito multipliers for several special irreducible polynomials, such as trinomial and equally-spaced-polynomial, and the obtained complexity results match the best known results. Moreover, we have discovered several new special irreducible polynomials which also lead to low-complexity Mastrovito multipliers.

Original languageEnglish (US)
Pages (from-to)734-749
Number of pages16
JournalIEEE Transactions on Computers
Volume50
Issue number7
DOIs
StatePublished - Jul 1 2001

    Fingerprint

Keywords

  • Complexity
  • Finite (or Galois) field
  • Irreducible polynomials
  • Multiplication
  • Standard basis
  • Toeplitz matrix
  • VLSI architecture

Cite this