Hardware Reference
In-Depth Information
[(p
2
;g
2
) (p
1
;g
1
)] (p
0
;g
0
) = (p
2
p
1
p
0
; g
2
_g
1
p
2
_g
0
p
2
p
1
)
Damit ist die Bedingung für die Umwandlung in eine Baumstruktur erfüllt
(Abb. 2.76 b).
Abbildung 2.77 zeigt einen 8-Bit-Addierer, der die Block-Propagate- und
die Block-Generate-Signale mit einer Baumstruktur berechnet. Die Berech-
nung der einfachen Propagate- und Generate-Signale p
i
und g
i
erfolgt wie
in Abb. 2.75 jeweils mit einem EXOR- und einem UND-Gatter (nicht darge-
stellt). Dann folgt die Baumstruktur für die Bildung der Blocksignale p
0;i
und
g
0;i
. In der nächsten Verarbeitungsschicht werden aus den Blocksignalen und
dem Eingangsübertrag c
0
die Überträge der einzelnen Bitstellen berechnet.
Die Summenbits sind die EXOR-Verknüpfungen der (einfachen) Propagate-
Signale mit dem Übertrag der vorherigen Bitstelle.
≈t
d
◦
≤4·t
d
◦
≈2·t
d
◦
(p
0
,
7
,g
0
,
7
)
(p
7
,g
7
)
c
8
(c
0
∧p
0
.
7
∨g
0
.
7
)
c
out
(p
0
,
6
,g
0
,
6
)
p
7
(p
6
,g
6
)
=1
s
7
(c
0
∧p
0
.
6
∨g
0
.
6
)
c
7
(p
5
,g
5
)
(p
0
,
5
,g
0
,
5
)
p
6
=1
s
6
c
6
(c
0
∧p
0
.
5
∨g
0
.
5
)
(p
4
,g
4
)
(p
0
,
4
,g
0
,
4
)
p
5
=1
s
5
c
5
(c
0
∧p
0
.
4
∨g
0
.
4
)
(p
3
,g
3
)
(p
0
,
3
,g
0
,
3
)
p
4
=1
s
4
c
4
(c
0
∧p
0
.
3
∨g
0
.
3
)
(p
0
,
2
,g
0
,
2
)
p
3
(p
2
,g
2
)
=1
s
3
(c
0
∧p
0
.
2
∨g
0
.
2
)
c
3
(p
0
,
1
,g
0
,
1
)
(p
1
,g
1
)
p
2
=1
s
2
c
2
(c
0
∧p
0
.
1
∨g
0
.
1
)
(p
0
,g
0
)
p
1
=1
s
1
(c
0
∧p
0
∨g
0
)
c
1
l¨angsterPfad
pg-Tupel(2-Bit-Vektor)
p
0
=1
s
0
c
0
⇒
Web-Projekt:P2.5/HiAdd.vhdl
Abb. 2.77. Hierarchischer 8-Bit-Addierer mit logarithmischer Laufzeit
Die größte Anzahl der Operatorfunktionen liegt auf dem Pfad von (a
0
;b
0
)
über (p
0
;g
0
) nach s
7
und beträgt vier. Zur Verzögerung durch die Operato-
ren kommen noch weitere Verzögerungen von insgesamt etwa 3 t
d
für die
Bildung der Propagate- und Generate-Signale am Eingang und die Bildung
der Übertrags- und der Summensignale am Ausgang hinzu. Eine Verdopplung
der Eingangsanzahl vergrößert die Verzögerung bei dieser Struktur jeweils nur
um 1 t
d
. Bei einem Ripple-Addierer verdoppelt sie sich im Vergleich dazu
bei einer Verdopplung der Bitanzahl. Die geringere asymptotische Ordnung
verkürzt aber nur für größere Bitbreiten der Operanden die Additionsdauer
wirksam:
