Subquadratic Space-Complexity Digit-Serial Multipliers Over $GF(2^{m})$ Using Generalized $(a,b)$ -Way Karatsuba Algorithm
Chiou‐Yng Lee, Pramod Kumar Meher · IEEE Transactions on Circuits and Systems I Regular Papers · 2015
Karatsuba algorithm (KA) is popularly used for high-precision multiplication by divide-and-conquer approach. Recently, subquadratic digit-serial multiplier based on (a,2)-way KA decomposition is proposed in [1]. In this paper, we extend a (a,2)-way KA to derive a generalized (a,b)-way KA decomposition with a ≠ b. We have shown that (a,2)-way KA and mult-way KA are special cases of the proposed (a,b)-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.