A Logic Function Reduction and Minimization Algorithm for Microcomputers

Abstract

Combinational logic forms the basis of any digital system when decomposed into its basic elements. Of particular significance in this area is the reduction and minimization of a combinational logic function. Besides being a necessary educational stepping stone towards more complex sequential logic systems, it still bears its importance today in fault analysis of digital systems, applications involving Field Programmable Logic Arrays (FPLAs), or chip-level design requirements for LSI and VLSI technology.

This paper proposes and describes a departure front the more popular Quine-McCluskey computer solution in the form of an algorithm based on variable partitioning, combination generation and searching techniques for the prime implicants. Minimization is done by using a Zero-One Integer Programming model of the problem where the implicants and the logic function min terms or maxterms form a set of constraints to the problem and an objective function is used based on a pseudo-cost coefficient for each implicant requirement on fan-in and number of inverters.

The algorithm was implemented in a computer program called BOZER (acronym for Boolean Zero-One Reduction) in a 64K microcomputer system using Microsoft’s MBASIC interpreter under a CDOS (CPM-enhanced) operating system. The present program can handle  up to 13 state variables. Even if the implementation is only in a microcomputer system the processing time is still reasonable. It is predicted that for larger problems run on larger computer systems, the algorithm will show a significant reduction of processing time and memory requirement when compared to other algorithms written in the same language and run on the same machine. Finally, an algorithm expansion for the multi-output case is described.