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
  • 1
    \$\begingroup\$ I can't fault you for being confused. It is a very academically ( poorly) defined problem, not a reality based one. \$\endgroup\$ Nov 11, 2016 at 3:04

2 Answers 2

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\$
2
  • \$\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, 2016 at 3:41
  • \$\begingroup\$ @JoshBarber It should be, but you might want to make output 1 for both "b" cases. \$\endgroup\$
    – nanofarad
    Nov 8, 2016 at 15:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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