1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Sequence detector, finite state machine circuit

  1. Aug 25, 2012 #1
    1. The problem statement, all variables and given/known data
    Please see the attached photo. (The one with the green highlighter), I haven't written it out to avoid mistakes.


    2. Relevant equations
    None.



    3. The attempt at a solution

    I have constructed a moore state diagram, a state transition table and come up with boolean expressions required for implementation. (Please have a look, it's very possible I've made a mistake somewhere there which is confusing me later).

    What I'm having trouble with is actually drawing the circuit (part d) . I've not really done a question like this with 2 inputs ? I assumed each input went into a different flip flop ? I'm also a little confused about the number of flip flops needed. Anyway, I've had a go (see picture), hope it's not too far off !

    Any help would, as always, be greatly appreciated.

    Many Thanks, Biren.
     

    Attached Files:

  2. jcsd
  3. Aug 25, 2012 #2
    My Boolean expressions and a slightly messy attempt at a solution (sorry). Usually to get these boolean expressions I'd use karnaugh maps, but what threw me here was that there are 5 variables (X0 X1 and the three Q's). That makes the karnaugh map pretty complicated.

    Instead I went by inspection from the state transition table. I've got a feeling that if there's a mistake leading up to part d) it's here !
     

    Attached Files:

  4. Aug 28, 2012 #3

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Normally I don't respond to a question where I have to look at 5 images to figure out what the problem is. But digital design is a hobby of mine so here I am.

    I don't understand your reluctance to use a K-map to solve this problem. You have 3 flip-flops giving 8 possible states, of which you only use 3. So the K-map is full of "don't cares". I haven't analyzed all your next state equations, but it is obvious that your next state equation for ##Q_2## is wrong. For example if you are in the starting state 001 with ##Q_2=0## the next state will have ##Q_2=1##, which is wrong since the next state will be either 001 or 010 depending on the inputs.
     
  5. Aug 29, 2012 #4
    Hi LCKurtz

    Really appreciate you helping me with my question and I apologise for all the images.

    I'm just starting out with Digital Electronics and haven't been taught ( or haven't taught myself ) how to simplify a boolean expression with 5 variables using a karnaugh map. That's why I tried to get the expressions straight from the state transition table.

    Could you recommend somewhere I could look to learn this?
     
  6. Aug 29, 2012 #5

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I really can't help you with the literature. What I know about digital electronics I learned by sitting in a class at the University of Kentucky 40 years ago, from which I kept my notes. Perhaps someone else will chime in with some current references for you.

    I would assume most classes now have a software simulator such as LogicWorks or similar with which you can check out your circuit.
     
  7. Aug 29, 2012 #6
    Right, I have read the relevant parts of my textbook on 5 variable karnaugh maps and have constructed one for Q1+. Do you mind having a look at it ? Also, you said my K-map would be full of don't cares, would you mind telling me why and where I would put them on my Kmap?

    I understand that my next state expressions were horribly wrong but with the 5 variable K map they now seem horribly complicated (hence the need for the don't cares) !

    Thanks !
     

    Attached Files:

  8. Aug 29, 2012 #7

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    With 3 flip-flops you have 8 states but you are using only 100,010,001, so the next state for any of the remaining states are don't cares. Here's my first row of the K-map. Notice that when we are in the 00 input situation the next state is always 001 from the state diagram.

    There may be better ways to do it, but I would set up my K-map like this (sorry I don't have time to make it look nice but you get the idea):$$
    \left|\begin{array}{ccccccccccccccccc}
    X_1X_0Q_2^+Q_1^+Q_0^+&|& 000&|& 001&|& 011&|& 010&|& 110&|& 111&|& 101&|& 100\\
    00&|&XXX&|&001&|&XXX&|&001&|&XXX&|&XXX&|&XXX&|&001\\
    01&|\\
    11&|\\
    10&|

    \end{array}\right |$$

    You can fill in the rest, then the fun begins. The wife is calling me for dinner.
     
    Last edited: Aug 29, 2012
  9. Aug 30, 2012 #8
    Haha, I see we're in very different time zones. You must be in the US ? I've only ever been to Orlando, lovely place. I'm studying in London, England :)

    Right, I haven't actually seen a 5 variable K map done like this but I understand how to fill it in, I think. I think I'm ready for the fun to begin !


    \left|\begin{array}{ccccccccccccccccc}
    X_1X_0Q_2^+Q_1^+Q_0^+&|& 000&|& 001&|& 011&|& 010&|& 110&|& 111&|& 101&|& 100\\
    00&|&XXX&|&001&|&XXX&|&001&|&XXX&|&XXX&|&XXX&|&001\\
    01&|&XXX&|&010&|&XXX&|&010&|&XXX&|&XXX&|&XXX&|&001\\
    11&|&XXX&|&010&|&XXX&|&010&|&XXX&|&XXX&|&XXX&|&001\\
    10&|&XXX&|&001&|&XXX&|&100&|&XXX&|&XXX&|&XXX&|&001\\

    \end{array}\right |$$
     
    Last edited: Aug 30, 2012
  10. Aug 30, 2012 #9

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    That's good. Now do the next state equations. Try ##Q_1^+,\, Q_2^+,\, Q_0^+## in that order. The first two are the easiest. Let's see what you get. You will be able to use lots of those don't cares, resulting in pretty simple equations.
     
  11. Aug 31, 2012 #10
    Thank You.

    I'm not really sure how to do the next state equations from the K map that we've constructed... If you could take me through the process of how to do one of them I'll be happy to have a stab at the the two ?

    Also, what we're saying here is that if we end up in an undefined state, such as 000, then we don't care what the next state is ? Could we not also say that if we do end up in an undefined state, we should map back to S1 (001) with XX as the input variables ?

    Once again, really appreciate your help !
     
  12. Aug 31, 2012 #11

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Do you know how to get next state equations from K-maps in general? If you don't, you are going to have to read about it because it's too much to explain here. You do this one the same as any other K map. Redraw the K map showing just the ##Q_1## outputs and its X's and draw the largest qualifying block containing the 1's and as many X's as appropriate.

    You could map all the unused states back to 001 but that would most likely make the circuit very complicated because you wouldn't have any don't cares. When you actually design such a circuit, you would use something like a power-on set/reset to make it start in the 001 state so the other states would never arise, so you really do not care where those other states would have gone.
     
  13. Sep 1, 2012 #12
    Okay so if I'm constructing the K map for Q1 then it looks something like this:

    X0 X1 | Q | 0 | 1 |
    0 0
    0 1
    1 1
    1 0

    So what I do is I look at when Q1 is 0 and what happens to it when I input a 00. From the big K map above, I can see that it is either a don't care or a 0, so should I be putting a 0 or a 1 in the corresponding place above ? I feel that I should put a 0 because in that case the output is never 1, whereas a don't care implies it could be 1 or 0.

    It's a little more confusing if we consider when Q1 is 0 and we input 01. In this case the resulting output could be a don't care, a 1, or a 0 depending on which state you're in. So I'm not sure what to put in my K map.

    If you could just clear that up for me I'll have these maps and equations constructed in no time ! Thanks a lot !
     
  14. Sep 1, 2012 #13

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    No, it doesn't look like that. You keep all the states but just show the next state output for ##Q_1## (the middle column in the outputs). I did the first row for you and it looks like this (you can finish it):$$
    \begin{array}{|c|c|c|c|c|c|c|c|c|}
    \hline
    X_1X_0Q_2Q_1Q_0& 000& 001& 011& 010& 110& 111& 101& 100\\
    \hline
    00&X&0&X&0&X&X&X&0 \\
    \hline
    01&XXX&010&XXX&010&XXX&XXX&XXX&001 \\
    \hline
    11&XXX&010&XXX&010&XXX&XXX&XXX&001 \\
    \hline
    10&XXX&001&XXX&100&XXX&XXX&XXX&001 \\
    \hline
    \end{array}$$
     
    Last edited: Sep 1, 2012
  15. Sep 1, 2012 #14
    Oh ok, right so it looks like this :

    $$
    \begin{array}{|c|c|c|c|c|c|c|c|c|}
    \hline
    X_1X_0Q_2Q_1Q_0& 000& 001& 011& 010& 110& 111& 101& 100\\
    \hline
    00&X&0&X&0&X&X&X&0 \\
    \hline
    01&X&1&X&1&X&X&X&0 \\
    \hline
    11&X&1&X&1&X&X&X&0 \\
    \hline
    10&X&0&X&0&X&X&X&0 \\
    \hline
    \end{array}$$[/QUOTE]
     
    Last edited: Sep 1, 2012
  16. Sep 1, 2012 #15
    So applying the same technique as I would in a 4 variable karnaugh map, I can make a group of 8 which gives me the equation Q1+ = XO.Q2
     
  17. Sep 1, 2012 #16

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Soooo close! But ##Q_2## is the right hand side of the table.
     
  18. Sep 1, 2012 #17
    Haha, don't worry I definitely meant Q1+ = X0.Q2'.
    I'm going to do the others in the morning (it's getting late here in the UK) and let you know how I get on !

    You are certainly right though in that this simplifies the circuit greatly. I had a go producing some equations where all undefined states map back to 001 and they were pretty complicated, which resulted in the circuit looking quite ugly.
     
  19. Sep 1, 2012 #18

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Good, that is correct. I will check and see what you get for the other two tomorrow.
     
  20. Sep 2, 2012 #19
    Hi,

    Ok these are my answers from the K maps,

    Q2+ = Q1.X1.X0'

    Q1+ = X0.Q2'

    Q0+ = Q2 + Q2'.Q0.X0' + Q2'.X0'.X1'

    I've attached the working so that you can see my grouping - as far as I can see this is the best way. I've also gone ahead and sketched the circuit, also attached.

    Now I've just got the small matter of the output Z, surely this would require a K map as well ?
     

    Attached Files:

  21. Sep 2, 2012 #20

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I agree with the first two. The last one will work but can be simplified slightly because your green grouping can go all the way across the first row, eliminating the Q2' in the last term.

    Yes, you can do a K map for the output but, as you will see, it is really trivial.

    In your circuit, you should connect the flip-flop outputs back into the logic inputs where they are needed. You would also want a set/reset button to initialize the circuit to the 001 state. Also, since your inputs are ##X_0,\, X_1##, where you need them inverted you either need an inverter or a gate with an inverted input. The only "loose ends" would be for the clock and ##X_0,\, X_1## inputs.

    Do you have logic simulator software so you can try out your circuit? It is always fun to see your circuit in action, not to mention verify that it is correct. Just for the fun of it, I also implemented this problem with two flip-flops, but then, being retired, I probably have more time on my hands than you do.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Sequence detector, finite state machine circuit
Loading...