MINIMIZATION OF AND-OR-EXOR 3-LEVEL NETWORKS WITH AND GATE SHARING

This paper presents an exact minimization algorithm for AND-OR-EXOR th ree-level networks, where a single two-input exclusive-OR (EXOR) gate is used. The network realizes an EXOR of two sum-of-products expressio ns (EX-SOP), where the two sum-of-products expressions (SOP) can share products. The objective is to minimize the total number of different products in the two SOPs. An algorithm for the exact minimization of E X-SOPs with up to five variables are shown. Up to five variables, EX-S OPs for all the representative functions of NP-equivalence classes wer e minimized. For five-variable functions, we confirmed that minimum EX -SOPs require up to 9 products. For n-variable functions, minimum EX-S OPs require at most 9 . 2(n-5) (n greater than or equal to 6) products .