Comparateur numérique expliqué : égalité et magnitude

Déduisez les comparateurs d'égalité et de magnitude, mettez en cascade des blocs 4 bits, distinguez l'ordre signé de l'ordre non signé et vérifiez les sorties supérieur, égal et inférieur.

Denny

7 mai 20268 min de lecture

Chalkboard feature illustration for “Comparateur numérique expliqué : égalité et magnitude”

En bref : l’égalité est un AND de réduction des résultats XNOR bit à bit. La magnitude non signée est décidée par la position de poids fort où A et B diffèrent. La magnitude signée exige une interprétation différente du bit de signe ou des indicateurs de soustraction. Un comparateur n’est correct que lorsque la largeur, le signe, la polarité des sorties et les entrées de cascade sont tous définis.

Un comparateur transforme deux vecteurs de bits en une relation :

A < B, A = B, or A > B

Cela semble sans ambiguïté jusqu’à ce que les mêmes bits soient interprétés différemment. Sur quatre bits, 1000 vaut 8 en non signé, mais -8 en complément à deux. Comparé à 0111, il est supérieur selon l’interprétation non signée et inférieur selon l’interprétation signée.

Ce guide construit d’abord l’égalité, déduit ensuite un réseau de magnitude non signée, puis montre comment la comparaison signée et la mise en cascade des blocs modifient la conception.

Définir le contrat

Pour deux entrées A et B valides de $n$ bits, un comparateur de magnitude à trois sorties produit généralement :

G : A est supérieur à B ;
E : A est égal à B ;
L : A est inférieur à B.

Dans un modèle d’entrée valide à deux valeurs :

G+E+L=1

et deux sorties ne sont jamais à l’état haut ensemble. Cette relation one-hot dépend d’une implémentation complète et de niveaux logiques valides. Une entrée de validation, une interface active à l’état bas, des valeurs inconnues en simulation ou des entrées de cascade mal initialisées peuvent modifier le comportement visible.

L’égalité ne dépend pas du signe : les vecteurs de bits correspondent ou ne correspondent pas. Les relations supérieur et inférieur, elles, en dépendent.

Déduire l’égalité avec XNOR

Pour une position :

E_i=A_i\odot B_i=\overline{A_i\oplus B_i}

$E_i=1$ lorsque les deux bits correspondent. Des mots entiers sont égaux uniquement lorsque toutes les positions correspondent :

E=\bigwedge_{i=0}^{n-1}E_i

Pour quatre bits :

E=(A_3\odot B_3)(A_2\odot B_2)(A_1\odot B_1)(A_0\odot B_0)

Le schéma direct utilise quatre portes XNOR suivies d’un AND de réduction.

Il est tentant d’appeler cela « deux délais de porte quelle que soit la largeur ». Ce n’est vrai que pour un schéma au niveau booléen à fan-in illimité. Les implémentations physiques peuvent construire la réduction en arbre équilibré, la factoriser dans des cellules composées ou la mapper dans des tables de recherche FPGA. Avec des portes AND à deux entrées, la profondeur de réduction croît approximativement comme $\lceil\log_2 n\rceil$ lorsqu’elle est équilibrée.

Magnitude non signée : la différence de poids fort gagne

Pour chaque bit, définissons :

G_i=A_i\overline{B_i}

L_i=\overline{A_i}B_i

E_i=A_i\odot B_i

À la position de poids fort qui diffère, un 1 dans A et un 0 dans B signifie que A est supérieur ; l’inverse signifie que A est inférieur. Les positions de poids faible ne comptent que si toutes les positions supérieures correspondent.

Pour des valeurs non signées sur quatre bits :

\begin{aligned} G={}&G_3 +E_3G_2 +E_3E_2G_1 +E_3E_2E_1G_0 \end{aligned}

\begin{aligned} L={}&L_3 +E_3L_2 +E_3E_2L_1 +E_3E_2E_1L_0 \end{aligned}

E=E_3E_2E_1E_0

Chaque terme G signifie « tous les bits supérieurs sont à égalité et A gagne ici ». Chaque terme L décrit le cas symétrique.

Exemple non signé détaillé

Comparons :

A = 0110 (6)
B = 0101 (5)

Les bits 3 et 2 correspondent. Au bit 1, A vaut 1 et B vaut 0, donc $G_1=1$ . Le bit 0 est sans importance, car une différence de poids supérieur existe déjà :

G=1, E=0, L=0

Il s’agit d’une fonction de priorité, mais la priorité va du bit de données de poids fort vers celui de poids faible.

Une cellule de comparateur récursive

Au lieu de développer une longue somme de produits, combinez les groupes hiérarchiquement. Supposons que H décrive un groupe de poids fort et Lw un groupe de poids faible :

G_{\text{all}}=G_H\lor(E_H\land G_{Lw})

E_{\text{all}}=E_H\land E_{Lw}

L_{\text{all}}=L_H\lor(E_H\land L_{Lw})

Le groupe de poids fort décide, sauf s’il est égal ; dans ce seul cas, le groupe faible transmet son résultat. Cette combinaison de type associatif peut former une cascade linéaire ou une hiérarchie équilibrée.

Ces équations expliquent les entrées d’expansion d’un circuit intégré comparateur de magnitude 4 bits. Le bloc a besoin d’un résultat G/E/L de poids inférieur au cas où ses quatre bits locaux sont à égalité.

Mettre des blocs SN74LS85 en cascade

Le SN74LS85 compare deux mots binaires directs de 4 bits ou deux mots BCD 8-4-2-1 et expose trois entrées d’expansion ainsi que trois sorties de relation.

Pour une comparaison sur huit bits :

le composant de poids faible compare les bits 3:0 ;
initialisez sa relation d’expansion à égalité : G_in=0, E_in=1, L_in=0 ;
reliez ses sorties G/E/L aux entrées d’expansion correspondantes du composant de poids fort ;
le composant de poids fort compare les bits 7:4 et produit le résultat final.

Si les moitiés hautes diffèrent, cette décision locale prend le pas sur l’entrée basse. Si les moitiés hautes correspondent, la relation de poids faible est transmise.

Suivez la fiche technique exacte pour la polarité des broches, le fan-out, la tension et le timing. La récursion logique ne remplace pas la conception électrique.

Comparaison signée en complément à deux

L’égalité utilise le même réseau XNOR pour les valeurs signées et non signées. L’ordre diffère.

Méthode 1 : interpréter séparément le bit de signe

Soient $s_A=A_{n-1}$ et $s_B=B_{n-1}$ .

Si $s_A\ne s_B$ , l’opérande dont le bit de signe vaut 1 est le plus petit.
Si les signes correspondent, la comparaison lexicographique ordinaire de la relation restante donne le bon ordre.

Une transformation matérielle pratique consiste à inverser le MSB de chaque opérande avant de l’envoyer à un comparateur non signé :

A'=A\oplus 2^{n-1}

B'=B\oplus 2^{n-1}

Inverser le bit de signe transpose l’ordre du complément à deux dans l’ordre non signé. Sur quatre bits :

signed -8 = 1000  → biased 0000
signed -1 = 1111  → biased 0111
signed  0 = 0000  → biased 1000
signed +7 = 0111  → biased 1111

Les valeurs biaisées croissent maintenant dans le même ordre que les nombres signés.

Méthode 2 : soustraire et interpréter les indicateurs

Si une ALU calcule $R=A-B$ :

E est Z ;
L signé est $N\oplus V$ ;
G signé est $\overline Z\land\overline{N\oplus V}$ .

Le inférieur non signé dépend de la convention de retenue de la soustraction. Lorsque la retenue brute signifie absence d’emprunt, le inférieur non signé est $\overline C$ . Avec un indicateur d’emprunt de type x86, le inférieur non signé est C. Le guide des indicateurs CPU déduit les deux conventions.

N’utilisez pas N seul pour le inférieur signé. Un débordement signé peut inverser le signe apparent du résultat stocké.

Exemple avec deux interprétations opposées

A = 1000
B = 0111

Non signé :

8 > 7

Complément à deux signé :

-8 < +7

Un comparateur étiqueté seulement « A>B » est incomplet tant que le signe n’est pas connu.

Timing et choix d’implémentation

La profondeur d’une chaîne de priorité linéaire est proportionnelle à la largeur. Un réseau équilibré de combinaison de groupes peut réduire la profondeur logique. La synthèse peut utiliser :

des portes larges ou composées ;
des combinaisons d’égalité/supérieur de type préfixe ;
le matériel de soustraction déjà présent dans une ALU ;
les ressources de chaîne de retenue ou de tables de recherche d’un FPGA ;
des structures d’arrêt anticipé pour certains usages.

Aucune topologie n’est universellement la plus rapide. Un comparateur dédié peut éviter d’attendre un résultat arithmétique dans une conception, tandis que la réutilisation d’un additionneur peut économiser de la surface dans une autre. Les processeurs modernes répartissent également les comparaisons entre la logique de branchement, de génération d’adresses, vectorielle et d’autres unités d’exécution plutôt que d’implémenter un comparateur monolithique unique.

Le chemin temporisé inclut le clock-to-Q de la source, la sélection d’entrée, la logique de comparaison, le routage, le setup de la destination et les effets d’horloge. Le seul nombre de portes ne fixe pas la fréquence maximale.

Utilisations pratiques

Correspondance exacte d’adresse

Un comparateur d’égalité peut produire un chip-select lorsqu’une adresse est égale à une valeur fixe. Pour une région alignée de taille puissance de deux, comparez uniquement les bits d’adresse de poids fort et traitez les bits bas comme décalage. Des plages arbitraires peuvent plutôt utiliser des inégalités ou une logique de décodage factorisée.

La validité du bus exige davantage qu’une égalité : les validations, le type d’accès, les privilèges et la propriété mutuellement exclusive peuvent également qualifier la sélection.

Tests de seuil et de fenêtre

La logique de contrôle peut tester :

LOW\le X\le HIGH

avec deux comparaisons de magnitude. Faites attention aux bornes inclusives ou exclusives et au signe éventuel de X.

Minimum/maximum et comparaison–sélection

Un résultat de magnitude peut piloter des multiplexeurs :

min = (A < B) ? A : B
max = (A < B) ? B : A

La politique en cas d’égalité compte lorsque chaque valeur porte des métadonnées ou qu’un ordre stable est requis.

Réseaux de tri

Une cellule compare-échange combine un comparateur avec des multiplexeurs de routage des données. Des réseaux fixes composent ces cellules par étages. Leur latence dépend à la fois de la profondeur du comparateur et du nombre d’étages compare-échange, pas seulement du nombre de cellules.

Construire et vérifier dans DigiSim

Utilisez le composant comparateur comme référence, puis construisez les équations avec des portes :

construisez quatre signaux $E_i$ avec des XNOR ;
réduisez-les pour obtenir E ;
construisez $G_i$ et $L_i$ pour chaque position ;
combinez-les du MSB vers le LSB ;
affirmez qu’exactement un des signaux G/E/L est à l’état haut pour chaque paire d’entrées valide ;
ajoutez une option de biais du MSB pour passer de la comparaison non signée à la comparaison signée.

Le test exhaustif est pratique sur quatre bits : évaluez les $16\times16=256$ paires.

Pour chaque paire, vérifiez :

E est égal à l’égalité des vecteurs de bits ;
G/L non signé correspond aux entiers 0–15 ;
G/L signé correspond aux entiers -8–7 ;
échanger A et B échange G et L tout en conservant E ;
G, E et L sont mutuellement exclusifs et collectivement exhaustifs.

Mettez ensuite deux blocs quatre bits en cascade et ciblez des paires limites comme 0x0F/0x10, 0x7F/0x80 et des moitiés hautes égales avec des moitiés basses différentes.

Un simulateur fonctionnel établit la relation booléenne. Il n’établit ni le délai de propagation physique, ni la compatibilité électrique, ni la fermeture du timing dans la technologie finale.

Référence

Page produit et fiche technique du comparateur de magnitude 4 bits SN74LS85 de Texas Instruments