Low Complexity Multiplexer-Based Parallel Multiplier of GF(2^m)

Gi-Young BYUN, Heung-Soo KIM

Summary :

Two operations, polynomial multiplication and modular reduction, are newly induced by the properties of the modified Booth's algorithm and irreducible all one polynomials, respectively. A new and effective methodology is hereby proposed for computing multiplication over a class of fields GF(2^m) using the two operations. Then a low complexity multiplexer-based multiplier is presented based on the aforementioned methodology. Our multiplier consists of m 2-input AND gates, an (m² + 3m - 4)/2 2-input XOR gates, and m(m - 1)/2 4 1 multiplexers. For the detailed estimation of the complexity of our multiplier, we will expand this argument into the transistor count, using a standard CMOS VLSI realization. The compared results show that our work is advantageous in terms of circuit complexity and requires less delay time compared to previously reported multipliers. Moreover, our architecture is very regular, modular and therefore, well-suited for VLSI implementation.

• Publication: IEICE TRANSACTIONS on Information Vol.E86-D No.12 pp.2684-2690
• Publication Date: 2003/12/01
• Type of Manuscript: PAPER
• Category: Computer System Element

Authors

Gi-Young BYUN
Heung-Soo KIM

Keyword

finite fields,  MUX-based multiplier,  all one polynomials (AOP),  standard basis,  circuit complexity