Digitale Schaltungstechnik/ Addierer/ Binäre Quersumme

Titelseite
Addierer Mehr-Bit Addierer BCD Binäre Quersumme mehrere Variablen Subtraktion kombiniertes Rechenwerk Alternative Addierer Carry-Ripple-Addierer Carry-Skip-Addierer Stufe 2 bis n Stufe 1 Rückspiegel Carry-Look-Ahead-Addierer Serienaddierwerk

Binäre Quersumme

Anwendungen

Die binäre Quersumme hat keine direkte Anwendung, jedoch soll es in diesem Kapitel auch nicht um die Anwendung gehen: Es geht darum, den Umgang mit Addieren trainieren.

Doch ein paar Anwendungsfälle lassen sich dennoch finden:

Anzahl Signale, die High sind
Prüfsumme

und nicht verheimlicht werden soll, dass dies schlicht auch eine sehr beliebte Schulbuchaufgabe ist.

Lösungsverfahren

Hier wird nun eines von vielen möglichen Lösungsverfahren vorgestellt. Wenn der Leser eine eigene Methode entwickelt, so ist das sehr zu begrüßen: Das Entwickeln einer eigenen Methode zeugt von hohem Verständnis.

Dennoch gibt es eine Aussage, auf die wir uns verlassen können:

die Schaltung ist fertig, wenn für jedes Gewicht nur noch eine Leitung besteht

Was es damit auf sich hat, wird sich nach und nach offenbaren.

Reihenfolge

Ich empfehle, unten links mit dem Schema zu beginnen. Natürlich lässt sich das Schema auch an einem anderen Ort beginnen, doch das kann nachteilig sein.

Beispiel 1

Wir haben die sechs Eingänge E₀ bis E₅ und wollen diese Bits miteinander addieren.

Wie gesagt, wir beginnen beim Entwickeln der Schaltung unten links mit einem Volladdierer:
Dann gehen wir ein Stück nach oben und legen uns die nächsten zwei Variablen bereit:
Da das Sigma unseres ersten Addieres die gleiche Wertigkeit wie die weiteren Eingänge hat, können wir die drei Variablen addieren:
Als nächstes legen wir den nächsten und zugleich letzten Eingang bereit:
Da es nur noch zwei Variablen sind, reicht ein Halbaddierer:
Die Addition der nächsten Wertigkeit (zwei) führen wir in der nächsten Reihe nach dem gleichen Verfahren durch.
Da es nur drei Variablen sind, ist das sehr einfach.
Da nun jedes Gewicht einmalig ist, können wir die Ausgänge beschriften:

Beispiel 2

Bei diesem Beispiel hat die Schaltung fünf Eingänge und wieder soll die binäre Quersumme gebildet werden. Diesmal im Schnelldurchgang:

unten links mit drei Eingängen und einem Volladdierer beginnen
Übertrag bereit legen
zwei weitere Eingänge dazu zeichnen
Volladdierer einzeichnen
Nächste Wertigkeit (2) aufaddieren

Größere Schaltungen

Bisher haben wir uns nur relativ kleine Schaltungen angesehen, aber natürlich können wir das Verfahren auch bei wesentlich größeren anwenden:

Die einzelnen Stufen werden nebeneinander gezeichnet, das Verfahren bleibt für jede Stufe identisch. Die Schaltung ist dann fertig, wenn jede Wertigkeit nur noch einmal auftritt.

Beispiellösung

Aufgaben

Schema vorgegeben

einfache Aufgaben

einfache Textaufgaben

Bürgermeister

Abstimmung

Alarmanlage

freie Parkplätze

komplexe Textaufgaben

Unfaire Aufgaben

Nicht immer ist ein vorgegebenes Schema eine Hilfe, um die einfachste Lösung zu finden:

naheliegende Lösung

Verbindet man im ersten Schritt die Eingänge der Schaltung mit den Eingängen der Addierer, ergibt sich diese Schaltung:
Im nächsten Schritt wird festgelegt, dass der obere Addierer die 2^0 und der untere Addierer die 2^1 Stelle verarbeiten sollen. Die naheliegenden Verbindungen dazu sind:
Um noch den Wert des jeweils anderen Addierers zu verarbeiten, werden die Leitungen so verbunden:
Im nächsten Schritt müssen noch die beiden Addierer miteinander verbunden werden:
Addiert man in der nächsten Addiererstufe die Zwischenresultate, ergibt sich diese Schaltung:

Keine Frage, die Schaltung funktioniert, aber es nicht die optimale Lösung.

Animation

optimale Lösung

Verwenden wir das oben beschriebene Lösungsverfahren, verläuft es wie folgt:

Wir belegen den untersten Volladdierer voll:
Dann verbinden wir das Sigma des unteren linken Addierers mit dem untersten Eingang des nächsten Addierers:
Danach verbinden wir die nächsten und hier zugleich letzten Eingänge mit diesem Addierer:
Das Sigma von Addierer oben Links ist die letzte freie Leitung mit der Wertigkeit 1. Wir können sie also mit dem Ausgang verbinden: Die Übertrage der beiden linken addieren wir im Addierer unten rechts:
Der Sigma-Ausgang dieses Addierers ist die letzte freie Leitung mit der Wertigkeit 2 und der Übertragsausgang ist der letzte mit der Wertigkeit 4, also können wir auch diese mit dem Ausgang verbinden:

Vergleichen wir die beiden Schaltungen, fällt auf, das bei der zweiten Lösung keine Leitungskreuzungen vorhanden sind und sogar noch ein kompletter Volladdierer übrig bleibt.
Als letzten Feinschliff sollten die freien Eingänge noch mit Masse bzw. 0 Volt verbunden werden:

Animation

Diese Seite enthält GIF-Animationen. Sollten die Animationen nicht laufen, klicken Sie auf die jeweilige Animation um sie zu vergrössern.

Für Computer versierte: Sie können versuchen gemäß Hilfe:Cache den serverseitigen Zwischenspeicher zu bereinigen: Dies kann, muss aber nicht, das Problem lösen.