SYSTEMES A EVENEMENTS DISCRETS - …chauvincpge.free.fr/dis/Dis_Cours.pdf · cours sur les SLCI) : - Systèmes combinatoires : ... et des changements de base binaire vers décimal

PTSI - SII

SYSTEMES A EVENEMENTS DISCRETS

AUTOMATIQUE DISCRETE : SYSTÈMES COMBINATOIRES SYSTÈMES SÉQUENTIELS

(COURS)

a

1

&a

&

&

a b c d

11

b

c

b

d

b_

a.c

a_

a b_.

b d_.

a b c a_. .++++

S a b c a b d==== ++++ ++++. . .

1

OBJECTIFS :

♦ Ce qu’il faut connaître : - La définition d’un système à évènements discrets ;

- Les fonctions logiques (et, ou, non, nand, nor, xor) ;

- Les notions machine d’états, transition, états, actions, activité, évènement,

conditions, état initial et état final ;

- Le diagramme d’états ;

- Les structures algorithmiques de base.

♦ Ce qu’il faut savoir faire : - Interpréter la table de vérité d’un système logique ;

- Etablir la table de vérité d’un système logique à partir d’une représentation

de ses fonctions logiques ;

- Interpréter tout ou partie de l’évolution temporelle d’un système ;

- Représenter tout ou partie de l’évolution temporelle d’un système ;

- Lire et décoder un diagramme d’états ;

- Décrire et compléter un algorithme représenté sous forme graphique.

PTSI - SII

SYSTEMES A EVENEMENTS

DISCRETS

Table des matières

I) Définitions 1 II) Systèmes combinatoires 3 Variables (binaires) 3 Fonctions logiques 4 Table de vérité 4 Opérateurs logiques usuels 5 Principales propriétés des opérateurs 5 Représentation d’une fonction logique : logigramme et chronogramme 6 III) Numération et codage 7 IV) Systèmes séquentiels : généralités sur les machines d’états 10 V) Systèmes séquentiels : diagramme d’états(-transitions) 11 VI) Systèmes séquentiels : algorigramme 19

PTSI – SII SED – I) Définitions 1

I) Définitions

Nous avons déjà introduit les notions de systèmes automatiques, en séparant les systèmes linéaires continus et invariants (asservis ou non) des systèmes « à évènements discrets » (logiques ou numériques), eux-mêmes sous-divisés en systèmes combinatoires ou séquentiels (cf. chapitre 1 du cours sur les SLCI) :

- Systèmes combinatoires : les grandeurs de sortie s’expriment comme une combinaison des grandeurs d’entrée à chaque instant (sans mémorisation des valeurs précédentes) ;

- Systèmes séquentiels : les grandeurs de sortie s’expriment comme une combinaison des grandeurs d’entrée ET de l’état précédent des grandeurs d’entrée et de sortie. Les systèmes séquentiels ont donc besoin de mémoires afin de retenir la valeur de certaines variables (d’entrées, de sorties ou internes).

Diagramme de blocs internes d’un système à évènements discrets séquentiel :

PTSI – SII SED – I) Définitions 2

Les systèmes à évènements discrets (SED) sont des systèmes dont l’état change seulement à certains instants, lors de l’occurrence d’évènements particuliers, contrairement aux systèmes continus dont l’état change en permanence avec l’évolution du temps.

Les systèmes à évènements discrets (SED) possèdent un ensemble d’états possibles fini. L’état d’un système est donné par l’ensemble des valeurs de ses variables d’entrées, de sorties et internes. Les variables des SED sont discrètes. Si elles sont issues d’un capteur analogique, ces variables continues seront discrétisées (numérisées), via par exemple un convertisseur analogique-numérique (CAN). Les variables discrètes ne peuvent prendre une valeur que dans une plage finie de valeurs possibles. Les variables discrètes peuvent être « binaires » (une valeur parmi deux possibles, symbolisées par exemple par « 0 » ou « 1 ») ou « numériques » (une valeur parmi un nombre fini possible, souvent par palier constant appelé résolution, et souvent obtenues par combinaison de données binaires, via des paquets de bits). Dans les systèmes pluritechniques, l’information logique d’entrée provient d’un détecteur, d’un bouton poussoir, d’un contact ; l’ordre logique de sortie sert à démarrer / arrêter un moteur, à faire bouger la tige d’un vérin… Les carte de commande et les ordinateurs (basés tous deux sur des microprocesseurs) sont des systèmes numériques à évènements discrets, et sont aujourd’hui très répandus pour commander les systèmes pluritechniques.

PTSI – SII SED – II) Systèmes combinatoires 3

II) Systèmes combinatoires

♦ Variables (binaires) Comme déjà précisé, un système est dit combinatoire si toutes ses variables d’entrées et de sorties sont binaires, c’est-à-dire ne pouvant qu’une valeur parmi deux possibles. Les variables d’entrée peuvent être des boutons poussoirs (interrupteurs), des détecteurs (de présence, de lumière…). Les variables de sortie peuvent être des moteurs, vérins, résistances chauffantes, pompes, ampoules… en mode de fonctionnement TOR (tout ou rien), c’est-à-dire « allumé ou éteint ». Remarques:

- le comportement "Tout ou Rien" (TOR) ne correspond qu'au comportement normalement prévu en régime stabilisé et en l'absence de tout dysfonctionnement.

- l'association d'une variable binaire à un composant ne peut pas rendre compte des états transitoires apparaissant entre deux états stables. C'est donc une modélisation simplifiée du comportement réel.


♦ Fonctions logiques Un système combinatoire est décrit par une fonction logique qui permet de définir de manière unique la sortie pour une combinaison des entrées. Une fonction logique est une combinaison de variables logiques, reliées par des opérateurs logiques. Il existe 3 opérateurs logiques élémentaires : NON ( ¯ ) ; ET ( . ) ; OU ( + ). Exemple : Soit la fonction logique NN traduisant un niveau normal de liquide dans une cuve.

Le capteur b de niveau bas est à 1 si le niveau est au-dessus de lui. De même, le capteur h de niveau haut est à 1 si le niveau est surabondant. Alors, le niveau est normal (NN = 1) si b est à 1 ET si h est à 0. On écrit donc l’équation de la fonction logique : .NN b h= On dit que b et h sont les variables d’entrée de la fonction logique NN, qui est appelée elle-même la variable de sortie.

♦ Table de vérité La table de vérité d’une fonction logique est l’inventaire des valeurs (binaires) de la variable de sortie, pour toutes les combinaisons possibles des variables d’entrée. Pour n variables binaires d’entrée, il y a 2n combinaisons possibles, donc 2n lignes à la table de vérité. L’équation de la fonction logique est obtenue en écrivant les combinaisons des entrées pour lesquelles la sortie est à 1.

Exemple ci-contre : . . . . . . . .F a b c a b c a b c a b c= + + +

Remarque : lorsque la sortie vaut plus souvent 1 que 0, il est plus court d’écrire sa fonction logique complémentaire, qui sera vraie uniquement pour les valeurs 0 de la sortie.

Exemple ci-contre : . . . .G a b c a b c= + Pour en déduire l’expression de G, voir le chapitre ci-dessous « principales propriétés des opérateurs », même si la simplification des expressions logiques n’est pas au programme.

Entrées Sortie a b c F 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1

Entrées Sortie a b c G 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 1


♦ Opérateurs logiques usuels

♦ Principales propriétés des opérateurs Ne sont pas à connaître par cœur, mais à savoir retrouver grâce aux tables de vérité.

Théorèmes de De Morgan : .a b a b+ = et .a b a b= + .1a a= .0 0a = .a a a=

1 1a + = 0a a+ = a a a+ = a a= . 0a a = 1a a+ =

Commutativité : . .a b b a= a b b a+ = + Associativité : ( )a b c a b c+ + = + + ( ). . . .a b c a b c=

Distributivités : ( ) ( ) ( ). . .a b c a b a c+ = + ( ) ( ) ( ). .a b c a b a c+ = + +

Absorption : .a a b a+ = .a a b a b+ = +


♦ Représentation d’une fonction logique

�� Table de vérité : voir plus haut

�� Logigramme C’est une représentation utilisant des opérateurs logiques élémentaires. Exemple : Ci-contre le logigramme de la fonction F dont la table de vérité figure en début de cours. • Plusieurs logigrammes sont possibles, selon les opérateurs dont on dispose et selon le nombre d'entrées qu'ils ont. • Tout logigramme peut être réalisé en n’utilisant que des portes NON-ET, ou bien en n’utilisant que des NON-OU. Ces deux opérateurs sont dits universels. Ci-dessous les ET, OU et Complément avec ces portes.

�� Chronogramme Le chronogramme est un graphe qui permet de définir l’état d’une variable de sortie à partir de l’état des entrées définies chronologiquement.

Exemple ci-dessous de la fonction F avec une évolution des entrées au cours du temps comme définie dans le tableau ci-contre :

PTSI – SII SED – III) Numération et codage 7

III) Numération et codage

♦ Nécessité du codage et du décodage

Les circuits logiques (en particulier les microprocesseurs) ne peuvent traiter que des informations binaires. Ainsi, tout problème, avant d’être traité par calculateur, doit être transcrit sous forme binaire : cette opération s’appelle le codage. Le résultat est donné sous forme binaire par le calculateur. Il faut alors le retranscrire dans le langage original, seul exploitable par l’homme : cette opération s’appelle le décodage.

Exemple :

♦ Bases de numération

Le système de numérotation le plus utilisé aujourd’hui est le système décimal. Les systèmes automatiques utilisent plus naturellement le système binaire. La connaissance du système binaire et des changements de base binaire vers décimal et décimal vers binaire est donc essentielle à l’étude et à la réalisation des chaînes d'informations.

�� Bases Dans une base, un nombre est représenté par la juxtaposition de symboles appelés digits pris parmi les éléments de la base B considérée.

Les bases les plus couramment utilisées sont : - la base 10 (ou décimale) contenant 10 symboles : 0, 1, 2, 3, 4,

5, 6, 7, 8, 9 - la base 2 (ou binaire) contenant 2 symboles : 0, 1 - la base 16 (ou hexadécimale) comptant 16 symboles : 0, 1, 2, 3,

4, 5, 6, 7, 8, 9, A, B, C, D, E, F Exemple : (10)10 (lire « dix ») représente le nombre 10 en base 10, (10)2 (ou %10, lire « un, zéro ») représente le nombre 2 écrit en base 2 et (10)16 (ou $10) représente le nombre 16 écrit en base 16.

0 0 01 1 12 10 23 11 34 100 45 101 56 110 67 111 78 1000 89 1001 910 1010 A11 1011 B12 1100 C13 1101 D14 1110 E15 1111 F

Base décimale

B10

Base binaireB2

Base hexadécimale

B16


�� Changement de base L’objectif est de mettre en place la correspondance entre l’expression d’un nombre dans une base (ex : base 10) et son expression dans une autre base (ex : base 2).

• Passage d'une base X vers la base décimale : Un nombre (abcd)X (avec a,b,c,d quatre digits) dans une base X correspond au nombre suivant en base décimale : (abcd)X = a.X3 + b.X2 + c.X1 + d.X0

On parle de système de numérotation pondéré. On appelle poids le rang de chaque digit (exemple : « a » digit de poids le plus fort)

Exemples : Binaire vers décimal : ( ) ( )3 2 1 0

2 101011 1 2 0 2 1 2 1 2 11= × + × + × + × =

Hexadécimal vers décimal : ( ) ( )2 1 0

16 103 10 16 3 16 11 16 1619A B = × + × + × =

• Passage d'une base décimale bers une base X :

On utilise la méthode des divisions successives. Soit un nombre N défini sur une base X et comprenant n digits. Son écriture en base 10 est la suivante : (N)X = np.X

p + np-1.Xp-1 + … + n1.X

1 + n0.X0

Effectuer le changement de base revient à déterminer n0, n1, … np-1, np En mettant x en facteur il vient : (N)X = X.(np.X

p-1 + np-1.Xp-2 + … + n1.X

0) + n0 qui est de la forme : (N)X = X.(quotient) + reste Ceci permet de déterminer n0 en prenant le reste de la division euclidienne de (N)X par X. En reprenant le quotient précédent et en factorisant de nouveau par X on trouve un nouveau reste n1 et ainsi de suite jusqu’à np.

Ainsi pour écrire un nombre décimal en binaire, il faut faire des divisions successives par 2. Par exemple pour écrire 19 en binaire : Le sens de lecture, et donc d’écriture, se fait selon la flèche. Donc 19 s’écrit en binaire 10011, soit : (19)10 = (10011)2.

Exemple : Ecrire 28 en binaire et en héxadécimal :

19 2

1 9 2

1 4 2

0 2 2

0 1 2

1 0

28 2

0 14 2

0 7 2

1 3 2

1 1 2

1 0

(28)10 = (11100)2

28 16

12 1 16

1 0

(28)10 = (1C)16


♦ Différents codes

Les ordinateurs travaillant en binaire, tout traitement informatique ou automatique nécessite de coder l’information en binaire, à l’aide des deux états 1 ou 0. Un bit (contraction de binary digit) est un chiffre binaire (1 ou 0).

Il est également intéressant de regrouper un ensemble de valeurs binaires suivant une autre organisation qu’un système de nombres. Ces autres organisations sont appelées des codes. Il en existe un très grand nombre et chacun peut en créer selon un besoin spécifique. Les qualités requises pour un code sont principalement :

- la taille du codage (nombre de bits nécessaires) ; - la fiabilité de lecture ; - la simplicité de manipulation.

Exemple : Code ASCII (American Standard Code For Information Interchange) : Il permet de coder 128 caractères sur 8 bits (un octet). La lettre A est codée 65 en décimal, 01000001 en binaire, 41 en hexadécimal. C'est la norme la plus répandue de codage des caractères.

On distingue un code pondéré pour lequel chaque chiffre possède un poids (le binaire naturel par ex) d’un code non pondéré qui nécessite une table de correspondance pour décoder un nombre.

�� Code binaire naturel Ce code pondéré correspond à donner un nombre selon sa valeur en système de numérotation binaire. C’est un code qui permet de réaliser des opérations facilement.

Inconvénient : il introduit des erreurs lors d’un changement de code. Pour passer de (01)2 à (10)2 (donc de 1 à 2), il faut modifier deux bit en même temps. Il existe forcément un décalage temporelle, et donc, il peut s'afficher, même très brièvement, soit (11)2 soit (00)2, ce qui peut provoquer des perturbations, ou des erreurs.

�� Code binaire réfléchi, ou code Gray Ce code non pondéré est un arrangement du système binaire. Le passage d'un nombre à son suivant se fait en changeant l'état d'un seul bit. Il est très utilisé pour décrire des automatismes (un changement d’état d’un composant correspond à un bit qui change), en particulier dans les codeurs de position absolue.

Avantage : Il apporte une garantie d’interprétation avec une erreur maximale d’une incrémentation.

L'inconvénient de ce code non pondéré est qu'il est nécessaire de stocker la table de correspondance pour décoder un nombre.

Pour obtenir le code Gray, il faut faire toutes les deux (21), quatre (22), huit (23),... lignes, une symétrie en changeant la valeur du bit de gauche.

�� Code décimal codé binaire (DCB) C’est un code pondéré basé sur le code binaire naturel, mais qui est adapté à la représentation des nombres en base 10. La propriété du code DCB est d’associer quatre bits différents à chaque puissance de 10. Ainsi (1664)(10) = (0001.0110.0110.0100)(DCB). Il est utilisé pour les afficheurs 7 segments par exemple :

Décimal Binaire naturel

0 0 0 0 0 1 0 0 0 1 2 0 0 1 0 3 0 0 1 1 4 0 1 0 0 5 0 1 0 1 6 0 1 1 0 7 0 1 1 1 8 1 0 0 0

Décimal Binaire réfléchi

0 0 0 0 0 1 0 0 0 1

2 0 0 1 1 3 0 0 1 0

4 0 1 1 0 5 0 1 1 1 6 0 1 0 1 7 0 1 0 0

8 1 1 0 0

Codeur de position rotatif absolu,

en codage Gray :

PTSI – SII SED – IV) Systèmes séquentiels 10

IV) Systèmes séquentiels : généralités

sur les machines d’états La machine à nombre fini d’états (FSM : Finite State Machine), est aussi appelée automate fini. Elle peut être une entité matérielle (un microprocesseur par exemple), mais aussi une entité conceptuelle comme un algorithme. Elle comporte un nombre fini d’états. La machine à états est un système à évènement discrets, capable de mémoriser des données, de les traiter et de les restituer selon des scénarios définis au préalable.

Dans un état, un système peut avoir une activité ou être en attente. Les états d’un système se succèdent en fonction d’évènements. Un évènement est une description d’occurrence qui conduit à une évolution du comportement du système. On l’appelle aussi un déclencheur (trigger).

Par exemple, pour une machine à café, les états peuvent être : 1 – Attente de pièce ; 2 – Descente du gobelet ; 3 – Versement de la poudre à café ; 4 – Versement de l’eau chaude ; 5 – Affichage "café est prêt"…

Et les évènements : Pièce insérée ; Gobelet présent ;

Gobelet absent ; Timer terminé (compte-à-rebours)… Le comportement (succession d’états) de la machine se déroule selon une séquence. Un tel système est donc bien séquentiel.

Il existe plusieurs outils afin de représenter le fonctionnement d’une machine d’états :

- Diagramme d’états(-transitions) issu du SysML ; - Diagramme d’activités issu du SysML (pas au programme) ; - Algorigramme ; …

Il s’agit essentiellement d’outils graphiques permettant de modéliser le comportement séquentiel en termes de déroulement d’actions temporelles. Ces outils sont, à la base, des outils de modélisation du comportement séquentiel, mais peuvent aussi servir à la programmation des composants réalisant la fonction Traiter de la chaîne d’information (microcontrôleur, microprocesseur, automate programmable, …). Quel que soit l’outil adopté pour modéliser le comportement séquentiel d’un système, il existe souvent plusieurs « solutions ». « La solution » la plus simple et celle qui respecte l’ensemble des contraintes est donc à privilégier. C’est le rôle de l’ingénieur de choisir le « bon » outil, et la « meilleure solution ».

PTSI – SII SED – V) Systèmes séquentiels : diagramme d’états-transitions 11

V) Systèmes séquentiels : diagramme

d’états (-transitions)

♦ Présentation et formalisme

Le diagramme d’états (state machine diagram ou stm) est un diagramme normalisé SysML, il est utilisé pour décrire le comportement d’une machine d’états : - Le nœud (rectangle) symbolise un état

interne. Il montre ce qui se passe. - L’arc qui relie deux noeuds est appelé

transition. Il indique la possibilité de passer d’un état à un autre lorsqu’un évènement se produit.

Un même état représenté par un noeud. Au cas où aucune activité n’est souhaitée, c’est un état d’attente.

Les cas d’évolution du système entre les états sont identifiés par les transitions. On trace alors un lien entre les noeuds correspondants. Chaque transition peut être qualifiée par un évènement, une condition de garde et un effet.

♦ Règle d’évolution

Lorsqu’une transition est active (c’est-à-dire lorsque son état source est actif) et franchissable (son évènement et sa condition de garde sont vrais), alors « instantanément » l’état source est inactivé, éventuellement l’effet de la transition est effectué, et l’état destination est activé.

♦ Transition

Une transition représente le passage instantané d'un état vers un autre. Une transition ne peut donc pas avoir de durée. On appelle état source l’état de départ d’une transition et état destination l’état d’arrivée. Une transition est déclenchée par un évènement. En d'autres termes : c'est l'arrivée d'un évènement qui conditionne le franchissement de la transition. Une transition peut aussi être automatique, lorsqu'on ne spécifie pas l'évènement : elle s’effectuera alors lorsque l’activit de l’état source sera terminée (et lorsqe la condition de garde sera vraie).

Dans une transition,

- le ET logique s’écrit & - le OU logique s’écrit || - la fonction NON s’écrit !


�� Evènements

�� Condition de garde La condition de garde est une expression booléenne (ou fonction logique) faisant intervenir des entrées et / ou des variables internes. Elle se note entre crochets. Elle autorise le passage d’un état à un autre. Il est possible d’utiliser les notations non booléennes de front montant (↑) et front descendant (↓).

Remarque : Différence entre évènement et condition de garde : Un événement est parfaitement daté dans le temps, il correspond par exemple à un passage d'une variable de 0 à 1 (front montant). Une condition de garde n'est pas datée, elle doit être vraie (niveau logique 1) à l'instant où l'événement survient pour que la transition soit franchie.

Exemple d'évènement : appui sur un bouton-poussoir, capteur fin de course atteint, etc. Exemple de condition de garde : vitesse du véhicule non nulle, température > 20°C, etc.

�� Effet

L’effet associé à une transition est effectué lorsque la transition est franchie, il ne prend pas de temps et ne peut pas être interrompu. Il se note après l’évènement, précédé d’un « / ». Son exécution peut par exemple provoquer un changement d’état ou l’émission d’un ordre.

�� Transition réflexive Une transition réflexive entraîne une sortie d’état puis un retour dans ce même état.

�� Transitions conditionnelles Plusieurs transitions peuvent quitter un même état. Une seule d'entre elles doit être déclenchée ; les événements et / ou les conditions de garde doivent donc être exclusives.

Une autre représentation est possible, qui utilise le point de décision : Il est possible d’utiliser une condition particulière, notée [else], sur un des segments en aval d’un point de décision. Ce segment n’est franchissable que si les conditions des autres segments sont toutes fausses.


♦ Etats

Un état représente une période de la vie du système. Pendant cette période, le système accomplit une ou plusieurs actions, ou attend un évènement. Il peut être actif ou non ; plusieurs sous-états peuvent être actifs en même temps dans le même système. Chaque (sous-)état est dessiné sous la forme d'un rectangle aux coins arrondis (ou une ovale), contenant son nom.

�� Etats initial et final Il existe deux états particuliers :

- l'état initial : pseudo-état qui indique un point d'entrée dans un graphe ; - l'état final : non obligatoire, il indique que le système décrit n'a plus d'état actif.

�� Activités et actions associées à l’état

A un état, on peut principalement rattacher : - une action d’entrée, précédée de « entry/ » ; - une activité, précédée de « do/ » ; - une action de sortie, précédée de « exit/ ».

Une activité peut être considérée comme une unité de comportement. Elle prend du temps et peut être interrompue. On la trouve à l’intérieur des noeuds du diagramme (mot-clé « do »).

A contrario, une action ne prend pas de temps et ne peut pas être interrompue. Son exécution peut par exemple provoquer un changement d’état, l’émission d’un ordre pour un pré-actionneur ou un retour de valeur. On peut les trouver dans les transitions (effet) ou dans les états (mot-clé « entry » ou « exit »). Une action peut être :

- un ordre de mise à 1 d'une sortie ; la syntaxe est alors SORTIE := 1 ; - un ordre de mise à 0 d'une sortie ; la syntaxe est alors SORTIE := 0 ; - une modification d'une variable numérique interne, par exemple un compteur C : la syntaxe

est alors C := C + 1 ; pour incrémenter la valeur du compteur C de 1.

Pendant que l'état est actif, un évènement peut lancer une action avec la syntaxe : évènement/ suivi de l'action. Cette action est lancée chaque fois que l'évènement survient, tant que l'état est actif.

Remarque : Un état peut ne pas contenir d'action. Il sert alors à attendre le déclenchement de la transition suivante. On parle d’état d’attente.

♦ Exemple générique de base


♦ Etats composites et hiérarchisation

�� Etat composite Lorsque le comportement à décrire :

- risque d’être peu lisible car trop complexe, - fait apparaître des parties "séparables" de l’ensemble,

alors on extrait ces parties pour en faire des sous-graphes séparés, hiérarchiquement inférieurs au graphe principal. On englobe ces sous-graphes dans un état appelé « état composite » ou « super-état » ou « état sous-machine » ou « sous-machine à état ». Un état composite est composé de plusieurs sous-états internes et possède un état initial. Il est repéré par ce symbole, en bas à droite de l’état :

�� Règles d’évolution avec des états composites

Prenons l’exemple d’un four à micro-ondes :

Il y a 2 états composites "Fermé" et "Ouvert". L'état composite "Fermé" contient lui-même un sous-état composite "Chauffe". Il contient lui-même un sous-graphe formé de 2 sous-états "600 W" et "900 W". • Il peut y avoir des transitions ayant pour source / cible la frontière d'un sous-état ou la frontière d'un état composite. Si une transition de frontière est franchie, alors l’ensemble de l’état composite source est désactivé, et c’est l’état initial de l’état composite cible qui est activé.

• Quand plusieurs transitions sont possibles, on choisit de suivre celle qui part de l'état le plus en bas de la hiérarchie des états actifs, donc ici partant de "Chauffe" et non pas de "Fermé". Autrement dit :

- si l'état actif est "Chauffe" quand on ouvre la porte, l'état "En pause" s'active ; - si l'état actif est "Off" contenu dans "Fermé" quand on ouvre la porte, l'état "Ouvert" s'active

et donc l'état "Off" qu'il contient. • Autre exemple de l'évolution avec des états composites :

Supposons que l'état actif soit l'Etat11. Alors, lorsque l'évènement "event" arrive, l'Etat1 est désactivé et il se produit successivement les actions suivantes : - Quitter E11 - Quitter E1 - EntrerE2 - EntrerE21 - EntrerE22,

et l'état actif est l'Etat22 (les états composites Etat 21 et Etat2 sont aussi actifs).


�� Concurrence et synchronisation (états orthogonaux)

Dans un état composite, plusieurs graphes d'états peuvent évoluer simultanément (en parallèle). On dit qu'il y a concurrence de plusieurs états. Par exemple pour un distributeur de boissons : L'état composite est dit orthogonal car il comporte plus d’une région, chaque région représentant un flot d’exécution.

• Graphiquement, dans un état orthogonal, les différentes régions sont séparées par un trait horizontal ou vertical en pointillés allant d'un bord à l'autre de l’état composite.

• Chaque région peut posséder un état initial et final. Une transition qui atteint la bordure d’un état composite orthogonal est équivalente à une transition qui atteint les états initiaux de toutes ses régions concurrentes.

• Toutes les régions concurrentes d’un état composite orthogonal doivent atteindre leur état final pour que l’état composite soit considéré comme terminé. La synchronisation est alors automatique et la transition de sortie de l'état composite est déclenchée. • Il est également possible de représenter ce type de comportement au moyen de transitions concurrentes constituées de barres de synchronisation "fork" et "join" . Le graphe ci-dessous est une représentation équivalente à la précédente :

• Les transitions automatiques (sans évènement ou condition de garde) qui partent d'une barre de synchronisation "fork" se déclenchent en même temps. On ne franchit une barre de synchronisation "join" qu'après déclenchement de toutes les transitions qui s'y rattachent.

Remarque : Sur ce diagramme, l’état orthogonal "préparation boisson et restitution monnaie" peut éventuellement ne pas apparaître (tout en gardant la représentation de ses sous-états) pour alléger la représentation, car la notion de concurrence est clairement apparente de par l’utilisation des barres.


�� Conditionner une transition par l’activité de l’état d’un autre sous-graphe :

L'état composite orthogonal K est composé des sous-états L et M. L et M s'activent simultanément, et évoluent indépendamment, en parallèle. Au départ, EL1 et E-M1 sont actifs.

Pour que M passe d'E-M2 à E-M1, il faut que l'évènement Tr4 survienne, à condition que E-L3 soit actif. Cet évènement est conditionné par l'activité de l'état E-L3 de l'autre sous-graphe.

La syntaxe de la condition de garde vérifiant l'activité de ETAT est : [in ETAT].

�� Points d’entrée/sortie multiples :

Lorsque plusieurs points d’entrée et/ou sortie sont utiles dans une sous machine, il faut placer des pseudo‐états correspondants :


♦ Les neufs pseudo-états


♦ Démarche de modélisation du comportement séquentiel d’un

système par un graphe d’états

Etape 1 : Définir la frontière du système et recenser les variables d’entrées et de sorties ;

Etape 2 : Recenser, nommer et tracer les états du système ;

Etape 3 : Tracer les transitions entre les états en fonction du comportement séquentiel souhaité ou observé ;

Etape 4 : Définir les conditions (et évènements) associées à chaque transition et les actions associées à chaque état ;

Etape 5 : Vérifier, pour le graphe d’états complet, les propriétés de :

- complétude : signifie que le comportement est toujours défini : à chaque évolution des variables d’entrées (conditions ou évènements), et quel que soit l’état source, il existe au moins un état destination ;

- non contradiction : signifie qu’à tout changement des variables d’entrées (conditions et évènements), un et un seul état destination existe ;

PTSI – SII SED – VI) Systèmes séquentiels : Algorigramme 19

VI) Systèmes séquentiels :

algorigramme

♦ Définitions

Algorithme : C'est l'ensemble de règles opératoires ordonnant à un processeur d'exécuter dans un ordre déterminé un nombre d'opérations élémentaires.

Algorigramme (ou ordinogramme) : C'est une représentation graphique de l'algorithme utilisant des symboles normalisés.

♦ Eléments constitutifs d’un algorigramme


♦ Structures de base des algorigrammes

♦ Structure linéaire (ou « unique ») :

♦ Structure alternative :


♦ Structure itérative :

♦ Structure à reprise de séquence :

♦ Démarche de modélisation d’un système par un algorigramme

Même pour la description du comportement d’un système simple, il est souvent nécessaire de décomposer le fonctionnement en tâches simples : « petits » algorigrammes appelés « macros » ou « fonctions » réalisant chacun une tâche simple. Un algorigramme général fera appel alors à ces différents algorigrammes pour décrire le comportement global du système.

Documents

SYSTEMES A EVENEMENTS DISCRETS - …chauvincpge.free.fr/dis/Dis_Cours.pdf · cours sur les SLCI) : - Systèmes combinatoires : ... et des changements de base binaire vers décimal