QTOP: A topological approach to minimizing single-output logic functions

摘要

Minimizing Logic functions is of great importance in design and implementation of digital circuits because makes them more efficient and simpler to implement. Therefore, it is considered as an important subject in electrical and computer engineering educational programs. There are some systematic techniques, which are traditionally used in order to teach how to minimize logic functions. These techniques can be easily implemented in the form of computer programs; however, each of them has shortcomings from education point of view. For example, the Quine-McCluski technique is an iterative technique and therefore takes a long time and increases the probability of making mistakes. The K-map- the other traditional method-causes a visual difficulty in distinguishing adjacent entries and prime implicants. This paper proposes a topological non-iterative approach to minimizing single-output logic functions which is based on representing minterms by nodes in a Q_n graph. The main goal of this approach is to represent prime implicants by explicit cycles in Q_n graphs in order to eliminate the ambiguity in distinguishing implicants and prevent mistakes.