Tema 2 ´ Y REPRESENTACION TRATAMIENTO DE LOS SISTEMAS DIGITALES 2.1.

´ ALGEBRA DE BOOLE

En el dise˜ no de los sistemas digitales se hace un uso extensivo de la teor´ıa l´ogica. Es preciso pues conocer detalladamente las propiedades matem´aticas de las funciones l´ogicas. ´ Estas se incluyen en la teor´ıa matem´atica de las Algebras de Boole. ´ Definici´ on 2.1 Un ALGEBRA DE BOOLE es un conjunto A = {a, b, c, ...} que verifica los siguientes postulados: 1. Existen dos operaciones binarias internas (+ y ·) definidas sobre el conjunto, es decir, el resultado de estas dos operaciones se encontrar´a siempre dentro del conjunto. 2. Estas operaciones son conmutativas: a + b = b + a y ab = ba 3. Ambas son distributivas una con respecto a la otra: · distributiva respecto a +: a(b + c) = ab + ac + distributiva respecto a · : a + bc = (a + b)(a + c) (Esta u ´ltima propiedad no la verifican los n´ umeros reales) 4. Existen elementos neutros para ambas operaciones, 0 para + y 1 para ·: a + 0 = a y a·1=a 5. Todo elemento del ´algebra tiene su complementario. Se denota por a y ha de verificar las dos condiciones siguientes: a + a = 1 y aa = 0. 17

´ Y TRATAMIENTO DE LOS SISTEMAS DIGITALES 18TEMA 2. REPRESENTACION ´ El Algebra de Boole m´as sencilla es aquella formada por los elementos {0,1} con las operaciones AND y OR definidas en el primer tema. ´ Una propiedad importante de un Algebra de Boole es el principio de Dualidad. ´ Este principio establece que las expresiones algebraicas deducidas a partir de un Algebra de Boole permanecen v´alidas si se intercambian los operadores (+ por ·) y los elementos neutros (0 por 1). ´ Otras propiedades importantes de un Algebra de Boole son las siguientes: 1. Asociativa: a + b + c = (a + b) + c = a + (b + c) y abc = (ab)c = a(bc) 2. Idempotencia: a + a = a y aa = a 3. Absorci´on del neutro: a + 1 = 1 y a · 0 = 0 4. Involuci´on: (a) = a 5. Absorci´on: a + ab = a 6. a + ab = a + b 7. Leyes de De Morgan: a + b = ab a + b + ··· + n = ab···n

ab = a + b ab · · · n = a + b + · · · + n

Todas estas propiedades pueden demostrarse directamente a partir de los postulados ´ del Algreba de Boole. Como ejemplo vamos a verificar dos de ellas, quedando las dem´as como ejercicios para los alumnos: Propiedad 2: a + a = a a+a = = = = =

(a + a) · 1 (a + a)(a + a) a + aa a+0 a

Elemento neutro 1 Complementario Distributiva Complementario Elemento neutro 0

Propiedad 6: a + ab = a + b a + ab = (a + a)(a + b) Distributiva = 1 · (a + b) Complementario = a+b Elemento neutro 1

´ 2.1. ALGEBRA DE BOOLE

19

b

a

b

c

a

c

a

a(b+c)=ab+ac

a b

c

a

a

b

c

a+bc=(a+b)(a+c)

a a a

b

a+ab=a

a a

a

a

a 1=a

a+0=a

a a

a+1=1

a 0=0

a a a

a+a=a

a

a

a

a a=a

´ Figura 2.1: Interpretaci´on f´ısica de algunas propiedades del Algebra de Boole.

´ Y TRATAMIENTO DE LOS SISTEMAS DIGITALES 20TEMA 2. REPRESENTACION a

b

c

f

Figura 2.2: Implementaci´on de la funci´on f del ejemplo

2.2.

FUNCIONES DE BOOLE

´ Una funci´on f de n variables sobre un Algebra de Boole A es una aplicaci´on n

z

}|

{

f : A × A × · · · × A −→ A Si A = {0, 1} son 2n las posibles combinaciones de entrada (xn−1 , · · · , x1 , x0 ), donde xi ∈ {0, 1}. ´ Una Funci´on de Boole puede definirse mediante expresiones del Algebra de Boole o bien dando su Tabla de Verdad (tabla de valores). Ejemplo: f (a, b, c) = a + abc

f (0, 0, 0) = 1 + 1 · 0 · 1 = 1 f (0, 0, 1) = 1 + 1 · 0 · 0 = 1 f (0, 1, 0) = 1 + 1 · 1 · 1 = 1 f (0, 1, 1) = 1 + 1 · 1 · 0 = 1 f (1, 0, 0) = 0 + 0 · 0 · 1 = 0 f (1, 0, 1) = 0 + 0 · 0 · 0 = 0 f (1, 1, 0) = 0 + 0 · 1 · 1 = 0 f (1, 1, 1) = 0 + 0 · 1 · 0 = 0

a 0 0 0 0 1 1 1 1

b 0 0 1 1 0 0 1 1

c f 0 1 1 1 0 1 1 1 0 0 1 0 0 0 1 0

Dos funciones se dicen iguales si sus Tablas de Verdad son iguales. Por ejemplo, la funci´on anterior f es igual a la siguiente funci´on f1 (a, b, c) = a. A esta conclusi´on se ´ podr´ıa haber llegado simplificando f mediante las propiedades del Algebra de Boole: f (a, b, c) = a + abc = a(1 + bc) = a

´ ´ DE BOOLE 2.3. EXPRESIONES CANONICAS DE UNA FUNCION

21

Funciones de Boole son tambi´en las funciones AND y OR, que para tres variables tienen la siguiente Tabla de Verdad: a 0 0 0 0 1 1 1 1

b 0 0 1 1 0 0 1 1

c 0 1 0 1 0 1 0 1

abc a + b + c 0 0 0 1 0 1 0 1 0 1 0 1 0 1 1 1

En general la funci´on AND de n variables es 1 cuando todas las variables toman el valor 1. La funci´on OR de n variables es 1 cuando alguna de las n variables es 1.

2.3.

´ EXPRESIONES CANONICAS DE UNA FUN´ DE BOOLE CION

En primer lugar vamos a definir dos conceptos muy importantes: Definici´ on 2.2 Para funciones de n variables, llamamos minterm a un t´ermino producto que contiene cada una de las n variables, o bien negadas o bien sin negar, sin repetirse ninguna. Ejemplo: Para funciones de tres variables ser´ıan minterms: abc, abc, abc. Y no ser´ıan minterms: ab, aabc. Los minterms se denotan de forma simplificada tomando un 1 por cada variable sin negar. Los posibles minterms para funciones de 3 variables son los siguientes: Minterm Variables abc 000 abc 001 abc 010 abc 011 abc 100 abc 101 abc 110 abc 111

Notaci´on 0 1 2 3 4 5 6 7

´ Y TRATAMIENTO DE LOS SISTEMAS DIGITALES 22TEMA 2. REPRESENTACION Definici´ on 2.3 Para funciones de n variables, llamamos maxterm a un t´ermino suma que contiene cada una de las n variables, o bien negadas o bien sin negar, sin repetirse ninguna. Ejemplo: Para funciones de tres variables ser´ıan maxterms: a + b + c, a + b + c, a + b + c. Y no ser´ıan maxterms: a + b, a + a + b + c. Los maxterms se denotan de forma simplificada tomando un 0 por cada variable sin negar. Los posibles maxterms para funciones de 3 variables son los siguientes: Maxterm Variables a+b+c 111 a+b+c 110 a+b+c 101 a+b+c 100 011 a+b+c a+b+c 010 001 a+b+c a+b+c 000

Notaci´on 7 6 5 4 3 2 1 0

Vamos a enunciar un teorema muy importante relacionado con los maxterms y minterms: Teorema 2.1 (Teorema de expansi´ on de Shannon) Cualquier funci´on binaria puede expresarse en forma de suma de minterms o en forma de producto de maxterms. Estas expresiones, que son u ´nicas, reciben el nombre de representaciones can´ onicas de la funci´ on. Demostraci´ on: Queremos expresar una funci´on cualquiera f (xn , · · · , x1 ) en forma de suma de minterms. Podemos poner la funci´on de la siguiente forma: f (xn , · · · , x1 ) = x1 f (xn , · · · , 0) + x1 f (xn , · · · , 1) Esta expresi´on se verifica para los dos valores posibles de x1 . Si x1 = 0 quedar´a: f (xn , · · · , x1 ) = 1 · f (xn , · · · , 0) + 0 · f (xn , · · · , 1), y si x1 = 1 tendremos: f (xn , · · · , x1 ) = 0 · f (xn , · · · , 0) + 1 · f (xn , · · · , 1). Repitiendo el proceso para x2 : f (xn , · · · , x2 , x1 ) = x2 x1 f (xn , · · · , 0, 0) + x2 x1 f (xn , · · · , 0, 1) + x2 x1 f (xn , · · · , 1, 0) + x2 x1 f (xn , · · · , 1, 1)

´ ´ DE BOOLE 2.3. EXPRESIONES CANONICAS DE UNA FUNCION

23

Y repitiendo el proceso para las n variables: f (xn , · · · , x2 , x1 ) = + + +

xn · · · x2 x1 f (0, · · · , 0, 0) + xn · · · x2 x1 f (0, · · · , 0, 1) xn · · · x2 x1 f (0, · · · , 1, 0) + xn · · · x2 x1 f (0, · · · , 1, 1) · · · + xn · · · x2 x1 f (1, · · · , 0, 0) + xn · · · x2 x1 f (1, · · · , 0, 1) xn · · · x2 x1 f (1, · · · , 1, 0) + xn · · · x2 x1 f (1, · · · , 1, 1)

Por tanto, en la expresi´on de la funci´on van a aparecer aquellos minterms que representan combinaciones de entradas para las cuales la funci´on vale 1, los dem´as desaparecen. De forma similar se har´ıa la demostraci´on para expresar una funci´on en forma de producto de maxterms. En este caso van aparecer aquellos maxterms que representan combinaciones de entrada para los cuales la funci´on vale 0, los dem´as maxterms desaparecen. Conclusi´ on: El Teorema de expansi´on de Shannon demuestra que existe una relaci´on sencilla entre la Tabla de Verdad de una funci´on de Boole y su representaci´on can´onica: la funci´on presentar´a un minterm para las combinaciones de entradas en las cuales la funci´on vale 1 y presentar´a un maxterm para las combinaciones de entradas en las cuales la funci´on es 0. Ejemplo: vamos a expresar en forma de suma de minterms y en forma de producto de maxterms la siguiente funci´on f :

0 1 2 3 4 5 6 7

a 0 0 0 0 1 1 1 1

b 0 0 1 1 0 0 1 1

c 0 1 0 1 0 1 0 1

f 0 0 1 0 0 1 0 1

Minterm Maxterm a+b+c a+b+c abc a+b+c a+b+c abc a+b+c abc

Donde hemos a˜ nadido a la Tabla de Verdad de la funci´on los minterms que corresponden a las combinaciones de entradas para las cuales la funci´on vale 1 y los maxterms que corresponden a las combinaciones de entradas para las cuales la funci´on vale 0. As´ı tenemos las siguientes representaciones can´onicas (en la notaci´on simplificada vamos a indicar los minterms con una “m” y los maxterms con “M ”): f (a, b, c) =

X

m(2, 5, 7) = abc + abc + abc

f (a, b, c) =

Y

M (0, 1, 3, 4, 6) = (a + b + c)(a + b + c)(a + b + c)(a + b + c)(a + b + c)

Este desarrollo se generaliza sin dificultad para funciones de cualquier n´ umero de variables.

´ Y TRATAMIENTO DE LOS SISTEMAS DIGITALES 24TEMA 2. REPRESENTACION Definici´ on 2.4 Aquellas combinaciones de entradas para las cuales no nos interesa el valor que pueda tomar la salida se llaman indiferencias y se dice que las funciones que incluyen indiferencias est´an incompletamente especificadas. Esto ocurre en algunas ocasiones cuando el circuito que se dise˜ na forma parte de un sistema mayor en el que ciertas entradas se producen s´olo en circunstancias tales que la salida del circuito no influir´a en el sistema general. Siempre que la salida no tenga ning´ un efecto, es evidente que no importa si la salida es un 0 o´ un 1. Otra posibilidad es que ciertas combinaciones de entrada no ocurran jam´as debido a varias resctricciones externas. El circuito responder´a de alguna forma a cualquier entrada, pero como esas entradas no se producir´an nunca no importa si el circuito final responde con una salida de 0 ´o 1. Las indiferencias se indican en la tabla de verdad anotando un “−” como valor funcional, en vez de un 0 ´o un 1. No es un s´ımbolo est´andar y tambi´en son utilizados otros como “∅”, “d” y “X”. Supongamos por ejemplo, que queremos construir un sistema que produzca como salida el cuadrado de los n´ umeros del 0 al 4. Necesitaremos tres bits como entradas para represetar del 0 al 4 y cinco bits de salida para representar el mayor valor que es 42 = 16. La tabla de verdad de este sistema ser´ıa la siguiente: a 0 0 0 0 1 1 1 1

b 0 0 1 1 0 0 1 1

f4 0 0 0 0 1 − − −

c 0 1 0 1 0 1 0 1

f3 0 0 0 1 0 − − −

f2 0 0 1 0 0 − − −

f1 0 0 0 0 0 − − −

f0 0 1 0 1 0 − − −

Las representaciones can´onicas para estas funciones ser´ıan, en notaci´on simplificada (n´otese que en este caso las indiferencias son indicadas con una “d” o “D” como un t´ermino a parte de los minterms o maxterms): f4 (a, b, c) =

X

m(4) +

X

f3 (a, b, c) =

X

d(5, 6, 7)

m(3) +

X

f2 (a, b, c) =

X

d(5, 6, 7)

m(2) +

X

f1 (a, b, c) =

X

d(5, 6, 7)

d(5, 6, 7)

f0 (a, b, c) =

X

m(1, 3) +

X

d(5, 6, 7)

o bien, f4 (a, b, c) =

Y

M (0, 1, 2, 3)

Y

D(5, 6, 7)

´ DE FUNCIONES 2.4. MINIMIZACION f3 (a, b, c) =

Y

f2 (a, b, c) =

Y

f1 (a, b, c) =

Y

f0 (a, b, c) =

Y

25

M (0, 1, 2, 4)

Y

D(5, 6, 7)

M (0, 1, 3, 4)

Y

D(5, 6, 7)

M (0, 1, 2, 3, 4) M (0, 2, 4)

Y

Y

D(5, 6, 7)

D(5, 6, 7)

Una indiferencia puede ser considerada como salida 0 ´o 1 seg´ un convenga. Por ejemplo, en la funci´on f0 , podemos considerar f0 (1, 0, 1) = 1, f0 (1, 1, 0) = 0 y f0 (1, 1, 1) = 1, entonces desarrollando la funci´on en forma de suma de minterms: f0 (a, b, c) =

X

m(1, 3, 5, 7) = abc + abc + abc + abc = ac(b + b) + ac(b + b) = c(a + a) = c

Con este ejemplo podemos ver que las indiferencias van a ser muy u ´tiles a la hora de simplificar las expresiones algebraicas de una funci´on.

2.4.

´ DE FUNCIONES MINIMIZACION

Minimizar una funci´on es obtener la expresi´on m´as simplificada posible para dicha funci´on. En general, la funci´on minimizada no es u ´nica. Una expresi´on de una funci´on en forma de suma de productos ser´a m´ınima si: No existe otra expresi´on de la funci´on con menor n´ umero de t´erminos producto. Cualquier otra expresi´on con igual n´ umero de t´erminos producto tendr´a m´as variables dentro de los productos. Si la expresi´on es un producto de t´erminos suma ser´a m´ınima si cumple las condiciones anteriores cambiando la palabra producto por suma. Vamos a ver ahora una serie de conceptos que nos ayudar´an a obtener las expresiones m´ınimas de las funciones. Definici´ on 2.5 Dos minterms (maxterms) constituyen un implicante de primer orden si la expresi´on de uno de ellos puede obtenerse a partir de la del otro negando una sola variable. La suma de los minterms que componen un implicante es simplificable (lo mismo que el producto de los maxterms). Ejemplo: Para funciones de tres variables: a bc y abc. Suma: a bc + abc = ac(b + b) = ac (implicante ac). Definici´ on 2.6 Dos implicantes de primer orden constituyen un implicante de segundo orden si la expresi´on de uno de ellos puede obtenerse a partir del otro negando una sola variable.

´ Y TRATAMIENTO DE LOS SISTEMAS DIGITALES 26TEMA 2. REPRESENTACION Ejemplo: a bc y abc (implicante ac), a b c y abc (implicante a c). Suma: ac + a c = a(c + c) = a (implicante de segundo orden a). Definici´ on 2.7 Dos implicantes de segundo orden constituyen un implicante de tercer orden si la expresi´on de uno de ellos puede obtenerse a partir del otro negando una variable. Ejemplo:a bc, abc, a b c y abc (implicante a), ab c, abc, abc y abc (implicante a). Suma: a + a = 1. Esto se generaliza sin dificultad para funciones de cualquier n´ umero de variables y para implicantes de cualquier orden, es decir, dos implicantes de orden n constituyen uno de orden n+1 si la expresi´on de uno de ellos se puede obtener a partir del otro negando una variable. Es conveniente notar que un implicante de primer orden simplifica una variable, uno de segundo dos, uno de tercero tres, etc. Tambi´en es importante recalcar que un implicante de orden n est´a compuesto por 2n minterms (maxterms), es decir, uno de primer orden est´a formado por dos minterms (maxterms), uno de segundo por cuatro, uno de tercero por ocho, etc.

2.4.1.

Mapas de Karnaugh

Un mapa de Karnaugh es un diagrama formado por cuadrados, cada uno de los cuales representa una de las posibles combinaciones de las variables de la funci´on. En cada cuadrado representaremos el valor que toma la funci´on para la combinaci´on de variables que le corresponde, y como hay una correspondencia directa uno a uno entre los cuadrados y las distintas combinaciones de entrada, el mapa de Karnaugh va a ser otra forma de especificar una funci´on (es un diagrama visual de la tabla de verdad). Los mapas de Karnaugh para funciones de 2, 3, 4 y 5 variables son los ilustrados en la figura 2.3. Hemos indicado el minterm (maxterm) que corresponder´ıa a cada casilla. Importante: el orden para los pares de variables es obligatoriamente (00, 01, 11, 10) y para un grupo de tres variables (000, 001, 011, 010, 110, 111, 101, 100). En el caso de querer obtener una expresi´on m´ınima como suma de t´erminos producto, en el mapa colocaremos los unos de la funci´on, adem´as de las indiferencias, omitiendo los ceros. Si lo que nos proponemos es calcular la expresi´on m´ınima como producto de t´erminos suma, entonces pondremos los ceros y las indiferencias, excluyendo los unos. El segundo paso en la minimizaci´on es localizar los implicantes de la funci´on en el mapa de Karnough. A continuaci´on mostramos unos ejemplos de implicantes obtenidos a partir de minterms, para funciones de distinto n´ umero de variables. Los implicantes deben estar formados por celdas adyacentes y pueden contener tanto unos como indiferencias (deben contener al menos un 1). Los implicantes de primer orden ocupan dos casillas adyacentes. La adyacencia de dos casillas puede ser horizontal o vertical, nunca diagonal.

´ DE FUNCIONES 2.4. MINIMIZACION

b a 0

0

1

0

1

1

2

3

27

cd 0 0 0 1 1 1 1 0 ab 00 0 1 3 2

bc a 00 01 11 10 0 0 1 3 2 1

4

2 variables

5

7

01

6

3 variables

4

5

7

6

1 1 12

13

15

14

10

9

11

10

8

4 variables cde 000 001 011 010 110 111 101 100 ab 00 0 1 3 2 6 7 5 4 01

8

9

11

10

14

15

13

12

11

24

25

27

26

30

31

29

28

10

16

17

19

18

22

23

21

20

5 variables

Figura 2.3: Mapas de Karnaugh para 2, 3, 4 y 5 variables. Las casillas de la primera y u ´ltima fila son adyacentes y lo mismo ocurre con la primera yu ´ltima columna. Un implicante de segundo orden est´a formado por dos implicantes de primer orden adyacentes, uno de tercero por dos de segundo adyacentes, etc. a) Dos variables: En la figura 2.4 tenemos en el primer mapa dos minterms que no son adyacentes y, por tanto, no forman un implicante de primer orden. En los otros mapas s´ı tenemos minterms adyacentes, obteni´endose los siguientes implicantes: i1 (a, b) =

X

m(0, 1) = a b + ab = a(b + b) = a

i2 (a, b) =

X

m(1, 3) = a b + ab = b(a + a) = b

i3 (a, b) =

X

m(0, 1, 2, 3) = a b + ab + ab + ab = a(b + b) + a(b + b) = a + a = 1

b

0

0

1

a

1

1

1

b

0

1

0

1

1

a

1

i1

a

b

0

1

a

b

0

1

0

1

0

1

1

1

1

1

1

1

i2

i3

Figura 2.4: Ejemplos de implicantes de orden 1 (2 celdas adyacentes) y orden 2 (2 implicantes de orden 1 adyacentes) para mapas de dos variables.

´ Y TRATAMIENTO DE LOS SISTEMAS DIGITALES 28TEMA 2. REPRESENTACION Existe un forma simplificada de obtener la expresi´on de los implicantes. Primero se buscan las variables que tomen el mismo valor para todas las casillas del implicante. A continuaci´on, si la variable es cero, en la expresi´on del implicante aparecer´a la variable complementada, y si es 1 aparecer´a la variable sin complementar. i1 : a = 0 en las dos casillas. i1 (a, b) = a i2 : b = 1 en las dos casillas. i2 (a, b) = b i3 : No hay variables que tomen el mismo valor en las cuatro casillas. i3 (a, b) = 1 b) Tres variables: a

bc 0 0 0 1 1 1 1 0 1

0

1

1

a

bc 0 0 0 1 1 1 1 0

0

1

1

1

i4

a

a

bc 0 0 0 1 1 1 1 0

a

1

0

1

1

1

1

1

0

1

1

1

1

i8

1

1

1

1

i6

bc 0 0 0 1 1 1 1 0

0

bc 0 0 0 1 1 1 1 0

0

i5

bc 0 0 0 1 1 1 1 0

a

1

1

i9

a

i7

bc 0 0 0 1 1 1 1 0

a

bc 0 0 0 1 1 1 1 0

0

1

1

0

1

1

1

1

1

1

1

1

1

1

1

1

i 10

i 11

Figura 2.5: Ejemplos de implicantes de o´rdenes 1, 2 y 3 para mapas de tres variables.

En la figura 2.5 se puede ver los siguientes ejemplos de implicantes de ´ordenes 1, 2 y 3: i4 : a = 0, c = 1. i4 (a, b, c) = ac i6 : b = 1, c = 1. i6 (a, b, c) = bc i8 : c = 1. i8 (a, b, c) = c i10 : c = 0. i10 (a, b, c) = c

i5 : a = 0, c = 0. i5 (a, b, c) = a c i7 : a = 1, b = 0. i7 (a, b, c) = ab i9 : a = 1. i9 (a, b, c) = a i11 : i11 (a, b, c) = 1

c) Cuatro variables: En la figura 2.6 se puede ver los siguientes ejemplos de implicantes de ´ordenes 1, 2, 3 y 4: i12 : i14 : i16 : i18 : i20 : i22 :

b = 0,c = 0,d = 1. i12 (a, b, c, d) = b cd i13 : a = 0,b = 1,d = 0. i13 (a, b, c, d) = abd a = 0,b = 1,d = 1. i14 (a, b, c, d) = abd i15 : b = 1,c = 1,d = 1. i15 (a, b, c, d) = bcd c = 1, d = 1. i16 (a, b, c, d) = cd i17 : b = 1, d = 1. i17 (a, b, c, d) = bd b = 0, d = 0. i18 (a, b, c, d) = b d i19 : b = 1, d = 0. i19 (a, b, c, d) = bd a = 1, d = 0. i20 (a, b, c, d) = ad i21 : b = 1. i21 (a, b, c, d) = b d = 0. i22 (a, b, c, d) = d i23 : i23 (a, b, c, d) = 1

´ DE FUNCIONES 2.4. MINIMIZACION

ab

cd 0 0 0 1 1 1 1 0

ab

1

00

cd 0 0 0 1 1 1 1 0

01

11

11 10

1

cd 0 0 0 1 1 1 1 0

00 1

1

i 12 ab

ab

00

01

10

29

ab

cd 0 0 0 1 1 1 1 0

00 1

01

1

11

11

1

10

10

01

i 13

cd 0 0 0 1 1 1 1 0

ab

1

i 14

cd 0 0 0 1 1 1 1 0

ab

i 15

cd 0 0 0 1 1 1 1 0 1

1

ab

cd 0 0 0 1 1 1 1 0

00

1

00

01

1

01

1

1

01

01

1

1

11

1

11

1

1

11

11

1

1

10

1

10

00

10

i 16 ab

1

i 17

cd 0 0 0 1 1 1 1 0

ab

00

01

01

1

1

1

1

1

1

11

1

1

11

10

1

1

10

i 20

10

i 18

cd 0 0 0 1 1 1 1 0

00

1

00

ab

i 19

cd 0 0 0 1 1 1 1 0

ab

cd 0 0 0 1 1 1 1 0

00

1

1

00

1

1

1

1

1

01

1

1

01

1

1

1

1

1

11

1

1

11

1

1

1

1

10

1

1

10

1

1

1

1

i 22

i 21

i 23

Figura 2.6: Ejemplos de implicantes de orden 1, 2, 3 y 4 para mapas de cuatro variables.

cde 000 001 ab

011

010

110

111

101

100

00 01 11 10

Figura 2.7: En un mapa de 5 variables las celdas sim´etricas respecto del eje central son adyacentes.

´ Y TRATAMIENTO DE LOS SISTEMAS DIGITALES 30TEMA 2. REPRESENTACION d) Cinco variables: Los mapas para funciones de 5 variables se construyen a partir de mapas de 4 variables. Las celdas sim´etricas respecto al eje central representan tambi´en adyacencias, como se indica en la figura 2.7.

2.4.2.

Minimizaci´ on en suma de productos mediante mapas de Karnaugh

El objetivo a seguir es incluir todos los unos del mapa con el menor n´ umero de implicantes y del mayor orden posible. Las indiferencias ayudan a completar los implicantes. No importa que los implicantes se solapen unos a otros, lo que si interesa es no incluir implicantes que no son necesarios. El procedimiento a seguir puede resumirse en las siguientes reglas: 1. Extraer todos los implicantes de cualquier orden que no est´en incluidos en otros y que contengan al menos un 1 (se llaman implicantes primos de la funci´on). Empezar por los de mayor orden. 2. Escoger de los implicantes primos aquellos que contengan unos en exclusiva (son los implicantes primos esenciales de la funci´on). 3. En caso de que quede alg´ un 1 por cubrir, escoger el menor n´ umero de implicantes (y del mayor orden posible) necesario para cubrir todos los unos.

ab

cd 0 0 0 1 1 1 1 0 1

00

ab

cd 0 0 0 1 1 1 1 0

1

00

1

ab

cd 0 0 0 1 1 1 1 0

1

00

1

1

01

1

1

-

01

1

1

-

01

1

1

-

11

-

1

-

11

-

1

-

11

-

1

-

1

10

1

10

10

1

1

1

1

Implicantes primos

i1

1

i3

1

i2

1

i4

Figura 2.8: Ejemplo de minimizaci´on como suma de productos en un mapa de Karnaugh de 4 variables. La expresi´on de la funci´on se obtiene a partir de la expresi´on de los implicantes escogidos en los puntos 2 y 3. En la figura 2.8 podemos ver un ejemplo de aplicaci´on de este procedimiento a la siguiente funci´on: f1 (a, b, c, d) =

X

m(2, 3, 4, 5, 9, 10, 11, 13) +

X

d(6, 12, 14)

´ DE FUNCIONES 2.4. MINIMIZACION

31

Las expresiones de los implicantes primos esenciales son: i1 : b = 1, c = 0. i1 = bc

i2 : b = 0, c = 1. i2 = bc

Una vez seleccionados los implicantes primos esenciales queda un u ´nico 1 por cubrir. Hay dos implicantes primos no esenciales que lo cubren, cuyas expresiones son: i3 : a = 1, c = 0, d = 1. i3 = acd

i4 : a = 1, b = 0, d = 1. i4 = abd

As´ı tendremos dos expresiones alternativas para la funci´on, que son: Posibilidad 1: implicantes i1 , i2 e i3 . f1 (a, b, c, d) = bc + bc + acd Posibilidad 2: implicantes i1 , i2 e i4 . f1 (a, b, c, d) = bc + bc + abd Vamos a ver un ejemplo de minimizaci´on de una funci´on de cinco variables: f2 (a, b, c, d, e) =

X

m(2, 9, 10, 11, 15, 21, 25, 29, 31) +

X

d(6, 13, 16, 17, 27)

i3

cde 000 ab

001

011

010

00

110

111

101

100

1

01

1

11

1

1

1

1 1

10

1 1

i1

i2

Figura 2.9: Ejemplo de minimizaci´on como suma de productos en un mapa de Karnaugh de 5 variables.

En la figura 2.9 vemos que los implicantes primos esenciales son i1 = be e i2 = ade. Para cubrir el resto de unos la opci´on con el menor n´ umero de t´erminos producto es tomar el implicante primo i3 = a cde. Por tanto la expresi´on m´ınima es: f2 (a, b, c, d, e) = be + ade + a cde

´ Y TRATAMIENTO DE LOS SISTEMAS DIGITALES 32TEMA 2. REPRESENTACION

2.4.3.

Minimizaci´ on en producto de sumas mediante mapas de Karnaugh

El m´etodo para minimizar la funci´on obteniendo una expresi´on producto de sumas es totalmente equivalente al descrito anteriormente. Las modificaciones que han de realizarse son las siguientes: Colocar en el mapa de Karnaugh los ceros y las indiferencias de la funci´on. Los implicantes estar´an formados por celdas adyacentes que pueden contener tanto ceros como indiferencias (deben contener al menos un cero). La obtenci´on de la expresi´on de cada implicante es la siguiente: por cada variable que no cambie en un implicante, si es 0 tomar la variable tal cual y si es 1 tomar la variable negada. Sumar las variables obtenidas de esta forma. Veamos el siguiente ejemplo de tres variables: g1 (a, b, c) =

X

m(1, 2, 3, 4) +

X

d(6) =

Y

M (0, 5, 7)

Y

D(6)

En la figura 2.10 observamos que existen tres implicantes primos (i1 es un minterm, pero tambi´en lo podemos considerar como un implicante de orden cero). De ellos son implicantes primos esenciales i1 e i2 , que cubren todos los ceros. La expresi´on de los implicantes es: i1 : a = 0, b = 0, c = 0. i1 = a + b + c

a

i2 : a = 1, c = 1. i2 = a + c

bc 0 0 0 1 1 1 1 0

0

0

1

0 i1

i3

0

i2

Figura 2.10: Minimizaci´on como producto de t´erminos suma en un mapa de Karnaugh de 3 variables. Entonces la expresi´on m´ınima ser´a: g1 (a, b, c) = (a + b + c)(a + c) Para finalizar, veamos un u ´ltimo ejemplo de minimizaci´on en forma de producto de sumas de una funci´on de cuatro variables. Estudiemos la siguiente funci´on: g2 (a, b, c, d) =

X

=

Y

m(2, 6, 7, 8, 9, 12, 13, 15) + M (0, 1, 3, 4, 10, 11)

Y

X

d(5, 14)

D(5, 14)

´ DE FUNCIONES 2.4. MINIMIZACION

33

Se observa en el figura 2.11 que s´olo hay un implicante primo esencial que es i1 = a + c (a = 0, c = 0). Para cubrir el resto de ceros tenemos los siguientes implicantes primos: i2 : a = 0, b = 0, d = 1. i2 = a + b + d i4 : a = 1, b = 0, c = 1. i4 = a + b + c

i3 : b = 0, c = 1, d = 1. i3 = b + c + d i5 : a = 1, c = 1, d = 0. i5 = a + c + d i1

cd 00 0 1 1 1 10 ab 00 0 0 0 01

i2

0 i5

11 0

10 i3

0 i4

Figura 2.11: Minimizaci´on como producto de t´erminos suma en un mapa de Karnaugh de 4 variables. Si cogemos i2 , con i4 cubrir´ıamos el resto de ceros. Sin embargo, el maxterm 3 tambi´en puede ser cubierto por i3 , qued´andonos solamente por cubrir el maxterm 10, para lo cual podr´ıamos coger tanto el implicante i4 como el i5 . De esta forma tenemos tres expresiones m´ınimas alternativas: Posibilidad 1: implicantes i1 , i2 , i4 . g2 (a, b, c, d) = (a + c)(a + b + d)(a + b + c) Posibilidad 2: implicantes i1 , i3 , i4 . g2 (a, b, c, d) = (a + c)(b + c + d)(a + b + c) Posibilidad 3: implicantes i1 , i3 , i5 . g2 (a, b, c, d) = (a + c)(b + c + d)(a + c + d)

´ Y TRATAMIENTO DE LOS SISTEMAS DIGITALES 34TEMA 2. REPRESENTACION

EJERCICIOS 2.1. Expresar las siguientes funciones como suma de minterms y como producto de maxterms: i) f1 (a, b, c, d) = abc + ab + ab c ii) f2 (x, y, z) = xy + xz iii) f3 (a, b, c, d) = d(a + b) + bd iv) f4 (w, x, y, z) = yz + wxy + wxz + w xz 2.2. A partir del siguiente circuito, x

y

z

f

i) Obtener la expresi´on l´ogica asociada a la salida. ii) Convertir dicha expresi´on en suma de minterms. iii) Convertir la expresi´on en producto de maxterms. 2.3. Demostrar que los circuitos de la figura 2.12 equivalen a una puerta EXOR y a una NEXOR.

x

f

y

a)

x

f

y

b)

Figura 2.12: a) Equivalente EXOR; b) equivalente NEXOR. 2.4. De un conjunto de 5 elementos {A,B,C,D,E} ha de seleccionarse un subconjunto que verifique las siguientes condiciones:

´ DE FUNCIONES 2.4. MINIMIZACION

35

i) Debe incluirse a A o a B, pero no a ambos. ii) Debe incluirse a C o a E o a ambos. iii) Debe incluirse a A y a C juntos, o a ninguno de los dos. iv) Si D es incluido, debe incluirse tambi´en a B. Construir la funci´on que detecte si un determinado subconjunto es v´alido. 2.5. Minimizar las siguientes funciones como sumas de t´erminos producto: i) f1 (a, b, c, d) =

P

m(0, 2, 6, 11, 13, 14) +

ii) f2 (a, b, c, d) =

P

m(0, 2, 4, 5, 13)

iii) f3 (a, b, c, d) =

P

m(3, 5, 6, 7, 10, 11, 13, 14, 15) +

iv) f4 (a, b, c, d) =

P

v) f5 (a, b, c, d) =

P

m(0, 1, 8) +

vi) f6 (a, b, c, d) =

P

m(0, 1, 2, 3, 8, 14) +

vii) f7 (a, b, c, d) =

P

m(1, 4, 5, 10, 11, 12, 13) +

viii) f8 (a, b, c, d) =

P

ix) f9 (a, b, c, d, e) =

m(0, 1, 2, 4, 8, 9, 10) + P

x) f10 (a, b, c, d, e) =

P

d(1, 3, 9) d(4, 9)

d(3, 5)

P

P

d(4, 5, 6, 7, 9) P

d(3, 6, 14)

d(1, 9)

m(0, 4, 9, 16, 20, 25, 29) +

P

P

d(2, 5, 7, 10, 11, 14, 15)

m(0, 2, 4, 8, 10) + P

P

P

m(1, 6, 17, 18, 19, 22, 23) +

d(2, 6, 18, 22)

P

d(2, 3, 27, 31)

2.6. Minimizar las funciones anteriores como productos de t´erminos suma. 2.7. Dise˜ nar una funci´on que valga 1 cuando la entrada es suma de dos potencias de dos distintas. Los posibles valores de las entradas est´an comprendidos entre 0 y 10, ambos inclusive. 2.8. Dise˜ nar un detector de n´ umeros primos para n´ umeros comprendidos entre el 0 y el 24. Considerar el 0 como n´ umero no primo. Basar el dise˜ no en la obtenci´on de una expresi´on m´ınima para la salida en forma de suma de productos. 2.9. Realiza la minimizaci´on de la funci´on f1 como suma de t´erminos producto y la de las funciones f2 y f3 como producto de t´erminos suma, mediante mapas de Karnaugh. Da todas las posibilidades m´ınimas. La variable a es la de m´as peso. i) f1 (a, b, c, d) =

P

m(0, 2, 7, 9, 11) +

P

d(1, 3, 5, 6, 8, 14)

ii) f2 (a, b, c, d) =

P

m(0, 10, 13, 14) +

P

d(2, 4, 9)

P

iii) f3 (a, b, c, d, e) = m(2, 6, 7, 9, 13, 15, 16, 18, 20, 21, 22, 23, 29, 31) P + d(12, 17, 19, 28, 30) 2.10. Realiza la minimizaci´on de la funci´on f1 como suma de t´erminos producto y la de las funciones f2 y f3 como producto de t´erminos suma, mediante mapas de Karnaugh. Escribe todas las posibilidades m´ınimas. La variable a es la de mayor peso.

´ Y TRATAMIENTO DE LOS SISTEMAS DIGITALES 36TEMA 2. REPRESENTACION i) f1 (a, b, c, d) =

P

m(1, 6, 12, 13, 14) +

ii) f2 (a, b, c, d) =

P

P

m(0, 1, 5, 7, 15) +

P

d(4, 7, 9, 10)

d(2, 6, 14)

P

iii) f3 (a, b, c, d, e) = m(0, 3, 4, 8, 10, 12, 14, 15, 17, 18, 20, 24, 30) P + d(1, 2, 5, 16, 19, 26, 28, 31) 2.11. Realiza la minimizaci´on de la funci´on f2 como suma de t´erminos producto y la de las funciones f1 y f3 como producto de t´erminos suma, mediante mapas de Karnaugh. Escribe todas las posibilidades m´ınimas. La variable a es la de mayor peso. i) f1 (a, b, c, d) =

P

m(2, 4, 6, 8, 11, 12, 13) +

ii) f2 (a, b, c, d) =

P

m(2, 7, 8, 10, 11) +

iii) f3 (a, b, c, d, e) =

Q

P

P

d(3, 5, 7, 9)

d(0, 3, 5, 6, 9, 15)

M (1, 2, 5, 9, 10, 25, 27) ·

Q

D(0, 6, 8, 13, 14, 17, 24)