Gibt es Möglichkeiten auf Gate-Ebene, das Minimum oder Maximum von zwei Binärwerten zu erzeugen?

Einige Grundlagen der digitalen Logik sind der Halbaddierer und der Volladdierer . Wir wissen, wie man die Summe zweier Binärwerte auf der Ebene von UND/ODER/NICHT-Gattern auf einfache Weise erzeugt, wie es in vielen Lehrbüchern dargestellt wird. (Kümmern Sie sich nicht um fortgeschrittene Tricks, die in echten Hochleistungschips verwendet werden.) Ein paar Optimierungen, und wir können subtrahieren .

Was ich mich nicht erinnern kann, jemals gesehen zu haben, sind Methoden auf Gate-Ebene, um das Minimum oder Maximum von zwei Binärwerten zu erzeugen. Gibt es so etwas? Wenn ja, verwenden es irgendwelche Mikroprozessoren?

Relative Vergleiche erfordern eine Kaskadierung durch die Bits und können nicht mit weniger als log n Schichten durchgeführt werden. Noch zwei Ebenen zu AND und OR mit den Eingabewerten und fertig.
@IgnacioVazquez-Abrams, was meinst du mit "kann nicht mit weniger als log n Schichten ausgeführt werden"? Ein ausreichend großes ROM könnte dies in einem Schritt tun.
@ThePhoton: Ich habe meine Big List of Gates durchgesehen, konnte aber keine namens "ROM" finden.
@IgnacioVazquez-Abrams Betrachten Sie es als einen wirklich großen Fan-in-Summe-von-Produkten.
@IgnacioVazquez-Abrams Es gibt kein einzelnes Tor, das dieses Problem lösen kann, selbst das, was Sie vorgeschlagen haben. ROM LUT kann sicherlich genauso aus Gattern aufgebaut werden wie Ihr Kaskadensystem ...
@ThePhoton: Die Schaltgeschwindigkeit eines einzelnen großen N-Eingangstors ist proportional zu N, wenn in die Richtung "beliebig" und zu N ^ 2 in die Richtung "alle" geschaltet wird [z. B. für ein NAND die Richtung "beliebig". ist "jeder Eingang niedrig: Ausgang hoch", und die Richtung "alle" ist "alle Eingänge hoch: Ausgang niedrig"]. Eine NAND-Funktion mit 32 Eingängen wird im Allgemeinen nicht unter Verwendung eines einzelnen Gatters mit 32 Eingängen implementiert, sondern als so etwas wie acht NAND-Gatter mit 4 Eingängen, die zwei NOR-Gatter mit 4 Eingängen ansteuern, die wiederum ein NAND mit zwei Eingängen ansteuern. Eine solche Implementierung würde mehr Schaltungen erfordern, wäre aber viel schneller als die Verwendung eines Gatters.
@supercat, "unpraktisch langsam" ist nicht dasselbe wie "geht nicht".
@ThePhoton: Ich denke, es hängt davon ab, was Ihr Ziel ist, wenn Sie versuchen, weniger Ebenen zu haben. Wenn eine "zweischichtige" Schaltung mehr Fläche einnehmen würde als eine mit mehr Schichten, eine längere Ausbreitungszeit hätte und bei jedem Umschalten mehr Energie verbrauchen würde, würde ich die Tatsache in Betracht ziehen, dass die Schaltung in zwei Schichten implementiert werden "könnte". nur von vagem theoretischem Interesse.
@supercat, ich würde es nicht so machen, aber ich würde nicht behaupten, dass es "nicht machbar" ist. Die Frage fordert uns ausdrücklich auf: "Kümmern Sie sich nicht um fortgeschrittene Tricks, die in realen Hochleistungschips verwendet werden." Es geht also um die Frage, was theoretisch möglich ist, nicht darum, wie man Dinge in der realen Welt am besten umsetzt.
@ThePhoton: Ich nehme an, eine gute Frage könnte dann sein, ob ein Gate mit 32 Transistoren in Reihe als eine "Schicht" oder 32 betrachtet werden sollte. Wenn Eingänge sowohl in invertierter als auch in nicht invertierter Form verfügbar sind, könnte jede kombinatorische Funktion implementiert werden, um sie bereitzustellen sowohl normale als auch komplementäre Ausgänge, ohne dass das Gate eines Transistors mit etwas anderem als den Eingängen verbunden ist. Die meisten ROMs verwenden zusätzlich zur Eingabeinversion zwei Schritte, aber kombinatorische Funktionen "brauchen" nie mehr als einen. Auf der anderen Seite, wo hat das OP nach "Schichten" gefragt? Ich denke, IVA sprach von einem praktischen Standpunkt aus.

Antworten (2)

Wie wäre es, bevor Sie sich mit dem Min/Max befassen, einfach zwei Zahlen zu vergleichen? Angenommen, Sie haben zwei Binärzahlen: A und B, und Sie möchten wissen, ob A > B. Was Sie tun, ist eine einfache Subtraktion, C=BA. Wenn C negativ ist, dann war A größer als B. Bei einer binären Zweierkomplementzahl ist das höchstwertige Bit (MSB) 1, wenn die Zahl negativ ist, und 0, wenn sie positiv ist. Nach der Subtraktion sagt Ihnen also ein einzelnes Bit, ob A oder B größer ist.

Nun, das war eine super einfache Art, es zu erklären. Dabei sind einige Details zu beachten.

Dies funktioniert mit vorzeichenbehafteten Zahlen (Zweierkompliment). Wenn A und B nicht signiert sind, müssen Sie sie zuerst in signiert konvertieren. Das bedeutet eigentlich nur, dass man links ein Null-Bit hinzufügt und die resultierende Zahl um ein Bit größer ist. Wenn beispielsweise A = 1111 (unsigned) ist, müssen Sie A = 01111 (signed) machen.

Das andere Problem ist, dass Sie auf den Zahlenbereich achten müssen, den Sie verwenden werden, und sicherstellen müssen, dass Sie keine Überlauf-/Unterlaufbedingungen haben. Normalerweise gehe ich damit um, indem ich A und B etwas mehr gebe. Aus einer 8-Bit-Zahl mit Vorzeichen wird also eine 9-Bit-Zahl mit Vorzeichen. Sie tun dies, indem Sie das oberste (Vorzeichen-)Bit duplizieren. Wenn beispielsweise A = 1000 (mit Vorzeichen) ist, wird A zu 11000 (mit Vorzeichen).

Sobald Sie die Mathematik richtig durchgeführt haben, können Sie das MSB von C verwenden, um festzustellen, welche Zahl größer ist. Sie können dann einen einfachen MUX verwenden, um A oder B auszuwählen, abhängig vom Wert des MSB von C.

Subtrahieren gefolgt von der Auswahl des einen oder anderen. Nun, das ist der offensichtliche Weg, und derzeit ist das so, was getan wird. Ich hatte gehofft, es gäbe einen direkteren, clevereren Weg.

Es heißt Magnitude Comparator und verwendet weniger Gates als die Vanilla-Lösung. Siehe https://stackoverflow.com/questions/10767316/finding-the-maximum-of-two-integers-in-binary-using-bit-logic-only .

Die „Vanille“-Lösung, die Differenz zu berechnen und das MSB zu betrachten, hat den Vorteil, dass bekannte „Teile“ wiederverwendet werden, und kann Ihnen je nach Anwendungsfall etwas Entwurfszeit sparen. Sie können zumindest alle Gatter bis auf eines für die Ausgabe speichern, da Sie nur auf das MSB schauen.

Gibt es Möglichkeiten auf Gate-Ebene, das Minimum oder Maximum von zwei Binärwerten zu erzeugen?
AntwortenHierDatenschutz-Bestimmungen1y, 0v