Minimierung (Optimierung) digitaler Logikschaltung mit Multiplexer(n)

(das war übrigens eine Prüfungsfrage)

Für F = ∑ M ( 2 , 3 , 5 , 7 , 11 , 13 ) , versuche ich, eine digitale Logikschaltung zu implementieren, die nur Folgendes verwendet:

  • 2:1 MUX (Kosten: 12, und muss mindestens einen 2:1 MUX verwenden )
  • UND-Gatter mit 2 Eingängen (Kosten: 6)
  • ODER-Gatter mit 2 Eingängen (Kosten: 6)
  • Wechselrichter (Kosten: 2)

Es ist offensichtlich ziemlich einfach, es ohne Einschränkungen zu implementieren - das heißt, wenn ich mich überhaupt nicht um die Kosten kümmere. Aber wenn ich die Kosten minimieren wollte, wie sollte ich vorgehen?

Ich habe erstmal vereinfacht F mit der K-Karte davon, und ich bekam zwei Darstellungen davon F , A als MSB:

  • F = B C ' D + A ' B ' C + B ' C D + A ' C D
  • F = B C ' D + A ' B ' C + B ' C D + A ' B D .

Die zweite Darstellung sah für mich einfach gut aus, weil ich alle Produktbegriffe danach gruppieren kann B so was: F = B D ( A ' + C ' ) + B ' C ( A ' + D ) . Und anscheinend ist mein Design tatsächlich die Implementierung mit den geringsten Kosten - ich habe:Mein Design

Aber die Art und Weise, wie ich es gelöst habe, kann nicht für andere Ausdrücke im Allgemeinen verwendet werden, und ich denke ehrlich, ich habe einfach Glück gehabt. Gibt es einen besseren Weg, um dieses Problem zu lösen, dh einen allgemeinen Weg, der garantiert (oder zumindest überprüft), dass die Implementierung die mit minimalen Kosten ist?

Interessante Frage
Der einzige Weg, den ich kenne, ist, es brutal zu erzwingen. Finden Sie eine beliebige Lösung, damit Sie eine Obergrenze haben. Gehen Sie dann alle möglichen Schaltungen mit geringeren Kosten durch und prüfen Sie, ob sie die richtige Wahrheitstabelle haben. Ausgabe am günstigsten.
Wie erhalten Sie zwei Ausdrücke? Der erste Ausdruck ist der richtige. Nicht die zweite

Antworten (2)

schematisch

Simulieren Sie diese Schaltung – Mit CircuitLab erstellter Schaltplan

$34 ist das Beste, was ich tun kann. Irgendjemand anderes?

Wenn Sie Wechselrichter mit Open-Collector-Ausgängen verwenden, können Sie die Kosten auf etwa 24 senken, ohne den MUX zu verwenden. Leider ist der MUX in dieser Anwendung seine Kosten nicht wert, es sei denn, er hat eine andere Funktion, die er hinzufügt, die nicht gegeben ist, wie HI- Z- oder Open-Collector-Ausgänge usw. Es kann ein Gatter zum Preis von 2 Gattern ersetzen.

In realen Anwendungen könnten Sie normale Wechselrichter verwenden, da sie alle intern Open Collector (technisch Drain) mit einem HI-Fanout sind, das viel niedriger ist als das LO-Fanout. Dies gibt auch den zusätzlichen Vorteil, dass die Kosten für einen Widerstand nicht ausgegeben werden. WARNUNG Diese Verwendung erzeugt viel Wärme, wenn der Ausgang HI ist, wenn ein anderer paralleler Ausgang LO ist, aber es funktioniert und überschreitet nicht die Chipwerte der meisten Chips der 74er-Serie.

Minimierung (Optimierung) digitaler Logikschaltung mit Multiplexer(n)
AntwortenHierDatenschutz-Bestimmungen1y, 0v