So finden Sie heraus, ob eine Binärzahl Null ist

16

Ich implementierte die ALU gemäß den Angaben in meinem Buch The Elements of Computing systems. Ich stecke nur in einem Problem fest. Wie finde ich heraus, ob eine bestimmte Zahl Null ist oder nicht? Eine Sache, die ich tun kann, ist oder jedes bisschen im Bus, und dann ein Nicht-Gatter darauf anwenden. Aber es muss eine andere elegante Lösung geben.

Rick_2047
quelle
6
es hört sich nicht so an, als ob du wirklich feststeckst - eher als ob du unzufrieden bist :)
vicatcu
7
Ein X-Eingang NOR ist die elegante Lösung. Um festzustellen, ob das Register Null enthält, muss jedes Bit daraufhin überprüft werden, ob es eine logische 0 enthält. Sie haben angegeben, dass Sie eine Einzelbitausgabe benötigen. Daher benötigen Sie eine Funktion mit X Eingängen und einem Ausgang, wie z. B. ein NOR.
W5VO

Antworten:

14

Es führt einfach kein Weg daran vorbei, alle Teile zu ORen, so unbefriedigend das auch scheinen mag. Sie sind jedoch auch nicht auf zwei Eingangsgatter in Silizium beschränkt. Sie können ein NOR-Gatter mit 4 Eingängen in CMOS-Logik erstellen, indem Sie 4 p-Serientransistoren in das Pullup-Netzwerk und 4 parallele n-Transistoren in das Pulldown-Netzwerk einfügen. Dies verringert die Tiefe Ihrer Baumtopologie und damit die Laufzeitverzögerung. Sie können diese Theorie nur so weit führen, aber bevor der kumulative Spannungsabfall an den Serientransistoren dazu führt, dass der Pull-up nicht hoch genug ist, um eine "1" zu sein ... vier ist eine gute Faustregel, wenn ich mich richtig erinnere.

vicatcu
quelle
Wäre für eine größere Anzahl von Bits die Verwendung von alternierenden NOR- und NAND-Gattern sinnvoll? Bei einem 64 - Bit - Nulltest mit Fan - In von 4 Gattern könnten beispielsweise 16 NOR - Gatter verwendet werden, die ein Ergebnis von 1 liefern, wenn die 4 Bits Null bis 4 NAND - Gatter sind, und die ein Ergebnis von 0 liefern, wenn alle 4 Bits 1 sind (alle) 16 ursprüngliche Bits waren 0), diese vier Ergebnisse würden dann an ein endgültiges NOR-Gatter gesendet. (Ich bin kein EE, aber das scheint besser zu sein, als Zwischeninverter zu verwenden - um das Null-Ergebnis wieder auf 0 zu bringen - und nur NOR-Gatter zu verwenden.)
Paul A. Clayton
Möglicherweise gibt es auch Möglichkeiten, die Latenz der Null-Erkennung teilweise in die zusätzliche Latenz umzuwandeln.
Paul A. Clayton
Was ist mit NMOS: Ein Pull-Up-Widerstand und X-Transistoren, um den Pegel auf 0 zu senken, wenn ein Eingang 1 ist?
Oskar Skog
13

Die Logikfunktion ist das NOR-Gatter. Das ist die einfachste Logikfunktion, die es gibt.

Rex Logan
quelle
8

Die typische Lösung für 8-Bit-Maschinen war, dass die ALU eine Reihe von Flag-Bits erzeugt, die das Ergebnis der letzten Operation darstellen. Während es möglich wäre, eine beliebige Anzahl von Flag-Bits zu haben (dh, Sie könnten ein 'Z'-Flag für jedes Register in Ihrer CPU haben), ist es normalerweise das, was Sie gerade berechnet haben, für das Sie am interessantesten sind Es macht einen gewissen Sinn, dies so zu tun.

Einige dieser alten CPUs setzten automatisch Flag-Bits für fast jede Datenbewegung, während andere erfordern würden, dass Sie eine bestimmte 'Compare'-Anweisung in Ihren Code einfügen, wenn Sie nur plötzlich wissen müssen, ob ein bestimmtes Register Null ist. Unabhängig davon, ob Sie für jedes Register oder nur für das, was gerade berechnet wurde, eine Nullprüfung durchführen, gibt es keinen einfacheren Weg, nach "Ist dieses Wort Null" zu suchen, als einfach alle Bits zusammen zu ODER.

JustJeff
quelle
1
Dies ist auch typisch für 32-Bit-ARM-Chips und kann typisch für die meisten Architekturen sein. Für den ARM enthält das APSR (Application Program Status Register) die Bits N, Z, C, V und Q (Negative, Zero, Carry, Overflow, SaturateQ), um neben dem gesuchten Nullbit weitere Funktionen bereitzustellen . Diese können für Ihr Gerät nützlich sein oder auch nicht.
Kevin Vermeer
Ich habe die Lösung oder in Ordnung, aber es nervt mich, dass ich so viel Logik verwenden muss, um nur ein bisschen zu bekommen. Es muss eine elegante Lösung geben.
Rick_2047
@ Rick_2047 - du hast nicht erwähnt, womit du das umsetzt, aber ich vermute ein FPGA? Es würde mich auch ärgern, eine beliebige Anzahl von Logikblöcken binden zu müssen, um ein hohes Fan-In-Gate zu erzeugen. Das ist ein guter Grund, nur einen einzutragen.
JustJeff
Nicht gerade ein FPGA, sondern ein HDL- und Hardware-Simulator.
Rick_2047
3

Einige CPUs, z. B. MIPS, haben ein Register, das immer Null enthält, was das Testen eines anderen Registers auf Null sehr schnell macht.

Leon Heller
quelle
Wie überprüfe ich die Nummer, wenn ich ein Register mit Null habe? Außerdem möchte ich nur ein Bit generieren, das wahr oder falsch ist, je nachdem, ob der 16-Bit-Bus null ist oder nicht
Rick_2047
1
ein Komparator ... der zu einem verherrlichten NOR-Gatter
verkommt
Er könnte auf diese Weise etwas gewinnen, wenn die Register billig sind (sie befinden sich in einem SRAM-Block in einem FPGA) und er ohnehin einen Registervergleichsbefehl aus anderen Gründen benötigt.
JPC
@vicatu - Wenn Sie zwei N-Bit-Zahlen vergleichen möchten, benötigen Sie N XOR-Gatter mit 2 Eingängen. Das OR / NOR-Ding ist nur für Nulltests gut.
JustJeff
aber letztendlich müsste ich so viele gates verwenden, wie ich eingabebits oder mindestens so viele transistoren habe.
Rick_2047
0

Ich bin ein großer Fan von or_reduce- die meisten Synthesewerkzeuge optimieren es auf die beste Implementierung, da sie genau wissen, was Sie tun.

Aaron D. Marasco
quelle