10-11-2012, 06:20 PM
Digital Computer Arithmetic
Speeding Up Multiplication
Multiplication involves 2 basic operations - generation of partial products + their accumulation
2 ways to speed up - reducing number of partial products and/or accelerating accumulation
3 types of high-speed multipliers:
Sequential multiplier - generates partial products sequentially and adds each newly generated product to previously accumulated partial product
Parallel multiplier - generates partial products in parallel, accumulates using a fast multi-operand adder
Array multiplier - array of identical cells generating new partial products; accumulating them simultaneously
No separate circuits for generation and accumulation
Reduced execution time but increased hardware complexity
Reducing Number of Partial Products
Examining 2 or more bits of multiplier at a time
Requires generating A (multiplicand), 2A, 3A
Reduces number of partial products to n/2 - each step more complex
Several algorithm which do not increase complexity proposed - one is Booth's algorithm
Fewer partial products generated for groups of consecutive 0’s and 1’s