# State Diagram - Mealy or Moore

#### olympus123456

Joined Apr 1, 2011
8
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.

#### narasimhan

Joined Dec 3, 2009
72
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.

#### Georacer

Joined Nov 25, 2009
5,182
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

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

#### olympus123456

Joined Apr 1, 2011
8
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

#### Georacer

Joined Nov 25, 2009
5,182
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.

#### olympus123456

Joined Apr 1, 2011
8
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.

#### Attachments

• 42.5 KB Views: 52
Last edited:

#### Georacer

Joined Nov 25, 2009
5,182
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.

#### olympus123456

Joined Apr 1, 2011
8
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:

#### Georacer

Joined Nov 25, 2009
5,182
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?