Need help in solving State Diagram using Mealy or Moore

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.

each of r1/r2/r3 can be 0 or 1. So in total you have 8 combinations from all inputs (000, 001, 010, 011, 100, 101, 110, 111).

possible input sequences( r1 r2 r3) - output(g1 g2 g3)
000 - 000
001 - 000
010 - 010
011 - 010
100 - 100
101 - 100
110 - 100
111 - 100

vipinlal said:

possible input sequences( r1 r2 r3) - output(g1 g2 g3)
000 - 000
001 - 000
010 - 010
011 - 010
100 - 100
101 - 100
110 - 100
111 - 100

Click to expand...

Small mistake here: should be 001 - 001

yeah.. sorry about the mistake..

thank you so much, i will build the state diagram and see how things work out. thank u all

---------- Post added at 16:12 ---------- Previous post was at 15:57 ----------

100 - 100
101 - 100
110 - 100
111 - 100

why are the outputs 100 and not going to 111 or 110 or 101 ? Can you please explain ?
I am using Moore diagram to make state table.

olympus123456 said:

why are the outputs 100 and not going to 111 or 110 or 101 ? Can you please explain ?
I am using Moore diagram to make state table.

Click to expand...

Seems like you didn't understand your task at all...
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.

P.S. If the task was unclear to you, why didn't you ask for explanation?

I am have not done this course before and the lecturer is horribly bad in conveying the lecture properly and briefly.

I understand it now since we are arbitering we will have 100 output in the last cases which mean that state would be g3. right ?

olympus123456 said:

I am have not done this course before and the lecturer is horribly bad in conveying the lecture properly and briefly.

Click to expand...

I sympathize you then.

olympus123456 said:

I understand it now since we are arbitering we will have 100 output in the last cases which mean that state would be g3. right ?

Click to expand...

Yep.

I will post the state table in few minutes, as I understand.

Can you please be online and guide me if its correct or not ?

---------- Post added at 16:41 ---------- Previous post was at 16:37 ----------

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

Encoding : g1 = 000
G2 = 010
G3 = 100
Can you please check the state , if it correct ?

---------- Post added at 17:04 ---------- Previous post was at 16:41 ----------

D-flip flop has two out ports Q and Q' with two bits each.

So how can I used D-flip flop in this case since I am having 3 bits ?

Firstly, as far as I remember (and as far as intuition tells me), your full state table should have 8*3 rows to cover all alternatives (3 being number of states, and 8 being number of possible input signals for each state). There is a thing called reduced state table, but I don't remember how it's composed, and I don't think what you wrote is it.
Secondly, single trigger, no matter the type, has 1 bit output Q and bit Q'.
And why did you choose such an encoding? Did you mean g1 = 001?

---------- Post added at 19:25 ---------- Previous post was at 19:21 ----------

And one more thing I want to tell you: if you intend to be an electrical engineer, understanding FSM is required since it's a fundamental knowledge. I advise you to get a book on FSM theory (or lectures, or something). Personaly, I have a lecture synopsis in FSM theory. Everything is explained there, and it all really is very-very simple to understand (my lecture synopsis is in Russian language, otherwise I'd give it to you right away).

I have attached the file with what you said. the table format from word wasn't getting copied here, so i m attaching the file.

I chose encoding as such because , the lecturer said - " for a 3 state minimum number of bits is 2 to uniquely encode all states."
So I assumed that i can add an extra bit for three inputs, so that i can write the equation (SOP , when the output is 1)

Can you please suggest me some books if possible ? I will order them online by mid of this month ?

But for now you are my resource.

olympus123456 said:

Can you please suggest me some books if possible ? I will order them online by mid of this month ?

Click to expand...

I'd like to... I tried using Google to find something on the subject, but I couldn't find anything. The problem is, I've only studied it in Russian, I just don't know how it is called in English. What you're currently doing we call "FSM sinthesys", but that search query only gives me HDL- and FPGA-related pages. How is it really called in English?


---------- Post added at 22:50 ---------- Previous post was at 22:44 ----------

olympus123456 said:

I chose encoding as such because , the lecturer said - " for a 3 state minimum number of bits is 2 to uniquely encode all states."

Click to expand...

True, but minimal encoding isn't always the best. Some encodings (so called optimal coding) give smaller and simpler equation for transition functions than others. Basically, Gray's coding works well. Yours, however, looks like optimal, I didn't realize that before. Sorry.

---------- Post added at 22:53 ---------- Previous post was at 22:50 ----------

olympus123456 said:

I have attached the file with what you said. the table format from word wasn't getting copied here, so i m attaching the file.

Click to expand...

1) Again: you can receive ANY possible input combination in ANY possible current state. Your table doesn't reflect that.
2) Line 2 of your table contains mistake. Try to find it, it's pretty obvious (considering that you are creating an arbiter).
3) Why did you choose Mealy FSM? I'm not objecting, just wondering. Personally, I prefer Moore's FSM, for no particular reason.

---------- Post added at 23:06 ---------- Previous post was at 22:53 ----------

Tried searching WEB again. Again, couldn't find anything useful on the subject. I just don't know the necessary keywords, sorry. I'm sure there is plenty of books on the web, you should be able to find them.
P.S. Try asking your lecturer for a list of books, he must have such a list. It's his duty to provide it to you, that's what he got paid for. Your duty is to receive knowledge. Insist on it, no matter what. Lecturer's incompetence must not be an excuse for you.

Some of the earlier postings have missed the fact that there are 4 possible output states. The 4th is when no output is active.

It is possible to encode the 4 states with 2 bits, but in this case I think it is better to let the 3 output bits represent the states directly.
One advantage is that there can be no glitches on the outputs.

Using the 3 output bits to represent the state means that there are some illegal states that should never be reached (more than one output active).
You should have code to move from an illegal state to a legal state. If you don't handle the illegal states you could in theory have a state machine that would get stuck forever in an illegal state.

std_match said:

Some of the earlier postings have missed the fact that there are 4 possible output states.

Click to expand...

The thought had crossed my mind. I came to a conclusion that it won't be an error to grant access to one of the devices when no access request is received.

lecturer solved it in the class.
thanks for your help.