On Transformation of a Logical Circuit to a Circuit with NAND and NOR Gates Only
Abstract
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:
PDFReferences
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.
Refbacks
- 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