Bi-Decomposition using 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). Three-level structures have been studied previously, e.g. resulting in AND- OR-AND or AND-OR-XOR implementations. By using the LUT effectively, the composition of the AND-plane can be controlled to implement a PLA which has the optimum phase assignment for 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 flexibility induced by the final LUT logic. The extra LUT level provides a dimension beyond simple phase assignment. We performed experiments using a Boolean relation mini- mizer to compare such realizations vs. SOP forms and published three-level forms, comparing areas and delays. To approximate the possible sharing in the PLA, we mapped the 2m PLA logic using SIS. We focused on experiments with 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.