7 / 63 · Concept

Algèbre de Boole, transformations équivalentes et coût de réalisation

Transformer des circuits par De Morgan et factorisation, en distinguant équivalence logique et propriétés temporelles.

Des expressions équivalentes donnent la même sortie pour toute entrée

Simplifier un circuit combinatoire ne consiste pas seulement à raccourcir une formule. Il faut préserver sa fonction tout en considérant profondeur logique, nombre d'entrées par porte, charge des sorties et cellules disponibles. En algèbre de Boole^{Algèbre de Boole Algèbre des valeurs 0 et 1 et des opérations AND, OR, NOT. Le signe plus y désigne généralement OR, dont les règles diffèrent de l'addition entière.}, interprétez d'abord $+$ comme OR et le produit comme AND.

A+AB=A,\qquad A+\overline A B=A+B

La deuxième identité se vérifie par cas : si $A=1$ , les deux membres valent 1 ; si $A=0$ , ils valent $B$ . Même après avoir appliqué une identité mémorisée, vous devez pouvoir en expliquer le sens.

Lire les structures NAND et NOR avec De Morgan

\overline{AB}=\overline A+\overline B,\qquad \overline{A+B}=\overline A\,\overline B

Par exemple, $Y=AB+AC=A(B+C)$ . La première forme utilise deux AND et un OR ; la seconde un OR et un AND. Toutefois, selon l'arrivée des entrées et les charges, moins de portes ne signifie pas toujours plus rapide.

Le théorème du consensus est également utile.

AB+\overline A C+BC=AB+\overline A C

Lorsque $BC=1$ , si $A=0$ , $\overline A C$ vaut déjà 1 ; si $A=1$ , $AB$ vaut déjà 1. Le terme $BC$ est donc redondant en régime stable. Sa suppression peut toutefois modifier les aléas pendant les transitions ; nous y reviendrons dans la leçon sur les retards.

Chaque colonne ci-dessous représente une combinaison ABC, pas un instant successif. Vérifiez l'égalité des deux sorties dans toutes les colonnes. Malgré des nombres de portes et des chemins différents, les fonctions coïncident pour des entrées 0/1 stables.

Équivalence de AB + AC et A(B + C)

Voir les données du chronogramme

Données du chronogramme : chaque caractère représente un intervalle ; un point maintient l'état précédent ; p représente un cycle d'horloge.
Signal	Forme d'onde	Valeurs du bus
ABC	`23452345`	000 → 001 → 010 → 011 → 100 → 101 → 110 → 111
AB+AC	`0....1..`
A(B+C)	`0....1..`

Le critère de vérification de l'équivalence

Nommez les versions initiale et optimisée y_ref et y_opt. Lorsque l'espace d'entrée est petit, comparez toutes les entrées. Un ou deux exemples réussis ne prouvent pas l'équivalence.

SystemVerilog
assign y_ref = (a & b) | (a & c);
assign y_opt = a & (b | c);
assign mismatch = y_ref ^ y_opt;

mismatch doit rester à 0 pour les huit combinaisons 0/1. La simulation à quatre états avec X/Z et l'équivalence séquentielle exigent d'autres conditions. Préciser la portée de la preuve est une habitude essentielle en revue de conception.

Essayez vous-même

Simplifiez $F=\overline A B+AB+A\overline B$ et indiquez le nombre de combinaisons d'entrée à vérifier.

Lire l’explication

Les deux premiers termes valent $B(\overline A+A)=B$ , donc $F=B+A\overline B=A+B$ . Deux variables exigent quatre combinaisons. L'équivalence des expressions ne garantit pas des retards de propagation identiques.