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

Samary Baranov, Andrei Karatkevich


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 in some cases requires 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.

Full Text:



D. A. Pinelli, Fundamentals of Digital Logic Design With VLSI Circuit Applications, Prentice Hall, 1990.

M. M. Mano and Ch. R. Kime, Logic and Computer Design Fundamentals, 3rd ed. Prentice Hall, 2004.

S. Baranov, Logic and System Design of Digital Systems, Tallinn: TUT Press, 2008.

G. De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill, 1994.

A. Zakrevskij, Yu. Pottosin and L. Cheremisinova, Optimization in Boolean Space, Tallinn: TUT Press, 2009.

T. Luba, Synteza układow logicznych, Warszawa: WSISiZ, 2000.

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.

P. N. Bibilo, Decomposition of Boolean Functions by Means of Solving Logical Equations, Minsk: Belaruskaya Navuka, 2009.

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.

R. Diestel, Graph Theory, Springer-Verlag, 2000.

J. Guo, J. Gramm, F. H¨uffner, 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.

A. Avidor and M. Landberg, ”The multi-multiway cut problem”, Proceedings of 9th SWAT, LNCS, vol. 3111, Springer-Verlag, 2004, pp. 273-284.

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-

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.

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. 2143-2156.

Th. H. Cormen, Ch. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd ed. MIT Press and McGraw-Hill, 2009.

M. Kubale (editor), Graph Colorings, Contemporary Mathematics, vol. 352, 2004.


  • There are currently no refbacks.

International Journal of Electronics and Telecommunications
is a periodical of Electronics and Telecommunications Committee
of Polish Academy of Sciences

eISSN: 2300-1933