Lösungen

Lösungen

Aufgabe: Logische Operationen programmieren

Wir können alle Funktionen mit Hilfe einer einzigen bedingten Verzweigung definieren.

def nicht(x):
    if x:
        return False
    else:
        return True

def und(x, y):
    if x:
        return y
    else:
        return False

def oder(x, y):
    if x:
        return True
    else:
        return y

Hier sind alternative Definitionen mit optionalen Anweisungen (ohne else-Zweig):

def nicht1(x):
    if x:
        return False
    return True

def und1(x, y):
    if x:
        if y:
            return True
    return False

def oder1(x, y):
    if nicht(x):
        if nicht(y):
            return False
    return True

Die und- und oder- Funktionen können wir mit Hilfe der De Morganschen Gesetze auch mit Hilfe der jeweils anderen Operation ausdrücken.

def und2(x, y):
    return nicht(oder(nicht(x), nicht(y)))

def oder2(x, y):
    return nicht(und(nicht(x), nicht(y)))

Aufgabe: Binärzahlen konvertieren

def decimal(b):
    n = 0
    for i in range(0, len(b)):
        n = n + 2**i * int(b[len(b)-i-1])
    return n

Aufgabe: 2-zu-1 Multiplexer definieren

Wenn x Null ist, hat der Ausgang out des gesuchten Bauteils den selben Wert wie der Eingang a; wenn x Eins ist, hat out den selben Wert wie b.

Dieses Verhalten wird auch durch die Gleichung out = (not x and a) or (x and b) beschrieben: Der Ausgang out ist genau dann gesetzt, wenn x nicht gesetzt ist und a gesetzt ist oder wenn x und b beide gesetzt sind.

Die folgende Implementierung des 2MUX1-Gatters, setzt diese Formel als Hardware-Beschreibung um.

2MUX1(x,a,b;out):
  NOT(x;y)
  AND(y,a;c)
  AND(x,b;d)
  OR(c,d;out)

Die Eingänge sind in den Parameterlisten von den Ausgängen durch ein Semikolon getrennt.

Da das NOT-Gatter ein NAND-Gatter enthält, das AND-Gatter zwei und das OR-Gatter drei, besteht der so definierte Multiplexer insgesamt aus acht NAND-Gattern.

Aufgabe: Volladdierer definieren

Die Verknüpfungstabelle eines ADD-Gatters zur Addition der Eingänge a, b und cin (für input carry) mit den Ausgängen sum und cout (für output carry) sieht wie folgt aus.

Der Summen-Ausgang sum ergibt sich dabei als Summe der drei Eingänge, die nacheinander mit zwei Halbaddierern berechnet werden kann. Der Übertrags-Ausgang cout ist genau dann gesetzt, wenn bei (mindestens) einer dieser Additionen ein Übertrag auftritt. Wir können ihn also mit einem OR-Gatter aus den beiden Überträgen der Halbaddierer berechnen.

Die folgende Implementierung des ADD-Gatters implementiert diese Idee.

ADD(a,b,cin;sum,cout):
  HADD(a,b;s1,c1)
  HADD(s1,cin;sum,c2)
  OR(c1,c2;cout)

Zur Addition von \(n$-stelligen Binärzahlen können nun $n\) so definierte ADD-Gatter hintereinander geschaltet werden.

Bonusaufgabe: Rechenwerk simulieren

Diese Lösung beschreibt das Rechnewerk mit Hilfe unserer Hardware-Beschreibungs-Sprache.

Die folgenden Definitionen fassen logische Gatter zusammen, die wir zur Definition des Rechenwerks verwenden werden. Alle gezeigten Gatter werden wir auch so verwenden, dass statt Bits Busse als Argumente verwendet werden. Das ist so zu verstehen, dass die einzelnen Bits komponentenweise (entsprechend ihres Index im Reißverschlussverfahren) verknüpft werden. Zusätzlich werden wir eine Variante OR(ins;out) des OR-Gatters verwenden, bei dem das out-Bit die Oder-Verknüpfung aller Bits des Busses ins darstellt.

NOT(a;out):
  NAND(a,a;out)

AND(a,b;out):
  NAND(a,b;c)
  NOT(c;out)

OR(a,b;out):
  NOT(a;x)
  NOT(b;y)
  NAND(x,y;out)

XOR(a,b;out):
  NAND(a,b;x)
  NAND(a,x;y)
  NAND(b,x;z)
  NAND(y,z;out)

MUX(a,b,sel;out):
  NOT(sel;nsel)
  AND(nsel,a;u)
  AND(sel,b;v)
  OR(u,v;out)

Die folgenden Definitionen fassen arithmetische Schaltnetze zusammen, die wir verwenden werden. Zusätzlich werden wir ein Schaltnetz ADD(as,bs;outs) verwenden, das auf Basis des Voll-Addierers FADD definiert werden kann, mit dem die als Bus gleicher Größe dargestellten Argumente verknüpft werden, wobei das letzte Übertragsbit ignoriert wird.

HADD(a,b,;sum,carry):
  XOR(a,b;sum)
  AND(a,b;carry)

FADD(a,b,cin;sum,cout):
  HADD(a,b,;s,c1)
  HADD(s,cin;sum,c2)
  OR(c1,c2;cout)

Auf Basis dieser Definitionen können wir nun das Rechenwerk definieren. Es kombiniert die (Mehrbit-) Eingangssignale x und y zum (Mehrbit-) Ausgangssignal out. Welche Operation ausgeführt werden soll, wird durch die folgenden zusätzlichen Eingangssignale bestimmt:

• zx (zero x) zeigt an, ob statt x ein Nullsignal verwendet werden soll.
• nx (negate x) zeigt an, ob x (bitweise) negiert werden soll.
• zy und ny zeigen entsprechende Operationen auf dem Eingang y an.
• f (function) zeigt an, ob die so entstehenden Signale durch Konjunktion oder Addition verknüpft werden sollen.
• no (negate output) zeigt an, ob der Ausgang (bitweise) negiert werden soll.

Die zusätzlichen Ausgänge zr (zero) und ng (negative) des Rechenwerks zeigen an, ob das Ergebnis Null oder negativ ist. Zur verwendeten Binärdarstellung negativer Zahlen empfliehlt sich die Lektüre des in der Aufgabenstellung angesprochenen Kapitels zu Arithmetischen Schaltkreisen.

Der Bus zero besteht aus Null-Bits. Die Schreibweise bus[i] steht für das i-te Bit des Busses bus.

ALU(x,y,zx,nx,zy,ny,f,no;out,zr,ng):
  # The zx and zy bits determine whether the corresponding inprint are zeroed.
  MUX(x,zero,zx;x_zero)
  MUX(y,zero,zy;y_zero)
  
  # The nx and ny bits determine whether inprint are bitwise negated.
  NOT(x_zero;x_not)
  NOT(y_zero;y_not)
  MUX(x_zero,x_not,nx;x_mod)
  MUX(y_zero,y_not,ny;y_mod)

  # The ALU combines (possibly modified) inprint using conjunction or addition.
  AND(x_mod,y_mod;out_and)
  ADD(x_mod,y_mod;out_add)
  MUX(out_and,out_add,f;o)
  
  # The output is bitwise negated if the no bit is set.
  NOT(o;o_not)
  MUX(o,o_not,no;out)
  
  # The zr output bit is set if the output is zero.
  OR(out;nzr)
  NOT(nzr;zr)
  
  # The ng output bit is set if the output is negative.
  AND(out[0],out[0],ng)