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

In a look-ahead carry generator, the carry generate function $G_i$ and the carry propagate function $P_i$ for inputs $A_i$ and $B_i$ are given by:

$$P_i = A_i \oplus B_i \text{ and }G_i = A_iB_i$$

The expressions for the sum bit $S_i$ and the carry bit $C_{i+1}$ of the look ahead carry adder are given by:

$$S_i = P_i \oplus C_i \text{ and } C_{i+1} = G_i + P_iC_i, \text{ where }C_0 \text{ is the input carry}.$$

Consider a two-level logic implementation of the look-ahead carry generator. Assume that all $P_i$ and $G_i$ are available for the carry generator circuit and that the AND and OR gates can have any number of inputs. The number of AND gates and OR gates needed to implement the look-ahead carry generator for a 4-bit adder with $S_3, S_2, S_1, S_0$ and $C_4$ as  its outputs are respectively:

  1. $6, 3$
  2. $10, 4$
  3. $6, 4$
  4. $10, 5$
asked in Digital Logic by Veteran (52k points)
edited by | 3.1k views

Assume that all $P_i$ and $G_i$ are available for the carry generator circuit and that the AND and OR gates can have any number of inputs.

Instead of any number of inputs if it was given as only 2 inputs to any gate allowed. What would have been the answer?


1)all Pi and Gi are available for the carry generator circuit

 2)the AND and OR gates can have any number of inputs.

We have to find the number of AND gates and OR gates needed to implement the look-ahead carry generator ?

just write equation in simple term and calculate AND  & OR

3 Answers

+36 votes
Best answer
$C1 = G0 + C0.P0$

$C2 = G1 + G0.P1 + C0.P0.P1$

$C3 = G2 + G1.P2 + G0.P1.P2 + C0.P0.P1.P2$

$C4 = G3 + G2.P3 + G1.P2.P3 + G0.P1.P2.P3 + C0.P0.P1.P2.P3$  // read this as carry is generated in $3^{rd}$ stage OR carry is generated in $2^{nd}$ stage AND propagated to $3^{rd}$ stage OR carry is generated in $1^{st}$stage AND carry is propagated through $2^{nd}$ AND $3^{rd}$ stage OR carry is generated in 0th stage AND propagated through $1^{st}$ $2^{nd}$ AND $3^{rd}$stage OR initial carry is propagated through $0^{th}$, $1^{st}$, $2^{nd}$AND $3^{rd}$stage.

$4$ OR gates are required for $C1, C2, C3, C4$

$1$ AND gate for $C1$

$2$ AND gate for $C2$

$3$ AND gate for $C3$

$4$ AND gate for C4

AND $= 10$

OR $= 4$

Correct Answer: $B$
answered by Boss (13.2k points)
edited by
but why we are not taking gates required for Sum?
Question asks GATES required for Carry-Generator only. This is the part of Look-Ahead Adder that is responsible for Generating CARRY only. Sum part is handled by ADDER part of the circuit.
@thanks sandy
Can you please explain how we got 4 OR gates? Like at every stage we need 1AND and 1OR gate. At 4th stage only we will need four OR Gates- 1 fit carry generated at each stage. So total gates will be 10.

But that's not the answer. Please help me understand this



So total 4 OR gates. What you are doing is expanding it. You dont need to use an extra OR again since you have already calculated Ci in the previous step.

Then who u r getting 10AND gates. it should be only 4

The output of carry generator is C4 only i.e.

C4 = G3 + G2.P3 + G1.P2.P3 + G0.P1.P2.P3 + C0.P0.P1.P2.P3

which requires 4 OR gates and 10 AND gates.


I just misinterpretted the question.

As the question says, there can be any no. of inputs to AND and OR gates thus the solution will be:


@GATE-17 Aspirant  

NO, How can you calculate Sum expressions without carries ?
See this, $S_i = P_i \oplus C_i$, it requires "$C_i$".

You might have missed one important line in question "AND and OR gates can have any number of inputs".
Now you see the answer again, you will get to know appreciate his efforts :)

Multi-input OR gates (and not unexpanding). In unexpanding, you're doing simple ripple full adder as you are propagating carry of previous output. Whole point of CLA is to get rid of all propagate and express in terms of first carry-in.

there is mistake here, C2 = G1 + G1.P0 + C0.P0.P1  it should be c2 = G1+G0P1+C0P0P1


yes edited ..

design should be like this


C1 = G0 + P0C0 = G0. As C0 is 0 always. So, C0.P0 will always be 0. 

If we calculate this way, No of AND gate required is 6 and No of OR gate required is 3. Like - 

Can anyone comment on this plz?

yes, what I chked
where C-1 also exists
So, also have some value

Yes, this is default configuration.But in the below question we've assumed it as 0.

If we consider it 0, we would need minimum no of gates.Wandering, when to consider it and when to not.


@Sachin  can you edit the answer and add your comment in the answer part to understand why are we considering the AND and OR gate of C0,C1,C2,C3 also. 

But since the question says that the output are s0 s1 s2 s3 and c4... Does it not mean that s0 to s3 also have to be considered here since they are given to be outputs of the ckt.... I. E the must have been generated by d very same ckt....since they are clearly not one of the inputs...
+10 votes
let the carry input be c0


c1 = g0 + p0c0 = 1 AND, 1 OR
c2 = g1 + p1g0 + p1p0c0
   = 2 AND, 1 OR

c3 = g2 + p2g1 + p2p1go + p2p1p0c0
   = 3 AND, 1 OR
c4 = g3 + p3g2 + p3p2g1 + p3p2p1g0 + p3p2p1p0c0
   = 4 AND, 1 OR

So, total AND gates = 1+2+3+4 = 10 , OR gates = 1+1+1+1 = 4

So as a general formula we can observe that we need a total of ” n(n+1)/2 ” AND gates and “n” OR gates for a n-bit carry look ahead circuit used for addition of two binary numbers.
answered by Active (4.7k points)
Why not 4 and gates be used here as every equation has only 1 and operation and 1 or operation ,

C1=g0+c0p0, 1 and gate

C2=g1+c1p1, 1 and gate as c1 is already available

Same way for other gates also
The question says that it is a 2 level implementation.

Also, in Look Ahead Carry Adder, all the carries are generated simultaneously. If we believe that C2 = G1 + C1.P1 & it requires 1 AND, 1 OR gate only, how did you get C1 ? For Ci+1 only Gi & Pi are available, not Ci ( otherwise it would be just same as Ripple adder ).
0 votes

In a carry look ahead adder if we ignore input size of a gate, then to add two n bit numbers using CLA the total no of AND and OR gate required are as follows:

for C1= 1 OR + 1 AND; AS C1=C0*P0+G0

for C2=1 OR + 2 AND ; AS C2=C1*P1+G1=C0*P0*P1+G0*P1+G2

for C3=1 OR + 3AND;


for Cn=1 OR + n AND

so total no of OR gates reduired is = n

and total no of AND gates required is = 1+2+3+....+n=n(n+1)/2

answered by (101 points)

Related questions

0 votes
1 answer
asked Nov 15, 2018 in Digital Logic by Na462 Loyal (6.6k points) | 66 views
0 votes
1 answer
asked Oct 1, 2018 in Digital Logic by Na462 Loyal (6.6k points) | 113 views
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,541 questions
54,084 answers
70,994 users