A Moore machine

Discussion in 'Homework Help' started by belaamg, Apr 30, 2011.

  1. belaamg

    Thread Starter New Member

    Apr 30, 2011
    2
    0
    Hello,
    This is my first post. This problem was in my last exam and next week is the final and I can't even start it:
    A sequential system has two binary inputs x & y and one binary output z. The system output a '1' if the number of '1's that has occurred on x and the number of '1's that has occured on y are both divisible by 3. Otherwise, the system outputs a '0'. draw the state transition diagram that represents this sequential system using as few states as possible. Make your systema Moore machine.
    I don't know how to start the problem. Where does the count stop and where is the input going, the states are not specified? How can make a state table if I don't know the state.
    Thank you
     
  2. Georacer

    Moderator

    Nov 25, 2009
    5,142
    1,266
    First of all, check this link out so that you have a general idea of the steps you will follow later:
    http://www.allaboutcircuits.com/vol_4/chpt_11/5.html

    After you have done that, let's examine your problem, in order to setup your state diagram.
    Basically, as I see it, you need to keep track of two counters that count the aces of each input. They make a cycle of 3 steps. They advance only when the corresponding input gives them a 1.

    So picture two loops into your head, one for the X input and one for the Y. Each loop will have 3 states and will advance to the next state only with an input of 1. The third state of each cycle will be the "3rd ace mark" and will denote the existence of a multiple of 3.
    An AND gate watching those two states can give you the final Z result.

    For starters, can you draw and post the state diagram?
     
    belaamg likes this.
  3. belaamg

    Thread Starter New Member

    Apr 30, 2011
    2
    0
    I entered a state diagram
     
  4. Georacer

    Moderator

    Nov 25, 2009
    5,142
    1,266
    Even though the state diagram is correct, it is a bit of a waste to use 3 Flip Flops to encode 3 states. Remember that for each bit you use to describe the states you use 1 FF.
    The state naming should be 00, 01 and 10.

    You now have two identical circuits that count the aces in three's. When the two FFs of each circuit have a state of {00}, that means that your output is 1. In the guide I gave you, you can find out how to produce that 1 from each circuit.

    The process of producing the final 1 when both circuits give you a 1, is a simple as connecting both outputs to an AND gate.
     
  5. guitarguy12387

    Active Member

    Apr 10, 2008
    359
    12
    Not to diverge from the subject... but for the sake of completeness, there are reasons why you might go with a one-hot state encoding. For example, one-hot encoding is faster on an FPGA than standard binary encoding.
     
  6. Georacer

    Moderator

    Nov 25, 2009
    5,142
    1,266
    By one hot I guess you mean state naming like 100, 010 and 001. I 'll take your word for it as far as FPGA's are concerned, but in a classic discrete IC solution it is out of the question.
     
  7. guitarguy12387

    Active Member

    Apr 10, 2008
    359
    12
    That is one-hot encoding, yes.

    That was only one example... there's numerous reasons to use one-hot encoding. It reduces the amount of comb. logic, don't need to decode states, more robust due to ease of error correction because of guaranteed hamming distance of 2, easier timing analysis, etc...

    Ref:
    http://www.trilobyte.com/pdf/golson_pldcon93.pdf

    My point was, this is an engineering decision. Tradeoff between different types of resources used, speed, size, cost, etc. Admittedly, for learning about FSMs, standard binary encoding is a pretty usual way to learn.
     
  8. Georacer

    Moderator

    Nov 25, 2009
    5,142
    1,266
    The only objection I have against one-hot encoding is the much larger quantity of ICs it requires. Especially when in need of many states. Usually, homework help inquirers utilise discrete ICs and not FPGAs or PLCs and the less ICs your final design has, the merrier.
     
Loading...