hamilton.tex

   1 Many approaches have been developed to solve the problem of building
   2 a Gray code in a $\mathsf{N}$ cube~\cite{Robinson:1981:CS,DBLP:journals/combinatorics/BhatS96,ZanSup04,Bykov2016}, according to properties
   3 the produced code has to verify.
   4 For instance,~\cite{DBLP:journals/combinatorics/BhatS96,ZanSup04} focus on
   5 balanced Gray codes. In the transition sequence of these codes,
   6 the number of transitions of each element must differ
   7 at most by 2.
   8 This uniformity is a global property on the cycle, \textit{i.e.}
   9 a property that is established while traversing the whole cycle.
  10 On the opposite side, when the objective is to follow a subpart
  11 of the Gray code and to switch each element approximately the
  12 same amount of times,
  13 local properties are wished.
  14 For instance, the locally balanced property is studied in~\cite{Bykov2016}
  15 and an algorithm that establishes locally balanced Gray codes is given.
  16
  17 The current context is to provide a function
  18 $f:\Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ by removing a Hamiltonian
  19 cycle in the $\mathsf{N}$ cube. Such a function is going to be iterated
  20 $b$ time to produce a pseudo random number, \textit{i.e.} a vertex in the
  21 $\mathsf{N}$ cube.
  22 Obviously, the number of iterations $b$ has to be sufficiently large
  23 to provide a uniform output distribution.
  24 To reduced the number of iterations, the provided Gray code
  25 should ideally possess the both balanced and locally balanced properties.
  26 However, none of the two algorithms is compatible with the second one:
  27 balanced Gray codes that are generated by state of the art works~\cite{ZanSup04,DBLP:journals/combinatorics/BhatS96} are not locally balanced. Conversely,
  28 locally balanced Gray codes yielded by Igor Bykov approach~\cite{Bykov2016}
  29 are not globally balanced.
  30 This section thus shows how the non deterministic approach
  31 presented in~\cite{ZanSup04} has been automatized to provide balanced
  32 Hamiltonian paths such that, for each subpart,
  33 the number of switches of each element is as uniform as possible.
  34
  35 \subsection{Analysis of the Robinson-Cohn extension algorithm}
  36 As far as we know three works,
  37 namely~\cite{Robinson:1981:CS},~\cite{DBLP:journals/combinatorics/BhatS96},
  38 and~\cite{ZanSup04} have adressed the probem of providing an approach
  39 to produce balanced gray code.
  40 The authors of~\cite{Robinson:1981:CS} introduced an inductive approach
  41 aiming at producing balanced Gray codes, provided the user gives
  42 a special subsequence of the transition sequence at each induction step.
  43 This work have been strengthened in~\cite{DBLP:journals/combinatorics/BhatS96}
  44 where the authors have explicitely shown how to construct such a subsequence.
  45 Finally the authors of~\cite{ZanSup04} have presented
  46 the \emph{Robinson-Cohn extension}
  47 algorithm. There rigourous presentation of this one
  48 have mainly allowed them to prove two properties.
  49 The former states that if
  50 $\mathsf{N}$ is a 2-power, a balanced Gray code is always totally balanced.
  51 The latter states that for every $\mathsf{N}$ there
  52 exists a Gray code such that all transition count numbers are
  53 are 2-powers whose exponents are either equal
  54 or differ from each other by 1.
  55 However, the authors do not prove that the approach allows to build
  56 (totally balanced) Gray code.
  57 What follows shows that this fact is established and first recalls the approach.
  58
  59
  60 Let be given a $\mathsf{N}-2$-bit Gray code whose transition sequence is
  61 $S_{\mathsf{N}-2}$. What follows is the
  62  \emph{Robinson-Cohn extension} method~\cite{ZanSup04}
  63 which produces a $n$-bits Gray code.
  64
  65 \begin{enumerate}
  66 \item \label{item:nondet}Let $l$ be an even positive integer. Find
  67 $u_1, u_2, \dots , u_{l-2}, v$ (maybe empty) subsequences of $S_{\mathsf{N}-2}$
  68 such that $S_{\mathsf{N}-2}$ is the concatenation of
  69 $$
  70 s_{i_1}, u_0, s_{i_2}, u_1, s_{i_3}, u_2, . . . , s_{i_l-1}, u_{l-2}, s_{i_l}, v
  71 $$
  72 where $i_1 = 1$, $i_2 = 2$, and $u_0 = \emptyset$ (the empty sequence).
  73 \item Replace in $S_{\mathsf{N}-2}$ the sequences $u_0, u_1, u_2, \ldots, u_{l-2}$
  74   by
  75   $\mathsf{N} - 1,  u'(u_1,\mathsf{N} - 1, \mathsf{N}) , u'(u_2,\mathsf{N}, \mathsf{N} - 1), u'(u_3,\mathsf{N} - 1,\mathsf{N}), \dots, u'(u_{l-2},\mathsf{N}, \mathsf{N} - 1)$
  76   respectively, where $u'(u,x,y)$ is the sequence $u,x,u^R,y,u$ such that
  77   $u^R$ is $u$ in reversed order.
  78   The obtained sequence is further denoted as $U$.
  79 \item Construct the sequences $V=v^R,\mathsf{N},v$, $W=\mathsf{N}-1,S_{\mathsf{N}-2},\mathsf{N}$, and let $W'$ be $W$ where the first
  80 two elements have been exchanged.
  81 \item The transition sequence $S_{\mathsf{N}}$ is thus the concatenation $U^R, V, W'$.
  82 \end{enumerate}
  83
  84 It has been proven in~\cite{ZanSup04} that
  85 $S_{\mathsf{N}}$ is transition sequence of a cyclic $\mathsf{N}$-bits Gray code
  86 if $S_{\mathsf{N}-2}$ is.
  87 However, the step~(\ref{item:nondet}) is not a constructive
  88 step that precises how to select the subsequences which ensures that
  89 yielded Gray code is balanced.
  90 Next section shows how to choose the sequence $l$ to have the balancy property.
  91
  92 \subsection{Balanced Codes}
  93 Let us first recall how to formalize the balancy property of a Gray code.
  94 Let  $L = w_1, w_2, \dots, w_{2^\mathsf{N}}$ be the sequence
  95 of a $\mathsf{N}$-bits cyclic Gray code.
  96 The  transition sequence
  97 $S = s_1, s_2, \dots, s_{2^n}$, $s_i$, $1 \le i \le 2^\mathsf{N}$,
  98 indicates which bit position changes between
  99 codewords at index $i$ and $i+1$ modulo $2^\mathsf{N}$.
 100 The \emph{transition count} function
 101 $\textit{TC}_{\mathsf{N}} : \{1,\dots, \mathsf{N}\} \rightarrow \{0, \ldots, 2^{\mathsf{N}}\}$
 102 gives the number of times $i$ occurs in $S$,
 103 \textit{i.e.}, the number of times
 104 the bit $i$ has been switched in $L$.
 105
 106 The Gray code is \emph{totally balanced} if $\textit{TC}_{\mathsf{N}}$
 107 is constant (and equal to $\frac{2^{\mathsf{N}}}{\mathsf{N}}$).
 108 It is \emph{balanced} if for any two bit indices $i$ and $j$,
 109 $|\textit{TC}_{\mathsf{N}}(i) - \textit{TC}_{\mathsf{N}}(j)| \le  2$.
 110
 111
 112
 113 \begin{xpl}
 114 Let $L^*=000,100,101,001,011,111,110,010$ be the Gray code that corresponds to
 115 the Hamiltonian cycle that has been removed in $f^*$.
 116 Its transition sequence is $S=3,1,3,2,3,1,3,2$ and its transition count function is
 117 $\textit{TC}_3(1)= \textit{TC}_3(2)=2$ and  $\textit{TC}_3(3)=4$. Such a Gray code is balanced.
 118
 119 Let now
 120 $L^4=0000, 0010, 0110, 1110, 1111, 0111, 0011, 0001, 0101,$
 121 $0100, 1100, 1101, 1001, 1011, 1010, 1000$
 122 be a cyclic Gray code. Since $S=2,3,4,1,4,3,2,3,1,4,1,3,2,1,2,4$ $\textit{TC}_4$ is equal to 4 everywhere, this code
 123 is thus totally balanced.
 124
 125 On the contrary, for the standard $4$-bits Gray code
 126 $L^{\textit{st}}=0000,0001,0011,0010,0110,0111,0101,0100,1100,$
 127 $1101,1111,1110,1010,1011,1001,1000$,
 128 we have $\textit{TC}_4(1)=8$ $\textit{TC}_4(2)=4$ $\textit{TC}_4(3)=\textit{TC}_4(4)=2$ and
 129 the code is neither balanced nor totally balanced.
 130 \end{xpl}
 131
 132
 133 \begin{thrm}\label{prop:balanced}
 134 Let $\mathsf{N}$ in $\Nats$, and $a_{\mathsf{N}}$ be defined by
 135 $a_{\mathsf{N}}= 2 \lfloor \dfrac{2^{\mathsf{N}}}{2\mathsf{N}} \rfloor$.
 136 Then, there exists a sequence $l$ in
 137 step~(\ref{item:nondet}) of the \emph{Robinson-Cohn extension} algorithm
 138 such that all the transition counts $\textit{TC}_{\mathsf{N}}(i)$
 139 are $a_{\mathsf{N}}$ or $a_{\mathsf{N}}+2$
 140 for any $i$, $1 \le i \le \mathsf{N}$.
 141
 142
 143
 144
 145 \end{thrm}
 146
 147
 148
 149
 150 \begin{proof}
 151
 152
 153
 154 \end{proof}
 155
 156 \subsection{Toward a local uniform distribution of switches}