Klausur 2010, lösungen PDF

Preview

Summary

Download Klausur 2010, lösungen PDF

Description

RA-Klausur SS 2010 I (Lösung) von Tobias Munzert, Julia Bugl, Alexander Kehr, Stefanie Schreiner, Carla Harth

1. Multiple Coice (20 Pkt.) Darstellung von Informationen a Die Wortlänge des Systems hängt von der Datenbusbreite ab. b Mit einer 2-Bit-Zahl in Einer-Komplement-Darstellung kann man genau 3 verschiedene ganze Zahlen darstellen. c Jede vier Bit lange Binärzahl lässt sie durch eine Oktalziffer ausdrücken. d Nach IEEE-Standard wird der Exponent im Zweierkomplement dargestellt. e Um ein Schwarz/Weiß-Bild mit den Abmessungen m*n Pixel unkomprimiert zu speichern, benötigt man (aufgerundet) log2 (m*n) Bit.

Wahr x x

Arithmetik a Bei der Addition von zwei positiven Binärzahlen kann kein Überlauf stattfinden. b Ausgehend von einer festen Anzahl an Bits ist in der ZweierkomplementDarstellung der Betrag der kleinsten negativen Zahl größer, als der der größten positiven. c Bei Verwendung einer Einerkomplement benötigt man zur Durchführung der Subtraktion ein Subtrahierwerk. d Sei x2 eine 8-stellige Binärzahl. Mit dem Einerkomplement berechnet man die Differenz des Betrags von –x2 und 100000002. e Um n m-stellige Dualzahlen zu addieren reichen m-2 Carry-SelectAddierbausteine aus.

Wahr

Boolesche Algebra a {NAND} ist funktional vollständig. b Es gibt genau fünf verschiedene zweistellige Boolesche Operatoren. c Jede Boolesche Funktion (mit beliebig vielen Stellen) kann mit dem Verfahren von Quine-McCluskey minimiert werden. d Die boolschen Terme A + B * (A + B) + A * (-A + B) und A + B sind äquivalent. e Es gibt maximal 2n verschiedene n-stellige booleschen Funktionen.

Wahr x ? x

Schaltnetze a Alle Schaltkreise in einem Computer können ausschließlich mit NOR-Gattern gebaut werden. b Gegeben sei ein SR-Latch mit der Belegung S=R=0. Setzt man den Eingang S=1, hängt der Zustand von Q von der Belegung von R ab. c Das D-Latch beseitigt den Undeterminismus des SR-Latch. d In einem normalen PLA kann die Und-Ebene einen oder mehrere Addierbausteine enthalten, wenn die zu realisierende Boolesche Funktion in DNF gegeben ist. e Wenn die disjunkte Normalform (DNF) einer n-stelligen Booleschen Funktion ohne Don’t-Care-Argumente aus m Termen besteht, dann besteht die konjunktive Normalform (KNF) dieser Funktion immer aus 2n-m Termen.

Wahr x

1

Falsch

x x x

Falsch x

x

x x x

Falsch

x x Falsch

x x x

?

2. Zweierkomplement (14 Pkt.) a)

Bilden Sie von den Dezimalzahlen x=-73 und y=36 die 8-Bit-Zweierkomplement-Darstellung. x = 10110111 y = 00100100

b) Stellen Sie da, wie die Subtraktion mit Zweierkomplement funktioniert. 2er-Komplement des Subtrahenden bilden und dann mit dem Minuend addieren. c)

Berechnen Sie z=x-y. (Rechenweg) s.o.: -36 = 11011100 10110111 + 11011100 10010011 = - 109

d) Hat bei c ein Overflow stattgefunden? (Begründung) Wenn bei der Addition zweier negativer Zahlen ein negatives Ergebnis folgt, hat kein Überlauf stattgefunden. e)

a=1011 1111 b=0100 0001 Findet bei der Addition der beiden Zweierkomplement-Darstellungen ein Überlauf statt? (Begründung ohne Berechnung) Bei der Addition von einer negativen (a) mit einer positiven Zahl (b) kann kein Überlauf stattfinden.

f)

Geben Sie (-5/16) als IEEE754 an. (Rechenweg) - 5/16 = - 0,0101 = - 1,01 * 2-2 Vorzeichen (31): 1 Expontent (30-23): 01111101 [-2 + 127] Signifikant (22-0): 01 [1 vor dem Komma wird weggelassen] Bit Wert

31 1

30 0

29 1

28 1

27 1

26 1

25 1

24 0

23 1

22 0

21 1

20 0

Bit Wert

15 0

14 0

13 0

12 0

11 0

10 0

9 0

8 0

7 0

6 0

5 0

4 0

2

19 0 3 0

18 0 2 0

17 0 1 0

16 0 0 0

… …

3. boolsche Funktionen durch normiertes PLA (10 Pkt.) a)

Stellen Sie h(a,b,c,d) = (-ab-cd) + (a-d) + (-bc) mittels Identer, Addierer, Multiplizierer und NegatMultiplizierer da. Identer:

Addierer:

y x

x

0

x

y x

1

y 1

Multipl.:

y 1

1

a

3

2

0

b

2

0

3

c

3

0

2

d

2

3

0

0

1

1

1

x

NegatMultipl.:

y 2

x

x

x*y

y 3

x -x*y

h(a,b,c,d)

b) Sei die Schaltfunktion f: Bn -> Bm gegeben. i)

Geben Sie die Anzahl der Zeilen an, die man maximal benötigt, um diese Schaltfunktion durch PLA zu realisieren. (Begründung) n+m [Inputs + Outputs]

ii) Angenommen f liegt in disjunkter Form vor: Wovon hängt die Anzahl der Spalten des entsprechenden PLAs ab? Anzahl der Produktterme.

3

4. Hamming-Code (18 Pkt.) a)

Was ist der Hamming-Abstand und wie groß muss er mindestens sein um d Einzelbitfehler erkennen bzw. korrigieren zu können? Der Hamming-Abstand bezeichnet die Anzahl an unterschiedlichen Stellen zweier Codewörter mit fester (gleicher) Länge. (Anzahl der Bits von einem zum nächsten gültigen Codewort). Zur Erkennung von d Einzelbitfehlern benötigt man lediglich ein einfaches Paritätsbit, der Abstand beträgt also d + 1. Um d Einzelbitfehler korrigieren zu können, ist der Abstand 2d + 1 nötig.

b) Codieren sie das 8-Bit Datenwort 1110 1110 nach Hamming-Verfahren, geben Sie das Codewort an (verwenden Sie dazu gerade Parität) und kennzeichnen Sie die Paritätsbits.

Datenwort Bit 1

0

Bit 2

0

1

1

1

1

1

1

Bit 4

0

1

0

1

0

1

1

0

1

0

1

1

0

1 1

1 0

Bit 8

1

1

1

1

0

Codewort => 0010 1101 1110 c)

Dekodieren Sie folgende 12-Bit-Codewörter. Korrigieren Sie diese wenn möglich. Verwenden Sie gerade Parität. i) 0101 1011 0000

Datenwort Bit 1

0

Bit 2

1

0

1

0

1

0

Bit 4

1

1

0

1

0

1

0

0

1

0

1

Bit 8

0

0

0(1)

0 0

0 0(1)

1

0

0

0

0(1)

0

1

1

1

0

0

1

Datenwort => 0101 0001 ii) 1011 0101 1110

Datenwort Bit 1 Bit 2

1 0

1

0

1

0

1

Bit 4

1

Bit 8

0

1 1

0

1

0

1

4

1 0

1

Datenwort => 1010 1110

1

1

1

1

0

5. Multiplexer (15 Pkt.) a)

0 c

0 M U 2 X 3 1

1 d

a i)

y

b

Geben Sie die Ausgabewerte von y = f(a,b,c,d) für alle möglichen Eingabewerte an: a 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

b 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

c 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

d 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

y 0 0 0 0 0 0 0 1 1 1 1 1 1 0 1 0

ii) Geben Sie y in disjunkter Normalform (DNF) an. -abcd + a-b-c-d + a-b-cd + a-bc-d + a-bcd + ab-c-d + abc-d

b) Gegeben sei y(x1x2x3x4) = -x1x2-x3x4 + -x1-x2-x3x4 + -x1-x2-x3-x4 + x1x2-x3-x4 + x1-x2-x3x4 + x1-x2-x3-x4 + x1x2x3x4 + x1-x2x3-x4 Vereinfachen sie y(x1x2x3x4) mittels Karnaugh-Diagramm. X3x4\x1x2 00 01 11 10

00 x x

01

11 x

x

10 x x

x x

y = -x2-x3 + -x1-x3x4 + x1-x3-x4 + x1x2x3x4 + x1-x2-x4

5

6. Pipeline (13 Pkt.) a)

Benennen und erklären Sie verschiedene Arten von Konflikten (Hazards), die durch die Einführung von Pipelining entstehen können. Geben Sie ein Bsp. für diejenigen Hazards an, die bei der MipsArchitektur auftreten können. strukturelle Hazards, Steuer-Hazards, Daten-Hazards Details siehe Skript S. 200 - 202

b) 5-stufiges Pipelining Ausführungszeit: 2ns pro Stufe; Befehl load word (lw) add Branch (beq)

c)

IF 2ns 2ns 2ns

ID 1ns 1ns 1ns

EX 2ns 2ns 2ns

MEM 2ns -

WB 1ns 1ns -

lw add add

$2, 100 ($5) $3, $3, $4 $1, $4, $5

i)

Geben Sie die Dauer des Programms mit Pipelining an. (5 + 3 -1) * 2ns = 7 * 2ns = 14ns

ii)

Geben Sie die Dauer des Programms ohne Pipelining an. 2ns + 1ns + 2ns + 2ns + 1ns + 2 * (2ns + 1ns + 2ns + 1ns) = 20ns

Delayed Branch Ein Pipeline-Stall soll nach dem Branch-Befehl vermieden werden, die Semantik aber nicht verändert werden. (manipulieren bzw. modifizieren) sw addi add beq

$2, $3, $4, $2,

100 $3, $4, $3,

($3) $4 $2 200

??? sw addi beq add ???

$2, $3, $2, $4,

100 $3, $3, $4,

($3) $4 200 $2

7. Mips – Binomialkoeffizient (30 Pkt.)

Binomialkoeffizient:

a)

Schreiben Sie ein Mips-Assembler-Programm das für n und k den Binomialkoeffizienten auf die Konsole ausgibt. Hinweise: - Nenner und Zähler getrennt, aber in der selben Schleife berechnen; - die Division als letzten Schritt durchführen; - Grenzfälle beachten; z.B.: k=0, n=0; - Fehlermeldung für nn then fail # if k=0 then fail

li li

$t0, 1 $t1, 1

# Temporäres Register für Zähler # Temporäres Register für Nenner

mul sub

$t0, $t0, $s0 $s0, $s0, 1

# Zähler

mul sub bgtz

$t1, $t1, $s1 $s1, $s1, 1 $s1, loop

# Nenner

div

$t2, $t0, $t1

# Ergebnis

li la syscall li move syscall li la syscall

$v0, 4 $a0, ansstr

# Ausgabe Ergebnis

$v0, 1 $a0, $t2 $v0, 4 $a0, newline

exit:

li $v0, 10 syscall

fail:

li $v0, 4 la $a0, failstr syscall j exit

# Fehlerfall

7

b) Eine sehr ineffiziente Art den Binomialkoeffizienten zu berechnen besteht darin, zunächst die drei Fakultätsterme n!, k! und (n-k)! zu berechnen und diese dann der obrigen Formel entsprechend zu kombinieren. Die Fakultätsfunktion fac(n)=n! ist bekanntlich folgendermaßen definiert: Fakultätsfunktion:

Das Mips-Programm, das sich auf dem Din-A3- Bogen befindet, realisiert die rekursive Berechnung der Fakultätsfunktion mit Hilfe des Stacks … Leider liegt mir diese Angabe nicht vor  Tragen Sie den Zustand des Stacks in die Tabelle ein …

8...