VLSI Design of Karatsuba Integer Multipliers and Its Evaluation

Multidigit multiplication is widely used for various applications in recent years, including numerical calcula-tion, chaos arithmetic, and primality testing. Systems with high performance and low energy consumption are de-manded, especially for image processing and communica-tions with cryptography using chaos. Karatsuba algorithm with computational complexity of O(n1.58) has been em-ployed in software for multiplication of hundreds to thou-sands of bits, where n stands for bit-length of operands. In this paper, hardware design of multidigit integer multipli-cation based on Karatsuba algorithm is described and its VLSI realization is evaluated in terms of the cost, perform-ance, and energy consumption. We present two design choices of the Karatsuba hardware: RKM (Recursive Karatsuba Multiplier) and IKM (Iterative Karatsuba Mul-tiplier). We found that RKM has less area cost than WTM (Wallace Tree Multiplier) for bit-length larger than 29 with area cost of 30 mm2. Critical path delay of RKM is always larger than that of WTM. Therefore, we should use WTM as combinational circuits for IKM to have better cost per-formance. We also found that a version of IKM using 0.18 µm process can perform 1024-bit multiplications 30 times faster than software at the area cost of 10.9 mm2. Energy for the computation by the IKM version was found to be nearly 1/600 of that consumed by general-purpose proces-sor which executes the software. The results obtained by this study will help system designers for applications re-quiring multidigit multiplication to select design alterna-tives including ASIC realization. © 2009 Wile