All About Circuits Forum  

Go Back   All About Circuits Forum > Electronics Forums > Homework Help

Notices

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.

Reply   Post New Thread
 
Thread Tools Display Modes
  #1  
Old 04-24-2012, 03:37 PM
squashbuddy squashbuddy is offline
New Member
 
Join Date: Apr 2012
Posts: 2
Default 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.


Reply With Quote
  #2  
Old 04-24-2012, 08:37 PM
WBahn WBahn is offline
Senior Member
 
Join Date: Apr 2012
Location: Larkspur, Colorado
Posts: 8,072
Blog Entries: 9
Default

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

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

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.
Reply With Quote
  #5  
Old 04-25-2012, 08:59 PM
Jeff88 Jeff88 is offline
New Member
 
Join Date: Apr 2012
Posts: 1
Default

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

Quote:
Originally Posted by Jeff88 View Post
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.
Reply With Quote
  #7  
Old 06-23-2012, 10:50 PM
rmcghee rmcghee is offline
New Member
 
Join Date: Jun 2012
Posts: 1
Default 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
Reply With Quote
Reply   Post New Thread

Tags
, , , ,


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
Two 4-bit Binary Adder using SPDT switches and only 1 Full Adder Circuit arwayeyen Homework Help 12 03-05-2012 02:10 PM
Carry save adder Verilog help knowledge8069 Programmer's Corner 0 05-08-2009 10:57 PM
H Bridge High Side Mosfet Driver bigbigblue General Electronics Chat 31 09-07-2007 10:28 AM
How do I implement an 8-1 multiplexer in a full adder? anaki73 Homework Help 15 08-16-2007 08:22 AM
Full adder rds1975 Homework Help 2 04-30-2007 05:50 PM

Thread Tools
Display Modes

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 Jump


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


User-posted content, unless source quoted, is licensed under a Creative Commons Public Domain License.
Powered by vBulletin
Copyright ©2000 - 2014, vBulletin Solutions, Inc.