An Approach to Multilevel Boolean Minimization

Abstract

An approach to the problem of multilevel Boolean minimization is described. The conventional prime implicant is generalized to the multilevel case, and the properties of multilevel prime implicants are investigated. A systematic procedure for computing mul- tilevel prime implicants is described, and several examples are worked out. It is shown how ,'absolutely minimal" forms can be obtained by carrying out multilevel minimization to a sutSciently large number of levels. 1. (ntroduclion Boolean forms cart be classified by the number of levels of sums and products they contain; e.g. a sum of products or a product of sums has two levels, whereas a sum of products of sums has three. There are a number of well-known methods for finding minimal two-level forms for a given function. However, there has been comparatively little progress in the development of methods for finding minimal forms with more than two levels; some references to prior work are appended to this paper. This paper describes an approach to the problem of finding minimal N-level forms and "absolutely minimal" forms. The techniques described are applicable to any and all Boolean functions, and are suitable for automatic computation. The approach generalizes two-level minimization procedures, and it is assumed that the reader is familiar with these methods.