Upload
others
View
0
Download
0
Embed Size (px)
Citation preview
Rechnerstrukturen
Michael Engel und Peter Marwedel
TU Dortmund, Fakultät für Informatik
SS 2013
Hinweis: Folien a. d. Basis von Materialien von Gernot Fink und Thomas Jansen 6. Mai 2013
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
http://ls12-www.cs.tu-dortmund.de/~engel/
1 Boolesche Funktionen und Schaltnetze
2 KV-Diagramme (Wiederholung)
3 Algorithmus von Quine und McCluskey (Wiederholung)
4 Unvollständig definierte FunktionenEinleitungMinimalpolynome für partiell definierte Funktionen
5 HazardsEinleitungSchaltungshazards
6 Programmierbare BausteineEinleitungEinsatz von PLAs
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Minimalpolynombestimmung mit
KV-Diagramm
Wieso suchen wir eigentlich Minimalpolynome?
Aufgabe Bestimme für f : {0, 1}4 → {0, 1} ein Minimalpolynom.
Vorgehen
1. Eintragen der Funktion ins KV-Diagramm
2. Finden aller maximaler Zweierpotenz-Rechtecke
3. Finden eines Primimplikanten für jedes Rechteck
4. Finden einer Überdeckung aller Einsen durch eine minimaleMonomauswahl
jetzt noch ein Beispielf : {0, 1}4 → {0, 1} mit (1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1)
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Eintragen der Funktion ins KV-Diagramm
f : {0, 1}4 → {0, 1} mit (01,
10,
21,
31,
40,
51,
60,
71,
80,
91,
100 ,
111 ,
120 ,
130 ,
141 ,
151 )
1
1
1
1
1
1
1
1
1
00
01
11
10
00 01 11 10
x1 x2
x3 x4
0 = (00 00)21 = (00 01)22 = (00 10)23 = (00 11)24 = (01 00)25 = (01 01)26 = (01 10)27 = (01 11)28 = (10 00)29 = (10 01)2
10 = (10 10)211 = (10 11)212 = (11 00)213 = (11 01)214 = (11 10)215 = (11 11)2
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Finden aller maximaler
Zweierpotenz-Rechtecke
f : {0, 1}4 → {0, 1} mit (1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1)
00
01
11
10
00 01 11 10
x1 x2
x3 x4
1
1
1
1
1
1
1
1
1
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Finden eines Primimplikanten für jedes
Rechteck
f : {0, 1}4 → {0, 1} mit (1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1)
00
01
11
10
00 01 11 10
x1 x2
x3 x4
1
1
1
1
1
1
1
1
1
x3 x4
x1 x2 x3x1 x2 x4x1 x2 x3
x1 x2 x4x1 x2 x4
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Überdeckung aller Einsen durch minimaleMonomauswahl
f : {0, 1}4 → {0, 1} mit (1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1)
erforderlich
erforderlich
erforderlich
erforderlich
beste Wahl
00
01
11
10
00 01 11 10
x1 x2
x3 x4
1
1
1
1
1
1
1
1
1
x3 x4
x1 x2 x3x1 x2 x4x1 x2 x3
x1 x2 x4x1 x2 x4
also x3 x4 ∨ x1 x2 x4 ∨ x1 x2 x3 ∨ x1 x2 x4 ∨ x1 x2 x4Minimalpolynom
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Fazit KV-Diagramme
Mit KV-Diagrammen effizient beide Schritte zurMinimalpolynomberechnung durchführbar
1. Bestimmung aller Primimplikanten
2. Bestimmung einer minimalen Überdeckung
für Funktionen f : {0, 1}n → {0, 1} für n ∈ {3, 4}
klar Das reicht nicht aus.
Wie bestimmen wir Minimalpolynome für f : {0, 1}n → {0, 1}für größeres n?
klar Wir suchen einen Algorithmus.
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Der Algorithmus von Quine und McCluskey
Willard van Orman Quine (1955)Edward J. McCluskey (1956)
Algorithmus von Quine/McCluskey
Eingabe Fkt. f als Liste aller Minterme zu einschlägigen IndizesAusgabe Minimalpolynom zu f
1. Berechne PI, Menge aller Primimplikanten von f .
2. Berechne minimale f überdeckende Auswahl aus PI.
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Algorithmus von Quine/McCluskey: Erster Teil
Algorithmus 11 (Berechnung von PI)
Eingabe L0: Liste aller Minterme zu einschlägigen Indizes von fAusgabe PI: Menge aller Primimplikanten zu f
1. i := 0; PI := ∅
2. So lange Li 6= ∅
3. Li+1 := {m | ∃x : {mx ,mx} ⊆ Li} (Resolution)
4. PI := PI ∪ {m ∈ Li | m hat keine echte Verkürzung in Li+1}
5. i := i + 1
6. Ausgabe PI
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Beispiel PI-Berechnung
1. i := 0; PI := ∅
2. So lange Li 6= ∅
3. Li+1 := {m | ∃x : {mx ,mx} ⊆ Li}
4. PI := PI ∪ {m ∈ Li | m hat keine echte Verkürzung in Li+1}
5. i := i + 1
6. Ausgabe PI
PI = {x1 x2 x3, x1 x2 x4, x1 x2 x4, x1 x2 x3, x3 x4}
L0 = {x1 x2 x3 x4, x1 x2 x3 x4, x1 x2 x3 x4, x1 x2 x3 x4,
x1 x2 x3 x4, x1 x2 x3 x4, x1 x2 x3 x4, x1 x2 x3 x4}
L1 = {x1 x2 x3, x1 x3 x4, x2 x3 x4, x1 x2 x4, x2 x3 x4, x1 x2 x4,
x1 x3 x4, x1 x2 x3}
L2 = {x3 x4}
L3 = ∅
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Der Algorithmus von Quine und McCluskey
Algorithmus von Quine/McCluskey
Eingabe Fkt. f als Liste aller Minterme zu einschlägigen IndizesAusgabe Minimalpolynom zu f
1. Berechne PI, Menge aller Primimplikanten von f .√
2. Berechne minimale f überdeckende Auswahl aus PI.
schwieriges kombinatorisches Problem
nur heuristische Lösungmit gewissen Freiheitsgraden
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Das Überdeckungsproblem
Aufgabe Finde minimale Überdeckung von f mit PI.
PI-Tafel
◮ eine Zeile für jeden Primimplikanten
◮ eine Spalte für jede Eins-Eingabe
◮ Eintrag =
{
1 Primimplikant überdeckt Eins-Eingabe
0 sonst
klar PI-Tafel meist riesig groß
klar verkleinern
dazu Verkleinerungsregeln
Freiheit durch
◮ Reihenfolge der Regelanwendung
◮ Art der Regelanwendung
Problem Lösung oft trotzdem nicht ablesbar
Lösung Backtracking oder HeuristikenBoole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Beispiel PI-Tafel
<
Streichung überdeckender Spalten
x1 x2 x3x3 x4
x1 x2 x4x1 x2 x3
x1 x2 x4
0010 0011 0101 0111 1001 1011 1110 1111
1 1
1 1 1 1
1 1
1 1
1 1
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Beispiel PI-Tafel
<
Streichung überdeckender Spalten
x1 x2 x3x3 x4
x1 x2 x4x1 x2 x3
x1 x2 x4
0010 0101 0111 1001 1011 1110 1111
1
1 1 1
1 1
1 1
1 1
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Beispiel PI-Tafel
<
Streichung überdeckender Spalten
x1 x2 x3x3 x4
x1 x2 x4x1 x2 x3
x1 x2 x4
0010 0101 1001 1011 1110 1111
1
1 1
1
1 1
1 1
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Beispiel PI-Tafel
Streichung überdeckter Zeilen
x1 x2 x3x3 x4
x1 x2 x4x1 x2 x3
x1 x2 x4
0010 0101 1001 1110 1111
1
1
1
1 1
1
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Beispiel PI-Tafel
Kernimplikanten-Zeilen
x1 x2 x3x1 x2 x4x1 x2 x3
x1 x2 x4
0010 0101 1001 1110 1111
1
1
1 1
1
also f (x1, . . . , x4) = x1 x2 x3 ∨ x1 x2 x4 ∨ x1 x2 x3 ∨ x1 x2 x4
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Unvollständig definierte Funktionen
formal f : {0, 1}n → {0, 1, ∗}
Bedeutung f (x) = ∗ Funktionswert für x egal (“don’t care”)
klar Schaltnetz realisiert immer eine
”normale“ boolesche Funktion
Definition
f ′ : {0, 1}n → {0, 1} heißt Realisierung (oder auch Erweiterung)von f : {0, 1}n → {0, 1, ∗}⇔ ∀x ∈ {0, 1}n : (f ′(x) = f (x)) ∨ (f (x) = ∗)
klar größere Freiheiten
Wie nutzen wir die?Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Wahl der Realisierung
Wunsch Finde Realisierung f ′ mit minimalem Minimalpolynom.
nützliche Begriffe
◮ minimale Erweiterung f0 von f
f0(x) :=
{
f (x) falls f (x) ∈ {0, 1}
0 sonst
◮ maximale Erweiterung f1 von f
f1(x) :=
{
f (x) falls f (x) ∈ {0, 1}
1 sonst
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Über extreme Erweiterungen
Beobachtungen
◮ Primimplikanten von f0 sind keine echten Verkürzungen vonPrimimplikanten von f1
◮ Primimplikanten von f1 können echte Verkürzungen vonPrimimplikanten von f0 sein
Warum?klar zusätzliche Einsen verkürzen Primimplikanten höchstens
Also hat f1 das kürzere Minimalpolynom?
So allgemein gilt das nicht!
denn f1 kann viel mehr Primimplikanten haben
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Über unvollständige definierte Funktionen
Satz 12
Minimalpolynome einer unvollständig definierten Funktionf : {0, 1}n → {0, 1, ∗} enthalten ausschließlich Primimplikantenvon f1.
Beweis Sei p = m1 ∨m2 ∨ · · · ∨mk Minimalpolynom von f .
Beobachtung p ist Realisierung von f .
Sei mi beliebiger Primimplikant in p.Beobachtung mi ist Implikant von f1.denn mi (x) = 1 ⇒ (f (x) = 1) ∨ (f (x) = ∗) ⇒ f1(x) = 1also Verkürzung m′ von mi ist Primimplikant von f1aber Ersetzen wir mi in p durch m
′, erhalten wir Polynom für f
klar m′ kann nicht echte Verkürzung von mi sein,sonst wäre p nicht Minimalpolynom zu f
also mi Primimplikant von f1Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Minimalpolynome unvollständig definierter
Funktionen
Algorithmus
1. Berechne Menge aller Primimplikanten PI(f1) zu f1.
2. Berechne minimale Überdeckung von f0 durch Monome aus PI(f1).
also algorithmisch keine neuen Probleme
Einwand Vielleicht lässt sich f0 gar nicht so überdecken?
Beobachtung Überdeckung von Nullen von f0 unproblematisch
Wieso eigentlich?Primimplikanten von f1 können nur Einsen oderdon’t cares von f überdecken!
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Hazards
ärgerlich, aber unvermeidlich Abweichungen zwischenModell und Realität
Das gilt auch für technisch realisierte Schaltnetze.
Was passiert, wenn die Eingabe wechselt?
klar Die Ausgabe kann wechseln.
Wunsch
◮ wenn f die Ausgabe wechselt, wechselt das Schaltnetz genaueinmal seine Ausgabe
◮ wenn f die Ausgabe nicht wechselt, wechselt das Schaltnetz seineAusgabe nicht
Realität Schaltnetz kann Ausgabe”zwischendurch“ wechseln.
Das heißt Hazard.Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Hazards: Begriffe
Hazards sind
◮ statisch Ausgabewert soll gleich bleiben, ändert sich aber.
◮ dynamisch Ausgabewert soll sich ändern, ändert sich abermehrfach.
◮ Funktionshazard”schon in der Funktionsdefinition enthalten“
◮ Schaltungshazard Hazard, der kein Funktionshazard ist
also vier verschiedene Fälle
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Statischer Funktionshazard
Definition
f : {0, 1}n → {0, 1} hat statischen Funktionshazard, wenn esa = a1a2 · · · an ∈ {0, 1}n und b = b1b2 · · · bn ∈ {0, 1}n mit a 6= bund f (a) = f (b) gibt, sowie c = c1c2 · · · cn ∈ {0, 1}
n mitci ∈ {ai , bi} für alle i ∈ {1, 2, . . . , n} und f (c) 6= f (a).
Beispielx1 x2 x3 f (x1, x2, x3)
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
1
0
0
1
0
0
0
0
1
0x3
00 01 11 10x1 x2
1
1
a = 000, f (a) = 1
b = 011, f (b) = 1
c = 010, f (c) = 0
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Dynamischer Funktionshazard
Definition
f : {0, 1}n → {0, 1} hat dynamischen Funktionshazard, wenn esa, b ∈ {0, 1}n mit a 6= b und f (a) 6= f (b) gibt, sowiec = c1c2 · · · cn und c
′ = c ′1c′2 · · · c
′n mit ci ∈ {ai , bi}, c
′i∈ {ci , bi}
(i ∈ {1, 2, . . . , n}) und f (c) 6= f (a) sowie f (c) 6= f (c ′).
Beispielx1 x2 x3 f (x1, x2, x3)
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
1
0
0
1
0
0
1
0
1
0x3
00 01 11 10x1 x2
1
1
1
0
a = 000, f (a) = 1
b = 111, f (b) = 0
c = 001, f (c) = 0
c ′ = 011, f (c ′) = 1
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Zusammenfassung: Statische/DynamischeHazards
Wir haben korrektes Schaltnetz S für f .
Wir betrachten Eingabewechsel von a auf b.
1. Funktionswert bleibt gleich: f (a) = f (b)Am Ausgang von S liegt kurzzeitig ein anderer Wert an.statischer Hazard
2. Funktionswert ändert sich: f (a) 6= f (b)Am Ausgang von S ändert sich der Wert mehrfach.dynamischer Hazard
Weitergehende Klassifikation
◮ Manche Hazard heißen Funktionshazards.
◮ Die übrigen Hazards heißen Schaltungshazards.
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Wie kommt es zum Funktionshazard?
Betrachte Eingabewechsel von a nach b mitentweder f (a) = f (b) statischoder f (a) 6= f (b) dynamisch
Es gibt statisch: 1 andere Eingabe cdynamisch: 2 andere Eingaben c , c ′
zwischen a und b,so dass der Funktionswert beim Weg von a nach b
statisch über c wechseltdynamisch über c und c ′ mehrfach wechselt
zentral andere Eingaben echt”dazwischen“
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Was bedeutet”dazwischen“?
in Bezug auf Eingabewechsel
◮ Wertänderung einiger Eingabebits (alle Bits mit ai 6= bi)
◮ nicht völlig gleichzeitig
◮ also”dazwischen“ = kann als Zwischenschritt bei Wertänderung
der Eingabebits vorkommen
beim Blick auf KV-Diagramm
◮ auf einem kürzsten Weg von a nach b
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Kürzeste Wege im KV-Diagramm
10
11
01
00
x3 x4
00 01 11 10x1 x2
a = 0000
b = 1110
Beobachtung 3 Bits verschiedenkürzeste Wege haben Länge 3(i.a.: n unterschiedliche Bits ⇒ kürzeste Weglänge = n)
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Funktionshazards
klar Funktionshazards sind in Realisierungen vonSchaltnetzen nicht zu vermeiden
zur Kenntnis nehmen Es gibt Hazards.
für uns interessanter Schaltungshazards
Definition Schaltzungshazard Funktion hatbezüglich a, b keinen Hazard,Schaltnetz aber schon
Fragen
1. Wie kann das passieren?
2. Kann man das vermeiden?Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Definition Schaltungshazard
Definition
Schaltnetz S für f hat einen statischen Schaltungshazard, wenn esa, b ∈ {0, 1}n gibt, so dass f bezüglich a, b keinen statischenFunktionshazard hat, aber beim Eingabewechsel von a nach b amAusgang von S nicht notwendig stabil f (a) anliegt.
Definition
Schaltnetz S für f hat einen dynamischen Schaltungshazard, wennes a, b ∈ {0, 1}n gibt, so dass f bezüglich a, b keinen dynamischenFunktionshazard hat, aber beim Eingabewechsel von a nach b amAusgang von S mehr als ein Funktionswertwechsel auftreten kann.
Beachte: Auftreten nicht garantiert!
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Beispiel statischer Schaltungshazard
f (x1, x2, x3) = x1 x2 ∨ x2 x3
x1 x2 x3 f (x1, x2, x3)
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
1
0
0
0
1
1
1
a = 111, f (a) = 1
b = 101, f (b) = 1
klar kein Funktionshazard
Gar kein c zwischen a und b!
x1&
x2
1&
x3
≥ 1
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Vermeidung von Schaltungshazards
Wir konzentrieren uns auf
◮ statische Schaltungshazards,
◮ Schaltnetze, die direkt Polynome realisieren.
Sind in solchen Schaltnetzen Schaltungshazards ganz vermeidbar?
gute Nachricht ja
schlechte Nachricht nicht kostenlos
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Wie vermeidet man statische
Schaltungshazards?
Satz
Sei S ein Schaltnetz, das direkt ein Polynom p einer booleschenFunktion f realisiert. S hat genau dann keinen statischenSchaltungshazard, wenn S für jeden Primimplikanten von f einUnd-Gatter enthält.
Beweis durch Widerspruch:statischer Schaltungshazard ⇔ ein Primimplikant fehlt
Beweistrategie
1. Beweise: statischer Schaltungshazard ⇒ ein Primimplikant fehlt
2. Beweise: Primimplikant fehlt ⇒ statischer Schaltzungshazard
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Hazard ⇒ Primimplikant fehlt
Voraussetzungen◮ Es gibt statischen Hazard bezüglich a und b.◮ Es gibt keinen Funktionshazard bezüglich a und b.◮ a und b unterscheiden sich in genau einem Bit
1. Fall f (a) = f (b) = 0klar alle Und-Gatter permanent 0also Wert am Ausgang permanent 0
also kein Hazard√
2. Fall f (a) = f (b) = 1Sei ma Minterm zu a, mb Minterm zu bBeobachtung ∃Monom m,Variable x : {ma,mb} = {mx ,m x}klar m ist Implikant von falso S enthält Und-Gatter für Verkürzung m′ von mBeobachtung Dieses Und-Gatter ist permant 1 (da unabh. vonx).
also Wert am Ausgang permanent 1 also kein Hazard√
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Primimplikant fehlt ⇒ Hazard
Voraussetzungen
◮ S realisiert direkt Polynom p für f
◮ ∃Primimplikant m von f : kein Und-Gatter für m in S
Definiere Eingaben a und b.
◮ xi ∈ m ai = bi = 1
◮ xi ∈ m ai = bi = 0
◮ sonst ai = 0, bi = 1
Beobachtung m(a) = m(b) = 1also f (a) = f (b) = 1Beobachtung kein Hazard ⇔ ein Und-Gatter permanent 1klar So ein Und-Gatter realisiert Verkürzung von m.also So ein Und-Gatter gibt es in S nicht.also Hazard
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Zusammenfassung: Hazards
Fazit Hazards
◮ Hazards sind ärgerlich.Wann liegt der richtige Funktionswert vor?
◮ Funktionshazards sind so nicht vermeidbar.
◮ Statische Schaltungshazards können mit zusätzlichem Aufwandvermieden werden.
◮ Eine grundsätzliche Lösung ist wünschenswert.
mögliche grundsätzliche Lösung: Taktung der Schaltung ⇒ später
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Realisierung von Schaltnetzen
Gedanken zur Anwendung
1. Problem
2. boolesche Funktion
3. Schaltnetz-Entwurf
4. Schaltnetz-Realisierung
Realisierungen
◮ hoch-integrierte Schaltungteuer Lohnt sich nur bei großen Stückzahlen.
◮ direkte Umsetzung mit Gatternumständlich
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Realisierung mit Gattern
Datenblatt von Texas Instruments (www.ti.com)
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Alternative Realisierung
◮ massenhaft produzierte
◮ darum preisgünstige
◮ nach der Fertigstellung in ihrer Funktion noch beeinflussbare
◮ funktional vollständige
◮ also universelle Standardbausteine
Programmable Logic Array (PLA)
Varianten PAL, PROM, FPGA, . . .(zum Teil eingeschränkte Funktionalität)
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Programmable Logic Array (PLA)
Datenblatt von Lattice (www.latticesemi.com)
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
PLA Grundbausteine
y f1(x , y)
x
f2(x , y)
t
Name Typ f1(x, y) f2(x, y)
Identer 0 y xAddierer 1 x ∨ y xMultiplizierer 2 y x yNegat-Multiplizierer 3 y x y
klar funktional vollständig
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
PLA
t4,0
t3,0
t2,0
t1,0
t0,0
t4,1
t3,1
t2,1
t1,1
t0,1
t4,2
t3,2
t2,2
t1,2
t0,2
t4,3
t3,3
t2,3
t1,3
t0,3
t4,4
t3,4
t2,4
t1,4
t0,4
t4,5
t3,5
t2,5
t1,5
t0,5
t4,6
t3,6
t2,6
t1,6
t0,6
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
PLA für f : {0, 1}3 → {0, 1}
1 1 1 1 1 1
0
x3
x2
x1
t3,0
t2,0
t1,0
t0,0
t3,1
t2,1
t1,1
t0,1
t3,2
t2,2
t1,2
t0,2
t3,3
t2,3
t1,3
t0,3
t3,4
t2,4
t1,4
t0,4
t3,5
t2,5
t1,5
t0,5
f (x1, x2, x3)
Wie wählt man die Bausteintypen?Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
PLA: Bausteinwahl
klar jede Funktion als Polynom darstellbar
Erinnerung Polynom = Disjunktion einiger Monome
erster Schritt
Wie realisieren wir Monome?
exemplarisch am Beispiel x1 x2 x4
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
PLA: Monomrealisierung
Beispiel Monom x1 x2 x4
1x1
x2
x3
x4
Erinnerung
Name Typ fr(o, l) fu(o, l)
Identer 0 l oAddierer 1 o ∨ l oMultiplizierer 2 l o l
Negat-Multiplizierer 3 l o l
2 x11 ∧ x1 = x1
3 x2x1 x2
0 x3x1 x2
2 x4
x1 x2 x4
also jedes Monom leicht realisierbar
◮ falls Variable fehlt Typ 0
◮ falls xi vorkommt Typ 2
◮ falls xi vorkommt Typ 3
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
PLA: Polynomrealisierung
gesehen für f : {0, 1}n → {0, 1}k verschiedene Monome m1, m2, . . . , mkin n Zeilen und k Spalten realisierbar
Wie können wir f realisieren, z. B. f = m1 ∨m2 ∨m4?
0
m1 m2 m3 m4
Erinnerung
Name Typ fr(o, l) fu(o, l)
Identer 0 l oAddierer 1 o ∨ l oMultiplizierer 2 l o l
Negat-Multiplizierer 3 l o l
1m1
1m1 ∨m2
0m1 ∨m2
1 m1 ∨m2 ∨m4
Ist das sinnvoll?klar fürf : {0, 1}n → {0, 1}
nichtaber fürf : {0, 1}n → {0, 1}m
schonBoole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
PLA: Ein konkretes Beispiel
Beispiel f (x1, x2, x3, x4) = x1 x2 x4 ∨ x2 x3 x4 ∨ x1 x3 x4 ∨ x2 x3
0
x4
x3
x2
x1
1 1 1 1
f (x1, . . . , x4)1 1 1 1
2 2 2 0
0 2 2 2
2 2 0 3
3 0 3 0
Und-Teil
Oder-Teil
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Fazit zur PLA-Nutzung
also Wir können jede Funktion f : {0, 1}n → {0, 1}m,für deren Polynom insgesamt k Implikanten ausreichen,mit einem PLA mit n +m Zeilen und k Spalten realisieren.
klar Wir wünschen uns k klein.
dafür Minimalpolynome
Wie findet man Minimalpolynome für Funktionenf : {0, 1}n → {0, 1}m?
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Minimalpolynome für f : {0, 1}n → {0, 1}m
Notation statt f : {0, 1}n → {0, 1}m
(f1, f2, . . . , fm) mit fi : {0, 1}n → {0, 1}
für i ∈ {1, 2, . . . ,m}
Definition Ein Minimalpolynom für f : {0, 1}n → {0, 1}m
ist (p1, p2, . . . , pm) mit minimalen Kosten,dabei ist pi Polynom für fi . Bei den Kostenzählen mehrfach vorkommende Monome nur einmal.
Also suchen wir Minimalpolynome pi für fi? Nein!
Beispiel p1(x1, x2, x3) = x1 x3 ∨ x2 x3 ist Minimalpolynomp2(x1, x2, x3) = x1 x2 ∨ x2 x3 ist Minimalpolynom
p′1(x1, x2, x3) = x1 x2 x3 ∨ x2 x3 stellt auch p1 darp′2(x1, x2, x3) = x1 x2 ∨ x1 x2 x3 stellt auch p2 dar
Gesamtkosten (p1, p2) = (n +m)× k = (3 + 2)× 4Gesamtkosten (p′1, p
′2) = (n +m)× k
′ = (3 + 2)× 3Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Monome für Minimalpolynome für
f : {0, 1}n → {0, 1}k
Welche Monome übernehmen die Rolle der Primimplikanten?
Definition Ein Monom m ist ein multipler Primimplikantvon f = (f1, f2, . . . , fk) mit fi : {0, 1}
n → {0, 1},wenn m Primimplikant von
∧
i∈I
fi ist für eine
nicht-leere Menge I ⊆ {1, 2, . . . , k}.
Theorem Minimalpolynome für f : {0, 1}n → {0, 1}k enthaltennur multiple Primimplikanten von f .
Beweis und Algorithmus zur Berechnung → Skript
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Multiple Primimplikanten berechnen
Wie finden wir alle multiplen Primimplikanten?
Theorem m ∈ PI
(
∧
i∈Ifi
)
⇒ ∀i ∈ I : ∃mi ∈ PI(fi) : m =∧
i∈Imi
Beweis
klar m ∈ PI
(
∧
i∈I
fi
)
ist für alle i ∈ I Implikant von fi
Sei mi ∈ PI(fi) Verkürzung von m (i ∈ I )klar
∧
i∈I
mi ist Verkürzung von m
weil m ∈ PI
(
∧
i∈I
fi
)
, kann∧
i∈I
mi keine echte Verkürzung
von m sein
also∧
i∈Imi = m
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Berechnung aller multipler Primimplikanten
Algorithmusberechnet für I ⊆ {1, 2, . . . , k} die Menge MI der multiplenPrimimplikanten m =
∧
i∈I
mi
1. Für i ∈ {1, 2, . . . , k} berechne M{i} := PI(fi ).
2. M :=k⋃
i=1
{
{i}}
; M ′ :=k⋃
i=1M{i}.
3. Wiederhole
4. Für I , J ∈ M mit I ∩ J = ∅
5. MI∪J := {m 6= 0 | m = m′m′′ mit m′ ∈ MI , m
′′ ∈ MJ ,keine echte Verkürzung von m in MI∪J}.
6. M := M ∪ {I ∪ J}; M ′ := M ′ ∪MI∪J .
7. So lange, bis M ′ eine Iteration unverändert bleibt.
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Minimalpolynomberechnung für
f : {0, 1}n → {0, 1}m
Algorithmus
1. Für alle fi berechne alle Primimplikanten.
2. Berechne alle multiplen Primimplikanten.(ergeben sich potentiell als paarweise Verknüpfung“normaler”Primimplikanten)
3. Berechne eine möglichst günstige Überdeckung.
also günstigste Darstellung für PLA-Realisierungenmit uns bekannten Mitteln berechenbarallerdings sehr aufwendig
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
PLA als ROM
Aufgabe Speichere 2n”Wörter“ der Länge m.
w0 = w0,0w0,1w0,2 · · ·w0,m−1 ∈ {0, 1}m
w1 = w1,0w1,1w1,2 · · ·w1,m−1 ∈ {0, 1}m
w2 = w2,0w2,1w2,2 · · ·w2,m−1 ∈ {0, 1}m
......
w2n−1 = w2n−1,0w2n−1,1w2n−1,2 · · ·w2n−1,m−1 ∈ {0, 1}m
Benutze PLA mit n+m Zeilen, 2n Spalten
Beobachtung m · 2n Zellen für m · 2n zu speichernde Bitsmindestens erforderlich
Adressierung mit jeweils n Bitsin n zusätzlichen Zeilen
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Beispiel
n = 3, m = 6
23 = 8 Wörterjeweils 6 Bits
x0
x1
x2
1 1 1 1 1 1 1 1
0 w0,5 w1,5 w2,5 w3,5 w4,5 w5,5 w6,5 w7,5
0 w0,4 w1,4 w2,4 w3,4 w4,4 w5,4 w6,4 w7,4
0 w0,3 w1,3 w2,3 w3,3 w4,3 w5,3 w6,3 w7,3
0 w0,2 w1,2 w2,2 w3,2 w4,2 w5,2 w6,2 w7,2
0 w0,1 w1,1 w2,1 w3,1 w4,1 w5,1 w6,1 w7,1
0 w0,0 w1,0 w2,0 w3,0 w4,0 w5,0 w6,0 w7,0
3 3 3 3 2 2 2 2
3 3 2 2 3 3 2 2
3 2 3 2 3 2 3 2 Beobachtung
Und-Teil fest
nur von Größeabhängig
Anmerkung
PLAs mit festem
Und-Teil werden
als PROM
verkauft.
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Zwischen-Fazit PLAs
PLAs sind preiswerte, universelle Bausteine, die
◮ beliebige boolesche Funktionen leicht realisierbar machen,
◮ Minimalpolynomdarstellungen motivieren,
◮ Speicherung von 2n Wörtern der Länge m in einem(n +m)× 2n-PLA erlauben.
Nachteil nur einmal programmierbar
Wie kann man PLAs beliebig neu programmierbar machen?
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
”Software“-PLAs
Typ
f2(x , y)
f1(x , y)
x
y
Typ s t f1(x , y) f2(x , y)
0 0 0 y x1 0 1 x ∨ y x2 1 0 y x y3 1 1 y x y
klar vier verschiedene Typen, mit zwei Bits codierbar
Idee erweitere PLA-Baustein um zwei zusätzliche Eingaben,die den Baustein-Typ codieren
jetzt f1 und f2 als Funktionen von (s, t, x , y) darstellen
◮ f1(s, t, x , y) = y ∨ s t x
◮ f2(s, t, x , y) = s x ∨ s x(t ⊕ y)
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Bemerkung zum Einsatz
klar für ein n×m-PLA werden zur Programmierung2nm Bits gebraucht.
Beobachtung Man kann diese 2nm Bits gutin einem PROM speichern.
Fazit
◮ einfache und günstige Realisierung von booleschen Funktionen
◮ besonders geeignet für kleine Stückzahlen
◮ besonders geeignet bei nur temporärem Gebrauch
Boole. Fkt. KV-Diagramme (Wiederholung) Wdh. Quine/McCluskey Partiell definierte Funktionen Hazards PLAs
Boolesche Funktionen und SchaltnetzeKV-Diagramme (Wiederholung)Algorithmus von Quine und McCluskey (Wiederholung)Unvollständig definierte FunktionenEinleitungMinimalpolynome für partiell definierte Funktionen
HazardsEinleitungSchaltungshazards
Programmierbare BausteineEinleitungEinsatz von PLAs