Subquadratic Space-Complexity Digit-Serial Multipliers Over $GF(2^{m})$ Using Generalized $(a,b)$-Way Karatsuba Algorithm

摘要

Karatsuba algorithm (KA) is popularly used for high-precision multiplication by divide-and-conquer approach. Recently, subquadratic digit-serial multiplier based on -way KA decomposition is proposed in [1]. In this paper, we extend a -way KA to derive a generalized -way KA decomposition with . We have shown that -way KA and mult-way KA are special cases of the proposed -way KA decomposition. Based on the proposed KA decomposition, we have established two types of subquadratic digit-serial multipliers, namely, the KA-based multiplier and the recombined KA-based multiplier. From theoretical analysis, as well as, from synthesis results we have shown that the proposed KA-based multipliers have significantly less delay and less area-delay product (ADP) compared to the existing naive digit-serial multipliers.