Prof. Dr. R. Laue WS9900 Informatik I
Übungsblatt 11
Abgabe: 8.2.00 vor der Vorlesung

URL: /axel/informatik1_ws9900_blatt11.html
Dieses Übungsblatt ist in Zweiergruppen zu bearbeiten. Auf dem Blatt bitte den Übungsgruppentag angeben. Um den Übungsschein zu erhalten, muß man 50% der Punkte erreichen und zweimal erfolgreich eine Aufgabe vorrechnen.

Aufgabe 29 - Wabenmultiplizierer (3+3+5 Punkte)

In der Vorlesung wurde ein Verfahren zur parallelen Multiplikation mit Ergebnistransport von Matrizen vorgestellt. Dazu werden die Bausteine wabenförmig angeordnet. Zeichnen Sie das schematische Netz zur Multiplikation von zwei 3x3 Matrizen (a_ij) und (b_ij). Es ist zu beachten, daß das Netz leicht auf größere Beispiel zu erweitern ist und daß die Eingaben (Matrizen A und B) nur einmal zur Verfügung stehen. (3 Punkte)
Erläutern Sie die Funktionsweise und zeigen Sie wieviele Schritte bei einer Multiplikation von zwei nxn Matrizen nötig sind. (3 Punkte)
Nehmen Sie als ein Beispiel eine 3x3 Matrix, die als Einträge die Ziffern Ihrer Matrikelnummer in zufälliger Reihenfolge und sonst Nullen hat und quadrieren diese mit obigen Netz. Nehmen Sie für jeden Schritt eine Fotokopie Ihres Netzes und tragen Sie die Belegungen der Bausteine ein. (5 Punkte)

Aufgabe 30 - Schul Division (4 Punkte)

Entwerfen Sie ein Schaltwerk, das die Division zweier natürlicher Zahlen nach der Schulmethode implementiert.. Verwenden Sie dazu ein Schieberegister, das den Quotienten aufnimmt und Flip-Flops. Ferner haben Sie einen fertigen Vergleicher und Subtrahierer zur Hand.

Aufgabe 31 - Bitoner Sortierer (3+3 Punkte)

a) Zeichnen Sie das Schaltnetz für den bitonen Sortierer mit 16 Eingängen. (3 Punkte)
b) Sortieren Sie damit das Wort "REFERENCE_MANUAL" in absteigender Reihenfolge. Nehmen Sie dazu eine Fotokopie Ihres Schaltnetzes und tragen SIe die Belegung in den einzelnen Schichten ein. (3 Punkte)