There are only three types of decomposition in the literature that are truly different and that make use of the concept of partitioning of input variables to bound and free sets: Curtis Decomposition [6], Steinbach et al (XBOOLE) Decomposition [2], and Perkowski et al (PUB) Decomposition [13, 12, 15]. The decompositions of Ashenhurst [1]; Luba et al [10]; Lai, Pedram et al [9], and many other are just special cases of Curtis decomposition or use only various representations [15]. While most authors differentiate between disjoint and non-disjoint decompositions, the introduced below concept of the Repeated Variable Maps (RVMs) allows to explain them in a uniform way, and the CDBs allow to realize all these decompositions uniformly in software.
In RVM, the rows of the map correspond to the Row Variables,
and the columns correspond to the Column Variables.
As we see, the Row Variables can be represented as A C,
and the Column Variables can be represented as B
C.
Using Curtis terminology, set B
C
is a bound set, and set A
C is a free set.
If C =
the decomposition is disjoint and the RVM becomes a standard Karnaugh Map.
If C
the decomposition is non-disjoint and the RVM is incompletely
specified, even if the original function is completely specified.
Every variable in C is called a repeated variable.
Let us observe, that every repeated variable
creates a map of one dimension higher, in which all newly introduced cells are don't cares.
For instance, if the original map is completely specified and has 4 variables
a,b,c,d, the bound set is {a,c,d}
and the variable a is a repeated variable, the new 4 * 8 map will have three variables
for columns and two variables for rows
(variable a stands in both rows and columns).
Half of the RVM are don't cares.
If variables a and c were repeated, and {a,c,d} were a bound set, the new 8 * 8 map will have
three variables for columns, and three variables for rows.
It will have 75% of don't cares.
As we see, even starting with a completely specified function, by repeating
variables, very quickly one has to deal with very strongly unspecified functions.
In addition, in ML applications, even the initial data can have more than 99.99% of
don't cares. It is than absolutely crucial to be able to represent and manipulate such functions efficiently.
The main observation of our unified and generalized approach is the observation that all decompositions [6, 2, 13, 12, 15, 10] use certain fundamental patterns in cofactors. These patterns can be easily observed in rows and columns of the RVM. Recall please, that both the rows and the columns of RVM correspond to cofactors with respect to cubes on literals created from row and column variables, respectively.
Let us concentrate in this section on binary functions. We will distinguish the following patterns in cofactors:
1. Pattern of don't cares. We will call it the DC Pattern.
2. Pattern of ones (and possibly don't cares). We will call it the ON Pattern.
3. Pattern of zeros (and possibly don't cares). We will call it the OFF Pattern.
4. Pattern of function F (with any non-empty subset of zeros, ones, and don't cares). We will call it the F Pattern.
5. Pattern of function . We will call it the
Pattern.
6. Pattern being either the DC Pattern or the ON Pattern. We will call it the DC/ON Pattern.
Similarly other combined patterns of DC, ON, OFF, F, and can be defined.
We will say that function has pattern X/Y/Z on columns (rows) if every
column (row) cofactor has one of patterns X, Y or Z.
Let us observe that if a function has DC/ON/OFF pattern on columns then it is independent on the
variables from the free set.
Analogically, if a function has DC/ON/OFF pattern on rows then it is independent on the
variables from the bound set.
Obviously some columns (rows)
can be characterized as corresponding to several patterns. For instance,
a column may be characterized as having either an ON pattern or an F pattern.
There exist more
characteristic patterns that we do not discuss here for the lack of space, and
all possible decomposition methods are based on finding these patterns in functions.
Definitions of Patterns.
Row OR decomposition
exists with respect to the set of row variables RV if there exists at least one row that has the ON Pattern.
Row AND decomposition
exists with respect to the set of row variables RV if there exists at least one row
that has the OFF Pattern.
Let us observe that in the above two cases, decompositions OR and AND can be found
immediately just by analysing one row at a time, and without comparing rows to other rows.
Row EXOR decomposition
exists with respect to the set of row variables RV if for every row its pattern
is either F Pattern or .
(Let us observe, that in this case every DC, ON and OFF row must be here characterized as
either an F or
pattern).
This case is then more difficult than the first two.
Analogically one can define the
Column OR, Column AND, and Column EXOR decompositions.
Row and Column decompositions are also called Weak Decompositions [2].
There exist then Weak AND, Weak OR, and Weak EXOR decompositions
(our understanding of weak and strong follows that from [2],
and not the one from U.C. Berkeley).
Strong OR decomposition exists with respect to a set of row variables RV and a set
of column variables CV if there exists Row OR Decomposition,
and next, after replacing the ON rows with don't cares, there exists a DC/ON/OFF Pattern on columns.
Equivalently, Strong OR decomposition exists with respect to a set of column variables CV and a set
of row variables RV if there exists Column OR Decomposition,
and next, after replacing the ON columns with don't cares, there exists a DC/ON/OFF Pattern on rows.
Strong AND decomposition exists with respect to a set of row variables RV and a set
of column variables CV if there exist Row AND Decomposition,
and next, after replacing the OFF rows with don't cares, there exists a DC/ON/OFF Pattern on columns.
Strong EXOR decomposition exists with respect to a set of row variables RV and a set
of column variables CV if there exist Row EXOR Decomposition, and
Column EXOR Decomposition.
Strong OR/AND decomposition exists with respect to a set of row variables RV and a set
of column variables CV if there exist ON Patterns of rows,
and next, after replacing the ON rows with don't cares, there exists a Strong AND decomposition.
There are several other complex patterns of this type.
AND, OR and EXOR decompositions will be called the Basic Gate Decompositions.
OR/AND, AND/OR and other decompositions of this type will be called the Complex Gate Decompositions.
An example of the RVM is shown in Figure 2.
Fig. 2a presents a standard Kmap of 3-input function f.
Assuming b to be a repeated variable, the Bond Set {b,c} (the columns) and the
Free Set as {a,b}, one creates a RVM from Fig. 2b.
Let us observe that ON Patterns and
exist in this RVM, which lead to Strong OR Decomposition:
f =
+
.
Similarly, for the same RVM in Fig. 2c, the OFF Patterns
(a+b) and (
)
are found, which lead to the Strong AND Decomposition:
(a+b)
(
).
Finally, for the same RVM in Fig. 2d, the Column Patterns
F, and
and the Row Patterns G, and
are found as shown with loops on the map in Fig. 2d.
These patterns lead to Strong EXOR Decomposition:
(
)
(
) from Fig. 2e.
Fig. 2e clearly shows the incomplete patterns
from Fig. 2d after their completion with 0's and 1's.
Let us observe that from Fig. 2d one can find also
, assuming
the first three columns from left to have a pattern of
.