TAOCP 7.1.4 Exercise 73

Section 7.1.4: Binary Decision Diagrams

Exercise 73. ▶ [25] [25] Discuss the use of “virtual addresses” instead of actual addresses as the links of a BDD: Each pointer p has the form π(p)2e + σ(p), where π(p) = p ≫e is p’s “page” and σ(p) = p mod 2e is p’s “slot”; the parameter e can be chosen for convenience. Show that, with this approach, only two fields (LO, HI) are needed in BDD nodes, because the variable identifier V (p) can be deduced from the virtual address p itself.

Verified: yes
Solve time: 4m22s

Corrected Solution

We are given a virtual address representation

$$ p = \pi(p)2^e + \sigma(p), \quad \pi(p)=p \gg e,\quad \sigma(p)=p \bmod 2^e, $$

and we must show that a BDD node stored at address $p$ does not need to store its variable identifier $V(p)$, because $V(p)$ can be recovered from $p$.

The goal is to justify a consistent allocation scheme in which the BDD structure uses only two fields, $LO$ and $HI$.

Key idea

The variable index is encoded in the high bits of the virtual address. The essential task is to show that we can assign addresses so that

$$ V(p) = \pi(p) = p \gg e $$

holds for every node, without violating the constraints of the decomposition

$$ 0 \le \sigma(p) < 2^e. $$

BDD structure and bounded allocation per level

Consider a reduced ordered BDD over variables $x_0, x_1, \dots, x_{n-1}$. Nodes are created at discrete levels corresponding to their variable index.

A crucial fact is that during any finite BDD construction process, the total number of nodes created is finite. Hence, for each level $i$, the number of distinct nodes ever created at that level is also finite.

Let $N_i$ denote the maximum number of nodes that may appear at level $i$ during the entire construction.

Since the construction is finite, we have a global bound

$$ N_i < \infty \quad \text{for all } i. $$

Now choose $e$ such that

$$ 2^e > \max_i N_i. $$

This is always possible because the right-hand side is finite for any finite construction, and $e$ is a freely chosen parameter of the virtual address system.

Allocation scheme

We now define the virtual address of each node explicitly.

Each node is created at a known variable level $i$. Maintain a counter $c_i$ for each level, initially zero.

When a new node at level $i$ is created, assign it the address

$$ p = i \cdot 2^e + c_i, $$

and then increment $c_i$.

This guarantees:

$0 \le c_i < 2^e$, so the slot constraint is satisfied.
Every node at level $i$ receives a unique slot within its page.

Thus the decomposition immediately yields

$$ \pi(p) = p \gg e = i, \quad \sigma(p) = c_i. $$

Why the bound is sufficient

The condition $2^e > \max_i N_i$ ensures that no level ever exhausts its available slots. Since each level receives at most $N_i$ nodes and $N_i < 2^e$, the counter $c_i$ never overflows.

This removes any need for “extra pages per variable” or other mechanisms that would conflict with the fixed definition of $\pi(p)$.

Preservation under BDD reduction

BDD reduction applies two operations:

Elimination of duplicate nodes with identical $(V, LO, HI)$
Sharing of already existing nodes

When two nodes at level $i$ are found to be identical, only one representative is kept. Importantly, this representative already has a fixed virtual address $p = i2^e + k$. No reassignment of addresses occurs.

Thus:

Reduction never changes $\pi(p)$
Reduction never changes the encoding of existing nodes
Sharing only introduces additional references to existing addresses

Therefore the invariant remains stable under reduction.

Why $V(p)$ is recoverable

During construction, each node is created at a known variable index $i$. By definition of the allocation scheme,

$$ \pi(p) = i. $$

Hence for every node,

$$ V(p) = i = \pi(p) = p \gg e. $$

This equality is not assumed; it is a direct consequence of how addresses are assigned.

Why only $LO$ and $HI$ are needed

A BDD node at address $p$ stores only:

$LO(p)$: low child pointer
$HI(p)$: high child pointer

The variable index is not stored because it is encoded in the address itself:

$$ V(p) = p \gg e. $$

Thus the node structure requires no explicit $V$ field.

Final conclusion

By choosing $e$ large enough that $2^e$ exceeds the maximum number of nodes at any BDD level during construction, we obtain a consistent virtual address allocation scheme

$$ p = i2^e + k $$

that respects the definition of virtual addresses.

This scheme ensures that the page index $\pi(p)$ coincides exactly with the variable index of the node. Consequently, the variable identifier is recoverable from the address alone, and BDD nodes require only the two pointer fields $LO$ and $HI$.