MTODO DE REDUCCIN DE MAPAS DE KARNAUGHEl lgebra de Boole, resuelve problemas que dependiendo delnmero de trminosque tena lafuncin cannica, siendo elnmero de compuertas lgicasutilizadasigualalnmero de trminosobtenidosMS UNO; por lo tanto, los circuitos obtenidos son dedos niveles de conmutacincon untiempo mnimo de retardo, pero que deninguna manera es el ms sencillo ni el ms econmico.2.1 Generacin de MAPA DE KARNAUGH de 2 y 3 variables. Losmapas deKarnaughes uno de losmtodos ms prcticos. Se puede decir que es elms poderoso, cuando elnmero de variables de entradaesmenor o igual a seis; ms all, ya no es tan prctico. En general, elmapa deKarnaughse considera como laforma grficade unatabla de verdado como unaextensindeldiagrama de Venn. Antes de explicar como se utiliza elmapa deKarnaughen laminimizacindefunciones, veremos como se obtiene elmapa. Esto nace de larepresentacin geomtricade losnmeros binarios. Unnmero binariodenbits, puede representarse por lo que se denomina unpunto en un espacioN. Para entender lo que se quiere decir con esto, considrese elconjuntode losnmeros binariosde un bit, es decir0o1. Esteconjuntopuede representarse pordos puntosen unespacio 1; esto es, pordos puntos unidospor unalnea. Tal representacin se denomina uncubo 1.

De laFigura 2.1, se observa que elcubo 1se obtuvoproyectandoalcubo 0y que elcubo 2se obtendrproyectandoalcubo 1.

De laFigura 2.2, se observa que alreflejarseelcubo 1se obtiene uncuadrilterocuyosvrticesrepresentanunnmero binario. Estosnmerosse obtienen alagregarun0a laizquierdade losvrticesdelcubo reflejado. Delcubo 2se observa que se obtienen4 vrtices, los cuales corresponden a lascombinaciones de dos variables(22=4), pero si se sigue latrayectoriaindicada en laFigura 2.2.b, se podrobservarque al pasar de unvrticeal otro,existe un solo cambio, lo que da lugar a uncdigo especial, debido que a no sigue la formacin delcdigo binario, como se muestra en la siguientetabla. Ms adelante le daremos un nombre a estecdigo.AB

00

01

11

10

Ahora, si a cada vrtice delcubo 2se le asigna un casillero, se tendr laFigura 2.3. De laFigura 2.3.(b), si proyectamos elcubo 2, obtendremos elcubo 3, el cual se muestra en laFigura 2.4.

De laFigura 2.4.b, si seguimos latrayectoriamarcada por las flechas obtendremos la siguientetabla, en donde deuncarcteraotroexiste unsolo cambio; otra caracterstica de latabla, es elreflejoque existe entre los caracteres1-2y5-6de la columnaCy elreflejoentre los caracteres2-3-4-5en la columnaB. Elreflejoque existe siempre es con respecto aleje central de simetra.

Ahora que tenemos elcubo 3, podemosobtenerlarepresentacinen la forma de laFigura 2.3.(a),(b)y(c), lo cual se muestra en laFigura 2.5.

Ellevantamientodelcubo 3, a partir de laFigura 2.5, se muestra en laFigura 2.6.

Ahora, si asignamos una rea a cada punto, como se muestra en laFigura 2.7, seobtendrlarepresentacinque se denominamapadelcuboN, que en este caso fue desarrollado para uncubo 3. Como se tienen8 casilleros, stos corresponden a lascombinaciones de tres variables, la cuales pueden serA,ByC, siendoAlams significativayClamenos significativa, por lo que latabla funcionalpara presentar estemapaes:DECCDIGO

BINARIOGRAY

ABCG1G2G3

01234567000011110011001101010101000011110011110001100110

Laprimera tablacorresponde alcdigo binarioy la otra corresponde alcdigo especialque en realidad se le conoce comocdigo de Grayocdigo reflejado. Como veremos, amboscdigosestn implcitos en elmapa de Karnaugh. Si observamos el mapa de laFigura 2.8.(d), cada casillero tiene asignado un nmero, el cual corresponde a unnmerodelcdigo binario. De la mismafigurapero del inciso(e), si seguimos la trayectoria marcada por las flechas, cadanmerorepresenta a un carcter delcdigo Gray.

En latablaanterior, se muestran cada uno de loscdigosmencionados.2.2 Procedimiento para MINIMIZAR una FUNCIN por MAPAS K En forma definitiva, el mapa que se utilizar para laminimizacindefunciones booleanascontres variables, ser el que se muestra en laFigura 2.9.(d). A continuacinexplicaremosla forma como se utilizar en este mapa. Lospasosa seguir sern los mismos para cualquiermapa, no importa cual sea elnmero de variables.1.De ladefinicindel problema y de latabla funcionalse obtiene lafuncin cannica.2.Losminitrminosomaxitrminosde lafuncin cannicase trasladan al mapaK. Se coloca un1si esminitrminoy0si esmaxitrmino.3.Serealizanlosenlacesabarcandoelmayor nmero de trminosbajo los siguientes criterios:a)Elnmero de trminosque seenlazan(agrupan) deben seguir laregla de formacin binaria,es decir, de1en1, de2en2, de4en4, de8en8, etc.b)Alagruparlostrminos, se debe cuidar lasimetracon losejes centralesysecundarios.4.El hecho de que se haya tomado untrminopara unenlaceno quiere decir queste mismono puedautilizarsepara otrosenlaces.5. Lafuncin reducidatendrtantos trminoscomoenlacesse hayan realizado.6.Para obtener eltrmino reducidose realizandos movimientossobre el mapa,uno vertical, quebarrea lasvariables ms significativasyotro horizontal, que barre a lasvariables menos significativas.7.Se aplican los siguientespostulados:A . A' = 0A . A = A

EJEMPLO 1.Disearuncircuito lgico combinatorioquedetecte, medianteUNOS, losnmerosparespara una combinacin de3 variables de entrada.SOLUCINa)Diagrama a bloques. El diagrama a bloques se presenta en la figura adjunta.

b)Tabla funcional: Para propsitos del problema, se considera a0como un nmeroimpar:DECABCZ

0123456700001111001100110101010100101010

c) Funcin cannica.Z = Sumaminitrminos (2,4,6)d) Reduccinpormapas de Karnaugh.La figura adjunta muestra losminitrminosde lafuncin de conmutaciny losenlacesCorrespondientes.e) Obtencinde lafuncin reducida.Del mapa, figura anexa, se observa que existendosenlaces; por lo tanto la funcin reducida tendrdos trminos, de acuerdo con elpaso5delprocedimiento de reduccin.

Para cadaenlace, serealizaelbarridoparacada una de las variables. Por orden, es conveniente iniciar con lavariable de mayor peso binario, en este casoA.Como se muestra en lafigura adjunta, una parte delenlace(1), el elemento6, se encuentra dentro delbarridoy otra, el elemento2, fuera de l. Esto indica que se tieneA.A', que es igual a0, por lo que esa variableno participa, seelimina, deltrmino reducido.Para mayor claridad, tomemos la suma de losminitrminos2y6:

A'BC' + ABC' = (A' + A)BC' = BC'Como puede observarse, la variableAseeliminadeltrmino reducido.

Lafigura adjuntapresenta elbarridodeB. En este caso, elenlace(1)est contenido dentro delbarrido, lo cual corresponde aB.B = B, lo que significa que esta variableforma parte del trmino reducido.

Finalmente, elbarridode la variableC, demenor peso binario, eshorizontaly se muestra en lafigura adjunta. Claramente se observa que elenlace (1) est fuera del barrido, es decir se encuentra enC', indicando que dicha variableforma parte del trmino reducido. Eltrmino reducidocorrespondiente alenlace (1)esBC'. Siguiendo el mismo procedimiento y apoyndonos en las3 figuras previas, se encuentra que para elenlace (2), eltrmino reducidoesAC'. Lafuncin reducidaen este primer ejemplo es:Z(A,B,C) = BC+AC(1) (2)