Browse Prior Art Database

Method for recognizing MUX elements in transistor-level circuits

IP.com Disclosure Number: IPCOM000004909D
Publication Date: 2001-Jul-11
Document File: 6 page(s) / 140K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a method for recognizing MUX elements in transistor-level circuits. Benefits include improved automated recognition of MUX elements for use in chip-design modeling.

This text was extracted from a Microsoft Word 97 document.
This is the abbreviated version, containing approximately 26% of the total text.

Method for recognizing MUX elements in transistor-level circuits

Disclosed is a method for recognizing MUX elements in transistor-level circuits. Benefits

include improved automated recognition of MUX elements for use in chip-design modeling.

The disclosed method identifies general N-to-1 (N =2) MUXs in transistor level circuits. The algorithm assumes that all relevant transistors in the design are unidirectional. Most transistor- level circuit analysis programs split the circuit into Channel Connected Sub-Networks

(CCSN) then analyze the circuit on a CCSN basis. The biggest problem with this approach is in custom digital designs with pass-transistor logic where each CCSN is quite large. The

size is a consequence of pass transistors that connect the channel regions of different gates that otherwise would each comprise a separate CCSN. This complexity makes the analysis

complicated, if not impossible. The Boolean equations that describe the CCSN are dual-rail and not complimentary and introduce too many tri-state devices into the model. Eventually, many

types of MUX structures are not recognized. This causes downstream test generation tools to be inefficient because unmodeled MUX transistors are treated as tri-state elements.

The disclosed method splits a CCSN into smaller groups that are easily recognizable. While pattern recognition has been attempted before, the disclosed algorithm achieves its goal in an efficient way using sorting techniques. Its runtime complexity is O(nlogn), where n is the number of transistors in a CCSN. This compares favorably with the O(n3) complexity of symbolic Gaussian elimination, which often used by comparable tools in industry and

academia. Furthermore, symbolic Gaussian elimination yields dual-rail equations and introduces tri-state devices in the final model.

Figure 1 shows the circuit for a latch. Figure 2 shows the largest CCSN in the circuit.

This CCSN has a NAND gate, an inverter, 2 MUX gates, and a pass transistor gate. Because of the pass transistors, the NAND gate and the inverter transistors are part of this CCSN. Figure 2 also indicates the node numbers assigned to various signals in the circuit. The node numbers start at 1. Ground and power nodes are assigned 1 and 2 respectively.

Each transistor in the circuit is identified by its attributes, which include (but are not limited to) the following fields:

Source

Drain and gate nodes

CCSN integer identifier

Transistor type (NIP)

Signal-f1ow direction that is always source-to-drain initially

The last field may change to drain-to-source if the source and drain fields in the transistor record get swapped. The Source and Drain fields are swapped if the source node identifier is less than the drain node identifier. The signal flow direction attribute is changed in that case. When all transistor node identifiers are swapped (as required), the transistors are sorted by their CCSN identifiers. An in-place sort algorithm that reorders the transistors in an initial array without req...