Wie implementieren Sie die folgende Funktion nur mit 2: 1 MUX?

Ich habe Schwierigkeiten zu verstehen, wie boolesche Funktionen implementiert werden, insbesondere da ich nur 2: 1-Muxes und die Variable D als Restvariable verwenden darf.

Die Funktion ist wie folgt:

F (A, B, C, D, E) = \sum (6, 7, 12, 13, 14, 15, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31)

$F(A, B, C, D, E) = \sum ( 6, 7, 12, 13, 14, 15, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31)$

Ich habe die Wahrheitstabelle erstellt und mithilfe einer Karnaugh-Karte die Funktion auf diese Weise minimiert:

F (A, B, C, D, E) = A B + B C + C D \bar{E} + C D E

$F(A, B, C, D, E) = AB + BC + CD \bar{E} + CDE$

Ich habe es auch geschafft, einen 16: 1-MUX mit A, B, C und E als Selektor und D als Restvariable zu entwerfen.

Ich verstehe, wie ein Multiplexer funktioniert, und ich bin in der Lage, eine Wahrheitstabelle aus einer vorhandenen Implementierung abzuleiten, aber ich verstehe einfach nicht, wie man die Wahrheitstabelle, die Karnaugh-Karte und die minimierte SOP-Funktion nimmt und die Funktion nur mit 2: 1 implementiert MUX und D als Restvariable.

Ich frage nicht unbedingt nach der direkten Antwort, obwohl es schön wäre, sie zu sehen. Ich interessiere mich mehr für eine Erklärung, einen Algorithmus oder wirklich alles, was mir helfen kann, die Implementierung selbst zu finden.

Ich möchte in der Lage sein, die Verbindung zwischen der Funktion und der Implementierung zu visualisieren und nicht nur zu lernen, wie man sie auswendig implementiert, ohne zu verstehen, warum es so ist, wie es ist.

Vielen Dank für Ihre Zeit!

Bearbeiten: Während ich die akzeptierte Antwort verstanden habe und es die richtige Antwort ist, musste ich nur die folgenden Eingaben für die Datenleitungen meiner 2: 1-Muxes verwenden: Logik 0, Logik 1 und die Variable D. Die Variablen A, B, C sollten nur als Auswahllinien verwendet werden.

Ich habe die VK-Karte für F (A, B, C, D) = AB + BC + CD erstellt und diese Karte dann verwendet, um eine VK-Karte für F (A, B, C) abzuleiten, wie unten zu sehen ist.

Bearbeiten: Für die Karte rechts sollte der Wert für ABC = 000 0 und nicht 1 sein. Ein Fehler, den ich gemacht habe, als ich die Tabelle von meinem Notizbuch nach Excel kopiert habe.

Danach habe ich folgende Mux-Implementierung erstellt:

Das Mux-Design stammt aus einem Elektronikbuch. Die Implementierung ist zwar nicht besonders effizient, funktioniert aber. Ich habe die Ausgabe der Muxes mit der Formel M (X, Y, Z) = XZ '+ YZ berechnet und die Ausgabe der Mux ganz rechts ist:

M U X 7 = A B \bar{C} + D \bar{B} C + B C

$MUX7 = AB\bar{C} + D\bar{B}C + BC$

Unter Verwendung einer weiteren Karnaugh-Karte vereinfacht sich das Obige zu AB + BC + CD, der Funktion, die ich implementieren musste.

Das Design der MUXes selbst stammt aus einem Elektronikbuch. In dem Buch wurden die Dateneingaben der MUX-Ebene ganz links nummeriert, wie in meinem Diagramm zu sehen ist, und die Beschriftungen repräsentieren das Dezimaläquivalent der F (A, B, C) VK-Kartenzellen. Wenn Sie beispielsweise die Zelle 101 (binär für 5) betrachten, ist der Wert in dieser Zelle die Eingabe für die entsprechend gekennzeichnete MUX-Eingabe in der Implementierung, in diesem Fall 'D'.

Kann sich jemand einschalten, warum die Dateneingabezeilen in dieser bestimmten Reihenfolge beschriftet sind (0, 4, 2, 6, 1, 5, 3, 7)?

multiplexer logic-gates decoder boolean-algebra user1969903
quelle

reduziert sich F (A, B, C, D, E) nicht auf A (B + C) + CD?

Tony Stewart Sunnyskyguy EE75

für A = msb, F = 00110 + 00111 + 011xx + 10110 bis 11111 haben Sie so begonnen?

Tony Stewart Sunnyskyguy EE75

Vielen Dank, dass Sie sich die Zeit genommen haben, meine Frage zu lesen. Es kann sehr gut darauf reduziert werden. Ich habe keine Algebra verwendet, um die Funktion zu minimieren, nur die Karnaugh-Karte. In jedem Fall ist die Funktion selbst nicht so relevant wie das Endziel der Frage. Technisch interessiert mich die Implementierung selbst, unabhängig davon, wie die Funktion aussieht.

user1969903

Es reduziert sich auf F = AB + BC + C D.

Jonk

Antworten:

Es ist nicht zu komplex, denke ich, vorausgesetzt, Sie haben die gewünschte Gleichung richtig ausgearbeitet (ich gehe davon aus, dass Sie dort in Ordnung waren). Sehen Sie sich zunächst die Gleichung für einen 2-in-MUX an:

\begin{aligned} M_{2} (A, B, S) & = A \cdot \bar{S} + B \cdot S \end{aligned}

$\begin{align*} M_2(A,B,S) &= A\cdot \bar{S} + B\cdot S \end{align*}$

Daraus können Sie einige nützliche Ergebnisse ableiten:

\begin{aligned} M_{2} (0, x, y) & = x \cdot y \\ M_{2} (x, 0, y) & = x \cdot \bar{y} \\ M_{2} (x, y, 0) & = x \\ M_{2} (1, x, y) & = x + \bar{y} \\ M_{2} (x, 1, y) & = x + y \\ M_{2} (x, y, 1) & = y \\ M_{2} (x, y, x) & = x \cdot y \\ M_{2} (x, y, y) & = x + y \\ M_{2} (0, 0, x) & = 0 \\ M_{2} (0, 1, x) & = x \\ M_{2} (1, 0, x) & = \bar{x} \\ M_{2} (1, 1, x) & = 1 \end{aligned}

$\begin{align*} M_2(0,x,y) &= x\cdot y \\ M_2(x,0,y) &= x\cdot\bar{y} \\ M_2(x,y,0) &= x \\ M_2(1,x,y) &= x + \bar{y} \\ M_2(x,1,y) &= x + y \\ M_2(x,y,1) &= y \\ M_2(x,y,x) &= x\cdot y \\ M_2(x,y,y) &= x + y \\ M_2(0,0,x) &= 0 \\ M_2(0,1,x) &= x \\ M_2(1,0,x) &= \bar{x} \\ M_2(1,1,x) &= 1 \end{align*}$

Daraus folgt:

\begin{aligned} F & = A B + B C + C D \\ x & = A B = M_{2} (A, B, A) \\ y & = B C = M_{2} (B, C, B) \\ z & = C D = M_{2} (C, D, C) \\ ∴ F & = x + y + z \\ F & = M_{2} (M_{2} (x, y, y), z, z) \end{aligned}

$\begin{align*} F &= A B + B C + C D \\ x &= A B = M_2(A,B,A) \\ y &= B C = M_2(B,C,B) \\ z &= C D = M_2(C,D,C) \\ \therefore F &= x + y + z \\ F &= M_2(M_2(x,y,y),z,z) \end{align*}$

Kurz gesagt, Sie benötigen (5) 2-in-Muxes:

schematisch

^{simulieren Sie diese Schaltung - Schema erstellt mit CircuitLab}

Es gibt dort auch eine schöne Symmetrie. Bemerke es?

HINZUGEFÜGT: Sie haben gefragt, ob Sie nur 0, 1 oder D als Mux-Dateneingabequelle verwenden können. Ich gehe davon aus, dass Sie damit meinen, dass alle A, B, C und D als Mux-Selektoren verwendet werden können. (Andernfalls glaube ich nicht, dass das Ergebnis erzielt werden kann.) Dies bedeutet also nur, dass Sie einige der anderen nützlichen Ergebnisse verwenden müssen, die ich zuvor erwähnt habe. Die einfachste Idee wäre, nur drei weitere 2-in-Muxes hinzuzufügen:

schematisch

^{simulieren Sie diese Schaltung}

Ich bin mir nicht sicher, ob es eine Möglichkeit gibt, es weiter zu optimieren. Ich habe nicht alle Möglichkeiten geprüft.

WIEDER BEARBEITEN: Ja! Mit der neu hinzugefügten Lösung des OP fließen die folgenden beiden einfach heraus. Der linke beantwortet seinen ersten Teil der Frage, der rechte beantwortet seinen zweiten Teil.

schematisch

^{simulieren Sie diese Schaltung}

WIEDER BEARBEITEN: Die Bestellung ist nicht kompliziert. Es geht nur darum, die Buchstaben dort zuzuweisen, wo sie hingehören. Der Autor nahm (A) als das höherwertige Bit eines Drei-Bit-Binärwerts an, also repräsentiert es entweder oder ; nahm (B) als das mittlere Bit eines Drei-Bit-Binärwerts, so dass es entweder oder ; und nahm (C) als das niederwertige Bit eines Drei-Bit-Binärwerts, so dass es entweder oder . Eine Vielzahl unterschiedlicher Perspektiven würde gleich gut funktionieren. Aber das ist derjenige, den sie gewählt zu haben scheinen. $0\cdot 2^2=0$ $1\cdot 2^2=4$ $0\cdot 2^1=0$ $1\cdot 2^1=2$ $0\cdot 2^0=0$ $1\cdot 2^0=1$

Also begannen sie jetzt mit der ersten (linken) Stufe, legten (4) Muxes an, die von (A) gesteuert wurden, und blieben geistig bequem, indem sie diese Muxes als ABC = "x00", ABC = "x01", ABC = "x10" nummerierten. und für das untere ABC = "x11".

Da für das oberste ABC = "x00" bedeutet, bedeutet dies, dass entweder "000" = 0 oder "100" = 4 akzeptiert wird. Für den "0" -Eingang dieses Mux (mux1) haben sie in der Tabelle nach ABC = "000" = 0 gesucht und den Tabelleneintrag in den "0" -seitigen Eingang eingefügt. Für den "1" -Eingang dieses Mux haben sie in der Tabelle nach ABC = "100" = 4 gesucht und diesen Tabelleneintrag in den "1" -seitigen Eingang eingefügt. (Diese Tabelle sieht hier falsch aus, da sie in diesem Feld eine 0 sein sollte, was durch Betrachten der früheren erweiterten Spalten bestätigt wird.)

Der nächste Mux Down (Mux2) ist für ABC = "x10" und wird daher verwendet ABC = "010" = 2 und ABC = "110" = 6; der nächste Mux Down (Mux3) ist für ABC = "x01" und wird daher verwendet ABC = "001" = 1 und ABC = "101" = 5; und schließlich ist der letzte Mux Down (Mux4) für ABC = "x11" und verwendet daher ABC = "011" = 3 und ABC = "111" = 7.

Sowohl mux1 (ABC = "x00") als auch mux2 (ABC = "x10") werden gemeinsam mux5 zugeführt. Sie können hier sehen, dass B die Variation zwischen diesen ist, 0 oder 1, also haben sie sie hier angeschlossen. Die Ausgabe von mux5 ist ABC = "xy0", wobei die ersten beiden Bits bereits decodiert wurden und nur noch die Situation C = 0 decodiert werden muss. Der Ausgang von mux5 geht also zum Eingang "0" von mux7. In ähnlicher Weise werden mux3 (ABC = "x01") und mux4 (ABC = "x11") gemeinsam mux6 zugeführt. B ist wieder die Variation, zwischen der mux6 wählt. Der Ausgang von mux6 bezieht sich immer auf den Fall C = 1 und wird in den Eingang "1" von mux7 eingespeist.

Alles was bleibt ist, dass mux7 zwischen C = 0 und C = 1 wählt.

Jonk
quelle

Ich gebe zu, ich habe nie daran gedacht, die Formeln für den Mux zu verwenden, um mich zu führen. Ich kann manchmal ein bisschen unwissend sein, nehme ich an.

user1969903

@ user1969903: Es geht nur darum, deine Gedanken ein bisschen herumlaufen zu lassen. Lass dich nicht überraschen. Lehnen Sie sich einfach zurück und spielen Sie herum. Vielleicht finden Sie etwas Interessantes. Die Entdeckung selbst macht am meisten Spaß. Deshalb bin ich natürlich überhaupt hier und antworte. Ich habe auch etwas aus Ihrem Problem gelernt und ich habe das Gefühl genossen, damit zu spielen. Lerne einfach selbst damit umzugehen. Betrachten Sie es als ein Rätsel, das Sie lösen möchten. (Wenn Sie nicht in Rätsel sind, können Sie im falschen Bereich sein.)

Jonk

Nachdem ich Ihre Antwort studiert hatte, nahm ich mir die Zeit, die Formel für UND und ODER mit einem Mux abzuleiten, und implementierte die Funktion selbst. Ich war erfreut zu sehen, dass es genau so war, wie Sie es gepostet haben, aber auf den Kopf gestellt (ich habe die letzten beiden Eingänge umgekehrt angeschlossen, aber es ist immer noch korrekt). Wenn Sie ein wenig weiter damit spielen möchten, muss ich die Funktion jetzt nur mit Mux 2: 1 erneut implementieren, aber dieses Mal darf ich A, B, C oder E nicht als Eingaben für eine Datenleitung für eine verwenden der Muxes. Die einzigen Dateneingänge, die ich verwenden darf, sind logisch 0, logisch 1 und D.

user1969903

@ user1969903: Sollte wahrscheinlich entweder zu Ihrer aktuellen Frage hinzugefügt werden (damit eine Antwort von mir sinnvoller wäre) oder eine neue Frage erstellen. Im Moment werde ich noch ein paar M () -Bedingungen hinzufügen, die nicht schaden werden.

Jonk

Eigentlich habe ich es herausgefunden, aber ich bin mir nicht sicher, wie ich es hier teilen soll. Morgen, nachdem ich die Arbeit beendet habe, werde ich die ursprüngliche Frage bearbeiten und meine Version der Implementierung hinzufügen, damit jeder sie sehen und auch korrigieren kann, wenn sie falsch ist.

user1969903

Ein 2: 1-Mux enthält einen Inverter, zwei UND-Gatter und ein ODER-Gatter. Bei entsprechender Verkabelung können Sie es als UND-Gatter, ODER-Gatter, Wechselrichter und einige andere Funktionen verwenden. In der Tat basieren bestimmte Familien von FPGAs vollständig auf diesem Konzept.

Dies sollte ein Hinweis sein, der es Ihnen ermöglicht, beliebige Funktionen mit 2: 1-Muxen zu realisieren.

Dave Tweed
quelle

Ein Multiplexer mit zwei Eingängen verfügt über drei Eingänge (a, b und select). Überlegen Sie, wohin es degeneriert, wenn Sie zwei davon auswählen, und verdrahten Sie das andere fest mit "0" oder "1". Überlegen Sie, was passiert, wenn Sie zwei davon auswählen und die dritte mit einer der beiden verbinden. Grundsätzlich gibt es eine Reihe von Möglichkeiten, diesen Raum mit drei Eingaben in einen Raum mit zwei Eingaben zu entarten.

Ohne etwas so ausgefallenes zu tun, müssen Sie nur erkennen, dass Sie mit einem Multiplexer den Ausgabewert für Wahrheitstabellenzeilen, die den decodierten Auswahleingängen entsprechen, explizit festlegen können. Mit einem Multiplexer mit vier Eingängen (und daher zwei Auswahlbits) können Sie also eine beliebige boolesche Funktion mit zwei Eingängen darstellen, indem Sie die Eingänge einfach entsprechend fest verdrahten.

Darüber hinaus sollte klar sein, dass Sie einen 4: 1-Multiplexer aus drei 2: 1-Multiplexern, einen 8: 1-Multiplexer aus sieben 2: 1-Multiplexern usw. erstellen können, indem Sie eine Baumtopologie erstellen und die Auswahl entsprechend verdrahten. Stellen Sie einfach genug 2: 1-Multiplexer ab, um die Anzahl der benötigten Eingänge zu erhalten, und leiten Sie die Ausgänge paarweise in nachgeschaltete 2: 1-Multiplexer, bis Sie zu einem einzelnen Ausgang gelangen, und überlegen Sie, wie Sie die ausgewählten Eingänge verdrahten.

Sie können mit einer versteckten Variablen davonkommen, weil Sie nur 16 Intervalle haben, obwohl Sie eine 32-zeilige Wahrheitstabelle haben, und diese so gruppiert sind, dass ganze Teilbäume ignorierbar sind.

vicatcu
quelle