Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Optimization of Primitive Gate Networks Using Multiple Output Two Level Minimization

IP.com Disclosure Number: IPCOM000110131D
Original Publication Date: 1992-Oct-01
Included in the Prior Art Database: 2005-Mar-25
Document File: 3 page(s) / 135K

Publishing Venue

IBM

Related People

Malik, AA: AUTHOR

Abstract

A process is disclosed that helps in reducing the size of primitive gate networks. Such networks are used to represent parts of digital integrated circuits during their automatic design. Reduction of a primitive gate network enables a reduction in the size of the integrated circuit, thus lowering the cost.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 48% of the total text.

Optimization of Primitive Gate Networks Using Multiple Output Two Level Minimization

       A process is disclosed that helps in reducing the size of
primitive gate networks. Such networks are used to represent parts of
digital integrated circuits during their automatic design.  Reduction
of a primitive gate network enables a reduction in the size of the
integrated circuit, thus lowering the cost.

      The application of two-level minimization has proved very
useful for the optimization of multi-level Boolean networks in MIS: a
computer program for designing digital integrated circuits (1).  MIS
represents the network as a Directed Acyclic Graph (DAG).  Each node
of the graph represents a two-level logic expression.  The two-level
minimization is carried out for each node.  The minimization uses the
implicit don't cares which are derived from the structure of the
network (2).  The result is a reduction of the functions at nodes of
the graph which, in turn, results in the reduction in the area of the
digital circuit being designed.

      There are many other programs that use primitive gates: OR,
AND, NOR, NAND, and INV rather than a MIS-like DAG representation.
Examples of such programs are LSS (3), BOLD (4) and SYLON (5).  An
efficient method for two-level minimization of primitive gate
networks is therefore of importance.

      Treating each primitive gate as a node of the graph for the
purpose of two-level minimization is not very helpful because the
two-level function associated with a primitive gate is too small to
be reduced substantially.

      Another approach that can be considered is to selectively
collapse parts of the network to two levels and apply the two-level
minimization to each collapsed part.  There are several problems with
that approach.  First, the collapsing of a part of the network
usually increases its size.  The two-level minimization is often not
able to reduce the size to less than the pre-collapsed size.
Secondly, the quality of the optimization will depend heavily on how
the parts to be collapsed are selected.  Finally, it may become
difficult to collapse parts of the network if the network contains
gates that the user may not like to be altered.

      A novel process is disclosed here for applying the two-level
minimization to primitive gate network.  This process does not
collapse the network.  For each gate in the network, a two-level
expression is set up.  In this process, a reduction in the size of
the two-level expression guarantees a reduction in the number of
connections and possibly in the number of gates in the network.
Unlike MIS that uses single output minimization, this approach uses
multiple output two-level minimization.

      The primitive gate network is first converted into one
consisting solely of NOR gates or NAND gates.  The process will be
described for the NOR-network.  With minor modifications the process
is applicable to a NAND-network....