A new logic circuits optimization algorithm using bipartite graph

Abstract

Designing a logic circuit from the scratch requires its description in logical expression, (e.g. sum of products), and then the expression should be optimized to diminish the cost and complexity of the circuit by reducing the number of literals, the number of logical terms, and/or logical operations. Karnaugh map, K-Map, is the most popular method in the optimization process, but it suffers from many drawbacks such as its inefficiency or the inability to be used in minimizing logical expression containing more than four literals, in addition to the complexity of implementing it as a program. In this paper, we propose a new algorithm to optimize the logic circuits depending on the bipartite graph and some of the suggested mathematical operations. The proposed algorithm is simple for programming implementation, literal-unlimited number, and is easy to be visualized and understandable. Many of the logic circuits of 3, 4, 5, and 6 literals were optimized and the results were correctly matched with the results of the Karnaugh map. Also, tens of logic circuits of more than 6 literals are optimized and the results were correctly checked with their truth tables and Logic-Friday tool.