Conditions « don't care » dans les tables de Karnaugh

En bref : une condition « don’t care » autorise le choix de la valeur de sortie lorsque le contrat du système ne l’impose pas. Dans une K-map, incluez les cases X uniquement si elles agrandissent un groupe utile ; ne couvrez jamais un zéro requis en SOP ni un un requis en POS. L’optimisation n’est valide que si l’hypothèse concernant l’ensemble de cas utiles est vraie au point d’utilisation. Un X de HDL, une valeur inconnue en simulation et une condition « don’t care » de synthèse ne sont pas automatiquement la même chose.

La minimisation logique préserve normalement une fonction pour chaque entrée possible. Les conditions « don’t care » assouplissent cette exigence : certains cas d’entrée/sortie sélectionnés peuvent recevoir 0 ou 1, ce qui permet d’obtenir une implémentation plus petite pour les cas qui comptent réellement.

Cette liberté peut supprimer des littéraux et des portes. Elle peut aussi supprimer la récupération après une réinitialisation, faire apparaître un motif d’affichage invalide ou créer un écart entre simulation et silicium si son hypothèse est fausse. Une conception professionnelle consigne ensemble trois éléments :

1. l’ensemble ON requis, où la sortie doit valoir 1 ;
2. l’ensemble OFF requis, où la sortie doit valoir 0 ;
3. l’ensemble « don’t care », où l’un ou l’autre résultat respecte le contrat du système.

Deux raisons pour lesquelles une sortie peut être non contrainte

1. L’entrée est inatteignable

L’environnement garantit qu’un vecteur d’entrée donné ne peut pas atteindre cette logique à un instant d’observation pertinent.

Un chiffre BCD valide appartient à l’ensemble 0–9 ; les valeurs 10–15 peuvent donc être inatteignables si :

• la source produit toujours un BCD valide ;
• la réinitialisation et la mise sous tension ne peuvent pas exposer une autre valeur ;
• les transitions intermédiaires ne sont pas échantillonnées comme des chiffres ;
• les défauts qui corrompent le code sont hors du modèle de défauts exigé par la conception.

« L’algorithme ne demande jamais 12 » ne suffit pas si un bus de quatre bits peut brièvement prendre la valeur 1100 en passant d’une valeur enregistrée valide à une autre.

2. L’entrée peut survenir, mais cette sortie n’est pas observée

Une étape de pipeline peut transporter des données arbitraires lorsque valid=0. Si chaque consommateur valide ces données avec ce même état valid, la sortie de données est sans importance pendant les cycles invalides.

Il s’agit d’une condition d’observabilité, et non d’une entrée inatteignable. Elle reste sûre tant qu’aucun consommateur n’enregistre, ne compare, ne transmet ni n’utilise autrement le champ réputé sans importance.

Ces deux cas deviennent des cases X dans un problème de minimisation à deux valeurs. Leurs preuves sont différentes ; il faut donc conserver la raison dans la spécification.

X ne signifie pas une seule chose universelle

Le symbole X est surchargé :

• sur une K-map, X signifie que « l’implémentation peut choisir 0 ou 1 » ;
• dans une simulation HDL à quatre états, X signifie souvent « inconnu, contradictoire ou non initialisé » ;
• dans un document de table de vérité, X peut signifier que la valeur d’entrée est sans importance pour cette ligne ;
• dans une directive de synthèse, une construction propre à l’outil peut autoriser une optimisation.

Ces significations ne sont pas interchangeables.

Attribuer 'x dans du RTL peut améliorer l’optimisation dans certains flux, propager des inconnues en simulation, être ignoré ou transformé dans un autre flux et masquer un véritable défaut d’initialisation. Une affectation combinatoire incomplète peut inférer un verrou plutôt qu’une condition « don’t care ». Des directives d’outil comme full_case peuvent également faire diverger le comportement synthétisé de la simulation ; la documentation d’Intel met explicitement en garde contre cette possibilité.

Exprimez l’intention d’une manière prise en charge par le langage cible, le simulateur, l’outil de synthèse, les règles de lint et le flux formel. Vérifiez ensuite le résultat synthétisé avec les mêmes hypothèses environnementales.

Règles des K-maps

Pour une somme de produits minimisée :

1. Représentez chaque case par 0 requis, 1 requis ou X.
2. Formez des rectangles de taille puissance de deux qui ne contiennent que des 1 et des X.
3. Couvrez chaque 1 requis.
4. N’incluez jamais un 0 requis.
5. Laissez une case X inutilisée lorsqu’elle n’améliore pas la couverture.
6. Choisissez une couverture selon l’objectif de coût réel : littéraux, cellules, profondeur, termes partagés ou autre métrique d’implémentation.

Pour un produit de sommes, appliquez le dual :

• regroupez les 0 requis avec les X facultatifs ;
• couvrez chaque 0 requis ;
• n’incluez jamais un 1 requis.

Chaque sortie peut utiliser un X différemment. Une fonction de segment peut choisir une case BCD invalide donnée comme 1, tandis qu’une autre la choisit comme 0. Rien n’impose d’attribuer un motif invalide global, sauf si la spécification de l’interface l’exige.

Exemple détaillé : un chiffre BCD valide vaut au moins 5

Soit A le bit de poids fort du BCD et D le bit de poids faible. Le comportement requis est :

• F=0 pour les chiffres 0–4 ;
• F=1 pour les chiffres 5–9 ;
• X pour les codes 10–15.

En utilisant l’ordre des lignes et des colonnes en code Gray :

              CD
           00  01  11  10
AB = 00     0   0   0   0
AB = 01     0   1   1   1
AB = 11     X   X   X   X
AB = 10     1   1   X   X

Les cases X permettent de former trois groupes utiles :

• les deux lignes où A=1 forment un octet, ce qui donne A ;
• 0110, 0111, 1110 et 1111 donnent BC ;
• 0101, 0111, 1101 et 1111 donnent BD.

Par conséquent :

ou, sous forme factorisée :

Vérifions l’ensemble de cas utiles :

• les chiffres 0–4 produisent 0 ;
• les chiffres 5–7 satisfont $B(C+D)$ ;
• les chiffres 8–9 satisfont A.

L’expression produit par hasard 1 pour chaque code invalide 10–15. C’est acceptable uniquement parce que ces lignes étaient explicitement non contraintes.

Si les codes invalides doivent produire 0

Ils ne sont alors plus des conditions « don’t care ». Une SOP valide avec F=0 pour 10–15 est :

Cette version conserve le zéro requis sur les codes invalides. Elle est plus grande, car le contrat de l’interface est plus strict.

Un cas où les conditions « don’t care » n’aident pas

Pour un chiffre BCD valide, « est pair » vaut :

Le bit de poids faible encode déjà la parité. Autoriser les codes 10–15 comme X ne peut pas supprimer l’unique littéral sans modifier les valeurs requises ; le minimum reste donc identique.

Les conditions « don’t care » élargissent l’espace d’optimisation ; elles ne garantissent pas une amélioration.

Un cas où un littéral disparaît

Définissons F=1 pour les chiffres BCD valides 8 et 9, et F=0 pour les chiffres valides 0–7.

Si les codes invalides 10–15 doivent eux aussi produire zéro :

Seuls 1000 et 1001 satisfont l’expression.

Si 10–15 sont des conditions « don’t care », les 1 requis peuvent être regroupés avec les six cases X :

Les deux implémentations concordent sur les BCD valides. Elles divergent volontairement sur certaines entrées invalides.

Cette comparaison correcte est importante : une conception ne peut pas prétendre « sans conditions don’t care » tout en utilisant discrètement des cases invalides pour agrandir un groupe.

Entrées transitoires et frontières d’échantillonnage

Même si les registres source et destination contiennent des codes valides, les bits combinatoires ne commutent pas simultanément. Une transition du BCD 7 (0111) vers 8 (1000) modifie quatre bits et peut traverser d’autres combinaisons électriques.

L’importance de ce phénomène dépend de la frontière :

• un registre de destination qui n’échantillonne qu’après stabilisation du décodeur peut ne jamais capturer le résultat intermédiaire ;
• une autorisation de sortie asynchrone, un strobe d’écriture ou une horloge dérivée de la logique minimisée peut réagir à un transitoire ;
• un afficheur multiplexé peut montrer brièvement un motif fantôme ;
• un analyseur logique peut révéler des valeurs que le logiciel n’observe jamais.

La preuve de l’ensemble inatteignable doit donc préciser quand la sortie importe, et pas seulement quelles valeurs stables le logiciel prévoit.

L’enregistrement des entrées ou des sorties, la contrainte temporelle, la conception de commandes sans aléa ou l’ajout d’un masquage peuvent rendre l’hypothèse vraie. Déclarer X sur une K-map ne le fait pas.

États invalides dans les machines à états

Supposons que cinq états soient codés sur trois bits. Trois codes ne sont pas utilisés en fonctionnement normal. Optimiser la logique d’état suivant et de sortie en traitant ces codes comme des conditions « don’t care » peut être raisonnable si la réinitialisation est garantie et si la corruption d’état est hors périmètre.

Si une perturbation d’événement unique, une erreur CDC, une réinitialisation partielle ou l’injection de défauts est prise en compte, ces codes ne sont pas sans importance. La conception peut devoir :

• détecter un état illégal ;
• inhiber immédiatement les sorties dangereuses ;
• revenir à la réinitialisation ou à un autre état sûr ;
• signaler le défaut ;
• utiliser un codage avec une distance de Hamming imposée.

Les outils FPGA proposent des mécanismes explicites d’état sûr. Par exemple, FSM_SAFE_STATE d’AMD Vivado ajoute une logique de détection et de récupération des états invalides, avec un compromis surface/performances. La documentation Intel Quartus distingue elle aussi la synthèse ordinaire des options de machine à états sûre.

N’optimisez pas les états illégaux pour ensuite revendiquer une récupération garantie après ces mêmes états. Ce sont deux spécifications différentes.

Entrées one-hot et entrées prioritaires

Une interface exactement one-hot à $n$ bits possède n vecteurs légaux et $2^n-n$ autres vecteurs. Le vecteur nul est également légal si le protocole est one-hot-ou-zéro.

Un encodeur simple peut traiter plusieurs bits activés comme des conditions « don’t care » si la logique amont garantit une entrée exactement one-hot. Un encodeur prioritaire définit volontairement les lignes à plusieurs bits actifs et ne peut donc pas les considérer comme non contraintes. Il peut néanmoins définir le code comme sans importance lorsqu’aucune requête n’est active, à condition qu’une sortie valide qualifie le code.

Cette distinction explique pourquoi il faut documenter les hypothèses d’entrée aux frontières des modules plutôt que les déduire d’un nom tel que « encodeur ».

Données sans importance en sortie

Considérons :

valid = 0
data  = anything

Il est sûr de minimiser la logique aval dépendante des données uniquement lorsque chaque effet observable est conditionné :

write_enable = valid AND condition(data)

Même dans ce cas, la commutation physique de condition(data) peut consommer de l’énergie, créer une fuite latérale ou affecter le timing. « Fonctionnellement non observé » ne signifie pas nécessairement « électriquement sans importance ».

Pour clarifier la simulation, de nombreuses équipes attribuent tout de même une valeur déterministe aux données invalides et laissent la synthèse optimiser au moyen de contraintes explicites ou des signaux d’activation environnants. Le meilleur choix dépend du flux de vérification et d’implémentation.

Conseils HDL

Évitez de traduire directement la notation des K-maps en affectations X HDL improvisées.

Un schéma combinatoire prudent définit chaque sortie :

always_comb begin
  valid = (bcd <= 4'd9);
  ge_five = 1'b0;
  if (valid)
    ge_five = (bcd >= 4'd5);
end

Cela spécifie le comportement des entrées invalides comme étant zéro. Si le projet veut que les entrées invalides soient des conditions « don’t care » de synthèse, encodez cette intention avec un mécanisme relu et pris en charge par l’outil, accompagné d’une hypothèse. Il peut s’agir, par exemple, de contraintes d’entrée formelles, d’attributs de synthèse, d’interfaces de modules contraintes ou d’une primitive propre à la technologie.

Quelle que soit la méthode choisie :

• faites un lint des affectations incomplètes et des verrous involontaires ;
• comparez le comportement RTL et porte-à-porte lorsque le flux l’exige ;
• prouvez l’équivalence sur l’ensemble de cas utiles ;
• vérifiez que les hypothèses environnementales sont respectées ;
• examinez les avertissements sur les états inatteignables et la couverture des cas ;
• évitez casex ou les correspondances génériques qui peuvent masquer des bits de commande inconnus, sauf si ce comportement est spécifiquement voulu.

Plan de vérification

Une optimisation avec conditions « don’t care » nécessite deux contrôles complémentaires.

Équivalence fonctionnelle sur l’ensemble de cas utiles

Pour chaque entrée requise :

Avec quatre variables, énumérez la table de vérité complète. Pour une logique plus grande, utilisez des assertions ou une équivalence formelle avec une contrainte explicite sur l’ensemble de cas utiles.

Validation de l’hypothèse

Prouvez ou testez que :

• les codages invalides ne peuvent pas être échantillonnés lorsque la sortie importe ;
• la réinitialisation et la mise sous tension respectent l’hypothèse ;
• les chemins CDC ne peuvent pas créer de combinaisons non prises en charge ;
• les exigences de tolérance aux défauts n’incluent pas l’ensemble « inatteignable » ;
• la validation aval couvre chaque effet secondaire ;
• les modes de test et de débogage ne contournent pas le qualificatif.

Tester uniquement l’équation booléenne minimisée ne vérifie que la moitié incorrecte du contrat si c’est l’environnement qui rend X légal.

Construire l’exemple BCD dans DigiSim

Construisez deux détecteurs digit ≥ 5 :

1. Version à invalides définis : implémentez $F=\overline A BC+\overline A BD+A\overline B\overline C$.
2. Version optimisée avec conditions « don’t care » : implémentez $F=A+BC+BD$.
3. Balayez les seize entrées.
4. Confirmez que les deux versions correspondent pour 0–9.
5. Notez leurs différences intentionnelles pour 10–15.
6. Ajoutez valid = NOT(A AND (B OR C)) pour le BCD 0–9 et conditionnez une sortie observable.
7. Modifiez plusieurs bits d’entrée simultanément et vérifiez si le simulateur modélise les transitions intermédiaires ; ne déduisez pas un comportement analogique d’aléa s’il utilise des mises à jour idéales simultanées.

L’exercice montre le compromis réel : une logique plus petite en échange d’une promesse comportementale plus étroite.

Liste de contrôle pour la revue

Avant de marquer une case X, demandez-vous :

• pourquoi cette sortie est-elle non contrainte : entrée inatteignable ou sortie non observée ?
• à quelle frontière d’échantillonnage ou d’observation cette affirmation est-elle vraie ?
• la réinitialisation, le CDC, le mode de test ou le comportement en cas de défaut la contredisent-ils ?
• X est-il une permission de K-map, une inconnue HDL ou une directive d’outil ?
• les états illégaux doivent-ils récupérer ?
• l’implémentation optimisée est-elle vérifiée pour chaque entrée de l’ensemble de cas utiles ?
• l’hypothèse elle-même est-elle affirmée ou prouvée ?

Les conditions « don’t care » ne sont pas des « portes gratuites ». Elles échangent un comportement hors d’un ensemble de cas utiles défini contre une liberté d’implémentation. Lorsque cet ensemble est explicite et vérifié, il s’agit d’une optimisation rigoureuse. Lorsqu’il est seulement supposé, il devient une fonctionnalité cachée.

Poursuivez avec les fondamentaux du BCD pour le contrat de codage, le décodage BCD vers sept segments pour une application à sept sorties, et les aléas statiques et dynamiques pour le comportement pendant les transitions.

Références

• Synthèse AMD Vivado : FSM_SAFE_STATE
• Directives HDL des machines à états Intel Quartus
• Attribut de synthèse full_case Intel Quartus et avertissement d’écart avec la simulation