GATE CSE 2016 Set 1 | Question: 33

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

• A. $\Theta (1)$
• B. $\Theta (\log(n))$
• C. $\Theta (\sqrt{n})$
• D. $\Theta (n)$)

Comments

So is O(log n) true for CLA carry also for fan in = 2?

---

Yes it's O(logn).

---

Almost same question

https://gateoverflow.in/2231/gate1997-2-5

Answer 1

Look ahead carry generator gives output in constant time if fan in $=$ number of inputs. 

Example, it will take  $O(1)$ to calculate $c_4 = g_3 + p_3g_2 + p_3p_2g_1 + p_3p_2p_1g_0 + p_3p_2p_1p_0c_0$, if OR gate with $5$ inputs is present.

If we have $8$ inputs, and OR gate with $2$ inputs, to build an OR gate with $8$ inputs, we will need $4$ gates in level-$1, 2$ in level-$2$ and $1$ in level-$3$. Hence, $3$ gate delays, for each level.

Similarly an $n$-input gate constructed with $2$-input gates, total delay will be $O(\log n).$

Hence, answer is option B.

Comments

Can anyone kindly give a diagramatic answer for this question or any link ?

---

Why we are only considering the OR gate inputs here,why not including the AND gates inputs here like for calculating C3=G2+P2G1+P2P1G0+P2P1P0C0.So here we should also consider two inputs for calculating AND operation for P2P1G0?

---

its a very short explanation did not get it

Answer 2

I didn't found any analysis to be satisfying, so I am posting this.

The carry generator circuit of 4-bit CLA(for example I have taken) is as below :

Now Below are my equations

$P_i=A_i \oplus B_i$ $,G_i=A_iB_i$

$C_{i+1}=G_i+P_iC_i$

And for Sum $S_i=P_i \oplus C_i$

$C_0$ will be my input carry, and $C_4$ , will be my carry out of MSB of sum bit $S_3$

My Equations for carry generation circuit are:

$C_1=G_0+P_0C_0$

$C_2=G_1+P_1G_0+P_1P_0C_0$

And circuits for them using fan-in of gates to be 2 are below

 

 

$C_3=G_2+P_2G_1+P_2P_1G_0+P_2P_1P_0C_0$

And it's circuit is below

 

 

So, here my biggest term to do AND with consists of 4 terms, so I Need $log_24=2$ level of AND gates and I have 4 terms to OR together, so similarly 2 level of OR gates.

Now, you might say you have total 4 levels and your total time looks like $\theta(n)$, but before you say this, I ask you to not forget carry $C_4$

$C_4=G_3+P_3G_2+P_3P_2G_1+P_3P_2P_1G_0+P_3P_2P_1P_0C_0$

and it's circuit diagram with gates of fan-in two is below

 

Now, you see, it's a way bigger term than $C_3$ and here total level is only 5. Why don't levels increase in linear to the number of carry?

The biggest term in $C_4$ to be ANDed together consists of 5 terms and for this you need $\lceil log_25 \rceil=3$ level of AND gates and maximum terms to be ORed together is 5 so 3 level of OR gates.

So, for n bit carry look ahead adder, the biggest carry expression would be of $C_n$ and it would have a total delay of $log_2n(\,for\,AND\,gates\,) + log_2n(\,for\,OR\,gates\,)\,=2log_2n$

Okay, so my carry generation circuit would take $2log_2n$ time.

What about total sum? The sum bits?

The carry-look ahead generator would look like this

 

So, it is clear that my $P_i,G_i$ inputs are available in only 1 propagation delay (only 1 level) and once, carry bits are calculated, the sum bits will also be calculated in another just one propagation delay time unit (only 1 level gates).

So, my total time to get Sum=$2log_2n+2$ time units.

So, my operation time of carry look ahead adder designed using gates of fan-in 2 is $\theta(log_2n)$

Generalization: If the fan-in of the gates is $k$, carry generation will take $2log_kn$ time where n=Number of bits in the input.
When $k=n$(Means, there is no limit on fan-in of gates), carry generation takes $2log_nn=2$ time units of the propagation delay of gates.

Hence, Total Carry Look Ahead Adder time in such case would be $2log_kn+2$ propagation delay units.

When there is no limit on fan-in, then $k=n$ and hence in that case my carry look ahead adder delay is $2log_nn+2=4$ propagation time units and this will be independent of the number of bits present in the input.

Comments

$P_{i} = A_{i} \oplus B_{i} $ isn't it?

---

Yes,thanks :)

---

yes this is correct that both AND & OR require $\log_{2}n$ levels but in question they are asking about

"The time to perform addition using this adder is" ,shouldn't be the answer contain OR levels only?

---

@Shubgupta- No. the time to perform addition means you want both final carry output and sum.So it must include both AND and OR levels.

---

best explanation!!

---

Sir why at last line you wrote fan-in 2 is θ(n) it would be  θ(logn) .

---

@rajinder-Thanks. That was a typo :)

---

But total delay should be less the 2logn for carry generation since OR gate here is computing parallelly with AND gate at some levels and if delay of both the gates is assumed to be same then we may take delay of any one of them at a particular level.

For ex, for C4, though there are logn levels for individual AND and OR gates but total delay here would be only 5 (since 5 levels), not 2*seal(log(5))=6

So it would be value less then 2logn +2(for Pi Gi and sum).

In terms of complexity it should be O(2*logn)=O(logn) but not Θ(logn). Pls correct if i am wrong.

---

@Namrata-I think you are not clear with the definition of $\theta$

See, if my cost is say 2logn, or 3 logn or (1/10)logn or $klogn$ where k is any constant,

by definition of theta notation I can bound it with theta as

$c_1logn \leq klogn \leq c_2 logn$ for some constants c1 and c2.

When I say $\theta(logn)$, $\Omega(logn)$ and $O(logn)$ are already implied by that.

---

great explanation @Ayush sir

---

sir mat bolo :(

---

This is best explanation :0. Thank you....

---

So, for n bit carry look ahead adder, the biggest carry expression would be of Cn and it would have a total delay of log2n(forANDgates)+log2n(forORgates)=2log2n

But aren't this OR and AND levels overlapping so..time required will not be like sequential First AND levels then OR levels right???

So, it is clear that my Pi,Gi inputs are available in only 1 propagation delay (only 1 level

If XOR is not provided the

Pi operation will need XOR so using 2 input gates(AND/OR) it will be possible in minimum 2 levels.how it can be done in 1 level

Same for final FA sum which is Ci XOR Pi 

---

Thanks a lot

---

@Ayush Upadhyaya

pls tell me why time is 2logn+2 , why not logn+2??

why to take time of AND  and OR  level time separately??

when we know that while calculating C4 , i am getting 5 levels; so it is ceil of logn +2

pls tell me!!whenever u are free!!

---

What is n here?  I think its no of bits to add. So as per logn for 4 bits , delay will be of log4 equals  2 units. But delay is of 3 units due to c4 as there are 5 terms to and in ç4  which would take log5 equals 3 units. So i think it shiuld be log(n+1) instead of log(n).

---

Thanks you . Great explanation.

---

best explanation !!

@Ayush Upadhyaya 🙏🙏

thanks

---

Thanks @Ayush Upadhyaya Sir, for this wonderful explanation.

---

this is really great explanation! thanks for posting this

Answer 3

option "b" 

$O(\log_2 n)$  

because as fan-in is at most 2 then we can use two variable to the i/p of one XOR gate and then one i/p and one o/p from previous XOR gate and so, on ..

https://www.cs.umd.edu/class/fall2003/cmsc311/Lectures/lecture22/lookahead.pdf

Comments

Here we can measure time ccomplexity by OR gate only.

Because in one level result of OR gate require to measure the value in next level

---

why are we considering only OR gates? what about AND gate ? they are also of fan in 2?

---

in this question only addtion time is asked so we have to consider OR gates delays only which is required to add all those terms which are obtained after Anding all.

Answer 4

Answer : A

C_i+1 = G_i + P_iC_i

Constant time because in Carry Lookahead both carry bit and sum bit available in constant time.

Comments

But it has been mentioned that maximum fan-in is two.

Considering this, shouldn't the option be B?