On Transformation of a Logical Circuit to a Circuit with NAND and NOR Gates Only

• Autorzy: Baranov S. , Karatkevich A.

Identyfikatory

DOI

10.24425/123535

• Języki publikacji: EN

Abstrakty

EN

In the paper we consider fast transformation of a multilevel and multioutput circuit with AND, OR and NOT gates into a functionally equivalent circuit with NAND and NOR gates. The task can be solved by replacing AND and OR gates by NAND or NOR gates, which requires in some cases introducing the additional inverters or splitting the gates. In the paper the quick approximation algorithms of the circuit transformation are proposed, minimizing number of the inverters. The presented algorithms allow transformation of any multilevel circuit into a circuit being a combination of NOR gates, NAND gates or both types of universal gates.

Słowa kluczowe

EN

logic synthesis; logic devices; VLSI; minimization

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: International Journal of Electronics and Telecommunications
• Rocznik: 2018
• Tom: Vol. 64, No. 3
• Strony: 373--378
• Opis fizyczny: Bibliogr. 17 poz., rys.

Twórcy

autor

Baranov S.

• Holon Institute of Technology, Israel

autor

Karatkevich A.

• Institute of Electrical Engineering, University of Zielona Gora, Zielona Gora, Poland

Bibliografia

• [1] D. A. Pinelli, Fundamentals of Digital Logic Design With VLSI Circuit Applications, Prentice Hall, 1990.
• [2] M. M. Mano and Ch. R. Kime, Logic and Computer Design Fundamentals, 3rd ed. Prentice Hall, 2004.
• [3] S. Baranov, Logic and System Design of Digital Systems, Tallinn: TUT Press, 2008.
• [4] G. De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill, 1994.
• [5] A. Zakrevskij, Yu. Pottosin and L. Cheremisinova, Optimization in Boolean Space, Tallinn: TUT Press, 2009.
• [6] T. Luba, Synteza układów logicznych, Warszawa: WSISiZ, 2000.
• [7] M. Rawski, T. Luba, Z. Jachna, and P. Tomaszewicz, ”The influence of functional decomposition on modern digital design process.” in Design of Embedded Control Systems. Springer-Verlag, 2005, pp. 193-204.
• [8] P. N. Bibilo, Decomposition of Boolean Functions by Means of Solving Logical Equations, Minsk: Belaruskaya Navuka, 2009.
• [9] G. Borowik, G. Labiak, and A. Bukowiec, ”FSM-based logic controller synthesis in programmable devices with embedded memory blocks.” in Innovative technologies in management and science. Cham Heidelberg : Springer International Publishing Switzerland, 2015 - (Topics in Intelligent Engineering and Informatics ; Vol. 10) - s. 123–151.
• [10] R. Diestel, Graph Theory, Springer-Verlag, 2000.
• [11] J. Guo, J. Gramm, F. Hüffner, R. Niedermeier, and S. Wernicke, ”Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization”, Journal of Computer and System Sciences, vol. 72, 2006.
• [12] A. Avidor and M. Landberg, ”The multi-multiway cut problem”, Proceedings of 9th SWAT, LNCS, vol. 3111, Springer-Verlag, 2004, pp. 273284.
• [13] F. T. Nobibon, C. A. J. Hurkens, R. Leus, and F. C. R. Spieksma, ”Coloring Graphs Using Two Colors while Avoiding Monochromatic Cycles”, Informs Journal on Computing, 6124(3), January 2010, pp. 229-242.
• [14] F. T. Nobibon, C. A. J. Hurkens, R. Leus, and F. C. R. Spieksma, ”Exact algorithms for coloring graphs while avoiding monochromatic cycles”, Proc. of 6th International Conference on Algorithmic Aspects in Information and Management, Weihai, China, July 2010, pp. 229-242.
• [15] P. Heggernes, P. Van ’T Hof, D. Lokshtanov, and Ch. Paul, ”Obtaining a Bipartite Graph by Contracting Few Edges”, SIAM Journal on Discrete Mathematics, vol. 27, issue 4, 2013, pp. 21432156.
• [16] Th. H. Cormen, Ch. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd ed. MIT Press and McGraw-Hill, 2009.
• [17] M. Kubale (editor), Graph Colorings, Contemporary Mathematics, vol. 352, 2004.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).