Fct6.pdf

CIRCUITOS SECUENCIALES 3

Tema 6: ANÁLISIS Y DISEÑO DE CIRCUITOS SECUENCIALES SÍNCRONOS Contenido: J

Elementos de memoria: biestables asíncronos y síncronos. Biestables JK, T, D. Entradas asíncronas.

J

Modelo general de máquina secuencial: máquinas de Mealy y de Moore. Representación mediante diagramas y tablas. Estructura general de un circuito secuencial síncrono.

J

Procedimiento de análisis de circuitos secuenciales síncronos.

J

Pasos en el proceso de diseño. Ejemplo de diseño. Optimización del diseño: * reducción de estados * asignación de estados * elección de biestables

Bibliografía

FC

* * * * *

M. Morris Mano y Charles R. Kime: Cap 6 V. P. Nelson et al: Cap 6 y 8 C.H. Roth: Caps 11, 13, 14, 15, 16 J. Wakerly: Cap 7 C. Baena et al: Cap 7 y 8

Dpto. Tecnología Electrónica, U. Sevilla.

Fundamentos de Computadores

Circuitos Secuenciales 1

CIRCUITOS SECUENCIALES Circuitos digitales: Combinacionales y Secuenciales

Combinacionales x1

Secuenciales S1

S1 Suma

x0

x

Suma S0

S0

x1

FC

x0

x

S1

S1

S0

S0

S(t0) = F( x(t0) )

Dpto. Tecnología Electrónica, U. Sevilla.

S(t0) = F( x(t0), x(t < t0))

Fundamentos de Computadores

Circuitos Secuenciales 2

CIRCUITOS SECUENCIALES Elementos de memoria: biestables D Biestables (latches, flip-flops): son los circuitos que almacenan 1 bit de información D

entradas de excitación

q

* *

q

En todo momento, el biestable tiene almacenado un bit, q = 0 o q = 1, que es su estado presente El valor del bit se cambia con las entradas de excitación. Estas, pues, indican lo que almacenará como siguiente valor o próximo estado (Q o q+)

D Los biestables son los componentes básicos secuenciales. Hay múltiples tipos: H A nivel lógico, según sean las entradas de excitación (SR, JK, ...)

FC

H A nivel temporal, según sea la forma de disparo, esto es, cuándo/cómo cambia ‘q’ H A nivel de realización, según el almacenamiento del bit haya que refrescarlo o no

Dpto. Tecnología Electrónica, U. Sevilla.

Fundamentos de Computadores

Circuitos Secuenciales 3

CIRCUITOS SECUENCIALES BIESTABLES A NIVEL LÓGICO D Las entradas de excitación suelen ser sólo 1 o 2 D Los biestables más típicos son: SR (Set Reset), JK, D (Data o Delay) y T (Toggle). Se describen por sus tablas y ecuaciones de cambio de estado SR q 00 01 11 10 0 0 0 - 1 1 1 0 - 1 Q Q = S + R·q

FC

q

JK 00 01 11 10 0 0 0 1 1 1 1 0 0 1 Q

q

Q = J·q + K·q

D

0 0 0 1 0

Fundamentos de Computadores

q

T

0 0 0 1 1

1 1 0 Q

Q=T⊕q

Q=D

y por sus tablas de excitación para cambios de estado q J Q SR q J Q JK qJQ 0J0 00J0 00J0 0 J 1 10 0J1 10J1 1 J 0 01 1J0 -1 1J0 1J1 -0 1J1 -0 1J1

Dpto. Tecnología Electrónica, U. Sevilla.

1 1 1 Q

D 0 1 0 1

qJQ 0J0 0J1 1J0 1J1

T 0 1 1 0

Circuitos Secuenciales 4

CIRCUITOS SECUENCIALES BIESTABLES A NIVEL TEMPORAL D Biestable con transparencia: Cuando el biestable sigue a las entradas durante un intervalo temporal (en el cual el biestable es transparente a los cambios de entrada): H Latch: Los biestables con transparencia H Flip-Flop (FF): Los biestables sin transparencia D Asíncronos o sin reloj: Al cambio de entrada le sigue inmediatamente el del bit almacenado (latches) D Síncronos o con reloj: Poseen una señal de entrada especial, la de reloj (Clock, φ), que controla cuándo puede haber cambio en el bit almacenado H Disparados por nivel, alto (H) o bajo (L). Son latches. H Disparados por flanco, positivo/subida ( ) o negativo/bajada ("). Son flip-flops: * Master - Slave (MS) * Edge Triggered (ET)

FC

D Suelen incluir entradas asíncronas de puesta a 0 (R) y a 1 (S) las cuales dominan a las síncronas

Dpto. Tecnología Electrónica, U. Sevilla.

Fundamentos de Computadores

Circuitos Secuenciales 5

CIRCUITOS SECUENCIALES REPRESENTACIONES Latches

Flip-Flops S

Asíncrono

q

Master-Slave

R q S S

Nivel H

Edge-Triggered

q

R q

q

R q

S Flanco

Clk

q

R q Clk

Clk S Nivel L

FC

q

R q

S

q

R q

S Flanco

Clk

q

R q Clk

Clk

Dpto. Tecnología Electrónica, U. Sevilla.

Fundamentos de Computadores

Circuitos Secuenciales 6

CIRCUITOS SECUENCIALES CRONOGRAMAS PARA BIESTABLES SÍNCRONOS Latch disparado por nivel H Clock

Q=q

Captura entrada Cambia estado

Entradas (p. ej. SR) Salida q

Master-Slave disparado por flanco de subida Master captura entrada

Clock Cambia estado

Cambia estado

Q=q Puede capturar glitches

Edge-Triggered disparado por flanco de subida Clock Captura entrada y cambia estado

Q=q

Entradas

FC

Salida q

Dpto. Tecnología Electrónica

Fundamentos de ComputadoresCircuitos Secuenciales 7

CIRCUITOS SECUENCIALES CLASIFICACIÓN POR REALIZACIÓN

D Estáticos: El bit almacenado se mantiene estable hasta que hay un nuevo cambio de entrada o deja de haber alimentación. * El almacenamiento básico ocurre en dos inversores realimentados. q

≡

q

q

D

q

⎨

q=0

q=1

q=1

q=0

D Dinámicos: El bit se almacena como una carga en un condensador; como estos tienen pérdidas, si no se refresca el bit almacenado, acaba perdiéndose con el tiempo

FC

D Cuasiestáticos: El bit se introduce de forma dinámica, pero se almacena de forma estática.

Dpto. Tecnología Electrónica, U. Sevilla.

Fundamentos de Computadores

Circuitos Secuenciales 8

CIRCUITOS SECUENCIALES LATCHES ESTÁTICOS Asíncronos

S

Síncronos &

S >1

&

q

q

&

q

&

R

>1

q R CK

S

&

D

&

&

q

q

&

&

&

q

q

FC

R CK

Dpto. Tecnología Electrónica, U. Sevilla.

Fundamentos de Computadores

Circuitos Secuenciales 9

CIRCUITOS SECUENCIALES FLIP-FLOPS ESTRUCTURA GENERAL MASTER-SLAVE (flanco negativo)

D D

D

q

qint

D

CK

q

qint CK

q OTRAS ESTRUCTURAS D

FC

D

q

qint

D

CK

q

D

D

q

qint

D

CK CK

Dpto. Tecnología Electrónica, U. Sevilla.

CK

Fundamentos de Computadores

q

D

D

q

qint

D

q

φ1 φ2 φ1, φ2 no solapadas

Circuitos Secuenciales 10

CIRCUITOS SECUENCIALES LATCHES CUASIESTÁTICOS: Con llave en la realimentación

Transistor débil en realimentación

φ φ φ φ

D

FUERTE (W/L >>)

D Q

Q φ

φ

débil (W/L <<)

Operación D

φ=0 Q=q D FUERTE D

φ=1

φ=1

FC

Q=D

Dpto. Tecnología Electrónica, U. Sevilla.

Q=D

Fundamentos de Computadores

q débil

Circuitos Secuenciales 11

CIRCUITOS SECUENCIALES LATCHES DINÁMICOS: Con llave de paso CMOS

CCMOS (Inv Clocked-CMOS)

Operación CCMOS

Con llave

φ M1

M2

M1 M3

x

In φ

φ=1

φ

Out Cg

M4

Cg

CL

M2

Out

In CL

Out = In

In

φ

M3

CL

M4

M1

φ=0 Out = In

In

In

Out = In

Cg

CL M4

PROBLEMAS DE CARÁCTER ELÉCTRICO-TEMPORAL:Ajuste de reloj (φ φ = 00 o φ φ = 11) Carreras, Redistribución de carga, Anchura mínima de pulso de f, Frecuencia mínima de operación (por fugas, depende de tecnología y obliga al refresco del valor almacenado)

FC

Dpto. Tecnología Electrónica, U. Sevilla.

Fundamentos de Computadores

Circuitos Secuenciales 12

CIRCUITOS SECUENCIALES D Cronograma de un flip-flop tipo D disparado por flanco de subida (positivo) y entradas asíncronas de puesta a 0 y a 1 Ck S R

D=1

1

0

0

1

0 0

0 0

0 set

1

Q reset

R

0

D=0

1

D

D=0

Ck

D=0

Q

D=1

S

D=0

D

D Temporización/Restricciones de operación Ck

FC

D

fmax tsetup thold

Fija

Fija tprop

Q Dpto. Tecnología Electrónica, U. Sevilla.

Fundamentos de Computadores

Circuitos Secuenciales 13

CIRCUITOS SECUENCIALES D Otras características: F Disparo por flanco negativo o de bajada Ck D

S

Q

Ck

D Q

R

D1

D0

D2

D0

?

D1

F Entrada de habilitación (E, enable) de la operación síncrona

D

S

Q

E=0

D

Q+ = Q

Inhibición

E=1

D

Q+ = D

Habilitación (tipo D)

Ck

FC

E R

Dpto. Tecnología Electrónica, U. Sevilla.

Fundamentos de Computadores

Circuitos Secuenciales 14

CIRCUITOS SECUENCIALES MODELO GENERAL DE MÁQUINA SECUENCIAL: MÁQUINAS DE

MEALY Y DE MOORE

D Una Máquina Secuencial posee unos conjuntos de entrada (I) y de salida (O); además, posee un conjunto de estados internos (S, States) que recogen todas las situaciones por las que puede pasar la Máquina. D Los estados internos recogen la historia de la Máquina.

I

Máquina Secuencial

O

Estados internos S

D En cada momento hay unos valores presente (en I y en S) que marcan el estado total. De ese estado presente se deriva la salida presente (O) y el estado próximo (NS: Next State) de acuerdo con las siguientes funciones:

FC

*

Cambio de estado, que depende del estado total: NS = NS(I, S)

** Salida: · Modelo de Mealy, depende del estado total: O = O(I, S) · Modelo de Moore, depende sólo del estado interno: O = O(S) Dpto. Tecnología Electrónica, U. Sevilla.

Fundamentos de Computadores

Circuitos Secuenciales 15

CIRCUITOS SECUENCIALES REPRESENTACIONES POR GRAFOS Y POR TABLAS Moore

Mealy Ij/O(Ij, Si)

Si

I

S Si

Ij ... ... . . . NS, O ... ...

NS

Si O(Si)

I

... ... ...

S Si

Ij

Ij

NS O(NS)

O

... ... ... . . . NS . . . O(Si) ... ... ...

FC

Dpto. Tecnología Electrónica, U. Sevilla.

Fundamentos de Computadores

Circuitos Secuenciales 16

CIRCUITOS SECUENCIALES CIRCUITOS SECUENCIALES SÍNCRONOS DE MEALY Y DE MOORE ...

Banco de Biestables

entradas

D=Q

salidas tipo Mealy q estado presente

CC Q+ salidas de excitación para el próximo estado

Clk salidas tipo Moore CC

FC

Las salidas Moore no cambian con las entradas, sino sólo con el flanco activo de reloj

D Cualquier biestable sirve para almacenar el estado presente D Los biestables se conectan a una misma señal de reloj, Clk Dpto. Tecnología Electrónica, U. Sevilla.

Fundamentos de Computadores

Circuitos Secuenciales 17

CIRCUITOS SECUENCIALES UN EJEMPLO CON ESTRUCTURA MUY GENERAL: A0 A1 A2 A3

X

ROM

d0 d1 d2 d3

Z

q3q2q1 (2 J N(10

q3 D3

S

0 1 2 3 4 5 6 7

q2 D2 q1 D1

FC

$

[$]

$

[$]

0 1 2 3 4 5 6 7

A B 6 8 6 C 7 6

8 9 A B C D E F

4 7 D 1 8 4 A 9

Dpto. Tecnología Electrónica, U. Sevilla.

X 0 5, 0 3, 0 3, 0 3, 1 2, 0 6, 1 4, 0 5, 0

1 5, 1 4, 0 6, 0 3, 0 3, 1 0, 1 2, 0 4, 1

Z(X) J Mealy NS, Z

Fundamentos de Computadores

Circuitos Secuenciales 18

CIRCUITOS SECUENCIALES Procedimiento de análisis de circuitos secuenciales síncronos ∗

Objetivo: Conocido el circuito, determinar su operación Según el caso, el resultado final será: • La tabla o grafo de estado/salida • Un cronograma o secuencia entrada-salida • Una descripción en lenguaje normal de su operación con significado funcional

∗

∗

FC

Procedimientos: Hay dos formas principales ∗

Para CSS con reloj común y único, se sigue el procedimiento sistemático indicado en la página siguiente

∗

Para cualquier circuito secuencial, se analiza en el tiempo cómo se propagan los estímulos de entrada hasta la salida

Orden aconsejado para el análisis temporal y la obtención de secuencias: En relación al tipo de entrada o excitación en los biestables: 1º Excitaciones asíncronas 2º Excitaciones síncronas En relación a las salidas: 1º Determinar los estados

Dpto. Tecnología Electrónica, U. Sevilla.

2º Obtener las salidas

Fundamentos de Computadores

Circuitos Secuenciales 19

CIRCUITOS SECUENCIALES Procedimiento de análisis de CSS con reloj único 1º Obtener las ecuaciones de excitación de los biestables y de salida del CSS. Se analiza el circuito combinacional que proporciona las entradas de los biestables y las salidas del CSS

2º Obtener las tablas de excitación/salida. Se pasan a mapas de Karnaugh las ecuaciones obtenidas en el punto 1

3º Obtener las tablas de transición (de estado)/salida. En cada celda de la tabla de excitación se aplica la correspondiente transición de estado del biestable

4º Obtener las tablas de estado/salida. En su caso, obtener el grafo de estado/salida A cada código binario de estado se le asigna un símbolo; con estos símbolos se reescribe la tabla de transición

1º

2º

3º

x J = Fj(x, q)

x

q

FC

Dpto. Tecnología Electrónica, U. Sevilla.

x

q

K = Fk(x, q) z = Fz(x, q)

4º S

Q, z

JK, z

Fundamentos de Computadores

NS, z

Circuitos Secuenciales 20

CIRCUITOS SECUENCIALES Procedimiento de diseño ∗

Objetivo: Conocida la función, determinar el circuito

∗

Procedimiento: Seguir los pasos de diseño siguientes: Descripción inicial No sistemático Grafo estado/salida

Sin cambio de información

Reducción número de estados

Tabla estado/salida

Tabla de estado mínima

Asignación: Se asignan códigos binarios a los estados Tabla de transición Elección de biestable (JK o D o ...). Si es tipo D, estas tablas son iguales Tabla de excitación

FC

Diseño combinacional de funciones de excitación y salidas Ecuaciones excitación/salida

Dpto. Tecnología Electrónica, U. Sevilla.

Fundamentos de Computadores

Circuitos Secuenciales 21

CIRCUITOS SECUENCIALES De la descripción inicial al grafo/tabla de estados-salida ∗

PRIMERAS DECISIONES: Modelo de Mealy o de Moore; secuencias solapadas o no-solapadas, agrupadas o no en grupos de bits

∗

GUÍAS PARA OBTENER EL PRIMER GRAFO [o tabla]: 1. 2.

3.

4.

FC

5.

Construir una secuencia de entrada y, desde el enunciado, obtener la secuencia de salida. Previamente se habrán establecido las entradas y las salidas del CSS. Comenzar con un ‘estado’ conocido; típicamente puede ser: • Aquél en que se acaba de detectar la secuencia deseada • Aquél en que aún no se ha comenzado a detectar la secuencia • Un estado inicial (RESET) en el que ‘aún no se ha recibido nada’ A partir de ese estado, para todas las entradas del CSS, determinar: • el próximo estado: crear tantos como sea necesario • la salida que corresponde Los CSS son máquina de estados finitos. Por tanto, el grafo debe ser cerrado, esto es, hay que volver a estados ya puestos (no pueden ponerse nuevos estados indefinidamente). En caso de duda, incluir estados nuevos. Comprobar el grafo obtenido: 5.1. Que de todos los estados salen ramas correspondientes a todas las entradas 5.2. Que las secuencias del punto 1 se cumplen también en el grafo obtenido

Dpto. Tecnología Electrónica, U. Sevilla.

Fundamentos de Computadores

Circuitos Secuenciales 22

CIRCUITOS SECUENCIALES OPTIMIZACIÓN ∗

Objetivo: Reducir el coste final del circuito

∗

Mecanismos: Se pueden utilizar las siguientes técnicas de reducción de coste: • Reducir el número de estados: •• Puede reducir el número de biestables a utilizar •• Puede reducir el coste de la parte combinacional • Realizar una buena asignación (en su caso, óptima). Reduce la parte combinacional • Elegir adecuadamente el tipo lógico de los biestables. Reduce la parte combinacional

FC

• Aplicar las técnicas de diseño óptimo para funciones combinacionales

Dpto. Tecnología Electrónica, U. Sevilla.

Fundamentos de Computadores

Circuitos Secuenciales 23

CIRCUITOS SECUENCIALES REDUCCIÓN DE TABLAS COMPLETAMENTE ESPECIFICADAS DEFINICIONES (para todo tipo de tablas de estados/salidas): *

Tabla completamente especificada: Es aquélla que tiene especificados el próximo estado y la salida en todas las celdas (cada celda corresponde a un estado total del CSS) En otro caso se trata de una tabla incompletamente especificada.

*

Tablas compatibles: Son aquéllas que producen la misma secuencia de salida, siempre que esté especificada, ante la misma secuencia de entrada.

*

Estados de salida compatible (o estados compatibles): S1 y S2 son de salida compatible si, para cualquier entrada, las salidas de S1 y de S2 son las mismas o están inespecificadas.

*

Estados de salida incompatible (o estados incompatibles): S1 y S2 son de incompatibles si, para alguna entrada, las salidas de S1 y de S2 son distintas y ambas están especificadas.

FC

TABLAS COMPLETAMENTE ESPECIFICADAS: La relación de compatibilidad es una relación de equivalencia: en su caso, se llaman estados equivalentes y tablas equivalentes o indistinguibles.

Dpto. Tecnología Electrónica, U. Sevilla.

Fundamentos de Computadores

Circuitos Secuenciales 24

CIRCUITOS SECUENCIALES Fundamentos de la reducción (tablas completamente especificadas) ∗

Objetivo: A partir de la tabla inicial encontrar una equivalente con ella con el menor número de estados (tabla mínima)

( Reducción inicial: Se eliminan los estados inalcanzables ( La tabla mínima está compuesta por estados que son las clases de equivalencia del conjunto de estados de la tabla inicial respecto a la relación de compatibilidad ( TEOREMA: Dos estados S1 y S2 son equivalentes si sólo si se cumplen: 1. S1 y S2 son de salida compatible 2. La pareja de sucesores (próximos estados) de S1 y de S2 también son equivalentes ( PROCEDIMIENTO: Seguir los 3 pasos siguientes: 1. Construir la tabla de pares compatibles

FC

2. Determinar los incompatibles 3. Obtener los compatibles máximos (clases de equivalencia) y formar la tabla mínima.

Dpto. Tecnología Electrónica, U. Sevilla.

Fundamentos de Computadores

Circuitos Secuenciales 25

CIRCUITOS SECUENCIALES ( Ejemplo, Problema 34.a: Redúzcanse las máquinas cuyas tablas son las de la Figura. ¿Se trata de máquina de Mealy o de Moore?

a) x S A B C D E F G

0 D D G A E A C

1 F E E 1 F E 1 B G 1

FC

Dpto. Tecnología Electrónica, U. Sevilla.

Fundamentos de Computadores

Circuitos Secuenciales 26

CIRCUITOS SECUENCIALES ASIGNACIÓN ∗

Objetivo: Codificar los estados mediante un código binario válido

∗

Asignaciones tipo: Son las dos de longitudes de código extremas. Para M estados: ** Longitud grande: 1 bit (biestable) por estado con código 1-entre-M, total M bits ** Longitud mínima: n bits (biestables), n = ⎡Log2M⎤

∗

Asignaciones de longitud mínima: Varía el coste de la parte combinacional del circuito según la asignación ** Hay muchas asignaciones posibles ( V( 2 , M ) = 2n • ( 2n – 1 ) • ( 2n – 1 ) • … ( 2n – M + 1 ) ) P.ej. 24 para 3 estados; 40320 para 8 estados ** El coste del circuito no cambia si: a/ Se permutan dos columnas (yi ↔ yj) b/ Se complementa una columna (yi ↔ yi) n V ( 2 – 1 )! 2 ,M ----------------------------------------------Así, el número de asignaciones de coste distinto es: = n n n

n

FC

n! • 2

n! • ( 2 – M )!

Sigue habiendo muchas: 3 para M=3 o 4; 140 para M=5; 840 para M=8; casi 11 millones para M=9; 54 mil millones para M=16; ... Dpto. Tecnología Electrónica, U. Sevilla.

Fundamentos de Computadores

Circuitos Secuenciales 27

CIRCUITOS SECUENCIALES ∗ Técnicas de asignaciones para bajo coste: 1. Estudio exhaustivo: Consiste en diseñar el CSS para todas las asignaciones y quedarse con la del menor coste A mano, es útil sólo para 3 y 4 estados Con ayuda de ordenador es útil hasta 8 estados 2. Método de adyacencias: Es una técnica útil para hacer a mano buenas asignaciones (hasta unos 10 estados aproximadamente)

FC

I S

II

III

q1q0 q1q0 q1q0

A

00

00

00

B

01

01

11

C

10

11

01

D

11

10

10

3. Método aleatorio/cuasiexhaustivo: Consiste en elegir aleatoriamente un cierto número de asignaciones y estudiar exhaustivamente esos casos 4. Otros métodos: * Método SHR (Story, Harrison & Reinhold): Óptimo, trabajoso, computable * Método de la particiones: Dan estructura al CSS

Dpto. Tecnología Electrónica, U. Sevilla.

Fundamentos de Computadores

Circuitos Secuenciales 28