Carry look ahead


#1


#2

Let for N=64
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 log64.

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