Digitale Schaltungstechnik/ Addierer/ Binäre Quersumme

Aus Wikibooks
Zur Navigation springen Zur Suche springen
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: Adder Network 6 011.svg
Dann gehen wir ein Stück nach oben und legen uns die nächsten zwei Variablen bereit: Adder Network 6 010.svg
Da das Sigma unseres ersten Addieres die gleiche Wertigkeit wie die weiteren Eingänge hat, können wir die drei Variablen addieren: Adder Network 6 009.svg
Als nächstes legen wir den nächsten und zugleich letzten Eingang bereit: Adder Network 6 008.svg
Da es nur noch zwei Variablen sind, reicht ein Halbaddierer: Adder Network 6 006.svg
Die Addition der nächsten Wertigkeit (zwei) führen wir in der nächsten Reihe nach dem gleichen Verfahren durch. Adder Network 6 004.svg
Da es nur drei Variablen sind, ist das sehr einfach.
Da nun jedes Gewicht einmalig ist, können wir die Ausgänge beschriften: Adder Network 6 003.svg

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: Adder Network 15 Stufenmarkiert.svg
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]

Adder Network 5.svg

Adder Network 10.svg

Adder Network 15.svg

Adder Network 6 001.svg

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:

Adder Network 5 Task 000.svg

naheliegende Lösung[Bearbeiten]

Verbindet man im ersten Schritt die Eingänge der Schaltung mit den Eingängen der Addierer, ergibt sich diese Schaltung: Adder Network 5 Task 001 Step 1.svg
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: Adder Network 5 Task 001 Step 2.svg
Um noch den Wert des jeweils anderen Addierers zu verarbeiten, werden die Leitungen so verbunden: Adder Network 5 Task 001 Step 3.svg
Im nächsten Schritt müssen noch die beiden Addierer miteinander verbunden werden: Adder Network 5 Task 001 Step 4.svg
Addiert man in der nächsten Addiererstufe die Zwischenresultate, ergibt sich diese Schaltung: Adder Network 5 Task 001.svg

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

Quersummenzähler.gif
GNU Animation

optimale Lösung[Bearbeiten]

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

Wir belegen den untersten Volladdierer voll: Adder Network 5 Task 002 Step 1.svg
Dann verbinden wir das Sigma des unteren linken Addierers mit dem untersten Eingang des nächsten Addierers: Adder Network 5 Task 002 Step 2.svg
Danach verbinden wir die nächsten und hier zugleich letzten Eingänge mit diesem Addierer: Adder Network 5 Task 002 Step 3.svg
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:

Adder Network 5 Task 002 Step 4.svg
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: Adder Network 5 Task 002 Step 5.svg
Adder Network 5 Task 002 Step 6.svg
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: Adder Network 5 Task 002.svg
OptQersummenzähler.gif
GNU Animation

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.