CMOS CIRCUIT DESIGN OF THRESHOLD GATES WITH HYSTERESIS

Gerald E. Sobelman, Karl Fant

Theseus Logic, Inc.

1080 Montreal Ave., Suite 200
St. Paul, MN 55116, USA
[email protected],[email protected]

ABSTRACT combinational logic and storage elements, are

constructed out of these same primitives. The designer
M-of-N threshold gates with hysteresis form a class of
simply specifies an interconnection of library modules in
circuit elements that have important application in
order to obtain a desired computational functionality.
NULL Convention Logic ", a novel asynchronous logic
The circuit operates at the maximum speed of the
design methodology. General design guidelines for these
underlying semiconductor device technology.
M-of-N gates are presented using CMOS technology.
Three types of circuit implementations are discussed: In this paper, we will describe the transistor-level design
static, semi-static and dynamic. In addition, criteria for CMOS implementations of the M-of-N gates.
initialization techniques are presented for use in In section 2, the desired threshold and hysteresis
establishing a known initial state. behavior are explained. Then, in sections 3 - 5, various
types of CMOS circuit implementations are presented.
1. INTRODUCTION Initialization techniques are discussed in section 6.
The clocked synchronous paradigm is currently the Finally, the results are summarized in section 7.
dominant design methodology for digital systems.
2. BEHAVIOR OF THRESHOLD GATES WITH
While this approach has enjoyed great success over many
HYSTERESIS
decades, limitations and drawbacks of the methodology
exist. For example, the need for precise distribution of The primitive element that we consider is an M-of-N
high-speed clocks over a large chip area is complex and threshold gate with hysteresis, which we refer to as
the clock tree itself dissipates a significant fraction of the simply an M-of-N gate. The abstract symbol for an M-of-
total power consumption. Also, the need to meet critical N gate is shown in Figure 1. The cases of interest are
path constraints requires a complex timing analysis those where M s N. An M-of-N gate is a generalization
based on worst-case design where the performance is of both a Muller C-element [4] and a Boolean OR gate.
limited by the edges of the specified process, temperature Specifically, for N > 1, an N-of-N gate corresponds to an
and voltage ranges. These problems become more severe N-input Muller C-element. On the other hand, a 1-of-N
as device sizes continue to shrink and as clock gate corresponds to an N-input Boolean OR gate. The
frequencies continue to rise. cases where both M > 1 and M < N are novel and have
no counterparts in the literature.
Asynchronous design techniques have been proposed as
an alternative to the clocked system methodology, and
the subject has a long history [ 11. These approaches seek
to overcome the above limitations by dispensing with z
the clock and using self-timed signaling to control the AN
sequencing of computations in the system. While much
research has been devoted to this area, no asynchronous Figure 1. Symbol for a general M-of-N gate.
approach has yet managed to gain a strong foothold in The M-of-N gates operate on signals that can have two
the design community. Most of these approaches are possible abstract values, which we refer to as DATA and
themselves highly complex and difficult to design. Also, NULL. In the normal mapping arrangement, DATA
their claimed advantages have, for the most part, not corresponds to a logic-1 voltage level while NULL
been sufficiently compelling for designers to consider corresponds to a logic-0 voltage level. The reverse
adopting a major change in their existing methodology. mapping is also possible, as are mappings into units of
NULL Convention Logic'" (NCL'") is a new clock-free, current.
delay-insensitive logic design methodology [2,3] for There are two important aspects of the M-of-N gate,
digital systems. Unlike previous asynchronous design namely threshold behavior and hysteresis behavior. The
approaches, NCL circuits are very easy to design and threshold behavior means that the output becomes
analyze. In NCL, a circuit consists of an interconnection DATA if at least M of the N inputs have become DATA.
of primitive modules known as M-of-N threshold gates The hysteresis behavior means that the output only
with hysteresis. All functional blocks, including both changes after a sufficiently complete set of input values
11-61

0-7803-4455-3/98/$10.00 0 1998 IEEE

have been established. In the case of a transition to
DATA, the output remains at NULL until at least M of
the N inputs become DATA. In the case of a transition
to NULL, the output remains at DATA until all N of the
inputs become NULL.
In the following sections, we will demonstrate how this
desired abstract behavior is implemented using static,
semi-static and dynamic CMOS circuits. The properties
of each implementation are pointed out.
A2+

AN-+;
:A I 4
'9
A24 **'ANA

3. STATIC IMPLEMENTATION§ Figure 4. General structure of a static CMOS N-

of-N gate.
The general structure of a static M-of-N threshold gate
with hysteresis is shown in Figure 2. For analysis of its operation, begin with the situation
where all N inputs are 0. In this case, the Go to NULL
and Hold NULL blocks are ON and Z goes low, so that
l
;
i
$ -
& b all of the PMOS transistors in the pull-up network (not
counting the inverter) are ON. At the same time, the Go
Z to DATA and Hold DATA blocks are OFF, and all of
the NMOS transistors in the pull-down network (not
DATA counting the inverter) are OFF. If one of the inputs goes
DATA
to 1, the Go to NULL block tums OFF and the Hold
DATA block tums ON. However, the Z output does not
Figure 2. General structure of a static CMOS M- change because the Hold NULL block, which remains
of-N gate. ON, maintains a connection between the intermediate
node and VDD. It is only when all N of the inputs go to
For any M-of-N gate, the Go to NULL and Hold DATA 1 that the output can change. At that point, the Hold
blocks are complementary to each other and have the NULL block tums OFF and the Go to DATA block
universal forms shown in Figure 3. tums ON, forcing the Z output to DATA. We then reach
A1 A2 A3 AN
a situation when all of the PMOS transistors in the pull-
b d b up network (not counting the inverter) are OFF and all of
the NMOS transistors in the pull-down network (not
counting the inverter) are ON. Because of the symmetry
of the circuit, a similar set of actions will occur for the
transition of the output back to NULL.
In the cases where M < N, the topologies of the Go to
Figure 3. Universal blocks within the static DATA and Hold NULL blocks must be determined for
CMOS M-of-N gate. each case. As an example, a 2-of-3 gate having inputs A,
B and C is shown in Figure 5.
From these topologies, it is clear that the Go to NULL
block is only ON when all N inputs are 0. Also, the
-
Hold DATA block is ON if one or more of the inputs are
1. Because of the series chain in the Go to NULL block,
speed considerations will limit these structures to a
maximum number of inputs, typically N 5 6 . Threshold
gates with higher values of N can be synthesized using a
multi-level tree of small-N gates.
Similarly, the Go to DATA and Hold NULL are
complementary to each other, but their precise structures 6
depend on the particular values of M and N. It is Figure 5. Static 2-of-3 gate.
simplest to begin with the special case where M = N.
The general structure of a static N-of-N gate is shown in Note first that the Go to NULL and Hold DATA blocks
Figure 4. As noted earlier, this structure has been known assume their standard forms. The forms for the other two
in the literature as an implementation of Muller C - blocks may be obtained by the following analytical
elements [4]. procedure. First, begin with the Go to DATA block.
This should turn ON when any 2 of the 3 inputs go
high. The switching expression for this condition is as
follows:

11-62
 f = AB + BC + C A = A B + C(A + B)
The structure of the Go to DATA block is obtained
directly from this expression using the normal rules for
constructing NMOS switching networks. Since the Hold
NULL block is complementary to this, its structure may
be obtained by complementing the above expression and
then simplifjling using DeMorgan’s laws as follows:
f = [AB + C(A + B)]’ = (A’ + B’)(C’ + A’B’) = A’C’
+ A’B’ + B’C’ = A’B’ + C’(A’ + B’)
The final form for f leads directly to the topology of the Figure 6. Static 3-of-4 gate.
Hold NULL block shown in Figure 5 using the normal 4. SEMI-STATIC IMPLEMENTATIONS
rules for constructing PMOS switching networks. Note

wz
that the equation for f implies that the Hold NULL The general structure of a semi-static M-of-N threshold
block will be ON if two or more of the inputs are 0, gate with hysteresis is shown in Figure 7.
which agrees with the desired behavior for this gate. This
is seen to be true because, if two or more of the inputs Go to NULL
are 0, then the three input values would necessarily be
below the threshold value for this particular gate. Go to DATA

Note also that in this example, the topologies of the Go

to DATA and Hold NULL blocks are identical. We refer Figure 7. General structure of a semi-static
to this as the self-dual properq. This is a special threshold gate with hysteresis.
attribute that is present in only a subset of all possible
M-of-N gates. As a specific example, the design of a semi-static 2-of-3
threshold gate with hysteresis is shown in Figure 8.
As a second and more complicated example, consider the Note the structure of the NMOS transistors in the pull-
design of a 3-of4 gate having inputs A, B, C and D. down network is derived from the unfactoredform of the
The switching expression for the Go to DATA block is switching expression given earlier. This form is used in
immediately obtained from the desired behavior of this order to obtain maximum robustness against charge
gate: sharing effects. This robustness is due to several factors.
f = ABC + ABD + ACD + BCD First, note that the precise order of the A, B and C
inputs have been permuted so that only one intermediate
This can be factored into a more compact form as node capacitance in the pull-down network will
follows: contribute to charge sharing when any one of the three
inputs is high. Also, in an actual physical layout, each of
f = AB(C + D) + CD(A + B)
the three intermediate nodes in the pull-down network
The Hold NULL block is computed as follows: would consist of a single shared diffision region, which
would have a very small capacitance. Note that the
f ’ = (A’ + B’ + C’)(A’ + B’ + D’) presence of the weak feedback inverter also provides some
(A’ + C’ + D’)(B’ + C’ + D’) protection. Since the NMOS and PMOS transistors in
After expanding and simplifying terms, we obtain: this inverter are weak, they may not be able to source or
sink current fast enough to completely counteract the
f = ,473’ + A’C’ + A’D’ + B’C’ + B’D’ + C’D’ effects of charge sharing. However, the current from the
A factored representation is as follows: weak devices as well as the extra capacitance at the
intemal node both act to limit the extent of charge
f=(A’ + B’)(C’ + D’) + A’B’ + C’D’ sharing. Moreover, the weak inverter will eventually
Note that this result corresponds to the fact that the Hold restore a partially degraded voltage level at the intemal
NULL block will be ON provided that at least two of the node to the rail value, which provides additional noise
four inputs are low. This agrees with the desired immunity.
behavior for this particular gate.
The factored equations for f and f lead directly to the
$ (weak)

circuit shown in Figure 6. Note that the 3-of-4 gate does

not have the self-dual property.

T-
Figure 8. Semi-static 2-of-3 gate.
11-63
 T
1
5. DYNAMIC IMPLEMENTATIONS
In many real-time computing applications, such as those
involving signal processing, the input data stream is
continuous at a specified minimum rate. In these Node 1 1-b- 2

situations, there is no need to maintain state information

with a feedback mechanism. Rather, the presence or A4
absence of charge at an isolated node can be maintained
on the order of a few milliseconds without any loss of
information. Thus, for these kinds of applications, we 0
can eliminate the weak feedback inverter of the semi- Figure 11. Static 2-of-2 gate with reset to 0.
static configuration. The resulting circuits are called
dynamic M-of-N gates, and the general block diagram for 7. CONCLUSIONS
such a gate is shown in Figure 9. The form of the Go to
NULL and Go to DATA blocks are the same as those The general class of M-of-N threshold gates with
used in the semi-static configuration, including the hysteresis has been introduced and several types of
appropriate optimizations for minimizing charge sharing CMOS circuit implementations have been proposed. The
effects. general design procedures for static, semi-static and
dynamic configurations have been described, and several
specific M-of-N gate design examples have been given.
These gates are the primitive building blocks of NULL
Convention Logic.
54
Go to DATA

Figure 9. General structure of a dynamic

These circuit techniques can be used to construct an
ASIC cell library of M-of-N gates for a range of values of
M and N. Standard automated place and route tools can
threshold gate with hysteresis. be combined with schematic capture or synthesis tools to
For example, a dynamic 2-of-3 gate would have the same produce a complete CAD environment for logical and
form as the circuit of Figure 8 except that the weak physical design of systems within this framework.
feedback inverter would be removed. Several prototype chips, including one-dimensional and
6. INITIALIZATION TECHNIQUE§ two-dimensional discrete cosine transform processors
have been designed and fabricated using this
In many applications, it is necessary to be able to methodology.
independently reset a given M-of-N gate to a known
initial state. A general mechanism for accomplishing this 8. ACKNOWLEDGMENTS
initialization is shown in Figure 10 for the case where We thank Ryan Jorgenson, David Lamb, Dave Parker, Ross
the output Z can be initialized to 0. (An analogous Smith, Rick Stephani, Ching-Yi Wang and Ken Wagner of
structure can be constructed for initializing Z to 1.) In the Theseus Logic, Inc. for their help in developing this
circuit, the signal -RST is an active-low reset signal. technology and for their comments on this paper. Research
When -RST = 0, the output Z is forced to 0 regardless of supported by Ballistic Missiles Defensehnovative Science
the states of the pull-up and pull-down networks. When - and Technology and managed by the Office of Naval
RST = 1, the M-of-N gate operates normally. This Research.
general structure applies to any of the three circuit G.E. Sobelman is also with the University of Minnesota,
implementation styles discussed above. Minneapolis, MN.
T T 9. REFERENCES
Network PR l--RST [ l ] J. A. Brzozowski and C.-J. H. Seger, Asynchronous
Node 1 Circuits, Springer-Verlag, 1995.
[2] Karl M. Fant and Scott A. Brandt, NULL Convention
Pull-Down Logic SystemTM,U. S. patent #5,305,463, April 19, 1994.
[3] Karl M. Fant and Scott A. Brandt, “NULL Convention
Logic? A Complete and Consistent Logic for
Asynchronous Digital Circuit Synthesis,” Proceedings,
Figure 10. General structure of a threshold gate International Conference on Application-Specific Systems,
with hysteresis and reset to 0. Architectures and Processors, pp. 261-273, 1996.
As a specific example of this technique, a static 2-of-2 [ 41 T.-Y. Wuu and S. B. K. Vrudhula, “A Design of a Fast
gate with the reset-to-0 capability is shown in Figure 11. and Area Efficient Multi-Input Muller C-element,” IEEE
Transactions on Very Large Scale Integration (VLSI)
Systems, Vol. 1, No. 2, p. 215-219, 1993.

11-64