AN EXTREMAL PROBLEM IN THE HYPERCUBE AND OPTIMIZATION OF ASYNCHRONOUS CIRCUITS

Carlos Gustavo T. de A. Moreira and Pablo Emanuel

IMPA-Instituto de Matemática Pura e Aplicada Estrada Dona Castorina, 110 - Jardim Botanico 22460-320, Rio de Janeiro-RJ Brasil

gugu@ impa.br pablo@ impa.br

Abstract. We prove that if m ≥ 2 then the minimum k ∈ ℕ such that the k-cube {0, 1}^{k} can be decomposed as the disjoint union of connected adjacent subsets satisfies 2 log_{2} m−log_{2} log_{2} m−1 ≤ k ≤ 2⌈log_{2} m⌉ − ⌊log_{2} log_{2} m⌋ + 5.

Introduction

One of the main uses of electronic digital circuits is implementing finite state machines. There are two main types of digital circuits: the synchronous circuits, in which all transitions occur in discrete time, determined by a clock pulse; and the asynchronous circuits, in which transitions may occur at any time.

In a digital circuit, the state is determined by the binary value (voltage or current) in some components, so it can be viewed as a fixed length binary word.

In a synchronous circuit, all such bits change state at the same time in a transition, namely the time determined by the clock pulse. In the asynchronous case, however, when there is a transition, some bits may change faster than others, and the circuit passes through intermediate states, that do not correspond to actual intermediate states in the state machine that is being implemented. Clearly, this problem would not occur if, in every state transition, only one bit changes.

In general, it isn’t possible to assign a k-bit word to each state of the machine satisfying the condition that every transition is a 1-bit transition (e.g. complete graph with 3 states). In [1], Huffmann proposed, as a solution to this problem, to assign more than one word per state, and implement the transitions as a sequence of 1-bit transitions, such that the initial words in this sequence corresponds to the initial state of the transition and the other ones to the final state. He proved that this could be done, for a complete state machine ( complete graph ), with 2⌈log_{2} m⌉ − 1 bits, where m is the number of states. We prove in this paper a better bound, and prove that it can’t be significatively improved.

A more precise formulation of this problem is as follows:

• Each state is assigned to a subset of the set of the k-bit words (that can be viewed as the k-cube (ℤ/2ℤ)^{k}).

• Each 1-bit transition is an edge of the cube, so each transition can be viewed as a path in the cube graph. The way to avoid undesired transient states is to assure that every transition is a 1-bit transition.

We will consider the worst case, namely the complete machine state (each state has transitions to every other state).

So, the problem is to find the minimum k such that the k-cube can be decomposed as the union of m disjoint connected subsets A_{1}, …, A_{m} such that for each i, j ≤ m there is a pair of adjacent vertices, one of them in A_{i} and the other one in A_{j} .

Statements and Proofs

Definition: We say that two subsets A, B of a hypercube {0, 1}^{k} are adjacent if there are two adjacent points x ∈ A, y ∈ B. Proposition 1. If m ≥ 2 and the k-cube {0, 1}^{k} can be divided as the union of m disjoint adjacent subsets then k ≥ 2 log_{2} m − log_{2} log_{2} m − 1.

Proof: Suppose that the k-cube {0, 1}^{k} can be divided in m disjoint subsets A_{1}, A_{2}, …, A_{m} such that for each i, j ≤ m there are x, y adjacent vertices such that x ∈ A_{i}, y ∈ A_{j} . Then there is one of the sets A_{i} such that A_{i} has at most ⌊2^{k}/m⌋ elements and, since any vertex has exactly k adjacent vertices and every A_{j} is adjacent to A_{i} for j ≠ i, we have k⌊2^{k}/m⌋ ≥ m − 1 ⇒ k2^{k} ≥ m(m − 1), and so we have k ≥ 2 log_{2} m − log_{2} log_{2} m − 1 for m ≥ 2. □

Proposition 2. If m ≥ 2 then the k-cube {0, 1}^{k} can be decomposed as the disjoint union of connected adjacent subsets for some k ≤ 2⌈log_{2} m⌉ − ⌊log_{2} log_{2} m⌋ + 5

Proof: We will present a construction of a decomposition that satisfies the conditions of the proposition. We will use many times the fact that a face of any dimension of a hypercube is always connected.

Let n = ⌈log_{2} m⌉, r = ⌊\frac{n}{2}⌋, p = ⌊log_{2} r⌋. We will construct a decomposition of the k-cube, where k = 4 + 2n − p ≤ 2⌈log_{2} m⌉ − ⌊log_{2} log_{2} m⌋ + 5.

Let us write a typical element of the k-cube as \underline{u} = a_{1}a_{2}bc \underline{x_{0}} \underline{x_{1}} \underline{y}, where a_{1}, a_{2}, b and c are bits, \underline{x_{0}}, \underline{x_{1}} belongs to the (n − r)-cube \{0, 1\}^{r} and \underline{y} belongs to the (n − p)-cube \{0, 1\}^{n−p}.

The r-cube {0, 1}^{r} can be regarded as an r-dimensional vector space over ℤ/2ℤ with the canonical basis {e_{1}, e_{2}, …, e_{r}}, where e_{j} is the vector that has the j-th coordinate equal to 1 and all the other coordinates equal to 0. Since p ≤ log_{2} r, we have 2^{p} ≤ r so there is a surjective function f̃: {e_{1}, e_{2}, …, e_{r}} → (ℤ/2ℤ)^{p} that extends in a unique way to a linear function f: (ℤ/2ℤ)^{r} → (ℤ/2ℤ)^{p}. It follows that given v ∈ (ℤ/2ℤ)^{r} and w ∈ (ℤ/2ℤ)^{p} there is an element e_{j} of the canonical basis of (ℤ/2ℤ)^{r} such that f(v + e_{j}) = w (note that v + e_{j} is adjacent to v). Since n − r ≥ r we have a linear function g: (ℤ/2ℤ)^{n−r} → (ℤ/2ℤ)^{p} analogous to f.

We may define now a function F: (ℤ/2ℤ)^{k} → (ℤ/2ℤ)^{2r} in the following way: for \underline{u} =

a_{1}a_{2}bc \underline{x_{0}} \underline{x_{1}} \underline{y} ∈ (ℤ/2ℤ)^{k} we look at the 3 bits a_{1} , a_{2} and b^{∗}, where b^{∗} is the sum modulo 2 of all the bits of u. If at least 2 of these 3 bits are equal to 0 we say that \underline{u} is of type I and define F (\underline{u}) = \underline{x_{0}} \underline{x_{1}} ; otherwise we say that u is of type II and define

F (\underline{u}) = \{ \begin{matrix}f(\underline{x_{0}})\underline{y}, if c = 0 \\ g(\underline{x_{1}})\underline{y}, if c = 1 \end{matrix}

We claim that the 2^{n} sets F^{−1}(\underline{x}), \underline{x} ∈ (ℤ/2ℤ)^{n} are disjoint, connected and adjacent, so, given

a bijection h: (ℤ/2ℤ)^{2r} → {1, 2, …, 2^{2r}} (for instance h(σ_{1}, σ_{2}, …, σ_{2r}) = 1 + ∑_{ℓ=1}^{2r} σ_{ℓ}2^{ℓ−1}), the

decomposition of (ℤ/2ℤ)^{k} as A_{1} ∪ A_{2} ∪ ⋯ ∪ A_{m} where A_{i} = (h ∘ F)^{−1}(i) for 1 ≤ i < m, A_{m} = ⋃_{j≥m}(h ∘ F)^{−1}(j) satisfies the conditions of our problem.

To prove this let us first verify that for each \underline{x}, \underline{y} in (ℤ/2ℤ)^{n} there are adjacent vertices \underline{u_{1}} ∈ F^{−1}(\underline{x}), \underline{u_{2}} ∈ F^{−1}(\underline{y}). If \underline{x} = ˜ \underline{x_{o}} ˜ \underline{x_{1}} ∈ (ℤ/2ℤ)^{n} = (ℤ/2ℤ)^{r} × (ℤ/2ℤ)^{n−r} we can take a_{1} = 0, a_{2} = 1 and b such that b^{∗} = 0, and ˜ \underline{y} ∈ (ℤ/2ℤ)^{2r−p} equal to the projection of \underline{y} in the last 2r − p coordinates. We will have F (01b0˜\underline{x_{0}} ˜ \underline{x_{1}} ˜ \underline{y}) = ˜ \underline{x}, and we can take \underline{x_{0}}′ adjacent to ˜ \underline{x_{0}} such that f(\underline{x_{0}}′) is the projection of \underline{y} in the first p coordinates, so 01b0\underline{x_{0}}′ ˜ \underline{x_{1}} ˜ \underline{y} is adjacent to 01b0˜\underline{x_{0}} ˜ \underline{x_{1}} ˜ \underline{y} and F (01b0\underline{x′_{0}} ˜ \underline{x_{1}} ˜ \underline{y}) = \underline{y}.

Now we will prove that the sets F^{−1}(\underline{x}) are connected. We can decompose F^{−1}(\underline{x}) as B\underline{x} ∪ C\underline{x} where

B\underline{x} = \{\underline{u} ∈ F^{−1}(\underline{x}) | \underline{u} if of type I\} and
C\underline{x} = \{\underline{u} ∈ F^{−1}(\underline{x}) | \underline{u} is of type II\}.

The previous argument can be used to show that B\underline{x} and C\underline{x} are adjacent since there are adjacent elements \underline{u_{1}} ∈ B\underline{x} and \underline{u_{2}} ∈ C\underline{x}. It is enough to prove that B\underline{x} and C\underline{x} are connected.

If \underline{u} = a_{1}a_{2}bc \underline{x_{0}} \underline{x_{1}} \underline{y} ∈ B\underline{x}, then \underline{u} is equal or adjacent to \underline{u}′ = 00bc \underline{x_{0}} \underline{x_{1}} \underline{y} ∈ B\underline{x}, and the set B̃\underline{x} of the \underline{u}′ ∈ B\underline{x}; such that a_{1} = a_{2} = 0 is clearly connected, since it is equal to \{\underline{u}′ = 00bc \underline{x_{0}} \underline{x_{1}} \underline{y} | \underline{x_{0}} \underline{x_{1}} = \underline{x}\}, that is a face of the hypercube \{0, 1\}^{k}.

If \underline{u} = a_{1}a_{2}bc \underline{x_{0}} \underline{x_{1}} \underline{y} ∈ C\underline{x} then \underline{u} is equal or adjacent to \underline{u}′′ = 11bc \underline{x_{0}} \underline{x_{1}} \underline{y} ∈ C\underline{x}. The set C̃\underline{x} = \{\underline{u}′′ ∈ C\underline{x} | a_{1} = a_{2} = 1\} can be decomposed as D\underline{x} ∪ E\underline{x} where D\underline{x} = \{\underline{u}′′ ∈ C\underline{x} | a_{1} = a_{2} = 1 and c = 0\} and E\underline{x} = \{\underline{u}′′ ∈ C\underline{x} | a_{1} = a_{2} = 1 and c = 1\}. To prove that C̃\underline{x} (and so C\underline{x}) is connected, it is enough to show that any element \underline{u}_{1} ∈ D\underline{x} can be joined by a path in C̃\underline{x} to any element \underline{u_{2}} ∈ E\underline{x}. This is a consequence of the following facts:

• \underline{u_{1}} = 11b̃0 ˜ \underline{x_{0}} ˜ \underline{x_{1}} ˜ \underline{y} belongs to the connected set L(\underline{u_{1}}) contained in D\underline{x} defined as

L(\underline{u_{1}}) = \{11b0 \underline{x_{0}} \underline{x_{1}} \underline{y} ∈ D\underline{x} | \underline{x_{0}} = ˜ \underline{x_{0}}, \underline{y} = ˜ \underline{y}\}.

• \underline{u_{2}} = 11b′1 \underline{x_{0}}′ \underline{x_{1}}′ ˜ \underline{y} belongs to the connected set M(\underline{u_{2}}) contained in E\underline{x} defined as

M(\underline{u_{2}}) = \{11b1 \underline{x_{0}} \underline{x_{1}} \underline{y} | \underline{x_{1}} = \underline{x_{1}}′, \underline{y} = ˜ \underline{y}\}

• (11b̃0 ˜ \underline{x_{0}} \underline{x_{1}}′ ˜ \underline{y}) ∈ L(\underline{u_{1}}) and (11b̃1 ˜ \underline{x_{0}} \underline{x_{1}}′ ˜ \underline{y}) ∈ M(\underline{u_{2}}) are adjacent. □

REFERENCES

[1] D. A. Huffman, A Study of the Memory Requirements of Sequential Switching Circuits, M.I.T., Res. Lab. Electron. Tech. Rept. 293, April, 1955.

[2] Z. Kohavi, Switching and Finite Automata Theory, McGraw-Hill computer science series, 1978