Benutzer:Dirk Huenniger/hagen/cs1/ea4

Aufgabe 5a

Bearbeiten

Z4

Aufgabe 5b

Bearbeiten

Z3

Aufgabe 5c

Bearbeiten

 

Aufgabe 5d

Bearbeiten
Z          
  1 1 0 0 1
  0 0 0 X X
  1 1 0 1 0
  0 0 1 X X

Aufgabe 6a

Bearbeiten

 

Die Frage ist nun warum ist das korrekt. Seien   die Bits in MR. Seien   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:  . Der Inhalt von MD die folgende:  , 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   enthällt. Wir müssen die Induktion verankern. Dies tun wir für n=2. Dann muss gelten   ist der Wert von Y. Wir beschränken uns zunächst auf den Fall das es mitdestens ein   mit   gibt. Dann ist die Bedinung MR=0 immer False. Im Falle   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  . Das ist also richtig. Analog ist im Falle   auch   erfüllt. Nun zum Falle das kein solches   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  . Wir sind also zum Zeitpunkt n-1 genau dann in Zustand Z1 wenn   gilt sonst in Z2. Ferner gilt laut Induktionsannahme  . Beim Wechsel von n-1 nach wird also in Abhängigkeit von   die Anweisung y=y+OMD ausgeführt. Wobei OMD den Wert MD aus Takt n-2 hat. Also   mit n-2 Nullen. Damit gilt   zum Zeitpunkt n. Damit ist der Induktionsschritt bewiesen. Damit ist der Beweis abgeschlossen.

Aufgabe 6b

Bearbeiten

 

Aufgabe 6c

Bearbeiten

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

Aufgabe 6d

Bearbeiten

 

 

 

 

Aufgabe 6e

Bearbeiten
Z              
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