automatas

‘Análisis y síntesis de sistemas secuenciales
‘Análisis
síncronos’
Introducción
Autómatas de estados finitos
Metodología
Análisis de circuitos secuenciales
Síntesis de circuitos secuenciales
Comparación entre autómatas de Moore y Mealy
Caso particular: autómata sin entradas
Conclusiones

M. Mazo, S. E. Palazuelos, L. M. Bergasa

1

Introducción
Aspectos generales de los sistemassecuenciales
Entradas
Estado
actual

Circuito
Circuito
combinacional
combinacional
Memoria
Memoria

Selección
producto

Espera

No hay
moneda
Espera moneda
Informa precio
Introducción
de moneda

Entrega
producto

Salidas
Información para
generar el próximo
estado

Introducción
No hay de moneda
selección
Espera selección
de producto
Selección de
producto

M.Mazo, S. E. Palazuelos, L. M. Bergasa

• Entrada
• Entrada
• Salida
• Salida
• Estado
• Estado
• Transición
• Transición

2

1

Índice

Introducción
Autómatas de estados finitos
Definición
Nomenclatura
Tipos de circuitos secuenciales síncronos
Representación de los autómatas
Metodología
Análisis de circuitos secuenciales
Síntesis de circuitos secuenciales
Comparaciónentre autómatas de Moore y Mealy
Caso particular: autómata sin entradas

M. Mazo, S. E. Palazuelos, L. M. Bergasa

3

Autómatas de estados finitos (I)
Definición de autómata
Entradas x(t)

z(t)

Circuito
Circuito

Salidas

combinacional
combinacional
Estado
q(t)
actual

Excitaciones
para generar
e(t)
el próximo
estado

FF0
FF0
FF1
FF1
.
.
.

CLK

FFp-1
FFp-1Memoria
p flip-flops

2p estados como máximo

M. Mazo, S. E. Palazuelos, L. M. Bergasa

4

2

Autómatas de estados finitos (II)
Nomenclatura

Nombre de la
variable

Símbolo
general

Nombre de las
líneas físicas en
el circuito

Nº de
líneas
físicas

Combinaciones de la
variable

Nº de combs.
necesarias

Entradas

x(t), xt

X0, X1, ..., Xu-1

u

X={x0, x1,..., xn-1}

n#2u

Salidas

z(t), zt

Z0, Z1, ..., Zv-1

v

Z={z0, z1, ..., zr-1}

r#2v

Estados (salidas de
los biestables)

q(t), qt

Q0, Q1, ..., Qp-1

p

Q={q0, q1, ..., qm-1}

m#2p

Excitación de los
biestables
(realimentación)

e(t), et

E0, E1, ..., Es-1

s

E={e0, e1, ..., el-1}

l#2s

M. Mazo, S. E. Palazuelos, L. M. Bergasa

5

Autómatas deestados finitos (III)
Tipos de circuitos secuenciales síncronos

Autómata de Moore

Autómata de Mealy

zt = g [qt]

zt = g [xt, qt]

qit+1 = h(f [xt, qt])

qit+1 = h(f [xt, qt])

Bloque combinacional
xt

zt

Bloque combinacional

xt

Func. salida g
Func. salida g
Func. transición f
Func. transición f

CLK

Func. transición f
Func. transición f
et

qt
FF’s
FF’sBloque memoria

zt

Func. salida g
Func. salida g

et

qt
CLK

FF’s
FF’s
Bloque memoria

M. Mazo, S. E. Palazuelos, L. M. Bergasa

6

3

Autómatas de estados finitos (IV)
Representación de circuitos secuenciales síncronos (I)

Autómata de Moore

Grafo

Tabla de estados o de transiciones

Entrada

Transición

10

Estado/salida

Estado
actual
qt

00

11q1/11

00

q0/00

01
10 11

00
01

10

11

q2/01

01

01

01
q3/10

q0
q1
q2
q3

Entrada actual
xt
00

01

10

11

q0
q1
q0
q2

q2
q3
q2
q1

q2
q1
q2
q1

q1
q2
q1
q3

zt
0
1
0
1

0
1
1
0

qt+1
Próximo estado

11

00

Salida
actual

10
M. Mazo, S. E. Palazuelos, L. M. Bergasa

7

Autómatas de estados finitos (V)Representación de circuitos secuenciales síncronos (II)

Autómata de Mealy
Grafo
Entrada/salida

Transición

1/0

Estado

q1
0/0

1/0

q0

0/1

0/0
1/0

q3

0/0

q2

Tabla de estados o de
transiciones
Estado
actual
qt
q0
q1
q2
q3

1/0
M. Mazo, S. E. Palazuelos, L. M. Bergasa

Entrada actual
xt
0
q0/0
q0/0
q0/0
q0/1

1
q1/0
q2/0
q3/0
q0/0...