close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

0 - TU Dortmund

EinbettenHerunterladen
technische universität
dortmund
fakultät für informatik
Rechnerstrukturen, Teil 1
Vorlesung
4 SWS
WS 14/15
Prof. Dr Jian-Jia Chen
Dr. Lars Hildebrand
Fakultät für Informatik – Technische Universität Dortmund
lars.hildebrand@tu-dortmund.de
http://ls1-www.cs.tu-dortmund.de
TU Dortmund
Übersicht
1. Organisatorisches
2. Einleitung
3. Repräsentation von Daten
4. Boolesche Funktionen und Schaltnetze
5. Rechnerarithmetik
6. Optimierung von Schaltnetzen
7. Programmierbare Bausteine
8. Synchrone Schaltwerke
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
- 2-
TU Dortmund
4. Boolesche Funktionen und Schaltnetze
4. Boolesche Funktionen und Schaltnetze
1. Einleitung
2. Boolesche Algebra
3. Repräsentationen boolescher Funktionen
4. Normalformen boolescher Funktionen
5. Repräsentation boolescher Funktionen mit OBDDs
6. Schaltnetze
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
- 3-
TU Dortmund
4.1 Einleitung
Boolesche Funktionen
Vielleicht schon bekannt: Aussagenlogik
• Satz ist Aussage mit eindeutigem Wahrheitswert
• Wahrheitswerte
• wahr
• falsch
• neue Aussagen entstehen durch Verknüpfung von Aussagen
• Verknüpfungen
• Negation (¬, ”nicht“)
• Konjunktion (∧, ”und“)
• Disjunktion (∨, ”oder“)
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
- 4-
TU Dortmund
4.1 Einleitung
Definition der Verknüpfungen
Seien A, B zwei Aussagen.
Definition Negation
A
¬A
falsch
wahr
wahr
falsch
Definition Kunjunktion
Definition Disjunktion
A
B
A∧B
A
B
A∨B
falsch
falsch
falsch
falsch
falsch
falsch
falsch
wahr
falsch
falsch
wahr
wahr
wahr
falsch
falsch
wahr
falsch
wahr
wahr
wahr
wahr
wahr
wahr
wahr
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
- 5-
TU Dortmund
4. Boolesche Funktionen und Schaltnetze
4. Boolesche Funktionen und Schaltnetze
1. Einleitung
2. Boolesche Algebra
3. Repräsentationen boolescher Funktionen
4. Normalformen boolescher Funktionen
5. Repräsentation boolescher Funktionen mit OBDDs
6. Schaltnetze
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
- 6-
TU Dortmund
4.2 Boolesche Algebra
Eine boolesche Algebra ist eine spezielle algebraische Struktur, die die
• Eigenschaften der logischen Operatoren UND, ODER, NICHT und die
• Eigenschaften der mengentheoretischen Verknüpfungen
Durchschnitt, Vereinigung, Komplement
verallgemeinert.
Definition 2
Wir nennen , ∪, ∩, ̅ mit = 0, 1 und
•
∪ =
,
•
∩ =
,
• ̅ =1−
für alle , y ∈ eine boolesche Algebra.
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
- 7-
TU Dortmund
4.2 Boolesche Algebra
Wir sehen hier bereits Entsprechungen zur Aussagenlogik:
•
•
•
•
•
falsch
wahr
∧
∨
¬
technische universität
dortmund
⇔
⇔
⇔
⇔
⇔
0
1
∩
∪
̅
fakultät für
informatik
Rechnerstrukturen (Teil 1)
- 8-
TU Dortmund
4.2 Boolesche Algebra
In einer boolesche Algebra gelten folgende Rechengesetze:
Satz 3
In der booleschen Algebra , ∪, ∩, ̅ für alle , y, z ∈
Kommutativität:
∪ = ∪
∩ = ∩
Assoziativität:
Distributivität:
technische universität
dortmund
∪
∩
∩
∪
fakultät für
informatik
∪
∩
∪
∩
=
=
=
=
∪
∩
∩
∪
:
∪
∩
∪
∩
Rechnerstrukturen (Teil 1)
∩
∪
- 9-
TU Dortmund
4.2 Boolesche Algebra
In einer boolesche Algebra gelten folgende Rechengesetze:
Satz 3 (cont.)
, ∪, ∩, ̅ für alle , y, z ∈
In der booleschen Algebra
Neutralelement:
∪0=
∩1=
Nullelement:
∪1=1
∩0=0
Idempotenz:
=
=
Involution:
technische universität
dortmund
:
∪
∩
x= ̿
fakultät für
informatik
Rechnerstrukturen (Teil 1)
- 10 -
TU Dortmund
4.2 Boolesche Algebra
In einer boolesche Algebra gelten folgende Rechengesetze:
Satz 3 (cont.)
, ∪, ∩, ̅ für alle , y, z ∈
In der booleschen Algebra
Absorption:
∪
∩
∩
∪
=
=
Resolution:
∪
∩
∩
∪
̅∪
̅∩
Komplementarität:
∪
∩
∩
∪
de Morgan:
∪
∩
= ̅∩
= ̅∪
technische universität
dortmund
fakultät für
informatik
:
=
=
=
=
Rechnerstrukturen (Teil 1)
- 11 -
TU Dortmund
4.2 Boolesche Algebra
Wie beweist man einzelne Rechengesetze?
Wir stellen eine Wertetabelle auf.
Beispiel: Absorption
∪
∩
=
linke Seite
∪
∪
rechte Seite
∩
0
0
0
0
0
0
1
1
0
0
1
0
1
1
1
1
1
1
1
1
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
- 12 -
TU Dortmund
4. Boolesche Funktionen und Schaltnetze
4. Boolesche Funktionen und Schaltnetze
1. Einleitung
2. Boolesche Algebra
3. Repräsentationen boolescher Funktionen
4. Normalformen boolescher Funktionen
5. Repräsentation boolescher Funktionen mit OBDDs
6. Schaltnetze
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
- 13 -
TU Dortmund
4.3 Repräsentationen boolescher Funktionen
Wir benötigen im Folgenden den Begriff der booleschen Funktion.
Definition 4
Seien ,
∈ N und eine boolesche Algebra. Eine Funktion f ∶
heißt boolesche Funktion.
→
Notation
•
= Menge aller n-stelligen Tupel über B
• Beispiel
= = {(0), (1)}
• Beispiel = {(0, 0), (0, 1), (1, 0), (1, 1)}
• Beispiel = {(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1),
(1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)}
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
- 14 -
TU Dortmund
4.3 Repräsentationen boolescher Funktionen
Anzahl boolescher Funktionen
• boolesche Funktion f ∶
•
= 2 Zeilen
•
=2
2
=2
→
als Wertetabelle darstellbar, mit
Funktionswerten pro Zeilen
∙
technische universität
dortmund
boolesche Funktionen für f ∶
fakultät für
informatik
→
Rechnerstrukturen (Teil 1)
- 15 -
TU Dortmund
4.3 Repräsentationen boolescher Funktionen
Grundfunktion aus dem Bereich der booleschen Funktionen
• boolesche Grundfunktion f ∶
→
als Wertetabelle darstellbar, mit
•
= 2 Zeilen
•
= 2 1 Funktionswert pro Zeilen
Beispiel 1-stellige boolesche Grundfunktionen
•
→
• 2 ∙ =4
=0
=1
f0
0
0
f1
0
1
f2
1
0
̅
Negation
f3
1
1
Konstante 1
Tautologie
technische universität
dortmund
fakultät für
informatik
Funktion
Name
Konstante 0
Kontradiktion
Identität
Rechnerstrukturen (Teil 1)
- 16 -
TU Dortmund
4.3 Repräsentationen boolescher Funktionen
Alle booleschen 2-stelligen Grundfunktionen
→
(2
∙
= 16)
x 1, x 2
f0
f1
f2
f3
f4
f5
0, 0
0
0
0
0
0
0
0, 1
0
0
0
0
1
1
1, 0
0
0
1
1
0
0
1, 1
0
1
0
1
0
1
Funktion
0
⋀
Name
Kontradiktion
Konjunktion
Inhibition von x1
Identität von x1
Inhibition von x2
Identität von x2
f6
0
1
1
0
⊕
Antivalenz, Alternative
f7
0
1
1
1
∨
Disjunktion
f8
1
0
0
0
∨
Nihilition
f9
f10
f11
f12
f13
1
1
1
1
1
0
0
0
1
1
0
1
1
0
0
1
0
1
0
1
⇔
⇒
Äquivalenz
Negation von x2
Replikation
Negation von x1
Implikation
f14
1
1
1
0
⋀
Exklusion
f15
1
1
1
1
1
Tautologie
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
- 17 -
TU Dortmund
4.3 Repräsentationen boolescher Funktionen
Im Folgenden werden diese Symbole verwenden:
∧
• Konjunktion
(und)
∨
• Disjunktion
(oder)
• Negation
(nicht)
̅
• Antivalenz
(xor)
⨁
In der Regel abkürzende Notation der Konjunktion, z.B.:
∧

Feste Folge der Funktionswerte, entsprechend des Wertes der Binärzahl:
Beispiel: f6=(0,1,1,0) korrespondiert zu x
y
f6
0
0
0
0
1
1
1
0
1
1
1
0
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
- 18 -
TU Dortmund
4.3 Repräsentationen boolescher Funktionen
Vorsicht bei der Notation
•
≠
0
0
1
1
0
1
1
0
1
0
1
0
1
1
0
0
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
- 19 -
TU Dortmund
4. Boolesche Funktionen und Schaltnetze
4. Boolesche Funktionen und Schaltnetze
1. Einleitung
2. Boolesche Algebra
3. Repräsentationen boolescher Funktionen
4. Normalformen boolescher Funktionen
5. Repräsentation boolescher Funktionen mit OBDDs
6. Schaltnetze
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
- 20 -
TU Dortmund
4.4 Normalformen boolescher Funktionen
Einschlägige und nicht einschlägige Indizes
• Wir tragen die Werte der Argumente gemäß ihrer natürlichen
Ordnung (Index) in eine Wertetabelle ein
• Ist der Funktionswert für einen Index = 1 , nennen wir den Index
einschlägig,
• Ist der Funktionswert für einen Index = 0 , nennen wir den Index
nicht einschlägig
Beispiel:
Index
f6
0
0
0
0
nicht einschlägig
1
0
1
1
einschlägig
2
1
0
1
einschlägig
3
1
1
0
nicht einschlägig
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
- 21 -
TU Dortmund
4.4 Normalformen boolescher Funktionen
Minterm
Definition 5
Die boolesche Funktion
Minterm zum Index i.
, für die nur der Index i einschlägig ist, heißt
Ein Minterm ist nur mit Negationen und Konjunktionen darstellbar:
• ist die Eingangsbelegung an der Stelle
= 0, setzen wir ̅
• ist die Eingangsbelegung an der Stelle
= 1, setzen wir
• und bilden dann die Konjunktion der Literale
Literal: In der mathematischen Logik ist ein Literal eine atomare Aussage
(Atom) oder die Negation einer atomaren Aussage. Hier also eine Variable
oder die negierte Variabletechnische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
- 22 -
TU Dortmund
4.4 Normalformen boolescher Funktionen
Beispiel zu Index und Minterm
Index
f6
0
0
0
0
nicht einschlägig
1
0
1
1
einschlägig
2
1
0
1
einschlägig
3
1
1
0
nicht einschlägig
Minterm zum Index 2 = (10)2:
,
=
∧
∧
Index
Was bewirk nun
?
nimmt nur für den Index 2 den Wert 1 an.
technische universität
dortmund
fakultät für
informatik
0
0
0
0
1
0
1
0
2
1
0
1
3
1
1
0
Rechnerstrukturen (Teil 1)
- 23 -
TU Dortmund
4.4 Normalformen boolescher Funktionen
Hinführung zu Normalformen
Für wie viele Eingaben liefert ein Minterm 1?
Wie soeben gesehen für genau 1 Eingabe.
Folgerungen
• Disjunktion aller Minterme zu einschlägigen Indizes einer booleschen
Funktion f ist wieder f
• XOR-Verknüpfung aller Minterme zu einschlägigen Indizes einer
booleschen Funktion f ist wieder f
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
- 24 -
TU Dortmund
4.4 Normalformen boolescher Funktionen
Normalformen
Definition 8
Die Darstellung einer booleschen Funktion f als Disjunktion all ihrer
Minterme zu einschlägigen Indizes heißt disjunktive Normalform (DNF).
Die Darstellung einer booleschen Funktion f als XOR-Verknüpfung all ihrer
Minterme zu einschlägigen Indizes heißt Ringsummen-Normalform (RNF).
Anmerkung: Normalformen sind eindeutig.
Index
Beispiel f6
• DNF von f6:
• RNF von f6:
technische universität
dortmund
∨
⊕
fakultät für
informatik
f6
Minterme
0
0
0
0
∧
1
0
1
1
∧
2
1
0
1
∧
3
1
1
0
∧
Rechnerstrukturen (Teil 1)
- 25 -
TU Dortmund
4.4 Normalformen boolescher Funktionen
Funktionale Vollständigkeit
Beobachtung:
• jede boolesche Funktion f ∶
→ ist durch ausschließliche
Verwendung von Konjunktion, Disjunktion und Negation darstellbar
• z. B. durch ihre DNF
Definition 8
Eine Menge F von booleschen Funktionen heißt funktional vollständig,
wenn sich jede boolesche Funktion durch Einsetzen und Komposition von
Funktionen aus F darstellen lässt.
Satz 6
F = ∧,∨,
ist funktional vollständig.
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
- 26 -
TU Dortmund
4.4 Normalformen boolescher Funktionen
Funktionale Vollständigkeit
Frage: Gibt es kleinere funktional vollständige Mengen F ?
Behauptung: Funktional vollständig sind
• F1= ∧,
• F2= ∨,
Zum Beweis genügt es zu zeigen, dass ∧,∨,
darstellbar ist.
Beweis
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
- 27 -
TU Dortmund
4.4 Normalformen boolescher Funktionen
Funktionale Vollständigkeit
Frage: Gibt es kleinere funktional vollständige Mengen F ?
Behauptung: Funktional vollständig sind
• F1= ∧,
• F2= ∨,
Zum Beweis genügt es zu zeigen, dass ∧,∨,
darstellbar ist.
Beweis
Anwendung der de Morgan-Regeln (Satz 3):
•
∨ = ∧
 ∨ ist durch = ∧,
•
∧
=
technische universität
dortmund
∨

fakultät für
informatik
∧ ist durch = ∨,
Rechnerstrukturen (Teil 1)
darstellbar
darstellbar
- 28 -
TU Dortmund
4.4 Normalformen boolescher Funktionen
Funktionale Vollständigkeit
Frage: Gibt es noch kleinere funktional vollständige Mengen F ?
Behauptung: Funktional vollständig ist
• F3 =
• F4 =
Zum Beweis der funktionalen Vollständigkeit von F3 genügt es zu zeigen,
dass ∨,
darstellbar ist.
Beweis Teil 1
Darstellung der Negation
•
=
,
technische universität
dortmund
fakultät für
informatik
( )
0
1
1
1
0
0
Rechnerstrukturen (Teil 1)
- 29 -
TU Dortmund
4.4 Normalformen boolescher Funktionen
Beweis Teil 2
Darstellung der Disjunktion
∨
•
=
( , ),
( , )
∨
x
( , ),
0
0
0
1
1
0
0
1
1
1
0
1
1
0
1
0
1
1
1
1
1
0
0
1
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
( , )
- 30 -
TU Dortmund
4.4 Normalformen boolescher Funktionen
Maxterme
Beobachtung: Minterm-Darstellung betont Funktionswert 1.
Definition
Die boolesche Funktion , für die nur der Index i nicht einschlägig
ist, heißt Maxterm zum Index i .
Beobachtungen
• Definition Maxterm unterscheidet sich nur in ”nicht“ von Definition
Minterm
• wenn
Minterm zum Index i und
Maxterm zum Index i ist
⇒ =
• Konjunktion aller Maxterme zu nicht einschlägigen Indizes einer
booleschen Funktion f ist wieder f
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
- 31 -
TU Dortmund
4.4 Normalformen boolescher Funktionen
Normalformen
Fortsetzung von Definition 8
Die Darstellung von f als Konjunktion all ihrer Maxterme zu nicht
einschlägigen Indizes heißt konjunktive Normalform (KNF).
Beispiel
∨
∨
∨
∨
∨
x
0
0
0
0
1
1
1
1
1
0
0
1
0
0
1
1
2
0
1
0
0
1
0
1
3
0
1
1
0
1
1
0
4
1
0
0
1
1
1
1
5
1
0
1
1
1
1
1
6
1
1
0
1
1
1
1
7
1
1
1
1
1
1
1
technische universität
dortmund
z
∨
Index
fakultät für
informatik
Rechnerstrukturen (Teil 1)
- 32 -
TU Dortmund
4.4 Normalformen boolescher Funktionen
Wozu stellt man boolesche Funktionen dar?
• Realisierung
• Verifikation
• Fehleranalyse
• Synthese
• ...
Wo stellt man boolesche Funktionen dar?
• auf dem Papier
• im Computer
Probleme
• Wertetabelle, Wertevektor immer groß
• Normalformen oft groß
• Normalformen unterstützen gewünschte Operationen kaum
Wunsch: andere Repräsentation
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
- 33 -
TU Dortmund
4. Boolesche Funktionen und Schaltnetze
4. Boolesche Funktionen und Schaltnetze
1. Einleitung
2. Boolesche Algebra
3. Repräsentationen boolescher Funktionen
4. Normalformen boolescher Funktionen
5. Repräsentation boolescher Funktionen mit OBDDs
6. Schaltnetze
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
- 34 -
TU Dortmund
4.5 Ordered Binary Decision Diagrams
Eine Datenstruktur für boolesche Funktionen
Ziel: Darstellung für f ∶
→
Wünsche:
• zu einer Belegung x1, x2, . . . , xn schnell den Funktionswert
f(x1, x2, . . . , xn ) ausrechnen können
• Funktionen schnell auf Gleichheit testen können
• Funktionen schnell manipulieren (z. B. eine Variable konstant setzen)
können
• schnell eine Null-Eingabe/eine Eins-Eingabe finden können
• Funktionen möglichst klein repräsentieren
• ...
Ordered Binary Decision Diagrams
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
- 35 -
TU Dortmund
4.5 Ordered Binary Decision Diagrams
ODBBs
• erster Schritt; Festlegung einer Variablenordnung
z. B.: =
, , ,
bei einer 4-stelligen Funktion
• zweiter Schritt: OBDD bauen
• aus Knoten für Variablen oder Konstanten
• Kanten, die zwei Knoten verbinden
• nach folgenden Regeln:
Regeln
• Knoten mit Variablen, 0 oder 1 markiert
• Kanten mit 0 oder 1 markiert
• Variablen-Knoten mit je einer ausgehenden 0- und 1-Kante
• Konstanten-Knoten ohne ausgehende Kante
• genau ein Knoten ohne eingehende Kante
• Kanten zwischen Variablenknoten beachten π
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
- 36 -
TU Dortmund
4.5 Ordered Binary Decision Diagrams
ODBB – Ein Beispiel
=
,
,
Regeln
• Knoten mit Variablen, 0 oder 1 markiert
• Kanten mit 0 oder 1 markiert
• Variablen-Knoten mit je einer ausgehenden 0- und 1-Kante
• Konstanten-Knoten ohne ausgehende Kante
x
• genau ein Knoten ohne eingehende Kante
0
• Kanten zwischen Variablenknoten beachten π
1
1
x2
x2
0
x3
0
1
technische universität
dortmund
fakultät für
informatik
0
1
x3
x3
1
0
1
0
0
0
Rechnerstrukturen (Teil 1)
1
0
1
x3
1
1
0
1
1
1
- 37 -
TU Dortmund
4.5 Ordered Binary Decision Diagrams
ODBB – Ein Beispiel
=
,
,
x1
0
Index
x
z
0
0
0
0
1
1
0
0
1
0
2
0
1
0
0
3
0
1
1
0
4
1
0
0
1
5
1
0
1
1
6
1
1
0
1
7
1
1
1
1
x2
fakultät für
informatik
x2
0
0
0
1
x3
1
technische universität
dortmund
1
x3
x3
1
0
1
0
0
0
Rechnerstrukturen (Teil 1)
1
0
1
x3
1
1
0
1
1
1
- 38 -
TU Dortmund
4.5 Ordered Binary Decision Diagrams
=
ODBB – Ein Beispiel
,
,
x1
Auswertung (1, 0, 1)
•
=1
•
=0
•
=1

0
1
x2
x2
1, 0, 1 = 1
0
x3
0
1
technische universität
dortmund
fakultät für
informatik
0
1
x3
1
x3
1
0
1
0
0
0
Rechnerstrukturen (Teil 1)
0
1
x3
1
1
0
1
1
1
- 39 -
TU Dortmund
4.5 Ordered Binary Decision Diagrams
ODBB – Ein Beispiel
=
,
,
x1
Ist das nicht etwas groß?
0
1
x2
x2
0
x3
0
1
technische universität
dortmund
fakultät für
informatik
0
1
x3
1
x3
1
0
1
0
0
0
Rechnerstrukturen (Teil 1)
0
1
x3
1
1
0
1
1
1
- 40 -
TU Dortmund
4.5 Ordered Binary Decision Diagrams
ODBB – Ein Beispiel
=
,
,
x1
Vereinfachungen
• gleichartige Senken
verschmelzen
0
1
x2
x2
0
x3
0
1
technische universität
dortmund
fakultät für
informatik
0
1
x3
1
x3
1
0
1
0
0
0
Rechnerstrukturen (Teil 1)
0
1
x3
1
1
0
1
1
1
- 41 -
TU Dortmund
4.5 Ordered Binary Decision Diagrams
ODBB – Ein Beispiel
=
,
,
x1
Vereinfachungen
• gleichartige Senken
verschmelzen
0
1
x2
x2
0
x3
0
1
technische universität
dortmund
fakultät für
informatik
0
1
x3
1 0
1
0
Rechnerstrukturen (Teil 1)
1
x3
0
1
x3
1
1
0
1
1
1
- 42 -
TU Dortmund
4.5 Ordered Binary Decision Diagrams
ODBB – Ein Beispiel
=
,
,
x1
Vereinfachungen
• gleichartige Senken
verschmelzen
0
1
x2
x2
0
x3
0
1
technische universität
dortmund
fakultät für
informatik
0
1
x3
1 0
1
0
Rechnerstrukturen (Teil 1)
1
x3
0
1
x3
1
1
0
1
1
1
- 43 -
TU Dortmund
4.5 Ordered Binary Decision Diagrams
ODBB – Ein Beispiel
=
,
,
x1
Vereinfachungen
• gleichartige Senken
verschmelzen
0
1
x2
x2
0
0
1
x3
x3
1 0
1
x3
1
0
x3
1 0
1
0
0
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
1
- 44 -
TU Dortmund
4.5 Ordered Binary Decision Diagrams
ODBB – Ein Beispiel
=
,
,
x1
Vereinfachungen
• gleichartige Senken
verschmelzen
• gleichartige Knoten
verschmelzen
0
1
x2
x2
0
0
1
x3
x3
1 0
1
x3
1
0
x3
1 0
1
0
0
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
1
- 45 -
TU Dortmund
4.5 Ordered Binary Decision Diagrams
ODBB – Ein Beispiel
=
,
,
x1
Vereinfachungen
• gleichartige Senken
verschmelzen
• gleichartige Knoten
verschmelzen
0
1
x2
x2
0
0
1
x3
x3
1 0
1
x3
1
0
1
0
0
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
1
- 46 -
TU Dortmund
4.5 Ordered Binary Decision Diagrams
ODBB – Ein Beispiel
=
Vereinfachungen
• gleichartige Senken
verschmelzen
• gleichartige Knoten
verschmelzen
• Knoten ohne Einfluss
entfernen
,
,
x1
0
1
x2
x2
0
0
1
x3
x3
1 0
1
x3
1
0
1
0
0
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
1
- 47 -
TU Dortmund
4.5 Ordered Binary Decision Diagrams
ODBB – Ein Beispiel
=
Vereinfachungen
• gleichartige Senken
verschmelzen
• gleichartige Knoten
verschmelzen
• Knoten ohne Einfluss
entfernen
,
,
x1
0
1
x2
x2
0
0
1
x3
1
x3
1 0
1
0
0
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
1
- 48 -
TU Dortmund
4.5 Ordered Binary Decision Diagrams
ODBB – Ein Beispiel
=
Vereinfachungen
• gleichartige Senken
verschmelzen
• gleichartige Knoten
verschmelzen
• Knoten ohne Einfluss
entfernen
,
,
x1
0
1
x2
x2
0
0
1
x3
1
x3
1 0
1
0
0
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
1
- 49 -
TU Dortmund
4.5 Ordered Binary Decision Diagrams
ODBB – Ein Beispiel
=
Vereinfachungen
• gleichartige Senken
verschmelzen
• gleichartige Knoten
verschmelzen
• Knoten ohne Einfluss
entfernen
,
,
x1
0
1
x2
0
1
x3
x3
1 0
1
0
0
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
1
- 50 -
TU Dortmund
4.5 Ordered Binary Decision Diagrams
ODBB – Ein Beispiel
=
Vereinfachungen
• gleichartige Senken
verschmelzen
• gleichartige Knoten
verschmelzen
• Knoten ohne Einfluss
entfernen
,
,
x1
0
1
x2
0
1
x3
x3
1 0
1
0
0
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
1
- 51 -
TU Dortmund
4.5 Ordered Binary Decision Diagrams
ODBB – Ein Beispiel
=
Vereinfachungen
• gleichartige Senken
verschmelzen
• gleichartige Knoten
verschmelzen
• Knoten ohne Einfluss
entfernen
,
,
x1
0
1
x2
0
1
x3
1
0
0
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
1
- 52 -
TU Dortmund
4.5 Ordered Binary Decision Diagrams
ODBB – Ein Beispiel
=
Vereinfachungen
• gleichartige Senken
verschmelzen
• gleichartige Knoten
verschmelzen
• Knoten ohne Einfluss
entfernen
 OBDD minimal
,
,
x1
0
1
x2
0
1
x3
1
0
0
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
1
- 53 -
TU Dortmund
4.5 Ordered Binary Decision Diagrams
OBDD-Reduzierung
Satz 9
Die erschöpfende Anwendung der
• Verschmelzungsregel
Knoten mit gleicher Markierung und gleichen Nachfolgern können
verschmolzen werden und der
• Eliminationsregel
Ein Knoten mit gleichem Null- und Einsnachfolger kann entfernt
werden
in beliebiger Reihenfolge führt zum reduzierten πOBDD.
reduziert bedeutet: OBDD hat minimale Größe und ist eindeutig definiert
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
- 54 -
TU Dortmund
4.5 Ordered Binary Decision Diagrams
Was bringt und die OBDD-Reduzierung
Originalfunktion als DNF
=
∨
technische universität
dortmund
∨
∨
fakultät für
informatik
∨
Rechnerstrukturen (Teil 1)
Index
x
z
0
0
0
0
1
1
0
0
1
0
2
0
1
0
0
3
0
1
1
0
4
1
0
0
1
5
1
0
1
1
6
1
1
0
1
7
1
1
1
1
- 55 -
TU Dortmund
4.5 Ordered Binary Decision Diagrams
ODBB in boolesche Funktion umwandeln
• disjunktive Form, d. h. Disjunktion von Termen, die nur Negation und
Konjunktion enthalten
• wir berücksichtigen nur Kanten, die zu Konstanten-Knoten mit 1
führen
• folgen wir für eine Variable einer 1-Kante,
x1
setzen wir als Literal in den Term
0
1
• folgen wir für eine Variable einer 0-Kante,
setzen wir als Literal in den Term
x2
• Literale werden mit der Konjunktion (UND)
0
1
verknüpft
• jeder Pfad zu einem Konstanten-Knoten
x3
mit 1 ergibt einen Term
• alle entstandenen Terme werden mit der
1
Disjunktion (ODER) verknüpft
0
 hier:
=
technische universität
dortmund
0
∨
fakultät für
informatik
Rechnerstrukturen (Teil 1)
1
- 56 -
TU Dortmund
4.5 Ordered Binary Decision Diagrams
Was bringt und die OBDD-Reduzierung
Originalfunktion als DNF
•
=
∨
∨
∨
∨
Originalfunktion aus OBDD-Reduzierung
•
=
∨
• weniger Terme
• einfachere Terme
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
Index
x
z
0
0
0
0
1
1
0
0
1
0
2
0
1
0
0
3
0
1
1
0
4
1
0
0
1
5
1
0
1
1
6
1
1
0
1
7
1
1
1
1
- 57 -
TU Dortmund
4. Boolesche Funktionen und Schaltnetze
4. Boolesche Funktionen und Schaltnetze
1. Einleitung
2. Boolesche Algebra
3. Repräsentationen boolescher Funktionen
4. Normalformen boolescher Funktionen
5. Repräsentation boolescher Funktionen mit OBDDs
6. Schaltnetze
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
- 58 -
TU Dortmund
4.6 Schaltnetze
Wo bleibt die Hardware?
• bis jetzt haben wir über theoretische Grundlagen diskutiert
• wir betrachten die Hardware auf abstrakter Ebene
Wunsch
• Realisierung boolescher Funktionen in Hardware
• wir benötigen eine funktional vollständige Menge boolescher
Funktionen
• Erinnerung: technische Realisierung
von NAND reicht aus
• Beobachtung: folgende Schaltung
mit Transistoren realisiert
die NAND-Funktion
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
- 59 -
TU Dortmund
4.6 Schaltnetze
Logische Gatter
• Realisierung mit Transistoren . . . für uns die falsche Ebene!
Grundlage für RS
• einfache logische Bausteine (logische Gatter)
• Bausteine für
• Negation
• Konjunktion
• Disjunktion
• Regeln
• Eingänge mit Variablen oder Konstanten belegt
• nur Verbindungen von Ausgängen zu Eingängen
• keine Kreise (Rückkopplung Ausgang  Eingang)
 Schaltnetz
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
- 60 -
TU Dortmund
4.6 Schaltnetze
Symbole für logische Gatter (1)
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
- 61 -
TU Dortmund
4.6 Schaltnetze
Symbole für logische Gatter (2)
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
- 62 -
TU Dortmund
4.6 Schaltnetze
Schaltnetzbewertung
Wir können nun beliebige Schaltnetze entwerfen. Wie messen wir die
Qualität eines Schaltnetzes?
• Schaltnetzgröße (= Anzahl der Gatter) wegen Kosten, Stromverbrauch,
Verlustleistung, Zuverlässigkeit, . . .
• Schaltnetztiefe (= Länge des längsten Wegs von Eingang zu Ausgang)
wegen Schaltgeschwindigkeit
• Fan-In (= max. Anzahl eingehender Kanten) wegen Realisierungsaufwand
• Fan-Out (= max. Anzahl ausgehender Kanten) wegen
Realisierungsaufwand
• . . . (z. B. Anzahl Gattertypen, Testbarkeit, Verifizierbarkeit)
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
- 63 -
TU Dortmund
4.6 Schaltnetze
Schaltnetzbewertung
Was wir schon wissen:
• Jede boolesche Funktion kann mit einem {∧, ∨, ¬}- bzw. einem
{⊕, ∧, ¬}-Schaltnetz der Tiefe 3 realisiert werden
Beweis DNF, KNF oder RNF direkt umsetzen
Probleme
• Fan-In des tiefsten Gatters kann extrem groß sein
• Größe des Schaltnetzes oft inakzeptabel
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
- 64 -
TU Dortmund
4.6 Schaltnetze
Beispiel DNF
→ , Wertevektor (1, 0, 0, 0, 1, 1, 1, 1, 1)
:
=
∨
technische universität
dortmund
∨
fakultät für
informatik
∨
∨
Rechnerstrukturen (Teil 1)
- 65 -
TU Dortmund
4.6 Schaltnetze
Beispiel RNF
:
→ , Wertevektor (1, 0, 0, 0, 1, 1, 1, 1, 1)
=
⊕
⊕
⊕
⊕
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
- 66 -
TU Dortmund
4.6 Schaltnetze
Beispiel KNF
:
→ , Wertevektor (1, 0, 0, 0, 1, 1, 1, 1, 1)
=( ∨ ∨ ) ∧( ∨
∨ ) ∧( ∨
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
∨
)
- 67 -
TU Dortmund
4.6 Schaltnetze
Beispiel Multiplexer
:
,
→
,…,
,
,
,…,
=
,
,…,
Wichtige Funktion für die Praxis
• Selektiert aus vielen Eingängen einen speziellen (ähnlich Drehschalter)
• kann parallel anliegende Daten in serielle Daten verwandeln
• mehrere Eingänge
• Signaleingänge
• Selektionseingänge
• ein Ausgang
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
- 68 -
TU Dortmund
4.6 Schaltnetze
Beispiel Multiplexer
:
→
,…,
,
,
,
,…,
MUX1 vollständige Darstellung
,
=
,
MUX1 verkürzte Darstellung
,
,
0
0
0
0
0
0
0
1
0
1
0
1
0
1
0
1
1
1
1
0
0
0
1
0
1
1
1
1
0
0
1
1
1
1
technische universität
dortmund
,…,
fakultät für
informatik
Rechnerstrukturen (Teil 1)
,
- 69 -
TU Dortmund
4.6 Schaltnetze
Beispiel Multiplexer
:
→
,…,
,
,
,
,…,
=
,
,…,
MUX3 verkürzte Darstellung
,
0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
1
1
1
technische universität
dortmund
fakultät für
informatik
,
,
,
,…,
Rechnerstrukturen (Teil 1)
- 70 -
TU Dortmund
4.6 Schaltnetze
Beispiel Multiplexer
MUX3 vollständige Darstellung
•
•
•
•
•
:
,
→
,…,
,
,
,
,
,
,…,
:
:
Die Abbildung
211 = 2048 Zeilen
technische universität
dortmund
,
,…,
=
=
,
,
,…,
,
→
→
:
→
fakultät für
informatik
hat demnach in vollständiger Darstellung
Rechnerstrukturen (Teil 1)
- 71 -
TU Dortmund
4.6 Schaltnetze
Beispiel Multiplexer
MUX3 vollständige Darstellung
•
•
•
•
•
:
,
→
,…,
,
,
,
,
,
,…,
:
:
Die Abbildung
211 = 2048 Zeilen
,
,…,
=
=
,
,
,…,
,
→
→
:
→
hat demnach in vollständiger Darstellung
Da die Hälfte der Indizes einschlägig ist (bedingt durch die Funktion eines
Multiplexers) sind sowohl DNF als auch KNF riesig und würden zu sehr
großen Schaltungen führen.
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
- 72 -
TU Dortmund
4.6 Schaltnetze
Beispiel Multiplexer
Trotzdem existiert eine
überschaubare Schaltung für
MUX3.
•
und selektieren
passende UND-Gatter
• für jede Belegung der
ist genau ein UNDGatter ausgewählt
• bis auf einen Eingang
sind bei ausgewähltem
Gatter alle Eingänge auf
1 gesetzt.
• Eigenschaft des Neutralelements 1 für UND
leitet sel. durch
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
- 73 -
TU Dortmund
4. Boolesche Funktionen und Schaltnetze
4. Boolesche Funktionen und Schaltnetze
1. Einleitung
2. Boolesche Algebra
3. Repräsentationen boolescher Funktionen
4. Normalformen boolescher Funktionen
5. Repräsentation boolescher Funktionen mit OBDDs
6. Schaltnetze
technische universität
dortmund
fakultät für
informatik
Rechnerstrukturen (Teil 1)
- 74 -
Document
Kategorie
Technik
Seitenansichten
10
Dateigröße
676 KB
Tags
1/--Seiten
melden