Cartes de Karnaugh et conditions des don't-care

Relier la table de vérité au coût de réalisation

La table de vérité^{iTable de vérité Tableau énumérant toutes les combinaisons d'entrée et leur sortie. Les évolutions temporelles s'examinent séparément sur un chronogramme. En savoir plus} définit la fonction ; la minimisation choisit une expression pour la réaliser. Pour trois entrées, numérotons les mintermes par le nombre binaire ABC, avec A de poids fort.

Le minterme 4 correspond à ABC=100. Les lignes non citées 0, 2 et 6 valent 0. Au lieu de conserver cinq produits, regroupons les termes qui ne diffèrent que par un bit.

Une carte de Karnaugh est une table réordonnée

Placez les colonnes BC dans l'ordre 00, 01, 11, 10. Cet ordre de Gray ne change qu'un bit entre colonnes voisines. Les colonnes extrêmes sont également voisines.

Les groupes sont rectangulaires et contiennent $1,2,4,8,\ldots$ cellules. Inclure un 0 modifierait la fonction ; un même 1 peut appartenir à plusieurs groupes.

1. Regroupez les quatre cellules des colonnes C=1. A et B varient sans changer la sortie : il reste C.
2. Sur la ligne A=1, regroupez BC=00 et 01. Seul C varie : il reste $A\overline B$.
3. Le OR de ces groupes couvre tous les 1 et aucun 0.

Comparez définition initiale et expression minimisée sur les huit entrées. Vérifiez séparément que l'expression est plus courte et que la fonction reste identique.

Le schéma traduit les deux groupes en termes : A et B disparaissent du groupe C ; C disparaît du groupe à deux cellules, car ces variables y changent.

Un don't-care est une autorisation d'optimiser sous une hypothèse

Supposons que le contrat système exclue toujours ABC=000. Cette cellule peut devenir X et être utilisée comme 0 ou 1 selon les besoins. Regrouper les quatre cellules B=0 donne :

La nouvelle expression vaut 1 pour ABC=000, contrairement à la table complète initiale. Son équivalence exige donc l'hypothèse ABC≠000. Si 000 peut apparaître pendant l'initialisation ou la récupération d'erreur, cette optimisation peut violer les exigences système.

Minimiser l'expression n'est pas minimiser la puce

Moins de littéraux ne garantit pas les meilleures aire, vitesse et puissance dans une bibliothèque de cellules donnée. Charge, fan-out, portes complexes disponibles, câblage et glitches influencent le résultat. Ici, établissez la fonction et les hypothèses ; évaluez le coût physique par la synthèse et l'analyse temporelle.

Pour aller plus loin : MIT OpenCourseWare — Combinational Logic

Manipulation · Recouvrement et conditions des don't-care

1. Sélectionnez C : A et B varient parmi les quatre cellules, donc seul C reste.
2. Sélectionnez A·¬B : il couvre m4 et m5 ; m5 appartient aussi au groupe C. Le recouvrement est permis, inclure un 0 ne l'est pas.
3. Cliquez deux fois sur m0 : 0 → 1 → X. La spécification devient incomplète avec d(0). Le groupe B=0 s'élargit et donne $C+\overline B$.
4. Cliquez encore pour remettre m0 à 0. L'exigence initiale revient et le grand groupe doit disparaître.

Sélectionner un groupe ne change aucune valeur. L'expression complète couvrant tous les 1 reste en place ; seul le terme examiné est encadré. « Minimal » privilégie ici le nombre de produits, puis les littéraux ; lorsqu'il existe plusieurs solutions, une seule est affichée.