Pass-transistor logic circuit and a method of designing thereof

Details Pass-transistor logic circuit and a method of designing thereof Pass-transistor logic circuit and a method of designing thereof

1997-11-07

2001-02-06

Teska, Kevin J. (Department: 2768)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C716S030000, C326S113000, C326S121000, C326S104000

Reexamination Certificate

active

06185719

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to a logic circuit using pass transistors, and more particularly to a logic circuit with a combination of one or more pass transistors and one or more multiple-input logic gates. Further, the present invention relates to a method of designing a logic circuit for executing a desired logical operation, using a small number of transistors and a small number of stages in a form in which the advantages of pass transistors and multiple-input logic gates are utilized. The present invention also relates to a logic circuit using pass transistors, capable of executing a logical operation in an efficient manner, and to a system using such a logic circuit. The present invention also relates to a method of executing a logical operation in an efficient fashion using a logical circuit including pass transistors.
DESCRIPTION OF THE RELATED ART
It is known in the art to employ a “pass-transistor logic circuit” to reduce a number of elements and power consumption, and to improve operating speed. Pass-transistor logic circuits use pass transistors each comprising a switching device. Conduction between an input terminal and output terminal of the switching device is turned ON or OFF according to a potential at a control terminal. Each pass transistor is realized by connecting the switching device so that whether a logic signal applied to the input terminal is transmitted to the output terminal can be determined with the conducting or nonconducting state of each switching device. In general, a plurality of pass transistors are connected in series and/or parallel to constitute a pass-transistor logic circuit for executing a desired logical operation. As for the switching devices, MOS transistors, for example, may be used. In this case, the gate, source, and drain of each MOS transistor correspond to the control, input, and output terminals, respectively. Both n- and p-channel MOS transistors and the combination of the n- and p-channel MOS transistors may be used as the pass transistors. A pass transistor employing the combination of an n- and a p-channel MOS transistor is often called as a “transmission gate” or a “transfer gate”.
It is also known to realize a logic circuit using a combination of one or more transfer gates and a logic gate such as an inverter, multiple-input NOR gate, multiple-input NAND gate, etc.
The inventor of the present invention has proposed a composite pass-transistor logic circuits which is realized with a combination of a plurality of pass-transistor logic circuits (pass-transistor logic trees) and a multiple-input logic circuit as disclosed in the U.S. patent application Ser. No. 08/716,883 titled “LOGIC CIRCUIT UTILIZING PASS TRANSISTORS AND LOGIC GATE,” filed on Sep. 20, 1996, and in the U.S. patent application Ser. No. 08/763,264 titled “SEMICONDUCTOR INTEGRATED CIRCUIT CAPABLE OF REALIZING LOGIC FUNCTIONS,” filed on Dec. 10, 1996. These patent applications cited above are incorporated herein by reference.
However, a practical technique of designing integrated circuits, in which various functions required by various users are realized using a logic circuit including pass transistors, has not been established. For example, in the technique disclosed in Japanese Unexamined Patent Publication No. 1-216622, logic circuits each composed of a combination of transfer gates and a logic gate are prepared as logic cells, and a desired LSI is designed by combining these logic cells. However, a specific technique is not disclosed for designing various logic circuits required for practical applications, although some simple logic circuits such as an exclusive OR, exclusive NOR, and full adder are disclosed.
One known technique of designing pass-transistor logic circuits is to use a BDD (binary decision diagram). For example, a logical expression (1) which includes variables a, b, and c as described below can be represented in a BDD as shown in FIG.
1
. This BDD can then be mapped to a pass-transistor logic circuit as shown in FIG.
2
. Herein, a process of replacing a logical expression by a corresponding logic circuit is referred to as a mapping. Symbol 9 denotes exclusive OR in the logical expression (1).
f=a⊕b⊕c
  (1)
When equivalent logical expressions are represented by BDDs, the size of the graph varies depending on the order of variables included in the equivalent logical expressions. For example, the logic circuit shown in FIG.
3
and the logic circuit shown in
FIG. 5
are equivalent to each other although there is a difference in the order of variables. The logic circuit shown in
FIG. 3
can be represented by a BDD graph as shown in
FIG. 4
, and the logic circuit shown in
FIG. 5
can be represented by a BDD graph as shown in FIG.
6
. The logic circuit shown in FIG.
3
and the corresponding BDD graph shown in
FIG. 4
is the optimum in terms of the order of variables. In contrast, the logic circuit shown in FIG.
5
and the corresponding BDD graph shown in
FIG. 6
is the worst in the order of variables.
If the number of inputs of a logical operation, that is the number of variables included in a logical expression, is given by n, then, in theory, there can be at most 2
n
different orders of variables. It is practically impossible to select an optimum order from such a huge number of possible orders of variables, because the process of selecting the optimum order will take a very long time. On the other hand, if the processing time required to determine the order of variables is limited, there is a risk that the resultant order of variables be inadequate and very far from the optimum order, which will cause an impractically great increase in the number of gates making up a logic circuit mapped from the inadequate BDD graph.
There are various techniques known to determine the order of variables in a BDD. For example, in a technique disclosed in a paper titled “Method of determining the order of variables with respect to the “width” of a common binary decision diagram” (Hata, The 42-th Meeting of Information Processing Society of Japan, 2J-5, 1991, hereinafter referred to as the first prior art), when a BDD is divided into two parts at a boundary between a k-th input variable and a (k+1)th input variable, the number of edges passing through the cross section is defined as the “width”. When variables are selected in the process of determining variables from the top to bottom, each variable is selected from input variables remaining as candidates so that each variable results in a minimum width. In this method, if the number of input variable is n and the number of nodes of the BDD is G, the calculation time required to determine the order of the input variables is of the order of O(n
2
·G), wherein O(n
2
·G) refers to a time required to perform n
2
·G times operations.
In another technique disclosed in a paper titled “Multi-Level Pass-Transistor Logic for Low-Power ULSIs” (Yano et al., IEEE 0-7803-3036-6/95, hereinafter the second prior art), those parts which share the same logic function are extracted from the original BDD, and the BDD is replaced by a new BDD so that the resultant BDD has the same number of leaves as that included in the original BDD. After that, logic associated with the control inputs at nodes in the resultant BDD is created so that the BDD represents the original logic.
In the first prior art, however, the BDD has a feature that AND and/or OR logic circuits are connected in series by pass transistors, and thus a great number of pass-transistor stages are required in the logic circuit. To determine the order of input variables within a practical calculation time, the number of input variables should be limited to a few tens and the number of nodes should be limited to a few ten thousands. Furthermore, the solution of the order of input variables obtained by the above calculation is still far from the optimum solution.
In the second prior art, it is possible to map a logical expression into a pass-transistor logic circuit having a less number of pass-transist

Affiliated with

Also associated with

Rating

Pass-transistor logic circuit and a method of designing thereof does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Pass-transistor logic circuit and a method of designing thereof, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pass-transistor logic circuit and a method of designing thereof will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2576501