edited by
30,746 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

1 votes
1 votes

I know my answer is not interactive much but this explanation can help u understand the answer well

 First the time delay to calculate the value of P's and G's = 1 time delay(all P's and G's would be calculated parallely)

as Pi = Ai ex-or Bi and Gi = Ai.Bi

now sum at last would be calculated in 1 time delay as sum = Pi ex-or Ci ( all such ex-or's for S0, S1, .. would be done parallely)

So total time = 1(P's and G's) + carry generation time + 1(Pi ex-or Ci)

now carry generation time would be max for maximum carry as for 4 bits we need C4 and that will take max time

so time to generate carry = time to generate Cn for n bits

lets say n = 6

then C6 = g5+ P5G4 + P5P4G3 + P5P4P3G2 + P5P4P3P2G1 + P5P4P3P2P1G0 + P5P4P3P2P1P0C0

calculation will be done parallely so biggest term here P5P4P3P2P1P0C0 would take 3 time delay becoz 3 levels of calculation

2nd term = 1 time delay = ceil(log2(2))

3rd term = 2 time delay = ceil(log2(3))

4th term = 2 time delay = ceil(log2(4))

5th term = 3 time delay = ceil(log2(5))

6th term = 3 time delay = ceil(log2(6))

7 th term = 3 time delay = ceil(log2(7))

so max time delay in multiplication and some addition as well = 3 = ceil.log2(7) = ceil.log2(n+1)

Some addition would be performed  parallely as here in this example addition of any 2 terms of first 3 can be done in  parallely with in 3 time delays but what about all terms with 3 time delay they would take further time to add here max 4 terms can be there with 3 time delay that would take log2(4)- no of terms in max time delay here 3 max time

so how many max terms with ceil(log2(n+1)) = 2^(ceil(log2(n+1))-1)

now addition will be performed on these max terms that would take log2(maxterms) = ceil(log2(n+1) -1 time

so carry generation time = ceil(log2(n+1))+ ceil(log2(n+1))-1 = 2 ceil(log2(n+1)) -1

so total time = 2 ceil(log2(n+1))-1 +2

= 2ceil(log2(n+1)) +1

0 votes
0 votes

Most time consuming operation is generating last carry

in case of C$_4$ = g$_3$ + p$_3$g$_2$+ p$_3$p$_2$g$_1$+p$_3$p$_2$p$_1$g$_0$+p$_3$p$_2$p$_1$p$_0$c$_0$

among this most time consuming is 

p$_3$p$_2$p$_1$p$_0$c$_0$

it requires 2 AND gates and then 2 OR gates of FAN-IN 2 

similarly

then for generating C$_n$ we will require logn AND gates and logn OR gates

O(logn+logn)=O(logn)

 

0 votes
0 votes

Time Complexities of different adders : 

  • Ripple Carry – O(n)
  • Carry Select – O(√n)
  • Carry Lookahead Adder – O(log(n))
0 votes
0 votes
Imagine trying to add two massive numbers, bit by bit. In a traditional ripple carry adder, each addition step depends on the carry result from the previous one, creating a domino effect of delays. As the number of bits grows, so does the wait time, leading to a linear time complexity – $\Theta(n)$.

But, enter the carry lookahead adder (CLA), Instead of waiting for the ripples to settle, the CLA pre-calculates the carry signals for each addition stage, effectively cutting through the delay chain. This ingenious approach offers speedups, especially for large numbers.

Forget complex multi-input gates; the CLA shines with simple AND and OR gates, each limited to a mere two inputs – a design constraint with a surprising benefit. Instead of brute force, the CLA employs a hierarchical approach. At the base, all input bits and initial carry signals converge. Then, through successive levels, these signals are processed by the two-input gates, generating intermediate carry information. Each level effectively halves the number of signals needing further analysis, and hence, the number of levels is roughly $\log_2(n)$ (which simplifies to $\log n$). Here's where the logarithmic magic emerges. Each level adds a constant delay due to the simple gates. Multiplying this constant by the number of levels ($\log n$) gives us the overall time complexity for carry generation – $\Theta(\log n)$.
Answer:

Related questions

24 votes
24 votes
7 answers
1
113 votes
113 votes
20 answers
2
Sandeep Singh asked Feb 12, 2016
51,679 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,127 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