I'm trying to understand a paper (Tandem Networks of Universal Cells, Butler, 1978 1), but I can't make it past the first paragraph:

Consider the $x_l … x_{k - 1} | x_k$ partition matrix of a function $f( x_1, x_2, …, x_k)$, as shown in Fig. 1, where $C_0$ and $C_1$ represent the $x_k = 0$ and $x_k = 1$ columns, respectively. Let $0$ and $1$ represent the columns of all 0's and all 1's, respectively. Let $X$ denote a column with at least one 0 and at least one 1, and $\overline{X}$ its complement. The concatenation of two columns will represent a complete partition matrix. Thus, for example, $01$ represents $f(x_1, x_2, …, x_k) = x_k$ and $XX$ represents a function independent of $x_k$, but dependent on at least one of the remaining variables.

I'm trying to build something like a Karnaugh map, but the result I'm getting doesn't make sense.

For example, here's what I made from $f = x_1 \times x_2 \times x_3$ (with digital logic "&" for boolean times):

The first column ($C_0$) I would call $0$, from the author's definition, but the second column ($C_1$) doesn't seem to be a $0$, $1$, or $X$. What am I doing wrong?


You're pretty close.

I don't think that's what they intended as the partition matrix. Instead, I think they intended the following matrix:

x1 x2 \  0 1
 0  0  | 0 0
 0  1  | 0 0
 1  0  | 0 0
 1  1  | 0 1

That's slightly different from what you have written. In particular, the partition matrix will have $2^{k-1}$ rows and 2 columns.

It's best to think of the first sentence as one paragraph, and the remaining sentences as a second disconnected paragraph that is trying to explain a taxonomy for classifying a column of this matrix. The author is proposing to classify every column into one of three types: all-zeros, all-ones, or contains both a 0 and a 1. The paper represents an all-zeros column by 0, an all-ones column by 1, and the third case by X. Thus, X is used to represent any column that contains at least one 0 and at least 1, i.e., any column that is not all-zeros and not all-ones.

By this classification, the partition matrix above would be of the form 0X: the first column is all-zeros (type 0), and the second column is type X.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.