cap. 8. descomposición - departamento de electrónicalsb/elo211/clases/c08.pdf · si se escribe la...

1

Profesor Leopoldo Silva Bijit 19-01-2010

Capítulo 8

Descomposición

La descomposición de un problema complejo en un número de subproblemas más simples de

resolver es una actividad usual en ingeniería.

En síntesis lógica es una actividad fundamental, ya que separa un sistema lógico de un número

elevado de entradas en un conjunto de subsistemas interconectados con un número menor de

variables de entrada.

En la actualidad los dispositivos programables están basados en unidades que pueden

implementar funciones con un número reducido de entradas y salidas. Por ejemplo en FPGAs

basadas en tablas de búsquedas de k entradas se pueden representar funciones boolenas con k

variables de entrada y una salida. Entonces la tarea es descomponer los nodos de una red

boolena que tengan más de k entradas en subredes funcionalmente equivalentes que estén

formadas solamente por nodos con k o menos entradas.

Figura 8.1. Descomposición paralela y serial.

La Figura 8.1, a la izquierda, muestra la descomposición paralela, que separa la red en varias

redes con menor número de entradas y salidas. La ubicada a la derecha ilustra la

descomposición en serie.

La descomposición funcional de los circuitos combinacionales influye poderosamente en la

disminución de costos de implementación de los sistemas digitales. Y tiene su fundamento en

que las tablas de verdad de funciones combinacionales, de un número elevado de variables,

pueden contener redundancias, las que pueden ser eliminadas por la descomposición de la

función en varias funciones independientes con menos variables de entrada.

2 Sistemas Digitales


Esta descomposición no sólo reduce la complejidad sino que aumenta la escalabilidad y la

realizabilidad de los sistemas.

Desde un punto de vista matemático la descomposición es el proceso de expresar una función de

n variables como una función de funciones con variables menores que n.

Se exponen los principales resultados de la teoría de descomposición, ilustrando los diferentes

ejemplos mediante mapas, lo cual es posible para un número reducido de variables. Sin embargo

en problemas reales con un número elevado de variables, para resolver cada uno de los

subproblemas asociados a la descomposición existen heurísticas, que han permitido desarrollar

aplicaciones computacionales que resuelven el problema. Su exposición tiene mayor relación

con cursos de estructuras de datos y algoritmos.

8.1. Descomposición trivial. Teorema de Shannon.

8.1.1. Extracción de una variable.

Una función de n variables puede ser descompuesta, aplicando el teorema de expansión de

Shanonn, según:

1 2 1 1 2 1 1 2 1( , ,.., , ) ' ( , ,.., ,0) ( , ,.., ,1)n n n n n nf x x x x x f x x x x f x x x

Xn f(Xn) f

Figura 8.2 Función de n variables.

En la Figura 8.1. se ha definido: 1 2 1, ,.., ,n n nX x x x x

Si definimos las funciones de (n-1) variables, según:

0 1 2 1 1 2 1

1 1 2 1 1 2 1

( , ,.., ) ( , ,.., ,0)

( , ,.., ) ( , ,.., ,1)

n n

n n

g x x x f x x x

g x x x f x x x

Podremos expresar:

1 2 1 0 1( , ,.., , ) ( , , )n n nf x x x x F g g x

Con:

0 1 0 1( , , ) 'n n nF g g x x g x g

Capítulo 8. Descomposición 3


f(Xn)

xn

Xn-1

g0

g1 F(g0, g1, xn)

Figura 8.3 Descomposición trivial.

Donde: 1 1 2 1, ,..,n nX x x x

La descomposición consiste en encontrar las funciones: g0, g1 y F. Las funciones gi se

denominan funciones predecesoras o auxiliares; y la descomposición se denomina serial o en

red lógica de tipo árbol.

La función F, puede ser implementada usando un multiplexor.

f(Xn)

xn

Xn-1

g0

g1

0

1

Figura 8.4 Implementación con multiplexor.

Si se escribe la tabla de verdad de f como una matriz, similar a un mapa de Karnaugh, donde los

renglones representan los valores de xn, y las columnas asociadas a los valores de las

combinaciones del resto de las (n-1) variables, se tiene la Figura 8.5, la que representa una

función de 4 variables:

x4/x1x2x3 000 001 011 010 110 111 101 100

0 1 1 1 1 1

1 1 1 1

Figura 8.5. Tabla de verdad de una función de 4 variables.

Entonces el primer renglón es la tabla de verdad de la función g0; el segundo corresponde al

mapa de g1.

La función g0, puede minimizarse empleando el siguiente mapa de tres variables:



x3/x1x2 00 01 11 10

0 1 1 1

1 1 1

g0=x2’+x1’x3’

Figura 8.6 Mapa de g0.

La función g1, puede minimizarse empleando el siguiente mapa de tres variables:

x3/x1x2 00 01 11 10

0 1 1

1 1

g1=x1x2+x2x3’

Figura 8.7 Mapa de g1.

Resultando:

0 1 3 3 0 3 1 3 2 1 3 3 1 2 2 3( , , ) ' '( ' ' ') ( ')F g g x x g x g x x x x x x x x x

8.1.2. Extracción de dos variables.

Del mismo modo pueden disminuirse las entradas a las funciones auxiliares, generando

funciones con un número menor de variables de entrada. La Figura 8.8 muestra las funciones

cofactores cuando se han extraído las variables xn y xn-1.

f(Xn)

xn-1, xn

g0

g1

F(g0, g1, g2, g3, xn-1, xn)

Xn-2

g2

g3

Figura 8.8. Descomposición en 4 subfunciones.

Las funciones de (n-2) variables se obtienen a partir de la función f, según:

0 1 2 2 1 2 2

1 1 2 2 1 2 2

2 1 2 2 1 2 2

3 1 2 2 1 2 2

( , ,.., ) ( , ,.., ,0,0)

( , ,.., ) ( , ,.., ,0,1)

( , ,.., ) ( , ,.., ,1,0)

( , ,.., ) ( , ,.., ,1,1)

n n

n n

n n

n n

g x x x f x x x

g x x x f x x x

g x x x f x x x

g x x x f x x x



La función F, queda dada por:

0 1 2 3 1 1 0 1 1 1 2 1 3( , , , , , ) ' ' ' 'n n n n n n n n n nF g g g g x x x x g x x g x x g x x g

La cual puede ser implementada mediante un mux de 4 vías a una, según se muestra en la

Figura 8.9.

f(Xn)

xn-1, xn

g0

g1

Xn-2

g2

g3

0

1

2

3

Figura 8.9. Multiplexor de 4 vías.

La identificación de las funciones auxiliares o cofactores pueden visualizarse como los

renglones del mapa de Karnaugh, cuando en los renglones se ubican los valores de las

combinaciones de las variables que controlan el multiplexor, que podríamos llamar variables

libres. La Figura 8.10, ilustra el caso de una función de 5 variables.

x4x5/x1x2x3 000 001 011 010 110 111 101 100

00 1 1 1 1 1

01 1 1 1

11 1 1 1

10 1 1 1 1

Figura 8.10. Tabla de verdad de una función de 5 variables.

Donde las funciones gi, se pueden minimizar empleando mapas de tres variables.

8.2. Descomposición de Ashenhurst.

En 1952 Ashenhurst demuestra las condiciones en que una función f puede ser descompuesta

en la forma:

1 2 1 1 2 1 2( , ,.., , ) ( , ,.. , ( , ,.., ))n n k k k nf x x x x h x x x g x x x

Se define el conjunto de k variables libres, según: 1 2, ,..,l kX x x x , y el conjunto de variables

acotado según: 1 2, ,..,a k k nX x x x . Debe notarse que el número de variables de entrada



que tiene la subfunción g es (n-k), y que el número de variables de entrada del bloque h es de

(k+1) variables, ambos menores que n.

El módulo g debe poder ser implementado en un dispositivo en el cual se pueda programar una

función de (n-k) variables de entrada y una salida.

Si la función h tiene más de (n-k) entradas puede ser descompuesta de manera similar.

Generando una red multinivel con estructura de árbol. Si resultan en el proceso dos funciones

iguales, basta utilizar una instancia, y generar múltiples salidas de este bloque; en este caso la

estructura deja de ser de tipo árbol para convertirse en un grafo dirigido acíclico.

Se dice que la descomposición es disjunta ya que el conjunto de variables de entrada es partido

en dos subconjuntos con intersección vacía.

f(Xn)

Xl

Xa g

h(g, Xl)

Figura 8.11. Descomposición de Ashenhurst.

8.2.1. Compactando las columnas.

Si se dibuja la tabla de verdad, colocando en los renglones las combinaciones de los valores de

las variables libres, y en las columnas los valores de las combinaciones del conjunto acotado, se

tiene una matriz denominada de descomposición.

La condición para que pueda aplicarse la descomposición de Ashenhurst, es que las columnas

de este arreglo tengan a lo más dos valores diferentes. Uno de los valores de las columnas estará

asociado a 1 2( , ,.., ) 0k k ng x x x ; el otro a 1 2( , ,.., ) 1k k ng x x x .

Consideremos el siguiente ejemplo de 5 variables.

x1x2/x3x4x5 000 001 010 011 100 101 110 111

00

01 1 1 1 1

10 1 1 1 1

11 1 1 1 1 1 1 1 1

Figura 8.12. Matriz de descomposición con dos columnas con valores diferentes.

Se tienen dos posibles elecciones para la función h, dependiendo de la columna que se asocie al

valor de g=0. La Figura 8.13 ilustra una de las elecciones posibles.



x1x2/g(x3,x4,x5) 0 1

00

01 1

10 1

11 1 1

h

Figura 8.13. Tabla de verdad de h(g,Xa).

Resulta, minimizando: 1 2 1 2( )h x x x x g

Si se elige la otra columna asociada al valor de g=0, resulta una función de igual costo, salvo

que aparece g’ en la expresión. Nótese que se efectúa una minimización o reducción de

columnas equivalentes.

Las cuatro columnas asociadas a g=1, permiten determinar la función 3 4 5( , , )g x x x .

Corresponden a los valores equivalentes decimales del conjunto 3 4 5, , 3,5,6,7x x x .

x5/x3x4 00 01 11 10

0 1

1 1 1 1

g=x3x4+x3x5+x4x5

Figura 8.14. Tabla de verdad de g(Xa).

Debe notarse que tanto h como g pueden implementarse con bloques que tengan un número de

entradas acotado a 3. Si se efectúa el diseño con compuertas tradicionales, se obtiene un diseño

en cuatro niveles con 17 entradas.

Un diseño mínimo en dos niveles permite obtener la expresión con 27 entradas:

1 2 1 3 4 2 3 4 1 3 5 2 3 5 1 4 5 2 4 5f x x x x x x x x x x x x x x x x x x x x

La cual al ser factorizada, permite obtener:

1 2 1 2 3 4 3 5 4 5( )( )f x x x x x x x x x x

Expresión en la cual pueden reconocerse las funciones g y h, obtenidas mediante

descomposición.

Esta descomposición disjunta se basa en la mezcla de las columnas equivalentes con el objetivo

de remover las redundancias de la tabla de verdad de n variables.



8.2.2. Redundancia de renglones.

Otra forma de encontrar las condiciones suficientes y necesarias para que exista la

descomposición de Ashenhurst es observar los renglones de la matriz, que representan las

combinaciones de valores que puede tomar el conjunto libre de variables de entrada.

Observando las Figuras 8.3 y 8.8, se puede generalizar el resultado para la extracción de k

variables, notando que la función f puede descomponerse en 2kfunciones ( )i lg X , una por cada

renglón. Con 2km el número de funciones auxiliares, se tiene:

f(Xn)

Xl

g0

g1

Xa

…

gm-1

0

1

…

2k-1

Figura 8.15. Multiplexor de m entradas, controlado por variables libres.

Pero como la descomposición de Ashenhurst sólo tiene una función g, las diferentes funciones

cofactores deben ser constantes (formadas por solamente ceros o unos), o poder ser expresadas

en términos de una sola función o su complemento.

Dicho de otro modo: no considerando los renglones formados por solamente ceros o unos, o

aquellos que son complementos de otros renglones, sólo puede existir un y solo un renglón

diferente, el cual estará asociado a la función g de la Figura 8.11.

La Figura 8.16, muestra la estructura interna de la función h: un bloque C, que solamente

interconecta sus cuatro posibles entradas con las 2kentradas del mux; observando el diagrama

en bloques la función combinacional h depende de g y lX , que es la forma deseada de

descomposición.



f(Xn)

0

Xl

Xa g C

1

0

1

…

2k-1

h(g,Xl)

Figura 8.16. La función h es el multiplexor más red combinacional.

En el caso del ejemplo de la Figura 8.12, esto se cumple, ya que existe un solo renglón diferente

en la matriz, además de las constantes. En este ejemplo no existe un renglón que sea

complemento de otro. Observando la tabla de la Figura 8.12, la función h puede escribirse:

1 2 1 2 1 2( ' ')h x x x x x x g

La que minimizada en el espacio de las variables libres y g, tres variables en este caso, permite

obtener:

1 2 1 2( )h x x x x g

La función g, se determina obteniendo la tabla de verdad del segundo o tercer renglón, en

términos de las variables acotadas, lo que se muestra en la Figura 8.14.

Esta descomposición disjunta se basa en la extracción de los renglones equivalentes con el

objetivo de remover las redundancias de la tabla de verdad de n variables.

8.2.3. Complejidad de la descomposición.

La dificultad computacional de la descomposición está en la revisión de las diferentes

particiones de la tabla de verdad que pueden realizarse.

Como existen C(n, a) combinaciones de a variables de un conjunto de n, que es el número de

formas de escoger a elementos de un total de n, donde C(n, a) es el coeficiente binomial; se

tendrá ese número de particiones posibles. Además cada tabla tendrá 2nvalores. Esto implica

que el método descrito es no polinomial, debido al crecimiento exponencial.

Si lo que interesa es obtener todas las particiones posibles, aceptando que tanto las variables

acotadas como las libres puedan ser cero, se tendrá un número total de particiones igual a 2n,

ya que se tiene que:



... 20 1 1

nn n n n

n n

Para el caso del ejemplo descrito en la tabla de la Figura 8.11, se tienen 10 particiones,

considerando que el número de variables del conjunto acotado es 3. Se enumeran a continuación

los conjuntos de los índices de las variables acotadas: {1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4},

{1, 3, 5}, {1, 4, 5}, {2, 3, 4}, {2, 3, 5}, {2, 4, 5}, {3, 4, 5}. En el ejemplo visto antes sólo se

analizó el último conjunto.

Pero no todas las particiones permiten obtener una descomposición disjunta de Ashenhurst.

La partición, en la cual las variables acotadas son x2x3x4, se muestra en la Figura 8.17, en la cual

hay 5 columnas diferentes, lo cual implica que no existe la descomposición de Ashenhurst. Lo

mismo puede concluirse al observar que existen cuatro renglones diferentes.

x1x5/ x2x3x4 000 001 010 011 100 101 110 111

00 1

01 1 1 1

10 1 1 1 1 1

11 1 1 1 1 1 1

Figura 8.17. Partición {2, 3, 4}.

La tabla se construyó con el mapa de la expresión mínima en dos niveles de f.

1 2 1 3 4 2 3 4 1 3 5 2 3 5 1 4 5 2 4 5f x x x x x x x x x x x x x x x x x x x x

Entonces la descomposición es de complejidad no polinomial y para su implementación

práctica, deben resolverse los subproblemas: la generación de particiones, la determinación de

cuales columnas o renglones son equivalentes y los métodos para determinar las subfunciones.

Existen numerosas contribuciones para resolver estos problemas: Algunas basadas en grafos

coloreados, otras en cálculo con cubos, otras en diagramas de decisión binarios. Todas ellas

escapan a un curso introductorio de sistemas digitales.

8.3. Descomposición de Curtis.

Lo primero que debe explorarse es si existe la descomposición de Ashenhurst, ya que ésta

descompone de manera significativa el problema. Sin embargo en muchos casos esta

descomposición no existe, en esta situación puede continuarse aplicando la descomposición de

Curtis.

Si en la Figura 8.3, consideramos un conjunto limitado de (n-k) variables de entrada, en las

funciones auxiliares, asumiendo que las funciones gi, se implementarán con bloques que tienen

también un número acotado de entradas y una salida, podemos considerar el resto de las

variables como un conjunto de k variables que denominaremos libre.



Para el caso tratado antes de extracción de una variable, que se muestra en la Figura 8.3, se tiene

que k=1 y por lo tanto: (n-k)=n-1, este caso se denomina descomposición simple o trivial.

8.3.1. Descomposición de Curtis, con dos funciones auxiliares.

Interesa la situación en que los bloques gi tienen acotado el número de variables de entrada. El

esquema general de las funciones, con la notación introducida, se muestra en la Figura 8.18,

para el caso de dos funciones seriales.

f(Xn)

Xl

Xa

g0

g1 F(g0, g1, Xl)

Figura 8.18. Descomposición disjunta de Curtis.

Si los dos conjuntos de variables tienen intersección vacía, se denomina disjunta a la

descomposición. Una vez encontradas las funciones g0, g1, y F, puede volver a aplicarse

descomposición a la función F, hasta que todos los bloques seriales gi tengan no más de (n-k)

entradas.

Demostraremos las condiciones necesarias y suficientes para que pueda encontrarse la

descomposición anterior.

Si se dibuja la tabla de verdad, colocando en los renglones las combinaciones de los valores de

las variables libres, y en las columnas los valores de las combinaciones del conjunto acotado, la

condición para que pueda aplicarse la descomposición de Curtis, con dos funciones auxiliares,

es que las columnas de este arreglo tengan a lo más cuatro valores diferentes. Las cuatro

columnas no redundantes quedarán asociadas a los siguientes valores:

1 0, 00,01,10,11g g

El mapa formado por 4 columnas y 2k renglones, define la función F, en términos de Xl, g1 y

g0.

Las mezclas de las columnas equivalentes, permiten determinar las funciones auxiliares en

términos de las variables del conjunto acotado.

Nótese que en este caso el número de columnas equivalentes debe ser mayor que 2; ya que si

sólo fueran dos podría aplicarse la descomposición de Ashenhurst. Puede decirse que la

descomposición simple de Curtis, cuando sólo se tienen dos columnas diferentes, es la

descomposición de Ashenhurst.



Si las columnas equivalentes fueran solamente 3, la determinación de la función F, se ve

simplificada por la introducción de una columna con valores superfluos.

El análisis de los renglones permite establecer que existe la descomposición de Curtis, con dos

funciones seriales, si se tienen dos renglones diferentes, una vez eliminados los renglones

constantes y los renglones que son el complemento de otros.

8.3.2. Descomposición de Curtis, con m funciones auxiliares.

El resultado anterior puede generalizarse cuando se tienen a lo más 2m columnas diferentes. En

este caso se tendrán m funciones auxiliares. Si a es el número de variables que forman el

conjunto acotado, la descomposición se aplica si m < a; notar que si m=a, el número de entradas

a la función F, no disminuye.

Alternativamente se tiene una descomposición general de Curtis: si se tienen m renglones

diferentes, una vez eliminados los renglones constantes y los renglones que son el complemento

de otros.

f(Xn)

Xl

Xa

g0

g1

F(g0, g1, …, gm-1, Xl) …

gm-1

Figura 8.19. Descomposición disjunta de Curtis.

Entonces para n variables, con k variables libres, y m columnas equivalentes en la tabla de

verdad de 2 2k n k se tiene la descomposición de Curtis, si y solamente si:

1

2

k

m n k

Nótese que los bloques g, representan una codificación de las variables del conjunto acotado, y

existe compactación si: m < n-k.

Algunas funciones pueden descomponerse por compactación de renglones y no por mezcla de

columnas y también ocurre lo opuesto. Debido a esto pueden considerarse métodos de

descomposición diferentes.



8.3.3. Fundamentos.

Si se escribe la tabla de verdad de la función f de n variables, pero en la cual se colocan en los

renglones las combinaciones de las k variables libres y en las columnas las combinaciones de las

a variables acotadas; y se rotulan las columnas de acuerdo al valor decimal equivalente se

obtiene la matriz de descomposición de 2kr renglones y 2ac columnas. Esta matriz es

similar a un mapa de Karnaugh, pero sin emplear codificación Gray para enumerar renglones y

columnas.

Por ejemplo para la función completamente especificada, de cinco variables:

1 2 3 4 5( , , , , ) (0,6,7,8,13,15,17,19,22,23,24,25,27,28)f x x x x x m

Con el conjunto de variables acotado 1 2 3, ,A x x x y el conjunto de variables libres:

4 5,L x x

La matriz de descomposición resulta:

A 0 1 2 3 4 5 6 7

L x4x5\x1x2x3 000 001 010 011 100 101 110 111

0 00 1 1 1 1

1 01 1 1 1

2 10 1 1

3 11 1 1 1 1 1

f(A, L)=f(x1,x2,x3,x4,x5)

Figura 8.20. Matriz de descomposición.

Si descomponemos las variables en términos de los subconjuntos A y L, podemos escribir:

1 2 3 4 5( , , , , ) ( , )f x x x x x f A L

La cual puede escribirse en términos de los renglones, en lugar de los mintérminos:

4 5 4 5 4 5 4 5( , ) ( ,0) ' ' ( ,1) ' ( ,2) ' ( ,3)f A L f A x x f A x x f A x x f A x x

El primer renglón de f, es una función de tres variables, que representa los mintérminos de ese

renglón, lo cual puede anotarse:

1 2 3 1 2 3 1 2 3 1 2 3 1 2 3( ,0) ( , , ,0,0) ' ' ' ' ' 'f A f x x x x x x x x x x x x x x x

Existiendo definiciones similares para el resto de los renglones.



Si además definimos el producto de las variables de L, con el subíndice decimal equivalente del

mintérmino asociado a esas dos variables, como ( )ip L . Se tienen:

0 4 5( ) ' 'p L x x , 1 4 5( ) 'p L x x y así sucesivamente.

Empleando estas definiciones, puede escribirse:

0 1 2 3( , ) ( ,0) ( ) ( ,1) ( ) ( ,2) ( ) ( ,3) ( )f A L f A p L f A p L f A p L f A p L

Y empleando notación con sumatorias, resulta: 3

0

( , ) ( , ) ( )i

i

i

f A L f A i p L

De manera similar la expansión por columnas, puede anotarse:

7

0

( , ) ( , ) ( )i

i

i

f A L f i L p A

En un caso general de n variables, la expansión por columnas, resulta con c igual al número de

columnas de la matriz:

1 2

0

( , ,..., ) ( , ) ( , ) ( )i c

n i

i

f x x x f A L f i L p A

En la Figura 8.21, se muestra una implementación con multiplexor, controlado por las variables

acotadas de la expansión. Notar que las entradas al mux son funciones de las variables libres,

que representan los unos presentes de la función en cada columna. Existe simplificación en la

descomposición si varias de estas funciones son iguales entre sí, o bien si unas son el

complemento de otras, o si son constantes. La generación de una entrada lógica uno o cero, no

requiere electrónica para ser implementada; si una función es el complemento de otra, basta un

inversor para generarla.

f(A,L)

A

L

f(0,L)

f(1,L)

f(i,L)

f(c,L)

0

1

i

c

…..

.

…..

.

Figura 8.21. Expansión por columnas.

La expansión por renglones, para un caso general con r igual al número de renglones, resulta:



1 2

0

( , ,..., ) ( , ) ( , ) ( )i r

n i

i

f x x x f A L f A i p L

En la Figura 8.22, se muestra una implementación con multiplexor, controlado por las variables

libres, de la expansión. Notar que las entradas al mux son funciones de las variables acotadas,

que representan los unos presentes de la función en cada renglón. Existe simplificación en la

descomposición si varias de estas funciones son iguales entre sí, o bien si unas son el

complemento de otras, o si son constantes.

f(A,L)

L

A

f(A,0)

f(A,1)

f(A,i)

f(A,r)

0

1

i

r

…..

.

…..

.

Figura 8.22. Expansión por renglones.

Estas representaciones son únicas, ya que en ambos casos se están representando los

mintérminos de la función f. En un caso se expande por columnas, en el otro por renglones.

1 2

0 0

( , ,..., ) ( , ) ( ) ( , ) ( )i c i r

n i i

i i

f x x x f i L p A f A i p L

Una vez introducida la notación, nos interesa descomponer f en las funciones g y h, según:

( , ) ( ( ), )f A L h g A L

Lo cual representa analíticamente a la descomposición serial, que se muestra en la Figura 8.23.

En la cual interesa determinar las funciones h y g.

f(A,L)

L

A g

h( g(A), L)

Figura 8.23. Descomposición serial disjunta.

Si cg es el número de columnas de la matriz que representa a la función h, se tiene la siguiente

representación por columnas:



0

( , ) ( , ) ( )i cg

i

i

h g L h g i L p g

El mínimo número de columnas es dos, es decir cg=2. Lo cual implica que la salida del bloque

g, está formado por una variable. Una de las columnas de la matriz de h está asociada a g=0, la

otra a g=1. Corresponde a la descomposición de Ashenhurst.

El número de columnas debe ser una potencia de dos, si cg=4, entonces el bloque g tiene dos

salidas, que podemos denominar g1 y g0, las que serían las variables, cuyos mintérminos

identificarían a las columnas.

Si cg=2m, entonces g tiene m salidas. Que podemos denominar: g0, g1, …, gm. Este es el caso

general de la descomposición disjunta de Curtis.

Si c=cg, es decir si A y g tienen el mismo número de columnas, no se reduce el número de

entradas a la función h, será el mismo número de entradas de la función f. Entonces para que la

descomposición sea de interés debe tenerse: c > cg.

Entonces la función f, puede descomponerse en las funciones g y h:

1 2( , ,..., ) ( , ) ( ( ), )nf x x x f A L h g A L

si y solamente si se cumple la igualdad de:

0 0

( , ) ( ) ( , ) ( )i cgi c

i i

i i

f i L p A h g i L p g

Para el caso de cg=4, se tiene que cumplir:

1 0 1 0 1 0 1 0

0

( , ) ( ) (0, ) ' ' (1, ) ' (2, ) ' (3, )i c

i

i

f i L p A h L g g h L g g h L g g h L g g

Donde el lado izquierdo es conocido, y el objetivo es determinar las subfunciones: h, g1 y g0.

Debe notarse que h(i,L) y f(i,L) son solamente funciones de las variables libres.

Si c es mayor que cg, por ejemplo 8, ya que tiene que ser una potencia de dos, existirán 8

columnas en f y 4 columnas en h. Esto implica tres variables acotadas.

Entonces se requiere que a lo más f tenga 4 columnas diferentes, incluidas los valores de

columnas con puros ceros o puros unos; los valores de esas columnas serán los valores de las

columnas de h. Existen 4! formas de escoger las columnas de h, a partir de las columnas

diferentes de f.

Si f tiene 3 columnas diferentes, una de las columnas de h puede escogerse con solamente

valores superfluos.



Si f tiene sólo dos columnas diferentes, entonces debe escogerse una función h que tenga dos

columnas, y sólo basta una función g, es el caso de la descomposición Ashenhurst.

Si f tiene 5 columnas diferentes, no es posible satisfacer la igualdad, en este caso es preciso que

h tenga también 8 columnas, de las cuales 3 pueden ser fijadas en condiciones superfluas. Sin

embargo en este caso se requieren 3 funciones g, lo cual implica que h tendrá igual número de

entradas que la función f. Razón por la cual este caso no es de interés en descomposición.

Una vez seleccionadas las columnas de f que representarán a las de h, esta función puede

determinarse. Además la determinación de las funciones g puede realizarse con las siguientes

cuatro ecuaciones:

0 1 0

( , ) (0, )

( ) ( ) ' 'i

i f i L h L

p A p g g g

1 1 0

( , ) (1, )

( ) ( ) 'i

i f i L h L

p A p g g g

2 1 0

( , ) (2, )

( ) ( ) 'i

i f i L h L

p A p g g g

3 1 0

( , ) (3, )

( ) ( )i

i f i L h L

p A p g g g

Las cuales permiten escribir las tablas de verdad de las funciones g1 y g0, en términos de las

variables acotadas, ya que los ( )ip A sólo dependen de las variables acotadas.

En la tabla de la Figura 8.20, se han agregado dos renglones que identifican la selección

realizada de las columnas de h, y los valores binarios correspondientes de las salidas g1 y g0.

g1g0 00 01 00 10 10 01 11 00

h(0,L) h(1,L) h(0,L) h(2,L) h(2,L) h(1,L) h(3,L) h(0,L)

A 0 1 2 3 4 5 6 7

L x4x5\x1x2x3 000 001 010 011 100 101 110 111

0 00 1 1 1 1

1 01 1 1 1

2 10 1 1

3 11 1 1 1 1 1

f(A, L)=h(g(A),L)

Figura 8.24. Descomposición serial disjunta.

La selección realizada para las columnas de h puede anotarse:

4 5(0, ) (0, ) (2, ) (7, ) ' 'h L f L f L f L x x

4 5 4 5 4(1, ) (1, ) (5, ) 'h L f L f L x x x x x

4 5 4 5 5(2, ) (3, ) (4, ) 'h L f L f L x x x x x



4 5 4 5 4 5 4 5(3, ) (6, ) ' ' ' 'h L f L x x x x x x x x

Las que reemplazadas en la siguiente ecuación, nos permiten obtener h.

0

( , ) ( , ) ( )i cg

i

i

h g L h g i L p g

4 5 1 0 4 1 0 5 1 0 4 5 1 0( , ) ' ' ' ' ' ' ( ' )h g L x x g g x g g x g g x x g g

Para determinar las funciones g1 y g0, realizamos las sumatorias:

1 0 0 2 7 1 2 3 1 2 3 1 2 3

0,2,7

' ' ( ) ( ) ( ) ( ) ' ' ' ' 'i

i

g g p A p A p A p A x x x x x x x x x

1 0 1 5 1 2 3 1 2 3

1,5

' ( ) ( ) ( ) ' ' 'i

i

g g p A p A p A x x x x x x

1 0 3 4 1 2 3 1 2 3

3,4

' ( ) ( ) ( ) ' ' 'i

i

g g p A p A p A x x x x x x

1 0 6 1 2 3

6

( ) ( ) 'i

i

g g p A p A x x x

Si se suman las dos últimas ecuaciones, se tiene:

1 1 2 3 1 2 3 1 2 3 1 2 3 1 3' ' ' ' ' 'g x x x x x x x x x x x x x x

Si se suman la segunda y la cuarta, se obtiene:

0 1 2 3 1 2 3 1 2 3 2 3 1 2 3' ' ' ' ' 'g x x x x x x x x x x x x x x

La determinación de las funciones también puede obtenerse empleando la información de la

matriz de descomposición. Eliminando las columnas duplicadas de la Figura 8.24. y los

renglones asociados a las variables acotadas, resulta la Figura 8.25; donde se puede determinar

la función sucesora h.

h(0,L) h(1,L) h(2,L) h(3,L)

L x4x5\ g1g0 00 01 10 11

0 00 1 1

1 01 1 1

2 10 1

3 11 1 1 1

h(g,L)

Figura 8.25. Función h(g,L).



Si en la Figura 8.24, se eliminan los renglones asociados a las variables libres, y sólo se dejan

los renglones asociados a las tablas de verdad de las funciones g1 y g0, se obtiene la Figura

8.26.

g1g0 00 01 00 10 10 01 11 00

x1x2x3 000 001 010 011 100 101 110 111

Figura 8.26. Tablas de verdad de las funciones g1 y g0.

Funciones que pueden ser minimizadas, redibujando las tablas de verdad como mapas de

Karnaugh.

x4x5\ g1g0 00 01 11 10

00 1 1

01 1 1

11 1 1 1

10 1

h(g, x4, x5)

Figura 8.27. Mapa de Karnaugh de h.

1 0 4 5 1 5 1 0 4 1 0 4 1 0 4 5( , , , ) ' ' ' ' ' 'h g g x x g x g g x g g x g g x x

Para las funciones antecesoras:

x3\ x1 x2 00 01 11 10

0 00 00 11 10

1 01 10 00 01

g1g0

Figura 8.28. Mapa de Karnaugh de g1 y g0.

Resultan:

1 1 2 3 1 3 1 2 3( , , ) ' 'g x x x x x x x x

0 1 2 3 2 3 1 2 3( , , ) ' 'g x x x x x x x x

8.4. Descomposición de funciones incompletamente especificadas.

Cuando la tabla de verdad tiene condiciones superfluas se dice que dos columnas i, j son

compatibles si cada elemento en la columna i es igual al correspondiente elemento de j, o si el

elemento en i o en j no está especificado.

Dicho de otra forma: Dos columnas, Cr y Cs, son compatibles, si no existe un renglón i, para el

cual los correspondientes elementos Cir y Cis sean diferentes, cuando ambos están

especificados.



La descomposición de estas funciones está gobernada por las mismas reglas anteriores, excepto

que existen varias combinaciones alternativas para mezclar las columnas compatibles. En estos

casos la solución puede no ser única.

Un conjunto de columnas para el cual cada par de columnas son compatibles se denomina clase

compatible. Las clases compatibles que no son subconjuntos de otras clases compatibles se

denominan clases de compatibilidad máxima.

Finalmente se selecciona un subconjunto de mínima cardinalidad de las clases máximas, tal que

cada columna esté al menos en una de clases de compatibilidad máxima que se empleen.

8.4.1. Ejemplo.

Veremos a través de un ejemplo la forma de compactar las columnas de la tabla de la función f

incompletamente especificada. Variables libres: (a,b), variables acotadas: (c,d,e).

ab/ cde 000 001 010 011 100 101 110 111

00 1 - 0 1 - 0 1 0

01 - - - - 1 1 - -

10 - 0 1 0 0 - 0 1

11 0 1 - - - - - -

C0 C1 C2 C3 C4 C5 C6 C7

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

Figura 8.29. Descomposición de función con condiciones superfluas.

Como ejemplo, los siguientes pares son incompatibles: (C0, C1), (C0, C2), (C0, C5), (C0, C7).

Para formar las clases, es preciso disponer de los pares de columnas compatibles. En la

siguiente tabla de la Figura 8.30, en la primera columna se anotan los pares indicando los

índices de las columnas.

Para formar la segunda columna, se recorren los pares para detectar los tríos de columnas

compatibles entre sí. Por ejemplo se tienen los pares: (0,3), (0,4) y (3,4), entonces se forma el

trío de columnas compatibles entre sí: (0, 3, 4). En la Figura 8.30, no se muestran todos los

vínculos que permiten construir la segunda columna. Como se usan todos los pares al formar la

columna de tríos, no se tiene una clase máxima formada por dos columnas.

Luego de la columna de tríos se forma una clase compatible de cuatro columnas entre sí. De este

modo puede formarse la clase (0,3,4,6) ya que se tienen: (0,3,4), (0,3,6), (0,4,6) y (3,4,6). Se

procede de igual forma hasta que no se puedan generar clases con un número mayor de

columnas compatibles entre sí.

Nótese que en la tercera columna quedan dos clases con cuatro columnas compatibles entre sí, y

en la segunda quedan dos con tres columnas compatibles entre sí. Éstas son las clases de

compatibilidad máxima.



0,3

0,4

0,6

1,3

1,4

1,5

1,6

2,5

2,7

3,4

3,6

4,5

4,6

5,7

0,3,4

0,3,6

0,4,6

1,3,4

1,3,6

1,4,5

1,4,6

2,5,7

3,4,6

0,3,4,6

1,3,4,6

Figura 8.30. Formación de clases de compatibilidad máxima.

Ahora debe efectuarse una selección de las clases, de tal modo que cada una de las columnas

esté incluida en alguna de las clases seleccionadas. Por ejemplo, pueden escogerse las clases:

(0,3,4,6), (1,4,5), (2,5,7). Finalmente los elementos múltiples deben eliminarse, resultando las

siguientes clases: (0,3,4,6), (1,5), (2,7).

La mezcla de las columnas de cada clase, que en el caso del ejemplo son tres, se asocian a los

valores de las funciones seriales g1 y g0. Nótese que se agrega una columna con valores

superfluos, lo que permite un nivel adicional de minimización de la función: h(g1, g0, (a,b))

La codificación de las columnas influye en la minimización.

ab/ g1g0 00 01 10 11

00 1 0 0 -

01 1 1 - -

10 0 0 1 -

11 0 1 - -

C0,C3,C4,C6 C1,C5 C2,C7 -

h

Figura 8.31. Mezcla de columnas de clases compatibles.

Para la determinación de las funciones g, en términos de las variables acotadas, se tienen:



cde 000 001 010 011 100 101 110 111

g1g0 00 01 10 00 00 01 00 10

C0 C1 C2 C3 C4 C5 C6 C7

Figura 8.32. Tablas de las funciones predecesoras.

Resultan, luego de la minimización:

1 0 0 1

1

0

' ' '

' '

'

h a g g bg ag

g c de cde

g d e

a b

c d e

g

h f

Figura 8.33. Resultado de la descomposición.

8.5. Descomposiciones no disjuntas.

Cuando no se cumplen las condiciones para descomposiciones disjuntas, puede encontrarse

descomposiciones no disjuntas, agregando al conjunto acotado una de las variables libres.

Si A C son las variables acotadas y L C son las variables libres y C es no vacío se tiene

una descomposición no disjunta.

g A

F f

C

L

Figura 8.34. Descomposición no disjunta.

El uso de mapas con variables repetidas, permite generalizar el caso de las descomposiciones

disjuntas al tratamiento de las no disjuntas.

El mapa con variables repetidas es incompletamente especificado aunque la función original sea

completamente especificada. Cada variable repetida crea un mapa de una dimensión mayor en el

cual las nuevas celdas introducidas son condiciones superfluas.

8.5.1. Ejemplo.

La función f, de la Figura 8.35, no tiene descomposición disjunta de Curtis, no hay 4 columnas

diferentes; ni Ashenhurst, ya que no hay sólo 2. Puede verificarse que no existe



descomposiciones eligiendo los seis conjuntos libres posibles en este caso: ab, cd, ac, bd, ad,

bc.

Diseño en dos niveles: f = bcd+acd+a’c’d’+b’c’d’+a’b’d’ con 20 entradas.

00 01 11 10

00

01

11

10

1

0

0

1

1

0

1

0

0

0

1

0

1

0

1

0

15 11 7 3

14 10 6 2

13 9 5 1

12 8 4 0

CD

AB

f(A, B, C, D)

Figura 8.35. Descomposición no disjunta.

Si se introducen las variables C1 = C2 = C, aparecen numerosas condiciones superfluas, ya que

si C es la misma variable, no se pueden producir los casos en que C1 y C2 sean diferentes.

000 001 011 010

00

01

11

10

1

0

-

-

1

0

-

-

0

0

-

-

1

0

-

-

15 11 7 3

14 10 6 2

13 9 5 1

12 8 4 0

C2D

f(A, B, C, D)

100 101 111 110

-

-

0

1

-

-

1

0

-

-

1

0

-

-

1

0

C1AB

Figura 8.36. Mapa con variable C repetida.

a) Diseño mezclando columnas.

Eligiendo valores para las casillas superfluas, pueden tenerse los siguientes conjuntos de

columnas compatibles: (0,1,2,4) (3,5,6,7), se ha empleado el decimal equivalente para

identificar la columna. Puede notarse que las columnas 1 y 2 no son compatibles, ya que para el

renglón 0, una tiene valor uno y la otra valor cero.

Existen otras elecciones posibles de las condiciones superfluas, que permiten seleccionar otros

conjuntos de columnas compatibles.

Entonces mezclando las columnas compatibles, puede verse que existe la descomposición de

Ashenhurst no disjunta.



cd\g 0 1

00 1 0

01 0 0

11 0 1

10 1 0

h=d’g’+cdg

Figura 8.37. Ashenhurst no disjunta.

La determinación de la función g, puede obtenerse considerando que g será uno cuando las

variables acotadas CAB toman las combinaciones: 011, 101, 111, 110, con el mapa:

c\ab 00 01 11 10

0 1

1 1 1 1

g=ab + ac+ bc

Figura 8.38. Función predecesora g.

Evaluando el costo con compuertas elementales, resulta de 17 entradas y 5 niveles. Sin embargo

este cálculo no es relevante si las funciones g y h pueden implementarse en un bloque básico.

b) Diseño compactando renglones.

Eligiendo valores para las condiciones superfluas, pueden formarse dos renglones

complementarios

000 001 011 010

00

01

11

10

1

0

0

1

1

0

0

1

0

0

1

0

1

0

0

1

15 11 7 3

14 10 6 2

13 9 5 1

12 8 4 0

C2D

f(A, B, C, D)

100 101 111 110

1

-

0

1

0

-

1

0

0

-

1

0

0

-

1

0

C1AB

Figura 8.39. Formación de renglones compatibles.

La ecuación para la función sucesora, se obtiene con la ecuación del multiplexor gobernado por

las variables libres.

h= gc’d’+0c’d+ g’cd + gcd’

La cual puede ser minimizada:

h= cdg’+d’g



La función antecesora, resulta del mapa del primer renglón:

c\ab 00 01 11 10

0 1 1 1

1 1

g=a’b’ + a’c’+ b’c’

Figura 8.40. Mapa para obtener función g.

Que para fines de comparación, implementada con compuertas tradicionales, resulta de 17

entradas y 5 niveles

Factorizando con SIS, que emplea cálculo con cubos, se obtiene la red booleana:

g1 = ab, g2=a’+b’ h= d’g1’+cdg1+c’d’g2 con 16 entradas, 4 niveles

8.6. Descomposición paralela.

En caso de tener sistemas con múltiples salidas debe aplicarse la descomposición en paralelo.

En la descomposición paralela el conjunto de variables de salida f, es particionado en dos

subconjuntos fG y fH, y la función f en las funciones G y H correspondientes. De tal modo que

los conjuntos XG y XH, de variables de entrada a los bloques G y H respectivamente, contengan

menos variables que el conjunto X de variables de entrada a la función f.

X

f

XG XH

fG fH

Figura 8.41. Descomposición paralela.

Si los conjuntos XG y XH son disjuntos, se dice que la descomposición paralela es disjunta; si la

intersección es no vacía se dice que es no disjunta.

Se denomina descomposición balanceada al proceso de partir una función mediante

descomposición paralela o serial en cada fase del proceso de síntesis.

8.7. Síntesis multinivel

8.7.1. Redes lógicas booleanas.

La minimización como suma de productos es un proceso de síntesis lógica realizada en dos

niveles de compuertas. Estos diseños tienen mínimo retardo para la propagación de los cambios

entre las entradas y las salidas, pero a costa de compuertas con gran número de entradas.



Compuertas con muchas entradas requieren mayor superficie para ubicar los transistores dentro

del proceso de integración; por lo cual debido al compromiso área versus tiempo de retardo, los

diseños de sistemas complejos suelen tener más de dos niveles.

La estructura de dispositivos CPLD permite naturalmente la implementación de lógica en dos

niveles. La estructura interna de los dispositivos FPGA, basada en la interconexión de pequeñas

celdas estándares, está más orientada a la implementación de lógica multinivel.

Los sistemas computacionales de ayuda al diseño (CAD) que permiten la optimización de lógica

multinivel, modelan las ecuaciones mediante una red lógica booleana, que es una

generalización de un netlist o un esquemático basado en compuertas.

La Figura 8.42 muestra un esquemático simple, basado en compuertas.

B

C

x2

A

D

x1

Figura 8.42. Esquemático basado en compuertas.

La Figura 8.43 representa una red lógica booleana, en la cual las salidas de los bloques,

denominados vértices internos o nodos, son funciones booleanas. Es decir un netlist de

componentes conectadas, pero éstas pueden ser ahora funciones booleanas arbitrarias.

La estructura resultante es un grafo dirigido acíclico.

En un caso general puede suponerse que las entradas a la red, provienen de salidas de latchs o

flip-flops, que almacenan los valores de las variables; y que las salidas de la red son

almacenadas en registros.

B

C x2

A

D

x1

Figura 8.43. Red lógica booleana.

Los métodos de minimización están basados en transformaciones locales o globales de la red.

Las transformaciones locales apuntan a reducir el área y el tiempo de propagación asociados al

nodo o bien a mapear la función del nodo a determinada interconexión de celdas básicas. Las



transformaciones globales reestructuran la red, por ejemplo: uniendo nodos, o separando un

nodo en dos, o cambiando las conexiones entre nodos.

Si las funciones de cada nodo se representan en forma suma de productos, el costo de la red

puede calcularse como la suma de los literales de cada nodo.

No se dispone, por el momento, de herramientas que logren la optimización de sistemas

complejos multinivel; a cambio se dispone de operaciones que se realizan sobre la red,

intentando un cambio; en caso de disminuir el costo de la red, se acepta el cambio, en caso

contrario se intenta otra modificación, esto puede repetirse hasta que no se logren nuevas

reducciones del costo.

Se entiende por optimización multinivel al proceso de encontrar factores lógicos que sean

comunes, lo cual reduce el fan in pero aumenta el número de niveles. Luego debe mapearse

estas formas factorizadas en alguna de las formas que estén disponibles en una biblioteca.

8.7.2. Operaciones.

Eliminación de un nodo.

Se elimina un nodo interno mediante el reemplazo de la función que lo describe en todos los

nodos que éste alimenta. Se elimina un nodo de pequeño costo, el cual es absorbido por el

resto. También se denomina colapsamiento del nodo x. Esta operación disminuye el tiempo de

propagación de la red pero aumenta los costos de los nodos.

La Figura 8.44 muestra la eliminación del nodo con salida x.

S=x+C

x=A’+B

T=xD

C

D

A

B

S=A’+B+C

T=(A’+B)D

C

D

A

B

A

B

Figura 8.44. Eliminación nodo x.

Creación de un nodo.

Se agrega un nuevo vértice que contiene una subexpresión que es común a dos o más nodos;

luego la salida del nuevo nodo substituye el término común en los nodos.

Se disminuye el tamaño de algunos nodos, agregando un nodo factor; de este modo los nodos

resultantes son de costos menores.



S=(A+B)C

T=(A+B)D

C

D

A

B

A

B

S=xC

x=A+B

T=xD

C

D

A

B

Figura 8.45. Creación nodo x.

Esta operación también se denomina extracción, ya que obtiene un factor que es común a varias

funciones. Esta operación aumenta el tiempo de propagación de la red pero disminuye los costos

de los nodos.

Las siguientes son operaciones que se realizan sobre un nodo.

Descomposición.

Una función puede descomponerse en partes.

Por ejemplo la función que tiene asociado el nodo: f = abc+abd

Puede descomponerse en tres nodos: f, x e y, con las siguientes funciones para cada nodo:

f = xy x = ab y = c+d

Factorización.

Una función puede descomponerse en sus factores.

Por ejemplo la función que tiene asociado el nodo: f = ac + ad + bc + bd

Puede factorizarse según: f = (a+b)(c+d)

Encontrar métodos para obtener factores adecuados ha sido posible gracias al desarrollo de

nuevos conceptos teóricos: Para lograr disponer del operador división no se definen algunos

postulados del algebra de Boole, de este modo una expresión booleana se comporta como un

polinomio de números reales.

Específicamente no se definen: a+a’=1, aa’=0, aa=a, a+a=a, a+1=1, a+(b+c) =(a+b)(a+c).

Con esto podemos usar para expresiones las reglas algebraicas empleadas con reales. Nótese

que en este ambiente una variable y su complemento no tienen ninguna relación.

Simplificación.

Puede aplicarse un método de simplificación, del tipo minimización en forma de suma de

productos, a la función asociada a un nodo. Si no se eliminan variables se tiene una

minimización local; sin embargo si se elimina una o más variables, se dice que la simplificación

es global ya que cambia la red.

SIS

La forma de efectuar minimizaciones multinivel es a través de herramientas CAD de ayuda al

diseño. Éstas suelen venir incorporadas en el software provisto por los fabricantes de

dispositivos programables, o bien se producen en forma comercial. Por otra parte se puede usar

software libre como sis, que fue desarrollado por la Universidad de Berkeley. Ver Apéndice 6,



sobre uso de sis. Más recientemente está en desarrollo el sistema abc, también en la Universidad

de Berkeley, éste último acepta entradas en verilog estructural.

8.7.3. Formas factorizadas.

Una expresión booleana puede representarse mediante una forma factorizada.

Estas formas podían describirse según:

Es un producto de sumas de productos o una suma de producto de sumas.

Las siguientes son formas factorizadas: x, y’, abc’, a+b’c, ((a’+b)cd+e)(a+b’)+e’

Pero: (a+b)’c no es una forma factorizada ya que la complementación de una expresión no

está permitida, salvo sobre literales.

Puede definirse recursivamente según:

Una forma factorizada es un producto o una suma, donde:

El producto es un literal simple o un producto de formas factorizadas.

La suma es un literal simple o una suma de formas factorizadas.

Las formas factorizadas no son únicas. La siguientes tres formas son equivalentes:

ab+c(a+b) bc+a(b+c) ac+b(a+c)

Una forma suma de productos es una forma factorizada pero seguramente no es una buena

factorización considerando el costo espacial.

La expresión en forma de suma de productos: f = ae+af+bce+bcf+bde+bdf tiene un costo de

16 literales. La forma factorizada equivalente f = (a+b(c+d))(e+f), tiene un costo de 6 literales.

Esto implica que una forma “bien” factorizada es bastante más compacta que la cobertura

mínima formada por la suma de implicantes primos.

La forma suma de productos de la función de 10 variables, func1 tiene 42 literales, con 54

entradas en total, en dos niveles. El or final de esta implementación tiene 12 entradas.

func1=ac+ade+adfg+adfh+adfi+adfj+bc+bde+bdfg+ bdfh+bdfi+bdfj

Esto considerando que func1 está minimizada.

La forma factorizada equivalente func2, tiene 10 literales y 6 niveles. Con 16 entradas en total.

En este diseño todas las compuertas son de dos entradas, salvo una que es de 4.

func2=(a+b)(c+d(e+f(g+h+i+j)))

A través de los ejemplos anteriores se comprueba que las formas factorizadas son útiles en la

reducción del costo de una red multinivel.

En diseños de funciones integradas CMOS, las redes de pull-up y pull down corresponden a la

forma factorizada de la función.



Problemas resueltos.

P8.1. Descomposición.

Se tiene la siguiente función de cuatro variables.

a b c d f

0 0 0 0 0

0 0 0 1 1

0 0 1 0 1

0 0 1 1 0

0 1 0 0 1

0 1 0 1 0

0 1 1 0 0

0 1 1 1 1

1 0 0 0 1

1 0 0 1 1

1 0 1 0 1

1 0 1 1 1

1 1 0 0 0

1 1 0 1 0

1 1 1 0 0

1 1 1 1 0

Figura P8.1. Función de cuatro variables.

Se efectúa la descomposición, empleando como variables libres: a, b. LO primero que se realiza

es determinar la matriz de descomposición.

ab\cd 00 01 10 11

00 0 1 1 0

01 1 0 0 1

10 1 1 1 1

11 0 0 0 0

Figura P8.2. Matriz de descomposición.

Luego se buscan columnas equivalentes. Se encuentran dos columnas diferentes, lo que implica

que la red tiene descomposición de Ashenhurst.

Luego se escogen las columnas de h.



ab\g 0 1

00 0 1

01 1 0

10 1 1

11 0 0

h=ab’+b’g+a’bg’

Figura P8.3. Función sucesora.

Finalmente se determina la función g.

a\b 0 1

0 1 0

1 1 0

g=b’

Figura P8.4. Función predecesora.

La solución alternativa es compactando los renglones. El primer y segundo renglón son

complementarios, los otros dos renglones son constantes, lo cual implica que existe

descomposición de Ashenhurst:

' ' ' ' 1 ' 0

' '

f ga b g a b ab ab

g c d cd

P8.2. Factorización.

La función de 5 variables: f AC AD BE BF es de la forma suma de productos, y no

puede ser reducida por simplificación. Su implementación tiene un costo total de:

2+2+2+2+4 = 12 entradas, y 8 literales.

Se desea obtener una forma factorizada implementada mediante NANDs,

Sin embargo, mediante factorización puede escribirse: ( ) ( )f A C D B E F , la cual

requiere 2+2+2+2+2 = 10 entradas, y 6 literales según puede apreciarse en la Figura P8.5. Esta

expresión no es suma de productos pura; pero su implementación es directa, empleando AND y

OR e implica tres niveles. C

D

E

F

A

B

f

Figura P8.5. Forma factorizada en tres niveles.



Las formas factorizadas también pueden mapearse con compuertas nand.

El teorema de De Morgan indica que la siguiente compuerta es equivalente a un NAND.

Figura P8.6. Nand según De Morgan.

Se complementan las variables de entrada y se insertan burbujas inversoras en las entradas de

las compuertas or de primer nivel. Luego se insertan dobles burbujas inversoras a la salida de

los ands del segundo nivel, formando un nand y desplazando la burbuja hacia las entradas de los

or del tercer nivel. Resulta la red de la Figura P8.7.

C’

D

E’

F’

A

B

f

Figura P8.7. Diseño en base a NANDs

Luego se representan todas las compuertas, usando el símbolo de los NAND. El diseño se logra

empleando 5 compuertas nand y con 10 entradas. Debe notarse que este método asume que se

dispone de las entradas y sus complementos.

Ejercicios propuestos.

E8.1.

Efectuar la descomposición, si es posible, del problema P8.1, para los siguientes juegos de

variables libres: (a,c), (a,d), (b,c), (b,d) y (c,d). Comparando los resultados, y seleccionando la

mejor descomposición.

E8.2.

Dada la forma factorizada: (a + b + c)(d + e) f+g expandirla a suma de productos.

Comparar las formas respecto del: número de niveles, de entradas y de literales.

Efectuar el diseño empleando solamente compuertas nand.



Referencias.

R. L. Ashenhurst, “The decomposition of switching functions” , Bell Laboratories, Tech. Rep.

BL-1(11), 1952.

H. Allen Curtis, “Generalized Tree Circuit”, Lewis Research Center. NASA. 1961.

Marek A. Perkowski, Tadeusz Luba, et al, “Unified approach to functional decompositions of

switching functions”, Portland State University, 1995.



Índice general.

CAPÍTULO 8 .............................................................................................................................................. 1

DESCOMPOSICIÓN ................................................................................................................................. 1

8.1. DESCOMPOSICIÓN TRIVIAL. TEOREMA DE SHANNON. ......................................................................... 2 8.1.1. Extracción de una variable. ....................................................................................................... 2 8.1.2. Extracción de dos variables. ...................................................................................................... 4

8.2. DESCOMPOSICIÓN DE ASHENHURST. .................................................................................................. 5 8.2.1. Compactando las columnas. ...................................................................................................... 6 8.2.2. Redundancia de renglones. ........................................................................................................ 8 8.2.3. Complejidad de la descomposición. ........................................................................................... 9

8.3. DESCOMPOSICIÓN DE CURTIS. .......................................................................................................... 10 8.3.1. Descomposición de Curtis, con dos funciones auxiliares. ....................................................... 11 8.3.2. Descomposición de Curtis, con m funciones auxiliares. .......................................................... 12 8.3.3. Fundamentos. ........................................................................................................................... 13

8.4. DESCOMPOSICIÓN DE FUNCIONES INCOMPLETAMENTE ESPECIFICADAS. ........................................... 19 8.4.1. Ejemplo. ................................................................................................................................... 20

8.5. DESCOMPOSICIONES NO DISJUNTAS. ................................................................................................. 22 8.5.1. Ejemplo. ................................................................................................................................... 22

a) Diseño mezclando columnas. ..................................................................................................................... 23 b) Diseño compactando renglones. ................................................................................................................ 24

8.6. DESCOMPOSICIÓN PARALELA. .......................................................................................................... 25 8.7. SÍNTESIS MULTINIVEL....................................................................................................................... 25

8.7.1. Redes lógicas booleanas. ......................................................................................................... 25 8.7.2. Operaciones. ............................................................................................................................ 27

Eliminación de un nodo. ................................................................................................................................ 27 Creación de un nodo. ..................................................................................................................................... 27 Descomposición. ............................................................................................................................................ 28 Factorización. ................................................................................................................................................. 28 Simplificación. ............................................................................................................................................... 28 SIS.................................................................................................................................................................. 28

8.7.3. Formas factorizadas. ............................................................................................................... 29 PROBLEMAS RESUELTOS. ........................................................................................................................ 30

P8.1. Descomposición. ....................................................................................................................... 30 P8.2. Factorización. ........................................................................................................................... 31

EJERCICIOS PROPUESTOS. ........................................................................................................................ 32 E8.1. ................................................................................................................................................... 32 E8.2. ................................................................................................................................................... 32

REFERENCIAS. ......................................................................................................................................... 33 ÍNDICE GENERAL. .................................................................................................................................... 34 ÍNDICE DE FIGURAS ................................................................................................................................. 35



Índice de figuras

Figura 8.1. Descomposición paralela y serial. ............................................................................... 1 Figura 8.2 Función de n variables. ................................................................................................ 2 Figura 8.3 Descomposición trivial. ............................................................................................... 3 Figura 8.4 Implementación con multiplexor. ................................................................................ 3 Figura 8.5. Tabla de verdad de una función de 4 variables. .......................................................... 3 Figura 8.6 Mapa de g0. .................................................................................................................. 4 Figura 8.7 Mapa de g1. .................................................................................................................. 4 Figura 8.8. Descomposición en 4 subfunciones. ........................................................................... 4 Figura 8.9. Multiplexor de 4 vías. ................................................................................................. 5 Figura 8.10. Tabla de verdad de una función de 5 variables. ........................................................ 5 Figura 8.11. Descomposición de Ashenhurst. ............................................................................... 6 Figura 8.12. Matriz de descomposición con dos columnas con valores diferentes. ...................... 6 Figura 8.13. Tabla de verdad de h(g,Xa). ...................................................................................... 7 Figura 8.14. Tabla de verdad de g(Xa). ......................................................................................... 7 Figura 8.15. Multiplexor de m entradas, controlado por variables libres. ..................................... 8 Figura 8.16. La función h es el multiplexor más red combinacional. ........................................... 9 Figura 8.17. Partición {2, 3, 4}. .................................................................................................. 10 Figura 8.18. Descomposición disjunta de Curtis. ........................................................................ 11 Figura 8.19. Descomposición disjunta de Curtis. ........................................................................ 12 Figura 8.20. Matriz de descomposición. ..................................................................................... 13 Figura 8.21. Expansión por columnas. ........................................................................................ 14 Figura 8.22. Expansión por renglones. ........................................................................................ 15 Figura 8.23. Descomposición serial disjunta. .............................................................................. 15 Figura 8.24. Descomposición serial disjunta. .............................................................................. 17 Figura 8.25. Función h(g,L)......................................................................................................... 18 Figura 8.26. Tablas de verdad de las funciones g1 y g0. ............................................................. 19 Figura 8.27. Mapa de Karnaugh de h. ......................................................................................... 19 Figura 8.28. Mapa de Karnaugh de g1 y g0. ............................................................................... 19 Figura 8.29. Descomposición de función con condiciones superfluas. ....................................... 20 Figura 8.30. Formación de clases de compatibilidad máxima. ................................................... 21 Figura 8.31. Mezcla de columnas de clases compatibles. ........................................................... 21 Figura 8.32. Tablas de las funciones predecesoras. ..................................................................... 22 Figura 8.33. Resultado de la descomposición. ............................................................................ 22 Figura 8.34. Descomposición no disjunta. .................................................................................. 22 Figura 8.35. Descomposición no disjunta. .................................................................................. 23 Figura 8.36. Mapa con variable C repetida. ................................................................................ 23 Figura 8.37. Ashenhurst no disjunta. ........................................................................................... 24 Figura 8.38. Función predecesora g. ........................................................................................... 24 Figura 8.39. Formación de renglones compatibles. ..................................................................... 24 Figura 8.40. Mapa para obtener función g. ................................................................................. 25 Figura 8.41. Descomposición paralela. ....................................................................................... 25 Figura 8.42. Esquemático basado en compuertas. ...................................................................... 26 Figura 8.43. Red lógica booleana. .............................................................................................. 26



Figura 8.44. Eliminación nodo x. ............................................................................................... 27 Figura 8.45. Creación nodo x. .................................................................................................... 28 Figura P8.1. Función de cuatro variables. .................................................................................. 30 Figura P8.2. Matriz de descomposición. .................................................................................... 30 Figura P8.3. Función sucesora. ................................................................................................... 31 Figura P8.4. Función predecesora. ............................................................................................. 31 Figura P8.5. Forma factorizada en tres niveles............................................................................ 31 Figura P8.6. Nand según De Morgan. ......................................................................................... 32 Figura P8.7. Diseño en base a NANDs ....................................................................................... 32

cap. 8. descomposición - departamento de electrónicalsb/elo211/clases/c08.pdf · si se escribe la...

Documents