3
\$\begingroup\$

I have recently began studying Digital Electronics and have hit a wall trying to figure out how to design FSMs. At the moment, I am attempting to desing the FSM in the title which generates the following states: 1101->1011->0111->0101->0011->0010. Am I right in saying that this is a Moore machine and there will be 4 DFFs in this circuit? And what are the inputs for the circuit?

I now need to create the Karnaugh maps and this is where I am really stuck. I understand K maps and can create them, but I don't understand how you determine how many K maps are needed, and what goes in the x-axis and y-axis of the K maps when designing an FSM?

Here is what I have come up with so far:

enter image description here

EDIT

3rd bit Karnaugh Map:

enter image description here

\$\endgroup\$
  • \$\begingroup\$ An under-specified problem. No inputs are indicated so it presumably makes one state transition per clock. Then what does it do when it reaches 0010? Stop? And how does it get to 1101 in the first place? You can use a Reset input to get it there, and start transitions when Reset = 0. But also over-specified : for 6 states you only need 3 FFs, but this example apparently wants you to use an extra one. \$\endgroup\$ – Brian Drummond Nov 7 '15 at 17:19
  • \$\begingroup\$ Yes it makes one transition per clock cycle and yes it needs a synchronous reset but I do not know how to implement this either. \$\endgroup\$ – KOB Nov 7 '15 at 17:28
  • \$\begingroup\$ It doesn't actually matter with Karnaugh maps which inputs are the rows and which are the columns. You just distribute your various inputs between them. For state machines it makes sense that you put your state registers in one direction (say rows), and other inputs in the other direction (say columns). You'll need one map for every state machine register. \$\endgroup\$ – Tom Carpenter Nov 7 '15 at 17:28
  • \$\begingroup\$ So the circuit needs 3 DFFs and therefore 3 Karnaugh maps? What do I use to create each Karnaugh map, or in other words - how is each Karnaugh map different from the others? \$\endgroup\$ – KOB Nov 7 '15 at 17:30
  • \$\begingroup\$ Well each state register will depend on the current state (i.e. all state registers), and on any other inputs (which includes the reset signal). It helps to draw a state diagram first. \$\endgroup\$ – Tom Carpenter Nov 7 '15 at 17:31
2
\$\begingroup\$

Based on your state diagram and explanation, you have everything you need there.

For every register (you have 4), you need to create a Karnaugh Map which determines what value will be clocked onto that register in each clock cycle.

The next value for each state register will depend on the current state as a whole (i.e. all state registers), and any other inputs (in your case only reset). So build your Karnaugh Map using those inputs.

Each of your states has a 4-bit value (e.g. your starting state is 1101). So you will need 4 registers to hold the value indicating current state. So for example lets call your state registers \$\left(S_3, S_2, S_1, S_0\right)\$, where the starting state would be say \$S_3=1\$, \$S_2=1\$, \$S_1=0\$, and \$S_0=1\$. Also lets call the reset signal \$R\$.

You will have maps which look something like:

$$ \begin{array}{c c c| cc} S_0 & & R & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1\\ & & S_3 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0\\ & & S_2 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0\\ S_0 & S_1 & \\ \hline 0 & 0 & & & & & & 1 & 1 & 1 & 1\\ 0 & 1 & & 1 & & & & 1 & 1 & 1 & 1 \\ 1 & 1 & & 0 & 1 & & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & & & 1 & 1 & & 1 & 1 & 1 & 1 \\ \end{array} $$

I've been exceedingly nice and filled in the map for \$S_0\$ for you based on your next state table. I'll let you make and fill in the other three maps.

Once you have your four maps you know the logic for each of the state registers.

\$\endgroup\$
  • \$\begingroup\$ Thank you for the help. How did you determine that there needs to be 4 registers? And you say that I need to create a K map for each register - does this mean that I need to fill in the above map 4 seperate times? If so, what makes each of these 4 maps differ from one another? \$\endgroup\$ – KOB Nov 7 '15 at 18:10
  • \$\begingroup\$ @KOB Your states are 4-bit numbers (e.g. 1101), so you will need a 4-bit state register (i.e. 4 registers). Yes you will need to fill out the above four times, one for \$S_0\$, once for \$S_1\$, and so on. \$\endgroup\$ – Tom Carpenter Nov 7 '15 at 18:12
  • \$\begingroup\$ Ok, this is all starting to makes sense. I'll see how I get on now. Thank you. \$\endgroup\$ – KOB Nov 7 '15 at 18:21
  • \$\begingroup\$ For the example above did you mean to say the starting state would be "S0=1, S1=0, S2=1, S3=1?" I figured the starting state should be S0=1, S1=1, S2=0, S3=1 as you said "e.g. your starting state is 1101". \$\endgroup\$ – user91153 Nov 7 '15 at 22:18
  • \$\begingroup\$ @TomCarpenter Unfortunately, I didn't quite grasp your K map example yesterday and have come back to the problem again today. I really can't see how you determined what goes into each sell of the K map, or in other words, I can't figure out what each of the 4 K maps are representing? \$\endgroup\$ – KOB Nov 8 '15 at 15:11

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.