Equivalencia y Asignación de Estados.lsb/elo211/clases/c12.pdfde cada uno de los estados. Por...

1

Profesor Leopoldo Silva Bijit 19-01-2010

Capítulo 12

Equivalencia y Asignación de Estados.

12.1. Estados equivalentes.

Dos máquinas secuenciales son equivalentes si la relación entre la entrada y la salida son

idénticas para todas las posibles secuencias de entrada.

Un diseño en particular puede ser representado por varios diagramas de estado equivalentes. Los

costos de implementación pueden ser diferentes; en general los diagramas que tengan más estados

requieren más elementos de memoria y por lo tanto también necesitan mas redes combinacionales

para determinar el próximo estado.

Dos estados son equivalentes si no puede distinguirse entre ellos. Esto implica que si se aplica

cualquier secuencia de entrada, a partir de esos estados, se observan iguales secuencias de salida.

Puede determinarse, por inspección, que dos estados son equivalentes si tienen iguales renglones

en la matriz de transiciones. Es decir, para iguales entradas van a iguales estados próximos o

futuros, con salidas iguales.

Uno de estos estados puede removerse sin alterar la conducta de la máquina. Esto se logra

modificando la tabla de modo que no se invoque el estado eliminado sino a su equivalente.

La reducción de estados puede disminuir el número de flip-flops necesarios y a la vez puede

introducir más estado superfluos, lo cual simplifica el diseño combinacional para determinar el

próximo estado. Una lógica más simple implica, en general, menor complejidad de conexiones y

menores tiempos de propagación.

Veremos algunos algoritmos para determinar estados equivalentes cuando la matriz de

transiciones está completamente especificada.

12.2 Método de Reducción de Estados por Inspección.

Ejemplo: Se tiene la siguiente matriz de transiciones:

Estado/Entrada 0 1

A B/0 C/1

B C/0 A/1

C D/1 B/0

D C/0 A/1

Figura 12.1. Matriz de transiciones

2 Sistemas Digitales


Se observa que los renglones asociados a B y D son iguales. Iguales estados próximos e iguales

salidas. Por lo tanto B y D son equivalentes. Si se considera a D redundante se tendrá:

Estado/Entrada 0 1

A B/0 C/1

B C/0 A/1

C B/1 B/0

Figura 12.2. Matriz de transiciones reducida.

Donde se elimina el renglón asociado al estado D y se reemplaza la ocurrencia de D por B.

El método sólo puede aplicarse a casos sencillos.

12.3. Reducción de estados en máquinas completamente especificadas.

12.3.1. Método de Reducción de Moore. Método de las Particiones.

Se aplican secuencias de entrada de diverso largo.

Se irá aplicando el método al ejemplo propuesto en el método anterior.

Se define una partición o conjunto de estados equivalentes P0, formada por todos los estados del

diagrama. Esto refleja la ignorancia del próximo estado cuando aún no se ha aplicado una entrada.

Se tiene entonces:

P0 = {A, B, C, D}

Se agrupan los estados con igual salida para iguales entradas:

Se tiene que A, B y D para entrada 0 y 1, tienen salida 0 y 1 respectivamente.

Se tiene que C para entrada 0 y 1, tiene salida 1 y 0 respectivamente. La formación de P1 tiene

que ver con las salidas.

Entonces se forma la partición P1, según:

P1 = {A, B, D}, { C }

Las partes de P1 tienen igual salida para una secuencia de largo 1. Es decir, si se aplica cualquier

secuencia de largo 1 (hay dos) los estados de las partes no pueden distinguirse. Se dice que son 1-

equivalentes.

Luego para cada parte se definen los sucesores 0 y 1, que son los estados que siguen para entrada

0 y 1 respectivamente.

En el ejemplo:

Sucesores 0 de (ABD) son (BCC)

Sucesores 1 de (ABD) son (CAA).

Si los sucesores de un grupo no pertenecen a un grupo de equivalencia previo, debe efectuarse

una partición que deje sucesores en grupos de equivalencia. En el ejemplo debe partirse {A, B,

D}, ya que el sucesor 0 de A, y los sucesores 0 de B y D, no pertenecen al mismo grupo de

Capítulo 12. Equivalencia y Asignación de Estados. 3


equivalencia en P1. Lo mismo puede observarse en los sucesores 1 de A y los sucesores 1 de B y

D.

Entonces A no puede ser 2-equivalente con B y D, se tiene:

P2 = {A}, {B, D}, { C }

Ahora: sucesores 0 de (BD) son (CC) y sucesores 1 de (BD) son (AA). En ambos casos los

sucesores pertenecen a una de las clases anteriores.

Los estados sucesores 0 y 1, pertenecen a un mismo grupo en P2, por lo tanto: P3 = P2

Como no pueden generarse nuevas particiones se tendrá que B y D son equivalentes.

La razón por la cual P2 está formado por conjuntos de estados equivalentes, es que partiendo de

cualquier estado, de un conjunto determinado y para cualquier entrada de largo 2, se llega siempre

a un mismo conjunto. Y como los estados de un mismo conjunto generan igual salida para igual

entrada, se deduce que dichos estados son equivalentes.

Ejemplo 12.1

El siguiente ejemplo, ilustra con más detalle el método de reducción.

La siguiente tabla muestra la salida z0 para una entrada x0 de una secuencia de un bit, partiendo

de cada uno de los estados. Por ejemplo, estando en C, si llega un 0, la salida es 1.

Figura 12.3. Diagrama de estados Ejemplo 12.1

Las secuencia de salida, respecto a la de entrada, para los estados A, B y D, son iguales; no así

para el estado C. Lo cual muestra que C no puede ser equivalente con A, B o D. Esto justifica la

formación de la partición P1. Entonces C no es 1-equivalente con A, B o D.

La siguiente tabla muestra la secuencia de salida (z0z1) para una entrada de una secuencia de dos

bits (x0x1), partiendo de cada uno de los estados. Por ejemplo, estando inicialmente en A, si llega

la secuencia de entrada 10, en la salida se tiene la secuencia 11, y se recorren los estados C y D.

A B 0/0

C D

1/1

0/0 1/0

0/1

1/1

0/0

1/1

x0 A B C D

0 0 0 1 0

1 1 1 0 1

z0



Figura 12.4. Secuencia de salida para entrada de largo dos.

Se advierte que no es necesario plantear la columna a partir del estado C, ya que como ilustraba

la tabla anterior el primer bit será diferente. Se observa que las columnas asociadas a los estados

B y D son idénticas y diferentes de las secuencias de la columna A. Por lo tanto A, no puede ser

equivalente a los estados B y D. Esto implica la partición P2. El estado A no es 2-equivalente con

B o D.

La siguiente tabla muestra la secuencia de salida (z0z1z2) para una entrada de una secuencia de

tres bits (x0x1x2), partiendo de los estados B y D solamente. Por ejemplo, estando inicialmente en

B, si llega la secuencia de entrada 110, en la salida se tiene la secuencia 111, y se recorren la

secuencia de estados ACD. Esto implica la partición P3.

Figura 12.5. Secuencia de salida para entrada de largo tres.

Puede decirse que los estados B y D son 3-equivalentes, ya que no puede distinguirse entre ellos

para secuencias de largo tres de entrada, debido a que tienen iguales secuencias de salida. El

procedimiento de Moore permite encontrar los estados n-equivalentes, y cuando no pueden

formarse nuevas particiones determina los estados equivalentes.

Algoritmo de las particiones de Moore.

1. Colocar todos los estados en un conjunto.

2. La partición inicial (P1) está basada en la conducta de la salida.

3. Las particiones sucesivas están basadas en las transiciones al próximo estado.

4. Se repite paso (3) hasta que no se produzcan nuevas particiones.

Los estados que queden en un mismo conjunto son equivalentes. Puede demostrarse que el algoritmo es de costo polinomial.

x0x1 A B C D

00 00 01 10 01

01 01 00 11 00

10 11 10 00 10

11 10 11 01 11

z0z1

x0x1x2 B D

000 010 010

010 000 000

100 100 100

110 111 111

001 011 011

011 001 001

101 101 101

111 110 110

z0z1z2



Ejemplo 12.2.

Se tiene la siguiente matriz de transiciones:

Estado/Entrada 0 1

A C/1 B/0

B C/1 E/0

C B/1 E/0

D D/0 B/1

E E/0 A/1

Figura 12.6. Matriz de transiciones ejemplo 12.2.

Por inspección, puede verse que B y C son equivalentes.

Por particiones:

Se tienen P0 = {A , B, C, D, E} y P1 = {A, B, C }, {D, E }

Ya que A, B y C tienen salidas 1 y 0 para entrada 0 y 1 respectivamente. Y D y E tienen salidas 0

y 1 para entradas 0 y 1 respectivamente.

Sucesores 0 de (ABC) son (CCB)

Sucesores 1 de (ABC) son (BEE), implica partición.

Sucesores 0 de (DE) son (DE)

Sucesores 1 de (DE) son (BA).

Entonces: P2 = {A } , {B, C } , {D, E }

Sucesores 0 de (BC) son (CB)

Sucesores 1 de (BC) son (EE)

Sucesores 0 de (DE) son (DE)

Sucesores 1 de (DE) son (BA). Implica partición.

Entonces: P3 = { A }, {B, C} , {D}, {E}

Sucesores 0 de (BC) son (CB)

Sucesores 1 de (BC) son (EE).

Entonces: P4 = P3, y se tiene que B y C son equivalentes.

El método puede optimizarse, observando que algunos estados son equivalentes, luego de algunas

iteraciones. De este modo, no se requiere seguir obteniendo los sucesores de dichos estados.



Ejemplo 12.3.

Estado/Entrada 0 1

A E/0 D/1

B F/0 D/0

C E/0 B/1

D F/0 B/0

E C/0 F/1

F B/0 C/0


Se procede a determinar la secuencia de particiones:

P1 = {ACE} {BDF}

S0(ACE) =(EEC) S1(ACE) =(DBF) S0(BDF)= (FFB) S1(BDF)= (DBC)

P2 = {ACE} {BD} {F}

S0(ACE) =(EEC) S1(ACE) =(DBF) S0(BD )= (FF ) S1(BD )= (DB)

P3 = {AC} {E} {BD} {F}

S0(AC) =(EE ) S1(AC ) =(DB ) S0(BD )= (FF ) S1(BD )= (DB)

P4 = P3

Entonces A y C son equivalentes. B y D son equivalentes.

El método por inspección no permite ver estas equivalencias con sencillez.

Nótese que:

Ha medida que se reducen los conjuntos de equivalencia, también lo hacen los sucesores.

Cuando un estado queda aislado, no se requieren plantear sus sucesores.

Cuando los sucesores 0 y 1 son iguales a un mismo estado, el grupo completo es equivalente.

Ejemplo 12.4.

Reducir el siguiente diagrama de estados de una máquina, que analiza una secuencia de 4 bits de

la entrada, y que genera salida uno si el código no es BCD. La salida debe ser cero en el resto de

los casos. Ver Verificador BCD en 9.6.1.

Estado/Entrada 0 1

a b/0 c/0

b d/0 e/0

c f/0 g/0

d h/0 i/0

e j/0 k/0

f l/0 m/0

g n/0 o/0

h a/0 a/0

i a/0 a/0

j a/0 a/0

k a/0 a/0

l a/0 a/0

implica partir en: {BD} y {F}



m a/1 a/1

n a/1 a/1

o a/1 a/1


La partición P1 resulta de observar las diferentes secuencias de salida:

P1 ={a,b,c,d,e,f,g,h,i,j,k,l} {m,n,o}

S0(abcdefghijkl)=(bdfhjlnaaaaa) S1(abcdefghijkl)=(cegikmoaaaaa)

De S0(abcdefghijkl) f no puede estar en la primera partición; y de S1 f y g no pueden estar en el

mismo grupo.

S0(mno)=(aaa) S1(mno)=(aaa) Ya en este paso m, n y o son equivalentes.

Entonces se logra P2:

P2 ={a,b,c,d,e,h,i,j,k,l} {f} {g} {m,n,o}

S0(abcdehijkl)=(bdfhjaaaaa) S1(abcdehijkl)=(cegikaaaaa)

S0(mno)=(aaa) S1(mno)=(aaa) Estos sucesores no requieren considerarse nuevamente.

Debe separarse c.

P3 ={a,b,d,e,h,i,j,k,l}{c} {f} {g} {m,n,o}

S0(abdehijkl)=(bdhjaaaaa) S1(abdehijkl)=(ceikaaaaa)

Debe separarse a.

P4 ={a}{b,d,e,h,i,j,k,l}{c} {f} {g} {m,n,o}

S0(bdehijkl)=(dhjaaaaa) S1(bdehijkl)=(eikaaaaa)

Debe separarse al grupo: h, i, j, k, l

P5 ={a}{b,d,e}{h,i,j,k,l}{c} {f} {g} {m,n,o}

S0(bde)=(dhj) S1(bde)=(eik)

S0(hijkl)=(aaaaa) S1(hijkl)=(aaaaa) En este paso se determina que h,i,j,k y l son equivalentes.

Debe separarse b:

P6 ={a}{b}{d,e}{h,i,j,k,l}{c} {f} {g} {m,n,o}

S0(de)=(hj) S1(de)=(ik)

S0(hijkl)=(aaaaa) S1(hijkl)=(aaaaa)

No hay nuevas particiones que puedan generarse.

P6 = P7

Entonces el estado e es redundante. i,j,k,l se reemplazan por h; también n y o por m.

Queda el siguiente diagrama reducido:



Estado/Entrada 0 1

a b/0 c/0

b d/0 d/0

c f/0 g/0

d h/0 h/0

f h/0 m/0

g m/0 m/0

h a/0 a/0

m a/1 a/1

Figura 12.9. Matriz de transiciones reducida y diagrama de estados Ejemplo 12.4.

12.3.2. Método del diagrama de implicación.

Lo veremos a través de un ejemplo.

Determinar estados equivalentes para la siguiente máquina secuencial completamente

especificada.

Entradas x1 x0 Salida

Estado presente 00 01 10 11 z

S0 S0 S1 S2 S3 1

S1 S0 S3 S1 S4 0

S2 S1 S3 S2 S4 1

S3 S1 S0 S4 S5 0

S4 S0 S1 S2 S5 1

S5 S1 S4 S0 S5 0

Próximo estado

Figura 12.9a. Matriz de transiciones.

Se confecciona un diagrama triangular que tenga tantas celdas como posibles pares de estados.

Luego se marcan con diagonales cruzadas las casillas de estados que no puedan ser equivalentes

debido a que tienen salidas diferentes. Observando la tabla anterior, sólo podrían ser equivalentes

los pares: (S0, S2), (S0, S4), (S2, S4) por tener salida 1; y los pares (S1, S3), (S1, S5), (S3, S5)

por tener salida 0.

A las casillas que pueden representar estados equivalentes, por tener iguales salidas, se les

colocan los pares de estados que deben ser equivalentes; por ejemplo: S0 y S2 son equivalentes si

/0 /0

/0

/0

a

b

d

c

h

c

f g

m

h /1

/0

/0

0/

0

1/0

1/0

0/0

1/0

0/0



los siguientes pares son equivalentes: (S0, S1), (S1, S3), (S2, S2) (S3, S4). Esto puede verificarse

observando el primer y tercer renglón, para las diferentes combinaciones de las entradas. Nótese

que se podrían no escribir los pares formados por un solo estado.

Luego en las celdas que tienen pares marcados, se descartan aquellas cuyos pares ya estén

marcados como no equivalentes. Por ejemplo, la celda de la primera columna y segundo renglón

se descarta por tener como condición el par (S0, S1), que ya se conoce que no pueden ser

equivalentes.

Observando las casillas no marcadas se concluye que los pares (S3, S5) y (S0, S4) deben ser

estados equivalentes.

S0,S1

S1,S3

S2,S2

S3,S4

S0 S1 S2 S3 S4

S5

S4

S3

S2

S1

S0,S0

S1,S1

S2,S2

S3,S5

S0,S1

S3,S0

S1,S4

S4,S5

S1,S0

S3,S1

S2,S2

S4,S5

S0,S1

S3,S4

S1,S0

S4,S5

S1,S1

S0,S4

S4,S0

S5,S5

Figura 12.9b. Tabla de implicaciones.

La matriz reducida, eliminando los estados equivalentes, resulta:



Entradas x1 x0 Salida

Estado presente 00 01 10 11 z

S0 S0 S1 S2 S3 1

S1 S0 S3 S1 S0 0

S2 S1 S3 S2 S0 1

S3 S1 S0 S0 S3 0

Próximo estado

Figura 12.9c. Matriz reducida.

12.3.3. Minimización de estados en máquinas incompletamente especificadas.

Cuando la máquina está completamente especificada la equivalencia de estados es una relación

transitiva: Si a es equivalente con b, y b es equivalente con c, entonces a y c son también

equivalentes. Esto refleja que la equivalencia de estados es una relación de equivalencia que

particiona los estados en clases de equivalencia disjuntas.

Pero esto no se cumple si la matriz de transiciones contiene condiciones superfluas.

Estado Salidas

E0 -0

E1 1-

E2 -1

Figura 12.9d. Salidas con condiciones superfluas.

En la tabla anterior el estado E1 es compatible con E0 y E2, pero E0 no es compatible con E2.

En este caso no se dispone de algoritmos, de complejidad polinomial, que determinen las mejores

agrupaciones de estados en conjuntos equivalentes, los cuales permiten reducir el número de

estados. Existen numerosos programas CAD que realizan la minimización en este tipo de

máquinas.

12.4. Asignación de Estados.

12.4.1. Análisis del problema de asignación.

Dado el nombre lógico de un estado se desea formar un nombre físico en binario, dado por los

estados de los flip-flops.

Si se tienen e estados, el número mínimo m de flip-flops necesarios para codificarlos, debe

cumplir:

mm e 22 1



De acuerdo al principio de multiplicación, si una tarea A puede efectuarse de m formas diferentes,

y después de terminada en cualesquiera de estos modos, la tarea B puede ser realizada de n

diferentes modos; entonces la secuencia de tareas A, B puede ser efectuada de m por n modos.

Si de n elementos tomamos k de ellos (sin repetición, sólo puede tomarse una vez a cada

elemento), el primero puede ser elegido de n formas, el siguiente de (n-1) formas; y el k-ésimo de

(n-k+1) formas.

Éste es el número de permutaciones de n elementos tomando k a un tiempo, lo que puede

anotarse:

n(n-1)(n-2)....(n-k+1) = n!/(n-k)!

Entonces el número de asignaciones de estado de e estados con m flip-flops, resulta ser:

Si se tienen 4 estados lógicos A, B, C y D, se requieren dos flip-flops. Con dos flip-flops pueden

establecerse 4 estados binarios: 00, 01, 10, 11. El nombre binario de A, puede ser escogido de 4

formas, el de B de tres formas, el de C de dos formas y el último de una sola forma. Esto produce

24 formas de asignar estados, empleando dos flip-flops.

No todas estas asignaciones implican ecuaciones lógicas diferentes.

a) consideremos dos asignaciones binarias que tengan una variable complementada:

asignación 1: 01001001

asignación 2: 01011001

Cualquier función de próximo estado, puede expresarse usando la asignación 1 según:

f(a,b,c,d,e,f,g,h)

entonces la misma función, empleando la asignación 2 se puede expresar según:

f(a,b,c,d',e,f,g,h)

Es decir, las funciones tendrán estructura similar, salvo la complementación de una variable. Y

como en los flip-flops y PLDs se dispone de las variables y sus complementos, las dos

asignaciones en discusión llevarán a implementaciones de igual costo.

Con dos variables a y b, se tienen las siguientes formas: ab, a'b, ab' a'b'. En general m variables

pueden ser complementarse de 2m formas. Entonces, aplicando el principio inverso de la

multiplicación de las tareas, el número de asignaciones se reduce en el factor 2m.

b) consideremos un intercambio de columnas, para una determinada asignación:

2 !

2 !

m

mae

e



estado 1 ... ... ...

estado 2 ... ... ...

estado 3 ... ... ...

...

...

...

estado e ... ... ...

Figura 12.10. Intercambio de columnas en asignaciones.

Una determinada función de próximo estado puede escribirse:

(..., ,..., ,...)i jf y y

Si se escoge la asignación con el intercambio de columnas, la misma función podrá representarse

por:

(..., ,..., ,...)j if y y

Nuevamente estas asignaciones llevan a implementaciones de iguales costos.

Si se tiene m columnas, la primera puede escogerse de m formas, la segunda de (m-1) formas, y

así sucesivamente. Es decir existen m! asignaciones que llevan a iguales implementaciones.

Entonces el número de asignaciones de estados que llevan a posibles implementaciones diferentes

son:

Si bien aeu es mucho menor que ae, el crecimiento es importante a medida que aumenta e.

La siguiente tabla ilustra lo anterior:

e m ae aeu

2 1 1 1

3 2 24 3

4 2 24 3

5 3 6.720 140

6 3 20.160 420

7 3 40.320 840

Figura 12.11. Número de asignaciones de estados.

2 !

2 ! 2 !

m

m maeu

e m



Puede comprobarse que un conjunto de nombres únicos que pueden llevar a implementaciones

diferentes son, para e = 4:

Nombre lógico asig. 1 asig. 2 asig. 3

A 00 00 00

B 01 11 10

C 11 01 01

D 10 10 11

Figura 12.12. Asignaciones de estado únicas para cuatro estados.

A continuación se ilustran las 24 asignaciones posibles que se pueden efectuar con dos flip-flops.

L 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

A 00 00 10 01 11 10 01 11 00 00 10 01 11 10 01 11 00 00 10 01 11 10 01 11

B 01 10 11 00 10 00 11 01 11 11 01 10 00 01 10 00 10 01 00 11 01 11 00 10

C 11 11 01 10 00 01 10 00 01 10 11 00 10 00 11 01 01 10 11 00 10 00 11 01

D 10 01 00 11 01 11 00 10 10 01 00 11 01 11 00 10 11 11 01 10 00 01 10 00

Figura 12.13. Asignaciones de estado posibles para cuatro estados.

La 2 se genera por intercambio de columnas de la 1.

La 3 complementado la primera columna de la 1.

La 4 complementando la segunda columna de la uno.

La 5 complementado las dos columnas de la uno.

La 6, 7 y 8, complementando la primera, la segunda y ambas variables de la 2.

La 9 es la segunda asignación única.




La 17 es la tercera asignación única.




Debe notarse que cualquiera de las 8 primeras columnas puede ser elegida como asignación única

1. También cualquiera entre las columnas 9 a 16, puede ser la asignación única 2. La elección de

la asignación única 3 puede ser cualquier columna entre la 17 y 24. Se han elegido tres que

establezcan el estado A con nombre 00.

La siguiente tabla genera las 24 permutaciones posibles que se pueden efectuar con dos flip-flops

para colocar nombre binario a 4 estados. Se han mantenido los nombres de las columnas de la

Figura 12.13.



L 18 1 17 2 9 10 4 23 12 15 7 20 6 19 14 11 22 3 16 13 8 21 5 24

A 00 00 00 00 00 00 01 01 01 01 01 01 10 10 10 10 10 10 11 11 11 11 11 11

B 01 01 10 10 11 11 00 00 10 10 11 11 00 00 01 01 11 11 00 00 01 01 10 10

C 10 11 01 11 01 10 10 11 00 11 10 00 01 11 00 11 00 01 01 10 00 10 00 01

D 11 10 11 01 10 01 11 10 11 00 00 10 11 01 11 00 01 00 10 01 10 00 01 00

Figura 12.13a. Asignaciones de estado generadas por permutaciones.

No es posible, debido al rápido crecimiento de aeu, intentar buscar la solución óptima para la

asignación de estados. Esto debido a que se requerirían realizar aeu diseños y seleccionar el de

costo menor. En lugar de esto se desarrollan métodos que guíen a encontrar una asignación de

estados razonablemente buena.

Ejemplo 12.5.

Asignaciones diferentes conducen a implementaciones diferentes. Por ejemplo considere la

siguiente matriz de transiciones:

Estado/Entrada 0 1

A B/0 E/0

B C/0 G/0

C D/0 F/0

D A/1 A/0

E G/0 C/0

F A/0 A/1

G F/0 D/0


Se estudian las siguientes dos asignaciones de las 40.320 posibles:

Estado Lógico Estado Físico 1

y1y2y3

Estado Físico 2

y1y2y3

A 000 000

B 001 001

C 011 010

D 010 011

E 101 100

F 110 101

G 111 110

Figura 12.15. Comparación entre dos asignaciones.

Para la asignación 1, por un diseño convencional y usando JK, se logran:

J1 = xy2' + xy3; K1 = x + y3' ; J2 = y3 ; K2 = y3' ; J3 = y2' ; K3 = y2

z = y3'y2y1'x' + y3'y1'x



Considerando un inversor para formar x'. Pueden contarse 18 entradas a compuertas. Y 8 chips

convencionales SSI.

Para la asignación 2, se obtienen:

J1 = xy3' + xy2' ; K1 = x + y3 ; J2 = y1y3' + y1'y3 ; K2 = x'y1 + xy1' +y3

J3 = x'y1' + y2; K3 = 1; z = xy1y3 + x'y2y3

Se tienen 34 entradas y se requieren 16 chips SSI.

El ejemplo ilustra que no todas las asignaciones conducen a redes combinacionales de bajo costo.

La asignación 2 resulta bastante más costosa que la asignación 1.

12.4.2. Estrategias de asignación.

Si la codificación conduce a un mínimo número de flip-flops las funciones combinacionales de

próximo estado resultan complejas. Esta asignación resulta adecuada cuando la implementación

se realiza mediante CPLD.

La codificación one-hot emplea un flip-flop por estado, de este modo el diseño de las funciones

combinacionales de próximo estado resultan más sencillas. Esta forma de codificación presenta

ventajas cuando se implementa en FPGA, dispositivos que tienen bastantes flip-flops y

generadores de funciones de ancho limitado. Por ejemplo para tres estados, los códigos binarios

serían: 001, 010, 100.

En la codificación de contadores, pueden asociarse los estados a las salidas del dispositivo,

haciendo innecesarias las redes combinacionales de salida.

Debido a que no existen algoritmos polinomiales para enfrentar este problema se han desarrollado

algunas heurísticas.

12.5 Reglas para la asignación de Estados.

La forma tradicional de enfrentar el problema de la codificación binaria de estados es la

aplicación de reglas para efectuar la asignación. Estas reglas o heurísticas son las siguientes:

Regla de Alta prioridad:

Estados que tienen iguales estados próximos, para una entrada dada, se los debe asignar como

lógicamente adyacentes.



Figura 12.16. Regla de Alta prioridad.

Fundamentación de la regla: Las funciones de Estado Próximo pueden simplificarse al disminuir

la distancia entre Si y Sj. De este modo aumentan las adyacencias de los mintérminos de los unos

de S.

Regla de Prioridad Media:

Estados próximos de un estado presente, bajo entradas lógicamente adyacentes (a distancia

unitaria), se los debe asignar como lógicamente adyacentes.

Estado/Entradas xi xj

S Si Sj

....

Figura 12.17. Regla de prioridad media.

Fundamentación de la regla: Las funciones de Estado Próximo pueden simplificarse al disminuir

la distancia entre Si y Sj. De este modo aumentan las adyacencias de los mintérminos de los unos

de Si y Sj.

Regla de Baja Prioridad:

Estados con la misma salida para una entrada dada, se los debe asignar como lógicamente

adyacentes.

Si

S

Sj

xi xj

Est. Próximo


Si S

....

Sj S

Si Sj

xi xi

S Est. Próximo




Si S1/z

....

Sj S2/z

Est. Próximo/Salidas

Si

S1

xi/z

Sj

S2

xi/z

Figura 12.18. Regla de prioridad baja.

Fundamentación de la regla: Las funciones de Salida pueden simplificarse al disminuir la

distancia entre Si y Sj. De este modo aumentan las adyacencias de los mintérminos de los unos de

la salida.

Análisis de las reglas.

En la siguiente matriz de transiciones, según la primera regla, debemos asignar los estados S1 y

S2 como adyacentes. Esto debido a que tienen estados próximos iguales para la misma entrada. Si

asignamos S1= 010 y S2= 011, tendremos, asumiendo que el próximo estado tiene nombre binario

101:

Q2Q1Q0 x1x0=01

S1=010 101/0

S2=011 101/0

Q2+,Q1+,Q0+/z

Figura 12.18a. Regla de prioridad alta.

Con lo cual se logra, agrupando solamente los unos que se indican en el diagrama, para las

funciones de próximo estado:

Q2+= x1’x0(Q2’Q1Q0’+Q2’Q1Q0) = x1’x0(Q2’Q1)

Q0+= x1’x0(Q2’Q1Q0’+Q2’Q1Q0) = x1’x0(Q2’Q1)



Observamos que siempre se cancelará una de las variables de estado en las expresiones para los

estados próximos. Q0 en el caso del ejemplo.

En la siguiente matriz de transiciones, según la segunda regla, debemos asignar los estados S1 y

S2 como adyacentes. Esto debido a que son estados próximos de un mismo estado S, para

entradas adyacentes. Si asignamos S1= 101 y S2= 100, tendremos, asumiendo que S tiene código

binario 010:

Q2Q1Q0 x1x0=01 x1x0=11

S=010 S1=101/0 S2=100/1

Q2+,Q1+,Q0+/z

Figura 12.18b. Regla de prioridad media.

Con lo cual se logra, agrupando solamente los unos que se indican en el diagrama, para las

funciones de próximo estado:

Q2+= Q2’Q1Q0’(x1’x0+x1x0) = Q2’Q1Q0’(x0)

Q0+= Q2’Q1Q0’(x1’x0)

Observamos que en todos los casos, menos uno, se cancelará una variable de entrada en las

expresiones para los estados próximos. En el caso del ejemplo, la expresión para Q0+ contendrá

las dos variables de entrada; la expresión de Q2+ no contendrá a la variable x1.

De los dos casos particulares anteriores, puede concluirse que la regla de alta prioridad producirá

mayor minimización que la regla de prioridad media. Razón por la cual se les da estos nombres.

Ejemplo 12.6.

Asignar estados para la siguiente matriz de transiciones:

Estado/Entrada 0 1

A C/0 D/0

B C/0 A/0

C B/0 D/0

D A/1 B/1


Regla de alta prioridad:

a) A y B deben ser adyacentes. Van a C con entrada igual a 0.

b) A y C deben ser adyacentes. Van a D con entrada igual a 1.

Regla de prioridad media.



c) C y D deben ser adyacentes. Estados próximos de A, con x = 0 y x = 1.

d) C y A deben ser adyacentes. Estados próximos de B, con x = 0 y x = 1.

e) B y D deben ser adyacentes. Estados próximos de C, con x = 0 y x = 1.

f) A y B deben ser adyacentes. Estados próximos de D, con x = 0 y x = 1.

Regla de Prioridad Baja.

g) A, B y C deben ser adyacentes. Salida igual a 0 para x = 0.

h) A, B y C deben ser adyacentes. Salida igual a 0 para x = 1

Si se ubican en un mapa los nombres de los estados que deben ser adyacentes, cumpliendo la

primera regla, se tiene:

Figura 12.20. Asignación de estados ejemplo 12.6.

Del segundo grupo, con la primera regla de asignación, se cumplen: d) y f).

Si se elige la casilla vacante para D, se cumplen: c) y e).

Las reglas g) y h) no pueden satisfacerse. Ya que A es adyacente con B, y A es adyacente con C,

pero es imposible cumplir B adyacente con C.

Reemplazando los estados lógicos por los nombres físicos, se obtiene:

Estado/Entrada 0 1

A = 00 10/0 11/0

B = 01 10/0 00/0

C = 10 01/0 11/0

D = 11 00/1 01/1

Figura 12.21. Matriz de transiciones con asignación de estados.

Ordenando, según código Gray:

Q1 Q0

0 1

0

1

0 0

0 0 2

0 1

3

0 1

0

1

A B

C D 2

0 1

3



Estado Actual x

Q1Q0 0 1

00 10/0 11/0

01 10/0 00/0

11 00/1 01/1

10 01/0 11/0

Q1+Q0+/z

Figura 12.22. Matriz de transiciones con ordenamiento Gray.

Minimizando, y empleando flip-flops Ds:

D1 = Q1+ = x'Q1' + xQ0'

D0 = Q0+ = Q1Q0' + xQ0' + xQ1

z = Q1Q0

Resultan 15 entradas (en dos niveles). Debido a que existe el producto xQ0' que es común a

ambos flip-flops.

Para este caso, puede buscarse la asignación óptima, efectuando los diseños con todas las

asignaciones únicas de estado. Se tienen:

Nombre lógico asig. 1 asig. 2 asig. 3

A 00 00 00

B 01 11 10

C 10 10 11

D 11 01 01

Figura 12.23. Asignaciones óptimas para ejemplo 12.6.

La asignación 1 es la que resulta de aplicar las reglas, y que se vio antes.

Se efectuará el diseño para la asignación 2.

Estado/Entrada 0 1

A = 00 10/0 01/0

B = 11 10/0 00/0

C = 10 11/0 01/0

D = 01 00/1 11/1

Figura 12.24. Matriz de transiciones con asignación 2.

Que ordenando según código Gray, puede escribirse:



Estado/Entrada 0 1

00 10/0 01/0

01 00/1 11/1

11 10/0 00/0

10 11/0 01/0

Figura 12.25. Matriz de transiciones con asignación 2, ordenada en Gray.

Resulta el siguiente diseño, empleando flip-flops Ds:

D1 = Q1+ = x'Q1 + x'Q0' + xQ1'Q0

D0 = Q0+ = Q1Q0' + xQ1'

z = Q1'Q0

Resultan 18 entradas (en dos niveles).

Para la tercera asignación única, se tiene:

Estado/Entrada 0 1

A = 00 11/0 01/0

B = 10 11/0 00/0

C = 11 10/0 01/0

D = 01 00/1 10/1

Figura 12.26. Matriz de transiciones con asignación 3.

Resulta el siguiente diseño, empleando flip-flops Ds:

D1 = Q1+ = x'Q0' + x'Q1 + xQ1'Q0

D0 = Q0+ = x'Q0' + Q1'Q0' + xQ1Q0

z = Q1'Q0

Con 20 entradas, considerando el producto común x'Q0'.

Se comprueba entonces que, en este caso, las reglas para la asignación de estados llevan a una

asignación razonablemente buena. En la situación planteada es la óptima.

A medida que el número de estados aumenta, la asignación de estados requiere el uso de

herramientas de apoyo. Existen programas que facilitan la tarea de asignar estados.

Asignación one-hot.

Para la matriz de transiciones de la Figura 12.19, puede efectuarse la asignación de tipo one-hot,

en la cual cada estado tiene un nombre binario con un solo 1. Esto se muestra en la Figura 12.26a.

Si A es el estado inicial, la operación de reset, es ahora levemente más compleja.

Las variables de estado son las salidas de los flip-flops: Q3, Q2, Q1, Q0.



x

Q3Q2Q1Q0 0 1

A=0001 0100/0 1000/0

B=0010 0100/0 0001/0

C=0100 0010/0 1000/0

D=1000 0001/1 0010/1

Q3+Q2+Q1+Q0+/z

Figura 12.26a. Asignación one-hot para ejemplo 12.6.

Deben considerarse superfluas todas las combinaciones que tengan más de un uno en su nombre

binario. En la Figura 12.26b, puede observarse los mapas de Karnaugh de 5 variables, para las

variables de próximo estado Q3+ y Q2+.

00 01 11 10

00

01

11

10

d

1

d

1

d

d

d

d

d

d

d

d

d

d

2

1

8 4

Q1Q0

Q3Q2

Q3+ x=1

00 01 11 10

00

01

11

10

d

1

d

1

d

d

d

d

d

d

d

d

d

d

2

1

8 4

Q1Q0

Q3Q2

Q2+ x=0

Figura 12.26a. Asignación one-hot para ejemplo 12.6.

Minimizando empleando las condiciones superfluas, pero cubriendo sólo los mintérminos

presentes, se obtienen:

Q3+= Q3’Q1’x La cobertura Q3+=Q2x + Q0x es de mayor costo.

Q2+=Q3’Q2’x’ La cobertura Q2+=Q1x’+Q0x’ es de mayor costo.

Procediendo en forma similar para el resto de las funciones, se obtienen:

Q1+=Q2x’+Q3x

Q0+=Q3x’+Q1x

z= Q3

Deben evaluarse los diseños alternativos, basados en producto de sumas. Si se agrupan los ceros

de Q3+ se obtiene: (Q3+)’=Q2’Q0’x’ que equivale a: Q3+=Q2+Q0+x. Existiendo soluciones

similares para el resto de las variables.



Con un poco de práctica, pueden escribirse directamente los resultados a partir de la tabla de

transiciones de la Figura 12.26a.

Ejemplo 12.7.

Asignar estados para un reconocedor de secuencias de largo de tres bits, que tenga salida 1

cuando se tienen en la entrada las secuencias: 010 y 110; y salida cero en el resto de los casos. La

señal externa reset debe llevar la máquina al estado inicial.

Una vez eliminados los estados equivalentes, se obtiene la siguiente matriz de transiciones, con

E0 como el estado inicial:

Estado/Entrada 0 1

E0 E1/0 E1/0

E1 E2/0 E3/0

E2 E0/0 E0/0

E3 E0/1 E0/0


Estados que tienen iguales estados próximos, para una entrada dada, se los debe asignar como

lógicamente adyacentes. En este caso E2 y E3 debe ser adyacentes, tanto para entrada 0, como

para entrada 1, desde los estados 2 y 3 se va al estado 0.

Estados próximos de un estado presente, bajo entradas lógicamente adyacentes, se los debe

asignar como lógicamente adyacentes. Nuevamente implica asignar E2 y E3 como adyacentes,

ya que estando en E1 va estado 2 con entradas 0 y a E3 con entrada 1.

La regla que intenta minimizar la función de salida implica que E0, E1 y E2 deben ser adyacentes

ya que hay salida 0 para entrada cero. Además E0, E1, E2, E3 debe ser adyacentes ya que se tiene

salida cero para entrada 1.

Para obtener una función simple de reset se escoge el estado inicial E0 como 00.

La figura 12.28 ilustra tres asignaciones posibles.

La asignación 1 deja E0 como estado inicial, cumple E2 a distancia uno de E3, cumpliendo así las

dos primeras reglas en forma completa.

De la tercera regla cumple: E0 con E2, E0 con E1, E1 con E3. No pueden cumplirse: E1 con E2

del grupo con salida y entrada 0; tampoco pueden cumplirse: E0 con E3, y E1 con E2 del grupo

con entrada 1 y salida cero.



Figura 12.28. Asignaciones ejemplo 12.7.





con entrada 1 y salida cero.





con entrada 1 y salida cero. Además esta asignación resulta ser equivalente en costo a la

asignación 1, ya que deviene de ésta por intercambio de columnas.

Lo mismo ocurre con la asignación 4 que se obtiene de la asignación 2 por intercambio de

columnas.

Figura 12.29. Asignación 2 con intercambio de columna.

En resumen cualquiera de las asignaciones 1 a 4 puede ser una elección razonable, ya que

cumplen con las dos primeras reglas: tener E2 adyacente con E3, y el máximo posible de

cumplimiento de la tercera regla.

Q1 Q0

0 1

0

1

0 0

0 0 2

0 1

3

0 1

0

1

E0 E2

E1 E3 2

0 1

3

Q1 Q0

0 1

0

1

0 0

0 0 2

0 1

3

1

0

1

E0 E3

E1 E2 2

0 1

3

Asignación 1 Asignación 2

Q1 Q0

0 1

0

1

0 0

0 0 2

0 1

3

0 1

0

1

E0 E1

E2 E3 2

0 1

3

Asignación 3

Q1 Q0

0 1

0

1

0 0

0 0 2

0 1

3

0 1

0

1

E0 E1

E3 E2 2

0 1

3

Asignación 4



Ejemplo 12.8.

Reconocedor de secuencias de largo 4. Salida uno cuando llegan: 0110 y 1010; salida cero en el

resto de los casos. El comando externo reset, debe llevar al estado inicial.

El diagrama reducido de estados es el siguiente:

Estado/Entrada 0 1

E0 E1/0 E2/0

E1 E3/0 E4/0

E2 E4/0 E3/0

E3 E5/0 E5/0

E4 E5/0 E6/0

E5 E0/0 E0/0

E6 E0/1 E0/0

Figura 12.30 Matriz de transiciones reducida ejemplo 12.8

Primera regla: E3 adyacente con E4; E5 con E6

Segunda regla: E1 adyacente con E2; E3 con E4; E5 con E6.

Tercera regla: Para entrada 0, estados E0, E1, E2, E3, E4, E5 adyacentes entre sí. E0, E1, E2, E3,

E4, E5, E6 adyacentes entre sí para entrada 1.

Q0

Q2Q1

00 01

0

1

E0 E3

E1 E4

11 10

E6

E5 E2

Figura 12.31. Asignación de estados, aplicando reglas.

Primero asignamos E3 adyacente con E4, y E5 con E6, ya que figuran en la primera y segunda

regla. Después E1 con E2.

Con la asignación anterior se obtiene:



Q2Q1Q0 x=0 x=1

000 001/0 101/0

001 010/0 011/0

101 011/0 010/0

010 111/0 111/0

011 111/0 110/0

111 000/0 000/0

110 000/1 000/0

100 / /

Q2+,Q1+,Q0+/z

Figura 12.32. Matriz de transiciones con asignación de estados de Figura 12.31.

Escribiendo un mapa, se logra:

Figura 12.33. Mapa de Karnaugh de Figura 12.32.

Que permite obtener:

Q2+ = Q2'Q1+Q2'Q0'x ; Q1+ = Q2'Q1+Q2'Q0+Q1'Q0 ;

Q0+ = Q2'Q0' +Q2'Q1'x+Q2'Q1x'+Q2Q1'x'; z = Q2Q0'x'

12.6 Descomposición de Máquinas Secuenciales.

Debido a la aparición de componentes programables, puede ocurrir que se requieran demasiadas

entradas o salidas, o que no se tenga macroceldas con los productos necesarios. En estos casos

puede resultar conveniente descomponer una máquina secuencial en dos o más sub-máquinas que

se comuniquen. Este procedimiento está descrito en el libro de R. Katz cap. 9.5.

Q0x

Q2Q1

00 01

00

01

0010 1110

1010 1110 1

0 4

5

11 10

0001

0000 13

12 8

9

11

10

0110 1100

0100 1110 2

3 7

6

0000 0100

0000 0110 14

15 11

10

Q2+,Q1+,Q0+,z



Problemas resueltos.

Problema 12.1.

Para el siguiente diagrama de estados:

Figura P12.1. Diagrama de estados Problema 12.1.

a) Describir la función de la máquina secuencial.

b) Determinar estados equivalentes aplicando el método de las particiones. Reducir el diagrama

eliminando estados equivalentes asociados a letras de mayor orden; por ejemplo, si a y c son

equivalente, se elimina c.

c) Asignar nombres binarios a los estados, aplicando reglas. El estado inicial (a) debe estar

formado por puros ceros. Se deben elegir: b=001, d=010 y e=110, indicando si esta asignación

cumple o no las reglas.

d) Diseñar empleando flip-flops ds y compuertas. No es necesario dibujar el esquemático.

e) Diseñar empleando un registro de desplazamiento y compuertas. Si es necesario puede

agregarse otra componente o subsistema.

Solución.

a) Analiza secuencias de largo tres, determinando con salida 1 la llegada de las secuencias: 011 ó

100; para el resto de las posibles secuencias de tres bits la salida es cero.

b)

P0 = { a, b, c, d, e, f, g}

P1 = {e}, {f}, {a, b, c, d, g}

P2 = {e}, {f}, {b}, {c}, {a, d, g}

P3 = {e}, {f}, {b}, {c}, {a}, {d, g}

P4 = P3

Por lo tanto d es equivalente con g. Se elimina g.

c) Se tiene la siguiente tabla de transiciones:

Por la regla de mayor prioridad:

Estado Inicial

a

d

0/0 1/0

e

0/0 1/1

f

0/1 1/0

g

0/0 1/0

b 0/0 1/0

c 0/0 1/0

0/0 1/0



Deben ser adyacentes entre sí: def. Es decir: d con e, e con f y f con d.

Por la regla de mediana prioridad:

Deben ser adyacentes: b con c (nueva); d con e, y f con d (ya presentes en la regla de alta

prioridad)

Por la tercera regla, de menor prioridad, deben ser adyacentes entre sí: abcde y abcdf. (La función

de salida se minimiza agrupando los ceros, como producto de sumas)

Figura P12.2. Asignación de estados Problema 12.1.

Con las asignaciones dadas, que se ilustran en el mapa, se cumplen automáticamente que: d es

adyacente con e, de la primera regla; y d con a y b con a de la tercera regla; y sólo se puede

cumplir una de las dos siguientes: e con f o f con d.

c1) Si se elige f=011, f adyacente con d, no se puede cumplir que e sea adyacente con f; en este

caso a c debe asignarse 101, para cumplir la regla de media prioridad.

c2) Si se elige f=111, f es adyacente con e, y no puede cumplirse que f sea adyacente con d. En

este caso con c=101 se logra c adyacente con b (segunda regla). Es mejor asignar, en este caso c=

011, ya que además logra c adyacente con d, de la tercera regla.

c3) Si se elige f=100, f es adyacente con e, y no puede cumplirse que f sea adyacente con d; en

este caso conviene c=011, ya que logra b con c y además c con d de la tercera regla.

Para c2) quedan dos estados sin asignar, a los cuales pueden colocarse próximo estado y salida

superfluos. Resulta la siguiente tabla de transiciones.

Figura P12.3. Matriz de transiciones Problema 12.1.

x=0 x=1

a b/0 c/0

b d/0 e/0

c f/0 d/0

d a/0 a/0

e a/0 a/1

f a/1 a/0

Q2Q1Q0 x=0 x=1

a 000 001/0 011/0

b 001 010/0 110/0

c 011 111/0 010/0

d 010 000/0 000/0

e 110 000/0 000/1

f 111 000/1 000/0

100 / /

101 / /

Q2+Q1+Q0+/z

Q0

Q2Q1

00 01

0

1

a d

b 1

0 2

3

11 10

e

7

6 4

5



d) Formando un mapa

Figura P12.4. Mapa de matriz de transiciones Problema 12.1.

Se obtienen:

Q2+ = D2 = Q1’Q0x +Q2’Q1Q0x’

Q1+ = D1 = Q2’Q0 + Q1’x

Q0+ = D0 = Q1’Q0’+ Q2’Q1Q0x’

z = Q2Q0’x + Q2Q0x’

e) Usando un registro de desplazamiento con dos flip-flops.

Es necesario agregar un contador módulo tres.

Se tiene:

Secuencia 0 1 2 3 4 5 6 7

Contador 0 1 2 0 1 2 0 1

Qa 0 1 0 0 1 0 0 1

Qb 0 0 1 0 0 1 0 0

Registro Q1 0 x0 x1 x2 x3 x4 x5 x6

Q0 0 0 x0 x1 x2 x3 x4 x5

Entrada x0 x1 x2 x3 x4 x5 x6 x7

Figura P12.5. Secuencias Problema 12.1.

En la tabla anterior, el número de secuencia indica los cantos de reloj que han ocurrido hasta el

momento.

Después del primer canto del reloj, el contador pasa a la cuenta 1 (Qa=1 y Qb =0).

Q0x

Q2Q1

00 01

00

01

001/0 000/0

011/0 000/0 1

0 4

5

11 10

000/0 ФФФ/Ф

000/1 ФФФ/Ф

13

12 8

9

11

10

110/0 010/0

010/0 111/0 2

3 7

6

000/0 ФФФ/Ф

000/1 ФФФ/Ф 14

15 11

10

Q2+Q1+Q0+/z



Después del primer canto, el valor x0 pasa al primer flip-flop del registro.

Cuando la cuenta es dos, en la entrada se tiene x2, en Q1 se tiene x1 y en Q0 se tiene x0. Más

adelante se tiene en la entrada x5, en Q1 se tiene x4 y en Q0 se tiene x3.

Entonces:

Ha llegado la secuencia 011 se logra con Q0’Q1x

Ha llegado la secuencia 100 se logra con Q0Q1’x’

Ha llegado la secuencia 011 o la secuencia 100 en la cuenta dos del contador, se logra con:

z = (Q0’Q1x + Q0Q1’x’)QbQa’

El diseño del contador módulo tres, queda especificado por la siguiente tabla.

QbQa

00 01

01 10

10 00

11

Qb+Qa+

Figura P12.6. Contador módulo tres Problema 12.1.

De la cual se logran: Qb+= Db = Qa y Qa+ = Da = Qb’Qa’

El registro de desplazamiento, queda:

Figura P12.7. Registro desplazamiento Problema 12.1.

Otra solución es mediante un registro de desplazamiento formado por tres flip-flops.

Secuencia 0 1 2 3 4 5 6 7

Contador 0 1 2 0 1 2 0 1

Qa 0 1 0 0 1 0 0 1

Qb 0 0 1 0 0 1 0 0

Registro Q2 0 x0 x1 x2 x3 x4 x5 x6

Q1 0 0 x0 x1 x2 x3 x4 x5

Q0 0 0 0 x0 x1 x2 x3 x4

Entrada x0 x1 x2 x3 x4 x5 x6 x7

Figura P12.8. Registro con tres flip-flops Problema 12.1.

Q1 D1 Q0 D0 x



En esta situación, la salida se genera según:

z = Qb’Qa’(Q0’Q1Q2 + Q0Q1’Q2’)

Figura P12.9. Registro desplazamiento con tres flip-flops. Problema 12.1.

Problema 12.2.

Para el siguiente diagrama:

a) Determinar la matriz de transiciones y la ecuación de salida.

b) Reducir estados equivalentes. Dibujando el diagrama de estados resultante.

c) Dibujar el esquemático de la máquina secuencial más simple que realiza igual función

que el diagrama dado.

Figura P12.10. Esquemático. Problema 12.2.

Solución.

a) Se tienen: D1 = x’Q1’Q0’ + x Q0; D0 = Q1’ + x’ Q0’; z = Q1Q0’ +Q1’Q0 (Moore)

De los flip-flops Ds se tienen: Q1+ = D1 y Q0+ = D0

Figura P12.11. Matriz de transiciones. Problema 12.2.

Q2 D2 Q1 D1 x Q0 D0

x

Q1’ D1

Q1

Q0’ D0

Q0

z

Estado x z

Q1 Q0 0 1

0 0 11 01 0

0 1 01 11 1

1 1 00 10 0

1 0 01 00 1

Q1+Q0+

x

Estado 0 1

A=00 C B 0

B=01 B C 1

C=11 A D 0

D=10 B A 1

Estado + z



b) P1 = {A, C}, {B, D}

Sucesores 0 de AC = CA, Sucesores 1 de AC = BD

Sucesores 0 de BD = BB, Sucesores 1 de BD = CA

Entonces P2 = P1, y se tiene que A es equivalente a C; y que B es equivalente a D.

Figura P12.12. Matriz de transiciones reducida. Problema 12.2.

c) Se requiere un flip-flop, sea éste Q.

Para tipo D, se tienen Q+ = D = x’Q + xQ’; z = Q

Figura P12.13. Diseño basado en flip-flop D. Problema 12.2.

Observación. La salida genera el bit de paridad de la secuencia de entrada. La salida es uno si

en la secuencia se tiene un número impar de unos.

Con tipo JK: Se tiene xQ’ +x’Q = JQ’ +K’Q con lo que se obtiene: J = x; K = x

Figura P12.14. Diseño basado en flip-flop JK. Problema 12.2.

Problema 12.3.

Se tiene la siguiente matriz de transiciones:

Determinar si las proposiciones son verdaderas o falsas.

x z

Estado 0 1

A=0 A B 0

B=1 B A 1

Estado +

0 A/0

1

B/1

1

0

x z

Q 0 1

0 0 1 0

1 1 0 1

Q+

x

Q’ D Q z

x J

K Q’

Q z



Figura P12.15. Matriz de transiciones. Problema 12.3.

Solución:

P0 = {E0, E1, E2, E3, E4, E5, E6 }

P1 = {E0, E1, E2, E4, E6 } { E3, E5 }

S0(E0E1E2E4E6)=(E1E3E5E0E0) S0(E3E5)=(E0E0)

S1(E0E1E2E4E6)=(E2E4E6E0E0) S1(E3E5)=(E0E0)

P2={E0, E4, E6 }{ E1, E2 }{ E3, E5 }

S0(E0E4E6)=(E1E0E0) S0(E1E2)=(E3E5) S0(E3E5)=(E0E0)

S1(E0E4E6)=(E2E0E0) S1(E1E2)=(E4E6) S1(E3E5)=(E0E0)

P3={E0} { E4, E6 }{ E1, E2 }{ E3, E5 }

S0(E4E6)=(E0E0) S0(E1E2)=(E3E5) S0(E3E5)=(E0E0)

S1(E4E6)=(E0E0) S1(E1E2)=(E4E6) S1(E3E5)=(E0E0)

P4 = P3

P5 = P4 y así sucesivamente.

Entonces el mínimo número de estados (no equivalentes entre sí) es 4.

E3, E4 y E5 son 1-equivalentes es Falsa ya que E3 y E5 están en un grupo; y E4 en otro.

E3 y E5 son 2-equivalentes es Verdadera ya que E3 y E5 están en un mismo grupo en P2.

E4 y E6 son 3-equivalentes es verdadera, ya que E4 y E6 están en un mismo grupo en P3.

E0, E4 y E6 son equivalentes es Falsa. Ya que E4 es equivalente con E6, E1 con E2 y E3 con E5.

El conjunto P3 es igual a P5 es verdadera, ya que P5 = P4 = P3.

E1 y E2 son equivalentes es verdad.

El diagrama de estados se puede representar con 4 estados. Es verdadera, por ejemplo pueden

emplearse E0, E1, E4, E3.

El diagrama de estados se puede representar con 5 estados. Es verdadera, pero obviamente no es

la mejor solución. Quedarían dos estados equivalentes.

Estado x=0 x=1

E0 E1/0 E2/0

E1 E3/0 E4/0

E2 E5/0 E6/0

E3 E0/0 E0/1

E4 E0/0 E0/0

E5 E0/0 E0/1

E6 E0/0 E0/0

V F E3, E4 y E5 son 1-equivalentes.

V F E3 y E5 son 2-equivalentes

V F E4 y E6 son 3-equivalentes

V F E0, E4 y E6 son equivalentes

V F El conjunto P3 es igual a P5.

V F E1 y E2 son equivalentes

V F El diagrama de estados se puede representar

con 4 estados.

V F El diagrama de estados se puede representar

con 5 estados.

Dos estados son n-equivalentes si pertenecen a un

grupo o partición de Pn.



Problema 12.4.

Se tiene el siguiente diagrama de estados y algunas asignaciones de estados.

Determinar si las proposiciones son verdaderas o falsas.

Figura P12.16. Problema 12.4.

Mayor Prioridad: Estados con estados próximos iguales para igual entrada.

Mediana Prioridad: Próximos Estados para entradas adyacentes

Baja Prioridad: Estados con Iguales salidas para igual entrada.

Solución:

Mayor prioridad:

A adyacente con D, ya que con entrada 0 van al estado A.

C adyacente con D, ya que con entrada 1 van al estado D.

Mediana prioridad:

A adyacente con C, ya que son estados próximos de A, para entrada 0 y 1 respectivamente.

D adyacente con B, ya que son estados próximos de B, para entrada 0 y 1 respectivamente.

B adyacente con D, ya que son estados próximos de C, para entrada 0 y 1 respectivamente.

A adyacente con D, ya que son estados próximos de D, para entrada 0 y 1 respectivamente.

Baja Prioridad.

B adyacente con C, ya que tienen salida 1 para entrada 0 y 1.

A adyacente con D, ya que tienen salida 0 para entrada 0 y 1.

Estado x=0 x=1

A A/0 C/0

B D/1 B/1

C B/1 D/1

D A/0 D/0

Estado Asig.1 Asig.2 Asig. 3

A 00 00 00

B 10 01 01

C 11 11 10

D 01 10 11

V F Asig. 1 y Asig. 2 cumplen todas las reglas y tienen igual costo.

V F Asig. 1 y Asig. 3 cumplen todas las reglas y tienen igual costo.

V F Asig. 1 y Asig. 2 cumplen todas las reglas y tienen diferente costo.

V F Asig. 2 y Asig. 3 no cumplen todas las reglas.

V F A con D y B con C deben estar a distancia uno por regla de mayor prioridad.

V F A con D y B con C deben estar a distancia uno por regla de mediana prioridad.

V F A con D y B con C deben estar a distancia uno por regla de inferior prioridad.

V F A con D deben a estar a distancia uno por las tres reglas.



Figura P12.17. Asignaciones Problema 12.4.

Asig. 1 cumple AD, CD, BC. No cumple AC, DB (mediana prioridad).

Asig. 2 cumple AD, CD, BC, AD. No cumple AC, DB (mediana prioridad).

Asig. 3 cumple CD, AC, DB. No cumple: AD (alta), AD (mediana prioridad); BC y AD baja

prioridad.

Q1 Q0

0 1

0

1

0 0

0 0 2

0 1

3

0 1

0

1

A D

B C 2

0 1

3

Asig. 1

Q1 Q0

0 1

0

1

0 0

0 0 2

0 1

3

0 1

0

1

A B

D C 2

0 1

3

Asig. 2

Q1 Q0

0 1

0

1

0 0

0 0 2

0 1

3

0 1

0

1

A B

C D 2

0 1

3

Asig. 3



Índice general.

CAPÍTULO 12 .............................................................................................................................................. 1

EQUIVALENCIA Y ASIGNACIÓN DE ESTADOS. ............................................................................... 1

12.1. ESTADOS EQUIVALENTES. .................................................................................................................. 1 12.2 MÉTODO DE REDUCCIÓN DE ESTADOS POR INSPECCIÓN. .................................................................... 1 12.3. REDUCCIÓN DE ESTADOS EN MÁQUINAS COMPLETAMENTE ESPECIFICADAS. ...................................... 2

12.3.1. Método de Reducción de Moore. Método de las Particiones. .................................................... 2 Ejemplo 12.1 ....................................................................................................................................................... 3 Algoritmo de las particiones de Moore. .............................................................................................................. 4 Ejemplo 12.2. ...................................................................................................................................................... 5 Ejemplo 12.3. ...................................................................................................................................................... 6 Ejemplo 12.4. ...................................................................................................................................................... 6

12.3.2. Método del diagrama de implicación. ........................................................................................ 8 12.3.3. Minimización de estados en máquinas incompletamente especificadas. ................................. 10

12.4. ASIGNACIÓN DE ESTADOS. ............................................................................................................... 10 12.4.1. Análisis del problema de asignación. ...................................................................................... 10 Ejemplo 12.5. ....................................................................................................................................... 14 12.4.2. Estrategias de asignación. ....................................................................................................... 15

12.5 REGLAS PARA LA ASIGNACIÓN DE ESTADOS. ..................................................................................... 15 Regla de Alta prioridad: ...................................................................................................................... 15 Regla de Prioridad Media: .................................................................................................................. 16 Regla de Baja Prioridad: ..................................................................................................................... 16 Análisis de las reglas. .......................................................................................................................... 17 Ejemplo 12.6. ....................................................................................................................................... 18 Asignación one-hot. ............................................................................................................................. 21 Ejemplo 12.7. ....................................................................................................................................... 23 Ejemplo 12.8. ....................................................................................................................................... 25

12.6 DESCOMPOSICIÓN DE MÁQUINAS SECUENCIALES. ............................................................................ 26 PROBLEMAS RESUELTOS. .......................................................................................................................... 27

Problema 12.1. ..................................................................................................................................... 27 Problema 12.2. ..................................................................................................................................... 31 Problema 12.3. ..................................................................................................................................... 32 Problema 12.4. ..................................................................................................................................... 34

ÍNDICE GENERAL. ...................................................................................................................................... 36 ÍNDICE DE FIGURAS ................................................................................................................................... 37



Índice de figuras

Figura 12.1. Matriz de transiciones .................................................................................................. 1 Figura 12.2. Matriz de transiciones reducida. .................................................................................. 2 Figura 12.3. Diagrama de estados Ejemplo 12.1 ............................................................................. 3 Figura 12.4. Secuencia de salida para entrada de largo dos. ............................................................ 4 Figura 12.5. Secuencia de salida para entrada de largo tres............................................................. 4 Figura 12.6. Matriz de transiciones ejemplo 12.2. ........................................................................... 5 Figura 12.7. Matriz de transiciones ejemplo 12.3. ........................................................................... 6 Figura 12.8. Matriz de transiciones ejemplo 12.4. ........................................................................... 7 Figura 12.9. Matriz de transiciones reducida y diagrama de estados Ejemplo 12.4. ....................... 8 Figura 12.9a. Matriz de transiciones. ............................................................................................... 8 Figura 12.9b. Tabla de implicaciones. ............................................................................................. 9 Figura 12.9c. Matriz reducida. ....................................................................................................... 10 Figura 12.9d. Salidas con condiciones superfluas. ........................................................................ 10 Figura 12.10. Intercambio de columnas en asignaciones. .............................................................. 12 Figura 12.11. Número de asignaciones de estados. ....................................................................... 12 Figura 12.12. Asignaciones de estado únicas para cuatro estados. ................................................ 13 Figura 12.13. Asignaciones de estado posibles para cuatro estados. ............................................. 13 Figura 12.13a. Asignaciones de estado generadas por permutaciones. ......................................... 14 Figura 12.14. Matriz de transiciones ejemplo 12.5. ....................................................................... 14 Figura 12.15. Comparación entre dos asignaciones. ...................................................................... 14 Figura 12.16. Regla de Alta prioridad............................................................................................ 16 Figura 12.17. Regla de prioridad media. ........................................................................................ 16 Figura 12.18. Regla de prioridad baja. ........................................................................................... 17 Figura 12.18a. Regla de prioridad alta. .......................................................................................... 17 Figura 12.18b. Regla de prioridad media. ...................................................................................... 18 Figura 12.19. Matriz de transiciones ejemplo 12.6. ....................................................................... 18 Figura 12.20. Asignación de estados ejemplo 12.6. ....................................................................... 19 Figura 12.21. Matriz de transiciones con asignación de estados. ................................................. 19 Figura 12.22. Matriz de transiciones con ordenamiento Gray. ...................................................... 20 Figura 12.23. Asignaciones óptimas para ejemplo 12.6. ............................................................... 20 Figura 12.24. Matriz de transiciones con asignación 2. ................................................................. 20 Figura 12.25. Matriz de transiciones con asignación 2, ordenada en Gray.................................... 21 Figura 12.26. Matriz de transiciones con asignación 3. ................................................................. 21 Figura 12.26a. Asignación one-hot para ejemplo 12.6. ................................................................. 22 Figura 12.26a. Asignación one-hot para ejemplo 12.6. ................................................................. 22 Figura 12.27. Matriz de transiciones ejemplo 12.7. ....................................................................... 23 Figura 12.28. Asignaciones ejemplo 12.7. ..................................................................................... 24 Figura 12.29. Asignación 2 con intercambio de columna. ............................................................. 24 Figura 12.30 Matriz de transiciones reducida ejemplo 12.8 .......................................................... 25 Figura 12.31. Asignación de estados, aplicando reglas. ................................................................ 25 Figura 12.32. Matriz de transiciones con asignación de estados de Figura 12.31. ........................ 26 Figura 12.33. Mapa de Karnaugh de Figura 12.32. ....................................................................... 26 Figura P12.1. Diagrama de estados Problema 12.1. ...................................................................... 27



Figura P12.2. Asignación de estados Problema 12.1......................................................................28 Figura P12.3. Matriz de transiciones Problema 12.1. .....................................................................28 Figura P12.4. Mapa de matriz de transiciones Problema 12.1. ......................................................29 Figura P12.5. Secuencias Problema 12.1. ......................................................................................29 Figura P12.6. Contador módulo tres Problema 12.1. .....................................................................30 Figura P12.7. Registro desplazamiento Problema 12.1. ................................................................30 Figura P12.8. Registro con tres flip-flops Problema 12.1. .............................................................30 Figura P12.9. Registro desplazamiento con tres flip-flops. Problema 12.1. ...................................31 Figura P12.10. Esquemático. Problema 12.2. .................................................................................31 Figura P12.11. Matriz de transiciones. Problema 12.2. ..................................................................31 Figura P12.12. Matriz de transiciones reducida. Problema 12.2. ...................................................32 Figura P12.13. Diseño basado en flip-flop D. Problema 12.2. .......................................................32 Figura P12.14. Diseño basado en flip-flop JK. Problema 12.2. .....................................................32 Figura P12.15. Matriz de transiciones. Problema 12.3. .................................................................33 Figura P12.16. Problema 12.4. ......................................................................................................34 Figura P12.17. Asignaciones Problema 12.4. ................................................................................35

Equivalencia y Asignación de Estados.lsb/elo211/clases/c12.pdfde cada uno de los estados. Por...

Documents

Transcript of Equivalencia y Asignación de Estados.lsb/elo211/clases/c12.pdfde cada uno de los estados. Por...