Zum Inhalt springen

Digitale Schaltungstechnik/ Addierer/ Binäre Quersumme

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

Binäre Quersumme

[Bearbeiten]

Anwendungen

[Bearbeiten]

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

[Bearbeiten]

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

[Bearbeiten]

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

[Bearbeiten]

Wir haben die sechs Eingänge E0 bis E5 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

[Bearbeiten]

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

Größere Schaltungen

[Bearbeiten]

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

[Bearbeiten]

Aufgaben

[Bearbeiten]

Schema vorgegeben

[Bearbeiten]

einfache Aufgaben

[Bearbeiten]

einfache Textaufgaben

[Bearbeiten]

Bürgermeister

Abstimmung

Alarmanlage

freie Parkplätze

komplexe Textaufgaben

[Bearbeiten]

Unfaire Aufgaben

[Bearbeiten]

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

naheliegende Lösung

[Bearbeiten]
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.

GNU Animation

optimale Lösung

[Bearbeiten]

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:
GNU Animation

GNU
GNU
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.