FSM miplementations in C
Dr. Bystrov
School of Engineering Newcastle University, Newcastle upon Tyne
FSM miplementations in C
Copyright By PowCoder代写 加微信 powcoder
Aims and Objectives
Aim: Implementation of SW systems that have been designed with FSM models
Objectives:
1. Switch-Case implementation style
2. Goto-Label implementation style
3. Finite State Table implementation style
The examples below are simpler than in the book by Williams. Only simple examples are included in the exam; the book is optional, but read it anyway.
FSM miplementations in C
The FSM benchmark
Trigger event Action list
Is it of Moore or Mealy type?
What if a3 and a4 actions were the same?
Remember the formal definition and examples?
FSM miplementations in C
Switch-Case Implementation
enum {s0,s1,s2} state=s0;
while (1) {
switch(state) {
case s0: t=input_trigger();
if (t==t1) {a1(); state=s1;}
case s1: t=input_trigger();
if (t==t2) {a2(); state=s2;}
case s2: t=input_trigger();
if (t==t3) {a3(); state=s1;}
else if(t4) {a4(); state=s0;}
} //end switch
} //end while
} //end main
FSM miplementations in C
Goto-Label Implementation
L0: t=input_trigger();
if(t==t1) {a1();goto L1;} else goto L0;
L1: t=input_trigger();
if(t==t2) {a2();goto L2;} else goto L1;
L2: t=input_trigger();
if(t==t3) {a(3); goto L1;}
else if(t==t4) {a4(); goto L0}
else goto L2;
}//end main
This is faster than Switch-Case!
Still, the size of the code is proportional to the size of the model.
Very reliable, because the labels are stored in ROM.
FSM miplementations in C
FST Implementation – Data Structures
#define states 3
#define triggers 4
struct state
int next_state; action_type action;
struct state state_table[triggers][states]=
{// s0 s1 s2
{{1,1},{1,0},{2,0},}, //t1
{{0,0},{2,2},{2,0},}, //t2
{{0,0},{1,0},{1,3},}, //t3
{{0,0},{1,0},{0,4},}, //t4
The FSM is “encoded” into the data structure. Size?
FSM miplementations in C
FST Implementation – Code
void main() {
int state=0, t;
t=input_trigger();
execute_action(
state_table[t][state].action
state_table[t][state].next_state;
Fast. The code size is independent from the spec size.
FSM miplementations in C
Switch-Case Goto-Label
Finite State Tables
Conclusions
Three implementation styles of FSM are covered
They can be used with any language, not just C Simple actions can be replaced with action lists
Actions can be associated with either transitions or states
Several implementation styles are not covered
Direct Sequential Coding – a convoluted version of Goto-Label
Object-Oriented approach – specific to C++, the algorithm idea is similar to the above three.
FSM miplementations in C
y=1 A 0010
C y=1 1000
Exercise 1
The inputs are e and r; the output is y.
Implement this FSM in all three styles discussed above.
FSM miplementations in C
Exercise 2
Develop an FSM model of a lift and implement it in the above three styles.
Three floors
One button on each floor
Three buttons on the controller inside the lift There are no doors for simplicity
FSM miplementations in C
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com