The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+21 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:

- 6, 3
- 10, 4
- 6, 4
- 10, 5

+28 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 3rd stage OR carry is generated in 2nd stage AND propagated to 3rd stage OR carry is generated in 1st stage AND carry is propagated through 2nd AND 3rd stage OR carry is generated in 0th stage AND propagated through 1st,2nd AND 3rd stage OR initial carry is propagated through 0th, 1st ,2nd AND 3rd 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

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 3rd stage OR carry is generated in 2nd stage AND propagated to 3rd stage OR carry is generated in 1st stage AND carry is propagated through 2nd AND 3rd stage OR carry is generated in 0th stage AND propagated through 1st,2nd AND 3rd stage OR initial carry is propagated through 0th, 1st ,2nd AND 3rd 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

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.

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

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

C_{i+1}=G_{i}+P_{i}C_{i}

So:

C_{1}=G_{0}+P_{0}C_{0 }

C_{2}=G_{1}+P_{1}C_{1}

C_{3}=G_{2}+P_{2}C_{2}

C_{4}=G_{3}+P_{3}C_{3}

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.

The output of carry generator is C_{4} 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.

[EDIT]:

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:

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.

**C _{1}** =

If we calculate this way, No of AND gate required is 6 and No of OR gate required is 3. Like - https://gateoverflow.in/1294/gate2006-36

Can anyone comment on this plz?

yes, what I chked

http://cs.umw.edu/~finlayson/class/spring16/cpsc305/notes/09-lookahead.html

where C-1 also exists

So, also have some value

right?

http://cs.umw.edu/~finlayson/class/spring16/cpsc305/notes/09-lookahead.html

where C-1 also exists

So, also have some value

right?

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

https://gateoverflow.in/1294/gate2006-36

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

+5 votes

let the carry input be c0

Now,

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.

Now,

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.

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.7k
- Digital Logic 1.9k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.7k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 835
- Others 1.2k
- Admissions 263
- Exam Queries 390
- Tier 1 Placement Questions 17
- Job Queries 50
- Projects 6

33,593 questions

40,128 answers

114,021 comments

38,389 users