Minimization of incompletely specified functions as three-level logic via Boolean relations

Abstract—We study three-level implementations where the first two levels represent a standard PLA form with an AND- plane and an OR-plane. This implements a 2m-output SOP. The final stage consists of m two-input programmable LUTs. The PLA outputs are paired so that the LUT outputs implement a set of m given incompletely specified functions (ISFs). Such three-level structures have been studied previously where the final two-input operator was fixed, say an AND or an XOR resulting in an AND-OR-AND implementation or an AND- OR-XOR implementation. By using the LUT effectively, the composition of the AND-plane can be controlled to implement a set of cubes which have the maximum cube sharing. For each output, we characterize the problem of all legal implementations of such a model, by defining Boolean relations that capture all the don’t care conditions induced by any LUT logic. The extra LUT level provides a dimension beyond simple phase assignment. We performed experiments using a Boolean relation minimizer to compare such realizations vs. SOP forms and three-level forms, comparing areas and delays. To approximate the possible sharing in the AND plane, we mapped the 2-m PLA logic using SIS. We focused on two-input Boolean functions not captured by AND- OR-AND or AND-OR-XOR approaches and found good gains in many cases with affordable increases in synthesis runtimes.