Sequence detector, finite state machine circuit

[bd411]

Homework Statement

Please see the attached photo. (The one with the green highlighter), I haven't written it out to avoid mistakes.

Homework Equations

None.

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.

 

[bd411]

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 !

 

[LCKurtz]

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.

 

[bd411]

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?

 

[LCKurtz]

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?

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.

 

[bd411]

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 !

 

[LCKurtz]

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.

 

[bd411]

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.

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 |$$

 

[LCKurtz]

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.

 

[bd411]

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 !

 

[LCKurtz]

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 !

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.

 

[bd411]

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 !

 

[LCKurtz]

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

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}$$

 

[bd411]

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}$$

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]

 

[bd411]

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

 

[LCKurtz]

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

Soooo close! But $Q_2$ is the right hand side of the table.

 

[bd411]

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.

 

[LCKurtz]

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.

Good, that is correct. I will check and see what you get for the other two tomorrow.

 

[bd411]

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 ?

 

[LCKurtz]

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 ?

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.

 

[bd411]

Ok, great, I'll get to it.

I don't actually have a logic simulator but I've been thinking about downloading LogicWorks onto my computer. It's not cheap at 48 pounds but seeing as I am studying this subject for at least another year, it might be useful !

Are there any others that I should consider?

 

[LCKurtz]

Ok, great, I'll get to it.

I don't actually have a logic simulator but I've been thinking about downloading LogicWorks onto my computer. It's not cheap at 48 pounds but seeing as I am studying this subject for at least another year, it might be useful !

Are there any others that I should consider?

I got LogicWorks many years ago from my university connection. I don't have the latest version and I have no idea if there are better or cheaper programs. Maybe others reading this thread can help you with that. Once small advantage of LogicWorks for you at the moment is that, after you have completed the problem yourself, I could send you my circuit to show the extra details and let you play with it.

 

[bd411]

Ok, I've produced a K map for the output Z, and my thinking is that the output must necessarily be 0 for all inputs to all states, except for the input of '10' when we are in the state 010 (S1). So that is the only place I should have a 1 on my K map ?

Hence no groups, and I got Z = Q2'.Q1.Q0'.X1.X0' ?

Am downloading LogicWorks now, it also seems to be quite popular amongst my department.

 

[LCKurtz]

Ok, I've produced a K map for the output Z, and my thinking is that the output must necessarily be 0 for all inputs to all states, except for the input of '10' when we are in the state 010 (S1). So that is the only place I should have a 1 on my K map ?

Hence no groups, and I got Z = Q2'.Q1.Q0'.X1.X0' ?

Am downloading LogicWorks now, it also seems to be quite popular amongst my department.

No. The "on" state is 100 = Q2 isn't it? You don't care whether the output is on in those five unused states because they aren't going to happen. It is much simpler.

 

[bd411]

Oh ok, I've just done it again with the 100 column full of 1's, 0's in the 010 and 001 columns and a bunch of don't cares. That gives me Z = Q2, which is really handy if it's right ?

 

[LCKurtz]

Oh ok, I've just done it again with the 100 column full of 1's, 0's in the 010 and 001 columns and a bunch of don't cares. That gives me Z = Q2, which is really handy if it's right ?

Bingo! Your logic is now correct. The only difference between your solution and mine is in the next state for $Q_0$. The bottom row is X1X0XXX1 and you picked up the 1 on the left with your yellow grouping with the top row. I grouped it like this in the bottom row: X1X0XXX1 so I had a $\bar Q_1X_1\bar X_0$ where you have $\bar Q_2Q_0\bar X_0$.

Now, since you have correctly completed this problem, know how to draw the circuit, and have apparently downloaded LogicWorks, I will send you my LogicWorks circuit to play with if you would like. If you want to do that, click on my ID for this post, select "view home page" and you will see my email address. Send me an email and I will reply with an attachment containing my circuit. After you are up to speed on LogicWorks you can modify my solution to agree with yours as described in the preceding paragraph.