\documentclass[compress]{beamer}

\usetheme[compress]{Ilmenau}
\setbeamertemplate{items}[ball]
\usenavigationsymbolstemplate{}

\usepackage{thumbpdf}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{pifont}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{tabularx}
\usepackage{graphicx}
\usepackage{ifthen}
\usepackage[francais]{babel}
\usepackage{rotating}

\graphicspath{{Figures/}}

%\includeonlyframes{1,2,3,4,5,6,7,8,9,10,11,15,17,18,19,20,21,22,23,24,25,26,28,29,30,31,32,33,34,35,36,37,38,39,bibliocont,bibliodisc}
%\includeonlyframes{6}

\newboolean{acroread}
\setboolean{acroread}{true}
\newcommand{\N}{\mathbb N}
\newcommand{\R}{\mathbb R}
\newcommand{\Z}{\mathbb Z}
\newcommand{\Q}{\mathbb Q}
\newcommand{\C}{\mathbb C}
\newlength{\tl}
\newcommand{\attention}{%
  \settowidth{\tl}{$\triangle$}%
  \makebox[0pt][l]{$\triangle$}%
  \makebox[\tl][c]{\raisebox{.2ex}{\tiny\string!}}}
\newcommand{\hauteur}[2]{\raisebox{0pt}[#1][-#1]{#2}}
\def\oeuvre{\oe uvre }
\def\oeuvrepv{\oe uvre}

%\newenvironment{myitemize}[1]{
%%  \setlength{\topsep}{#1mm}
%  \begin{itemize}
%%    \setlength{\partopsep}{#1mm}
%    \setlength{\itemsep}{#1}
%  }
%  {\end{itemize}
%}

%\newcounter{selection}
%\setcounter{selection}{0}
%\newcounter{num}
%\setcounter{num}{0}

\newcommand{\frameselect}[2]{
  % \addtocounter{num}{1}
  \ifthenelse{\boolean{#1}}%\value{selection}=0 \or
    % \value{num}=\value{selection}}
  {
    #2
  }{}
}

\newenvironment{algo}[0] {
  \begin{quotation}
  \begin{tabbing}
  \hspace{5mm}\=\hspace{5mm}\=\hspace{5mm}\=\hspace{5mm}\= \kill} %
 { \end{tabbing}\end{quotation}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TITRE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\author{Jean-François Couchot$^1$ et Sylvain Contassot-Vivier$^2$} 

\title{Construction de codes de Gray équilibrés \\et forme canonique}
%\subtitle{Habilitation à Diriger des Recherches}

\date{1 - Équipe AND - FEMTO-ST - Univ. Bourgogne Franche-Comté\\
  2 - Équipe Simbiot - LORIA - Université de Lorraine
}

\begin{document}

\frameselect{true}{
  \begin{frame}[label=1]
    \titlepage
  \end{frame}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Méthode R-C
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\frameselect{true}{
  \begin{frame}[label=2]  
    \frametitle{Méthode R-C de construction de CG}
    
    Méthode de Robinson-Cohn :
    \begin{itemize}
    \item Méthode inductive
    \item Produit un CG à N bits à partir d'un CG à N-2 bits
      \begin{itemize}
      \item Séquence connue de transitions $S_{N-2} = (s_1,...,s_{2^{N-2}})$
      \item Codées par la dimension empruntée lors de chaque déplacement du code\\
        $\Rightarrow$ $1\le s_i \le N-2$
      \end{itemize}
    \end{itemize}

    Définitions :
    \begin{itemize}
    \item $u^R$ est le renversé de la séquence $u$
    \item $u'(u, x, y) = (u,x,u^R,y,u)$ 
    \end{itemize}
  \end{frame}
}

\frameselect{true}{
  \begin{frame}
    \frametitle{Méthode R-C de construction de CG}
    Algorithme :
    \begin{enumerate}
    \item Pour $l$ un entier pair, décomposer $S_{N-2}$ en une séquence :\\
      \centerline{$(s_{i_1}, \underline{u_0}, s_{i_2}, \underline{u_1}, s_{i_3}, \underline{u_2}, \dots , s_{i_l-1}, \underline{u_{l-2}}, s_{i_l}, \underline{v})$}
      où les $u_i$ sont des ss-séqs éventuellement vides de $S_{N-2}$\\
      et $u_0 = \emptyset$, $i_1 = 1$, $i_2 = 2$ et $v$ éventuellement $\emptyset$.
    \item Obtenir une nouvelle séquence $U$ en remplaçant :
      \begin{itemize}
      \item $u_0$ par $N-1$
      \item $u_{2i+1}$ par $u'(u_{2i+1},N-1,N)$
      \item $u_{2i}$ par $u'(u_{2i},N,N-1)$
      \end{itemize}
    \item Construire les séquences :\\
      \begin{itemize}
      \item $V=(v^R,N,v)$
      \item $W=(N-1,S_{N-2},N)$
      \item $W'=(w_2,w_1,W_{[3:]})$ \hfill(inversion des 2 1ers élts de $W$)
      \end{itemize}
    \item $S_{N} = (U^R, V, W')$
    \end{enumerate}
  \end{frame}
}

\frameselect{true}{
  \begin{frame}
    \frametitle{Méthode R-C de construction de CG}
    \textbf{Exemple 1} : $N = 5$ et $S_3 = (1,2,1,3,1,2,1,3)$
    \begin{enumerate}
    \item le choix $l=2$ implique : $S_3=(s_{1}, \underline{u_0}, s_{2},v)$\\
      avec $v = (s_3,...,s_{2^{N-2}}) = (1,3,1,2,1,3)$
    \item on obtient $U = (s_1, 4, s_2, s_3,...,s_{2^{N-2}}) = (1,4,2,1,3,1,2,1,3)$
    \item et les séquences :\\
      \begin{itemize}
      \item $V= (v^R,N,v) = (3,1,2,1,3,1,5,1,3,1,2,1,3)$
      \item $W=(N-1,S_{N-2},N)=(4,1,2,1,3,1,2,1,3,5)$
      \item $W'=(w_2,w_1,W_{[3:]})=(1,4,2,1,3,1,2,1,3,5)$
      \end{itemize}
    \item $S_{N} = (U^R, V, W')=(\underline{3,1,2,1,3,1,2,4,1},$\\
      \hspace{9em} $3,1,2,1,3,1,5,1,3,1,2,1,3,$\\
      \hspace{9em} $1,4,2,1,3,1,2,1,3,5)$
    \end{enumerate}

    Fréquences = 14, 6, 8, 2, 2
  \end{frame}
}

\frameselect{true}{
  \begin{frame}
    \frametitle{Méthode R-C de construction de CG}
    \textbf{Exemple 2} : $N = 5$ et $S_3 = (1,2,1,3,1,2,1,3)$
    \begin{enumerate}
    \item le choix $l=4$ implique : $S_3=(s_{1}, \underline{u_0}, s_{2}, \underline{u_1}, s_{i_3}, \underline{u_2}, s_{i_4},v)$\\
      on choisit $u_1=(1,3)$, donc $s_{i_3}=1$\\
      et $u_2=(2)$, donc $s_{i_4}=1$ et $v =(3)$
    \item on a $u'(u_1,4,5) = (1,3,4,3,1,5,1,3)$\\
      et $u'(u_2,5,4) = (2,5,2,4,2)$\\
      et donc $U = (1,4,2,\underline{1,3,4,3,1,5,1,3},1,\underline{2,5,2,4,2},1,3)$
    \item et les séquences :\\
      \begin{itemize}
      \item $V= (v^R,N,v) = (3,5,3)$
      \item $W$ et $W'$ comme précédemment
      \end{itemize}
    \item $S_{N} = (U^R, V, W')=(\underline{3,1,2,4,2,5,2,1,3,1,5,1,3,4,3,}$\\
      \hspace{9em} $\underline{1,2,4,1},3,5,3,$\\
      \hspace{9em} $1,4,2,1,3,1,2,1,3,5)$
    \end{enumerate}

    Fréquences = 10, 6, 8, 4, 4
  \end{frame}
}

\frameselect{true}{
  \begin{frame}
    \frametitle{Problématique des CG équilibrés}
    
    L'algo précédent n'est pas \textbf{constructif}\\
    $\rightarrow$ pas d'indication sur le choix de $l$ et des $u_i$ !
    \vspace{1em}

    Formalisation de l'équilibre d'un CG :
    \begin{itemize}
    \item Soit $TC_N : \{1,\dots, N\} \rightarrow \{0, \ldots, 2^N\}$\\
      nb d'occurrences d'une dimension dans une séquence
    \item un CG est \textbf{équilibré} ssi :\\
      \centerline{$\forall i,j\in \{1,...,N\},~|TC_N(i) - TC_N(j)|\le 2$}
    \item il est \textbf{totalement équilibré} ssi:\\
      \centerline{$\forall i\in \{1,...,N\},~TC_N(i) = \frac{2^N}{N}$}
    \end{itemize}
    \vspace{1em}

    On a  montré qu'il existe au  moins un choix  de $(u_i)$ dans l'algo  RC qui
    donne un CG équilibré.
  \end{frame}
}

\frameselect{true}{
  \begin{frame}
    \frametitle{Construction de CG équilibrés}
    
    L'idée est de : 
    \begin{itemize}
    \item Compter pour chaque dimension, les occurrences générées par l'algo RC :
      \begin{itemize}
      \item Pour les dimensions $N-1$ et $N$ on arrive à $l$
      \item Pour les autres, on établit une formulation dépendant :
        \begin{itemize}
        \item des occurrences dans la séquence initiale $S_{N-2}$
        \item des choix d'inclusion ou non dans les $s_{i_j}$, $u_i$ et $v$ :
          $TC_N(k)=TC(k, \cup_j(s_{i_j})) + 3\times ( TC(k, \cup_iu_i) + TC(k, v)) + TC_{N-2}(k)$\\
        \end{itemize}
      \end{itemize}
    \item Appliquer la contrainte d'équilibre aux formulations obtenues
    \end{itemize}

    \begin{center}
      $\Rightarrow$ On en déduit le nombre d'occurrences de chaque dimension à
      insérer dans les $s_{i_j}$, $u_i$ et $v$
    \end{center}
  \end{frame}
}

\frameselect{true}{
  \begin{frame}
    \frametitle{Construction de CG équilibrés}
    
    Exemple : $S_2 = (1,2,1,2)$
    \begin{itemize}
    \item Pour avoir l'équilibre final, $l$ doit valoir 4
    \item On en déduit une décomposition de la forme :\\
      $S_2 = (s_{i_1},u_0,s_{i_2},u_1,s_{i_3},u_2,s_{i_4},v)$ et $s_{i_1}=1$, $u_0=\emptyset$, $s_{i_2}=2$
    \item Or, on a : $TC_2(1) = 2$ et $TC_2(2)=2$
    \item Et pour $k=1$ et $k=2$, il faut vérifier :
      $TC(k, \cup_j(s_{i_j})) + 3\times ( TC(k, \cup_iu_i) + TC(k, v)) + TC_2(k)=4$\\
      $TC(k, \cup_j(s_{i_j})) + 3\times ( TC(k, \cup_iu_i) + TC(k, v))=2$\\
      $\Rightarrow TC(k, \cup_iu_i) + TC(k, v) = 0$\\
      $\Rightarrow TC(k, \cup_j(s_{i_j}))=2$
    \item Donc $u_0,u_1,u_2$ et $v$ doivent être vides !
    \end{itemize}
  \end{frame}
}

\frameselect{true}{
  \begin{frame}
    \frametitle{Construction de CG équilibrés}
    
    Comme $u_0,u_1,u_2$ et $v$ sont vides, on a :
    \begin{itemize}
    \item $u'(u_1,3,4) = (3,4)$
    \item $u'(u_2,4,3) = (4,3)$
    \item $U = (1,3,2,3,4,1,4,3,2)$
    \item $V= (v^R,N,v) = (4)$
    \item $W=(N-1,S_{N-2},N)=(3,1,2,1,2,4)$
    \item $W'=(w_2,w_1,W_{[3:]})=(1,3,2,1,2,4)$
    \item $S_{4} = (U^R, V, W')=(2,3,4,1,4,3,2,3,1,4,1,3,2,1,2,4)$
    \end{itemize}
    \begin{center}
      $\Rightarrow$ Fréquences = 4, 4, 4, 4
    \end{center}
  \end{frame}
}

\frameselect{true}{
  \begin{frame}
    \frametitle{Algo de construction de CG équilibrés}
    
    Une fois  déterminés les nombres d'occurrences  à placer dans les  $u_i$, il
    faut construire la séquence :
    \begin{itemize}
    \item Parcours exhaustif :
      \begin{itemize}
      \item [$\frownie$] Coûteux
      \item [$\smiley$] Produit tous les CG équilibrés atteignables par cette méthode
      \end{itemize}
    \item Algorithme glouton :
      \begin{itemize}
      \item Construction des $u_i$ dans l'ordre
      \item  Choix  glouton  pour  chaque  $u_i$ :\\
        sous-séquence  maximale  de  $S_{N-2}$   vérifiant  les  nombres  totaux
        d'occurrences déterminés pour les $u_i$
      \end{itemize}
    \item [$\frownie$] Ne produit pas tous les CGE possibles !
    \item [$\smiley$] Produit rapidement un CG pour n'importe quelle dimension !\\
      (à partir des dimensions 2 et 3)
    \end{itemize}
  \end{frame}
}

\frameselect{true}{
  \begin{frame}
    \frametitle{Algo de construction de tous les CG équilibrés}
    
    Algo basé sur la méthode de M.~Wild : 
    \begin{itemize}
    \item Basé sur le principe d'exclusion
    \item Liste des arêtes du N-cube 
    \item Chaque arête prend un état dans l'ensemble $\{0,1,2,g,d\}$ :
      \begin{itemize}
      \item 0 pour supprimée, 1 pour incluse, 2 pour indéterminé (initial)
      \item $g$ pour un ensemble d'arêtes dont une seule est incluse
      \item $d$ pour un ensemble d'arêtes dont deux sont incluses
      \end{itemize}
    \item Ajouts successifs des noeuds en appliquant :
      \begin{itemize}
      \item Condition locale (chaque noeud) : degré 2
      \item Conditions globales : \\
        cycle max : nb arêtes à 1 = nb sommets\\
        cycles inf : pas de cycles < nb sommets
      \item [$\Rightarrow$] élagage dès qu'une contrainte n'est pas vérifiée 
      \end{itemize}
    \end{itemize}
  \end{frame}
}

\frameselect{true}{
  \begin{frame}
    \frametitle{Adaptation au contexte de N-cube}
    
    \begin{itemize}
    \item Ajout de la contrainte d'équilibre dans l'élagage
    \item Utilisation d'une forme canonique des CG :\\
      \begin{itemize}
      \item [$\Rightarrow$] Unicité des représentants
      \item [$\Rightarrow$] Ordre global sur les représentants :
        \begin{itemize}
        \item Détection efficace des doublons
        \item Stockage minimal
        \end{itemize}
      \end{itemize}
    \end{itemize}
  \end{frame}
}

\frameselect{true}{
  \begin{frame}
    \frametitle{Forme canonique des CG}
    
    \begin{itemize}
    \item Alignement sur début d'une sous-séquence avec \textbf{écart max} :
      \begin{itemize}
      \item Plus grand intervalle entre 2 occurrences d'une même dimension
      \end{itemize}
    \item Écart max sur l'ensemble des dimensions = \textbf{équilibre local}
    \item Renumérotation des dimensions :
      \begin{itemize}
      \item Affectation dans l'ordre croissant des n° \hfill$\Rightarrow$ débuts = (1,2)
      \item Équivalent à des isomorphismes du N-cube
      \item Donne un ordre global \hfill$\Rightarrow$ tri possible
      \end{itemize}
    \item Travaux en cours :
      \begin{itemize}
      \item Unicité de la forme canonique pour une classe d'isomorphismes
      \item Deux formes canoniques distinctes ne sont pas isomorphes
      \end{itemize}
    \end{itemize}
    \begin{center}
      $\Rightarrow$ Génération exhaustive en accord avec la théorie (dims $\le$ 5)
    \end{center}
  \end{frame}
}

\end{document}
