Efficient FPGA Implementation of Low-Complexity Systolic Karatsuba Multiplier Over $GF(2^{m})$ Based on NIST Polynomials

Abstract

Systolic implementation of Karatsuba algorithm (KA)-based digit-serial multiplier over GF(2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</sup> ) on field-programmable gate array (FPGA) platforms has many attractive features, such as efficient tradeoff in area-time complexity and high-throughput rate. But on the other side, it suffers from high register-complexity, which leads to increase in area and power consumption. In this paper, we present an algorithm and architecture for efficient FPGA implementation of KA-based digit-serial systolic multiplier over GF(2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</sup> ) based on the National Institute of Standards and Technology (NIST) recommended polynomials. A number of efficient techniques have been explored and used to realize efficient implementation of these multipliers. First, we propose a novel KA-based approach, where the computational complexity is significantly reduced compared with the existing one. Second, we propose efficient register minimization techniques, such as redundant register removal, two-stage pipelining, and register sharing to reduce the register complexity of the proposed structure. Third, we adopt an efficient FPGA-specific digit-parallel implementation strategy to optimize the area-time-power complexities of the proposed structure on FPGA platforms. The results obtained from FPGA synthesis indicate that the proposed multiplier (for field based on NIST trinomial GF(2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">233</sup> )) has significantly lower area-time-power complexities than the existing designs, e.g., the proposed structure could achieve 65.7% and 73.6% reduction on area-delay product and power-delay product over the best of existing KA-based systolic structures, respectively.