gray.tex

   1 On  a vu  dans  la  partie précédente  que  pour avoir  un  générateur à  sortie
   2 uniforme, il est nécessaire que  la matrice d'adjacence du graphe d'itération du
   3 système  soit doublement stochastique.   Nous présentons  dans cette  partie une
   4 méthode permettant de générer de telles matrices.
   5
   6 Les approches théoriques basées sur la programmation logique par contraintes sur
   7 domaines  finis ne  sont pas  envisageables en  pratique dès  que la  taille des
   8 matrices considérées devient suffisamment grande.
   9
  10 Une approche plus pragmatique consiste  à supprimer un cycle hamiltonien dans le
  11 graphe d'itérations, ce qui revient à supprimer en chaque n{\oe}ud de ce graphe une
  12 arête sortante et une arête entrante.
  13
  14 \begin{xpl}
  15   On considère   le
  16   $3$-cube   dans  lequel  le cycle hamiltonien défini par la séquence
  17   $000,100,101,001,011,111,110,010,000$ a été supprimé.
  18   Ceci correspond à la fonction $f^*$ définie par
  19 $$f^*(x_1,x_2,x_3)=
  20 (x_2 \oplus x_3, \overline{x_1}\overline{x_3} + x_1\overline{x_2},
  21 \overline{x_1}\overline{x_3} + x_1x_2).
  22 $$
  23
  24 Le graphe  des itérations chaotiques de  $f^*$  est représenté à la
  25 Figure~\ref{fig:iteration:f*}.
  26 La matrice de Markov correspondante est donnée à
  27 la figure~\ref{fig:markov:f*}.
  28
  29 \begin{figure}[ht]
  30   \begin{center}
  31     \subfloat[Graphe des itérations chaotiques de $f^*$.
  32     \label{fig:iteration:f*}]{
  33       \begin{minipage}{0.55\linewidth}
  34         \centering
  35         \includegraphics[width=\columnwidth]{images/iter_f}%
  36       \end{minipage}
  37     }%
  38     \subfloat[Matrice de Markov du graphe d'itérations chaotiques de
  39     $f^*$\label{fig:markov:f*}]{%
  40       \begin{minipage}{0.35\linewidth}
  41         \begin{scriptsize}
  42           \begin{center}
  43             $ \dfrac{1}{4} \left(
  44               \begin{array}{cccccccc}
  45                 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\
  46
  47                 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\
  48
  49                 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\
  50
  51                 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\
  52
  53                 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\
  54
  55                 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
  56
  57                 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
  58
  59                 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\
  60
  61               \end{array}            \right) $
  62           \end{center}
  63         \end{scriptsize}
  64       \end{minipage}
  65     }%
  66     \caption{Représentations de $f^*(x_1,x_2,x_3)=
  67       (x_2 \oplus x_3, \overline{x_1}\overline{x_3} + x_1\overline{x_2},
  68       \overline{x_1}\overline{x_3} + x_1x_2)$.}\label{fig1}
  69   \end{center}
  70 \end{figure}
  71 \end{xpl}
  72
  73 \subsection{Suppression des cycles hamiltoniens}
  74 \label{sec:hamiltonian}
  75
  76 Dans un premier temps, nous montrons en section~\ref{sub:removing:theory} que la
  77 suppression  d'un  cycle  hamiltonien   produit  bien  des  matrices  doublement
  78 stochastiques.   Nous  établissons  ensuite  le  lien avec  les  codes  de  Gray
  79 équilibrés.
  80
  81 \subsubsection{Aspects théoriques}
  82 \label{sub:removing:theory}
  83
  84 Nous donnons  deux résultats complémentaires, reliant la  suppression d'un cycle
  85 hamiltonien  du $n$-cube,  les matrices  doublement stochastiques  et  la forte
  86 connexité du graphe d'itérations.
  87
  88 \begin{Theo}\label{th:supprCH}
  89   La suppression d'un cycle hamiltonien dans une matrice de Markov $M$, issue du
  90   $n$-cube, produit une matrice doublement stochastique.
  91 \end{Theo}
  92 \begin{Proof}
  93
  94 Un cycle hamiltonien passe par chaque n{\oe}ud une et une seule fois.
  95 Pour chaque n{\oe}ud $v$ dans le $n$-cube $C_1$,
  96 une arête entrante $(o,v)$ et une arête sortante $(v,e)$
  97 est ainsi enlevée.
  98 Considérons un autre  $n$-cube $C_2$ auquel on ajoute les arêtes
  99 pour le rendre complet. La matrice de Markov $M$ correspondante est
 100 remplie de $\frac{1}{2^n}$ et est doublement stochastique.
 101 Comme on enlève exactement une arête sortante $(v,e)$
 102 à chaque n{\oe}ud $v$ dans $C_1$, on enlève ainsi dans
 103 $C_2$ les $2^{n-1}$ arêtes issues de $v$ et
 104 relatives aux parties de $\{1,\ldots,n\}$ qui
 105 contiennent $e$. Cela revient à annuler
 106 dans la matrice $M$ les $2^{n-1}$ coefficients correspondants et ajouter
 107 $1/2$ à l'élément $M_{vv}$.
 108 La matrice $M$ reste stochastique.
 109 On effectue un raisonnement similaire pour les arêtes entrantes:
 110 comme on enlève exactement une arête entrante $(o,v)$ pour chaque
 111 n{\oe}ud $v$ dans $C_1$, dans $C_2$, ce sont exactement
 112 $2^{n-1}$ arêtes menant à $v$ qui sont enlevées.
 113 Dans $M$ les $2^{n-1}$ coefficients correspondants sont mis à 0 et
 114 $M_{vv}$ vaut alors $\frac{2^{n-1} +1}{2}$.
 115 $M$ est donc doublement stochastique.
 116 \end{Proof}
 117
 118
 119
 120 \begin{Theo}\label{th:grapheFC}
 121   Le  graphe d'itérations  issu du  $n$-cube,  auquel un  cycle hamiltonien  est
 122   enlevé, est fortement connexe.
 123 \end{Theo}
 124
 125
 126 \begin{Proof}
 127 On considère les deux $n$-cubes $C_1$ et $C_2$ définis
 128 dans la preuve du théorème~\ref{th:supprCH}.
 129 Dans $C_1$ on considère le cycle inverse $r$ du cycle
 130 hamiltonien $c$.
 131 Aucun arc n'appartient à la fois  à $r$ et à $c$:
 132 en effet, sinon $c$ contiendrait un n{\oe}ud deux fois.
 133 Ainsi aucune arête de $r$ n'est enlevée dans $C_1$.
 134 Le cycle $r$ est évidement un cycle hamiltonien et contient tous les n{\oe}uds.
 135 Tous les n{\oe}uds de $C_1$ dans lequel $c$ a été enlevé sont accessibles
 136 depuis n'importe quel n{\oe}ud. Le graphe des itérations $\Gamma$ qui
 137 étend le précédent graphe est ainsi fortement connexe.
 138
 139 \end{Proof}
 140
 141
 142
 143 Les preuves, relativement directes, sont  laissées en exercices au lecteur.  Par
 144 contre, ce qui  est moins aisé est la génération de  cycles hamiltoniens dans le
 145 $n$-cube,  ce qui  revient à  trouver des  \emph{codes de  Gray  cycliques}.  On
 146 rappelle que  les codes de  Gray sont des  séquences de mots binaires  de taille
 147 fixe ($n$),  dont les éléments successifs ne  différent que par un  seul bit. Un
 148 code  de  Gray est  \emph{cyclique}  si  le premier  élément  et  le dernier  ne
 149 différent que par un seul bit.
 150
 151 \subsection{Lien avec les codes de Gray cycliques (totalement) équilibrés}
 152 \label{sub:gray}
 153
 154 La borne  inférieure du  nombre de codes  de Gray  ($\left(\frac{n*\log2}{e \log
 155     \log   n}\times(1  -  o(1))\right)^{2^n}$),   donnée  dans~\cite{Feder2009NTB},
 156 indique  une explosion combinatoire  pour notre  recherche.  Afin  de contourner
 157 cette  difficulté,  nous  nous   restreignons  aux  codes  induisant  un  graphe
 158 d'itérations $\Gamma(f)$  \emph{uniforme}.  Cette uniformité se  traduit par des
 159 nombres d'arcs  équilibrés entre les  \emph{dimensions} du graphe,  la dimension
 160 $i$  correspondant aux  seules variations  du  bit $i$  (parmi les  $n$ bits  au
 161 total).   Cette  approche  revient  à  chercher  des  codes  de  Gray  cycliques
 162 \emph{équilibrés}.
 163
 164 Un code de Gray équilibré peut être défini de la façon suivante :
 165
 166 \begin{Def}[Code de Gray cyclique équilibré]\label{def:grayequ}
 167   Soit $L = w_1,  w_2, \dots, w_{2^n}$ la séquence d'un code  de Gray cyclique à
 168   $n$ bits.  Soit $S = s_1,  s_2, \dots, s_{2^n}$ la séquence des transitions où
 169   $s_i$, $1  \le i \le 2^n$  est l'indice du seul  bit qui varie  entre les mots
 170   $w_i$ et  $w_{i+1}$. Enfin, soit  $\textit{NT}_n : \{1,\dots,  n\} \rightarrow
 171   \{0, \ldots, 2^n\}$  la fonction qui au paramètre  $i$ associe le \emph{nombre
 172     de transitions} présentes dans la séquence $L$ pour le bit $i$, c'est-à-dire
 173   le nombre d'occurrences de $i$ dans $S$.
 174
 175   Le      code       $L$      est      \textbf{équilibré}       si      $\forall
 176   i,j\in\{1,...,n\},~|\textit{NT}_n(i)  -  \textit{NT}_n(j)|  \le  2$.   Il  est
 177   \textbf{totalement             équilibré}             si             $\forall
 178   i\in\{1,...,n\},~\textit{NT}_n(i)=\frac{2^n}{n}$.
 179 \end{Def}
 180
 181 On peut  donc déjà déduire  qu'il ne peut  exister des codes de  Gray totalement
 182 équilibrés que  pour les  systèmes ayant un  nombre d'éléments $n=2^k,  k>0$. De
 183 plus,  comme  dans tout  code  de  Gray  cyclique, $\textit{NT}_n(i)$  est  pair
 184 $\forall  i\in\{1,...,n\}$,  alors  les  systèmes  ayant  un  nombre  d'éléments
 185 différent  de $2^k$,  ne peuvent  avoir  que des  codes de  Gray équilibrés  avec
 186 $\textit{NT}_n(i)=\lfloor\frac{2^n}{n}\rfloor$                                 ou
 187 $\textit{NT}_n(i)=\lceil\frac{2^n}{n}\rceil,    \forall    i\in\{1,...,n\}$   et
 188 vérifiant $\sum_{i=1}^nNT_n(i) = 2^n$.
 189
 190 \begin{xpl}
 191   Soit  $L^*=000,100,101,001,011,111,110,010$ le code  de Gray  correspondant au
 192   cycle hamiltonien enlevé de $f^*$.  Sa séquence des transitions est \linebreak
 193   $S=3,1,3,2,3,1,3,2$  et  les nombres  de  transitions sont  $\textit{TC}_3(1)=
 194   \textit{TC}_3(2)=2$ et $\textit{TC}_3(3)=4$. Un tel code est équilibré.
 195
 196   Si l'on  considère maintenant $L^4=$ 0000,  0010, 0110, 1110, 1111,  0111, 0011,
 197   0001,  0101, 0100,  1100, 1101,  1001,  1011, 1010,  1000,  un  code de  Gray
 198   cyclique. En construisant la séquence $S=$ 2,3,4,1,4,3,2,3,1,4,1,3,2,1,2,4,
 199   on constate que  $\forall
 200   i\in\{1,..,4\},~\textit{TC}_4(i)=4$ et donc que
 201   ce code est totalement équilibré.
 202 \end{xpl}
 203
 204 \subsection{Génération de codes de Gray équilibrés par induction}
 205 \label{sec:induction}
 206
 207 Dans  leur  article de  2004~\cite{ZanSup04},  Zanten  et  Suparta proposent  un
 208 algorithme inductif  pour générer  des codes  de Gray équilibrés  de $n$  bits à
 209 partir   de  codes   de  $n-2$   bits.   Cependant,   leur  méthode   n'est  pas
 210 constructive. En effet, elle effectue  des manipulations sur un partitionnement du
 211 code de Gray  initial de $n-2$ bits pour  obtenir un code de Gray  sur $n$ bits,
 212 mais le  résultat n'est pas  systématiquement équilibré. Il est  donc nécessaire
 213 d'évaluer les résultats obtenus à  partir de tous les partitionnements réalisables
 214 en suivant les  contraintes spécifiées.  Or, le nombre  de possibilités augmente
 215 exponentiellement (voir~\cite{Mons14} pour  l'évaluation détaillée), ce qui rend
 216 déraisonnable    tout   parcours    exhaustif.    Une    amélioration   proposée
 217 dans~\cite{Mons14} permet  de réduire le nombre  de partitionnements considérés,
 218 mais l'ordre  de grandeur  reste similaire. On  constate donc clairement  ici la
 219 nécessité de trouver  des algorithmes de génération de  codes de Gray équilibrés
 220 plus  efficaces.  Ce  problème  représente  une des  voies  que nous  souhaitons
 221 explorer dans la suite de nos travaux.
 222
 223 Le   tableau~\ref{table:nbFunc}  donne  le   nombre  de   fonctions  différentes
 224 compatibles avec les codes de  Gray équilibrés générés par l'approche précédente
 225 selon le nombre  de bits. Il donne  donc la taille de la  classe des générateurs
 226 pouvant être produits.  Les  cas 7 et 8 ne sont que  des bornes minimales basées
 227 sur des sous-ensembles des partitionnements possibles.
 228
 229 \begin{table}[table:nbFunc]{Nombre de générateurs selon le nombre de bits.}
 230   \begin{center}
 231     \begin{tabular}{|l|c|c|c|c|c|}
 232       \hline
 233       $n$              & 4 & 5 & 6    & 7      & 8      \\
 234       \hline
 235       nb. de fonctions & 1 & 2 & 1332 & > 2300 & > 4500 \\
 236       \hline
 237     \end{tabular}
 238   \end{center}
 239 \end{table}
 240
 241
 242 %%% Local Variables:
 243 %%% mode: latex
 244 %%% TeX-master: "main"
 245 %%% End: