Übungen - Umwandlung von Binär-,Dezimal- und Hexadezimaldarstellung - Darstellungen für ganze Zahlen - OBDDs - Multiplexer Rechnerstrukturen (Block A-1/2/3/4) 08.10.2014 PDF

Preview

Summary

Umwandlung von Binär-,Dezimal- und Hexadezimaldarstellung - Darstellungen für ganze Zahlen - OBDDs - Multiplexer Rechnerstrukturen (Block A-1/2/3/4) 08.10.2014...

Description

08. Oktober 2014

Rechnerstrukturen im WS 2014/15 Übungsblatt 1 (Block A-1)

Aufgabe 1 (Umwandlung von Binär-, Dezimal- und Hexadezimaldarstellung) (4 Punkte) In den folgenden Paaren ist links die Repräsentation einer Zahl zur Basis 2, 10 oder 16 gegeben. Wandeln Sie diese in eine Repräsentation zu der Basis um, die als rechter Teil des Paares angegeben ist. a) (111011)2, 10 b) (1A9)16, 10 c) (11101011001)2, 16 d) (A37)16, 2

Aufgabe 2 (Divisionsmethode) (4 Punkte) a) Konvertieren Sie mit der Divisionsmethode (Algorithmus 1) folgende Dezimalzahl in die Binärdarstellung: 55 . Schreiben Sie alle Schritte auf. b) Konvertieren Sie mit der Divisionsmethode (Algorithmus 1) folgende Dezimalzahl in die Hexadezimaldarstellung: 380. Schreiben Sie alle Schritte auf.

Aufgabe 3 (Einfachste Umrechnungen) (4 Punkte) a) Wandeln Sie folgende Zahlen ins Dezimalsystem um. Die Zahlendarstellung der gegebenen Zahl ist jeweils angegeben. Betragszahl:

1001

Festkomma-Betragszahl: 0101,01 Vorzeichen-Betrag:

001011; 101100

Einerkomplement:

001101; 110011

Zweierkomplement:

001110; 110010

Exzessdarstellung, Bias 35, 7Bit: 0010001, 1000011 b) Sie finden folgende zwei „Geheimcodes: 1. 2.

57 69 6E 74 65 74 20 31 34 44 C3 B6 6E 65 34 62 75 64 65

Versuchen Sie ihn zu entschlüsseln.

-1-

Aufgabe 4 (Ordnen von Zahlen) (4 Punkte) Betrachten Sie die folgenden Bitmuster: 0100, 0011, 1100, 1000. Tragen Sie in der unten stehenden Tabelle jeweils diese Bitmuster aufsteigend nach der Größe der durch sie repräsentierten Zahlen sortiert von links nach rechts aufsteigend ein. (Binärdarstellung verwenden) Repräsentation Einerkomplement Zweierkomplement Vorzeichen-Betrag Exzess mit Bias 25

geordnete Bitmuster

Die Abgaben sollen bis Mittwoch den 15. Oktober 2014 um 18.00 Uhr in die Briefkästen in der Otto-Hahn-Strasse 12 eingeworfen werden. Bitte Name (bei einem 3er-Team alle), Matrikel- und Gruppennummer oben auf allen Seiten der Lösungen angeben. Es gibt insgesamt 12 Übungblätter, die in 3 Blöcke (A,B,C) aufgeteilt sind. In jedem Block müssen Sie 20 Punkte erreichen, um zur Prüfung zugelassen zu werden. Schreiben Sie die Gruppennummer gut lesbar rechts oben auf das Blatt. Heften Sie die Abgabe zusammen. (Tacker oder notfalls Büroklammer). Falten Sie aber nicht ihre Abgabe. Stecken Sie die Abgabe nicht in einen Umschlag. Benutzen Sie den richtigen Briefkasten. Dazu benötigen Sie ihre Gruppennummer. Die Übungen beginnen am 20. Oktober 2014 mit der Besprechung dieser Aufgaben.

-2-

15. Oktober 2014 Rechnerstrukturen im WS 2014/15 Übungsblatt 2 (Block A-2) Aufgabe 1 (Darstellungen für ganze Zahlen) (4 Punkte) a) Die ganze Dezimalzahl −14 soll mit fünf Bits repräsentiert werden. Geben Sie jeweils das passende Bitmuster für die untenstehenden Darstellungen an. Vorzeichenbetragsdarstellung: Einerkomplementdarstellung: Zweierkomplementdarstellung: Exzessdarstellung mit Bias 15: b) Das Bitmuster 1001 0111 soll als ganze Zahl interpretiert werden. Geben Sie zu jeder der unten angegebenen Darstellungen an, welche ganze Zahl durch dieses Bitmuster repräsentiert wird. Vorzeichenbetragsdarstellung: Einerkomplementdarstellung: Zweierkomplementdarstellung: Exzessdarstellung mit Bias 127:

Aufgabe 2 (Darstellung von rationalen Zahlen) (4 Punkte) a) Stellen Sie -33,625 als Gleitkommazahl im Format IEEE 754-1985 mit 32 Bits dar. b) Geben Sie in Dezimaldarstellung an, welche rationale Zahl durch 1 1000 0011 101 1010 0000 0000 0000 0000 im Format IEEE 754-1985 codiert wird.

Aufgabe 3 (Algebraische Umformungen) (4 Punkte) Boolesche Formeln sind eine Möglichkeit, boolesche Funktionen darzustellen. Sie können mit Hilfe der booleschen Rechengesetze algebraisch umgeformt werden. Benutzen Sie diese Umformungen, um die Formeln zu vereinfachen. Vereinfachen Sie so weit wie möglich die folgenden booleschen Formeln. Verwenden Sie außer Klammern, Variablen und Konstanten nur die Operatoren ∧, ∨ und die Negation. Verwenden Sie zur Darstellung der Negation ausschließlich den Querstrich, ggfs. auch über ganze Subterme.

a) a ∧ (a ⊕ b) b) (a ∧ b ∧ c) ∨ (a ∧ b ∧ c) ∨ (a ∧ b ∧ c)

-1-

Aufgabe 4 (Normalformen) (4 Punkte) a)

Die booleschen Funktionen f und g sind durch die folgenden Wertetabellen gegeben. a 0 0 0 0 1 1 1 1

b 0 0 1 1 0 0 1 1

c 0 1 0 1 0 1 0 1

f(a,b,c) 0 1 0 0 1 0 0 1

x 0 0 0 0 1 1 1 1

y 0 0 1 1 0 0 1 1

z 0 1 0 1 0 1 0 1

g(x,y,z) 1 1 0 1 1 1 1 0

Geben Sie f und g in entweder disjunktiver oder konjunktiver Normalform an. Sie sollen aber jeweils nur die Darstellung wählen, die am „einfachsten“ ist (am wenigsten Arbeit macht). Begründen Sie Ihre Wahl. b) Gegeben sei eine boolesche Funktion f(x,y,z). Geben Sie die DNF an.

f = (x ∧ y)∨ (x ∧ y ∧ z)

Die Abgaben sollen bis Mittwoch den 22.Oktober 2014 um 18.00 Uhr in die Briefkästen in der Otto-Hahn-Strasse 12 eingeworfen werden. Bitte Name (bei einem 3er-Team alle), Matrikelund Gruppennummer oben auf allen Seiten der Lösungen angeben.

-2-

22. Oktober 2014

Rechnerstrukturen im WS 2014/15 Übungsblatt 3 (Block A-3) Aufgabe 1 (OBDDs) (4 Punkte) Gegeben seien vier Graphen G1, G2, G3, G4, die Funktionen f1, f2, f3, f4 : B4 → B repräsentieren sollen. Entscheiden Sie, ob diese πOBDDs darstellen. Begründen Sie Ihre Antwort. Falls ein Graph ein πOBDD ist, reduzieren Sie ihn schrittweise unter Angabe der angewendeten Regeln zu einem minimalen πOBDD. G1

G2

x1

x1

0

0

1

1

x2

x2

x3

1

x2 0

1

0

1

1

x3 1

x4

x2

0

1

0

0

0

1

1

0

G3

0

1

G4 x4 0

1

x5

0

1

1

x1

x3 1 0

0

0

x3

1

0

0

x2 1

1

0

x1 1

0

0

x3 1

1

Aufgabe 2 (OBDDs) (4 Punkte) Sie sollen das unten angegebene πOBDD schrittweise unter Anwendung der Reduktionsregeln reduzieren. In jedem Schritt darf jeweils nur eine Reduktionsregel einmal angewendet werden. Geben Sie in der nummerierten Liste jeweils die angewendete Regel an und markieren Sie die Knoten, auf welche die Regel angewendet werden soll, indem Sie die entsprechende Zeilennnummer in die betroffenen Knoten schreiben. Sie brauchen nicht nach jeder Regelanwendung ein neues πOBDD zeichnen. Nur das reduzierte πOBDD stellen Sie unten einmal gesondert dar. Es müssen nicht so viele Regelanwendungen gefunden werden, wie Zeilen in der Liste zur Verfügung stehen. x2 0

1. ______________________________

1

x1 0

x3 0

x4 0

x3

3. ______________________________

0

4. ______________________________

1

1

x4

1

2. ______________________________

1

0

0

x4

0

5. ______________________________

1

1

1

-1-

Aufgabe 3 (Rechnen mit Zweierkomplementen) (4 Punkte) Berechnen Sie: 1) 2) 3) 4)

10011110 00011101 00001010 01011010

+ +

01100111 01011000 10001101 00111100

Die Zahlen sind in Zweierkomplementdarstellung (8-bit Breite) gegeben. Geben Sie das Ergebnis ebenfalls in dieser Darstellung an. Geben Sie an, wenn ein Ergebnis ungültig ist. (das wird extra bepunktet) Aufgabe 4 (Additionsschaltnetze) (4 Punkte) Es sollen zwei 8bit binär codierte Betragszahlen x = (x7 ... x0)2 und y = (y7 ... y0)2 addiert werden. Wie Sie wissen, werden dafür Überträge üi berechnet. Dabei entsteht der Übertrag üi bei der Addition von xi−1, yi−1 und üi−1. Uns interessiert die Laufzeit, bis das Ergebniss der höchsten Stelle c8 vorliegt. (c 8 wird an den Eingang der nächsten Stelle weitergeleitet) Skizzierien Sie das Addierwerk für einen Ripple-Carry-Adder mit 8 bit Breite. Verwenden Sie für die Skizze möglichst wenige Halb- und Volladdierer. Skizzieren Sie ebenfalls den Aufbau eines Halb- und Volladdierers. Es stehen die Gatter „UND “, „ODER“ und „XOR “ zur Verfügung. Die Laufzeit eines Gatters sei jeweils t. Nehmen wir an, dass die Summanden xi und yi gleichzeitig an den HA und VA anliegen. Wie groß ist die Laufzeit tg bis das Ergebnis von c8 vorliegt? Die Laufzeit der Halb- und Volladdierer hängt von deren innerem Aufbau ab und ist entsprechend zu berücksichtigen.

Die Abgaben sollen bis Mittwoch den 29. Oktober 2014 um 18.00 Uhr in die Briefkästen in der Otto-Hahn-Strasse 12 eingeworfen werden. Bitte Name (bei einem 3er-Team alle), Matrikel- und Gruppennummer oben auf allen Seiten der Lösungen angeben.

-2-

29. Oktober 2014

Rechnerstrukturen im WS 2014/15 Übungsblatt 4 (Block A-4) Aufgabe 1 (Multiplexer) (4 Punkte) Gegeben ist die Schaltung eines 4 zu 1 Multiplexers. Geben Sie die Ausgabewerte von y = f(s0,s1,e1,e2) für alle möglichen Eingabewerte tabellarisch an. (s = Steuereingang, s0 niederwertiger als s1, e = Dateneingang). Die Eingänge 1 und 3 des MUX sind fest belegt. e1

&

0

1

1 M U 2 X

0 e2 1

y

3

s0 s1 s0

s1

e1

e2

y

Aufgabe 2 (Gleitkommaarithmetik) (4 Punkte) Gegeben seien Zahlen in 32-Bit-Gleitkommadarstellung nach IEEE 754-1985. Führen Sie die folgende Rechnung mittels Gleitkommaarithmetik durch und notieren Sie auch das Ergebnis in dieser Darstellung. Geben Sie Ihre Rechenschritte nachvollziehbar an. Berechnen Sie GKZ1 - GKZ2:

GKZ1: 0 1000 0001 010 0101 0000 0000 0000 0000 GKZ2: 1 1000 0101 111 1010 1000 0000 0000 0000

Aufgabe 3 (Gleitkommaarithmetik) (4 Punkte) Gegeben seien Zahlen in 32-Bit-Gleitkommadarstellung nach IEEE 754-1985. Führen Sie die folgende Multiplikation schrittweise nachvollziehbar in dieser Darstellung durch und geben Sie auch das Ergebnis in diesem Format an. Multiplizieren Sie GKZ1 mit GKZ2:

GKZ1: 1 1000 1100 010 1000 0000 0000 0000 0000 GKZ2: 0 0111 1101 101 0000 0000 0000 0000 0000

-1-

Aufgabe 4 (KV-Diagramme) (4 Punkte) a) Gegeben sei eine boolesche Funktion f1: B4 → B auf x1, x2, x3, x4 durch ihren Wertevektor (1,1,1,1, 1,1,1,1, 0,0,0,1, 0,0,0,1). Geben Sie für die Funktion f1 die Menge aller Primimplikanten an. b) Gegeben sei eine boolesche Funktion f2: B4 → B auf x1, x2, x3, x4 durch ihren Wertevektor (1,1,0,1, 0,1,0,1, 1,1,1,1, 0,0,0,0). Geben Sie für die Funktion f2 die Menge aller Primimplikanten an. Hinweis: Lösen Sie die Aufgabe unter Verwendung von KV-Diagrammen.

Die Abgaben sollen bis Mittwoch den 05. November 2014 um 18.00 Uhr in die Briefkästen in der Otto-Hahn-Strasse 12 eingeworfen werden. Bitte Name (bei einem 3er-Team alle), Matrikel- und Gruppennummer oben auf allen Seiten der Lösungen angeben.

-2-...