The physical limitations of complementary metal-oxide semiconductor (CMOS) technology have led many researchers to consider other alternative technologies. Quantum-dot cellular automate (QCA), single electron tunneling (SET), tunneling phase logic (TPL), spintronic devices, etc., are some of the nanotechnologies that are being considered as possible replacements for CMOS. In these nanotechnologies, the basic logic units used to implement circuits are majority and/or minority gates. Several majority/minority logic circuit synthesis methods have been proposed. In this paper, we give a comparative study of the existing majority/minority logic circuit synthesis methods that are capable of synthesizing multi-input multi-output Boolean functions. Each of these methods is discussed in detail. The optimization priorities given to different factors such as gates, levels, inverters, etc., vary with technologies. Based on these optimization factors, the results obtained from different synthesis methods are compared. The paper also analyzes the optimization capabilities of different methods and discusses directions for future research in the synthesis of majority/minority logic networks.
2013 International Technology Roadmap for Semiconductors (ITRS). http://www.semiconductors.org
Lent, C.S., Tougaw, P.D., Porod, W. and Bernstein, G.H. (1993) Quantum Cellular Automata. Nanotechnology, 4, 49. https://doi.org/10.1088/0957-4484/4/1/004
Tougaw, P.D. and Lent, C.S. (1994) Logical Devices Implemented Using Quantum Cellular Automata. Journal of Applied Physics, 75, 1818-1825. https://doi.org/10.1063/1.356375
Lent, C.S. and Tougaw, P.D. (1997) A Device Architecture for Computing with Quantum Dots. Proceedings of the IEEE, 85, 541-557. https://doi.org/10.1109/5.573740
Porod, W. (1997) Quantum-Dot Devices and Quantum-Dot Cellular Automata. International Journal of Bifurcation and Chaos, 7, 2199-2218. https://doi.org/10.1142/S0218127497001606
Snider, G., Orlov, A., Amlani, I., Zuo, X., Bernstein, G., Lent, C., Merz, J. and Porod, W. (1999) Quantum-Dot Cellular Automata: Review and Recent Experiments. Journal of Applied Physics, 85, 4283-4285. https://doi.org/10.1063/1.370344
Walus, K., Jullien, G.A. and Dimitrov, V.S. (2003) Computer Arithmetic Structures for Quantum Cellular Automata. Conference Record of the 37th Asilomar Conference on Signals, Systems and Computers, Pacific Grove, CA, 9-12 November 2003, 1435-1439. https://doi.org/10.1109/ACSSC.2003.1292223
Oya, T., Asai, T., Fukui, T. and Amemiya, Y. (2002) A Majority-Logic Nanodevice Using a Balanced Pair of Single-Electron Boxes. Journal of Nanoscience and Nanotechnology, 2, 333-342. https://doi.org/10.1166/jnn.2002.108
Oya, T., Asai, T., Fukui, T. and Amemiya, Y. (2003) A Majority-Logic Device Using an Irreversible Single-Electron Box. IEEE Transactions on Nanotechnology, 2, 15-22. https://doi.org/10.1109/TNANO.2003.808507
Fahmy, H.A.H. and Kiehl, R.A. (1999) Complete Logic Family Using Tunneling- Phase-Logic Devices. Proceedings of the International Conference on Microelectronics, Kuwait City, November 1999, 153-156.
Nikonov, D.E. and Young, I.A. (2013) Overview of Beyond-CMOS Devices and a Uniform Methodology for Their Benchmarking. Proceedings of the IEEE, 101, 2498-2533. https://doi.org/10.1109/JPROC.2013.2252317
Miller, H.S. and Winder, R.O. (1962) Majority-Logic Synthesis by Geometric Methods. IRE Transactions on Electronic Computers, EC-11, 89-90. https://doi.org/10.1109/TEC.1962.5219329
Akers, S.B. (1962) Synthesis of Combinational Logic Using Three-Input Majority Gates. Proceedings of the Third Annual Symposium on Switching Circuit Theory and Logical Design, Chicago, IL, 7-12 October 1962, 149-158. https://doi.org/10.1109/FOCS.1962.16
Muroga, S. (1971) Threshold Logic and Its Applications. Wiley, New York.
Rumi, Z., Walus, K., Wang, W. and Jullien, G.A. (2004) A Method of Majority Logic Reduction for Quantum Cellular Automata. IEEE Transactions on Nanotechnology, 3, 443-450. https://doi.org/10.1109/TNANO.2004.834177
Walus, K., Schulhof, G., Jullien, G.A., Zhang, R. and Wang, W. (2004) Circuit Design Based on Majority Gates for Applications with Quantum-Dot Cellular Automata. Conference Record of the Thirty-Eighth Asilomar Conference on Signals, Systems and Computers, Pacific Grove, CA, 7-10 November 2004, 1354-1357.
Bonyadi, M.R., Azghadi, S.M.R., Rad, N.M., Navi, K. and Afjei, E. (2007) Logic Optimization for Majority Gate-Based Nanoelectronic Circuits Based on Genetic Algorithm. International Conference on Electrical Engineering, ICEE’07, Lahore, 11-12 April 2007, 1-5.
Rai, S. (2008) Majority Gate Based Design for Combinational Quantum Cellular Automata (QCA) Circuits. 40th Southeastern Symposium on System Theory, New Orleans, LA, 16-18 March 2008, 222-224. https://doi.org/10.1109/SSST.2008.4480225
Huo, Z., Zhang, Q., Haruehanroengra, S. and Wang, W. (2006) Logic Optimization for Majority Gate-Based Nanoelectronic Circuits. 2006 IEEE International Symposium on Circuits and Systems, Island of Kos, 21-24 May 2006, 1307-1310.
Zhang, R., Gupta, P. and Jha, N.K. (2007) Majority and Minority Network Synthesis with Application to QCA-, SET-, and TPL-Based Nanotechnologies. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 26, 1233-1245. https://doi.org/10.1109/TCAD.2006.888267
Kong, K., Shang, Y. and Lu, R. (2010) An Optimized Majority Logic Synthesis Methodology for Quantum-Dot Cellular Automata. IEEE Transactions on Nanotechnology, 9, 170-183. https://doi.org/10.1109/TNANO.2009.2028609
Wang, P., Niamat, M. and Vemuru, S. (2013) Minimal Majority Gate Mapping of Four-Variable Functions for Quantum-Dot Cellular Automata. In: Iniewski, K., Ed., Nanoelectronic Device Applications Handbook, CRC Press, Boca Raton, Florida, 263-280.
Mitchell, M. (1998) An Introduction to Genetic Algorithms. MIT Press, Cambridge, Massachusetts.
Holland, J.H. (1992) Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. U Michigan Press, Ann Arbor, Michigan.
Sentovich, E.M., Singh, K.J., Lavagno, L., Moon, C., Murgai, R., Saldanha, A., Savoj, H., Stephan, P.R., Brayton, R.K. and Sangiovanni-Vincentelli, A. (1992) SIS: A System for Sequential Circuit Synthesis. Technical Report No. UCB/ERL M92/41. University of California, Berkeley.
Wang, P., Niamat, M.Y., Vemuru, S.R., Alam, M. and Killian, T. (2015) Synthesis of Majority/Minority Logic Networks. IEEE Transactions on Nanotechnology, 14, 473-483. https://doi.org/10.1109/TNANO.2015.2408330
Orlov, A.O., Amlani, I., Toth, G., Lent, C.S., Bernstein, G.H. and Snider, G.L. (1999) Experimental Demonstration of a Binary Wire for Quantum-Dot Cellular Automata. Applied Physics Letters, 74, 2875-2877. https://doi.org/10.1063/1.124043
Orlov, A.O., Amlani, I., Kummamuru, R.K., Ramasubramaniam, R., Toth, G., Lent, C.S., Bernstein, G.H. and Snider, G.L. (2000) Experimental Demonstration of Clocked Single-Electron Switching in Quantum-Dot Cellular Automata. Applied Physics Letters, 77, 295-297. https://doi.org/10.1063/1.126955
Nikonov, D.E., Bourianoff, G.I. and Ghani, T. (2011) Proposal of a Spin Torque Majority Gate Logic. IEEE Electron Device Letters, 32, 1128-1130. https://doi.org/10.1109/LED.2011.2156379
Bourianoff, G.I. and Nikonov, D.E. (2011) Recent Progress, Opportunities and Challenges for Beyond CMOS Information Processing Technologies. ECS Transactions, 35, 43-53. https://doi.org/10.1149/1.3568847
Behin-Aein, B., Datta, D., Salahuddin, S. and Datta, S. (2010) Proposal for an All-Spin Logic Device with Built-In Memory. Nature Nanotechnology, 5, 266-270. https://doi.org/10.1038/nnano.2010.31
Behin-Aein, B., Sarkar, A., Srinivasan, S. and Datta, S. (2011) Switching Energy-Delay of All Spin Logic Devices. Applied Physics Letters, 98, Article ID: 123510. https://doi.org/10.1063/1.3567772
Mankalale, M.G. and Sapatnekar, S.S. (2016) Optimized Standard Cells for All-Spin Logic. ACM Journal on Emerging Technologies in Computing Systems (JETC), 13, 21. https://doi.org/10.1145/2967612
Krivorotov, I. and Markovic, D. (2011) STT Oscillators/Memory. MIND Annual Review and NRI Benchmarking Workshop, Notre Dame, IN, USA, 16-18.
Khitun, A. and Wang, K.L. (2005) Nano Scale Computational Architectures with Spin Wave Bus. Superlattices and Microstructures, 38, 184-200. https://doi.org/10.1016/j.spmi.2005.07.001
Bernstein, K., Cavin, R.K., Porod, W., Seabaugh, A. and Welser, J. (2005) Device and Architecture Outlook for beyond CMOS Switches. Proceedings of the IEEE, 98, 2169-2184. https://doi.org/10.1109/JPROC.2010.2066530
Klingler, S., Pirro, P., Bracher, T., Leven, B., Hillebrands, B. and Chumak, A.V. (2014) Design of a Spin-Wave Majority Gate Employing Mode Selection. Applied Physics Letters, 105, Article ID: 152410. https://doi.org/10.1063/1.4898042
Zografos, O., Raghavan, P., Amaru, L., Soree,′ B., Lauwereins, R., Radu, I., Verkest, D. and Thean, A. (2014) System-Level Assessment and Area Evaluation of Spin Wave Logic Circuits. 2014 IEEE/ACM International Symposium on Nanoscale Architectures (NANOARCH), Paris, 8-10 July 2014, 25-30. https://doi.org/10.1109/NANOARCH.2014.6880475
Khitun, A. and Wang, K.L. (2011) Non-Volatile Magnonic Logic Circuits Engineering. Journal of Applied Physics, 110, Article ID: 034306. https://doi.org/10.1063/1.3609062
Kostylev, M., Serga, A., Schneider, T., Leven, B. and Hillebrands, B. (2005) Spin- Wave Logical Gates. Applied Physics Letters, 110, Article ID: 153501. https://doi.org/10.1063/1.2089147
Amaru, L., Gaillardon, P.-E., Mitra, S. and De Micheli, G. (2015) New Logic Synthesis as Nanotechnology Enabler. Proceedings of the IEEE, 103, 2168-2195. https://doi.org/10.1109/JPROC.2015.2460377
Cowburn, R.P. and Welland, M.E. (2000) Room Temperature Magnetic Quantum Cellular Automata. Science, 287, 1466-1468. https://doi.org/10.1126/science.287.5457.1466
Zhu, J., Zhang, L., Dong, S. and Wang, E. (2013) Four-Way Junction-Driven DNA Strand Displacement and Its Application in Building Majority Logic Circuit. ACS Nano, 7, 10211-10217. https://doi.org/10.1021/nn4044854
Li, W., Yang, Y., Yan, H. and Liu, Y. (2013) Three-Input Majority Logic Gate and Multiple Input Logic Circuit Based on DNA Strand Displacement. Nano Letters, 13, 2980-2988. https://doi.org/10.1021/nl4016107
George, A.K. and Singh, H. (2016) Three-Input Majority Gate Using Spatially Localised DNA Hairpins. IEEE Transactions on NanoBioscience, 15, 928-938. https://doi.org/10.1109/TNB.2016.2623218
Schwierz, F. (2010) Graphene Transistors. Nature Nanotechnology, 5, 487-496. https://doi.org/10.1038/nnano.2010.89
Yang, H., Heo, J., Park, S., Song, H.J., Seo, D.H., Byun, K.-E., Kim, P., Yoo, I., Chung, H.-J. and Kim, K. (2010) Graphene Barristor, a Triode Device with a Gate- Controlled Schottky Barrier. Science, 336, 1140-1143. https://doi.org/10.1126/science.1220527
Miryala, S., Tenace, V., Calimera, A., Macii, E., Poncino, M., Amaru, L., De Micheli, G. and Gaillardon, P.-E. (2015) Exploiting the Expressive Power of Graphene Reconfigurable Gates via Post-Synthesis Optimization. 25th Great Lakes Symposium on VLSI (GLSVLSI), Pittsburgh, Pennsylvania, 20-22 May 2015, 39-44. https://doi.org/10.1145/2742060.2742098
Linn, E., Rosezin, R., Kugeler, C. and Waser, R. (2010) Complementary Resistive Switches for Passive Nanocrossbar Memories. Nature Materials, 9, 403-406. https://doi.org/10.1038/nmat2748
Fackenthal, R., Kitagawa, M., Otsuka, W., Prall, K., Mills, D., Tsutsui, K., Javanifard, J., Tedrow, K., Tsushima, T., Shibahara, Y., et al. (2014) 19.7 A 16Gb ReRAM with 200MB/s Write and 1GB/s Read in 27 nm Technology. 2014 IEEE International Solid-State Circuits Conference Digest of Technical Papers (ISSCC), San Francisco, CA, 9-13 February 2014, 338-339. https://doi.org/10.1109/ISSCC.2014.6757460
Sheu, S.-S., Chang, M.-F., Lin, K.-F., Wu, C.-W., Chen, Y.-S., Chiu, P.-F., Kuo, C.-C., Yang, Y.-S., Chiang, P.-C., Lin, W.-P., et al. (2011) A 4Mb Embedded SLC Resistive-RAM Macro with 7.2 ns Read-Write Random-Access Time and 160 ns MLC-Access Capability. IEEE Solid-State Circuits Conference Digest of Technical Papers, February 2011, 200-202.
Lin, Y.-M., Appenzeller, J., Knoch, J. and Avouris, P. (2005) High-Performance Carbon Nanotube Field Effect Transistor with Tunable Polarities. IEEE Transactions on Nanotechnology, 4, 481-489. https://doi.org/10.1109/TNANO.2005.851427
Appenzeller, J. (2008) Carbon Nanotubes for High-Performance Electronics Progress and Prospect. Proceedings of the IEEE, 96, 201-211. https://doi.org/10.1109/JPROC.2007.911051
Navi, K., Momeni, A., Sharifi, F. and Keshavarzian, P. (2009) Two Novel Ultra High Speed Carbon Nanotube Full-Adder Cells. IEICE Electronics Express, 6, 1395-1401. https://doi.org/10.1587/elex.6.1395
Navi, K., Sharifi, F., Momeni, A. and Keshavarzian, P. (2009) Ultra High Speed CNFET Full-Adder Cell Based on Majority Gates. IEICE Transactions on Electronics, 93, 932-934.
Dadda, L. (1963) Information Processing: Proceedings of the IFIP Congress. North Holland, The Netherlands.
Lisanke, R. (1988) Logic Synthesis and Optimization Benchmarks User Guide Version 2.0. Tech Report, Microelectronics Center North Carolina, Research Triangle Park.