5
\$\begingroup\$

Now I have a homework question that isn't quite clear to me.

"Construct a finite state machine that accepts a base 2 value entered one bit at a time with the most significant bit first. The machine output is 1 if the number entered so far (i.e. current state) reflects 2 mod 3 else the output is 0."

now I would have to build a truth table as well as a logical circuit.

I'm confused at where it says 1 bit at a time with the most significant bit first. So the most significant bit would be 1 in base 2, but would I not have to use more than one bit per cycle to structure this? So would this be an error in the question, or am I missing something.

Thanks in advance

\$\endgroup\$
  • 1
    \$\begingroup\$ I can't fault you for being confused. It is a very academically ( poorly) defined problem, not a reality based one. \$\endgroup\$ – Tony Stewart Sunnyskyguy EE75 Nov 11 '16 at 3:04
3
+50
\$\begingroup\$

Ok, here is more detail. The state diagram for implementing this as a Moore machine looks like this; enter image description here A Moore machine is one where that states are the outputs. I always remember this as Mealy machines are more complicated. From this state diagram the next state and excitation tables can be created. They look like this; enter image description here

Karnaugh maps for each J and K input are used to come up with the logic. The logic can be seen in this schematic; enter image description here A simulation of this schematic shows an input string that causes the machine to go from state 0 to 1 and back to 0 starting at 2us. So X = 1,1,0. Starting a 6us the machine goes from 0 to 1 to 2 and stays there for X = 1,0,1,1. At 10 us the machine goes from 2 to 1 to 0 for the inputs 1,0. This has exercised all the transistion possible. Here is the simulation output; enter image description here

\$\endgroup\$
3
\$\begingroup\$

When reading a number, MSB first, you only need to keep track of the previous value modulo 3, not just the overall previous value, which is easily achievable with a simple transition table and three states. If input is zero, the following transitions can be shown to occur:

  • 0 -> 0
  • 1 -> 2
  • 2 -> 1

If the input is 1, the following transitions occur instead:

  • 0 -> 1
  • 1 -> 0
  • 2 -> 2

according to the rules of modular arithmetic.

\$\endgroup\$
  • \$\begingroup\$ Thanks, I don't want to tie you up too much, as our prof never really went into specifics. So would this be ideal imgur.com/zdrg8jM \$\endgroup\$ – 1011 1110 Nov 8 '16 at 3:41
  • \$\begingroup\$ @JoshBarber It should be, but you might want to make output 1 for both "b" cases. \$\endgroup\$ – ζ-- Nov 8 '16 at 15:28

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.