406 IEEE TRANSACTIONS ON INSTRUMENTATION AND MEASUREMENT, VOL. 55, NO.

2, APRIL 2006

Reversible-Logic Design With Online Testability

Dilip P. Vasudevan, Parag K. Lala, Fellow, IEEE, Jia Di, and J. Patrick Parkerson

Abstract—Conventional digital circuits dissipate a significant TABLE I

amount of energy because bits of information are erased during TRUTH TABLE OF THE TOFFOLI GATE
the logic operations. Thus, if logic gates are designed such that
the information bits are not destroyed, the power consumption can
be reduced dramatically. The information bits are not lost in case
of a reversible computation. This has led to the development of
reversible gates. This paper proposes three new reversible logic
gates; two of the proposed gates can be employed to design online
testable reversible logic circuits. Furthermore, they can be used
to implement any Boolean logic function. The application of the
reversible gates in implementing several benchmark functions has
been presented.
Index Terms—Fredkin gate, garbage outputs, online testing, TABLE II
reversible logic, Toffoli gate, two-pair two-rail checker. TRUTH TABLE OF THE FREDKIN GATE

I. I NTRODUCTION

T HE COMPUTATION carried out in conventional comput-

ers is irreversible, i.e., once a logic block generates the
output bits, the input bits are lost. This loss of input bits leads to
the power consumption in the system. Landauer [1] has shown
that for every bit of information lost in logic computations that
are not reversible, kT ∗ log 2 joules of heat energy is generated,
where k is the Boltzmann’s constant, and T is the absolute
temperature at which the computation is performed. The energy
dissipation due to bit loss is not significant for the current clock
speed of computers. However, as the clock speeds of computers
are elevated, the frequency with which the information bits are
lost will also increase. Reversible logic circuits avoid energy
loss by “uncomputing” the computed information, thereby re-
cycling the energy in the system [2]. Bennett [3] showed that
Fig. 1. Toffoli gate.
a zero power dissipation in logic circuits is possible only if a
circuit is composed of reversible logic gates. A gate is reversible
if there is a distinct output assignment for each distinct input
[3]. Thus, a reversible gate’s inputs can be uniquely determined
from its outputs. A reversible logic gate must have the same
number of inputs and outputs [3]. In an n-output reversible
gate, the output vectors are permutations of the numbers 0 to
2n − 1. Reversible gates are balanced, i.e., the outputs are 1s for
exactly half of the inputs. A circuit composed of reversible gates Fig. 2. Fredkin gate.
and without constants on its inputs realizes only balanced func-
tions. It can realize nonbalanced functions only with garbage outputs. Some of the major problems with reversible-logic
synthesis are [4]:
1) Fanouts are not allowed.
2) Feedback from gate outputs to inputs is not permitted.
Manuscript received August 12, 2004; revised September 8, 2005. A logic synthesis technique using a reversible gate should
D. P. Vasudevan, J. Di, and J. P. Parkerson are with the Department have the following features [4]:
of Computer Science and Computer Engineeering, University of Arkansas,
Fayetteville, AK 72701 USA (e-mail: dvasude@[Link]; jdi@[Link]; 1) use a minimum number of garbage outputs;
jpp@[Link]). 2) use a minimum input constants;
P. K. Lala is with Engineering and Information Sciences, Texas A&M Uni-
versity at Texarkana, Texarkana, TX 75501 USA (e-mail: plala@[Link]). 3) use a minimum circuit level;
Digital Object Identifier 10.1109/TIM.2006.870319 4) use a minimum number of gates.
0018-9456/$20.00 © 2006 IEEE
Authorized licensed use limited to: NATIONAL INSTITUTE OF TECHNOLOGY KURUKSHETRA. Downloaded on March 17,2026 at 16:51:22 UTC from IEEE Xplore. Restrictions apply.
 VASUDEVAN et al.: REVERSIBLE-LOGIC DESIGN WITH ONLINE TESTABILITY 407

Fig. 3. (a) New reversible-logic gate R. (b) Signal duplication. (c) AND gate. (d) NAND gate. (e) OR gate.

This paper proposes three types of reversible logic gates. TABLE III
TRUTH TABLE OF THE PROPOSED REVERSIBLE-LOGIC GATE
Two of these can be combined to design an online testable
block, which in turn can be utilized to implement an online
testable reversible-logic system. This paper is arranged as
follows. Section II discusses the universality feature of one
of the proposed reversible gates R, by showing the imple-
mentation of conventional functions like OR, AND, NOT, etc.,
Section III introduces the reversible gates “R1” and “R2”
and the details of designing a testable block using these two
gates. The design of a two-pair two-rail checker using the
reversible gate “R” is described in Section IV. A technique
for synthesizing reversible circuits using R1 and R2 is dis-
cussed in Section V. The CMOS realization of the three re- is shown in Table III. From the truth table, it can be verified that
versible gates is presented in Section VI. Finally, the power the input pattern corresponding to a particular output pattern
estimation for several Microelectronics Center North Carolina can be uniquely determined. The new gate can be used both to
(MCNC) benchmark circuits implemented using R gates and invert and duplicate a signal.
the online testable digital circuits using the R1 and R2 gates The signal duplication function can be obtained by setting
are discussed in Section VII, followed by the conclusion the input b to 0, as shown in Fig. 3(b). The EXOR function is
in Section VIII. available at the output “l” of the new gate. The AND function is
obtained by connecting the input c to 0, the output is obtained
at the terminal n, as shown in Fig. 3(c).
II. R EVERSIBLE L OGIC G ATES
The implementation of a NAND gate is shown in Fig. 3(d).
Several reversible gates have been proposed over the years, An OR gate is realized by connecting two new reversible gates,
e.g., the Toffoli gate, the Fredkin gate etc. [5]–[7]. The truth as shown in the Fig. 3(e).
tables for three input and three output Toffoli and Fredkin gates
are shown in Tables I and II, respectively. In a Toffoli gate, all
III. R EVERSIBLE G ATES W ITH A B UILT -I N T ESTABILITY
inputs from 1 to (n − 1) are passed as output. The nth output is
controlled by 1 to (n − 1) inputs. When all the inputs from 1 to The currently available reversible gates can be used to im-
(n − 1) are 1s, the nth input is inverted and passed as output; plement arbitrary logic functions; however, to the best of our
otherwise, the original signal is passed. The Toffoli gate shown knowledge, the testing of such circuits has not been addressed
in Fig. 1 has three inputs and three outputs. in literature. The testing of reversible logic gates can be a
The inputs “a” and “b” are passed as the first and second problem because the levels of logic can be significantly higher
output, respectively. The third output is controlled by a and b to than in standard logic circuits. This paper proposes two re-
invert “c”. The Fredkin gate [8], [9] is shown in Fig. 2. Here, the versible logic gates, R1 and R2 that can be used in pairs to
input a is passed as the first output. Inputs b and c are swapped design testable reversible logic circuits. The first gate R1 is
to get the second and third outputs, which are controlled by a. used for implementing arbitrary functions while the second gate
Thus, two inputs can be swapped by controlling the swap using R2 is employed to incorporate online testability features into
another input in the Fredkin Gate. the circuit. Gates R1 and R2 are shown in Fig. 4(a); and the
A new three-input and three-output reversible-logic gate R corresponding truth tables of the gates are shown in Tables IV
[Fig. 3(a)] is proposed in this paper. The truth table of the gate and V, respectively. From the truth tables, it can be verified that
Authorized licensed use limited to: NATIONAL INSTITUTE OF TECHNOLOGY KURUKSHETRA. Downloaded on March 17,2026 at 16:51:22 UTC from IEEE Xplore. Restrictions apply.
 408 IEEE TRANSACTIONS ON INSTRUMENTATION AND MEASUREMENT, VOL. 55, NO. 2, APRIL 2006

Fig. 4. (a) Reversible-logic gate R1 and reversible-logic gate R2. (b) OR and EXOR gates. (c) XNOR and NAND gates. (d) NOR gate. (e) AND gate.

TABLE IV
TRUTH TABLE OF THE REVERSIBLE-LOGIC GATE R1

Fig. 5. Testable block.

[Fig. 4(b)]. The EXNOR function and the NAND function are
obtained by setting input c to 1 [Fig. 4(c)]. The NOR function
can be obtained by cascading two R1 gates [Fig. 4(d)]. An
AND gate also requires the cascading of two gates [Fig. 4(e)].
R1 can transfer a signal at input a to output u by setting the
input c to 0.
Gate R2 is used to transfer the input values at d, e, and f
to outputs x, y, and z; it also generates the parity of the input
TABLE V pattern at output s. The output s of the gate is the complement
TRUTH TABLE OF THE REVERSIBLE-LOGIC GATE R2
of the input r if all other inputs of the gate remain unchanged.
For example, if input def r = 1000 is changed to 1001, the
output of the gate will change from 1000 to 1001. During a
normal operation, the input r is set to 1. A testable logic block
can be formed by cascading R1 and R2, as shown in Fig. 5. In
this configuration, gate R2 is used to check online whether there
is a fault in R1 or in itself. If R1 is fault free, its parity output
q and the parity output s of R2 should be complementary;
otherwise, the presence of a fault is assumed. Thus, during a
normal operation, the presence of a fault in the logic block can
be detected.

IV. T WO -P AIR T WO -R AIL C HECKER

A two-pair two-rail checker is constructed using gate R, as
shown in Fig. 6. The two-pair rail checker is composed of
the input pattern corresponding to a particular output pattern eight R gates. The error checking functions of the two pair rail
can be uniquely determined. checker are as follows:
Gate R1 can implement all Boolean functions and during
e1 = x0y1 + y0x1
a normal operation, the input p is set to 0. The OR and the .
EXOR functions can be simultaneously implemented on R1 e2 = x0x1 + y0y1
Authorized licensed use limited to: NATIONAL INSTITUTE OF TECHNOLOGY KURUKSHETRA. Downloaded on March 17,2026 at 16:51:22 UTC from IEEE Xplore. Restrictions apply.
 VASUDEVAN et al.: REVERSIBLE-LOGIC DESIGN WITH ONLINE TESTABILITY 409

Fig. 6. Two-pair two-rail checker.

Fig. 8. NAND gate using R1 and R2.

The NAND block-based implementation of function  F  =

ab + cd is given below:



1) ab = ((ab) ) = (1 ab) , cd =

(cd) ) =

(1 ab) .
2) ab + cd = ((ab) · (cd)) = ((1 ab) · (1 cd)) .
Fig. 7. Testable block embedded with the two-pair two-rail checker.
The implementation of the function F is shown in Fig. 9.
The number of signal duplication blocks, which serves in
The fault-free checker will produce the complementary out- avoiding the fanout depends on the number of times the variable
put at e1 and e2 if the inputs are complementary; otherwise, appears in the function. An example of the number of blocks
they will be identical. The block diagram of the testable block required to implement the fanout of a variable that appears six
along with the two-pair rail checker is shown in Fig. 7. The times as a and three times as its complement a’ is shown in
outputs q and s of one testable block forms the input x0 and Fig. 10.
y0 for the two-pair rail checker, and the outputs of another Several MCNC benchmark functions were implemented us-
testable block forms the input x1 and y1. Thus, the testable ing the above approach. The gate counts, garbage outputs, and
blocks constructed using gates R1 and R2 are tested using the number of checkers for the implemented MCNC benchmark
two-pair rail checker. designs are shown in Table VII.

V. S YNTHESIS OF THE R EVERSIBLE L OGIC C IRCUITS VI. C MOS R EALIZATION OF THE P ROPOSED
R EVERSIBLE L OGIC G ATES
A sum of products (SOP) expression can be synthesized
using reversible logic by converting the SOP expression into a The transistor level design of the three reversible logic gates
NAND –NAND form. Each testable NAND block is implemented are realized in CMOS. Fig. 11 shows the transistor level design
by cascading gates R1 and R2. Fig. 8 shows the implementation of the gate R. Since an EXOR functionality is needed for
of (ab) . If a variable appears more than once in an expression, implementing the output functions of the reversible gates, an
then a signal duplication gate will be required. Note that fanouts efficient four-transistor EXOR function design has been chosen
are not allowed in the reversible-logic design. to implement the transistor level design [12]–[14]. Gate R was
Authorized licensed use limited to: NATIONAL INSTITUTE OF TECHNOLOGY KURUKSHETRA. Downloaded on March 17,2026 at 16:51:22 UTC from IEEE Xplore. Restrictions apply.
 410 IEEE TRANSACTIONS ON INSTRUMENTATION AND MEASUREMENT, VOL. 55, NO. 2, APRIL 2006

Fig. 9. Reversible NAND block implementation for the function ab + cd.

Fig. 10. Signal duplication.

Fig. 12. CMOS implementation of gate R1.

reversible gate R2. As the first three output of the gate are just
the direct wire connection from input, the input d, e, and f of
the gate can be used as the output.
All the gates (R, R1, and R2) can be combined to form a
reversible cell, which minimizes

the number transistors by a
count of four as a function a c needed by gate R and gate
R1 are shared. Thus, the cell can be implemented with a total
of 46 transistors (Fig. 14).

VII. E STIMATION OF P OWER

Fig. 11. CMOS implementation of gate R. The implementation of the full adder using the proposed
reversible gate R has been compared with that implemented
implemented using 12 transistors. The implementation of gate using the Fredkin Gate [10]. The design implemented using the
R1 is shown in Fig. 12. It took 26 transistors to implement the proposed gate is found to be more efficient; it requires fewer
design. Fig. 13 shows the four inputs and one output of the gates, fewer garbage outputs, and consumes less power. The
Authorized licensed use limited to: NATIONAL INSTITUTE OF TECHNOLOGY KURUKSHETRA. Downloaded on March 17,2026 at 16:51:22 UTC from IEEE Xplore. Restrictions apply.
 VASUDEVAN et al.: REVERSIBLE-LOGIC DESIGN WITH ONLINE TESTABILITY 411

Fig. 13. CMOS implementation of gate R2.

Fig. 14. Reversible cell.

Authorized licensed use limited to: NATIONAL INSTITUTE OF TECHNOLOGY KURUKSHETRA. Downloaded on March 17,2026 at 16:51:22 UTC from IEEE Xplore. Restrictions apply.
 412 IEEE TRANSACTIONS ON INSTRUMENTATION AND MEASUREMENT, VOL. 55, NO. 2, APRIL 2006

TABLE VI
COMPARISON OF RESULTS

TABLE VII
COMPARISON OF THE PROPOSED GATES WITH FREDKIN AND TOFFOLI GATES

power analysis has been made using Xilinx ISE version 6.1 in Table VIII. The percentage overhead of the realized designs
[11]. The full adder with propagate was implemented at the ranges from 12.5 to 33.28%.
behavioral level [VHSIC (very high speed integrated circuit)
hardware description language (VHDL)] using the Fredkin
VIII. C ONCLUSION
gate, the proposed gates, and the Toffoli gate. Table VI shows
the comparison of the designs using these gates. The implemen- Three new reversible logic gates have been proposed in this
tation of the adder circuit is given in [15]. paper. Two of these gates can be paired such that any function
Table VII shows the number of gates, garbage outputs, and implemented using the gate pair will be online testable. A fault
the power estimation of several benchmark circuits imple- in any of these gates will produce a single bit output error.
mented in VHDL using reversible gate R, testable gate R1/R2, In order to ensure that errors can be detected online, two rail
and the Fredkin and Toffoli gates. The transistor overhead checkers are incorporated in the design. Such checkers are also
resulting from adding the testable feature to the gates is shown constructed from the proposed reversible logic gates. A CMOS
Authorized licensed use limited to: NATIONAL INSTITUTE OF TECHNOLOGY KURUKSHETRA. Downloaded on March 17,2026 at 16:51:22 UTC from IEEE Xplore. Restrictions apply.
 VASUDEVAN et al.: REVERSIBLE-LOGIC DESIGN WITH ONLINE TESTABILITY 413

TABLE VIII [12] J.-M. Wang, S.-C. Fang, and W.-S. Feng, “New efficient designs for XOR
OVERHEAD ESTIMATION OF THE TESTABLE DESIGN OVER THE and XNOR functions on the transistor level,” IEEE J. Solid-State Circuits,
NON-TESTABLE DESIGN vol. 29, no. 7, pp. 780–786, Jul. 1994.
[13] H. T. Bui, A. K. Al-Sheraidah, and Y. Wang, “New 4-transistor XOR and
XNOR ,” in Proc. 2nd IEEE Asia Pacific Conf. ASICs (AP-ASIC), Cheju,
Korea, Aug. 2000, pp. 25–28.
[14] N. Weste and K. Eshraghian, Principles of CMOS VLSI Design. Read-
ing, MA: Addison-Wesley, 1985.
[15] D. P. Vasudevan, P. K. Lala, and J. P. Parkerson, “Logic implementation
using a reversible logic gate,” in Proc. IASTED Int. Conf. Circuits, Sys-
tems and Signals (CSS), Clearwater, FL, Dec. 2004, pp. 452–456.

Dilip P. Vasudevan received the B.E. degree in

electronics and communications engineering from
the University of Madras, Madras, India, in 2003.
He is currently working toward the M.S. degree
in computer engineering at University of Arkansas,
Fayetteville.
His current research interests include reversible
logic, online testing, cellular automata-based
nanosystems design, and fault-tolerant quantum
computing.

Parag K. Lala (F’01) received the [Link]. degree

from the King’s College, University of London, Lon-
don, U.K., in 1972, the Ph.D. degree from the City
University, London, U.K., in 1977, and the [Link].
degree from the University of London, in 1998, all
in electrical engineering.
He is the Cary and Lois Patterson Chair of
Electrical Engineering, Texas A&M University at
Texarkana. He has supervised more than 30 M.S. and
implementation of reversible gates are also proposed. The most Ph.D. theses and has authored or coauthored over
important requirement of the reversible gate-based design is the 130 papers. His research has been funded by several
reduction of garbage outputs rather than the actual number of government agencies, such as the Air Force Office of Scientific Research,
Office of Naval Research, National Aeronautics and Space Administration,
gates. A study that aims to optimize the implemented functions and Defense Advanced Research Projects Agency. He is the author of five
by lowering the number of garbage outputs and reducing the books, namely: Fault-Tolerant & Fault-Testable Hardware Design (Englewood
number of checkers is currently in progress. Cliffs, NJ: Prentice-Hall, 1985), Digital System Design Using PLDs (Engle-
wood Cliffs, NJ: Prentice-Hall, 1990), Practical Digital Logic Design and
Testing (Englewood Cliffs, NJ: Prentice-Hall, 1996), Digital Circuit Testing
R EFERENCES and Testability (New York: Academic Press, 1997), and Self-Checking and
[1] R. Landauer, “Irreversibility and heat generation in the computing Fault-Tolerant Digital Design (San Mateo, CA: Morgan-Kaufmann, 2001).
process,” IBM J. Res. Develop., vol. 5, no. 3, pp. 183–191, Jul. 1961. His current research interests include biologically inspired digital system
[2] M. P. Frank, “Reversibility for efficient computing,” Ph.D. dissertation, design, online testable logic design, reversible logic, and reconfigurable
Dept. Elect. Eng. Comput. Sci., Mass. Inst. Technol., Cambridge, Jun. computing.
1999. Dr. Lala was made a Fellow of the IEEE in 2001 "for contributions to
[3] C. H. Bennett, “Logical reversibility of computation,” IBM J. Res. De- the development of self-checking logic and associated checker design." He is
velop., vol. 17, no. 6, pp. 525–532, Nov. 1973. also a Fellow of the Institute of Electrical Engineers, the largest professional
[4] E. Fredkin and T. Toffoli, “Conservative logic,” Int. J. Theor. Phys., engineering society in Europe. He was an Associate Editor of the IEEE
vol. 21, no. 3–4, pp. 219–253, 1982. TRANSACTIONS ON VERY LARGE SCALE INTEGRATION SYSTEMS from
[5] G. J. Milburn, “Quantum optical Fredkin gate,” Phys. Rev. Lett., vol. 62, 1999 to 2001. In 1994, he was selected to receive the Outstanding Educator
no. 18, pp. 2124–2127, May 1989. Award by the IEEE Central North Carolina Section.
[6] M. Perkowski and P. Kerntopf, “Reversible logic (Invited Tutorial),” pre-
sented at the EURO-MICRO, Warsaw, Poland, Sep. 2001.
[7] M. Perkowski et al., “Regularity and symmetry as a base for efficient
realization of reversible logic circuits,” in Proc. Int. Workshop Logic
Synthesis, Lake Tahoe, CA, Jun. 2001, pp. 90–95. Jia Di received the B.S. and M.S. degrees from
[8] P. D. Picton, “Fredkin gates as the basis for comparison of different logic Tsinghua University, Beijing, China, in 1997 and
designs,” in Proc. IEE Colloq. Synthesis and Optimisation Logic Systems, 2000, respectively. He received the Ph.D. degree in
London, U.K., 1994, pp. 5/1–5/4. electrical and computer engineering from the Uni-
[9] T. Sasao and K. Kinoshita, “Conservative logic elements and their univer- versity of Central Florida, Orlando, in 2004.
sality,” IEEE Trans. Comput., vol. C-28, no. 9, pp. 682–685, Sep. 1979. In August 2004, he joined the Computer Science
[10] J. W. Bruce, M. A. Thornton, L. Shivakumaraiah, P. S. Kokate, and and Computer Engineering Department, University
X. Li, “Efficient adder circuits based on a conservative reversible logic of Arkansas, Fayetteville, as an Assistant Professor.
gate,” in Proc. IEEE Computer Society Annu. Symp. VLSI, Pittsburgh, PA, His current research interests include nanocomput-
Apr. 25–26, 2002, pp. 74–79. ing systems, asynchronous logic, low power digital
[11] [Link]. [Online]. Available: [Link] circuit/system design, digital system security, and
ise6_tutorials/[Link] application-specified ICs.
Authorized licensed use limited to: NATIONAL INSTITUTE OF TECHNOLOGY KURUKSHETRA. Downloaded on March 17,2026 at 16:51:22 UTC from IEEE Xplore. Restrictions apply.
 414 IEEE TRANSACTIONS ON INSTRUMENTATION AND MEASUREMENT, VOL. 55, NO. 2, APRIL 2006

J. Patrick Parkerson was born in Mena, AK, and

raised in Fayetteville, AK. He received the B.S.E.E.
(Honors), M.S.E.E., and Ph.D. degree in engineering
from the University of Arkansas, Fayetteville, in
1982, 1986, and 1996, respectively. He was a Texas
Instruments (TI) Graduate Fellow while working on
his M.S.E.E. degree.
In 1982, he joined TI Central Research Labora-
tories, where he worked on nonvolatile memories.
While at TI, he also worked on the design of a
Very High-Speed IC 1750A microprocessor and de-
veloped computer-aided design software for other IC design engineers. In
1985, he joined Fairchild Semiconductor, South Portland, ME (now part of
National Semiconductor) as a Senior Design Engineer and designed emitter-
coupled logic (ECL) and TTL integrated circuits. In 1988, he joined the Applied
MicroCircuits Corporation, San Diego, CA, as a Senior Design Engineer
and worked on high-speed ECL/mixed signal integrated circuits, including
application specified ICs and custom ICs. In 1990, he joined the University of
Arkansas as a member of the research staff supporting research programs with
the U.S. Postal Service. Later, he became a Research Assistant Professor and
the Chief Design Engineers at the High Density Electronics Center. In 2005, he
was promoted to the rank of Associate Professor of computer engineering. He
is also an Adjunct Faculty member of the Electrical Engineering Department of
the same university. His current research interest include IC design, application-
specified IC design, design methodologies, integrated passive components,
electronic packaging design, and electronic circuits for space and aerospace
applications. He is the holder of one patent and has three patents pending. He
is the author or coauthor of about 20 publications.

Authorized licensed use limited to: NATIONAL INSTITUTE OF TECHNOLOGY KURUKSHETRA. Downloaded on March 17,2026 at 16:51:22 UTC from IEEE Xplore. Restrictions apply.