BCD Ripple Carry AdderBCD Ripple Carry Adder

von Enrico Billichvon Enrico Billich

Mathematische EigenschaftenMathematische Eigenschaften

Addiert zwei 8 Bit BCD ZahlenAddiert zwei 8 Bit BCD Zahlendies ermöglicht Additionen von dies ermöglicht Additionen von Summanden zwischen 0 und 99Summanden zwischen 0 und 99unter Berücksichtigung des Carry In sind unter Berücksichtigung des Carry In sind Summen zwischen 0 und 199 Summen zwischen 0 und 199 berechenbarberechenbar

Schaltungstechnische EigenschaftenSchaltungstechnische Eigenschaften

Einfacher modularer SchaltungsaufbauEinfacher modularer SchaltungsaufbauSchnelle Wandlung wiederum in ein BCD-Schnelle Wandlung wiederum in ein BCD-Codiertes Ergebnis durch eine einfache Codiertes Ergebnis durch eine einfache zweistufige Kombinatorikzweistufige KombinatorikNachteil: Carry wird im Worst-Case durch Nachteil: Carry wird im Worst-Case durch ganze Schaltung gereicht und steht erst ganze Schaltung gereicht und steht erst am Ende festam Ende fest

Oberste HierarchieebeneOberste Hierarchieebene

BCDRipple Carry

Adder

Cin

Cout

A0

A1

B0

B1

A2

B2

A3

B3

A4

B4

A5

B5

A6

B6

A7

B7

S0

S1

S2

S3

S4

S5

S6

S7

8Bit-Adder aus 2 4Bit-Adder8Bit-Adder aus 2 4Bit-Adder

C1

Cout

A4B4A5B5A6B6A7B7

S4S5S6S7

4Bit BCD-Adder

Cin

C1

A0B0A1B1A2B2A3B3

S0S1S2S3

4Bit BCD-Adder

4Bit BCD-Adder4Bit BCD-AdderCin

C1

A0B0A1B1A2B2A3B3

S0S1S2S3

FullAdder

FullAdder

FullAdder

FullAdder

Co3 Z3 Z2Co2 Co1 Co0Z1 Z0

≥1

& &&≥1

& &

≥1

& &&

≥1

&&

≥1& ≥1 & &

≥1

Full AdderFull Adder

a

b

Ci

s Co

≥1

& & &&& & &&

≥1 ≥1≥1

& & &

≥1

Gleichungen des Full Adders und Gleichungen des Full Adders und längster Pfad durch ihnlängster Pfad durch ihn

iiii abccbacbacbaS

iio bcacabc

Negator 2*UND-Gatter 2*ODER-Gatter

= 5 Gatter je 5ns = 25ns maximale Verzögerungszeit

UND-Gatter 2*ODER-Gatter

= 3 Gatter je 5ns = 15ns maximale Verzögerungszeit

Längster Pfad durch 8Bit BCD AdderLängster Pfad durch 8Bit BCD Adder

Da 8Bit-Adder aus 2 4Bit-Adder aufgebaut ist, Da 8Bit-Adder aus 2 4Bit-Adder aufgebaut ist, lässt sich Problem in 2 Teile zerlegenlässt sich Problem in 2 Teile zerlegenIm ersten 4Bit-Adder muss das Carry vom Im ersten 4Bit-Adder muss das Carry vom ersten Full Adder bis zum letzten schrittweise ersten Full Adder bis zum letzten schrittweise durchgereicht werden, so dass erst am Ende mit durchgereicht werden, so dass erst am Ende mit Berechnung der letzten Summe (Z3) der Berechnung der letzten Summe (Z3) der tatsächlicher Wert des Carry (C1) feststehttatsächlicher Wert des Carry (C1) feststehtIm zweiten 4Bit-Adder muss durch das erhaltene Im zweiten 4Bit-Adder muss durch das erhaltene Carry die Summe im obersten Full Adder so Carry die Summe im obersten Full Adder so verändert werden, dass S5 möglichst spät verändert werden, dass S5 möglichst spät seinen endgültiges Wert erreichtseinen endgültiges Wert erreicht

A0B0

FullAdder

A1B1

FullAdder

A2B2

FullAdder

A3B3

FullAdder

CinCo2 Co1 Co0

A7B7

FullAdder

A6B6

FullAdder

A5B5

FullAdder

A4B4

FullAdder

Co3

Z3 Z2 Z1

C1

Co4 Co5 Co6

Co7Z5 Z6 Z7

S5

≥1

& &&& &

≥1

≥1& &

≥1

Berechnung des längsten WegesBerechnung des längsten Weges

7 Carry Berechnungen (Co0, Co1, Co2, 7 Carry Berechnungen (Co0, Co1, Co2, C1, Co4, Co5, Co6) je 3 Gatter = 21 C1, Co4, Co5, Co6) je 3 Gatter = 21 GatterGatter2 Summen (Z3, Z7) je maximal 5 Gatter = 2 Summen (Z3, Z7) je maximal 5 Gatter = 10 Gatter10 Gattereine Umrechnung des Ergebnisses ins eine Umrechnung des Ergebnisses ins BCD-Format (S5) maximal 5 GatterBCD-Format (S5) maximal 5 GatterInsgesamt 36 Gatter je 5ns = 180nsInsgesamt 36 Gatter je 5ns = 180ns

Simulationsproblem des längsten PfadesSimulationsproblem des längsten Pfades

Theoretisch längster Pfad kann praktisch Theoretisch längster Pfad kann praktisch nicht vorkommen weil sich bestimmte nicht vorkommen weil sich bestimmte Konstellationen, die an den Gattern nötig Konstellationen, die an den Gattern nötig sind, sich gegenseitig widersprechensind, sich gegenseitig widersprechendeshalb wird eine möglichst langsame deshalb wird eine möglichst langsame Lösung gesucht, die der theoretisch Lösung gesucht, die der theoretisch langsamsten am nächsten kommtlangsamsten am nächsten kommt

Beweis für vorherige BehauptungBeweis für vorherige Behauptung

132331 ZZZZCOC

03 CO 112 ZZ

Belegungen für ersten 4Bit-BCD-Adder

Damit C1 so spät wie möglich feststeht, muss es von Z3 abhängig sein, dass sich dadurch ebenfalls so spät wie möglich ändern muss. Folglich:

iiii abccbacbacbaS

Wegen dieser Bedingungen, der Beschränkung auf BCD Zahlen und dass Z3 erst mit dem erhaltenen und negierten Carry Co2 sein endgültiges Ergebnis erreicht, ergibt sich folgende Eingangsbelegung.

Au=0111 Bu=1000

Für das Ci, dass sich als einziges ändert, ergeben sich die Belegungen:Ci ändert sich von 1 auf 0

Folglich ändert sich C1 von anfangs 1 auf 0 (nachdem Co3 feststeht) und endgültig auf 1 (nachdem Z3 feststeht). 17 Gatter = 85ns.

Beweis für vorherige BehauptungBeweis für vorherige Behauptung

5667756 ZZZZCoZS

567757575 ZZZCoZCoZZS

Belegungen für zweiten 4Bit-BCD-AdderDa auch hier das Carry durchgereicht werden muss, damit Z7 möglichst spät fest steht, gilt ähnliche Eingangsbelegung wie für den ersten Adder.

Durch diese Eingangsbelegung werden aber Z5 und Z6 immer 0, wenn das Carry (C1=1) ankommt. Folglich werden auch alle Terme 0, in denen das negierte Z7 steht. Das gleiche gilt auch für den Weg über S6.

Da der längste Weg über das negierte Z7 nicht mehr geht, bleibt nur der Weg über das nichtnegierte Z7, was mit den Werten für Z6 und Z5 im zweiten Term von S7 passt.Das sind wieder 17 Gatter mit 85ns, was sich mit dem vorherigen 4Bit-BCD-Adder zu 170ns addiert.

Ao=0111 Bo=1000

567757 ZZZCoZS

Beispiel mit 170ns (34 Gatter)Beispiel mit 170ns (34 Gatter)

Anfangsbelegung einstellenAnfangsbelegung einstellenA: 01110111 (77)A: 01110111 (77)B: 10001000 (88)B: 10001000 (88)Cin: 1Cin: 1

Änderung des Carry InÄnderung des Carry InCin: 0Cin: 0

Ergebnis der SimulationErgebnis der Simulation

Literaturreferenz

Randy H. Katz – Contemporary Logic Randy H. Katz – Contemporary Logic Design (S. 265, ZN 5630 kat)Design (S. 265, ZN 5630 kat)Balabanian, Cartson – Digital Logic Balabanian, Cartson – Digital Logic Design Principles (ZN 4930 bal)Design Principles (ZN 4930 bal)Reichardt, Schwarz – VHDL-SyntheseReichardt, Schwarz – VHDL-Synthese

ENDE