Benutzer:Dirk Huenniger/hagen/cs1/ea4

Aufgabe 5a

Z4

Aufgabe 5b

Z3

Aufgabe 5c

Aufgabe 5d

Z	$\mathrm {S_{A}}$	$\mathrm {S_{B}}$	$\mathrm {S_{C}}$	$\mathrm {S_{D}}$	$\mathrm {S_{E}}$
$\mathrm {Z_{1}}$	1	1	0	0	1
$\mathrm {Z_{2}}$	0	0	0	X	X
$\mathrm {Z_{3}}$	1	1	0	1	0
$\mathrm {Z_{4}}$	0	0	1	X	X

Aufgabe 6a

Die Frage ist nun warum ist das korrekt. Seien $r_{0},...,r_{k-1}$ die Bits in MR. Seien $d_{0},...,d_{k-1}$ die Bits in MD. Sei das 0-te bit das niederwertigste. Zur Nummerierung der Takte: Der Zeitpunkt 0 sei der Zeitpunkt bei dem sich das System zum ersten mal nicht in Zustand ist der nicht Zustand 0 ist. Zu zeigen ist folgendes. Ist das System zum ersten mal in Zustand 3 so enthält Y das Produkt der Zahlen die ursrünglich in MR und MD standen. Zum Takt n hat der Inhalt von MR folgende Gestalt: $(r_{n},...,r_{k-1})$. Der Inhalt von MD die folgende: $(0,...,0,d_{0},...,d_{k-1})$, wobei es genau n führende 0 gibt. Für OMD gilt selbiges mit n-1 führenden Nullen. Mit ausnahme von Takt 0 dort ist es undefiniert, wird jedoch auch nicht gelesen. Zu zeigen ist nun das Y zu Takt n gerade den Wert $(r_{0},...,r_{n-2})\cdot (d_{0},...,d_{k-1})$ enthällt. Wir müssen die Induktion verankern. Dies tun wir für n=2. Dann muss gelten $(r_{0})\cdot (d_{0},...,d_{k-1})$ ist der Wert von Y. Wir beschränken uns zunächst auf den Fall das es mitdestens ein $r_{i}=1$ mit $i>0$ gibt. Dann ist die Bedinung MR=0 immer False. Im Falle $r_{1}=0$ wird in Takt 1 Z2 betreten und in Takt 2 in jedem Falle y=y+OMD beim Betreten von Z1 bzw. Z2 oder Z3 ausgeführt. OMD hat zu diesem Zeitpunkt den Wert von MD aus Takt 0. Also gilt $y=\cdot (d_{0},...,d_{k-1})$. Das ist also richtig. Analog ist im Falle $r_{0}=0$ auch $y=0$ erfüllt. Nun zum Falle das kein solches $r_{i}$ existiert. Ist r_0 gleich Null, so wird Z3 in Takt 1 betreten und alles ist richtig. Andernfalls wird. Z3 in Takt 2 betreten und Z2 in Takt 1. Dann wird y=y+OMD beim betreten von Z3 ausgeführt und alls ist in Ordnung. Somit ist die Induktionsverankerung fertig. Sei die Aussage für n-1 schon bewiesen. Wir sind zum Zeitpunkt n-1 in Z1 oder Z2 oder Z3. Anderfalls wären wir vorher fertig geworden und hätte sowiso kein Problem gehabt. Zum Zeitpunkt n-2 waren wir entsprechend entweder in Z1 oder in Z2. Dort wurde MR[0]=0 geprüft und es war $MR=(r_{n-2},...,r_{k-1})$. Wir sind also zum Zeitpunkt n-1 genau dann in Zustand Z1 wenn $r_{n-2}==0$ gilt sonst in Z2. Ferner gilt laut Induktionsannahme $y=(r_{0},...,r_{n-3})\cdot (d_{0},...,d_{k-1})$. Beim Wechsel von n-1 nach wird also in Abhängigkeit von $r_{n-2}$ die Anweisung y=y+OMD ausgeführt. Wobei OMD den Wert MD aus Takt n-2 hat. Also $(0,...,0,d_{0},...,d_{k-1})$ mit n-2 Nullen. Damit gilt $y=(r_{0},...,r_{n-2})\cdot (d_{0},...,d_{k-1})$ zum Zeitpunkt n. Damit ist der Induktionsschritt bewiesen. Damit ist der Beweis abgeschlossen.

Aufgabe 6b

Aufgabe 6c

MR braucht k Bit. MD und Y brauchen 2 mal k Bit.

Aufgabe 6d

$D_{0}={\overline {D_{0}}}\wedge {\overline {D_{1}}}\wedge {\overline {D_{2}}}$

$D_{1}=D_{0}\wedge C_{1}\vee \left({\overline {C_{2}}}\wedge C_{3}\right)\wedge \left(D_{1}\vee D_{2}\right)$

$D_{2}=\left({\overline {C_{2}}}\wedge {\overline {C_{3}}}\right)\wedge \left(D_{1}\vee D_{2}\right)$

$D_{3}=C_{2}\wedge \left(D_{1}\vee D_{2}\right)$

Aufgabe 6e

Z	$\mathrm {S_{A}}$	$\mathrm {S_{B}}$	$\mathrm {S_{C}}$	$\mathrm {S_{D}}$	$\mathrm {S_{E}}$	$\mathrm {S_{U}}$	$\mathrm {S_{Y}}$
0	0	0	0	0	0	1	1
1	1	1	1	X	X	0	0
2	1	1	1	1	X	0	1
3	0	0	0	X	1	1	0