Low-Latency Bit-Parallel Systolic Multiplier for Irreducible x^m+x^n+1 with GCD(m, n) =1(Algorithms and Data Structures)

概要

論文の詳細を見る
This investigation proposes a new multiplication algorithm in the finite field GF (2^m) over the polynomial basis, in which the irreducible x^m+x^n+1 with gcd (m, n) =1 generates the field GF (2^m). 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 m^2 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= [(m-2)/(m-n)] +1. Notably, the latency can be very low if n is in the range 1【less than or equal】 n 【less than or equal】 [(m/2)]. For the computing multiplication in GF (2^m), 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.
一般社団法人電子情報通信学会の論文
2003-11-01