Der Darstellung boolescher Funktionen durch Formeln kann folgende „ingenieurtechnisch-konstruktive“ Bedeutung beigemessen werden. Wir betrachten eine Formel über einer willkürlich festgelegten Menge als „Black Box“, ein bestimmtes Gerät, dessen Eingang mit allen möglichen Mengen von Variablenwerten und am Ausgang mit den Werten der durch die Formel dargestellten Funktion versorgt wird entsprechenden Mengen erscheinen (Abb. 6.22).
Um zu verstehen, wie die „Black Box“ funktioniert, müssen wir den Prozess der Konstruktion einer Formel aus Unterformeln analysieren. Kommen wir zu den „grundlegenden“ Unterformeln, d.h. Elemente der Menge kommen wir zu den „Bricks“, den Strukturelementen, aus denen die „Black Box“ zusammengesetzt wird, und berechnen die Funktion. Jede „Basis“-Funktion wird vom entsprechenden „Knoten“ berechnet, der als kleinste Struktureinheit unserer „Black Box“ gilt, und seine interne Struktur wird nicht mehr analysiert.
Beispiel 6.22. Wählen wir eine Standardbasis als Menge. Dann wird die Formel über der Standardbasis, die die Funktion (Äquivalenz) darstellt, wie folgt aufgebaut:
Die Berechnung mit dieser Formel (und der Prozess ihrer Konstruktion aus Elementen der Standardbasis) kann schematisch wie in Abb. dargestellt dargestellt werden. 6.23.
Eine Variable (genauer gesagt der Wert dieser Variablen) wird dem Eingang eines Strukturelements namens Inverter zugeführt (Abb. 6.24, a) und berechnet die Negation. Das vom Wechselrichterausgang entfernte Minus, d.h. Funktion , wird einem der Eingänge des Konjunktors zugeführt (Abb. 6.24.5), dessen zweiter Eingang mit einer Variablen versorgt wird. Die Funktion erscheint am Ausgang des Konjunktors. Die Berechnung der Funktion kann auf ähnliche Weise nachvollzogen werden. Beide Funktionen werden den Eingängen des Disjunktors zugeführt (Abb. 6.24, c), von dessen Ausgang die Funktion entfernt wird (dies ist nichts anderes als die Summe modulo 2:). Und schließlich wird diese Funktion dem Eingang des Wechselrichters zugeführt, an dessen Ausgang bereits die Funktion (Äquivalenz) erhalten wird.
So kommen wir zur Idee eines „Schemas“ – eines mathematischen Modells eines Booleschen Funktionsrechners, dargestellt durch eine bestimmte Formel, zusammengesetzt aus Strukturelementen, von denen jedes eine der „grundlegenden“ Booleschen Funktionen berechnet. Im allgemeinen Fall berechnet die „Schaltung“ einen booleschen Operator und jede Koordinatenfunktion dieses Operators wird von einem der Ausgänge der Schaltung übernommen.
Mathematisch ist ein „Kreis“ als ein gerichteter Graph einer besonderen Art definiert, in dem sowohl Eckpunkte als auch Bögen mit einigen Beschriftungen versehen sind.
Führen wir die Notation ein: Wenn es sich um eine Menge boolescher Funktionen handelt, dann bezeichnen wir mit die Teilmenge, die aus allen Funktionen der Variablen besteht.
Definition 6.14. Die Mengen von (Booleschen Funktionen) und (Booleschen Variablen) seien fest.
Ein Schaltkreis funktionaler Elemente über einer Basis (SFE), oder einfach ein Schaltkreis über einer Basis, auch ein (F,X)-Schema, ist ein nicht konturgerichteter Graph (d. h. ein Netzwerk), dessen jeder Scheitelpunkt beschriftet ist mit einem der Elemente des Sets, sodass Folgendes erfüllt ist: Anforderungen:
1) Jeder Eingang des Netzwerks ist entweder durch eine Variable von oder durch eine Konstante von gekennzeichnet.
2) Wenn der Scheitelpunkt v des Netzwerks mit einer Funktion von Variablen (d. h.) beschriftet ist, dann ist sein halber Grad gleich, und auf der Menge der Bögen, die in den Scheitelpunkt eintreten, ist eine (eins-zu-eins) Nummerierung gegeben , bei dem jeder Bogen eine Zahl von 1 bis erhält.
Bei der Darstellung von Schaltkreisen werden Eingänge durch Kreise und Scheitelpunkte, die keine Eingänge sind, durch Dreiecke gekennzeichnet, in die die Bezeichnung der Funktion geschrieben wird, die diesen Scheitelpunkt markiert. Ausgänge sind mit „Ausgang“-Pfeilen gekennzeichnet. In Abb. Abbildung 6.25 zeigt den SFE über der Basis.
Wenn eine Basis impliziert ist, sagen wir einfach „Schema“. Wenn außerdem die Menge der Variablen „ein für alle Mal“ festgelegt ist und wir bei der Betrachtung verschiedener Schemata nur die Menge der Funktionen ändern, dann werden wir, wie wir es bei der Einführung der Konzepte der Formel und der Überlagerung auf einer bestimmten Basis getan haben, sprechen über SFE über die Basis, jedes Mal vorausgesetzt, was einen einmal festgelegten Satz von Variablen impliziert, der (wenn er die Präzision nicht beeinträchtigt) nicht erwähnt wird.
Definieren wir nun durch Induktion das Konzept einer Booleschen Funktion, die von einem Scheitelpunkt der Schaltung berechnet wird.
Definition 6.15. Es sei ein SFE über einer Basis gegeben, deren Eckpunktmenge ist.
1. Es wird davon ausgegangen, dass jeder Eingang des SFE die boolesche Funktion berechnet, mit der er markiert ist (d. h. eine Variable oder Konstante).
2. Wenn ein Scheitelpunkt mit einer Funktion beschriftet ist, kommt der Bogen, der mit der Zahl in ihn eintritt, von dem Scheitelpunkt, der die Funktion berechnet, dann berechnet Scheitelpunkt v die Überlagerung.
Wenn also jeder Scheitelpunkt des SFE eine bestimmte Funktion überrechnet, ist im allgemeinen Fall die Reihenfolge, in der die Funktionen aufgelistet und anstelle der Variablen der Funktion eingesetzt werden, von Bedeutung. Es ist natürlich, eine boolesche Funktion von Variablen kommutativ zu nennen, wenn sie ihren Wert bei jeder Permutation ihrer Variablen behält. In diesem Fall müssen wir uns nicht um die Nummerierung der Bögen kümmern, die in den durch eine solche Funktion markierten Scheitelpunkt des Diagramms eintreten.
Beispiel 6.23. Betrachten wir den SFE in Abb. 6.25. Die Eckpunkte und sind die Eingaben des SFE. Diese Eckpunkte berechnen die Funktionen bzw. Dann berechnet der Scheitelpunkt sowie der Scheitelpunkt gemäß Definition 6.15 die Funktion (Schaeffer-Strich) und der Scheitelpunkt (Netzwerkausgang) berechnet die Funktion, die bekanntermaßen gleich der Konjunktion ist.
SFE in Abb. 6.26, hat zwei Ausgänge, Berechnungsfunktionen und.
Definition 6.16. Boolesche Funktion, vom SFE über die Basis berechnet, ist eine Funktion, die von einem seiner Ausgänge berechnet wird.
Somit berechnet das SFE genau so viele boolesche Funktionen, wie es Ausgänge hat. SFE in Abb. 6.25 berechnet eine Funktion und das SFE in Abb. 6,26 - zwei.
Im allgemeinen Fall bestimmt das SFE die Abbildung eines booleschen Würfels in einen booleschen Würfel, wenn es sich um die Menge aller Variablen handelt, die als Bezeichnungen für die Eingänge einer Schaltung auf der Basis dienen, die sie ausgibt, d. h. Boolescher Operator.
Bemerkung 6.10. In einigen Fällen wird die von einem bestimmten SFE berechnete Funktion etwas anders definiert, vorausgesetzt, es handelt sich um eine Funktion, die von einem beliebigen Scheitelpunkt aus der Teilmenge ausgewählter Scheitelpunkte des SFE berechnet wird. Dabei kann es sich insbesondere um Ausgänge handeln. In jedem Fall sind wir damit einverstanden, einen „Ausgabe“-Pfeil von den ausgewählten (im gerade angegebenen Sinne) Eckpunkten des Diagramms zu zeichnen.
Somit berechnet jeder Schaltkreis aus Funktionselementen einen booleschen Operator. Insbesondere wenn die Anzahl der Ausgänge des Schaltkreises 1 beträgt, berechnet er eine boolesche Funktion.
Das Gegenteil kann auch bewiesen werden: Für jeden booleschen Operator kann ein SFE über der Basis konstruiert werden, wobei sich die vollständige Menge befindet, die diesen Operator auswertet.
Beispiel 6.24. Definieren wir einen booleschen Operator mit einer Tabelle, die auf (Tabelle 6.9) abgebildet wird.
Aus der Tabelle ist das leicht zu erkennen (die Funktion ist nichts anderes als eine Mehrheitsfunktion der Variablen, und der minimale DNF dafür ist oben angegeben, siehe Beispiel 6.12). Stellen wir uns die Funktion in der Zhegalkin-Basis vor. Mit den Gesetzen von De Morgan erhalten wir
In Anbetracht dessen werden wir es haben
(Denken Sie daran, dass die Summe Modulo 2 einer geraden Anzahl gleicher Terme 0 ist.) Also,
SFE für den in der Tabelle angegebenen booleschen Operator. 6.9, oben ist die Zhegalkin-Basis in Abb. dargestellt. 6.27.
Beim Entwurf eines SPV ist es sinnvoll, einen numerischen Parameter namens Komplexität im Auge zu behalten.
Die Komplexität des SFE ist die Anzahl seiner Eckpunkte, die keine Eingaben sind.
In Abb. dargestellt. 6.27 SFE über der Zhegalkin-Basis hat Komplexität 5.
Betrachten wir nun den SFE für denselben Betreiber auf Standardbasis. Mithilfe der Tabelle (siehe Tabelle 6.9) erstellen wir eine SDNF für die Funktion
Die Karnaugh-Karte für diese Funktion, dargestellt in Abb. 6.28 zeigt, dass es nicht minimiert werden kann (genauer gesagt ist der oben beschriebene SDNF der minimale DNF für diese Funktion).
Aber Sie können einen anderen Weg einschlagen. Wir können die Tabelle betrachten. 6.9 als Tabelle, die eine partielle boolesche Funktion definiert. Durch Minimierung dieser Funktion mithilfe der Karnaugh-Karte*, die in Abb. 6,29, wir bekommen
*Auf dieser Karte haben wir explizit die Mengen angegeben, auf denen die Funktion den Wert 0 annimmt, indem wir Nullen in die entsprechenden Zellen gesetzt haben. Daher möchten wir noch einmal darauf aufmerksam machen, dass Nullen nicht mit Bindestrichen verwechselt werden sollten: Ein Bindestrich in einer Zelle der Karte, die eine Teilfunktion definiert, bedeutet, dass der Wert der Funktion auf dieser Menge nicht definiert ist, d. h. ist weder 0 noch 1.
Der SFE über der Standardbasis für den betrachteten Booleschen Operator ist in Abb. dargestellt. 6.30 Uhr. Die Komplexität dieses SFE beträgt 11. Beachten Sie, dass der Scheitelpunkt, der die Funktion berechnet, nicht die Ausgabe ist.
Der in diesem Beispiel besprochene boolesche Operator berechnet die zweistellige Summe (Modulo 2) von drei einstelligen Termen. Man kann es sich auch als einen Einzelbit-Binäraddierer – den Funktionsblock eines Mehrbit-Binäraddierers – für zwei Terme vorstellen. Dann wird die r/1-Funktion als „Übertragungssignal“ zum höchstwertigen Bit interpretiert. In Abb. Abbildung 6.31 zeigt eine „Verbindung“ von drei SFEs (wie sie in Abb. 6.30 dargestellt sind), mit deren Hilfe die Summe zweier dreibitiger Binärzahlen berechnet wird. Der dritte Eingang des Addierers für das niederwertige Bit wird mit einer konstanten 0 versorgt, und das „Übertragssignal“ des höherwertigen Bits ist das höchstwertige Bit der Summe, die im allgemeinen Fall ein vierstelliges Bit sein wird. Bitnummer.
31. Schemata funktionaler Elemente, Konstruktions- und Betriebsregeln, Synthesemethode von SFE, basierend auf SDNF und SKNF.
DefinitionDefinition. Ein Funktionselement ist ein mathematisches Modell eines elementaren diskreten Wandlers, der nach einem bestimmten Gesetz die an seinem Eingang empfangenen Signale in das Signal am Ausgang des Wandlers umwandelt. Aus Funktionselementen ist es mit Hilfe bestimmter Regeln möglich, in Aufbau und Funktionsweise komplexere Modelle zu erstellen – Diagramme aus Funktionselementen. Bei diesen Modellen werden Ein- und Ausgangssignale mit den Symbolen 0 und 1 codiert.
Bauregeln. Um komplexe SFEs aus einfacheren zu erhalten, werden nacheinander die Vorgänge des Aufteilens des Eingangs oder Ausgangs der Schaltung, des Anbringens eines Funktionselements an die Schaltung und des Verbindens eines Funktionselements mit dem Eingang oder Ausgang der Schaltung auf sie angewendet. Diese Operationen ähneln den Regeln zum Erhalten einer komplexen Formel aus einfacheren durch Überlagerung.
Synthese von SFE. Da sich Disjunktion, Konjunktion und Negation bilden Vollständiges System in der Klasse R 2 , dann jede boolesche Funktion von N Argumente können durch eine Schaltung von Funktionselementen – Disjunktoren, Konjunktoren und Inverter – umgesetzt werden N Eingänge und einen Ausgang. Dazu können Sie beispielsweise eine bestimmte boolesche Funktion durch SDNF oder SCNF ausdrücken und dann die resultierende Formel in Form einer Schaltung aus Funktionselementen „synthetisieren“, indem Sie nacheinander die oben genannten Operationen des Teilens, Addierens und Verbindens anwenden.
32. Eine Methode zur Synthese von SFE, basierend auf der kompakten Implementierung aller Konjunktionen unter Verwendung eines universellen Multiport-Netzwerks, der Komplexität der resultierenden Schaltkreise.
Definition. Eine Funktion mit n Argumenten wird als Boolesche Funktion (oder Funktion der logischen Algebra) bezeichnet, wenn sie jeder Menge eine Zahl zuweist.
Um boolesche Funktionen anzugeben, verwenden wir Tabellen, Vektoren, Formeln und Grafiken. Akzeptieren wir die folgende Notation: – ist die Menge aller Mengen, wobei.
Definition. Ein Funktionselement ist ein mathematisches Modell eines elementaren diskreten Wandlers, der nach einem bestimmten Gesetz die an seinem Eingang empfangenen Signale in das Signal am Ausgang des Wandlers umwandelt. Aus Funktionselementen ist es mit Hilfe bestimmter Regeln möglich, in Aufbau und Funktionsweise komplexere Modelle zu erstellen – Diagramme aus Funktionselementen. Bei diesen Modellen werden Ein- und Ausgangssignale mit den Symbolen 0 und 1 codiert.
Eine Methode zur Synthese von SFEs, die auf der kompakten Implementierung aller Konjunktionen mithilfe eines universellen Multiport-Netzwerks basiert. Diese Methode basiert ebenfalls auf der Darstellung einer Funktion in Form von SDNF, ermöglicht jedoch den Aufbau weniger komplexer Schaltungen aufgrund einer kompakteren Implementierung von Konjunktionen. Die Erweiterung einer Funktion in SDNF kann Konjunktionen enthalten, die gemeinsame Faktoren haben. Wenn zwei solcher Konjunktionen durch eine Teilschaltung in einem Block implementiert werden, ist mindestens ein Konnektor weniger erforderlich als zuvor, wobei alle Konjunktionen unabhängig voneinander durch die erste Synthesemethode implementiert werden. Kompakte Implementierung aller möglichen Längenkonjunktionen N kann mit einem induktiv aufgebauten universellen Multiport-Netzwerk erreicht werden N Eingänge und 2 N Ausgänge wo N = 1,2,3,... Die Vorteile der Methode kommen besonders zum Tragen, wenn eine Schaltung ein System aus mehreren booleschen Funktionen implementieren muss. In diesem Fall wäre es möglich, die Ausgänge des universellen Multiport-Netzwerks, die den im SDNF enthaltenen Konjunktionen von Funktionen eines bestimmten Systems entsprechen, aufzuteilen und dann durch die Disjunktoren zu leiten. Dies würde es ermöglichen, weniger Konjunktoren zu verwenden, als wenn jede Funktion eines bestimmten Systems unabhängig von einer eigenen Unterschaltung implementiert würde.
Die Komplexität eines solchen Multiport-Netzwerks ist gleich L() =.
Wenn ein Schaltkreis aus Funktionselementen Σ genau enthält R funktionale Elemente, dann sagen sie, dass es Komplexität hat R und schreibe es als Gleichheit L(Σ) = R.
| " |
Vorlesung 2. Schaltungen funktionaler Elemente
(SFE) in gewisser Weise. Komplexität und Tiefe
planen. Beispiele. Methode zur Synthese von SFE unter Verwendung von DNP.
Dozentin - außerordentliche Professorin Selezneva Svetlana Nikolaevna
Vorlesungen zum Thema „Diskrete Mathematik 2“.
1. Jahr, Gruppe 141,
Fakultät für Computermathematik und Mathematik der Moskauer Staatlichen Universität, benannt nach M.V. Lomonossow
Vorträge auf der Website http://mk.cs.msu.su
SFE-Beispiele Synthese von SFE unter Verwendung von DNF
Schemata funktionaler Elemente
Definieren wir Schaltkreise von Funktionselementen auf einer bestimmten Grundlage.
Gegeben sei uns ein bestimmter Satz boolescher Funktionen B = (g1 (x1,..., xn1),..., gs (x1,..., xns)) P2, wobei n1,..., ns 0 ist .
Nennen wir diesen Satz eine Basis.
Beachten Sie, dass dieser Basisbegriff in keiner Weise mit dem Basisbegriff P2 zusammenhängt, der in der Algebra der Logik berücksichtigt wurde.
Als Regel betrachten wir die Standardbasis B0 = (x&y, x y, x ).
SFE-Beispiele Synthese von SFE unter Verwendung von DNF Definition eines Schaltkreises aus Funktionselementen Ein Schaltkreis aus Funktionselementen (SFE) in der Basis B0 = (x&y, x y, x) ist
1) ein gerichteter azyklischer Graph G = (V, E), dessen jeder Scheitelpunkt v V einen halben Grad d (v) hat, der zwei nicht überschreitet (d (v) 2);
2) jeder Scheitelpunkt v mit einem halben Grad gleich 0 (d (v) = 0) wird als Eingang (oder Schaltungseingang) bezeichnet und ihm wird eine boolesche Variable xi zugewiesen;
3) alle anderen Scheitelpunkte (außer Eingänge) werden interne Scheitelpunkte der Schaltung genannt;
4) jedem Scheitelpunkt v mit halbem Grad gleich 1 (d (v) = 1) wird ein (funktionales) Negationselement zugewiesen; alle solchen Eckpunkte werden Inverter genannt;
5) jedem Scheitelpunkt v mit halbem Grad gleich 2 (d (v) = 2) wird entweder ein (funktionales) Element der Konjunktion & oder ein (funktionales) Element der Disjunktion zugewiesen; alle Knoten, denen Elemente einer Konjunktion zugeordnet sind, heißen Konjunktoren, alle Knoten, denen Elemente einer Disjunktion zugeordnet sind, heißen Disjunktoren;
SFE-Beispiele Synthese von SFE mittels DNF Bestimmung eines Schaltkreises aus Funktionselementen (Fortsetzung)
6) Zusätzlich werden einigen Knoten paarweise unterschiedliche Ausgabevariablen y1,..., ym zugewiesen.
Wenn ein SFE S gegeben ist, dessen Eingängen nur Variablen x1,..., xn zugeordnet sind und mit Ausgangsvariablen y1,..., ym, dann bezeichnen wir dieses SFE mit S(x1,..., xn ; y1,... ., ym).
SFE-Beispiele Synthese von SFE unter Verwendung von DNF
– – –
Bestimmen der Tiefe des Scheitelpunkts des SFE Durch Induktion bestimmen wir die Tiefe d(v) des Scheitelpunkts v im SFE S.
1. Grundlagen der Induktion. Jeder Eingang v des SFE S hat eine Tiefe gleich 0: d(v) = 0.
– – –
SFEs und ihre Eigenschaften Schaltkreise aus Funktionselementen sind ein Rechenmodell.
Die von uns eingeführten SFE-Merkmale zeigen verschiedene Aspekte der Recheneffizienz.
Die Komplexität des SFE entspricht der Zeit der sequentiellen Berechnung.
Die Tiefe des SFE entspricht der parallelen Rechenzeit.
Die maximale Anzahl von Vertices mit gleicher Tiefe im SFE entspricht der Anzahl der Prozessoren bei paralleler Berechnung.
SFE-Beispiele Synthese von SFE mit DNF Beispiel: Summe von drei Bits Lösung. Schreiben wir ähnlich wie in Beispiel 6 eine Tabelle für die Summe der drei Bits x, y und z. Diese Summe kann auch eine Zahl mit zwei Binärziffern sein, daher führen wir zwei boolesche Variablen ein
u0, u1, so dass x + y + z = 2u1 + u0:
– – –
Literatur zur Vorlesung 4
1. Yablonsky S.V. Einführung in die diskrete Mathematik. M.:
Höhere Schule, 2001. Teil V, Kap. 2, S. 336-355.
2. Gavrilov G.P., Sapozhenko A.A. Probleme und Übungen zur diskreten Mathematik. M.: Fizmatlit, 2004. Kap. X 1,1, 1,5, 1,7, 1,17, 1,18.
SFE-Beispiele Synthese von SFE unter Verwendung von DNF
Der Darstellung boolescher Funktionen durch Formeln kann folgende „ingenieurtechnisch-konstruktive“ Bedeutung beigemessen werden. Wir betrachten die Formel Ф(x 1 ,..., x n) über einer willkürlich festgelegten Menge F als eine „Black Box“, ein bestimmtes Gerät, dessen Eingang mit allen möglichen Mengen von Variablenwerten versorgt wird, und am Geben Sie die Werte der Funktion f aus, die diesen Mengen entsprechen, dargestellt durch die Formel Ф (Abb. 6.22).
Um zu verstehen, wie die „Black Box“ funktioniert, müssen wir den Prozess der Konstruktion einer Formel aus Unterformeln analysieren. Kommen wir zu den „grundlegenden“ Unterformeln, d.h. Elemente der Menge F kommen wir zu den „Bricks“, den Strukturelementen, aus denen die „Black Box“ zusammengesetzt wird, und berechnen die Funktion f. Jede „Basis“-Funktion F wird vom entsprechenden „Knoten“ berechnet, der als kleinste Struktureinheit unserer „Black Box“ betrachtet wird, und seine interne Struktur wird nicht mehr analysiert.
Beispiel 6.22. Wählen wir eine Standardbasis als Menge F. Dann wird die Formel über der Standardbasis, die die Funktion ~ (Äquivalenz) darstellt, wie folgt aufgebaut:
Die Berechnung mit dieser Formel (und der Prozess ihrer Konstruktion aus Elementen der Standardbasis) kann schematisch wie in Abb. dargestellt dargestellt werden. 6.23.
Die Variable x 1 (genauer gesagt der Wert dieser Variablen) wird dem Eingang eines Strukturelements namens Inverter zugeführt (Abb. 6.24, a) und berechnet die Negation. Das Minus x 1 wird vom Wechselrichterausgang entfernt, d.h. Funktion x 1 wird einem der Eingänge des Konjunktors zugeführt (Abb. 6.24, b), dessen zweiter Eingang der Variablen x 2 zugeführt wird. Am Ausgang des Konjunktors erscheint die Funktion x 1 x 2. Die Berechnung der Funktion x 1 x 2 lässt sich auf ähnliche Weise verfolgen. Beide Funktionen werden den Eingängen des Disjunktors zugeführt (Abb. 6.24, c), aus dessen Ausgang die Funktion x 1 x 2 ∨ x entsteht 1 x 2 wird entfernt (das ist nichts anderes als die Summe Modulo 2: x 1 ⊕ x 2). Und schließlich wird diese Funktion dem Eingang des Wechselrichters zugeführt, an dessen Ausgang bereits die Funktion ~ (Äquivalenz) erhalten wird. #
So kommen wir zur Idee eines „Schemas“ – eines mathematischen Modells eines Booleschen Funktionsrechners, dargestellt durch eine bestimmte Formel, zusammengesetzt aus Strukturelementen, von denen jedes eine der „grundlegenden“ Booleschen Funktionen berechnet. Im allgemeinen Fall berechnet die „Schaltung“ einen booleschen Operator und jede Koordinatenfunktion dieses Operators wird von einem der Ausgänge der Schaltung übernommen.
Mathematisch ist ein „Kreis“ als ein gerichteter Graph einer besonderen Art definiert, in dem sowohl Eckpunkte als auch Bögen mit einigen Beschriftungen versehen sind.
Führen wir die Notation ein: Wenn F eine Menge boolescher Funktionen ist, dann bezeichnen wir mit F (n) eine Teilmenge von F, die aus allen Funktionen von n Variablen (n≥0) besteht.
Definition 6.14. Die Mengen F (Boolesche Funktionen) und X (Boolesche Variablen) seien fest.
Ein Schaltkreis aus Funktionselementen über der Basis F ∪ X (S F E), oder einfach ein kontrahiertes F ∪ X über einer Basis, auch ein (F, der Elemente der Menge F U X so, dass folgende Anforderungen erfüllt sind:
- Jeder Eingang des Netzwerks ist entweder durch eine Variable aus X oder durch eine Konstante aus F (0) gekennzeichnet.
- Wenn ein Scheitelpunkt v eines Netzwerks durch eine Funktion f von n Variablen gekennzeichnet ist (d. h. f ∈ F (n)), dann ist sein halber Grad gleich n, und auf der Menge der Bögen, die in den Scheitelpunkt v eintreten, ist a (eins). Die Nummerierung erfolgt so, dass jeder Bogen eine Zahl von 1 bis n erhält.
Wenn eine Basis impliziert ist, sagen wir einfach „Schema“. Wenn außerdem die Menge der Variablen „ein für alle Mal“ festgelegt ist und wir bei der Betrachtung verschiedener Schemata nur die Menge der Funktionen F ändern, werden wir dies tun, wie wir es bei der Einführung der Konzepte der Formel und der Superposition über eine gegebene Basis getan haben Sprechen Sie über SFE über der Basis F und setzen Sie jedes mal, was einen einmal festgelegten Satz von Variablen X impliziert, der (wenn es die Genauigkeit nicht beeinträchtigt) nicht erwähnt wird.
Definieren wir nun den Begriff durch Induktion Boolesche Funktion, berechnet durch den Scheitelpunkt der Schaltung .
Definition 6.15. Der SFE sei gegeben S über einer Basis F ∪ X, deren Eckpunktmenge V ist.
- Es wird davon ausgegangen, dass jeder Eingang des SFE die boolesche Funktion berechnet, mit der er markiert ist (d. h. eine Variable oder Konstante).
- Wenn ein Scheitelpunkt v ∈ V mit einer Funktion f ∈ F (n) beschriftet ist, kommt der in ihn eintretende Bogen mit der Nummer i (1≤i≤n) vom Scheitelpunkt u i ∈ V, der die Funktion g i auswertet, dann vom Scheitelpunkt v wertet die Überlagerung f(g 1 , ... ,g n) aus.
Wenn also jeder Scheitelpunkt des SFE über F eine bestimmte Funktion berechnet, dann ist im allgemeinen Fall die Reihenfolge, in der die Funktionen g 1 , ... , g n aufgelistet und durch die Variablen der Funktion f ersetzt werden, von Bedeutung. Es ist natürlich, eine boolesche Funktion f von n Variablen kommutativ zu nennen, wenn sie ihren Wert bei jeder Permutation ihrer Variablen behält. In diesem Fall müssen wir uns nicht um die Nummerierung der Bögen kümmern, die in den durch eine solche Funktion markierten Scheitelpunkt des Diagramms eintreten.
Beispiel 6.23. Betrachten wir den SFE in Abb. 6.25. Die Eckpunkte v 1 und v 2 sind die Eingaben des SFE. Diese Eckpunkte berechnen die Funktionen x bzw. y. Dann berechnet der Scheitelpunkt v 3 sowie der Scheitelpunkt v 4 gemäß Definition 6.15 die Funktion x|y (Schaeffer-Strich) und der Scheitelpunkt v 5 (Netzwerkausgabe) berechnet die Funktion (x|y)l(x|y). , die bekanntlich gleich der Konjunktion x · y ist.
SFE in Abb. 6.26 hat zwei Ausgänge, die die Funktionen (x|x)|(y|y) =x ∨ y und (x|y)|(x|y) =x·y berechnen.
Definition 6.16. Von SFE berechnete boolesche Funktion über der Basis F ∪ X ist eine Funktion, die durch eine ihrer Ausgaben berechnet wird.
Somit berechnet SFE genau so viele boolesche Funktionen, wie es Ausgänge hat. SFE in Abb. 6.25 berechnet eine Funktion und das SFE in Abb. 6,26 - zwei.
Im Allgemeinen gilt, wenn (x 1 ,..., x n ) die Menge aller Variablen ist, die als Beschriftungen der Schaltkreiseingänge dienen S über der Basis F ∪ X, mit m Ausgängen, SFE S Definiert die Anzeige eines booleschen Würfels B n zum Booleschen Würfel B m, d.h. Boolescher Operator.
Bemerkung 6.10. In einigen Fällen wird die von einem bestimmten SFE berechnete Funktion etwas anders definiert, vorausgesetzt, es handelt sich um eine Funktion, die von einem beliebigen Scheitelpunkt aus der Teilmenge ausgewählter Scheitelpunkte des SFE berechnet wird. Dabei kann es sich insbesondere um Ausgänge handeln. In jedem Fall sind wir damit einverstanden, einen „Ausgabe“-Pfeil von den ausgewählten (im gerade angegebenen Sinne) Eckpunkten des Diagramms zu zeichnen. #
Somit berechnet jeder Schaltkreis aus Funktionselementen einen booleschen Operator. Insbesondere wenn die Anzahl der Ausgänge des Schaltkreises 1 beträgt, berechnet er eine boolesche Funktion.
Auch das Gegenteil kann bewiesen werden: Für jeden booleschen Operator kann ein SFE über einer Basis F konstruiert werden, wobei F die vollständige Menge ist, die diesen Operator auswertet.
Stellen wir die Funktion y 1 in der Zhegalkin-Basis dar. Mit den Gesetzen von De Morgan erhalten wir
(Denken Sie daran, dass die Summe Modulo 2 einer geraden Anzahl gleicher Terme 0 ist.)
y 1 = x 1 x 2 ⊕ x 1 x 3 ⊕ x 2 x 3 = x 1 x 2 ⊕ x 3 (x 1 ⊕ x 2).
SFE für den in der Tabelle angegebenen booleschen Operator. 6.9, oben ist die Zhegalkin-Basis in Abb. dargestellt. 6.27.
Beim Entwurf eines SPV ist es sinnvoll, einen numerischen Parameter namens Komplexität im Auge zu behalten.
Komplexität von SFE ist die Anzahl seiner Eckpunkte, die keine Eingaben sind.
In Abb. dargestellt. 6.27 SFE über der Zhegalkin-Basis hat Komplexität 5.
Betrachten wir nun den SFE für denselben Betreiber auf Standardbasis.
Mithilfe der Tabelle (siehe Tabelle 6.9) konstruieren wir den SDNF für die Funktion y 2:
y 2 = x 1 x 2 x 3 ∨ x 1 x 2 x 3 ∨ x 1 x 2 x 3 ∨ x 1 x 2 x 3 .
Die Karnaugh-Karte für diese Funktion, dargestellt in Abb. 6.28 zeigt, dass es nicht minimiert werden kann (genauer gesagt ist der oben beschriebene SDNF der minimale DNF für diese Funktion). Aber Sie können einen anderen Weg einschlagen. Wir können die Tabelle betrachten. 6.9 als Tabelle, die die boolesche Teilfunktion y 2 = y 2 (x 1 x 2 x 3 y 1) definiert. Durch Minimierung dieser Funktion um
Carnot-Karte* in Abb. 6,29, wir bekommen
* Auf dieser Karte haben wir die Mengen angegeben, auf denen die Funktion den Wert 0 annimmt, und Nullen in die entsprechenden Zellen eingefügt. Daher möchten wir noch einmal darauf aufmerksam machen, dass Nullen nicht mit Bindestrichen verwechselt werden sollten: Ein Bindestrich in einer Zelle der Karte, die eine Teilfunktion definiert, bedeutet, dass der Wert der Funktion auf dieser Menge nicht definiert ist, d. h. ist weder 0 noch 1.
y 2 = x 1 x 2 x 3 ∨ y 1 (x 1 ∨ x 2 ∨ x 3).
Der SFE über der Standardbasis für den betrachteten Booleschen Operator ist in Abb. dargestellt. 6.30 Uhr. Die Komplexität dieses SFE beträgt 11. Beachten Sie, dass der Scheitelpunkt, der die Funktion y 1 auswertet, keine Ausgabe ist.
Der in diesem Beispiel besprochene boolesche Operator berechnet die zweistellige Summe (Modulo 2) von drei einstelligen Termen. Man kann es sich auch als einen Einzelbit-Binäraddierer – den Funktionsblock eines Mehrbit-Binäraddierers – für zwei Terme vorstellen. Dann wird die Funktion y 1 als „Übertragssignal“ zum höchstwertigen Bit interpretiert. In Abb. Abbildung 6.31 zeigt eine „Verbindung“ von drei SFEs (wie sie in Abb. 6.30 dargestellt sind), mit deren Hilfe die Summe zweier dreibitiger Binärzahlen berechnet wird. Der dritte Eingang des Addierers für das niederwertige Bit wird mit einer konstanten 0 versorgt, und das „Übertragssignal“ des höherwertigen Bits ist das höchstwertige Bit der Summe, die im allgemeinen Fall ein vierstelliges Bit sein wird. Bitnummer.
Bemerkung 6.11. Wenn wir ein SFE auf Standardbasis entwerfen und dessen Komplexität minimieren möchten, müssen wir zunächst die entsprechende minimale DNF konstruieren. In diesem Fall können wir ein weiteres Kriterium berücksichtigen, nach dem der DNF selbst minimiert wird – die Anzahl der Negationen. Unter allen minimalen (im Sinne von Definition 6.6) DNFs sollten wir diejenigen auswählen, bei denen die Häufigkeit des Vorkommens von Variablen unter dem Negationszeichen am geringsten ist. Unter dem Gesichtspunkt der Komplexität des SFE, das mit der minimalen DNF erstellt wird, bedeutet dies, dass die Anzahl der „Inverter“ – der mit der Negationsfunktion markierten Eckpunkte des SFE – minimiert wird.
Beispielsweise sollte man für eine durch eine Carnaugh-Karte gegebene Funktion (Abb. 6.32) zu dem Kern, der aus den Primimplikanten x 1 x 2 x 4 und x 1 x 3 x 4 besteht, den Primimplikanten x 2 x 3 x 4 hinzufügen statt x 1 x 2 x 3, da es keine Negationen enthält.
Funktionsdiagramme (FC) dienen der Umwandlung logischer Informationen. Hintergrundinformation, kodiert als diskrete Signale, den Eingängen der Schaltung zugeführt `x n. Dann diese Information verarbeitet und in diskreter Form von den Schaltungsausgängen gelesen `y m(n, m– die Anzahl seiner Ein- und Ausgänge). Betrachten wir FS, das in zweiwertiger Logik arbeitet und einen Ausgang hat ( M=1). Die Umwandlung von Informationen in sie kann als Funktion der logischen Algebra angegeben werden bei=F(x n). Anstelle von Relaiselementen verwendet das FS Funktionselemente (FE), die in der Regel elementare logische Funktionen implementieren.
Definition.Analyse heißt die Konstruktion einer logischen Algebraformel (ggf. ihrer Wahrheitstabelle) gemäß einem gegebenen FS.
Um eine Formel nach einem vorgegebenen Schema zu konstruieren, ist es notwendig, die Verbindungen zwischen FEs im FS in Form von Substitutionen in die entsprechenden Elementarfunktionen darzustellen. Es wird davon ausgegangen, dass Informationen stufenweise vom Input bis zum Output verarbeitet werden. In realen Systemen werden zusätzliche Elemente verwendet, um die zeitliche Koordinierung des Betriebs aller FS sicherzustellen.
Die FS-Analyse kann auf zwei Arten durchgeführt werden – von Eingaben zu Ausgaben und von Ausgaben zu Eingaben. Betrachten wir die erste Methode und verwenden zusätzliche Notation für Zwischenverbindungen in der Schaltung.
Beispiel 1.(& ,Ú ,Ø) werden als FEs angenommen. Führen Sie eine Analyse des FS durch, dessen physikalische Struktur in Abb. 1.19 dargestellt ist.
Lösung. Nachdem wir die PV-Zwischenanschlüsse wie in der Abbildung gezeigt gekennzeichnet haben, ermitteln wir Schritt für Schritt die entsprechenden Signale . In diesem Fall bewegen wir uns von den Eingängen der Schaltung zu ihrem Ausgang.
Abb.1.19
SCHRITT 1. R=`y, Q = `z.
SCHRITT 2. X=X&R= X&`y, P=X& y, W=P&Q= X&j&`z.
SCHRITT 3. Y=X&z=X&`y& z, U=P&z = X&j&z.
SCHRITT 4. Z = YÚ U=X&`y&zÚ X&j&z.
SCHRITT 5. F = ZÚ W=X&`y& zÚ X&j&zÚ X&j&`z.
Somit implementiert das betrachtete FS die folgende logische Algebra-Formel:
F(X,j,z) = X&`y&zÚ X&j&zÚ X&j&`z.
Die gefundene Formel ist SDNF. Der Vektor seiner Wahrheitswerte hat die Form (00000111) .
Abhängig von den Ausgangsdaten können wir unter den Aufgaben der Synthese (Gestaltung) eines FS unterscheiden:
1) Synthese von Schaltkreisen nach vorgegebenen Formeln,
2) Synthese von Schaltkreisen nach vorgegebenen Funktionen.
Definition.Synthese von PS nach einer vorgegebenen Formel bezeichnet die Konstruktion einer FS-Struktur, die einer gegebenen Formel der Algebra der Logik entspricht.
Solche Probleme werden mit einem zur Analysemethode inversen Algorithmus gelöst. Wie in Abschnitt 1.7 erwähnt, ermöglicht die Struktur der Formeln der logischen Algebra die isomorphe Darstellung nur von Systemen mit parallelen und serielle Verbindungen Elemente. Daher sollte die zur entsprechenden Formel isomorphe FS nur Verbindungen dieses Typs enthalten.
Definition.Synthese von FS gemäß einer vorgegebenen Funktion Bau genannt Blockdiagramm, Implementierung einer gegebenen logischen Algebrafunktion.
Da die Darstellung von Funktionen durch Formeln nicht eindeutig ist, gibt es für dieses Problem eine nicht eindeutige Lösung. Wie bei Relaisschaltungen sind FSs optimal, die aus einer minimalen Anzahl von FEs und Verbindungen zwischen ihnen bestehen. Eine solche FS kann mithilfe von Formeln mit einer minimalen Anzahl von Variablen ermittelt werden.
Was RS betrifft, werden wir die Formeln, die in der Klasse optimal sind, separat betrachten Normalformen(die den entsprechenden Minimalformen entsprechen) sowie absolut optimale Formeln, die aus minimalen Normalformen durch weitere Reduzierung unter Verwendung der Gesetze der logischen Algebra erhalten werden. Die Methoden zum Erhalten optimaler Formeln sind die gleichen wie in Relaisschaltungen. Beispiel 1 betrachtet ein Dateisystem, das die Funktion (00000111) implementiert. . Dieser FS ist nicht optimal, da die entsprechende Formel den SDNF beschreibt F = x`y z Ú x y zÚ x y`z, was nicht minimal ist. Durch Minimierung erhalten wir eine MDNF der folgenden Form: F = x yÚ x z. Es entspricht dem FS in Abb. 1.20
Abb.1.20
Wenn wir das Verteilungsgesetz auf MDNF anwenden, erhalten wir eine Formel mit einer noch geringeren Anzahl von Variablen: F = X(jÚ z). Für diese Funktion stimmte es mit der ICNF überein. Es entspricht dem absolut optimalen Schema
Abb.1.21
Offensichtlich ist dieses Schema viel einfacher als das Original (Abb. 1.19). Da die Synthese optimaler FS auf die Konstruktion minimaler Formeln reduziert wird, werden optimale Schemata auf ähnliche Weise auf anderen Grundlagen konstruiert. Analoga des ersten und zweiten Verteilungsgesetzes der Algebra der Logik für Sheffer- und Webb-Formen können durch Ersetzen in diesen Gesetzen erhalten werden:
&(X,j)= Ø ½ ( X,j) = ¯ (Ø X,Ø j);
Ú ( X,j)= ½ (Ø X, Ø j) =Ø ¯ ( X,j).
Beispiel 2. Konstruieren Sie ein FS, das einen Ein-Bit-Binäraddierer zweier Zahlen unter Verwendung von FEs implementiert, die der Basis (Ø,¯) sowie in der Basis (¯) entsprechen.
Lösung. Bezeichnen wir einstellige Binärzahlen, die dem Eingang zugeführt werden, mit ( X,bei). Die Ausgabe sollte ihre Summe sein binäres System. Wenn x= 1, y= 1, dann S = 2 10 = 10 2, daher ist es zur Darstellung im allgemeinen Fall notwendig, zwei Binärzeichen zu verwenden, und der FS muss zwei Ausgänge haben. Bezeichnen wir sie F(höchste Ziffer des Betrags) und G(Juniorrang). Wahrheitstabellen von Funktionen F (X,bei),G(X,bei):
| X | j | F(X,j) | G(X,j) |
Wir konstruieren SVNF-Funktionen in der Basis (Ø ,¯). F hat eine Einheit in seinem Wahrheitsvektor, daher besteht seine Form aus einem Konstituenten: F=¯ (Ø x,Ø bei). Funktion G SVNF hat die Form: G=د(¯( X,Ø bei),¯(Ø X,bei)). Diese Formen sind minimal. Bei der Kombination der Eingänge der Elemente lässt sich das Funktionsdiagramm wie folgt darstellen:
Abb.1.22
Im betrachteten Beispiel ist es unmöglich, Webb-Normalformen mithilfe der Gesetze der logischen Algebra zu vereinfachen. In der Einzelfunktionsbasis (¯) erhalten wir die FS durch die Substitution Ø X= ¯ ( X,X). Das entsprechende Diagramm ist in Abb. 1.23 dargestellt.
Abb.1.23
AUFGABEN
1. Konstruieren Sie mit FE (& ,Ú ,Ø ) optimale in der Klasse der Normalformen und absolut optimale FS, die die folgenden Funktionen implementieren:
A) ( X® j)Å zy;B)( XÅ j)|z,V) xy® yz;G) X|(jÚ z);e) X®( j® z) ;
f) (10011101) ;g) (01101011) ;h) (1110101111111110) .
2. Konstruieren Sie mit FE (Ú,Ø )FS der Funktionen 1.a) -g).
3. Konstruieren Sie mit FE (&,Ø )FS der Funktionen 1.a)-g).
4. Konstruieren Sie ein FS, das einen Ein-Bit-Binäraddierer (Beispiel 2) implementiert, indem Sie ein FE der folgenden Form verwenden:
a)(& ,Ú ,Ø), b) (Ú ,Ø ) , c) (& ,Ø), d) ( x| j} .
5. Erstellen Sie mit FE (& ,Ú ,Ø ) ein FS aus den folgenden Geräten:
a) Wandler mit Binäreingängen ( X,bei) und beenden F, was so funktioniert: beim Absenden x= 0Ausgabe F =bei, und beim Absenden x = 1 am Eingang F =`du;
b) ein selektives Gerät mit Binäreingängen ( X,bei) und beendet F 0 , F 1 , F 2 , F 3, die eine Kombination von Werten als Eingabe erhält ( x y) Wie Binärzahlich, liegen im Bereich von 0 bis 3. Die Ausgabewerte für jeden ich die folgende: f i= 1 und alle anderen f j= 0, (0 £ J£3, J¹ ich).
6. Ist es möglich, die folgenden Funktionssätze als Grundlage für den Aufbau eines FS zu verwenden:
a) (1001),(10001110),
b) (0101),(1011),(1101),
c) (1010),(01110001)?
Begründen Sie die Antwort.
7. Nennen Sie Beispiele für Steuerfunktionen, deren FS nicht allein aus FEs vom Typ (®) konstruiert werden können.
8. Nennen Sie Beispiele für Kontrollfunktionen, deren FS nicht allein aus FEs des Typs ( Å , º ) konstruiert werden kann.
9. Gegeben sei ein FS aus FE (& ,Ú ,Ø ).
Abb.1.24
Ist es möglich, durch äquivalente Transformationen davon auszuschließen:
a) alle Elemente (Ø)?
b) alle Elemente (&)?
c) alle Elemente (Ú)?
10. Optimieren Sie das FS anhand der FE (& ,Ú ,Ø ), dargestellt in Abb. 1.25.
Abb.1.25
FS erstellen:
a) optimal in der Klasse der Normalformen und
b) absolut optimal.