retardprng.tex

   1 Nous avons  vu comment construire  un générateur de nombre  pseudo-aléatoires en
   2 utilisant un système  booléen en mode chaotique.  Cependant,  cela nécessite une
   3 contrainte forte  sur le graphe d'itérations  de la fonction  associée, qui doit
   4 être fortement connexe.  Nous étudions  dans cette partie une méthode permettant
   5 de relâcher  un peu les contraintes  sur les fonctions $f_i$  en enrichissant le
   6 système initial de façon à modéliser la notion de \emph{retards} entre éléments.
   7
   8 \subsection{Les retards dans les systèmes dynamiques}
   9 \label{sec:retards}
  10
  11 La notion  de retard provient  initialement du besoin  de prendre en  compte les
  12 délais de transfert d'information entre les éléments d'un système.  Lorsque l'on
  13 se place dans  le contexte général, ces délais peuvent  eux-mêmes varier dans le
  14 temps. On décrit donc  le retard de l'élément $j$ par rapport  à l'élément $i$ à
  15 l'instant $t$ par  $r_j^i(t)$. Ainsi, l'information reçue de $j$ en  $i$ à $t$ a
  16 été générée à  l'instant (ou itération) $s_j^i(t)=t-r_j^i(t)$. On  en déduit que
  17 la mise à jour de l'élément $i$ de l'instant $t$ à $t+1$ s'écrit :
  18 \begin{equation*}
  19   x_i(t+1) = f_i(x_1^{s_1^i(t)},x_2^{s_2^i(t)},\dots,x_i^t,\dots,x_{n-1}^{s_{n-1}^i(t)},x_n^{s_n^i(t)})
  20 \end{equation*}
  21 On constate que même si le modèle le permet, on ne met généralement pas de délai
  22 entre l'élément $i$ et lui-même car cela n'a pas d'intérêt pratique fort.
  23
  24 Plusieurs travaux  sur les systèmes  à retards (\cite{Mie75, Rob86,  BT89, BC02,
  25   TNN2006})  ont montré que  l'une des  influences majeures  des retards  sur la
  26 dynamique du  système est d'augmenter  le nombre de transitions  possibles entre
  27 les états. En  d'autres termes, cela revient à augmenter  la connexité du graphe
  28 d'itérations, ce qui est justement la propriété recherchée.
  29
  30 Cependant, une difficulté  majeure dans notre contexte de  génération de nombres
  31 pseudo-aléatoires  vient du  fait que  les retards  induisent une  dépendance du
  32 système à son  \emph{historique} plus ancien que la  seule itération précédente.
  33 Cela  empêche le  recours  aux chaînes  de  Markov classiques  pour établir  les
  34 preuves que les propriétés nécessaires à un bon générateur sont vérifiées.
  35
  36 Afin  de  contourner  cet  obstacle,  nous  proposons  ici  une  méthode  simple
  37 permettant de simuler des retards dans un système booléen chaotique.
  38
  39 \subsection{Simulation de retards dans un système booléen chaotique}
  40 \label{sec:simuRets}
  41
  42 Soit un système  booléen à $n$ éléments dont la  dynamique chaotique est décrite
  43 par $G_f$. Nous  proposons d'étendre ce système afin  d'y incorporer des retards
  44 simulés.  Le  principe consiste  à ajouter un  n{\oe}ud intermédiaire au  niveau de
  45 chaque interaction entre deux éléments  différents (les arcs $(i,s,j)$ t.q $i\ne
  46 j$) du graphe d'interactions. Ainsi, si l'on considère l'arc $(i,s,j)$ du graphe
  47 initial,  alors cet  arc  sera remplacé  dans  le nouveau  graphe  par les  arcs
  48 $(i,+,k)$ et  $(k,s,j)$, avec $x_k$ un  nouvel élément booléen  du système ayant
  49 pour fonction  d'évolution $f_k(x)=x_i$. De  plus, les occurrences  de l'élément
  50 $x_i$ dans la fonction $f_j(x)$ seront  remplacées par $x_k$.  On note que l'arc
  51 allant de $i$ à $k$ est systématiquement positif alors que l'arc allant de $k$ à
  52 $j$ conserve le signe $s$ de l'ancien arc $(i,s,j)$.
  53
  54
  55 %%% Local Variables:
  56 %%% mode: latex
  57 %%% TeX-master: "main"
  58 %%% End: