On a vu dans le chapitre précédent que pour avoir
un générateur à sortie
uniforme, il est nécessaire que la matrice d'adjacence du graphe d'itération du
-système soit doublement stochastique. Nous présentons dans cette partie une
-méthode permettant de générer de telles matrices.
-
-Les approches théoriques basées sur la programmation logique par contraintes sur
-domaines finis ne sont pas envisageables en pratique dès que la taille des
-matrices considérées devient suffisamment grande.
-
+système soit doublement stochastique. Nous présentons dans cette partie
+des méthodes effectives permettant de générer de telles matrices.
+La première est basée sur la programmation logique par contraintes
+(Section~\ref{sec:plc}).
+Cependant celle-ci souffre de ne pas passer à l'échelle et ne fournit pas
+une solution en un temps raisonnable dès que la fonction à engendrer
+porte sur un grand nombre de bits.
Une approche plus pragmatique consiste à supprimer un cycle hamiltonien dans le
-graphe d'itérations, ce qui revient à supprimer en chaque n{\oe}ud de ce graphe une
-arête sortante et une arête entrante.
+graphe d'itérations $\textsc{giu}(\neg)$ (section~\ref{sec:hamiltonian}).
+Pour obtenir plus rapidement une distribution uniforme, l'idéal serait
+de supprimer un cycle hamiltonien qui nierait autant de fois chaque bit.
+Cette forme de cycle est dit équilibré. La section~\ref{sub:gray} établit le
+lien avec les codes de Gray équilibrés, étudiés dans la litérature.
+La section suivante présente une démarche de génération automatique de code de Gray équilibré (section~\ref{sec:induction}).
+La vitesse avec laquelle l'algorithme de PRNG converge en interne vers
+une distribution unifiorme est étduiée théoriquement et pratiquement à la
+section~\ref{sec:mixing}.
+L'extension du travail aux itérations généralisées est présenté à la
+section~\ref{sec:prng:gray:general}.
+Finalement, des instances de PRNGS engendrés selon les méthodes détaillées dans
+ce chapitre sont présentés en section~\ref{sec:prng;gray:tests}.
+Les sections~\ref{sec:plc} à~\ref{sub:gray} ont été publiées
+à~\ref{chgw+14:oip}.
% This aim of this section is to show
\section{Génération de codes de Gray équilibrés par induction}
\label{sec:induction}
-Dans leur article de 2004~\cite{ZanSup04}, Zanten et Suparta proposent un
-algorithme inductif pour générer des codes de Gray équilibrés de $n$ bits à
-partir de codes de $n-2$ bits. Cependant, leur méthode n'est pas
-constructive. En effet, elle effectue des manipulations sur un partitionnement du
-code de Gray initial de $n-2$ bits pour obtenir un code de Gray sur $n$ bits,
-mais le résultat n'est pas systématiquement équilibré. Il est donc nécessaire
-d'évaluer les résultats obtenus à partir de tous les partitionnements réalisables
-en suivant les contraintes spécifiées. Or, le nombre de possibilités augmente
-exponentiellement (voir~\cite{Mons14} pour l'évaluation détaillée), ce qui rend
-déraisonnable tout parcours exhaustif. Une amélioration proposée
-dans~\cite{Mons14} permet de réduire le nombre de partitionnements considérés,
-mais l'ordre de grandeur reste similaire. On constate donc clairement ici la
-nécessité de trouver des algorithmes de génération de codes de Gray équilibrés
-plus efficaces. Ce problème représente une des voies que nous souhaitons
-explorer dans la suite de nos travaux.
-
-Le tableau~\ref{table:nbFunc} donne le nombre de fonctions différentes
-compatibles avec les codes de Gray équilibrés générés par l'approche précédente
-selon le nombre de bits. Il donne donc la taille de la classe des générateurs
-pouvant être produits. Les cas 7 et 8 ne sont que des bornes minimales basées
-sur des sous-ensembles des partitionnements possibles.
+De nombreuses approches ont été developpées pour résoudre le problème de construire
+un code de Gray dans un $\mathsf{N}$-cube~\cite{Robinson:1981:CS,DBLP:journals/combinatorics/BhatS96,ZanSup04},
+selon les propriétés que doit vérifier ce code.
+
+Dans les travaux~\cite{Robinson:1981:CS}, les auteurs
+proposent une approche inductive de construction de code de Gray équilibrés
+(on passe du $\mathsf{N}-2$ à $\mathsf{N}$)
+pour peu que l'utilisateur fournisse une sous-séquence possédant certaines
+propriétés à chaque pas inductif.
+Ce travail a été renforcé dans ~\cite{DBLP:journals/combinatorics/BhatS96}
+où les auteurs donnent une manière explicite de construire une telle sous-séquence.
+Enfin, les autheurs de~\cite{ZanSup04} présentent une extension de l'algorithme de
+\emph{Robinson-Cohn}. La présentation rigoureuse de cette extension leur permet
+principalement de prouver que si $\mathsf{N}$ est une puissance de 2,
+le code de Gray équilibré engendré par l'extension est toujours totalement équilibré et
+que $S_{\mathsf{N}}$ est la séquence de transition d'un code de Gray de $\mathsf{N}$ bits
+si $S_{\mathsf{N}-2}$ l'est aussi..
+Cependant les auteurs ne prouvent pas que leur approche fournit systématiquement
+un code de Gray (totalement) équilibré.
+Cette section montre que ceci est vrai en rappelant tout d'abord
+l'extension de l'algorithme de \emph{Robinson-Cohn} pour un
+code de Gray avec $\mathsf{N}-2$ bits.
-\begin{table}[ht]
- \begin{center}
- \begin{tabular}{|l|c|c|c|c|c|}
- \hline
- $n$ & 4 & 5 & 6 & 7 & 8 \\
- \hline
- nb. de fonctions & 1 & 2 & 1332 & $>$ 2300 & $>$ 4500 \\
- \hline
- \end{tabular}
- \end{center}
-\caption{Nombre de codes de Gray équilibrés selon le nombre de bits.}\label{table:nbFunc}
-\end{table}
+\begin{enumerate}
+\item \label{item:nondet}Soit $l$ un entier positif pair. Trouver des sous-sequences
+$u_1, u_2, \dots , u_{l-2}, v$ (possiblement vides) de $S_{\mathsf{N}-2}$
+telles que $S_{\mathsf{N}-2}$ est la concaténation de
+$$
+s_{i_1}, u_0, s_{i_2}, u_1, s_{i_3}, u_2, \dots , s_{i_l-1}, u_{l-2}, s_{i_l}, v
+$$
+où $i_1 = 1$, $i_2 = 2$, et $u_0 = \emptyset$ (la séquence vide).
+\item\label{item:u'} Remplacer dans $S_{\mathsf{N}-2}$ les sequences $u_0, u_1, u_2, \ldots, u_{l-2}$
+ par
+ $\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)$
+ respectivement, où $u'(u,x,y)$ est la séquence $u,x,u^R,y,u$ telle que
+ $u^R$ est $u$, mais dans l'ordre inverse. La séquence obtenue est ensuite notée $U$.
+\item\label{item:VW} Contruire les séquences $V=v^R,\mathsf{N},v$, $W=\mathsf{N}-1,S_{\mathsf{N}-2},\mathsf{N}$. Soit alors $W'$ définie commé étant égale à $W$ sauf pour les
+deux premiers éléments qui ont été intervertis.
+\item La séquence de transition $S_{\mathsf{N}}$ est la concatenation $U^R, V, W'$.
+\end{enumerate}
+
+L'étape~(\ref{item:nondet}) n'est pas constructive: il n'est pas précisé
+comment sélectionner des sous-séquences qui assurent que le code obtenu est équilibré.
+La théoreme suivante montre que c'est possible et sa preuve explique comment le faire.
+
+
+\begin{theorem}\label{prop:balanced}
+Soit $\mathsf{N}$ dans $\Nats^*$, et $a_{\mathsf{N}}$ défini par
+$a_{\mathsf{N}}= 2 \left\lfloor \dfrac{2^{\mathsf{N}}}{2\mathsf{N}} \right\rfloor$.
+il existe une séquence $l$ dans l'étape~(\ref{item:nondet}) de l'extension
+de l'algorithme de \emph{Robinson-Cohn} extension telle que
+le nombres de transitions $\textit{TC}_{\mathsf{N}}(i)$
+sont tous $a_{\mathsf{N}}$ ou $a_{\mathsf{N}}+2$
+pour chaque $i$, $1 \le i \le \mathsf{N}$.
+\end{theorem}
+La preuve de ce théorème est donnée en annexes~\ref{anx:generateur}.
-Ces fonctions étant générée, on s'intéresse à étudier à quelle vitesse
+Ces fonctions étant générées, on s'intéresse à étudier à quelle vitesse
un générateur les embarquant converge vers la distribution uniforme.
C'est l'objectif de la section suivante.
-\section{Quantifier l'écart par rapport à la distribution uniforme}
+\section{Quantifier l'écart par rapport à la distribution uniforme}\label{sec:mixing}
On considère ici une fonction construite comme à la section précédente.
On s'intéresse ici à étudier de manière théorique les
itérations définies à l'équation~(\ref{eq:asyn}) pour une
\P_X(\tau > t)$.
\end{theorem}
+
+Soit alors $\ov{h} : \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ la fonction
+telle que pour $X \in \Bool^{\mathsf{N}} $,
+$(X,\ov{h}(X)) \in E$ et $X\oplus\ov{h}(X)=0^{{\mathsf{N}}-h(X)}10^{h(X)-1}$.
+La fonction $\ov{h}$ est dite {\it anti-involutive} si pour tout $X\in \Bool^{\mathsf{N}}$,
+$\ov{h}(\ov{h}(X))\neq X$.
+
+
\begin{theorem} \label{prop:stop}
-If $\ov{h}$ is bijective et telle que if for every $X\in \Bool^{\mathsf{N}}$,
+Si $\ov{h}$ is bijective et anti involutive
$\ov{h}(\ov{h}(X))\neq X$, alors
$E[\ts]\leq 8{\mathsf{N}}^2+ 4{\mathsf{N}}\ln ({\mathsf{N}}+1)$.
\end{theorem}
-Sans entrer dans les détails de la preuve, on remarque tout d'abord
-que le calcul
-de cette borne n'intègre pas le fait qu'on préfère enlever des
-chemins hamiltoniens équilibrés.
-En intégrant cette contrainte, la borne supérieure pourrait être réduite.
-
-On remarque ensuite que la chaîne de Markov proposée ne suit pas exactement
+Les détails de la preuve sont donnés en annexes~\ref{anx:generateur}.
+On remarque tout d'abord que la chaîne de Markov proposée ne suit pas exactement
l'algorithme~\ref{CI Algorithm}. En effet dans la section présente,
la probabilité de rester dans une configuration donnée
est fixée à $frac{1}{2}+\frac{1}{2n}$.
du temps d'arrêt.
+Sans entrer dans les détails de la preuve, on remarque aussi
+que le calcul de cette borne impose uniquement que
+pour chaque n{\oe}ud du $\mathsf{N}$-cube
+un arc entrant et un arc sortant sont supprimés.
+Le fait qu'on enlève un cycle hamiltonien et que ce dernier
+soit équilibré n'est pas pris en compte.
+En intégrant cette contrainte, la borne supérieure pourrait être réduite.
+
+En effet, le temps de mixage est en $\Theta(N\ln N)$ lors d'une
+marche aléatoire classique paresseuse dans le $\mathsf{N}$-cube.
+On peut ainsi conjecturer que cet ordre de grandeur reste le même
+dans le contexte du $\mathsf{N}$-cube privé d'un chemin hamiltonien.
+
+On peut évaluer ceci pratiquement: pour une fonction
+$f: \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ et une graine initiale
+$x^0$, le code donné à l'algorithme algorithm~\ref{algo:stop} retourne le
+nombre d'itérations suffisant tel que tous les éléments $\ell\in \llbracket 1,{\mathsf{N}} \rrbracket$ sont équitables. Il permet de déduire une approximation de $E[\ts]$
+en l'instanciant un grand nombre de fois: pour chaque nombre $\mathsf{N}$,
+$ 3 \le \mathsf{N} \le 16$, 10 fonctionss ont été générées comme dans
+ce chapitre. Pour chacune d'elle, le calcul d'une approximation de $E[\ts]$
+est exécuté 10000 fois avec une graine aléatoire.La Figure~\ref{fig:stopping:moy}
+résume ces resultats. Dans celle-ci, un cercle représente une approximation de
+$E[\ts]$ pour un $\mathsf{N}$ donné tandis que la courbe est une représentation de
+la fonction $x \mapsto 2x\ln(2x+8)$.
+On cosntate que l'approximation de $E[\ts]$ est largement inférieure
+à la borne quadratique donnée au thérème~\ref{prop:stop} et que la conjecture
+donnée au paragraphe précédent est sensée.
-\section{Et les itérations généralisées?}
+\begin{algorithm}[ht]
+%\begin{scriptsize}
+\KwIn{a function $f$, an initial configuration $x^0$ ($\mathsf{N}$ bits)}
+\KwOut{a number of iterations $\textit{nbit}$}
+
+$\textit{nbit} \leftarrow 0$\;
+$x\leftarrow x^0$\;
+$\textit{fair}\leftarrow\emptyset$\;
+\While{$\left\vert{\textit{fair}}\right\vert < \mathsf{N} $}
+{
+ $ s \leftarrow \textit{Random}(\mathsf{N})$ \;
+ $\textit{image} \leftarrow f(x) $\;
+ \If{$\textit{Random}(1) \neq 0$ and $x[s] \neq \textit{image}[s]$}{
+ $\textit{fair} \leftarrow \textit{fair} \cup \{s\}$\;
+ $x[s] \leftarrow \textit{image}[s]$\;
+ }
+ $\textit{nbit} \leftarrow \textit{nbit}+1$\;
+}
+\Return{$\textit{nbit}$}\;
+%\end{scriptsize}
+\caption{Pseudo Code of stoping time calculus }
+\label{algo:stop}
+\end{algorithm}
+
+
+\begin{figure}
+\centering
+\includegraphics[width=0.49\textwidth]{images/complexityET}
+\caption{Average Stopping Time Approximation}\label{fig:stopping:moy}
+\end{figure}
+
+
+
+
+\section{Et les itérations généralisées?}\label{sec:prng:gray:general}
Le chaptire précédent a présenté un algorithme de
PRNG construit à partir d'itérations unaires.
On pourrait penser que cet algorithme est peu efficace puisqu'il
-\section{Tests statistiques}
+\section{Tests statistiques}\label{sec:prng;gray:tests}
La qualité des séquences aléatoires produites par
le générateur des itérations unaires ainsi que
\end{table}
-%
+\section{Conclusion}
+Ce chaptitre a montré comment construire un PRNG chaotique, notamment à partir
+de codes de Gray équilibrés. Une méthode completement automatique de
+construction de ce type de codes a été présentée étendant les méthodes
+existantes.
+Dans le cas des itérations unaires,
+l'algorithme qui en découle a un temps de mélange qui a
+une borne sup quadratique de convergence vers la distribution uniforme.
+Pratiquement, ce temps de mélange se rapproche de $N\ln N$.
+Les expérimentations au travers de la batterie de test de NIST ont montré
+que toutes les propriétés statistiques sont obtenues pour
+ $\mathsf{N} = 4, 5, 6, 7, 8$.
+
