General Question About Logic Design

Thread Starter

Nikos Theodosiadis

Joined Jun 18, 2019
10
Hey everyone,first post here. Really cool site,it has helped a lot so far.
So i'm an electrical engineering student,currently ending my 1st year out of 5.
Recently i noticed something interesting in logic design course. Most - easy to think of - circuits ,to build what you want,are also very bad from number of gates perspective . So hopefully sometimes there are alternative designs which have less gates but are of course harder to understand . So my question is : how people come up with these alternative designs ? I know they can use different kind of methods like K map when it comes to sequential circuits but it doesn't really seem that helpful in sequential . For example one way to make an edge triggered D flip-flop is to implement the Master-Slay design,but there's another way which uses only 6 instead of 10 gates . How would someone come up with these ?

Thanks in advance for your time .
 

WBahn

Joined Mar 31, 2012
29,978
Hey everyone,first post here. Really cool site,it has helped a lot so far.
So i'm an electrical engineering student,currently ending my 1st year out of 5.
Recently i noticed something interesting in logic design course. Most - easy to think of - circuits ,to build what you want,are also very bad from number of gates perspective . So hopefully sometimes there are alternative designs which have less gates but are of course harder to understand . So my question is : how people come up with these alternative designs ? I know they can use different kind of methods like K map when it comes to sequential circuits but it doesn't really seem that helpful in sequential . For example one way to make an edge triggered D flip-flop is to implement the Master-Slay design,but there's another way which uses only 6 instead of 10 gates . How would someone come up with these ?

Thanks in advance for your time .
Point of clarification -- K-maps are useful for one type of minimization of combinatorial logic, not sequential. We often use it when designing sequential circuits, but we principally use it on the combinatorial excitation logic.

As to your main question -- engineering is both an art and a science (the art is learning from your own mistakes while the science is learning from the mistakes of others). There are some techniques that can be learned and applied to some types of circuits, but to get the most out of circuits you need to have enough experience with enough different types of problems to be able to call on that experience and spot how some aspect of one problem can be applied to another. This is greatly aided by having a strong fundamental understanding of the concepts in your field and the why and how different things work instead of just what they do.

You also need to develop the ability to clearly break down and describe what you are trying to accomplish and what the actual requirements are and to do so in such a way that you have a model that you can play with.

Having a broad range of experience also helps tremendously -- I forget the details, but one major advancement in digital electronics stemmed from the person applying some concepts from embroidery (or something similar) as far as how patterns are encoded for others to follow. When I first started designing fully asynchronous digital circuits my primary guide was how the hydraulic sequencing events are accomplished on the F-15 main landing gear extension and retraction systems. For a large fraction of the problems you will face, many other people from many fields of endeavor have developed extremely elegant solutions to essentially the same underlying problem over many centuries (and sometimes millenia). The more exposure you have to as many of those as possible, the more full your tool bag of tricks will be.
 

Thread Starter

Nikos Theodosiadis

Joined Jun 18, 2019
10
Point of clarification -- K-maps are useful for one type of minimization of combinatorial logic, not sequential. We often use it when designing sequential circuits, but we principally use it on the combinatorial excitation logic.

As to your main question -- engineering is both an art and a science (the art is learning from your own mistakes while the science is learning from the mistakes of others). There are some techniques that can be learned and applied to some types of circuits, but to get the most out of circuits you need to have enough experience with enough different types of problems to be able to call on that experience and spot how some aspect of one problem can be applied to another. This is greatly aided by having a strong fundamental understanding of the concepts in your field and the why and how different things work instead of just what they do.

You also need to develop the ability to clearly break down and describe what you are trying to accomplish and what the actual requirements are and to do so in such a way that you have a model that you can play with.

Having a broad range of experience also helps tremendously -- I forget the details, but one major advancement in digital electronics stemmed from the person applying some concepts from embroidery (or something similar) as far as how patterns are encoded for others to follow. When I first started designing fully asynchronous digital circuits my primary guide was how the hydraulic sequencing events are accomplished on the F-15 main landing gear extension and retraction systems. For a large fraction of the problems you will face, many other people from many fields of endeavor have developed extremely elegant solutions to essentially the same underlying problem over many centuries (and sometimes millenia). The more exposure you have to as many of those as possible, the more full your tool bag of tricks will be.
Thanks for taking the time to answer .
You're pretty clear about what you want to say and i really like your perspective of the field .
I will try to stick with your advices, and if i understood correctly the key idea here is being exposed to as many different problems as you can possibly be ,right ? I thought it would be easy,but to my surprise digital electronics are not a piece of cake,they have their challenges too .
Asynchronous must be harder to analyse than sychronous,we didn't really bother with those . I will be happy to study them more though.
Do you mean you had in your mind the actual landing system of the f-15 or just as a visual guide to better understand the material ?

The course itself actually emphasizes more on knowing what the components do rather how they work,or how you could make them work better ,at least for sequential circuits . But i guess that's normal,not everybody would like to study these stuff in more depth at this level . So i guess i should not be discouraged having hard time to understand the "smarter" designs.It just takes time and lots of practise to get good at ?
 

WBahn

Joined Mar 31, 2012
29,978
Do you mean you had in your mind the actual landing system of the f-15 or just as a visual guide to better understand the material ?
The electronic problem that I had to solve was how to respond to a short transient event in a circuit that had no clock (and couldn't have one because of the noise issues involved) that had to trigger a sequence of events in such a way that I could be sure that each event in the sequence was guaranteed to happen. The landing gear of the F-15 solved a similar problem (though the better analogy is actually the wing-root switching valve, but the landing gear was what came to mind). In either case, the analogy wasn't perfect, but it got me to thinking about how the various events could communicate such that one event would assert the activation signal for the next event until that next event informed it that it had actually acted upon that signal.The result was a tiny little circuit that could be chained together to control the process. It also had some similarities to a token-passing scheme I had come up with many years earlier for a very different problem that shared some of the same elements.
 

Thread Starter

Nikos Theodosiadis

Joined Jun 18, 2019
10
The electronic problem that I had to solve was how to respond to a short transient event in a circuit that had no clock (and couldn't have one because of the noise issues involved) that had to trigger a sequence of events in such a way that I could be sure that each event in the sequence was guaranteed to happen. The landing gear of the F-15 solved a similar problem (though the better analogy is actually the wing-root switching valve, but the landing gear was what came to mind). In either case, the analogy wasn't perfect, but it got me to thinking about how the various events could communicate such that one event would assert the activation signal for the next event until that next event informed it that it had actually acted upon that signal.The result was a tiny little circuit that could be chained together to control the process. It also had some similarities to a token-passing scheme I had come up with many years earlier for a very different problem that shared some of the same elements.
Hey sorry for the late reply,i'm having my exams for this semester around this period.
Sounds pretty interesting . So digital systems with lots of noise are better to be asychronous ? How long did it take until you were comfortable enough for solving such problems,and if i may ask what was the project about?
 

MrChips

Joined Oct 2, 2009
30,708
@WBahn said it well.

You will benefit from (1) knowledge and (2) experience.
It is not about combinational vs sequential circuitry. It is not about asynchronous vs synchronous circuit design. You have to learn the fundamentals of it all and then gain the experience by applying that knowledge.

When does one start being proficient with this knowledge? 2 - 4 years would be my estimate.
 

dl324

Joined Mar 30, 2015
16,845
For example one way to make an edge triggered D flip-flop is to implement the Master-Slay design,but there's another way which uses only 6 instead of 10 gates .
If you want us to compare two different implementations of D flip flops, post the schematics so we don't have to guess at what you're referring to.

Some constructive criticism. Using paragraphs to organize your thoughts would be helpful.
 

Thread Starter

Nikos Theodosiadis

Joined Jun 18, 2019
10
@WBahn said it well.

You will benefit from (1) knowledge and (2) experience.
It is not about combinational vs sequential circuitry. It is not about asynchronous vs synchronous circuit design. You have to learn the fundamentals of it all and then gain the experience by applying that knowledge.

When does one start being proficient with this knowledge? 2 - 4 years would be my estimate.
Hey,thanks for answering .
I was quite specific there . The thing is ,everything was totaly fine,until we got into sequential circuits . It got a little bit more complex for me there than what combinatorial was ,and i got worried if it is my fault i don't fully understand them or it's just i'm inexperienced.

Two to four years of regular practise ? I see . Could you please suggest some good projects ideas or ways that would help gain some good insight of logic design ?

If you want us to compare two different implementations of D flip flops, post the schematics so we don't have to guess at what you're referring to.

Some constructive criticism. Using paragraphs to organize your thoughts would be helpful.
Hello,i'm really sorry if you had trouble reading my post,i will try be more clear .
Yes,i can provide an example. So my question is basically how would someone from this design :



Would think that's an alternative way to do it,with less gates .
How can he be sure if there is in first place an alternative to even bother trying it?
Even if there is one,or you assume there is one,how you would work your way to end up with something like this :

 

WBahn

Joined Mar 31, 2012
29,978
Hey,thanks for answering .
I was quite specific there . The thing is ,everything was totaly fine,until we got into sequential circuits . It got a little bit more complex for me there than what combinatorial was ,and i got worried if it is my fault i don't fully understand them or it's just i'm inexperienced.

Two to four years of regular practise ? I see . Could you please suggest some good projects ideas or ways that would help gain some good insight of logic design ?



Hello,i'm really sorry if you had trouble reading my post,i will try be more clear .
Yes,i can provide an example. So my question is basically how would someone from this design :



Would think that's an alternative way to do it,with less gates ?
How can he be sure if there is in first place an alternative to even bother ?
Even if there is one,or you assume there is one,how you would work your way to end up with something like this :

These are two pretty different approaches to designing a flip flop. Both use a master-slave topology, but the second one uses two flip flops in the master and a type of internal handshaking in order to automatically remove the sensitivity to the clock once the signals propagate through the first latch.

One thing that can help you out is to first understand, in detail, how both of these circuits work. The best way that I know of to do that is to draw a detailed state diagram of the circuit. For the states, you need to identify the storage nodes for the circuit, but that's pretty simple -- any node that is feeding backward is an obvious candidate. In the top one it is the output of each of the NOR gates, so you have four state variables. You need each output to be a separate state variable because the outputs of the flip flops are not guaranteed to always be opposite each other. For the bottom one the output of each NAND gate is a state variable -- that's 64 possible states, but you will discover that many of them are unreachable, so it's not as bad as it seems at first.

For each state you have four input combinations that you need to consider (forget that the clock is a "clock", it is simply one of two input signals -- a sequential circuit that has no clock is sometimes referred to as a "fundamental mode machine"), but you only need to consider one signal changing at a time, so each state only has two arrows leaving it. So walk through the logic and determine which state each input combination leads to. What you will discover, particularly in the case of the bottom one, is that a particular input combination often leads to a state that is not stable for that input combination. That's fine -- it simply immediately continues on to the next state. You will probably also find that for some states more than one internal signal changes in response to a change in one of the inputs. You need to consider all of the possible sequences. So if three signals change, then you need to consider eight possibilities. Those may not all lead to the same state, but as long as the external behavior is the same for each path, that's all that matters (well, in theory you could get some timing differences, but those seldom matter). These paths are called non-critical races. If the external behavior isn't the same, then you have a critical race condition and this is unacceptable -- you either must make changes to the design topology or ensure that the implementation ensures that only the design path can win the race (this is often accomplished by putting delay elements, such as two inverters in series, into the paths you need to have lose).

Once you have the state diagram, partition it into sections that perform the expected behavior of the circuit. The first obvious partition is to put all states that have the Q output being 0 on top of a horizontal dividing line and all of the ones that have the Q output being 1 below it. The other partitions will be dictated by what happens as each input in changed -- the system should settle into one or more stable states after each change. Input changes from these states are the ones that can cross into another partition.

Once you have that, see if you can understand how the little automatic sequences involved (in the bottom one) result in the edge-triggered behavior of the circuit.

The design process works basically in the reverse. You decide what the big picture behavior you want is and use that to define your partitions. Then you come up with little sequences that either keep you in the desired partition of input changes that should not result in any change or move you into the correct partition for ones that should.
 

Analog Ground

Joined Apr 24, 2019
460
On Flip Flops

All the basic flip flops were worked out long ago and the definitive guide is looking at the gate level designs for TTL logic of the 74xxx series parts. I just took down the TI TTL Data Book from my shelf and, yep, they are still in there. They were designed as asynchronous sequential state machines. IMHO, the basic "cross-coupled" SR latch is about as far as one should go in understanding the guts of a flip-flop without having an understanding of asynchronous machines. Throw in asynchronous reset and clear and it all gets pretty complicated, pretty fast. Reverse engineering from the gate diagram is very difficult. Again, IMHO. Give it a try but don't get discouraged if you cannot do it. Now, it is my understanding that asynchronous machines are largely not taught anymore. So, there is a hill to climb to reach the time machine to take you back to a class when asynchronous design was common place.

Your interest is commendable but concentrate on your course work. Work through synchronous machines first. This was always a prerequisite to asynchronous machines. I will say it again, work through synchronous first. You are getting ahead of yourself.

On Simplification

You mention adding gates to enhance understanding. I have never heard of such a thing. Write the equations, reduce the logic and move on. Trust the boolean logic. Learn the techniques for preventing glitches, etc. Now, once you learn all this and pass your exams, forget it. Modern design software takes care of all this for you. Thank goodness.
 
Last edited:

MrChips

Joined Oct 2, 2009
30,708
Yes, don't be discouraged when you see 50-100 gates in an IC logic design.

The basic SR latch is the "cross-coupled" dual NAND circuit (or NOR circuit).
That is your starting point.
See this blog on Flip-Flop Fundamentals.

Master-slave flip-flops take advantage of this basic configuration for a given reason. Once you understand the feature of the master-slave flip-flop you can leave it at that. One never builds circuits like that unless you are the IC designer making flip-flops. For us ordinary mortals, we use the chips with the flip-flops already designed by the masters of the universe.
 

dl324

Joined Mar 30, 2015
16,845
how you would work your way to end up with something like this
The usual way; you build a circuit with whatever constraints you, or someone, wants to impose.

Here's a D flip flop (actually it's a latch) made with 3 inverters and 2 transmission gates (2 CD4007 IC's):
upload_2019-6-21_20-11-1.png
The MOSFETs with bubbles on the gates are P channel MOSFETs. A and B designate ICA and ICB. The numbers on the terminals are the IC pin numbers.

The constraint was that it had to be done with no more than 2 CD4007.
upload_2019-6-21_20-13-31.png
 
Last edited:

Thread Starter

Nikos Theodosiadis

Joined Jun 18, 2019
10
Thank you WBahn for writing such a detail description . It's really very much appreciated,
i believe it will help me a lot and it's quite informative :) .

Analog Ground, i guess you're right,i might have pulled it a little bit too far .
Thank you though for stressing what's important for me right now based on how things actually work in reality.
It's easy for me to get lost in the details sometimes, so i will take your word for it .

MrChips, so those people are kind of expertised or at least very experienced on making such components ?
My first reaction when saw those designs was those people must be paid quite a lot of money,for designing such things :p .

dl324,we haven't seen the logic designs be implemented in the physical level using mosfets(although he have been introduced to them) .
I suppose we will see this during digital design course ?

An other question that comes into my mind though is : how would one know if the constraints posed, are actually feasible ?
 

dl324

Joined Mar 30, 2015
16,845
we haven't seen the logic designs be implemented in the physical level using mosfets(although he have been introduced to them) .
I suppose we will see this during digital design course ?
I think most datasheets will give the circuit for the gate (at least RCA/TI and Motorola/OnSemi do).

A complication is that some manufacturers use DeMorganized gates. I read somewhere that RCA's strategy was to use DeMorganized gates when going from unbuffered logic to buffered.
An other question that comes into my mind though is : how would one know if the constraints posed, are actually feasible ?
That's where skill and experience come in.

It's like a puzzle. Some people can solve some easily while others struggle and never find a solution.

The first master-slave D FF you showed takes the equivalent of 38 MOSFETs. It can be done with 20 MOSFETs using inverters and transmission gates.
 
Top