The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+17 votes

An N-bit carry lookahead adder, where $N$ is a multiple of $4$, employs ICs $74181$ ($4$ bit ALU) and $74182$ ( $4$ bit carry lookahead generator).

The minimum addition time using the best architecture for this adder is

  1. proportional to $N$

  2. proportional to $\log N$

  3. a constant

  4. None of the above

asked in Digital Logic by Veteran (52k points)
edited by | 2.6k views

In CLA we know

generate (G)= AB

Propagate (P)= A EXOR

Bits to be added n.

Now to get the carries of look ahead adder in one go, we need fan in of exactly n+1 to AND and OR gates to calculate carry in O(1) time otherwise if fan in is less than n+1 we need $\log (n+1)$ (base=fan in).  

Here our fan in is 4 as we have given those two circuit to carry out the task.

Therefore it will be log (n+1) base 4

5 Answers

+24 votes
Best answer
For N = $64$ $bits$.

Suppose you want to build a $64$ $bit$ adder then you need $16$ $4$-$bit$ ALU and $16$ $4$-$bit$ carry generator, at this point there will be $16$ carries that will ripple through these $16$ ALU modules, to speed up the adder we need to get rid of these $16$ rippling carries, now we can again use $4$ $4$-$bit$ carry generator to generate these $16$ carries, now we have only $4$ carries to ripple through, again we can use the same trick to minimize the rippling of these $4$ carries, we can use an additional $4$-$bit$ carry generator which will generate these carry and we are done :) there will be no more propagation of carry among the ALU modules.

So, the we have used $3$ level of $4$-$bit$ carry generator, and the time taken to add $64$ $bits$ will be proportional to $3$ which is log464.

So, in general to add N-bits it takes Log4N time.

Correct Answer: $B$
answered by Boss (13.2k points)
edited by
I get that you'll need sixteen 4-bit ALUs to add two 64 bit numbers, and that sixteen 4-bit look-ahead carry generators can be used for generating the carries for each of those ALUs. But how do you reduce those sixteen carries to four carriers using another level of carry generators when each generator takes only one carry (Cn) as an input and the rest of its inputs are bits of the numbers that have to be added, and outputs Cn+4?
Please clear above doubt
What is the use of ALU??
@arjun sir please clear @alakyadav's doubt.
I too think that its not possible to eliminate rippling of carry generated at most significant bits of one 4 bit adder to next adder. Someone please explain.
Not a ble to understand the answer:(

I was also didn't able understand the using and workings of CLA levels at first time. Later I realized those are used to get the final carry. I drew a rough diagram, hope it will help understanding this. Correct me if I'm wrong.

Can we reason like this: We have 4 bit carry looahead generators, to generate carries we need sum of all 4 bits which can be obtained in one shot. But since we have N bits to add, the number of bits to add will decrease by 4 times in every step. Hence log4N.
+2 votes
answer - B
answered by Loyal (8.7k points)
0 votes

answer is c

cla contains two stages

1. carry generation stage

2.sum generation stage

it provides constant time for addition

answered by Active (4.7k points)

​​​​not in this case, the adder are in 4 bit segment, so we will need to design a hybrid adder with levels, the levels are dissected at a rate of 4 as the N is multiple of 4

read the summary here, so it will be a log N base 4 time

Still not able to understand the level wise implementation of CLAs. Somebody please explain in detail.
0 votes
answered by Junior (677 points)
edited by
–2 votes
Answer a)

Parallel processing is not possible here, carry of the current generator depends on the previous one.
answered by Junior (895 points)

but for efficient implementation if we use FAN-IN=2 then it will be $O(logn)$ still answer is B)


Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,535 questions
54,122 answers
71,040 users