Niveau conseillé : Bac+1 / Bac+2 — Cycle préparatoire, BTS, BUT, Licence

Présentation du chapitre

Une même fonction logique peut être représentée par plusieurs expressions équivalentes. Certaines utilisent un grand nombre de termes, de littéraux et de portes, alors que d’autres décrivent exactement la même table de vérité avec une structure beaucoup plus courte. La simplification consiste à rechercher une représentation équivalente qui minimise les ressources nécessaires à la réalisation du circuit.

Deux approches complémentaires sont étudiées. La simplification algébrique s’appuie sur les lois de Boole et permet des transformations symboliques rapides. Les tableaux de Karnaugh proposent une lecture visuelle des adjacences entre mintermes ou maxtermes. Ils sont particulièrement efficaces pour les fonctions contenant deux, trois ou quatre variables.

La réduction d’une expression ne doit jamais être considérée comme une simple manipulation esthétique. Elle influence directement le nombre de composants, le coût, la consommation énergétique, le temps de propagation, la complexité du câblage et la fiabilité du système. Une solution minimale sur le plan algébrique doit cependant rester compatible avec la technologie utilisée et les contraintes physiques du montage.

Objectifs pédagogiques

Prérequis

• connaître les variables binaires et les opérations NON, ET et OU ;
• maîtriser les lois fondamentales de l’algèbre de Boole ;
• savoir écrire une fonction sous forme canonique somme de produits ou produit de sommes ;
• savoir associer une ligne de table de vérité à un minterme ou à un maxterme ;
• lire et réaliser un circuit utilisant des portes logiques élémentaires.

Conventions et notations

Organisation du chapitre

Figure 1 — Démarche générale de simplification et de validation d’une fonction logique.

6.1. Simplification algébrique

6.1.1. Principe de l’équivalence logique

Deux expressions E₁ et E₂ sont équivalentes lorsqu’elles prennent la même valeur pour toutes les combinaisons possibles de leurs variables. La simplification algébrique remplace progressivement une expression par une autre expression équivalente, en appliquant uniquement des identités booléennes démontrées.

E₁ ≡ E₂ ⇔  E₁ = E₂ pour toutes les combinaisons d’entrées

Le résultat recherché n’est pas toujours unique. Deux expressions différentes peuvent posséder le même nombre de termes et de littéraux. Le choix final dépend alors de critères technologiques : type de portes disponibles, nombre maximal d’entrées par porte, profondeur du circuit ou besoin d’éviter certains aléas temporels.

6.1.2. Lois de Boole mobilisées

6.1.3. Mise en facteur

La mise en facteur est l’opération inverse de la distributivité. Elle consiste à repérer un facteur commun dans plusieurs termes produits. Une seule occurrence de ce facteur est ensuite conservée.

A·B + A·C = A·(B + C)

Exemple : F = A·B + A·¬B. Les deux produits contiennent A. En mettant A en facteur, on obtient F=A(B+¬B). La complémentarité donne B+¬B=1, puis l’élément neutre du produit donne A·1=A.

La distributivité duale permet également de factoriser une expression en produit de sommes : (A+B)(A+C)=A+B·C. Cette identité est très utile lorsque l’on recherche une forme POS.

(A + B)·(A + C) = A + B·C

6.1.4. Élimination d’une variable complémentée

Lorsqu’une expression contient deux termes identiques à l’exception d’une variable présente une fois sous forme directe et une fois sous forme complémentée, cette variable peut disparaître.

X·Y + X·¬Y = X

Cette règle signifie que, si X=1, la sortie vaut 1 quelle que soit la valeur de Y. Les deux termes couvrent ensemble les deux possibilités Y=0 et Y=1.

6.1.5. Élimination des termes redondants

Un terme est redondant lorsqu’il n’ajoute aucune combinaison d’entrées à celles déjà couvertes par un terme plus général. Dans A+A·B, le terme A couvre tous les cas où A=1, y compris ceux où A=1 et B=1. Le produit A·B n’apporte donc aucune information supplémentaire.

A + A·B = A

A·(A + B) = A

La première identité est l’absorption en forme somme de produits. La seconde est son dual en forme produit de sommes.

6.1.6. Théorème d’absorption et variantes

La variante A+¬A·B=A+B est particulièrement utile. Elle permet de supprimer le complément ¬A dans le produit sans développer toute la table de vérité.

6.1.7. Théorème du consensus

Le théorème du consensus identifie un terme redondant construit à partir des parties communes de deux autres termes. Dans l’expression A·B + ¬A·C + B·C, le terme B·C est le consensus des deux premiers termes et peut être supprimé.

A·B + ¬A·C + B·C = A·B + ¬A·C

Lorsque A=1, le terme A·B couvre les situations où B=1. Lorsque A=0, le terme ¬A·C couvre celles où C=1. Si B=C=1, l’un des deux premiers termes vaut donc nécessairement 1, quelle que soit la valeur de A. Le terme B·C n’est jamais indispensable à la valeur logique de la fonction.

6.1.8. Exemple complet n° 1

Simplifier F = A·B + A·¬B + ¬A·B.

La fonction initiale nécessite plusieurs produits et deux compléments. La forme réduite F=A+B se réalise avec une seule porte OU à deux entrées.

6.1.9. Exemple complet n° 2

Simplifier G = (A+B)·(A+¬B).

6.1.10. Exemple complet n° 3 — consensus

Simplifier H = A·B + ¬A·C + B·C.

La forme obtenue contient deux produits de deux littéraux. Une vérification par table de vérité confirme que le terme B·C ne modifie aucune sortie.

6.1.11. Stratégie pratique de simplification algébrique

1. Supprimer les doubles négations et appliquer De Morgan lorsque des compléments portent sur des expressions composées.

2. Réordonner les termes grâce à la commutativité afin de rapprocher les facteurs communs.

3. Chercher une mise en facteur ou deux termes ne différant que par une variable complémentée.

4. Appliquer les lois d’absorption et les identités A+¬A·B=A+B.

5. Rechercher un éventuel terme de consensus.

6. Répéter jusqu’à ce qu’aucune transformation utile n’apparaisse.

7. Vérifier l’équivalence par table de vérité, carte de Karnaugh ou simulation.

6.2. Tableaux de Karnaugh

6.2.1. Définition et objectif

Un tableau de Karnaugh, ou carte de Karnaugh, est une réorganisation géométrique de la table de vérité. Chaque case représente un minterme, donc une combinaison unique des variables d’entrée. Les cases sont disposées de sorte que deux cases adjacentes ne diffèrent que par la valeur d’une seule variable.

Cette propriété permet d’éliminer visuellement la variable qui change. Lorsque deux mintermes adjacents sont regroupés, la variable différente disparaît. Un groupe de quatre cases élimine deux variables, un groupe de huit cases en élimine trois, et ainsi de suite.

Groupe de 2ᵏ cases  ⇒ élimination de k variables

6.2.2. Principe de l’adjacence

Deux cases sont adjacentes lorsqu’elles partagent un côté. Les diagonales ne sont jamais adjacentes. Les bords opposés de la carte sont également voisins : la première et la dernière colonne se touchent, de même que la première et la dernière ligne. Les quatre coins d’une carte à quatre variables forment donc un groupe valide de quatre cases.

Figure 2 — Ordre Gray et adjacence par les bords dans une carte à quatre variables.

6.2.3. Organisation des cases en code Gray

L’ordre binaire naturel 00, 01, 10, 11 ne convient pas, car le passage de 01 à 10 modifie deux bits. Le code Gray place les combinaisons dans l’ordre 00, 01, 11, 10. Entre deux étiquettes successives, un seul bit change.

6.2.4. Règles générales de groupement

• un groupe contient uniquement des 1 pour obtenir une SOP, ou uniquement des 0 pour obtenir une POS ;
• la taille d’un groupe est une puissance de deux : 1, 2, 4, 8 ou 16 cases ;
• la forme du groupe est rectangulaire ;
• les groupes doivent être aussi grands que possible afin d’éliminer le maximum de variables ;
• tous les 1, ou tous les 0 selon la forme recherchée, doivent être couverts au moins une fois ;
• le recouvrement est autorisé lorsqu’il permet d’obtenir des groupes plus grands ou de couvrir une case isolée ;
• les bords opposés sont adjacents ;
• un groupe ne contient jamais une case ayant la valeur opposée ;
• les cas X peuvent être inclus seulement lorsqu’ils améliorent la simplification.

Figure 3 — Groupement de grande taille, adjacence par les bords et recouvrement autorisé.

6.2.5. Tableau de Karnaugh à deux variables

Une fonction de deux variables possède quatre mintermes. La carte peut être organisée sous la forme de deux lignes et deux colonnes. Chaque case possède deux voisins par les côtés, en tenant compte du repliement des bords.

Exemple : F(A,B)=Σm(1,2,3)

Les cases m₂ et m₃ forment un groupe correspondant à A. Les cases m₁ et m₃ forment un groupe correspondant à B. La case m₃ est utilisée dans les deux groupes, ce qui est autorisé.

F = A + B

6.2.6. Tableau de Karnaugh à trois variables

Une fonction de trois variables possède huit cases. Une variable est placée sur les lignes et deux variables sur les colonnes en ordre Gray. Une autre disposition est possible, à condition de respecter l’adjacence.

Exemple : F(A,B,C)=Σm(1,3,6,7)

Le groupe vertical de la colonne BC=11 contient m₃ et m₇ : B=1 et C=1 y restent constants, d’où le terme B·C. Le groupe horizontal de la ligne A=1 couvrant BC=11 et BC=10 contient m₇ et m₆ : A=1 et B=1 restent constants, d’où A·B.

F = B·C + A·B = B(C + A)

6.2.7. Tableau de Karnaugh à quatre variables

Une fonction de quatre variables possède seize cases. Deux variables sont affectées aux lignes et deux aux colonnes. Les deux axes suivent l’ordre Gray 00, 01, 11, 10. La carte à quatre variables permet des groupes de 1, 2, 4, 8 ou 16 cases.

Exemple : F(A,B,C,D)=Σm(0,2,5,7,8,10,13,15)

Les quatre coins forment un groupe : B=0 et D=0 y restent constants, d’où ¬B·¬D. Les quatre cases centrales correspondant aux lignes B=1 et aux colonnes D=1 forment un second groupe, d’où B·D. Les variables A et C disparaissent entièrement.

F = ¬B·¬D + B·D = B XNOR D

6.2.8. Groupements de 1 — forme somme de produits

Pour obtenir une forme SOP, on regroupe les cases contenant 1. Chaque groupe produit un terme ET. Les termes obtenus sont ensuite réunis par une opération OU.

1. Placer les 1 dans la carte à partir de la table de vérité ou de la liste des mintermes.

2. Commencer par les 1 qui ne peuvent appartenir qu’à un seul grand groupe.

3. Former les groupes les plus grands possibles.

4. Pour chaque groupe, conserver les variables constantes : valeur 1 sous forme directe, valeur 0 sous forme complémentée.

5. Additionner logiquement tous les termes produits.

6. Vérifier que chaque 1 est couvert.

6.2.9. Groupements de 0 — forme produit de sommes

Pour obtenir une forme POS, on regroupe les cases contenant 0. Chaque groupe produit un terme somme qui doit valoir 0 sur toutes les cases du groupe. Les termes sommes sont ensuite multipliés.

La règle de polarité est donc inversée par rapport aux groupements de 1. Pour un groupe de 1, une variable constante à 1 apparaît directe. Pour un groupe de 0, une variable constante à 1 apparaît complémentée.

Figure 4 — Passage des groupements de 1 à la SOP et des groupements de 0 à la POS.

6.2.10. Groupements avec recouvrement

Une case peut appartenir à plusieurs groupes. Le recouvrement est utile lorsqu’une case sert de pont entre deux régions ou lorsqu’il permet de créer deux groupes de grande taille au lieu de plusieurs petits groupes. Il ne modifie pas la fonction, car A+A=A.

Le recouvrement n’est cependant pas un objectif en soi. Ajouter un groupe qui ne couvre aucun minterme nouveau et qui n’est pas nécessaire à une solution minimale augmente inutilement le nombre de termes.

6.2.11. Cas indifférents — don’t care

Dans certains systèmes, certaines combinaisons d’entrées ne se produisent jamais ou leur sortie n’a aucune importance. Elles sont notées X, d ou φ. Pendant la simplification, chaque X peut être choisi comme 0 ou comme 1, indépendamment des autres, afin d’agrandir un groupe.

Figure 5 — Utilisation sélective des cas indifférents pour agrandir les groupements.

• en recherche SOP, un X peut être utilisé comme un 1 ;
• en recherche POS, un X peut être utilisé comme un 0 ;
• un X peut être ignoré s’il n’améliore aucun groupe ;
• il est interdit de modifier une case imposée à 0 ou à 1 ;
• la fonction simplifiée n’est contrainte que sur les combinaisons réellement spécifiées.

Exemple : pour F=Σm(1,3,7,11,15)+d(0,2,5), l’utilisation des cas 0 et 2 permet de former un groupe de quatre donnant ¬A·¬B. Un second groupe donne C·D. Une forme possible est donc F=¬A·¬B+C·D.

6.2.12. Erreurs fréquentes dans les cartes de Karnaugh

6.3. Obtention d’une expression simplifiée

6.3.1. Forme somme de produits — SOP

Une forme SOP est obtenue en couvrant tous les 1 de la carte. Chaque groupe correspond à un implicant, c’est-à-dire un produit qui garantit F=1 pour toutes les cases qu’il couvre. La somme logique de ces produits reconstitue la fonction.

1. Identifier les groupes maximaux de 1, en incluant éventuellement des X.

2. Écrire le produit associé à chaque groupe en conservant uniquement les variables constantes.

3. Repérer les groupes indispensables à la couverture de certains 1.

4. Ajouter le minimum de groupes supplémentaires pour couvrir les 1 restants.

5. Écrire la somme des produits et vérifier la couverture.

F = P₁ + P₂ + … + Pₙ

6.3.2. Forme produit de sommes — POS

Une forme POS est obtenue en couvrant tous les 0. Chaque groupe de 0 produit un terme somme qui vaut 0 dans toute la zone couverte. Le produit logique de ces sommes vaut 0 exactement sur les cases spécifiées.

1. Identifier les groupes maximaux de 0, avec les éventuels X.

2. Écrire la somme associée à chaque groupe en inversant la règle de polarité.

3. Sélectionner les groupes essentiels.

4. Compléter la couverture avec le minimum de groupes.

5. Multiplier les termes sommes et vérifier la fonction.

F = S₁ · S₂ · … · Sₙ

6.3.3. Implicant, implicant premier et implicant essentiel

Les implicants premiers essentiels doivent toujours figurer dans la solution. Après leur sélection, les mintermes déjà couverts sont rayés. Il reste ensuite à choisir une combinaison minimale parmi les implicants premiers non essentiels.

6.3.4. Recherche des implicants premiers

1. Repérer d’abord les groupes de 8 ou de 16 cases, puis les groupes de 4, de 2 et enfin les cases isolées.

2. Écarter tout groupe entièrement contenu dans un groupe plus grand : il n’est pas premier.

3. Lister les mintermes couverts par chaque groupe maximal.

4. Identifier les mintermes qui n’apparaissent que dans une seule ligne de la liste.

5. Déclarer essentiels les groupes correspondants.

6.3.5. Tableau de couverture des implicants

Lorsque plusieurs couvertures sont possibles, un tableau de couverture aide à sélectionner les implicants. Les colonnes représentent les mintermes à couvrir et les lignes les implicants premiers. Une marque indique qu’un implicant couvre le minterme.

Dans cet exemple fictif, un minterme apparaissant dans une seule colonne marquée rend l’implicant correspondant essentiel. Lorsque plusieurs choix restent possibles, on privilégie la couverture utilisant le moins d’implicants, puis le moins de littéraux.

6.3.6. Choix d’une solution minimale

Le mot minimal peut désigner plusieurs critères. Une expression ayant le moins de termes n’a pas nécessairement le moins de littéraux, et une expression ayant le moins de littéraux n’utilise pas toujours le moins de boîtiers intégrés dans une technologie donnée.

6.3.7. Solutions minimales multiples

Une carte peut posséder plusieurs couvertures ayant le même nombre de groupes et de littéraux. Ces solutions sont logiquement équivalentes et toutes minimales selon le critère choisi. Il faut alors comparer leur réalisation physique.

• choisir la solution qui réutilise des compléments déjà disponibles ;
• éviter une porte ayant trop d’entrées si le composant n’est pas disponible ;
• favoriser une structure NAND–NAND ou NOR–NOR homogène ;
• réduire le nombre de niveaux entre une entrée critique et la sortie ;
• tenir compte des risques d’aléas et des contraintes de synchronisation.

6.3.8. Exemple complet — SOP et POS

Considérons F(A,B,C,D)=Σm(0,2,5,7,8,10,13,15). La carte fait apparaître deux groupes de quatre. Les quatre coins donnent ¬B·¬D et les quatre cases où B=D=1 donnent B·D.

SOP minimale : F = ¬B·¬D + B·D

En regroupant les 0, on obtient deux groupes correspondant aux sommes (B+¬D) et (¬B+D).

POS minimale : F = (B + ¬D)·(¬B + D)

Les deux formes représentent l’équivalence logique B XNOR D. Le choix entre SOP et POS dépend des portes disponibles. Une structure NAND–NAND favorise la SOP, tandis qu’une structure NOR–NOR favorise la POS.

6.3.9. Exemple avec cas indifférents

Pour F=Σm(1,3,7,11,15)+d(0,2,5), les cas indifférents 0 et 2 peuvent compléter un groupe de quatre couvrant 0,1,2,3. Ce groupe donne ¬A·¬B. Un autre groupe de quatre couvrant 3,7,11,15 donne C·D.

F = ¬A·¬B + C·D

Sans utiliser les X, les mintermes 1 et 3 formeraient un groupe de deux donnant ¬A·¬B·D, plus coûteux. Les cas indifférents réduisent donc le nombre de littéraux tout en respectant les combinaisons imposées.

6.3.10. Vérification de l’expression obtenue

6.4. Intérêt de la simplification

6.4.1. Réduction du nombre de portes

Chaque terme produit d’une SOP exige généralement une porte ET, chaque complément une porte NON et la réunion des termes une porte OU. La diminution du nombre de termes et de littéraux réduit donc directement le nombre de composants et de connexions.

Figure 6 — Comparaison qualitative entre une expression initiale et sa forme simplifiée.

6.4.2. Réduction du coût

Un circuit utilisant moins de portes nécessite moins de boîtiers, moins de surface sur un circuit intégré et moins de pistes de connexion. Dans un prototype à composants discrets, cela réduit le coût d’achat et le temps de câblage. Dans un FPGA ou un ASIC, cela peut réduire le nombre de ressources logiques et la surface de silicium.

Le coût réel dépend toutefois du conditionnement. Remplacer deux portes à deux entrées par une porte à quatre entrées n’est intéressant que si cette porte existe dans la famille logique choisie ou si le boîtier est déjà présent.

6.4.3. Réduction de la consommation

Chaque commutation charge et décharge des capacités internes et externes. Moins de portes et moins de nœuds commutés signifient généralement une consommation dynamique plus faible. La réduction du nombre d’entrées et des connexions diminue également les capacités parasites.

6.4.4. Réduction du temps de propagation

Le signal de sortie d’une porte apparaît après un retard de propagation. Dans une cascade, les retards s’additionnent approximativement le long du chemin critique. Réduire le nombre de niveaux logiques permet donc d’augmenter la fréquence maximale de fonctionnement.

tₚ,total ≈ tₚ,1 + tₚ,2 + … + tₚ,n sur le chemin critique

Une expression plus courte n’implique pas automatiquement une profondeur plus faible. Il faut examiner la structure du circuit, la décomposition des portes ayant un grand nombre d’entrées et l’éventuel équilibrage des chemins.

6.4.5. Amélioration de la fiabilité

Un nombre réduit de composants et de connexions diminue le nombre de points susceptibles de tomber en panne, de provoquer un faux contact ou de capter du bruit. Le diagnostic et la maintenance deviennent également plus simples.

• moins de fils et de soudures ;
• moins de composants soumis au vieillissement ;
• schéma plus lisible et plus facile à tester ;
• réduction des erreurs de câblage ;
• documentation et validation plus simples.

6.4.6. Limites d’une minimisation purement logique

La solution la plus courte sur le papier n’est pas toujours la meilleure solution industrielle. Une redondance peut être utile pour éliminer un aléa, faciliter le test, respecter une architecture modulaire ou réutiliser des signaux déjà disponibles.

6.5. Travaux dirigés

Les travaux dirigés suivants suivent une progression : simplification algébrique, cartes à deux et trois variables, cartes à quatre variables, réalisation NAND et comparaison technologique. Pour chaque question, la justification des groupements ou des lois utilisées est obligatoire.

TD 1 — Simplification algébrique

Simplifier les expressions suivantes et indiquer la loi utilisée à chaque étape :

• F₁=A·B+A·¬B ;
• F₂=A+A·B+A·B·C ;
• F₃=A·B+¬A·B ;
• F₄=(A+B)(A+¬B) ;
• F₅=A+¬A·B ;
• F₆=A·B+¬A·C+B·C ;
• F₇=(A+B+C)(A+B+¬C) ;
• F₈=A·¬B·C+A·B·C+¬A·B·C.

TD 2 — Fonctions à deux variables

Pour chaque fonction, construire la carte, former les groupements et donner la SOP minimale puis, lorsque cela est pertinent, la POS minimale :

TD 3 — Fonctions à trois variables

Simplifier à l’aide d’une carte de Karnaugh :

TD 4 — Fonctions à quatre variables

Pour chaque fonction, remplir la carte 4×4, déterminer les implicants premiers, identifier les implicants essentiels et proposer une expression minimale :

TD 5 — Réalisation avec des portes NAND

Une structure NAND–NAND réalise naturellement une somme de produits. Pour une fonction F=P₁+P₂+…+Pₙ, chaque produit est d’abord inversé par une porte NAND. Une dernière NAND applique De Morgan et restitue la somme.

F = P₁ + P₂ = ¬(¬P₁ · ¬P₂)

1. Simplifier F(A,B,C)=Σm(1,2,3,5,7) sous forme SOP.

2. Tracer la réalisation avec des portes ET, OU et NON.

3. Transformer cette réalisation en structure NAND–NAND.

4. Réaliser les compléments nécessaires avec une NAND dont les entrées sont reliées ensemble.

5. Comparer le nombre de boîtiers si seules des NAND à deux entrées sont disponibles.

TD 6 — Comparaison d’un circuit initial et d’un circuit simplifié

On considère F=A·B+A·¬B+¬A·B.

1. Dessiner le circuit correspondant directement à l’expression initiale.

2. Simplifier l’expression par l’algèbre de Boole.

3. Dessiner le circuit simplifié.

4. Compter les inverseurs, portes ET, portes OU, connexions d’entrée et niveaux logiques.

5. En supposant un retard de 8 ns par inverseur, 12 ns par porte ET et 15 ns par porte OU, estimer le retard maximal des deux réalisations.

6. Discuter le coût, la consommation et la fiabilité.

6.6. Activité pratique de simulation

Objectif

Valider expérimentalement l’équivalence entre une fonction initiale et sa forme simplifiée, puis observer l’effet du nombre de niveaux logiques sur le retard de propagation à l’aide de Logisim Evolution, Proteus, Multisim ou d’un logiciel équivalent.

Matériel et ressources

• ordinateur équipé d’un simulateur logique ;
• portes NON, ET, OU et NAND ;
• interrupteurs logiques pour les entrées ;
• LED ou sondes pour les sorties ;
• générateur d’impulsions pour l’étude temporelle.

Manipulation proposée

1. Réaliser le circuit initial F=A·B+A·¬B+¬A·B.

2. Réaliser en parallèle le circuit simplifié F=A+B.

3. Relier les mêmes interrupteurs A et B aux deux circuits.

4. Ajouter une porte XOR entre leurs sorties : sa sortie doit rester à 0 pour toutes les combinaisons.

5. Compléter un tableau de vérité expérimental.

6. Attribuer des retards aux portes et appliquer des transitions proches dans le temps.

7. Observer les éventuelles impulsions transitoires du circuit initial.

8. Réaliser ensuite F=A·B+¬A·C avec et sans le terme de consensus B·C et comparer les aléas.

Compte rendu attendu

6.7. Synthèse du chapitre

6.8. Glossaire

6.9. Exercices d’entraînement

Exercice 1 — Application directe des lois

Simplifier : a) A+0 ; b) A·1 ; c) A+A·B ; d) A·(A+B) ; e) A+¬A·B ; f) A·¬A+A·B.

Exercice 2 — Factorisation

Simplifier F=A·B·C+A·B·¬C+A·¬B·C. Indiquer le nombre de littéraux avant et après simplification.

Exercice 3 — Consensus

Montrer que F=A·B+¬A·C+B·C est équivalente à A·B+¬A·C. Vérifier le résultat pour A=0 et A=1.

Exercice 4 — Karnaugh à deux variables

Construire la carte de F(A,B)=Σm(0,1,3), former les groupes et donner la SOP minimale.

Exercice 5 — Karnaugh à trois variables

Simplifier F(A,B,C)=Σm(0,2,4,6). Quelle variable n’influence pas la sortie ?

Exercice 6 — Recouvrement

Simplifier F(A,B,C)=Σm(0,1,2,3,7). Montrer pourquoi la case m₃ peut appartenir à deux groupes.

Exercice 7 — Karnaugh à quatre variables

Simplifier F(A,B,C,D)=Σm(1,3,4,5,7,9,11,12,13,15). Donner une SOP minimale et une POS minimale.

Exercice 8 — Cas indifférents

Simplifier F(A,B,C,D)=Σm(1,3,7,11,15)+d(0,2,5). Comparer le résultat avec celui obtenu sans utiliser les X.

Exercice 9 — Réalisation NAND

Réaliser F=A·B+¬A·C uniquement avec des portes NAND à deux entrées. Préciser comment obtenir ¬A.

Exercice 10 — Comparaison technologique

Comparer les réalisations de F=A·B+A·¬B+¬A·B et de F=A+B selon les critères suivants : nombre de portes, littéraux, niveaux, délai, coût et fiabilité.

6.10. Auto-évaluation

6.11. Corrigés des exercices

Corrigé de l’exercice 1

Corrigé de l’exercice 2

F=A·B(C+¬C)+A·¬B·C=A·B+A·¬B·C=A(B+¬B·C)=A(B+C).

L’expression initiale contient 9 littéraux. La forme développée simplifiée A·B+A·C en contient 4 ; la forme factorisée A(B+C) en contient 3 occurrences de variables dans l’écriture structurelle.

Corrigé de l’exercice 3

Si A=1, A·B=B et ¬A·C=0 : le terme B·C est absorbé par B. Si A=0, A·B=0 et ¬A·C=C : le terme B·C est absorbé par C. Il est donc redondant dans les deux cas.

A·B + ¬A·C + B·C = A·B + ¬A·C

Corrigé de l’exercice 4

Les mintermes m₀ et m₁ forment un groupe donnant ¬A. Les mintermes m₁ et m₃ forment un groupe donnant B. La SOP minimale est F=¬A+B.

Corrigé de l’exercice 5

Les mintermes 0,2,4,6 correspondent exactement à toutes les combinaisons où C=0. Les variables A et B parcourent toutes leurs valeurs et disparaissent.

F = ¬C

Corrigé de l’exercice 6

Le groupe m₀,m₁,m₂,m₃ couvre toute la ligne A=0 et donne ¬A. Le groupe m₃,m₇ couvre B=1 et C=1 et donne B·C. La case m₃ appartient aux deux groupes, ce qui est autorisé et nécessaire pour obtenir les groupes maximaux.

F = ¬A + B·C

Corrigé de l’exercice 7

La carte permet de former un groupe de huit correspondant à D=1, puis un groupe de quatre correspondant à B=1 et C=0. Une SOP minimale est F=D+B·¬C.

En groupant les 0, une POS minimale équivalente est F=(B+D)(¬C+D).

Corrigé de l’exercice 8

En utilisant les X 0 et 2, les cases 0,1,2,3 donnent ¬A·¬B. Les cases 3,7,11,15 donnent C·D. Une forme simplifiée est F=¬A·¬B+C·D. Sans les X, le groupe contenant 1 et 3 ne comporte que deux cases et produit le terme ¬A·¬B·D, qui possède un littéral supplémentaire.

Corrigé de l’exercice 9

Produire N₁=¬(A·B) avec une NAND. Produire ¬A=NAND(A,A), puis N₂=¬(¬A·C) avec une NAND. La sortie vaut F=NAND(N₁,N₂), car ¬(¬(A·B)·¬(¬A·C))=A·B+¬A·C.

Corrigé de l’exercice 10

La fonction initiale se simplifie en F=A+B. La réalisation directe nécessite deux inverseurs, trois portes ET et une porte OU, avec plusieurs niveaux et de nombreuses connexions. La réalisation simplifiée nécessite une seule porte OU. Elle est généralement moins coûteuse, moins énergivore, plus rapide et plus fiable. Une vérification temporelle reste nécessaire si le circuit initial ou la transition des entrées peut provoquer des aléas.