45
Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Informatik 2 Grundlagen der Digitaltechnik Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen 4. Minimierung digitaler Schaltfunktionen Prof. Dr. Prof. Dr. - - Ing. Jürgen Teich Ing. Jürgen Teich Dr. Dr. - - Ing. Christian Ing. Christian Haubelt Haubelt Lehrstuhl für Hardware Lehrstuhl für Hardware - - Software Software - - Co Co - - Design Design

Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

  • Upload
    hakhue

  • View
    243

  • Download
    1

Embed Size (px)

Citation preview

Page 1: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Grundlagen der Digitaltechnik

Grundlagen der Informatik 2Grundlagen der Informatik 2Grundlagen der DigitaltechnikGrundlagen der Digitaltechnik

4. Minimierung digitaler Schaltfunktionen4. Minimierung digitaler Schaltfunktionen

Prof. Dr.Prof. Dr.--Ing. Jürgen TeichIng. Jürgen TeichDr.Dr.--Ing. Christian Ing. Christian HaubeltHaubelt

Lehrstuhl für HardwareLehrstuhl für Hardware--SoftwareSoftware--CoCo--DesignDesign

Page 2: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 2

Minimierung (Optimierung)Minimierung (Optimierung)

• Aus den schaltalgebraischen Ausdrücken ist ersichtlich, dass der Beschreibungsaufwand sinkt, je wenigerTerme vorhanden sind bzw. je mehr Literale aus den Termen entfallen

– Bei der schaltungstechnischen Realisierung zeigt sich ebenfalls, dass entsprechende Aufwendungen für logische Gatter von den Termen und den verwendeten Literalen abhängen

Page 3: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 3

Minimierung (Optimierung)Minimierung (Optimierung)

– Bei der DNF (KNF) benötigt man für jede Einsstelle (Nullstelle) einen Minterm (Maxterm)-> durch gezieltes Weglassen von Literalen in einem Minterm

(Maxterm) kann dieser Term mehrere Einsstellen (Nullstellen)repräsentieren-> Anzahl der benötigten Terme und Literale wird reduziert-> Minimierung von Schaltfunktionen!

Page 4: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 4

MinimierungMinimierung

• Beispiele

12341234 x&x&x&x)x,x,x,x(f = )}1,0,0,1{(E = 1E =

1341234 x&x&x)x,x,x,x(f = )}1,1,0,1(),1,0,0,1{(E = 2E =

131234 x&x)x,x,x,x(f = )}1,1,0,1(),1,0,0,1(),1,1,0,0(),1,0,0,0{(E = 4E =

Also: die Reduzierung von Literalen in einem Term hat auch die Reduzierung der Anzahl von Termen zur Folge

Gesucht: Terme mit minimaler Anzahl von Literalen, die trotzdem nur Einsstellen (Nullstellen) der zu beschreibenden Funktion erfassen, werden Primterme genannt

Page 5: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 5

MinimierungMinimierung

• Primterme und Eins- bzw. Nullstellenüberdeckung– Einsstellen (Nullstellen) verschiedener Primterme können

“überlappen“

– (kosten)günstigste Auswahl von Primtermen gesucht, die alleEinsstellen (Nullstellen) der Funktion überdecken

• Überdeckungsproblem!

– das Gesamtproblem nennt man das Minimierungsproblem

• Bewertungskriterium– zur Bewertung unterschiedlicher Lösungen des

Minimierungsproblems wird die Summe der Anzahl von Literalen aller Primterme zuzüglich der Zahl der verwendeten Terme verwendet

Page 6: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 6

MinimierungMinimierung

• Beispiel:

• Gesucht: Auswahl von Primtermen mit L(y) minimal

( ) ( ) ( )

( ) 123234yL

x&xx&x&xx&x&x&xy 352341234

=+++=

∨∨=

Page 7: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 7

MinimierungsmethodenMinimierungsmethoden

• Minimierung am Symmetriediagramm– Die Minimierung mit

Symmetriediagrammstellt eine graphischeMethode dar-> Ausnutzung derSymmetrierelationen

– Zusammenfassungvon Belegungenzu maximalen Blöcken

-> Finden aller Primblöcke(charakteristische Terme also Primterme)-> Überdeckung aller Einsstellen (bzw. Nullstellen)

0 011

0 110

0 -10

- 001

x1

x2

x3

x4

10

2 3

5 4

6

16

7

1415

17

1110

1312

Page 8: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 8

MinimierungsmethodenMinimierungsmethoden

• Minimierung am Symmetriediagramm

- Finden von Primblöcken (Primtermen) in Symmetriediagrammen

- Sukzessive Bildung von Blöcken aus Einsstellen (Nullstellen)und Freistellen durch Spiegelung von kleineren Blöcken (einzelne Einsstellen sind kleinste Blöcke) an allen möglichen Symmetrielinien

• Maximal zusammengefasste Blöcke von Einsstellen sind Primeinsblöcke, wenn keine Spiegelung mehr möglich

Page 9: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 9

MinimierungsmethodenMinimierungsmethoden

Page 10: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 10

• Minimierung am Symmetriediagramm• Beispiel (1):

– Gegeben:y = f (x4, x3, x2, x1) durch die Angabe der Eins- und Nullstellenim Symmetriediagramm

– Gesucht:Kürzester algebraischer Ausdruck-> Disjunktive Minimalform (DMF)

– Primterme zur Bildung einer DMF spezifizierenPrimeinsblöcke-> werden Primimplikanten genannt

(Primimplikate für Konjunktive Minimalform KMF)

– Die farbig dargestellten Primimplikantenüberdecken Eins- und Freistellen

0 011

0 110

0 -10

- 001

x1

x2

x3

x4

10

2 3

5 4

6

16

7

1415

17

1110

1312

MinimierungsmethodenMinimierungsmethoden

Page 11: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 11

MinimierungsmethodenMinimierungsmethoden

• Minimierung am Symmetriediagramm• Beispiel (2):

– Als Primimplikanten erhält man:

Vorgehensweise:-> Auswahl derjenigen Primimplikanten, die allein eine Einsstelle

überdecken (diese müssen genommen werden)-> sogenannte Kerne

-> sind durch die Kerne alle Einstellen überdeckt-> Minimallösung

-> sonst:sonst: Auswahl weiterer Primimplikanten(Strategie + Bewertung notwendig!)

231 xxw =1242 xxxw = 1343 xxxw = 1234 xxxw = 2345 xxxw =

Page 12: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 12

MinimierungsmethodenMinimierungsmethoden

• Mögliche Lösung:

421 wwwy ∨∨=

0 011

0 110

0 -10

- 001

x1

x2

x3

x4

10

2 3

5 4

6

16

7

1415

17

1110

1312

Page 13: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 13

MinimierungsmethodenMinimierungsmethoden

• Formale algebraische Minimierung-> Das Nelson/Petrick-Verfahren

– sehr leistungsfähiges algebraisches Verfahren

– Nelson-Verfahren: Bestimmung der Menge aller Primimplikanten(bzw. Primimplikate)

– Petrick-Verfahren: Bestimmung der kostenminimalen Auswahlvon Primimplikanten zur Einsstellenüberdeckung(bzw.Primimplikate zur Nullstellenüberdeckung)

Alternativ: graphisch mit Überdeckungstabelle+ Regeln zur Abarbeitung/Vereinfachung

Ergebnis: kostenminimaler algebraischer Ausdruck der zu realisierenden Schaltfunktion

Page 14: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 14

MinimierungsmethodenMinimierungsmethoden• Nelson-Verfahren:

Ziel: Bestimmung aller Primimplikanten zur Bildung einerdisjunktiven Minimalform DMF(dual dazu: alle Primimplikate für KMF)

Vorgehensweise:

1) alle Freistellen werden zu Einsstellen verfügt: Einsstellenergänzung fE

-> Bildung einer Nullblocküberdeckung für die Einsstellenergänzung fE der gegebenen (unvollständigen) Schaltfunktion: τ0 = {B01,B02,...,B0r}

2) Aufstellen eines schaltalgebraischen Ausdrucks (KNF bzw. KMF)für die Einsvervollständigung fE: fE = W01 & W02 & ... & W0r

Page 15: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 15

MinimierungsmethodenMinimierungsmethoden

3) Schrittweises Ausdistribuieren des Ausdrucks fE = W01 & W02 & ... & W0r aus 2) + Umformen und Streichen überflüssiger Termanteile bzw. Terme

– Anwendung von Distributiv- und Absorptionsgesetzen– aus der konjunktiven Form die gewünschte disjunktive Form

bestimmen

4) Streichen aller im 3. Schritt gefundenen Terme, die nur Freistellenüberdecken

Wiederholung:

Distributivgesetz: (a v b) & (c v d) = (a&c) v (a&d) v (b&c) v (b&d)Absorptionsgesetz: a v (a&b) = a Ferner gilt: a&a = a, bzw. a v a = a und a&a = 0, bzw. a v a = 1

Page 16: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 16

MinimierungsmethodenMinimierungsmethoden• Nelson-Verfahren:• Beispiel:

– Man nehme eine Nullblocküberdeckung:

– Durch Ausdistribuieren + Umformung erhält man:

1 0 0 1

- 0 1 -x2

x3

x1

)xx(&)xx(f 3121

E∨∨=

1 0 0 1

- 0 1 -

x1

x2

x3

Distributivgesetz

gleiches Element

Absorption

Absorption

)x&x(xxxx

xxxxx

xxxxxxxxxxxxxxx

)xx(&)xx(f

321

321

32211

3221311

32213111

3121

E

∨=

∨=

∨∨=

∨∨∨=

∨∨∨=

∨∨=

Page 17: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 17

MinimierungsmethodenMinimierungsmethoden

• Satz: Jedes Minimalpolynom p einer Schaltfunktion fbesteht ausschließlich aus Primimplikanten von f.

• Überdeckungsproblem (hier auch Auswahlproblem genannt)

– Bei dem Nelson-Verfahren erfolgte nur die Ermittlung aller Primterme

– Weiterhin gesucht: optimale Auswahl der Primterme, wobei eine vollständige Überdeckung aller Einsstellen der gewünschten Funktion gefordert ist.

Page 18: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 18

MinimierungsmethodenMinimierungsmethoden

• Lösung: graphische Auswahl der Primterme mit Überdeckungstabelle

-> für jeden Primterm wird angegeben, welche Einsstellen(bzw. Nullstellen) er überdeckt

-> zur Bewertung wird eine Spalte mit Kosten ck angefügt

-> Überdeckungstabelle wird mit Hilfe bestimmter Regeln abgearbeitet (vereinfacht) -> Kernermittlung + Dominanzregel

-> es ist auch eine algebraische Behandlung der optimalen Auswahl von Primtermen möglich

-> Bildung des Petrick-Ausdrucks!

• Ergebnis: kostenminimale Überdeckung der Eins- bzw. Nullstellenmenge der Schaltfunktion

Page 19: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 19

MinimierungsmethodenMinimierungsmethoden

• Überdeckungsproblem– Beispiel:

j k Pl 0 2 4 11 12 14 16 pi ci

1 24xx x x p1 c1

223xx x x p2 c2

3134 xxx x x p3 c3

4134 xxx x p4 c4

5124 xxx x x p5 c5

6134 xxx x x p6 c6

7123 xxx x x p7 c7

x4

1 0 0 1

1 0- -

1 1- -

0 1 0 1

0 1

2 3

5 4

7 6

1415

1617

10 11

12 13

x1

x2

x3

Page 20: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 20

MinimierungsmethodenMinimierungsmethoden

• Überdeckungsproblem• Kernermittlung

– Wenn eine Einsstelle (Nullstelle) nur durch einen einzigenPrimterm abgedeckt wird, nennt man den Primimplikanten(Primimplikaten) Kernimplikant (Kernimplikat)

– Kernimplikanten (Kernimplikate) müssen auf jeden Fall in die Überdeckungslösung aufgenommen werden

– Spalten von Einsstellen (Nullstellen) in der Überdeckungstabelle, die von Kernimplikanten (Kernimplikaten) abgedeckt werden können gestrichen werden, und müssen in der weiteren Abarbeitung nicht mehr berücksichtigt werden

Page 21: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 21

MinimierungsmethodenMinimierungsmethoden

• Kernermittlung und Vereinfachung der Überdeckungstabelle

• Beispiel: j k Pl 0 2 4 11 12 14 16 pi ci

1 24xx x x p1 c1

2 23xx x x p2 c2

3 134 xxx x x p3 c3

4 134 xxx x p4 c4

5124 xxx x x p5 c5

6 134 xxx x x p6 c6

7 123 xxx x x p7 c7

Page 22: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 22

MinimierungsmethodenMinimierungsmethoden

• Dominanzregeln und Ihre Anwendung (1)• Spaltendominanzregeln:

– Spaltendominanz in der Überdeckungstabelle:

i1 i2X X p1

p2

X X p3

X p4

X p5

i1 i2X X p1

p2

X X p3

X p4

X p5

Page 23: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 23

MinimierungsmethodenMinimierungsmethoden

– Wenn die Spalte i2 durch einen der beiden Terme p1 oder p3

überdeckt wird, so wird dadurch auch i1 überdeckt Also: Einsstelle der Spalte i1 ist durch p1 oder p3 auch realisiert

– Man sagt: (“Vektor“ i1) dominiert (“Vektor“ i2) und schreibt: i1 ≥ i2

– Dominierende Spalten (hier: i1) können gestrichen werden

Page 24: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 24

MinimierungsmethodenMinimierungsmethoden

• Dominanzregeln und Ihre Anwendung (2)

• Zeilendominanzregeln:

X X X X c1

X c2

...X X X ck

p1

p2

pk

i 1

i 2

i k

X X X X c1

X c2

...X X X ck

p1

p2

pk

i 1

i 2

i k

i 1

i 2

i k

X X X X c1

X c2

...X X X ck

p1

p2

pk

i 1

i 2

i k

X X X X c1

X c2

...X X X ck

p1

p2

pk

i 1

i 2

i k

X X X X c1

X c2

...X X X ck

p1

p2

pk

i 1

i 2

i k

i 1

i 2

i k

Page 25: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 25

MinimierungsmethodenMinimierungsmethoden

– Wenn eine Zeile i2 (für Primterm p2) nur Spalten (Einsstellen) überdeckt, die auch von einer anderen Zeile i1 (für Primterm p1) überdeckt werden (d.h. i2 wird von i1 dominiert: i2 ≤ i1) undzusätzlich für die Kosten c1 ≤ c2 gilt. Dann kann die Zeile i2 gestrichen werden.

– Weiterhin: Wenn i2 ≤ i1 , jedoch c2 < c1 und es existieren keine Zeilen ik (Primterme pk), welche die restlichen Einsstellen der Zeile i1 überdecken können und weniger als die Differenz c1 - c2

kosten (d.h.: c1 ≤ c2 + ck). Dann kann die Zeile i2 auch gestrichen werden.

Page 26: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 26

MinimierungsmethodenMinimierungsmethoden

• Überdeckungsproblem

– Um die optimale Überdeckung der Schaltfunktion durch eine optimale Auswahl von Primtermen zu ermitteln, kann das Problem durch die vorgestellten Regeln graphischvereinfacht oder komplett gelöst werden

– Achtung: Oft endet das Verfahren mit einer sog. zyklischen Resttabelle (wenn keine der Regeln mehr anwendbar ist, aber noch keine Überdeckung gefunden wurde)

Page 27: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 27

MinimierungsmethodenMinimierungsmethoden

• Allgemeine Vorgehensweise:

1) Kerne bestimmen und Streichen aller überdeckten Spalten(≅ Einsstellen) (“leergewordene“ Zeilen können auch gestrichen werden)

2) Spaltendominanzen finden und dominierende Spalten streichen

3) Zeilendominanzen finden und dominierte Zeilen streichen nach Möglichkeit (hängt von Kosten ab)

4) Schritte 1-3 wiederholen, bis Überdeckungstabelle nicht mehr reduziert werden kann (keine Änderung mehr möglich)

Page 28: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 28

Beispiel: Zyklische ResttabelleBeispiel: Zyklische Resttabelle

jk Pl 0 2 4 11 12 14 16 pi ci

1 24xx x x p1 2

2 23xx x x p2 2

3 134 xxx x x p3 3

4 134 xxx x p4 3

5 124 xxx x x p5 3

6 134 xxx x x p6 3

7 123 xxx x x p7 3

Page 29: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 29

MinimierungsmethodenMinimierungsmethoden

• Lösung des Überdeckungsproblems mit Hilfe des Petrick-Verfahrens– Das Petrick-Verfahren ist eine algebraische Methode, ähnlich

dem Nelson-Verfahren. Es dient zur Bestimmung kostenminimaler Lösungen von Überdeckungsproblemen

– Es kann direkt nach dem Nelson-Verfahren zur kostenminimalen Auswahl von Primtermen verwendet werden

– Spaltendominanzen und Zeilendominanzen können algebraischin Form von Absorptionsregeln bzw. Ausdistribuierenabgearbeitet bzw. bewiesen werden

– Petrick-Verfahren kann auch bei zyklischen Resttabellenverwendet werden!

Page 30: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 30

MinimierungsmethodenMinimierungsmethoden

• Petrick-Ausdruck (PA)

– Der Petrick-Ausdruck ist algebraische Beschreibung der ÜberdeckungsbedingungenOb der Primterm k zur Lösung gehört, wird mit der Booleschen

Präsenzvariable (Auswahlvariable) pk angegeben-> pk = 0 => Primterm k ist nicht in Lösung enthalten-> pk = 1 => Primterm k ist Bestandteil der Lösung

-> zur Überdeckung jeder Einsstelle muss mindestens ein Primterm zur Lösung gehören, der diese Stelle überdeckt

Page 31: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 31

MinimierungsmethodenMinimierungsmethoden

– Petrick-Ausdruck besteht daher aus Termen von disjunktivverknüpften Präsenzvariablen

-> für jede Einsstelle der Tabelle enthält der PA einen Term-> in jedem Term muss mindestens eine Präsenzvariable den

Wert ´1´ haben

– Diese Terme werden konjunktiv zum Petrick-Ausdruck verknüpft-> der Petrick-Ausdruck muss immer eins liefern!

Page 32: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 32

MinimierungsmethodenMinimierungsmethoden

• Beispiel: j k Pl 0 2 4 11 12 14 16 pi ci

1 24 xx x x p1 c1

2 23 xx x x p2 c2

3 134 xxx x x p3 c3

4 134 xxx x p4 c4

5124 xxx x x p5 c5

6 134 xxx x x p6 c6

7 123 xxx x x p7 c7

1)pp(&)pp(&)pp(&p&)pp(&)pp(&)pp(PA!

3173214756265 =∨∨∨∨∨∨=

Im Petrick-Ausdruck kann man erfassen (beweisen!), dass die Präsenzvariablen der Kernimplikanten (p4) immer eins sein müssen

Page 33: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 33

MinimierungsmethodenMinimierungsmethoden

• Überdeckungsproblem (Auswahlproblem)– Auch der Petrick-Ausdruck wird durch Distributionsregeln

und Absorptionsregeln vereinfacht

• Beispiel:

1)pppppppppppppppppp(&p1ppppppppppppppppppppppp

...1)pp(&)pp(&)pp(&p&)pp(&)pp(&)pp(PA

7521763265315327614

75421764326543154327641

3173214756265

=∨∨∨∨=

=∨∨∨∨==

=∨∨∨∨∨∨=

1pppppppppppppppppppppppPA 75421764326543154327641 =∨∨∨∨=

Page 34: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 34

MinimierungsmethodenMinimierungsmethoden

• Überdeckungsproblem (Auswahlproblem)

– Damit der Petrick-Ausdruck ´1´ wird, muss mindestens einerder disjunktiv verknüpften konjunktiven Teilterme eins sein

– Jeder konjunktive Teilterm repräsentiert genau eine mögliche Lösung des Auswahlproblems

– Vergleich der Gesamtkosten K aller möglichen LösungenDadurch können diejenigen Überdeckungen mit minimalen Kosten ermittelt werden

– Zur Auswahl der optimalen Lösung werden die Kosten ck der Primterme pk herangezogen (Anzahl der Literale von pk)

Page 35: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 35

MinimierungsmethodenMinimierungsmethoden

• Beobachtung: Jeder Term stellt eine Überdeckung dar.• Beispiel: Bestimmung einer kostenminimalen Überdeckung

durch Evaluation und Vergleich der Kosten:

1pppppppppppppppppppppppPA 75421764326543154327641 =∨∨∨∨=

K=2+3+3+3+4=15

K=2+3+3+3+4=15

K=2+3+3+3+3+5=19

K=2+3+3+3+3+5=19

K=2+2+3+3+3+5=18

Page 36: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 36

MinimierungsmethodenMinimierungsmethoden

• Überdeckungsproblem (Auswahlproblem)• Beispiel: 1pppppppppppppppppppppppPA 75421764326543154327641 =∨∨∨∨=

jk Pl 0 2 4 11 12 14 16 pi ci

1 x2x4 x x p1 c1=22 x2x3 x x p2 c2=2

3 x1x3x4 x x p3 c3=3

4 x1x3x4 x p4 c4=3

5 x1x2x4 x x p5 c5=3

6 x1x3x4 x x p6 c6=3

7 x1x2x3 x x p7 c7=3

p1p4p6p7 K = 15p2p3p4p5 K = 15p1p3p4p5p6 K = 19p2p3p4p6p7 K = 19p1p2p4p5p7 K = 18

Damit ergeben sich zwei kostenminimale Lösungen:p1p4p6p7 und p2p3p4p5

Page 37: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 37

Beispiel einer minimalen ÜberdeckungBeispiel einer minimalen Überdeckung

jk Pl 0 2 4 11 12 14 16 pi ci

1 24xx x x p1 2

2 23xx x x p2 2

3 134 xxx x x p3 3

4 134 xxx x p4 3

5 124 xxx x x p5 3

6 134 xxx x x p6 3

7 123 xxx x x p7 3

5432 ppppy ∨∨∨=

Kosten K:2+3+3+3+4=15

Page 38: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 38

MinimierungsmethodenMinimierungsmethoden

• Beispiel:– die zugehörigen disjunktiven Minimallösungen (DMF)

mit nur 11 Literalen und 4 Termen (Kosten K=15) sind:

x3

x2

x1

x4

1 0 0 1

1 0- -

1 1- -

0 1 0 1

y2

y2

x2

x1

x4

1 0 0 1

1 0- -

1 1- -

0 1 0 1

x3y1

y1

124134134232123124134241 xxxxxxxxxxxyundxxxxxxxxxxxy ∨∨∨=∨∨∨=

Page 39: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 39

QuineQuine/McCluskey/McCluskey--VerfahrenVerfahren

• Das Quine/McCluskey-Verfahren arbeitet ebenfalls in den zwei Schritten:– Bestimmung der Primimplikanten und – Lösung des Überdeckungsproblems.

• Das Verfahren lässt sich einfach in ein Programm zurautomatischen Vereinfachung von Schaltfunktionenumsetzen.

Page 40: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 40

QuineQuine/McCluskey/McCluskey--VerfahrenVerfahren• Vorgehensweise zur Bestimmung der Primimplikanten (1):

1) Bildung der Disjunktiven Normalform DNF(Alle Belegungen der Redundanzmenge werden zu 1 gewählt und mit berücksichtigt)

2) Sortiere die Implikanten (der Länge i=n) derart, dass sie nach Anzahl ihrer negierten Literale j zu Klassen Qi,j zusammengefasst sind.

3) Implikanten benachbarter Klassen Qi,j und Qi,j-1 werden durch Anwendung des Distributivgesetzes zu einer neuen Klasse Qi-1,j-1zusammengefasst. Die zusammengefassten Terme der Klassen Qi,j und Qi,j-1 werden (als berücksichtigt) markiert.Reduktionsregel: (x & y) v (x & y) = x & (y v y) = xIst ein zusammengefasster Term schon in der Klasse Qi-1,j-1enthalten, so wird dieser nicht ein weiteres Mal eingetragen.

Page 41: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 41

QuineQuine/McCluskey/McCluskey--VerfahrenVerfahren

• Vorgehensweise zur Bestimmung der Primimplikanten (2):

Der Arbeitsschritt wird wiederholt, bis keine weiteren Verkürzungen mehr möglich sind.

4) Alle nicht beim Zusammenfassen von benachbarten Klassen Qi,j und Qi,j-1 berücksichtigten Terme sind die Primimplikanten.

5) Überdeckt ein Primimplikant nur Elemente der Redundanzmenge, so wird er verworfen.

Page 42: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 42

QuineQuine/McCluskey/McCluskey--VerfahrenVerfahren

• Beispiel (1):1) DNF

f =11

x1

x2

x3

x4

10

2 3

5 4

6

16

7

1415

17

1110

1312

_ _ _x4 x3 x2 x1 v

_ _x4 x3 x2 x1 v

_ _x4 x3 x2 x1 v

1

1

1

1

_x4 x3 x2 x1 v

_ _x4 x3 x2 x1 v x4 x3 x2 x1 v

-

-

_x4 x3 x2 x1

Redundanzmenge wird mit berücksichtigt!

2) Sortierung der MintermeQ4,4 = { }Q4,3 = { }Q4,2 = { }Q4,1 = { }Q4,0 = { }

_ _ _x4 x3 x2 x1 ,

x4 x3 x2 x1

00

00

00

0

_ _x4 x3 x2 x1 ,

_ _x4 x3 x2 x1 ,

_ _x4 x3 x2 x1 _

x4 x3 x2 x1 ,_

x4 x3 x2 x1

_ _ _x4 x3 x2 x1

_ _ _x4 x3 x2 x1 v

In der Klasse Q4,2 befinden sich nur Implikanten mit 4 Literalen, wovon 2 negierte Literale sind.

0

Page 43: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 43

3) Zusammenfassen der MintermeQ4,4 = { }Q4,3 = { }Q4,2 = { }Q4,1 = { }Q4,0 = { }

---------------------------------------------------------------Q3,3 = { } // bleibt leer, da Q4,4 leer ist und mit Q4,3 zu Q3,3 zusammengefasst wird.

Q3,2 = { }Q3,1 = { }Q3,0 = { }

QuineQuine/McCluskey/McCluskey--VerfahrenVerfahren

011

x1

x2

x3

x4

10

2 3

5 4

6

16

7

1415

17

1110

1312

1

1

1

1

-

- 00

00

00

0• Beispiel (2):

_ _ _x4 x3 x2 x1 ,

x4 x3 x2 x1

_ _x4 x3 x2 x1 ,

_ _x4 x3 x2 x1 ,

_ _x4 x3 x2 x1 _

x4 x3 x2 x1 ,_

x4 x3 x2 x1

_ _ _x4 x3 x2 x1

_ _x4 x2 x1 ,

_ _x3 x2 x1 ,

(zusammengefasste Terme markieren)

_ _x4 x3 x2_

x4 x3 x1 ,_x4 x3 x2 ,

_x3 x2 x1

x4 x3 x2 x3 x2 x1 ,

Die Klassen Q4,4 bis Q4,0 sind alle als berücksichtigt markiert.Es gibt folglich keinen Primimplikan-ten, der vier Literale besitzt.

Page 44: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 44

4) rekursives Zusammenfassen der Minterme

Q3,3 = { } Q3,2 = { }Q3,1 = { }Q3,0 = { }

---------------------------------------------------------------Q2,2 = { }Q2,1 = { } Q2,0 = { }

5) Primimplikanten auslesen: w =

QuineQuine/McCluskey/McCluskey--VerfahrenVerfahren

11

x1

x2

x3

x4

10

2 3

5 4

6

16

7

1415

17

1110

1312

1

1

1

1

-

- 00

00

00

0• Beispiel (3):

_ _x4 x2 x1 ,

_ _x3 x2 x1 ,

_ _x4 x3 x2_

x4 x3 x1 ,_x4 x3 x2 ,

_x3 x2 x1

x4 x3 x2 x3 x2 x1 ,

x3 x2

•Der Minterm (x3 & x2) wird nur einmalin die Klasse Q2,0 aufgenommen.

•An dieser Stelle ist keine weitereVereinfachung möglich.

x3 x2 v_ _x4 x2 x1 v

_ _x3 x2 x1 v

_ _x4 x3 x2 v

_x4 x3 x1

0

Die Auswahl der Primimplikanten (Lösung des Überdeckungsproblems) erfolgt beim Quine/McCluskey-Verfahren mit einer Überdeckungstabelle.

Page 45: Grundlagen der Informatik 2 Grundlagen der … · Grundlagen der Digitaltechnik Grundlagen der Informatik 2 Grundlagen der Digitaltechnik 4. Minimierung digitaler Schaltfunktionen

Technische Informatik I 45

ZusammenfassungZusammenfassung

• Problem I: Bestimmung der Primimplikanten:

– KV-Diagramme (graphisch)– Nelson-Verfahren (algebraisch)– Quine/McCluskey-Verfahren (tabellarisch)

• Problem II: kostenminimale Auswahl der Primimplikanten(Lösung des Überdeckungsproblems)

– KV-Diagramme (graphisch)– Petrick-Verfahren (algebraisch)– Überdeckungstabelle (tabellarisch)