Graph-based output phase assignment for PLA minimization

A graph-based approach to finding near-optimal output phase assignments for PLA minimization is presented. A distinctive feature of the approach is that it exploits the necessary and sufficient conditions to reduce the number of product terms needed for PLA implementation and permits the use of existing graph algorithms to solve the PLA output phase optimization problem. The work is based on the transformation of a PLA into a graph whose vertices are the set of conditions required to reduce each product term of the PLA, and whose edges represent the relations between these conditions. Cliques (completely connected subgraphs) in the graph correspond to the output phase assignments required to reduce the product terms represented by the vertices in the cliques. The optimal PLA output phase assignment problem is then formulated as the well-studied problem in graph theory: finding maximum cliques in graphs. Using an existing algorithm for locating cliques in graphs, a modified greedy algorithm is proposed to compute output phase assignments for logic functions in polynomial time. Experimental results using a number of benchmark functions show that the graph-based approach can achieve optimal or near-optimal output phase assignment for PLA minimization and can lead to PLA´s with fewer product terms than achieved using existing approaches