Digitale Vergleicher erklärt: Gleichheit und Größenordnung

Gleichheits- und Größenvergleicher herleiten, 4-Bit-Blöcke kaskadieren, vorzeichenbehaftete und vorzeichenlose Ordnung unterscheiden und Ausgänge für größer/gleich/kleiner verifizieren.

Denny

7. Mai 20267 Min. Lesezeit

Chalkboard feature illustration for “Digitale Vergleicher erklärt: Gleichheit und Größenordnung”

Kurz gesagt: Gleichheit ist ein reduziertes UND der bitweisen XNOR-Ergebnisse. Die vorzeichenlose Größenordnung wird an der höchstwertigen Position entschieden, an der sich A und B unterscheiden. Bei vorzeichenbehafteten Werten muss das Vorzeichenbit oder die Subtraktions-Flags anders interpretiert werden. Ein Vergleicher ist erst dann korrekt, wenn Breite, Vorzeichenbehandlung, Ausgangspolarität und Kaskadeneingänge festgelegt sind.

Ein Vergleicher wandelt zwei Bitvektoren in eine Beziehung um:

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

Das klingt eindeutig, bis dieselben Bits unterschiedlich interpretiert werden. Bei vier Bits ist 1000 vorzeichenlos 8, im Zweierkomplement aber -8. Verglichen mit 0111 ist es bei vorzeichenloser Interpretation größer und bei vorzeichenbehafteter Interpretation kleiner.

Dieser Leitfaden baut zunächst die Gleichheit auf, leitet dann ein Netzwerk für die vorzeichenlose Größenordnung her und zeigt anschließend, wie vorzeichenbehaftete Vergleiche und die Kaskadierung von Blöcken das Design verändern.

Den Vertrag festlegen

Für zwei gültige $n$ -Bit-Eingänge A und B erzeugt ein dreiausgängiger Größenvergleicher typischerweise:

G: A ist größer als B;
E: A ist gleich B;
L: A ist kleiner als B.

Unter einem gültigen zweiwertigen Eingangsmodell gilt:

G+E+L=1

und nie sind zwei Ausgänge gleichzeitig High. Diese One-Hot-Beziehung hängt von einer vollständigen Implementierung und gültigen Logikpegeln ab. Ein Enable-Eingang, eine active-low-Schnittstelle, unbekannte Simulationswerte oder falsch initialisierte Kaskadeneingänge können das sichtbare Verhalten verändern.

Gleichheit hängt nicht von der Vorzeichenbehandlung ab: Die Bitvektoren stimmen entweder überein oder nicht. Größer und kleiner tun es.

Gleichheit aus XNOR

Für eine Position gilt:

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

$E_i=1$ , wenn die beiden Bits übereinstimmen. Ganze Wörter sind nur dann gleich, wenn alle Positionen übereinstimmen:

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

Für vier Bits gilt:

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

Der direkte Schaltplan verwendet vier XNOR-Gatter, gefolgt von einer UND-Reduktion.

Es ist verlockend, das als „zwei Gatterverzögerungen unabhängig von der Breite“ zu bezeichnen. Das ist nur eine Boolesche Zeichnung mit unbegrenzter Fan-in-Zahl. Physische Implementierungen können die Reduktion als ausgewogenen Baum aufbauen, in zusammengesetzte Zellen faktorisieren oder in FPGA-Lookup-Tabellen abbilden. Mit UND-Gattern mit zwei Eingängen wächst die Reduktionstiefe bei ausgewogener Struktur ungefähr als $\lceil\log_2 n\rceil$ .

Vorzeichenlose Größenordnung: Der höchste Unterschied entscheidet

Für jedes Bit definieren wir:

G_i=A_i\overline{B_i}

L_i=\overline{A_i}B_i

E_i=A_i\odot B_i

An der höchstwertigen unterschiedlichen Position bedeutet eine 1 in A und eine 0 in B, dass A größer ist; umgekehrt ist A kleiner. Niedrigere Positionen sind nur dann relevant, wenn alle höheren Positionen übereinstimmen.

Für vorzeichenlose Vierbitwerte gilt:

\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

Jeder G-Term sagt: „Alle höheren Bits sind gleich und A gewinnt hier.“ Jeder L-Term beschreibt den symmetrischen Fall.

Durchgerechnetes vorzeichenloses Beispiel

Vergleichen wir:

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

Bits 3 und 2 stimmen überein. Bei Bit 1 hat A eine 1 und B eine 0, also ist $G_1=1$ . Bit 0 ist irrelevant, weil bereits ein höherer Unterschied existiert:

G=1, E=0, L=0

Das ist eine Prioritätsfunktion, doch die Priorität läuft vom höchstwertigen Datenbit zum niederwertigsten.

Eine rekursive Vergleicherzelle

Statt eine lange Summe von Produkten auszuschreiben, können Gruppen hierarchisch kombiniert werden. Angenommen, H beschreibt eine höherwertige Gruppe und Lw eine niederwertige Gruppe:

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})

Die höhere Gruppe entscheidet, solange sie nicht gleich ist; erst dann wird die niedrigere Gruppe durchgereicht. Diese kombinierbare Struktur kann eine lineare Kaskade oder eine ausgewogene Hierarchie bilden.

Die Gleichungen erklären die Expansionseingänge eines 4-Bit-Größenvergleicher-ICs. Der Block benötigt ein G/E/L-Ergebnis der niedrigeren Gruppe, falls seine lokalen vier Bits gleich sind.

SN74LS85-Blöcke kaskadieren

Der SN74LS85 vergleicht zwei 4-Bit-Wörter im reinen Binärformat oder im BCD-Format 8-4-2-1 und stellt drei Expansionseingänge sowie drei Beziehungsausgänge bereit.

Für einen Achtbitvergleich:

Das niederwertige Bauteil vergleicht die Bits 3:0.
Initialisieren Sie seine Expansionsbeziehung als gleich: G_in=0, E_in=1, L_in=0.
Verbinden Sie seine G/E/L-Ausgänge mit den entsprechenden Expansionseingängen des höherwertigen Bauteils.
Das höherwertige Bauteil vergleicht die Bits 7:4 und erzeugt das Endergebnis.

Wenn sich die höherwertigen Hälften unterscheiden, überschreibt diese lokale Entscheidung den niederwertigen Eingang. Stimmen die höherwertigen Hälften überein, wird die Beziehung der niederwertigen Hälfte weitergegeben.

Befolgen Sie das genaue Datenblatt für Pinpolarität, Fan-out, Spannung und Timing. Die logische Rekursion ersetzt kein elektrisches Design.

Vorzeichenbehafteter Vergleich im Zweierkomplement

Für vorzeichenbehaftete und vorzeichenlose Werte verwendet die Gleichheit dasselbe XNOR-Netzwerk. Die Ordnung unterscheidet sich.

Methode 1: Vorzeichenbit separat interpretieren

Seien $s_A=A_{n-1}$ und $s_B=B_{n-1}$ .

Wenn $s_A\ne s_B$ , ist der Operand mit Vorzeichenbit 1 kleiner.
Stimmen die Vorzeichen überein, liefert der gewöhnliche lexikografische Vergleich der übrigen Beziehung das richtige Ergebnis.

Eine praktische Hardwaretransformation besteht darin, das MSB jedes Operanden zu invertieren, bevor es an einen vorzeichenlosen Vergleicher geht:

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

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

Das Umdrehen des Vorzeichenbits verschiebt die Zweierkomplementordnung in die vorzeichenlose Ordnung. Für vier Bits:

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

Die verschobenen Werte steigen nun in derselben Reihenfolge wie die vorzeichenbehafteten Zahlen.

Methode 2: Subtrahieren und Flags interpretieren

Wenn eine ALU $R=A-B$ berechnet:

E ist Z;
vorzeichenbehaftetes L ist $N\oplus V$ ;
vorzeichenbehaftetes G ist $\overline Z\land\overline{N\oplus V}$ .

Unsigned-Less-than hängt von der Carry-Konvention der Subtraktion ab. Wenn der rohe Carry-out kein Borrow bedeutet, ist das vorzeichenlose L $\overline C$ . Bei einem x86-ähnlichen Borrow-Flag ist das vorzeichenlose L C. Der CPU-Flags-Leitfaden leitet beide Konventionen her.

Verwenden Sie N allein nicht für vorzeichenbehaftetes kleiner. Ein vorzeichenbehafteter Überlauf kann das scheinbare Vorzeichen des gespeicherten Ergebnisses invertieren.

Beispiel mit entgegengesetzten Interpretationen

A = 1000
B = 0111

Vorzeichenlos:

8 > 7

Vorzeichenbehaftetes Zweierkomplement:

-8 < +7

Ein Vergleicher, der nur mit „A>B“ beschriftet ist, ist unvollständig spezifiziert, solange die Vorzeichenbehandlung unbekannt ist.

Timing und Implementierungsentscheidungen

Eine lineare Prioritätskette hat eine Tiefe, die proportional zur Breite ist. Ein ausgewogenes Netzwerk zur Gruppenkombination kann die logische Tiefe verringern. Die Synthese kann Folgendes verwenden:

breite oder zusammengesetzte Gatter;
prefixartige Kombinationen für Gleichheit und größer;
bereits in einer ALU vorhandene Subtraktionshardware;
FPGA-Carry-Chain- oder Lookup-Table-Ressourcen;
Early-out-Strukturen für ausgewählte Einsatzfälle.

Keine Topologie ist grundsätzlich am schnellsten. Ein dedizierter Vergleicher kann in einem Design das Warten auf ein Rechenergebnis vermeiden, während die Wiederverwendung eines Addierers in einem anderen Fläche spart. Moderne Prozessoren verteilen Vergleiche außerdem auf Branch-, Adressgenerierungs-, Vektor- und andere Ausführungslogik, statt einen einzigen monolithischen Vergleicher zu implementieren.

Der getaktete Pfad umfasst Clock-to-Q der Quelle, Eingangsauswahl, Vergleicherlogik, Routing, Setup des Ziels und Takteffekte. Die Zahl der Gatter allein legt keine maximale Frequenz fest.

Praktische Anwendungen

Exakte Adressübereinstimmung

Ein Gleichheitsvergleicher kann ein Chip-Select erzeugen, wenn eine Adresse einem festen Wert entspricht. Für einen ausgerichteten Bereich der Größe einer Zweierpotenz werden nur die höherwertigen Adressbits verglichen; die niederwertigen Bits gelten als Offset. Beliebige Bereiche können stattdessen Ungleichheiten oder faktorisierte Decodierlogik verwenden.

Buskorrektheit erfordert mehr als Gleichheit: Enable, Zugriffstyp, Berechtigung und einander ausschließender Besitz können die Auswahl ebenfalls qualifizieren.

Schwellen- und Fensterprüfungen

Die Steuerlogik kann Folgendes prüfen:

LOW\le X\le HIGH

mit zwei Größenvergleichen. Achten Sie auf inklusive und exklusive Grenzen sowie darauf, ob X vorzeichenbehaftet ist.

Min/Max und Compare-Select

Ein Größenergebnis kann Multiplexer steuern:

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

Die Behandlung von Gleichständen ist wichtig, wenn jeder Wert Metadaten trägt oder eine stabile Ordnung erforderlich ist.

Sortiernetzwerke

Eine Compare-Exchange-Zelle verbindet einen Vergleicher mit Multiplexern zur Datenführung. Feste Netzwerke setzen diese Zellen in Stufen zusammen. Ihre Latenz hängt sowohl von der Tiefe des Vergleichers als auch von der Anzahl der Compare-Exchange-Stufen ab, nicht nur von der Zahl der Zellen.

In DigiSim bauen und verifizieren

Verwenden Sie die Vergleicher-Komponente als Referenz und konstruieren Sie anschließend die Gleichungen aus Gattern:

Bauen Sie vier $E_i$ -Signale mit XNOR.
Reduzieren Sie sie zu E.
Bauen Sie für jede Position $G_i$ und $L_i$ .
Kombinieren Sie sie vom MSB zum LSB.
Stellen Sie sicher, dass für jedes gültige Eingangspaar genau eines von G/E/L High ist.
Ergänzen Sie eine MSB-Bias-Option, um zwischen vorzeichenlosem und vorzeichenbehaftetem Vergleich umzuschalten.

Bei vier Bits ist eine vollständige Prüfung praktisch: Werten Sie alle $16\times16=256$ Paare aus.

Prüfen Sie für jedes Paar:

E entspricht der Gleichheit der Bitvektoren;
vorzeichenloses G/L stimmt mit den Ganzzahlen 0–15 überein;
vorzeichenbehaftetes G/L stimmt mit den Ganzzahlen -8–7 überein;
das Vertauschen von A und B vertauscht G und L, erhält aber E;
G, E und L sind gegenseitig exklusiv und zusammen vollständig.

Kaskadieren Sie anschließend zwei Vierbitblöcke und testen Sie Grenzpaare wie 0x0F/0x10, 0x7F/0x80 sowie gleiche höherwertige Hälften mit unterschiedlichen niederwertigen Hälften.

Ein funktionaler Simulator stellt die Boolesche Beziehung fest. Er belegt weder die physische Ausbreitungsverzögerung noch elektrische Kompatibilität oder Timing-Abschluss in der endgültigen Technologie.

Referenz

Produktseite und Datenblatt des 4-Bit-Größenvergleichers SN74LS85 von Texas Instruments