8 Zahlen und Codes

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

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:

• Vorzeichen und Absolutbetrag (engl. sign and magnitude),
• Offset-Dual (engl. offset binary),
• B-Komplement,
• (B-1)-Komplement.
  

Es gilt demnach:

(8.14)

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.

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.

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:

• (B-1)-Komplement:

  ,

  (8.17)

• B-Komplement:

  .

  (8.18)

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:

• Zweierkomplement:

  ,

  (8.19)

• Einerkomplement:

  .

  (8.20)

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	.

Zur Ermittlung des Zweierkomplements C₂ wird am einfachsten zunächst das Einerkomplement C₁ 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.

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

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.

Die beiden Booleschen Funktionen s_i und c_i 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:

b₁)

Dieses Ergebnis ist offensichtlich problemlos darstellbar.

b₂)

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:

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

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ß:

• Einerkomplement:
  Existiert ein "end-around-carry" (eac = "1"), wird "1" zur Zwischensumme addiert.

• Zweierkomplement:
  Ein evtl. auftretendes "end-around-carry" (eac = "1"), wird vernachlässigt.

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:

• Einerkomplement und Zweierkomplement:
  Entspricht das an der Position "n - 1" erzeugte Übertragsbit (carry bit) nicht dem Übertragsbit, das an der Position "n" (s) gebildet wird, liegt eine Fehlersituation vor; es existiert in diesem Fall ein Überlauf (overflow), d.h. das Rechnungsergebnis kann nicht mit der vorgegebenen Informationsbreite dargestellt werden.
  Anschaulich bedeutet diese Regel, daß der Übertragswert, der in die Vorzeichenposition hineintransportiert wird auch wieder heraustransportiert werden muß (carry-in und carry-out an der Position des Vorzeichenbits müssen gleich sein!)

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

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

      6
    - 7

     0110
     1000

     0110
     1001

carry bits:
Zwischensumme:
Ergebnis:

 
 
    - 1

     0000
    01110
     1110

     0000
    01111
     1111

Nein

      6
    - 4

     0110
     1011

     0110
     1100

carry bits:
Zwischensumme:
Korrektur:
Ergebnis:

 
 
         +
    + 2

     1110
    10001
        1
    10010

     1100
    10010
 
     0010

Nein

      6
    + 6

     0110
     0110

     0110
     0110

carry bits:
Zwischensumme:
Ergebnis:

 
 
   (+12)

     0110
    01100
     1100

     0110
    01100
     1100

Ja

    - 7
    - 7

     1000
     1000

     1001
     1001

carry bits:
Zwischensumme:
Korrektur:
Ergebnis:

 
 
         +
   (-14)

     1000
    10000
        1
     0001

     1001
    10010
 
     0010

Ja

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.

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.

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.

Ergebnis:   Quotient Q = 0011₂ = 3₁₀,   Rest R = 1.