Editando C10 - Finite State Machine (sección)

= Finite State Machine with Indexed Structures =
<br>
*FSM se puede llamar a un sistema lógico que tiene inputs y outpus
*Este sistema lógico tiene estados que cambian según los inputs y producen outpus
<br>
Una FMS contiene 5 cosas:
*Conjunto de inputs
*Conjunto de outputs
*Conjunto de estados que hay en el sistema
*State Transition: Nos dice que causa que el sistema pasa de un estado a otro. Se puede representar mediante
**Gráfico
**Matriz numérica
*Output determination: Que condiciones genera los outpus
<br>
Tipos de FSM
*Moore FSM
**NextState = f(current_State, Input) <math>\Rightarrow</math> NextState va en función del current_State y de los inputs
**Output = g(current_State) <math>\Rightarrow</math> Output va en función del current_State
*Mealey FSM
**NexStet igual que en Moore
**Output = h(current_State, Input) <math>\Rightarrow</math> Output va en función del current_State y de los inputs
<br>
== Ej. Máquina cuenta 1s ==
<br>
Tenemos un sistema que lee por un puerto bits (0 o 1). El sistema cuenta cuantos bits 1 ha leido y por un output escribe 1 si el número de 1s es impar y 0 si es par<br>
<br>
=== Definición FSM ===
*Input - 1 bit que puede ser 0 o 1
*Output - 1 bit que puede ser 0 o 1
*States - 2 estados
**nº de 1 par
**nº de 1 impar
*State Transition Graphic
**Los círculos expresan los estados y las flechas expresan las transiciones
**En el estado par
***Si recibimos un 0 nos quedamos en el estado porque el número de 1 no ha cambiado
***Si recibimos un 1 pasamos al estado impar
**En el estado impar
**Si recibimos un 0 nos quedamos en el estado porque el número de 1 no ha cambiado
**Si recibimos un 1 pasamos al estado par
[[File: edx-odd-stg.png | 300px]]<br>
*Output
**Como estamos haciendo una FSM de Moore cada estado tiene un output
**Los outputs son los números azules del gráfico
**Cuando estamos en el estado par ponemos un 0 en el output
**Cuando estamos en el estado impar ponemos un 1 en el output 
<br>

=== Programación estados ===

Código que plasma el STG que vemos mas arriba en un struct.<br>
<br>
 //Construimos el "contenedor" de cada estado
 struct State{
    unsigned char out;       //Aqui va la salida que tendrá cada estado (los numero azules del dibujo)
    unsigned long wait;      //Entre cada estado esperaremos un tiempo para que pueda leer la entrada
    unsigned char next[2];   //En cada estado almacenamos los posibles estados siguientes
 }
 typedef struct State SType;
 
 #define Even 0              //Lo hago para que sean más claros los estados
 #define Odd  1
 
 //Creamos los estados y los inicializamos
 //En primer el estado el output sera 0, en el segundo estado sera 1
 //El tiempo que esperaremos para cambiar de estado sera de 100ms en los dos estados
 //En el primer estado si obtenemos un 0 nos mantenemos en el y si obtenemos un 1 cambiamos a Odd
 //En el segundo estado si obtenemos un 0 nos mantenemos en el y si obtenemos un 1 cambiamos a Even
 Stype fsm[2]={
   {0,100,{Even, Odd}},
   {1,100,{Odd, Even}}
 };
<br>
=== Programación controlador FSM ===
El controlador de la máquina de estados finita es le encargado de leer las entradas, escribir las salidas y cambiar entre los diferentes estados.<br>
Este controlador se programa en el main y se sigue este esquema:
*Escribo el output
*Espero
*Leo input
*Cambio de estado según el input y el estado en el que estoy
<br>
Nota:<br>
No entiendo porqué no se hace así:
*Leo input
*Cambio estado según input y estado actual
*Escribo output
*Espero
<br>
El código de este ejemplo quedaria:<br>

 unsigend char cState;
 void main(void){
   unsigned char input;
   
   //Inicializar puertos
   //Inicializar SysTick para función delay
   
   cState = Even;
   while(1){
    GPIO_PORT... = Fsm[cState].out;    //Escribimos el output del estado actual
    delay();                                          //Esperamos
    input = GPIO_PORT...;                   //Leemos input
    cState = Fsm[cState].next[input];  //Cambiamos de estado según el input. Si el input
                                       //es 0 vamos al estado Even y si el input es 1 vamos al estado Odd
                                       //y también según el estado en el que estamos (la variable 
                                       //cState es la que nos indica en que estado estamos)
   }
 }

== Ej. Semaforos ==
<br>
El siguiente ejemplo es sobre un cruce que tiene dos semáforos para controlar el tráfico. Hay dos sensores que detectan si hay coches en la calle 1 o en la calle 2. Dependiendo de donde hayan los coches se pone el semáforo en rojo o verde.<br>
<br>
[[File: Edx-fsm-semaforo.png | 300px]]<br>
<br>
=== Definicion FSM ===
Imagen STG<br>
<br>
La tabla muestra la misma información que el gráfico. Es un resumen de la funcionalidad de la máquina de estados<br>
{| class="wikitable"
! colspan="9" style="text-align: center;" | 
! colspan="4" style="text-align: center; font-weight: bold;" | Input
|-
| colspan="2" style="text-align: center; font-weight: bold;" | Estados
| style="text-align: center;" | 
| colspan="6" style="text-align: center; font-weight: bold;" | Output
| style="text-align: center; font-weight: bold;" | S2S1
| style="text-align: center; font-weight: bold;" | S2S1
| style="text-align: center; font-weight: bold;" | S2S1
| style="text-align: center; font-weight: bold;" | S2S1
|-
| style="text-align: center; font-weight: bold;" | Descripción
| style="text-align: center; font-weight: bold;" | Nombres
| style="text-align: center; font-weight: bold;" | Tiempo
| style="text-align: center; font-weight: bold;" | V1
| style="text-align: center; font-weight: bold;" | A1
| style="text-align: center; font-weight: bold;" | R1
| style="text-align: center; font-weight: bold;" | V2
| style="text-align: center; font-weight: bold;" | A2
| style="text-align: center; font-weight: bold;" | R2
| style="text-align: center; font-weight: bold;" | 00
| style="text-align: center; font-weight: bold;" | 01
| style="text-align: center; font-weight: bold;" | 10
| style="text-align: center; font-weight: bold;" | 11
|-
| Calle 1 verde. Calle 2 rojo
| style="text-align: center;" | C1
| style="text-align: center;" | 30
| style="text-align: center;" | 1
| style="text-align: center;" | 0
| style="text-align: center;" | 0
| style="text-align: center;" | 0
| style="text-align: center;" | 0
| style="text-align: center;" | 1
| style="text-align: center;" | C1
| style="text-align: center;" | C1
| style="text-align: center;" | W1
| style="text-align: center;" | W1
|-
| Calle 1 amarillo. Calle 2 rojo
| style="text-align: center;" | W1
| style="text-align: center;" | 5
| style="text-align: center;" | 0
| style="text-align: center;" | 1
| style="text-align: center;" | 0
| style="text-align: center;" | 0
| style="text-align: center;" | 0
| style="text-align: center;" | 1
| style="text-align: center;" | C2
| style="text-align: center;" | C2
| style="text-align: center;" | C2
| style="text-align: center;" | C2
|-
| Calle 1 rojo. Calle 2 verde
| style="text-align: center;" | C2
| style="text-align: center;" | 30
| style="text-align: center;" | 0
| style="text-align: center;" | 0
| style="text-align: center;" | 1
| style="text-align: center;" | 1
| style="text-align: center;" | 0
| style="text-align: center;" | 0
| style="text-align: center;" | C2
| style="text-align: center;" | W2
| style="text-align: center;" | C2
| style="text-align: center;" | W2
|-
| Calle 1 rojo. Calle 2 amarillo
| style="text-align: center;" | W2
| style="text-align: center;" | 5
| style="text-align: center;" | 0
| style="text-align: center;" | 0
| style="text-align: center;" | 1
| style="text-align: center;" | 0
| style="text-align: center;" | 1
| style="text-align: center;" | 0
| style="text-align: center;" | C1
| style="text-align: center;" | C1
| style="text-align: center;" | C1
| style="text-align: center;" | C1
|}
Inputs:
*Coche calle 1 - S1
*Coche calle 2 - S2
Outputs:
*V1 A1 R1 <math>\Rightarrow</math> semáforo calle 1 que cuenta con verde, amarillo y rojo
*V2 A2 R2
<br>
<b>Estado1 - C1</b>
*Verde en calle 1 y rojo en calle 2, por lo tanto las salidas son 
 V1 A1 R1 V2 A2 R2
  1  0  0  0  0  1
*Siempre que S1 se mantenga en 1 nos quedamos en este estado
*Si no hay ningún coche en las dos calles también nos mantenemos en este estado
*Para pasar al siguiente estado S2 tiene que valer 1
<b>Estado2 - W1</b>
*Es un estado de transición entre el verde y el rojo. Hemos de pasar por el amarillo y el estado tiene una duración máxima de 5ms
*La salida es 010001 <math>\Rightarrow</math> Activamos A1 porque vamos a cambiar de V1 a R1
*Cualquier input nos hace pasar al siguiente estado
<b>Estado3 - C2</b>
*Rojo calle 1 y verde calle 2 <math>\Rightarrow</math> 001100
*Siempre que S2 se mantenga en 1 nos quedamos en este estado
*Si no hay ningún coche en las dos calles también nos mantenemos en este estado
*Para pasar al siguiente estado S1 tiene que valer 1
<b>Estado4 - W2</b>
*Es un estado de transición entre el verde y el rojo. Hemos de pasar por el amarillo y el estado tiene una duración máxima de 5ms
*La salida es 001010 <math>\Rightarrow</math> Activamos A2 porque vamos a cambiar de V2 a R2
*Cualquier input nos hace pasar al siguiente estado
<br>

=== Programación estados ===

 //Contenedor de cada estado
 struct State{
  unsigned long out;
  unsigned long wait;
  unsigned long next[4];
 };
 typedef struct State SType;
 
 #define C1 0     //Estado con el sensor de la calle 1 activo
 #define W1 1     //Estado de transición de C1 a C2
 #define C2 2     //Estado con el sensor de la calle 2 activo
 #define W2 3     //Estado de transición de C2 a C1
 
 //Definición estados
 Stype fsm[4]={
  {0x21, 3000, {C1,W1,C1,W1}},
  {0x11, 500, {C2,C2,C2,C2}},
  {0x0C, 3000, {C2,C2,W2,W2}},
  {0x0A, 500, {C1,C1,C1,C1}}
 };
<br>
=== Programación controlador FSM ===
<br>
El código del controlador de la fsm es igual al del ejemplo anterior:<br>
  S = goN;                          //Colocamos el primer estado
  while(1){
    LIGHT = FSM[S].Out;             //Escribimos la salida
    SysTick_Wait10ms(FSM[S].Time);  //Esperamos
    Input = SENSOR;                 //Leemos
    S = FSM[S].Next[Input];         //Pasamos al siguiente estado según los inputs leidos
  }
<br>