f(w,x,y,z) = (!w & !x & !y & !z) |
(!w & x  & y  &  z) |
(w  & !x & !y &  z) |
(w  &  x &  y & !z)

g(w,z)     = (!w & !z) | (w & z)
h(x,y,t)   = (!x & !y !t) | (x & y & !t)
f(w,x,y,z) = h(x,y,g(w,z))

The Decomposition of Switching Functions Robert Ashenhurst International Symposium on the Theory of Switching Functions’59

Say you are given a logic formula such as:

f(w,x,y,z) = (!w & !x & !y & !z) |
(!w & x  & y  &  z) |
(w  & !x & !y &  z) |
(w  &  x &  y & !z)

and you want to rewrite it in a more structured form. One way to impose structure is to express f as the composition of simpler functions. You can perform such a rewrite with the Ashenhurst-Curtis decomposition, and the result will look like this:

g(w,z)     = (!w & !z) | (w & z)
h(x,y,t)   = (!x & !y !t) | (x & y & !t)
f(w,x,y,z) = h(x,y,g(w,z))

This transformation is useful in logic synthesis. The task of synthesizing a circuit to implement the 4-input function f can be broken down into synthesizing circuits to implement:

The 2-input function g

The 3-input function h

The goal of the Ashenhurst-Curtis decomposition is to partition the inputs of a logic formula (w,x,y,z are the inputs in the running example) into two disjoint sets ({x,y}, {w,z}). The partitioning depends on the logic formula being decomposed. The idea is to decompose the formula into two simpler formulas:

Formula 1 accepts {w,z} as inputs

Formula 2 accepts {x,y} as inputs, along with the output of #1

A way to do this is to search through all possible partition matrices. Fig. 4 shows the partition matrix for the decomposition in the running example:

Think of a partition matrix as a two-dimensional truth table. Here is the original logic formula, along with the above partition matrix containing explicit values for x,y,w,z:

f(w,x,y,z) = (!w & !x & !y & !z) |
(!w & x  & y  &  z) |
(w  & !x & !y &  z) |
(w  &  x &  y & !z)

In other words, f is non-zero only when given the following inputs (which correspond to the 4 entries in the partition matrix with the value 1).

w=0,z=0,x=0,y=0

w=0,z=1,x=1,y=1

w=1,z=0,x=1,y=1

w=1,z=1,x=0,y=0

For a given logic formula, there exist many partition matrices. Only some are suitable for decomposing the logic formula. The key property to look for is the column multiplicity of the partition matrix. This column multiplicity is the number of unique column vectors in the partition matrix. The partition matrix above has a column multiplicity of 2 (i.e., there are two unique column vectors in the matrix, <1,0,0,0> and <0,0,0,1>).

If you can find a partition matrix with a column multiplicity less than or equal to two, then you can decompose the logic formula. Note that a partition matrix is defined not only by the values in the matrix, but also the partitioning of the input variables.

If you have located a partition matrix with a column multiplicity no greater than two, then the row multiplicity must be no greater than 4. In particular, there are 4 kinds of row vectors that you will see in the partition matrix:

Vectors of all 0s 1.

Vectors of all 1s 1.

A particular vector ϕ 1.

The inverse of ϕ

In the running example, the row vectors are:

[1,0,0,1] (we call this ϕ) 1.

[0,0,0,0] 1.

[0,0,0,0] 1.

[0,1,1,0] (note how this is the inverse of ϕ)

To decompose f, first generate a function ϕ. The inputs to the function are the variables written at the top of the partition matrix (w and z in this example). The truth table for ϕ is simply the first non-trivial row vector in the partition matrix ([1,0,0,1] in the example).

Next, generate a function F. The inputs to F are the variables written at the left of the partition matrix (x and y in this example), and the output of ϕ. In this example, F has 3 inputs, so the truth table defining F has 8 entries. A simple algorithm is used to generate the entries in that truth table. The algorithm iterates over the row vectors in the partition matrix, and each row vector defines 2 elements in the truth table of F.

If row vector i is all zeros, then the truth table elements at indices 2i and 2i+1 are 0

If row vector i is all ones, then the truth table elements at indices 2i and 2i+1 are 1

If row vector i is ϕ, then the truth table element at index 2i is 0, and the element at index 2i+1 is 1

If row vector i is the inverse of ϕ, then the truth table element at index 2i is 1, and the element at index 2i+1 is 0

These rules are described in Table 1:

The final decomposed function is:

f(w,x,y,z) = F(x,y,ϕ(w,z))

Until now, we’ve assumed that someone has handed us a partition matrix with column multiplicity no greater than two. But how does one find such a matrix. The paper proposes iterating through all partition matrices in the partition chart of the input formula. A partition chart contains many partition matrices, each one corresponding to a different partitioning of the input variables. A circled element in the partition chart corresponds to a 1 in the truth table of the input logic formula. Fig. 5 shows partition charts for the running example. The one in the lower right corner is the partition matrix in the running example. Astute readers will notice that it is actually the transpose of the partition matrix (i.e., w and z are on the left, x and y are on the top), but that is no big deal, they can be transposed as long as the variable names are transposed along with the matrix entries.

Once you have generated a partition chart, it is straightforward to search for partition matrices which have column (or row) multiplicity no greater than two. These are the ones that can be used to generate the decomposed function.

No posts