# Designing a State Machine

Question: Design a state machine that would output the sequence 0 1 7 1 and then 1 7 1 1 7 1 and so on. A reset will make the machine go to the which outputs 0?

What I've managed to do so far:

Since the sequence has four numbers so we use two Flip Flops. And states would be: 00, 01, 11, 10

And I'm considering "reset" to be an input, so the state table would have 2^3 = 8 rows.

Present St. Input Next St. Output in Dec.
00        0      01       0
00        1      00       0
01        0      10       1
01        1      00       1
10        0      11       7
10        1      00       7
11        0      01       1
11        1      00       1


From this table, I can draw K-Maps to find out simplified equations for D_A and D_B which are going to be the inputs of two D-Type Flip-Flops. But I'm to unable figure out how to display the output?

Should I convert it to binary and use three state machines instead since 7 would be 111 and three flip-flops would be needed to store this value.

Or can I use a ROM if Size 2*3 having two address lines and 3 bit output.And burn 0, 1, 7, 1 at respective locations 00, 01, 10, 11. Or is there a better solutions? Thank you. :')

• Output is your state change. If 00, go to 01. 01 to 11. 11 to 10. 10 to 01. etc. – StainlessSteelRat May 15 '15 at 21:05
• The sequence appears to have only 3 numbers does it not? 0,1,7. So while yes you need 2 bits, you could actually not use one of the states. My suggestion is to ignore state '10' (maybe have a mapping that if it is ever reached, go to '00'). This means your state machine would go: '00','01','11','01','01','11','01' and so on. Given that you want the output values to be 000 (0) in state '00', 001 (1) in state '01' and 111 (7) in state '11', notice how you don't require any additional logic to generate the 3 bit output from the 2 bit state value? (Hint bits 1 and 2 are the same in the output). – Tom Carpenter May 15 '15 at 21:05
• @TomCarpenter: But your scheme can't generate the sequence 1->1, only the sequences 1->7 and 7->1. While there are only 3 numbers, there are two states of 1 (one transitioning to 7 and another to 1) one state of 0 and 1 state of 7 = 4 states, not 3 – slebetman May 15 '15 at 21:10
• @slebetman Ah yes, my mistake, missed that. In which case you can use state '10' for going from 1 to 1. Then the lower bit of the output would be the XOR of the state value, and the upper 2 bits of the output would be the AND of the state value. So the state machine would go: '00','01','11','10','01','11','10' – Tom Carpenter May 15 '15 at 21:13
• You could simplify the output logic a little and recognise that 2 of the states have the same output : if there is some common feature between their state representations, you could generate that output when that feature appears. – user_1818839 May 16 '15 at 9:03

     Input Present St. Next St. Output in Binary
0      00        01       000
0      01        11       001
0      10        01       001
0      11        10       111
1      00        00       000
1      01        00       001
1      10        00       001
1      11        00       111


I'd rearrange truth-table. 3 inputs, 5 outputs (2 for state).

Lower bit, OR of present state. Upper bits AND of present state.

• But how would you figure the "Combinational Circuit" to use for this output? You can't represent the MSB of the output using any thing. We only have two flip flops. In your case, we can't have 7. – muqsitnawaz May 15 '15 at 22:05
• You only have 2 (for state). "Lower bit, OR of present state. Upper bits AND of present state." You have two things to keep track, state and output. 2 flip-flops for state. AND and OR off of flip-flops for output. – StainlessSteelRat May 15 '15 at 22:10
• That's a good straight forward answer. – mrbean Oct 29 '20 at 1:50

Let me suggest an approach. First off decide if you want to adopt a Moore or Mealy representation. A Moore machine will generally have more states and the outputs depend only on the state register value. A Mealy machine has conditional outputs, where the output logic functions are functions of both the state register value and the inputs to the state machine.

Need to make that choice first. Ok, I think for this case, a Moore machine might be an interesting way of doing it. Your discussions so far have centred on a state register comprising two bits (two flipflops), ,if we allow the design to contain 3 bits then we can do this: finite state machine state register outputs drive a 7 segement decoder/driver, which means you can have a 7 segment display represent the code on the state register.

State Code ......OutputCode to 7 Seg Driver

0 ..............0

1...............1

7...............7

1...............1

1...............1

7...............7

...

So you can see from this, that the careful selection of the state values means your output functions (logic functions) aren't required! Just take the Q output of the flipflops of the state register and feed directly to the 7 segment decoder/driver.

Your design then simplifies to the following:

3 x flipflop for the state register

1 x 7 segment decoder driver chip

3 next state logic functions to be designed.

You could implement the 3 next state functions in ROM as a truth table, but I wouldn't do that, I think you need to have the experience of designing the logic functions, using Karnaugh maps to reduce them and then build the whole thing. You can easily do this in a field programmable logic sequencer chip which contains flipflops and combinational logic functions. That will then give you experience of programmable logic devices too and the whole design with possibly the exception of the 7 segment decoder driver can be squeezed into a single chip. (16PALR4 perhaps?)