Clase 16Minimizacion de

Mapas de Karnaugh

M.C. Juan Angel Garza Garza

Maurice Karnaugh

Ingeniero de Telecomunicaciones

• AT&T Bell en1953.

• Inventa el mapa-K o mapa de Karnaugh.

– Minimitzación de POS(SOP) por inspección

visual.

Tabla o mapa de Karnaugh

Procedimiento gráfico para la simplificación

de funciones algebraicas de un número

de variables relativamente pequeño (en

la práctica se puede utilizar para

funciones de hasta seis variables).

Tabla o mapa de Karnaugh

Un diagrama o mapa de Karnaugh es una

tabla de verdad dispuesta de manera

adecuada para determinar por inspección

la expresión mínima de suma de

productos de una función lógica.

Maurice Karnaugh

• Ph.D. (Physics), Yale University (1952)

• Research Staff member, Thomas J. Watson Research Center, IBM Corporation, Yorktown Heights, New York, USA.

• Fellow of the IEEE for contributions to the understanding and application of digital techniques in telecommunications (1975); introduced the MAP method for logic design; one of the co-inventors of ESSEX, the first experimental digital switching system; other contributions to logic hardware, digital switch configurations, network layout algorithms, and expert systems applications; employed by the Bell Telephone Laboratories 1952 to 1966 and by the IBM Corporation 1966-1993

• 1980-1999 Adjunct Professor of Computer Science at the Polytechnic Institute of New York. Currently retired.

la Factorización se efectúa cuando solo cambia una variable entre dos términos y esta variable se elimina

Con 2 variables A y B se pueden tener 4 Términos

Cada termino de dos variables tiene dos posibilidades de factorizacion

K map para 2 variables

K map para 2 variables

K map para 2 variables

Como llenar el K map para 2 variables

1

0

1

1

Como resolver K map para 2 variables

F1(A,B)= A

1

+ B’

0

K map para 3 variables

Con 3 Variables se tienen 8 términos

y cada termino tiene 3 posibilidades

de factorización

K map para 3 variables

Cada termino tiene 3 posibilidades de factorización

K map para 3 variables

K map para 3 variables

K map para 3 variables

K map para 4 variables

Con 4 Variables se tienen 16 términos

y cada termino tiene 4 posibilidades

de factorización

K map para 4 variables

Cada termino tiene 4 posibilidades de factorización

Cada termino tiene 4 posibilidades de factorización

K map para

4 variables

AB00 01 11 1010

K map para

4 variables

K map para

4 variablesAB

CD

00 01 11

00

01

11

1010

10

10

K map para 4 variables

K map para 4 variables

K map para 5 variables

Con 5 Variables se tienen 32 términos

y cada termino tiene 5 posibilidades

de factorización

K map para 5variables

K map para 5variables

K map para 5 variables

Reglas para el uso del Kmap

1.- Formar el menor numero de grupos

2.- Cada grupo lo mas grande posible

3.- Todos los unos deberán de ser agrupados

Un solo uno puede formar un grupo

Casillas de un grupo pueden formar parte de otro grupo

Grupo = Unos adyacentes enlazados (paralelogramos) en una cantidad igual a una

potencia entera de dos eje. (1, 2, 4, 8,…).

ejemplos del Kmap

0

1

ejemplos del Kmap

F2(X, Y, Z) =m(1, 2, 5, 7)

1

1 1 1

00

0

0

F2(X, Y, Z) =m(1, 2, 5, 7)

1

1 1 1

00

0

0

F2(X, Y, Z) = X Z

1 1

1

+ Y’

F2(X, Y, Z) =m(1, 2, 5, 7)

1

1 1 1

00

0

0

F2(X, Y, Z) = X Z Z

00

1

+ Y’

F2(X, Y, Z) =m(1, 2, 5, 7)

1

1 1 1

00

0

0

F2(X, Y, Z) = X Z Z + X’ Y Z’

01

0

F3(A, B, C, D) =m(0,2,5,6,7,8,12,14)

F3(A, B, C, D) =m(0,2,5,6,7,8,12,14)

D'

F3(A, B, C, D) =m(0,2,5,6,7,8,12,14)

F3= A'B'

00

0

0

C'D' D'

F3(A, B, C, D) =m(0,2,5,6,7,8,12,14)

F3= A'B' + A

C D'C'D' D'

F3(A, B, C, D) =m(0,2,5,6,7,8,12,14)

F3= A'B' + A

+B

C D'C'D' D'

F3(A, B, C, D) =m(0,2,5,6,7,8,12,14)

F3= A'B' + A

+B +A'B

D

F3(A, B, C, D) =m(0,2,5,6,7,8,12,14)

F3=A'B'D' + A C'D' +A'B D + B C D‘F3=B'C'D' +A'C D' + A'B D + A B D'

F3(A, B, C, D) =m(0,2,5,6,7,8,12,14)

F3=A'B'D' + A C'D' +A'B D + B C D‘F3=B'C'D' +A'C D' + A'B D + A B D'

F4(A, B, C) =m(2, 7)

0

0

1 1 1

1 1 1

F4(A, B, C) =m(2, 7)

0

0

1 1 1

1 1 1

F4(A, B, C) = A’

0 0

1

C

C

F4(A, B, C) =m(2, 7)

0

0

1 1 1

1 1 1

F4(A, B, C) = A’

1 1

0

+A C’

C

F4(A, B, C) =m(2, 7)

0

0

1 1 1

1 1 1

F4(A, B, C) = A’

0

+A C’

0

+B’

Reglas para el uso del Kmap

1.- Formar el menor numero de grupos

2.- Cada grupo lo mas grande posible

3.- Todos los unos deberán de ser agrupados

Un solo uno puede formar un grupo

Casillas de un grupo pueden formar parte de otro grupo

Grupo = Unos adyacentes enlazados (paralelogramos) en una cantidad igual a una

potencia entera de dos eje. (1, 2, 4, 8,…).

F5(X, Y, Z, W) =m(0,2,7,8,10,12,13,14)

F6(A, B, C, D) =m(0,15)

F7(A, B, C, D) =m(5, 7,15)

F8(X, Y, Z, W) =m(0,2,3,5,6,7,8,10,11,14,15)

F9 ( A,B,C,D )= m ( 2, 5, 7, 13, 15)

F10 ( X,Y,Z,W )= m ( 5, 13, 15)

F11 ( X,Y,Z,W )= m ( 1, 3, 6, 7, 9, 11, 12)

F12 (A,B,C,D) = m ( 3,5,6,7, 9,10,11,12,13,14)

La mejor forma de Huir de un problema es resolverlo.

F5(X, Y, Z, W) =m(0,2,7,8,10,12,13,14)

1

1

1

1

1

1

1

1

F5(X, Y, Z, W) =m(0,2,7,8,10,12,13,14)

La mejor forma de Huir de un problema es resolverlo.

F5(X, Y, Z, W) = X W' + X Y Z' + X'Y Z W + Y'W'

F6(A, B, C, D) =m(0,15)

F6(A, B, C, D) =D'+A C'+B'+A'C (SOP)

F6(A, B, C, D) =(A'+B'+C'+D')(A+B'+C+ D') (POS)

F7(A, B, C, D) =m(5, 7,15)

F7(A, B, C, D)=D' + A C' + B' (SOP)

F7(A, B, C, D) =m(5, 7,15)

Agrupando ceros POS

F7(A, B, C, D)=(B'+C'+D')(A+B'+D') (POS)