electrónica digital unidad iii

Electrónica DigitalUnidad III

Ing. Raúl V. Castillo C.

Lógica Booleana

Ing. Raúl V. Castillo Carrillo

Introducción

El Álgebra de Boole es una herramienta matemática que permite modelar y diseñar los llamados Sistemas Digitales.

Fue desarrollada por el matemático ingles George Boole (1815-1864) y propuesta en sus libros "The Mathematical Analysis of Logic" El Análisis Matemático de Lógica (1847) y "An Investigation of the Laws of Thought" “Una Investigación sobre las Leyes del Pensamiento” (1854).

Claude Shannon fue el primero en aplicarla en el diseño de circuitos de conmutación eléctrica biestables, en 1948

Introducción

El Algebra de Boole es importante pues permite representar matemáticamente el funcionamiento de los circuitos digitales. Los circuitos digitales son capaces de permanecer en 2 estados, a saber, encendido y apagado, presencia o ausencia de energía.

Estos dos estados son representados matemáticamente por los valores 1 y 0.

Introducción

Postulados de HUNTINGTON

Para sustentar la estructura algebraica propuesta por Boole y definir las operaciones entre los elementos del álgebra, es necesario establecer una serie de postulados básicos.

Un conjunto de postulados fue propuesto por Huntington en 1904, que definen básicamente la relación de equivalencia, y las operaciones de unión, intersección y complementación y sus propiedades

Introducción

• Equivalencia y sus propiedades

Existe un conjunto N de n elementos sujetos a una relación de equivalencia representada por el símbolo “=”, la cual satisface las siguiente propiedades.

Nombre de la Propiedad Significado

Reflexiva a = a

Simétrica a = b entonces b = a

Transmutativa Si a = b y b = c, entonces a = c

Sustitución Si a = b, entonces a puede reemplazarse por b en cualquier

parte de una expresión, sin cambiar la validez de la expresión

Introducción

• Definición de operación Unión e Intersección

Se define la operación “UNION ” representada por el símbolo “” tal que:

Si a y b N entonces a b N

Se define la operación “INTERSECCIÓN” representada por el símbolo “” tal que:

Si a y b N entonces a b N

Introducción

• Definición de elemento neutro de la unión y elemento neutro en la intersección.

(a) Existe un elemento “0” en N tal que:

Si a N entonces a 0 = a

(b) Existe un elemento “1” en N tal que:

Si a N entonces a 1 = a

Introducción

• Propiedades de la Unión y la Intersección .

Si a, b, c N entonces

Nombre Propiedad Unión Intersección

Conmutativa a b = b a a b = b a

Distributiva a (b c) = a (b c) =

=(a b) (a c) =(a b) (a c)

Introducción

• Existencia del complemento y sus propiedades.

Si a N entonces existe un elemento (complemento de a, no a) N tal que

• Cantidad mínima de elementos del conjunto N

Existen por lo menos 2 elementos a y b N tales que a ≠ b.

Observación importante: Es posible verificar que el conjunto N = {0,1} cumple con los postulados de Huntington.

a

1aa

0aa

Axiomas Básicos

El Álgebra de Boole es un sistema matemático cerrado que consiste en un conjunto N de dos o más elementos y dos operaciones llamadas: OR (+) y AND ()

y que cumplen los siguientes axiomas:

• Conmutatividad

ABBA

ABBA

N BA,

Axiomas Básicos

• Asociatividad

•Distributividad

CBACBA

CBACBA

N CB,A,

Axiomas Básicos

CABACBA

CABACBA

N CB,A,

• Existen elementos neutros 0 y 1

•Existencia de Complemento

A1A

A0A

N A

Axiomas Básicos

0AA

1AA

N A

• Postulado de Huntington : Considera al conjunto N como

El Postulado de Huntington define un caso especial del Álgebra de Boole llamada Álgebra de Conmutación. De aquí en adelante es ésta álgebra la que se utiliza para la modelación de los sistemas digitales.

1,0N

Álgebra de Conmutación

Definiciones

• Variable: Son símbolos que pueden representar cualquier valor de P. El valor de las variables puede cambiar en el transcurso del tiempo. El concepto es igual a variables de los lenguajes de programación.

A

AccionarAlarma

Definiciones

• Constante: Son símbolos que representan sólo un valor de P para cualquier instante de tiempo. Su concepto es igual a constantes de los lenguajes de programación.

1

AccionarAlarma

Constante

Definiciones

• Expresión de Conmutación: Es una combinación de un número finito de variables y constantes relacionadas mediante operaciones OR y AND. Para simplificar el uso de paréntesis se aplican reglas de procedencia de operadores al igual que las expresiones del álgebra normal, considerando el OR como suma y el AND como producto.

Ejemplo:

DDBCBA 0

Definiciones

• Literal: Es toda ocurrencia de una variable, ya sea complementada o sin complementar en una expresión de conmutación.

Ejemplo:

Existen 4 variables: A, B, C y D

Existen 6 literales:

DDBCBA 0

DDBCBA y , , , ,

Definiciones

• Expresión Dual: Es la expresión que se obtiene intercambiando las operaciones AND por OR, OR por AND y las constantes 0 por 1 y 1 por 0 en una expresión de conmutación.

Ejemplo:

10 CBACBADual

Teoremas

• De los axiomas anteriores se desprenden un conjunto de teoremas. La forma de demostración es:

Aplicando axiomas

Por inducción

• Se verán un conjunto de teoremas que sirven para trabajar con las expresiones de conmutación dándoles un sentido práctico.

Teoremas

• Teorema 1: Operaciones básicas

1+0=1 11=10+0=0 01=0

Se demuestra aplicando el Axioma 4

A+0=A A1=A

Teoremas

• Teorema 2: Operaciones básicas

A+1=1 A0=0

Se demuestra aplicando el Axioma 4

Luego 0+1=1 y 1+1=1

111

1111

AAAAA

AAAAA

Operaciones AND, OR y NOT

• AND OR00=0 0+0=001=0 0+1=110=0 1+0=111=1 1+1=1

NOT

01

10

Teoremas

• Teorema 3: El Complemento de A es único.Supongamos que existen dos complementos para A: A1 y A2.

A+A1=1 A+A2=1 AA1=0 AA2=0 A1=A11=A1(A+A2)=A1A+A1A2

A1=0+A2A1

A1=AA2+A1A2=(A+A1) A2

A1=A2

Teoremas

• Teorema 4: El Complemento de A es A.

• Teorema 5

A+A=A AA=A

Se demuestra por inducción comprobando exhaustivamente todas las combinaciones.

Teoremas

• Teorema 6: Absorción.

A+AB=A A(A+B)=A

Demostración:

A+AB=(A1)+(AB)=A(1+B)=A

Teoremas

• Teorema 7: Simplificación.

A+AB=A+B A(A+B)=AB

Demostración:

A+A=1 En ambos lados se hace una AND con BAB+AB=B En ambos lados se hace una OR con A

AB+A+AB=A+BA(1+B)+AB=A+B

A+AB=A+B

Teoremas

• Teorema 8: Teorema de De Morgan.

A+B+C+D…=ABCD… AB CD… =A+B+C+D+…

La demostración se hace por inducción:

A=B=C=D=…=0 0+0+0+….=0=1A=B=C=D=…=1 1+1+1+….=1=0

1+0+X=1=0

Teoremas

• El Teorema de De Morgan establece que para obtener el complemento de una expresión, se debe complementar cada variable e intercambiar las operaciones OR y AND y las constantes 1 y 0.

Ejemplo:

A(B+C)=A+BC

• Definición: Una función de conmutación es una aplicación f: Pn P

Cada elemento x Pn es un conjunto de variables de P x=(x1, x2, …, xn). A este conjunto de variables se le denomina n-tupla.Una función de conmutación es completamente especificada cuando asigna un valor (0 o 1) a todos los posibles valores de sus variables. En otro caso, la función es incompletamente especificada.

Funciones de conmutación

• Representación de funciones de conmutaciónExisten varias formas de representar una función de conmutación:

expresión tabla de verdad mapa circuito

Existen funciones de conmutación completamente especificadas de n variables.

Funciones de conmutación

n22

Representación de funciones de conmutación

Ejemplo:F(x, y, z)=xy+xz+yz

x y z f(x, y, z)0 0 0 00 0 1 00 1 0 00 1 1 11 0 0 01 0 1 11 1 0 11 1 1 1

0 0 1 00 1 1 1

00 01 11 10

0

1

xyz

f

xy

zf

La forma más intuitiva de representar una función de conmutación es por medio de una Tabla de Verdad.

La Tabla de Verdad expresa el valor de salida de una función para cada combinación de entrada.

La Tabla de Verdad permite modelar un tipo especial de sistema Digital llamado Sistema Combinacional.

Tabla de Verdad

Tabla de Verdad

Ejemplo:

Tabla de Verdad:

x1 x2 x3 f0 0 0 00 0 1 00 1 0 10 1 1 01 0 0 11 0 1 11 1 0 11 1 1 0

Formas Canónicas

Problema: Dada una Tabla de Verdad, obtener la forma algebraica

x1 x2 x3 f0 0 0 00 0 1 00 1 0 10 1 1 01 0 0 11 0 1 11 1 0 11 1 1 0

x1x2 x3

x1 x2x3 x1 x2x3 x1 x2x3

Formas Canónicas

La forma algebraica queda:

f(x1, x2, x3)=x1x2 x3 + x1 x2x3 + x1 x2x3 + x1 x2x3

Para convertir se observa la combinación de entrada para la cual la salida toma el valor 1. La variable aparece sin complementar si vale 1 para la combinación en la cual la salida vale 1 y aparece complementada si vale 0 para la combinación en la cual la salida toma el valor 1.

Formas Canónicas: Minitérminos

Se denomina minitérmino a un factor de una expresión booleana a que está formado por el AND de todas las variables.

Una función de conmutación corresponde al OR de minitérminos. La función generada de esta manera se denomina OR canónico de AND.

f(x1, x2, x3)=OR( m0, m1, …, mn )

f(x1, x2, x3)=( m0, m1, …, mn )

Formas Canónicas: Minitérminos

Para el ejemplo anterior:

f(x1, x2, x3)=OR( 2, 4, 5, 6 )

f(x1, x2, x3)=(2, 4, 5, 6 )

Formas Canónicas: Maxitérminos

(x1+x2+ x3)

(x1+ x2+x3)

(x1+ x2+x3)

(x1+ x2+x3)

Una forma alternativa de expresar la función es examinando las combinaciones en las cuales vale 0.

x1 x2 x3 f0 0 0 00 0 1 10 1 0 00 1 1 11 0 0 01 0 1 11 1 0 11 1 1 0


La función queda ahora:

f(x1, x2, x3)=(x1+x2+ x3 )(x1+ x2+x3 )( x1+ x2+x3 )( x1+ x2+x3 )

Para convertir se observa la combinación de entrada para la cual la salida toma el valor 0. La variable aparece sin complementar si vale 0 para la combinación en la cual la salida vale 0 y aparece complementada si vale 1 para la combinación en la cual la salida toma el valor 0.


Se denomina maxitérmino a un factor de una expresión booleana a que está formado por el OR de todas las variables.

Una función de conmutación corresponde al AND de maxitérminos. La función generada de esta manera se denomina AND canónico de OR.

f(x1, x2, x3)=AND( M0, M1, …, Mn )

f(x1, x2, x3)=( M0, M1, …, Mn )


Para el ejemplo anterior:

f(x1, x2, x3)=AND( 0, 2, 4, 7 )

f(x1, x2, x3)=( 0, 2, 4, 7 )

Conversión entre Formas Canónicas

Problema: dada una función en OR canónico de AND, obtener la forma canónica AND canónico de OR

F(A, B, C)=( 0, 1, 2, 7 )

F(A, B, C)=( 3, 4, 5, 6 )=ABC+ ABC+ABC+ ABC

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

F(A, B, C)=( 3, 4, 5, 6 )

Funciones Equivalentes

Dos funciones de conmutación son equivalentes cuando sus expansiones en formas canónicas son idénticas, es decir tienen el mismo valor de salida para las mismas combinaciones de entradas.

Una forma similar de expresar lo mismo es que dos funciones de conmutación son equivalentes cuando tienen la misma Tabla de Verdad

Funciones Equivalentes

¿Cuántas funciones de n variables existen?

La respuesta a esta pregunta se encuentrafácilmente preguntando: ¿Cuántas Tablasde Verdad existen con n variables?

La respuesta está en observar la columna de salida. El número de funciones es:

n22

Funciones de una y dos variables

F(x)=x NOT

F(x, y)=xy AND

F(x, y)=x+y OR

F(x, y)=x+y NAND

Funciones de una y dos variables

F(x)=x y NOR

F(x, y)=xy+ xy OR EXCLUSIVO

F(x, y)= xy+ x y AND EXCLUSIVO

Ejercicio: Construir las Tablas de Verdad de estas funciones.

Lógica Combinacional

Lógica Combinacional contra la Lógica SecuencialRepresentación de entradas/salidas de circuitos lógicos:

Circuitos de lógica combinacional: La salida depende solo de las entradas actuales. La relación de entrada/salida esta descrita por una tabla de verdad.

Circuitos de lógica secuencial: La salida depende de las entradas actuales y de las salidas previas. La relación de entrada/salida esta descrita por una tabla de estados.

Circuito LógicoX

Y

Z

F SalidaEntradas

Diversificación de las compuertas

Compuertas Lógicas

Una forma alternativa de representar funciones es mediante Compuertas Lógicas. Las Compuertas Lógicas se construyen físicamente con electrónica integrada en sustratos de silicio.

El éxito de los sistemas digitales se debe en gran medida al bajo costo por compuerta que se logra con este proceso y a la alta densidad de integración, llegando en la actualidad a millones de compuertas en un circuito integrado cuya área no sobrepasa 1cm2.

Compuertas Lógicas

Una red de compuertas lógicas se denomina circuito combinacional. Los circuitos combinacionales constituyen una parte importante de una CPU moderna.

ALU CPU

Compuertas Lógicas

A

B

A+B

A A

A

B

AB A

B

AB

A

B

A+B

A

B

AB

AND NAND

OR NOR

NOT OR-EX

Compuertas Lógicas: Ejemplo

F(A, B, C, D)

CA

B

D

F(A, B, C, D)=AC+ABC+ABCD

Implementación de Funciones con Compuertas

Redes con AND, OR y NOT

Una vez que se define la suma de productos mínima se debe de definir el diagrama lógico, compuesto por una red de compuertas que describan la función.

Ejemplo de un circuito de dos niveles

zyxzyxyzxzyxf X

Y

Z

X

Y

Z

X

Y

Z

X

Y

Z

Niveles

El número de niveles corresponde al máximo número de compuertas que una señal debe pasar desde su entrada hasta la salida.

En el caso anterior tenemos dos niveles, esto asumiendo que tenemos disponibles en la entradas los complementos de la literales, cuando no se dispone de los complementos es necesario complementar con compuertas NOT.

Problema

xyzzyxzyxyzxzyxf

a) Diagrama de la suma de productosb) Diagrama de la suma de productos mínimo

Una red multinivel

)( wxzvyxwzh

Las redes multinivel son el resultado de implementar funciones que no esténen la forma ni de suma de productos ni de productos de sumas.

Minimización de funciones

Minimización de Funciones

Minimizar una función de conmutación F(x1, x2, …,xn) es encontrar una función G(x1, x2, …,xn) equivalente a F y que contenga el mínimo número de términos y literales en una expresión OR de AND.

Ejemplo

F(A, B, C, D)=ACD+ ACD + ACD+ACD+ ABD

=(A+A) CD+ (A+A) CD+ABD

= CD+CD+ABD=(C+C)D+ABD=D+AB

Mapas de Karnaugh

Los mapas de Karnaugh son formas modificadas de Tablas de Verdad que permiten minimizar funciones de hasta 5 variables.

Los mapas de Karnaugh permiten el diseño rápido de circuitos combinacionales de mínimo costo, es decir, con el mínimo número de compuertas.

Construcción de Mapas de Karnaugh

Para construir mapas de Karnaugh se siguen los siguientes pasos:

1)Para una función de n variables, el mapa de Karnaugh tiene 2n celdas

n=2 n=3 n=3 n=4


2) En las coordenadas se anotan las combinaciones de variables según el código Gray

n=2 n=3 n=3 n=4

01

01

0 1 00 01 11 10

00 01 11 100 100011110

00011110


3) Se asigna un 1 a una variable sin complementar y un cero a una variable complementada. De esta forma cada celda queda determinada por una combinación de unos y ceros

De esta forma, cada celda queda determinada por una combinación de unos y ceros

A

0 1

00 10

01 11

AB AB

0 1

AB AB

0 1

AB B0 1


4) A cada combinación de unos y ceros de una celda se le asigna el equivalente decimal de la representación binaria

0 4 12 800 01 11 10

00011110

1 5 13 93 7 15 112 6 14 10

Ejemplo de construcción del Mapa de Karnaugh

Encontrar el mapa de la función

F(A, B, C, D)=(0, 1, 5, 6, 9, 13, 15)

0 4 12 800 01 11 10

00011110

1 5 13 93 7 15 112 6 14 10

ABCD

1 0 0 000 01 11 10

00011110

1 1 1 10 0 1 0 0 1 0 0

ABCD


5) Dos celdas son adyacentes si difieren en una variable

00 01 11 10

00

01

11

10


6) Un subcubo es un conjunto de 2n celdas con valor de 1, las cuales tienen la propiedad que cada celda es adyacente a m celdas del conjunto

00 01 11 10

00

01

11

10

1 0 0 0

1 1 1 1

0 0 1 0

0 1 0 0

ABCD

Subcubo tamaño 4

Subcubo tamaño 2

Subcubo tamaño 2

Subcubo tamaño 1


7) Un subcubo se puede expresar por un término algebraico que tiene n-m literales donde n es el número de variables y 2m es el tamaño del subcubo

00 01 11 10

00

01

11

10

1 0 0 0

1 1 1 1

0 0 1 0

0 1 0 0

ABCD

CD

ABD

ABC

ABCD


8) Una función se puede expresar como la suma de los subcubos necesarios para cubrir todos los unos del mapa de Karnaugh.Para que una función sea mínima hay que buscar el mínio número de subcubos, o sea, cada subcubo debe ser del mayor tamaño posible.El método de mapa de Karnaugh es un método manual. En términos prácticos sirve para minimizar funciones de hasta 6 variables


Minimización

F(A, B, C, D)=ABCD+ABC+ABD+CD

00 01 11 10

00

01

11

10

1 0 0 0

1 1 1 1

0 0 1 0

0 1 0 0

ABCD

CD

ABD

ABC

ABCD

Construcción de Mapas de Karnaugh: AND de OR

Una función se puede expresar también como el producto (AND) de los subcubos necesarios para cubrir todos los ceros del mapa de Karnaugh.

Ejemplo: Minimizar

F(A, B, C, D)=(0, 2, 5, 8, 10, 13, 14)

Construcción de Mapas de Karnaugh: AND de OR

00 01 11 10

00

01

11

10

0 1 1 0

1 0 0 1

1 1 1 1

0 1 0 0

ABCD

F(A, B, C, D)=(0, 2, 5, 8, 10, 13, 14)

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


Representación• Nótese que el mapa de 5 variables se obtiene a partir de dosmapas para n = 4.• A uno se le antecede un cero en la codificación de lascolumnas y al otro un 1.• El mapa de Karnaugh de 5 variables f(A,B,C,D,E):

000 001 011 010

00

01

11

10

0 4 12 8

1 5 13 9

3 7 15 11

2 6 14 10

ABCCD 110 111 101 100

24 28 20 16

25 29 21 17

27 31 23 19

26 30 22 18


• Otra forma de representación

000 001 011 010

00

01

11

10

0 4 12 8

1 5 13 9

3 7 15 11

2 6 14 10

ABCCD

100 101 111 110

16 20 28 24

17 21 29 25

19 23 31 27

18 22 30 26

f(A, B, C, D, E)

A=0

A=1


Generalizaciones• Un mapa de Karnaugh n variables tiene 2n celdas o cuadros.• Cada celda o casillero de un mapa de n variables, tiene n celdas adyacentes; es decir, los códigos binarios de los minitérminos están a distancia uno.• Una celda está asociada a un producto que contiene las n variables, pudiendo éstas estar o no complementadas.• Agrupando dos celdas adyacentes, se logra una expresión tipo producto de (n-1) variables.• Esto empleando:• Considerando que dos celdas adyacentes difieren en sólo una variable, ya que están a distancia 1 (código Grey).

baaba


•Bloques pueden agruparse de un número de celdas que es una potencia de dos; es decir: 2, 4, 8, 16...•Agrupando 2k celdas, que forman un k-cubo, la expresión booleana asociada es la que resulta de eliminar k variables de las n correspondientes a un minitérmino.•Los grupos posibles de k literales, cuando se tienen n variables (k ≤ n), quedan dados por:

•Ejemplo: los grupos de 1 literal cuando n=4

Son

kk

knk

n

k

n2

!!

!2

82!14!1

!42

1

4 11

D ,C ,B ,A D, C, B, A,


Ejemplo, para n = 4 (e.g. A, B, C, D):• Un minitérmino se expresa como un producto de 4 variables.• Una agrupación de 2 minitérminos, que forman un 1- cubo (o que son adyacentes), puede expresarse en tres variables.• Una agrupación de 4 minitérminos, que forman un 2- cubo, se expresa en dos variables.• Una agrupación de 23 minitérminos (que forman un 3-cubo), puede expresarse como una variable.• Una agrupación de los 24 minitérminos (forman un 4-cubo), puede expresarse como 1 (usando 0 variables).• Nótese que bajo el mapa suele escribirse la función que éste representa.


Ejemplo: los grupos de 2 literales (k=2), cuando n=4:

• Estos son:

242!24!2

!42

2

4 22

DC ,,CA ,CA ,CA AC, ,BA ,BA B,A AB,


Definiciones• Conjunto de unos en un mapa de Karnaugh que representa un termino producto de variables. Se denomina implicante porque cuando este termino toma el valor 1, implica que también la función toma el valor 1. Un minitérmino solo es un implicante. • Un implicante primo es aquel que no está incluido completamente dentro de otro implicante. No puede combinarse con otro implicante para eliminar un literal. • Un implicante primo esencial es un implicante primo que contiene uno o mas minitérminos que no están incluidos en cualquier otro implicante primo.


En el siguiente mapa de Karnaugh: Los términos I II y III son implicantes primosEl término IV no es implicante primoLos términos I y III son implicantes primos esencialesEl término II no es un implicante primo esencialesLa función se obtiene con los términos I y III


Derivación de una Expresión Mínima de un Mapa Un procedimiento para encontrar una expresión mínima como suma de productos es el siguiente:

1. Elegir un elemento del mapa y buscar todos los grupos máximos de 1s y Xs adyacentes a ese elemento. Repetir el paso 1 para encontrar todos los implicantes primos.

2. Visitar un elemento del mapa. Si esta cubierto por un solo implicante es esencial y va a contribuir un terminó a la expresión final de suma de productos. Repetir el paso 2 para encontrar todos los implicantes primos esenciales.

3. Si es que faltan algunos 1s que no están cubiertos entonces seleccionar un numero mínimo de implicantes primos para cubrirlos. Tratar varias alternativas de cubrimientos para encontrar el que tenga el numero menor de implicantes.

Ejemplos de uso de Mapas de Karnaugh

• f = Σm(0,2)

• Cout =Σm(3,5,6,7)

• f(A,B,C) = Σm(0,4,5,7)


CACB1,2,3,6mCB,A,F

versay vice s0'con s1' remplaza esimplement F

CBAC0,4,5,7mCB,A,F

ACB,A,G


DBDBACF

14,157,8,10,11,0,2,3,5,6,mDC,B,A,F

encontrar el menor número de subcubos demayor tamaño para cubrir el mapa(menor numero de términos con elmenor número de entradas por término)

Ejemplos de uso de Mapas de Karnaugh con indeterminados

DCBDAF

adosindeterminsin

6,12,13d1,3,5,7,9mDC,B,A,F

Ejemplos de uso de Mapas de Karnaugh con indeterminados

DCDAF

adosindetermincon

DCBDAF

adosindeterminsin

6,12,13d1,3,5,7,9mDC,B,A,F

usando un indeterminado como un "1“ se puede formar un 2-cubo en ves de un 1-cubo para cubrir este nodo

Los indeterminados se pueden usar como 1s o 0s, dependiendo de lo que sea mas conveniente

Implementación de circuitos combinacionales con SSI

Función lógica básica (suma)

Función lógica básica (suma)

Función aritmética de suma

Sumador

A

B Cout

Cin

SUMA

ACARREO

DE SALIDA

ENTRADAS DOS

NÚMEROS BINARIOS

ACARREO

DE ENTRADA

Funciones lógicas derivadas

Función aritmética de resta

Función aritmética de multiplicación

Función aritmética de división

Semisumador (Medio Sumador o Half Adder)

El circuito aritmético digital más simple es el de la suma de dos dígitos binarios. Un circuito combinatorio que ejecuta la suma de dos bits se llama semisumador.

Diagrama Lógico del Medio-Sumador

Sumador Completo (Full Adder)

Otro método para sumar dos números de n bits consiste en utilizar circuitos separados para cada par correspondiente de bits: los dos bits que se van a sumar, junto con el acarreo resultante de la suma de los bits menos significativos, lo cual producirá como salidas un bit de la suma y un bit del acarreo de salida del bit más significativo.

Diagrama en bloque de un Sumador Completo

Sumador CompletoSC

Xi

Yi Ci+1

Si

Ci

Sumador completo de dos palabras de un bit

Las expresiones mínimas de suma de producto para las salidas del SC

Funciones optimizadas

)(1 iiiiii

iiii

yxCyxC

CyxS

iiiii

iiiiiii

iiiiiiiiiiiii

yxCyx

CyCxyxC

CyxCyxCyxCyxS

1

Implementación de las ecuaciones del Sumador Completo

Implementación de un SC con dos MS

• Un sumador completo resulta de la unión de dos medios sumadores.

Sumadores de n bits

Podemos construir sumadores de n bits con n copias del circuito anterior, este tipo de sumadores son conocidos como, sumadores con propagación de acarreo (Carry-ripple adder).

Los sumadores completos se conectan en cascada de manera que el acarreo de salida de una etapa viene a ser el acarreo de entrada de la siguiente, como se ilustra en la figura de la siguiente diapositiva.

Implementación de un sumador en cascada Para dos palabras de 4 bits.

Cin

Cout

Podemos implementar un sumador de n bits con n copias de los circuitos anteriores

Sumadores del tipo con propagación de acarreo Como lo indicamos en una diapositiva anterior, una forma posible

para implementar sumadores de n bits es conectar n sumadores completos de un bit en cascada, a esta configuración se la denomina sumador con propagación de acarreo.

El mayor problema con este tipo de implementación es el tiempo de retardo, ya que cada módulo depende del resultado del módulo anterior, en base a la siguiente formula:

Donde: Δ es el tiempo de retardo de una compuerta.

Por ejemplo para un sumador de 64 bits el retardo será de 132 Δ, este es un tiempo de propagación muy grande.

)42( n

Sumadores basados en ecuaciones de suma de productos

Con la finalidad de incrementar la velocidad de los sumadores, se han pensado en varias aproximaciones, una de ellas es implementa un sumador multibit usando una expresión de suma de productos.

Por ejemplo un sumador para dos bits consistiría de una tabla de 5 entradas y tres salidas, consecuentemente tendríamos mapas de Karnaugh de 5 variables y expresiones simplificadas para la tres funciones de salida con 23 términos y 80 literales, un circuito de dos niveles requerirá una compuerta OR de 12 entradas y otras más.

Claramente podríamos seguir adoptando esta metodología para sumadores de 3 bits o 4 bits, no obstante el algebra cada vez será más compleja y el número de términos aumenta drásticamente.

Sumadores de tipo sumador con acarreo anticipado (Carry-look-ahead adder)

El problema en los sumadores anteriores ha sido el retardo de la señal de acarreo o de la complejidad del número de entradas.

Una solución para evitar estas desventajas son los sumadores de tipo sumador con acarreo anticipado.

La mayoría de los circuitos integrados comerciales usan este método.

Sumadores comerciales

Existe disponibles comercialmente sumadores de 4 bits: 7483, 7483A, y el 74F283 (4-bit binary full adder

with fast carry) Cada uno de ellos usa un circuito de 4 niveles para

producir la suma, usando una mezcla de compuertas NAND, NOR, NOT y OR-EX.

El retardo desde el Cin hasta el Cout es de 3Δ para cada 4 bits y produce un retardo total de (3/4 n+1)Δ.

Sumador de 12 bits con tres SC de 4 bits (74HC283) en cascada

U1

74HC283N_6V

SUM_4 10SUM_3 13

SUM_1 4SUM_2 1

C4 9

B411

A412

B315

A314

B22

A23

B16

A15

C07

U2

74HC283N_6V

SUM_4 10SUM_3 13

SUM_1 4SUM_2 1

C4 9

B411

A412

B315

A314

B22

A23

B16

A15

C07

U3

74HC283N_6V

SUM_4 10SUM_3 13

SUM_1 4SUM_2 1

C4 9

B411

A412

B315

A314

B22

A23

B16

A15

C07

Existe una tercera aproximación para implementar sumadores que es llamada sumador con acarreo anticipado.

Restadores y Sumadores-Restadores

Para realizar la substracción podríamos desarrollar la tabla de verdad para la resta de 1 bit y unir en cascada los módulos necesarios para el número de bits que se requiera, los que se denominaría un sustractor de propagación de préstamo (borrow-ripple subtractor).

En la mayoría de los casos, cuando se realiza una resta, también es necesario realizar una suma, por lo tanto podemos sacar ventaja de la aproximación de realizar una resta usando una suma de la siguiente forma: A – B = A + Bcomp a 1 + 1

El uso de las compuertas OR-EX ayudan a comandar el modo de funcionamiento.

Sumador/Restador

Sumador/Restador

A-B = A+B+1, para realizar el complemento se usan las compuertas OR-EX.

Función lógica básica (Comparador)

Función lógica básica (Comparación)

Función comparación

Comparador

A A>B

A=B

B A<B

SALIDAS

TRES ESTAADOS LÓGICOS

ENTRADAS DOS

NÚMEROS BINARIOS

Comparadores

Una necesidad común en la aritmética es la comparación de dos números, que indique si son iguales o si uno es mayor que el otro.

Se usa la OR Exclusiva (OR-EX) para generar un 1 en el caso de que los números sean diferentes y 0 para el caso de que sean iguales.

Para un caso de dos palabras de varios bits, si un par de bit son diferentes entonces las palabras son diferentes.

Circuito Comparador de 4 bits

a) Con OR exclusivas b) Con NOR exclusivas

Estos comparadores solo son para determinar la igualdad de dos palabras de 4 bits y pueden extenderse a cualquier tamaño de palabras.

Comparadores

Para la implementación de una comparador de 4 bits que indique si la palabra es mayor, menor o igual, debemos hacer un reconocimiento desde el bit más significativo de la siguiente forma: a>b si a4>b4 o (a4 = b4 y a3>b3) o (a4 = b4 y a3 = b3 y

a2>b2) o (a4 = b4 y a3 = b3 y a2 = b2 y a1>b1) a<b si a4<b4 o (a4 = b4 y a3<b3) o (a4 = b4 y a3 = b3 y

a2<b2) o (a4 = b4 y a3 = b3 y a2 = b2 y a1<b1) a = b si a4 = b4 y a3 = b3 y a2 = b2 y a1 = b1

Esta lógica se puede extender para la cantidad de bits que sea necesario o el de 4 bits puede estar en cascada con otros pasando las señales de > < =.

Comparador Comercial

El 7485 es un comparador de 4 bits, con la opción de realizar conexiones en cascada para aumentar en número de bits que se deseen comparar.

Para hacer la cascada las señales van del módulo más bajo al más alto

Comparador típico de 1 bit

=

<

>

Función lógica básica (Decodificadores)

Función lógica básica (Decodificador)

Función de decodificación

Entrada binaria

Decodificador

(BCD a 7segmentos)

Decodificadores

Un decodificador es un dispositivo que cuando está activado selecciona una de varias líneas de salida basándose en un código de entrada.

Las cantidades discretas de información se representan en sistemas digitales con códigos binarios (ejemplo: BCD, EXCESO 3, 84-2-1, 2421, etc.). Un código binario de n bits es capaz de representar hasta 2n elementos distintos de información codificada.

La mayoría de los decodificadores convierte información binaria de n líneas de entrada a un máximo de 2n líneas únicas de salida o menos. Estos decodificadores son denominados decodificadores n-a-m líneas, donde m 2n.

Decodificadores

Estos dispositivos normalmente cuentan con una entrada

habilitadora. Cuando esta entrada vale 0, todas las salidas

del codificador son 0. Cuando la entrada habilitadora vale

1, la salida correspondiente al minitérmino formado por la

combinación presente en las n entradas tomará el valor 1 y

las demás tomarán el valor 0.

Decodificador 24

Un valor de x en las entradas indica que puede tomar el valor de 1 o 0.

X X0 00 11 01 1

01111

DEC 24 S0

S1

S2

Hab. S3

C1 C0

0 1 0 0 0 0 0 1 0 00 0 0 1 0 0 0 0 0 1

Decodificador 24

Las funciones lógicas para las salidas del codificador 2x4 son:

010 CCHS

011 CCHS

012 CHCS

013 CHCS

Decodificadores

De forma semejante a como se define el decodificador 24, pueden definirse decodificadores de 38, 416, 532 y en forma general de n2n.

La principal utilización de este dispositivo es cuando se tiene N alternativas que se pueden seleccionar, pero se desea seleccionar solamente una de ella.

Decodificador 38

Decodificador comercial

El 74138 es un decodificador de tipo 38 comercialmente disponible

Ver hoja de datos Entradas con X Tipo de salidas

Active High Active Low

U1

74LS138N

Y0 15Y1 14Y2 13Y3 12Y4 11Y5 10Y6 9Y7 7

A1B2C3

G16~G2A4~G2B5

Decodificador comercial 4x16

El 74154 es un decodificador comercial 416

Es un CI de 24 pins

U1

74154N

2 33 4

5 64 5

6 7

1 2

7 8

0 1

8 99 1010 1111 1312 1413 1514 1615 17

A23B22C21D20

~G118~G219

Aplicación

Una aplicación de los decodificadores es seleccionar uno de muchos dispositivos que tiene una única dirección. La dirección sería la entrada del decodificador, una salida estaría activa, para seleccionar el dispositivo que fue seleccionado.

Decodificadores de mayor tamaño

Es posible unir varios decodificadores para implementar decodificadores de mayor tamaño.

Función lógica básica Codificador (encoder)

Función lógica básica (Codificador)

Función de codificación

7

4

1

0

9

8

7

6

5

4

3

2

1

+/-

.

0

Código binario

8

5

2

.

9

6

3

+/-

Codificador

(de teclado)

Codificador

Un codificador es un circuito digital que ejecuta la operación inversa de un decodificador. Un codificador tiene 2n (o menos) líneas de entrada y n líneas de salida. Las líneas de salida generan un código binario correspondiente al valor de entrada binario.

Es útil cuando uno de varios dispositivos desea enviar señales a una computadora.

Solo una entrada puede estar activada.

Codificador Octal a Binario

Entradas Salidas

D7 D6 D5 D4 D3 D2 D1 D0 A2 A1 A0

0 0 0 0 0 0 0 1 0 0 0

0 0 0 0 0 0 1 0 0 0 1

0 0 0 0 0 1 0 0 0 1 0

0 0 0 0 1 0 0 0 0 1 1

0 0 0 1 0 0 0 0 1 0 0

0 0 1 0 0 0 0 0 1 0 1

0 1 0 0 0 0 0 0 1 1 0

1 0 0 0 0 0 0 0 1 1 1

Codificador octal a binario

El codificador puede implantarse con compuertas OR cuyas entradas se determinan directamente de la tabla de verdad. Por ejemplo, la salida es A0 será igual a 1 si el digito octal de entrada es 1 o 3 o 5 o 7.

Las funciones de este codificador son las siguientes: A0 = D1+D3+D5+D7 A1 = D2+D3+D6+D7 A3 = D4+D5+D6+D7

Codificador BDC comercial el 74147

El 74147 es un codificador BCD, que toma 9 entradas activadas por nivel bajo y las codifica en 4 salidas activadas en nivel bajo.

U1

74147N

A 9B 7C 6D 14313

4152

212 111

85 74 63

910

Función lógica básica (multiplexor)

Función lógica básica (Multiplexor)

Función de selección de datos

Multiplexor Demultiplexor

Entrada de control de secuencia de conmutación

Entrada de control de secuencia de conmutación

A

B

C

D

E

F

Multiplexores

Problemática Los datos que se generan en una localidad se van a

usar en otra, para esto se necesita un método para transmitirlos de una localidad a otra a través de algún canal de comunicaciones.

.

.

.

Entrada dedatos

.

.

.

Salida dedatos

Canal de comunicaciones

multiplexor

demultiplexor

Multiplexores

Definición Un multiplexor digital es un circuito con 2n líneas

de entrada de datos y una línea de salida; también debe tener una manera de determinar la línea de entrada de datos específica que se va a seleccionar en cualquier momento. Esto se efectúa con otras n líneas de entrada, denominadas entradas de selección, cuya función es elegir una de las 2n entradas de datos para la conexión con la salida

Multiplexores (Selectores)

Existen dos tipos básicos de Multiplexores: De varias entradas a una salida, llamados de

selectores de 2n a 1, o simplemente MUX (del inglés multiplexer) de 2n a 1.

De una entrada a varias salidas, llamados selectores de 1 a 2n o simplemente DEMUX (del inglés demultiplexer) de 2n a 1.

Multiplexor 41

Multiplexor 4 a 1

El multiplexor 4 a 1 tiene seis entradas y una salida. Una tabla de verdad que describa el circuito necesitará 64 renglones, esta es una tabla excesivamente larga y no es práctica.

Una manera más práctica de describir el funcionamiento es por medio de una tabla de función.

Tabla de función de un mux 4 a 1

Selección Salida

S1 S0 Y

0 0 I0

0 1 I1

1 0 I2

1 1 I3

Esta tabla demuestra la relación entre las cuatro entradas.De datos y la salida única como función de las entradas de Selección S1 y S0.

Mux 81

Función lógica básica (Memoria)

Memorias ROM

• Memorias ROM (Read Only Memory, memoria de sólo lectura).• m entradas (2m elementos direccionables, o altura de la ROM).• n salidas (Cada posición contiene un dato de n bits, anchura de la

ROM).• Forma de la ROM = altura x anchura• Aunque se llame memoria, es un circuito combinacional.• Puede usarse para implementar n funciones binarias distintas

dependientes de las mismas m variables de entrada.• Se implementa usando dos niveles de puertas (aparte de las• negaciones de las entradas):

Un plano AND, con 2m puertas de m entradas cada una. Un plano OR, con n puertas de salida.

Memorias ROM

Esquema de una memoria ROM con 8 posiciones de 4 bits cada una (3 bits de dirección, y anchura de datos 4).

Variantes de Memorias ROM

PROM (Programmable ROM, ROM programables).

EPROM (Erasable PROM, PROM borrables).

EEPROM (Electronically EPROM, PROM borrables electrónicamente).

Memorias Flash (permiten el borrado y reescritura selectivos por bloques, miles de veces).

Arreglos Lógicos Programables

PAL (Programmable Array Logic, arreglo lógico programable).

Como una ROM, pero sólo se implementan los productos necesarios. Útiles cuando hay muchas entradas, pero sólo unas pocas combinaciones se utilizan realmente. Ejemplo Forma 3x6x4:

electrónica digital unidad iii

Documents