Dualsystem

Das Dualsystem (lat. dualis = zwei enthaltend), auch Binärsystem oder Zweiersystem genannt, ist ein Zahlensystem, welches nur zwei Ziffern zur Darstellung von Zahlen benutzt. Es wurde von Gottfried Wilhelm Leibniz erfunden und erlebte mit der Entwicklung der Digitaltechnik eine starke Verbreitung. Auf Grund dessen ist es das bekannteste und wichtigste Zahlensystem neben dem gewöhnlich benutzten Dezimalsystem

Das Dualsystem ist ein Stellenwertsystem mit der Basis 2, also die dyadische (2-adische) Darstellung von Zahlen (Dyadik). Die zwei Ziffern mit den Werten Null und Eins werden oft mit den Symbolen 0 und 1 dargestellt. Alle Zahlen werden als Folge von 0 und 1 dargestellt. Die 8 (acht) im Zehnersystem entspricht beispielsweise der 1000 im Dualsystem.

In älterer Literatur mit Bezug zur elektronischen Datenverarbeitung werden manchmal die Symbole Low (L) und High (H) anstelle von 0 und 1 verwendet. Low steht dann meist für den Wert Null und High für den Wert Eins. Diese Zuordnung nennt sich positive Logik, bei negativer Logik werden die Werte andersherum zugeordnet.

Die Zahlen, die durch das Dualsystem dargestellt werden, heißen Dualzahlen oder Binärzahlen, wobei letzteres auch einfach für binärcodierte Zahlen stehen kann. Die Darstellungsweise einer Zahl ist durch den Begriff Binärzahl, bis auf die Anzahl der verwendeten Ziffernsymbole (zwei), also nicht näher spezifiziert.

Geschichte

Der alt-indische Mathematiker Pingala stellte die erste bekannte Beschreibung eines Zahlensystems bestehend aus zwei Zeichen im 3. Jahrhundert v. Chr. vor. Dieses Zahlensystem kannte allerdings keine Null.

Eine Serie von acht Trigrammen und 64 Hexagrammen sind aus dem alt-chinesischen und daoistischen Text I Ching bekannt. Der chinesische Gelehrte und Philosoph Shao Yung entwickelte im 11. Jahrhundert eine geordnete Anordnung von Hexagrammen, die die Folge von 0 bis 63 darstellt und eine Methode, um dieselbe zu erzeugen. Es gibt jedoch keine Hinweise, dass Shao es verstand, Berechnungen im Dualsystem vorzunehmen oder das Konzept des Stellenwertes erkannt zu haben.

Leibniz binary_system_1703.png Das Dualsystem, also das Stellenwertsystem mit der Basis Zwei, wurde von Gottfried Wilhelm Leibniz am Anfang des 18. Jahrhunderts in seinem Artikel Explication de l'Arithmétique Binaire vollständig dokumentiert. Leibniz bestätigt darin die Ansicht Joachim Bouvets, eines Missionars am chinesischen Kaiserhof, der die Tri- und Hexagramme („Zeichen des Fu Hsi“, Leibniz_Fu_Hsi_1703.png) bei bestimmter Leserichtung als Zahlzeichen interpretiert hat, und sieht darin ein archaisches Binärsystem, das in Vergessenheit geraten ist. Diese Deutung gilt inzwischen als sehr unwahrscheinlich.

1854 veröffentlichte der britische Mathematiker George Boole eine richtungsweisende Arbeit, die detailliert ein logisches System beschreibt, das als Boolesche Algebra bekannt wurde. Sein logisches System bereitete der Realisierung von elektronischen Schaltkreisen den Weg, welche Arithmetik im Dualsystem implementieren.

1937 fertigte Claude Shannon seine Magisterarbeit am MIT an, die erstmals die Boolsche Algebra und die Arithmetik im Dualsystem in elektronischen Relais und Schaltern realisierte. Unter dem Titel „A Symbolic Analysis of Relay and Switching Circuits“ hat Shannons Arbeit die Konstruktion digitaler Schaltkreise begründet.

Im November 1937 vollendete George Stibitz, der später bei den Bell Labs arbeitete, seinen Relais-gestützten Rechner „Modell K“ (nach „K“ für „Küche“, wo er ihn zusammengebaut hat), der die Addition im Dualsystem beherrschte.

Definition und Darstellung

Eine Dualzahl wird durch die Ziffern z_i dargestellt. Die Ziffern werden wie im gewöhnlich verwendeten Dezimalsystem ohne Trennzeichen hintereinander geschrieben, ihr Stellenwert entspricht allerdings der zur Stelle passenden Zweierpotenz und nicht der Zehnerpotenz.

Es wird also die höchstwertige Stelle mit dem Wert z_m ganz links und die niederwertigeren Stellen mit den Werten z_m-1 bis z₀ in absteigender Reihenfolge rechts davon aufgeschrieben. Zur Darstellung von rationalen oder reellen Zahlen folgen dann nach einem trennenden Komma die Stellen z_-1 bis z_-n, die den gebrochenen Anteil der Zahl darstellen:

z_m z_{m-1} \ldots z_0\operatorname{,}z_{-1} z_{-2} \ldots z_{-n}

\qquad \left(m,n\in\mathbb{N} \quad z_i\in\{0,1\}\right)

Der Wert Z der Dualzahl ergibt sich durch Addition dieser Ziffern, welche vorher jeweils mit ihrem Stellenwert 2ⁱ multipliziert werden:

Z = \sum_{i=-n}^m z_i \cdot 2^i

Beispiel

Die Ziffernfolge 1101 zum Beispiel, stellt nicht (wie im Dezimalsystem) die Tausendeinhundertundeins dar, sondern die Dreizehn, denn im Dualsystem berechnet sich der Wert durch

= 1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 = [13_{10}

und nicht wie im Dezimalsystem durch

1 \cdot 10^3 + 1 \cdot 10^2 + 0 \cdot 10^1 + 1 \cdot 10^0 = ^*_{10} .

Die Klammerung der Resultate mit der tiefgestellten 2 beziehungsweise der 10 gibt die Basis des verwendeten Stellenwertsystems an. So kann leicht erkannt werden, ob die Zahl im Dual- oder im Dezimalsystem dargestellt ist. In der Literatur werden die eckigen Klammern oft weggelassen und die tiefergestellte Zahl wird dann manchmal in runde Klammern gesetzt. Ebenfalls möglich ist die Kennzeichnung durch den nachgestellten Großbuchstaben B (für binär).

Anwendung

Die Dyadik (dyo, griech. = Zwei), also die Darstellung von Zahlen im Dualsystem wurde schon Ende des 17. Jahrhunderts von Leibniz entwickelt. Er sah darin ein so überzeugendes Sinnbild des christlichen Glaubens, dass er damit den chinesischen Kaiser Kangxi überzeugen wollte. Dazu schrieb er an den französischen Jesuitenpater Bouvet, der als Missionar in China tätig war:

"Zu Beginn des ersten Tages war die 1, das heißt Gott. Zu Beginn des zweiten Tages die 2, denn Himmel und Erde wurden während des ersten geschaffen. Schließlich zu Beginn des siebenten Tages war schon alles da; deshalb ist der letzte Tag der vollkommenste und der Sabbat, denn an ihm ist alles geschaffen und erfüllt, und deshalb schreibt sich die 7 111, also ohne Null. Und nur wenn man die Zahlen bloß mit 0 und 1 schreibt, erkennt man die Vollkommenheit des siebenten Tages, der als heilig gilt, und von dem noch bemerkenswert ist, daß seine Charaktere einen Bezug zur Dreifaltigkeit haben."

Da die feinmechanischen Fertigkeiten der damaligen Zeit nicht ausreichten, musste Leibniz beim Bau seiner Rechenmaschinen auf das Dezimalsystem zurückgreifen.

Bei der späteren Entwicklung von elektronischen Rechenmaschinen erlangte das Dualsystem allerdings große Bedeutung, denn in der Digitaltechnik werden Zahlen durch elektrische Zustände dargestellt. Bevorzugt werden zwei komplementäre Zustände wie Strom an/Strom aus oder Spannung/Masse verwendet, da auf diese Weise sehr fehlerresistente und einfache Schaltungen zu realisieren sind (siehe Binärcode). Diese zwei Zustände lassen sich dann als Ziffern benutzen. Das Dualsystem ist die unkomplizierteste Methode mit Zahlen zu rechnen, die durch diese zwei Ziffern dargestellt werden.

Dualzahlen finden in der elektronischen Datenverarbeitung bei der Darstellung von Festkommazahlen oder ganzen Zahlen Verwendung. Negative Zahlen werden vor allem als 2-Komplement dargestellt, welches nur im positiven Bereich der Dualzahlendarstellung entspricht. Um näherungsweise rationale oder gar reelle Zahlen darzustellen, werden vorzugsweise Fließkommadarstellungen verwendet, bei der die Zahl normalisiert und in Mantisse und Exponent aufgeteilt wird. Diese beiden Werte werden dann in Form von Dualzahlen gespeichert.

Grundrechenarten im Dualsystem

Analog zu den Zahlen im Dezimalsystem lassen sich mit Dualzahlen die gängigen arithmetischen Grundoperation Addition, Subtraktion, Multiplikation und Division durchführen. Tatsächlich werden die benötigten Algorithmen sogar einfacher und lassen sich effizient mit logischen Schaltungen elektronisch realisieren. Die Einführung von Dualzahlen in der Rechentechnik brachte daher viele Vorteile.

0 + 1 = 1
1 + 0 = 1
1 + 1 = 10 {\begin{matrix} &1011_2\\ \operatorname{+}&\ \ \ 11_2\\ \end{matrix} \over \begin{matrix} &\ \ 1110_2\\ \end{matrix}}

Addition	Beispiel
0 + 0 = 0

0 - 1 = -1
1 - 0 = 1
1 - 1 = 0 \begin{matrix} &1011_2\\ \operatorname{-}&\ \ 111_2\\ \end{matrix} \over \begin{matrix} &\ \ \ 100_2 \end{matrix}

Subtraktion	Beispiel
0 - 0 = 0

- 0

\cdot

1 = 0
1

\cdot

0 = 0
1

\cdot

1 = 1 \begin{matrix} &1010_2\\ {\cdot}&\ \ \ 11_2\\ \end{matrix} \over \begin{matrix} &11110_2 \end{matrix}

Multiplikation	Beispiel
0 $\cdot$ 0 = 0

0 / 1 = 0
1 / 0 = n.def.
1 / 1 = 1 \begin{matrix} &1010_2\\ {/}&\ \ \ 10_2\\ \end{matrix} \over \begin{matrix} &\ \ \ 101_2 \end{matrix}

Division	Beispiel
0 / 0 = n.def.

Schriftliche Addition

$A$	$B$	$M_1$	$M_2$	$E$
0	0	0	0	0
0	0	1	0	1
0	1	0	0	1
0	1	1	1	0
1	0	0	0	1
1	0	1	1	0
1	1	0	1	0
1	1	1	1	1

Die binäre Addition ist eine grundlegende Basisoperation in der Computerwelt. Will man zwei nicht negative Binärzahlen $A$ und $B$ addieren, so geht man wie folgt vor:

Die Zahlen werden übereinander aufgeschrieben. Nun arbeitet man von rechts nach links alle Binärziffern (=Bits) von $A$ und $B$ simultan ab und erzeugt in jedem Zwischenschritt ein Ergebnisbit sowie ein Merkerbit (auch Übertrag genannt). Dabei werden die Bits entsprechend der Tabelle rechts zusammengezählt. In den Spalten A und B sind die Bits der zu addierenden Zahlen zu finden. In der Spalte $M_1$ steht das Merkerbit des vorherigen Zwischenschrittes. Daraus ergibt sich (entsprechend dieser Tabelle, welche einem Volladdierer entspricht) ein Ergebnisbit (E) und ein neues Merkerbit ( $M_2$ ). Alle Ergebnisbits, von rechts nach links aneinandergereiht, stellen das Resultat dar. Entsteht beim letzten Zwischenschritt ein Merkerbit, so bekommt das Resultat links eine zusätzliche 1.

Am besten sieht man dies anhand eines Beispieles. Hier werden die Zahlen A und B zusammengezählt. In jedem Schritt wird ein anfallendes Merkerbit bei der nächsten Ziffer notiert.

A        = 10011010 (154)
B        = 00110110 (54)
Merker   =  11111
           

Ergebnis = 11010000 (208)

Schriftliche Subtraktion

Die binäre (schriftliche) Subtraktion kann auf mindestens 2 Arten durchgeführt werden. Der Ansatz, der hier gezeigt werden wird, ist jedoch der, der für den Menschen wohl einfacher nachzuvollziehen ist.

Als Beispiel nehmen wir wieder:

Minuend    = 10011010 (154)
Subtrahend = 00110110 (54)
Merker     = 11001010 ("-54")
             

Ergebnis   = 01100100 (100)

Dem anderen Ansatz nach würde man nun das Komplement (den Gegenwert) des Subtrahenden bilden (-54: 11001010) und diesem den Minuenden hinzuaddieren. Der Gegenwert selbst wird so gebildet: jede Stelle des Substrahenden wird mittels dem exklusiven Oder (xor) mit 1 verknüpft. Dann wird 1 zum erhaltenen Ergebnis hinzuaddiert.

Das exklusive Oder besagt:

0 xor 1 = 1
1 xor 1 = 0
0 xor 0 = 0
1 xor 0 = 1

Bei diesem gesamten Ansatz ist jedoch darauf zu achten, dass die Länge der benutzten Binärzahlen beachtet werden muss, da es durchaus vorkommt, dass ein Zahlen-Überlauf stattfindet. Im Klartext heißt das: eigentlicht erhalten wir bei der Berechnung den Wert: 356 (101100100); da wir aber nur mit 8 Stellen gerechnet haben, ist die vorderste Stelle als Zahlenbereich-Überlauf zu ignorieren.)

So gelangt man zum Ergebnis:

Man geht von rechts so lange zur nächsten Stelle des Minuenden und Subtrahenden, bis die letzte "1" des Subtrahenden erreicht wird. Problematisch ist, dass man bei dieser Form der schriftlichen Subtraktion mit einem Übertrag arbeitet (ähnlich dem Übertrag in der normalen dezimalen schriftlichen Rechnung). Dieser ist bei jedem Schritt in die Rechnung mit einzubeziehen und gilt als weiterer Subtrahend.

Zur Rechnung geht man nun wie folgt vor (hier wird sich nur auf die aktuelle Position bezogen):

Ist der Minuend "1", Subtrahend UND Merker "0", so ist das Ergebnis gleich "1".
Ist der Minuend "1", Subtrahend ODER Merker "1", so ist das Ergebnis gleich "0". War der Merker "1", so wird dieser nun auf "0" gesetzt.
Ist der Minuend "1", Subtrahend UND Merker "1", so ist das Ergebnis gleich "1" und zusätzlich bleibt der Merker auf "1" gesetzt.
Ist der Minuend "0", Subtrahend UND Merker "0", so ist das Ergebnis gleich "0".
Ist der Minuend "0", Subtrahend ODER Merker "1", so ist das Ergebnis gleich "1" und zusätzlich wird der Merker auf "1" gesetzt.
Ist der Minuend "0", Subtrahend UND Merker "1", so ist das Ergebnis gleich "0" und zusätzlich bleibt der Merker auf "1" gesetzt.

Demzufolge sehen unsere Ergebnisse nach den einzelnen Schritten so aus:

1.)                 .
  Ergebnis = 00000000 (0)
  Merker   = 00000000 (0)
2.)                ..
  Ergebnis = 00000000 (0)
  Merker   = 00000000 (0)
3.)               ...
  Ergebnis = 00000100 (4)
  Merker   = 00000001 (1)
4.)              ....
  Ergebnis = 00000100 (4)
  Merker   = 00000000 (0)
5.)             .....
  Ergebnis = 00000100 (4)
  Merker   = 00000000 (0)
6.)            ......
  Ergebnis = 00100100 (36)
  Merker   = 00000001 (1)
7.)           .......
  Ergebnis = 01100100 (100)
  Merker   = 00000001 (1)
8.)          ........
  Ergebnis = 01100100 (100)
  Merker   = 00000000 (1)

Wie man sieht, ist man in 8 Schritten zu seinem gewünschten Ergebnis gekommen.

(Ein anderer Ansatz geht wie folgt: Wir bilden das Komplement des Subtrahenden und addieren dann den Minuenden zu diesem hinzu: 25-13 = -13+25)

schriftliche Subtraktion für Maschinenbauer

Die Subtraktion verhält sich analog zur Addition:

0 − 0 = 0

0 − 1 = −1 (mit Übertrag)

1 − 0 = 1

1 − 1 = 0

Eine Zahl im Dualsystem kann von der anderen wie im folgenden Beispiel dargestellt subtrahiert werden:

* * * * (Sternchen symbolisieren den Übertrag) 1 1 0 1 1 1 0 − 1 0 1 1 1

= 1 0 1 0 1 1 1

Die Subtraktion einer postiven Zahl ergibt das selbe Ergebnis wie die Addition zu einer negativen Zahl mit dem gleichen Betrag.

Schriftliche Multiplikation

Um Binärzahlen mutliplizieren zu können, muss man mehrere Schritte durchführen, um ans Ziel zu gelangen. Das Resultat hat so viele Ziffern, wie beide Faktoren zusammen.

Als Beispiel seien hier:

FaktorA  =     1100 (12)
FaktorB  =     1101 (13)
Ergebnis = 10011100 (156)

So berechnet man das Ergebnis:

Am einfachsten multipliziert man zwei Binärzahlen indem man (nach alter Schulmethode) schriftlich multipliziert.

Man arbeitet sich bei FaktorB zeichenweise von rechts nach links voran. Dabei zählt man den FaktorA zum Ergebnis dazu, falls die Ziffer "1" ist und schiebt danach den FaktorA in jedem Fall eins nach links.

(Anmerkung: Das Schieben ist mathematisch gleichzusetzen mit der Multiplikation mit/Division durch 2 (binär: 10), wobei nach links=Multiplikation und nach rechts=Division)

Dieses Beispiel würde also wiefolgt berechnet werden:

1100 × 1101

-- + 1100 ← erste Ziffer "1" + 0 ← da der Multiplikator "0" ist, steht hier eine "0" um keine Stelle zu vergessen, fügt man eine "0" ein + 1100 ← erst hier wird wieder gerechnet, weil die zweite Ziffer "0" ist und dritte erst wieder "1" + 1100 ← vierte Ziffer "1"

-- = 10011100

Schriftliche Division

Am Beispiel der Division von 1000010 / 11 (entspricht 66:3 im Dezimalsystem)

    1000010 ÷ 11 = 10110 Rest 0 (= 22 im Dezimalsystem)
  - 011
  -
    00100
    - 011
     
      0011
     - 011
     -
        000
      -  00
        ---
          0

Umrechnen von Dualzahlen in andere Stellenwertsysteme

Durch die kleine Basis ergibt sich der Nachteil, dass Zahlen im Verhältnis zu Dezimalzahlen relativ lang und schwer zu überschauen sind (siehe Tabelle unten). Dies hat zur Verbreitung des Hexadezimalsystems geführt, welches die Basis 16 besitzt. Da 16 eine Potenz von 2 ist, ist es besonders einfach möglich, Dualzahlen in Hexadezimalzahlen umzurechnen. Dazu werden je vier Stellen der Dualzahl durch eine Hexadezimalstelle ersetzt, was auch die Länge der dargestellten Zahlen um den Faktor vier verringert. Die Hexadezimalziffern mit dem Wert 0-15 werden in der Regel durch die Ziffernsymbole 0-9 und die Großbuchstaben A-F (für die Werte 10-15) dargestellt. Dadurch sind sie verhältnismäßig gut lesbar, so lässt sich zum Beispiel leicht feststellen, dass EDA5₍₁₆₎ größer ist als ED7A₍₁₆₎ wo hingegen sich die entsprechenden Dualzahlen 1110110110100101₍₂₎ und 1110110101111010₍₂₎ nicht so schnell überblicken lassen.

Dualsystem	1	10	11	100	101	110	111	1000	1001	1010	1011	1100	1101	1110	1111
Oktalsystem	1	2	3	4	5	6	7	10	11	12	13	14	15	16	17
Dezimalsystem	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
Hexadezimalsystem	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F

Vom Dualsystem ins Dezimalsystem

Um eine Dualzahl in die entsprechende Dezimalzahl umzurechnen, werden alle Ziffern jeweils mit ihrem Stellenwert (entsprechende Zweierpotenz) multipliziert und dann addiert.

Beispiel:

1010_{(2)} = 1 \cdot 2^3 + 0 \cdot 2^2 + 1 \cdot 2^1 + 0 \cdot 2^0= 1 \cdot 2^3 + 1 \cdot 2^1 = 8 + 2 = 10_{(10)}

vom Dezimalsystem ins Dualsystem

Es gibt mehrere Möglichkeiten der Umrechnung ins Dualsystem. Im Folgenden ist die Divisionsmethode (auch Modulo-Methode genannt) am Beispiel 41₍₁₀₎ beschrieben:

\left.\begin{matrix}

41 &: 2 &=& 20 &\mathrm{ Rest }\ \ \mathbf{1}\\ 20 &: 2 &=& 10 &\mathrm{ Rest }\ \ \mathbf{0}\\ 10 &: 2 &=& 5 &\mathrm{ Rest }\ \ \mathbf{0}\\ 5 &: 2 &=& 2 &\mathrm{ Rest }\ \ \mathbf{1}\\ 2 &: 2 &=& 1 &\mathrm{ Rest }\ \ \mathbf{0}\\ 1 &: 2 &=& 0 &\mathrm{ Rest }\ \ \mathbf{1} \end{matrix}\ \right\uparrow

Die entsprechende Dualzahl ergibt sich durch Notation der errechneten Reste von unten nach oben: 101001₍₂₎.

Siehe auch

Zahlbasiswechsel

Weblinks

Zahlensystem

Gourt Home::Gourt :: Dualsystem