gate question

Question

Consider a carry look ahead adder for adding two n-bit integers, built using gates of fan-in at most two. The time to perform addition using this adder is

Comments

plz explain betterway

---

O(logn) ???

---

plz sir explain???

---

C1=PoCo+Go  (2 terms :-1level or gate and 1-level and gate)

C2=P1PoCo+P1Go+G1 (3terms:- 2 level or gste and 2-level AND gate)

C3=P2P1PoC0+P2P1G0+P2G1+G2 (4terms:-2 level or gate 2-level AND gate)

.............................................

..............................................

............................................

..............................................

Cn={n+1 terms}  (logn n level or gate and logn level AND gate)

OR gates:-

maximum delay would be for Cn.....N+1 sum terms could be relised with logn lavel of OR logic gates

and N+1 Product term could be relised with logn level AND gates....

in first go...N/2

In second Go...N/4

In thirsd go ....N/8.....in logn go it would be   N/2^logn...

therefor final delay in adding n-bit would be:-

logn level AND gates delay+logn level OR gates :-

O(2logn)=O(logn).....