The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+15 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 (59.6k points)
edited by | 2k views

4 Answers

+23 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.

answered by Boss (13.7k 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.

+2 votes
answer - B
answered by Loyal (9.1k 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 (5k 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.
–2 votes
Answer a)

Parallel processing is not possible here, carry of the current generator depends on the previous one.
answered by Junior (885 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

42,686 questions
48,650 answers
63,961 users