74

Prefix Parallel Adder Virtual Implementation in

Reversible Logic
David Y. Feinstein, Mitchell A. Thornton and V.S.S. Nair
Department of Computer Science and Engineering, Southern Methodist University
{dfeinste, mitch, nair}@engr. smu.edu

Abstract - This paper demonstrates a simplified approach In this work, we are particularly interested in the
for reversible logic synthesis based on direct translation of Parallel Prefix Adder (PPA) architecture that was
the circuit VHDL description into virtual Fredkin gates. pioneered by Ladner and Fischer [11]. This approach was
We investigate the size and speed of such a reversible logic later improved by Brent and Kung [3] for reduced fan-
implementation of the Brent-Kung Parallel Prefix Adder
(PPA) in comparison to a standard logic implementation.
out, thus making it potentially suitable for future use in
' .
Using the Altera Corporation's Quartus II synthesis and
simulation tool, we show that our virtual reversible logic
reversb ic Therere e, our benhmarkfr th
research iS the Brent-Kung parallel prefix adder with
implementation follows the 0(log2n) delay and 0(n) cost of operand sizes up to 32 bits.
the standard logic implementation. Zimmerman [19] developed an extensive VHDL library
that conveniently implements the Ladner and Fischer, the
I. INTRODUCTION Brent and Kung, and many other PPA architectures using
standard logic. The Zimmerman library is parameterized,
Pioneering work by Bennet, Feynman, Fredkin, and allowing the user to create PPAs of arbitrary size. We
Toffoli investigated the potential of reversible logic to have modified the Zimmerman library to produce a
create circuits that theoretically achieve zero internal VHDL translation into reversible logic, which is then
power dissipation [16]. Accordingly, futuristic logic used as input to the Quartus II tool for virtual
design based on quantum devices must be based on such implementation and simulation.
reversible logic where the circuit has the same number of This paper is organized as follows. Section II discusses
inputs and outputs, all with fan-in and fan-out of 1. A the basic concepts of reversible logic and introduces the
variety of basic reversible gates have been proposed in fundamental architecture of PPAs. Section III describes
the past three decades. Such gates are combined in a our approach in modeling the reversible Fredkin gate
cascade fashion using various complex synthesis methods based on CMOS transmission gates and discusses the
that aim to minimize garbage outputs and ancillary inputs tools we use. Section IV provides our experimental
[15]. The synthesis of quantum reversible circuits is results and we conclude in Section V.
generally regarded as a hard research problem. The
synthesis tools that have been developed so far are able to II. PRELIMINARIES
work only with relatively small (< 25 inputs) reversible
circuits. A. Reversible Logic
This paper presents a simplified synthesis and Classical logic circuits provide outputs that result in a
simulation approach for reversible circuits of moderate loss of information and hence, corresponding power
complexity. We use direct translation of the circuit dissipation. For example, an n-bit input decision circuit
VHDL description into virtual Fredkin gates. While our obtains a one-bit yes or no result from which there is no
approach is not suitable (nor is it intended) to replace the way to reconstruct the original input set. Landauer's
gate cascade based synthesis techniques for quantum principle states that the erasure of a single bit of
circuits, it enables us to obtain some preliminary insights information dissipates at least KBTIn2 energy, where KB is
into synthesis issues for future reversible circuits of Boltzmann's constant and T is the temperature [6, 20].
meaningful sizes. This places a firm theoretical lower bound on the power
Our goal is to investigate the cost and delay of addition consumption of computation based on information
circuits as they are implemented in our virtual reversible entropy. It prompted the development of reversible logic
logic and to compare the resulting reversible logic circuits by Bennet [2], Fredkin, Toffoli [7], and others.
circuits with their classic logic implementation. We use Reversible logic circuits allow the full reconstruction of
the QuartusII tool (from the Altera Corporation [1]) to the circuit's input information at any time from the output
synthesize and simulate the VHDL files representing since such circuits can be modeled as bijective functions.
reversible circuits.

1-4244-1280-3/07/$25.00 ©2007 IEEE 2007 IEEE Region 5 Technical Conference, April 20-21, Fayetteville, AR
 75

All quantum logic circuits are necessarily reversible circuit is comprised of generalized Tofolli gates with one
since the fan-in and fan-out of 1 characteristic occurs due to four control lines.
to the principle of conservation of matter and thus also Reversible logic synthesis techniques that create
obeys the theoretical elimination of energy loss. We note circuits such as the one shown in Fig. 2 are still at an
that the first computers based on molecular level quantum infancy stage and can currently tackle only small circuits.
devices are just recently beginning to be realized and Interested readers should refer to recent work by Shende
there exists an intense research interest for the future of et al. [17], Kemtopf [10], Iwama et al. [9], and the
computing [16]. Adiabatic circuits are based on "MMD" template based synthesis by Miller et al. [15].
traditional CMOS technology that achieve ultra low Such synthesis techniques are not mature enough to
power loss due to reversibility. Lim et al. [13] produced a implement complex arithmetic circuits such as the PPAs
16-bit Carry-Lookahead adder employing Reversible we focus on here.
Energy Recovery Logic (RERL), which is a dual-rail
adiabatic logic style. While the RERL device is not a full ab
implementation of reversible logic, it uses partial
reversible features which contribute to the achievement of d

low power loss.

A variety of basic reversible gates have been proposed
that are realizable using quantum devices including the b
Toffoli, Fredkin, Controlled-NOT, Controlled-V, and I d
controlled V+. The use of Toffoli and Fredkin gates
shown in Fig. 1 illustrate how common classical
Fig. 2. The 5-variable hwb Function Implemented as a Cascade of
functions (NAND, AND, NOT, and fan-out duplication) Generalized Toffoli Gates
may be implemented. It is clear that once the NAND gate
or the equivalent set of AND and NOT gates are B. Prefix Parallel Adders
achievable, any arbitrary logic function can be Research in binary adders focuses on the problem of fast
implemented. Note that these implementations require the carry generation. A naive adder circuit implementation is
extra cost of auxiliary inputs (also called ancilla inputs), the Carry Ripple Adder (CRA), where the carry
which are crucial to the operation of the gates. For information propagates linearly along the entire structure
example, the Fredkin NOT and Fan-out implementation of full adders. As a result, while the CRA achieves the
uses only one input for the input variable x, while the lowest cost (size) of 0(n), its operation is very slow, with
remaining gate inputs become ancillary inputs, initialized a worst case delay of 0(n), where n is the number of
to either 0 or 1. added bits. We note that in quantum logic it is still
desirable to minimize cost (the number of gates) but the
a x Im x underlying reason is to reduce the possibility of
G c+ ab 1 *xyW 0 0+ 1X-x decoherence rather than delay minimization as is the case
Toffoli gate NAND imptementation Fan-ut Implemenion in classical logic circuit implementations.
(2 Copis of x) The parallel prefix adder suggested by Ladner and
a F aXbFac F
x
Fischer [11] in 1980 pioneered a stream of solutions that
b -
Fradkin gate
b + ab a+ae 1 3
AND implmentaUon NOT and Fan-out
x treat the carry generation problem as a prefix
computation.
Implemerntalon Prefix computation deals with computing compositions
Fig. 1. Classical Logic Functions using the Toffoli and Fredkin of operators. The composition operator * must be
Reversible gates associative, that is
Since the number of outputs for reversible logic gates
must equal the number of inputs, we find that reversible (x *y) * X * (y *z). (1)
circuits can create a large number of unused or "garbage"
outputs. Therefore, a major constraint in the synthesis, The prefix computation problem can be defined as
specification, and simulation of quantum circuits is the follows:
need to minimize the garbage outputs and the ancillary Given a set S and an associative composition operator
inputs. *: S x S-*S with input xo, xl,..., x,-l, compute
Research efforts attempt to develop techniques to yo.y-Y S so that yo= x Oand yi=:xo*XI * x2 k... *xi.
synthesize reversible quantum circuits using a cascade of By the above definition, it is clear that yi= yi- * xi.
gates like the example shown in Fig. 2. This circuit is the
5-variable hidden weighted bit "hwb5tc.tfc" benchmark
from Maslov's benchmarks web page and was captured
using Maslov's Reversible Circuit Viewer [14]. The

1-4244-1280-3/07/$25.00 ©2007 IEEE 2007 IEEE Region 5 Technical Conference, April 20-21, Fayetteville, AR
 76

Fig. 3b illustrates schematically how Pk(n) is created

recursively at level k of a PPA. It can be seen that each
V / additional level (increase in k) will increase the depth of
the circuit. Ladner and Fischer found that Pk(n) solves
the general prefix problem in parallel for n inputs with

Depth (delay) = D(Pk(n)) < K+ log2n (3)

Fig. 2. Parallel prefix product with associative operator *
and
Fig. 2 demonstrates a simple product circuit that
computes, in a parallel prefix fashion, the following set of Cost (size) = C(Pk(n)) < 2(2+1/2k) n - 4 (4)
values:
X1 *X2 *X2 *X3 *X2 for n > 1 and 0 < K < log2n. Therefore, the parallel
XI *X2 *X2 *X3 prefix computation has a delay of 0(log2n) and size of
XI *X2 O(n). While asymptotically the O(n) size is similar to
X2 *X3 (2) that of the CRA, the resulting delay is significantly less
[1 1].
Following the discussion in [11] we demonstrate how The PPA quickly dominated adder design, with various
the general parallel prefix operation Pk(n) is performed on architectures proposed by Brent and Kung [3], Kogge and
a set of n-inputs at the k level. Fig. 3a shows how PO(n) is Stone, Knowels [18], Han and Carlson, and more [8].
constructed recursively from P1(n12) and Po(nI2). The Interested readers also are referred to the detailed
left recursive construction P1(n12) has its' subscript k discussion in [5].
equal to 1 since it is connected in the second level to
Po(nI2). A,P G

(nt2) (n12) A

P1(nt) P,2n/) a. White Processor b. Black Processor

............
.........
.
...........
a. The First Recursive Step
n np s .
.............F. 4d

I~ ~~ ~~~~~~G,P PI GIIP1
XGYA G3P -12 I, b

| I ___~~~~~~~laot rulesl sutale fo exstn Vl S desig

As we were looking for a PPA architecture that is
b.l The RecursiverSte atd Levels kP
suitable for our demonstration of a virtual simulation of

3~.The RecursiveSteps ParaLvel

Fig. o h PrfxCmptto methodology, this architecture provides a consistent

1-4244-1280-3/07/$25.00 ©2007 IEEE 2007 IEEE Region 5 Technical Conference, April 20-21, Fayetteville, AR
 77

fanout of one on all outputs. This single fanout is crucial conveniently accepts various formats of design source
for reversible logic and thus seemed to be a good files, including standard VHDL and Verilog descriptions.
candidate for our study. The source files are synthesized into an RTL database,
A simplified illustration of the Brent-Kung PPA is which is then optimized and minimized for target FPGA
shown in Fig. 4, showing only the carry computation of devices. A convenient feature of the Quartus II program
the most significant carry bit during an 8-bit addition. for our research purposes is the ability to view RTL data
The carry calculation uses two sub-functions, g (carry priorto the optimization and minimization step.
generate) and p (carry propagate). The architecture uses We first modeled and implemented the basic Fredkin
two types of nodes dubbed the white and black gate using CMOS transmission gates as shown in Fig. 5.
processors. The white processor (Fig. 4a) is merely a VHDL implementation of the transmission gate is not a
routing node, with Gout=Gin and Pout=Pin. The black trivial matter [12]. We found that the approximation of a
processor performs the following computation: one-way transmission gate using the built-in Altera "TRI"
primitive is useful for our application.
Gout = Gin GiPin )5
nI .. .. .. .. .. .. .. .. .. .. .. .. . . . .

................................................................~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~..............................................................
C1"''''''''''' W ......
The Brent-Kung PPA design incurs a cost (size) of 0(n)
and exhibits a delay of 0og2n), where n is the number 10i Oil

of bits in the addition function. The ease of i103 O

implementation made it one of the first popular PPAs.

A~~~~~~~~~~~~~~~~~~~~~~~
III. OUR APPROACH
,,.....,,,,,..................................
Li,,
~ ~ ~ ~~
nT ~ ~ ~ ~ I TT) AII knT AI.w AA
rn .. I lh
;. FRE~D[KhIN AT1E IMPEMEN11EATION!WITH1T1 ANSNII11SONN4ATE. . .
In this paper we are concerned with a virtual
implementation of reversible circuits that use a direct Fig. 5. VHDL Model of a Fredkin Gate
translation of relatively complex binary functions into
circuits composed of Fredkin reversible gates. We note Zimmerman's PhD dissertation [19] on PPAs is an
that the Fredkin gate forms a complete set (with excellent research resource. He developed a
constants) so that any Boolean function can be realized comprehensive VHDL library for the implementation and
with only Fredkin gates. Since a classical logic n-bit PPA investigation of various PPA architectures. The
requires 2n inputs and n outputs (neglecting the carry-in Zimmerman PPA VHDL library is parameterized to allow
and the carry-out bits), a reversible counterpart will for the synthesis of adders with various data widths. His
require at least 2n variables or lines. Current reversible web site also includes a graphic interface applet that
logic synthesis based on gate cascading reported various produces graphical representations of various PPA
size limits of 8-25 varaibles [15]. In fact very few architectures.
benchmarks for reversible circuits with more than 25 _
variables are listed in the Maslov page[14]. Therefore, it Simulation mode: Timing
is fair to assume that 32 and 16 bit adders are beyond the
scope of current reversible logic synthesis based on gate -Maester Time Bar: 20.0 ns Pointer: 4.14 nsInteriaI:

pP 10.0 ns 20.0 ns 30.0 ns 60.0 ns

cascading. Therefore, we follow a direct translation Nam l 20.0 ns 40.0 ns
+1%
50.0 ns 7

approach similar to the work in [4]. This results in an 1 11 1

output VHDL file that is ready for Field Programmable B ________ 0 =
Gate Array (FPGA) implementation. The emphasis is on M s 11000100 10000000 110101
circuit regularity as opposed to emphasis on minimization
of the number of garbage outputs and ancillary inputs that
is very crucial in the synthesis of reversible logic circuits. Fig. 6. Simulation of 8-bit Brent-Kung PPA Implemented with Fredkin
We recognized a priori that our results will include a Gates
large number of such garbage outputs and ancillary
inputs, and are therefore useful only for the purpose of We modified the Zimmerman VHDL files to create the
virtual implementation in our current investigation. Our Brent-Kung PPA using our Fredkin gate models. We
implementation maintains direct correlation between the used direct translation by replacing each original standard
sub-modules of the reversible result to their standard logic equation with a corresponding Fredkin
logic counterpart. implementation corresponding to the mappings in Fig. 1.
The Altera Corporation's Quartus II software is a The resulting files were then used as input to the Quartus
comprehensive suite oftools for the synthesis, simulation, II tool for synthesis and simulation. Fig. 6 shows the
and implementation of complex logic circuits. It results of the timing simulation of our 8-bit

1-4244-1280-3/07/$25.00 ©2007 IEEE 2007 IEEE Region 5 Technical Conference, April 20-21, Fayetteville, AR
 78

implementation of the reversible Brent-Kung PPA. This errors occurring during the design decomposition into
simulation tool was useful for debugging translation Fredkin gates.

| L | HRevLog... I j Fredkin.... I0 RHL arith_. | RL Prefi... Coompilati... RL_Add|.. Simulatio... RevL

D evice: E P2OK3OE T C1 44-1

Al113~~~~~~N2 _ nI Mm m mm:. [3

4] Nl
41B[4]1" M rIC cm
V iDATA
ht D3 130 1 1 1 1 1 1 1 10 1 l 1g
V.K
I

Fig. 7. Place and Route Map of a 16-bit Brent-Kung PPA

Our research methodology was to compare the size and translation process, it is of course undesirable for our size
the delay simulation results between reversible and comparison purposes. This problem was avoided with the
standard logic versions of the Brent-Kung PPA of various RTL viewer which allows us to view the non-optimized
sizes. An interesting pitfall of our approach quickly VHDL files and to manually count the number of Fredkin
appeared when we tried to place and route the resulting gates required in order to compare sizes.
synthesis of both reversible and classic logic versions into
Altera's FPGA chips. Our motivation was to use the IV. EXPERIMENTAL RESULTS
number of Logic Element (LE) units reported at the end
of device compilation as a measure of size [1]. Fig. 7 We obtained our initial results shown in Table 1 using
shows the Place and Route map result when a reversible the LB count provided by the Quartus II compilation
16-bit Brent-Kung PPA is implemented in an Altera reports for operand sizes of 4, 8, 16, 32, and 64. As
EP2OK3OE
pha rse.attrns FPGA device. Each
outthatoogthe small square
oticmizatio phae within
simplthe discussed
16d in the
48nsato 71ces previous
72i section,nesrbefrorsz
fcus there is a loss of
chip map represents
covetste rever
siblel o
onegicn
LE unit.
fsles baketo aevesimilaset ofd information due
32prioprpss to
96 the
103 optimization
lewa and
9 9 minimization
iewihhof
When we placed and routed comparable reversible and both the reversible and the standard logic source files.
standard logic
optimized versions
weqainsw same operand
ofwereobained
thaedto frotsizethePPAs, the
rsutandard This results
rqieinodrt LE counts for each operand
in very similaropreszs
compilation tool reported a similar number of LBs (see size comparison.
logcumpefLolementain
Table 1). This clearlyWhLE)thitsinefacte vaiattes loss
indicates an information our TABLE I
problem since the extra logic required by the reversible INFORMATION Loss DUE TO PLACE AND ROUTE OPTIMIZATION OF TBlE RTL
circuits must result with more size. It seems that the DATA
problem lies in the optimization and minimization phase
2420K synthesis
0E3FP$GAoperation OPERAND REVERSIBLE LOGIC STANDARD LOGIC
ofEP the ©2vice
0 IEEEh
that the design undergoes 2007l IEEEr Tics5hSIZE
Region echnica
N
Conference,s Aprtilo2-2,
PINS IN LE UNITS
Fayetteisalle, AR
IN LE UNITS
within the Quartus,~II tool prior to the Place & Route 4 12 16 18
 79

Fig. 8 demonstrates the RTL viewer display for the 8-bit Cost based on RTL viewer
reversible Brent-Kung PPA. Each of the small square
elements represents a Fredkin gate. The large square is a 600
higher hierarchy sub-circuit which is comprised of 50
additional Fredkin gates. During the tedious manual
counting process, we must analyze all such sub-circuits in s30JaStandard Logic
order to accurately count all the Fredkin gates of the E 200 *m Reversible Logic
z10
benchmark. Similar efforts are needed in counting the
classical gates in the RTL views of the standard logic 4 8 16 32
implementations. It should be noted that other Operand size in bits
commercial modules for the Quartus II, like the Mentor
Graphics Leonardo Spectrum tool, allow users to treat a
Fig. 9. Comparison of Number of Fredkin and Classical Logic Gate
module as a black box. Such a tool can be used to Requirements for each Operand Wordsize
eliminate the tedious manual counting process. However,
this tool was not available to us during this research. Fig. 9 illustrates the size comparison. As predicted by
Table 2 summarizes our results for operand sizes of 4, 8, equation (4), the size grows linearly with respect to the
16, and 32. Here we see a consistent size cost increase operand size increase for both implementations. Of
when comparing the reversible and standard logic course, additional results with larger circuits will be
implementations. The I/O count column relates only to needed to confirm this trend beyond our current range of
the lines connected to the FPGA pads for time delay 64 bits. The number of Fredkin gates in the reversible
simulation. Currently our interface to the Altera tool does implementations seems to be about two times that of the
not provide an automatic means to count the internally implementation using classical logic gates.
unused inputs and outputs required by the Fredkin gates. Approximating the silicon size of a Fredkin gate to be
Since our simplified translation synthesis technique does about twice that of a standard logic gate, we conclude that
not minimize these extra inputs and outputs, a rough our reversible virtual implementations require about four
empirical estimate for the total I/O is approximately 2.5 times the cost of the standard logic implementations.
times the number of the Fredkin gates in addition to the
actual pad I/Os listed in the second column of Table 1.
Time delay at the I/O pads
100

11Standard Logic
Reversible Logic

1 0,
8 16 32 64
Operand size in bits

Fig. 10. Comparison of Time Delay Results for Reversible and Classical
ElaL 1 11 Logic Implementations

Using the Quartus II simulation tool, we have compared

the time delay for the reversible and standard logic
Fig. 8. The RTL Viewer Output for the 8-bit Brent-Kung PPA of Fig. 6 implementation for different operand sizes. The results
appear in Fig. 10 and they generally follow the expected
O(log2n) time for the Brent-Kung PPA in (3). There is a
slight delay overhead for our reversible virtual
TABLE2 implementations. While these results are important to
REVERSIBLE AND STANDARD LOGIC COMPARISON BY TBE RTL VIEWER validate our model, the actual delay with future quantum
Operand I/O Reversible Logic Standard Logic circuits are likely to exhibit different variances.
Size N pins in Fredkin Gates gates
4 12 53 26 V. CONCLUSIONS
8 24 120 62

32 96 547 3312 In view of the small size limitation of current gate

cascade synthesis tools for reversible logic, we
demonstrate a simplified synthesis technique based on

1-4244-1280-3/07/$25.00 ©2007 IEEE 2007 IEEE Region 5 Technical Conference, April 20-21, Fayetteville, AR
 80

direct logic block translation into reversible gates. While [11] R. Ladner and M. Fischer, "Parallel prefix computation", J Assoc.
our approach clearly cannot achieve the efficient Comp. Mach., Vol 27, pp. 831-838, 1980.
[12] S. S. Leung, "Behavioral modeling of transmission gates in
synthesis of the gate cascade synthesis, It allows us to VHDL", In Proceedings of the 26th ACM/IEEE Conference on
peek into the behavior of moderately complex reversible Design Automation, June 1989, pp 746-749.
arithmetic circuits such as the Brent-Kung PPA. [13] J. Lim, D.-G. Kim, and S.-I. Chae, "A 16-bit Carry-Lookahead
Comparison of our virtual reversible logic Adder using Reversible Energy Recovery Logic for ultra-low-
Complemetarison
implementation of of the Brent and Kung PPA with theenergy systems", IEEE Journal of Solid-State Circuits, Vol. 34,
the Brent and Kung PPA with the No. 6, pp. 898-903, June 1999.
standard logic implementation shows that it still follows [14] D. Maslov. Reversible logic synthesis benchmarks page. Online:
the 0(log2n) delay and 0(n) cost of the standard logic http://www.cs.uvic.ca/-dmaslov/, Nov. 15, 2005.
implementation. Due to the complexity of the Fredkin [15] D. M. Miller, D. Maslov, and G. W. Dueck. "A transformation
based algorithm for reversible logic synthesis". In Proceedings of
gate as compared to a standard logic gate, the cost of our the Design Automation Conference, 318-323 June 2003.
reversible logic implementation is roughly four times that [16] M.A. Nielsen and I.L. Chuang, Quantum Computation and
of the standard logic implementation. Qunatum Information, Cambridge University Press, 2000.
This result demonstrates how a state-of-the-art [17] V. V. Shende, A. K. Prasad, I. L. Markov, and J. P. Hayes,
commercial platformn*nlike
commercial
platfo like the
the Quartus
Quartus 11
II can be
be adapted toyg
adapted to
can "Synthesis of reversible logic circuits" IEEE Transactions on
Computer-Aided Design of Integrated Circuits and Systems, Vol.
investigate futuristic technology like reversible logic. In 22, No. 6, pp. 710-722, June 2003.
particular, we show how to overcome the loss of [18] M. M. Ziegler and M. R. Stan, "A unified design space for regular
information due to optimization by using the RTL viewer. Parallel Prefix Adders", In Proceedings of the Conference on
More importantly, the problems we encountered in using Design, Automation and Test in Europe - Volume 2, Feb 2004,
IEEE Computer Society.
this tool for synthesizing and modeling reversible logic [19] R. Zimmermann, Binary adder architectures for cell-based VLSI
circuits underscores the need for the development of new and their synthesis, PhD thesis, Swiss Federal Institute of
synthesis and simulation tools specifically for quantum Technology (ETH) Zurich, Hartung-Gorre Verlag, 1998. Online:
device based circuits. Since classical logic synthesis http://www.iis.ee.ethz.chHzimmi/.
[20] R. Landauer, "Irreversibility and Heat Generation in the Computing
tools exploit characterisics such as reconvergent fanout Process ", IBM J. Research and Development, vol. 3, pp. 183-19 1,
(which is not peirmissible in quantum circuits) and the July 1961.
optimization techniques automatically remap low-level
structures into those inappropriate for quantum logic,
altogether new approaches for quantum logic CAD tools
are required.
Future work includes the investigation of the use of
Toffoli gates instead of (or together with) Fredkin gates
and will involve arithmetic architectures other than PPAs.
REFERENCES
[1] Altera Corporation, Quartus II Software. Available online:
http://www.altera.com/products/software/products/quartus2/qts-
index.html.
[2] C.H. Bennett, "Logical reversibility of computation,"IBM, J. Res.
Dev., Vol. 17, No. 6, pp. 525-532, 1973.
[3] R. P. Brent and H. T. Kung, "Regular layout for parallel adders",
IEEE Trans. Comp., Vol. C 31, no. 3, pp. 260-264, 1982.
[4] J.W. Bruce, M.A. Thornton, L. Shivakumaraiah, P.S. Kokate, and
X. Li, "Efficient adder circuits based on a conservative reversible
logic gate", In Proceedings of the IEEE Computer Society Annual
Symposium on VLSI, pp. 83-88,April 2002
[5] M. D. Ercegovac and T. Lang, Digital Arithmetic, Morgan
Kaufmann, 2004.
[6] R. Feynman, "Quantum mechanical computers," Optics News, vol.
ll,pp. 11-20, 1985.
[7] E. Fredkin and T. Toffoli, "Conservative Logic," Int, J Theoretical
Physics, Vol. 21, Nos. 3/4, pp. 219-253, 1982.
[8] Z. Huang and M. D. Ercegovac "Effect of wire delay on the design
of prefix adders in deep-submicron technology", Signals, Systems
and Computers, 2000. Volume 2, pp. 1713 - 1717.
[9] K. Iwama, Y. Kambayashi and S. Yamashita, "Transformation rules
for designing CNOT-based quantum circuits", In Proceedings of
the Design Automation Conference, 2002, June 2002, pp. 419-425.
[10] P. Kerntopf, "A new heuristic algorithm for reversible logic
synthesis", In Proceedings of the 41st Annual Conference on
Design Automation, pp. 835-837, June 2004.

1-4244-1280-3/07/$25.00 ©2007 IEEE 2007 IEEE Region 5 Technical Conference, April 20-21, Fayetteville, AR