Fast Parallel Multiplication Using Redundant Quarternary Number System
Mallika De, Bhabani P. Sinha · Parallel Processing Letters · 1997
In this paper, we propose a high-speed VLSI multiplication scheme using redundant radix-4 representation of numbers. For m-digit by m-digit redundant radix-4 integer multiplication, we first generate m partial products, each of (m+1) digits in redundant radix-4 (RR-4) number system. These partial products are then added up four at a time by means of redundant quarternary adders. Parallel addition of four (m+1)-digit redundant radix-4 numbers can be performed in a constant time independent of m without any carry propagation. With these adders, multiplication of two m-digit numbers in RR-4 number system can be performed in ⌈(1/2)log2 m ⌉ + 1 steps of such additions of four RR-4 numbers. The number of computational elements of an m-digit multiplier based on the proposed algorithm is O(m2). Since the multiplier has a regular cellular array structure, it is suitable for VLSI implementation with O(m2 log m) AT-value.