Register Blogs FAQ Members List Today's Posts Search Today's Posts Mark Forums Read

 Homework Help Stuck on a textbook question or coursework? Cramming for a test and need help understanding something? Post your questions and attempts here and let others help.

#1
04-24-2012, 03:37 PM
 squashbuddy New Member Join Date: Apr 2012 Posts: 2
Gate delay in 4-bit ripple-carry full adder

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[i],B[i] -> S[i] = 6 gate delays
A[i],B[i] -> Cout = 5 gate delays
Cin -> S[i] = 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.

#2
04-24-2012, 08:37 PM
 WBahn Senior Member Join Date: Apr 2012 Location: Larkspur, Colorado Posts: 8,072 Blog Entries: 9

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).
#3
04-24-2012, 10:38 PM
 squashbuddy New Member Join Date: Apr 2012 Posts: 2

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.
#4
04-25-2012, 12:05 AM
 WBahn Senior Member Join Date: Apr 2012 Location: Larkspur, Colorado Posts: 8,072 Blog Entries: 9

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.
#5
04-25-2012, 08:59 PM
 Jeff88 New Member Join Date: Apr 2012 Posts: 1

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.
#6
04-26-2012, 12:02 AM
 WBahn Senior Member Join Date: Apr 2012 Location: Larkspur, Colorado Posts: 8,072 Blog Entries: 9

Quote:
 Originally Posted by Jeff88 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.
#7
06-23-2012, 10:50 PM
 rmcghee New Member Join Date: Jun 2012 Posts: 1
I agree with WBahn

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

 Tags 4bit, adder, delay, gate, ripplecarry

 Related Site Pages Section Title Worksheet Boolean algebra Worksheet Counters Worksheet Flip-flop circuits Worksheet CMOS logic gates Worksheet TTL logic gates Textbook ``Long'' and ``short'' transmission lines : Transmission Lines Textbook Serial-in/serial-out shift register : Shift Registers Textbook A Full-Adder : Combinational Logic Functions Textbook NAND gate S-R flip-flop : Digital Integrated Circuits

 Similar Threads Thread Thread Starter Forum Replies Last Post arwayeyen Homework Help 12 03-05-2012 02:10 PM knowledge8069 Programmer's Corner 0 05-08-2009 10:57 PM bigbigblue General Electronics Chat 31 09-07-2007 10:28 AM anaki73 Homework Help 15 08-16-2007 08:22 AM rds1975 Homework Help 2 04-30-2007 05:50 PM

 Thread Tools Display Modes Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is Off Forum Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home Electronics Forums     General Electronics Chat     The Projects Forum     Homework Help     Electronics Resources Software, Microcomputing, and Communications Forums     Programmer's Corner     Embedded Systems and Microcontrollers     Computing and Networks     Radio and Communications Circuits and Projects     The Completed Projects Collection Abstract Forums     Math     Physics     General Science All About Circuits Commmunity Forums     Off-Topic     The Flea Market     Feedback and Suggestions

All times are GMT. The time now is 07:47 AM.