LYCEE CHAPTAL

Cours 1

PTSI

Séquence 4 SED et réseaux

CPGE PTSI/PT*

Classe entière

A2 - Définir les frontières de l'analyse A3 - Conduire l'analyse B2 - Proposer un modèle D1 - Découvrir le fonctionnement d’un système complexe G1 - Élaborer, rechercher et traiter des informations

2h

Commande et comportement des systèmes à évènements discrets

Sciences

Industrielles pour

l’Ingénieur

2

Table des matières

I. SYSTEMESLOGIQUES 3

I.1. DEFINITION 3I.2. ALGEBREDEBOOLE 4I.3. TABLEDEVERITE 4I.4. LOGIGRAMME 6I.5. CHRONOGRAMME 6I.6. MISEENŒUVREDESFONCTIONSLOGIQUES 6I.7. CODAGEDEL’INFORMATION 7

II. SYSTEMESSEQUENTIELS 10

II.1. DEFINITION 10II.2. FONCTIONMEMOIRE 10II.3. MACHINED’ETAT 11II.4. DIAGRAMMED’ETAT(SYSML) 11II.5. LESSTRUCTURESALGORITHMIQUESDEBASE 12II.6. DIAGRAMMEDESEQUENCE(SYSML) 12

BIBLIOGRAPHIE 13

KHOLLETYPE(LOGIQUECOMBINATOIRE):ETUDED’UNFEUDECARREFOUR 14

3

Commande et comportement des systèmes à évènements discrets Dans l’ère du numérique, les signaux de communication entre les différents systèmes sont numériques et non plus analo-giques. Les signaux à contrôler sont donc du type « tout ou rien » (TOR) utilisant une information binaire « 1 » ou « 0 ». On distinguera deux types de systèmes :

• Systèmes à logique combinatoire : signal d’entrée logique (ou une combinaison de signaux d’entrée) conduit inva-riablement au même signal de sortie. On dit que la même cause produit toujours le même effet, et que l’effet disparaît dès que la cause disparaît.

• Systèmes à logique séquentielle : signal d’entrée logique (ou une combinaison de signaux d’entrée) conduit à un signal de sortie prenant en compte une chronologie préétablie. On dit qu’une même cause peut produire des effets différents, et qu’un effet peut rester maintenu alors même que sa cause a disparu.

I. Systèmes logiques

I.1. Définition

• Système à logique combinatoire : un système logique est dit combinatoire lorsqu’à une combinaison de variables d’entrées ne correspond à une seule combinaison de variable de sortie. Exemple : un sèche cheveux Son fonctionnement pourra être traduit sous forme d’équation logique, de table de vérité, de logigramme, de chronogramme, de schéma de contact électrique ou encore de schéma pneumatique.

• Variable binaire : on appel variable binaire une variable prenant ses valeurs dans l’ensemble {0,1}. Un état binaire est appelé « bit » (contraction de binary digit). Exemple : les variables binaires sont souvent appelées « a », « b » …

• Equation logique : on appelle équation logique une combinaison de plusieurs variables logiques donnant l’état d’une variable de sortie associée. Cette combinaison est réalisée à l’aide d’opérations logiques. Exemple : 𝑆 = 𝑎 + 𝑏

• Table de vérité : la table de vérité représente l’état de la variable de sortie pour chacune des combi-naisons des variables d’entrées. S’il y a n variables d’entrée, la table comporte 2n combinaisons diffé-rentes d’entrées.

• Logigramme : Un logigramme est la représentation d'une équation par le symbole graphique des opérateurs. Il répond à une norme (AFNOR en France ou ASGS en Amérique).

• Chronogramme : représentation temporelle des variables binaires d’entrées et de sorties.

Remarque :

• On considère généralement en logique combinatoire que les sorties évoluent en même temps que les entrées.

• Une table de vérité ́à plusieurs entrées peut se mettre sous la forme d’un tableau à deux entrées, dit de Karnaugh. Exemple :

Table de vérité ́ à trois entrées (m,a,X-) et une sortie X+

Tableau de Karnaugh

• Equation logique :𝑋+ = 𝑚 + 𝑋−. 𝑎̅ • Soit littéralement le système est à

l’état marche (𝑋+ = 1) si on appuie sur m (quelque soient a et 𝑋−) ou si il est déjà en marche (𝑋− = 1) et que l’on appuie pas sur a

4

I.2. Algèbre de Boole

George Boole, né le 2 novembre 1815 à Lincoln (Royaume-Uni) et mort le 8 dé-cembre 1864 à Ballintemple (Irlande), est un logicien, mathématicien et philo-sophe britannique. Il est le créateur de la logique moderne, fondée sur une structure al-gébrique et sémantique, que l'on appelle algèbre de Boole en son honneur.

L’algèbre de Boole est l’ensemble B={0,1} muni des lois :

• • •

Les lois précédentes sont définies par :

• • •

Propriétés vérifiées par l’algèbre de Boole :

Commutativité 𝑥. 𝑦 = 𝑦. 𝑥 𝑥 + 𝑦 = 𝑦 + 𝑥

Eléments neutres 𝑥. 1 = 𝑥 𝑥 + 0 = 𝑥 Eléments absorbants 𝑥. 0 = 0 𝑥 + 1 = 1 Eléments symétriques 𝑥. 𝑥 = 0 𝑥 + 𝑥 = 1 Idempotence 𝑥. 𝑥 = 𝑥 𝑥 + 𝑥 = 𝑥 Distributivité 𝑥. 𝑦 + 𝑧 = 𝑥. 𝑦 + 𝑥. 𝑧 𝑥 + 𝑦. 𝑧 = 𝑥 + 𝑦 . (𝑥 + 𝑧) Absorption 𝑥. 𝑥 + 𝑦 = 𝑥 𝑥 + 𝑥. 𝑦 = 𝑥

On notera le Théorème de De Morgan : 𝑥. 𝑦 = 𝑥 + 𝑦 et 𝑥 + 𝑦 = 𝑥. 𝑦 Et de manière généralisée : 𝑥1. 𝑥2 . … . 𝑥- = 𝑥1 + 𝑥2 + ⋯ + 𝑥- et 𝑥1 + 𝑥2 + … + 𝑥- = 𝑥1. 𝑥2 . … . 𝑥- Remarque : écriture des équations Booléennes

Il existe de nombreuses façons d’écrire les équations booléennes qui interviennent dans les tests. On donne les principales ci-dessous, issues des différents langages informatiques et que l’on retrouve dans les diagrammes d’états, selon la culture de leurs auteurs ou les logiciels utilisés.

I.3. Table de vérité

Fonction Tableau de vérité Equation logique

Logigramme AFNOR ASGS

Fonction Oui

a S

0

1

5

Fonction Tableau de vérité Equation logique

Logigramme AFNOR ASGS

Fonction NON

Fonction OU (« OR »)

Fonction ET (« AND »)

Fonction NON ET (« NAND »)

𝑆 = 𝑎. 𝑏

Fonction NON OU (« NOR »)

𝑆 = 𝑎 + 𝑏

Fonction inhibition

𝑆 = 𝑎. 𝑏

Fonction OU

exclusif (« XOR »)

𝑆 = 𝑎 ⨁ 𝑏 (= 𝑎. 𝑏 + 𝑎. 𝑏)

Remarque : les fonctions « ET », « OU » et « NON » permettent de réaliser toutes les fonctions logiques désirées.

a S

0

1

a b S

0 0

1 0

0 1

1 1

a b S

0 0

1 0

0 1

1 1

a b S

0 0 1

1 0 1

0 1 1

1 1 0

&

a S

b

a b S

0 0 1

1 0 0

0 1 0

1 1 0

≥ 𝟏

a S

b

a b S

0 0 0

1 0 1

0 1 0

1 1 0

&

a S

b

a b S

0 0 0

1 0 1

0 1 1

1 1 0

= 𝟏

a S

b

6

I.4. Logigramme

Un logigramme est une représentation graphique d’une fonction logique à l’aide de symboles logiques (appelés également « portes logiques »).

Exemple : Pour 𝑆 = 𝑎. 𝑏 + 𝑐 , voici le tracé du logigramme avec une porte « ET » et une porte « OU ».

I.5. Chronogramme

C’est le tracé qui montre l’évolution temporelle de la sortie en fonction de celles des entrées.

Exemple : Pour 𝑆 = 𝑎. 𝑏 + 𝑐 , voici le tracé du chronogramme. Remarque : Sur le chronogramme, le moment ou une variable passe de « 0 » à

« 1 » est appelé front montant. A l’inverse le moment ou elle passe de « 1 » à « 0 » est appelé front descendant.

I.6. Mise en œuvre des fonctions logiques

La réalisation la plus flexible réside dans l’utilisation de cartes programmables utilisant soit des langages propriétaires, soit des langages tels que Python, Scilab ou autres.

La mise en œuvre de fonction logique peut être réalisée également avec l’associations de :

• contacts électriques • composants pneumatiques • circuits de transistors • circuits logiques intégrés

Logigramme Contact électrique Composant pneumatique

Circuit de transistors Circuit logique intégré

Fonction « NON »

Circuit intégré

74HC04

Fonction « ET »

Circuit intégré

74HC08

Interrupteur a

Lampe S

Interrupteur b

Lampe S

Interrupteur a

7

I.7. Codage de l’information

I.7.1. Les bases les plus utilisées

• Base 2 : Binaire (naturelle)

En logique du fait que l’on traite des signaux on utilise un code binaire ou code base 2. Il s’écrira sous la forme 𝑁 = 𝑎(𝑎()* … 𝑎*𝑎, - = 𝑎(×2( + 𝑎()*×2()* + ⋯+ 𝑎*×2* + 𝑎,×2,. Si n=7, le nombre sera composé de 8 bits (appelé octet) et ne pourra représenter qu’un nombre compris entre 0 et 255 (soit 28 = 256 nombres différents).

Exemple : 𝑁 = 10110 - =

• Base 10 : décimal

C’est un système de numération très ancien, dicté par le nombre des doigts des deux mains. C’est le système que nous utilisons tous les jours. Il s’écrira 𝑁 = 𝑎(𝑎()* … 𝑎*𝑎, *, = 𝑎(×10( + 𝑎()*×10()* + ⋯+ 𝑎*×10* + 𝑎,×10,.

Exemple : 𝑁 = 1097 *, =

• Base 16 : hexadécimal

C’est un système utilisé pour abréger l’écriture des nombres binaires, qui nécessitent un grand nombre de bits pour exprimer un nombre élevé. Les symboles sont {1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F}. Il s’écrira 𝑁 = 𝑎(𝑎()* … 𝑎*𝑎, *6 =𝑎(×16( + 𝑎()*×16()* + ⋯+ 𝑎*×16* + 𝑎,×16,.

Exemple : 𝑁 = 1𝐴8𝐸3 *6 =

I.7.2. Code binaire réfléchi

Dans les conversions d’une grandeur analogique en une grandeur numérique on a besoin que les grandeurs successives ne diffèrent que d’un caractère, afin d’éviter les erreurs. En binaire naturel on passe du chiffre 7 au chiffre 8 en modifiant 4 bits (0111 devient 1000) alors qu’en binaire réfléchi seul le bit de poids fort change (0100 devient 1100). Ce code est couramment utilisé dans les roues codeuses (codeur absolu) et autres capteurs numériques, afin d’éviter les erreurs de mesures.

I.7.3. Code BCD

Le décimal codé binaire (DCB) (binary coded decimal ou BCD en anglais), est un système de numération utilisé en électronique et en informatique pour coder des nombres en se rapprochant de la représentation humaine usuelle, en base 10. Dans ce format, les nombres sont représentés par les chiffres décimaux les composant, et chacun de ces chiffres est codé sur quatre bits.

Décimal Code binaire Code binaire réfléchi 0 0000 0000 1 0001 0001 2 0010 0011 3 0011 0010 4 0100 0110 5 0101 0111 6 0110 0101 7 0111 0100 8 1000 1100 9 1001 1101

8

Ainsi, pour coder un nombre tel que 278, il suffit de coder chacun des chiffres 2, 7 et 8 séparément comme suit :

I.7.4. Code barre EAN 13

Les codes EAN 13 (European Article Numbering à 13 chiffres) sont les codes à barres utilisés dans le monde entier sur l'ensemble de produits de grande consommation (On utilise parfois le code EAN 8 pour les objets de petite taille). Ils comportent 13 chiffres dont la signification varie suivant le type du produit :

• les deux ou trois premiers correspondent au pays de provenance du produit, ou à une classe normalisée de produits ;

• les 4 ou 5 suivants sont le numéro de membre de l’entreprise participant au système EAN ;

• les 4 ou 5 suivants sont le numéro d’article du produit ainsi marqué et • le treizième est une clé de contrôle calculée en fonction des douze précédents.

Déchiffrement du code barre : Les barres verticales noires et blanches (d’éléments A ou B) utilisées sont des Codes Linéaires dont les barres élémen-

taires sont toutes de même largeur, dite largeur élémentaire ou module. Il en résulte que les largeurs des barres verticales sont toutes des multiples de ce module :

• une barre de largeur 1 correspond à une seule barre élémentaire ; • une barre de largeur 2 correspond à 2 barres élémentaires de même couleur ; • une barre de largeur 3 correspond à 3 barres élémentaires de même couleur ; • une barre de largeur 4 correspond à 4 barres élémentaires de même couleur ;

Pour faire correspondre le code barre au nombre écrit en dessous, on utilise le tableau ci-contre : Exemple :

On retrouve aujourd’hui d’autre type de code barre, en 2D :

9

I.7.5. Code ASCII

L’un des codes les plus connus des utilisateurs de PC est le code ASCII (American Standard Code for Information

Interchange). Il a été défini en 1963 aux Etats-Unis. Il est utilisé pour transmettre l'information entre les ordinateurs d'une part et leurs périphériques d'autre par (imprimantes, claviers, dispositifs de visualisation,etc.)

C’est un code à 7 bits autorisant donc le codage de 128 caractères parmi lesquels, tous les caractères alphanumériques utilisés en anglais.

Comme la plupart des ordinateurs traitent les bits par paquets de huit ou plus, le huitième bit est, soit inutilisé, soit utilisé comme bit de parité pour le contrôle lors de la transmission, soit utilisé pour coder un maximum de 128 caractères supplémentaires tels des caractères graphiques et des caractères nationaux (caractères accentués). On parle alors de code ASCII étendu.

10

II. Systèmes séquentiels

II.1. Définition

Exemple : Commande d’un moteur électrique par un système sé-quentiel. On remarque sur le chronogramme que la sortie S peut présenter une valeur diffé-rente (0 ou 1) pour une configuration identique des entrées m (0) et a (0). Il s’agit d’un système séquentiel.

L’évolution du système dépendant de l’évolution de ses entrées, mais aussi de son état, celui-ci doit être connu à chaque instant. Telle est le rôle de la fonction mémoire. Ainsi, tout système séquentiel peut être décrit à partir d’un cœur combi-natoire associé à une mémoire qui décrit l’état du système. De ce point de vue, un système séquentiel est un système combinatoire associé à une boucle de rétroaction. La fonction mémoire la plus simple mémorise l’état des sorties, images de l’état du système. Des fonctions plus avancées élaborent des variables internes, comme des compteurs ou des temporisations par exemple.

II.2. Fonction mémoire

La fonction mémoire permet donc de conserver le signal de sortie après que le signal d’entrée ait disparu ce qui permet une auto-alimentation du circuit de sortie (on appelle S-1, l’état antérieur de la sortie S). Voici l’exemple de la bascule RS qui contrôle un moteur. Soient deux boutons monostables « m » et « a » qui assurent le fonctionnement d'un moteur « Q ». L’appui sur le bouton « marche » déclenche la rotation du moteur s’il ne fonctionnait pas déjà ̀. L’appui sur le bouton « arrêt » provoque l’arrêt du moteur s’il était en marche. Les appuis simultanés sur les boutons « marche » et « arrêt » provoquent, soient :

- L’arrêt prioritaire - La marche prioritaire

On introduit une variable « x » interne au système (ou mémoire), qui représentera l’état précèdent du moteur.

Bascule RS Symbole normalisé Réalisation électrique (avec un relais )

Réalisation électronique (avec des portes logiques)

Table de vérité

Arrêt

prioritaire

Marche prioritaire

11

II.3. Machine d’état

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

• Un état initial et final • Un ensemble d’évènements (conditions) • Un ensemble d’états • Un ensemble d’activités • Un ensemble de règle permettant de déterminer le comporte-

ment du système.

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’action qui conduit à une évolution du comportement du système, on l’appelle aussi déclencheur (trigger).

II.4. Diagramme d’état (SysML)

II.4.1. Présentation

Le diagramme d’état (state machine diagram) est un diagramme normalisé SysML. Il permet de décrire le comportement d’un système ou d’un sous système. Le diagramme d’états est donc rattaché à un bloc. Un nœud symbolise un état interne, et un arc qui relie deux nœuds est appelé transition. Un état composite peut contenir un enchainement de plusieurs états.

II.4.2. Etat initial/final

Le point d’entrée du diagramme s’appelle l’état initial. Il est représenté par un point noir.

L’état final indique la fin d’activité de l’élément. Il est représenté par un cercle rempli de blanc avec un point noir en son centre

II.4.3. Evénement, condition de garde et effet (action)

Les évènements sont des changements pris en compte dans la description du com-portement du système. Un événement participe au déclenchement d’une transition.

La conditiopn de garde est une expression faisant intervenir des entrées et/ou des

variables internes. Elle autorise le passage d’un état à un autre. L’effet (action) associé à une transition est effectué lorsque la transition est franchie. Une transition reflexive entraine une sortie d’état puis un retour dans ce même état.

II.4.4. Activité et action

A un état, on peut rattacher une activité, une action d’entrée et une action de sortie. Une activité peut être considéré comme une unité de comportement et peut être inter-rompue. On la trouve à l’intérieur des états internes précédé du mot clé : « do ». A contrario, une action ne prend pas de temps et ne peut être interrompue. On peut les trouver dans les transitions (comme précédemment) ou dans les états, précédés du mot clé : « entry » ou « exit ».

12

II.4.5. Exemple de diagramme d’état d’un distributeur de billet

II.5. Les structures algorithmiques de base

Ces alternatives permettent de créer des structures algorithmiques de base :

• SI : si [cond] alors activer Etat1 sinon Etat2 (If)

• TANT QUE : Tant que [cond] alors activer Etat1 (boucle while)

• POUR : pour n variant de min à max activer Etat1 (boucle for)

II.6. Diagramme de séquence (SysML)

II.6.1. Présentation

Le diagramme de séquence est un diagramme normalisé SysML Le diagramme de séquence décrit les interactions entre le système ou ses sous systèmes et les acteurs extérieurs. Il décrit l’enchainement séquentiel de ces relations et définit donc un scénario de fonctionnement. Plusieurs diagrammes de séquence peuvent être définis pour un même système, ils sont à rattachés à un cas d’utilisation

13

II.6.2. Description

• Un élément (acteur ou sous-système) est représenté par une ligne de vie : ligne verticale en pointiller • Les activités de ces éléments sont représentées par des rectangles verticaux portés par une ligne de vie • Les relations entre acteurs sont des messages représentés par des flèches.

o Un trait en pointillé représente une réponse du receveur à l’émetteur du message précédent o Une flèche pleine représente un message synchrone : l’émetteur attend une réponse du récepteur

avant de pouvoir avoir une nouvelle activité o Une flèche évidée représente un message asynchrone : aucun retour n’est attendu par l’émetteur

II.6.3. Exemple de diagramme de séquence d’un distributeur de billet

Bibliographie

[1] Anthony MEURDEFROID, CI 4 Commande et comportement des SED , Cours PTSI [2] Patrick Beynet, Christian Collignon, Laurent Deschamps, PTSI Prépas sciences, ELLIPSE [3] Olivier Legallo, Systèmes à évènements discrets, Cours PSI

14

Kholle type (Logique Combinatoire) : Etude d’un feu de carrefour Soit une intersection entre une route principale 1 et une route secondaire. Des capteurs de présence de voitures sont placés le long des voies : a et b pour la route principale, c et d pour la route

secondaire. Les sorties de ces capteurs sont à 1 en présence de voitures. Un feu est à 1 lorsqu’il est vert Le cahier des charges fonctionnel partiel donne :

• le feu F1 est vert quand il y a des voitures en a et b en même temps • le feu F1 est vert quand simultanément il y a des voitures en a ou b et qu'il n'y en a pas en c ou pas en d • le feu F2 est vert quand il y a des voitures en c et d et qu’il n’y en a pas en a et en b • le feu F2 est vert quand il y a des voitures en c ou d et qu’il n’y en a ni en a ni en b • le feu F1 est vert quand il n’y a pas de voiture du tout

Question 1. Déterminer l'expression de F1 et de F2 en sommant les conditions logiques exprimées dans les 5

points du cahier des charges.

Question 2. Compléter les tableaux de Karnaugh de F1 et F2.

Question 3. Simplifier les expressions de F1 et F2 par les tableaux de Karnaugh.

Question 4. Tracer le logigramme de F1 et F2 correspondant aux expressions obtenues.

F1F2

F2F1

a

bc

d

route principale

Conditions extérieuresSol

Feu de carrefour

FS1

FS1 : faire évoluer les voitures conformément à la circulation routièreFS2 : s'adapter au solFS3 : résister au conditions extérieures

FS3FS2

Circulation routière Voitures

Fonction Critère Niveau

FS1... ...

Règles d'utilisation Voir cdcf... ...