3
\$\begingroup\$

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?

\$\endgroup\$
  • 2
    \$\begingroup\$ To three thou shalt count, and the number of the counting shall be three... \$\endgroup\$ – Olin Lathrop Feb 3 '13 at 22:20
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ +1 Yes, I would simply do a +3 each cycle, it looks pretty obvious. \$\endgroup\$ – Al Kepp Feb 4 '13 at 0:30
3
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ +1 for nice answer that addresses the original question square on the nose. \$\endgroup\$ – Michael Karas Feb 4 '13 at 0:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.