loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
12th IEEE Symposium on Computer Arithmetic (ARITH-12 '95)
Design Strategies for Optimal Multiplier Circuits
Bath, England
July 19-July 21
ISBN: 0-8186-7089-4
We present new design and analysis techniques for the synthesis of fast parallel multiplier circuits. In \cite{Vojin}, Oklobdzija, Villeger, and Lui suggested a new approach, the Three Dimensional Method (TDM), for Partial Product Reduction Tree (PPRT) design that produces multipliers which outperform the current best designs. The goal of TDM is to produce a minimum delay PPRT using full adders. This is done by carefully modelling the relationship of the output delays to the input delays in an adder, and then interconnecting the adders in a globally optimal way. Oklobdzija, et.~al. suggested a good heuristic for finding the optimal PPRT, but no proofs about the performance of this heuristic were given. We provide a formal characterization of optimal PPRT circuits and prove a number of properties about them. For the problem of summing a set of input bits within the minimum delay, we present an algorithm that produces a minimum delay circuit in time linear in the size of the inputs. Our techniques allow us to prove tight lower bounds on multiplier circuit delays. These results are combined to create a program which finds optimal TDM multiplier designs.
Index Terms:
Multiplier design, Partial product reduction, Algorithms, Circuit design
Citation:
Charles Martel, Vojin Oklobdzija, R. Ravi, Paul Stelling, "Design Strategies for Optimal Multiplier Circuits," arith, pp.42, 12th IEEE Symposium on Computer Arithmetic (ARITH-12 '95), 1995
Usage of this product signifies your acceptance of the Terms of Use.