Compact SOP representations for multiple-output functions-an encoding method using multiple-valued logic

Abstract

This paper shows a method to represent a multiple output function: Encoded characteristic function for non-zero outputs (ECFN). The ECFN uses (n+u) binary variables to represent an n-input m-output function, where u=[log/sub 2/m]. The size of the sum-of-products expressions (SOPs) depends on the encoding method of the outputs. For some class of functions, the optimal encoding produces SOPs with O(n) products, while the worst encoding produces SOPs with O(2/sup n/) products. We formulate encoding problem and show a heuristic optimization method. Experimental results using standard benchmark functions show the usefulness of the method.