Pour un bon nombre de bonnes raisons déja évoquées, les parties controle d'un système logique gagnent à ètre modélisées à l'aide de réseaux synchronisés (RdPS), et tout particulièrement dans le cas de la conception d'un ASIC, à l'aide de RdPS ou réseaux de Pétri synchrones synchronisés .

Synchrone, pour rappeler qu'à toute transition est associée une condition de franchissement (réceptivité), sachant que cette condition peut ètre aussi l'évènement lambda dit "toujours vrai" . Une transition lambda est une transition à hauteur de laquelle on ne rappelle pas de condition. Elle est franchie aussitot que franchissable du seul fait de l'état de marquage du réseau.

Le réseau est par ailleurs synchronisé, pour rappeler que tout franchissement ne se fera qu'en synchronisme sur un des deux fronts d'une horloge maitresse cadençant le système.

A chaque place est généralement associée une action ou une ou plusieurs commandes. Mais on peut tout aussi bien ne rien associer à une place. Alors, celle-ci n'est la que pour marquer une étape dans l'évolution du séquencement modélisé. Ce peut ètre aussi un sémaphore de synchronisation entre deux blocs de controle qui communiquent ou se synchronisent. Etc .....

Bien noter que toute commande associée à une place n'est active que durant le marquage de cette place. Cette commande est désactivée aussitot la place libérée de toute marque.

Une réceptivité Ri peut ètre aussi ordinaire que l'état logique d'une variable booléenne comme le résultat logique d'une fonction combinatoire aussi complexe que nécéssaire (prédicat ).

Dans tous les cas une réceptivité ramène une valeur logique (0, 1) qui conditionne l'autorisation de franchissement de la transition à laquelle elle est associée.
 

STRUCTURE:

La structure la plus simple d'une machine implémentant un graphe de controle modélisé par un RdP pourra se présenter conformément à la figure ci-après. Les signaux se répartissent en:

     - Entrées primaires           :  E
 
     - Sorties primaires            :  S
 
     - Marquage à l'instant t     :  M(t)
 
     - Marquage suivant          :  M(t+1)
 

 On distingue:
1) Deux blocs strictement combinatoires,  (Portes logiques exclusivement)

     - Le bloc de séquencement                               (A)
     - le bloc de commande (ou bloc de sortie)         (B)

2) Un registre dit "registre de marquage"  RM.

RM est constitué d'un ensemble de bascules. Chaque bascule rend compte à tout instant de l'état de marquage de la place du réseau à laquelle on l'aura associée.

Les deux blocs strictement combinatoires peuvent ètre définis par de simples tables de vérité ou par un systèmes d'équations booléennes.

Les logiques d'implémentation de ces  blocs combinatoires  pourront ètre:

     - Logique anarchique                         (portes ordinaires)
     - Mémoire morte                               (R.O.M)
     - Réseau logique programmable         (P.L.A)
 

Etat interne / état total

La configuration binaire du vecteur   M(t), donc le contenu du registre RM,  rend compte, à l'instant t, de l'état de marquage du réseau à cet instant. C'est l'ETAT INTERNE du séquenceur.

La concaténation de l'état des entrées primaires E au vecteur de marquage interne définit maintenant l'ETAT TOTAL de la machine  (E / Qt).
 

Machine de MEALY

S'il se trouve des sorties primaires dont les états logiques dépendent autant du marquage (RM) que des états d'entrée (soit de de l'état total), nous dirons avoir affaire à une machine de MEALY. La structure de la figure (   ) est celle d'une machine de MEALY.

Nous disons aussi que dans une machine de MEALY les entrées participent aux sorties. Le système d'équations est alors de la forme :

  S(t)        =   h [M(t),  E(t)]
  M(t+1)   =    g [M(t),  E(t)]
 

Machine de MOORE

Une machine est dite "machine de MOORE" si l'état logique de toute sortie  s_i  ne dépend que du marquage du RdP de controle. La structure précédemment proposée est celle d'une machine de MOORE. Son système d'équations est alors:

 S(t)       =    h [ M(t)
 M(t+1)  =    g [ M(t), E(t) ]   (marquage sur le prochain coup d'horloge)

M(t)  :  marquage à l'instant  t.

 Rappels:

Un RdP a une structure de graphe d'états (GE) si on y rencontre ni jonctions, ni distributions. Un graphe d'états est exclusivement constitué de sélections, d'attributions ou de transferts. On dit encore que c'est un RdP constitué uniquement que de noeuds OU. Si de plus ce graphe a pour marquage initial un jeton et un seul dans une des places, le graphe est alors un graphe de transition d'états (G.T.E). Le jeton est "conservatif". Il ne fait que transiter de place en place au grè des franchissements. Quand on parle d'un graphe d'états, on sous-entend souvent un G.T.E.

Au graphe d'états correspond le graphe de fluence. Ce dernier est en effet constitué que d'une seule catégorie de noeuds. Des arcs, auxquels on associe des évènements, relient ces noeuds entre eux.
 
 

Transcription d'un RdP en graphes d'états

Si on décide d'implémenter un RdP, non pas en mode cellulaire mais sous forme machines d'états (state machine), il nous faut disposer d'un ou de plusieurs graphes d'états. Deux méthodes pour cela:

    1) Tracé du graphe des marquages conséquents
    2) Partition en graphes d'états.
 

- Graphe des marquages conséquents  (G.M.C)

C'est se donner une nouvelle représentation du fonctionnement du réseau par l'étude exhaustive de l'ensemble des marquages atteignables. A chaque état de marquage est associé une place, place à hauteur de laquelle on peut rappeler la suite des places marquées dans le réseau initial pour ce marquage. Le graphe obtenu est unique et a alors les caractéristiques d'un graphe d'états.
 

GMC  et machine d'états.

Le graphe des marquages conséquents, de par son principe de construction, a tendance à exploser en nombre de places. Il pourra toujours servir à une étude exhaustive du RdP sur ordinateur mais on hésitera souvent à en faire le graphe destiné à étre implémenté.
 

- Partition en  G.E  d'un RdP

Il s'agit ici de découper le réseau en autant de graphes d'états que nécéssaire afin d'obtenir la disparition des jonctions et distributions. Les graphes séparés ainsi obtenus vont devoir communiquer ou se synchroniser, mais chacun des graphes pris individuellement sera bien un G.E.

On dispose de programmes qui se chargent de procéder automatiquement à ce type de décomposition (ANDRE - Nice). Tout outil de partition devra cependant, en plus d'un mode de traitement par défaut, autoriser une certaine interactivité. Un concepteur peut souhaiter par exemple désigner certaines places comme devant appartenir au mème graphe.

En effet, un mème RdP se prète généralement à plusieurs partitions possibles. Retenir plutot telle partition que telle autre relève en principe de la responsabilité du concepteur, de son expérience et des objectifs poursuivis (superficie, vitesse, aléas de décodage, .... ) Ainsi, il y a deux partitions possibles du RdP (     ). la partition  (a) conduit à se réserver un registre d'états de longueur  4  pour le graphe principal puisque  9  états à différencier.

Une fois la partition effectuée, chacun des graphes d'états sera implémenté selon n'importe laquelle des techniques d'implémentation d'une machine d'états. Il y a seulement à bien définir les synchronisations entre machines, lesquelles apparaissent en principe de façon évidente.

Les outils de saisie simultanée de n graphes d'états communiquant existent sur le marché des logiciels de développement, y compris pour  PC (ALDEC-foundation pour  FPGA - XILINX).

Introduisons la méthode directement sur l'exemple du G.T.E ci-dessous. Cette implémentation se fera ici sans la moindre préoccupation d'optimisation. Le seul objectif poursuivi étant l'obtention d'une première réalisation matérielle sur la base de l'utilisation d'un bloc P.L.A (Programmable Logic Array) pour le combinatoire et d'un registre d'état  RE.

Au niveau du graphe lui-mème, trois aménagements préalables s'imposent qui sont:

      - Exclusions des réceptivités.
      - Rajout des transitions de maintien.
      - Obtention de formes sommes de monomes au niveau des transitions (PLA oblige).

1- Exclusions des réceptivités.

- Il s'agit maintenant de s'assurer que pour toute sélection dans le réseau les réceptivités s'excluent mutuellement. En d'autres termes, pour toute sélection, il faut garantir qu'une et une seule des transitions de la sélection sera franchie.

Par exemple, de la place  p1  on peut atteindre les places p2, p3 ou p4  selon les occurences respectives   /a, b.c ou /c. Mais le principe du graphe d'état (autant que celui d'un RdP) oblige à obtenir, si franchissement, le franchissement d'une et d'une seule des transitions. En d'autres termes, si  c = 0 ET a = 0, quelle place marquer des places  p2  et  p4 ?

Le principe d'exclusion de franchissement simultané de deux transitions ou plus d'une mème sélection nous oblige à compléter les écritures des réceptivités de façon à garantir que si il y a franchissement celui-ci ne peut s'effectuer que par une et une seule des n  transitions de la sélection. Il nous faut compléter les conditions de franchissement.

On vérifie, réseau (     ), que les intersections logiques des réceptivités prises deux à deux sont chaque fois vides.

                 /a .  abc  =  0,          /a .  a/c =  0,           abc .   a/c =  0

On procèdera à cette vérification pour toutes les sélections du réseau.

Certains outils (COMPASS) autorisent une affectation de priorités aux transitions. Alors, si deux transitions d'une mème sélection sont franchissables, c'est la transition de priorité la plus élevée qui sera franchie. L'outil complète de lui-mème les conditions logiques.

2- Rajout des transitions de maintien.

Pour une machine dans un état  i, si aucune des transitions de sortie de cet état n'est validée, l'état futur de la machine reste l'état  i  (inscription dans le registre d'état sur le prochain front de synchronisation de la mème configuration Q(t)  soit:  [Q(t+1)  =  Q(t)].

- Sur le réseau on rajoute donc les arcs et transitions qui renvoient le jeton dans la mème place. En place  p0, tant que  a=0  le jeton doit ètre "réinscrit" en place p0 au coup d'horloge à venir. D'ou la réceptivité  /a associée à la transition de maintien rebouclée sur cette mème place.
 

Un traitement équivalent pour la place  1  nous amène à écrire pour la récéptivité associée à la transition de maintien du jeton en place  1  la réceptivité:

               r  =   /[ /a + bca + /ca ]   =  a . /b . c

C'est la condition qui, si vérifiée, oblige le jeton à rester en place  1  au coup d'horloge suivant. Etc......

Le synthétiseur sera vigilant sur ce point. Tel outil considèrera que par défaut on reste dans l'état (option à prérégler). Tel autre exigera que cela soit bien spécifié sur le graphe. Un troisième ne signalera rien du tout et écrira un code VHDL qui aboutira à une synthèse incorrecte.
 
 

3- Formes sommes de monomes.

La condition logique /(/b . c) associée à la transition  t( p2, p3 ) ne se présente pas sous forme somme de monomes. On s'oblige en conséquence à développer  cette condition sous la forme :

   / (/b . c)  =  b  +  /c

Cela pourrait se traduire dans le graphe par deux transitions parallèles de  p2  vers p3. L'une avec pour condition de transition b, l'autre avec pour condition de transition  /c.
 

Nous décidons ainsi, à fin d'automatisation et de vérification, qu'à toute transition ne soit asssocié qu'un monome et un seul. Alors, l'intersection logique de ce monome et du monome qui décode l'état Q(t) de la place d'entrée constituera un des monomes de la table PLA à venir. Cette représentation exhaustive des transitions dans le réseau a son importance car nous allons constater que le nombre de monomes du PLA  à venir devra égaler le nombre de transitions ainsi mis en évidence.

On considère à ce stade que le graphe est bien formé. Il se prète à transcription automatique sous forme d'une table des transitions.
 

Table des transitions:

Toute place pi est désormais désignée  Qi sachant que cette place sera ultèrieurement identifiée par une configuration binaire dans la suite des bascules d'un registre d'état (RE).

L'écriture de la table n'est donc qu'une transcription du graphe. Elle rappelle ligne par ligne toutes les transitions possibles d'état en état y compris le rebouclage d'un état sur lui-mème (maintien). Si toutes les réceptivités des transitions se limitent à l'écriture d'un seul monome le nombre de lignes de cette table égale le nombre d'arcs d'arrivée sur les places du graphe. Chaque ligne sera une ligne de programmation du PLA à venir.

         état                                           état
         présent        récep          suivant          sorties
                                                                          Z1  Z2
     _______________________________________

           Q0        a                    Q1           0   0
           Q0       /a                    Q0           0   0
           Q0        a.b.c               Q3          0   1

           Q1        a./c                Q4           0   1
           Q1        a./b.c             Q1           0   1
           Q1       /a                    Q2           0   1

           Q2       /b.c                 Q3           1   -
           Q2         b                    Q2          1   -             décomposition  de
           Q2        /c                    Q2          1   -         Q2 . /(/b . c)  =  Q2 . b  +  Q2 . /c

            Q3         a                    Q6         1   1
            Q3        /a                    Q3         1   1

            Q6        /c                    Q0          -   0
            Q6         c                    Q6          -   0

             Q4        /a                   Q4          0   1
             Q4        /c                   Q4          0   1
             Q4        a.c                  Q5          0   1

             Q5       /a.b                 Q6           -    -
             Q5         a                    Q5          -    -
             Q5        /b                   Q5           -    -

Le codage.

    Tout état de marquage d'un RdP devra pouvoir ètre caractérisé dans sa matérialisation par une configuration binaire identifiant cet état de marquage. Le choix et le principe des affectations de ces configurations binaires à chacun des marquages d'un RdP est l'étape de codage du RdP.

Nous distinguons deux grands modes de codage:

     - Le mode à registre d'état (RE)
     - le mode cellulaire  (One hot).

Le mode cellulaire a été examiné par ailleurs. Nous adoptons ici le mode à registre d'état (RE).

Le codage consiste alors à affecter un code représentatif à chacune des configurations symboliques  Qi.

Décidons du codage ci-après:

 Q0  =  0 0 0
 Q1 =   0 0 1
 Q2 =   0 1 1
 Q3 =   1 1 1
 Q4 =   1 1 0
 Q5 =   1 0 0

Si nous ne nous sommes pas préoccupé jusqu'ici d'optimisation, nous décidons tout de mème ici d'adopter un codage qui a le plus souvent le mérite d'amener un allègement de la circuiterie combinatoire. C'est le principe du codage par adjacences (ADJ)

Optimisation

On se doute que du choix du codage des états dépendra la plus ou moins grande complexité des blocs combinatoires de la machine, que ce soit en nombre de portes ou en taille de PLA. De nombreux algorithmes de codage optimal ont été proposés il y a de nombreuses années qui sont utilisés par les outils de synthèse automatique des machines d'états. Les travaux continuent de s'effectuer dans ce domaine. Travaux qui prennent en compte le fait qu'une optimisation se fait toujours avec pour objectif de satisfaire certains critères, notamment les critères vitesse, superficie, voire certaines spécificités de la technologie ciblée (FPGA par exemple).

Rappelons quelques codes usuels:

Binaire                                            :  BIN
Random                                          :  RND
One-hot                                          :  HOT
Adjacence                                       :  ADJ
Linear feedback shift register            :  FSR
 

Etats hors code

Si le codage a nécessité de se réserver une configuration binaire de longueur n, nous disposons d'une capacité de codage sur  2n  codes distincts. Le plus souvent, le nombre des états de la machine est inférieur à  2ⁿ. Parmi ces 2n codes distincts, les configurations binaires qui n'appartiennent pas à la liste des codes retenus sont dits états hors code.

On veille, lors de toute synthèse de machine d'états, à vérifier le comportement de la machine si consécutivement à un couplage parasite quelconque cette machine devait se retrouver dans un de ces états hors code.  Au besoin on complète la synthèse afin d'imposer, au rythme des impulsions d'horloge une évolution de la machine qui la ramène dans le cycle principal de fonctionnement.
 
 

         état                                             état
         présent       récep             suivant                    sorties
                                                          (t+1)
       q2 q1 q0          c   b   a          q2 q1 q0        Z1  Z2
     _______________________________________________

         0  0  0                1                0  0  1           0   0

         0  0  0                0                0  0  0           0   0

         0  0  0        1  1  1               1  1  1            0   1

         0  0  1        0  -  1                1  1  0           0   1

         0  0  1        1  0  1               0  0  1            0   1

         0  0  1         -  -  0                0  1  1            0   1

         0  1  1        1  0  -                1  1  1           1   -

         0  1  1         -  1  -                0  1  1           1   -

         0  1  1        0  -  -                 0  1  1          1   -

         1  1  1         -  -  1               1  0  1          1   1

         1  1  1        -  -  0                 1  1  1          1   1

         1  0  1        0  -  -                  0  0  0          -   0

         1  0  1        1  -  -                  1  0  1          -   0

         1  1  0        -  -  0                  1  1  0         0   1

         1  1  0        0  -  -                  1  1  0         0   1

         1  1  0        1  -  1                 1  0  0          0   1

         1  0  0        -  1  0                 1  0  1         -    -

         1  0  0        -  -  1                  1  0 0          -    -

         1  0  0        -  0  -                  1  0  0         -    -

       ______________________________________________
 

Table de programmation du P.L.A.

L'écriture intermédiaire de la table de programmation avant codage est donnée figure (   ). Elle se transcrit directement du graphe  (      ).

Aprés codage des états  Qi elle se présente sous la forme de la table  (       ) qui amène enfin la table de programmation (       ).
 

Simplifications

On peut considérer maintenant cette table comme une table de vérité ordinaire et appliquer toutes les règles de simplifications pour alléger le nombre de monomes du bloc combinatoire donc du PLA. On reprend les équations logiques des variables  q2(t+1), q1(t+1), q0(t+1), Z1 et Z2.
 

Matérialisation :

La structure de la machine mettra en évidence:

-  Un registre  RE  dédié à la représentation Q(t) de l'état courant ou état présent (n bascules si codage sur n bits).
-  Le bloc combinatoire qui détermine les évolutions d'état en état, c'est le bloc de séquencement. Il voit sur ses entrées la configuration de l'état présent et les entrées primaires.
-  Le bloc combinatoire qui génère les commandes en fonction des états. C'est le bloc de sortie ou bloc des commandes.

Dans une implémentation PLA, ces deux blocs peuvent gagner à ètre fondus dans un seul et mème PLA.

Observation:

Toute implémentation de G.E autour d'un registre d'état oblige à prévoir un état de départ ou état initial. Ce n'est pas le cas d'un codage cellulaire (One-hot). Dans ce dernier cas de figure, toutes les cellules sont initialement vides. Pour une machine à registre d'état, l'état initial faisant partie de l'ensemble des états de la machine doit avoir la place qui lui correspond dans le graphe d'origine. Place forcément marquée à l'initialisation du réseau.
 

Graphe prédicat / action

Plutot que d'associer les actions aux places, on peut les associer elles aussi aux transitions. A la transition se retrouvent alors attachées une réceptivité et une action. Le franchissement de la transition déclenche simultanément la commande. En fait dans nos graphes synchrones la représentation prédicat/action sera la façon de préciser que les commandes sont enregistrées latchées. Le front d'horloge qui déclenche le franchissement sur le graphe est aussi celui qui enregistre la ou les commandes. Les sorties de la machine sont des sorties synchrones.

Il pourra s'avérer plus pratique dans ce cas de figure d'utiliser des bascules RS voire  T en lieu et place de la traditionnelle bascule D  (bibliothèque).
 

Chemin critique

La suite de portes combinatoires traversée par un signal issu de la sortie  Q  d'une bascule et aboutissant sur l'entrée  D, ou toute autre entrée d'une bascule d'arrivée est un chemin. Ce chemin est dit chemin critique si c'est le chemin le plus long en terme de temps de propagation à travers les portes de ce chemin. Cette durée ou délai de temps de propagation conditionne la période minimale de l'horloge cadençant une structure totalement synchrone. On vérifiera toujours que dans le pire cas (process, tension, température), le signal a bien le temps de se propager sur ce chemin avant apparition du prochain front de synchronisation. Pour évaluation de la période minimale Th on ajoute à ce temps le temps de délai de commutation de la bascule de départ (clock to Q) et le temps de setup (temps d'établissement) de la bascule d'arrivée.

Performances:

Lorsque certains critères de performances doivent ètre atteints, on peut ètre amené à remodeler le graphe d'états. On peut par exemple ètre conduit à dupliquer certains états dans le cas de codage one-hot pour obtenir un allègement du combinatoire qui précède les bascules.
 

Les aléas de décodage.

    Nous avons vu qu'il y avait, lors des commmutations, des occasions de "courses" entre les signaux traversant les couches de portes des blocs strictement combinatoires. Ces disparités des délais de parcours dans le magma combinatoire sont à l'origine des "aléas" (Glitches, Spikes, ....).

Pour un système séquentiel nous parleront d'aléas de décodage quand il s'agira de manifestations d'aléas consécutivement au changement d'état d'un état  i  dans un état j du registre d'état. On assiste alors à la commutation d'un nombre plus ou moins grand des variables du registre d'état (RE).

Si on ne se préoccupe que très peu, voire pas du tout, des aléas dus à la traversée du combinatoire d'état ou du bloc de séquencement, puisque resynchronisation des signaux dans le registre d'état lui-mème, les aléas sur les signaux du combinatoire de sortie (bloc des commandes) devront eux systématiquement retenir l'attention du concepteur. En effet, la présence du registre d'état, synchronisé sur front d'impulsion, fait que les commutations intempestives entre deux coups d'horloge sur les entrées de ce registre, sont sans conséquences quant à la pureté des signaux au sortir de ce registre pour autant que les temps d'établissement (setup) des bascules soient respectées. Par contre, les signaux au sortir du bloc combinatoire de sortie, ou du bloc de commande, ont diverses destinations, et selon ces destinations, il peut y avoir obligation de prendre les dispositions qui empècheront l'apparition d'aléas. Dans bien des cas, et tout particulièrement lorsqu'on se situe dans le cadre d'un conception de type "totalement synchrone", les aléas susceptibles de se manifester sur les sorties du système séquentiel n'ont pas de conséquences sur l'intégrité du controle de la partie opérative, les signaux aboutissant normalement sur les entrées de controle (EC Enable Clock) des bascules de la PO.
 

Solutions:      Resynchronisation des signaux de sortie.

xxxxx  Structure d'ensemble d'un séquenceur:
<chro>
<synchronisation sur les plots de sortie>

La synchronisation des entrées / sorties: