Technische Informatik I (SS 2006) Digitale Information Schalter Lampenzustand ist Tabelle von Schalterzustand Analoge vs. Digitale Informationen Analoge

Technische Informatik I (SS 2006)

● Digitale Information▪ Schalter

▪ Lampenzustand ist Tabelle von Schalterzustand

Analoge vs. Digitale Informationen

● Analoge Information▪ Z.B. Dimmer

▪ Lampenzustand ist Funktion von Widerstand

Schalter Zustand

Auf Dunkel

Zu Hell


● Analoge Information▪ Tonband▪ Zeigermessgerät▪ Theoretisch unendlich

genau▪ Praktisch: Ablese- und

Reproduktionsgenauigkeit▪ Analogrechner

● Digitale Information● Diskretisierung der

Zustände▪ CD/DVD▪ Digitales Messgerät▪ Theoretisch ungenau▪ Reproduzierbar▪ Digitale Rechner

Analoge vs. Digitale Informationen: Beispiele


Digitale Informationen

● N diskrete Zustände▪ Technisch „einfache“

Realisierung: N=2: „Binär“▪ 0,1▪ An, Aus▪ Strom fließt/fließt nicht▪ Zwei Spannungspegel▪ Wahr, Falsch

● Mathematischer Hintergrund: Boolsche Algebra


Teil 1: Logik1a: Schaltfunktionen


Negation

● Funktion einer Variablen

● y = ¬x

● Alternativ: ▪ y = x▪ y = x‘▪ y = ~x

● Schaltsymbole

x y

0 1

1 0

x y

x y

x y

1 0


Und-Verknüpfung

● y = a & b● Alternativ:

▪ y = a · b▪ y = ab

● Schaltsymbole

a b y

0 0 0

0 1 0

1 0 0

1 1 1

a

by

&

a

by

a

b

y

a

c

yb

● Es gilt:● y = (a & b) & c

= a & (b & c) = a & b & c


Oder-Verknüpfung

● x = a | b● Alternativ:

▪ x = a + b

● Schaltsymbole

x a b

0 0 0

1 0 1

1 1 0

1 1 1

≥1

a

bx


Gatterschaltungen

● y = (a & e) | (b & e)● y = f (a,b,e)a

b

e y

0

0

1

0

0

0

● Eigenschaften:▪ e = 0 („Enable“)

• y = 0

▪ e = 1• y = a | b

ea

b

y


Gatterschaltungen

● y = (a & e) | (b & e)● y = f (a,b,e)

● Ziel: Implementierung von „f“ zu einfach wie möglich▪ Kosten▪ Gatterlaufzeit („Geschwindigkeit“)

▪ y = (a | b) & e

ea

b

yabe

ya b e y


NAND

● Weiteres Gatter: NAND▪ y = ¬(a & b)

● Schaltsymbol

● Ersatzschaltung

● Analog: NOR

a b y

0 0 1

0 1 1

1 0 1

1 1 0

a

by

a

b

y


XOR

● „Exclusive OR“▪ y = a ≡ b

● Auch: „Antivalenz“

● Schaltsymbol

● Ersatzschaltunga b y

0 0 0

0 1 1

1 0 1

1 1 0

a

by≡

0

1

1

1

1

10

0


Exkurs: Timing-Diagramme

● Zeitliche Darstellung von Gatterschaltungen▪ Hier: Eingänge a,b,e zeitlich variabel

a=1 =0

b=1 =0

e=1 =0

y=1 =0

Zeit

yeab


Boolsche Algebra

● George Bool (1854)● Drei Operationen

▪ „|“ (ODER, DISJUNKTION, auch: „+“)

▪ „&“ (UND, KONJUNKTION, auch: „ · “)

▪ „¬“ (NICHT, NEGATION, auch )

● Zwei Werte (0,1)


Boolsche Algebra: Axiome

● Axiome▪ Kommutativität: a|b = b|a , a&b = b&a▪ Neutrales Element: 0|a=a , 1&a=a ▪ Distributivität

• x = a & (b | c) = (a & b) | (a & c)• x = a | (b & c) = (a | b) & (a | c)

▪ Komplementäres Element• a |¬a = 1

• b & ¬b = 0

● Dualität▪ Durch Vertauschung von 1↔0 sowie „|“↔„&“ entsteht

wieder gültige Aussage


Gesetze zur Umformung

● Assoziative Gesetze▪ x = a & b & c = a & (b & c) = (a & b) & c▪ x = a | b | c = a | (b | c) = (a | b) | c

● Distributive Gesetze▪ x = a & (b | c) = (a & b) | (a & c)▪ x = a | (b & c) = (a | b) & (a | c)

● De Morgansche Gesetze▪ x = ¬(a & b) = ¬a | ¬b▪ x = ¬(a | b) = ¬a & ¬b


Normalformen

● y ist nur dann 1, wenn Zeile zu 1 verknüpft:▪ y1=¬a & ¬b & ¬c

▪ y2=¬a & ¬b & c

▪ y5= a & ¬b & ¬c

● Zeile verODERn:▪ y=(¬a & ¬b & ¬c)

| (¬a & ¬b & c) | (a & ¬b & ¬c)

● DISJUKTIVE Normalform

a b c y

0 0 0 1

0 0 1 1

0 1 0 0

0 1 1 0

1 0 0 1

1 0 1 0

1 1 0 0

1 1 1 0


● y ist nur dann 0, wenn Zeile zu 0 verknüpft:▪ y3= a | ¬b | c

▪ y4= a | ¬b | ¬c

▪ y6=¬a | b | ¬c

▪ y7=¬a | ¬b | c

▪ y8=¬a | ¬b | ¬c

● Zeile verUNDen:▪ y=(a | ¬b | c) & (a | ¬b | ¬c) &

(¬a | b | ¬c) & (¬a | ¬b | c) &(¬a | ¬b | ¬c)

● KONJUNKTIVE Normalform

Normalformen

a b c y

0 0 0 1

0 0 1 1

0 1 0 0

0 1 1 0

1 0 0 1

1 0 1 0

1 1 0 0

1 1 1 0


Normalformen

● Jede Schaltfunktion lässt sich als genau eine▪ konjunktive▪ disjunktive

● Normalform darstellen● Abgesehen von Vertauschungen sind diese

Formen eindeutig● Daraus folgt: Alle Schaltfunktionen sind durch

die 3 boolschen Grundoperationen darstellbar


Darstellung der 3 Grundoperationen

● Können mit ¬, &, | alle Funktionen darstellen● Brauchen wir auch diese 3 Gatter?

▪ NICHT („¬“) kann durch NAND dargestellt werden

▪ UND kann durch NAND dargestellt werden

y

x

ist gleichx y

ya

bist gleich

a

by


Darstellung der 3 Grundoperationen

▪ ODER kann durch NAND dargestellt werden• DeMorgan:

y = ¬(¬a & ¬b) = a | b• NOT vor jeden Eingang:

ya

b


Zusammenfassung

● Binäre Schaltfunktionen y(a,b,c….)▪ Als Wahrheitstabelle▪ Oder Darstellung durch 3 Grundoperationen: NICHT,

UND, ODER• Als boolsche Funktion• Als Schaltung

● Suche kostensparende Form der Implementierung von y()


Zusammenfassung

● Umformungsgesetze:▪ Assoziativgesetze, Distributivgesetze und deMorgan

● KV-Diagramme▪ Suche nach Logikblöcken▪ VerUNDere Variablen, verODERe Blöcke

● Normalformen● Darstellung jeder Schaltfunktion

▪ durch konjunktive, bzw. disjunktive Normalform▪ benötigt nur die 3 Grundoperationen

● Darstellung aller Grundoperationen durch z.B. NAND


Teil 1: Logik1b: Schaltnetze


Schaltnetze

● Schaltnetze● sind Funktionen, die von mehrere gleichen

Eingangsvariablen abhängen▪ y1=y1(x1….xn)

▪ y2=y2(x2….xn) …

▪ ym=ym(x1….xn)

● Beispiel für Schaltnetze: Addition und Subtraktion von Zahlen


Zahlensysteme

● Römische Zahlen▪ Buchstaben: I=1, V=5, X=10▪ Nicht skalierbar…

● Arabische Zahlen: 1,2,3,4,5,6,7,8,9,0▪ 10 Ziffern (10 Finger?)▪ 1972 = 2*1 + 7*10 + 9*10*10 + 1*10*10*10▪ Skalierbar!

● Logik: 2 Zustände darstellbar▪ 2 Ziffern: 0,1


Duales (Binäres) Zahlensystem

● Bsp: ▪ 1010 = 0*1 + 1*2 + 0*2*2 + 1*2*2*2 = 10

● Allgemein: ▪ Wertigkeit = 2Stelle-1

● 2er-Potenzen wichtig:▪ 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048…

● Dezimal -> Binär▪ Teilen + Rest bilden…


Umwandlung der Zahl 1972

● 2er-Potenzen:▪ 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048…

● Dezimal -> Binär▪ 11. Stelle: 1972 / 1024 = 1, Rest 948▪ 10. Stelle: 948 / 512 = 1, Rest 436▪ 9. Stelle: 436 / 256 = 1, Rest 180▪ 8. Stelle: 180 / 128 = 1, Rest 52▪ 7. Stelle: 52 / 64 = 0, Rest 52▪ 6. Stelle: 52 / 32 = 1, Rest 20▪ 5. Stelle: 20 / 16 = 1, Rest 4▪ 4. Stelle: 4 / 8 =0, Rest 4▪ 3. Stelle: 4 / 4 =1, Rest 0

● 1972 entspricht 111 1011 0100


Exkurs: Hexadezimalzahlen

● In Digitaltechnik praktisch: Alle Zahlensysteme mit einer Basis 2N

▪ Kann Bits zusammenfassen

● Gebräuchlich: ▪ Oktalsystem (3 Bits) ▪ Hexadezimalsystem (4 Bits)

● Gute Basis zur Beschreibung von Speicherstellen (da 8/16/32/64 Bit)

● Digits: 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F ● Bsp: 1972=111 1011 0100

0x7 B 4


Rechenregeln

● Im Prinzip wie im Dezimalsystem● Übertrag beachten (1+1=10, 1+1+1=11)

0111 +1011

10 11 10 10=10010

Ziel: Rechenregeln

durch Gatterlogik aufbauen

10010 - 1011

11 11 11 10 =00111


Teil 1: Logik1b: Schaltnetze


Addition

● 2-Bit-Addition▪ Summe und Übertrag Ü

● Funktionstabelle

A B Ü

0 0 0 0

0 1 0 1

1 0 0 1

1 1 1 0

A

B≡

A

BÜ

● Halbaddierer▪ Keine Verarbeitung des

EINGANGSÜbertrages▪ Kann nur für die

niedrigste Stelle verwendet werden

● Schaltsymbol

HA

A

B

Ü


Volladdierer

● Brauchen dritten Summanden (C = „carry“)▪ Addition A+B▪ Addition +C

▪ Da nie Ü1=Ü2=1• Verbleibende Überträge verodern

HA

A

B

Ü1

HA

C

Ü2

Ü

VA

A

C

Ü

B


Paralleladdierer

● Ziel: Addition von 0111 + 1011 ▪ 4 2-Bit-Additionen plus Übertrag (C)▪ Brauchen 4 Volladdierer

VA

A1 B1

Ü1

C

1 1

0

0

1VA

A2 B2

Ü2

C

1 1

1

1VA

A3 B3

Ü3

C

1 0

0

1VA

A4 B4

5

C

0 1

0

1


Subtraktion

● 2-Bit-Subtraktion A-B▪ Differenz D und Entlehnung E

● Funktionstabelle

A B E D

0 0 0 0

0 1 1 1

1 0 0 1

1 1 0 0

A

BD≡

● Halbsubtrahierer▪ Keine Verarbeitung der

EINGANGSEntlehnung▪ Kann nur für die

niedrigste Stelle verwendet werden

● Schaltsymbol

HS

A

B

D

E

A

BE


Vollsubtrahierer

● Hier: A - (B + C)▪ Addition B+C▪ Subtraktion A - Summe

▪ Da nie Ü1=E2=1• Verbleibende Überträge verodern

HA

B

C

Ü1

HS

C D

E2

E

VS

A

C

D

E

B


Volladdierer / -subtrahierer

● Volladdierer vs. Subtrahierer▪ Austausch durch HA↔HS in 2ter Stufe▪ HA vs. HS

• Nur ein logisches UND

● Fazit: Brauchen umschaltbaren Inverter

u A I

0 0 0

0 1 1

1 0 1

1 1 0

u

AI≡


Zusammenfassung

● Halbaddierer / -subtrahierer unterscheiden sich nur durch ein NICHT-Gatter

● Umschaltbarer HA/HS möglich● Brauchen Volladdierer…

▪ HA+HA

● Brauchen Vollsubtrahierer…▪ HA+HS

● …für parallele Rechenwerke

Weitere wichtige Schaltnetze?

Documents

Technische Informatik I (SS 2006) Digitale Information Schalter Lampenzustand ist Tabelle von Schalterzustand Analoge vs. Digitale Informationen Analoge