State Diagram - Mealy or Moore

Discussion in 'Homework Help' started by olympus123456, Apr 1, 2011.

  1. olympus123456

    Thread Starter New Member

    Apr 1, 2011
    8
    0
    Hi, I am having difficulty in drawing a state diagram for my homework question. Can any one of you please help me or guide me?
    Thank you, I would really appreciate your help.

    Question is - 1) Design an arbiter circuit to grant access to one of the three devices that may send an access request signal to the arbiter. Let the input requests to the arbiter be r1, r2, r3 the outputs will be g1, g2, g3 to grant only one of the three. Also assume priority that device 1 has higher priority than others, and device 2 has higher priority than device 3. Create a state diagram, state table and logic equations for all outputs and draw a schematic using D flip-flops. Make sure that at max only one of the three output is active at any given time.


    I am confused with the inputs r1,r2,r3. Should I take two values each for r1,r2,r3 , which will be r1=0 or r1=1 . Or second scenario I have is r1r2r3 = 000 to 111, i.e., three binary numbers.

    I can't understand how to solve it, please help.
     
  2. narasimhan

    Member

    Dec 3, 2009
    72
    6
    Since r1, r2 and r3 are separate inputs they each can take value of 0 or 1. So typically there are 8 possibilities(000, 001, 010 .... to 111). So both your scenarios are same.

    First draw the state table. it'll clear most of your doubts.
     
  3. Georacer

    Moderator

    Nov 25, 2009
    5,142
    1,266
    Take a look here: http://www.allaboutcircuits.com/vol_4/chpt_11/5.html
    Keep in mind that this article describes the construction of a Moore FSM. It is possible to solve your exercise with a Moore machine. If you want, however to utilize a Mealy machine for some reason, please say so.

    As you will see, the key is to define the problem correctly and build the state diagram. Then, it's a breeze in the park.

    But it is your job to do it, or at least give it a try. Make an effort ant post it. We 'll talk more then.
     
    olympus123456 likes this.
  4. olympus123456

    Thread Starter New Member

    Apr 1, 2011
    8
    0
    Thank you, i will draw state diagram and state table and update the thread in a while.
     
  5. olympus123456

    Thread Starter New Member

    Apr 1, 2011
    8
    0
    External Input (r1r2r3) Current State Next State Output
    000 G1 G1 000
    001 G1 G2 001
    010 G2 G2 010
    011 G2 G3 010
    100 G3 G3 100
    100 G3 G3 100
    100 G3 G3 100
    100 G3 G3 100
     
  6. Georacer

    Moderator

    Nov 25, 2009
    5,142
    1,266
    From the fifth column and lower, the rows are identical.
    Care to revise?

    Otherwise, your logic has some blanks. Since you lead your states to 3-bit combos with only 1 ace, your circuit won't get to, for example 110.

    You should do it like so:
    Have only 3 states and 3 input bits. Each state will represent one of the 3 outputs.

    An example:

    G__R__G'
    ...
    01_100_10
    ...

    That is, from G2 (01), with input 100 (R3) you should go to G3 (10).

    A better implementation would be to encode the input before using it, because the above method will give a 32-row state table.
    That way the above example would become:

    G__R__G'
    ...
    01_11_10
    ..

    Is that clear?

    Post a state diagram if you have the time to. It will show any fallacies you might have.
     
  7. olympus123456

    Thread Starter New Member

    Apr 1, 2011
    8
    0
    I have attached the state table and state Diagram i made.

    from fifth column and lower is 100 because the question is about arbitering, so a friend of mine said - The point of arbitering is to allow operation for only one device whenever several devices have sent request at the same time. Thus, having more than one '1' in output registers ('1' means "allow operation") would be an error.
     
    Last edited: Apr 1, 2011
  8. Georacer

    Moderator

    Nov 25, 2009
    5,142
    1,266
    Your work is far from complete. You posted two state tables that pretty much say the same thing, but miss one significant detail.

    You have taken as variables for your table only the inputs, and not the current states. Both those pieces of information need to be permutated in order to get a complete table.

    If you encode your input as I said, your final table will have 2^4=16 rows.

    I 'll change the encoding a bit, in order to incorporate a no-request possibility. Thus R=000 will encode to 00, 001 to 01, 010 to 10 and 100 to 11. The same will hold for G.

    I 'll start it for you:

    G__R__G'
    -----------
    00_00_00
    00_01_01
    00_10_10
    00_11_11
    01_00_01
    ...
    10_01_10
    ...

    Can you fill all 16 rows? We 'll discuss later about how to decode the output.
    I have also made the assumption, in the spirit of the exercise, that if a device stops requesting, it will still keep on getting served.
     
  9. olympus123456

    Thread Starter New Member

    Apr 1, 2011
    8
    0
    G__R__G'
    -----------
    00_00_00
    00_01_01
    00_10_10
    00_11_11
    01_00_01
    01_01_10
    01_10_00
    01_11_11
    10_00_00
    10_01_10
    10_10_01
    10_11_11
    11_00_00
    11_01_01
    11_10_10
    11_11_11

    I assume this will be the table with G state values, R input, and G' is output
     
    Last edited: Apr 1, 2011
  10. Georacer

    Moderator

    Nov 25, 2009
    5,142
    1,266
    Something I overlooked in the previous analysis: We used two bits to encode the input R, assuming that only one device will send a request at any given time. If more than one device can send a request, then we have two options.
    Either expand the input to three bits, producing a 32-row state table, or we can intervene a subcircuit after the input encoder to "filter" inputs of less importance.
    I also assumed that R3 will be the most significant input, which I found to be wrong after I re-read your original question. Please excuse any misunderstandings caused by that fallacy.

    As for your table, are you sure you remember what you want to achieve?

    Let's recap:
    For the state of the machine (G) 00 is reset, 01 is G1, 10 is G2 and 11 is G3.
    For the input (R) 00 is no input, 01 is R1, 10 is R2 and 11 is R3.

    So, for example, on row 6, you have written 01_01_10. That means that while you serve Device 1 and it sends another request, then you will switch to Device 2. Are you sure this is what you want to achieve?

    Another example: on row 8, you serve Device 1 and the Device 3, which is of less importance, sends a request. You have then chosen to serve device 3.

    A final example: on row 9, you serve Device 2 and you read no input (00). You then choose to seize all device services (00). Why is that?

    Please make a final effort on your state table.
     
    olympus123456 likes this.
  11. olympus123456

    Thread Starter New Member

    Apr 1, 2011
    8
    0
    The lecturer solved the question in the class.
    thanks for your help
     
Loading...