Fundamentos de los Computadores. Sistemas Combinacionales

T4-1

TEMA 4. Diseño de Sistemas Combinacionales SSI. INDICE: • SISTEMAS COMBINACIONALES • METODOLOGÍA DE DISEÑO • MÉTODOS DE SIMPLIFICACIÓN o MAPAS DE KARNAUGH • EXPRESIÓN MÍNIMA EN FORMA DE SUMA DE PRODUCTOS • EXPRESIÓN MÍNIMA EN FORMA DE PRODUCTO DE SUMAS • EXPRESIÓN MÍNIMA PARA FUNCIONES INCOMPLETAS

Maurice Karnaugh (1924-)

Fundamentos de los Computadores. Sistemas Combinacionales

T4-2

SISTEMAS COMBINACIONALES LOS SISTEMAS COMBINACIONALES SON AQUELLOS EN LOS QUE EN CADA INSTANTE, EL ESTADO LÓGICO DE SU SALIDA DEPENDEN ÚNICA Y EXCLUSIVAMENTE DE SUS ENTRADAS. UN SISTEMA COMBINACIONAL PUEDE TENER MÚLTIPLES SALIDAS. CADA SALIDA DEBE REPRESENTARSE POR UNA FUNCIÓN LÓGICA DIFERENTE. EL DISEÑO DE SISTEMAS COMBINACIONALES SE REALIZA MEDIANTE EL USO CIRCUITOS ELECTRÓNICOS: • SSI (SMALL SCALE OF INTEGRATION) QUE CONTIENEN UN NÚMERO PEQUEÑO DE PUERTAS BÁSICAS. • MSI (MEDIUM SCALE OF INTEGRATION) DÓNDE EL NÚMERO DE PUERTAS BÁSICAS PUEDE LLEGAR A 100. SON BLOQUES CONSTRUCTORES MÁS COMPLEJOS. • LSI (LARGE SCALE OF INTEGRATION ~1000). ALGUNOS SISTEMAS YA PROGRAMABLES. • VLSI (VERY LARGE SCALE OF INTEGRATION >1000). ALGUNOS PROCESAORES. • ULSI (ULTRA LARGE SCALE OF INTEGRATION >100000). ÚLTIMAS TECNOLOGÍAS. • ...

• EL DISEÑO DE SISTEMAS COMBINACINALES SSI, SE REALIZA CON PUERTAS BÁSICAS.

Fundamentos de los Computadores. Sistemas Combinacionales

T4-3

METODOLOGÍA DE DISEÑO 1. EL DISEÑO SE REALIZA A PARTIR DEL PLANTEAMIENTO DE UN PROBLEMA. 2. SE OBTIENE PRIMERO LA TABLA DE VERDAD DE CADA UNA DE LAS SALIDAS Y, OPCIONALMENTE, LAS EXPRESIONES CANÓNICAS. 3. LUEGO SE PROCEDE A LA SIMPLIFICACIÓN PARA OBTENER UNA EXPRESIÓN BOOLEANA MÍNIMA PARA CADA FUNCIÓN. 4. POR ÚLTIMO SE REALIZA EL DIAGRAMA LÓGICO Y EL CIRCUITO DE MÍNIMO TAMAÑO. Ejemplo: Para abrir una caja fuerte se dispone de tres llaves, la caja se abre si: • Están giradas A y B independientemente de si lo está C. • Cuando estando girada C, estén giradas A o B. TABLA DE VERDAD: C

B

A

F(C,B,A)

0

0

0

0

0

0

1

0

0

1

0

0

0

1

1

1

1

0

0

0

1

0

1

1

1

1

0

1

1

1

1

1

EXPRESIÓN CANÓNICA

F(C,B,A) = C’BA + CB’A + CBA’ + CBA

F(C,B,A) = m3 + m5 + m6 +m7 = Σ m(3,5,6,7)

Fundamentos de los Computadores. Sistemas Combinacionales

T4-4

MÉTODOS DE SIMPLIFICACIÓN (I) CRITERIOS: 1. MENOR NÚMERO DE TÉRMINOS EQUIVALEN A PUERTAS LÓGICAS)

EN

LA

FUNCIÓN

(QUE

2. MENOR NÚMERO DE VARIABLES EN CADA TÉRMINO (QUE EQUIVALEN A ENTRADAS DE LAS DIVERSAS PUERTAS) 3. MENOR VALOR ASOCIADO: Nº_TÉRMINOS+Nº_VARIABLES–Nº_TÉRMINOS_CON_UN_SOLO_LITERAL-1

MÉTODOS: SIMPLIFICACIÓN ALGEBRAICA, APLICANDO DIRECTAMENTE EL ÁLGEBRA DE BOOLE. ES ÚTIL PARA FUNCIONES CON POCAS VARIABLES. EJEMPLO: F(C,B,A)= C’BA + CB’A + CBA’ + CBA

F(C,B,A)= BA + CA + CB SIMPLIFICACIÓN TABULAR, MEDIANTE TABLAS Y MAPAS QUE REPRESENTAN LA TABLA DE VERDAD. ÚTIL PARA FUNCIONES CON HASTA CINCO O SEIS VARIABLES. EL MÉTODO MÁS USUAL ES EL MAPA DE KARNAUGH. SERÁ EL ÚNICO QUE SE APLIQUE EN ESTA ASIGNATURA. Y SE EXPLICARÁ A CONTINUACIÓN. SIMPLIFICACIÓN NUMÉRICA DE QUINE-McCLUSKEY, QUE PERMITE ESCOGER DE TODAS LAS SIMPLIFICACIONES POSIBLES DE UNA FUNCIÓN, LA QUE PUEDA SER IMPLEMENTADA CON EL MENOR NÚMERO DE ELEMENTOS. SE USA PARA FUNCIONES CON MUCHAS VARIABLES Y/O MULTISALIDAS.

Fundamentos de los Computadores. Sistemas Combinacionales

T4-5

MÉTODOS DE SIMPLIFICACIÓN (II) MAPAS DE KARNAUGH ES UN DIAGRAMA DE CUADROS O CELDAS DÓNDE CADA UNA DE ELLAS REPRESENTA UNA LÍNEA DE LA TABLA DE VERDAD DE LA FUNCIÓN, O SEA, UN MINTÉRMINO O UN MAXTÉRMINO.

(0) (1) (2) (3) (4)

D 0 0 0 0 0 •

C 0 0 0 0 1 •

B 0 0 1 1 0 •

A 0 1 0 1 0 •

F

CD

AB 00 01 11 10

00

01

11 10

(0)

(2)

(3)

(1)

(8)

(10)

(11)

(9)

(12)

(14)

(15)

(13)

(4)

(6)

(7)

(5)

LA PRINCIPAL CARACTERÍSTICA DEL MAPA ES QUE LAS CELDAS ADYACENTES FÍSICAMENTE, CORRESPONDEN A TÉRMINOS ADYACENTES LÓGICAMENTE, O SEA, LA DIFERENCIA ENTRE UNA CELDA Y LAS ADYACENTES ES EL CAMBIO EN UNA Y SOLO UNA DE LAS VARIABLES.

Celda (2) 0010 D’C’BA’

Celda (8) 1000 DC’B’A’

Celda (10) 1010 DC’BA’

Celda (14) 1110 DCBA’

Celda (11) 1011 DC’BA

Fundamentos de los Computadores. Sistemas Combinacionales

T4-6

EXPRESIÓN MÍNIMA EN FORMA DE SUMA DE PRODUCTOS 1. MARCAMOS EN EL MAPA UN 1 EN CADA MINTÉRMINO QUE REPRESENTA LA FUNCIÓN. 2. MEDIANTE RECTÁNGULOS HACEMOS AGRUPACIONES DE 1s ADYACENTES. ESTOS RECTÁNGULOS PUEDEN CONTENER UN NÚMERO DE 1s CORRESPONDIENTE A POTENCIAS DE 2, O SEA, 1, 2, 4, 8,... . 3. SE DEBEN ESCOGER EL MENOR NÚMERO DE RECTÁNGULOS PERO QUE CONTENGAN EL MAYOR NÚMERO DE 1s, DE MANERA QUE TODOS LOS 1s QUEDEN CUBIERTOS. 4. PARA OBTENER LA EXPRESIÓN, CADA RECTÁNGULO REPRESENTA UN PRODUCTO. LA VARIABLE QUE CAMBIE DE VALOR DENTRO DEL RECTÁGULO QUEDA ELIMINADA. EL PRODUCTO SE OBTIENE ASIGNANDO LA VARIABLE VERDADERA AL 1 Y LA NEGADA AL 0. La agrupación de las celdas 10 y 14, eliminaría la variable C y el producto resultante sería DBA’. 5. LA EXPRESIÓN MÍNIMA ES LA SUMA DE LOS PRODUCTOS RESULTANTES DE CADA RECTÁNGULO. EJEMPLO: Simplificar la función F(D,C,B,A) = Σm(0,1,2,4,5,6,8,9,12,13,14). CD

AB 00 01 11 10

00

1 1 1 1

01 (0) (8)

(12) (4)

1 1 1

11 (2)

(3)

(10)

(11)

(14)

(15)

(6)

(7)

Hemos formado 3 rectángulos: {(0),(8),(12),(4),(1),(9),(13),(5)} {(0),(2),(4),(6)} {(12),(14),(4),(6)} POR TANTO

D’A’ CA’

F = D’A’ + CA’ + B’

B’

10

1 1 1 1

(1) (9) (13) (5)

Fundamentos de los Computadores. Sistemas Combinacionales

T4-7

EXPRESIÓN MÍNIMA EN FORMA DE PRODUCTO DE SUMAS 1. MARCAMOS EN EL MAPA UN 0 EN CADA MAXTÉRMINO QUE REPRESENTA LA FUNCIÓN. 2. MEDIANTE RECTÁNGULOS HACEMOS AGRUPACIONES DE 0s ADYACENTES. ESTOS RECTÁNGULOS PUEDEN CONTENER UN NÚMERO DE 0s CORRESPONDIENTE A POTENCIAS DE 2, O SEA, 1, 2, 4, 8,... . 3. SE DEBEN ESCOGER EL MENOR NÚMERO DE RECTÁNGULOS PERO QUE CONTENGAN EL MAYOR NÚMERO DE 0s, DE MANERA QUE TODOS LOS 0s QUEDEN CUBIERTOS. 4. PARA OBTENER LA EXPRESIÓN, CADA RECTÁNGULO REPRESENTA UNA SUMA. LA VARIABLE QUE CAMBIE DE VALOR DENTRO DEL RECTÁGULO QUEDA ELIMINADA. LA SUMA SE OBTINE ASIGNANDO LA VARIABLE VERDADERA AL 0 Y LA NEGADA AL 1. La agrupación de las celdas 10 y 14, eliminaría la variable C y la suma resultante sería (D’+B’+A). 5. LA EXPRESIÓN MÍNIMA ES EL PRODUCTO DE LAS SUMAS RESULTANTES DE CADA RECTÁNGULO. EJEMPLO: Simplificar la misma función F(D,C,B,A) = ΠM(3,7,10,11,15). CD

AB 00 01 11 10

00

01 (0) (8)

0

11

(2) (10)

(12)

(14)

(4)

(6)

0 0 0 0

10

(3)

(1)

(11)

(9)

(15)

(13)

(7)

(5)

Hemos formado 2 rectángulos: {(3),(11),(15),(7)} {(10),(11)} POR TANTO

(B’ + A’)

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

Se puede comprobar que es la misma función F = (D’+C+B’)(B’+A’) = D’B’+D’A’+CB’+CA’+B’+B’A = B’+D’A’+CA’

Fundamentos de los Computadores. Sistemas Combinacionales

T4-8

EXPRESIÓN MÍNIMA PARA FUNCIONES INCOMPLETAS 1. PARA FUNCIONES INCOMPLETAS, AQUELLAS QUE NO ESTÁN DEFINIDAS PARA ALGUNAS COMBINACIONES DE LAS VARIABLES DE ENTRADA, MARCAMOS EN EL MAPA DE KARNAUGH UNA X EN EL LUGAR CORRESPONDIENTE A LA INESPECIFICACIÓN. 2. ESTAS X PODEMOS CONSIDERARLAS 0s Ó 1s Y PROCEDER COMO EN LOS CASOS ANTERIORES. 3. SOLO ES NECESARIO CUBRIR TODOS LOS 0s Ó TODOS LOS 1s, LAS INESPECIFICACIONES SÓLO DEBEN COGERSE PARA QUE EL RECTÁNGULO CONTENGA UN NÚMERO MAYOR DE TÉRMINOS. EJEMPLO: Simplificar la función F(D,C,B,A) = Σm(0,2,12,14) + Φ (5,6,7,8,9,10). CD

AB 00 01 11 10

00

1 X 1

01

(0) (8) (12) (4)

1 X 1 X

11 (2)

(3)

(10)

(11)

(14)

(15)

(6)

X

(7)

10

X X

(1) (9) (13) (5)

Hemos formado 2 rectángulos: {(0),(2),(8),(10)} {(8),(10),(12),(14)} POR TANTO

C’A’ DA’

F = DA’ + C’A’

COMO SE VE, HEMOS TRATADO LAS INESPECIFICACIONES (8) Y (10) COMO 1s Y EL RESTO COMO 0s.

Fundamentos de los Computadores. Sistemas Combinacionales

T4-9

MÁS MAPAS: PARA FUNCIONES DE 2 Y 3 VARIABLES: F(B,A) B

A

0

0 1

F(C,B,A)

1

BC

(0)

(1)

(2)

(3)

A

0

00 01 11 10

1

(0)

(1)

(4)

(5)

(6)

(7)

(2)

(3)

C

AB

00 01 11 10

0 1

(0)

(2)

(3)

(1)

(4)

(6)

(7)

(5)

PARA FUNCIONES DE 5 VARIABLES: F(E,D,C,B,A)

CD

AB 00 01 11 10

E=0 00 01 11 10

CD

(0)

(2)

(3)

(1)

(8)

(10)

(11)

(9)

(12)

(14)

(15)

(13)

(4)

(6)

(7)

(5)

AB 00 01 11 10

E=1 00 01 11 10 (16)

(18)

(19)

(17)

(24)

(26)

(27)

(25)

(28)

(30)

(31)

(29)

(20)

(22)

(23)

(21)

EJEMPLO DE SIMPLIFICACIÓN DE FUNCIONES CON 5 VARIABLES: F(E,D,C,B,A) = Σm(0,2,3,6,7,9,11,13,15,16,25,27,29,31)

CD

E=0

AB

00

1

00 01 11 10

(0)

01

1

(2)

(8)

(10)

(12)

(14)

(4)

1

(6)

11

1 1 1 1

(3) (11) (15) (7)

10

1 1

(1) (9) (13) (5)

CD

AB 00 01 11 10

E=1 00

1

(16) (24)

(26)

(28)

(30)

(20)

(22)

D’C’B’A’

{(2),(3),(6),(7)}

E’D’B

{(11),(9),(15),(13),(27),(25),(31),(29)} POR TANTO

F = DA + E’D’B + D’C’B’A’

11

10

(18)

Hemos formado 3 rectángulos: {(0),(16)}

01

DA

1 1

(19) (27) (31) (23)

1 1

(17) (25) (29) (21)