37
© IKS 2016 H.-D. Wuttke, K. Henke 08.12.2016 www.tu-ilmenau.de/iks 1 Rechnerorganisation Mathematische Grundlagen (1) Boolesche Algebren: BMA, BAA (2,3) Kombinatorische Schaltungen (4,5) Automaten (6,7) Sequentielle Schaltungen (8) Programmierbare Strukturen (9) Rechneraufbau und ~funktion (10,11) Informationskodierung (12,13,14)

Mathematische Grundlagen (1) Boolesche Algebren: BMA ...Mathematische Grundlagen (1) Boolesche Algebren: BMA, BAA (2,3) Kombinatorische Schaltungen (4,5) Automaten (6,7) Sequentielle

  • Upload
    others

  • View
    4

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Mathematische Grundlagen (1) Boolesche Algebren: BMA ...Mathematische Grundlagen (1) Boolesche Algebren: BMA, BAA (2,3) Kombinatorische Schaltungen (4,5) Automaten (6,7) Sequentielle

© IKS 2016H.-D. Wuttke, K. Henke 08.12.2016 www.tu-ilmenau.de/iks 1

Rechnerorganisation

Mathematische Grundlagen (1)Boolesche Algebren: BMA, BAA (2,3)Kombinatorische Schaltungen (4,5)

Automaten (6,7)Sequentielle Schaltungen (8)

Programmierbare Strukturen (9) Rechneraufbau und ~funktion (10,11)

Informationskodierung (12,13,14)

Page 2: Mathematische Grundlagen (1) Boolesche Algebren: BMA ...Mathematische Grundlagen (1) Boolesche Algebren: BMA, BAA (2,3) Kombinatorische Schaltungen (4,5) Automaten (6,7) Sequentielle

© IKS 2016H.-D. Wuttke, K. Henke 08.12.2016 www.tu-ilmenau.de/iks 4

Beispiel

Page 3: Mathematische Grundlagen (1) Boolesche Algebren: BMA ...Mathematische Grundlagen (1) Boolesche Algebren: BMA, BAA (2,3) Kombinatorische Schaltungen (4,5) Automaten (6,7) Sequentielle

© IKS 2016H.-D. Wuttke, K. Henke 08.12.2016 www.tu-ilmenau.de/iks 5

www.goldi-labs.net

Page 4: Mathematische Grundlagen (1) Boolesche Algebren: BMA ...Mathematische Grundlagen (1) Boolesche Algebren: BMA, BAA (2,3) Kombinatorische Schaltungen (4,5) Automaten (6,7) Sequentielle

© IKS 2016H.-D. Wuttke, K. Henke 08.12.2016 www.tu-ilmenau.de/iks 6

BeispielAnsatz: WertetabelleStart/Stopp

rechts links rechts links

x2 x1 x0 y1 y0

0 0 0 0 0 Stopp

0 0 1 0 0 Stopp

0 1 0 0 0 Stopp

0 1 1 * * don‘t care

1 0 1 1 0 links angekommen => rechts

X4 1 0 0 1 0 rechts weiter

1 1 0 0 1 rechts angekommen => links

X4 1 0 0 0 1 links weiter

1 1 1 * * don‘t care

Problem mit Kombinatorik nicht beschreibbar !!

Page 5: Mathematische Grundlagen (1) Boolesche Algebren: BMA ...Mathematische Grundlagen (1) Boolesche Algebren: BMA, BAA (2,3) Kombinatorische Schaltungen (4,5) Automaten (6,7) Sequentielle

© IKS 2016H.-D. Wuttke, K. Henke 08.12.2016 www.tu-ilmenau.de/iks 7

Zustandsübergang von Z0 nach Z1

Page 6: Mathematische Grundlagen (1) Boolesche Algebren: BMA ...Mathematische Grundlagen (1) Boolesche Algebren: BMA, BAA (2,3) Kombinatorische Schaltungen (4,5) Automaten (6,7) Sequentielle

© IKS 2016H.-D. Wuttke, K. Henke 08.12.2016 www.tu-ilmenau.de/iks 8

Automatengraph

intuitiver Entwurf Systematik aus Tabelle

Page 7: Mathematische Grundlagen (1) Boolesche Algebren: BMA ...Mathematische Grundlagen (1) Boolesche Algebren: BMA, BAA (2,3) Kombinatorische Schaltungen (4,5) Automaten (6,7) Sequentielle

© IKS 2016H.-D. Wuttke, K. Henke 08.12.2016 www.tu-ilmenau.de/iks 9

Rechnerorganisation 7. Vorlesung

4. Sequentielle SchaltungenAutomatentabellen, Automatentypen

Verifikation (Vollständigkeit& Widerspruchsfreiheit)

Synthese sequenzieller Strukturen(z- und y- Gleichungen)

Page 8: Mathematische Grundlagen (1) Boolesche Algebren: BMA ...Mathematische Grundlagen (1) Boolesche Algebren: BMA, BAA (2,3) Kombinatorische Schaltungen (4,5) Automaten (6,7) Sequentielle

© IKS 2016H.-D. Wuttke, K. Henke 08.12.2016 www.tu-ilmenau.de/iks 11

Beispiel - Zustandsüberführungsfunktion

Page 9: Mathematische Grundlagen (1) Boolesche Algebren: BMA ...Mathematische Grundlagen (1) Boolesche Algebren: BMA, BAA (2,3) Kombinatorische Schaltungen (4,5) Automaten (6,7) Sequentielle

© IKS 2016H.-D. Wuttke, K. Henke 08.12.2016 www.tu-ilmenau.de/iks 12

Beispiel - Ausgabefunktion

Page 10: Mathematische Grundlagen (1) Boolesche Algebren: BMA ...Mathematische Grundlagen (1) Boolesche Algebren: BMA, BAA (2,3) Kombinatorische Schaltungen (4,5) Automaten (6,7) Sequentielle

© IKS 2016H.-D. Wuttke, K. Henke 08.12.2016 www.tu-ilmenau.de/iks 13

Automatentabelle => Automatengraph

Typ alt (Zustand am „Rand“)

=> In Tabelle steht Ausgabe des „alten“ Zustandes (aZ,X)

z.B. in Z1 gilt: y= k2(x) k3(x)= x1

Page 11: Mathematische Grundlagen (1) Boolesche Algebren: BMA ...Mathematische Grundlagen (1) Boolesche Algebren: BMA, BAA (2,3) Kombinatorische Schaltungen (4,5) Automaten (6,7) Sequentielle

© IKS 2016H.-D. Wuttke, K. Henke 08.12.2016 www.tu-ilmenau.de/iks 14

Typ alt (Zustand am „Rand“)

=> In Tabelle steht Ausgabe des „alten“ Zustandes (aZ,X)

z.B. in Z1 gilt: y= k2(x) k3(x)= x1

d.h.

Ausgabe wird aus den Belegungen

je einer Zeile ermittelt

Automatentabelle => Automatengraph

Page 12: Mathematische Grundlagen (1) Boolesche Algebren: BMA ...Mathematische Grundlagen (1) Boolesche Algebren: BMA, BAA (2,3) Kombinatorische Schaltungen (4,5) Automaten (6,7) Sequentielle

© IKS 2016H.-D. Wuttke, K. Henke 08.12.2016 www.tu-ilmenau.de/iks 15

Automatentabelle => Automatengraph

Notation als Automatentabelle

Page 13: Mathematische Grundlagen (1) Boolesche Algebren: BMA ...Mathematische Grundlagen (1) Boolesche Algebren: BMA, BAA (2,3) Kombinatorische Schaltungen (4,5) Automaten (6,7) Sequentielle

© IKS 2016H.-D. Wuttke, K. Henke 08.12.2016 www.tu-ilmenau.de/iks 16

Automatentabelle => Automatengraph

Notation als Transitionsmatrix

Page 14: Mathematische Grundlagen (1) Boolesche Algebren: BMA ...Mathematische Grundlagen (1) Boolesche Algebren: BMA, BAA (2,3) Kombinatorische Schaltungen (4,5) Automaten (6,7) Sequentielle

© IKS 2016H.-D. Wuttke, K. Henke 08.12.2016 www.tu-ilmenau.de/iks 17

Automatentypen

Page 15: Mathematische Grundlagen (1) Boolesche Algebren: BMA ...Mathematische Grundlagen (1) Boolesche Algebren: BMA, BAA (2,3) Kombinatorische Schaltungen (4,5) Automaten (6,7) Sequentielle

© IKS 2016H.-D. Wuttke, K. Henke 08.12.2016 www.tu-ilmenau.de/iks 18

Moore / Mealy

Moore-Automat A=(X,Y,Z,,)

Ausgabe nur von Zuständen abhängig

Spezielle Ausgabefunktion:

: Z Y

Mealy-Automat A=(X,Y,Z,,)

: Z x X Y

Page 16: Mathematische Grundlagen (1) Boolesche Algebren: BMA ...Mathematische Grundlagen (1) Boolesche Algebren: BMA, BAA (2,3) Kombinatorische Schaltungen (4,5) Automaten (6,7) Sequentielle

© IKS 2016H.-D. Wuttke, K. Henke 08.12.2016 www.tu-ilmenau.de/iks 19

In Ausgabefunktion Moore: nur Konstante

Mealy-Automat:

Moore / Mealy

Page 17: Mathematische Grundlagen (1) Boolesche Algebren: BMA ...Mathematische Grundlagen (1) Boolesche Algebren: BMA, BAA (2,3) Kombinatorische Schaltungen (4,5) Automaten (6,7) Sequentielle

© IKS 2016H.-D. Wuttke, K. Henke 08.12.2016 www.tu-ilmenau.de/iks 20

In Ausgabefunktion Moore: nur Konstante

Moore / Mealy

Page 18: Mathematische Grundlagen (1) Boolesche Algebren: BMA ...Mathematische Grundlagen (1) Boolesche Algebren: BMA, BAA (2,3) Kombinatorische Schaltungen (4,5) Automaten (6,7) Sequentielle

© IKS 2016H.-D. Wuttke, K. Henke 08.12.2016 www.tu-ilmenau.de/iks 21

In Ausgabefunktion Mealy: auch x-Variablen

Moore / Mealy

Page 19: Mathematische Grundlagen (1) Boolesche Algebren: BMA ...Mathematische Grundlagen (1) Boolesche Algebren: BMA, BAA (2,3) Kombinatorische Schaltungen (4,5) Automaten (6,7) Sequentielle

© IKS 2016H.-D. Wuttke, K. Henke 08.12.2016 www.tu-ilmenau.de/iks 22

Beispiel als Moore-Automat

Korrekter Entwurf?

formale Verifikation

Page 20: Mathematische Grundlagen (1) Boolesche Algebren: BMA ...Mathematische Grundlagen (1) Boolesche Algebren: BMA, BAA (2,3) Kombinatorische Schaltungen (4,5) Automaten (6,7) Sequentielle

© IKS 2016H.-D. Wuttke, K. Henke 08.12.2016 www.tu-ilmenau.de/iks 23

4. Sequentielle SchaltungenAutomatentabellen, Automatentypen

Verifikation (Vollständigkeit& Widerspruchsfreiheit)

Synthese sequenzieller Strukturen(z- und y- Gleichungen)

Page 21: Mathematische Grundlagen (1) Boolesche Algebren: BMA ...Mathematische Grundlagen (1) Boolesche Algebren: BMA, BAA (2,3) Kombinatorische Schaltungen (4,5) Automaten (6,7) Sequentielle

© IKS 2016H.-D. Wuttke, K. Henke 08.12.2016 www.tu-ilmenau.de/iks 24

Verifikation

Korrekter Entwurf?

=> formale Verifikation

Prüfung auf

Vollständigkeit

und

Widerspruchsfreiheit

Page 22: Mathematische Grundlagen (1) Boolesche Algebren: BMA ...Mathematische Grundlagen (1) Boolesche Algebren: BMA, BAA (2,3) Kombinatorische Schaltungen (4,5) Automaten (6,7) Sequentielle

© IKS 2016H.-D. Wuttke, K. Henke 08.12.2016 www.tu-ilmenau.de/iks 25

Vollständigkeit

{X0, X2, X4, X6}{X1, X3, X5, X7}

{X2, X3, X6, X7}

{X0, X1, X4, X5}

BAA => BMA je Zustand für alle Xi vollständig

Page 23: Mathematische Grundlagen (1) Boolesche Algebren: BMA ...Mathematische Grundlagen (1) Boolesche Algebren: BMA, BAA (2,3) Kombinatorische Schaltungen (4,5) Automaten (6,7) Sequentielle

© IKS 2016H.-D. Wuttke, K. Henke 08.12.2016 www.tu-ilmenau.de/iks 26

BMA

BAA

x0 x0=1

allgemein

{X0, X2, X4, X6} {X1, X3, X5, X7}= X

Vollständigkeit

Page 24: Mathematische Grundlagen (1) Boolesche Algebren: BMA ...Mathematische Grundlagen (1) Boolesche Algebren: BMA, BAA (2,3) Kombinatorische Schaltungen (4,5) Automaten (6,7) Sequentielle

© IKS 2016H.-D. Wuttke, K. Henke 08.12.2016 www.tu-ilmenau.de/iks 27

Widerspruchsfreiheit

{X2, X3, X6, X7}

{X0, X1, X4, X5}

• BAA => BMA je Kantenpaar• keine gleichen Belegungen

Page 25: Mathematische Grundlagen (1) Boolesche Algebren: BMA ...Mathematische Grundlagen (1) Boolesche Algebren: BMA, BAA (2,3) Kombinatorische Schaltungen (4,5) Automaten (6,7) Sequentielle

© IKS 2016H.-D. Wuttke, K. Henke 08.12.2016 www.tu-ilmenau.de/iks 28

Widerspruchsfreiheit

BAA => BMA Widerspruch

{X2, X3, X6, X7}

{X0, X1, X4, X5}

{X0, X1, X2, X3}

Page 26: Mathematische Grundlagen (1) Boolesche Algebren: BMA ...Mathematische Grundlagen (1) Boolesche Algebren: BMA, BAA (2,3) Kombinatorische Schaltungen (4,5) Automaten (6,7) Sequentielle

© IKS 2016H.-D. Wuttke, K. Henke 08.12.2016 www.tu-ilmenau.de/iks 29

Widerspruchsfreiheit

BAA => BMA Widerspruch

BMA: paarweise Schnittbildung

BAA: paarweise Konjunktion

h10 h13 = 0? x1x2 0

{X0, X1, X2, X3} = {X2, X3}=> ! Widerspruch {X2, X3, X6, X7}

Page 27: Mathematische Grundlagen (1) Boolesche Algebren: BMA ...Mathematische Grundlagen (1) Boolesche Algebren: BMA, BAA (2,3) Kombinatorische Schaltungen (4,5) Automaten (6,7) Sequentielle

© IKS 2016H.-D. Wuttke, K. Henke 08.12.2016 www.tu-ilmenau.de/iks 30

Widerspruchsfreiheit

BAA allgemein

Page 28: Mathematische Grundlagen (1) Boolesche Algebren: BMA ...Mathematische Grundlagen (1) Boolesche Algebren: BMA, BAA (2,3) Kombinatorische Schaltungen (4,5) Automaten (6,7) Sequentielle

© IKS 2016H.-D. Wuttke, K. Henke 08.12.2016 www.tu-ilmenau.de/iks 31

Widerspruchsfreiheit

{X6, X7}

{X0, X1 X2, X3}

{X4, X5}

Vergleich mit Aufgabe und

Widerspruch auflösen

Page 29: Mathematische Grundlagen (1) Boolesche Algebren: BMA ...Mathematische Grundlagen (1) Boolesche Algebren: BMA, BAA (2,3) Kombinatorische Schaltungen (4,5) Automaten (6,7) Sequentielle

© IKS 2016H.-D. Wuttke, K. Henke 08.12.2016 www.tu-ilmenau.de/iks 32

Rechnerorganisation 7. Vorlesung

4. Sequentielle SchaltungenAutomatentabellen, Automatentypen

Verifikation (Vollständigkeit& Widerspruchsfreiheit)

Synthese sequenzieller Strukturen(z- und y- Gleichungen)

Page 30: Mathematische Grundlagen (1) Boolesche Algebren: BMA ...Mathematische Grundlagen (1) Boolesche Algebren: BMA, BAA (2,3) Kombinatorische Schaltungen (4,5) Automaten (6,7) Sequentielle

© IKS 2016H.-D. Wuttke, K. Henke 08.12.2016 www.tu-ilmenau.de/iks 33

Strukturgleichungen

Gleiches Vorgehen wie bei kombinatorischen Strukturen:

Zur DNF-Realisierung 1-Belegungen der Variablen (z bzw. y) suchen und

Bedingungen notieren:

z.B.

unter welchen Bedingungen wird z0 zu „1“

Page 31: Mathematische Grundlagen (1) Boolesche Algebren: BMA ...Mathematische Grundlagen (1) Boolesche Algebren: BMA, BAA (2,3) Kombinatorische Schaltungen (4,5) Automaten (6,7) Sequentielle

© IKS 2016H.-D. Wuttke, K. Henke 08.12.2016 www.tu-ilmenau.de/iks 34

z-Gleichungen

Zustandsüberführungsfunktion:

Zur DNF-Realisierung 1-Belegungen der

z-Variablen in den Zustandskodierungen suchen und Bedingungen notieren:

z.B. 1=Belegung von z0 in Z1

z0 :=

Page 32: Mathematische Grundlagen (1) Boolesche Algebren: BMA ...Mathematische Grundlagen (1) Boolesche Algebren: BMA, BAA (2,3) Kombinatorische Schaltungen (4,5) Automaten (6,7) Sequentielle

© IKS 2016H.-D. Wuttke, K. Henke 08.12.2016 www.tu-ilmenau.de/iks 35

z-Gleichungen

Zustandsüberführungsfunktion:z.B. 1-Belegung von z0 in Z1

hinführende Kanten

z0:= z0 x0 z0 x1

Page 33: Mathematische Grundlagen (1) Boolesche Algebren: BMA ...Mathematische Grundlagen (1) Boolesche Algebren: BMA, BAA (2,3) Kombinatorische Schaltungen (4,5) Automaten (6,7) Sequentielle

© IKS 2016H.-D. Wuttke, K. Henke 08.12.2016 www.tu-ilmenau.de/iks 36

z-Gleichungen

Zustandsüberführungsfunktion:

z0:= z0 x0 z0 x1

Page 34: Mathematische Grundlagen (1) Boolesche Algebren: BMA ...Mathematische Grundlagen (1) Boolesche Algebren: BMA, BAA (2,3) Kombinatorische Schaltungen (4,5) Automaten (6,7) Sequentielle

© IKS 2016H.-D. Wuttke, K. Henke 08.12.2016 www.tu-ilmenau.de/iks 37

z-Gleichungen

Zustandsüberführungsfunktion:

z0:= z0 x0 z0 x1

Page 35: Mathematische Grundlagen (1) Boolesche Algebren: BMA ...Mathematische Grundlagen (1) Boolesche Algebren: BMA, BAA (2,3) Kombinatorische Schaltungen (4,5) Automaten (6,7) Sequentielle

© IKS 2016H.-D. Wuttke, K. Henke 08.12.2016 www.tu-ilmenau.de/iks 38

y-Gleichungen

Ausgabefunktion:

z.B. 1-Belegung von y1 in Z1

Knotengewicht

y1= z0 x2

Page 36: Mathematische Grundlagen (1) Boolesche Algebren: BMA ...Mathematische Grundlagen (1) Boolesche Algebren: BMA, BAA (2,3) Kombinatorische Schaltungen (4,5) Automaten (6,7) Sequentielle

© IKS 2016H.-D. Wuttke, K. Henke 08.12.2016 www.tu-ilmenau.de/iks 39

Struktur-Gleichungen

Ausgabefunktion:y0= z0 x2

y1= z0 x2

Zustandsüberführungsfunktion:

z0:= x0 z0 x1

Page 37: Mathematische Grundlagen (1) Boolesche Algebren: BMA ...Mathematische Grundlagen (1) Boolesche Algebren: BMA, BAA (2,3) Kombinatorische Schaltungen (4,5) Automaten (6,7) Sequentielle

© IKS 2016H.-D. Wuttke, K. Henke 08.12.2016 www.tu-ilmenau.de/iks 40

Viel Spaß beim Wiederholen!

Bis nächsten Donnerstag 15.00 ...

Das war‘s für heute