Circuit design methods and tools

• US 5,841,674 A
• Filed: 04/29/1997
• Issued: 11/24/1998
• Est. Priority Date: 12/14/1995
• Status: Expired due to Term

• Current Assignee: Synopsys Incorporated
• Original Assignee: Viewlogic Systems, Inc. (Siemens AG)
• Inventors: Johannsen, David L.
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): Kik, Phallaka
• Application Number:
  US08/845,813
• Time in Patent Office: 574 Days
• Field of Search: 364/488-491, 364/754.01-760.05
• US Class Current: 716/104
• CPC Class Codes: G06F 2207/3852 Calculation with most significant digit first
• CPC Class Codes: G06F 30/30 Circuit design
• CPC Class Codes: G06F 7/5318 with column wise addition of partial products, e.g. using Wallace tree, Dadda counters G06F7/5324 takes precedence

Abstract

A circuit design tool which includes an architecture for a multiplier which is faster and more compact than known multipliers through the use of Wallace trees, the elimination of Dadda nodes along the critical paths, the placement of half-adders at an initial pat of the Wallace tree, the replacement of low-order terminating adders with ripple-carry adders, and the replacement of high-order terminating adders with carry-select adders.

Claims

1. A method for the operation of a circuit design tool to design a multiplier circuit, comprising the steps of

forming a netlist for a Wallace tree, whereby said Wallace tree comprises a tail of adders;

tracing a critical path for said netlist to a Dadda node in said Wallace tree and eliminating said Dadda node by replacing said Dadda node with a full-adder;

placing a half-adder at an initial part of said Wallace tree and removing an adder in said tail; and

repeating said steps of tracing and placing until a selected condition is reached.

2. A method for the operation of a circuit design tool to design a multiplier circuit as in claim 1, wherein said selected condition is that said tail is minimized.

3. A method for the operation of a circuit design tool to design a multiplier circuit as in claim 1, comprising the steps of

forming a netlist for a final adder coupled to said Wallace tree;

and

forming a netlist for a ripple carry adder at a low end of said Wallace tree and removing a portion of said final adder.

4. A method for the operation of a circuit design tool to design a multiplier circuit as in claim 1, comprising the steps of

forming a netlist for a final adder coupled to said Wallace tree;

and

forming a netlist for a carry select adder at a high end of said Wallace tree and removing a portion of said final adder.

5. A method for the operation of a circuit design tool to design a multiplier circuit as in claim 1, comprising the steps of

defining a matrix of partial products;

recoding pairs of said partial products so as to select each said partial product from a set of more than two possible outputs;

wherein said step of forming a netlist for a Wallace tree is responsive to said step of recoding.