32-bit-microprocessor

Karatsuba Multiplier: Multiplier takes [31:0] inputs which are multiplied using Karatsuba algorithm. General iterative method and Booths algorithm requires many iterations this increases hardware complexity and propagation delay. The delay of Booths algorithm is in the order of (n^2). But Karatsuba algorithm follow divide and conquer methodology. Example : consider two 2 bit operands (a1,a0),(b1,b0) multiplication. By naive approach we solve acoordingly. a1 a0 * b1 b0 = (a1 a0)b0 + (a1 a0 0)b1. This require 4 time units but through karatsuba algorithm we solve as a1b12^2 + (a1b0 + a0b1)2 + a0b0.