Introducción

Diseño Lógico
Prof. Dr. Martín Vázquez
Un poco de historia…
 La historia de la computación está fuertemente relacionada
con la necesidad de la humanidad de contar o calcular

 A principios del siglo pasado existía una motivación muy

fuerte en la creación de dispositivos de cálculo.
Principalmente para uso militar

 Desarrollo de dispositivos tecnológicos que requerían uso intensivo de

cálculos.
 asociados a balística, a cohetes, a criptoanálisis, etc
 Uso intensivo de cálculos, resolución de ecuaciones muy complejas
 El cálculo era realizado por equipos de personas
 Un poco de historia…
Dispositivos mecánicos (basados en ruedas dentadas)

 1642 - Pascalina de Blaise Pascal (1623 - 1662).Considerada la primer

calculadora, podía resolver operaciones de adición y substracción.

 1674 - Máquina de Gottfried Leibniz (1646-1716). Permitía multiplicación y

división. Capaz de resolver ecuaciones algebraicas.

 Máquinas de calcular de Charles Babbage (1791-1871).

 (1820-1822) - Máquina diferencial. Automatizaba el proceso de creación de
tablas matemáticas usadas para los cálculos.
 1842. Diseño de máquina analítica.
 Incorporaba uso de tarjetas perforadas. Conceptos de “almacen” como memoria
y “molino” como unidad de cálculo
 No se alcanzó a fabricar
 Un poco de historia…
Dispositivos mecánicos (basados en ruedas dentadas)

Pascalina (1642)
Blaise Pascal
Máquina Analítica de Babbage (1842)
Sciense Museum Londres
 Un poco de historia…
Dispositivos electrónicos (basados en conmutadores)

 (1930-1950). Etapa inicial pionera de la computación

moderna
 Conceptos: aplicación del algebra de Boole a circuitos digitales
mediante conmutadores, sistema binario para operaciones
aritméticas, programa almacenado, entre otros.
 Investigadores relevantes: John Von Neumann (1903-1957),
AlanTuring (1912-1954), John Atanasoff (1903-1995), Claude
Shannon (1916-2001), entre otros.
 Dispositivos: Colossus (1943), ABC (1937-1942), ENIAC (1946),
calculadores Mark-I,II,III,IV (1945), EDVAC (1949).
 Un poco de historia…
Dispositivos electrónicos (basados en conmutadores)
 Mark I (ideas de H. Aiken y R. Stibitz)
 Ordenador electromecánico. Dimensiones 15.5m x 2.4m x 60cm. Tenía 800
Km. de cableado interno
 Reles, interruptores y secuencia de instrucciones mediante cintas perforadas
de papel.

Harvard-IBM Mark I (1944)

 Un poco de historia…
Dispositivos electrónicos (basados en conmutadores)
 ENIAC (Electronic Numerical Integrator and Computer).
 Poseía 17468 válvulas de vacío. Sup. 167 m2. Podía almacenar 20 números.
Alcanzaba los 50 ºC. Para programarla era necesario reconfigurar sus
circuitos.
 Se estima que en diez años realizó más cálculos matemáticos que los que
realizó la historia de la humanidad hasta entonces.

ENIAC (1946)
J. Mauchly y J. Eckert
 Un poco de historia…
Dispositivos electrónicos (basados en conmutadores)
 EDVAC (Electronic Discrete Variable Automatic Computer)
 Incorpora la Arquitectura de Von Neumann con programa almacenado
 20000 operaciones por segundo vs. 333 de ENIAC

John Von Neumann

(1903-1957)
 Un poco de historia…
Dispositivos electrónicos (basados en conmutadores)
 (1951-a la fecha). Generaciones de computadoras.
 Directamente relacionado a la miniaturización de los conmutadores

Tecnología 10 nm2
Válvulas de Vacío
Con cientos de millones de
Sup. aprox. 3 cm2
transistores (actualidad)
(1904)
 Un poco de historia…
Dispositivos electrónicos (basados en conmutadores)

 Primera Generación (1951-1958): Uso de válvulas de vacío. Utilización de

tarjetas perforadas. Tambores giratorios con marcas magnéticas para
almacenamiento primario.
 Segunda Generación (1959-1963): Uso de transistores en circuitos
impresos. Redes de núcleos magnéticos para almacenamiento.
Incrementaron las aplicaciones: tráfico aéreo, en empresas, etc.
 Tercera Generación (1964-1970): Circuitos integrados con miles de
componentes electrónicos. Mutiprogramación y minicomputadoras.
 Cuarta Generación (1971-a la fecha): Microminiaturización de los circuitos
electrónicos. Microprocesadores. Chips de Memoria. VLSI (Very Large
Scale Integration) GLSI (Giga Large Scale Integration). Desarrollo de
PCs.
 Más en la actualidad…
Dispositivos electrónicos (basados en conmutadores)
 VLSI (Very Large Scale Integration), ULSI (Ultra Large Scale Integration)
GLSI (Giga Large Scale Integration).
 Los GLSI contienen cientos de millones de transistores en un chip
Conmutadores

 Un conmutador es un dispositivo que se usa para

interrumpir la conexión de un circuito eléctrico o electrónico.

 Se maneja eléctricamente

 Utilizado para el diseño de computadoras

 Relés electromagnéticos, válvulas de vacío (1904),

transistores (1947).
Conmutadores

Válvula de vacío
(funciona como diodo)

Relés
electromagnéticos

Transistor
Aplicación del algebra de Boole

 En 1938, Claude Shannon publica un de trabajo de Maestría

“Análisis simbólico de los relés y los circuitos conmutadores”
 Aplicación del algebra de Boole al diseño y síntesis de circuitos
electrónicos

 Demostró que las operaciones booleanas NOT, AND y OR podían

representarse mediante circuitos conmutadores electrónicos

Claude Shannon (1916-2001)

Matemático e Ingeniero Eléctrico
Fundador de la Teoría de la Información
 Aplicación del algebra de
Boole
 En 1938, Claude Shannon publica su trabajo de Maestría
“Análisis simbólico de los relés y los circuitos conmutadores”
 Circuito entre dos terminales: abierto (infinita impedancia), cerrado
(impedancia cero).

 Símbolo Xab (más simple X). El símbolo 0 indica circuito cerrado, y el

símbolo 1 indica circuito abierto

Xab
a b
 Aplicación del algebra de
Boole

 En 1938, Claude Shannon publica su trabajo de Maestría

“Análisis simbólico de los relés y los circuitos conmutadores”

se encuentra abierto (1) cuando X

o Y están abiertos
X Y X+Y
=

X
X Y
=

Y se encuentra abierto (1) cuando X

e Y están abiertos
 Algebra de la lógica
 En1847 George Boole publica libro “Análisis matemático de
la lógica, ensayo de un cálculo de razonamiento deductivo”
 Lógica como una rama de las matemáticas

 Razonamientos lógicos sujetos a leyes matemáticas. Representados y

analizados como ecuaciones matemáticas.

 No opera sobre números, sino sobre clases de objetos, x2=x.

 Más tarde surge la lógica booleana de los silogismos. Representa

cada silogismo y su conclusión mediante una ecuación matemática.

George Boole (1815-1864)

Matemático y Lógico autodidacta
británico
 Algebra de Boole
 En 1860 en trabajos posteriores, aparece el concepto más
general de “Algebra de Boole” de Ch. Peirce (1839-1914) y
W. Stanley Jevons(1835-1882).
 Algebra de Boole es una estructura algebraica
 Conjunto B con dos elementos distinguibles: 0 y 1.
 Dado dos elementos x e y de B, se puede realizar:
 dos operaciones: x+y e x∙y.
 negación: x’ e y’

 Algebra de conjuntos y cálculo proposicional

 Son ejemplos de algebras de Boole.
 Satisfacen los axiomas y teoremas que caracterizan esta estructura
algebraica.
Algebra de Boole
Axiomas

 Conmutatividad:
x+y = y+x x∙y = y∙x

 Asociatividad:
x+(y+z) = (x+y)+z x∙(y∙z) = (x∙y)∙z

 Distributividad:
x+(y∙z) = (x+y)∙(x+z) x∙(y+z) = (x∙y)+(x∙z)

 Elemento Neutro:
x+0 = x x∙1 = x

 Complementario:
x+x´ = 1 x∙x´ = 0
Algebra de Boole
Teoremas

 Idempotencia:
x+x = x x∙x= x

 Absorción:
x+1 = 1 x∙0 = 0

 De Morgan:
(x+y)´ = x´∙y´ (x∙y)´ = x´+y´

 Complementario:
1´ = 0 0´ = 1

 Involución:
(x´)´ = x
Algebra de Boole
Diseño de Sistemas Digitales

 Para el diseño de circuitos se requieren compuertas

lógicas que representan funciones booleanas

 Funciones booleanas básicas

 Negación (NOT), conjunción (AND) y disyunción (OR)

 Otras funciones
 Negación de la disyunción (NOR), negación de la conjunción
(NAND), disyunción exclusiva (XOR),
Algebra de Boole
Diseño de Sistemas Digitales

x o
 La compuerta NOT
0 1
1 0

 La compuerta AND
x y o
0 0 0
0 1 0
1 0 0
1 1 1
Algebra de Boole
Diseño de Sistemas Digitales

x y o
 La compuerta OR
0 0 0
0 1 1
1 0 1
1 1 1

 La compuerta XOR x y o
0 0 0
0 1 1
1 0 1
1 1 0
Algebra de Boole
Diseño de Sistemas Digitales

 La compuerta NAND x y o
0 0 1
0 1 1
1 0 1
1 1 0

 La compuerta NOR x y o
0 0 1
0 1 0
1 0 0
1 1 0
Algebra de Boole
Funciones lógicas – Tablas de Verdad

 Cualquier función lógica se

puede describir mediante una
tabla de verdad

 Cualquier tabla de verdad se

puede describir mediante una
ecuación booleana
Algebra de Boole
Funciones lógicas – Tablas de Verdad

 Cualquier función lógica se x y z o

puede describir mediante una 0 0 0 1
tabla de verdad 0 0 1 0
 Cualquier tabla de verdad se 0 1 0 0
puede describir mediante una 0 1 1 1
ecuación booleana
1 0 0 0
 Sea la función booleana de tres 1 0 1 1
variables, o = f(x, y, z), se 1 1 0 1
obtiene la siguiente tabla
1 1 1 0
Algebra de Boole
Funciones lógicas – Tablas de Verdad

 Una estrategia es mediante x y z o

expresión disyuntiva canónica 0 0 0 1
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 0
Algebra de Boole
Funciones lógicas – Tablas de Verdad

 Una estrategia es mediante x y z o

expresión disyuntiva canónica 0 0 0 1
0 0 1 0
 Primero se consideran todas las
filas en donde se cumple la 0 1 0 0
función 0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 0
Algebra de Boole
Funciones lógicas – Tablas de Verdad

 Una estrategia es mediante x y z o

expresión disyuntiva canónica 0 0 0 1
0 0 1 0
 Primero se consideran todas las
filas en donde se cumple la 0 1 0 0
función 0 1 1 1
 Luego se obtiene : 1 0 0 0
1 0 1 1
o = x´∙y´∙z´ + x´∙y∙z + x∙y´∙z + x∙y∙z´ 1 1 0 1
1 1 1 0
Algebra de Boole
Funciones lógicas – Tablas de Verdad

 Una estrategia es mediante x y z o

expresión disyuntiva canónica 0 0 0 1
0 0 1 0
 Primero se consideran todas las
filas en donde se cumple la 0 1 0 0
función 0 1 1 1
 Luego se obtiene : 1 0 0 0
1 0 1 1
o = x´∙y´∙z´ + x´∙y∙z + x∙y´∙z + x∙y∙z´ 1 1 0 1
1 1 1 0
minterm
Algebra de Boole
Funciones lógicas – Tabas de Verdad

Implementación mediante compuertas lógicas

o = x´∙y´∙z´ + x´∙y∙z + x∙y´∙z + x∙y∙z´
x y z

o
Algebra de Boole
Funciones lógicas – Tablas de Verdad

 Otra estrategia es mediante x y z o

expresión conjuntiva canónica 0 0 0 1
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 0
Algebra de Boole
Funciones lógicas – Tablas de Verdad

 Otra estrategia es mediante x y z o

expresión conjuntiva canónica 0 0 0 1
0 0 1 0
 Primero se consideran todas las
filas en donde no se cumple la 0 1 0 0
función 0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 0
Algebra de Boole
Funciones lógicas – Tablas de Verdad

 Otra estrategia es mediante x y z o

expresión conjuntiva canónica 0 0 0 1
0 0 1 0
 Primero se consideran todas las
filas en donde no se cumple la 0 1 0 0
función 0 1 1 1
 Se obtiene o´= f(x,y,z)´, 1 0 0 0
1 0 1 1
o´ = x´∙y´∙z + x´∙y∙z´ + x∙y´∙z´ + x∙y∙z 1 1 0 1
1 1 1 0
Algebra de Boole
Funciones lógicas – Tablas de Verdad

o´ = x´∙y´∙z + x´∙y∙z´ + x∙y´∙z´ + x∙y∙z expresión disyuntiva

Algebra de Boole
Funciones lógicas – Tablas de Verdad

o´ = x´∙y´∙z + x´∙y∙z´ + x∙y´∙z´ + x∙y∙z expresión disyuntiva

o = (x´∙y´∙z + x´∙y∙z´ + x∙y´∙z´ + x∙y∙z )´

Algebra de Boole
Funciones lógicas – Tablas de Verdad

o´ = x´∙y´∙z + x´∙y∙z´ + x∙y´∙z´ + x∙y∙z expresión disyuntiva

o = (x´∙y´∙z + x´∙y∙z´ + x∙y´∙z´ + x∙y∙z )´

o = (x´∙y´∙z)´∙(x´∙y∙z´)´∙(x∙y´∙z´ )´∙(x∙y∙z)´ (De Morgan)

Algebra de Boole
Funciones lógicas – Tablas de Verdad

o´ = x´∙y´∙z + x´∙y∙z´ + x∙y´∙z´ + x∙y∙z expresión disyuntiva

o = (x´∙y´∙z + x´∙y∙z´ + x∙y´∙z´ + x∙y∙z )´

o = (x´∙y´∙z)´∙(x´∙y∙z´)´∙(x∙y´∙z´ )´∙(x∙y∙z)´ (De Morgan)

o = (x+y+z´)∙(x+y´+z)∙(x´+y+z)∙(x´+y´+z´) (De Morgan)

Algebra de Boole
Funciones lógicas – Tablas de Verdad

o´ = x´∙y´∙z + x´∙y∙z´ + x∙y´∙z´ + x∙y∙z expresión disyuntiva

o = (x´∙y´∙z + x´∙y∙z´ + x∙y´∙z´ + x∙y∙z )´

o = (x´∙y´∙z)´∙(x´∙y∙z´)´∙(x∙y´∙z´ )´∙(x∙y∙z)´ (De Morgan)

o = (x+y+z´)∙(x+y´+z)∙(x´+y+z)∙(x´+y´+z´) (De Morgan)

maxterm
Algebra de Boole
Funciones lógicas – Tablas de Verdad

o´ = x´∙y´∙z + x´∙y∙z´ + x∙y´∙z´ + x∙y∙z expresión disyuntiva

o = (x´∙y´∙z + x´∙y∙z´ + x∙y´∙z´ + x∙y∙z )´

o = (x´∙y´∙z)´∙(x´∙y∙z´)´∙(x∙y´∙z´ )´∙(x∙y∙z)´ (De Morgan)

o = (x+y+z´)∙(x+y´+z)∙(x´+y+z)∙(x´+y´+z´) (De Morgan)

maxterm

Expresión conjuntiva canónica

 Algebra de Boole
Funciones lógicas – Tablas de Verdad

x y z o
0 0 0 1
0 0 1 0
0 1 0 0
o = (x+y+z´)∙(x+y´+z)∙(x´+y+z)∙(x´+y´+z´) 0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 0
Componentes Lógicos
Multiplexor

Multiplexor de dos entradas de un bit

s
x s=0
x 0
o o=
y 1
y s=1
MUX2_1
Componentes Lógicos
Multiplexor

Multiplexor de dos entradas de un bit

s
x s=0
x 0
o o=
y 1
y s=1
MUX2_1

o = x∙s´ + y∙s
Componentes Lógicos
Multiplexor

Multiplexor de dos entradas de un bit

s s
x 0 x
o
y 1 o
y
MUX2_1

o = x∙s´ + y∙s
Componentes Lógicos
Demultiplexor

Demultiplexor de dos salidas de un bit

x s=0
s
o1 =
0 o1
0 s=1
x
1 o2

DMUX2_1 x s=1
o2 =
0 s=0
Componentes Lógicos
Demultiplexor

Demultiplexor de dos salidas de un bit

x s=0
s
o1 =
0 o1
0 s=1
x
1 o2

DMUX2_1 x s=1
o2 =
0 s=0
o1 = x∙s´
o2 = x∙s
Componentes Lógicos
Demultiplexor

Demultiplexor de dos salidas de un bit

s
x
0 o1 o1
s
x
1 o2
o2
DMUX2_1

o1 = x∙s´
o2 = x∙s
Componentes Lógicos
Multiplexor

Multiplexor de cuatro entradas de un bit

s 2

s0 s1
s 2

x1 0 x1
x2 1
o
x3 2 x2
x4 3 o

MUX4_1 x3

x4
Componentes Lógicos
Multiplexor

Implementación de un MUX4_1 utilizando MUX2_1

s 2
s0 s1
x1 0

x2 1
0
o
1
x3 0

x4 1

TMUX4_1 = 2*TMUX2_1 = 2*(TAND+TOR)

CMUX4_1 = 3*CMUX2_1 = 3*COR + 6*CAND

Componentes Lógicos
Multiplexor

Implementar:

 Multiplexor de 8 entradas de un bit (MUX8_1) utilizando

MUX2_1
Componentes Lógicos
Multiplexor

s 3
s0 s1 s2
x1 0

x2 1
0

1
x3 0
TMUX8_1 = 3*TMUX2_1 = 3*(TAND+TOR)
x4 1
0
o CMUX8_1 = 7*CMUX2_1 = 7*COR + 14*CAND
1
x5 0

x6 1
0

1
x7 0

x8 1

MUX8_1 utilizando MUX2_1

Componentes Lógicos
Multiplexor

Tiempo y costo (área) de un MUXm_1 utilizando MUX2_1, con m=2i

TMUXm_1 = i*TMUX2_1 = i*(TAND+TOR)

CMUXm_1 = (2i-1)*CMUX2_1 = (2i-1)*COR + (2i+1-2)*CAND

 Componentes Lógicos
Multiplexor
Implementación de un multiplexor de 2 entradas de 8 bits, utilizando
MUX2_1 y x s o
8 8 8
x0
0 o0
y0
s 1

x 0 x1
8 0 o1
8
o y1
y 8
1 1

MUX2_8

x7
0 o7
y7
1
 Componentes Lógicos
Multiplexor
Implementación de un multiplexor de 2 entradas de 8 bits, utilizando
MUX2_1 y x s o
8 8 8
x0
0 o0
y0
s 1

x 0 x1
8 0 o1
8
o y1
y 8
1 1

MUX2_8

TMUX2_8 = TMUX2_1 = TAND+TOR x7

0 o7
y7
CMUX2_8 = 8*CMUX2_1 = 8*COR + 1
Componentes Lógicos
Multiplexor

Implementar:

 Multiplexor de 8 entradas de 8 bits (MUX8_8), utilizando

MUX2_8
Componentes Lógicos
Multiplexor
s 3
s0 s1 s2
x1 8
0

x2 8
1
0

1
x3 8
0

x4 8
1
0
8 o
1
x5 8
0

x6 8
1
0

1
x7 8
0

x8 8
1

MUX8_8 utilizando MUX2_8

Componentes Lógicos
Multiplexor

Determinar:

 Tiempo de cálculo y costo (área) de un MUX8_8 utilizando

MUX2_1

 Hallar expresión genérica de tiempo y área de un MUXm_n

utilizando MUX2_1, con m = 2i
Componentes Lógicos
Demultiplexor
Demultiplexor de cuatro salidas de un bit

s 2
s0 s1

s o1
2 x
0 o1
1 o2 o2
x
2 o3
3 o4 o3

DMUX4_1
o4
Componentes Lógicos
Multiplexor

Implementar:

 DMUX4_1 utilizando DMUX2_1

 DMUX8_1 utilizando DMUX2_1

 DMUX2_8 utilizando DMUX2_1

 DMUX8_8 utilizando DMUX2_8

Componentes Lógicos
Decodificador

x2..0 o7..0
000 00000001
001 00000010
010 00000100
x 3 8
o
011 00001000
100 00010000
101 00100000
DECODE3
110 01000000
111 10000000
Componentes Lógicos
Decodificador
x0x1x2

o0
o1
o2
x 3 8
o o3

o4

DECODE3 o5
o6

o7
 Componentes Lógicos
Decodificador

El Decodificador se puede implementar con un Demultiplexor

x 2

0 o0
1 o1
x 2 4
o 1
2 o2
3 o3
DECODE2
DECODE2