Complemented circuits

We study a three-level form, called {\em complemented circuit}, which implements a special type of decomposition of a Boolean function into two logic blocks, e.g., SOP forms, whose outputs feed a two-input Boolean operator or a two-input programmable LUT. Such structures have been studied previously with a final fixed two-input operator, say an AND or an XOR, resulting in an AND-OR-AND implementation or an AND-OR-XOR implementation. 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 the chosen logic structure. For all 10 non-trivial two-input Boolean operators, we performed experiments using a Boolean relation minimizer to compare such realizations vs. SOP forms and other three-level forms, comparing areas and delays.