V-1

Estructuras Discretas

( MCh/FCB)

Captulo V
Sistemas Secuenciales 5.1. Introduccin
En los sistemas secuenciales la salida depende de la entrada actual y adems de las salidas anteriores. Los sistemas secuenciales poseen memoria Se dividen en: Sistemas o Circuitos Secuenciales Sincrnicos (SSS) Sistemas o Circuitos Secuenciales Asincrnicos (SSA) En los SSS las variables cambian de estado de acuerdo a un "RELOJ" (Ck) Generalmente la seal de reloj tiene variaciones constantes (periodo fijo) y constituye la unidad de tiempo del circuito Ej.: sea la seal x(t)

x(t) t0 t1 t2 t3 t4 t5 t6

Analizando los tiempos se tiene: t0, t1, t2, t3, t4, t5, t6 x(t0,t1)=0, x(t1,t2)=1, x(t2,t3)=0, x(t3,t4)=1, x(t4,t5)=0, x(t5,t6)=1, x(t6,t7)=0, ....

V-2

Estructuras Discretas

( MCh/FCB)

Si la seal x(t) es acompaada de reloj(Ck) de sincronismo

x(t) CK
0 1 2 3 4 5 6 7 8 9 10 11

Existe una unidad de tiempo propia del circuito, as slo falta definir el tiempo de inicio La seal x(n) a partir de t0 es: x=(0,0,1,0,0,1,0,1,1,0,0, ...) Los valores en un instante se pueden representar en funcin de los perodos de reloj. x(2)=0, x(4)=0, x(6)=1 Los sistemas secuenciales se representan con los siguientes esquemas Sistemas Secuenciales Sincrnicos:

E y Ck

Lgica Combinacional

Z(E,y) Y(E,y)

Memoria

V-3

Estructuras Discretas

( MCh/FCB)

Sistemas Secuenciales Asincrnicos:

E y Lgica Combinacional Z(E,y) Y(E,y)

Donde: son retardos - no tiene reloj - no tiene memoria

5.2. Elementos de memoria

Para describir cada uno de estos elementos se requieren dos tablas: i) Tabla de Estados: describe las salidas para el tiempo (n+1) de acuerdo a las entradas en el tiempo (n) ii) Tabla de Transiciones: describe los cambios de (n) a (n+1) para una entrada dada. Con estas dos tablas queda completamente especificado el comportamiento del elemento de memoria. El elemento de memoria bsico que guarda un bit de informacin se denomina: Flip Flop.

V-4

Estructuras Discretas

( MCh/FCB)

F. F. Tipo D (Data) Posee una entrada (D) y dos salidas Q y Q

Q D Ck
Si Si

- Ck: entrada de sincronismo

Q
Ck = 0 no est habilitado, Q se mantiene Ck = 1 est habilitado se transfiere D Q

Tabla de Estados D (n) 0 1 Tabla de Transicin de Q (n)Q (n+1) 0 0 0 1 1 0 1 1 D (n) 0 1 0 1 Q (n+1) 0 1

Ecuacin caracterstica:

Q(n+1) = D(n)

V-5

Estructuras Discretas

( MCh/FCB)

F. F. Tipo T (Toggle) Elemento de una entrada T y dos salidas Q y Q

Q T Ck
Si T = 0 y acta el reloj, Q permanece en el estado actual Si T = 1 y acta el reloj, Q cambia a Q

Tabla de Estados T (n) 0 1 Q (n+1) Q (n) Q (n)

Tabla de Transiciones de Q (n) Q (n+1) 0 0 0 1 1 0 1 1 Ecuacin caracterstica: T (n) 0 1 1 0

Q(n+1) = T Q (n) + T Q(n)

V-6

Estructuras Discretas

( MCh/FCB)

F. F. Tipo SR (Set-Reset)

Elemento de dos entradas S y R y salidas Q y Q

S R Ck

Q Q

Donde la entrada S =R = 1 no est permitida (si esto ocurre, su salida es incongruente Q = Q ) Tabla de Estados S (n) 0 0 1 1 R (n) 0 1 0 1 Q (n+1) Q (n) 0 1 ?

?Q = Q = 1 Tabla de Transicin de Q (n) Q (n+1) 0 0 0 1 1 0 1 1 Ecuacin caracterstica: S (n) 0 1 0 X R (n) X 0 1 0

Q(n+1) = S + R Q(n) con S R=0

V-7

Estructuras Discretas

( MCh/FCB)

F. F. Tipo JK (Set-Reset mejorado) Elemento de dos entradas JK y salidas Q y Q

J K Ck

Q Q

Este es un FF. SR en que la entrada J=K=1 provoca la complementacin de su estado actual.

Tabla de Estados J (n) 0 0 1 1 K (n) 0 1 0 1 Q (n+1) Q (n) 0 1 Q (n)

Tabla de Transiciones de Q (n) Q (n+1) 0 0 0 1 1 0 1 1 Ecuacin caracterstica: J (n) 0 1 X X K (n) X X 1 0

Q(n+1) = J Q (n) + K Q(n)

V-8

Estructuras Discretas

( MCh/FCB)

Conversin de Flip-Flops 1. 2. 3. 4. Hacer tabla de verdad con entradas del FF deseado y Qn. Agregar columna con Qn+1 segn FF deseado. De la tabla de excitacin del FF utilizado, obtener las entradas. Minimizar funciones para esas entradas.

Ejemplo - Hacer FF. JK con SR J 0 0 0 0 1 1 1 1 K 0 0 1 1 0 0 1 1 Qn 0 1 0 1 0 1 0 1 Qn+1 0 1 0 0 1 1 1 0 SR 0X X0 0X 01 10 X0 10 01 Qn\JK 0 1 00 0 X 01 0 0 S=J Q 01 X 1 R=KQ 11 1 0 10 1 X

Qn\JK 0 1

00 X 0

11 0 1

10 0 0

Entonces el FF JK se puede generar a partir del FF-SR de la siguiente manera

V-9

Estructuras Discretas

( MCh/FCB)

Ejercicios para practicar: - Hacer FF Tipo D con JK Solucin:

J K

Q Q

Q Q

Se invierte la entrada K de modo tal que para D = 0, JK = 01 y, para D = 1, JK = 10

- Hacer FF Tipo T con JK Solucin:

J K

Q Q

Q Q

Por la simplicidad de esta conversin, ya que slo basta con unir las dos entradas, el FF tipo T no se fabrica. - Para determinar la ecuacin caracterstica de un FF: Hacer mapa para Q(n+1) con Q(n) y las entradas

V-10

Estructuras Discretas

( MCh/FCB)

5.3. Diseo de S.S.S.

Requerimientos: dada una secuencia de entrada, se desea generar una secuencia de salida que cumpla ciertas condiciones. Los pasos para el diseo son los siguientes: i) Generar Diagrama de Estados Se representa grficamente el comportamiento del sistema, segn las condiciones del problema, generando estados con las transiciones causadas por las entradas e indicando la salida que producir. ii) Generar la Tabla de Estados y Salidas Representar el diagrama de estados en forma tabular. iii) Generar la tabla de transiciones y salidas Se representan los estados por valores binarios, obtienindose la tabla de transiciones y salidas, desde la que se puede obtener las ecuaciones de estado del sistema. iv) Generar la tabla de Excitaciones y Salidas

Se eligen los elementos de memoria (FF) y basndose en su tabla de excitacin, se genera la tabla de Excitaciones y Salidas. v) Minimizacin de las funciones de excitacin y salidas Las funciones de excitacin y salidas se minimizan mediante alguna tcnica ([Link]. mapas de Karnaugh) para obtener la lgica combinacional mnima del circuito. vi) Implementacin Implementar estas funciones con sus respectivos elementos de memoria para obtener el circuito deseado.

V-11

Estructuras Discretas

( MCh/FCB)

Ej. 1: Disee un circuito que entregue un 1 cuando detecte la secuencia 0101 en su entrada. Considere traslape entre secuencias (se aceptan secuencias entrelazadas)

0101

00001010000
i)

MQUINA

1 001010100111 1

Diagrama de Estados

1/0

0/0

0/0

0/0

B
1/0

1/0

0/0 1/1

Definicin de estados A: B: C: D: No ha llegado ningn bit vlido de la secuencia Ha llegado el primer bit vlido Ha llegado el segundo bit vlido Ha llegado el tercer bit vlido

Note las diferencias al considerar el caso sin traslape:

1/0 0/0 0/0

0/0

B
1/0 1/0 1/1

0/0

V-12

Estructuras Discretas

( MCh/FCB)

ii) Tabla de Estados y Salidas EP A B C D x=0 B, 0 B, 0 D, 0 B, 0 ES, Z x=1 A, 0 C, 0 A, 0 C, 1

iii) Tabla de transiciones y salidas Se tiene 4 estados, entonces se necesitan 2 bits para representarlos ( se requiere dos elementos de memoria) A = 00, B = 01, C = 11, D = 10 Tabla de Transiciones y Salidas y1 y2 Y1,Y2,Z x=0 A 00 01, 0 B 01 01, 0 C 11 10, 0 D 10 01, 0 iv) Tabla de Excitaciones y Salidas Usando FF Tipo T T 0 1 Q (n+1) Q(n) Q(n)Q(n+1) 0 0 0 1 1 0 1 1 T 0 1 1 0 x=1 00, 0 11, 0 00, 0 11, 1

Q(t )

V-13

Estructuras Discretas

( MCh/FCB)

Tabla de Excitaciones y Salidas y1 y2 T1 T2 , Z x=0 x=1 A 00 01, 0 00, 0 B 01 00, 0 10, 0 C 11 01, 0 11, 0 D 10 11, 0 01, 1 v) x y1y2 0 1 00 01 1 11 1 10 1 Minimizacin de las funciones de excitacin y salidas x y1y2 00 01 11 10 0 1 1 1 1 1 1 x y1y2 0 00 01 11 10 1

Z = y1 y2 x ,
vi) Implementacin

T1 = y2 x + y1 y2 x ,

T2 = y1 + x y 2

CK

y1 y 1 y2 y2

T 1 T 2

V-14

Estructuras Discretas

( MCh/FCB)

Ej.2: Disee un circuito de dos entradas y una salida que entregue la suma de dos secuencias de nmeros que son puestos en su entrada (sumador serial)

x 1 / 1010 x 2 / 1101 Ck
Cmo se define la suma?

S / 10111

0 0 1 0 acarreo 1010 +0011 =1101 La suma se define de igual forma que el caso combinacional OREX La salida depende adems del estado anterior, es decir del acarreo El estado que importa, es el del acarreo A Acarreo en 0 B Acarreo en 1 i) Diagrama de Estados notacin x1x2 / Z
00/0 01/1 10/1 11/0 00/1 11/1 10/0 01/0

V-15

Estructuras Discretas

( MCh/FCB)

ii) Tabla de Estados y Salidas Sea ES = estado siguiente, EP = estado presente Ordenamos los estados de acuerdo a un mapa de Karnaugh Tabla de Estados y Salidas ES, Z (n+1) x1 x2 x1 x2 x1 x2 0 0 0 1 1 1 A,0 A,1 B,0 A,1 B,0 B,1

EP (n) A B

x1 x2 1 0 A,1 B,0

iii) Tabla de Transiciones y Salidas Slo dos estados, se pueden representar por un bit Sea: A = 0 , B = 1 (Tabla de Transiciones y Salidas) Y, Z y (n) x1 x2 x1 x2 x1 x2 x1 x2 0 0 0 1 1 1 1 0 (A) 0 0,0 0,1 1,0 0,1 (B) 1 0,1 1,0 1,1 1,0 iv) Tabla de Excitaciones y Salidas Elijamos un FF tipo D 0 1 Q (n+1) 0 1

Pregunta: Qu se debe aplicar en la entrada para tener y(n+1) dado y (n)?

V-16

Estructuras Discretas

( MCh/FCB)

Q (n)Q (n+1) 0 0 0 1 1 0 1 1

D(n) 0 1 0 1

Tabla de Excitaciones y Salidas y (n) D, Z x1 x2 x1 x2 x1 x2 0 0 0 1 1 1 (A) 0 0,0 0,1 1,0 (B) 1 0,1 1,0 1,1

x1 1 0,1 1,0

x2 0

v) Minimizacin de las funciones de excitacin y salidas Al estar ordenado como mapa facilita el traspaso: D y x1x2 0 1 00 01 1 11 1 1 10 1

D = yx2+yx1+x1x2 Z y x1x2 0 1 00 1 01 1 11 1 10 1

Z =x x y+ x x y+ x x y+ x x y 1 2 1 2 1 2 1 2

V-17

Estructuras Discretas

( MCh/FCB)

Z =(x x + x x ) y +(x x + x x ) y 1 2 1 2 1 2 1 2
Z =(x x + x x )y + (x x + x x ) y 1 2 1 2 1 2 1 2

Z = (x x )y + (x x ) y 1 2 1 2
Z =x x y 1 2
vi) Implementacin

x1 x2 D Q
y

x1 x2 cn+1

F. A.
Q D

s cn

Ck

V-18

Estructuras Discretas

( MCh/FCB)

Ejemplo 3: Disee un circuito que genere la secuencia 0,4,2,1,6 (en binario) y repita

0,1,0,0,1, ... 0,0,1,0,1, ... 0,0,0,1,0, ...

Sol: Cuando x=1 cambie al siguiente nmero de la secuencia i) Diagrama de Estados

0/000 0/110

A
1/000

1/100

0/100

E
1/110

B
1/010

D
0/001

1/001

C
0/010

Definicin de estados A: Genera el dgito 0 B: Genera el dgito 4 C: Genera el dgito 2 ii) Tabla de Estados y Salidas ES, Z EP A B C D E x=0 A, 000 B, 100 C, 010 D, 001 E, 110 x =1 B, 100 C, 010 D, 001 E, 100 A, 000 D: Genera el dgito 1 E: Genera el dgito 6

V-19

Estructuras Discretas

( MCh/FCB)

iii) Tabla de Transiciones y Salidas Hay 5 estados, entonces se necesitan 3 bits para representarlos A = 000, B = 100, C = 010, D = 001, E=110 Note que con esta asignacin, los estados resultan iguales a las salidas, entonces las salidas pueden ser obtenidas directamente de los FFs. Tabla de Transiciones y Salidas Y1,Y2,Y3 y1y2y3 x=0 x=1 000 000 100 001 001 110 010 010 001 011 XXX XXX 100 100 010 101 XXX XXX 110 110 000 111 XXX XXX

A D C B E

iv) Tabla de Excitaciones y Salidas FF Tipo JK Q(n)Q(n+1) 0 0 0 1 1 0 1 1

J 0 1 X X

K X X 1 0

V-20

Estructuras Discretas

( MCh/FCB)

y1y2y3 000 001 010 011 100 101 110 111

Tabla de Excitaciones y Salidas J1 K1 J2 K 2 x=0 x=1 x=0 x=1 0 X 1 X 0 X 0 X 0 X 1 X 1 X 0 X 0 X 0 X X 1 X 0 X X X X X X X X X 1 1 X X 0 0 X X X X X X X X X X 1 X 1 X 0 X 0 X X X X X X X X

J3 K 3 x=0 x=1 0 X 0 X X 1 X 0 1 X 0 X X X X X 0 X 0 X X X X X 0 X 0 X X X X X

- Los estados no utilizados se completan con don't cares v) Minimizacin de las funciones de excitacin y salidas J1 K1 y1y2 y3x 00 01 11 10 00 0 1 1 0 01 0 0 X X 11 X X X X 10 X X X X
J1 = y2 x

y1y2

J2 y1y2 y 3x 00 01 11 10 00 01 11 10 0 0 1 0 X X X X X X X X 0 1 X X J = y x+ y x 2 1 3

00 01 11 10 00 X X X X 01 X X X X 11 0 1 X X 10 0 1 X X K =x 1 K2 y 3x y1y2 00 10 11 10 00 X X X X 01 0 1 X X 11 0 1 X X 10 X X X X
K =x 2

y3x

V-21

Estructuras Discretas

( MCh/FCB)

J3 y3x y1y2 00 01 11 10 y3x y1y2 00 01 11 10

K3

00 01 11 10 00 01 11 10 X X 1 0 0 0 X X X X X X 0 1 X X X X X X 0 0 X X X X X X 0 0 X X J =yy x K =x 3 12 3 Note que todas las funciones de excitacin son dependientes de x; como se desea que el sistema cambie de estado cuando x = 1, se puede usar la entrada x como reloj de todos los FF. Eso es equivalente a generar la tabla de estados slo con la columna correspondiente a x = 1, lo que da origen a los siguientes mapas: J1 K1 J2 y3 y3 y3 y1y2 0 1 y1y2 0 1 y1y2 0 1 00 1 1 00 X X 00 0 1 01 0 X 01 X X 01 X X 11 X X 11 1 X 11 X X 10 X X 10 1 X 10 1 X J1 = y2 , J 2 = y1 + y3 K1 = 1 , K2 J3 K3 y3 y3 y3 y1y2 0 1 y1y2 0 1 y1y2 0 1 00 X X 00 0 X 00 X 1 01 1 X 01 1 X 01 X X 11 1 X 11 0 X 11 X X 10 X X 10 0 X 10 X X

K2 = 1 ,

J 3 = y1 y2 ,

K3 = 1

Compare estas funciones con las determinadas anteriormente.

V-22

Estructuras Discretas

( MCh/FCB)

vi) Implementacin

J1 = y2 J 2 = y1 + y3 J3 = y1 y2
y1

K1 = 1 K2 = 1 K3 = 1
y2 y3

1
Ck

J1 K1

y1 y 1

J2 K2

y2 y2

J3 K3

y3 y3

Tipos de Autmata Autmata de Mealy Las salidas dependen de la entrada y de las salidas de los elementos de memoria, es decir:

v v Z = f ( y ,x )

Autmata de Moore Las salidas dependen slo de las salidas de los elementos de memoria, es decir:

v Z = f (y)

V-23

Estructuras Discretas

( MCh/FCB)

Reduccin de Estados Mtodo de las Particiones Paso 1: Paso 2: Paso 3: Primera particin: todos los estados P0=(todos) Segunda particin: P1=( )( )( ) Separar en grupos los estados que tienen iguales salidas Tercera particin: P2=( )( )( ) Para cada grupo de la particin anterior: Se copia el primer estado del grupo. Aquellos estados cuyos ES no pertenezcan a los mismos grupos que los del primer estado, se separan para formar nuevos grupos donde todos los estados provengan del mismo grupo y tengan sus ES en los mismos grupos, respectivamente. Se repite el paso P3 iterativamente hasta que P i+1 = Pi

Paso 4:

Cada grupo as determinado est compuesto por estados equivalentes y puede ser reemplazado por un solo estado. Ej. 4. Reducir la tabla de estados EP S0 S1 S2 S3 S4 S5 S6 ES, Z x =0 x =1 S0,0 S4,1 S4,1 S2,0 S0,1 S3,1 S5,0 S6,1 S1,1 S2,0 S5,0 S4,1 S0,1 S3,1 grupos segn salidas a b c a b a c

V-24

Estructuras Discretas

( MCh/FCB)

Paso 1: P0 = (S0S1S2S3S4S5S6) Paso 2: P1 = ( S0 S3 S 5 )( S1S4 )( S 2 S6 ) 123 { {

a b c

Paso 3: grupo a (S0S3S5) con EP=S0 x=0 ES S0 a x=1 ES S4 b grupo b (S1S4) con x=0 x=1 grupo c (S2S6) con x=0 x=1 Se tiene entonces

EP=S3 ES S5 a ES S6 c

EP=S5 ES S5 a ES S4 b
Otro grupo

EP=S1 ES S4 b ES S2 c EP=S2 ES S0 a ES S3 a

EP=S4 ES S1 b ES S2 c EP=S6 ES S0 a ES S3 a

P2 = ( S0 S 5 )( S 3 )( S1S 4 )( S 2 S6 ) { { { {
a b c d

Paso 4: renombrando los grupos EP ES, Z x =0 x =1 S0 S0,0 S4,1 S1 S4,1 S2,0 S2 S0,1 S3,1 S3 S5,0 S6,1 S4 S1,1 S2,0 S5 S5,0 S4,1 S6 S0,1 S3,1

grupos de P2 a c d b c a d

V-25

Estructuras Discretas

( MCh/FCB)

grupo a (S0S5) con EP=S0 EP=S5 x=0 ES S0 a ES S5 a x=1 ES S4 c ES S4 c grupo b (S3) nico estado en el grupo, se copia. grupo c (S1S4) con EP=S1 x=0 ES S4 c x=1 ES S2 d grupo d (S2S6) con x=0 x=1 EP=S4 ES S1 c ES S2 d

EP=S2 EP=S6 ES S0 a ES S0 a ES S3 b ES S3 b P3 = ( S0 S5 )( S3 )( S1S4 )( S 2 S6 ) { { { {

a b c d

Esta particin es igual a la anterior, se detiene el proceso. P3 = P4 = ( S0 S5 )( S3 )( S1S4 )( S 2 S6 ) { { { {

a b c d

Tabla de estados reducida: EP a b c d

ES, Z x =0 x =1 a,0 c,1 a,0 d,1 c,1 d,0 a,1 b,1

V-26

Estructuras Discretas

( MCh/FCB)

El autmata mnimo es:

0/0 0/1 1/1 1/1

S05

S14

1/1 0/1 0/0

S3

1/0

S26

Sistemas Secuenciales de Mercado

Para el diseo prctico, se recurre a circuitos previamente diseados e integrados por fabricantes o se usan circuitos tpicos construidos en base a FF

Divisores de Frecuencia

Generan una salida cuya frecuencia es un submltiplo de la frecuencia del reloj de entrada.

Divisor por dos

Suponiendo en n = 1, Q (n)= 0
1 2 3 4 5

Con flanco de bajada activo

Ck Q

La frecuencia de la seal en Q es la mitad de la del Ck.

V-27

Estructuras Discretas

( MCh/FCB)

Con FF tipo T
Vcc="1"

T Ck
T 0 1

Q Q

01010

Q (n+1) Q (n) Q (n)

Divisor por 2n En general, se tiene:

+ T Q z

T Ck Ck

T Ck

Ck Q

El primer FF divide la frecuencia por 2 y como la salida se conecta al reloj del siguiente, en cada FF se divide nuevamente por 2. La frecuencia de la seal de salida del n-simo FF ser: [Link]/2n

V-28

Estructuras Discretas

( MCh/FCB)

Contadores

Entregan la cuenta (en binario) del nmero de pulsos que han ocurrido en la entrada. Definicin de Trminos
Ck es la entrada bsica de los contadores (cuenta pulsos del reloj) Reset: Entrada adicional que al ponerse en "1" vuelve la cuenta a

cero independiente del Ck

N: se define como el mdulo de un contador; es el nmero

mximo de pulsos que puede contar La mayora de los contadores son cclicos, es decir, despus de llegar a la cuenta mxima (N-1) vuelve a cero
Siempre se puede obtener cuentas en mdulos menores al mdulo

para el que fue diseado. En cada instante la cuenta est representada por: Qn-1, Qn-2, ..., Q2, Q1, Q0 En general existen dos tipos de contadores: - RIPPLE y ANILLO

Contador Ripple o asincrnico

Diseados en base a divisores de frecuencia El algoritmo usado tiene su fundamento en la transformacin a base 2 por divisin sucesiva.

V-29

Estructuras Discretas

( MCh/FCB)

Esto es fcil de realizar electrnicamente; con n FFs divisores por 2 en serie, se configura un divisor por 2n
+

T Ck

Q0 FF 0

Q1 FF 1

Q2 FF 2

T Qn FF n Ck a
2

Ck a
0

Ck a
1

n -1

La cuenta en binario es:

an-1an-2.....a2a1a0

Ej.: Contador mdulo 16 formado por 4 FFs tipo T

+

T Ck

Q1

T Ck a0

Q2

T Ck a1

Q3

T Q4 Ck a2 a3

Diagrama de tiempo
Ck

a0 a1 a2 a3
1 0 0 0 0 1 0 0 1 1 0 0 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 0

La secuencia de salida es la codificacin binaria natural de la ocurrencia de los pulsos del reloj Ck

V-30

Estructuras Discretas

( MCh/FCB)

Contadores en Anillo

Diseo basado en SSS, al recibir un nuevo pulso pasa a un estado que representa la cuenta De acuerdo a la teora de SSS se puede generar cualquier secuencia de acuerdo a una secuencia de entrada Se debe producir una secuencia de salida determinada sin poseer una entrada, slo el reloj es aplicado a los FF's Ej. Contador progresivo mdulo 5 cuenta 0 1 2 3 4 0 ... Diagrama de Estados

S0 S4 S3 S1 S2

S0 : estado inicial (cuenta = 0) S1 : al primer pulso de reloj entrega cuenta = 1 S2 : al segundo pulso de reloj entrega cuenta = 2 S3 : al tercer pulso de reloj entrega cuenta = 3 S4 : al cuarto pulso de reloj entrega cuenta = 4 al quinto pulso de reloj entrega cuenta = 0 y vuelve a S0 Tabla Estados EP S0 S1 S2 S3 S4 ES S1 S2 S3 S4 S0

V-31

Estructuras Discretas

( MCh/FCB)

Asignacin de Estados S0: 000 S1: 001 S2: 010 S3: 011 S4: 100

Tabla de transiciones y salidas y0y1y2 000 001 010 011 100 101 110 111

Y 0Y 1Y 2 001 010 011 100 000 XXX XXX XXX

Elementos de memoria FF tipo D y0y1y2 D0D1D2 000 001 001 010 010 011 011 100 100 000 101 XXX 110 XXX 111 XXX D0 y0 0 1 y1y2 00 01 X 11 1 X 10 X

V-32

Estructuras Discretas

( MCh/FCB)

D1 y0 y1y2 0 1 D2 y0 y1y2 0 1 00 1 01 X 11 X 10 1 X D0 = y1 y2 D1 = y2 y1 D2 = y0 y2 00 01 1 X 11 X 10 1 X

D0 Ck

Q Q D1

Q Q

D2

Q Q

Registros

Mdulos integrados, combinacionales

formados

por

FFs

circuitos

Funcin: almacenar un grupo de n bits y luego entregarlos en la forma requerida (serie o paralelo)

V-33

Estructuras Discretas

( MCh/FCB)

Registro Paralelo/Paralelo (Latch) Posee n entradas y n salidas con un flanco de reloj las n entradas pasan a las n salidas

(Reset) Ck

x 0 x1 Q 0 Q1 P/P

xn-1 Qn-1

Este tipo de registros est construido con FFs tipo D

x0 D0 Q0

x1 D1 Q1

x n-1 Dn-1 Qn-1

Ck

Registros: Serie/Paralelo Una entrada serie para el dato y n salidas en paralelo por los cuales entrega en todo momento los ltimos n bits que han ingresado

Datos

D/in Serie/Paralelo
Q
0

Q1

Qn-2 Qn-3

Ck Reset

V-34

Estructuras Discretas

( MCh/FCB)

Una implementacin con FF tipo D es:

Datos
D Ck Ck Q
0

D Ck

D Ck Q

Q Ck Q

n-1

Registro Paralelo/Serie Entran n bits en paralelo y los entrega en serie Posee una entrada adicional (P/S) cuando P/S="1" el dispositivo carga la data de entrada al canto de reloj cuando P/S="0" el dispositivo corre en serie la data almacenada en cada canto de reloj, entregndola por la salida nica S

(P/S) Ck

e0 e1

en-2en-1 Q Paralelo/Serie

Una implementacin con FF tipo D es:

e0 1

e3

D Ck P/S Ck

Q Ck

Q Ck

Q Ck

V-35

Estructuras Discretas

( MCh/FCB)

Este arreglo es un multiplexor de 2 canales

ei P/S Q
i

Ej.: Disear un circuito que reconozca la secuencia 10001101 Sol: basta usar un registro S/P de 8 bits y una compuerta AND

Datos

S/P D/in Q 7 Q 6 Q 5 Q 4 Q3 Q 2 Q 1 Q 0

Ck

Ej. 2: Disear un circuito que genere la secuencia 10001101 y repita Sol: slo basta usar un registro P/S

P/S

Ck

c0 c1
+

c2

P/S c3 c4 c5 c6 c7
+ + +

V-36

Estructuras Discretas

( MCh/FCB)

Registro de desplazamiento SN7495

Este registro de cuatro bits permite realizar: Carga serie Carga paralela Desplazamiento a la izquierda Desplazamiento a la derecha

Posee una entrada serial (DS) y cuatro entradas paralelas (P0-P3). Para seleccionar el modo de operacin, se usa el modo de control (MC). Cuando MC = 1, habilita el reloj CP2 y la carga paralela de P0-P3 a Q0-Q3. Cuando MC = 0, habilita el reloj CP1 y la carga serial de DS a Q0 y desplaza los bits de Q0 a Q1, de Q1 a Q2 y Q2 aQ3. El desplazamiento a la izquierda requiere conexiones externas.

V-37

Estructuras Discretas

( MCh/FCB)

Anlisis de Circuitos Secuenciales Sincrnicos

i)
Del circuito obtener las ecuaciones de excitacin para cada FF y las expresiones de las salidas. Construir los mapas de excitacin para cada FF y salidas. Construir mapas de estado siguiente usando las tablas de estados de los FFs

ii) iii)

iv) Generar la tabla de estados como sigue: - las entradas de la tabla de estados son los EP - el contenido de la celda del mapa de estado es el ES v)
Reduccin de estados equivalentes

vi) Dibujar el diagrama de estados reducido (autmata mnimo) vii)

Determinar el estado inicial y la funcin del autmata

Si se analiza a partir de las ecuaciones de estado, realizar desde iii en adelante.

Ej.: Analizar el circuito (el reloj es comn a ambos FF)

x J K Q Q J y
2

Q Q

z y
1

i) Ecuaciones de excitacin y salidas

J1 = y2 x

J2 = x

V-38

Estructuras Discretas

( MCh/FCB)

K1=1

K2 = x

z = y1 x

V-39

Estructuras Discretas

( MCh/FCB)

ii)

mapas de excitacin para cada FF FF1 (JK) FF2 x x y1 y2 0 1 y1 y2 0 00 01 11 10 01 11 11 01 01 01 01 01 00 01 11 10 01 01 01 01

(JK) 1 10 10 10 10 x y1 y2 00 01 11 10 0 0 0 0 0

Z 1 0 0 1 1

iii)

x y1 y2 00 01 11 10

mapas de estado siguiente Y1 0 0 1 0 0 1 0 0 0 0

x y1 y2 00 01 11 10

Y2 0 0 0 0 0 1 1 1 1 1

v)

tabla de estados EP y1 y2 A 0 0 B 0 1 C 1 0 D 1 1

ES , Z x=0 00, 0 10, 0 00, 0 00, 0 x=1 01, 0 01, 0 01, 1 01, 1

estados equivalentes

vi)

diagrama reducido de estados

0/0 1/0 1/0

A=00
0/0

B=01
0/0 1/1

1/0

C=10
vii) Funcin: El circuito con estado inicial 00 es un detector de secuencias 101 con traslape.

V-40

Estructuras Discretas

( MCh/FCB)

Anlisis mediante la ecuacin caracterstica de los FFs

i) Del circuito obtener las ecuaciones de excitacin para cada FF y las expresiones de las salidas. Generar la expresin del estado siguiente para cada FF mediante su ecuacin caracterstica.

ii)

iii) Para cada FF, construir el mapa de estado siguiente usando las expresiones de Qn+1 del paso anterior. iv) Generar la tabla de estados como sigue: - las entradas de la tabla de estados son los EP - el contenido de la celda es el ES v) Reduccin de estados equivalentes

viii) Dibujar el diagrama de estados reducido (autmata mnimo) vii) Determinar el estado inicial y la funcin del autmata Ej.: Analizar el circuito del ejemplo anterior i) Ecuaciones de excitacin y salidas

J1 = y2 x
K1=1

J2 = x K2 = x

z = y1 x

Ecuaciones de estado siguiente La ecuacin caracterstica del FF JK es

Q(n+1) = J Q (n) + K Q(n)

y1 y2 x y, para el FF2: Q2 (n+1) =Y2= y 2 x + y 2 x = x

Entonces, para el FF1: Q1 (n+1) =Y1=

V-41

Estructuras Discretas

( MCh/FCB)

iii)

mapas de estado siguiente y salidas Las expresiones obtenidas para Y1, Y2 y Z se representan en mapas de Karnaugh. Y1 Y2 1 0 0 0 0 x y1 y2 00 01 11 10 0 0 0 0 0 1 1 1 1 1 x y1 y2 00 01 11 10 0 0 0 0 0 Z

x y1 y2 00 01 11 10

0 0 1 0 0

1 0 0 1 1

Como se puede observar, los mapas de estado siguiente y salidas coinciden con los obtenidos con el mtodo anterior, por lo que sus resultados sern idnticos en los restantes puntos, llegando a la misma conclusin.