Hello everyone

I have tried searching the forums and the web and couldn't find a good explanation for the following problem:

Problem:
A full adder is implemented using 9 NAND gates as shown. For the NAND gate used, an input change on A will propagate to X in 3.4ps. An input change on B will propagate to X in 4.1ps. Wire delay is neglected.Use 4 set of the full adder design shown to form the fastest possible 4 bit ripple-carry adder! A and B on the NAND gate can be chosen freely in the design. Given that there are registers before and after the adder, each of them driven by exactly the same clock! Delay to and from the registers are set to 0ns.What is the minimum clock cycle-time (maximum frequency), where the adder will work correctly for all input value changes on {A[3:0], B[3:0], CIN} to form the result {S[3:0], COUT}?




Solutions:

• 43.6 ps
• 42.9 ps
• 39.5 ps
• 38.8 ps

Problem solving method:

What I've done for a start is counting the worst-case gate delays for each process.

A,B -> S = 6 gate delays
A,B -> Cout = 5 gate delays
Cin -> S = 3 gate delays
Cin -> Cout = 2 Gate delays

Because the carry-out of one stage is the next's input I found that the total amount of gate delays is:

6 gate delays for generating the first signal (A,B -> Cout)
2 gate delays per intermediate stage (Cin -> Cout)
3 gate delays for producing the sum and carry-out outputs (Cin -> S)

Total gate delays: 12

So what I am asking is if my method is correct. And how you guys would recommend I proceed.


Best regards,

NB: I should note that I've never done anything like this before and my field of study is completely different.

 

Read the problem carefully. It is not enough to just count gate delays, because the NAND gate is specified as being asymmetric. So it matters which side of the gates your worst case path is going through and you can't assume that you can design the circuit so that the worst case path always goes through the fastest NAND input.

Aside from that, you are overlooking something. In the last stage, is the Cout the last thing to change, or the S output?

I would recommend reworking the problem assuming that you have two types of gates, an F gate (fast) and an S gate (slow).

 

Thanks for the quick reply.

The circuit again:


I have revised my approach abit as you said. I have identified the different paths A -> Cout, B->Cout, Cin->Cout and Cin->S can follow.

I’ll use the following notation; UTF means approach gate U from top where top is configured as fast.
Cout is denoted C.

I have designed the orientation of the NAND gates in a way that causes the slowest of all the paths to be as fast as possible.

So looking at the initiation phase (A,B -> Cout) would the following be correct:

RED: A->Cout: TTF - UBF - WTF - XTS - CTF = 4*4.1 = 17.7 ps
BLUE: A->Cout: TTF - VTF - WBS - XTS - CTF = 3*3.4 + 2*4.1 = 18.4 ps

way1 B->Cout: TBS - UBF – WTF – XTS – CTF = 3*3.4 + 2*4.1 = 18.4 ps
way2 B->Cout: TBS – VTF – WBS – XTS – CTF = 2*3.4 + 3*4.1 = 19.1 ps

Intermediate phase (Cin -> Cout) times 2

Cin->Cout: XBF – CTF = 2*2*3.4 = 13.6 ps

Summation phase (Cin -> S)

GREEN: Cin->S: XBF – YBF – STF = 3*3.4 = 10.2 ps
ORANGE: Cin->S: XBF – ZTF – SBS = 2*3.4 + 4.1 = 10.9 ps


When the total delay is calculated is it correct to sum the slowest paths together?
Or can you, for example, in the last stage use the fastest path since the signal arrives at the same time at the S-gate but one of them is registered faster than the other?


Again thanks for the help. I really appreciate it.

 

It looks like you are mostly on the right path, but missing a few subtle things.

For instance, in your initiation phase, for Gate X, you have the Cin signal that goes direct to it and the other signals that take quite a bit of time. So you probably want to put the fastest input to Gate X in the slow path. It is very likely that you want to put it in the Cin path for the intermediate gates because the Cin signal will be delayed heavily from the prior stages. For the final stage you will have to determine which signal has the most delay at Gate X.

Now, an assumption being made here is that you get to assign the gate inputs differently in the different stages. The problem statement doesn't appear to preclude this, but it is very possible that the problem was meant to imply that you get to assign the gate inputs with the full adder, but that you have to use four identical full adders.

My guess, if you have a rational instructor, is that you could do it either way as long as you state what assumptions you are making and show that they are reasonable assumptions given the wording of the problem statement.

 

I had a very similar exercise last year.

You can state the delay of each NAND gate with logic. For instance, the delay through the gate you marked as T, would be max(A + t1, B + t2) where t1 is either 3.4ps or 4.1ps and t2 is the other. The problem is optimising the t1 and t2 values. If you look the system through, you will find that the first full adder takes 18.4ps to propagate from input to Cout. This only holds true for the first adder, as for the second adder and forth, the delay received from the Cin will greatly affect the output delay.

By the time you reach the fourth adder, you will find that it takes the signal 38.8ps to propogate to the output by my calculations.
Hope this helps.

Cheers,
Jeff.

 

By the time you reach the fourth adder, you will find that it takes the signal 38.8ps to propogate to the output by my calculations.

Please recheck your calculations. You may be right, but we don't get the same answer. In particular, be sure to check whether you are using the Cout or the S output of the final adder as your critical path.

Depending on which of the two assumptions I described earlier, I get:

If all four full adders must be identical, then the delay is 43.6ps. I would say that the problem statement strongly implies that this is the intended situation.

If each of the four adders can be optimized separately, then the delay is 42.9ps.

Since both of these are on the list, it is highly likely that the other two are also carefully chosen detractors intended to match common mistakes.

 

My understanding of the problem as stated is that I am free to optimize
the gates (so my first half-adder is slightly different from the others).

The gold path is the critical path (there's no faster way to get to that point
with all signals current). Once you've established the critical path, you
add up all delays along that path. Since the gates are the only propagation
delays (stated in problem), you sum to get: S+F+S+F+F+F+F+F+F+F+F+S
3 * 4.1 + 9 * 3.4 = 42.9 ps