Übungsaufgaben Lösungen PDF

Preview

Summary

Lösungen zu den Tutorübungsaufgaben...

Description

Digitaltechnik

Übungsaufgaben

Grundlagen

1 Grundlagen der Digitaltechnik 1.1 Datenkodierung Zahlensysteme und Kodierung von Festkommazahlen Vorzeichen-Betrag Gegeben sei folgende Zahlentabelle mit Dezimal-, Binär-, Octal- bzw. Hexadezimalzahlen. Die Darstellung der Binärzahlen hat maximal 12-Bit. Dezimal 168 −42 −1845 28

Binär 000010101000 100000101010 111100110101 000000011100

Octal o0250 o4052 o7465 o0034

Hexadezimal 0x0A8 0x82A 0xF35 0x01C

1. Geben Sie den positiven bzw. negativen Zahlenbereich in Dezimal-, Octal- und Hexadezimalzahlen an. Lösung (A1) Das erste Zeichen wird nur für das Vorzeichen benutzt. Also bleiben noch n − 1 Zeichen für den Betrag übrig. Die Null wird bei der Vorzeichen-Betrag-Darstellung doppelt dargestellt, d.h. ∃ ± 0. Formel : − (2n−1 − 1) bis − 0 und + 0 bis (2n−1 − 1). Dezimal : − 2047 bis − 0 und 0 bis 2047 Binär : 111111111111 bis 100000000000 und 000000000000 bis 011111111111 Octal : o7777 bis o4000 und o0000 bis o3777 Hexadezimal : 0xF F F bis 0x800 und 0x000 bis 0x7F F

2. Wieso sind 12-Bit für die binäre Darstellung sinnvoll? Lösung (A2) Für die Darstellung einer Octalstelle werden 3 Bit benötigt. Für die Darstellung einer Hexadezimalstelle werden 4 Bit benötigt. 1111 = 0xF 111 = o7 Deswegen wird zur optimalen Ausnutzung des Bitbereiches das kleinste gemeinsame Vielfache verwendet: 3 · 4 = 12 (Bit). 3. Ergänzen Sie die Tabelle um die fehlenden Einträge. 1

Digitaltechnik

Übungsaufgaben

Grundlagen

Lösung (A3) Dezimal ⇒ Binär • Vorzeichen bestimmt Vorzeichenbit: + = ˆ 0, − = ˆ1 • Wiederholtes teilen mit Rest durch 2 liefert den Betrag • Auffüllen mit 0 auf 11 Bit liefert das Ergebnis Binär ⇒ Octal • Jeweils 3 Binärestellen ergeben eine Octalstelle Binär ⇒ Hexadezimal • Jeweils 4 Binärestellen ergeben eine Hexadezimalstelle 168 ⇒ Binär: 168: 2 = 84 Rest 0 (LSB) 84: 2 = 42 Rest 0

168 ⇒ Octal: 000 → 0 LSB 101 → 5

42: 2 = 21 Rest 0 21: 2 = 10 Rest 1 10: 2 = 5 Rest 0

010 → 2 000 → 0 MSB

5: 2 = 2 Rest 1 2: 2 = 1 Rest 0

168 ⇒ Hexadezimal: 1000 → 8 LSB 1010 → A 0000 → 0 MSB

1: 2 = 0 Rest 1 (MSB) Auffüllen mit 0 Auffüllen mit 0 Auffüllen mit 0 Vorzeichen 0 −42 ⇒ Binär: 42: 2 = 21 Rest 0 (LSB) 21: 2 = 10 Rest 1 10: 2 = 5 Rest 0 5: 2 = 2 Rest 1 2: 2 = 1 Rest 0 1: 2 = 0 Rest 1 (MSB) Auffüllen mit 0 Auffüllen mit 0

−42 ⇒ Octal: 010 → 2 LSB 101 → 5 000 → 0 100 → 4 MSB −42 ⇒ Hexadezimal: 1010 → A LSB 0010 → 2 1000 → 8 MSB

Auffüllen mit 0 Auffüllen mit 0 Auffüllen mit 0 Vorzeichen 1

2

Digitaltechnik

Übungsaufgaben

Fortsetzung (A3) 0xF 35 ⇒ Binär: F → 1111 3 → 0011

Grundlagen

0xF 35 ⇒ Octal: 111 → 7 MSB 100 → 4

5 → 0101

110 → 6 101 → 5 LSB

0xF 35 ⇒ Dezimal: Vorzeichenbit: 1 → − Betrag: 011100110101 →

11 X

2i bi = 210 + 29 + 28 + 25 + 24 + 22 + 20 = 1845

i=0

o0034 ⇒ Binär:

o0034 ⇒ Hexadezimal: 0000 → 0 MSB 0001 → 1 1100 → C LSB

0 → 000 0 → 000 3 → 011 4 → 100

o0034 ⇒ Dezimal: Vorzeichenbit: 0 → + (siehe auch: Wertebereich Octal aus Aufgabe 1) Betrag: 0034 →

3 X

8i oi = 3 · 81 + 4 · 80 = 28

i=0

4. Führen Sie folgende Subtraktionen binär durch (8-Bit Zahlen) (a) 16 − 12 (b) 34 − 65 (c) −5 − 124

3

Digitaltechnik

Übungsaufgaben

Grundlagen

Lösung (A4) a−b= c Bei der Verarbeitung in der Vorzeichen-Betrag-Darstellung muss das Vorzeichen und der Betrag jeweils seperat berechnet werden. Dazu müssen mehrere Fälle unterschieden werden: 1. a, b > 0 und a > b: Ergebnis ist positiv (Vorzeichenbit 0), Subtraktion ohne weitere Anpassungen 2. a, b > 0 und a < b: Ergebnis ist negativ (Vorzeichenbit 1), vertausche a und b und berechne −c = b − a 3. a < 0, b > 0 : Ergebnis ist negativ (Vorzeichenbit 1), addiere −a und b Bei der Addition bzw. Subtraktion werden beide Zahlen untereinander geschrieben und die Operation Stellenweise ausgeführt. Dabei liefert 1 + 1 einen 1 Übertrag (Carry) und 0 − 1 einen 1 Übertrag (Borrowbit) auf die nächst höhere Stelle. a) Ergebnis ist positiv ⇒ Vorzeichenbit = 0 00010000 (16) − 00001100 (12) 11

00000100

(4)

b) Ergebnis ist negativ ⇒ Vorzeichenbit = 1 01000001 (65) − 00100010 (34) 11111

00011111 (31) Vorzeichen anpassen: 10011111 (−31) c) Ergebnis ist negativ ⇒ Vorzeichenbit = 1 00000101 (5) + 01111100 (124) 1111

10000001 (−1) In diesem Fall ist −5 − 124 = −129, doch der Betrag 129 lässt sich nicht mit 7 Bit darstellen, weshalb es hier zu einem Fehler kommt. 5. Führen Sie folgenden Multiplikationen binär aus (4-Bit positive Zahlen). (a) 0011 · 0010 4

Digitaltechnik

Übungsaufgaben

Grundlagen

(b) 0101 · 1110 Lösung (A5) Die binäre Multiplikation ist eine wiederholte Addition von geshifteten Multiplikanden. a) Ein Sonderfall stellt die Multiplikation mit 2er Potenzen dar, hier werden die Stellen des Multiplikanden lediglich um die entsprechende Potenz nach links verschoben: 0011 · 0010 = 0011 10 ⇒ L3 leuchtet, 5 < Z < 11 ⇒ L2 leuchtet.

Gehen Sie beim Schaltungsentwurf wie folgt vor: (a) Stellen Sie die Wahrheitstabelle für die Ausgänge L1, L2 und L3 in Abängigkeit der Eingangssignale a, b, c und d auf. (b) Stellen Sie für jeden Ausgang entweder eine disjunktive Normalform (DNF) oder eine konjunktive Normalform (KNF) auf. Begründen Sie die Wahl Ihrer Normalform kurz. (c) Zeigen Sie, dass L3 abhängig von a ist. (d) Ihnen stehen ausschließlich die 2 Gattertypen AND, OR mit bis zu 5 Eingängen und das NOT-Gatter mit einem Eingang zur Realisierung der Schaltung zur Verfügung. Zeichnen Sie für die drei Ausgänge L1, L2 und L3 ein Gatterschaltbild. (e) Zusatzaufgabe: Versuchen Sie eine möglichst effiziente Gatterschaltung mit Standardgattern (d.h. auf 2 Eingänge beschränkte Gatter) zu realisieren. Hinweis: Verwenden Sie so viele Gatterausgänge wie möglich wieder. Lösung (A3)

3

Digitaltechnik

Übungsaufgaben

a)

0 0

0 0 0 1

1 1 0 1

0 0

0 0

0

0 1

1 1

0

0

0

1 0

0 1

0

0

0 0

1 0 1 1

1 1 0 0

0 1

0 0

0

1 1

1 0

1

0

1

0 0

0 0

1

0

1 1

0 0 0 1

1 0 0 0

1 1

0 0

1

0 1

1 0

0

1

1 1

1 0 1 0

0 0 1 0

0 0

1 1

1

1 1

0 0

0

1

1

1 1

1 0

0

1

abcd2 < 610

d L1 L2 L3 0 1 0 0

Wandelt man die Zahlenbereiche, welche die Bereichslogik erfassen soll, in Binärzahlen um, so lässt sich die Wahrheitstabelle sofort aufstellen: L1 = 1 für 010 ≤ abcd2 ≤ 510 ⇔ 00002 ≤ abcd2 ≤ 01012 L2 = 1 für 610 ≤ abcd2 ≤ 1010 ⇔ 01102 ≤ abcd2 ≤ 10102 L3 = 1 für 1110 ≤ abcd2 ≤ 1510 ⇔ 10112 ≤ abcd2 ≤ 11112

abcd2 > 1010

a b c 0 0 0

Grundlagen

b) Die Entscheidung ob kanonische konjunktive oder kanonische disjunktive Normalform gewählt wird, hängt maßgeblich vom prinzipiellen Logikaufwand ab: • jede 0-Zeile verursacht einen ODER-Term in der KNF, • jede 1-Zeile verursacht einen UND-Term in der DNF. D.h. enthält eine Wahrheitstabelle mehr Nullen als Einsen, so wird die KNF länger als die DNF. Umgekehrt verhält es sich wenn die Wahrheitstabelle mehr Einsen als Nullen enthält, dann wird die DNF länger als die KNF. Da jeder Ausgang der Bereichslogik mehr Nullen als Einsen enthält ist die DNF hier vorzuziehen. L1 = abcd + abcd + abcd + abcd + abcd L2 = abcd + abcd + abcd + abcd + abcd L3 = abcd + abcd + abcd + abcd + abcd

4

Digitaltechnik

Übungsaufgaben

Grundlagen

Fortsetzung (A2) c) Um zu zeigen dass L3 abhängig von a ist überprüfen wir die Kofaktoren von L3: L3 = abcd + abcd + abcd + abcd + abcd = a(bcd + bcd + bcd + bcd + bcd) L3a = 1(bcd + bcd + bcd + bcd + bcd) = bcd + bcd + bcd + bcd + bcd L3a = 0(bcd + bcd + bcd + bcd + bcd) = 0 L3a 6= L3a ⇒ L3 ist abhängig von a. d) a b c d • • • •

a b c d • • • •

&

• • • •

&

• • • •

&

• • • • • • • •

• • • •

&

• • • •

&

&

• • • •

&

• • • •

≥1

L1

a b c d • • • •

&

&

• • • •

&

• • • •

&

&

• • • •

&

&

• • • •

&

5

≥1

L2

≥1

L3

Digitaltechnik

Übungsaufgaben

Realisierung

2 Realisierung digitaler Schaltungen 2.1 MOSFET MOSFET

1. Der Kondensator C ist zu Beginn entladen. (a) Auf welche Spannung wird er aufgeladen, wenn sowohl A als auch das Gate des Transistors auf VDD gelegt werden? (b) Auf welche Spannung wird er entladen wenn anschließend A auf gnd gelegt wird? Lösung (A1) a) x

Laut Maschenregel sind die Abhängigkeiten der Spannungen UDD, UGS und UC am Eingang sowie die Abhängigkeiten der Spannungen UDD, UDS und UC am Ausgang wie folgt beschrieben: UGS = UDD − UC und UDS = UDD − UC Zu Beginn sei der Kondensator entladen, d.h. UC = 0. Wenn wir annehmen, dass die Schwellspannung Ut des Transistors kleiner als die Versorgungsspannung UDD ist, d.h. dass Ut < UDD , dann ist UGS > Ut und UDS > 0, ⇒ ID 6= 0, und der Kondensator wird aufgeladen. Sobald der Kondensator auf die Spannung UC = UDD − Ut aufgeladen ist, ist UDS = UDD − UC = UDD − UDD + Ut = Ut , und UGS = UDD − UC = UDD − UDD + Ut = Ut . 1

Digitaltechnik

Übungsaufgaben

Lösung (A11) Die UTF-8 Kodierung der deutschen Umlaute ist Zeichen Ä Ö Ü ä ö ü

UTF-8 0x C384 0x C396 0x C39C 0x C3A4 0x C3B6 0x C3BC

, benötigen also jeweils 2 Byte (16 Bit). In der ASCII-Kodierung (mit der entsprechenden Ersetzung der Umlaute) ist Zeichen Ä Ö Ü ä ö ü

Ersetzung ASCII Ae Oe Ue ae oe ue

1000001 1100101 1001111 1100101 1010101 1100101 1100001 1100101 1101111 1100101 1110101 1100101

Grundlagen

, d.h. es werden nur 2 · 7 Bit = 14 Bit anstatt 16 Bit zur Kodierung der Umlaute benötigt. Die ASCIIVariante ist somit für Texte effizienter, die ausschließlich „normale“ Buchstaben, Zahlen und Umlaut (dann mit Ersetzung) enthalten. Für das deutsche „ß“ benötigen wir allerdings weiterhin einen erweiterten Zeichenumfang, der sich mi ASCII nicht darstellen lässt. Die Gewöhnung an die Umlaute trägt weiter dazu bei, dass sich lange Texte mit Umlauten „fluessiger“ lesen. Speziell in der Mathematik benötigt man häufig griechische Buchstaben (α, β, . . . , ω) und im interna tionalen Umfeld kommen dann noch Sonderzeichen wie z.B. ï, â, á und ¿ hinzu, welche den ASCIIZeichenvorrat vollends sprengen. 12. Welchen Vorteil bietet eine Zeichenkodierung mit variabler Codewortlänge?

Lösung (A12) Durch eine variable Codewortlänge lassen sich Texte effizienter kodieren als mit einer festen Codewort länge. Beispiel: Ca. 1,87% der Buchstaben im deutschen sind ∈ {Ä,Ö,Ü,ä,ö,ü,ß}, d.h. die durchschnittlich benötigte Anzahl an Bit errechnet sich für UTF-8 zu B = 0, 0187 · 16 Bit + 0, 9813 · 8 Bit = 8, 1496 Bit Im Gegensatz dazu benötigt man bei einer UTF-32 Kodierung (konstante Kodierung mit 32 Bit) durch schnittlich 32 Bit. 13

Digitaltechnik

Übungsaufgaben

Grundlagen

14

Digitaltechnik

Übungsaufgaben

1 Grundlagen der Digitaltechnik

Grundlagen

1.2

Boolesche Algebra

Boolesche Algebra 1. Zeigen Sie, dass Folgendes gilt: a + ab = a + b Lösung (A1) Für diese Aufgabe gibt es im Prinzip drei Lösungswege: • „Brute Force“ Lösung: mittels Wahrheitstabelle • Argumentative Lösung • Formale Lösung: mittels logischer Umformungen

„Brute Force“: nur sinnvoll für Gleichungen mit wenig Variablen und wenig Logikverknüpfungen. Durch Zerlegung der Gleichung in kleinere Elemente und sukzessive Verknüpfung von Teilergebnissen in de Wahrheitstabelle gelangt man bei kleinen Gleichungen mit wenig Variablen schnell zur Ausgangsglei chung der Logikgleichung. a b a ab a + ab a + b 0 0 1 0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 0 0 1 1

Argumentativ: wenn a = 1 ist die Gleichung immer 1, der zweite Teil ist unerheblich. Wenn a = 0 kommt der zweite Teil ins Spiel: da in diesem Fall a = 1 hängt dieser Teil von b ab. Ist b = 0 ist die Gleichung 0, ansonsten 1. Zusammenfassend: a + ab = 0 nur wenn a = 0 und b = 0. Diese Verknüpfung entspricht einem ODER.

Formal: zunächst wird die Gleichung leicht aufgebläht, dabei wird ausgenutzt dass a · 1 = a und b + 1 = 1 ist a + ab = a1 + ab = a(1 + b) + ab. Durch ausmultiplizieren erhält man: a(1 + b) + ab = a + ab + ab. Klammert man nun noch b aus den beiden letzten Termen aus ergibt sich a + ab + ab = a + b(a + a).

Der Term in der Klammer, a + a ist nach dem Komplementärgesetz gleich 1, d.h. a + a = 1. Dami erhalten wir a + b(a + a) = a + b1 = a + b.

Einen zweiten, sehr eleganten formalen Lösungsweg gibt es durch die Anwendung des allgemeinen Resolutionsgesetzes und des Absorptionsgesetzes: a + ab = a + ab + 1b

Resolutionsgesetz mit 1a + ab

a + (ab) + b = a + b

Absorptionsgesetz mit (ab) + b

1

Digitaltechnik

Übungsaufgaben

Grundlagen

2. Vereinfachen Sie die folgenden Ausdrücke. (a) ac · ac + bd · bd + c (b) a(a ⊕ b) + b + (b + c)(b + c) Lösung (A2) ac · ac + bd · bd + c = ac + ac + bd + bd + c

(DeMorgan)

= ac + ac + bd + bd + c = a(c + c) + b(d + d) + c =a+b+c

(Komplementärgesetz)

Das XOR, ⊕, entspricht der Funktion „a oder b OHNE (a und b)“ („ (a + b)\(ab) “). Dies Entspricht a ⊕ b = (a + b) · (ab)

= (a + b) · (a + b) = aa + ba + ab + bb

(Komplementärgesetz: aa = 0)

= ba + ab. Damit wird der umzuformende Ausdruck: a(a ⊕ b) + b + (b + c)(b + c) = a(ba + ab) + b + (b + c)(b + c)

(XOR)

= aab + aab + b + bb + bc + cb + cc = 0b + ab + b + 0 + bc + cb + 0

(Komplementärgesetz)

= 0 + (a + 1)b + bc + cb = 1b + bc + cb = (1 + c)b + bc = b + bc

Dieser Ausdruck lässt sich noch kompakter schreiben wenn wir das Ergebnis aus Aufgabe 1 wiederver wenden, wobei a=b ˆ und b=c: ˆ b + bc = b + c.

Schaltungsentwurf

3. Entwickeln Sie eine digitale Schaltung die zur Bereichsprüfung einer positiven 4-Bit Zahl Z = abcd dient, a sei das MSB. Der Bereich in dem die Zahl liegt, soll durch drei LEDs, L1,L2 und L3, angezeigt werden, wobei jeweils nur eine LED gleichzeitig an sein soll. Damit ergeben sich drei Bereiche für die Zahl Z : 2

Digitaltechnik

Übungsaufgaben

Grundlagen

Z < 6 ⇒ L1 leuchtet, Z > 10 ⇒ L3 leuchtet, 5 < Z < 11 ⇒ L2 leuchtet.

Gehen Sie beim Schaltungsentwurf wie folgt vor:

(a) Stellen Sie die Wahrheitstabelle für die Ausgänge L1, L2 und L3 in Abängigkeit der Eingangssignale a, b, c und d auf.

(b) Stellen Sie für jeden Ausgang entweder eine disjunktive Normalform (DNF) oder eine konjunktive Normalform (KNF) auf. Begründen Sie die Wahl Ihrer Normalform kurz. (c) Zeigen Sie, dass L3 abhängig von a ist.

(d) Ihnen stehen ausschließlich die 2 Gattertypen AND, OR mit bis zu 5 Eingängen und das NOT-Gatter mit einem Eingang zur Realisierung der Schaltung zur Verfügung. Zeichnen Sie für die drei Ausgänge L1, L2 und L3 ein Gatterschaltbild.

(e) Zusatzaufgabe: Versuchen Sie eine möglichst effiziente Gatterschaltung mit Standardgattern (d.h. auf 2 Eingänge beschränkte Gatter) zu realisieren. Hinweis: Verwenden Sie so viele Gatterausgänge wie möglich wieder. Lösung (A3)

3

Digitaltechnik

Übungsaufgaben

a)

0 0

0 0 0 1

1 1 0 1

0 0

0 0

0

0 1

1 1

0

0

0

1 0

0 1

0

0

0 0

1 0 1 1

1 1 0 0

0 1

0 0

0

1 1

1 0

1

0

1

0 0

0 0

1

0

1 1

0 0 0 1

1 0 0 0

1 1

0 0

1

0 1

1 0

0

1

1 1

1 0 1 0

0 0 1 0

0 0

1 1

1

1 1

0 0

0

1

1

1 1

1 0

0

1

abcd2 < 610

d L1 L2 L3 0 1 0 0

Wandelt man die Zahlenbereiche, welche die Bereichslogik erfas sen soll, in Binärzahlen um, so lässt sich die Wahrheitstabelle sofor aufstellen: L1 = 1 für 010 ≤ abcd2 ≤ 510 ⇔ 00002 ≤ abcd2 ≤ 01012 L2 = 1 für 610 ≤ abcd2 ≤ 1010 ⇔ 01102 ≤ abcd2 ≤ 10102 L3 = 1 für 1110 ≤ abcd2 ≤ 1510 ⇔ 10112 ≤ abcd2 ≤ 11112

abcd2 > 1010

a b c 0 0 0

Grundlagen

b) Die Entscheidung ob kanonische konjunktive oder kanonische disjunktive Normalform gewählt wird, hängt maßgeblich vom prinzipiellen Logikaufwand ab: • jede 0-Zeile verursacht einen ODER-Term in der KNF, • jede 1-Zeile verursacht einen UND-Term in der DNF.

D.h. enthält eine Wahrheitstabelle mehr Nullen als Einsen, so wird die KNF länger als die DNF. Um gekehrt verhält es sich wenn die Wahrheitstabelle mehr Einsen als Nullen enthält, dann wird die DNF länger als die KNF. Da jeder Ausgang der Bereichslogik mehr Nullen als Einsen enthält ist die DNF hier vorzuziehen. L1 = abcd + abcd + abcd + abcd + abcd L2 = abcd + abcd + abcd + abcd + abcd L3 = abcd + abcd + abcd + abcd + abcd

4

Digitaltechnik

Übungsaufgaben

Grundlagen

Fortsetzung (A2) c) Um zu zeigen dass L3 abhängig von a ist überprüfen wir die Kofaktoren von L3: L3 = abcd + abcd + abcd + abcd + abcd = a(bcd + bcd + bcd + bcd + bcd) L3a = 1(bcd + bcd + bcd + bcd + bcd) = bcd + bcd + bcd + bcd + bcd L3a = 0(bcd + bcd + bcd + bcd + bcd) = 0 L3a 6= L3a ⇒ L3 ist abhängig von a. d)

a b c d • • • •

a b c d • • • •

&

• • • •

&

• • • •

&

• • • • • • • •

• • • •

&

• • • •

&

&

• • • •

&

• • • •

≥1

L1

a b c d • • • •

&

&

• • • •

&

• • • •

&

&

• • • •

&

&

• • • •

&

5

≥1

L2

≥1

L3

Digitaltechnik

Übungsaufgaben

Realisierung

2 Realisierung digitaler Schaltungen 2.1 MOSFET MOSFET

1. Der Kondensator C ist zu B...