INFORME N 2 LABORATORIO
DE ELECTRNICA DIGITAL
MARCO TERICO
1. HISTORIA:
Maurice Karnaugh:
Maurice Karnaugh, (nacido el 4 de octubre de 1924 en la
ciudad de Nueva York) es un fsico y matemtico
estadounidense, mejor conocido por el mapa de Karnaugh
utilizado en el lgebra de Boole.
Estudi matemticas y fsica en el City College of New York
(1944-1948) y se transfiri a la Universidad de Yale para
completar su licenciatura (1949), M.Sc. (1950) y Ph.D. en
fsica con una tesis sobre La Teora de la Resonancia
Magntica y duplicacin de Tipo-Lambda en xido Ntrico
(1952).
Karnaugh trabaj en los Laboratorios Bell (1952-1966),
desarrollando el mapa de Karnaugh (1954), as como las
patentes para la codificacin PCM1 y la codificacin de
circuitos lgicos magnticos.2 3 Ms tarde, trabaj en la
Divisin Federal de Sistemas de IBM en Gaithersburg
(1966-1970) y en el Centro de investigaciones Thomas J.
Watson de IBM (1970-1989), estudiando las redes de
interconexin multietapas.4
Karnaugh fue elegido Fellow de IEEE en 1976, y ocup un
cargo adjunto en la Universidad Politcnica de Nueva York
en el campus Westchester 1980-1999.
2. MAPA DE KARNAUGH:
Un mapa de Karnaugh (tambin conocido como tabla de
Karnaugh o diagrama de Veitch, abreviado como Mapa-K o
Mapa-KV) es un diagrama utilizado para la simplificacin de
funciones algebraicas Booleanas. El mapa de Karnaugh
fue inventado en 1950 por Maurice Karnaugh, un fsico y
matemtico de los laboratorios Bell.
Los mapas de Karnaugh reducen la necesidad de hacer
clculos extensos para la simplificacin de expresiones
booleanas, aprovechando la capacidad del cerebro
humano para el reconocimiento de patrones y otras formas
de expresin analtica, permitiendo as identificar y eliminar
condiciones muy inmensas.
El mapa de Karnaugh consiste en una representacin
bidimensional de la tabla de verdad de la funcin a
simplificar. Puesto que la tabla de verdad de una funcin de
N variables posee 2N filas, el mapa K correspondiente
debe poseer tambin 2N cuadrados. Las variables de la
expresin son ordenadas en funcin de su peso y
siguiendo el cdigo Gray, de manera que slo una de las
variables vara entre celdas adyacentes. La transferencia
de los trminos de la tabla de verdad al mapa de Karnaugh
se realiza de forma directa, albergando un 0 un 1,
dependiendo del valor que toma la funcin en cada fila. Las
tablas de Karnaugh se pueden fcilmente realizar a mano
con funciones de hasta 6 variables, para funciones de
mayor cantidad de variables es ms eficiente el uso de
software especializado.
Ejemplo de mapa de Karnaugh.
EJEMPLO:
Dada la siguiente funcin algebraica Booleana
representada como el sumatorio de sus minitrminos, y con
las variables Booleanas: , , , , la funcin se puede
representar con dos notaciones distintas:
3. TABLA DE VERDAD:
Utilizando los Mintrminos definidos, se elabora la tabla de
verdad:
3.1 MAPA DE KARNAUGH(con la tabla):
Las variables de entrada pueden combinarse de 16 formas
diferentes, por lo que el mapa de Karnaugh tendr 16
celdas, distribuidas en una cuadrcula de 4 4.
La combinacin de dgitos binarios en el mapa representa
el resultado de la funcin por cada combinacin de
entradas. Por ejemplo, la celda en la esquina superior
izquierda del mapa es 0, porque el resultado de la funcin
es = 0 cuando A = 0, B = 0, C = 0, D = 0. De igual
manera, la esquina inferior derecha es 10 porque el
resultado de la funcin es = 10 cuando A = 1, B = 0,
C = 1, D = 0.
Una vez construido el mapa de Karnaugh, la siguiente tarea
es la de seleccionar conjunto de trminos denominados
subcubos de manera que se obtenga el menor nmero de
subcubos posible. Estos subcubos se seleccionan
formando grupos de rectngulos que encierren a los unos
del mapa, las reas deben ser potencia de 2 (ej. 1, 2, 4,
8, ...) y se debe tratar de agrupar el mayor nmero de unos
posible. En resumen hay que tomar en cuenta al hacer
estos grupos de unos (subcubos) lo siguiente:
Se puede visualizar tambin que los grupos pueden
continuar en el lado opuesto como en el subcubo 1 de la
figura dibujado en azul.
Debemos utilizar todos los unos del mapa.
Es mejor crear el menor nmero de grupos.
Los unos pueden estar en varios grupos.
El nmero de unos dentro de un grupo debe de ser
cualquier potencia de 2.
Mientras ms grande sea un grupo la simplificacin de
la funcin ser mejor.
No es necesario que todos los grupos tengan el
mismo tamao.
Qu trminos seleccionar va dependiendo de cmo se
quiera realizar la simplificacin, puesto que esta puede
realizarse por minitrminos o por maxitrminos.
4. Aplicaciones:
Los Mapas de Karnaugh son una herramienta muy utilizada
para la simplificacin de circuitos lgicos.
Cuando se tiene una funcin lgica con su tabla de verdad
y se desea implementar esa funcin de la manera ms
econmica posible se utiliza este mtodo.
Ejemplo: Se tiene la siguiente tabla de verdad para tres
variables.
Se desarrolla la funcin lgica basada en ella. (Primera
forma cannica). Ver que en la frmula se incluyen
solamente las variables (A, B, C) cuando F cuando es igual
a "1". Si A en la tabla de verdad es "0" se pone A, si B = "1"
se pone B, Si C = "0" se pone C, etc.
F =AB C +AB C +AB C +AB C +AB C +AB C
Una vez obtenida la funcin lgica, se implementa el mapa
de Karnaugh.
Este mapa tiene 8 casillas que corresponden a 2n, donde n
= 3 (nmero de variables (A, B, C))
La primera fila corresponde a A = 0
La segunda fila corresponde a A = 1
La primera columna corresponde a BC = 00 (B=0 y C=0)
La segunda columna corresponde a BC = 01 (B=0 y C=1)
La tercera columna corresponde a BC = 11 (B=1 y C=1)
La cuarta columna corresponde a BC = 10 (B=1 y C=0)
En el mapa de Karnaugh se han puesto "1" en las casillas
que corresponden a los valores de F = "1" en la tabla de
verdad.
Tomar en cuenta la numeracin de las filas de la tabla de
verdad y la numeracin de las casillas en el mapa de
Karnaugh.
Para proceder con la simplificacin, se crean grupos de
"1"s que tengan 1, 2, 4, 8, 16, etc. (slo potencias de 2).
Los "1"s deben estar adyacentes (no en diagonal) y
mientras ms "1"s tenga el grupo, mejor. La funcin mejor
simplificada es aquella que tiene el menor nmero de
grupos con el mayor nmero de 1s en cada grupo.
Se ve del grfico que hay dos grupos cada uno de cuatro
1s, (se permite compartir casillas entre los grupos). La
nueva expresin de la funcin boolena simplificada se
deduce del mapa de Karnaugh.
Para el primer grupo (rojo): la simplificacin da B (los
1s de la tercera y cuarta columna corresponden a B
sin negar)
Para el segundo grupo (azul): la simplificacin da A
(los 1s estn en la fila inferior que corresponde a A
sin negar)
Entonces el resultado es F = B + A F = A + B
Ejemplo: Una tabla de verdad como la de la derecha da la
siguiente funcin booleana: F = A B C + A B C + A B C + A
BC
Se ve claramente que la funcin es un reflejo del contenido
de la tabla de verdad cuando F = 1, Con esta ecuacin se
crea el mapa de Karnaugh y se escogen los grupos. Se
lograron hacer 3 grupos de dos 1s cada uno. Se puede
ver que no es posible hacer grupos de 3, porque 3 no es
potencia de 2. Se observa que hay una casilla que es
compartida por los tres grupos.
La funcin simplificada es: F = A B+ A C + B C. Grupo en
azul: A B, grupo marrn: A C, grupo verde: B C
Tambin pueden ser utilizados en la construccin de
estaciones de clasificacin, seleccin y control de calidad
de piezas fabricadas, entre otras aplicaciones.
