InhaltVorheriges Kapitel Nächstes Kapitel

8 Zahlen und Codes

8.4 Binäre Arithmetik

Arithmetische Operationen folgen in allen polyadischen Zahlensystemen den gleichen Regeln.

Die vom Dezimalsystem her bekannten Vorgehensweisen sollen zunächst auf das Dualsystem angewendet werden. Danach wird eine Ausweitung auf andere Zahlensysteme vorgenommen.

Bei allen arithmetischen Operationen muß davon ausgegangen werden, daß zur Informationsdarstellung nur eine begrenzte Anzahl von Speicherelementen zur Verfügung steht. In der Praxis bedeutet dies, daß nur eine genau definierte maximale "Informationsbreite" möglich ist, die über die Anzahl der realisierten Speicherbits definiert wird:

Informationsbreite
n
· · ·
0
Bit-Nr.
MSB
LSB

Abb. 8.1: Informationsbreite.

Zwei Bitpositionen werden auf Grund ihrer Stellung in der Informationsdarstellung mit besonderen Namen belegt:


Da die Informationsbreite endlich ist, kann numerische Information nur bis zu einem genau vorgegebenen Maximalwert dargestellt werden.
Sollen arithmetische Operationen durchgeführt werden, muß das Bestehen dieser Darstellungsgrenze beachtet werden. Dies führt zu Situationen, die als "Übertrag" (engl. carry) bzw. "Überlauf" (engl. overflow) bezeichnet werden.

Eine weitere Definition, die bei Durchführung arithmetischer Operationen vorgenommen werden muß, ist die des Vorzeichens von Zahlen, so daß

unterschieden werden können.

8.4.1 Darstellung negativer Zahlen

Um negative Zahlen zu definieren, ist die Reservierung einer Binärstelle notwendig.
Gebräuchlich ist die Benutzung des MSB zu diesem Zweck:

s

s = Vorzeichenbit (engl. sign bit)

Für positive Zahlen wird s = 0 gewählt, für negative Zahlen s = 1:

Typ
sign bit
Positive Zahlen
s = 0
Negative Zahlen
s = 1

Tab. 8.4: Definition des Vorzeichenbits.



Positive Zahlen werden damit genauso dargestellt wie Binärzahlen, mit der Einschränkung, daß das MSB nicht "1" werden darf.

Für die Realisierung negativer Zahlen (s = 1) gibt es unterschiedliche Möglichkeiten, von denen drei behandelt werden sollen:



8.4.1.1 Vorzeichen und Absolutbetrag

Kennzeichnend für diese Realisierungsform ist, daß im MSB das Vorzeichen gespeichert wird, während die restlichen Bits den Absolutbetrag der Zahl definieren, also:

s
Absolutbetrag von z

Es gilt demnach:

(8.14)

Zahl
Binärdarstellung
+0
0000 0000
+1
0000 0001
+2
0000 0010
+3
0000 0011
·
·
·
-0
1000 0000
-1
1000 0001
-2
1000 0010
-3
1000 0011
·
·
·

Tab. 8.5: Zahlendarstellung im Format "Vorzeichen und Absolutbetrag"


Diese Zahlendarstellung hat den Vorteil eines sehr einfachen Bildungsgesetzes; sie entspricht vollkommen der Form, in der das Dezimalsystem "manuell" eingesetzt wird.
Die einfache Definition negativer Zahlen ist insbesondere bei der Multiplikation und der Division von Vorteil.
Nachteilig ist, daß bei dieser Repräsentation zwei Darstellungen der Zahl Null möglich sind; es existiert sowohl eine positive als auch eine negative Null.

8.4.1.2 "Offset Binary"-Darstellung (Offset-Dual)

Die "Offset Binary"-Darstellung der Zahlen geht von einer sehr einfachen Unterteilung in positive und negative Werte aus. Eine vorgegebene duale Zahlenskala wird halbiert, der mittlere Wert wird willkürlich als Null definiert. Größere Werte erhalten ein positives Vorzeichen, kleinere entsprechend ein negatives Vorzeichen:

Dezimal
Offset Binary
+7
1111
+6
1110
+5
1101
+4
1100
+3
1011
+2
1010
+1
1001
0
1000
-1
0111
-2
0110
-3
0101
-4
0100
-5
0011
-6
0010
-7
0001
-8
0000

Tab. 8.6: "Offset Binary"




Durch diese Definition wird auch hier das "MSB" als Vorzeichenbit festgelegt. "1" entspricht positiven, "0" negativen Zahlen, im Gegensatz zu den weiteren hier behandelten Vorzeichen-definitionen.
Diese Zahlendarstellung ist bei der Ansteuerung vieler Bausteine von Bedeutung, so z.B. bei Verwendung von Digital-Analog- bzw. Analog-Digital-Umsetzern.


8.4.1.3 Komplement-Darstellung negativer Zahlen

Die oben eingeführte "Vorzeichen und Absolutbetrag"-Darstellung kann auch in elektronischen Systemen eingesetzt werden. Allerdings hat sie den Nachteil, daß zur Durchführung der Addition und der Subtraktion zwei getrennte, unabhängige Recheneinheiten notwendig werden.

Die Komplement-Darstellung der Zahlen hat den Vorteil, daß auch Subtraktionen mit einem Addierwerk ausgeführt werden können; eine spezielle Subtrahiereinheit ist nicht erforderlich.

Zu diesem Zweck wird die durchzuführende Operation zunächst umgeformt:

(8.15)

Der in dieser Gleichung auftretende Ausdruck

(8.16)

wird als Komplement von b bezüglich x bezeichnet.

Anschaulich bedeutet die Operation "Komplement" die Ergänzung auf ein vorgegebenes Ganzes, was in grafischer Form verdeutlicht werden kann:

Abb. 8.2: Komplement-Operation

Gl. 8.15 ist mathematisch sicherlich korrekt. Technisch sinnvoll wird sie erst, wenn für x eine Realisierung gewählt wird, die einerseits die Operation "x - b" einfach durchführen läßt und die andererseits auch die Korrektur "-x" erlaubt, ohne letztendlich doch noch eine Subtraktion durchführen zu müssen.

Ermöglicht wird dies insbesondere durch zwei unterschiedliche Realisierungen von x, was zu zwei wichtigen Komplement-Definitionen führt:

Die Größe n definert wiederum die zur Realisierung zur Verfügung stehende Anzahl von Bitpositionen. B entspricht der Basis des gewählten Zahlensystems.

Im Fall B=2 (Dualsystem) werden die beiden hier eingeführten Komplemente bezeichnet als:





8.4.1.4 Das Einerkomplement (1's complement)

Um das Einerkomplement zu bilden wird gesetzt, d.h. x entspricht der größten Zahl, die mit n Bits darstellbar ist.

Beispiel 8.5:  n = 8

x =
1
1
1
1
1
1
1
1

Mit dieser Wahl von x wird die Bildung des Komplements "x - b" besonders einfach. Da x in allen Bitpositionen eine "1" enthält, kann es bei der Differenzbildung niemals zu einem "Borgen" kommen. Dies bedeutet, daß "x - b" aus b durch stellenweises Invertieren aller Bits entsteht:

.(8.21)

Numerisches Beispiel:

b = 1011 0001
C1(b)= 0100 1110 .

8.4.1.5 Das Zweierkomplement (2's complement)

Im Fall des Zweierkomplements wird gesetzt, d.h. x ist um 1 größer als beim Einerkomplement bzw. die mit n Bits darstellbare Zahl.

Beispiel 8.6:  n = 8

x =
1
0
0
0
0
0
0
0
0

Zur Ermittlung des Zweierkomplements C2 wird am einfachsten zunächst das Einerkomplement C1 gebildet und anschließend der Wert "1" addiert:

.(8.22)

Numerisches Beispiel:

b = 1011 0001
C1(b)=0100 1110
+1
--------------------
C2(b)=0100 1111

Hinweis:

Bei der Bildung des Zweierkomplements muß (wie bei allen numerischen Operationen) die begrenzte Speicherkapazität der vorliegenden Informationseinheit (n Bits) beachtet werden.

8.4.2 Additions- und Subtraktionsoperationen

Die Addition zweier Dualzahlen läuft wie im Dezimalsystem positionsweise ab:

1. Summand
a
         
2. Summand
b
         
------------------------------------------------
Summe
c
         
Position i

Die Addition zweier Bits an der Position i entspricht dem bereits eingeführten Prinzip des Halbaddierers:

bi
ai
si
ci
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1

mit: si = Summenbit
ci = Übertragsbit (engl. carry bit)

Zur vollständigen Addition a + b ist ein Volladdierer notwendig, der auch den Übertrag (carry-in) aus der Addition in der Position i-1 berücksichtigt.

ci-1
bi
ai
si
ci
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

Die beiden Booleschen Funktionen si und ci können beschrieben werden durch:

(8.23)
und.(8.24)

Diese mehrstellige Addition wurde bereits in Kap. 2 als Beispiel einer iterativen Funktionszerlegung vorgestellt.

Beispiel 8.7: Addition von Dualzahlen

a) ohne Berücksichtigung der Informationsbreite:


      3,5010         11,102

    + 2,2510      +  10,012

    _______________________

    = 5,7510      = 101,112



b) mit Berücksichtigung der Informationsbreite:

In diesen Beispielen sollen für die Zahlendarstellung maximal n = 6 Bits reserviert werden:

       
5
0

b1)

1
0
0
1
1
1
+
0
0
1
1
0
0
=
1
1
0
0
1
1
Ergebnis richtig!

Dieses Ergebnis ist offensichtlich problemlos darstellbar.

b2)

1
1
0
1
1
1
+
0
1
0
1
0
0
=
1
0
0
1
0
1
1
Ergebnis falsch!

In diesem Fall würde sich der falsche Ergebniswert "001011" ergeben, da das führende Bit mit dem Wert "1" nicht darstellbar ist. Es entsteht ein sogenannter "Überlauf" (overflow), da die Kapazität der gewählten Zahlenrepräsentation nicht ausreicht, um das Additionsergebnis zu speichern.


Dieses Problem der begrenzten Darstellungsmöglichkeit einer Zahl tritt nicht nur bei der Additionsoperation auf. Auch bei der nachfolgend zu behandelnden Subtraktion muß auf diese Einschränkung geachtet werden.
Da allerdings nicht nach jeder numerischen Rechnung mit Dualzahlen eine Vergleichsrechnung z.B. im Dezimalsystem durchgeführt werden kann, soll ein algorithmischer Weg aufgezeigt werden, über den die Richtigkeit des Ergebnisses überprüft werden kann.

Dieser Algorithmus wird in Form zweier Regeln definiert, die die Addition vorzeichenbehafteter Dualzahlen vollständig definieren und gleichzeitig die gewünschte Überprüfung der Rechnung erlauben.

Die bereits bekannte Definition einer vorzeichenbehafteten Dualzahl wird zu diesem Zweck erweitert:

eac
s
n
n-1
0
s = sign bit
eac = end-around-carry

In dieser Darstellung wird als zusätzliches Bit das "end-around-carry" vorgesehen. Dieses Bit existiert nicht als realer Bestandteil zur Informationsspeicherung, es dient dem Additionsalgorithmus lediglich als Hilfsbit.

Außerdem wird das bei jeder Additionsoperation (siehe Halbaddierer) auftretende Übertragsbit (carry bit) weiter unterschieden in

"carry-in" und "carry-out":

Abb. 8.3: Übertragsverhalten im Vorzeichenbit




Regel 8.1: Additionsregel

Diese Regel zeigt, wie das "end-around-carry"-bit behandelt wird, wobei zwischen Einer- und Zweierkomplement unterschieden werden muß:



Regel 8.2: Ergebniskontrolle

Diese Regel zeigt, wie während der Addition das Ergebnis auf Richtigkeit überprüft werden kann; sie gilt gleichermaßen für Einer- und Zweierkomplementdarstellung:



Die hier aufgestellten Regeln sollen an einfachen Beispielen erläutert werden. Es wird n = 4 gewählt:

s
   
4
3
2
1

Die Subtraktion zweier Dualzahlen wird unter Verwendung des Einer- bzw. Zweierkomplementes nach Gl. 8.15 auf die Addition zurückgeführt.


Dezimal
Einerkompl.
Zweierkompl.
Fehler
Beispiel 8:
      6
- 7
     0110
1000
     0110
1001
carry bits:
Zwischensumme:
Ergebnis:
 
 
- 1
     0000
01110
1110
     0000
01111
1111


Nein
Beispiel 9:
      6
- 4
     0110
1011
     0110
1100
carry bits:
Zwischensumme:
Korrektur:
Ergebnis:
 
 
+
+ 2
     1110
10001
1
10010
     1100
10010
 
0010


Nein
Beispiel 10:
      6
+ 6
     0110
0110
     0110
0110
carry bits:
Zwischensumme:
Ergebnis:
 
 
(+12)
     0110
01100
1100
     0110
01100
1100


Ja
Beispiel 11:
    - 7
- 7
     1000
1000
     1001
1001
carry bits:
Zwischensumme:
Korrektur:
Ergebnis:
 
 
+
(-14)
     1000
10000
1
0001
     1001
10010
 
0010


Ja

Tab. 8.7: Beispiele dualer Addition und Subtraktion

An den Beipielen 10 und 11 ist ersichtlich, daß die in obiger Regel 2 geforderte Bedingung nicht erfüllt wird (carry-in und carry-out unterscheiden sich im Vorzeichenbit). Die Ergebnisse sind also falsch.
Offensichtlich sind die zu erwartenden Ergebniswerte (+12 bzw. -14) nicht mehr in einer 4-Bit-Darstellung realisierbar.


8.4.3 Multiplikation und Division von Dualzahlen

Die Multiplikation und Division von Dualzahlen geschieht wie im Dezimalsystem schrittweise.

8.4.3.1 Multiplikation von Dualzahlen

Zum Multiplizieren werden die Dualzahlen positionsweise multipliziert, die stellenverschobenen Zwischenwerte werden addiert. Allerdings ist die Multiplikation im Dualsystem wesentlich einfacher als im Dezimalsystem, da nur Multiplikationen mit den Werten "0" oder "1" auftreten. Der stellenverschobene Multiplikand muß also nur wiederholt addiert werden.

Der dualen Multiplikation liegt die folgende Multiplikationstabelle zu Grunde (das "Kleine Einmaleins" des Dualsystems):

b
a
a*b
0
0
0
0
1
0
1
0
0
1
1
1

Tab. 8.8: Duale Multiplikation.

Das Resultat der Produktbildung entspricht also dem von der UND-Funktion her bekannten Ergebnis:

a * b
a AND b
.

Bei der Multiplikation wird für das Ergebnis ein erhöhter Speicherbedarf benötigt. Sind Multiplikand und Multiplikator n-stellig, kann für das Produkt P abgeschätzt werden:

.

Zur Speicherung von P sind also 2n Bits vorzusehen, doppelt soviel wie für die einzelnen Faktoren.

Beispiel 8.12: Multiplikation von Dualzahlen


        10100 * 1011

        ____________

          101000

        +   10100

        +    10100

        ____________

          11011100

        ____________


Bei diesem Verfahren kann natürlich in gleicher Form von rechts nach links vorgegangen werden.



8.4.3.2 Multiplikationsalgorithmen

Um die Multiplikation technisch zu realisieren, ist ein genau definierter Algorithmus notwendig, der auch die existierenden Randbedingungen berücksichtigt, wie z.B. die Informationsbreite des Rechenwerks (speziell des Addierers).

Das oben beschriebene "Standardverfahren" ist auch zur Rechneranwendung geeignet, hat aber den Nachteil, daß ein 2n-stelliger Addierer notwendig ist, obwohl in den einzelen Schritten jeweils nur n Stellen addiert werden. Ein zweites Verfahren mit festem, reduziertem Additionsbereich vermeidet diesen Nachteil und soll deshalb ebenfalls untersucht werden.


Standard-Multiplikationsverfahren:

Seien x und y ein n-stelliger Multiplikand bzw. Multiplikator, so daß y durch ein n-stelliges Polynom beschrieben werden kann:

(8.25)

dann ergibt sich für das Produkt P:

also: (8.26)

Gl. 8.26 kann als Iterationsvorschrift aufgefaßt werden, die notwendige Addition kann schrittweise durchgeführt werden (hier von rechts nach links):

und
.(8.25)


Beispiel 8.13: x = 910 = 10012, y = 610 = 01102


i
Pi
yi
0
 
    0000 0000
+ 0
0110
 
1
 
  = 0000 0000
+ 1 001
0110
 
2
 
  = 0001 0010
+ 10 01
0110
 
3
 
  = 0011 0110
+ 0
0110
 

 
P
  = 0011 0110

  = 5410

Bei diesem Verfahren ist also ein 2n-stelliger Addierer notwendig.

Verfahren mit festem Additionsbereich:

Das beim Standardverfahren auftretende Verschieben des Additionsbereiches kann vermieden werden, wenn für die Multiplikation Gl. 8.26 wiederum nach dem Hornerschema vorgegangen wird:

(8.27)

Iterativ formuliert folgt hieraus:

und
.

In jedem Iterationsschritt kann zwar ein Überlauf in das (n+1)­Bit entstehen, aber der Bereich wird durch die anschließende Rechtsverschiebung (Multiplikation mit 0,5) wieder justiert.

Hinweis 1:

Dieses Verfahren mit festem Additionsbereich beschränkt zwar die Addition auf n Bits, es wird aber auch die Genauigkeit des Ergebnisses auf n Bits reduziert, während das Standardverfahren die volle Genauigkeit von 2n Bits beibehält.

Hinweis 2 :

Beide Multiplikationsverfahren setzen vorzeichenlose Zahlen voraus. Es existieren andere Algorithmen, um auch vorzeichenbehaftete Zahlen (z.B. in Zweierkomplement-Darstellung) zu verarbeiten.



8.4.3.3 Division von Dualzahlen

Die Division von Dualzahlen erfolgt in ähnlicher Weise durch sukzessives Subtrahieren des Divisors. Diese Subtraktion kann unter Umständen durch eine Addition im Einer- oder Zweierkomplement ersetzt werden.

Auch hier gilt, daß auf Grund der dualen Teilmultiplikationen die Rechnung einfacher ausführbar wird.

Beispiel 8.14: Division von Dualzahlen


        11011100 : 10100 = 1011

      - 10100

      ----------

          11110

      -   10100

      ----------

           10100

      -    10100

      ----------

           00000



8.4.3.4 Divisionsalgorithmen

Bei der Division Q = x/y werden schrittweise durch Abschätzen die Koeffizienten des Quotienten Q bestimmt. Der auftretende Rest R wird anschließend zur Überprüfung untersucht:

mit R = Rest. (8.28)

Dieser Rest R kann auch hier mit Hilfe des Hornerschemas iterativ ermittelt werden. Es folgt aus Gl. 8.28:


Daraus ergeben sich die Iterationsschritte:

Für die Koeffizienten des Quotienten ergibt sich:

wenn dann:
sonst:.




Beispiel 8.15: Dividend: x = 13, Divisor: y = 4
n = 4:

i
ri
24
23
22
21
20
2-1
2-2
2-3
2-4
qi
y =
1
0
0
0
4

1
1
0
1

1
1
0
1
0
3

1
1
0
1

1
1
0
1
0
2

1
1
0
1

1
1
0
1
1

-
1
0
0
0
1

0
1
0
1

0
1
0
1
1

-
0
1
0
0
Rest =
1
Quotient =
0
0
1
1
=310


Ergebnis:   Quotient Q = 00112 = 310,   Rest R = 1.




InhaltVorheriges Kapitel Nächstes Kapitel