Binäre Arithmetik
Hier geht es um das Rechnen im Binärsystem:
- Binäre Addition
- Binäre Multiplikation
Wir beginnen mit dem uns vertrauten Dezimalsystem, schauen uns an, wie wir vorgehen, übertragen das auf das Binärsystem und stellen fest, dass es einfacher ist als im Dezimalsystem.
Wir haben auswendig gelernt, was herauskommt, wenn wir zwei einstellige Zahlen addieren oder multiplizieren: das kleine Ein-Mal-Eins. Im Grunde genommen haben wir eine Tabelle gelernt.
| a | b | plus | mal |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 0 | 9 | 9 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 2 | 1 |
| 7 | 8 | 15 | 56 |
| 8 | 9 | 17 | 72 |
| 7 | 10 | 17 | 70 |
Tabelle 1: Ausschnitt aus dem dezimalen Ein-Mal-Eins
Wir haben eine Tabelle mit zwei mal 10 mal 10, also 2*100=200 Einträgen erlernt.
Nun stellen wir das binäre Ein-Mal-Eins auf:
| a | b | plus | mal |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 10 | 1 |
Tabelle 2: Das binäre Ein-Mal-Eins
Das binäre Ein-Mal-Eins umfasst nur zwei mal 2 mal 2, also 2*4=8 Einträge.
Das hexadezimale Ein-Mal-Eins ist eine Tabelle mit zwei mal 16 mal 16, also 2*256=512 Einträgen.
Binäre Addition
Wir konzentrieren uns hier auf die Addition von mehrstelligen Binärzahlen.
dezimal
35
+ 68
Übertrag 11
----
103
Wir haben den Übertrag aus der Tabelle 1 verwendet.
binär
101
+ 11
Übertrag 11
-----
100
Hier haben wir den Übertrag aus der Tabelle 2 verwendet.
Aber den Übertrag müssen wir uns genauer ansehen.
binär
101
+ 111
Übertrag 11
-----
1100
Was bedeutet die Addition der drei Einsen in der ersten Spalte?
Wir müssen das binäre Ein-Mal-Eins um die Überträge erweitern:
| Cin | a | b | plus | Cout |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Tabelle 3: Das binäre Ein-Mal-Eins mit Übertrag C
Tabelle 3 ist nichts anderes als eine Wahrheitstabelle für die binäre Addition. Wir haben drei Eingänge: die beiden Summanden a und b sowie den Übertrag Cin von der vorhergehenden Stelle.
Wir müssen die Logik für den Ausgang plus und die Logik für den Ausgang Cout bestimmen. Ein Logikbaustein, der Tabelle 3 realisiert, wird Volladdierer genannt.
Bild 1 zeigt einen 1-Bit-Halbaddierer und einen 1-Bit-Volladdierer. Nur Volladdierer verarbeiten einen eingehenden Übertrag. Die Addition eines Bits entspricht der Exklusiv-ODER-Verknüpfung.
Um zwei Binärzahlen mit n Bits zu addieren, werden n Volladdierer benötigt.
Bild 2 zeigt einen 4-Bit-Volladdierer. Zwei Binärzahlen A und B werden zu S addiert. Es gibt einen Überlauf-Eingang und einen Überlauf-Ausgang.
Die Geschwindigkeit des 4-Bit-Volladdierers hängt insbesondere von der Berechnung des Überlaufs ab. Moderne 4-Bit-Volladdierer enthalten daher eine Logik, die den Überlauf parallel aus allen acht Eingängen und Cin erzeugt. Diese Logik wird als Cary-Look-Ahead bezeichnet.
Negative Binärzahlen
Negative Zahlen werden durch ein vorangestelltes Minuszeichen gekennzeichnet. Im Binärsystem handelt es sich dabei einfach um ein vorangestelltes Bit:
- Ist das erste Bit 0, handelt es sich um eine positive Zahl.
- Ist das erste Bit 1, handelt es sich um eine negative Zahl.
Leider ist das negative Bitmuster einer Binärzahl nicht einfach das Bitmuster einer positiven Binärzahl mit einer 1 davor.
Wir wissen, dass 3 + -3 = 0 ist.
Wir fragen uns, welches Bitmuster wir zu 0011 addieren müssen, um 0 zu erhalten. Wir probieren es einfach aus. Es funktioniert nur mit Übertrag:
0011 + 1101 ------- 10000
Das Ergebnis ist eine negative 0. Wir vergessen einfach den Übertrag 
Wir erhalten -310 = -0112 = 11012.
Eine Binärzahl wird negiert, indem wir ihr Bitmuster invertieren und dann eine 1 addieren.
0011
invertiert: 1100
+1 1101
Das funktioniert auch mit 0
0000
invertiert: 1111
+1 10000
und für negative Zahlen:
1101
invertiert: 0010
+1 0011
Wir messen nach:
Die Schaltung in Bild 4 können wir verwenden, um die Wirkung der binären Addition zu untersuchen. Mit ihr können auch negative Zahlen addiert werden.
Fazit:
- Das erste Bit links kann als Vorzeichen betrachtet werden.
- Das Bitmuster einer Binärzahl ist nicht ganz einfach zu bilden.
- Die Addition negativer Binärzahlen ist mit der Addition positiver Binärzahlen kompatibel.
Binäre Multiplikation
Die Logik für die Multiplikation von zwei Bits a, b ist einfach a AND b, nur wenn a und b 1 sind, ist a*b=1.
Die Multiplikation von Dezimalzahlen mit Bleistift und Papier ist etwas komplizierter als die Addition. Das Gleiche gilt auch für Binärzahlen.
dezimal
45 * 67
-------
35
28
30
24
-------
3015
Wir multiplizieren jede Ziffer der rechten Zahl mit jeder Ziffer der linken Zahl, verschieben das Ergebnis um eine Stelle nach links und addieren dann alles zusammen.
Das Ergebnis hat so viele Stellen wie die beiden Multiplikanden zusammen. Im obigen Beispiel mit zwei zweistelligen Multiplikanden ist das Ergebnis vierstellig.
Einfacher ist es, wenn der Multiplikator nur 0en und 1en enthält:
45 * 1101
--------
45
00
45
45
--------
49545
Wir brauchen nur den nach links verschobenen Multiplikanden oder 0 zu addieren.
Das ist wie bei der binären Multiplikation.
binär 3 * 5 = 15
1011 * 1101
-----------
+ 0011
+ 0000
+ 0011
+ 0000
-----------
0001111
Hier ist es etwas einfacher. Wir multiplizieren jede Ziffer der rechten Zahl mit der linken Zahl, verschieben das Ergebnis um eine Stelle nach links und addieren dann alles zusammen.
Wir brauchen die Ziffern nicht einzeln zu multiplizieren.
- Wenn die rechte Ziffer 0 ist, schreiben wir 0000 hin und
- wenn die rechte Ziffer 1 ist, schreiben wir die rechte Zahl hin.
- Im Prinzip handelt es sich um eine Multiplikation von n Bits mit einem Bit.
Das Ergebnis enthält so viele Bits wie die beiden Multiplikanden zusammen.
Im obigen Beispiel sind es nur 7, aber bei
dezimal: 14 * 11 = 154 binär: 1110 * 1011 = 10011010
sind es 8 Bits.
Wir haben eine Folge von Additionen und Linksverschiebungen.
Bei Dezimalzahlen führt eine Linksverschiebung zu einer Multiplikation mit 10, bei Binärzahlen zu einer Multiplikation mit 2.
Wenn wir eine binäre Multiplikation von längeren Zahlen in einem Durchgang, in einem Takt, durchführen wollen, brauchen wir eine ganze Reihe von Addierern, die zum Teil verschoben miteinander verknüpft sind. Und natürlich eine Logik, die entscheidet, ob die linke Zahl addiert wird oder 0.
Wir können die Multiplikation auch seriell in mehreren Takten durchführen. Dann brauchen wir
- ein Schieberegister für den Multiplikanden,
- ein Schieberegister für den Multiplikator,
- doppelt so breites Schieberegister für das Ergebnis,
- einen Addierer und
- einen Multiplizierer mit einem Bit.
Der Multiplizierer multipliziert n Bits mit einem Bit und ist nichts anderes als n AND-Gatter.
Wir brauchen noch einen Controller, der die Durchführung der Multiplikationen, der Additionen und die Schieberegister steuert.
Das ist ziemlich komplex.
- Eine Multiplikation ist sehr aufwendig.
- Eine binäre Multiplikation mit 2 kann einfach mit einem Schieberegister realisiert werden.