Finite State Machines

Question

I want to design a finite state machine that is similar to a 3 bit counter. There are 3 bits of state (i.e. a 3 bit unsigned number) and the counter must count by 3's. More specifically, the sequence it should undergo is 0, 3, 6, 1, 4, 7, 2, 5, 0, 3, 6, 1.

I want to first produce a truth table showing what the next state of the machine should be as a function of the current state. Then I want to produce a combinational circuit using gates and D-flip flops that implements this state machine.

How do I do this?

Answer 1

If you just needed this done, use a microcontroller.

If the purpose is to make this discrete logic as a learning exercise, then I can think of several ways:

1. Use a 3 bit binary counter and increment it 3 times each count.

2. Use a 3 bit binary counter and increment the second bit (count up by two) once and the first bit (count up by one) once per count.

3. Use a 8-cell ROM such that the address is the existing counter value and the contents is the next counter value.

   Since you only have 8 possible states, such a ROM could be implemented by a 3-8 line decoder and a 8-3 line encoder and a flipflop to hold the output. The in to out mapping is done by selecting which decoder outputs drive which encoder inputs.

   You could also make the ROM with a diode array. There are lots of possibilities.

Answer 2

Olin gave a pretty good practical answer but let's look at what it takes to do this using gates (it's been a while). What you want to do is build the boolean function for the next state of every bit given the current state of the three bits, let's just take a few states an an example:

000 -> 011 
011 -> 110 
110 -> 001

I am going to convert those into a sum of products represenation. So let look at the rightmost bit position, I'll use the notation bn for the next state and an for the current state:

1. First state transition: b0_1 = (!a2) & (!a1) & (!a0) (So if all a bits are zero, b0 is 1)
2. Second state b0 is zero so I won't write a rule for it (since by default if no bit will be set to 1 the sum will be zero).
3. Third state b0_3 = a2 & a1 & (!a0).
4. Do this for all your 8 transitions.

Now b0 = b0_1 | b0_3 | ...

You'll do this for b0, b1 and b2 and you end up with all the logic you need. Next step you can simpify it (e.g. with Karnaugh maps or a computer). You current state is the output of your (three) flip-flops, going into the logic, and then back to the input of the flip flop. Then you can build it!