URL:        /axel/informatik1_ws0001_blatt7.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 21 - Quine McCluskey - (6 Punkte)

f(a,b,c,d) := 1 falls 2b+3a > 3d+2c
f(a,b,c,d) := 0 sonst

Stellen Sie die Wertetabelle auf und wenden Sie das Verfahren von Quine Mc Cluskey an. Verkürzen Sie weiter um ein möglichst kurzes realisierendes Schaltnetz zu erhalten. Zeichnen Sie dieses.

Aufgabe 22 - Länge eines Boole'schen Ausdrucks - (4 Punkte)

Ein Booolescher Ausdruck aus n Variablen wird aufgebaut aus den Konstanten 1,0 den Verknüpfungen + ,* den Variablen x₁,...x_n und Klammern. Die Länge l eines Ausdrucks wird rekursiv definiert:

l(0) = l(1) = l(x₁) = .... = l(x_n) = 1
Seien a und b Boole'sche Terme:
l(a+b) = l(a) + l(b) +1
l(a*b) = l(a)+l(b)+1
l(  (a)   ) = l(a)+2

Wieviele Boole'sche Terme gibt es mit n=4 und einer Länge von 4?

Aufgabe 23 - Quersumme - ( 4+2 Punkte)
 

Man entwerfe ein mehrstufiges Schaltnetz aus Volladdierern und Halbaddierern zur Berechnung der Anzahl der Einsen einer 16-stelligen Dualzahl.
Verallgemeinern Sie Ihr Schaltnetz für längere Eingaben. Wie steigt der Aufwand an Schaltelementen?