Unidad 2*Simplificacin de circuitos lgicos Algebra de Conmutacin

Sistemas Digitales

Tabla de Contenido*IntroduccinAlgebra de conmutacinManipulacin algebraicaOperaciones lgicasImplementacin de funciones lgicasIntroduccin a los Mapas de KarnaughPropiedades de las compuertas NAND y NOR

Introduccin*En la unidad anterior llegamos hasta la transformacin de un problema digital en su equivalente tabla de verdad, en un formato binario, esto sera suficiente para construccin de sistemas que usen memorias de solo lectura (ROM), para realizar la implementacin de estos sistemas con otro tipo de componentes (compuertas lgicas) es necesario tener una descripcin algebraica de estos sistemas.De lo dicho anterior, podemos concluir que necesitamos el lgebra para:Interpretar o describir una red de compuertas que componen el sistema digital.Permite simplificar y minimizar la cantidad de lgica usada en un sistema.Es bsica en el proceso de implementacin de una red de compuertas.

Definicin del Algebra de Conmutacin*Es el conjunto axiomtico que normaliza las operaciones que podrn existir en un ambiente con variables binarias, esto es, variables que puedan asumir nicamente dos valores, incluso, variables que fsicamente no son binarias, pero pueden ser representadas en trminos binarios.

Operadores del Algebra de Conmutacin*OR (suma lgica)Smbolos: + , Va + b (se lee: a or b), y es 1 s y slo s a=1 b=1 ambos.AND (producto lgico)Smbolos: . , , o simplemente dos variables seguidasa . b (se lee: a and b), y es 1 s y slo s a=1 y b=1.NOT (negacin, complemento, inversin)Smbolos: a (se lee: not a , a negado), y es 1 s y slo s a=0.

Tablas de verdad para las operaciones OR. AND y NOT*

aba + b000011101111

abab000010100111

aa0110

Sistemas Digitales

*Propiedades del Algebra de Conmutacin(Postulados y Teoremas)

Sistemas Digitales

Propiedad Conmutativa*Las operaciones OR y AND son conmutativasP1a. a + b = b + aP1b. a . b = b . ANote que el valor para las combinaciones en la tabla de verdad para las segundas y terceras lneas son iguales

Propiedad Asociativa (1)*Las operaciones OR y AND son asociativasP2a. (a+b)+c = a+(b+c) P2b. (a.b).c = a.(b.c) Esta propiedad es mencionada como la Ley Asociativa, declara que el orden de los factores no altera el resultado.Esta propiedad nos ayuda a establecer algunas particularidades de las operaciones OR y AND.

Propiedad Asociativa (2)*ORa+b+c+d+. Es 1 si cualquiera de las variables es 1 y es 0 slo si todas las variables son 0.ANDabcd . Es 1 si todas las variable son 1 y es 0 si cualquiera de las variables es 0.

Las compuertas (1)*Es el elemento bsico en los sistemas digitales.Es un elemento con una sola salida que implementa una de las funciones bsicas como AND y OR.Est disponibles en configuraciones de dos, tres, cuatro y ocho entradas.

Las compuertas (2)*Smbolos para OR y AND

Implementacin para la propiedad 2b*

Smbolo para la compuerta NOT*El circulo al final del tringulo es la representacin de la negacin

Identidad*Existen 2 elementos neutros, el 0 y el 1, cumplindose la propiedad en dos de los casos, quedando como 1 y 0 lgicos en los otros dos (ver teorema 2):P3a. a.1 = a(identidad)P3b. a+0 = a(identidad)

Nulo*Casos en que no se cumple la propiedad de elemento neutro, pero existen y se definen de esta forma.P4a. a.0 = 0P4b. a+1 = 1

Complemento*Existe el elemento complementario para cada variable binaria y el resultado para cada operacin es el que sigue.P5a. a + a = 1P5b. a . a = 0

Idempotencia*La suma o producto de dos variables iguales equivale a la misma variableP6a. a+a = aP6b. a.a = a

Involucin*Para todo elemento de un lgebra de boole se cumple que:P7. (a)=a

Distributiva*Ambas operaciones son distributivasP8a. a(b+c) = (ab)+(ac) P8b. a+bc = (a+b)(a+c) (Este postulado no existe para el lgebra comn)

Adyacencia*Se define de la siguiente forma:P9a. ab + ab= aP9b. (a+b)(a+b) = a

Simplificacin*Es una combinacin de las propiedades distributivas y asociativas, se usa comnmente en la simplificacin de funciones.P10a. a + a b = (a + a) (a+b) = a+bP10b. a (a + b) = a a + a b = ab

Absorcin*Ley de Absorcin.P11a. a + ab = aP11b. a(a + b) = a

Ley de Moorgan*Ley De Moorgan.P12a. (a + b + c + ...) ' = a' . b' . c' . ...P12b. ( a . b . c. ... ) ' = a' + b' + c' + ...

*Manipulacin de Funciones Algebraicas

Sistemas Digitales

Conceptos importantes*Literal o variableTrmino de productoTrmino estndar de productos o minitrminoSumatoria de productosSumatoria cannica o sumatoria de trminos de productos estndares.Sumatoria de productos mnima o expresin simplificada.Nota: cada uno de estos conceptos tiene un concepto dual para la suma.

La simplificacin*El proceso de la simplificacin consiste en aplicar los postulados y teoremas del lgebra de conmutacin para llegar a la expresin ms simple de la ecuacin, est, se presentar normalmente en su forma de sumatoria de productos mnima.

Ejemplo de simplificacin*F = xy(z+x+zy)F=xyz+xyx+xyzyF=xyz+xy+xyzF=xyz+xyF=xySimplificar:xyz + xyz + xyz + xyz + xyz

Sobre la simplificacin*No existe una metodologa para realizar la simplificacin.Slo la prctica es la manera de alcanzar la simplificacin ms ptima.La aplicacin del lgebra de conmutacin no garantiza el llegar a la simplificacin ptima.

*Implementacin de Funciones con Compuertas

Sistemas Digitales

Redes con AND, OR y NOT*Una vez que se define la suma de productos mnima se debe de definir el diagrama lgico, compuesto por una red de compuertas que describan la funcin.

Ejemplo de un circuito de dos niveles*

XYZ

XYZ

XYZ

XYZ

Niveles*El nmero de niveles corresponde al mximo nmero de compuertas que una seal 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*Diagrama de la suma de productosDiagrama de la suma de productos mnimo

Una red multinivel*Las redes multinivel son el resultado de implementar funciones que no estnen la forma ni de suma de productos ni de productos de sumas.

De la Tabla de Verdad a la Expresin Algebraica*En la mayora de los casos, un problema digital es presentado en la forma de una declaracin o como una tabla de verdad, esto nos obliga a tener la habilidad de llevar los datos de una tabla de verdad a una expresin algebraica.En la tabla de verdad, cada combinacin de las variables de entrada corresponde a un termino de producto estndar.Es posible extraer una sumatoria de productos estndares sumando cada termino de producto cuyo resultado en la tabla de verdad es igual a 1.

Miniterminos*En la tabla se muestra la equivalencia entre las combinaciones de una tabla de verdad y los minitrminos que estn asociados a cada uno de los productos estndares de una expresin algebraica.Los miniterminos pueden ser referidos tambin por sus nmeros, que estn mostrados en la columna de la derecha.

abcMiniterminoNmero000ABC0001ABC1010ABC2011ABC3100ABC4101ABC5110ABC6111ABC7

Sistemas Digitales

Ejemplo 1*La expresin algebraica ser:

f(A,B,C) = m(1,2,3,4,5)= ABC+ABC+ABC+ABC+ABCf(A,B,C) = m(0,6,7)= ABC+ABC+ABCPara la mayora de los casos la suma de los minitrminos no representa la sumatoria mnima de productos.

ABCff0000100110010100111010010101101100111101

Sistemas Digitales

Ejemplo 2, con condiciones irrelevantes (dont care)*La expresin algebraica ser:

f(a,b,c) = m(1,2,5) + d(0,3)

abcf000x00110101011x1000101111001110

Problema*Desarrollar las expresiones algebraicas para EJE1, EJE2 y EJE3.

Finalizacin del proyecto EJE1*Z2= ABCD+ABCD+ABCD+ABCD+ABCDZ2 suma mnima = ACD+BCD+ABC+ABDDiagrama lgico

*Introduccin a los Mapas de Karnaugh

Sistemas Digitales

Mapas de Karnaugh*Es un mtodo grfico usado para la simplificacin de funciones de conmutacin.Propuesto por Maurice Karnaugh en 1953.Los mapas de Karnaugh se compone de un cuadrado por cada minitrmino posible de una funcin.2 variables, 4 cuadrados3 variables, 8 cuadrados4 variables, 16 cuadrados

Mapa de Karnaugh para dos variables*0 10

1ABABAqu tenemos tres vistas de una mapa de dos variables, las casillas sombreadas, por ejemplo, corresponden al minitrmino 2 donde A=1 y B=0

ABABABAB

m0m2m1m3

0213

Sistemas Digitales

Representando funciones en un Mapa de Karnaugh (1)*Cuando se quiere llevar una funcin a un mapa, se coloca un 1 en el casillero correspondiente al minitrmino que result como 1 en la funcin.Los otros casilleros se dejan en blancoSi existen condiciones irrelevantes, es necesario poner una X en los minitrminos correspondientes.

Representando funciones en un Mapa de Karnaugh (2)*0 10

1ab0 10

1ABF(a,b) = m(0,3)F(A,B) = m(0,3) + d(2)

11

1X1

Mapa de Karnaugh para 3 variables*00 01 11 100

1ABC00 01 11 100

1ABCLa idea con la codificacin es poder usar el P9a. ab+ab=a

ABCABCABCABCABCABCABCABC

02641375

Mapa de Karnaugh para 4 variables*00 01 11 1000

01

11

10ABCD00 01 11 1000

01

11

10ABCD

ABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCD

0412815139371511261410

Ejemplo de adyacencia para un mapa de 4 variables*Los 1 en dos celdas adyacentes corresponden a un solo trmino de producto.00 01 11 1000

01

11

10ABCD00 01 11 1000

01

11

10ABCDACDABD

11

1

1

Extendiendo el concepto de adyacencia para agrupar ms celdas*00 01 11 100

1ABC00 01 11 100

1ABCAC ACC

1111

1111

Otros ejemplos para grupos de 4*00 01 11 1000

01

11

10ABCD00 01 11 1000

01

11

10ABCDABADBD BD

11111111

11111111

Grupos de 8*00 01 11 1000

01

11

10ABCD00 01 11 1000

01

11

10ABCDAD

11111111

1111

1111

Ejemplo de simplificacin usando Mapas de Karnaugh*00 01 11 100

1xyz00 01 11 100

1xyzxyz + xyz + xyz + xyz + xyz00 01 11 100

1xyzxy + xy + xz

11111

11111

11111

Problema*f = abc + abc + abc + abcPara la funcin f encontrar:La suma de productos mnima usando un mapa d karnaugh.

Retomaremos el estudio de los Mapas de Karnaugh un poco ms adelante

*Compuertas NAND, NOR y OR EXCLUISIVAS

Sistemas Digitales

Compuerta NAND y NOR*Como la otras compuertas que estudiamos, tambin estn disponibles en el comercio con dos, tres, cuatro y ocho entradas.Smbolos para NANDSmbolos para NOR

Importancia de las NAND y NOR*Todas las funciones Booleanas pueden ser substituibles por una funcin equivalente que utilice nicamente compuertas NAND y/o NOR, esto con los siguientes objetivos:Disminucin del nmero de componentes en una tarjeta de circuito impreso.Dar facilidad de mantenimiento futuro y Disminuir el consumo de energa.La transformacin de cualquier funcin se efectuar mediante la correcta utilizacin del teorema de Moorgan.

Algunas equivalencias*

Metodologa para transformar una expresin a NAND*Una vez obtenida la expresin correspondiente del problema digital, se realiza a todo el conjunto una doble inversin o negacin.Como nos encontramos en el caso de implementar con puertas NAND, si la expresin resultante est en funcin de productos, las dos negaciones deben dejarse tal cual. Si, por el contrario, es una suma, se aplica el teorema de Moorgan sobre dicha suma.Continuar 2, hasta la obtencin de una funcin compuesta exclusivamente como productos negados.

Metodologa para transformar una expresin a NOR*Con la expresin correspondiente se realiza a todo el conjunto una doble inversin o negacin.Si la expresin resultante est en funcin de sumas, las dos negaciones deben dejarse tal cual. Si se trata de un producto, tendremos que aplicar el teorema de Moorgan sobre el producto.Continuar 2 (realizando el proceso anterior) hasta la obtencin de una funcin compuesta exclusivamente por sumas negadas.

Compuerta OR-Exclusiva y NOR-Exclusiva*

aba xor b000011101110

aba xnor b001010100111

Sistemas Digitales