% This part is addressed in the first section. Next, we analyse the first
% results to provide a generation of DSSC matrices with small mixing times.
-\section{Programmation logique par contraintes sur des domaines finis}
+\section{Programmation logique par contraintes sur des domaines finis}\label{sec:plc}
Tout d'abord, soit ${\mathsf{N}}$ le nombre d'éléments.
Pour éviter d'avoir à gérer des fractions, on peut considérer que
les matrices (d'incidence) à générer ont des lignes et des colonnes dont les
-\subsection{Analyse de l'approche}\label{sub:prng:ana}
+%\subsection{Analyse de l'approche}\label{sub:prng:ana}
Exécutée sur un ordinateur personnelle, PROLOG trouve
en moins d'une seconde les
49 solutions pour $n=2$,
-\section{Graphes
- $\textsc{giu}(f)$
- $\textsc{gig}(f)$
- fortement connexes et doublement stochastiques}\label{sec:gen:dblstc}
-% Secrypt 14
+% section{Graphes
+% $\textsc{giu}(f)$
+% $\textsc{gig}(f)$
+% fortement connexes et doublement stochastiques}\label{sec:gen:dblstc}
+% %
+%Secrypt 14
-\subsection{Suppression des cycles hamiltoniens}
+\section{Suppression des cycles hamiltoniens}
\label{sec:hamiltonian}
-Dans un premier temps, nous montrons en section~\ref{sub:removing:theory} que la
+Dans un premier temps, nous montrons %en section~\ref{sub:removing:theory}
+que la
suppression d'un cycle hamiltonien produit bien des matrices doublement
stochastiques. Nous établissons ensuite le lien avec les codes de Gray
équilibrés.
-\subsubsection{Aspects théoriques}
-\label{sub:removing:theory}
+%\subsubsection{Aspects théoriques}
+%\label{sub:removing:theory}
Nous donnons deux résultats complémentaires, reliant la suppression d'un cycle
hamiltonien du $n$-cube, les matrices doublement stochastiques et la forte
code de Gray est \emph{cyclique} si le premier élément et le dernier ne
différent que par un seul bit.
-\subsection{Lien avec les codes de Gray cycliques (totalement) équilibrés}
+\section{Lien avec les codes de Gray cycliques (totalement) équilibrés}
\label{sub:gray}
La borne inférieure du nombre de codes de Gray ($\left(\frac{n*\log2}{e \log
ce code est totalement équilibré.
\end{xpl}
-\subsection{Génération de codes de Gray équilibrés par induction}
+\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
On pourrait penser à un algorithme basé sur les itérations généralisées,
c'est-à-dire qui modifierait une partie des éléments de $[n]$ à chaque
itération.
-C'est l'algorithme~\ref{CI Algorithm:prng:g}.
+C'est l'algorithme~\ref{CI Algorithm:prng:g} donné ci-après.
- \begin{algorithm}[h]
+ \begin{algorithm}[ht]
%\begin{scriptsize}
\KwIn{une fonction $f$, un nombre d'itérations $b$,
une configuration initiale $x^0$ ($n$ bits)}
correspondante à ce graphe
et $M$ une matrice $2^n\times 2^n$
définie par
- $M = \dfrac{1}{n} \check{M}$.
+ $M = \dfrac{1}{2^n} \check{M}$.
Si $\textsc{gig}(f)$ est fortement connexe, alors
la sortie du générateur de nombres pseudo aléatoires détaillé par
- l'algorithme~\ref{CI Algorithm} suit une loi qui
+ l'algorithme~\ref{CI Algorithm:prng:g} suit une loi qui
tend vers la distribution uniforme si
et seulement si $M$ est une matrice doublement stochastique.
\end{theorem}
\begin{xpl}
- On reprend l'exemple donné à la section~\ref{sub:prng:ana}:
- Dans le $3$-cube cycle hamiltonien défini par la séquence
+ On reprend l'exemple donné à la section~\ref{sec:plc}.
+ Dans le $3$-cube, le cycle hamiltonien défini par la séquence
$000,100,101,001,011,111,110,010,000$ a été supprimé engendrant
la fonction $f^*$ définie par
$$f^*(x_1,x_2,x_3)=
\begin{figure}[ht]
\begin{center}
- \subfigure[Graphe des itérations chaotiques de $f^*$.
+ \subfigure[Graphe $\textsc{gig}(f^*)$
\label{fig:iteration:f*}]{
\begin{minipage}{0.55\linewidth}
\centering
\includegraphics[width=\columnwidth]{images/iter_f}%
\end{minipage}
}%
- \subfigure[Matrice de Markov du graphe d'itérations chaotiques de
- $f^*$\label{fig:markov:f*}]{%
+ \subfigure[Matrice de Markov associée au $\textsc{gig}(f^*)$
+ \label{fig:markov:f*}]{%
\begin{minipage}{0.35\linewidth}
\begin{scriptsize}
\begin{center}
\end{minipage}
}%
\caption{Représentations de $f^*(x_1,x_2,x_3)=
- (x_2 \oplus x_3, \overline{x_1}\overline{x_3} + x_1\overline{x_2},
- \overline{x_1}\overline{x_3} + x_1x_2)$.}\label{fig1}
+ (x_2 \oplus x_3, \overline{x_1}.\overline{x_3} + x_1\overline{x_2},
+ \overline{x_1}.\overline{x_3} + x_1x_2)$.}\label{fig1}
\end{center}
\end{figure}
\end{xpl}
- \begin{table}
+ \begin{table}[ht]
\begin{center}
\begin{scriptsize}
\begin{tabular}{|c|l|c|c|}
\end{tabular}
\end{scriptsize}
\end{center}
-\label{table:functions}\caption{Fonctions avec matrices DSCC et le plus faible temps de mélange.}
+\label{table:functions}
+\caption{Fonctions avec matrices DSCC et le plus faible temps de mélange.}
++
\end{table}
Le tableau~\ref{table:functions} reprend une synthèse de
fonctions qui ont été générées selon la méthode détaillée
-à la section~\ref{sec:gen:dblstc}.
-Pour chaque nombre $n=3$, $4$, $5$
-,$6$, tous les cycles hamiltoniens non isomorphes ont été générés. Pour les
-valeur de $n=7$ et $8$, seules $10^{5}$ configurations ont été évaluées. Parmi
+à la section~\ref{sec:hamiltonian}.
+Pour chaque nombre $n=3$, $4$, $5$ et $6$,
+tous les cycles hamiltoniens non isomorphes ont été générés. Pour les
+valeur de $n=7$ et $8$, seules $10^{5}$ cycles ont été évalués. Parmi
toutes les fonctions obtenues en enlevant du $n$-cube ces cycles, n'ont été
retenues que celles qui minimisaient le temps de mélange relatif à une valeur de
$\epsilon$ fixée à $10^{-8}$.
l'on marche.
Cela s'explique assez simplement. Depuis une configuration initiale, le nombre
-de configurations qu'on ne peut pas atteindre en une itération est de
+de configurations qu'on ne peut pas atteindre en une itération est de:
\begin{itemize}
-\item $2^n-n$ en marchant, ce qui représente $\dfrac{2^n-n}{2^n} = 1-\dfrac{n}{2^n}$
+\item $2^n-n$ en unaire. Ceci représente un rapport de
+ $\dfrac{2^n-n}{2^n} = 1-\dfrac{n}{2^n}$
de toutes les configurations; plus $n$ est grand,
plus ce nombre est proche de $1$, et plus grand devient le nombre
- d'itérations suffisantes pour atteinte une déviation faible;
-\item $2^n-2^{n-1}$ en sautant, soit la moitié de toutes les configurations
+ d'itérations nécessaires pour atteinte une déviation faible;
+\item $2^n-2^{n-1}$ dans le cas généralisé,
+ soit la moitié de toutes les configurations
quel que soit $n$; seul 1 bit reste constant tandis que tous les autres peuvent changer. Plus $n$ grandit, plus la proportion de bits constants diminue.
\end{itemize}
-Cependant, dans le cas où l'on saute, chaque itération a une complexité
-plus élevée puisqu'il est nécessaire d'invoquer un générateur
-de nombres pseudo-aléatoires entre 1 et $2^{n}$ tandis qu'il suffit
-d'avoir un générateur entre 1 et $n$ dans le premier cas.
+Cependant, dans le cas généralisé, chaque itération a une complexité
+plus élevée puisqu'il est nécessaire d'invoquer un générateur
+produisant un nombre pseudo-aléatoire dans $[2^{n}]$ tandis qu'il suffit
+que celui-ci soit dans $[n]$ dans le cas unaire.
+Pour comparer les deux approches,
+on considère que le générateur aléatoire embarqué est binaire, \textit{i.e.} ne génère qu'un bit (0 ou 1).
-Pour comparer les deux approches, on considère que le générateur aléatoire embarqué est binaire, \textit{i.e.} ne génère qu'un bit (0 ou 1).
-
-Lorsqu'on marche et qu'on effectue $i$ itérations,
-à chaque itération, la stratégie génère un nombre entre
-$1$ et $n$.
-Elle fait donc $\ln(n)/\ln(2)$ appels à ce générateur en moyenne.
-La démarche fait donc au total $i*\ln(n)/\ln(2)$ appels pour $n$ bits et
-donc $i*\ln(n)/(n*\ln(2))$ appels pour 1 bit généré en moyenne.
-Lorsqu'on saute et qu'on effectue $i'$ itérations,
-à chaque itération, la stratégie génère un nombre entre
+Dans le cas généralisé, si l'on effectue $b$ itérations,
+à chacune d'elles, la stratégie génère un nombre entre
$1$ et $2^n$. Elle fait donc $n$ appels à ce générateur.
-On fait donc au total $i'*n$ appels pour $n$ bits et
-donc $i'$ appels pour 1 bit généré en moyenne.
+On fait donc au total $b*n$ appels pour $n$ bits et
+donc $b$ appels pour 1 bit généré en moyenne.
+Dans le cas unaire, si l'on effectue $b'$ itérations,
+à chacune d'elle, la stratégie génère un nombre entre
+$1$ et $n$.
+Elle fait donc $\ln(n)/\ln(2)$ appels à ce générateur binaire en moyenne.
+La démarche fait donc au total $b'*\ln(n)/\ln(2)$ appels pour $n$ bits et
+donc $b'*\ln(n)/(n*\ln(2))$ appels pour 1 bit généré en moyenne.
Le tableau~\ref{table:marchevssaute} donne des instances de
ces valeurs pour $n \in\{4,5,6,7,8\}$ et les fonctions
données au tableau~\ref{table:functions}.
-On constate que le nombre d'appels par bit généré décroit avec $n$ dans la
-seconde démarche et est toujours plus faible que celui de la première.
+On constate que le nombre d'appels par bit généré décroit avec $n$ dans le
+cas des itérations généralisées et est toujours plus faible
+que celui des itérations unaires.
- \begin{table}
+ \begin{table}[ht]
$$
\begin{array}{|l|l|l|l|l|l|}
\hline
- \textrm{Algorithme} & 4 & 5 & 6 & 7 & 8 \\
+ \textrm{Itérations} & 4 & 5 & 6 & 7 & 8 \\
\hline
- \textrm{marchant} & 19.0 & 22.2905097109 & 23.6954895899 & 25.2661942985 & 27.0\\
+ \textrm{Unaires} & 19.0 & 22.2905097109 & 23.6954895899 & 25.2661942985 & 27.0\\
\hline
- \textrm{sautant} & 17 & 13 & 11 & 10 & 9\\
+ \textrm{Généralisées} & 17 & 13 & 11 & 10 & 9\\
\hline
\end{array}
$$
-La qualité des séquences aléatoires a été évaluée à travers la suite
-de tests statistiques développée pour les générateurs de nombres
-pseudo-aléatoires par le
+\section{Tests statistiques}
+
+La qualité des séquences aléatoires produites par
+le générateur des itérations unaires ainsi que
+celles issues des itérations généralisées a été évaluée à travers la suite
+de tests statistiques développée par le
\emph{National Institute of Standards and Technology} (NIST).
Pour les 15 tests, le seuil $\alpha$ est fixé à $1\%$:
une valeur
qui est plus grande que $1\%$ signifie
que la chaîne est considérée comme aléatoire avec une confiance de $99\%$.
+
+
+
+
Le tableau~\ref{fig:TEST} donne une vision synthétique de toutes
- les expérimentations.
-
-
-
+ ces expérimentations.
L'expérience a montré notamment que toutes ces fonctions
passent avec succès cette batterie de tests.
+
+
+
%%%%%%%%% Relancer pour n=6, n=7, n=8
%%%%%%%%% Recalculer le MT
%%%%%%%%% Regenerer les 10^6 bits
%%%%%%%%% Evaluer sur NIST
- \begin{table}
+ \begin{table}[ht]
\centering
\begin{scriptsize}
\begin{tabular}{|*{5}{c|}}
Complexité linaire & 0.816 (1.0) & 0.897 (0.98) & 0.080 (0.98) & 0.798 (1.0) \\ \hline
\end{tabular}
\end{scriptsize}
-\label{fig:TEST}\caption{Test de NIST réalisé sur les fonctions $f^*$ détaillées au tableau~\label{table:functions}}
++
+\label{fig:TEST}
- \caption{Test de NIST réalisé sur les fonctions $f^*$ détaillées au tableau~\label{table:functions}.}
++\caption{Test de NIST réalisé sur les fonctions $f^*$ détaillées au tableau~\label{table:functions}}
\end{table}
%
