2.6k views

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

edited | 2.6k views
0

In CLA we know

generate (G)= AB

Propagate (P)= A EXOR

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

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$
edited
+5
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?
0
0
What is the use of ALU??
0
0
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.
+1
Not a ble to understand the answer:(
+1

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.

0
+2
0
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.

cla contains two stages

1. carry generation stage

2.sum generation stage

it provides constant time for addition

0

​​​​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

0
Still not able to understand the level wise implementation of CLAs. Somebody please explain in detail.
edited

Parallel processing is not possible here, carry of the current generator depends on the previous one.
+1

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

1
2
3
4
5
6