• Author / Uploaded
• Chris Castro

Citation preview

UNIVERSIDAD NACIONAL DE SAN AGUSTÍN FACULTAD DE INGENIERIA DE PRODUCCIÓN Y SERVICIOS-ESCUELA PROFESIONAL DE INGENIERÍA EN TELECOMUNICACIONES

CURSO: SISTEMAS DIGITALES DOCENTE: ING. JUAN CARLOS CUADROS TRABAJO DE INVESTIGACIÓN “MAQUINAS DE ESTADO” PRESENTADO POR:  CASTRO CASTRO, CHRISTIAN DAVID  VAGAYA QUISPE, GENNODY JOEL  CONDORI CALLA, LUIS CARLOS AREQUIPA-PERÚ 2019

INDICE

1. Máquinas de estado……………………………………………….…...... 1 1.1. Circuito Lógico Secuencial………………………………………….. 1 1.2. Diagramas de funcionamiento……………………….……………..... 6 2. Tipos…………………………………………………………………..… 2 2.1. Máquina de Mealy………………………………………………...…. 2 2.2. Máquina de Moore………………………………………………...…. 3 3. Análisis de estado ………………………………………………………... 4 4.Diseño de máquinas de estado………………………………………….… 6 5. Bibliografía………………………………………………………………..10

1. MÁQUINAS DE ESTADO 1.1.

INTRODUCCIÓN Hablar sobre la teoría de máquinas de estado, es igual a hablar de métodos de análisis, diseño y tipos de Circuitos Lógicos Secuenciales. Como bien se sabe la teoría de sistemas digitales, divide los circuitos lógicos en 2 partes; combinacionales y secuenciales. Y que la diferencia entre ambas es que las salidas de los circuitos lógicos combinacionales únicamente dependen de las entradas, mientras que las salidas de los circuitos lógicos secuenciales dependen de las entradas y los valores anteriores de las salidas. Una máquina de estado finita (FSM) es la representación de un sistema como un conjunto de estados, transiciones entre los estados, los cuales dependen de las entradas, conjuntamente con las entradas y las salidas asociadas.

1.2. CIRCUITO LÓGICO SECUENCIAL (CLS): No es más que un circuito lógico secuencial cuya salida depende del valor de las entradas y los valores anteriores de las salidas. Componentes: los componentes de un CLS son  Señales de entrada y salida  Señal de reloj, la cual pertenece a los componentes biestables también conocidos como flip-flop  Lógica combinacional  Almacenamiento

ESQUEMA GENERAL DE UN CIRCUITO SECUENCIAL SINCRONO

Figura 1

1

Del esquema se puede entender que: - Los bloques correspondientes a funciones, pertenecen a la parte de circuitos lógicos combinacionacionales, para lo cual se usan los componentes de estos, como las compuertas lógicas. - El bloque de estado está formado por los componentes biestables, todos estos sincronizados a una misma señal de reloj. Ahora bien, el comportamiento de estos circuitos lógicos secuenciales, se puede representar mediante una máquina de estados finitos FSM (Finite State Machine). ELEMENTOS DE UNA MAQUINA DE ESTADOS  X = Entradas  Y = Salidas  Z = Estados(correspondiente a los componentes biestables)  δ= Funciones de estado (Funciones combinacionales de entrada de los biestables)  λ= Funciones de salida.

2. TIPOS Estas máquinas de estado se distinguen comúnmente en dos tipos: Maquinas de Mealy y Maquinas de Moore. 2.1. MAQUINA DE MEALY En esta máquina de estados las salidas se encuentran determinadas por el estado interno del sistema y por las entradas no sincronizadas con el circuito, en pocas palabras las salidas dependen tanto de los estados como de las entradas. En la Figura 2 se muestra la estructura general asociada a una máquina de Mealy.

Figura 2

La figura 2 muestra que las salidas dependen de los estados como también de las entradas.

2

DIAGRAMA DE ESTADOS:

Estado 2 Entrada 1 / Salida 1

Estado 1

Estado 3 Entrada 2 / Salida 2

2.2.

Cada círculo del diagrama representa un estado. Cada transición de estado a estado, está representado por una flecha. Los valores de las entradas están representadas en las flechas. En el caso de la máquina de Mealy, las salidas se representan en las flechas.

MAQUINA DE MOORE

En esta máquina las salidas solo dependen del estado interno y de cualquier entrada sincronizada con el circuito como puede apreciarse en la estructura de una máquina de Moore mostrada en la Figura 3.

Figura 3 Como se puede comprobar en la Figura 3, a diferencia de la máquina de Mealey, la salida ya no depende de las entradas.

3

DIAGRAMA DE ESTADOS:

𝑬𝒔𝒕𝒂𝒅𝒐 𝟐 𝑺𝒂𝒍𝒊𝒅𝒂 𝟐

Entrada 1

𝑬𝒔𝒕𝒂𝒅𝒐 𝟏 𝑺𝒂𝒍𝒊𝒅𝒂 𝟏

Entrada 2

-

𝑬𝒔𝒕𝒂𝒅𝒐 𝟑 𝑺𝒂𝒍𝒊𝒅𝒂 𝟑

Cada círculo representa un estado del circuito. Cada transición de estado está representado por una flecha. Los valores de las entradas están representadas en las flechas. A diferencia de la máquina de Mealey, en la máquina de Moore las salidas se representan dentro de los círculos de estado.

3. ANÁLISIS DE MAQUINAS DE ESTADO El análisis de los circuitos secuenciales consiste en obtener su funcionalidad a partir de un circuito para lo cual es necesario:  Obtener diagramas de estado  Obtener funciones de estado  Obtener funciones de salida  Obtener tablas de transiciones Para explicar mejor el análisis, se tomara como ejemplo el Circuito Lógico Secuencial de la Figura 4

4

Figura 4 Primero: Obtenemos las funciones de estados y de salida de acuerdo al circuito

𝐷 = ̅̅̅̅̅̅̅̅̅̅̅ 𝑄0 + 𝐸𝑛 𝛿→{ 0 𝐷1 = ̅̅̅ 𝑄1 . 𝐸𝑛

̅̅̅1 . 𝑄0 𝜆 → 𝑆𝑎𝑙𝑖𝑑𝑎 = 𝑄

Segundo: Obtenemos la tabla de transiciones Q1

Q0

En

D1

D0

0 0 0 0 1 1 1 1

0 0 1 1 0 0 1 1

0 1 0 1 0 1 0 1

0 1 0 1 0 0 0 0

1 0 0 0 1 0 0 0

Q1 Q0 Salida sig. sig. 0 1 0 1 0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0

Tercero: De acuerdo a esta tabla de transiciones, podemos establecer nuestro diagrama de estados, y podemos notar que hay 3 posibles estados en las salidas de los biestables o flip-flops. Pero primero se debe entender que, para cada estado hay dos posibles estados siguientes, la cual estará determinada de acuerdo a la entrada en ella. Por ejemplo para el caso del estado 00 los posibles estados siguientes son 01 y 10, entonces basándose en la tabla se nota que cuando la entrada (En) es igual a 0, el siguiente estado es 01 y de igual forma cuando la entrada (En) es igual 1, el siguiente estado es 10.

5

DIAGRAMA DE ESTADOS (MEALEY) 0/0 01

0/1 00

0/0

1/1

1/0 10

1/0

Tal y como la teoría lo indica, en el diagrama de estados para las máquinas de Mealey, cada estado está representado en los círculos. Ahora, los números indicados en las flechas están escritos en el orden (entrada/salida) que son valores obtenidos de la tabla de transiciones. DIAGRAMA DE ESTADOS (MOORE) 0

01/1

0 1 0

00/0

1 1

10/0

La diferencia entre el diagrama de estados entre una máquina de Mealey y una de Moore se puede ver aquí, en donde para la máquina de Moore, los círculos de estado también incluyen la salida de la forma (estado/salida) y en las flechas solo están representadas las entradas para cada estado.

4. DISEÑO DE MAQUINAS DE ESTADO Partiendo del análisis del comportamiento de las máquinas de estado, también podemos diseñar o sintetizarlas, siguiendo una serie de pasos descritos a continuación podremos hacer el proceso de diseño, y son los siguientes: 1. Obtener el diagrama de estados 2. Obtener tablas de salidas y de transiciones de estados 3. Tabla de excitación de inestables 4. Obtener funciones de salida 5. Obtener funciones de estado 6. Implementación 6

TABLAS DE EXITACION Es importante saber las tablas de cada tipo de flip-flop, porque estas describen las posibles combinaciones de entradas que permiten salir del estado actual Q al estado siguiente Q sig. FLIP-FLOP J-K Q1 0 0 1 1

Q sig. 0 1 0 1

S

R

0 1 0 X

X 0 1 0

FLIP-FLOP D Q1 0 0 1 1

D

Q sig. 0 1 0 1

0 1 0 1

EJEMPLO Diseñaremos una máquina de Mealey usando el Flip-Flop D. 1. Diagrama de estados

1/0 0/1

0/0

0/0 0/0

0/0

1/0

1/1

7

1/1

2. Tabla de salidas y transiciones de estados En 0 0 0 0 1 1 1 1

Q1

Q0

0 0 1 1 0 0 1 1

0 1 0 1 0 1 0 1

Q1 Q0 Salida sig. sig. 0 0 0 0 0 0 X X X 0 0 0 0 1 0 1 1 0 X X X 1 1 1

Tener en cuenta que el estado 10 no está disponible o no alcanzable de acuerdo al diagrama de estados. 3. En 0 0 0 0 1 1 1 1

Tabla inversa de biestables: Q1

Q0

0 0 1 1 0 0 1 1

0 1 0 1 0 1 0 1

Q1 Q0 Salida sig. sig. 0 0 0 0 0 0 X X X 0 0 0 0 1 0 1 1 0 X X X 1 1 1

D1

D0

0 0 X 0 0 1 X 1

0 0 X 0 1 1 X 1

4. Función de Salida: Para esto haremos uso de los mapas de Karnaugh, correspondiente a la salida deacuerdo a la tabla.

Y tenemos que: 𝑆𝑎𝑙𝑖𝑑𝑎 = 𝑄1 . 𝐸𝑛 5. Funciones de Estado: También haremos uso de los mapas de Karnaugh, correspondiente cada biestable.

8

Y obtenemos que: 𝐷1 = 𝑄0 . 𝐸𝑛

Y de este último obtenemos que 𝐷0 = 𝐸𝑛 6.

IMPLEMENTACION:

Teniendo ya todo listo, podemos proceder a implementar el circuito.

9

5. BIBLIGRAFIA

 



Abad, P., & Prieto, P. (s.f.). Sistemas Digitales. Recuperado 13 julio, 2019, de https://ocw.unican.es/pluginfile.php/313/course/section/261/tema_04.pdf Casasnovas, M. Ing (2004, julio). Máquinas de Estado Finitas. Recuperado 13 julio, 2019, de http://www.profesores.frc.utn.edu.ar/electronica/tecnicasdigitalesi/pub/file/Ap ortesDelCudar/Maquinas%20de%20Estado%20MC%20V5.pdf Álvarez, A., & Coya, C. (s.f.). Diseño de circuitos secuenciales mediante diagramas de estados. Recuperado 13 julio, 2019, de http://www.cartagena99.com/recursos/alumnos/apuntes/Microsoft%20PowerP oint%20-%20SistDig-7-2010-1415_A%20%5bModo%20de%20compatibilidad%5d%20-%20SistDig-5-1718_A.pdf

10