Rechnerstrukturen, Teil 1 Vorlesung 4 SWS WS 14/15 · technischeuniversität - 2-dortmund...

fakultät für informatiktechnische universität dortmund

Rechnerstrukturen, Teil 1

Vorlesung 4 SWS WS 14/15

Prof. Dr Jian-Jia ChenDr. Lars Hildebrand

Fakultät für Informatik – Technische Universität Dortmundlars.hildebrand@tu-dortmund.de

http://ls1-www.cs.tu-dortmund.de

- 2 -technische universitätdortmund

fakultät fürinformatik Rechnerstrukturen (Teil 1)

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

TU Dortmund

1. Einleitung & Strukturierter Entwurf

2. Algebraische Vereinfachung

3. KV-Diagramme

4. Algorithmus von Quine/McCluskey

5. Unvollständig definierte Funktionen

6. Hazards

TU Dortmund

6.1 Einleitung & Strukturierter Entwurf

Was bedeutet Optimierung?

• bestmögliche Lösung finden• Vorgehen

1. Lösungen finden2. beweisen, dass es keine bessere gibt

In RS sehen wir das nicht ganz so streng• Wir wollen zu einem besseren Entwurf kommen• nicht zwingend zum optimalen Entwurf,

• da es häufig konkurrierende Ansätze gibt• die sich zum Teil auch widersprechen

Strukturierter Entwurf

TU Dortmund

Strukturierter Schaltnetz-Entwurf

Schaltnetz-Entwurf bisher• ad hoc• Normalformen

Wunsch• Systematisierung• Strukturierung

Hoffnungen• einfacher zu guten Entwürfen• Schaltnetze verständlicher• Schaltnetze besser verifizierbar

TU Dortmund

Systematisierung Schaltnetz-Entwurf

Grundidee• Wiederverwendung guter Schaltnetze als Komponenten• bereits angewendet:

• bei allen Addierern HA verwendet• HA zur Bestimmung ob Übertrag generiert oder weitergegeben

Zum Einstieg: Kann man VA sinnvoll aus HA bauen?

TU Dortmund

Noch einmal zum Volladdierer

Wir wollen Volladdierer aus Halbaddierern bauen (Wiederverwendung)

��

0 0 0 0 0

0 0 1 0 1

0 1 0 0 1

0 1 1 1 0

1 0 0 0 1

1 0 1 1 0

1 1 0 1 0

1 1 1 1 1

VA"�� + x + y"

TU Dortmund

Einsatz eines Halbaddierers• berechnet x + y

��

0 0 0 0 0

0 0 1 0 1

0 1 0 0 1

0 1 1 1 0

1 0 0 0 1

1 0 1 1 0

1 1 0 1 0

1 1 1 1 1

VA"�� + x + y"

��

HA"x + y"

TU Dortmund

Einsatz eines Halbaddierers• berechnet c und s ohne existierenden Übertrag korrekt• berechnet c und s mit existierendem Übertrag fast immer falsch

��

0 0 0 0 0

0 0 1 0 1

0 1 0 0 1

0 1 1 1 0

1 0 0 0 1

1 0 1 1 0

1 1 0 1 0

1 1 1 1 1

VA"�� + x + y"

��

HA"x + y"

TU Dortmund

Einsatz eines weiteren Halbaddierers• berechnet ��lt + As

��

0 0 0 0 0

0 0 1 0 1

0 1 0 0 1

0 1 1 1 0

1 0 0 0 1

1 0 1 1 0

1 1 0 1 0

1 1 1 1 1

VA"�� + x + y"

��

HA"x + y"

��

HA"��lt + As"

TU Dortmund

Einsatz eines weiteren Halbaddierers• berechnet c und s ohne existierenden Übertrag fast korrekt• berechnet c und s mit existierendem Übertrag fast korrekt

��

0 0 0 0 0

0 0 1 0 1

0 1 0 0 1

0 1 1 1 0

1 0 0 0 1

1 0 1 1 0

1 1 0 1 0

1 1 1 1 1

VA"�� + x + y"

��

HA"x + y"

��

HA"��lt + As"

TU Dortmund

Übertrag der Gesamtsumme entsteht, wenn mindestens einer der beiden Halbaddierer einen Übertrag erzeugt: �� bzw. ��

��

0 0 0 0 0

0 0 1 0 1

0 1 0 0 1

0 1 1 1 0

1 0 0 0 1

1 0 1 1 0

1 1 0 1 0

1 1 1 1 1

VA"�� + x + y"

��

HA"x + y"

��

HA"��lt + As"

TU Dortmund

Fügen wir die Verknüpfung von �� bzw. �� als Disjunktion (mindestens einer der Übertrage muss erzeugt worden sein) hinzu

��

0 0 0 0 0

0 0 1 0 1

0 1 0 0 1

0 1 1 1 0

1 0 0 0 1

1 0 1 1 0

1 1 0 1 0

1 1 1 1 1

VA"�� + x + y"

��

HA"x + y"

��

HA"��lt + As"

�� v ��

TU Dortmund

��

0 0 0 0 0

0 0 1 0 1

0 1 0 0 1

0 1 1 1 0

1 0 0 0 1

1 0 1 1 0

1 1 0 1 0

1 1 1 1 1

VA"�� + x + y"

��

HA"x + y"

��

HA"��lt + As"

�� v ��

TU Dortmund

Strukturierter Volladdierer

Ad-Hoc Volladdierer aus 5.2

TU Dortmund

Strukturierter Volladdierer

Eigenschaften• Größe 5• Tiefe 3• Erinnerung Halbaddierer: Größe 2, Tiefe 1• Erinnerung ”alter“ Volladdierer: Größe 5, Tiefe 3

immerhin nichts verloren im Vergleich zum sorgfältigen ”ad hoc-Entwurf“

TU Dortmund

Strukturierter Multiplexer

Die Idee eines strukturierten Entwurfs eines Volladdierers• wir haben Halbaddierer• bauen wir daraus einen Volladdierer

übertragen wir nun auf die Multiplexer:• wir haben einen MUXd

• bauen wir daraus einen MUX2d

TU Dortmund

Multiplexer

Erinnerung vereinfachte Wertetabelle

normale (ausführliche) Wertetabelle

�� MUX(��,��,��)

0 ��

1 ��

�� MUX(��,��,��)

0 0 0 0

0 0 1 1

0 1 0 0

0 1 1 1

1 0 0 0

1 0 1 0

1 1 0 1

1 1 1 1

TU Dortmund

Multiplexer

reduziertes Schaltnetz durch Anwendung der Resolution

�� MUX(��,��,��)

0 0 0 0

0 0 1 1

0 1 0 0

0 1 1 1

1 0 0 0

1 0 1 0

1 1 0 1

1 1 1 1

MUX(��,��,��)

TU Dortmund

Strukturiert zum Schaltnetz für MUX2

Beobachtung• �� = 0 ⇒ MUX2(��, ��, ��, ��, ��, ��)∈ {��, ��}• �� = 1 ⇒ MUX2(��, ��, ��, ��, ��, ��)∈ {��, ��}

also ein MUX1 wählt mittels �� aus {��, ��}

ein MUX1 wählt mittels �� aus {��, ��}

ein MUX1wählt mittels �� aus den Ergebnissen

�� MUX(��,��,��,��,��,��)

0 0 ��

0 1 ��

1 0 ��

1 1 ��

TU Dortmund

Strukturierter MUX2

MUX2(��,��,��,… ,��)

TU Dortmund

Strukturierter MUX4

• wir haben einenMUXd

�� MUX(��,��,��,��,��,��,��,… ,��)

0 0 0 0 ��

0 0 0 1 ��

0 0 1 0 ��

0 0 1 1 ��

0 1 0 0 ��

0 1 0 1 ��

0 1 1 0 ��

0 1 1 1 ��

1 0 0 0 ��

1 0 0 1 ��

1 0 1 0 ��

1 0 1 1 ��

1 1 0 0 ��

1 1 0 1 ��

1 1 1 0 ��

1 1 1 1 ��

TU Dortmund

Strukturiert MUX4

• wir haben einenMUXd

Beobachtung

• (��,��) = (0,0) ⇒MUX4(… )∈ {��, ��,��,��}

• (��,��) = (0,1) ⇒MUX4(… )∈ {��, ��,��,��}

• (��,��) = (1,0) ⇒MUX4(… )∈ {��, ��,��,��}

• (��,��) = (1,1) ⇒MUX4(… )∈ {��, ��,��,��}

�� MUX(��,��,��,��,��,��,��,… ,��)

0 0 0 0 ��

0 0 0 1 ��

0 0 1 0 ��

0 0 1 1 ��

0 1 0 0 ��

0 1 0 1 ��

0 1 1 0 ��

0 1 1 1 ��

1 0 0 0 ��

1 0 0 1 ��

1 0 1 0 ��

1 0 1 1 ��

1 1 0 0 ��

1 1 0 1 ��

1 1 1 0 ��

1 1 1 1 ��

TU Dortmund

Strukturiert MUX4

• 4 MUX2

wählen 4 Eingänge4 aus 16

• 1 MUX2

wählt Ergebnis1 aus 4

MUX2x 2

MUX2x 6

MUX2x 10

MUX2x 14

y 1 y 2y 3 y 4

TU Dortmund

Strukturiert MUX2d

MUX2d(��,… ��,��,… ,��)

TU Dortmund

Strukturiert MUX2d

MUX2d(��,… ��,��,… ,��)

Zur Realisierung eines MUX2d werden 2d+1 MUXd

benötigt.

TU Dortmund

Strukturierter Entwurf

Vorteile des strukturierten Entwurfs• einfaches Grundprinzip, dessen Korrektheit leicht zu zeigen ist• auch komplexe Schaltnetze intuitiv korrekt• schnelle Vorgehensweise

Nachteile des strukturierten Entwurfs• entstehende Schaltnetze sind groß• bereits berechnete Werte werden in der Regel nicht

wiederverwendet, das sie vom Konstruktionsprinzip nicht erkannt werden

TU Dortmund

3. KV-Diagramme

6. Hazards

TU Dortmund

6.2 Algebraische Vereinfachung

Entwurf kleiner Schaltnetze

Erinnerung Normalformen (DNF, RNF, KNF) direkt in

Schaltnetz umsetzbar

Beobachtung dabei jede Variable höchstens einmal negieren

ab jetzt Wir zählen Negationsgatter nicht mehr.

für große Schaltnetze nicht wesentlich

dann Schaltnetzgröße b≙ Anzahl Minterme/Maxterme + 1

Verbesserung äquivalenter kleinerer boolescher Ausdruck

führt zu kleinerem Schaltnetz

Vorsicht Kleinerer Ausdruck ist keine Normalform mehr!

TU Dortmund

Algebraische Vereinfachungen

Erinnerung Rechengesetze für boolesche Algebra (Satz 3)

Beispiel � ∶ {0,1}�→ 0,1 mit Wertevektor

(1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0)

DNF dazu

einschlägige Indizes 0, 2, 4, 6, 8, 9, 10, 11

Minterm zu i ist Funktion �� : {0,1}�→ {0,1}mit �� ,��,��,�� = 1⇔ ��,��,��,�� = �

am Beispiel i = 2 �� ,��,��,�� = ��

denn �� = 1

⇔ (�� = 0) ∧ (�� = 0) ∧ (�� = 1) ∧ (�� = 0)

⇔ ��,��,��,�� = 2

TU Dortmund

� ∶ {0,1}�→ 0,1 mit Wertevektor (1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0)

DNF dazu

Größe (ohne Negationen) 8 + 1 = 9

Wie können wir das verkleinern?

Resolution

� ��,��,��,�� = �� ⋁ �� ⋁ �� ⋁ ��⋁ �� ⋁ �� ⋁ �� ⋁ ��

�� ⋁ �� = ��

TU Dortmund

� ∶ {0,1}�→ 0,1 mit Wertevektor (1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0)

DNF dazu

Vereinfacht

Resolution

� ��,��,��,�� = �� ⋁ �� ⋁ �� ⋁ ��⋁ �� ⋁ �� ⋁ �� ⋁ ��

�� ⋁ �� = ��

� ��,��,��,�� = �� ⋁ ...

TU Dortmund

� ∶ {0,1}�→ 0,1 mit Wertevektor (1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0)

DNF dazu

Vereinfacht

Resolution �� ⋁ �� = ��

� ��,��,��,�� = �� ⋁ �� ⋁ �� ⋁ ��⋁ �� ⋁ �� ⋁ �� ⋁ ��

� ��,��,��,�� = �� ⋁ �� ⋁ ...

TU Dortmund

� ∶ {0,1}�→ 0,1 mit Wertevektor (1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0)

DNF dazu

Vereinfacht

� ��,��,��,�� = �� ⋁ �� ⋁ �� ⋁ ��⋁ �� ⋁ �� ⋁ �� ⋁ ��

� ��,��,��,�� = �� ⋁ �� ⋁ �� ⋁ ...

TU Dortmund

� ∶ {0,1}�→ 0,1 mit Wertevektor (1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0)

DNF dazu

Vereinfacht

� ��,��,��,�� = �� ⋁ �� ⋁ �� ⋁ ��⋁ �� ⋁ �� ⋁ �� ⋁ ��

� ��,��,��,�� = �� ⋁ �� ⋁ �� ⋁ �� ⋁ ...

TU Dortmund

� ∶ {0,1}�→ 0,1 mit Wertevektor (1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0)

Vereinfacht

� ��,��,��,�� = �� ⋁ �� ⋁ �� ⋁ ��

TU Dortmund

� ∶ {0,1}�→ 0,1 mit Wertevektor (1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0)

Vereinfacht

� ��,��,��,�� = �� ⋁ �� ⋁ �� ⋁ ��

� ��,��,��,�� = �� ⋁ ...

TU Dortmund

� ∶ {0,1}�→ 0,1 mit Wertevektor (1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0)

Vereinfacht

Größe (ohne Negationen) 4 + 1 = 5, vereinfacht: 2 + 1 = 3

Resolution

klar Größe 9 3 beeindruckend aber recht schwierig

�� ⋁ �� = ��

� ��,��,��,�� = �� ⋁ �� ⋁ �� ⋁ ��

� ��,��,��,�� = �� ⋁ ��

TU Dortmund

3. KV-Diagramme

6. Hazards

TU Dortmund

6.3 KV-Diagramme

KV-Diagramme

entwickelt von• Maurice Karnaugh (1953)• Edward W. Veitch (1952)

KV-Diagramme • systematischer, anschaulicher und • viel übersichtlicherer Weg, um Funktionen �: 0,1 � → 0,1 und �: 0,1 � → 0,1zu vereinfachen

aber schon für �: 0,1 � → 0,1 unübersichtlich

⇒ darum vor allem im HaPra wichtig.

TU Dortmund

6.3 KV-Diagramme

KV-Diagramme• Mittels eines KV-Diagramms lässt sich jede disjunktive Normalform in

einen disjunktiven logischen Ausdruck umwandeln• disjunktiver logischer Ausdruck ist minimal

Vorgehensweise1. Erstellen einer Funktionstabelle2. Ableitung der DNF3. Umwandlung der DNF in ein KV-Diagramm4. Auffinden von Strukturen, die zur minimalen Disjunktionen führen.

Dieser Schritt basiert auf der Resolution

TU Dortmund

6.3 KV-Diagramme

KV-Diagramm für �: �,� �→ �,�

Besonderheit• Kanten sind mit Variablen

beschriftet• jede Variable verfügt über eine

Zeile/Spalte für Variable und negierte Variable

• Nachbarschaften, d.h. Variablenbelegungen unterscheiden sich nur in einerStelle

TU Dortmund

6.3 KV-Diagramme

Nachbarschaften, d.h. Variablenbelegungen unterscheiden sich nur

in einer Stelle

TU Dortmund

6.3 KV-Diagramme

in einer Stelle

TU Dortmund

6.3 KV-Diagramme

in einer Stelle

TU Dortmund

6.3 KV-Diagramme

in einer Stelle

Hinweis: Nachbarschaften sind zyklisch

TU Dortmund

6.3 KV-Diagramme

in einer Stelle

TU Dortmund

6.3 KV-Diagramme

in einer Stelle

TU Dortmund

6.3 KV-Diagramme

in einer Stelle

TU Dortmund

6.3 KV-Diagramme

in einer Stelle

TU Dortmund

6.3 KV-Diagramme

in einer Stelle

TU Dortmund

6.3 KV-Diagramme

�: 0,1 � → 0,1 mit Wertevektor 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0(Beispielfunktion wie bereits gesehen)

TU Dortmund

6.3 KV-Diagramme

�� ,… ,��

0 0 0 0 1

⋮ ⋮

1 0 1 1 1

⋮ ⋮

1 1 1 1 0

TU Dortmund

6.3 KV-Diagramme

Was fällt bei der Variablenbelegung auf? Warum ist das so?

�� ,… ,��

0 0 0 0 1

⋮ ⋮

1 0 1 1 1

⋮ ⋮

1 1 1 1 0

TU Dortmund

6.3 KV-Diagramme

�� ,… ,��

0 0 0 0 1

⋮ ⋮

1 0 1 1 1

⋮ ⋮

1 1 1 1 0

TU Dortmund

6.3 KV-Diagramme

�� ,… ,��

0 0 0 0 1

⋮ ⋮

1 0 1 1 1

⋮ ⋮

1 1 1 1 0

TU Dortmund

6.3 KV-Diagramme

�� ,… ,��

0 0 0 0 1

⋮ ⋮

1 0 1 1 1

⋮ ⋮

1 1 1 1 0

TU Dortmund

6.3 KV-Diagramme

�� ,… ,��

0 0 0 0 1

⋮ ⋮

1 0 1 1 1

⋮ ⋮

1 1 1 1 01

TU Dortmund

6.3 KV-Diagramme

�� ,… ,��

0 0 0 0 1

⋮ ⋮

1 0 1 1 1

⋮ ⋮

1 1 1 1 0

TU Dortmund

6.3 KV-Diagramme

�� ,… ,��

0 0 0 0 1

⋮ ⋮

1 0 1 1 1

⋮ ⋮

1 1 1 1 0

TU Dortmund

Nullen weglassen

für mehr Übersichtlichkeit

6.3 KV-Diagramme

�� ,… ,��

0 0 0 0 1

⋮ ⋮

1 0 1 1 1

⋮ ⋮

1 1 1 1 0

TU Dortmund

6.3 KV-Diagramme

KV-Diagramm für Beispielfunktion �: �,� �→ �,�

Suche alle größten Rechtecke mit Zweierpotenzlänge.

TU Dortmund

6.3 KV-Diagramme

TU Dortmund

6.3 KV-Diagramme

TU Dortmund

6.3 KV-Diagramme

TU Dortmund

6.3 KV-Diagramme

Bilde für jedes Rechteck passendes Monom.

TU Dortmund

6.3 KV-Diagramme

�� = 1,�� = 0 ⇒ ��

TU Dortmund

6.3 KV-Diagramme

�� = 1,�� = 0 ⇒ ��

�� = 0,�� = 0 ⇒ ��

TU Dortmund

6.3 KV-Diagramme

�� = 1,�� = 0 ⇒ ��

�� = 0,�� = 0 ⇒ ��

TU Dortmund

6.3 KV-Diagramme

Decke alle Einsen durch sparsame Rechteckauswahl ab.

�� = 1,�� = 0 ⇒ ��

�� = 0,�� = 0 ⇒ ��

TU Dortmund

6.3 KV-Diagramme

Decke alle Einsen durch sparsame Rechteckauswahl ab.

Bilde f als Disjunktion der korrespondierenden Monome.

�� = 1,�� = 0 ⇒ ��

�� = 0,�� = 0 ⇒ ��

� ��,��,��,�� = �� ∨��

TU Dortmund

6.3 KV-Diagramme

Einordnung KV-Diagramme

Was leisten KV-Diagramme?

Beobachtung Wir lösen mit KV-Diagrammen ein Problem, das wir

noch gar nicht definiert haben.

klar Wir holen das jetzt nach.

vorab Begriffsfestlegungen

• Variable Beispiele ��,��,��,. . .

• Literale Variable und Negationen Beispiele ��,��,��,��,. . .

• Monom Konjunktion einiger Literale Beispiele ��,��

• Polynom Disjunktion einiger Monome Beispiel ��∨��∨��

TU Dortmund

6.3 KV-Diagramme

Weitere Begriffsdefinitionen

Wir haben schon Variable, Literal, Monom, Polynom.

• Implikant von f Monom m mit folgender Eigenschaft: ∀�� 0,1 �:� � = 1 ⇒ � � = 1

Beispiel Monom (auch Minterm) eines Polynoms für f

• Verkürzung eines Monoms m Monom m′, für das m Implikant ist

Beispiel �� ist Verkürzung von ��

TU Dortmund

6.3 KV-Diagramme

Weitere Begriffsdefinitionen

• echte Verkürzung eines Monoms m Monom m′, das Verkürzung

von m ist und echt weniger Literale enthält

Beispiel �� ist echte Verkürzung von ��

• Primimplikant von f Implikant von f , für den es keine echte

Verkürzung gibt, die auch Implikant von f ist

Beispiel �� ist Primimplikant von ��∨��

TU Dortmund

6.3 KV-Diagramme

Verbindung zu Schaltnetzen

Erinnerung Wir zählen keine Negationen mehr.

Monom mit i Literalen• Und-Gatter mit Fan-In i • oder i − 1 Und-Gatter mit Fan-In 2• angemessen Kosten i

Polynom mit j Monomen• zusätzlich Oder-Gatter mit Fan-In j oder• j − 1 Oder-Gatter mit Fan-In 2• angemessen zusätzlich Kosten j

direkte Verbindung zwischen Polynom-Kosten und Schaltnetz-Kosten

Noch ein letzter Begriff

Minimalpolynom zu f Polynom für f mit minimalen Kosten unter allen Polynomen für f

TU Dortmund

6.3 KV-Diagramme

Minimalpolynome

Minimalpolynome liefern ”günstigste“ Schaltnetze. . .

Vorsicht• Stimmt nicht so ganz!• nur richtig, wenn man sich auf• direkte Polynomrealisierung einschränkt• trotzdem suchen wir Minimalpolynome

Wie finden wir systematisch Minimalpolynome?

TU Dortmund

6.3 KV-Diagramme

Minimalpolynome und Primimplikanten

Theorem Minimalpolynome enthalten nur Primimplikanten.

Annahme � = ��∨��∨ … ∨�� Minimalpolynom, �� kein Primimplikant zu �

gemäß Definition ∃��: ��ist Implikant von ��, �� ist echte Verkürzung

von �� und �� ist Implikant von �

klar �� = 1⇒ �� = 1, da �� Implikant von��

Beobachtung ��= 1⇒ � = 1, da �� Implikant von � ist

also ��∨��∨ … ∨�� ist günstigeres Polynom für f

Widerspruch zur Voraussetzung, dass ��∨��∨ … ∨��

Minimalpolynom für �

Beweis (indirekt)

TU Dortmund

6.3 KV-Diagramme

Minimalpolynomberechnung

Idee für Minimalpolynomberechnung

1. Berechne alle Primimplikanten von f.

2. Berechne günstigste

”Überdeckung“ von f mit diesen Monomen.

Beobachtung Dieser Ansatz ist sicher schlecht, wenn das Minimalpolynom zu f klein ist, f aber viele Primimplikanten hat.

Wir verfolgen diesen Ansatz dennoch.

TU Dortmund

6.3 KV-Diagramme

Minimalpolynomberechnung

Behauptung Wir haben mit KV-Diagrammen Minimalpolynome berechnet.

Das bedeutet Wir haben günstigste Überdeckung von f gesucht.

Entsprechen maximale Rechtecke mit Zweierpotenzseitenlängen genau Primimplikanten?

Es gilt Für �: 0,1 � → 0,1 gibt es Monome der Längen 0, 1, 2, 3 und 4.

Wir schauen uns die Situation für jede mögliche Monomlänge an.

TU Dortmund

6.3 KV-Diagramme

Primimplikanten der Länge 0

TU Dortmund

6.3 KV-Diagramme

Monom1

TU Dortmund

6.3 KV-Diagramme

TU Dortmund

6.3 KV-Diagramme

Monom��

TU Dortmund

6.3 KV-Diagramme

Monom��

TU Dortmund

6.3 KV-Diagramme

Monom��

TU Dortmund

6.3 KV-Diagramme

Monom��

TU Dortmund

6.3 KV-Diagramme

Monom��

TU Dortmund

6.3 KV-Diagramme

Monom��

TU Dortmund

6.3 KV-Diagramme

Monom��

TU Dortmund

6.3 KV-Diagramme

Monom��

TU Dortmund

6.3 KV-Diagramme

TU Dortmund

6.3 KV-Diagramme

Monom��

TU Dortmund

6.3 KV-Diagramme

Monom��

TU Dortmund

6.3 KV-Diagramme

Monom��

TU Dortmund

6.3 KV-Diagramme

TU Dortmund

6.3 KV-Diagramme

Monom��

TU Dortmund

6.3 KV-Diagramme

Monom��

TU Dortmund

6.3 KV-Diagramme

Monom��

TU Dortmund

6.3 KV-Diagramme

Monom��

TU Dortmund

6.3 KV-Diagramme

TU Dortmund

6.3 KV-Diagramme

Monom��

TU Dortmund

6.3 KV-Diagramme

Monom��

TU Dortmund

6.3 KV-Diagramme

Monom��

TU Dortmund

6.3 KV-Diagramme

Monom��

TU Dortmund

6.3 KV-Diagramme

Monom��

TU Dortmund

6.3 KV-Diagramme

Beobachtung Primimplikanten entsprechen genau KV-Rechtecken

Monom��

TU Dortmund

6.3 KV-Diagramme

Minimalpolynombestimmung mit KV-Diagramm

Aufgabe Bestimme für �: 0,1 � → 0,1 ein Minimalpolynom.

Vorgehen1. Eintragen der Funktion ins KV-Diagramm2. Finden aller maximaler Zweierpotenz-Rechtecke3. Finden eines Primimplikanten für jedes Rechteck4. Finden einer Überdeckung aller Einsen durch eine minimale

Monomauswahl

jetzt noch ein Beispiel

�: 0,1 � → 0,1 mit 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1

TU Dortmund

6.3 KV-Diagramme

Eintragen der Funktion ins KV-Diagramm

�: 0,1 � → 0,1 mit 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1

0 = 0000 �

1 = 0001 �

2 = 0010 �

3 = 0011 �

4 = 0100 �

5 = 0101 �

6 = 0110 �

7 = 0111 �

8 = 1000 �

9 = 1001 �

10 = 1010 �

11 = 1011 �

12 = 1100 �

13 = 1101 �

14 = 1110 �

15 = 1111 �

0123456789101112131415

TU Dortmund

6.3 KV-Diagramme

�: 0,1 � → 0,1 mit 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1

0 = 0000 �

1 = 0001 �

2 = 0010 �

3 = 0011 �

4 = 0100 �

5 = 0101 �

6 = 0110 �

7 = 0111 �

8 = 1000 �

9 = 1001 �

10 = 1010 �

11 = 1011 �

12 = 1100 �

13 = 1101 �

14 = 1110 �

15 = 1111 �

0123456789101112131415

TU Dortmund

6.3 KV-Diagramme

�: 0,1 � → 0,1 mit 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1

0 = 0000 �

1 = 0001 �

2 = 0010 �

3 = 0011 �

4 = 0100 �

5 = 0101 �

6 = 0110 �

7 = 0111 �

8 = 1000 �

9 = 1001 �

10 = 1010 �

11 = 1011 �

12 = 1100 �

13 = 1101 �

14 = 1110 �

15 = 1111 �

0123456789101112131415

TU Dortmund

0 = 0000 �

1 = 0001 �

2 = 0010 �

3 = 0011 �

4 = 0100 �

5 = 0101 �

6 = 0110 �

7 = 0111 �

8 = 1000 �

9 = 1001 �

10 = 1010 �

11 = 1011 �

12 = 1100 �

13 = 1101 �

14 = 1110 �

15 = 1111 �

6.3 KV-Diagramme

�: 0,1 � → 0,1 mit 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1

0123456789101112131415

TU Dortmund

6.3 KV-Diagramme

�: 0,1 � → 0,1 mit 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1

0 = 0000 �

1 = 0001 �

2 = 0010 �

3 = 0011 �

4 = 0100 �

5 = 0101 �

6 = 0110 �

7 = 0111 �

8 = 1000 �

9 = 1001 �

10 = 1010 �

11 = 1011 �

12 = 1100 �

13 = 1101 �

14 = 1110 �

15 = 1111 �

0123456789101112131415

TU Dortmund

6.3 KV-Diagramme

Finden aller maximaler Zweierpotenz-Rechtecke

�: 0,1 � → 0,1 mit 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1

TU Dortmund

6.3 KV-Diagramme

Finden eines Primimplikanten für jedes Rechteck

�: 0,1 � → 0,1 mit 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1

��

TU Dortmund

6.3 KV-Diagramme

Überdeckung aller Einsen durch minimale Monomauswahl

�: 0,1 � → 0,1 mit 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1

��

TU Dortmund

6.3 KV-Diagramme

�: 0,1 � → 0,1 mit 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1

��erforderlich

TU Dortmund

6.3 KV-Diagramme

�: 0,1 � → 0,1 mit 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1

�� erforderlich��erforderlich

TU Dortmund

6.3 KV-Diagramme

�: 0,1 � → 0,1 mit 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1

�� erforderlich�� erforderlich��erforderlich

TU Dortmund

6.3 KV-Diagramme

�: 0,1 � → 0,1 mit 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1

�� erforderlich�� erforderlich�� erforderlich��erforderlich

TU Dortmund

6.3 KV-Diagramme

�: 0,1 � → 0,1 mit 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1

�� besteWahl�� erforderlich�� erforderlich�� erforderlich��erforderlich

TU Dortmund

6.3 KV-Diagramme

�: 0,1 � → 0,1 mit 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1

�� besteWahl�� erforderlich�� erforderlich�� erforderlich��erforderlich

also��˅��˅��˅��˅��Minimalpolynom

TU Dortmund

6.3 KV-Diagramme

Anmerkungen zu KV-Diagramme

KV-Diagramm für 3 Variablen

KV-Diagramm für 6 Variablen

Quelle: Hand Lohninger

TU Dortmund

6.3 KV-Diagramme

Fazit KV-Diagramme

Mit KV-Diagrammen effizient beide Schritte zur

Minimalpolynomberechnung durchführbar1. Bestimmung aller Primimplikanten2. Bestimmung einer minimalen Überdeckung für Funktionen

�: 0,1 � → 0,1 für �� 3,4klar Das reicht nicht aus.

Wie bestimmen wir Minimalpolynome für �: 0,1 � → 0,1

für größeres �?

klar Wir suchen einen Algorithmus.

TU Dortmund

3. KV-Diagramme

6. Hazards

Rechnerstrukturen, Teil 1 Vorlesung 4 SWS WS 14/15 · technischeuniversität - 2-dortmund...

Documents

Rechnerstrukturen,,Teil,1 …...technische universität! 3 ! dortmund fakultätfür informatik Rechnerstrukturen(Teil 1) TUDortmund 8.,Synchrone,Schaltwerke 8. Synchrone,Schaltwerke

64-040 Modul IP7: Rechnerstrukturen … · 64-040 Modul IP7: Rechnerstrukturen 2. Informationsbegri und Repr asentation Norman Hendrich & Jianwei Zhang Universit at Hamburg MIN Fakult

Michael Engel und Peter Marwedel - TU Dortmund · 2019. 7. 16. · Rechnerstrukturen Michael Engel und Peter Marwedel TU Dortmund, Fakult¨at f ¨ur Informatik SS 2013 Hinweis: Foliena.d.Basis

Technische universität dortmund Club of Excellence der TU Dortmund

64-040- Modul InfB-RS: Rechnerstrukturen · Informatik 1Einführung 64-040Rechnerstrukturen Brockhaus-Enzyklopädie:„Informatik“ DieWissenschaftvondersystematischenVerarbeitungvon

fakultät für informatik informatik 12 technische universität dortmund Rechnerstrukturen, Teil 2 2012/08/14

Rechnerstrukturen WS 2012/13 - TU Dortmundpatrec.cs.tu-dortmund.de/lectures/WS12/rechnerstrukturen/... · 2012. 9. 5. · Rechnerstrukturen WS 2012/13 Boolesche Funktionen und Schaltnetze

Vorlesung: Rechnerstrukturen, Teil 2 (Modul IP7)

Praktikum Rechnerstrukturen 1 filePraktikum Rechnerstrukturen Bogen 1 1 Einführung und Motivation Ziel des Praktikums Rechnerstrukturen ist die Vertiefung des Verständnis von Funktion

64-040- Modul InfB-RS: Rechnerstrukturen Modul InfB-RS: Rechnerstrukturen ... Praktikum Klausur 3. Literaturempfehlungen 4. ... I Maschinen- und Assembler-Code und -programmierung

Rechnerstrukturen - hhgym.de

Rechnerstrukturen - Uni Trier · 2013. 8. 18. · LHH L D3 \D3 HLL L D4 \D4 HLH L D5 \D5 HHL L D6 \D6 HHH L D7 \D7. Vorlesung Rechnerstrukturen 9 3.23 C B A Realisierung: Multiplexer

Skript zur Vorlesung Rechnerstrukturen, Teil 2” WS 2013/2014 · Skript zur Vorlesung ” Rechnerstrukturen, Teil 2” WS 2013/2014 P. Marwedel, Informatik 12 Technische Universitat

64-040- Modul InfB-RS: Rechnerstrukturen · Artenvielfaltvom„EmbeddedArchitekturen“ 14 Instruction Set Architecture 64-040 Rechnerstrukturen Prozessor 1 C 1 C 1ASIC 1 P, DSPs

Van den Troost, Anna - jockeys-in-deutschland.de€¦ · Van den Troost, Anna Inhaltsverzeichnis 7 16.02.2020 Dortmund 6 09.02.2020 Dortmund 5 02.02.2020 Dortmund 4 05.01.2020 Dortmund

© 2006 W. Oberschelp, G. Vossen Rechneraufbau & Rechnerstrukturen, Folie 2.1

Rechneraufbau & Rechnerstrukturen, Folie 13.1 © 2006 W. Oberschelp, G. Vossen

Rechnerstrukturen - Uni Trier

Chronik des Jahres 2005 - unige.ch pr5.pdfChronik des Jahres 2005. Das Jahr 2005 istein denkwür-diges Jahr für die Fakultätfür Psychologie und Erziehungs-wissenschaften (Faculté

64-040- Modul IP7: Rechnerstrukturen