Sistemas Digitales, Clase N°8

1

Circuitos de Conmutación

Los circuitos de conmutación están formados por compuertas lógicas, que implementan las operaciones lógicas (and, or y not).

Sus variables de entrada y su función de salida son valores lógicos representados por “ceros” y “unos”.

A continuación algunos ejemplos de circuitos de conmutación.

Sistemas Digitales, Clase N°8

2

Compuertas Básicas

A B Z A B Z A Z

0 0 0 0 0 0 0 1

0 1 0 0 1 1 1 0

1 0 0 1 0 1

1 1 1 1 1 1

A N D

AB

ZAB

Z A Z

O R N O T

Sistemas Digitales, Clase N°8

3

Compuertas Adicionales

N A N DAB

ZAB

ZAB

Z

N O R X O R

A B Z A B Z A B Z

0 0 1 0 0 1 0 0 0

0 1 1 0 1 0 0 1 1

1 0 1 1 0 0 1 0 1

1 1 0 1 1 0 1 1 0

Sistemas Digitales, Clase N°8

4

Minimización de funciones

• En general al minimizar un sistema digital para su implementación con compuertas se obtiene menor:– costo, – número de componentes– consumo de potencia,– espacio físico,– tiempo de respuesta.

• Técnicas:– Minimización Algebraica,– Minimización a través de Mapas de Karnaugh,

Sistemas Digitales, Clase N°8

5

Minimización Algebraica

• Usa los teoremas del álgebra de Boole, para minimizar la función.

• No existe una técnica o método que indique cuales teoremas usar, en general se recomienda:– Expresar la función en forma de Suma de

Productos o Productos de Sumas.– Utilizar los teoremas del álgebra, para eliminar

variables, duplicando términos que puedan agruparse.

Sistemas Digitales, Clase N°8

6

Minimización Algebraica

)(

:3

)1()(

:2

)(

:1

)(:

bcaz

paso

bacaz

cbabbcaz

cbacbabacbaz

paso

cbabacbaz

cabacbaz

paso

cabacbazejemplo

Sistemas Digitales, Clase N°8

7

Minimización Algebraica

ZA

A

B

C

ABC

ZB

A

C

Implementación original:

Implementación minimizada:

Sistemas Digitales, Clase N°8

8

Minimización por Mapas de Karnaugh

• Un mapa de Karnaugh es una representación gráfica de la tabla de verdad de una función de conmutación.

Para n variables, hay celdas en el mapa.

Ejemplo: 2 variables:

n2

X Y M inter

0 0 010 1

1 0 231 1

0

1

2

3

0 1

X

Y

0

1

X

Y

yx yx

yx xy

Sistemas Digitales, Clase N°8

9

Minimización por Mapas de Karnaugh

• Para 3 variables:X Y Z M inter

0 0 0 010 0 1

0 1 0 20 1 11 0 0 4

51 0 11 1 0 6

71 1 1

0

1

2

3

6

7

4

5

00 01 11 10

X Y

Z

0

1

X

Y

Z

Sistemas Digitales, Clase N°8

10

Minimización por Mapas de Karnaugh

• Para 4 Variables:

0

1

3

2

4

5

7

6

12

13

15

14

8

9

11

10

00 01 11 10

W X

Y Z

00

01

11

10

W

X

Z

Y

W X Y Z M inter

0 0 0 0 010 0 0 1

0 0 1 0 20 0 1 10 1 0 0 4

151 1 1 1

Sistemas Digitales, Clase N°8

11

Minimización por Mapas de Karnaugh

• En las coordenadas se anotan los valores de las variables según el código Gray,

• Coloque los valores”1” en las celdas correspondientes a los mintérminos de la función, complete el resto de las celdas por un “0”.

• En general cada celda del mapa está cubierta por un CERO o un UNO,

Ejemplo: Obtener el mapa de la función

00 01 11 10

0

1

)7,5,2,1(),,( zyxf0 1 0 0

1 0 1 1

Sistemas Digitales, Clase N°8

12

Minimización por Mapas de Karnaugh

Definición: Dos celdas son adyacentes si difieren solo en una variable, o sea en un bit.

Ejemplos:n=3 n=4

Cada celda tiene 3 celdas adyacentes

cada celda tiene 4 celdas adyacentes

Sistemas Digitales, Clase N°8

13

Minimización por Mapas de Karnaugh

Dos celdas adyacentes se pueden agrupar aplicando:

Ejemplo:

del mapa se obtiene la función:

bbaba

0000

0110

cbaacbcbacbadcbaf )(),,,(

ba ba ab ba

c

c

Sistemas Digitales, Clase N°8

14

Minimización por Mapas de Karnaugh

Definición: Subcubo: es la colección de celdas y cada celda adyacente a “n” celdas de la

colección.

Ejemplos:

OBS: Las variables que aparecen con complemento y sin complementos se eliminan.

n2

0 0 0 0

0 1 1 0

0 1 1 0

0 0 0 0

242 nn

0 1 1 0

0 0 1 0

ba ba ab ba

dc

dc

cd

dc bddcbaf ),,,(

abcbcbaf ),,(

cc

ba ba ab ba

Sistemas Digitales, Clase N°8

15

Minimización por Mapas de KarnaughEl subcubo cubre las celdas. Cada subcubo puede ser expresado por

un producto de m-n variables.

Ejemplo:

» m=4 (numero de variables)

» n=3

» Se eliminan tres variables

n2

0 0 1 1

0 0 1 1

0 0 1 1

0 0 1 1

ba baba ab

dc

dc

cd

dc

adcbaf ),,,(

Sistemas Digitales, Clase N°8

16

Minimización por Mapas de Karnaugh

• Una función puede ser expresada como la suma de los términos que corresponden a los subcubos necesarios para cubrir todos los unos del mapa. Si en un subcubo se agrupan “unos” el resultado será una función expresada como Suma de Productos.

• Una función puede ser expresada como el productos de los términos que corresponden a los subcubos necesarios para cubrir todos los ceros del mapa. Si en un subcubo se agrupan los “ceros” el resultado será una función expresada como Productos de Sumas.

• Una función es mínima cuando los unos son cubiertos con el mínimo número de subcubos (mínimo números de términos) y además cada subcubo es lo más grande posible (mínimo número de literales).

Sistemas Digitales, Clase N°8

17

Minimización por Mapas de Karnaugh

• Ejemplos:

1

1 1 1

00 01 11 10

X Y

0

X

Y

Z1

Z0

1

2

3

6

7

4

5

00 01 11 10

X Y

0

1

X

Y

Z

0 1 0 0

1 0 1 1

Z

X Y Z F

0 0 0 010 0 1

0 1 0 100 1 1

1 0 0 011 0 1

1 1 0 011 1 1

X Z

Y Z

X Y Z

Sistemas Digitales, Clase N°8

18

Minimización por Mapas de Karnaugh

11

0000 0101 1111 1010X YX Y

ZZ

XX

YY

11 11

111 11

XY

00

11 ZZ

Z X Z·

Sistemas Digitales, Clase N°8

19

Minimización por Mapas de Karnaugh

W X0

1

3

2

4

5

7

6

12

13

15

14

8

9

11

10

00 01 11 10

W X

Y Z

00 1

1 1

1 1

1

01

11

10

W

X

Y

Z

00 01 11 10

W X

Y Z

00 1

1 1

1 1

1

01

11

10

W

X

Y

Z

F( = (5 ,7,12,13,14,15)mW,X,Y,Z)

X Z

Sistemas Digitales, Clase N°8

20

Minimización por Mapas de Karnaugh

0

1

3

2

4

5

7

6

12

13

15

14

8

9

11

10

00 01 11 10

W X W X

Y Z Y Z

00

1 1 1

111

1

01

11

10

W W

X X

Y Y

Z Z

00 01 11 10

00

1 1 1

11 1

1

01

10

F(W ,X,Y,Z) = (1,2,3,5,7,11,13)m

11

X . Y . Z

X . Y. Z

W . X . Y

W . Z

Sistemas Digitales, Clase N°8

21

Minimización por Mapas de Karnaugh

Ejemplo: En el siguiente mapa de Karnaugh obtenga la función mínima:

• a) agrupando “unos”• b) agrupando “ceros”• Demuestre que la función que la función resultante en ambos

casos es la misma. » Solución: agrupando “unos” tenemos:

00

bcacabf ab

1110

0100c 10110100

1

0

Sistemas Digitales, Clase N°8

22

Minimización por Mapas de Karnaugh

» Solución: agrupando “ceros” tenemos:

)()()( cbcabaf

OBS:

Al agrupar “ceros” la función mínima resultante es un Producto de Sumas.

1110

0100c 10110100

1

0

Sistemas Digitales, Clase N°8

23

Minimización por Mapas de Karnaugh

acbcabf

acbcbabf

acbcabcabf

bcacabcacbcabcababf

cbbcacabaf

cbcabaf

)1(

)()(

)()()(

Por lo tanto queda demostrado que la función mínima resultante es la misma.

Sistemas Digitales, Clase N°8

24

Minimización por Mapas de Karnaugh

Tarea:

Utilizando Mapas de Karnaugh, determine las expresiones mínimas en “Sumas de Productos” y Productos de Sumas” de las siguientes funciones:

)14,13,12,10,7,6,4,0(),,,()

)14,13,12,11,10,8,7,4,3(),,,()

zwyxfb

zwyxfa