edited by
30,747 views
85 votes
85 votes

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

  1. $\Theta (1)$
  2. $\Theta (\log(n))$
  3. $\Theta (\sqrt{n})$
  4. $\Theta (n)$)
edited by

9 Answers

Best answer
126 votes
126 votes

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.

edited by
115 votes
115 votes

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.

edited by
17 votes
17 votes

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

4 votes
4 votes

Answer : A

Ci+1 = G+ PiCi

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

Answer:

Related questions

24 votes
24 votes
7 answers
1
113 votes
113 votes
20 answers
2
Sandeep Singh asked Feb 12, 2016
51,681 views
We want to design a synchronous counter that counts the sequence $0-1-0-2-0-3$ and then repeats. The minimum number of $\text{J-K}$ flip-flops required to implement this ...
34 votes
34 votes
9 answers
3
Sandeep Singh asked Feb 12, 2016
12,128 views
The $16\text{-bit}\;2's$ complement representation of an integer is $1111 \quad 1111 \quad 1111 \quad 0101;$ its decimal representation is ____________
68 votes
68 votes
7 answers
4