Das letzte Mal haben wir geklärt, wie logische Operationen auf einzelnen Bits durch einfache Bauteile umgesetzt werden können. Diesmal soll es darum gehen, wie man mit Hilfe dieser Bauelemente nun ganz konkret rechnen kann.

Zum Einstieg und zur Erinnerung noch einmal die Wertetabelle für die logischen Operationen AND (UND), OR (ODER) und XOR (EXKLUSIV-ODER) mit den zugehörigen Schaltbildern; die Wertetabellen sind diesmal in einer leicht anderen Form festgehalten (der Grund dafür erschließt sich beim Weiterlesen):

i-9d7375f9be2cc47b853d6cb0784d94ae-LogicTableWithGates.png

Die einfachste Art des binären Rechnens ist die Addition zweier einzelner Bits. Erinnern wir uns, wie das Rechnen im Binären war (auf den Index “2” verzichte ich im Folgenden aus Gründen der Übersichtlichkeit):

0 + 0 = 00
0 + 1 = 01
1 + 0 = 01
1 + 1 = 10

Dass Ergebnis der Rechnungen habe ich mit Absicht jeweils aus zwei Ziffern bestehend geschrieben. Der Grund ist, dass auf diese Art das Ergebnis optisch gut ersichtlich in zwei Teile zerlegt werden kann: den Übertrag C (von englisch carry) in der vorderen Ziffer und die Summe S in der hinteren Ziffer. Das kennt man ja noch von der schriftlichen Addition von Dezimalzahlen; die Gleichung 8+6 zum Beispiel hat das Ergebnis 14, wobei die 1 der Übertrag und die 4 die Summe ist.

Die Addition zweier Bits lässt sich somit wiederum als Wertetabelle aufschreiben (X und Y sind die jeweiligen Eingaben):

i-8da45f69d0313dbd28c4010b07071187-LogicTableHalfAdd.png

Aufmerksame Leser werden an der Tabelle sicher schon erkennen, wohin das führen wird. Die beiden Spalten für C und S lassen sich nämlich wunderbar mit den logischen Operationen erklären, wie ein Vergleich mit der ersten Abbildung zeigt – AND für C und XOR für S. Kombiniert man also ein AND-Gatter mit einem XOR-Gatter in ein Bauelement, so erhält man einen sogenannten Halbaddierer – ein Bauelement, welches 2 Bits als Eingänge besitzt, diese miteinander addiert und die Summe sowie den Übertrag der Rechnung an den Ausgängen wieder ausgibt.

Das Schaltbild dazu folgt hier. Diejenigen unter den Lesern, die Flash aktiviert haben (und – unter Umständen – diesen Artikel nicht im Feed-Reader, sondern direkt auf Scienceblogs lesen), sollten statt eines langweiligen Bildes einen interaktiven Schaltplan sehen, in welchem sie die Funktionsweise des Halbaddierers selber ausprobieren können (was ich sehr empfehle – es macht Spaß). Alle anderen müssen mit einem langweiligen Bild vorlieb nehmen*:

Damit sind wir schon auf dem halben Weg zum richtigen Addieren – was jetzt noch fehlt, ist die Möglichkeit, auch längere Binärzahlen miteinander addieren zu können. Wir erinnern uns: die schriftliche Addition findet immer stellenweise statt, wobei lediglich der Übertrag von einer Stelle an die nächste (also von rechts nach links) durchgereicht wird. Um den Halbaddierer also voll-additionsfähig (das Wortspiel muss sein) zu machen, also um einen Volladdierer zu erhalten, muss neben den Eingängen für die beiden zu addierenden Bits zusätzlich ein Eingang für den Übertrag der vorherigen Rechnung her. Es findet dann im Grunde eine Addition von 3 Bits statt. Damit ergibt sich die folgende Wertetabelle für einen Volladdierer:

i-683d3635926f3b59a4908d8823f09188-LogicTableFullAdd.png

Diese Berechnung kann durchgeführt werden, indem zwei Halbaddierer mit einem OR-Gatter verbunden werden, wie der folgende (wieder interaktive) Schaltplan zeigt (HA steht für Halbaddierer):

Damit haben wir jetzt alle Zutaten zusammen, um unser erstes Addierwerk zu bauen. Ein Addierwerk ist ein Bauelement, in welches zwei Binärzahlen mit jeweils der Länge n eingegeben werden und welches daraus die Summe der beiden Zahlen bildet. Addierwerke können auf verschiedene Art aufgebaut werden; grob sind dabei Paralleladdierer und Serienaddierer unterscheidbar, wobei es in jeder Gruppe weitere Unterteilungen gibt.

Die einfachste Form ist ein Paralleladdierer, welcher so arbeitet, wie wir es von der schriftlichen Addition kennen, sprich, welcher stellenweise die Summe zweier Ziffern berechnet und den eventuell entstehenden Übertrag an die nächste Ziffernaddition weitergibt. Der “parallele” Aspekt bezieht sich hier lediglich auf die Ziffern der beiden Eingabewerte, nicht auf den Übertrag. Ein solches Addierwerk nennt man passenderweise Ripple-Carry-Addierer und baut es einfach durch die Hintereinanderschaltung mehrerer Volladdierer auf. Jeder Volladdierer erhält als Eingabe die Bit-Ziffer der beiden Eingabezahlen entsprechend seiner Position und den Übertrag des vorgeschalteten Addierers (demzufolge kann der erste Volladdierer durch einen Halbaddierer ersetzt werden, da hier noch kein Übertrag berücksichtigt werden muss). Auch hierzu gibt es einen (interaktiven) Schaltplan, und zwar für einen 4-Bit-Addierer, also einen Addierer, der Bitketten der Länge 4 miteinander addieren kann:

Einfache Ripple-Carry-Addierer haben den Vorteil, dass sie ziemlich einfach aufgebaut werden können, aber auch den Nachteil, dass eine Berechnung relativ lange dauert, da ja der Übertrag von Position zu Position weitergereicht werden muss. Im Laufe der Zeit entstanden daher verschiedene verbesserte Paralleladdierer, welche dieses Problem umgehen. Für das Verständnis der Funktionsweise von Computern sind sie nicht weiter wichtig, daher werde ich sie auch nicht erklären – außer, es besteht der explizite Wunsch, dann schiebe ich noch einen Artikel nach.

1 / 2 / Auf einer Seite lesen

Kommentare (11)

  1. #1 michael
    Juni 17, 2011

    Die ersten beiden Paragraphen sind doppelt.

  2. #2 Marcus Frenkel
    Juni 17, 2011

    Die Tücken des Blog-Systems.
    Ist korrigiert, danke.

  3. #3 Dr. Webbaer
    Juni 17, 2011

    Nichts gegen die Grundlagen, aber bevor wir hier zu “Topologie von Flächen CLXXI” kommen, eine Anregung: Gerne auch weiterhin aktuelle IT-Themen anschneiden und so; kann man auch besser kommentieren. 🙂

    MFG
    Dr. Webbaer

  4. #4 Marcus Frenkel
    Juni 17, 2011

    Habe ich vor.

    Auf Grund aktueller Netzprobleme (mit GPRS ist Browsen nicht wirklich praktisch) werden die Artikel in den nächsten Tagen allerdings etwas rarer sein.

  5. #5 Dr. Webbaer
    Juni 17, 2011

    Dr. W hatte mal übergangsweise in seinem Büro ein UMTS-Internetmodem der Deutschen Telekom, das bedarfsweise oder nach Lust und Laune auf GPRS umgestellt hat. War lustig. – Als es dann aus dem Fenster gehängt (!) wurde, ging dann die GPRS-Zeit auf ca. 2% herunter von anfangs ca. 10%.
    Die Deutschen Telekom war hier i.p. Support ein guter Helfer!
    Ist aber fast zehn Jahre her…

  6. #6 rolak
    Juni 17, 2011

    Hi Marcus, die interaktiven Blitzer sind wirklich nett gemacht – mich interessiert aber weniger die Möglichkeit einer ‘Bestellung’ als die Entstehungsgeschichte. Indirekt gefragt: Nutzt Benjamin Chalupka ein spezielles Werkzeug oder die entsprechenden Teile aus Adobes CS?
    Generell wäre mir ja SVG lieber, aber der blöde IE weigert sich weiterhin stur…

  7. #7 a
    Juni 17, 2011

    […]daher werde ich sie auch nicht erklären – außer, es besteht der explizite Wunsch, dann schiebe ich noch einen Artikel nach.

    Hier besteht der Wunsch.

  8. #8 Michi
    Juni 18, 2011

    Vielen vielen Dank für diese Serie! Es hat mich schon lange gestört, dass ich zwar täglich mit dem Rechner arbeite, programmiere, etc – aber nicht die Grundlagen des Rechners kenne.
    Schade das man deine Beitrag nicht flattrn kann.

  9. #9 Sim
    Juni 18, 2011

    Toller Beitrag. Besonders die Flash-Animationen gefallen mir, weiter so :3

  10. #10 Marcus Frenkel
    Juni 29, 2011

    @rolak
    Jetzt habe ich ganz vergessen, hier zu antworten…
    Die Schaltpläne sind mit dem Adobe Flash Builder (4.5, wenn ich mich richtig erinnere) in gemacht.

  11. #11 rolak
    Juni 29, 2011

    ganz vergessen

    Nun ja, insgesamt nichr 😉 Danke!