31
© H.-D. Wuttke, K. Henke 20.10.2016 www.tu-ilmenau.de/iks 1 Zahlensysteme 12:34

RO-2 2016.ppt [Kompatibilitätsmodus]...Semantik: Wertfunktion W • E: Menge syntaktisch korrekter Ausdrücke X: Menge der Eingangsbelegungen Semantik W: E x X => {0,1} Ausdruck h

  • Upload
    others

  • View
    1

  • Download
    0

Embed Size (px)

Citation preview

Page 1: RO-2 2016.ppt [Kompatibilitätsmodus]...Semantik: Wertfunktion W • E: Menge syntaktisch korrekter Ausdrücke X: Menge der Eingangsbelegungen Semantik W: E x X => {0,1} Ausdruck h

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

Zahlensysteme 12:34

Page 2: RO-2 2016.ppt [Kompatibilitätsmodus]...Semantik: Wertfunktion W • E: Menge syntaktisch korrekter Ausdrücke X: Menge der Eingangsbelegungen Semantik W: E x X => {0,1} Ausdruck h

© H.-D. Wuttke, K. Henke 20.10.2016 www.tu-ilmenau.de/iks 2

Mathematische Grundlagen

Quantisierung von Individuum x• Allquantor x: „für alle x gilt“• Existenzquantor Ǝx: „es existiert ein mind. ein x“• Resultat:• x ist quantisiert: w, f unabhängig von x• Aussage x (p(x))

Ǝx (p(x))

Prädikate => Aussagen

Page 3: RO-2 2016.ppt [Kompatibilitätsmodus]...Semantik: Wertfunktion W • E: Menge syntaktisch korrekter Ausdrücke X: Menge der Eingangsbelegungen Semantik W: E x X => {0,1} Ausdruck h

© H.-D. Wuttke, K. Henke 20.10.2016 www.tu-ilmenau.de/iks 3

Venn-Diagramme (Beispiele)

Page 4: RO-2 2016.ppt [Kompatibilitätsmodus]...Semantik: Wertfunktion W • E: Menge syntaktisch korrekter Ausdrücke X: Menge der Eingangsbelegungen Semantik W: E x X => {0,1} Ausdruck h

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

Angebot zum Selbststudiumhttp://141.24.211.89/moodleIKSSchlüssel: *IKS2016#

Page 5: RO-2 2016.ppt [Kompatibilitätsmodus]...Semantik: Wertfunktion W • E: Menge syntaktisch korrekter Ausdrücke X: Menge der Eingangsbelegungen Semantik W: E x X => {0,1} Ausdruck h

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

Rechnerorganisation – 2.Vorlesung

• Begriffe, Mathematische Grundlagen (1)• Boolesche Algebren, Normalformen (2,3)• Kombinatorische Schaltungen (4)• Programmierbare Strukturen (5)• Automaten, Sequentielle Schaltungen (6-9)• Rechneraufbau und –funktion (11,12)• Informationskodierung (13,14)

Page 6: RO-2 2016.ppt [Kompatibilitätsmodus]...Semantik: Wertfunktion W • E: Menge syntaktisch korrekter Ausdrücke X: Menge der Eingangsbelegungen Semantik W: E x X => {0,1} Ausdruck h

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

Rechnerorganisation – 2.Vorlesung

Funktion digitaler Schaltungen:– Variablen, Belegungen– BMA, Wertetabellen– Syntax schaltalgebraischer Ausdrücke– Semantik, Wertfunktion– BAA, Wertberechnung– Ausdruck => Wertetabelle

Page 7: RO-2 2016.ppt [Kompatibilitätsmodus]...Semantik: Wertfunktion W • E: Menge syntaktisch korrekter Ausdrücke X: Menge der Eingangsbelegungen Semantik W: E x X => {0,1} Ausdruck h

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

Variablen, Belegungen

Page 8: RO-2 2016.ppt [Kompatibilitätsmodus]...Semantik: Wertfunktion W • E: Menge syntaktisch korrekter Ausdrücke X: Menge der Eingangsbelegungen Semantik W: E x X => {0,1} Ausdruck h

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

Variablen, Belegungen

Page 9: RO-2 2016.ppt [Kompatibilitätsmodus]...Semantik: Wertfunktion W • E: Menge syntaktisch korrekter Ausdrücke X: Menge der Eingangsbelegungen Semantik W: E x X => {0,1} Ausdruck h

© H.-D. Wuttke, K. Henke 20.10.2016 www.tu-ilmenau.de/iks 10

Variablen, Belegungen

Page 10: RO-2 2016.ppt [Kompatibilitätsmodus]...Semantik: Wertfunktion W • E: Menge syntaktisch korrekter Ausdrücke X: Menge der Eingangsbelegungen Semantik W: E x X => {0,1} Ausdruck h

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

Variablen

• Binäre Variable x0,y0:

– 2 Werte (Konstanten): 0,1

– Bezeichnung: Kleinbuchstabe + Index

• Vektoren x, y:

– Tupel aus n Variablen x=[xn-1,...,x1,x0], |x|=n

– 2n Wertekombinationen (Belegungen)

Page 11: RO-2 2016.ppt [Kompatibilitätsmodus]...Semantik: Wertfunktion W • E: Menge syntaktisch korrekter Ausdrücke X: Menge der Eingangsbelegungen Semantik W: E x X => {0,1} Ausdruck h

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

Belegungen

• Eingangsvektor x=[xn-1,...,x1,x0], |x|=n

• Belegungen: X0,Y0 X2n -1 , Y2m -1

– 2n : von [0,0,0,...,0] bis [1,1,1,...,1]

• Bezeichnung: Großbuchstabe + Index

• Belegungsmengen X: X={X0, X1, X2,... }, |X|= 2n

• Y={Y0, Y1, Y2,... }, |Y|= 2m

Page 12: RO-2 2016.ppt [Kompatibilitätsmodus]...Semantik: Wertfunktion W • E: Menge syntaktisch korrekter Ausdrücke X: Menge der Eingangsbelegungen Semantik W: E x X => {0,1} Ausdruck h

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

Wertetabelle Bezeichnung der Elemente

• Bit (Wert der Variablen eines Vektors x=[x2,x1,x0] bzw. y=[y1,y0]) in einer Belegung Xi, Yt

• z.B. Bit 2 von x=[x2,x1,x0] in der Belegung X3

– X3(x2)=0 („X3 von x2“) mit X3=[ 0, 1, 1], x=[x2,x1,x0]

• Bit 1 von y=[y1,y0] in der Belegung Y2

– Y2(y1)=1 („Y2 von y1“) Y2=[1,0], y=[y1,y0]

Page 13: RO-2 2016.ppt [Kompatibilitätsmodus]...Semantik: Wertfunktion W • E: Menge syntaktisch korrekter Ausdrücke X: Menge der Eingangsbelegungen Semantik W: E x X => {0,1} Ausdruck h

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

Wertetabelle Bezeichnung der Elemente

• Funktionsbeschreibung mit Mengen• Menge der Eingangsbelegungen: X• Menge der E. mit Funktionswert 1: X1

• zugehörige Indexmenge: I1

• Menge der E. mit Funktionswert 0: X0

• zugehörige Indexmenge: I0

– X= X1 X0, X1 X0 = – I = I1 I0, I1 I0 =

Page 14: RO-2 2016.ppt [Kompatibilitätsmodus]...Semantik: Wertfunktion W • E: Menge syntaktisch korrekter Ausdrücke X: Menge der Eingangsbelegungen Semantik W: E x X => {0,1} Ausdruck h

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

Rechenregeln: 0+0=0 Übertrag 0;0+1=1 Übertrag 0;

0+1+0=1 Übertrag 0;0+1+1=0 Übertrag 1;1+1+1=1 Übertrag 1;

Summe =1 eine „1“ oder drei „1“ in Xi

Übertrag =1 Anzahl „1“ in Xi > 1 (2 Bits sind = 1)

Ü

Wertetabelle Beispiel: Addition

Page 15: RO-2 2016.ppt [Kompatibilitätsmodus]...Semantik: Wertfunktion W • E: Menge syntaktisch korrekter Ausdrücke X: Menge der Eingangsbelegungen Semantik W: E x X => {0,1} Ausdruck h

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

Unter Berücksichtigung eines Übertrages der vorigen Stelle

Wertetabelle Beispiel: Addition

Page 16: RO-2 2016.ppt [Kompatibilitätsmodus]...Semantik: Wertfunktion W • E: Menge syntaktisch korrekter Ausdrücke X: Menge der Eingangsbelegungen Semantik W: E x X => {0,1} Ausdruck h

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

Wertetabelle Beispiel: AdditionNachbereich

üi-1 ai bi üi si Adder

x2 x1 x0 y1 y0 intern

X0 0 0 0 0 0 Y0

X1 0 0 1 0 1 Y1

X2 0 1 0 0 1 Y1

X3 0 1 1 1 0 Y2

X4 1 0 0 0 1 Y1

X5 1 0 1 1 0 Y2

X6 1 1 0 1 0 Y2

X7 1 1 1 1 1 Y3

Vorbereich

Page 17: RO-2 2016.ppt [Kompatibilitätsmodus]...Semantik: Wertfunktion W • E: Menge syntaktisch korrekter Ausdrücke X: Menge der Eingangsbelegungen Semantik W: E x X => {0,1} Ausdruck h

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

Wertetabelle Bezeichnung der Elemente

21 0 2

0 0 0

Page 18: RO-2 2016.ppt [Kompatibilitätsmodus]...Semantik: Wertfunktion W • E: Menge syntaktisch korrekter Ausdrücke X: Menge der Eingangsbelegungen Semantik W: E x X => {0,1} Ausdruck h

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

Digitales System

Architektur

Funktion Struktur

Wertetabelle Schaltung

Y=(X) y = hk(x)

Ausgangsbelegung Yt Ausgangsvariable yj

Eingangsbelegung Xi Eingangsvariable xi

Belegungsmengen X1 Ausdrücke hk

bn

an

Ün

Ün-1 Sn+

Page 19: RO-2 2016.ppt [Kompatibilitätsmodus]...Semantik: Wertfunktion W • E: Menge syntaktisch korrekter Ausdrücke X: Menge der Eingangsbelegungen Semantik W: E x X => {0,1} Ausdruck h

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

Rechnerorganisation – 2.Vorlesung

2. Funktion digitaler Schaltungen:– Variablen, Belegungen– BMA, Wertetabellen– Syntax schaltalgebraischer Ausdrücke– Semantik, Wertfunktion– BAA, Wertberechnung– Ausdruck => Wertetabelle

Page 20: RO-2 2016.ppt [Kompatibilitätsmodus]...Semantik: Wertfunktion W • E: Menge syntaktisch korrekter Ausdrücke X: Menge der Eingangsbelegungen Semantik W: E x X => {0,1} Ausdruck h

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

Schaltalgebraische Ausdrücke

(Wertetabellen: eindeutige Abbildung Eingangsbelegung/ Ausgangsbelegung=> funktionsorientierte Beschreibung)

• ... sind Zeichenreihen zur strukturorientierten Beschreibungdigitaler Schaltungen

Page 21: RO-2 2016.ppt [Kompatibilitätsmodus]...Semantik: Wertfunktion W • E: Menge syntaktisch korrekter Ausdrücke X: Menge der Eingangsbelegungen Semantik W: E x X => {0,1} Ausdruck h

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

Syntax

Page 22: RO-2 2016.ppt [Kompatibilitätsmodus]...Semantik: Wertfunktion W • E: Menge syntaktisch korrekter Ausdrücke X: Menge der Eingangsbelegungen Semantik W: E x X => {0,1} Ausdruck h

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

Syntax

Page 23: RO-2 2016.ppt [Kompatibilitätsmodus]...Semantik: Wertfunktion W • E: Menge syntaktisch korrekter Ausdrücke X: Menge der Eingangsbelegungen Semantik W: E x X => {0,1} Ausdruck h

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

Schaltalgebraische Ausdrücke

• Syntax• Vereinfachte Schreibweise:• ohne äußere Klammern• Priorität• Beispiel

Page 24: RO-2 2016.ppt [Kompatibilitätsmodus]...Semantik: Wertfunktion W • E: Menge syntaktisch korrekter Ausdrücke X: Menge der Eingangsbelegungen Semantik W: E x X => {0,1} Ausdruck h

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

Rechnerorganisation – 2.Vorlesung

• 2. Funktion digitaler Schaltungen: • Variablen, Belegungen• BMA, Wertetabellen• Syntax schaltalgebraischer Ausdrücke• Semantik Wertfunktion• BAA, Wertberechnung• Ausdruck => Wertetabelle

Page 25: RO-2 2016.ppt [Kompatibilitätsmodus]...Semantik: Wertfunktion W • E: Menge syntaktisch korrekter Ausdrücke X: Menge der Eingangsbelegungen Semantik W: E x X => {0,1} Ausdruck h

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

Wertberechnung

• Wertberechnung: BAA• Rechenregeln für Konstante:• Negation: 1=0 0=1• Konjunktion: 11=1; 01=00=0 • Disjunktion: 00=0; 01=11=1

x1 x0

0 0 0 00 1 0 11 0 0 11 1 1 1

Page 26: RO-2 2016.ppt [Kompatibilitätsmodus]...Semantik: Wertfunktion W • E: Menge syntaktisch korrekter Ausdrücke X: Menge der Eingangsbelegungen Semantik W: E x X => {0,1} Ausdruck h

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

Semantik: Wertfunktion W

• E: Menge syntaktisch korrekter AusdrückeX: Menge der Eingangsbelegungen

SemantikW: E x X => {0,1}

Ausdruck hi Ehat bei bestimmter Belegung Xk Xbestimmten Wert W(hi , Xk)=1 bzw. =0

Page 27: RO-2 2016.ppt [Kompatibilitätsmodus]...Semantik: Wertfunktion W • E: Menge syntaktisch korrekter Ausdrücke X: Menge der Eingangsbelegungen Semantik W: E x X => {0,1} Ausdruck h

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

Rechnerorganisation – 2.Vorlesung

• 2. Funktion digitaler Schaltungen:– Variablen, Belegungen– BMA, Wertetabellen– Syntax schaltalgebraischer Ausdrücke– Semantik, Wertfunktion– BAA, Wertberechnung– Ausdruck => Wertetabelle

Page 28: RO-2 2016.ppt [Kompatibilitätsmodus]...Semantik: Wertfunktion W • E: Menge syntaktisch korrekter Ausdrücke X: Menge der Eingangsbelegungen Semantik W: E x X => {0,1} Ausdruck h

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

Semantik: Wertfunktion W

• Rechenregeln: BAA– Wertberechnung für Ausdrücke W(hk , Xi): – schrittweise Berechnung des Wertes– 1. Belegung der Variablen (Bits) – 2. Verknüpfung der Werte – Variable xj => Bit der Belegung Xi(xj)

Page 29: RO-2 2016.ppt [Kompatibilitätsmodus]...Semantik: Wertfunktion W • E: Menge syntaktisch korrekter Ausdrücke X: Menge der Eingangsbelegungen Semantik W: E x X => {0,1} Ausdruck h

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

Rechnerorganisation – 2.Vorlesung

• 2. Funktion digitaler Schaltungen:• Variablen, Belegungen• BMA, Wertetabellen• schaltalgebraische Ausdrücke• Syntax, Semantik• Wertfunktion, Wertberechnung• Ausdruck => Wertetabelle

Page 30: RO-2 2016.ppt [Kompatibilitätsmodus]...Semantik: Wertfunktion W • E: Menge syntaktisch korrekter Ausdrücke X: Menge der Eingangsbelegungen Semantik W: E x X => {0,1} Ausdruck h

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

Ausdruck => Wertetabelle

• Berechnung der Werte eines Ausdrucks bei allen Belegungen der Eingangsvariablen:

• Wertverlauf• Notation in Wertetabelle

• => Ausdruck repräsentiert Wertetabelle(für eine Ausgangsvariable)

Page 31: RO-2 2016.ppt [Kompatibilitätsmodus]...Semantik: Wertfunktion W • E: Menge syntaktisch korrekter Ausdrücke X: Menge der Eingangsbelegungen Semantik W: E x X => {0,1} Ausdruck h

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

Das war‘s für heute

Viel Spaß beim Wiederholen!

Kap. 3.1.1, 3.2.1, 3.2.5.1, 3.2.5.2

Bis nächsten Donnerstag um 15.00 ...