\magnification=1200
\input amstex.tex
\input amsppt.sty
\NoRunningHeads
\openup 6pt
\NoBlackBoxes
\TagsOnRight
\nologo

\parindent=30pt

\pagewidth{17.50truecm}
\pageheight{21truecm}

\def\ov{\overline}
\def\und{\underline}
\def\fa{{\Cal F}}
\def\H{{\Cal H}}
\def\B{{\Cal B}}
\def\O{{\Cal O}}
\def\P{{\Cal P}}
\def\L{{\Cal L}}
\def\C{{\Cal C}}
\def\M{{\Cal M}}
\def\N{{\Cal N}}
\def\R{{\Cal R}}
\def\sa{{\Cal S}}
\def\I{{\Cal I}}
\def\A{{\Cal A}}
\def\K{{\Cal K}}
\def\al{{\alpha}}
\def\be{{\beta}}
\def\ve{\varepsilon}
\def\te{{\theta}}
\def\vr{\varphi}
\def\ga{{\gamma}}
\def\Ga{{\Gamma}}
\def\om{{\omega}}
\def\Om{{\Omega}}
\def\la{{\lambda}}
\def\La{{\Lambda}}
\def\ro{{\rho}}
\def\po{{\partial}}

\def\bp{{\Bbb P}}
\def\bz{{\Bbb Z}}
\def\bq{{\Bbb Q}}
\def\re{{\Bbb R}}
\def\na{{\Bbb N}}
\def\si{{\Cal S}}
\def\co{{\Bbb C}}
\def\AA{{\Bbb A}}
\def\Ii{{\frak I}}

\def\lg{\langle}
\def\rg{\rangle}
\def\lV{\left\Vert}
\def\rV{\right\Vert }
\def\lv{\left\vert}
\def\rv{\right\vert }

\def\esima{${}^{\text{\b a}}$}
\def\esimo{${}^{\text{\b o}}$}

\def\Hom{\operatorname{{Hom}}}
\def\codim{\operatorname{{codim}}}
\def\cotg{\operatorname{{cotg}}}
\def\dom{\operatorname{{dom}}}
\def\VIP{\operatorname{{VIP}}}
\def\argmin{\operatorname{{argmin}}}
\def\Sol{\operatorname{{Sol}}}
\def\Ker{\operatorname{{Ker}}}
\def\diag{\operatorname{{diag}}}
\def\Diff{\operatorname{{Diff}}}
\def\Log{\operatorname{{Log}}}
\def\Aff{\operatorname{{Aff}}}
\def\tni{\operatorname{{int}}}
\def\_#1{{\lower 0.7ex\hbox{}}_{#1}}

\def\bib#1{\setbox0=\hbox{[01]}\par\noindent\hangindent=\wd0 #1}
\def\bibb#1{\setbox0=\hbox{[01] Ma}\par\noindent\hangindent=\wd0 #1}

\def\itemitemitem{\par\indent\indent
      \hangindent3\parindent\textindent}
\def\itemitemitemitem{\par\indent\indent\indent
      \hangindent4\parindent\textindent}
\def\itemitemitemitemitem{\par\indent\indent\indent\indent\indent
      \hangindent5\parindent\textindent}

\vglue 30pt

\centerline{\bf AN EXTREMAL PROBLEM IN THE HYPERCUBE AND}
\centerline{\bf OPTIMIZATION OF ASYNCHRONOUS CIRCUITS}

\vglue .3in

\centerline{Carlos Gustavo T. de A. Moreira and Pablo Emanuel}

\bigskip

\centerline{IMPA-Instituto de Matem\'atica Pura e Aplicada}
\centerline{Estrada Dona Castorina, 110 - Jardim Botanico}
\centerline{22460-320, Rio de Janeiro-RJ}
\centerline{Brasil}

\vglue .2in

\centerline{gugu\@ impa.br \qquad\qquad\qquad pablo\@ impa.br}

\vglue .2in

\topmatter

\abstract{We prove that if $m\ge2$ then the minimum $k\in\Bbb N$ such that the 
$k$-cube $\{0,1\}^k$ can be decomposed as the disjoint union of connected adjacent subsets satisfies $2\log_2m-\log_2\log_2m-1\le k\le 2\lceil \log_2m\rceil-
\lfloor \log_2\log_2 m\rfloor + 5$.}\endabstract

\endtopmatter

\noindent{\bf Introduction}

\vglue .2in

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 \lceil \log_2 m
\rceil -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:  

$\bullet$ Each state is assigned to a subset of the set of the $k$-bit words (that can be viewed as the $k$-cube $\big(\bz/2\bz\big)^k$).

$\bullet$ 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,\dots,A_m$ such that for each
$i$,\,\, $j \le m$ there is a pair of adjacent vertices, one of them in
$A_i$ and the other one in $A_j$\,.


\newpage

\noindent{\bf Statements and Proofs}

\vglue .1in

\noindent
{\bf Definition:} We say that two subsets $A,B$ of a hypercube $\{0,1\}^k$ are adjacent if there are two adjacent points $x\in A$, $y\in B$.

\noindent
{\bf Proposition 1.} {\sl If $m\ge2$ and the $k$-cube $\{0,1\}^k$ can be divided as the union of $m$ disjoint adjacent subsets then $k\ge 2\log_2 m-\log_2\log_2m-1$.}

\vglue .1in

\noindent
{\bf Proof:}   
Suppose that the $k$-cube $\{0,1\}^k$ can be divided in $m$ disjoint subsets $A_1,A_2,\dots,A_m$ such that for each $i,j \le m$ there are $x,y$ adjacent vertices such that $x \in A_i$\,, $y \in A_j$\,. Then there is one of the sets $A_i$ such that $A_i$ has at most $\lfloor 2^k/m \rfloor$ elements and, since any vertex has exactly $k$ adjacent vertices and every $A_j$ is adjacent to $A_i$ for $j\ne i$, we have $k\lfloor2^k/m \rfloor \ge m-1 \Rightarrow k2^k \ge m(m-1)$, and so we have $k \ge 2 \log_2m - \log_2\log_2m-1$ for $m \ge 2$. \qed

\bigskip

\noindent
{\bf Proposition 2.} If $m\ge2$ then  the 
$k$-cube $\{0,1\}^k$ can be decomposed as the disjoint union of connected adjacent subsets for some $k\le 2\lceil \log_2m\rceil-
\lfloor \log_2\log_2 m\rfloor + 5$

\bigskip

\noindent
{\bf 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= \lceil \log_2m\rceil$, $r=\lfloor \frac n2 \rfloor$, $p=\lfloor \log_2 r \rfloor$. We will construct a decomposition of the $k$-cube, where $k=4+2n-p\le 2 \lceil\log_2 m\rceil - \lfloor \log_2\log_2 m \rfloor+5$.


Let us write a typical element of the $k$-cube as $\und{u} = a_1a_2bc\,\, \und{x_0}\,\,\und{x_1}\,\,\und{y}$, where $a_1, a_2,b$ and $c$ are bits, $\und{x_0}$, $\und{x_1}$ belongs to the $(n-r)$-cube $\{0,1\}^r$ and $\und{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 $\bz/2\bz$ with the canonical basis $\{e_1,e_2,\dots,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 \le \log_2r$, we have $2^p \le r$ so there is a surjective function $\tilde f\colon \{e_1,e_2,\dots,e_r\}\to \big(\bz/2\bz\big)^p$ that extends in a unique way to a linear function $f\colon \big(\bz/2\bz\big)^r \to \big(\bz/2\bz\big)^p$. It follows that given $v \in \big(\bz/2\bz\big)^r$ and $w \in \big(\bz/2\bz\big)^p$ there is an element $e_j$ of the canonical basis of $\big(\bz/2\bz\big)^r$ such that $f(v+e_j) = w$ (note that $v+e_j$ is adjacent to $v$). Since $n-r\ge r$ we have a linear function $g\colon(\bz/2\bz)^{n-r} \to (\bz/2\bz)^p$ analogous to $f$.

We may define now a function $F\colon \big(\bz/2\bz\big)^k \to \big(\bz/2\bz\big)^{2r}$ in the following way: for $\und{u} = a_1a_2bc \,\, \und{x_0} \,\, \und{x_1}\,\, \und{y} \in \big(\bz/2\bz\big)^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 $\und{u}$ is of type I and define $F(\und{u}) = \und{x_0}\,\, \und{x_1}$\,; otherwise we say that $u$
is of type II and define 
$$
F(\und{u})= \cases
f(\und{x_0})\und{y}, \quad \text{ if } c=0 \\
g(\und{x_1})\und{y}, \quad \text{ if } c=1 \endcases
$$
We claim that the $2^{n}$ sets $F^{-1}(\und{x})$, $\und{x}\in(\bz/2\bz)^{n}$ are disjoint, connected and adjacent, so,
given a bijection $h\colon \big(\bz/2\bz\big)^{2r} \to \{1,2,\dots,2^{2r}\}$ (for instance $h(\sigma_1,\sigma_2,\dots,\sigma_{2r}) = 1 + \sum\limits_{\ell=1}^{2r} \sigma_\ell 2^{\ell-1}$), the decomposition of $\big(\bz/2\bz\big)^k$ as $A_1 \cup A_2 \cup \dots \cup A_m$ where $A_i = (h\circ F)^{-1}(i)$ for $1 \le i < m$,\,\,\, 
$A_m = \bigcup\limits_{j\ge m}(h\circ F)^{-1}(j)$ satisfies the conditions of our problem.

To prove this let us first verify that for each $\und{x},\und{y}$ in $(\bz/2\bz)^n$ there are adjacent vertices $\und{u_1} \in F^{-1}(\und{x})$,\,\, $\und{u_2} \in
F^{-1}(\und{y})$. If $\und{x} = \widetilde{\und{x_o}}\,\,\widetilde{\und{x_1}} \in \big(\bz/2\bz\big)^{n}=(\bz/2\bz)^r\times (\bz/2\bz)^{n-r}$ we can take $a_1=0$, $a_2=1$ and $b$ such that $b^*=0$, and $\tilde{\und{y}} \in \big(\bz/2\bz\big)^{2r-p}$ equal to the projection of $\und{y}$ in the last $2r-p$ coordinates. We will have $F(01b0\widetilde{\und{x_0}}\,\,\widetilde{\und{x_1}}\,\, \widetilde{\und{y}}) = \widetilde{\und{x}}$, and we can take $\und{x_0}'$ adjacent to $\widetilde{\und{x_0}}$ such that $f(\und{x_0}')$ is the projection of $\und{y}$ in the first $p$ coordinates, so $01b0 \und{x_0}'\,\,\widetilde{\und{x_1}}\,\, \widetilde{\und{y}}$ is adjacent to $01b0\widetilde{\und{x_0}}\,\,\widetilde{\und{x_1}}\,\, \widetilde{\und{y}}$ and $F(01b0 \und{x_0'} \,\, \widetilde{\und{x_1}}\,\, \widetilde{\und{y}}) = \und{y}$.

Now we will prove that the sets $F^{-1}(\und{x})$ are connected. We can decompose $F^{-1}(\und{x})$ as $B_{\und{x}} \cup C_{\und{x}}$ where
$$
\align
&B_{\und{x}} = \{\und{u} \in F^{-1}(\und{x}) \mid \und{u} \text{ if of type I}\}\quad\text{and}\\
&C_{\und{x}} = \{\und{u} \in F^{-1}(\und{x}) \mid \und{u} \text{ is of type II}\}.
\endalign
$$
The previous argument can be used to show that $B_{\und{x}}$ and $C_{\und{x}}$ are adjacent since there are adjacent elements $\und{u_1}\in B_{\und{x}} $ and $\und{u_2} \in C_{\und{x}}$\,.  It is enough to prove that $B_{\und{x}}$ and $C_{\und{x}}$ are connected.

If $\und{u} = a_1a_2b c\,\, \und{x_0} \,\, \und{x_1}\,\, \und{y} \in B_{\und{x}}$\,, then $\und{u}$ is equal or adjacent to $\und{u}'= 00bc \,\,\und{x_0}\,\, \und{x_1}\,\,\und{y} \in B_{\und{x}}$\,, and the set $\widetilde B_{\und{x}}$ of the $\und{u}'\in B_{\und{x}}$; such that $a_1=a_2=0$ is clearly connected, since it is equal to $\{\und{u}'= 00bc \,\,\und{x_0}\,\, \und{x_1}\,\, \und{y} \mid \und{x_0} \,\, \und{x_1} = \und{x}\}$, that is a face of the hypercube $\{0,1\}^k$.

If $\und{u} = a_1a_2bc\,\, \und{x_0}\,\, \und{x_1}\,\, \und{y} \in C_{\und{x}}$ then $\und{u}$ is equal or adjacent to $\und{u}'' = 11bc \,\,\und{x_0}\,\, \und{x_1}\,\,\und{y} \in C_{\und{x}}$\,. The set $\widetilde C_{\und{x}} = \{\und{u}'' \in C_{\und{x}} \mid a_1=a_2=1\}$ can be decomposed as $D_{\und{x}} \cup E_{\und{x}}$ where $D_{\und{x}} = \{\und{u}'' \in C_{\und{x}} \mid a_1=a_2=1$ and $c=0\}$ and $E_{\und{x}} = \{\und{u}'' \in C_{\und{x}} \mid a_1=a_2=1$ and $c=1\}$. To prove that $\widetilde C_{\und{x}}$ (and so $C_{\und{x}}$) is connected, it is enough to show
that any element $\und{u}_1 \in D_{\und{x}}$ can be joined by a path in $\widetilde C_{\und{x}}$ to any element $\und{u_2} \in E_{\und{x}}$\,. This is a consequence of the following facts:

$\bullet$\,\,$\und{u_1} = 11\tilde b0\,\,\widetilde{\und{x_0}}\,\,\widetilde{\und{x_1}}\,\, \tilde{\und{y}}$ belongs to the connected set $L(\und{u_1})$ contained in $D_{\und{x}}$ defined as 
$$
L(\und{u_1}) = \{11b0 \,\,\und{x_0} \,\, \und{x_1}\,\, \und{y} \in D_{\und{x}} \mid \und{x_0} = \widetilde{\und{x_0}}, \und{y} = \tilde{\und{y}}\}.
$$

 $\bullet$\,\,$\und{u_2} = 11  b' 1 \,\,\und{x_0}'\,\,\und{x_1}'\,\, \tilde{\und{y}}$ belongs to the connected set $M(\und{u_2})$ contained in $E_{\und{x}}$ defined as 
$$
M(\und{u_2}) = \{11b1\,\, \und{x_0}\,\, \und{x_1}\,\, \und{y} \mid \und{x_1} = 
\und{x_1}', \und{y} = \tilde{\und{y}}\}
$$

$\bullet$\,\,\, $(11\tilde b0\,\,\widetilde{\und{x_0}}\,\, \und{x_1}' \,\, \tilde{\und{y}}) \in L(\und{u_1})$
and  $(11\tilde b 1\,\,\widetilde{\und{x_0}}\,\, \und{x_1}'\,\,\tilde{\und{y}}) \in M(\und{u_2})$
 are adjacent. \qed

\vglue .3in

\centerline{\bf REFERENCES}

\vglue .1in

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

\item{[2]} Z. Kohavi, \ {\it Switching and Finite Automata Theory,\/} McGraw-Hill computer science series, 1978 


\enddocument
