For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Low-Latency Bit-Parallel Systolic Multiplier for Irreducible xm + xn + 1 with GCD(m,n) = 1
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2003/11/01
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Algorithms and Data Structures
bit-parallel systolic multiplier, finite field, irreducible trinomial,
Full Text: PDF>>
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.