fakultät für informatik - Lehrstuhl für Rechnertechnik und

FAKULTÄT FÜR INFORMATIK
TECHNISCHE UNIVERSITÄT MÜNCHEN
Lehrstuhl für Rechnertechnik und Rechnerorganisation
Prof. Dr. Arndt Bode
Einführung in die Rechnerarchitektur
Wintersemester 2015/2016
Zentralübung 9
18.12.2015
Lösungsvorschlag Aufgabe 9.1
Aufgabenstellung
Sei f : {0, 1}n → {0, 1} eine eindimensionale Schaltfunktion von n Variablen (0 steht für falsch
und 1 steht für wahr ).
Zunächst soll herausgefunden werden, wieviele eindimensionale Schaltfunktionen mit n Argumenten prinzipiell existieren.
Grundidee: Betrachten wir uns eine Wahrheitstabelle für eine Schaltfunktion mit n Argumenten:
x1
0
0
..
.
x2
0
0
1
1
1
1
···
···
···
···
···
xn−1
0
0
1
1
xn
0
1
..
.
0
1
f
2n
Ergebnisbits
Um alle Schaltfunktionen darzustellen, müsste man nun lediglich für alle Kombinationen von
n
Ergebnisbits eine eigene Tabelle erstellen. Durch Nachrechnen erkennt man leicht, dass dies 2(2 )
Tabellen bzw. n-dimensionale Schaltfunktionen wären. (Um alle Kombinationen der jeweils 2n
n
Ergebnisbits zu erhalten, benötigt man insgesamt 2(2 ) unterschiedliche Funktionen.)
Im zweiten Teil der Aufgabe sollen nun alle zweidimensionalen Schaltfunktionen in einer Tabelle
aufgeschrieben werden. Da die Parameterwerte für jede Funktion gleich sind, erweitern wir
2
einfach eine Wahrheitstabelle auf 2(2 ) = 16 Ergebnisspalten:
1
e1 e2
0 0
0 1
1 0
1 1
Bez.
a
0
0
0
0
0
0
0
1
·
0
0
1
0
0
0
1
1
e1
0
1
0
0
0
1
0
1
e2
0
1
1
0
⊕
0 1 1
1 0 0
1 0 0
1 0 1
+ + ⊕
1
0
1
0
e2
1
0
1
1
1
1
0
0
e1
1
1
0
1
1
1
1
0
·
1
1
1
1
Wie leicht zu erkennen ist, finden sich die Grundoperationen UND, ODER, die Negation sowie
die Exklusiv-ODER-Funktion (durch das Symbol ⊕ angedeutet) in dieser Tabelle wieder.
Antworten auf die Fragen im Text
+ Was wird mit dem Involutionsgesetz, dem Kommutativitätsgesetz und dem Assoziativitätsgesetz ausgedrückt?
Involution:
(f ) = f
f ·g =g·f
Kommutativität:
Assoziativität:
(f · g) · h = f · (g · h)
und f + g = g + f
und
(f + g) + h = f + (g + h)
+ Was versteht man unter Idempotenz und Absorption?
Idempotenz:
f ·f =f
und
f +f =f
Absorption:
f · (f + g) = f
und
f + (f · g) = f
Interessant ist bei diesen Gesetzen die Tatsache, dass sie es ermöglichen, gezielt Redundanz
( unnötige“ Information) in eine Schaltfunktion einzubauen oder aus ihr zu entfernen.
”
+ Was ist die besondere Eigenschaft des Distributivitätsgesetztes der booleschen Algebra
verglichen z. B. mit der Algebra der reellen Zahlen?
Das Distributivitätsgesetz in der booleschen Algebra funktioniert im Gegensatz zur Algebra
reeller Zahlen für beide Operationen UND und ODER, während sonst nur das Ausmultipli”
zieren“ bzw. Ausklammern“ definiert sind:
”
Distributivität:
f · (g + h) = f · g + f · h und
f + (g · h) = (f + g) · (f + h)
Auch wenn also die Schreibweisen · und + an elementare Algebra erinnern, muss man sich die
Unterschiede z. B. beim Distributivitätsgesetz stets vor Augen halten.
2
+ Skizzieren Sie die De Morgansche Regel.
de Morgan: f · g = f + g
und
f +g =f ·g
Das Bemerkenswerte an dieser Regel ist, dass sie es uns ermöglicht, Ausdrücke, die beispielsweise auf UND-Verknüpfungen basieren, auch durch ODER-Verknüpfungen zu beschreiben.
Darüberhinaus ist die De Morgansche Regel auch als ein Hinweis darauf zu verstehen, dass man
im Extremfall lediglich einen NICHT-ODER-Operator (NOR) oder eine NICHT-UND-Operator
(NAND) benötigt, um damit alle Operationen der booleschen Algera zu verwirklichen.
+ Was besagt das Neutralitätsgesetz?
Neutralität:
f · (g + g) = f
und
f + (g · g) = f
Genau wie oben hilft uns das Neutralitätsgesetz beim Vereinfachen oder auch bewussten Vergrößern von Schaltfunktionen.
+ Warum ist die Wahrheitstabelle nicht für alle möglichen Gelegenheiten eine günstige Darstellungsform?
Der Platzbedarf einer Wahrheitstabelle (in Zeilen) wächst exponentiell mit der Anzahl ihrer Parameter. Eine Schaltfunktion mit 16 Parametern würde demnach 216 = 65536 Zeilen benötigen.
+ Wann ist eine DNF günstiger als eine KNF und umgekehrt? Hat dies auch technische
Auswirkungen?
Eine DNF bzw. eine KNF lassen sich direkt in zweistufige Schaltnetze umwandeln. Die UNDverknüpften Minterme der DNF in Form von UND-Schaltnetzen (auch UND-Gatter genannt)
bilden dabei die erste Stufe, die dann über ein ODER-Gatter zusammengeschaltet werden
können. Folgende Darstellung erhält man daher für DNF bzw. KNF:
Disjunktive Normalform
Konjunktive Normalform
e1
e1
&
>= 1
en
en
>= 1
a
&
e1
e1
&
>= 1
en
en
erste Stufe
(UND-Gatter)
zweite Stufe
(ODER-Gatter)
erste Stufe
(ODER-Gatter)
3
zweite Stufe
(UND-Gatter)
a
Eine DNF ist also günstiger, wenn die Einsmenge einer Schaltfunktion weniger mächtig als
die Nullmenge ist. Technisch ausgedrückt bedeutet dies, dass man weniger UND-Gatter in der
ersten Stufe des Schaltnetzes benötigt als ODER-Gatter in einer KNF-Umsetzung nötig wären.
Zudem wird die Anzahl der Eingänge in das ODER-Gatter der zweiten Stufe verringert. Dual
gilt dies natürlich entsprechend.
+ Wandeln sie die DNF von f in eine KNF um.
+ Wandeln sie die KNF von g in eine DNF um.
f (x, y, z) = xyz + xyz
= xz · (y + y)
(1)
(2)
Während also f zuvor über die Minterme xyz und xyz beschrieben war, ist es nun über die
Maxterme x, z, und y + y ausgedrückt. (Natürlich lässt sich der letzte Ausdruck noch vereinfachen . . . )
g(x, y, z) =
=
=
=
=
=
=
(x + y + z) · (x + y + z) · (x + y + z)
z + (x + y) · (x + y) · (x + y)
z + (xx + xy + xy + yy) · (x + y)
z + (x + xy + xy) · (x + y)
z + (xx + xy + xx y + xyy + xyx + xyy)
z + (xy + xy)
z + xy
(3)
(4)
(5)
(6)
(7)
(8)
(9)
Schaltfunktion g ist somit nun durch die Minterme z und xy ausgedrückt. (Es ist hilfreich,
sich klarzumachen, welche Gesetze bei den jeweiligen Umformungen verwendet wurden. Als
Hinweis bei den Vereinfachungen vergegenwärtige man sich Idempotenz, Distributivität und
Neutralität.)
Lösungsvorschlag Aufgabe 9.2
Zunächst sollte die Funktionstabelle für die einzelnen Personen aufgestellt werden, um zu ermitteln, wann sie granteln. Daraus kann man dann ermitteln, zu welchen Gelegenheiten Ruhe
herrscht.
Die ersten vier Spalten geben die Kombination der Anwesenheit der vier beteiligten Personen
an. Die folgenden vier Spalten sind aus den Bedingungen abgeleitet, die für das Granteln der
einzelnen Personen angegeben sind. Aus einer einfachen NICHT-ODER-Verknüpfung (NOR)
erhält man dann als letze Spalte die Schaltfunktion, die die Ruhe im Raum angibt.
4
Anwesenheit
A
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
F
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
P
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
B
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
Granteln bei Ruhe
Anwesenheit
A F P B
R
0 0 0 0
1
0 0 0 1
0
0 0 0 0
1
0 0 0 1
0
0 0 0 0
1
0 0 0 1
0
0 0 0 0
1
0 0 0 1
0
1 0 0 0
0
1 0 0 1
0
1 0 0 0
0
1 0 0 1
0
0 0 0 0
1
0 0 0 1
0
0 0 1 0
0
0 0 0 1
0
Als DNF aufgeschrieben ergibt sich:
R = A F P B + A F P B + AF P B + AF P B + AF P B
Die algebraische Minimierung dieser DNF kann z. B. folgendermaßen erfolgen:
R =
=
=
=
B · [A F P + A F P + AF P + ∗ AF P + AF P ]
B · [A F · (P + P ) + F P · (A + A) + AF · (P + P )]
B · [A · (F + F ) + F P ]
B A + BF P
(10)
(11)
(12)
(13)
Folgende Gesetze wurden für die Umformungen verwendet: Um auf (10) zu kommen, reicht
das Distributivitätsgesetz, nach (11) kommt man, indem man mit Hilfe der Idempotenz an der
mit ∗ markierten Stelle den Term AF P +“ zusätzlich erzeugt und den Inhalt der Klammer
”
mit dem Distributivitätsgesetz umordnet ( Ausklammern“). Durch das Neutralitätsgesetz und
”
anschließend die erneute Anwendung des Distributivitätsgesetzes gelangt man schließlich zu
(12). Der letzte Schritt besteht dann in der umgekehrten Anwendung der Distributivität und
hat (13) zur Folge.
5
Lösungsvorschlag Aufgabe 9.3
library IEEE;
use IEEE.std_logic_1164.all;
-- Wir brauchen std_logic aus der Bibliothek
-- Definition der Ein- und Ausgänge (Ports) mit den passenden Datentypen
-- Der Baustein (sog. entity) soll "ruhe_detektor" heissen.
entity ruhe_detektor is
port ( f, p, a, b : in std_logic;
es_ist_ruhe : out std_logic
end ruhe_detektor;
);
-- 4 Eingänge
-- 1 Ausgang
-- Jetzt kommt EINE mögliche Implementierung unseres Bauteils.
-- Der Variantename ("version_eins") ist für unsere Zwecke egal.
architecture version_eins of ruhe_detector is
begin
-- Hier muss die Berechnung der Ruhefunktion rein!
es_ist_ruhe <= (not b and not a) or (not b and f and not p);
end version_eins;
6

Download Report