Unidad 8.

Circuitos secuenciales
síncronos

Circuitos Electrónicos Digitales

E.T.S.I. Informática
Universidad de Sevilla
Diciembre, 2015
Jorge Juan <[email protected]> 2010-2015

Esta obra esta sujeta a la Licencia Reconocimiento-CompartirIgual 4.0 Internacional de Creative Commons. Para ver una copia de
esta licencia, visite http://creativecommons.org/licenses/by-sa/4.0/ o envíe una carta Creative Commons, PO Box 1866, Mountain
View, CA 94042, USA.

Departamento de Tecnología Electrónica – Universidad de Sevilla

Contenidos
● Introducción
● Biestables (latches)
● Máquinas de estados finitos y circuitos secuenciales síncronos (CSS)
● Diseño de CSS
● Análisis de CSS

Departamento de Tecnología Electrónica – Universidad de Sevilla

 Introducción
● Diseñe un sistema de control de una puerta de un garaje con dos
pulsadores separados por una distancia.
– x: abrir la puerta.
– y: cerrar la puerta.

abrir (x)
puerta (z)
cerrar (y)

Departamento de Tecnología Electrónica – Universidad de Sevilla

Introducción
● La mayoría de los problemas prácticos no pueden resolverse usando
sólo circuitos combinacionales.
● En muchos casos, la acción a realizar depende de las entradas y del
“estado” del sistema: la puerta está abierta, la luz está encendida, etc.
● Para “almacenar” el estado del sistema se necesitan nuevos elementos
de circuito: elementos de memoria.
● En esta unidad:
– Elementos de memoria.
– Concepto de “estado” y “circuito secuencial síncrono”.
– Técnicas de diseño y análisis de circuitos secuenciales síncronos.

Departamento de Tecnología Electrónica – Universidad de Sevilla

 Contenidos
● Introducción
● Biestables (latches)
– Biestables
– Biestable SR asíncrono
– Biestables síncronos
– Entradas asíncronas
– Temporización
● Máquinas de estados finitos y circuitos secuenciales síncronos (CSS)
● Diseño de CSS
● Análisis de CSS

Departamento de Tecnología Electrónica – Universidad de Sevilla

Biestables (latches)
● Los circuitos biestables son circuitos que pueden ser permanecer en
uno de dos posibles estados estables.
● El estado del biestable se puede conocer por el valor de señales de
salida del circuito.
● El estado puede cambiarse actuando sobre entradas de control.
● Los biestables son elementos básicos de memoria: almacenan 1 bit.
● Con n biestables pueden “memorizarse” 2 n estados posibles.

1 0 0 1 0 1 1 0

Departamento de Tecnología Electrónica – Universidad de Sevilla

 Biestable SR asíncrono
● La capacidad de almacenar información en los biestables se obtiene a
menudo usando “realimentación” de las salidas a las entradas del
circuito: el valor de salida refuerza el valor de entrada y viceversa.
● Posibles estados estables:
– q1=0, q2=1
– q1=1, q2=0
● Notación: q1 = q
– q = q2
– q = q1

q2 = q

Departamento de Tecnología Electrónica – Universidad de Sevilla

Biestable SR asíncrono
● Además de tener dos estados estables necesitamos una forma simple
de forzar cada estado.

S
q

q
R

Departamento de Tecnología Electrónica – Universidad de Sevilla

 Biestable SR asíncrono
● R=S=0 se conserva el estado

0 S 0 S
q 1 q 0

0 R q 0 0 R q 1

● S=1, R=0 cambio a 1 (set) S=0, R=1 cambio a 0 (reset)

1 0 S
S q 1
q 0

1 q 0
0 q 1 R
R

Departamento de Tecnología Electrónica – Universidad de Sevilla

Biestable SR. Descripción formal

Diagrama de estados
Símbolo Tabla de estados
SR=10
SR
00 01 11 10
q SR=0x SR=x0
S q 0 0 0 - 1 q=0 q=1
R
1 1 0 - 1
SR=01
Q
Verilog
module
module sra(
sra(
Tabla de excitación input
S q input s,
s,
input
input r,
r,
q→Q SR output
output reg
reg q);
q);
R q
0→0 0x always
always @(s,
@(s, r)
r)
case
case ({s,
({s, r})
r})
0→1 10 2'b01:
2'b01: qq <=
<= 1'b0;
1'b0;
1→0 01 2'b10:
2'b10: qq <=
<= 1'b1;
1'b1;
2'b11:
2'b11: qq <=
<= 1'bx;
1'bx;
1→1 x0 endcase
endcase
endmodule
endmodule

Departamento de Tecnología Electrónica – Universidad de Sevilla

 Biestables síncronos
● Los circuitos reales pueden contener miles de millones de biestables. Es
muy útil poder controlar cuándo cambian de estado y hacer que lo
hagan al mismo tiempo.
● Para ello, los cambios de estado se “sincronizan” con una “señal de
reloj” (CK, CLK, MCLK, etc.)
● La señal de reloj suele ser periódica con cambios a una frecuencia
prefijada: “frecuencia de reloj”.
● Biestables disparados por nivel (gated latches)
– El cambio de estado sólo es posible cuando la señal de reloj es 1 (nivel alto)
o 0 (nivel bajo).
● Biestables disparados por flanco (flip-flops)
– El cambio de estado sólo es posible cuando la señal de reloj cambia de 0 a
1 (flanco positivo) o de 1 a 0 (flanco negativo).
– El cambio de estado se determina con precisión.
– Hace más simple y robusto el diseño de circuitos digitales.

Departamento de Tecnología Electrónica – Universidad de Sevilla

Biestables síncronos
Biestable disparado por nivel Biestable disparado por flanco

module
module srl(
srl( S q module S q
input module srff(
srff(
input ck,
ck, input
input ck,
ck,
input
input s,
s, input
R input s,
s,
input
input r,
r, input Rck
output ck input r,
r,
output reg
reg q);
q); output
output reg
reg q);
q);
always
always @(ck,
@(ck, s,
s, r)
r) always
if always @(negedge
@(negedge ck)
ck)
if (ck
(ck ==
== 1)
1) case
case ({s,
({s, r})
r})
case
case ({s,
({s, r})
r}) 2'b01:
2'b01: 2'b01: qq <=
<= 1'b0;
1'b0;
2'b01: qq <=
<= 1'b0;
1'b0; 2'b10:
2'b10: qq <=
<= 1'b1;
1'b1;
2'b10:
2'b10: qq <=
<= 1'b1;
1'b1; 2'b11:
2'b11: 2'b11: qq <=
<= 1'bx;
1'bx;
2'b11: qq <=
<= 1'bx;
1'bx; endcase
endcase
endcase
endcase endmodule
endmodule endmodule
endmodule

Cambio de estado Cambio de estado cuando

cuando ck=1 ck cambia de 1 a 0

Departamento de Tecnología Electrónica – Universidad de Sevilla

 Biestables síncronos

S q qa S q ql S q qff

R R Rck
ck

Departamento de Tecnología Electrónica – Universidad de Sevilla

Otros biestables disparados por flanco

(flip-flops)
● SR
● JK
– Similar al SR: J~S, K~R
– Operación de complementar para J=K=1
● D
– Única entrada, valor del próximo estado.
– Fácil de usar e implementar.
● T
– Única entrada, complementa el estado cuando es 1.
– Muy útil en algunas aplicaciones especiales: ej. contadores.

Departamento de Tecnología Electrónica – Universidad de Sevilla

 Biestable JK

Símbolo Tabla de estados Diagrama de estados

JK JK=1x
q 00 01 11 10
JK=0x JK=x0
J q 0 0 0 1 1
q=0 q=1
K 1 1 0 0 1
ck
JK=x1
Q

Verilog
module
module jkff(
jkff(
J q
Tabla de excitación input
input ck,
ck,
input
input j,
j,
q→Q JK input
input k,
k,
K q output
output reg
reg q);
q);
ck 0→0 0x
always
always @(negedge
@(negedge ck)
0→1 1x case
ck)
case ({j,
({j, k})
k})
1→0 x1 2'b01:
2'b01: qq <=
<= 1'b0;
1'b0;
2'b10:
2'b10: qq <=
<= 1'b1;
1'b1;
1→1 x0 2'b11:
2'b11: qq <=
<= ~q;
~q;
endcase
endcase
endmodule
endmodule

Departamento de Tecnología Electrónica – Universidad de Sevilla

Biestable D

Símbolo Tabla de estados Diagrama de estados

D D=1
0 1
q
D=0 D=1
q 0 0 1
D q=0 q=1

ck
1 0 1
D=0
Q

Verilog
Tabla de excitación
q module
module dff(
dff(
input
input ck,
ck,
D q→Q D input
input d,
d,
q output
output reg
reg q);
q);
ck 0→0 0
0→1 1 always
always @(negedge
@(negedge ck)
ck)
qq <=
<= d;
d;
1→0 0
endmodule
endmodule
1→1 1

Departamento de Tecnología Electrónica – Universidad de Sevilla

 Biestable T

Símbolo Tabla de estados Diagrama de estados

T T=1
q 0 1
T=0 T=0
q 0 0 1
T q=0 q=1

ck
1 1 0
T=1
Q

Verilog
Tabla de excitación
q module
module tff(
tff(
input
input ck,
ck,
T q→Q T input
input t,
t,
q output
output reg
reg q);
q);
ck 0→0 0
0→1 1 always
always @(negedge
@(negedge ck)
ck)
if
if (t
(t ==
== 1)
1)
1→0 1 qq <=
<= ~q;
~q;
1→1 0 endmodule
endmodule

Departamento de Tecnología Electrónica – Universidad de Sevilla

Entradas asíncronas
● Forma fácil y directa de forzar un estado
CL
– CL (clear): puesta a 0 J q
– PR (preset): puesta a 1
K
● Efecto inmediato tras su activación: ck
– Activa en nivel bajo (0)
– Activa en nivel alto (1)
● Mayor prioridad que las entradas síncronas PR
– J, K, D, T, ... q
D
● Resuelven el problema de la inicialización en sistemas
digitales complejos ck
– Millones de biestables.
– Necesidad de comenzar a operar desde un estado
conocido.
CL PR
q
T

ck

Departamento de Tecnología Electrónica – Universidad de Sevilla

 Entradas asíncronas

CL PR CL PR CL PR CL PR
S q J q q q
D T
R K
ck ck ck ck

S=J, R=K, T=D

Departamento de Tecnología Electrónica – Universidad de Sevilla

Temporización
● Las entradas síncronas no deben cambiar en las proximidades del
flanco activo del reloj para evitar un cambio de estado no deseado.
● Tiempo de Set-up (ts)
– Tiempo antes del flanco durante el que las entradas deben permanecer
estables.
● Tiempo de Hold time (th)
– Tiempo después del flanco durante el que las entradas deben permanecer
estables.

Departamento de Tecnología Electrónica – Universidad de Sevilla

 Temporización. Ejemplo

q
ts th D

ck

CK

Q=1

Q=X
D
Q=X

Q=0

Departamento de Tecnología Electrónica – Universidad de Sevilla

Contenidos
● Introducción
● Biestables (latches)
● Máquinas de estados finitos y circuitos secuenciales síncronos
(CSS)
– Máquinas de estados finitos
– Circuitos secuenciales síncronos
– Representaciones formales
– Aplicaciones
● Diseño de CSS
● Análisis de CSS

Departamento de Tecnología Electrónica – Universidad de Sevilla

 Máquinas de Estados Finitos (MSF)
● “Máquinas de estados finitos deterministas” x1 x2 x3 ... z1 z2 z3 ...
● Una MSF está formada por:
x z
– Un conjunto finito de estados (S) δ, ω
– Un conjunto de símbolos de entrada (Σ)
– Un conjunto de símbolos de salida (Γ)
q Q
– Una función de próximo estado (δ)
● Q = δ(q, x)
estado
– Una función de salida (ω)
● Máquina de Mealy: z = ω(q, x)
S1
●
Máquina de Moore: z = ω(q) S2
S3
...

Mealy/Moore

x Q q
δ biestables ω z

Departamento de Tecnología Electrónica – Universidad de Sevilla

Máquinas de Estados Finitos (MSF)

Operación
● Llega un nuevo símbolo a la
entrada (x)
● Se calcula un nuevo símbolo de
x1 x2 x3 ... z1 z2 z3 ...
salida
z = ω(q, x) x z
δ, ω
● Se calcula el valor del próximo
estado de la máquina
Q = δ(q, x) q Q
● Se almacena el nuevo estado estado
● Se repite la operación
S1
S2
S3
...

Departamento de Tecnología Electrónica – Universidad de Sevilla

 Máquinas de Estados Finitos (MSF)
Propiedades
● Comenzando en el mismo estado, las MSF deterministas siempre
generan la misma secuencia de salida para la misma secuencia de
entrada.
● Dos MSF son equivalentes si generan la misma secuencia de salida
para la misma secuencia de entrada.
● Para toda máquina Mealy existe una máquina Moore equivalente, y
viceversa.
● Las MSF pueden optimizarse: MSF equivalente con un menor número
de estados.
● El estado de la MSF en cada momento depende del estado inicial y de
la secuencia de entrada hasta ese momento: el estado actual
representa la secuencia de símbolos de entrada pasados (historia de la
máquina).
● Una MSF puede no estar completamente especificada: el próximo
estado puede no estar definido para un estado actual y entrada dados.

Departamento de Tecnología Electrónica – Universidad de Sevilla

Circuitos Secuenciales Síncronos (CSS)

● Los circuitos digitales permiten implementar (hacer realizaciones
prácticas) de MSF: basta representar los símbolos de entrada y salida y
los estados mediante bits:
– Entradas/salidas: señales digitales de uno o más bits.
– Estado: palabra de n bits almacenada en biestables.
– Función de próximo estado: función lógica realizada con circuitos
combinacionales
– Función de salida: función lógica realizada con circuitos combinacionales.
● Los Circuitos Secuenciales Síncronos (CSS) son circuitos electrónicos
digitales que implementan MSF mediante circuitos combinacionales y
biestables.
● Por motivos prácticos, el instante de cambio de estado es controlado
por una señal de reloj que hace que todos los biestables cambien a la
vez, normalmente mediante disparo por flanco.

Departamento de Tecnología Electrónica – Universidad de Sevilla

 Circuitos Secuenciales Síncronos (CSS)

x z x z
δ, ω C.C.

q Q q Q

estado biestables

ck

Departamento de Tecnología Electrónica – Universidad de Sevilla

CSS. Representación formal

● Diagrama de estado
● Tabla de estados

Ejemplo 1: control de barrera

x=1: abre
y=1: cierra
z: control puerta (0: cerrado, 1: abierto)

Ejemplo 2: control de barrera con entrada simple

x=1 un ciclo: abre
x=1 dos o más ciclos: cierra
z: control puerta (0: cerrado, 1: abierto)

Departamento de Tecnología Electrónica – Universidad de Sevilla

 Diagrama de estados. Mealy
● Nodos
– Representan estados.
– Nombres intuitivos ¿?
1/0 ● {A, B, C, …}

B 0/0 ● {S0, S1, S2, …}

1/0
● {wait, start, receiving, ...}
● Arcos
1/0
A C – Representan posibles transiciones desde
1/1 un estado dado (S).
0/0
– Etiqueta x/z:
● x: valor de entrada que da lugar a la

0/0 0/0 transición desde el estado S.

D
● z: valor de salida de la máquina
cuando está en el estado S y la
entrada es x.

Departamento de Tecnología Electrónica – Universidad de Sevilla

Tabla de estados. Mealy

● Representación en forma de tabla de doble entrada con información
equivalente al diagrama de estados.
– Filas: posibles estados.
– Columnas: posibles valores de entrada.
– Celdas: próximo estado y valor de salida correspondiente.
● Cada nodo del diagrama de estados y los arcos que salen de él
corresponden a una fila en la tabla de estados.
● Pasar desde el diagrama de estados a la tabla de estados y vice-versa
es trivial.

Departamento de Tecnología Electrónica – Universidad de Sevilla

 Tabla de estados. Mealy

x 0 1
1/0 S
0/0 A A,0 B,0
1/0 B
B C,0 B,0

1/0
A C C D,0 B,0
0/0 1/1
D A,0 B,1

Q,z
0/0 D 0/0

Departamento de Tecnología Electrónica – Universidad de Sevilla

Diagrama de estados. Moore

● Nodos
1
– Representan estados.
0
1 B/0 – Nombres intuitivos ¿?
● {A, B, C, …}

● {S0, S1, S2, …}

A/0 0 1 1
C/0 ● {wait, start, receiving, ...}
0
E/1 – Cada nodo incluye el valor de salida
1 correspondiente a ese estado (Moore)

0
● Arcos
0 D/0
– Representan posibles transiciones desde
un estado dado (S).
– Etiqueta x: valor de entrada que da lugar a
la transición desde el estado S.

Departamento de Tecnología Electrónica – Universidad de Sevilla

 Tabla de estados. Moore
● Representación en forma de tabla de doble entrada con información
equivalente al diagrama de estados.
– Filas: posibles estados.
– Columnas: posibles valores de entrada.
– Celdas: próximo estado y valor de salida correspondiente.
●
Opcionalmente: valor de salida en columna aparte, ya que la salida sólo
depende del estado, no del valor de entrada.
● Cada nodo del diagrama de estados y los arcos que salen de él
corresponden a una fila en la tabla de estados.
● Pasar desde el diagrama de estados a la tabla de estados y vice-versa
es trivial.

Departamento de Tecnología Electrónica – Universidad de Sevilla

Tabla de estados. Moore

x
0 1 z
1 S
0 A A B 0
1 B/0
B C B 0

A/0 0 1 1
C/0 C D B 0
0
E/1
1 D A E 0

0 D/0 0 E A B 1

Departamento de Tecnología Electrónica – Universidad de Sevilla

 Mealy vs. Moore
● Ventajas Mealy
– Permite generar distintos valores de salida desde el mismo estado. Posible
ahorro de estados frente a máquina Moore equivalente.
– La salida se genera tan pronto está disponible la entrada. Posible menor
latencia frente a máquina Moore equivalente.
● Ventajas Moore
– Salidas siempre sincronizadas con la señal de reloj, aunque las entradas no
lo estén. Mayor robustez frente a fallos temporales.
– La mayor latencia frente a Mealy puede resolverse empleando registros de
salida.
● Moore preferible por la mayor robustez

Departamento de Tecnología Electrónica – Universidad de Sevilla

Aplicaciones de los CSS

● Detectores de secuencia
– La salida se activa sólo cuando las entradas reciben una determinada
secuencia de símbolos.
– Muchos problemas prácticos pueden describirse como detectores de
secuencia.
● Generadores de secuencias
– La salida genera una secuencia de símbolos fija o variable en función de las
entradas.
– Muchos problemas prácticos pueden describirse como detectores de
secuencia.

Departamento de Tecnología Electrónica – Universidad de Sevilla

 Aplicaciones de los CSS
● Unidades de control
– Las entradas reciben información sobre un sistema externo (estado del
sistema, sensores mecánicos, de humedad, temperatura, etc.) y las salidas
activan actuadores de forma adecuada (operaciones externas, actuadores,
calefactores, etc.)
– La máquina implementa efectivamente el algoritmo de control necesario.
– La señal de reloj determina con qué frecuencia se evalúa el estado del
sistema externo y se ejecuta la acción de control

señales de control

MSF Sistema externo

señales de estado

Departamento de Tecnología Electrónica – Universidad de Sevilla

Aplicaciones de los CSS

● Procesado (cálculo) secuencial
– La salida es el resultado de aplicar algún tipo de operación a los datos de
entrada:
● Cálculo de la paridad

● Operación aritmética secuencial

● Codificación/decodificación secuencial, etc.

Departamento de Tecnología Electrónica – Universidad de Sevilla

 Contenidos
● Introducción
● Biestables (latches)
● Máquinas de estados finitos y circuitos secuenciales síncronos (CSS)
● Diseño de CSS
– Objetivos del diseño
– Procedimiento de diseño manual
– Procedimiento de diseño con herramientas de diseño
● Análisis de CSS

Departamento de Tecnología Electrónica – Universidad de Sevilla

Diseño de CSS
Objetivo
● Objetivo
– Definir una MSF que resuelva el problema planteado
– Implementar la máquina de estados usando un CSS
● Criterios de coste
– Minimizar el número de elementos de memoria (número de estados)
– Minimizar número de dispositivos (parte combinacional)
– Frecuencia de operación (garantizar una frecuencia mínima)
– Consumo de energía (no superar un consumo máximo)
– Etc.
● Se debe alcanzar un compromiso entre diferentes factores

Departamento de Tecnología Electrónica – Universidad de Sevilla

 Diseño de CSS
Procedimiento
● Procedimiento manual
– Puede realizarse con papel y lápiz.
– Comienza con una formalización del problema mediante un diagrama o tabla
de estados.
– La tabla de estados se transforma en diferentes pasos hasta obtener una
representación en forma de circuito digital.
● Procedimiento automático mediante herramientas de diseño (CAD)
– El problema se formaliza mediante una descripción con un lenguaje de
descripción de hardware.
– Se simula la descripción para asegurar que es correcta.
– Se usan herramientas de síntesis automática para generar el circuito.

Departamento de Tecnología Electrónica – Universidad de Sevilla

Diseño de CSS
Procedimiento manual

Descripción verbal
Tabla de transición de estados
del problema

Traducción Selección de biestables

Diagrama de estados
Tabla de excitación
Tabla de estados

Reducción de estados Diseño de la parte combinacional

Tabla de estados mínima

Puertas Multiplexores
+ + Etc.
Biestables Biestables
Asignación de estados

Departamento de Tecnología Electrónica – Universidad de Sevilla

 Traducción
● Parte más importante del proceso de diseño
Descripción verbal
del problema ● No sistemática
● Pistas/consejos:
Traducción – Definir claramente entradas y salidas
– Seleccionar Mealy o Moore según el problema:
sincronización de salidas, etc.
Diagrama de estados
Tabla de estados – Definir secuencias de ejemplo para comprender
mejor el problema y detectar posibles casos
especiales.
– Representar el problema mediante un diagrama o
tabla de estados.
– Definir estados de la forma más general posible:
estados similares pueden ser el mismo estado.
– Comprobar el diagrama/table mediante
secuencias de ejmplo.

Departamento de Tecnología Electrónica – Universidad de Sevilla

Traducción
● Ejemplo
– Diseñar un circuito con una entrada x y una salida z que detecte la llegada
de la secuencia “1001” en x. Cuando se detecta la secuencia, z permanece
a 1 durante un ciclo de reloj. Las secuencias pueden solaparse (el último 1
de una secuencia puede ser el primero de la siguiente).

x:
x: 00100111000011101001001001010011...
00100111000011101001001001010011...
x z
z:
z: 00000100000000000001001001000010...
00000100000000000001001001000010...

Departamento de Tecnología Electrónica – Universidad de Sevilla

 Traducción

1/0 x
0 1
0/0 S
1/0 B A,0 B,0
A

B C,0 A,0
1/0
A C
0/0 1/1 C D,0 B,0

D A,0 B,1
0/0 D 0/0
Q,z

A: esperando primer bit de la secuencia "1"

B: 1er bit correcto, esperando "0"
C: 2º bit correcto, esperando "0"
D: 3er bit correcto, esperando "1"

Departamento de Tecnología Electrónica – Universidad de Sevilla

Reducción de estados
● Objetivo:
Tabla de estados
– Eliminar estados redundantes.
– Reducir el coste en número de biestables y lógica
Reducción de estados
combinacional.

Tabla de estados mínima

Estados equivalentes:

Dos estados p y q son equivalentes si cualquier secuencia de

entrada aplicada a la máquina comenzando en el estado p
produce exactamente la misma secuencia de salida
comenzando en q.

Dos estados p y q son equivalentes si y sólo si:

● Todos los próximos de p y q son idénticos o equivalentes

para cada valor de entrada.

● Los valores de salida de p y q son iguales para cada valor

de entrada.

En una tabla de estados mínima no hay estados equivalentes.

Departamento de Tecnología Electrónica – Universidad de Sevilla

 Reducción de estados
Procedimiento
● Comenzando con la tabla de estados, se comparan todas las parejas de
estados para identificar posibles estados compatibles.
● La tabla de estados compatibles ayuda a identificar estados
compatibles y las condiciones de compatibilidad.
● Una vez detectados todos los estados compatibles, se agrupan en
clases de equivalencia.
● Se construye una nueva tabla de estados usando las clases de
equivalencia obtenidas.

Departamento de Tecnología Electrónica – Universidad de Sevilla

Reducción de estados
Ejemplo 1

x
S 0 1

A B,0 C,0
x
B D,0 E,0 S 0 1
C G,0 E,0 a b,0 a,0
D H,0 F,0 b d,0 a,0
E G,0 A,0 d h,0 f,0
F G,1 A,0 f b,0 a,0
G D,0 C,0 h h,0 a,0
H H,0 A,0 NS, z
NS, z

Departamento de Tecnología Electrónica – Universidad de Sevilla

 Reducción de estados
Ejemplo 2

x
0 1
S
A A,0 B,0

B C,0 A,0

C D,0 B,0

D A,0 B,1
Minimum state table

Q,z

Departamento de Tecnología Electrónica – Universidad de Sevilla

Asignación de estados
● Objetivo:
Tabla de estados mínima
– Asignar valores binarios a los estados
(codificación de estados).
Asignación de estados
– Permite almacenar el estado en biestables.
● Selección de la codificación
Tabla de transición
– Afecta al resultado final: número de
de estados dispositivos, tamaño del circuito,
retraso/velocidad de operación, consumo de
energía, etc.
● Opciones típicas
– Algoritmos de asignación complejos:
optimizan el resultado final.
– Asignación arbitraria o aleatoria: circuitos
simples o cuando el coste no es importante.
– Un biestable por estado (codificación one-hot):
cuando no es importante minimizar el uso de
biestables. Uso típico en FPGA.

Departamento de Tecnología Electrónica – Universidad de Sevilla

 Asignación de estados

Asignación de estados Tabla de transición

Tabla de estados
de estados

x x
0 1 S q1q0 0 1
S q1q2
A A,0 B,0 A 00 00 00,0 01,0
B 01
B C,0 A,0 01 11,0 00,0
C 11
C D,0 B,0 D 10 11 10,0 01,0

D A,0 B,1 10 00,0 01,1

NS,z Q1Q2,z

Departamento de Tecnología Electrónica – Universidad de Sevilla

Selección de biestables

Tabla de transición
● Objetivo
de estados – Seleccionar el tipo de biestables que
almacenarán el estado codificado.
Selección de biestables ● Opciones:
– JK: reduce el coste de la parte combinacional
pero necesita dos entradas de control.
Tabla de excitación – SR: más simple que el JK internamente, pero
menos flexible.
– D: Simplifica el diseño y reduce el número de
conexiones (una entrada de control).
– T: útil en aplicaciones con cambios de estado
frecuentes.
● Restricciones
– Sujeto a disponibilidad de biestables.
– Componentes discretos: JK, por flexibilidad y
simplificación de la parte combinacional.
– Diseño integrado (ej. FPGA): D, elemento básico
disponible.

Departamento de Tecnología Electrónica – Universidad de Sevilla

 Selección de biestables
Ejemplo: JK
Tabla de transición
Tabla de excitación
de estados Tabla excitación JK

q→Q JK
x 0→0 0x x
0 1 0 1
q1 q2 0→1 1x q1q2
00 00,0 01,0 1→0 0x 00 0x,0x,0 0x,1x,0

1→1 x0
01 11,0 00,0 01 1x,x0,0 0x,0x,0

11 10,0 01,0 11 x0,0x,0 0x,x0,0

10 00,0 01,1 10 0x,0x,0 0x,1x,1

Q1Q2,z J1K1,J2K2,z

Departamento de Tecnología Electrónica – Universidad de Sevilla

Selección de biestables
Ejemplo: D
● Biestable D:
– El próximo estado es igual a D
– La excitación para alcanzar un próximo estado Q es: D = Q

Tabla de transición
Tabla de excitación
de estados

x
0 1
q1q2
00 00,0 01,0

01 11,0 00,0

11 10,0 01,0

10 00,0 01,1

Q1Q2,z
D1D2,z

Departamento de Tecnología Electrónica – Universidad de Sevilla

 Diseño de la parte combinacional
● La tabla de excitación especifica
x z completamente la parte
C.C. combinacional.
● La implementación de la parte
q Q combinacional puede usar cualquiera
de las técnicas disponibles:
biestables – Diseño en dos niveles con puertas
lógicas (K-mapa, etc.)
– Diseño con subsistemas:
Tabla de excitación multiplexores, decodificadores, etc.
– Otras.

Diseño combinacional

Puertas Multiplexores
+ + Etc.
Biestables Biestables

Departamento de Tecnología Electrónica – Universidad de Sevilla

Diseño de la parte combinacional

Ejemplo: diseño con puertas lógicas
x x x
q1q2 0 1 q1 q2 0 1 q 1 q2 0 1

00 0 0 00 x x 00 0 0

x
01 1 0 01 x x 01 0 0
0 1
q1q2 11 x 0 11 0 x 11 0 0
00 0x,0x,0 0x,1x,0 10 0 0 10 x x 10 0 1
J1 K1 z
01 1x,x0,0 0x,0x,0
x x
11 x0,0x,0 0x,x0,0 q1q2 0 1 q1q2 0 1

00 0 1 00 x x J1 = xq2
10 0x,0x,0 0x,1x,1 K1 = 0
01 x 0 01 0 x
J1K1,J2K2,z 11 0 x 11 x 0 J2 = xq2
K2 = 0
10 0 1 10 x x
z = xq1q2
J2 K2

Departamento de Tecnología Electrónica – Universidad de Sevilla

 Implementación del circuito
Ejemplo
J1 = xq2
K1 = 0
J2 = xq2
K2 = 0
z = xq1q2 CL

CL CL
J1 q1 J2 q2
x

0 K1 0 K2
ck ck

ck

Departamento de Tecnología Electrónica – Universidad de Sevilla

Diseño de CSS
Resumen del ejemplo
1/0 x x
0 1 0 1
0/0 S q1q2
1/0 B
A A,0 B,0 00 00,0 01,0

A 1/0 C B C,0 A,0 01 11,0 00,0

0/0 1/1

C D,0 B,0 11 10,0 01,0

0/0 D 0/0
D A,0 B,1 10 00,0 01,1
x
0 1 Q,z Q,z
q1 q2
00 0x,0x,0 0x,1x,0

J1 = xq2 CL

01 1x,x0,0 0x,0x,0
K1 = 0 CL CL
J1 q1 J2 q2
J2 = xq2 x
11 x0,0x,0 0x,x0,0 K1 0 K2
K2 = 0 0
ck ck

10 0x,0x,0 0x,1x,1 z = xq1q2 z

ck
J1K1,J2K2,z

Departamento de Tecnología Electrónica – Universidad de Sevilla

 Procedimiento de diseño empleando
herramientas CAD
Descripción verbal
del problema

Traducción Diagrama de estados

Descripción en LDH Traducción

Banco de pruebas Simulación

no sí
¿ok? Síntesis automática Circuito

Configuración

Departamento de Tecnología Electrónica – Universidad de Sevilla

Descripción de MSF en Verilog

Mealy

//
// State
State change
change process
process (sequential)
(sequential)
x Q q always
δ biestables ω z always @(posedge
@(posedge ck,
ck, posedge
posedge reset)
reset)
if
if (reset)
(reset)
state
state <=
<= A;
A;
else
else
state
state <=
<= next_state;
next_state;
● Tres procesos
//
// Next
Next state
state calculation
calculation process
process
– Cambio de estado. Representa el //
// (combinational)
(combinational)
bloque de biestables. always
always @* @* begin
begin
case
case (state)
(state)
– Cálculo del próximo estado. A:
A:
Representa las funciones de next_state
next_state == .. .. .;
.;
próximo estado (δ) B:
B:
next_state
next_state == .. .. .;
.;
– Cálculo de la salida. Representa .. .. ..
las funciones de salida (ω). endcase
endcase
end
end
● Sólo el proceso de cambio de
estado es secuencial (incluye //
// Output
Output calculation
calculation process
process
//
// (combinational)
elementos de memoria) (combinational)
always
always @* @* begin
begin
zz == .. .. .;
.;
end
end

Departamento de Tecnología Electrónica – Universidad de Sevilla

 Descripción de MSF en Verilog
Ejemplo
x
ck z
Ver ejemplo detector de secuencia
reset

1
1/0
0
0/0 1 B/0
1/0 B

A/0 0 1 1
A 1/0
C C/0
0
0/0 1/1 E/1
1

0 D/0 0
0/0 D 0/0

Departamento de Tecnología Electrónica – Universidad de Sevilla

Contenidos
● Introducción
● Biestables (latches)
● Máquinas de estados finitos y circuitos secuenciales síncronos (CSS)
● Diseño de CSS
● Análisis de CSS
– Análisis funcional
– Análisis temporal

Departamento de Tecnología Electrónica – Universidad de Sevilla

 Análisis funcional
● Proceso opuesto al de síntesis
● Objetivo:
– A partir del circuito construido, describir la operación general del circuito y su
utilidad.
● Procedimiento
– Obtención de comportamiento síncrono mediante la representación con
diagrama o tabla de estados. Este proceso es sistemático y consiste en
realizar los pasos de la síntesis en orden inverso.
– Descripción del comportamiento asíncrono: inicialización, etc.
– Descripción de la operación: determinar la utilidad y comportamiento del
circuito. No sistemático. Depende de la experiencia del diseñador y de
posible información adicional:
● ¿En qué tipo de sistema se encuentra el circuito?

● ¿Se conoce el tipo de aplicación? Alarma, control, etc.

Departamento de Tecnología Electrónica – Universidad de Sevilla

Análisis funcional

Circuito: biestables y
elementos combinacionales

Análisis combinacional
Tabla de estados/
Diagrama de estados
Tabla de excitación

Traducción

Análisis de biestables

Descripción verbal

Tabla de transición de estados

Definición de estados

Departamento de Tecnología Electrónica – Universidad de Sevilla

 Análisis funcional
Ejemplo

J1 q1
z
K1

ck

J2 q2
x

K2

ck

Departamento de Tecnología Electrónica – Universidad de Sevilla

Análisis temporal
● Objetivo: dado un CSS y un conjunto de señales de entrada, obtener las
señales de salida correspondientes y su evolución en el tiempo.
● Consideraciones
– Es posible analizar circuitos con biestables que no son CSS.
– Si el circuito es un CSS, la secuencia de estados/salida extraída del análisis
temporal debe corresponder con la secuencia de estados/salida de la MSF
que implementa.
● Similar al análisis temporal de circuitos combinacionales, añadiendo
biestables.
– Parte combinacional: idéntica.
– Biestables
● Comportamiento síncrono: aplicar el próximo estado en cada flanco

activo del reloj, usando la tabla de estados del biestable.

● Comportamiento asíncrono: aplicar próximo estado según señales
asíncronas.
– Retrasos: los biestables tienen retrasos desde el reloj a la salida (síncrono) y
desde las entradas asíncronas a la salida (asíncrono): tck-q, tCL-q, etc.

Departamento de Tecnología Electrónica – Universidad de Sevilla

 Análisis temporal
Ejemplo
clk
cl
x
y

cl
CL
q1
x D1
y a
z

CL
J2 q2

K2

clk

Departamento de Tecnología Electrónica – Universidad de Sevilla

Análisis temporal
Ejemplo
clk
cl
x=J2
y=K2
D1

q1
q2

a
z

D1 = x ⊕ y
J2 = x; K2 = y
a = q1 x
z = a ⊕ q2

Departamento de Tecnología Electrónica – Universidad de Sevilla