IEICE TRANSACTIONS on Information
A Lower Bound on the Gate Count of Toffoli-Based Reversible Logic Circuits
Summary :
We present a new lower bound on the number of gates in reversible logic circuits that represent a given reversible logic function, in which the circuits are assumed to consist of general Toffoli gates and have no redundant input/output lines. We make a theoretical comparison of lower bounds, and prove that the proposed bound is better than the previous one. Moreover, experimental results for lower bounds on randomly-generated reversible logic functions and reversible benchmarks are given. The results also demonstrate that the proposed lower bound is better than the former one.
- Publication
- IEICE TRANSACTIONS on Information Vol.E97-D No.9 pp.2253-2261
- Publication Date
- 2014/09/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2013LOP0013
- Type of Manuscript
- Special Section PAPER (Special Section on Multiple-Valued Logic and VLSI Computing)
- Category
- Reversible/Quantum Computing
Authors
Takashi HIRAYAMA
Iwate University
Hayato SUGAWARA
Iwate University
Katsuhisa YAMANAKA
Iwate University
Yasuaki NISHITANI
Iwate University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Takashi HIRAYAMA, Hayato SUGAWARA, Katsuhisa YAMANAKA, Yasuaki NISHITANI, "A Lower Bound on the Gate Count of Toffoli-Based Reversible Logic Circuits" in IEICE TRANSACTIONS on Information,
vol. E97-D, no. 9, pp. 2253-2261, September 2014, doi: 10.1587/transinf.2013LOP0013.
Abstract: We present a new lower bound on the number of gates in reversible logic circuits that represent a given reversible logic function, in which the circuits are assumed to consist of general Toffoli gates and have no redundant input/output lines. We make a theoretical comparison of lower bounds, and prove that the proposed bound is better than the previous one. Moreover, experimental results for lower bounds on randomly-generated reversible logic functions and reversible benchmarks are given. The results also demonstrate that the proposed lower bound is better than the former one.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2013LOP0013/_p
Copy
@ARTICLE{e97-d_9_2253,
author={Takashi HIRAYAMA, Hayato SUGAWARA, Katsuhisa YAMANAKA, Yasuaki NISHITANI, },
journal={IEICE TRANSACTIONS on Information},
title={A Lower Bound on the Gate Count of Toffoli-Based Reversible Logic Circuits},
year={2014},
volume={E97-D},
number={9},
pages={2253-2261},
abstract={We present a new lower bound on the number of gates in reversible logic circuits that represent a given reversible logic function, in which the circuits are assumed to consist of general Toffoli gates and have no redundant input/output lines. We make a theoretical comparison of lower bounds, and prove that the proposed bound is better than the previous one. Moreover, experimental results for lower bounds on randomly-generated reversible logic functions and reversible benchmarks are given. The results also demonstrate that the proposed lower bound is better than the former one.},
keywords={},
doi={10.1587/transinf.2013LOP0013},
ISSN={1745-1361},
month={September},}
Copy
TY - JOUR
TI - A Lower Bound on the Gate Count of Toffoli-Based Reversible Logic Circuits
T2 - IEICE TRANSACTIONS on Information
SP - 2253
EP - 2261
AU - Takashi HIRAYAMA
AU - Hayato SUGAWARA
AU - Katsuhisa YAMANAKA
AU - Yasuaki NISHITANI
PY - 2014
DO - 10.1587/transinf.2013LOP0013
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E97-D
IS - 9
JA - IEICE TRANSACTIONS on Information
Y1 - September 2014
AB - We present a new lower bound on the number of gates in reversible logic circuits that represent a given reversible logic function, in which the circuits are assumed to consist of general Toffoli gates and have no redundant input/output lines. We make a theoretical comparison of lower bounds, and prove that the proposed bound is better than the previous one. Moreover, experimental results for lower bounds on randomly-generated reversible logic functions and reversible benchmarks are given. The results also demonstrate that the proposed lower bound is better than the former one.
ER -
English
