EXMIN: a simplification algorithm for exclusive-OR-sum-of-products expressions for multiple-valued input two-valued output functions

Minimization of AND-EXOR PLAs (programmable logic arrays) with input decoders corresponds to minimization of the number of products in exclusive-OR sum-of-products (ESOPs) expressions for multiple-valued-input, two-valued-output functions. A simplification algorithm for ESOPs, called EXMIN, is presented. The algorithm is based on an iterative improvement. Seven rules are used to replace one pair of products with another. Many AND-EXOR PLAs for arithmetic circuits are simplified. It is shown that in most cases AND-EXOR PLAs require fewer products than AND-OR PLAs