• coolmoniker
In summary: Apparently it's possible, but I can't do it in less than six. There must be some trick or logic identity to exploit.
coolmoniker

## Homework Statement

I have a book which says that the gate delay for generating Ci is 2 logr(n) + 1, where r is the fan-in for each gate and n is the number of bits.

This implies that with a fan-in of 2 and 4 bits, the delay for a generating C5 as shown below should be 5 gate delays. How is this possible?

## Homework Equations

For an n-bit carry lookahead adder, it is well known that the carry out can be determined by examining the 'carry propagate' and 'carry generate' for each of the inputs. This allows the carry out to be expressed solely in terms of the input bits and carry-in.

As an example, the carry-out for a four bit adder is given by:

C5 = G4 + P4G3 + P4P3G2 + P4P3P2G1 + P4P3P2P1C

Where
C is the carry in,
Carry propagate Pi = Ai + Bi,
Carry generate Gi = AiBi

## The Attempt at a Solution

Initially:
We have the inputs
C,
A1,
B1,
A2,
B2,
A3,
B3,
A4,
B4

After one gate delay:
The carry-propagate and carry generate for each bit can be determined. So we have
C,
G1,
P1,
G2,
P2,
G3,
P3, G4, P4

After two gate delays:
We can use 'and' to start the carry propagates and carry generates together. So we have

P4G3,
P4P3,
P2G1,
P2P1

After three gate delays:
Now we can use 'or', and also continue 'anding' together the propogates
So
G4 + P4G3,
P4P3G2,
P4P3P2G1,
P4P3P2P1

After four gate delays:

G4 + P4G3 + P4P3G2,
P4P3P2G1,
P4P3P2P1C

After five gate delays:
G4 + P4G3 + P4P3G2 + P4P3P2G1,
P4P3P2P1C

This is too slow. There is still more work to be done as we need another 'OR' to put the two remaining terms together.

How is it possible to determine the carry out in only five gate delays?

I only skimmed the question, but why are you constrained to 2-input AND logic?

berkeman said:
I only skimmed the question, but why are you constrained to 2-input AND logic?

That's the difficulty...The book states that Ci can be found in 2 logr(n) + 1 delays, where r is the number of inputs for each gate. So for 2 inputs and 4 bits, that's 5 delays.

Apparently it's possible, but I can't do it in less than six. There must be some trick or logic identity to exploit.

A carry lookahead adder is a type of digital circuit used for addition in computers. It is designed to reduce the time it takes to perform addition by using a lookahead carry generator to predict the carry bits in advance.

A carry lookahead adder works by using a lookahead carry generator to predict the carry bits for each stage of the addition. The carry bits are then combined with the input bits using logic gates to produce the final sum.

The main advantage of a carry lookahead adder is that it reduces the time it takes to perform addition, making it more efficient for use in computers. It also allows for the addition of larger numbers without increasing the number of stages in the circuit.

## 4. Are there any limitations to using a carry lookahead adder?

One limitation of a carry lookahead adder is that it requires more circuitry and logic gates than a traditional ripple carry adder. This can make it more complex and expensive to implement in some cases.

A carry lookahead adder is different from other types of adders, such as ripple carry adders, because it uses a lookahead carry generator to predict the carry bits in advance. This allows for faster addition and the ability to add larger numbers without increasing the number of stages in the circuit.

• Set Theory, Logic, Probability, Statistics
Replies
3
Views
944
• Programming and Computer Science
Replies
1
Views
754
• Engineering and Comp Sci Homework Help
Replies
2
Views
1K
• Engineering and Comp Sci Homework Help
Replies
1
Views
11K
• Engineering and Comp Sci Homework Help
Replies
1
Views
2K
• Engineering and Comp Sci Homework Help
Replies
6
Views
5K
• Engineering and Comp Sci Homework Help
Replies
1
Views
5K
• Engineering and Comp Sci Homework Help
Replies
1
Views
5K
• Electrical Engineering
Replies
4
Views
3K
• Engineering and Comp Sci Homework Help
Replies
2
Views
2K