DOI: https://doi.org/10.15588/1607-3274-2020-1-5

LUT BASED FREDKIN GATE

S. F. Tyurin

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. 


Keywords


Quantum Computing, Logic Function, Fredkin Gate, Shannon decomposition or Boolean factorization.

Full Text:

PDF

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


GOST Style Citations


1. Quantum Gates – [Electronic resource]. – Access mode: https://web.archive.org/web/20150104033422/http://web.stanford.e du/~rsasaki/AP226/AP226.html

2. Morita K. Reversible Logic Gates. [Electronic resource] / K. Morita. – Access mode: https://link.springer.com/chapter/10.1007%2F978-4-431-56606-9_4

3. Reversible Computing. [Electronic resource]. Access mode: http://web.eecs.utk.edu/~bmaclenn/Classes/494-594-UCF14/handouts/LNUC-II.C.3-9.pdf

4. Lala P. K. Adder Designs using Reversible Logic Gates. – [Electronic resource] / P. K. Lala , J. P. Parkerson, P. Chakraborty. – Access mode: https://pdfs.semanticscholar.org/f782/40586e5c74688c439784498d 8bd31bab866c.pdf

5. Low Power Reversible Parallel Binary Adder/Subtractor. [Electronic resource] / [H. G. Rangaraju, U. Venugopal, K. N. Muralidhara, K. B. Raja]. – Access mode: https://arxiv.org/ftp/arxiv/papers/1009/1009.6218.pdf

6. S. Xu. Reversible Logic Synthesis with Minimal Usage of Ancilla Bits. [Electronic resource]. Access mode: https://arxiv.org/pdf/1506.03777.pdf

7. Mubin U. H. An Improved Design of a Reversible Fault Tolerant LUT-based FPGA / U. H. Mubin, T. S. Zarrin, M. Hafiz // 29th International Conference on VLSI Design and 2016 15th International Conference on Embedded Systems, VLSID-2016, 4–8 Jan. 2016: proceedings.

8. Fredkin E. Conservative logic. / E. Fredkin, T. Toffoli // International Journal of Theoretical. – Physics. – 21, 3/4. – P. 219– 253, 1982.

9. A quantum Fredkin gate [Electronic resource] / [R. B. Patel1, J. Ho, F. Ferreyrol1 et al.]. – Access mode: https://advances.sciencemag.org/content/2/3/e1501531

10. Rosanna M. Implementation of testable reversible sequential circuit on FPGA / M. Prasanna, S. Amudha // 2015 International Conference on Innovations in Information, Embedded and Communication Systems, ICIIECS–2015, 19–20 March 2015: proceedings. – Coimbatore, India: IEEE, 2015. – P. 145–150. DOI: 10.1109/ICIIECS.2015.7192888

11. Himanshu T. Design of Reversible Sequential Elements With Feasibility of Transistor Implementation / T. Himanshu, A. P. Vinod // 2007 IEEE International Symposium on Circuits and Systems, 27–3 0 May 2007: proceedings. – New Orleans, LA, USA: IEEE, 2007. – P. 121–126. DOI: 10.1109/ISCAS.2007.378815

12. Yelekar R. P. Design of sequential circuit using reversible logic / R. P. Yelekar, S. C. Sujata // IEEE-International Conference On Advances In Engineering, Science And Management, ICAESM – 2012, 30–31 March 2012: proceedings. – Nagapattinam, Tamil Nadu, India : IEEE, 2012. – P.321–326

13. Kiran J. Implementation of a FIR filter model using reversible Fredkin Gate / J. Kiran, K. M. Binu // 2014 International Conference on Control, Instrumentation, Communication and Computational Technologies, ICCICCT –2014, 10–11 July 2014: proceedings. – Kanyakumari, India: IEEE, 2014. – P. 125–132. DOI: 10.1109/ICCICCT.2014.6993048

14. Dueck G.W. Transformation-based synthesis of networks of Toffoli/Fredkin gates / G. W. Dueck, D. Maslov, D. M. Miller // 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. – P. 211–214. DOI: 10.1109/CCECE.2003.1226380

15. Kiran D. K. Implementation of 4-Tap FIR Filter Using Fredkin Gate / D. K. Kiran, L. K. Akalpita // International Journal of Engineering Science and Computing. – June 2016. – Volume 6, Issue No. 6. – P. 6504–6508. DOI 10.4010/2016.1563

16. Himanshu T. Design of Testable Reversible Sequential Circuits / T. Himanshu, N. Ranganathan, S. Kotiyal // IEEE Transactions on Very Large Scale Integration (VLSI). – 2013. – July Volume 21, Issue No. 7. – pp. 1201–1209. DOI: 10.1109/TVLSI.2012.2209688

17. Shannon C. E. The synthesis of two-terminal switching circuits [Electronic resource] / C. E. Shannon. – Access mode: https://ieeexplore.ieee.org/document/6771698

18. Tyurin S. F. Study of the multy input LUT complexity / S. F. Tyurin, A. V. Grekov // Radio Electronics, Computer Science, Control. – 2018. – № 1. – P. 14–21. DOI: 10.15588/1607-32742018-1-2

19. Tyurin S.F. Investigation of a Hybrid Redundancy in the FaultTolerant Systems // Radio Electronics, Computer Science, Control. – 2019. – № 2. – P. 23–33. 10.15588/1607-3274-2019-2-3

20. Tyurin S. F. LUT’s Sliding Backup. IEEE transactions on device and materials reliability. – 2019. – Published: MAR. – Vol. 19, Issue 1. – P. 221–225. DOI: 10.1109/TDMR.2019.2898724

21. 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

22. El-Maleh A. H. Transistor-Level Defect Tolerant Digital System Design at the Nanoscale. Research Proposal Submitted to Internal Track Research Grant Programs [Electronic resource] / A. H. ElMaleh, A. Al-Yamani, B. M. Al-Hashimi. – Access mode: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.474.3844 &rep=rep1&type=pdf

23. Mead C. A. Introduction to VLSI Systems / C. A. Mead, L. Conway. – [Electronic resource]. – Access mode: https://www.researchgate.net/publication/234388249_Introduction_t o_VLSI_systems







Copyright (c) 2020 S. F. Tyurin

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Address of the journal editorial office:
Editorial office of the journal «Radio Electronics, Computer Science, Control»,
National University "Zaporizhzhia Polytechnic", 
Zhukovskogo street, 64, Zaporizhzhia, 69063, Ukraine. 
Telephone: +38-061-769-82-96 – the Editing and Publishing Department.
E-mail: rvv@zntu.edu.ua

The reference to the journal is obligatory in the cases of complete or partial use of its materials.