TAOCP 7.1.3 Exercise 142

We work with subcubes (implicants) on variables $x_1,\dots,x_n$, where each coordinate is in $\{x_i,\bar x_i, *\}$.

taocpmathematicsalgorithmsvolume-4hard

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 142. ▶ [33] [33] A subcube such as ∗10∗1∗01 can be represented by asterisk codes 10010100 and bit codes 01001001, as in (85); but many other encodings are also possible. What representation scheme for subcubes works best, for finding prime implicants by the consensus-based algorithm of exercise 7.1.1–31?

Verified: yes
Solve time: 4m06s

Corrected Solution

We work with subcubes (implicants) on variables $x_1,\dots,x_n$, where each coordinate is in ${x_i,\bar x_i, *}$. The consensus operation of Exercise 7.1.1–31 combines two cubes only when they differ in exactly one variable in opposite polarity, and are identical elsewhere.

The goal is to choose a representation that makes:

  1. testing combinability,
  2. forming the consensus,

both simple and word-efficient.

1. Correct representation scheme

The best scheme for the consensus-based prime implicant algorithm is a 2-bit encoding per variable, i.e. a ternary code:

For each variable $x_i$, store two bitmasks $A, B \in {0,1}^n$ such that:

$$ (A_i,B_i) = \begin{cases} (1,0) & x_i \text{ appears positively} \ (0,1) & x_i \text{ appears negatively} \ (0,0) & x_i \text{ is don’t-care} \end{cases} $$

The pair $(1,1)$ is disallowed.

Equivalently, each cube is a vector in ${00,10,01}^n$.

Define the specification mask

$$ S = A \lor B $$

so $S_i=1$ iff variable $x_i$ is specified.

This encoding separates:

  • whether a variable is present ($S$),
  • its polarity (encoded in $A$ vs $B$).

2. Correct characterization of combinability

Let cubes be $C=(A,B)$ and $C'=(A',B')$.

We first express equality structure correctly.

2.1 Agreement condition on all non-differing coordinates

For any index $j$, the codes must match unless it is the unique differing coordinate. That is:

$$ (A_j,B_j) = (A'_j,B'_j) \quad \text{for all but one } j. $$

This is a strict equality requirement, not just absence of conflict.

2.2 Allowed difference pattern

At the unique differing coordinate $i$, we must have:

$$ (A_i,B_i) = (1,0), \quad (A'_i,B'_i) = (0,1) $$

or vice versa.

No other difference is allowed.

In particular:

  • differences involving $(1,0)$ vs $(0,0)$ are forbidden,
  • differences involving $(0,1)$ vs $(0,0)$ are forbidden,
  • mixed or multiple-coordinate differences are forbidden.

2.3 Bitwise test formulation

Define the XOR over the packed pairs:

$$ D_A = A \oplus A', \quad D_B = B \oplus B'. $$

A coordinate $i$ is a valid disagreement iff:

$$ (D_A(i), D_B(i)) = (1,1), $$

because:

$$ 10 \oplus 01 = 11. $$

All other cases must be:

$$ (D_A(i), D_B(i)) = (0,0). $$

Hence we obtain the correct condition:

$$ D_A \lor D_B \text{ has exactly one bit, and } D_A = D_B. $$

Equivalently:

  • $D_A \oplus D_B = 0$ (no mismatched partial differences),
  • $\operatorname{popcount}(D_A) = \operatorname{popcount}(D_B) = 1$,
  • and the 1-bits occur at the same index.

This enforces both:

  • exact equality everywhere else,
  • one opposite-literal difference.

3. Consensus construction

If the unique differing index is $i$, the consensus removes that variable entirely:

$$ A'' = A \land \overline{e_i}, \quad B'' = B \land \overline{e_i}. $$

Equivalently, in bitwise packed form:

$$ S'' = S \land \overline{e_i}. $$

The polarity bits at $i$ are discarded because the variable becomes unspecified.

This is correct because all other coordinates are identical, so no further adjustment is needed.

4. Why this representation is best for the algorithm

This encoding is optimal for the consensus method because:

(i) Combinability test is word-level

All checks reduce to:

  • XOR of two bitsets,
  • population count of two masks,
  • equality test of masks.

No decoding of ternary structure is required.

(ii) Consensus is a single mask operation

Once the differing bit is located:

$$ C'' = C ;\text{with bit } i \text{ cleared}, $$

which is a constant-time word operation.

(iii) Failure of the earlier $(P,N)$ scheme

The previous representation $(P,N)$ is insufficient because:

  • it does not distinguish “don’t-care” from “opposite literal” in a way that preserves equality constraints,
  • combinability cannot be reduced to a single local conflict mask,
  • it cannot enforce global equality across all non-differing coordinates without an additional mask $S$.

Thus it is not well-suited for fast consensus detection.

5. Final characterization

Two cubes are combinable under consensus iff, in the 2-bit encoding:

$$ \text{XOR}(C, C') \in {0, 11e_i} \text{ for some unique } i, $$

i.e.

  • exactly one coordinate differs,
  • and that difference is $10 \leftrightarrow 01$.

The consensus is obtained by deleting that coordinate.

Conclusion

The optimal representation for subcubes in the consensus-based prime implicant algorithm is the two-bit ternary encoding per variable with a specification mask implicit in the encoding. It allows:

  • exact equality checking by XOR,
  • correct detection of a single opposite-literal disagreement,
  • constant-time consensus formation via bit clearing.

This resolves the incorrect combinability criterion in the previous solution and yields a fully correct and implementation-suitable scheme. ∎