On Bi-Decompositions of Logic Functions
Tsutomu Sasao, Jon T. Butler · 1997
A logic function f has a disjoint bi-decomposition iff f can be represented as f = h(g 1 (X 1 );g 2 (X 2 )), where X 1 and X 2 are disjoint set of variables, and h is an arbitrary two-variable logic fuction. f has a non-disjoint bidecomposition iff f can be represented as f(X 1 ;X 2 ;x)= h(g 1 (X 1 ;x);g 2 (X 2 ;x)), where x is the common variable. In this paper, weshow a fast method to find bidecompositions. Also, weenumerate the number of functions having bi-decompositions. I Introduction Functional decomposition is a basic technique to realize economical networks. If the function f is represented as f(X 1 ;X 2 )=h(g(X 1 );X 2 ), then f can be realized bythe network shown in Fig. 1.1. To find such a decomposition, 1 X 2 X g h f Figure 1.1: A simple disjoint decomposition. 1 X 2 X g h g 1 2 f Figure 1.2: A disjoint bi-decomposition. 1 X 2 X g h g 1 2 x f Figure 1.3: A non-disjoint bidecomposition. a decomposition chart with 2 n1 columns and 2 n2 rows a...