Low-Latency Bit-Parallel Systolic Multiplier for Irreducible xm + xn + 1 with GCD(m,n) = 1

Chiou-Yng LEE  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E86-A   No.11   pp.2844-2852
Publication Date: 2003/11/01
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Algorithms and Data Structures
bit-parallel systolic multiplier,  finite field,  irreducible trinomial,  

Full Text: PDF>>
Buy this Article

This investigation proposes a new multiplication algorithm in the finite field GF(2m) over the polynomial basis, in which the irreducible xm +xn + 1 with gcd(m,n) = 1 generates the field GF(2m). The algorithm involves two steps--the intermediate multiplication and the modulo reduction. In the first step, the intermediate multiplication algorithm permutes a polynomial to construct the full-bit-parallel systolic intermediate multiplier. The circuit is identical of m2 cells, each cell is identical of one 2-input AND gate, one 2-input XOR gate, and four 1-bit latches. In the second step, based on the results of the intermediate multiplication in the first step, the modulo reduction circuit is built using regular and simple reduction operations. The latency of the proposed multiplier requires m + k + 1 clock cycles, where k = + 1. Notably, the latency can be very low if n is in the range 1 n . For the computing multiplication in GF(2m), the novel multiplier exhibits much lower latency than the existing systolic multipliers, and is well suited to VLSI systems due to their regular interconnection pattern, modular structure and fully inherent parallelism.