3." s
l" .
un- ..-

. I)?

haw:

‘.
.

; .9 . .w
v ~.\ .73....D f). ‘ o x . .
, I F g .' >7. .l V . a. » I .A
, .....L 35.5,... ...; \ "Eran..- ...-bur...) .
.rh". ...fié ..h-.’h1“‘l..v it‘s-£11.“, Llawth.
. . s . p t.
.it‘ .5551! h"- | ...-....erl

‘22:.
i= W
Y

7'. .
)

W
3.
I ‘ 3ng
W
.1;

\
.1

3.1... rl‘liAll
.I. ..‘.-.I..I.!l)’

. .5.
“*1

flu»
3.1%.”?
II. ‘
‘l‘,
E... :
~| \

if

‘2?!
’1‘: '

ti
:fi:

.
I'v
“1.

3mm- 0... . u ,
1)}...3:

’3

“3.
if

{ti
2... .s

if

,.
19;.
.W
“'3: .

1'.

. t9. ..- 1-.
2 .Iltl. .l ‘51.!).Ipz.l.l‘ \nofi.
‘3... It.

1,3?“

{£1le
.5 .

H. “and”.

-11.» .

.-vit .Irl‘. \\|A..

. . .-nvlrka‘ 1’ {.0 -0)... x.
. .l \..-’. . 3“» .L.‘

d. . ."
[I .n”
.g's'r,

.14.)...“
Low-ill.
I’l‘ ...IIHh

1?
h'
'4

t
.
Q
I
a

| voila-..-.

..LVN . .

f.“|yli
...lll‘l.‘

1!. '

.. .91. .0. .
..lorIOI. C. . lowdgkg’lv: iV-bl

. I it);
l’lI'Ol ‘5')!"
...‘4‘ ni‘li‘glill

L'f‘i
3.11 .3

g.
‘ 5.1"

g

41.3.!

. , .7 . ‘ . . . ... .. “....ru
. . Z 531......IIII
-.. If- I}?! . . . . . .. A . . . . . r. l.!l7.c..'f.
sinitlul; . 1.9.1! .5...u..:)....x 3 .. _ V . . . - ‘
I v.-. . l 0 -\0 .. . i .
.ulnrot 01...? .. I. Lt. . . . . .... .. ......I.
. in... . . H . V... 501.--, . “a .9! ... .... .. $2.5. Janna... .
r . . I . . i.‘ .YI‘! I! u t .. .... a not: w J" E
5.. . , kt t’biv- .31! ‘ti' .1 .c .‘s ..r: 5' a [4.51 I. . 1.3% l-
. . It 2‘. .) .... . ...av . ... . .2 311‘}: . . .. \A.\I.\n . .. ’.0 -...vtr . . .-
10.5.. 04$ .\ v f o “Hanna“ N... anf;:.vs~...v .m} :wfl.-l.}. i .3! )aul.-¢.r...| \! t .9051...” x , at): \ é. .. IUIII. F >-rt.v ..I ‘4!!!
.l.‘n'fl .... \rl.\.ll1n.t.n. ..I...O t vu..-ifl..\..|. ‘i..k.‘. ..u 1!...711 x - A .I . . .. .
x I v o 0 Vi‘ 0 I I f a O b I! - I 4 c .I I l .u .

.
( ... .l -.-... 2:: 12.";

15:33-... 3.... 2..-..- .
l - i l I. .--. 1,171-. .I....umr.r..!_ ‘. 1x. : . ,_. . . - a .
L..--fll..l2) I. Ruggma I? .1 . .

15'.lvw.y ...-Ir- , V t
......v. ...: 2‘ - -... v ... . ...a. -...t. 1.1.51... .

 

).V-.-

730‘! 504}

 

 

(am... r
Michigan State llHlWlHHIIHINHUNU

NIVERSITY LIBRARIESll

l ll'llll‘lll

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

o 3 1293 00574 0018 .
University +
This is to certify that the
dissertation entitled

VERIFICATION 0F MOS CIRCUITS AT THE SWITCH LEVEL

presented by

JIANN. LIAO

has been accepted towards fulfillment
of the requirements for

Ph.D. degree in Compter Science

 

 

$3401- professor

Date 01/08/1990

 

MS U is an Affirmative Action/Equal Opportunity Institution 0-12771

 

 

BOX to temave this checkout from your record.

LACE IN RETURN
on at before date due.

p
TO AVOID FINES mun

ATE DUE DATE DUE DATE DUE

           

 

/

’—

 

7

_4_
#l #-

1,

i i1: 0
J

 

 

_‘_

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

VJ L ‘l
E: L913

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

VERIFICATION OF MOS CIRCUITS

AT THE SWITCH LEVEL

By
J iann Liao
A DISSERTATION
Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of

DOCTOR OF PHILOSOPHY

Department of Computer Science

1990

ABSTRACT

VERIFICATION OF MOS CIRCUITS
AT THE SWITCH LEVEL

By

Jiann Liao

Because of the nature of MOS transistors, digital MOS circuits have been modeled
at the switch level rather than the traditional gate level. In this research, a novel switch
level circuit representation called Structured LogIcal Circuit Expression (SLICE) is pro-
posed to represent both the connectivity and signal flow information of MOS circuits.
Effective circuit verification methods based on the proposed representation are presented.
Circuit verification is crucial in today’s VLSI circuit design to ensure the correctness of
the design. The proposed switch level verification methods include functionality extrac-
tiOn, logic simulation, and signal flow analysis in timing verification. The first two
methods are used to assure the functional correctness of the design, while the third is

used to examine the timing constraints of the design.

When performing functional verification, the functionality (or Boolean behavior) of
a design must be extracted so that the functionality comparison between a design and its
specification can be performed. Several rules are developed from the SLICE representa-
tion to do the functionality extraction of different MOS circuit design styles. These rules
are capable of verifying both the functional correctness and the electrical safety of a
design. The whole functionality extraction process is achieved by a divide-and-conquer
algorithm which guides the application of the rules. Since SLICE describes the func-
tional as well as structural information contained in the circuits, efficient switch level

logic simulation can be demonstrated on the circuits represented by the proposed

representation. Experiment results are presented for functionality extraction.

To investigate the tinting behavior of circuits, we propose a switch level timing
verification method based on signal flow analysis of circuits in SLICE representation.
Due to a lack of proper functional information, signal paths may be falsely reported by
timing verifiers for some circuits. An algorithm is proposed to eliminate the false signal
paths from the possible paths. Furthermore, a heuristic algorithm is presented to expedite

the signal pathfinding process.

In conclusion, the contribution of this work to the verification of MOS circuits is

summarized and suggestions are offered for future research.

To my parents

iv

ACKNOWLEDGEMENTS

I wish to thank my advisor, Dr. Lionel M. Ni, for his guidance and encouragement
over the years of research work leading to this dissertation. I am also indebted to Dr.
Anthony S. Wojcik, Dr. Sakti Pramanik, and Dr. Dorian Feldman for their many valuable

suggestions and comments on this work.

I would also like to acknowledge my fellow graduate students who have helped me
in the course of my studies for the Ph.D.: S.W. Chen, E. Wu, C.T. King, C.J. Lee, D. Ra,
D. Vineyard and C.J. Yang. A word of thanks is also due to Mr. M. Smith for editing the
final manuscript of the dissertation.

Finally I would like to thank my family for their love and their constant support of
my graduate studies.

Table of Contents

List of Tables ............................................................................................................ viii
List of Figures ........................................................................................................... ix
Chapter 1 Introduction ........................................................................................... 1
1.1. Introduction .................................................................................................... 1
1.2. Background ................................................................................................... 3
1.2.1. Switch Level Circuit Model ................................................................... 4

1.2.2. Circuit Verification ................................................................................ 5
1.2.2.1. Switch Level Logic Simulation ..................................................... 5

1.2.2.2. Timing Verification ........................................................................ 6

1.2.2.3. Functional Verification .................................................................. 7

1.3 Previous Work ................................................................................................ 9

1.4 Overview of the Dissertation .......................................................................... 11
Chapter 2 MOS Circuit Representation ................................................................. 13
2.1 Introduction ..................................................................................................... 13
2.2 MOS Circuit Model and Its Representation at the Switch Level ................... 13
2.2.1 Graph Corresponding to a MOS Circuit ................................................. 16

2.2.2 Directed Graph for MOS Circuits ........................................................... 19

2.3 SLICE Representation and Boolean Equation of MOS Circuits .................... 23
2.3.1 SLICE Representation ............................................................................ 24

2.3.2 Boolean Equation of MOS Circuits ........................................................ 27
Chapter 3 Extraction Rules ...................................................................................... 30
3.1 Introduction ..................................................................................................... 30
3.2 Electrical Property Consideration ................................................................... 31
3.3 Rules for Functionality Extraction .................................................................. 35
3.3.1 Extraction Rules ..................................................................................... 35

3.3.2 Extraction of Self-Defined SLICE .......................................................... 40

3.4 Generalized Extraction Rule 2 ........................................................................ 43

vi

3.5 Extraction of Dynamic Circuits ...................................................................... 46

Chapter 4 Functionality Extraction Procedure .................................................... 48
4.1 Functionality Extraction Algorithm for a Transistor Group ........................... 48
4.1.1 Functionality Extraction for Circuits with DAG .................................... 51

4.1.2 Functionality Extraction for General Circuits ........................................ 61

4.2 Functionality Aggregation .............................................................................. 63
4.2.1 Aggregating Functionalities of Groups ................................................... 63

4.2.2 Extraction Rule Among Groups ............................................................. 68

4.3 Conclusion ...................................................................................................... 69
Chapter 5 Signal Flow Analysis in Timing Verification ....................................... 71
5.1 Introduction ..................................................................................................... 71
5.2 Timing Verification on SLICE Representation ............................................... 71

5.3 False Signal Path Problems in Timing Verification ........................................ 76
5.4 Method to Identify Correct Signal Flow Direction ......................................... 79

5.5 Heuristic to Find Signal Path Direction .......................................................... 81
5.6 Experiment and Discussion ............................................................................ 83
Chapter 6 Logic Simulation with SLICE ................................................................ 90
‘ 6.1 Logic Simulation at the Switch Level ............................................................ 90
6.2 Logic Evaluation of SLICE in Simulation ...................................................... 91
Chapter 7 Conclusion and Future Work ............................................................... 97
7.1 Summary ......................................................................................................... 97
7.2 Future Work .................................................................................................... 99
List of References .................................................................................................... 103

vii

List of Tables

Table 4.1: Extraction time for different circuits on SUN 3/280 ................................ 70

viii

List of Figures

Figure 1.1 VLSI design flow ...................................................................................... 6
Figure 2.1 Graph representation of a MOS circuit .................................................... 18
Figure 2.2 LDCC w.r.t. node f ................................................................................... 23
Figure 2.3 A MOS circuit and its LDCCs ................................................................. 26
Figure 2.4 A MOS circuit and its LDCC .................................................................. 29
Figure 3.1 A functional verification scheme ............................................................. 31
Figure 3.2 A safe circuit ............................................................................................ 33
Figure 3.3 An unsafe circuit ...................................................................................... 33
Figure 3.4 A circuit with two transistor groups ........................................................ 34
Figure 3.5 Pass transistor logic design ...................................................................... 36
Figure 3.6 XOR circuit ............................................................................................. 37
Figure 3.7 Circuit with logic A state ......................................................................... 37
Figure 3.8 Pseudo-nMOS circuit .............................................................................. 40
Figure 3.9 Circuit which is not an SMC ................................................................... 41
Figure 3.10 Circuit with self-defined SLICE ............................................................ 43
Figure 3.11 Dynamic NOR gate ............................................................................... 47
Figure 4.1 Circuit demonstrating divide-and-conquer verification approach ........... 49
Figure 4.2 Algorithm to perform functionality extraction of circuits with DAG 52
Figure 4.3 Algorithm to search for junction nodes ................................................... 54
Figure 4.4 A DCC and its JNPG ............................................................................... 56
Figure 4.5 Circuit to be extracted ............................................................................. 59
Figure 4.6 Algorithm for the functionality extraction of a general directed graph .. 61
Figure 4.7 Circuit with cycles in its DCC ................................................................. 62
Figure 4.8 Circuit demonstrating functionality aggregation ..................................... 65
Figure 4.9 Circuit aggregated ................................................................................... 66
Figure 4.10 Circuit needs extra knowledge when aggregating ................................ 67
Figure 4.11 Circuit with DCVS design style ............................................................ 69
Figure 5.1 Schematic of a CMOS circuit and its corresponding gate level network 73
Figure 5.2 2-bit shifter ............................................................................................. 75
Figure 5.3 Circuit with false path problem ............................................................... 77
Figure 5.4 Multiplexer circuit ................................................................................... 78

ix

Figure 5.5 Full adder and its directed group graphs ................................................. 85

Figure 5.6 3-bit barrel shifter and its directed group graph ...................................... 86
Figure 5.7 Tally circuit and its corresponding directed group graph ....................... 87
Figure 5.8 Circuit with different capacitances at nodes C l and C 2 ........................ 88
Figure 6.1 Lattice structures of different logic levels ............................................... 92
Figure 6.2 A DCVS XOR/XNOR gate ..................................................................... 93

Chapter 1

Introduction

 

1.1 Introduction

In today’s VLSI (Very Large Scale Integrated) circuit design, MOS (Metal Oxide
Silicon) technology [MeC080, WeEs85] is the dominant technology used. It is possible
now that hundreds of thousands of MOS devices may all be fabricated in a single chip.
To deal with this huge amount of devices, VLSI verification tools are indispensable to
the success of a design. Circuit verification is an important step in the process of ensur-
ing the correctness of the circuit design. Several kinds of verification may be required
for different verification purposes and different degrees of verification confidence. Com-
monly used verification methods include functional verification, timing verification, and

logic simulation.

Due to the nature of MOS transistors, digital MOS circuits have been modeled at
the switch level [Brya84, Haye82], instead of the traditional gate level. Therefore, many
MOS circuits are often designed and verified at the switch level. Identification of the sig-
nal flow direction of each transistor in the design is essential for performing different
kinds of verification. Only when all the correct signal paths are determined can tinting
verification be performed correctly [Joup87a, Oust85]. Knowing the signal flow direction

of every transistor in the circuit also facilitate efficient switch level simulation [RaTr87,

l

VaDS85]. Furthermore, until the correct signal path direction of the circuit is known,
functional verification cannot be properly applied to this circuit [WuNW87]. When only
the circuit connectivity information is available in a design, it is difficult to derive the
correct signal flow directions of the transistors in the circuit [Joup87b, Oust85]. How-
ever, a designer has the full knowledge of his/her own design, and can thus specify the
signal flow directions of the transistors in the design. Therefore, one proper way to ver-

ify the design of a MOS circuit is as follows.

(1) Pre-verify the circuit design, using estimated parasitics and known signal flow

directions specified by the designer before performing circuit layout;

(2) Compare precise parasitics, obtained by a circuit extractor after the circuit layout is
done, with the estimated parasitics used in the pre-verification and adjust the pre-

verification result; and

(3) Use wirelist comparison [Wata83, EbZa83, KoMc86, OTOO86] to make sure that
the layout-extracted wirelist matches the correct wirelist which has been pre-

verified in step (1).

From the above steps, we know that a circuit representation is demanded which can
represent both the signal flow and interconnection of a design. Since circuit schematic
representation only carries structural information, it cannot embed signal flow informa-
tion in the representation. Therefore, Other circuit design representations are required to

carry signal flow information in addition to structural information.

The Logical Circuit Expression proposed in [WuNW87] allows symbolic
verification of the functional correctness of MOS circuits. However, it cannot com-
pletely determine the circuit connectivity and does not describe the signal flow as
specified by the designer. Thus, it cannot be used as a design representation. A MOS
circuit representation called Structured Log/cal Circuit Expression (SLICE) is pr0posed

for this purpose. This representation is an extension of the Logical Circuit Expression

and eliminates its aforementioned shortcomings. The SLICE unifies the representation of
two major logic design styles, gate logic and path transistor logic, in M08 circuit design.
The SLICE also provides a systematic way to describe bOth the signal flow direction and
circuit connectivity of a design. Therefore, the SLICE representation can properly facili-
tate those processes of circuit verification which require signal flow information such as
timing verification, logic simulation, and functional verification. Circuit verification can
be performed more efficiently when it is based on the SLICE representation because
extra information is provided in addition to circuit connectivity information. The key
point in the efficient verification of a circuit is the expression of the circuit in terms of a

good representation.

It is also desired to automatically convert a circuit schematic, which only carries
connectivity information, into a circuit representation carrying functional information in
addition to structural information. By this automated process, the designer’s mistakes in
specifying signal flow can be eliminated, and the confidence of the design can be
increased. However, it turns out that this can be done only for most parts of a circuit.
Some part of the circuit will still need human intervention to complete the whole conver-
sion [Joup87b, Oust85]. Therefore, new methods to convert the representation of a cir-

cuit schematic into the desired representation are necessary.

The objective of this research is to develop a MOS circuit representation, namely
SLICE representation, which is able to provide both the functional (or signal flow) and
structural (or connectivity) information of a circuit. Efficient circuit verification methods

based on the proposed representation will also be developed.

1.2 Background

This section gives the background in switch level model of MOS circuits and circuit
verification methods of VLSI design. The need to have one level lower from the tradi-

tional gate level down to the switch level in digital MOS circuit design is explained.

Three verification methods emphasized at the switch level are introduced: logic simula-

tion, timing verification, and functional verification.

1.2.1 Switch Level Circuit Model

The use of a Boolean gate model to describe the behavior of integrated circuits con-
sisting of MOS transistors has been widely recognized to be quite inadequate [Brya84,
Haye82]. In the Boolean gate model, a circuit consists of a set of logic gates connected
by unidirectional memoryless wires. The logic gates compute Boolean functions of their
input signals and transmit these values along the wires to the inputs of other gates. Each
gate input has a unique signal source. Information is only stored in the feedback paths of
sequential circuits. Some MOS pass transistor networks, however, can implement combi-
national logic in ways that resemble relay contact networks more closely than conven-
tional logic gate networks. Dynamic memories using MOS devices can store information
without feedback paths by using the capacitance of the wires (interconnect region) and
the gates of the transistors attached to them. A variety of bus structures can provide mul—
tidirectional, multipoint communication. Thus, MOS circuits consist of bidirectional
switching elements connected by bidirectional wires. These wires contain memory due
to their interconnect and device capacitances and hence, the MOS circuits cannot be
modeled accurately by the Boolean gate level circuit model. Therefore, researchers have
modeled the MOS circuits at the switch level [Brya84, Haye82], by treating each transis-
tor as a perfect switch, rather than at the gate level. In the switch level model, each node
in the circuit has a discrete capacitance, and each transistor in the circuit has a discrete

resistance. Those discrete values determine the signal strength in the circuit.

Since VLSI circuits are mainly composed of MOS transistors, many designs have to
be performed at the switch level. Traditional digital design methods at the gate level must
be adjusted to handle the switch level designs. Furthermore, new methods and tools for

switch level circuit design have been emerging. These switch level methods, especially

for verification purposes, have received much attention because of their successful uses

in VLSI circuit design.

1.2.2 Circuit Verification

In the design of a VLSI circuit, circuit synthesis and circuit verification are two
important steps in completing a successful design. Synthesis is the process of imple-
menting the circuit based on a number of design specifications. After the circuit is
designed, it is necessary to make sure that the circuit does meet the design requirements.
Thus, a process called verification is required to verify the design. This verification pro-
cess includes a functional correctness check and a performance constraint check. The
functional correctness check is usually accomplished by logic simulation or functional
verification. The performance constraint check is usually done by timing verification.
We will introduce these verification methods with emphasis on switch level circuits. If
these verification methods shows that a circuit does not meet the design specification, the
circuit must be resigned and the verification process repeated. The iteration of the syn-
thesis and verification will continue until the design requirements are satisfied. A

diagram showing a typical VLSI design flow is given in Figure 1.1.

1.2.2.1 Switch Level Logic Simulation

Several logic simulators have been implemented based on switch level models
[Brya80, BaTr80, Brya84]. These simulators are able to simulate a large variety of MOS
designs, including ones containing huge transistors. The simulators accept logic values
for the inputs of the circuit and observe the expected logic values at the outputs of the

circuit. If the outputs are not as expected, then the design is incorrect.

Based on the switch level models, most research on switch level simulation has
focused on finding efficient algorithms to compute the steady state logic values of cir-

cuits. Usually these algorithms use some form of iterative method [Brya84]. These

~

1

Synthesis
according to
specification

 

 

 

 

 

 

'c .
sill}? ation Functional correctness

Functional checking
venficatron

 

 

 

 

 

Timing Circuit performance
verification

checking

 

 

 

  

No

 

 

   

Specification

Redesign satisfied?

  
  

Design is done

Figure 1.1 Flow of VLSI circuit design

simulators try to determine all the steady state logic values for every node in the circuit.
It is not necessary to evaluate all the nodes in the circuit, however. It is sufficient to
evaluate the logic values of some important nodes such as output nodes, thereby reducing

the simulation time.

1.2.2.2 Timing Verification

Timing verifiers identify the longest delay path (critical path) in a circuit in order to

ensure that timing requirements can be satisfied. Timing verifiers also try to improve the

circuit performance and to ensure that the clock cycles are correct [Oust85, Joup87a].
Timing verification is more like electrical-rule checking because its essential function is
to traverse the circuit network. For every input and output signal, there are many possi-
ble paths in the circuit. Each path consists of a set of network nodes that connect the out-
put of one component in the circuit to the input of another component. If the delay of
each node is first determined and stored, then the verifier’s job consists of recursively
finding the path of worst case delay to every output. An RC tree delay model, which
models the delay of circuit elements with resistance and capacitance [RuPe83], can
quickly approximate most timing. To determine a path delay precisely, many timing
verifiers extract the details of the longest path and then use circuit simulation to evaluate

the timing fully.

There are additional considerations that must be addressed to accurately verify the
delays in a circuit. In the case of MOS transistors, one such problem is their ability to
function bidirectionally. This means that complex subcircuits in the circuit can present an
exponential number of signal paths to the timing verifiers including many false paths.
Since timing verifier Operation focuses on some subset of the circuit, much help is
needed to make it focus correctly. Although intelligent analysis techniques [Joup87b]
are of some help, only the user knows what is correct. Thus, it may be necessary to let
users specify information in the circuit such as wire direction, initial conditions, and
elimination of circuitry from analysis [Oust85]. However, if a circuit representation can
carry enough signal path direction information, then many false paths searched in the
circuit by timing verifiers can be avoided and the time spent for timing verification can

be reduced.

1.2.2.3 Functional Verification

Functional verifiers compare symbolic descriptions of circuit functionality with the

derived behavior of the individual parts of the circuit, also described symbolically

[WuNW87, Brya85, Brya87b]. Although not as widely used as logic simulation, func-
tional verification is a significant analysis technique. When both logic simulation and
functional verification are successfully performed for a design, confidence in the design
is increased.

Each primitive circuit component in a circuit can be described behaviorally in terms
of its inputs, outputs, and internal state. By combining these component descriptions, an
overall circuit behavior is derived that can symbolically represent the Circuit’s function.
The verification consists of comparing this derived behavior with the designer-specified
behavior. The two descriptions should be mathematically equivalent after comparison, in
which case the circuit is successfully verified. The three steps of the functional
verification process are the selection of a behavior representation, the aggregation of
individual behavioral descriptions to form an overall circuit specification, and the com-

parison of derived functionality with specified functionality.

Usually, the circuit behavior consists of equations for the outputs and internal states
of its components. Combining output and state equations is a simple matter of substitu-
tion. The resulting equations are long and complex, but they can be reduced with stan-
dard techniques. The final stage of verification compares the aggregated behavior with
the designer-specified behavior. This involves showing equivalence between two sets of

equations, which can be done in a number of ways.

To efficiently derive the behavior from the MOS circuit, the circuit representation
itself must provide signal flow information. The derivation is especially difficult for
MOS circuits because the bidirectionality and high impedance state of MOS transistors
are not easy to handle. Therefore, a good circuit representation which carries signal flow
information is necessary for efficient functional verification. This can be achieved by the

proposed circuit representation.

:E-mq

1.3 Previous Work

Based on the proposed SLICE representation, this research proposes verification
methods which are important in circuit verification. The first method to be presented is
the functionality extraction from circuit connectivity. This method derives the Boolean
expressions of a circuit from a given circuit connectivity such as circuit layout. Previous
work [Brya87, WuNW87, HaSa83] has developed functionality extraction methods for
switch level networks. The work of [WuNW87] does not present a general algorithm to
extract the functionality of transistor groups in a MOS circuit. Nor can it handle high

impedance state or do the electrical checking in the circuits.

State encoding [Brya87] and path encoding [HaSa83] approaches are used to per-
form functionality extraction. The method proposed in this research is a rule-based
approach driven by the signal flow analysis. Since the number of rules employed is small,
the proposed approach is simple and effective. When applying the proposed rules, the
NP-complete Boolean equivalence problem is encountered in the functionality extraction
of transistor groups. We propose the junction node concept to greatly reduce the time
complexity of Boolean equivalence checking. The work in [Brya87] proposes an elegant
method which has polynomial time complexity to extract the functionality of transistor
groups, and does not encounter Boolean equivalence problems. However, because the
state encoding is used, this extraction cannot distinguish uncertain logic states from
unsafe uncertain logic states. If a logic state is an indeterminate logic level, say U, then
U is usually assumed to be a safe uncertain logic state which is either logic 1 or logic 0.
Then, the extraction process can still proceed. However, it is possible that U may be an
unsafe uncertain logic level between logic 1 and logic 0. The proposed method is able to
detect this kind of unsafe uncertain logic level, which may be caused by a design error

such as a short circuit.

Another feature of our approach is that it enables electrical rule checking to be per-

formed at the same time as the processing of functionality extraction. Thus, much work

10

in electrical rule checking which usually is a separate process in circuit verification can
be done along with the functionality extraction process. Furthermore, the work in
[Brys87, HaSa83] considers only the functionality extraction of transistor groups of a cir-
cuit, with no consideration of functionality aggregation among transistor groups. This is
because they are only interested in the logic simulation of a circuit and not the func-
tionality extraction of a circuit. At present, our approach can be applied to all static
MOS circuits, but only to some dynamic circuits. More work is needed to extend it to

general dynamic MOS circuits.

The next method proposed in this work addresses the problem of timing
verification. It is known that in some MOS circuits timing verifiers cannot identify the
correct signal flow direction in the circuit. Therefore, false critical paths may be reported
[Oust85, Joup87a]. Several methods have been proposed to derive the correct signal flow
direction of all the transistors in the MOS circuits. One solution requires users to tag
with direction flags [Oust85] all unidirectional pass transistors whose directions are
difficult to determine. Obviously, this approach involves error-prone user input. Another
approach tries to derive the correct signal flow direction through a set of rules [Joup87b].
However, the sizable number of the rules complicates the application. In this work, a
method to find the correct signal paths of MOS transistors in timing verification is pm
posed. A signal path searching scheme based On SLICE and signal direction finding for
MOS transistors will be presented. The proposed method takes into account information
which is usually ignored by timing verifiers. Thus, it is possible to identify correct signal
flow directions and eliminate false paths for the problematic circuits during timing

verification.

A switch level logic simulator [BaTr80, Brya84] is usually slower than a gate level
logic simulator because the logic values of many more nodes in the circuits must be
determined at the switch level. Therefore, if a switch level logic simulator evaluates only

the logic values of those nodes which it is interested in and ignores the logic values of the

11

other nodes in the circuit, then the total simulation time can be reduced. This is because
extra simulation time will not be spent for those nodes which are uninteresting. When
performing logic simulation on the circuit represented in SLICE, only the logic values of
interesting nodes are considered. Therefore, the proposed logic simulation method based

on SLICE can result in a faster simulator.

1.4 Overview of the Dissertation

A digital MOS circuit is a network composed of transistors and nodes. Therefore,
there is a natural way to express the transistor network structure in terms of a graph
model. A graph representation of MOS circuits will be introduced in Chapter 2. A circuit
representation, namely structured logical circuit expression (SLICE), is proposed to
represent both structural and functional properties of MOS circuits. Once a SLICE of a
circuit is available, the Boolean behavior of the circuit can be derived. The derivation of

Boolean equations of a circuit expressed in SLICE representation will be presented.

Rules for extracting the Boolean equations of the different design styles of a circuit
in SLICE will be presented in Chapter 3. To ensure that the circuit being extracted is
electrically safe, an approach is introduced to verify that the underlying circuit is safe.

The extraction of the general design style of static MOS circuits will also be examined.

Algorithms using the rules in Chapter 3 to extract the functionality of a transistor
group are proposed in Chapter 4. First, the algorithm to extract the circuits which can be
represented by directed acyclic graphs is exploited. Then the algorithm to extract the cir-
cuits represented by general directed graphs is developed. After the functionalities of all
the subcircuits in a circuit are obtained, methods for detenrrining the final aggregated

functionality of the circuit will be presented.

The manner of performing timing verification for the circuits expressed in SLICE

will be investigated in Chapter 5. A method to identify the correct signal flow direction

tr:-

12

within a transistor group during timing verification are proposed. Furthermore, a heuristic
to accelerate this process is presented. In Chapter 6, logic simulation at the switch level

for the circuits in SLICE representation will be demonstrated.

A closing chapter will summarize the contribution of this research to the technique
of MOS circuit verification. Finally, directions are suggested for future research in this

area.

Chapter 2

MOS Circuit Representation

 

2.1 Introduction

In this chapter, the digital MOS circuit (or simply MOS circuit) model employed in
this work is defined. An undirected graph representation to represent the MOS circuit
interconnection will be discussed. A directed graph representation to describe the func-
tional behavior of MOS circuits will also be presented. An expression, namely Struc-
tured LogIcal Circuit Expression (SLICE), to represent the connectivity and functionality
of MOS circuits will be introduced based on the directed graph representation. A method
to obtain the circuit functionality from a SLICE will be demonstrated after the introduc-
tion of SLICE. It is important to point out that SLICE may be used as a design represen-
tation and the designers themselves can specify the SLICE for the circuits being
designed. However, it is also important to derive the SLICE from structural information
such as circuit layout, and then compare the derived SLICE with the one specified by the

designers to verify the correctness of the design.

2.2 M08 Circuit Model and Its Representation at the Switch Level

A MOS circuit (2(N, T) is a transistor network consisting of a number of intercon-

nected MOS transistors including pMOS transistors and nMOS transistors. T is the set of

13

14

MOS transistors in the circuit, and N is the set of nodes which interconnect MOS transis-
tors. Each transistor has three terminals (nodes): source, drain, and gate. Source and
drain terminals are called data terminals. In the switch level model of MOS circuits, a
pMOS (nMOS) transistor is closed, or conducting, if the logic level of its gate terminal is
O (1). When a transistor is conducting, the signal at one data terminal will pass through
the transistor and reach the other data terminal. Thus, a channel is formed between two
data terminals. On the Other hand, a pMOS (nMOS) transistor is open, or not conducting,
if the logic level of its gate terminal is 1 (0). In this case, the two corresponding data ter-
rrrinals are disconnected. The transistors in the switch level model act like bidirectional

switches so that a signal may pass between their two data terminals in either directions.

Many properties in a MOS circuit can be revealed by identifying different types of
nodes in the circuit. In a MOS circuit, we define the nodes which are important in the

transistor network.
Definition 2.1: The following nodes in N of a MOS circuit Q(N, T) are defined.
(1) An exteer node is Vdd (l), V” (0), or a node to which an external signal can be
applied.
(2) All other nodes besides external nodes are internal nodes.
(3) A gate node is a node which is a gate terminal of one or more transistors.
(4) If a node is both an internal node and a gate node, it is called an internal gate node.

[1

Note that an external node accepts any external signal applied to a transistor net-

work. Note also that the "output" node referred in the network is never an external node.

When performing logic simulation, or functionality extraction, we want to know the
states of each node in the circuit. ln a MOS circuit, there are possible states in each node

of the circuit. We define different states in the MOS circuit as follows:

E“‘m‘tl

15

Definition 2.2:

(1) Logic 1 state ( logic 0 state ) of a node in a MOS circuit is obtained from the signal
coming from V44 (1) ( V” (0)). or external nodes which provide 1 (0), through a

sequence of conducting transistors.

(2) If both states of logic 1 and logic 0 cannot occur at a node, then the state of this

node is high impedance

(3) If both logic 1 state and logic 0 state can exist at the same node at the same time,

then the state of this node is unsafe.

A node is called an unsafe node if an unsafe state can occur at this node. Otherwise
it is a safe node. The four states defined in the above can handle static MOS circuit
design (which is defined below) and can be easily extended to cover general static MOS
circuits which allow a signal to be weakened by transistors in the circuit. We now for-
mally introduce a class of MOS circuits, namely static MOS circuits. Static MOS cir-

cuits are the main circuits dealt with in this research. We have the following definition:

Definition 2.3: A MOS circuit is a static MOS circuit if it obeys the following two

constraints:

1. Only four possible states are allowed in the nodes of the MOS circuit. The set of
states is { 1, 0, A, U} which corresponds to logic 1, logic 0, high impedance, and

unsafe, respectively.

2. It is not allowed in the MOS circuit that a high impedance state is applied to a gate

node.

From the above definition, high impedance state can appear at data terminal nodes,
but not at gate terminal nodes. For greater clarity, we will express the MOS circuit in

terms Of a mathematical structure. In the following subsection, we will use graph

16

structure to present our concepts.

2.2.1 Graph Representation of MOS Circuits

Our ideas can be more easily explained if the transistor network being discussed is
viewed as an undirected graph. Actually, it is natural to think of a MOS circuit as an
undirected graph. We have the following definition:

Definition 2.4: A MOS.circuit Q(N, T) can be viewed as an undirected graph
G (V, E) called channel graph, where each vertex v in V(G) has a one-to-one correspon-

dence to a node in N, and each edge e in E (G) a transistor in T [Brya84, RaTr87].
Cl

We can easily define different types of vertices in the channel graph from the

corresponding MOS circuit.

Definition 2.5: In a channel graph G(V, E), the following vertices in V(G) are
defined.

(1) A vertex is an external vertex if it is an external node in the MOS circuit.

(2) A vertex is an internal vertex if it is an internal node in the MOS circuit.

(3) A vertex is a gate vertex if it is a gate node in the MOS circuit.

(4) A vertex is an internal gate vertex if it is an internal gate node in the MOS circuit.
CI

Note, for the sake of convenience, when referring to a graph, vertex and node will
be used interchangeably. For the circuit in Figure 2.1 (a), nodes a, b, O, and 1 are exter-
nal nodes. Nodes a, z and b are gate nodes. Node 2, g, and f are internal nodes. Nodes z

is an intemal gate node.

It is quite natural to partition a MOS circuit into a number of subcircuits so that in

each of subcircuits, all the transistors are channel-connected through internal nodes

i; rm

17

[Brya84, RaTr87]. For the transistor network partitioning purpose, it must be ensured
that external vertices, if they are data terminal nodes of some transistors in the circuit,
have vertex degree 1. Therefore, these external vertices must be replicated in the channel
graph as needed. We define the induced channel graph as the graph obtained after par-
tioning the channel graph.

Definition 2.6: Given a channel graph, a new graph can be obtained if we replicate
all the external vertices, that are data terminal nodes of transistors, such that each exter-
nal vertex has vertex degree 1. The resulting graph after replication is the induced chan-

nel graph of the channel graph [Brya84, RaTr87].
C]

By replicating the external nodes which are data terminal nodes of transistors in the
circuit, we have already performed a partition on the MOS circuit. The MOS circuit is
then partitioned into subcircuits as defined in the following:

Definition 2.7: A MOS circuit can be partitioned into a number of transistor
groups, where each transistor group is a connected component [AhHU83] of its
corresponding induced channel graph. If a connected component in an induced channel
graph contains only a vertex, then it is a trivial connected component, Otherwise, it is a

non-trivial connected component.
C]

Figure 2.1 (a) shows a simple MOS circuit, and its corresponding graph representa-

tion is shown in Figure 2.1 (b). Obviously, as shown in Figure 2.1 (c), the induced chan-‘

nel graph has four isolated subgraphs after its external vertices are properly replicated.
We will introduce the direction concept for transistors in the circuit. It is natural to use
directed graph representation to describe this concept. In the following subsection, it
shows how we can go from an undirected graph to a directed graph to represent a MOS

circuit.

'E 4932-11-1!

l8

 

a b

,l
a-l ——l b—l

O 0 O
(a) MOS circuit

 

 

(b) Corresponding channel graph representation

./\.

(c) Four connected components in induced channel graph

9|

 

(d) LDCCs w.r.t. nodes f and 2

Figure 2.1 Graph representation of 3 M08 circuit

5L . ...-

19

2.2.2 Directed Graph for MOS Circuits

In this section, a directed graph representation is presented to describe the behavior
of MOS circuits. It is necessary to introduce some basics from graph theory before we
proceed. A directed graph with no cycles is called a directed acyclic graph (DAG). A
directed path in a directed graph is a sequence of edges e 1, - ° - ,ek where each edge e,- is
of the form (ug,u,~+1), u; and um are vertices in the graph and 1 Si S k such that every
vertex in the path is distinct. k is the length of the directed path. ul and uk+1 are called
the origin and terminus of the path, respectively, while the vertices u2,u3, ' - - ,uk are its

internal vertices. A directed path is a directed cycle if u1 = uk+1 and k > 1.

A labeled directed graph is a directed graph with a label for each edge in the graph.
An l-path corresponding to a directed path p = < e1, ~ ' - ,ek > in a directed graph is a
sequence of labels < 11, . - - ,I,‘ > where l,- is the label of edge e,- for all 1 Si S k. The
length of an l-path is the length of the corresponding directed path. A product term of an
l-path <11, - ~ - ,lk> is ll ---lk. An l-path or product term is said to disappear if its
corresponding product term can become Boolean 0 after applying Boolean operations on
it by considering each label as a Boolean variable and a product term as a Boolean pro-

duct of Boolean variables.

For any node but external nodes in a transistor group, it is desirable to identify the
functionality of this node, especially an output. node. To determine the functionality of a
particular node in a transistor group, namely the goal node, it is helpful to identify all the
signal paths from the external nodes toward the goal node through a sequence of transis-
tors. Though MOS transistors are physically bidirectional, we may define the direction
of each transistor in the circuit in terms of their signal path directions. This direction of

MOS transistors allows transistors to be unidirectional, bidirectional, or non-directional.

20

Definition 2.8:

(1) The direction of each transistor in a transistor group with respect to a goal node is
defined by all the path directions from the external nodes through a sequence of

transistors toward this goal node.

(2) After all the possible signal path directions are considered with respect to the goal
node, the direction of a transistor in a transistor group may become unidirectional if
all the path directions are from one data terminal to the other data terminal of the
transistor, bidirectional if the paths through the transistor are from either one of the

data terminals to the other, or non-directional if no path goes through this transistor.

Obviously, the direction of a transistor is dependent on the location of the goal
node, the node whose functionality is to be extracted. Thus, no external node can be a
goal node. Usually the goal node is a gate node or an output node to be observed. If it is

a gate node, it is normally the gate terminal of transistors in other transistor groups.

We have defined the direction of each transistor in a transistor group with respect to
a goal node. Thus, we can now define a directed graph for each connected component in

an induced channel graph.

Definition 2.9: A directed connected component ( DCC ) with respect to a goal
node is a directed graph which is the nontrivial connected component of an induced
channel graph with directed edges. The direction of each edge with respect to goal node
in the DCC is the same as the corresponding transistor direction in the transistor group
with respect to the same goal node. If an edge in the connected component corresponds
to a bidirectional transistor, a new edge will be added in parallel to the original edge and

these two edges are of different directions.

Cl

...

$4.1

21

The gate terminal signal of each transistor in the circuit controls the on and off of
the transistor. Thus, signal names of gate nodes are important. We now have the follow-
in g definition:

Definition 2.10: Labeled DC C (LDCC) of a transistor group is a DCC with labeled
edges, where the labels are the signal names of the gate nodes for n-type transistors

corresponding to these edges, or the negation of the signal names for p-type transistors.
[3

Note that the signal name of the gate node of a transistor may be either an external
input signal name (input variable name) or an internal gate node name. Two special
external signal names are 1 (V44) and 0 (V5,). In the example of Figure 2.1, to find out
the functionality of node f, the Boolean behavior of node 2 must be known. Thus, 2 is the
goal node in its group. All the transistor directions are detenrrined by the signal path
traversed, starting from external nodes to node 2. Similarly, the transistor directions with
respect to node f, which is a goal node in its group, can be determined. Figure 2.1 (d) is a
directed graph with labels. It has two LDCCs and shows the directions of transistors with
respect to the goal nodes f and z, iespectively. In the corresponding induced channel
graph of a transistor network, the external nodes all have node degree 1 or O. The goal
nodes and gate nodes in channel graph G can be identified from the original transistor

network 9.

To determine the direction of the transistors with respect to a given goal node, all
the signal paths from the external nodes toward the goal node must be found. A
pathfinding algorithm based on the depth first search can be utilized to search for these
paths. The search is done until all the signal paths are found. The direction of each

transistor is decided by the direction of the path from the external nodes to the goal node.

Particularly interesting are special nodes called junction nodes. A junction node is

the node which V4,, and V”, "Cm and an input signal, V3, and an input signal, or two input

22

signals, may reach by travelling along two different signal paths. Since the signals of
different logic states may reach junction nodes, the behavior description of junctions
nodes is of importance. Actually, junction nodes play a key role in functionality extrac-
tion as shown in the following chapters. Junction nodes can be formally defined as fol-

lows:

Definition 2.11: Given an LDCC, let two directed paths in this LDCC be p1 = <
e1, - ° ° ,ek > and p2 = <f1, ' - ' ,fi) where e;=(u,-,v,-),1$i$k,f,- =(w,;x,-), lSj Sl,
e,- ¢ fj, and V; =x1. Vertex vk is a junction vertex if u1 and wl are both external vertices
which have different signal names. The corresponding nodes in the transistor network of
junction vertices are called junction nodes. If all the internal vertices in p1 and p2 are
not junction vertices, then p1 and p2 are called the prime paths of junction vertex vk. u1

and wl are the origins of the prime paths.
1]

Note that in the above definition, vertex vk is also a junction vertex if u 1 is either an
external vertex or a junction vertex, which has a different signal name from wl, where
wl is either an external vertex or a junction vertex. The following example shows the
junction nodes in a given LDCC.

Example 2.1: An LDCC is shown w.r.t. node f as shown in Figure 2.2. 1, 0, a, b,

and c are external input signals. The nodes n5, n7, nm and um are junction nodes by the

definition, since different logic states may reach these nodes. The prime paths are

<(n1,n3),(n3,n5)>, <(n2.n3).(n3.ns)>, <(n4,n5)>, <(n5,n7)>. <(n6.n7)>.

(017," 3),(ng,n 12)>, <(Ilq,n 10>, <(n11,n10)>, and <(n10,n12)>.

C]

'F‘ ....____q

23

 

O 0
"1 O 0'12
\ / 1
n3 0\ /0 n4
0 Oils
"5 \ /
b
:70
/O<————O n“

f
Figure 2.2 LDCC w.r.t. node f

2.3 SLICE Representation and Boolean Equation of MOS Circuits

Functional information from the circuit allows us to understand the behavior of the
circuit. Thus, if we could have a circuit representation which carries not only the struc—
tural but also functional information of the circuit, then we would have a better under-
standing of the circuit behavior and an accurate knowledge of the functionality of the cir-
cuit. This kind of representation can be used as a circuit design representation since it
describes both circuit connecrivity and functionality. When transistor direction informa-
tion is available in a MOS circuit, functional information can be obtained from the cir—
cuit. Since designers have the transistor direction of the circuit in mind, they can add this

knowledge to a design representation if there is a representation that can accommodate

24

this information. In this section, a circuit representation is proposed which can provide
circuit information for both connectivity and functionality. The derivation of the func-

tionality of the circuit from this representation is presented.

2.3.1 SLICE Representation

Once all the transistor directions of a group have been decided with respect to a goal
node, all non-extemal nodes can be described in terms of their neighboring nodes and
neighboring transistors. Thus, a Structured LogIcal Circuit Expression (SLICE), which
expresses both circuit connectivity and signal flow direction, is proposed to represent

each internal node in the circuit.

Definition 2.12: Given the LDCC of a transistor group with respect to a goal node,
the Structured Loglcal Circuit Expression (SLICE) of an internal node 2 in this LDCC is
defined as

m "j
Ez=2((flgjt)dj) (2.1)
j=1 i=1
"i
where 1'1 g j,- is the product term of <gj1, - . ° , g W >, the l-path of a directed path starting

i=1
from node j and ending at node 2. Nodes j are origins of the directed path. n,- is the

length of the l-path. d j is the signal name of nOde j, and m is the in-degree of node 2.
D

The SLICE of a node 2 is self-defined if one g j,- in (2.1) is the signal name or the
negation of the signal name of node 2. We will pay special attention to those circuits
with self-defined SLICE in Chapter 3. Furthermore, for simplicity of notation, z is used
instead of E2 for a node z’s SLICE in (2.1) as shown below. Also, we may use signal

name d,- in (2.1) to refer to a node j for the sake of convenience.

 

25

Since each edge of a LDCC corresponds to a transistor, attributes of each transistor
may be associated with each edge in the LDCC, and thus with each label in the SLICE.
Those attributes which may be useful for verification purposes include a transistor’s type,
size, gate terminal node label, or identifying name. Similarly, the attributes related to
each node in the circuit may be associated with the vertex in the LDCC. Those attributes
may include the state of the node, node types as defined in Definition 2.1, or the capaci-
tance of the node.

Note that this definition of SLICE is from an LDCC which has signal flow direction
information. However, this direction information may be specified by the designer who
designs the circuit. Thus, the definition of SLICE can also be used for the circuit in which
signal flow information is already known. From this point of view, SLICE can be used as
a design representation to represent a design in which both structural and functional
information are embedded. From the definition, we know that the SLICE of a transistor
group depends on the location of the goal nodes as shown in the following example.

Example 2.2: According to (2.1), for the circuit shown in Figure 2.3 (a), we have

SLICEs (for nodes f and g, respectively.

From the LDCC with respect to node f shown in Figure 2.3 (b), we have the SLICE
of node f

f = a0 + b0 + 551
From the LDCC with respect to node g shown in Figure 2.3 (c), we have the SLICE
of node g
g =ba0+bb0+iil =Ea0+51
Note thatfand g are used instead of Ef and E8.

E3

26

 

a
g
b f
a 4% b 44
0 O
(a) MOS circuit

 

(b) LDCC w.r.t. node f

 

(c) LDCC w.r.t. node g
Figure 2.3 M08 circuit and its LDCCs

Once we have the SLICE of a transistor group, we can derive from it the functional
behavior of the group. The next subsection describes how to obtain the corresponding

Boolean equations from a given SLICE.

27

2.3.2 Boolean Equation of MOS Circuits

Given the SLICE expression of an internal node, Boolean equations of this node can
be obtained according to its SLICE. These Boolean equations characterize the functional-
ity of this node. Since high impedance state is allowed in M08 circuits, it is necessary to
have three Boolean equations instead of only one to characterize the functionality of the
node under discussion. For the node dj in a given SLICE of a MOS circuit, three Boolean
equations (dj)l, (dj)0, and “1% are defined at this node for Boolean logic 1, Boolean

logic 0, and Boolean logic A, respectively. The value of Boolean equation “91 becomes

logic 1 only when logic 1 state occurs at this node. Its value is logic 0 when no logic 1

state occurs at this node. Similarly, Boolean equation (dj)0 and BOolean equation (dj)A

are defined for logic 0 state and high impedance state, respectively.

Definition 2.13: Given a SLICE of a node 2 in (2.1), the three corresponding

Boolean equations are defined as

21= 2: angina-)1) (2.2)
j=1 i=1

20 = )3 (( 1i g,-.- ) (4,)0) (2.3)
j=1 i=1

ZA=H ( Z] §;+(d,-)A) (2.4)
j=1 i=1

Boolean logic 1 equation 21 is defined by all possible signal paths starting from.
logic 1 state of each node (1,, and Boolean logic 0 equation 20 is defined by those paths
starting from logic 0 State of each node dj. Boolean logic A equation 2A is used to indi-
cate that a node is in high impedance state. Whenever there is no conducting path from
external nodes to a particular node, then this node is in high impedance state. Note that

in the following discussion, it is assumed that all external inputs are either in logic 1 state

28

or in logic 0 state, but not allowed in high impedance state. The following examples

show how to derive the corresponding Boolean equations when a SLICE is given.

Example 2.3: We want to determine Boolean equations of nodes f and g in the
Example 2.2. Since (1)1 = 1, (1)0 = O, (0)1 = O, and (0)0 = 1, and it is also assumed, as
mentioned before, that no high impedance state can occur at external nodes 0 and 1, i.e.

(1),; = O, (0)4 = 0. thus from (2.2)-(2.4), we have
13:55 f0=a+b fA=(a+b)Eb=O
81=a 80:30 gA=a(b+E)=ab.

Note that the SLICE of node g is based on the transistor direction with respect to g. Thus,

node g may be in high impedance state if a is in logic 0, and b logic 1.
1:]

Example 2.4: Find the Boolean equations of node f in Figure 2.4 if Boolean equa-
tions of both nodes m and n are given. If m1, mg, mg, n1, no, and nA are known, then
from (2.2)-(2.4), we have

f1 =(ab)m1 +(cd)n1
fo=(ab )mo+(cd)no

A=(E+E.+MA)(C+E+HA).

Similarly, if more signals reach node f in the above example, similar formulae can
be derived. For static MOS circuits with self-defined SLICEs, the derivation of the
corresponding Boolean equations may not be straightforward as shown in (2.2)-(2.4).
However, it is still possible to derive the Boolean equations for them. This will be

demonstrated in the next chapter.

We have explained how to derive Boolean equations from a SLICE. However, it

Still needs further investigation to see if the derived equations can indeed correctly

29

m n
b -l d -l
a -+ c -l
f
(a) MOS circuit

 

(b) LDCC w.r.t. node f
Figure 2.4 M08 circuit and its LDCC

represent the circuit. In the following Chapter 3, rules are proposed to examine the
correctness of the Boolean equations derived from a SLICE. These rules also assist in

deriving the Boolean equations of different circuit design styles.

Chapter 3

Extraction Rules

 

3.1 Introduction

Formal verification through Boolean comparison is a useful technique to verify the
functional correctness of a circuit. This method compares the Boolean behavior
extracted from the circuit layout with the behavior from the design specification to deter-
mine whether both are equivalent. However, because of the bidirectionality and high
impedance state of MOS transistors, the Boolean behavior extraction method used in

traditional logic gate design cannot be adequately applied to VLSI MOS circuits.

An efficient functionality extraction method for static MOS circuit and some
dynamic circuits based on SLICE representation will be presented. Several verification
rules are proposed to extract the Boolean behavior of MOS transistor circuits through a
fast guiding algorithm. Section 2 will present the condition to verify whether the nodes
in the circuit are electrically safe. The rules to do the extraction are demonstrated in Sec-
tion 3, 4, and 5, while the extraction algorithm is presented in the next chapter. In this
proposed approach, a transistor circuit is first partitioned into a number of transistor
groups, where each transistor group is an isolated connected component of the
corresponding induced channel graph. The Boolean behavior of each group is then

extracted. The whole circuit behavior can be obtained by aggregating the behavior of all

30

31

the individual groups. The whole verification scheme is shown in Figure 3.1. This work

deals with the first three processes of Figure 3.1, circuit partitioning, functionality extrac-

tion, and functionality aggregation. The last functionality comparison process is not con-

sidered here and can be found in [OTOO86, WeSa86].

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Specified Transistor circuit
functionality to be verified
Circuit
mutioning
Transistor Transistor . . . Transistor
grow group 8’0“?
. . . Functionality
extraction
Extracted Extracted Extracted
functionality functionali functionality
° ° ° Functionality
aggregation
Derived
functionality
Functionality
comparison
pared m eon...

Figure 3.1 A functional verification scheme

3.2 Electrical Property Consideration

To extract the functionality of a circuit, it is desirable to guarantee that there is not

only no functional error but also no electrical error ( i.e., no unsafe nodes ). Thus, some

electrical rule checking is needed to uncover electrical errors. First we have the follow-

ing lemma.

Lemma 3.1: Given the SLICE of a node f, and the corresponding Boolean equa-

tions f1 andf0.Iff1f0 = 0, then this node is safe.

32

Proof: Since f1 f0 = O, logic 1 and logic 0 cannot reach node f at the same time.

Thus, node f is safe.
E]

The following theorem can help examine the safe nodes in a transistor group.

Theorem 3.1: Given the SLICE of a node f, f = foo +f11, if all the product terms
do not disappear and m = fl, where f0, f1, and fA are Boolean logic 1, Boolean
logic 0, and Boolean logic A equations of node fs SLICE, respecfively, then all the
nodes present in fs SLICE are safe.

Cl

Proof: Because M: f1 at node f, logic 1 and logic 0 will not reach node f.
This implies f1 f0 = 0. Hence, node f is safe. Suppose that there exists an unsafe node,
say node x, present in f s SLICE. Since this node is unsafe, both logic 1 and logic 0 may
reach this x node at some moment. Because no product term disappears, there is a path
from node x to node f. Thus, the unsafe state of node x may reach node f through this

path. Hence node f is unsafe, and a contradiction.
[I]

This theorem shows that if the safe condition is satisfied for a portion of a circuit,
then this partial circuit is safe. However, if the condition is not satisfied, then this partial

circuit may or may not be safe.

Example 3.1 We want to check if the circuit in Figure 3.2 is safe. The SLICE of

node c is

c=bl+ba1+b50

Since, c0 = Cl and no product term disappears, thus the whole circuit is safe.

33

1 O
a —i t— E
1
b -t +— E
c
Figure 3.2 Safe circuit

 

 

El
Example 3.2: Is the circuit in Figure 3.3 safe?
3 _
04:51 ’1
a g Tl;
J.
It] a b
1 r 1
1 _Tl'_Zl_‘l; f
b
1 1
0 LIT—II;
E b
.L J.
1 M
Figure 3.3 Unsafe circuit
The SLICE of node f is

f=b51+ba0+ bal +Eb0+551
=b'a'1+ba()+ bal +1351
= (b5 + ba + film + (ba)0

=f11+f00

34

Although fo- = fl, one product term disappears in f. Thus, the safe condition is not
satisfied, and the nodes in the circuit cannot be guaranteed to be safe. Actually, an electr-

ical short may occur at node g.
C]

Example 3.3: The circuit in Figure 3.4 has two groups. The left group is safe
because b=51+a O and b—0=b1. For the other group f=a 1+b0, if we do not
know that b = 5, we may conclude that f is unsafe, since f—o at f1. However, since b = 5,

after substituting b by {—1 , we know that f is safe.

b
O 0

Figure 3.4 Circuit with two transistor groups

From this example, we know that if a group is determined to be safe using internal
signal names, then it is safe. Otherwise, it is necessary to substitute external signal names
for all internal signal names. After substitution if it is still unsafe, then we can draw the

conclusion that this node is really unsafe.
C]

In general, if the internal signal names appear in both of the Boolean equations
being compared, then it is not necessary to do the substitution. However, if only one
equation has some signal names which do not appear in the other equation, then we have

to substitute internal signal names until both equations have all the same signal names.

35

3.3 Rules for Functionality Extraction

Several rules will be proposed to extract different design styles of static MOS cir-
cuits in Section 3.3.1. The way to extract the circuit with a self-defined SLICE will be
explained in Section 3.3.2. In Section 3.3.3, a general extraction rule will be demon-

strated for general static MOS circuits.

3.3.1 Extraction Rules

In some MOS design styles, such as pass transistor logic and transmission gate
design, input signals may be applied to data terminals. Therefore, dj in (2.1) may not be
0 or 1. Some method is needed to transform the SLICE with input signals into another
form which will aid the Boolean equations extraction. The following rule achieves the

transformation.

Rule 1: If the SLICE of a node 2 is ( H x) a and a is either logic 1 or logic 0, then
i

theBooleanequationsofnodeziszo=(1'[x)5,21=(1'Ix)a,zAzzx.
. l. .

I I

C]
Justification: For the node a, we have a1 = a, a0 = 21' and a A = 0. Thus, the above
Boolean equations can be derived from formulas (2.2)-(2.4).

1:]

Example 3.4: Consider in Figure 3.5 the pass transistor logic with two transistors,
where a is an input signal with either logic 1 or logic 0, and f is the output to be

observed.
The SLICE Of node f is f = Eba. Thus, from Rule 1, we have f0 =Eb2i, f1 =Eba, and
fA = C + E.

D

36

b c
J- A
aJ"E___Tl'_f

Figure 3.5 Pass transistor logic design

From Theorem 3.1 in the previous section, the following rule is used to check
whether a node is safe or not, based on the node’s SLICE. Note that it is always assumed

that the external input is either logic 1 or logic 0, but not high impedance state.

Rule 2: Given the SLICE of nodef,f=f00+f11. Iffo +fA =f1, then the nodef
is safe; otherwise, the node f is unsafe. Furthermore, if no product term disappears in f s
SLICE, then all the nodes present inthe SLICE of f are safe. Also, if f A = 0, then one

Boolean equation f1 itself is sufficient to represent the functionality of the node f.
Cl

Justification: Justified from Theorem 3.1.

Note that if f0 = 0, then f1 and f A are used to represent the functionality. Similarly,
if f1 = 0, the functionality is represented by f0 and f A. Rule 2 provides a step by step
way to examine the unsafe nodes in a transistor group. If it is established that the nodes
in a portion of the circuits are safe, then we only need to examine the nodes in the rest of
the circuit. In fact, a lot of fully complementary CMOS structures, such as logic gates,

can be examined by Rule 2, and most of them turn out to be safe without logic A state.

Example 3.5: In Figure 3.6, the circuit is a pass transistor logic, the node f is an

exclusive or function, XOR, where a and b are input signals.

According to Rule 1, we have
f=&+w+m+m

=ba+b5+5b

37

a
b -q
b
b -+ f _
_ a
a
Figure 3.6 XOR circuit

=(ani-Ea1) + (baO+bEl) +(530+ab1)
= (35 +ba)0+ (ba +b2i)l

Thus, f0 = 35 + ba, f1 = ba + bag and fA = (b + a )(E + axb + 5x5 + a) = 0. Since
5: f1 and no product term disappears, from Rule 2 the circuit is safe and f1 itself is

sufficient to represent the functionality of the XOR circuit.
Cl

Also, it can be shown that the circuit in Example 2.2 is safe because i; =f1. and no
product term disappears. Actually, f1 can represent the functionality of a two-input
NAND gate. By applying Rule 2 in a divide-and-conquer fashion, we can determine

whether the whole circuit is safe or not, as demonstrated in the following example.

Example 3.6: In the circuit of Figure 3.7, we want to examine the functionality of

node g, and whether the whole circuit is safe or not.

TI-
hzdfi
0

Figure 3.7 Circuit with logic A state

38

We may consider all the paths reaching g. Thus, we have

g=dba+dcl+dEO

=dba1+db50+dc1+dEO
g1=dba+dc
go=db5+35

gA=(d+b+5)(d+b+a)(d+E)(d+c)=db

 

Because g0 + g A = g 1, node g is safe. From Rule 2 we can draw the conclusion that
the whole circuit is safe. However, if we do go through intermediate nodes f and g, then
we can also answer the question of whether the whole circuit is safe or not. Consider the

SLICEs of nodes f and h first.
f1 = ba f0 = b a fA = 13. Since ETTA-4,, node fis safe.
h1=c ho='c' hA=O. Sincem=h1,nodehissafe.
g1=df1+dh1=dba+dc
g0=df0+2h0=dba+26

gA=(d+fA)(d+hA)=de+dhA+fAhA=db

 

Since g0 + g A = g 1, node g is safe. Thus, the whole circuit is safe and the behavior

of node g is described by g0, g1, and gA.
D

In VLSI circuit design, a design style called pseudo-nMOS logic is used in many
CMOS PLA designs. It uses pull-up transistors to introduce a weakened signal from Vdd-
A pull-up node is never trapped into a high impedance state. It is considered to have
logic 1 unless grounded through other paths. Thus, pseudo-nMOS circuits do not have
high impedance states as found in Other MOS logic structures. In general, if it is allowed

that some attenuated signal can be overridden by the signal coming from other signal

39

sources through gate controlled conducting transistors, then the following rule is
required.

Rule 3: If the SLICE of a node f is f = f0 0 + 1 then the only Boolean equation of
node f is f—o. If f =O+ f1 1 then the only Boolean equation of node f is f1. In both

cases, i; and f1 are the traditional two-valued Boolean equations of node f.
C]

Justification: Suppose f = f0 0 + l . Node f is always logic ,1 if there is no conduct-
ing path from logic 0 (Vss). Therefore, there is no high impedance state. Hence, we do
not need a logic A equation, and only one logic 1 equation is sufficient to represent the
functionality of node f. Since f0 considers all the paths to get logic 0, f0- will consider
all the paths to get logic 1. Thus, the Boolean equation of node f is ft). The second state-

ment of Rule 3 can be similarly justified.
Cl

Note that before applying Rule 3, we must check that the overridden signal has been
attenuated through some transistors. For instance, in the nMOS case, it uses a depletion
pull-up transistor to decay the signal. Since in SLICE representation, transistor attributes,
such as size, can be associated with each transistor, the check can be done before Rule 3
is applied.

Example 3.7: Consider in Figure 3.8 the pseudo-nMOS circuit with a bridging

. transistor.

Since the p-type transistor is always on, f = (ad + be + ace + bed )0 + 1. Thus, the

 

Boolean equation of node f is ad + be + ace + bed.

[I]

40

0-4

a-l t-b

d -l l- e
O 0
Figure 3.8 Pseudo-nMOS circuit

3.3.2 Extraction of Self-defined SLICE

We have not yet considered how to extract the functionality of a circuit whose
SLICE is self-defined. If it is a self-defined SLICE, first, it must be established that the
circuit behavior follows the constraints of a static MOS circuit (SMC) , and then the cir-
cuit behavior can be extracted by the following given theorem. We have the following
lemmas.

Lemma 3.2: If the SLICE of a node 2 in (2.1) is self-defined, and for every j,
j = 1, - - - , m, at least one g j,- is the signal name or negation of the signal name of node

2, then the circuit expressed by this. SLICE is not an SMC.

Cl

Proof: Since at least one gate control of each signal path toward node 2 itself is con-
trolled by node 2, the logic value of node 2 may initially rely on the capacitance of node 2
instead of any signal from external inputs. Thus, since the circuit violates the first con-

straint of an SMC in Definition 2.3, the circuit is not an SMC.

[:1

Lemma 3.2 tells if a node’s output feeds back to some gate controls of all the signal

paths coming toward this node, then the circuit associated with this node is not an SMC.

41

Example 3.8: Given the circuit in Figure 3.9, the corresponding SLICE for node 2

is E2 = 2a + zdb + ezc. From Lemma 3.1, the circuit is not an SMC.

a b c
d—l i-——»

F _._.

Z

 

Figure 3.9 Circuit which is not an SMC

Lemma 3.3: If E2, the SLICE of a node 2 in (2.1), is self-defined, then 2 A must be 0.

Proof: Suppose zA¢ 0, then high impedance state would apply to the gate terminal
node. This violates the second constraint of an SMC in Definition 2.3. Therefore, zA
must be 0.

El .

We now present the following theorem. This theorem derives the Boolean equations
of a circuit that has a self-defi ned SLICE.

Theorem 3.2: If E2 in (2.1) is self-defined, the following procedure can be used to
determine whether the underlying circuit is an SMC and to compute the Boolean equa-

tions of node 2 if it is.

1. Let Sz be the SLICE of node 2 such that

m n;
S,= 2 ((ng,. )dj) such that j¢k,
j=l i=1

g,“- is the signal name of node 2, 1.<_i Snk ,

42

2. IfS, is null then the circuit is not an SMC. Otherwise, compute 21, 20, and 2A from
S,.

3. If the z A from S, is not 0, then the circuit cannot be an SMC. If it is 0 then it is an
SMC; thus substitute g5, which is the signal name of node 2, in E, by 21, and

recompute 21 and 20 from E,. 21 and 20 are the Boolean expressions for node 2.

Proof: In step 1, the product terms in E, that cause a self-defined circuit are elim-
inated from E,, thus the new SLICE is S,. If S, is null, then from Lemma 3.2, we know
that the underlying circuit is nOt an SMC. Otherwise, 21, 20, and z A can be derived from
S,. If 2 A from S, is not 0, then from Lemma 3.3, the circuit represented by 5, cannot be
an SMC, and thus, the underlying circuit represented by E, is not an SMC either. How-
ever, if z A is 0, then we know that the underlying circuit is an SMC from Lemma 3.3.
Therefore, from S,, 21 and 20 can then be derived. Since 2 A is O, 21 itself is the Boolean
behavior which contributes to node 2 through other signal paths except those paths which
cause the transistor group to be self-defined. Thus, after substituting g,“- in E, with 21
obtained from S,, we can derive 21 and 20 from this new E,, 21 and 20 are the Boolean

expressions for node 2.

1]

Example 3.9: The behavior of node f in the circuit of Figure 3.10 is an XOR, and

the Boolean expressions of node g are to be derived.

The SLICE of node g which is self-defined is
E, =51+a0+hba + bdb +bgb
=51+a0+bc7b +bgb
Taking out bgb, we have

Sg=Zil+a0+bZib

43

Figure 3.10 Circuit with self-defined SLICE

=El+a0+b2ibO+bdbl (By Rule 1)
=El+a0

From 5,, we have g1=2i,go =a, gA =0, thus this circuit is an SMC and g =g1=5.

Substitute g by g1 in E g.
Eg=51+a0+b2ib+b5b
E, = 51+ a0

From Rule 2, we know node g is .safe and we have g1 = 21', and g0 = a which are the

Boolean expressions for node 2.

C]

3.4 Generalized Extraction Rule 2

General static MOS circuits allow different strengths of signal paths in the circuits.
The external nodes have the signal with the largest strength. The signals from the exter—
nal nodes may be weakened through conducting transistors, so different strengths Of sig-
nal may appear in a circuit. To extract the Boolean behavior from a circuit having dif-
ferent signal strengths. Theorem 3.1 and Rule 2 need to be generalized to handle the gen-

eral static MOS circuits as shown in the following.

44

Suppose strength 1 is the strongest signal, and strength n the weakest signal where n
is an integer greater than or equal to 1. We say a node is safe in general static MOS cir-
cuits if logic state 1 and logic state 0 of each signal strength i, i = 1, , n, cannot reach

this node at the same time. Otherwise, the node is unsafe.

Let the SLICE of node f be
f=(zti>1+():tii)0 (3.1)
i=1 i=1

where i = 1, , n. f‘, is a Boolean logic 1 equation of signal strength i, where I is either 0

or 1. We have the following lemma to claim the node f is safe.

Lemma 3.4: Given the SLICE of node fin (3.1), if f; ff, :0 for all i = 1, , n,
then the node is safe.

[:1

Proof: Since f1 fl) = 0 for all i = 1, , n, logic 1 and logic 0 of each signal strength

i cannot reach node f at the same time for all possible i. Thus, node f is safe.
El

Let

The definition of F A implies that if there is no conducting paths to node 2 from the exter-
nal nodes, then this node is in high impedance state. Note that the signal with the larger
strength can always override the signal with the lesser strength. Thus, let P 1 (F 0) be the
Boolean logic 1 (0) equation which describes the logic state 1 (0) among different signal

strengths. Now we have the following Theorem.
Generalized Theorem 3.1: Given the SLICE of a node f in (3.1), if all the product

terms do not disappear and F u + FA = F1, then all the nodes present in f’s SLICE are

safe.

45

Proof: Because EFF-A = F 1 at node f, logic 1 and logic 0 will not reach node f.
This implies 1‘} fl) = 0, for all i = 1, ,n. Hence, node f is safe. Suppose that there exists
an unsafe node, say node x, in f s SLICE. Since this node is unsafe, both logic 1 and
logic 0 of some strength i may reach this x node at some moment. Because no product
term disappears, there is a path from node x to node f. Thus, the unsafe state of node x

may reach node f through this path. Hence node f is unsafe, and a contradiction.

CI

Based on the above theorem, Rule 2 in Section 3.3.1 can be generalized to handle

general static MOS circuits.

Generalized Rule 2: Given the SLICE of node f in (3.1), if F 0 + F A = F 1, that is

 

.9, (f1 +ii>+ri=fi

i,j=1, i¢l

 

55 (fi +f6 )+FA=fi.

i,j=1, i¢2

 

i (f1+f6)+FA=fflt
i.j=1, in
then node f is safe; otherwise node f is unsafe. Furthermore, if no product term disap-
pears in fs SLICE, then all the nodes present in the SLICE of f are safe. Also, if FA = 0,
then the one Boolean equation F 1 itself is sufficient to represent the functionality of the
node f.
C]

Justification: Justified from Generalized Theorem 3.1.

46

Note that when n is l, the Generalized Theorem 3.1 and Generalized Rule 2 degen-

erate to Theorem 3.1, and Rule 2, respectively.

3.5 Extraction of Dynamic Circuits

It has been shown that the static MOS circuits can be extracted to obtain their
Boolean behavior. This has not yet been shown for dynamic circuits. In this section, a
rule for dynamic circuit design style is presented. However, it still will not be considered
for general dynamic circuits. General dynamic circuits allow nodes with different capaci-
tances. Thus, they may have different node strengths in each node. In the following rule,
however, the Boolean behavior of dynamic circuits is realized by the recognition of the

circuit pattern.

Rule 4: Let the SLICE of node 2 be 2 = q) 1 + g<|> 0, where 4) is a clock input, node 2
has a bigger capacitance value than other nodes in the group, and g is a Boolean expres-

sion. Then the Boolean equation for node 2 is 21 = g, 20 = g, and z A = 0.
D

Justification: If it is known that (l) is a clock input, and final SLICE for node 2 can
be simplified to the form as shown in Rule 4, then the circuit is a dynamic circuit. This is
clear from the fact that the circuit pattern is a dynamic circuit design style. When (it is O,
the node 2 is charged to logic 1. While O is 1, the node 2 may remain logic 1 due to node
capacitance or become logic 0 through a conducting path from ground. Thus, high
impedance state can never happen in node 2, and the Boolean equation 20 is g, and 21 is
g.

El

Example 3.10: The circuit in Figure 3.11 is a dynamic NOR gate.

47

Figure 3.11 Dynamic NOR gate

The SLICE of node 2 is$1+a¢0+b¢0= 81+(a+b)¢0. From Rule 4, we

have 21 = (a + b) which is truly a NOR gate.
Cl

Several rules have been proposed to extract the Boolean behavior of different
design styles of MOS circuits. The circuit class considered is static MOS circuits plus
some dynamic circuits. Furthermore, the electrical safe property of a node being
extracted in the circuit is examined. In reality, the Generalized Rule 2 will not be applied
Often, and it is mainly of theoretical interest. Therefore, it is usually sufficient to extract
the circuits with every proposed rule except Generalized Rule 2. These rules are used by
a complete algorithm for extracting the functionality of a complex transistor group. This

extraction algorithm will be introduced in the following chapter.

Chapter 4

Functionality Extraction Procedure

 

4.1 Functionality Extraction Algorithm for a Transistor Group

In the previous chapter, several rules to extract the Boolean behavior of a transistor
group are presented. An extraction algorithm which guides the application of these rules
is presented in this chapter. Two things must be taken into consideration during the
extraction. First, we must make the extraction process efficient and second, we should be

able to locate the error region whenpxtraction fails due to design errors.

For the first consideration, the most important thing is to try to reduce the time com—
plexity of the Boolean comparison which may be encountered in the application of Rule
2. The BoOlean comparison is known to be an NP-hard problem [GaJo79]. Thus, to per-
form the Boolean comparison in a practical way, the number of variables in the Boolean
expression cannot be large. Usually the number of variables involved in a transistor
group, or a DCC, is small, thus the Boolean comparison complexity cannot dominate the
whole extraction process. However, for most DCCs this complexity can be further
reduced done by extracrion through junction nodes. In this way, the problem of Boolean
comparison can be broken down to several smaller subproblems. Thus, the number of
Boolean variables involved in each subproblem becomes smaller, and the whole func-

tionality extraction process can be expedited.

48

49

Through junction nodes, incorrect design also can be uncovered and located. Since
only in these nodes can improper Boolean behavior occur, if we can make sure all the
junction nodes in a DCC are safe, then the transistor group being verified is safe. Thus,
design errors can be easily identified and located by examining the junction nodes in the
transistor group. Therefore, through junction nodes, our two concerns regarding extrac-
tion can be addressed. The following example gives us an intuitive feeling for why junc-

tion nodes can assist in the extraction process.

Example 4.1: Consider the following circuit with transmission gates. The transis-
tors in the transmission gates are indexed 1 through 4 to distinguish different transistor

instances.

 

 

11
b Flint
1 _
e cc
0 1 3,
a-i I r45
e geb-I t-c
o
r—d
0

Figure 4.1 Circuit demonstrating divide-and-conquer verification approach

g =e_12il +551+e3Ebl+e3dl+e4Ebl+e4d1
+ Zao + Z2110 + e3bd0 + e3cd0+ (:4de +e4cd0
=(ZE+eEb+ed)l+(Ea+ebd+ecd)0

g1=(55+eEb+ed)
go=(Za+ebd+ecd)

gA=(e+a)(E+c+b)(E+d)(e+5)(E+B+Z)(Z+E+E)=o

50

The functionality of node g is (E E + eEb +ed ). Since there is no disappearing
product term, the whole circuit is safe. However, the above approach is not a good one
because many paths and signal inputs need to be considered. Hence the Boolean com-
parison complexity is high when applying Rule 2. Also, it may not be easy to identify an
error region in the circuit if a design error exists or the circuit is unsafe. A better

approach is to use a divide-and-conquer approach.

The better way is to make use of the junction nodes f and h. Consider node f first.
f=El +a0. Thus, f0 = a, f1=5, and fA =at'i=0. Therefore, m=fh so the
functionality of node f is E and it is a safe subcircuit. For node h,
h=Ebl+dl+bd0+ch. Thus, h0=bd+cd, h,=EE+Ft, and
hA = ( 5+2 )(E+Z )( b +c )d =0. Therefore, Mal, and the functionality of
node h is b? + d and the subcircuit is safe. Finally, consider node g.
g = e_1f + e_2f + e3h + e4h. After applying Rule 1 and Rule 2, we can find out the func-
tionality of node g which is Ef + eh, and node g is safe. By substituting f and h, we get
g = ( E H + ec'b + ed ), and the whole circuit is safe. Thus, the Boolean comparison com-
plexity involved has been reduced through the junction nodes when deriving the Boolean

behavior of node g through junction nodes f and h.
C]

We will first present the extraction algorithm for DCCs which are directed acyclic
graphs (DAG) [AhHU74]. Then, an extraction algorithm for general DCCs which allow
directed cyclic graphs will be proposed. Usually, the DCCs of most circuits are DAGs.
Before giving the algorithm, we will show that only the junction nodes in the DCC need

examining to guarantee that the whole circuit is safe. We have the following theorem.

Theorem 4.1: If all the junction nodes in a DCC are safe, then all the nodes in the

DCC are safe.

51

Proof: The signal which reaches a non-junction node in the circuit must come
through junction nodes or external nodes. Thus, since the signal from a junction node is
safe and only one signal can reach the non-junction node from a junction node or an

external node, this non-junction node is safe. Hence, all the nodes are safe.

Cl

4.1.1 Functionality Extraction for Circuits with DAG

The following algorithm FunctionalityExtraction (Algorithm 4.1) is presented to
extract the functionality of a specific goal node g in a given transistor group which is a
DAG. Before the functionality of the goal node g is extracted, all the transistor directions

with respect to this goal node must be determined.

Once the direction of each transistor is determined, then the proposed algorithm can
be put to work. If the underlying DCC is a DAG then the algorithm FunctionalilyEx-
traction can be used. The following theorem helps us decide whether a DCC is a DAG or

not.

Theorem 4.2: If all the transistors are unidirectional in a transistor group, then the

corresponding directed connected component is a DAG. Otherwise it is not a DAG.
Cl

Proof: Suppose the corresponding directed connected component is not a DAG and
there is a directed cycle in the DCC. Let us consider a directed cycle consisting of two
edges. Since these two nodes can reach each other, the transistor corresponding to the
edges between these two nodes is a bidirectional transistor. This contradicts the assump-

tion that all the transistors are unidirectional.

Cl

52

Algorithm 4.1: FunctionalityExtraction /* for circuits with directed acyclic graph */
l
Jr—{g}; /* g is the goal node, J is the set of current junction nodes */
S(—{ all the external data terminal nodes ];
repeat
for (each s in S) do
j = SearchJuncNode(s);
/* find a junction node j from starting node 3 */
J<-J+{j};
end for;
for (each j in J) do
JNje—{ }; /* Initialize JNj, each junction node j has an associated set JNj */
end for;
for (each s in S) do
j = LocateJuncNode(s);
/* Locate the closest junction node j starting from node 3 */
Jth—JNJ-Hs}
/* JNj is used to keep all the starting nodes s whose junction
node is j when calling LocateJuncNode(s) */
SearchAllPaths(s,j);
/* Find all the paths from node s to node j */
end for;
JJ(-—J; J<—{ }; S <—{ }; /* JJ now is the set of current junction nodes */
for (each j in 1!) do
if (Dependo) = TRUE)
then /* Node j has no predecessor junction node */
if (Extracto') = TRUE)
/* Try to extract the Boolean equations of node j */
then /* Successfully extracted */
S (——S+{ j};
else
Print(Extraction fails for node j);
end if;
else
J(—J+{ j l; /* Node j cannot be extracted because it has a predecessor
junction node. Put node j back to J. */
Se—S+JNJ-; /* Put starting nodes in JNj which is associated
with node j back to S */
end if;
end for;
until (g is not in J);
/* the Boolean behavior of g is extracted */

1

Figure 4.2 Algorithm to perform functionality extraction of circuits with DAG

53

In this extraction algorithm, the time spent on the Boolean behavior extraCtion for a
group of transistors is mainly for Rule 2 application. In order to reduce the extraction
time, the number of variables involved in the Boolean comparison of Rule 2 application
must be reduced. This may be achieved by extracting the junction nodes earlier than
extracting the goal node. The order of extraction of different junction nodes is important.
A junction node cannot be extracted if it has a predecessor junction node which has not
been extracted in the DAG. Since this junction node extraction depends on the signal
path coming from its predecessor, the predecessor must be extracted prior to this junction
node. Thus, for all the junction nodes, there is a precedence relationship among them,
and a junction node precedence graph (JNPG) can be used to describe the extraction

order.

The procedure SearchJuncNode(s) searches for a goal node g starting from a node
s. This procedure returns a found node if a junction node or the node g is found. After
the first for-loop, all the junction nodes with respect to node g may not be found. How-
ever, all the junction nodes eventually will be identified after iterations of repeat-until
loops. The procedure LocateJun'cNode(s) tries to locate a junction node which is
clOsest to a node 3 and then return this node. The procedure SearchAllPaths(s,j), start-

ing from a node s, searches all paths that end with a junction node j.

Procedure Dependo') decides whether a junction node j has any predecessor junc-
tion node which has not been extracted. If the node j does have an unextracted prede-
cessor junction node, then it cannot be extracted until all its predecessor junction nodes
are extracted. After all signal paths toward a junction node j are obtained, the rules
presented in the previous chapter try to derive the corresponding Boolean behavior for
this node j. In the procedure ExtractU), when either a junction node or an external node
is encountered, Rule 1 is applied to perform the transformation. If a junction node is
found with one path conneCting to V4,, or V,, through an attenuated transistor, Rule 3 is

applied to the extract junction node; otherwise, if without attenuated transistor, Rule 2 is

54

applied. The above procedure is repeated until the goal node g is extracted.

The procedure SearchJuncNode plays a key role in Algorithm 4.1. The detailed
algorithm (Algorithm 4.2) for this procedure is shown below.

Algorithm 4.2 SearchJuncNode /* Search a junction node j starting from a node s *l
/* Before the first call of this algorithm every external node has a signal
associated with it */
/* Initially, internal nodes do not have any signal associated with them */
1
t = DFS(s); /* Depth first search for a next node t which is a neighboring
node of a node 3 */
while (t at g) /* g is the goal node */
if ( t in J )
then
retum([ D; /* t is a junction node already
identified, return nothing */
else
if (SameSignaI(t,s))
then
retum([ D; /* Nodes tand s are of the same signal,
return nothing */
else
if (DifferentSignal(t,s)) /* Nodes t and s are of
different signals */
then
retum(j); /* Find a new junction node j */
else
Sig na|(t) = s; /* Node t is never reached
by UPS before */
/* Set signal of node t to s */
t = DFS(t); /* Keep searching for
next neighboring node from t */
endif
endif
endif
endwhile

Figure 4.3 Algorithm to search for junction nodes

55

Algorithm 4.2 SearchJuncNode is the main procedure in Algorithm 4.1. It uses a
depth first search algorithm to search for a next neighboring node from the current node,
and tries to determine whether this neighboring node is an already identified junction
node, a new junction node, a node never searched before, or a node of the same signal as
the current node. Whenever the neighboring node is not an identified junction node, if its
signal is the same as that of the current node, it is not a junction node. Otherwise, if they
are of different signals, a new junction node is identified, or a node never searched before
is encountered and the depth first search is continued until the goal node g is reached.
Note that the order of junction nodes being discovered depends on the calling sequence

of Algorithm 4.2 which is shown in the following example.

Example 4.1: This example demonstrates Algorithm 4.1 and Algorithm 4.2. The
DCC shown in Figure 4.4 (a) has a goal node g.

Before the first repeat-until loop in Algorithm 4.1, J = {n11}, S = {n1, n2, n3, n7,
n9}. During the first iteration of the repeat-until loop Of Algorithm 4.1, Algorithm 4.2 is
called several times in the first for-loop. Nodes n4 and n11 would be identified as junc-
tion nodes after calling SearchJuncNode after the first repeat-until loop. However,
node us may or may not be identified as a junction node after the first repeat-until loop,
depending on the calling sequence of node s in SearchJuncNode (s). For instance, if
the nOde order is n3, n1, n2 when calling SearchJuncNode in Algorithm 4.1, then node
n 5 is not identified as a junction node and node n4 is. Nevertheless, for another node
order n3, n2, n1, both nodes n5 and n4 can be identified as junction nodes because both
nodes are reached with different signals. No matter. what the node order is, all the junc~

tion nodes eventually can be identified after several iterations of repeat-until loop.

In this example, at most, three repeat-until loops are needed to identify all the junc-
tion nodes and extract their functionality. Suppose junction nodes n4, n5 are identified in
the first repeat-until loop, and we have J = [ n4, n5, n 11 }. The LocateJuncNode tries to

locate the closest junction node for each node in S set. The closest junction node for node

56

 

(a) DCC w.r.t. node g

 

 

(b) Corresponding J NPG of the DCC
Figure 4.4 DCC and its JNPG

n1 or n2 is n4. The closest junction node for node n3 is n5, and for node n7 or no, it is
n11. In the first repeat-until loop, only junction node n4 can be extracted since it is the
only node without predecessor in the JNPG ishown. This can be checked through pro-
cedure Depend. The signal paths toward n4 can be decided by SearchAllPaths, and
they are < (n1,n4) > and < (n2, n4) >. Before starting the second repeat-until loop, we
now have J = {n5, n11], S = {n4, n3, n7, no] if the extraction of node n4 is successful.
Since node n5 precedes node n11 in the JNPG, junction node n5, which is the closest
junction node for nodes n4 and n3, can be extracted during the second repeat-until loop.
The paths found toward node n5 in SearchAllPaths are < (n4,n5) > and < (n3,n6),
(n6,n5) >. In the beginning of the third repeat-until loop, suppose node n 5 is successfully

extracted, then J = {n11}, S = {n5, n7, n9}. Node n11, which is the goal node, is

57

extracted in this iteration.

C]

It can be shown that all the junction nodes in the DAG can be identified and exam-
ined by the SearchJuncNode called in Algorithm 4.1. Thus, the electrical property of a
DCC can also be verified along with the Boolean behavior extraction. The following

theorem shows this.

Theorem 4.3: The Algorithm 4.1 FunctionalityExtraction can identify all the junc-

tion nodes in a given DCC.
Cl

Proof: Initially in Algorithm 4.1, J, which is the junction node set, contains only g,
the goal node, and set S consists of all the external nodes. In thefirst repeat-until loop,
the junction nodes, which are created because of different signals from the external
nodes, can be identified by the procedure SearchJuncNode. From the second repeat-
until loop on, S set contains junction nodes, which have been successfully extracted, and
external nodes which have not yet contributed to create a junction node in the previous
repeat-until loop. Of course, J set contains the node g and junction nodes which are
newly found or are not successfully extracted in the previous repeat-until loop due to the
violation of the junction node precedence relation. The repeat-until loop is repeated until

junction node g in J is successfully extracted.

From the definition of junction node, we know that the signal of a junction node
comes either from external nodes or from junction nodes. Therefore, the way to find
junction nodes in the repeat-until loop satisfies the definition of junction node. Since the
underlying transistor group is a DAG, the path from each external node or each junction
node toward the goal node is uniquely determined and only one such path is possible.
Thus, whenever each junction node is identified, the way to find all the possible signal

paths entering this junction node is uniquely determined and there is no other way to get

58

these signal paths. Hence, through Algorithm 4.1, all the junction nodes in the transistor

group can be identified.
El

Example 4.2: Consider the following MOS circuit of a transistor group, the goal
node is z. This circuit uses many design styles including pass transistor, transmission
gate, pseudo-nMOS, and complementary CMOS. The precedence graph of the junction

nodes is also shown.

Initially, J=[z} and S is the set of all the external nodes which are data terminals. In
the first iteration of the repeat-until loop, we may have J=[A, B, C, D, k, z }. Note that
node k may appear in either the first or the second iteration of the repeat-until loop
depending on the junction node finding algorithm SearchJuncNode. By applying Rule

2, the respective functionalities of node A and node C are

11:55 C=rrqp+ur§p+rp

Both node A and node C are safe. By applying Rule 3, we have

 

B=(cd+fg+ceg+fed)
The functionality of node D is extracted and found to be safe by applying Rule 1 and
Rule2. D =e+m n
At the end of the first repeat-until iteration, we obtain J={k, z} and
S={A, B, C, D, F, G, j}. Since k has predecessors in the junction node precedence
graph, node k cannot be extracted in the first iteration. In the second iteration of the
repeat-until loop, we can extract the node k, which is the predecessor junction node of
node 2, by applying Rule 1 and Rule 2.

k=(xyA+§yB+x§C+f§D)
Node k is safe, J becomes {2}, and S is (k, F, G, j }. In the third iteration, the goal node

2 is extracted and safe by applying Rule 1 and Rule 2. Thus 2 =ik + i j k +ij-I

:i
jifggtw
Q

P

{-1

M

hm:>or:|:;:(DJ-d

C

i
i

new i

l V-ltJFF-‘vl

f

 

 

ix.

‘<H
N-l

 

:14

0

5%

1

 

View

.l-x‘fE‘
I.
X

 

(a) Circuit with many design styles

 

(b) Corresponding JNPG

Figure 4.5 Circuit to be extracted

It is important to analyze Algorithm 4.1 so that the time complexity of this algo-
rithm can be fully understood. We first examine each procedure called inside Algorithm
4.1. Considering the procedure SearchJuncNode, from Algorithm 4.2 we know that its
worst case complexity is bounded by the longest path length from an external node
toward the goal node. Procedure LocateJuncNode is still bounded by the longest path
length in the worst case since it tries to locate the closest junction node along a path, on
which there may be more than one junction node, toward the goal node. The procedure
SearchAllPaths searches for all the paths between two nodes. It is theoretically possible
that an exponential number of paths may occur between two nodes in a DCC. However,
in reality, for almost all circuits, the number of paths tends to be small if only a portion of

DCC is considered each time.

The procedure Depend examines whether a junction node has a predecessor junc-
tion node. This can be done by traveling from each junction node found toward the goal
node. If during the traveling, a junction node is passed by, then this passed-by junction
node cannot be extracted. Therefore, the time complexity for this procedure is bounded
by the longest path length and the number of junction nodes in the current junction node
set J. As mentioned, the computation time of the procedure Extract is mainly spent in
Rule 2. However, by the extraction of junction nodes in a divide-and-conquer fashion,

the time spent in the Boolean comparison may be significantly reduced.

When Algorithm 4.1 is finished, each of the procedures SearchJunCNode,
LocateJuncNode, and SearchAllPaths is called 0 (n) times in the worst case, where n
is the number of nodes in the circuit. The procedure Extract is called i times in the worst
case where i is the number of junction nodes in the circuit, while the procedure Depend
is called 0 (i) times in the worst case. Thus, we know that the time complexity in Algo-
rithm 4.1 is dominated by the procedures Extract and SearchAllPaths. However,

through the junction nodes, the time spent in both procedures can be greatly reduced,

61

since each time only a portion of a DCC is considered.

4.1.2 Functionality Extraction for General Circuits

If a DCC contains cycles because of bidirectional transistors, then this DCC is not a
DAG. We will present an algorithm to handle DCCs which are directed cyclic graphs.
This algorithm is based on the Algorithm 4.1 and relies on finding strongly connected
components [AhHU74] of directed cyclic graphs. A strongly connected component
(SCC) [AhHU74] of a directed graph is a maximal set of vertices in which there is a path
from any one vertex in the set to any other vertex in the set. By finding out the SCCs of a
DCC, it is possible to obtained a new DAG called pseudo DAG (PDAG) which is the ori-
ginal DCC with some of its SCCs replaced by a node called pseudo nodes. The follow-

ing algorithm is used to extract the functionality of a DCC having cycles.

Algorithm 4.3: FunctionalityExtraction /* for a general directed graph */

1.Find all the SCCs for the given DCC and construct its PDAG. The algorithm to find
SCCs can be found in [AhHU74].

2.If different signals enter a certain SCC, then all the nodes in this SCC are junction
nodes, and this SCC stands as a pseudo junction node in the corresponding PDAG.
Otherwise, this SCC is just a pseudo node in the PDAG.

3.Use the Algorithm 4.1 FunctionalityExtraction to perform the functionality extrac-
tion on this PDAG.

4.When extracting the pseudo junction node, first identify the junction nodes in the
pseudo junction node, if any, which leave for other nodes outside the pseudo junc-
tion node. Then all the signal paths toward these junction nodes from the paths
entering this pseudo junction node must be figured out. Thus the functionality of

these junction nodes can be derived.

Figure 4.6 Algorithm for the functionality extraction of a general directed graph

62

Note that the time complexity to find SCCs in a DCC is O(max(n,e)) where n is the
number of nodes in DCC, and e the number of edges [AhHU74]. Therefore, the intro-
duction of SCC does not significantly increase complexity in Algorithm 4.3. Also, note
that extra time is needed to do the path searching in step 4 of Algorithm 4.3. As men-
tioned, path searching may encounter numerous paths. However, in practice, the number

of paths is limited.

Example 4.3: In the circuit of Figure 4.7, there are two bidirectional transistors with

gate terminals d and e.

 

 

 

 

(b) Corresponding DCC (c) PDAG

Figure 4.7 Circuit with cycles in its DCC

63

In the corresponding DCC, an SCC consisting of nodes A, B, and C can be
identified. The corresponding PDAG is shown and node P is the pseudo junction node in
this PDAG. From the PDAG the SLICE of node g can be derived. Nodes A and B in the
SCC (pseudo junction node) are leaving for node g which is the only node that can be
reached from the SCC. Thus, all the signals entering nodes A and B outside the SCC
have to be discovered. We have A = a0 + deb 1, and B = b1 + eda 0, Also, g = cA +fB.

Hence, the Boolean equations of node g can be determined.

C]

4.2 Functionality Aggregation

After the functionality extraction of each transistor group is done, the final func-
tionality of the whole circuit can be derived by the aggregation of the individual Boolean

behavior of each transistor group.

4.2.1 Aggregating Functionalities of Groups

Most of the aggregation may be achieved through the substitution of the Boolean
equations of extracted transistor groups. To do this substitution, we have to understand
the relationships among the groups. These relationships can be revealed through the
input-output relationships among transistor groups. These input-output relationships are
reflected in the gate inputs of gate nodes. If the output of one transistor group is the input
of the gate node of another transistor group, then we say that the former transistor group
precedes the latter one. Thus, we can define a directed graph called transistor group pre-
cedence graph (TGPG), where each vertex in TGPG is a transistor group. A directed
edge is defined from u to v. if u and v are vertices of TGPG and u precedes v. From this
TGPG, the order of aggregation by substitution among transistor groups can be deter-

mined. We may use techniques such as topological sort [AhHU83] to decide the order of

aggregation.

However, we may encounter feedback loops which presents the sequential behavior
of the circuits. Thus, in the corresponding TGPG, directed cycles may certainly occur.
For a TGPG with cycles, we may first try to find the strongly connected components
(SCCs) of a TGPG. We can then try to identify the sequential behavior of each SCC
found. Some sequential behavior, such as RS-latch, may not be properly reflected by a
Boolean expression derivation. Extra knowledge about some sequential circuit proper-
ties may be needed during the functionality aggregation to correctly identify circuit
behavior. Once all the SCCs are found and replaced by new vertices representing these
SCCs in the TGPG, the appropriate order of aggregation by substitution can be per-
formed using topological sort to obtain the overall circuit functionality. However, for
still other circuits, we need to explore more properties among different transistor groups
to determine their Boolean behavior. Usually this comes from different circuit design
styles, and more rules may be required to recognize these styles. In the following subsec-

tion, this kind of circuits will be discussed.

If an input to a uansistor group coming from another group is described by only a
single Boolean equation of Boolean logic 1, the aggregation by substitution is straightfor-
ward. It may be considered as a design error for static MOS circuits when the input is a
Boolean logic A equation. However, if the input contains a Boolean logic 1 or O equa-
tion, as well as a Boolean logic A equation, then we may use the Boolean logic 1 equa-
tion to continue the substitution and also to properly reflect a design error warning mes-
sage. Another way is to use another state, called unknown state, to represent the input
and to continue the substitution. However, this method will generate a number of
unknown states, so that the final aggregated Boolean equations may not be useful for

functionality comparison.

The following example shows how to obtain an aggregated functionality by substi-

tution.

65

Example 4.4: Figure 4.8 shows a circuits at both the switch level and gate level,

respectively.

 

 

 

(c) Corresponding TGPG

Figure 4.8 Circuit demonstrating functionality aggregation

66

The circuit has four transistor groups and the corresponding TGPG is also given.
For each group, the Boolean behavior is extracted respectively as D = C, C = AB, A =
a + b, and B = E. The order of aggregating the Boolean behavior is determined by the

precedence in the TGPG. We can see that gate 3 must be substituted before gate 4 is pro-

 

cessed. We first have to substitute C = A? = (a + b) E. Then the second substitution is D

 

 

 

= C, so D = (a + b) E = (a + b) E, which is the final aggregated Boolean behavior.

C]

Example 4.5: The circuit in Figure 4.9 is a CMOS D flip-flop, a memory element.
The functionality of node q is to be found.

11 11
3-4 ‘1’ b-d
q p
¢-* *-¢
Z—t l-d
00 00

(a) CMOS D flip-flop

~0-
(b) Corresponding TGPG

Figure 4.9 Aggregated circuit

This circuit has two transistor groups. The corresponding TGPG has a cycle, so the

circuit has sequential behavior. Once the logic function of each group is recognized, in

 

this case q = 4) d + p and p = 4) d + q, we can recognize the function of the binary storage

67

cell by substituting one signal name and making the other a function of time. Thus, we

 

have 4 = 4) d +p = ( 6 + d)13. Therefore, we obtain

can=(i+d)<¢d+q.>=$q.+d¢.

Example 4.6: The circuit of RS-latch is shown in Figure 4.10.

 

l 1
44
R AP S'fiQ
—t4 Hi —ii s-tl
0 0 O 0
(a)RS-latch

(b) Corresponding TGPG

 

 

 

 

 

Figure 4.10 Circuit needs extra knowledge when aggregating

 

There are two transistor groups. The outputs of each group are P = Q + R, and Q =

P + S, respectively. However, the output of Q is not simply obtained by substitution to

 

get Q,“ = (Q, + R) + S, which is obviously not the Boolean behavior we are familiar
with for RS-latch. Thus, more knowledge is needed during aggregation to identify the

behavior of some sequential circuits.

D

 

68

4.2.2 Extraction Rule Among Groups

Some MOS design styles may be defined within different transistor groups. During
the functionality aggregation, some other rules may be needed to uncover those styles
and to derive the Boolean behavior of each style from the relationships among transistor
groups.

There is a tightly coupled design style called DCVS logic [HGDT84], which can be
identified by recognizing the relationship between two different transistor groups. There-
fore, some extra rule is required to find this special relationship among transistor groups
after the functionality extraction of each group is done. The DCVS design is achieved by
converting all p-type transistors of a fully complementary CMOS gate to n-type transis-
tors and by adding two cross-coupled p-type transistors. It is always possible to obtain
both true and false values of the original logic function. The following rule identifies two

transistor groups which use DCVS design style.

Rule 4: Let a SCC from a TGPG consist of only two transistor groups, and let the
output nodes of these groups be x and y, respectively. Given the SLICEs of node x and y,
ifx =y'1-t-f0, y =fl+g0, andf=§, thenx =17, andy =§ =f.

Cl

Justification: Since f = g, the conducting paths from V3, to nodes x and y comple-
ment each other. Thus, nodes x and y cannot both have logic 0 at the same time. How-
ever, whenever one node gets logic 0, say node x, the other node y will get a logic 1
because node x turns on the p transistor connecting node y and V4,. Therefore, the

Boolean expressions of nodes x and y are complementary, and x = f, y = f.

Cl

Example 4.7: Consider in Figure 4.11 the DCVS logic with two transistor groups
whose TGPG is a directed cycle. SLICEs of nodes x and y, respectively, are

x=y1+ab0

 

69

 

(a) Circuit using DCVS logic

(b) Corresponding TGPG
Figure 4.11 Circuit with DCVS design style

y=il+(5+b)0

SinceE+b=cfii ,wehavex=a_b=5+bandy=5+b=a b.

In general, if still other design styles are defined among different transistor groups,
more rules will be required to describe each style. During the final functionality aggrega-

tion phase, these rules then have to be applied to derive the final functionality.

4.3 Conclusion

A functionalin extraction method for static MOS circuits and part of dynamic MOS
circuits has been proposed. From the signal flow point of view, the approach can unify
the functionality extraction of different design styles. Rules are presented to extract the

Boolean behavior as well as to perform electrical safety checking at certain special

 

70

nodes, namely junction nodes. An algorithm is introduced to identify these special nodes
and guide the rules for performing the functionality extraction. The extraction process is
fast, because the number of rules is small and they are only applied to a small portion of
a transistor group each time. Furthermore, it is easy to locate the design error, because
the error region is confined to a small region by the algorithm during extraction. The
final overall functionality of the circuit can be obtained by transistor group aggregation.
Extra knowledge may be required during the aggregation to understand the behavior of
some circuits which cannot be well represented by Boolean expressions such as RS-latch.
Moreover, more rules may be needed for design styles which are defined within different

transistor, groups.

Most of this method has been implemented in C language. Since the algorithm tries
to derive the functionality of a group in a divide-and-conquer fashion, the time required
for applying rules and finding signal paths is insignificant. The functionality extraction
time in the experiment is shown in Table 4.1. Most of the extraction time is spent in
applying Rule 2. This rule has to perform Boolean comparison, and the performance may

be improved by using better comparison heuristics.

 

 

 

 

 

 

 

 

 

circuits no. of extraction
transistors time (secs)
alul l 10 0.7
cnt3 130 0.5
onepulse 186 0.8
LFSR 428 2.2
rcgtrs 672 3.6
alu8 2280 12.0

 

 

 

 

Table 4.1: Extraction time for different circuits on SUN3/280

Chapter 5

Signal Flow Analysis in Timing Verification

 

5.1 Introduction

As pointed out before, the SLICE can be used as a design representation. The circuit
designers may use SLICEs to represent and describe both the circuit connectivity and
signal flow direction of MOS circuits being designed. SLICE representation is better
than traditional graph-based representation such as transistor net lists, since graph-based
representation provides only connectivity information but no functional information such
as signal flow direction. In Section 5.2, we demonstrate how to perform tinting
verification for the circuits expressed in SLICE. In the subsequent sections, we apply the
SLICE representation and junction node concept to the false path problem which occurs
in a transistor group during timing verification. An algorithm to derive the correct signal
paths is presented first, and then a heuristic is proposed to accelerate the correct signal

path finding process.

5.2 Timing Verification on SLICE Representation

In this section we demonstrate the ability of SLICE to efficiently perform timing
verification of MOS circuits. A number of circuit simulation programs such as SPICE

[Nage75], have been developed to measure the timing performance of integrated circuits.

71

 

72

These programs give a more accurate result, but they are very time consuming. Thus,
they are impractical for today’s VLSI circuits which may contain hundreds of thousands
of transistors. The switch level model is then proposed to estimate the circuit perfor-
mance, which is much faster, but at the expense of less accuracy [Joup87a, Oust85]. The
switch level model considers each transistor in the circuit as a perfect switch with a cer-
tain value of resistance, and each node in the circuit associated with a certain value of
capacitance. The resistance and capacitance of a circuit is usually estimated by the cir-
cuit designer before the actual layout is performed. The timing estimation of the circuit
can then be easily computed based on the given RC information [RuPe83, Oust85]. A
more accurate tinting measurement can be obtained by feeding back more accurate RC
information after the circuit layout is done. Obviously, timing analysis at the switch
level is an important step in the circuit design, and, thus, an appropriate switch level cir-

cuit representation is essential to the efficiency of the timing verification process.

To perform timing verification at the switch level, the representation of a MOS cir—
cuit schematic should provide both the circuit connectivity and the signal flow informa-
tion needed to calculate the circuit delay time [Joup87a, Joup87a, Oust85]. Path
enumeration and critical path analysis on a circuit schematic are two basic procedures
involved in the timing verification process. These procedures are required to identify the
signal flow direction of transistors and to extract the circuit stages of the circuit being
verified. Since some fixed logic values of circuit inputs are allowed in timing verification,
the timing verifier should have the ability to handle logic simulation [Hitc82, Joup87b,

Oust85].

In timing verification, the path enumeration technique tries to find all the possible
signal paths in the circuit. It starts from the output and traces back until an input is
reached. Now consider a MOS circuit represented by a set of SLICEs. Given an output
node, say node 2, we try to find all paths coming from external inputs to the node 2. First,

find the SLICE, in the form of (2.1), of the current node 2. For the right hand side of this

 

73

expression, if node d, in (2.1) is a junction node, then (ii is in the path. Otherwise, d,- is
an external node and the corresponding nodes of the gate terminal nodes of g j,- in (2.1)
are in the path. This procedure is repeatedly applied to each newly found node on the

possible paths until the external input nodes are reached.

Let us consider the example in Figure 5.1.

 

g
e.#:rh i
33 Di 3

 

3 f

(a) Gate level network

 

 

 

 

 

 

0

(b) Circuit schematic

Figure 5.1 Schematic of a CMOS circuit and its corresponding gate level network

74

For instance, the SLICEs of the four nodes in Figure 5.1 are

i=hf1+h0+f0 (5.1)
h=ge (5.2)
e=51+bl+ab0 (5.3)
f=El+dl+cd0 (5.4)

The above four expressions completely specify the signal flow and connectivity of the
circuit shown in Figure 5.1. The primary output node i, expressed in (5.1), is defined in
terms of h. Then, we have h in terms of e, and e in terms of a and b which are external
input nodes. Two paths (a,e,h,i) and (b,e,h,i) are then obtained. Two other paths from

nodes c and d through f to i can be similarly found.

For critical path analysis, one has to start from some external inputs at a given
instant. Then one has to follow certain paths until an output node is reached. During this
path following process, the timing delay along each stage is recorded and updated. Thus,
the time instance at which the output node is reached from the worst case path delay can

be obtained.

Based on the SLICE representation, the critical path can be found as follows. First,
find a SLICE which has external input signals specified on its right hand side. Then cal-
culate the delay for the left hand side node of this SLICE, and record the delay time for
this node. Considering this left hand side node as an input, we have to repeat this pro—
cedure until the desired output node is reached. Thus, the delay time for a path from
external inputs to an observed output node can be obtained. However, this path may not
be the critical path. We have to consider all possible SLICEs which are affected by the
external input signals. Then, the path with the longest delay time is the critical path.
Apparently, the critical path finding described above is a depth first search with the long-

est delay time pruning [Oust85].

 

75

In the example of Figure 5.1, we want to measure the delay at output i. We begin
applying input signals at a and b. We start from (5.3) because a and b are in (5.3). Since
the left hand side of (5.3) is in (5.2), we proceed to (5.2), and then to (5.1) in which we

want to measure the delay time for node i.

In tinting verification, before the delay is calculated, we have to extract and identify
stages which are usually logic gates in the transistor network. Once all stages have been
extracted, the delay time of each stage can be computed. By summing up the delay times
of different stages, the delay of a signal path is obtained. Note that the SLICE represen—
tation explicitly identifies stages in terms of junction nodes or gate nodes. If a graph-
based circuit representation is used, additional effort must be spent to identify the circuit

stages.

The direction of the signal flow in a circuit is important for performing tinting
verification. Again, the graph-based circuit representation provides no signal flow infor-
mation. Let’s examine the example in Figure 5.2 which is a two-bit shifter with two

inputs and two outputs.

 

 

an: in:

56~||:L (MEL;

01 02

 

 

 

 

 

Figure 5.2 2-bit shifter

The SLICE representation for the circuit in Figure 5.2 is shown below.

 

76

ol=ai1+ci2
02=bi1+di2

Note that a and c cannot be logic 1 at the same time, nor can b and d. As demonstrated
in Figure 5.2, the dash path from input i 1 to output 02 may be considered as a possible
path if using graph-based representation. However, this false path never exists in a real
shift register. To avoid finding such a false path, other information is needed besides the
representation of the circuit connectivity. Usually this information is provided by the
designer in terms of signal flow direction. In the SLICE representation, the direction of

signal flow of all transistors is clearly described. Thus, no false path will be derived.

During timing verification, we may also have to perform a case analysis in which
the fixed logic values of some inputs are given. It is then necessary to propagate these
inputs to all possible subsequent stages. Therefore, the tinting verifier should be able to
perform logic simulation when needed. With SLICEs, the switch level simulation can be
done systematically no matter what kind of transistor logic style is employed. The logic
simulation capability of the SLICE representation will be demonstrated in the next

chapter.

5.3 False Signal Path Problems in Timing Verification

Timing verification [Hitch82, Joup87a, Oust85] is a widely used technique to exam-
ine the circuit performance in the VLSI design community. Timing verifiers try to find
the longest propagation delay path (critical path) in the circuit, and check whether it

meets the circuit design requirement.

It is known that for some MOS circuits there are problems for timing verifiers in
identifying the correct signal paths. Therefore, false critical paths may be reported.
There are two kinds of false path problems in timing verification. The first kind occurs in

a general digital network among transistor groups [BrIy88, BMCM87, DuYG89]. The

 

77

other one happens within a transistor group [Joup87b, Oust85]. Both kinds of problems

are caused by a lack of proper functional information during timing verification.

Let us examine the first kind of false path problem. Suppose each gate of the circuit
in Figure 5.3 has unit delay 1. This circuit has three transistor groups. A timing verifier
without considering functional information may report the longest delay of node f as
being three units. However, when c is logic 1, f gets logic 1 after one unit, and when c is
logic 0, f gets logic 0 after two units. Thus, because some gates are always blocked by
signal c, the longest delay is actually two units. Hence, if the functional information such
as gate types and external inputs is not taken into consideration, a timing verifier may

falsely report a path delay which is too pessimistic.

a

. t
c c

Figure 5.3 Circuit with false path problem

For another kind of false path problem, let us take another example. Consider the
multiplexer circuit in Figure 5.4 which itself is a transistor group. We want to know the
longest delay of node g2. The longest delay path may be considered as < b, c, E > or < b,
c, E > which is expressed in terms of l-path. However, this is not true, since these two sig-
nal paths are never activated when considering gate terminal node inputs c and E, which
block paths. The correct delay path of node g 2 actually is , < E > or < a >. Thus, again, if
the functional information of the circuit is not taken into consideration by the timing

verifiers, false signal paths may be reported and result in an incorrect timing estimation.

We will consider the false path problem of the second kind in this research. For this
problem, methods have been proposed to derive the correct signal flow direction of all

the transistors in a transistor group of MOS circuits [Joup87b, Oust85]. One solution

 

78

Figure 5.4 Multiplexer circuit

requires users to tag all the unidirectional pass transistors, which are difficult to handle,
with direction flags [Oust85]. Obviously, this approach involves error-prone user input.
Another approach tries to derive the correct signal flow direction through a set of rules
[Joup87bj. However, since the number of rules is not small, the application of the rules is

complicated.

A method to find the correct signal flow direction of MOS transistors in a transistor
group during timing verification is proposed. The proposed method takes into account
information which is usually ignored by timing verifiers. Thus, it is able to identify the
correct signal flow directions for the problematic circuits during timing verification.
Distinguishing different kinds of nodes in a transistor network and making use of transis-
tor gate terminal node names (functional names) can aid the derivation of signal flow
direction for MOS transistors. Using both transistor network connectivity information
and functional information, a more effective signal flow analysis method is developed for
finding the correct signal flow direction. Although the method is able to find correct sig-
nal paths, it can sometimes encounter time consuming pathfinding To speed up the run-
ning time of pathfinding, a heuristic is proposed to perform the signal path derivation.
This heuristic does not guarantee to obtain all the correct signal paths. However, most of

the time it has been found to work well.

79

5.4 Method to Identify Correct Signal Flow Direction

In this section, a method is proposed to find the correct signal flow direction in tim-
ing verification. When the tinting constraints of a MOS transistor network are to be
verified, the circuit is first partitioned into transistor groups. For each transistor group, the
signal flow direction of each transistor is to be determined. Since signals always flow
from external nodes and are blocked by the goal nodes (either output nodes or gate
nodes), the possible signal paths can be derived from paths starting from external nodes
and ending at the goal nodes. The signal flow direction of each transistor in a transistor
group can be determined by the following procedure. This procedure uses functional

information to eliminate the impossible signal paths.

Algorithm 5.1 Algorithm to eliminate false signal paths in a transistor group
For each goal node in the transistor group

1. Signal flow directions are determined by all the directed signal paths starting from

external nodes and ending at the goal node.

2. Each time a path is found, the product term of the corresponding l-path must be
examined. If it disappears after Boolean simplification, then the direction of the
signal path is set to each transistor until some transistor blocks the signal path.
This signal path is then discarded and not considered. If the signal path does not

disappear, then this path is a valid one.

Note that during Boolean simplification, all the intermediate variables in the gate
product term may need to be replaced by the signal names of the external nodes so that

the Boolean Operation can be fully exploited.

If only the signals from the external nodes are considered to affect signal paths, the

above procedure can guarantee to find the correct signal paths and set the correct signal

 

“HAM " l- I‘-
r-

80

flow direction of each transistor in a group. The time complexity of Algorithm 5.1 is
proportional to the number of signal paths in the transistor group. In the worst case, the
possible signal paths, which usually contain many false paths, may be exponential in the
number of nodes in a transistor group. Still, the correct signal paths can eventually be

determined by using Algorithm 5.1.

Consider the circuit in Figure 5.4. Let the goal node be node g2. The SLICE of g;
is 51 + a0+ Ecb 1 +Ecb0 = 51 + a0. Product terms Feb and Ecb disappear, thus the
corresponding two signal paths never occur. The directions of the transistors with gate
terminal nodes a and b are set, but not the transistor with gate terminal node c. Now let
the goal node be node g 1, and Z" 51 + EaO + cbl + cb0 is the SLICE ofg 1. The four sig-

nal paths in the SLICE are all valid and set the direction of all the transistors accordingly.

Usually timing verifiers do not consider the functional information of the underlying
circuit. Among many signal paths, verifiers use a delay calculator to compute the signal
delay for each path, and then find the longest propagation delay path. This is an expen-
sive way to Obtain the critical path since the delay calculation is costly, and moreover,
the paths found may be incapable of occuning in the actual circuit. However, by using
functional information we can eliminate paths that never occur in the circuits before per-
forming the delay calculation. Therefore, the total computation cost of finding a critical

path can be reduced, and the reporting of false paths can be avoided.

In most circuits, a transistor group has a limited number of correct signal paths.
When many signal paths are reported, especially in a group with multiple goal nodes, it is
very likely that false paths which never occur in the actual circuits are also reported.
Thus, in the case where the number of paths reported exceeds a certain threshold number,
it is believed that false paths may be reported among the superfluous number of paths.
Therefore, we may abort the signal path derivation method of Algorithm 5.1, and instead
use a heuristic method to accelerate the signal path finding process. The heuristic does

not guarantee to find all the correct signal paths, but it speeds up the identification of

81

correct signal paths in most cases. Therefore, the heuristic will not be used unless there
is an indication that false paths may be reported. It would also be better to notify users
that the timing verifier is running the heuristic, so that users may double check the signal
flow direction for themselves. In the following section, a heuristic is proposed to quickly

eliminate false paths in the tinting verification of a transistor group.

5.5 Heuristic to Find Signal Path Direction

The idea behind the proposed heuristic is the observation of the relationships
between external nodes and goal nodes. A signal starts propagating from external nodes
and searches for goal nodes. If a goal node or gate node is reached, it may not be neces-
sary to propagate away from the reached goal node or gate node since the output nodes or
gate nodes seem likely to block the signal paths. Also, when a junction node is formed, it
seems likely to behave as a new signal source. Therefore, an identified junction node may
be treated as a new external node providing a signal source. By using the heuristic, we
may in advance eliminate many impossible signal paths before we use functional infor-

mation to eliminate false paths. The algorithm of the proposed heuristic is as follows.

Algorithm 5.2 Heuristic to find correct signal paths in a transistor group
For each goal node in the transistor group

1. Signal directions are determined by all directed signal paths starting from external

nodes to a goal node.
2. During the search, if a gate node is encountered, then the path searching from the

current external node stops at this gate node. It is not necessary to keep searching

for the goal node. The search continues from the remaining external nodes, if any.

3. During the search, if a junction node is encountered, then the path searching from

the current external node stops at this junction node. It is not necessary to keep

 

82

searching for the goal node. The search continues from the remaining external

nodes, if any.

4. When searching for a particular goal node, if other goal nodes are encountered,
then the path searching from the current external node stops at this goal node.
There is no need to keep on searching for the goal node. The search continues

from the remaining external nodes, if any.

5. If a junction node is identified after the search from all the external nodes is
finished, this junction node can then become a pseudo external node. We treat
each pseudo external node as an external node and repeat steps 1-5. Thus we may

reset the transistor direction which has been previously set.

6. When steps 1-5 can not be applied any more, then we search for all the directed
paths formed by the transistor direction set in steps 1-5. Each time a path is
found, the product term of the corresponding l-path must be examined. If it disap-
pears after Boolean simplification, then the direction of the signal path is set to
each transistor until some transistor blocks the signal path. This signal path is
then discarded-and is not considered. If the signal path does not disappear, then

this path is a valid one.

This heuristic tends to assume that all the transistors in the circuit are unidirectional.
Thus, the heuristic may fail when there are true bidirectional transistors in the circuit. An
exponential number of signal paths may still be encountered in the circuits when steps
1-5 of Algorithm 5.2 are applied. However, if the circuit contains many junction nodes,
goal nodes, or gate nodes, direction of every transistor may be determined by the com-
plexity of the number of transistors in the circuit. This is because the heuristic is likely to
set the direction of each transistor in the circuit as unidirectional. Step 6 evaluates all the
possible paths from the transistor direction determined from steps 15 Though the

number of paths evaluated may still be exponential, it is much less than it would be

83

without using the heuristic.

5.6 Experiments and Discussion

In this section, we will show how to apply the proposed heuristic to different cir-
cuits whose correct signal paths are difficult for tinting verifiers to determine. A thres-
hold value for the number of paths found is used to decide whether the heuristic should
be run or not. A useful guideline is, the more goal nodes in a transistor group, the larger
the threshold value. The heuristic can quickly identify the correct signal paths in most of

the problematic circuits.

Consider the full adder circuit shown in Figure 5.5. There are four transistor groups
in this circuit. The heuristic is applied when the total number of paths exceeds 10, the
threshold value, for the group containing goal nodes e and f. Step 2 is applied when the
heuristic encounters node d which is a gate node. Then consider the node d, which is a
pseudo external node, as an external node. Step 5 is applied. Without the heuristic, node
e or f each has eight signal paths going toward them and three of them are false paths.
These false paths can be eliminated using functional information. However, with the
heuristic the number of signal paths is correctly reduced to five for each node before
functional information is used to eliminate false paths, as shown in the directed group
graph. .

Now let us again examine the barrel shifter circuit. A 3-bit barrel shifter with out-
put nodes 0 1, o 2, and o 3 is shown in Figure 5.6. Without using the heuristic, this circuit
contains too many false paths. However, applying steps 4 and 5 of the heuristic, the
correct signal flow direction is easily obtained as shown in the directed group graph.
Though the heuristic is working in this example, it may have trouble when the three

nodes in the circuit cannot be easily identified as output nodes by the timing verifier.

 

84

 

 

 

h CARRY

 

 

 

 

 

 

 

 

 

 

(a) Full adder circuit

85

 

(b) Path finding without heuristic

 

A
B
e
1
B
Dd
0 B
f4
B
A0

(c) Path finding with heuristic

Figure 5.5 Full adder and its directed group graphs

86

 

 

 

 

 

 

(a) 3-bit barrel shifter circuit

1.

 

i1 01
00

10

i2 02
0. ‘

le

03

 

1'3
00

(b) Directed group graph derived from the heuristic
Figure 5.6 3-bit barrel shifter and its directed group graph

87

 

x3
o 23
163*
12 X3
0 22

 

 

 

 

 

 

 

 

 

 

 

 

1-
xri A Xf‘t‘ B xg—lH.
0 0 0

(a) Tally circuit

(b) Directed group graph derived from the heuristic
Figure 5.7 Tally circuit and its corresponding directed group graph

88

Thus, as can be seen, the success of the heuristic is not guaranteed.

For the circuit shown in Figure 5.7, this tally circuit definitely has many possible
paths. After applying steps 3, 4 and 5 of the heuristic repeatedly, surprisingly, the signal

flow direction can be determined correctly as is shown.

The proposed method only considers the signal flow direction derivation from the
external signal source point of view. For circuits using static design, the proposed
method can find the correct signal flow direction. However, the signal flow direction of a
circuit depends not only on external signal sources, but also on node properties in the cir-
cuit, such as node capacitance. To more precisely identify the correct signal flow direc-
tions, the node properties of the circuit must be considered. For the circuit shown in Fig-
ure 5.8, the transistor with gate terminal node c is determined to have no direction from
the proposed method. However, if the capacitance of nOde C 2 is much greater than that
of node C 1, then the signal flow direction is from node C 2 to node C 1 and that transistor
becomes a unidirectional transistor. Consideration of node capacitance when finding the

correCt signal flow direction is not covered in this work.

 

x Y
he] i Fit—E
“Fl;

C1 C2

Figure 5.8 Circuit with different capacitances at nodes C 1 and C 2

In summary, a method to find the correct signal flow direction of MOS transistors in
tinting verification is presented. Since both the connectivity information and the func-
tional information of transistor networks are considered, this method guarantees to find
all the correct possible signal flow directions in the circuits from the signal flow point of
view. A heuristic is presented to quickly determine signal flow direction. This heuristic
does not ensure that every signal path can be correctly found. However, in most cases, it

facilitates rapid reduction of the false signal paths and faster identification of the conect

signal paths.

89

Chapter 6

Logic Simulation with SLICE

 

6.1 Logic Simulation at the Switch Level

Logic simulation is a commonly used circuit verification method in the VLSI design
community. Logic simulation may be performed at different circuit levels such as the
functional block level, gate level, or switch level. Since SLICE is a circuit representation
at the switch level, it would be necessary to understand how a switch level logic simula-
tion can be performed on the circuits expressed in SLICE. Since SLICE describes both
connectivity and functionality of the circuit being verified, circuit designers may specify
the SLICE representation from the functionality ( i.e., signal flow ) point of view. Thus,
each SLICE represents a functional block partitioned from the original circuit. How to
partition the whole circuit really depends on the designer’s approach. However, each
SLICE is a subcircuit of a transistor group, i.e. it may be a transistor group or a portion of
a transistor group. Because we are only dealing with logic behavior, we are not con-
cerned with the timing behavior of the circuit. We may assume each SLICE expression
has a unit delay. Once we have a set of SLICEs to represent a circuit being implemented,
logic simulation at the switch level may be performed on this set of SLICEs. An event
driven scheme is usually used in logic simulation. Therefore, we may use event driven

simulation among different functional blocks, each of which is a SLICE representation.

90

91

However, our emphasis is not on event driven schemes, which are a common technique,

but on the logic value evaluation of each SLICE during the simulation.

The logic states of four-valued Boolean algebra [Haye82] will be considered first.
These states are sufficient to simulate static MOS circuits with no ratioed logic such as
pseudo nMOS design. The lattice structure which describes four-valued Boolean algebra
is shown in Figure 6.1 (a). Let 1, 0, A and U be the logic levels corresponding to
Boolean logic 1, Boolean logic 0, indeterminate value, and some types of faults (such as
short circuits), respectively. For every SLICE expressed in (2.1), the logic value of the
left hand side node, say node 2, is to be determined. Then when the logic levels of each
signal name in the right hand side of node z’s SLICE are available, the new logic level of
node 2 can be evaluated. Note that only the logic level of the nodes in the left hand side
of a SLIDE needs to be evaluated, and it is not necessary to be concerned with the logic

level of other nodes in the circuit.

6.2. Logic Evaluation of SLICE in Simulation

In this section, we will show how to evaluate the logic level of a node expressed in
SLICE. g,- mentioned in the following is interpreted as the logic level for the gate termi-
nal node of the i-th transistor, and d represents the logic level of a node. The logic level
of g,- denotes the logic level (negation logic level) of a gate terminal node of n-type (p-

type) transistor. Let L = 0, H = l, and Y = U.

The following rules are defined to evaluate the logic level of product terms for a

node 2 in the SLICE of (2.1).

92

 

A
(C)
Figure 6.1 Lattice structures of different logic levels
Rulel: (I'Ig;)d=L ifgi=H foralliandd=L (6.1)
i .

Rule2: (Hg;)d=H if g,-=H foralliandd=H (6.2)
1'
Rule 3: ( [I g,- )d = A if there exists an I such that g: L or d = A(6.3)

Rule 4: ( n g,- )d = Y if there exists an I such that g1: Y or d = Y(6.4)

To evaluate the summation of different logic levels of a node in (2.1), the following rules

are defined. They are based on the lattice structure of four elements in Figure 6.1 (a).

 

93

 

 

Figure 6.2 DCVS XOR/XNOR gate

A+A=A A+1=1 1+0=Y Y+1=Y
A+0=0 0+0=0 Y+Y=Y Y+0=Y

The following example demonstrates the switch level logic simulation on a DCVS
[HGDT84] XOR/XNOR gate. The SLICEs of the circuit shown in Figure 6.2 are
described below.

y=<'z‘>81+bi<a>20+bttEisz+liica40+(Eicbsz
Y=(7)81+b1(5)20+(5)6040

2:0)71+b3a40+b315>6y+<E>5(a)20+(5)5b1y
z=<7hl+b3a40+<B>5<a>20

Nodes y and z are the outputs of NOR and XOR, respectively, and can be characterized
by the above expressions. If node a and node b are set to logic 1 and logic 0, respec-
tively, then logic states of nodes y and 2 can be evaluated according to the above rules as

follows:

y=§1+110+IOO=A+0+A=0

 

94

z=§1+100+010=01+A+A=1

To simulate a static circuit with ratioed design, seven logic levels {0, 1, A, U, 0, I,
U} [Haye82] are needed, where 0, I, and U represent weak signals. The four rules used
to evaluate the product term in the above can be easily modified to accommodate simula-
tion by reducing the signal strength when the signal is traversing through a transistor of
different strength. The L, H, and Y in the above four rules have to extend to allow L in
[0, 0}, H in [1, I}, and Y in (U, U}. Also the rules for summation operations are now
based on the partial ordering lattice structure with seven elements shown in Figure 6.1
(b).

For MOS circuits with a dynamic logic design style, ten logic levels [Haye82] are
sufficient to simulate the circuit in practice. The corresponding partial ordering lattice
structure which describes ten-valued logic is shown in Figure 6.1 (c), where l 6, i, U l
are stored charge signals. To perform logic simulation for the circuits based on the ten-
valued logic, the above product term rules can still be used, but extra checks are needed
for all the dynamic nodes. Since ten-valued logic is used, there are only two possible
strengths of a node. If a static signal (signal from external nodes not from stored charge)
reaches a dynamic node, then the lOgic level of this node is decided by this signal; other-
wise, the logic level of this node is its previous logic state in the form of its stored
charge. For dynamic circuits, L in the above rules is modified to include 0. Similarly, H
includes I, and Y includes U. The summation operations of product terms for the circuits

with ten logic levels can be performed according to the lattice structure in Figure 6.1 (c).

For the example in Figure 5.1, node h is a dynamic node and suppose its present
logic level is 1. If a, b, c, and d are all set to logic 1, and g is set to logic 0, the logic

value of node i can be obtained as follows. From (5.3), we have

e=51+bl+ab0=A+A+0=O

95

From (5.2), we get
h = ge = 00 = A

Since h is a dynamic node, h will keep its previous logic value when no other static sig-

nal reaches it. So the logic state of h is still 1. From (5.4), we have
f=El+dl+cd0=A+A+0=0
From (5.1), we obtain
i=fh1+h0+f0=A+0+A=0

Thus, we obtained the logic value of node i, which is logic 0, from a given set of input

logic values.

We can see from what has been presented that the proposed switch level logic simu-
lation has the following advantages when performing simulation on the circuit expressed

in SLICE representation.
(1) Static partition of the circuit is explicitly represented in SLICE expressions.

(2) Only simple logic operations'are involved in logic value evaluation. Thus, no
dynamic partition [Brya84] is needed to simulate different input patterns. Since the
signal flow direction is provided, far fewer nodes need to be evaluated for the steady
state lOgic level compared to other simulation approaches. Thus, simulation time

can be saved.

(3) The SLICE representation unifies complementary gate logic and pass transistor
logic, so it is suitable for mixed level simulation, including both gate level and

switch level, as shown in Figure 5.1 (a).

It is easy to extend the proposed simulator to cover different strengths of MOS
transistors in the circuits. However, it is difficult to cover different strengths of nodes in
the circuits, since charge sharing between nodes must be handled. Though the method

proposed may not be suitable for handling theoretical MOS circuits which allow any

96

number of logic strengths, it is practical enough to deal with real MOS circuits of dif-

ferent design styles including ratioed and dynamic logics.

 

Chapter 7

Conclusion and Future Work

 

7.1 Summary

We have presented the verification methods for MOS circuits represented in SLICE
expression. In this chapter we will summarize the work and the contribution we have

made, with discussion of possible future research.

Chapter 1 introduced the motivation behind this research. We realized that an effec-
tive switch level circuit representation would facilitate the circuit verification process.
Some background about the switch level model of MOS circuits and circuit verification
methods was reviewed. Previous work and the problems in different verification

methods were also briefly mentioned. '

The switch level MOS circuit model employed in this research was presented in
Chapter 2. A graph representation describing a switch level MOS circuit was presented.
Then we introduced a directed graph to describe the behavior of MOS circuits. Based on
the directed graph, we proposed a switch level circuit representation called Structured
LogIcal Circuit Expression (SLICE) which canies both the structural and functional
information of a MOS circuit. The representation enabled us to develop more effective
and efficient circuit verification methods. We then examined the derivation of Boolean

behavior from a SLICE. This derivation is important for functional verification.

97

98

Preliminary results of this research were presented in [LiNi88].

In Chapter 3, several rules were proposed to extract the Boolean behavior of a
transistor group represented by a SLICE. These rules consider the electrical safety of the
circuit, and examine whether a circuit is electrically safe or not. Thus, the unknown logic
states caused by design error can be discovered. Different design styles of MOS circuits
can be handled well by these extraction rules. In particular, the extraction of gate logic
and pass transistor logic can be unified through the proposed rules. We also discussed
the extraction rules for the design style of general static MOS circuits. An extraction rule

for some dynamic circuits was also presented.

Functionality extraction algorithms to guide the application of the extraction rules
were presented in Chapter 4. The extraction algorithm for a transistor group with a
directed acyclic graph was proposed first. In order to have an efficient extraction process,
we introduced the novel concept of the junction nodes in a circuit. Through these junc-
tion nodes and the divide-and—conquer approach, the time complexity of the Boolean
comparison, which is an important operation in the extraction process, can be greatly
reduced. Then we expanded the extraction algorithm to handle a transistor group with a
general directed graph, using the idea of the strongly connected component. After show-
ing how to extract the functionality of each group in the circuit, we then presented a
method to aggregate the functionality of each group and obtain the final overall func-
tionality of the whole circuit. An additional extraction rule was presented to help accom-
plish the process of aggregation. Experiment result implementing the extraction process
were also shown. The initial concept of functionality extraction was presented in
[LiNi89].

In chapter 5, we explained how to perform timing verification on the circuits
represented in SLICE. Then the false signal path problems in timing verification were

introduced. We only considered the problem of finding correct signal paths within a

transistor group. Distinguishing different types of nodes in the transistor network and

Age" Am

99

making use of transistor gate terminal node names facilitated the derivation of the conect
signal paths. Thus, an effective method to determine the correct signal paths was
developed. Although the method is able to find conect signal paths, it sometimes
encounters time consuming signal pathfinding. To speed up the pathfinding computation
time, a heuristic was proposed to perform signal direction derivation and signal
5 pathfinding. This heuristic does not guarantee to obtain all the correct signal paths. How-

ever, most of the time it has been found to work well.

In Chapter 6, we demonstrated the advantages of performing logic simulation on the
circuit in SLICE representation. Since not all the logic states of every node in the circuit
need to be known, and only those nodes that are on the left hand side of the SLICE need
to be simulated, the simulation time can be reduced. Rules to evaluate logic states during

simulation were also presented.

In summary, a circuit representation, SLICE, was proposed, which carries bOth the
structural and functional information of the circuit. Effective verification methods which
take advantage of the information provided by SLICE were then developed. These
methods include functionality extraction, timing verification, correct signal pathfinding,
and logic simulation. Thus, the functional and tinting behavior of a MOS circuit can be

completely verified through its SLICE representation.

7.2 Future Work

The work we have presented is, of course, not exhaustive. There is still much room

for future research. Here are some possible areas for further study.
(1) Verification methods for general MOS circuits

In this research, we have limited our discussion to static MOS circuits and some
dynamic MOS circuits. We do not consider those dynamic MOS circuits which allow

charge sharing phenomena in the circuits. However, some circuit designs do make use of

 

100

charge sharing techniques to accomplish some desired functional behavior. Thus, extend-
ing our verification methods to cover all the dynamic MOS circuits is important to make
the proposed methods complete. When we want to consider the general MOS circuits,
then, each node in the circuit should have different node capacitances. Each node capaci-
tance in the circuit holds a charge which can contribute its logic state to some other
nodes. Thus, every node in the circuit is considered as a possible signal source. An
efficient algorithm to identify useful signal paths that affect the goal nodes is the main
object of research in the extension of the proposed verification methods for dynamic cir-

cuits.
(2) Efficient methods to automatically generate SLICE

It is assumed that the SLICE representation describing the behavior of a circuit is
available before circuit verification is performed. When the SLICE is not available, we
suggested that a path searching algorithm like depth first search might be used to identify
all the signal paths and then generate the SLICE expression. However, with such an
approach, the time complexity may be high. Thus, a more efficient path searching
method is needed. One possible approach is to add some rules, such as those suggested in
[JOup87b] to guide the path searching algorithm by reducing the search space. In this
way, a more efficient search method may be obtained to automatically generate the

SLICE representation of the circuit.
(3) Fault diagnosis using SLICE representation

Uncovering the faults in the circuits is crucial in VLSI design. In order to do this,
test generation is required. Test generation generates a set of test patterns capable of sen-
sitizing the signal paths. From these paths, a faulty circuit can be distinguished from a
fault-free circuit. Signal path analysis is needed to generate useful test patterns. Since
SLICE representation carries signal flow information, it can assist the signal path
analysis and generate appropriate test patterns at the switch level. Test generation tech-

niques at the switch level are not well developed and usually each technique is only

 

101

applicable to a special class of circuits [Agra84, RoSh85]. It would be interesting to con-

sider the test generation for the class of static MOS circuits using SLICE representation.
(4) Finding false signal paths among different transistor groups

We have proposed a method to eliminate false signal paths within a transistor group
by utilizing the functional information in the circuit. Similarly, we may investigate the
false signal path problem among transistor groups by considering the functional informa-
tion revealed in the SLICE. Since the SLICE is able to describe transistor interconnection
of circuits at the switch level, and furthermore, to identify different stages of functional
blocks in the circuit such as logic gates, the functional relationships among different
groups are embedded in the SLICE. Using this information, we may develop methods to
eliminate the false signal paths which occur among different transistor groups in the cir-

cuit designed at the switch level.
(5) Application of proposed verification method to digital bipolar circuits

Earlier research did not investigate the need to describe the digital bipolar circuits at
the switch level. More recently, this need has been addressed in [HaSa87]. Since bipolar
transistors are physically unidirectional devices, and do not have charge sharing
phenomena between nodes in the circuit, the switch level model of four-valued lattice
structure can well describe the behavior of the bipolar circuits. Because the SLICE
representation is suitable for such static circuits as those with four-valued lattice struc-
tures, the verification methods we have proposed can be profitably applied to bipolar cir-
cuits. In this way, the functional and timing behavior of the bipolar circuits can be under,-
stood by incorporating an appropriate timing model of bipolar transistors in the proposed

verification methods.
(6) Circuit synthesis through SLICE representation

We have proposed a SLICE representation and investigated different verification

methods on the circuits in a SLICE. But we have not discussed the possibility of circuit

102

synthesis through SLICE representation. Since a SLICE is a design representation, it is
possible to manipulate a SLICE with some design constraints to yield several different
SLICEs. Thus, we can use a SLICE to accomplish a circuit synthesis. The synthesis is
especially good for pass transistor logic design style, because a SLICE can clearly
describe the signal flow of the circuit at the switch level. Actually, a SLICE is similar in
some ways to a binary decision diagram (BDD) [Aker78], which has been used in syn-
thesis [Brya86]. Hence, it would be interesting to exploit circuit synthesis at the switch

level through a SLICE representation.
(7) Incorporating efficient Boolean comparison methods in functionality extraction

We have tried to reduce the Boolean comparison complexity during the functional-
ity extraction process. The Boolean comparison computation time can be further reduced
by using a better Boolean comparison algorithm. This will improve the overall perfor-

mance of the functionality extraction process.

 

[Agra84l

[AhHU 74]

[AhHU83]

[Aker78]

[BaTr80]

[BMCM87]

[BrIy88]

[Brya80]

[Brya84]

[Brya85]

[Brya86]

[Brya87]

[DuYG89]

List of References

P. Agrawal, "Test Generation at Switch Level," Proc. International Confer-
ence on Computer Aided Design, 1984, pp. 128-130.

A.V. Aho, J.E. Hopcroft, and JD. Ullman, The Design and Analysis of
Computer Algorithms, 1974.

A.V. Aho, J.E. Hopcroft, and JD. Ullman, Data Structure and Algorithm,
Reading, MA:Addison-Wesley, 1983. ~

8.3. Akers, "Binary Decision Diagram," IEEE Trans. Computers, Vol. c-
27, NO. 6, June 1978, pp. 509-516. ’

C. Baker and C. Terman, "Tools for verifying Integrated Circuit Designs,"
Lambda Magazine, 4th Quarter 1980, pp. 22-30.

J. Benkoski, E.V. Meersch, L. Claesen, and H. De Man, "Efficient Algo-
rithms for Solving the False Path Problem in Tinting Verification," Interna-
tional Conference on Computer Aided Design, 1987, pp. 44-47.

D. Brand and VS. Iyengar, "Timing Analysis Using Functional Analysis,"
IEEE Trans. Computers, Oct. 1988, pp. 1309-1314.

R.E. Bryant, "An Algorithm for MOS Logic Simulation," LAMBDA Maga-
zine, Vol. 1, no. 3, 1980, pp. 46-53.

R.E. Bryant, "A Switch-Level Model and Simulator for MOS Digital Sys-
tems," IEEE Trans. Computers, Feb. 1984, pp. 160-177.

R.E. Bryant, "Symbolic Verification of MOS circuits," 1985 Chapel Hill
Conf. VLSI, 1985, pp. 419-438.

R.E. Bryant, "Graph-based Algorithm for Boolean Function Manipulation,"
IEEE Trans. Computer, Vol. c-35, Aug. 1986, pp. 677-691.

R.E. Bryant, "Boolean Analysis of MOS Circuits," IEEE Trans.
Computer-Aided Design, Vol. CAD-6, NO. 4, July 1987, pp. 634-649.

D.H.C. Du, S.H.C. Yen, and S. Ghanta "On the General False Path Problem
in Tinting Analysis", 26th Design Automation Conference, 1989, pp. 555-

103

 

[EbZa83]

[GaJo79]

[HaSa83]

[HaSa87]

[Haye82]

[HGDT84]

[Hitc82]

[Joup87a]

[Joup87b]

[LiNi88]

[LiNi89]

[KoMc86]

104

560.

C. Eberling and O. Zajicek, "Validating VLSI Circuit Layout by Wirelist
Comparison," Proc. 1983 Int’l Conf. Computer- Aided Design, Santa Clara,
Calif., Sept. 1983. PP. 172-173.

MR. Garey and D.S. Johnson, Computers and Intractability: A Guide to
the Theory of NP-Completeness. New York: Freeman, 1979.

IN. Hajj and D. Saab, "Symbolic Logic Simulation of MOS Circuits,"
Proc. Int. Symp. Circuits Syst., 1983 pp. 246-249.

I.N. Hajj and D. Saab, "Switch Level Logic Simulation of Digital Bipolar
Circuits," Computer-Aided Design, Vol. CAD 6, NO. 2, March 1987, pp.
251-258.

J.P. Hayes, "A Unified Switching Theory with Applications to VLSI
Design," Proc. IEEE, 1982, pp. 1140-1151.

L.G. Heller, W.R. Griffin, J.W. Davis and NO. Thoma, "Cascode Voltage
Switch Logic: A Differential CMOS Logic Family," IEEE International
Solid State Circuits Conference, February 1984, pp. 16-17.

R.B. Hitchcock, Sr., "Timing Verification and the Tinting Analysis Pro-
gram," Proc. 19th Design Automation Conference, 1982, pp. 594-604.

N.P. Jouppi, "Timing Analysis and Performance Improvement of MOS
VLSI Designs," IEEE Tran. Computer-Aided Design, Vol. CAD-6, NO. 4,
July 1987. PP. 650-665.

N.P. Jouppi, "Derivation of Signal Flow Direction in MOS VLSI," IEEE
Tran. Computer-Aided Design, Vol. CAD-6, No.3, May 1987, pp. 480-490.

J. Liao and L.M. Ni, "A New CMOS Circuit Representation for Timing
Verification," Proc. 1988 International Symposium on Circuits and Sys-
tems, June, 1988.

J. Liao and L.M. Ni, "Boolean Behavior Extraction from Circuit Layout",
I 989 International Symposium on VLSI Technology, Systems and Applica-
tions, May, 1989, pp. 139-143.

K.L. Kodandapani and EJ. McGrath, "A Wirelist Compare Program for
Verifying VLSI Layouts," IEEE Design & Test , June 1986, pp. 46-51.

[MeCo80]

[Nage75]

[OTOOB6]

[Oust85]

[RaTr87].

[RoSh85]

[RuPe83]

[vaosssl

105

C. Mead and L. Conway, Introduction to VLSI Systems. Reading, MA:
Addison-Wesley, 1980.

LA. Nagel, "SPICE2: A Computer Program to Simulate Semiconductor
Circuits," Tech. Rep. UCB ERL-M250, Univ. of California, Berkeley, May
1975.

G. Odawara, M. Tontita, O. Okuzawa, T. Ohta, and Z. Zhuang, "A Logic
Verifier Based on Boolean Comparison," Proceedings of 23rd Design Auto-
mation Conference, June 1986, pp. 208-214.

J .K. Ousterhout, "A Switch-Level Tinting Verifier for Digital MOS VLSI,"
IEEE Tran. Computer-Aided Design, Vol. CAD-4, NO. 3, July 1985, pp.
336-349.

V.B. Rao, and TN. Trick, "Network Partitioning and Ordering for MOS
VLSI Circuits," IEEE Tran. Computer-Aided Design, Vol. CAD-6, no. 1,
Jan. 1987, pp. 128-144.

S.H. Robinson and JP. Shen, "Towards a Switch Level Test Pattern Gen-
eration Program," International Conference on Computer Aided Design,

1985.

J. Rubinstein, P. Penfield, Jr., and MA. Horowitz, "Signal delay in RC tree
networks," IEEE Trans. Computer-Aided Design, Vol. CAD-2, July 1983,
pp. 202-211.

A.V. Vasquez, S.W. Director, and K.A. Sakallah, "PRIMO: A VLSI Circuit
Partitioner for Simulation Applications," Proc. 1985 International Sympo-

. sium on Circuits and Systems," 1985, pp. 1075-1078.

[Wata83]

[WeEs85]

[WeSa86]

[WuNW87]

T. Watanabe et al., "A New Automatic Logic Interconnection Verification
System for VLSI design," IEEE Tran. CAD/ICAS, Vol. CAD-2, No. 2,
April 1983, pp. 70-82.

N. Weste and K. Eshraghian, Principles of CMOS VLSI Design, Addison-
Wesley, 1985.

R. Wei and A.L. Sangiovanni-Vincentelli, "Proteus: a Logic Verification
System for Combinational Circuits", International Test Conference, 1986,
pp. 350-359.

C.-F.E. Wu, L.M. Ni, and AS. Wojcik, "Functional Recognition of Static
CMOS Circuits," Proc. 1987 International Conference on Computer Aided

 

106

Design, Nov. 1987, pp. 306-308.