LUT BASED FREDKIN GATE
DOI:
https://doi.org/10.15588/1607-3274-2020-1-5Keywords:
Quantum Computing, Logic Function, Fredkin Gate, Shannon decomposition or Boolean factorization.Abstract
Context. The concept of existing computers when achieving nanoscale hardware has almost exhausted itself. This also applies to computing power and related energy costs. Reversible computing, for example billiard-ball computer, is the base model of the quantum computing which are considered to be the prospect of IT technology. Billiard-ball computing is energy-effective computing or green computing. Base of such paradigm are special logic gates. However, the mathematical apparatus for creating such computers has not yet been fully developed. The problem is that for new reversible elements that have a one-to-one correspondence between inputs and outputs, the application of well-known methods of analysis and synthesis encounters certain difficulties. So, for example, it is forbidden to use branching, which significantly complicates the synthesis. Reversible elements should provide signal transmission in the forward and reverse directions, which is in principle feasible in binary logic based on tri-states buffers, but significantly complicates the device, increases the crystal area and power consumption, which they are designed to reduce.
Objective. The goal of the work is the analysis of the functionally complete reversible gates that named Toffoli gate, Fredkin gate, the analysis of the binary full adder, based on Fredkin gates and to design method for circuits based proposed gate.
Methods. Analysis of the digital circuits with Boolean algebra. Synthesis digital circuits with proposed decomposition method. Design Fredkin gate in term of the FPGA’s Look up Table. Simulation of proposed element in the system NI Multisim by National Instruments Electronics Workbench Group.
Results. Analysis of the full adder based on Fredkin gates. Synthesis method of the reversible circuits based on Fredkin gates. LUT based Fredkin gate and it simulation.
Conclusions. The conducted studies allows us to build circuits based on Fredkin gates from proposed novel elements.
References
Quantum Gates – [Electronic resource]. Access mode: https://web.archive.org/web/20150104033422/http://web.stanford.e du/~rsasaki/AP226/AP226.html
Morita K. Reversible Logic Gates. [Electronic resource]. Access mode: https://link.springer.com/chapter/10.1007%2F978-4-43156606-9_4
Reversible Computing. [Electronic resource]. Access mode: http://web.eecs.utk.edu/~bmaclenn/Classes/494-594-UCF14/handouts/LNUC-II.C.3-9.pdf
Lala P. K., Parkerson J. P., Chakraborty P. Adder Designs using Reversible Logic Gates. [Electronic resource]. Access mode: https://pdfs.semanticscholar.org/f782/40586e5c74688c439784498d 8bd31bab866c.pdf
Rangaraju H. G, Venugopal U., Muralidhara K. N., Raja K. B. Low Power Reversible Parallel Binary Adder/Subtractor. [Electronic resource]. Access mode: https://arxiv.org/ftp/arxiv/papers/1009/1009.6218.pdf
Xu S. Reversible Logic Synthesis with Minimal Usage of Ancilla Bits. [Electronic resource]. Access mode: https://arxiv.org/pdf/1506.03777.pdf
Mubin U. H., Zarrin T. S., Hafiz M. An Improved Design of a Reversible Fault Tolerant LUT-based FPGA, 29th International Conference on VLSI Design and 2016 15th International Conference on Embedded Systems, VLSID-2016, 4–8 Jan. 2016: proceedings.
Fredkin E., Toffoli T. Conservative logic, International Journal of Theoretical. Physics, 21, 3/4, p. 219–253, 1982.
Patel1 R. B., Ho J., Ferreyrol1 F., Ralph T. C., Pryde G. J. A quantum Fredkin gate [Electronic resource]. Access mode: https://advances.sciencemag.org/content/2/3/e1501531
Rosanna M., Prasanna M., Amudha S. Implementation of testable reversible sequential circuit on FPGA, 2015 International Conference on Innovations in Information, Embedded and Communication Systems, ICIIECS–2015, 19–20 March 2015: proceedings. Coimbatore, India, IEEE, 2015, pp. 145–150. DOI: 10.1109/ICIIECS.2015.7192888
Himanshu T., Vinod A. P. Design of Reversible Sequential Elements With Feasibility of Transistor Implementation, 2007 IEEE International Symposium on Circuits and Systems, 27–30 May 2007: proceedings. New Orleans, LA, USA: IEEE, 2007, pp. 121– 126. DOI: 10.1109/ISCAS.2007.378815
Yelekar R. P., Sujata S. C. Design of sequential circuit using reversible logic, IEEE-International Conference On Advances In Engineering, Science And Management, ICAESM–2012, 30–31 March 2012: proceedings. Nagapattinam, Tamil Nadu, India, IEEE, 2012, pp. 321–326
Kiran J., Binu K. M. Implementation of a FIR filter model using reversible Fredkin Gate, 2014 International Conference on Control, Instrumentation, Communication and Computational Technologies, ICCICCT–2014, 10–11 July 2014: proceedings. Kanyakumari, India, IEEE, 2014, pp. 125–132. DOI: 10.1109/ICCICCT.2014.6993048
Dueck G. W. Maslov D., Miller D.M. Transformation-based synthesis of networks of Toffoli/Fredkin gates, Canadian Conference on Electrical and Computer Engineering. Toward a Caring and Humane Technology, CCECE –2003, 4–7 May 2003: proceedings. Montreal, Quebec, Canada, IEEE, 2003, pp. 211–214 DOI: 10.1109/CCECE.2003.1226380
Kiran D. K., Akalpita L. K. Implementation of 4-Tap FIR Filter Using Fredkin Gate, International Journal of Engineering Science and Computing, June, 2016, Volume 6, Issue No. 6, pp. 6504–6508. DOI 10.4010/2016.1563
Himanshu T., Ranganathan N., Kotiyal S. Design of Testable Reversible Sequential Circuits, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, July 2013, Volume 21, Issue No 7, pp. 1201–1209. DOI: 10.1109/TVLSI.2012.2209688
Shannon C. E. The synthesis of two-terminal switching circuits [Electronic resource]. Access mode: https://ieeexplore.ieee.org/document/6771698
Tyurin S. F., Grekov A. V. Study of the multy input LUT complexity, Radio Electronics, Computer Science, Control, 2018, No. 1, pp. 14–21. DOI: 10.15588/1607-3274-2018-1-2
Tyurin S. F. Investigation of a Hybrid Redundancy in the FaultTolerant Systems, Radio Electronics, Computer Science, Control, 2019, No. 2, pp. 23–33. 10.15588/1607-3274-2019-2-3
Tyurin S. F. LUT’s Sliding Backup, IEEE transactions on device and materials reliability, 2019, Published, MAR, Vol. 19, Issue 1, pp. 221–225. DOI: 10.1109/TDMR.2019.2898724
Carmichael C. Triple Module Redundancy Design Techniques for Virtex FPGAs [Electronic resource]. Access mode: https://www.xilinx.com/support/documentation/application_notes/x app197.pdf
El-Maleh A. H., Al-Yamani A., Al-Hashimi B. M. Transistor-Level Defect Tolerant Digital System Design at the Nanoscale. Research Proposal Submitted to Internal Track Research Grant Programs [Electronic resource]. Access mode: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.474.3844 &rep=rep1&type=pdf
Mead C. A., Conway L. Introduction to VLSI Systems. [Electronic resource]. Access mode: https://www.researchgate.net/publication/234388249_Introduction_t o_VLSI_systems
Downloads
How to Cite
Issue
Section
License
Copyright (c) 2020 S. F. Tyurin
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Creative Commons Licensing Notifications in the Copyright Notices
The journal allows the authors to hold the copyright without restrictions and to retain publishing rights without restrictions.
The journal allows readers to read, download, copy, distribute, print, search, or link to the full texts of its articles.
The journal allows to reuse and remixing of its content, in accordance with a Creative Commons license СС BY -SA.
Authors who publish with this journal agree to the following terms:
-
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License CC BY-SA that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
-
Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
-
Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
