Maker Pro
Maker Pro

Finite state machine

smiljanic997

Jun 8, 2017
5
Joined
Jun 8, 2017
Messages
5
Hey guys, I'm struggling with this type of problems, so it would be great if someone could explain to me how to approach the analysis of this problem.

So, I need to "form a synchronus sequential circuit that implements the fonite state machine from picture".
 

Attachments

  • 20170612_124303.jpg
    20170612_124303.jpg
    104.1 KB · Views: 64

Harald Kapp

Moderator
Moderator
Nov 17, 2011
13,700
Joined
Nov 17, 2011
Messages
13,700
This finite state machine has 4 states. There are several ways to encode the states of a finite state machine. You first need to select an encoding scheme (number of bits, code). Then assign each state (s0...s3) from the diagram to one dedicated code of the encoding scheme.

You now have the 4 states encoded by 4 well defined codes of the machine. In the next step you need to find the boolean equations which will generate the next state from the curent state and the condition for the transition. You obviously have one input signal which can be either 0 or 1 (the left side of the 1|0 or 0|0 statements in your diagram).
You neeed to define the boolean function such that new_state = f(current_state, input_signal).

Show us your progress, then we can help you along the way.
It is forum policy not to provide full answers to homework, rather we will guide you so you really learn something.
 

smiljanic997

Jun 8, 2017
5
Joined
Jun 8, 2017
Messages
5
So I need to encode states S0, S1, S2 and S3 like 00, 01, 10, 11. Then what, how will my state table look like ?
 

Laplace

Apr 4, 2010
1,252
Joined
Apr 4, 2010
Messages
1,252
Then what, how will my state table look like ?
The state table will track individual bits, i.e. the bits that encode each state and the input bits that control the transition to the next state. Each of those bits must be given a name that will then become the column headings in the state table. So each line in the state table will document combinations of the current state and the inputs that produce the next state. It will also show any combinations that do not occur in the state diagram and can be labeled as "don't care" conditions for the next state.
 

Harald Kapp

Moderator
Moderator
Nov 17, 2011
13,700
Joined
Nov 17, 2011
Messages
13,700
So I need to encode states S0, S1, S2 and S3 like 00, 01, 10, 11.
To define the encoding is your task.
There are several option, e.g.:
You chose one of these (read the descriptions I linked and decide which code suits you best), then you assign each state S0...S3 one of the codes from the chosen code.

To give you an example without disclosing the answer to your homework:

Assume you have a state machine with states S0, S1, ...S7 (8 states).
Assume you use a 4 bit binary code.
With 4 bits you can encode 16 states:
0000 = state 1
0001 = state 2
...
1111 = state 16
You now assign the given states S0...S7 to this code. How you map the states to the codes is basically random. There is no given scheme. Although it may be preferable, depending on the application, to use some special mapping which may simplify zhe logic equations or the generation of output signals from the state machine. This is not relevant for your homework and I will not discuss this here. I'll leave this as an exercise to you once you've mastered this task.

In this example I could chose (out of many other possible mappings) e.g.:
S0 -> 0000
S1 -> 0001
S2 -> 0010
S3 -> 0011
S4 -> 1000
S5 -> 1001
S6 -> 1010
S7 -> 1011
Lets call the bits at the right side of the above assignment the logic state variables and give them names such as e.g. sv3, sv2, sv1, sv0 such that a logic state is represented by a vector of these variables. This could be written as logic_state = [sv3, sv2, sv1, sv0].
Example: S6 -> 1010 -> [1,0,1,0] -> sv3=1, sv2=0, sv1=1, sv0=0

You now have 4 bits from the state machine plus the number of input bits (in your task this is just one bit). A total of 5 bits as inputs to your logic equations or truth tables. You write one truth table per logic state variable:
sv3(t+1) = f (input, sv3(t), sv2(t), sv1(t), sv0(t))
Note the use of indices (t) and (t+1) which indicate the present state (t) and the next state (t+1).

This information can also be found here.
 
Top