A novel graphical technique for combinational logic representation and optimization

DOI10.1155/2017/9696342MaRDI QIDQ680814zbMATH OpenOpenAlexFDO

Authors Vedhas Pandit, Björn W. Schuller

Publication date 29 January 2018

Published in Complexity (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1155/2017/9696342

zbMATH Keywords

binary decision diagrams (BDDs)combinational logic representationcombinatorial optimizationdigital functionsdiscrete systemsgraphical techniqueKarnaugh-maps (K-maps)

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Discrete-time control/observation systems (93C55)

Review text

Summary: We present a new technique for defining, analyzing, and simplifying digital functions, through hand-calculations, easily demonstrable therefore in the classrooms. It can be extended to represent discrete systems beyond the Boolean logic. The method is graphical in nature and provides complete ``implementation-free description of the logical functions, similar to Binary Decision Diagrams (BDDs) and Karnaugh-maps (K-maps). Transforming a function into the proposed representations (also the inverse) is a very intuitive process, easy enough that a person can hand-calculate these transformations. The algorithmic nature allows for its computing-based implementations. Because the proposed technique effectively transforms a function into a scatter plot, it is possible to represent multiple functions simultaneously. Usability of the method, therefore, is constrained neither by the number of inputs of the function nor by its outputs in theory. This, being a new paradigm, offers a lot of scope for further research. Here, we put forward a few of the strategies invented so far for using the proposed representation for simplifying the logic functions. Finally, we present extensions of the method: one that extends its applicability to multivalued discrete systems beyond Boolean functions and the other that represents the variants in terms of the coordinate system in use.

Recommendations

• Suggestion for a new representation for binary function
• Representations of Boolean functions
• scientific article; zbMATH DE number 910723
• Graph-Based Algorithms for Boolean Function Manipulation
• scientific article; zbMATH DE number 512939

Cites work

• A Way to Simplify Truth Functions
• Abstract interpretation using typed decision graphs
• Automatic Sequences
• Binary Decision Diagrams
• Graph-Based Algorithms for Boolean Function Manipulation
• scientific article; zbMATH DE number 3353170 (Why is no real title available?)
• Reconfigurable asynchronous logic automata (RALA)
• The Problem of Simplifying Truth Functions

Cited in

(3)

• Karnaugh maps of logical systems and applications in digital circuit design
• FCA in a logical programming setting for visualization-oriented graph compression
• Fractals in logic

This page was built for publication: A novel graphical technique for combinational logic representation and optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q680814)