Logique combinatoire et séquentielle

  • ECTS

    4 crédits

  • Composante

    Collège Sciences et Technologies pour l’Energie et l’Environnement (STEE)

  • Volume horaire

    39h

Description

De nombreux problèmes de décision sont issus du monde du Tout ou Rien : faire par exemple tourner un moteur ou pas, en fonction de conditions vraies ou fausses. On décline dans ce cours une méthodologie, permettant de concevoir le système de décision selon qu’il est combinatoire (les sorties ne dépendent que des entrées) ou séquentiel, lorsque les sorties dépendent des entrées, et du temps, au travers du passé du système (automates à espace fini d’états). L’algèbre de Boole est l’outil mathématique fondamental. L’électronique numérique permet de concevoir ces systèmes.

Partie Logique Combinatoire : Sur la base d’exemples simples liés à des schémas électriques comportant des interrupteurs ouverts ou fermés, on réfléchit comment répondre à des énoncés de plus en plus complexes, permettant d’assembler ces interrupteurs. On se rend compte rapidement de la nécessité d’une algèbre, permettant de représenter des énoncés pouvant être Vrai ou Faux par des variables, et d’effectuer des calculs sur ces variables, à partir des opérations élémentaires de l’algèbre de Boole. Ces axiomes, dans le monde des interrupteurs sont naturellement vérifiés, il n’est pas nécessaire ainsi de vérifier physiquement tous les théorèmes déduits de cette algèbre. L’intérêt est grand : on peut manipuler des équations, mettre en forme à l’aide des théorèmes, puis, lorsque l’étude est faite, mettre en place le montage élaboré. En parallèle, l’électronique a permis de fabriquer des interrupteurs pilotés électroniquement (les transistors). Assemblés astucieusement, ils ont permis de fabriquer les briques élémentaires nécessaires au 3 opérations de l’algèbre de Boole. On passe ainsi de montages dangereux éventuellement pilotés à la main, à des montages, où l’on distingue un pupitre (permettant les relations avec un opérateur), une partie commande (fabriquée à partir de composants élémentaires de l’électronique numérique) répondant à un cahier des charges, à la partie opérative (chargée des courants forts, isolée de la partie commande par un organe type transistor de puissance).

 1 - Algèbre de Boole et électronique numérique sont présentées en parallèle.

Des axiomes, aux théorèmes (démontrés en TD) essentiels : idempotence, éléments invariants, absorption, résolution de système d’équation, et définition du complément, complément du complément, théorème général de Shannon, de complémentation d’une fonction de variables (sans démonstration), et le théorème essentiel (dû à Shannon) : forme canonique d’écriture d’une fonction de variables, à l’aide de fonctions indicatrices.

2 - Méthodologie pour résoudre un problème de logique combinatoire : ce chapitre est réalisé sur la base d’un cahier des charges « fil conducteur ». On fait toujours de l’algèbre de Boole pour adapter la conception d’un problème à un type de composant, à une structure particulière. Le parallèle est fait systématiquement. Des schémas fonctionnels sont systématiquement réalisés.

  • Table de vérité – Mémoire : identification et algébrisation des entrées et sortie(s) du problème. Mise en table du cahier des charges. Le parallèle est fait avec un composant mémoire accueillant en entrées d’adresses les entrées, la sortie étant disponible en sortie de données de la mémoire. Taille de la mémoire nécessaire, en fonction du nombre d’entrées, et du nombre de sorties. Simulations avec outil libre : DigSim. Exercices où plusieurs composants mémoires non extensibles, sont mis en parallèle si trop d’entrées.
  • Les fonctions indicatrices ou mintermes – Décodeur à sorties actives à l’état haut : elles sont ajoutées à la table de vérité. Expression simplifiée canonique de la sortie comme somme des indicatrices (expression 1). Présentation et simulation d’un schéma canonique utilisant un décodeur, et une porte OU (à rapprocher de la lecture de la table par les 1).
  • Expression générale canonique de la sortie sous la forme somme des indicatrices (expression 2) – Multiplexeur : la somme précédente est étendue à toutes les indicatrices. C’est l’expansion de Shannon. Cette écriture capitale est mise en place grâce à un multiplexeur. Schéma et simulation.
  • Parallèle en informatique avec des structures d’affectation ou conditionnelles (IF, ELSE, END)
  • Expression générale canonique de la sortie sous la forme produit des indicatrices complémentées (expression 3) : cette expression est issue de la précédente inversée une première fois par le raisonnement, puis une deuxième fois par le théorème d’inversion généralisé (dû à Shannon).
  • Simplification pour obtention de la forme simplifiée canonique, somme des maxtermes (expression 4) – décodeur à sorties actives à l’état bas : Schéma et simulation utilisant un décodeur à sorties actives à l’état bas, et une porte ET (à rapprocher de la lecture de la table par les 0).
  • Sur la base de ces écritures canoniques, on peut procéder à des modifications ou simplifications pour minimiser le nombre de composants, pour utiliser un certain type de composants.
  • Recherche de formulations en pré classant les variables d’entrées par leur aspect prioritaire
  • Comment on passe simplement de manière méthodique de logique positive à une logique négative.
  • Notion de temps nécessaire pour effectuer un calcul, en électronique numérique (de manière générale) – causalité

Partie Logique Séquentielle : Sur la base d’exemples simples notamment décrits par des chronogrammes, on met en échec la méthodologie de la logique combinatoire : prendre une décision sur une sortie ne dépend pas seulement des entrées, mais aussi d’autres informations, liées au passé du système. La méthodologie adoptée dans ce cours permet la construction rigoureuse du système séquentiel (automate à espace fini d’états).

  • Identification des entrées et sorties
  • Transcription en un graphe du cahier des charges : chaque nœud du graphe correspond à un état stable du système qu’il atteint, suite à un changement d’entrée.
  • Notion d’état présent stable, tant qu’un jeu d’entrées perdure, et d’état futur atteint dès qu’une entrée est modifiée : la prise de décision sur les sorties dépend non seulement des entrées, mais aussi de l’état dans lequel est le système. Le système est séquentiel.
  • Schéma fonctionnel : entrées exogènes, entrées endogènes, état du système, « Bloc calcul de l’état futur », « Bloc calcul des sorties », bouclage de l’état, sorties. Le bouclage de l’état permet sa mémorisation.
  • Tous les blocs deviennent alors combinatoires : toute la démarche du chapitre précédent peut alors être appliquée à chacun pour sa conception.
  • Application à des exemples : codage des états, synthèse de chacun des blocs de calculs, combinatoires, schémas fonctionnels, équations logiques, schémas électroniques, simulations sous DigSim.
  • Passage de l’asynchrone au synchrone : on explique pourquoi une prise de décision, au fil de l’eau, asynchrone, peut s’avérer problématique, pour des raisons technologiques. Présentation de l’intérêt de synchroniser les calculs sur une cadence (choix de la cadence) – Horloge du système. On présente toutefois les inconvénients.
  • Présentation des bascules D permettant de faire vivre ces schémas fonctionnels : ces mémoires permettent de garantir le stockage de l’état entre 2 front d’horloge. La mémoire est au cœur des systèmes séquentiels.
Lire plus

Objectifs

À la fin de cette UE, vous serez capable de :

 

  • Algébriser un problème, identifier les entrées et les sorties. Schéma fonctionnel
  • Jongler entre table de vérité, et les 4 expressions canoniques d’une fonction de logique
  • Adapter grâce à l’algèbre de Boole ces expressions, en fonction des composants d’électronique numérique disponibles
  • Distinguer les systèmes combinatoires des systèmes séquentiels
  • Dessiner un graphe d’états traduisant un cahier des charges du domaine séquentiel
  • Mettre en place le schéma fonctionnel d’un système séquentiel tournant autour de 3 blocs : « mémoire de l’état », « Calcul de l’état futur », « Calcul des sorties ».
Lire plus

Heures d'enseignement

  • Logique combinatoire et séquentielle - CMCours Magistral15h
  • Logique combinatoire et séquentielle - TDTravaux Dirigés12h
  • Logique combinatoire et séquentielle - TPTravaux Pratique12h

Contrôle des connaissances

Évaluation Continue Intégrale 100%

Lire plus

Informations complémentaires

Ressources pédagogiques :

  • Cours disponibles sur Elearn : documents de cours (pdf), enregistrements de cours en vidéo, document de TD/TP (docx), fichiers de travail avec DigSim (txt). Annales de contrôle, sitographie
Lire plus

Compétences visées

Bloc 2             

C2.3 Collecter, stocker, transformer les données

Débutant

C2.4 Analyser les données et produire de l'information

Débutant

C2.5 Découvrir, représenter et exploiter des connaissances

Débutant

Bloc 5 

C5.2 Formuler et modéliser des problèmes de systèmes complexes

Débutant

Lire plus

Bibliographie

  • Logique combinatoire et composants numériques, M. SBAÏ, Ellipses, 2013, Logique combinatoire et séquentielle, C. BRIE, Ellipses, 2003.
Lire plus