Representación gráfica

M APAS DE K ARNAUGH

Representación gráfica de los mintérminos (o maxtérminos) de dos variables.

y (0,1)

(1,1)

(0,0)

Circuitos Digitales EC1723

(1,0)

x

Si una función de x e y incluye, por ejemplo, los mintérminos 2 y 3, podemos aplicar el teorema de combinación para eliminar un literal: x·y’+x·y = x En la gráfica, estos mintérminos se encuentran en el lado marcado en verde, que corresponde al literal x. El segmento (0,0)-(1,0) corresponde al literal y’.

Universidad Simón Bolívar Departamento de Electrónica y Circuitos Prof. Juan. C. Regidor

Prof. Juan Claudio Regidor

Universidad Simón Bolívar

2

1

Distancia La distancia entre dos mintérminos es el número de segmentos que se recorren para llegar de un punto a otro

Distancia y

(0,1)

(0,0)

Los mintérminos de 3 variables pueden representarse como los vértices de un cubo.

(1,1)

(1,0)

x

Una arista del cubo representa al producto de dos literales, pues se elimina una variable por combinación.

La distancia entre (0,0) y (0,1) es 1 La distancia entre (0,1) y (1,0) es 2 Si la distancia entre dos mintérminos es 1, se dice que son adyacentes. Si ambos están presentes en una función, puede aplicarse el teorema de combinación y eliminar un literal. Prof. Juan Claudio Regidor

Universidad Simón Bolívar

z

(0,1,1)

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

y

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

(1,0,0)

(1,1,0)

x

Una cara del cubo representa a un literal. El T. de combinación permite eliminar 2 variables. Ejemplo: x’·y’·z + x·y’·z + x·y·z + x’·y·z = y’·z + y·z = z 3

Prof. Juan Claudio Regidor

Universidad Simón Bolívar

4

Mapa de Karnaugh de 3 Variables

Métodos de minimización Estas ideas de distancia, adyacencia y eliminación de variables por combinación se pueden extender a dimensiones mayores, y son la base de los métodos prácticos de minimización de funciones lógicas: Mapa de Karnaugh, propuesto en 1953, permite el tratamiento manual de funciones de 2 a 6 variables.

! " #

5

}A

! " #

Universidad Simón Bolívar

! " #

}C

Algoritmo de Quine-McCluskey, propuesto por W. V. Quine en 1955 y modificado por E. J. McCluskey en 1956; usado por programas de computadora, permite minimizar funciones de cualquier tamaño. Prof. Juan Claudio Regidor

B

! " #

A

B

C

Prof. Juan Claudio Regidor

Universidad Simón Bolívar

6

Mapa de 3 Variables (mintérminos)

Mapa de 3 Variables (Maxtérminos)

Los puntos del mismo color indican recuadros adyacentes.

Los puntos del mismo color indican recuadros adyacentes.

m0 + m4 = B’.C’

m1 + m3 = A’.C

m6 + m7 = A.B

m4 + m5 + m6 + m7 = A

Prof. Juan Claudio Regidor

Universidad Simón Bolívar

m1 + m3 = A’.C M0 . M4 = B+C

M1 . M3 = A+C’

M6 . M7 = A’+B’ 8

Prof. Juan Claudio Regidor

m1 + m

M4 . M5 . M6 . M7 = A’

Universidad Simón Bolívar

10

Mapa de Karnaugh de 4 Variables

Mapa de 4 Variables (mintérminos) Los puntos del mismo color indican recuadros adyacentes.

00 01

0 1

! 11 3 #10 2

C"

01 4

11 12

10

00

8

5

13

9

7

15

11

6

14

10

! " #

CD 00 AB

! "D #

01

11

10

0

1

3

2

4

5

7

6

13

15

14

9

11

10

! 11 12 # 10 8

A"

01

! " #

! " #

Prof. Juan Claudio Regidor

C

! " #

A

AB 00 CD

B

D

Universidad Simón Bolívar

! "B # m12 + m14 = A.B.D’ m0 + m2 + m8 + m10 = B’.D’ m1 + m9 = B’.C’.D m2 + m3 + m6 + m7 = A’.C !m(1,3,5,7,9,11,13,15) = D 11

Prof. Juan Claudio Regidor

Universidad Simón Bolívar

Mapa de 4 Variables (Maxtérminos)

Mapa de 5 Variables (mintérminos)

Los puntos del mismo color indican recuadros adyacentes.

Los puntos del mismo color indican recuadros adyacentes.

M12 . M14 = A’+B’+D M0 . M2 . M8 . M10 = B+D M1 . M9 = B+C+D’ "M(1,3,5,7,9,11,13,15) = D’ M2 . M3 . M6 . M7 = A+C’ Prof. Juan Claudio Regidor

Universidad Simón Bolívar

15

13

m1 + m3 = A’.C

m1 + m

m4 + m6 = A’.B’.C.E’ !m(9,11,13,15) = A’.B.E Prof. Juan Claudio Regidor

m1 + m

!m(16,18,24,26) = A.C’.E’ m1 + m17 = B’.C’.D’.E

Universidad Simón Bolívar

17

Mapa de 5 Variables (mintérminos)

Mapa de 5 Variables (Maxtérminos)

Los puntos del mismo color indican recuadros adyacentes.

Los puntos del mismo color indican recuadros adyacentes.

m1 + m3 = A’.C

!m(4,6,20,22) = B’.C.E’ !m(1,5,9,13,17,21,25,29)=D’.E !m(10,11,26,27) = B.C’.D !m(0,8,16,24) = C’.D’.E’ Prof. Juan Claudio Regidor

Universidad Simón Bolívar

19

m1 + m

M4 . M6 = A+B+C’+E "M(16,18,24,26) = A’+C+E "M(9,11,13,15) = A+B’+E’ M1 . M17 = B+C+D+E’ Prof. Juan Claudio Regidor

Mapa de 5 Variables (Maxtérminos)

Universidad Simón Bolívar

21

Mapa de 6 Variables (mintérminos)

Los puntos del mismo color indican recuadros adyacentes.

m14+m30 = A’.C.D.E.F’ m10+m42 = B’.C.D’.E.F’ !m(13,29,45,61) = C.D.E’.F !m(1,3,17,19,33,35,49,51) = C’.D’.F

m1 + m3 = A’.C

"M(4,6,20,22) = B+C’+E "M(1,5,9,13,17,21,25,29)=D+E’ "M(10,11,26,27) = B’+C+D’ "M(0,8,16,24) = C+D+E Prof. Juan Claudio Regidor

Universidad Simón Bolívar

23

m1 + m

!m(32,36,40,44)= A.B’.E’.F’

Prof. Juan Claudio Regidor

Universidad Simón Bolívar

25

Mapa de 6 Variables (Maxtérminos)

Minimización de funciones con Mapas de Karnaugh

M14+M30 = A+C’+D’+E’+F M10+M42 = B+C’+D+E’+F "M(13,29,45,61) = C’+D’+E+F’

"M(1,3,17,19,33,35,49,51)= C+D+F’

Implicante: grupo de mintérminos o maxtérminos adyacentes. Implicante primo: es aquel que no está contenido en otro. Implicante primo esencial: un implicante que cubre a

m1 + m3 = A’.C un m o M que no aparece en ningún otro implicante

"M(32,36,40,44) = A’+B+E+F Prof. Juan Claudio Regidor

Universidad Simón Bolívar

27

Minimización de funciones con Mapas de Karnaugh AB 00 CD 00 01 11 10

01

11

0

12

8

1

1 5

1 13

9

3

7

2

6

1

1

15

11

14

10

Universidad Simón Bolívar

28

Minimización de funciones con Mapas de Karnaugh Para obtener una expresión mínima a partir del mapa de Karnaugh:

10

1 4

Prof. Juan Claudio Regidor

Tomar todos los implicantes primos esenciales Completar la cobertura de términos de la función usando la menor cantidad posible de implicantes primos no esenciales

El mapa contiene 11 implicantes: 5 mintérminos, 5 pares de mintérminos, y un grupo de 4 mintérminos

Se debe dar prioridad a aquellos implicantes que contengan el menor número de literales

Hay dos implicantes primos: m4+m5 y !m(5,7,13,15) Ambos implicantes primos son esenciales. Prof. Juan Claudio Regidor

Universidad Simón Bolívar

29

Prof. Juan Claudio Regidor

Universidad Simón Bolívar

30

Minimización de funciones con Mapas de Karnaugh AB 00 CD 00 1 0 01 11 10

01

1

10

12

8

1

1 5

1 13

9

3

7

15

11

6

14

10

2

1

4

11

1

Minimización de funciones con Mapas de Karnaugh

Si no existe ningún implicante esencial, se toma uno cualquiera como si lo fuera y se procede a partir de él

1 1

En cualquier caso es posible que existan varias expresiones diferentes con la misma complejidad

El mapa contiene 8 implicantes primos. No hay ningún implicante esencial. Universidad Simón Bolívar

Prof. Juan Claudio Regidor

32

Prof. Juan Claudio Regidor

Ejemplos

0

0

1

1

01

11

10

1

1

1

1

2 3

1

6 7

Minimizar F(A,B,C,D) = !m(4, 5, 7, 13, 15) AB 00 CD

4

F(A,B,C) = B + A·C’

00

5

01 11

Minimizar F(A,B,C) = "M(0, 1, 5) AB 00 C 0 0 1

Prof. Juan Claudio Regidor

0

10 01 0 1

11 2 3

10 6 7

4

0

33

Ejemplos

Minimizar F(A,B,C) = !m(2, 3, 4, 6, 7) AB 00 C

Universidad Simón Bolívar

F(A,B,C) = (A + B) · (B + C’)

01

1

0

4

1

1 5

3

7

2

6

1

11

10

12

8

1 13

9

1

15

11

14

10

F(A,B,C,D) = B·D + A’·B·C’

5

Universidad Simón Bolívar

34

Prof. Juan Claudio Regidor

Universidad Simón Bolívar

35

Ejemplos

Ejemplos AB 00 01 11 10 CD 00 0 0 4 12 0 8 0

Reducir F(A,B,C,D) = "M(0, 1, 2, 4, 5, 8, 10)

01 05

01

F(A,B,C,D) = (A+C)·(B+D)

11

3

02

10

7 6

13

AB 00 01 11 10 CD 00 0 0 4 12 0 8 0

Reducir F(A,B,C,D) = "M(0, 1, 2, 4, 5, 8, 10)

01

9

15

11

14

010

F(A,B,C,D) = (A+C)·(B+D)

01 05

11 10

3

AB 00 CD

Reducir F(A,B,C,D) = # !m(3,6,7,9,11,12,13,14,15)

00

11

Universidad Simón Bolívar

36

Prof. Juan Claudio Regidor

Ejemplos

1

A=0

00

0

01 11 10

01

1

1

11 4

1

5

3

7

2

1

6

10

1

12

8

1

13

9

15

11

1

14

1

10

BC 00 DE 00 1

16

01

1

11 10

Reducir F(A,B,C,D,E,F) ="M(5,7,10,11, 21,23,26,27,37,42, 43,48,49,50,51,58, 59)

A=1 01 20

11 28

1

17

21

19

23

31

22

30

1

18

29

10

1

24

1

25

F(A,B,C,D,E,F) = (C'+D+E'). (A'+B'+C+D). (A+C+D'+F'). (B+C+D'+E+F')

27

1

26

F(A,B,C,D,E) = A.C’.D’+ C’.D.E’ + A’.C.E’ + B.C.D’.E Prof. Juan Claudio Regidor

Universidad Simón Bolívar

15

11

14

010

11

10

4

112

5

113 1 9

8

2

1 6 114

Universidad Simón Bolívar

10 36

Ejemplos

Minimizar F(A,B,C,D,E) = !m(2, 4, 6, 10, 12, 13, 14, 16, 17, 18, 24, 25, 26, 29) BC 00 DE

01

9

1 3 1 7 115 111

10 Prof. Juan Claudio Regidor

6

0

01

F(A,B,C,D) = # A·B + C·D + A·D + B·C

7

02

13

37

Prof. Juan Claudio Regidor

A=0

CD 00 EF 00

01 0

01

1

11

3

10

00 01 11 10

4

0 0

2

CD 00 EF 16 17 19 18

11

5

12

15

6

14

01 20

0

21

0

8

13

7

11 28 29

23

31

22

30

Universidad Simón Bolívar

CD 00 EF

10

9

00 01

0

11

0

10

11

10

10 24

32 33

45 47

34

38

46

CD 00 EF 00 0

48

0

11

0

0

10

0

26

37

44

39

0

27

36

0

11

35

01

25

A=1 01

49 51 50

01

11

52

60

53

61

55

63

54

62

10 40 41

0

B=0

43

0

42

10 56 57

0

B=1

59

0

58 38

Ejemplos

Problema de Votación

Minimizar F(A,B,C,D) = !A,B,C,D(0,2,4,5,10,11,13,15)

Un comité de cuatro miembros (A, B, C y D) debe tomar decisiones por mayoría simple. En caso de empate, el voto del presidente del comité (A) es decisivo. Hallar una función lógica mínima que valga 1 cuando el voto sea aprobatorio, y 0 en caso contrario.

AB 00 CD 00 1 0 01 11 10

1

01 4 5

3

7

1 2

6

1 1

11 12

1

10

AB 00 CD 00 1 0

8

13

9

1 15

1 11

14

1 10

01 11

F = A’·C’·D’+B·C’·D+A·C·D+B’·C·D’

10

1

1 4 5

3 2

01

1

1

11 12

10 8

1

13

1

AB 00 CD

9

1

01

1

1

1

1

1

1

15

11

6

14

10

Universidad Simón Bolívar

39

Sumador Completo X2 Y2 Ci2

X1 Y1 Ci1

X0 Y0 Ci0

...

XY 00 Cin

01

0

1

1

Cn Sn

X Y Cin

Cout S Prof. Juan Claudio Regidor

C2 S2

X 0 0 0 0 1 1 1 1

C1 S1

Y 0 0 1 1 0 0 1 1

C0 S0

Cin Cout S 0 0 0 1 0 1 0 0 1 1 1 0 0 0 1 1 1 0 0 1 0 1 1 1 Universidad Simón Bolívar

1

10

1

7

F = A’·B’·D’+A’·B·C’+A·B·D+A·B’·C

Xn Yn Cin

11

1

1

11

Prof. Juan Claudio Regidor

01

00

10 Prof. Juan Claudio Regidor

V = A·B + A·C + A·D + B·C·D

Universidad Simón Bolívar

40

Sumador Completo 11

10

1

X Y Cin

1

S = X’·Y’·Cin + X’·Y·C’in + X·Y’·C’in + X·Y·Cin

S = X ! Y ! Cin

S = X ! Y ! Cin XY 00 Cin

01

1

11

Cout = XY + XCin +YCin

10

1

0

1

1

1

Cout = XY + XCin +YCin 41

Prof. Juan Claudio Regidor

Universidad Simón Bolívar

42

Convertidor de Binario a Código Gray de 4 bits B3 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

B2 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

B1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

B0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

G3 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

G2 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0

G1 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0

G0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0

B3 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

G3 = B3

Universidad Simón Bolívar

Prof. Juan Claudio Regidor

Convertidor de Binario a Código Gray de 4 bits

43

B2 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

B1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

Prof. Juan Claudio Regidor

B0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

G3 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

G2 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0

G1 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0

G0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0

Universidad Simón Bolívar

B3B2 00 B1B0

01

11

00

1

1

01

1

1

1

1

10

1

1

B0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

G3 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

G2 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0

G1 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0

G0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0

B3B2 00 B1B0

01

00

1

1

01

1

1

11

1

1

10

1

1

11

10

G2

Universidad Simón Bolívar

43

Convertidor de Binario a Código Gray de 4 bits B3 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

10

11

B1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

Prof. Juan Claudio Regidor

Convertidor de Binario a Código Gray de 4 bits B3 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

B2 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

G1

43

B2 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

B1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

Prof. Juan Claudio Regidor

B0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

G3 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

G2 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0

G1 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0

G0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0

Universidad Simón Bolívar

B3B2 00 B1B0

01

11

10

1

1

1

1

1

1

1

1

00 01 11 10

G0

43

Convertidor de Binario a Código Gray de 4 bits B3B2 00 B1B0

01

00

10

B3B2 00 B1B0

01

11

1

1

00

1

1

01

1

1

01

1

1

11

1

1

10

1

B3B2 00 B1B0

01

11

11

G2

1

1

1

10

1

1

10

G3 = B3

G 3 = B3 G3

G1

G 2 = B3 ! B2 G2

G 1 = B2 ! B1 G1

G2 = B’3B2 + B3B’2 = B3 ! B2 1

1

B3 B2 B1 B0

1

1

1

11 10

10

11

00 01

Convertidor de Binario a Código Gray de 4 bits

1

1

G1 = B2B’1 + B’2B1 = B2 ! B1

G0

G0 = B’1B0 + B1B’0 = B1 ! B0

1

G G0 0 = B1 ! B0

Gk = Bk+1 ! Bk Universidad Simón Bolívar

Prof. Juan Claudio Regidor

44

Convertidor de Código Gray de 4 bits a Binario G3 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

G2 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

G1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

Prof. Juan Claudio Regidor

G0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

B3 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

B2 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0

B1 0 0 1 1 1 1 0 0 1 1 0 0 0 0 1 1

B0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0

Universidad Simón Bolívar

Universidad Simón Bolívar

Prof. Juan Claudio Regidor

45

Convertidor de Código Gray de 4 bits a Binario G3 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

B3 = G3

46

G2 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

G1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

Prof. Juan Claudio Regidor

G0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

B3 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

B2 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0

B1 0 0 1 1 1 1 0 0 1 1 0 0 0 0 1 1

B0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0

G3G2 00 G1G0

01

00

1

1

01

1

1

11

1

1

10

1

1

Universidad Simón Bolívar

11

10

B2

46

Convertidor de Código Gray de 4 bits a Binario G3 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

G2 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

G1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

G0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

B3 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

B2 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0

B1 0 0 1 1 1 1 0 0 1 1 0 0 0 0 1 1

B0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0

G3G2 00 G1G0

01

00

1

1

01

1

1

11

11

1

1

10

1

1

G3 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

10

B1

Universidad Simón Bolívar

Prof. Juan Claudio Regidor

Convertidor de Código Gray de 4 bits a Binario

46

Convertidor de Código Gray de 4 bits a Binario G3G2 00 G1G0

01

10

G3G2 00 G1G0

00

01

1

1

00

1

1

01

1

1

01

1

1

11

1

1

10

1

1

G3G2 00 G1G0

01

00

1

01

1

11

1

Prof. Juan Claudio Regidor

B2

10

1 1

1

11 10

11

1 1

B0

11

11

1

1

10

1

1

G2 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

G1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

Prof. Juan Claudio Regidor

B3 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

B2 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0

B1 0 0 1 1 1 1 0 0 1 1 0 0 0 0 1 1

B0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0

G3G2 00 G1G0

01

00

1

01

1

1

10

1 1

1

11 10

11

1 1

B0

Universidad Simón Bolívar

46

Convertidor de Código Gray de 4 bits a Binario

10

G3 G2 G1 G0

G3 G2 G1 G0 B3

B3

B2

B2

B1

B1

B0

B0

B1

B3 = G3 B2 = G’3G2 + G3G’2 = G3 ! G2 B1 = G’3G2 G’1 + G3G’2 G’1 + G’3G’2 G1 + G3G2 G1 = G3!G2!G1 B0 = G3 ! G2 ! G1 ! G0 Bk = Gn–1 ! Gn–2 ! ... ! Gk Universidad Simón Bolívar

G0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

47

Prof. Juan Claudio Regidor

Universidad Simón Bolívar

48