Multiple-valued minimization to optimize PLAs with output EXOR gates

Abstract

This paper considers an optimization method of programmable logic arrays (PLAs), which have two-input EXOR gate at the outputs. The PLA realizes an EXOR of two sum-of-products expressions (EX-SOP) for multiple-valued input two-valued output functions. We present techniques to minimize EX-SOPs, which is an extension of Dubrova-Miller-Muzio's AOXMIN algorithm. We conjecture that, when n is sufficiently large, an EX-SOP for n-bit adder requires at most 2/sup n/ products while an ordinary sum-of-products expression (SOP) requires 6/spl middot/2/sup n/-4n-5 products. Experimental results for two- and four-valued benchmark functions show that the proposed method produces better EX-SOPs than existing methods.