[MÚSICA] Hola, continuamos con el capítulo 4, el módulo 4 implementación optimizada de funciones lógicas. Veamos cuál es la motivación a estos vídeos. La idea es la siguiente, nosotros sabemos como por ejemplo, tomar una función cualquiera que sea y convertirla en suma de productos o productos de suma. ¿Pero cómo sabemos que esa implementación es óptima? Para ello, vamos a estudiar mapas de Karnaugh que son una forma muy práctica y muy sencilla de implementar funciones óptimas. La idea es la siguiente, aquí vamos a partir con un ejemplo, esta es una tabla de verdad dónde tenemos tenemos el minterm el número de minterm aquí. Aquí tenemos el x 1, x 2, x 3, que son las entradas y tenemos f que es la salida. Esto es una tabla de verdad cualquiera arbitraria y la función la podemos expresar como la suma de los minterms 0, 2, 4, 5 y 6, que son los minterms que tienen un 1 como salida. Cómo dije hasta ahora hemos usado manipulación del álgebra Booleana para encontrar una expresión mínima, pero cuando crece el número de entradas este procedimiento suele volverse bastante más complejo. Entonces para ello existen los mapas de Karnaugh, que son una forma alternativa para representar una tabla de verdad. Y es una forma alternativa que además nos permite visualizar inmediatamente cuál es la implementación óptima, suena como increíble pero así es. Y quiero que lo estudiemos. Les comento que los mapas de Karnaugh no son la forma actual que utiliza el software para implementación o para síntesis de circuito, porque existen otros algoritmos similares, pero que son mejor instalables cuando hay funciones de muchas entradas. Pero para pocas entradas lo estándar es aprender mapas de Karnaugh que funcionan bien hasta 5 entradas. Entonces, es cómo dije una forma alternativa de representar una tabla de verdad. Vamos a hacerlo de modo que los minterms adyacentes en esta representación alternativa que se llama mapa de Karnaugh, puedan ser agrupados bajo ciertas condiciones y ahí producen funciones mínimas y vamos a aprender a agrupar esos minterms. Entonces cada celda de un mapa de Karnaugh corresponde a una fila de la tabla de verdad de la función, vamos a ver cómo funciona esto. Esto es una tabla de verdad típica, aquí tenemos minterm 0, minterm 1, minterm 2 y minterm 3, que podrían ser lo que sea podrían ser 1, 0, 0, 1, da lo mismo. Vamos a llamarle m 0, m 1, m 2 y m 3. Y aquí tenemos x 1 y x 2. Y tenemos los diferentes valores para x 1 y x 2 y ésta es una tabla de verdad. Ahora, existe la representación a traves de un mapa de Karnaugh dónde la tabla de verdad se representa x 1 en un eje, aquí esos son los valores de x 1, x 2 en otro eje y en las intersecciones, por ejemplo, cuando x 1 vale 0 y x 2 vale 0, x 1 vale 0, x 2 vale 0, ponemos m 0. Y donde x 1 vale 0 y x 2 vale 1, x 1 vale 0 y x 2 vale 1, ponemos m 1. Luego m 2 va en esta celda y m 3 va en esta celda, entonces digamos que un mapa de Karnaugh es simplemente otra forma de dibujar una tabla de verdad, pero es una forma interesante, ingeniosa porque nos permite visualizar la optimización directamente. Entonces, si la función posee n entradas, x 1, x 2 hasta x n, entonces el mapa va a tener 2 a la n celdas. Eso es esperable y esto es simple cuando n es menor que 5 o igual a 5. Si tenemos más de 6 entradas se vuelve un poco complicado, no es imposible pero para eso hay software que nos permite hacer esto mismo. Entonces entendamos esto a través de un ejemplo, cómo funciona los mapas de Karnaugh. Vamos a hacer un ejemplo de 2 variables, tenemos nuestra función f de x 1, x 2, va a ser x 1, x 2, más x 1 negado, x 2 más x 1, x 2 todo negado. Hacemos la tabla de verdad para las 4 posibilidades x 1 y x 2 aquí están y aquí tenemos la función que cumple con esta fórmula. Entonces luego hacemos el mapa de Karnaugh, el mapa de Karnaugh nos muestra que cuando x 1 es 0 y x 2 es 0, cuando x 1 es 0 y x 2 es 0 la función vale 1, ahí está. Cuando x 1 es 0 y x 2 es 1, la función vale 1. Cuando x 1 es 1 y x 2 es 0, la función vale 0. Y cuando ambos son 1, la función vale 1. Y ese es mi mapa de Karnaugh, no es muy complicado. Entonces aquí viene la magia del mapa de Karnaugh. Si queremos simplificar funciones usando un mapa de Karnaugh, lo que hay que hacer es intentar crear grupos de celdas que valgan 1, grupos adyacentes de manera lograr expresiones más compactas. Entonces vamos a agrupar todas las celdas posibles que valgan 1 y que sean adyacentes. Ojo que no nos sirve agrupar por ejemplo, 3 celdas. Tienen que ser 4 celdas o tienen que ser 2 celdas o tienen que ser 8 celdas, en general, potencias de 2, desde 1 hacia adelante. Eso sirve. Y lo otro importante en los mapas de Karnaugh, es que yo no puedo agrupar haciendo una forma arbitraria, por ejemplo, estas 2 no sirven. No sirven agrupar estas 2, hay que agruparlas en vertical o en horizontal formando rectángulos a partir de un rectángulo de 1 por 1 o de 2 por 1 o de 4 por 2. Siempre resguardando que el ancho y el alto del rectángulo sean potencias de 2, cuando hacemos eso es visualmente muy fácil encontrar el óptimo. De acuerdo, entonces los grupos como dije deben ser arreglos regulares de un número de celdas que sea potencia de 2, tanto en ancho como en alto. Aquí encontramos 2 grupos, 2. Encontramos este grupo que está marcado en verde y este grupo que está marcado en azul. Este grupo es de 1 por 2 y este otro grupo es de 2 por 1, ambos son potencias de 2 así que no hay problema. Y luego, vemos ¿cuándo la función da 1? Bueno, da 1 en este caso, cuándo da 1 cuando x 2 vale 1, cuando x 2 vale 1, y da lo mismo cuánto valga x 1. Porque cuando x 2 vale 1, da lo mismo si es x 1 es 0 o x 1 es 1, la función va a valer 1. Por lo tanto, ponemos aquí x 2 que es el término que aparece aquí. Luego, para este otro término que es el término en verde, decimos cuando x 1 vale 0, da lo mismo cuánto valga x 2 si es x 1 vale 0, la función va a ser 1. Entonces ponemos x 1 negado, porque cuando x 1 vale 0, x 1 negado vale 1 y la función por lo tanto vale 1. Entonces esta función así como está va a ser exactamente la simplificación de esta función. Wow, lo que hicimos fue simplificar de aquí a acá, visualmente. Gracias a una forma ordenada de poner los minterms en una tabla que se llama mapa de Karnaugh. Eso es súper interesante. Vamos a aprender algo más sobre los mapas de Karnaugh. Existe un concepto que se llama la distancia Hamming entre 2 palabras digitales. Entonces nosotros you vimos que podemos expresar 2 números en base binaria usando dígitos binarios. Por ejemplo, el número 13 en base 10 es 1, 1, 0, 1 en base 2. Eso sabemos hacerlo. La distancia Hamming entre 2 números binarios como éste, corresponde al número de dígitos diferentes entre esos 2 números. Por ejemplo, les pregunto, ¿cuál es la distancia Hamming entre este número binario y este número binario? Pongan pausa, piénsenlo y me cuentan. Okey, veamos. Este es el mismo, este es el mismo, este es el mismo, este es el mismo, este es el mismo, éste no. Este es el mismo y este es el mismo. Por lo tanto, hay 1 número en la misma posición que es diferente, un bit por lo tanto la distancia Hamming aquí es 1. ¿Qué hay con este? Pónganle pausa y me cuentan. Okey, distancia Hamming aquí este es igual, este es igual, este es igual, este es igual, este es igual, este es igual, este es igual, este es igual. Son idénticos, la distancia Hamming es 0, porque son idénticos, entonces cuando dos números son idénticos, su distancia Hamming es 0. Cuando dos números varían por un bit, su distancia Hamming es 1 y cuando dos números varían por n bits, su distancia Hamming es n. Entonces existen formas de escribir o codificar números binarios, de manera que la distancia Hamming entre dos números consecutivos, sea siempre 1, que no es simplemente expresar números binarios de esta forma. Ejemplo, de lo que no es distancia Hamming 1, a ver si yo tengo el número 3 por ejemplo en decimal, vamos a ponerle en base 10, es 0 1 1. ese es el 3. Y el 4 en base 10, va a ser 1 0 0. La distancia entre esos dos números es 1. Pero la distancia Hamming es 1 2 3. Guao, están super separados, aunque el 3 está al lado del 4, en binario la distancia Hamming entre ellos, es 3, guao, bueno. Es posible cambiar esta codificación, no usar esta codificación típica y al terminar un poco las posiciones de los números, de manera que siempre la distancia Hamming sea 1. Estos códigos especiales se llaman códigos Gray y tienen muchas aplicaciones, algunas de las cuales tal vez veamos como ejemplo, pero la primera de las aplicaciones va a ser en mapas de Karnaugh. Entonces código Gray, aquí hay un código Grey de 0 0 0, 0 0 1, esto está en binario estándar, esto está sin código Grey y con código Grey cambió y ¿cómo cambio? Bueno la distancia Hamming entre esta y esta es 1, la distancia Hamming entre este y este es 1, la distancia Hamming entre este y este, este se repite, este se repite es 1, entonces todos los números están distanciados 1 y yo puedo ponerles el nombre que quiera a cada uno de estos números, lo importante es entender que esta codificación con códigos Grey, hace que cada una de las cifras estén distanciados con distancia Hamming 1. Para crear un código Grey en forma fácil, podemos hacerlo por reflexión. Esto se llama Reflected Binary Code o RBC por ejemplo, yo parto con 0 1 y aquí pongo 0 0. Entonces parto con este pedazo y este pedazo lo replico pero poniendo un espejo aca, si pongo un espejo aca, el 1 queda aca, el 0 queda aca y para este segundo dígito, en ves de espejarlo, lo cambio y me queda 0 0 1 1. Teniendo esta base espejo todo esto, o sea este que es 0 convierte en 0, este que es 1 convierte en 1, este que es 1 convierte en 1, este que es 0 convierte en 0, espejo esto estos dos 0 aparecen aca, estos dos 1 aparecen aca y el tercer bit, aquí pongo puros 0 por un lado, pongo puros 1 en el otro y de esa forma uno puede crear un código Grey binario. Esta no es la única forma de crear códigos Grey, pero es una forma de crear más bien de crear códigos que estén a distancia 1 pero es una de las formas. Okey, aplicando lo anterior, vamos a aprender cómo ocurren estos minterms en mapas de Karnaugh de tres variables. Para ubicar los minterms en un mapa de Karnaugh de tres variables, tenemos que aplicar códigos Grey, porque sino no nos van a aparecer los adyacentes donde debieran estar. Entonces aquí tenemos, nuestro 0 0 0, 0 0 1, 0 1 0, 0 1 1, esto es binario estándar, esta tabla en verdad está escrita en binario. No está con código Grey, lo que hacemos en código Grey es el mapa de Karnaugh. Entonces vamos a poner por un lado x1 x2 y por otro lado x3 y esto es lo que ponemos en código Grey. Entonces si se fijan, 00, 01, 11, 10, entonces aquí está 0 distancia Hamming 1, 01 distancia Hamming 1, 11 10 distancia Hamming 1 y de aquí a aca, la distancia Hamming también es 1, entonces entre dos celdas adyacentes, you sea que están una al lado de la otra o una en un extremo respecto al otro, la distancia Hamming es 1. A eso responde esta pregunta. ¿Cuál es la distancia Hamming de las celdas del extremo derecho y del izquierdo? Acabamos de ver que es 1. Entonces esta disposición mediante código Grey, asegura que la distancia Hamming entre celdas adyacentes sea 1 y esto permite visualizar, directamente los términos que se puedan agrupar, entonces para escribir los minterms ponemos m0, m1, m2, m3, ojo aquí, m4, m5, m6, m7. ¿Cómo llegué a eso? m0 es cuando todos valen 0, perfecto, m1 cuando x3 vale 1 y los otros dos valen 0, m1. m2 sería este cuando x0 vale 0, x1 vale 1 y x3 vale 0 y cuando x1 vale 0, x2 vale 1 y x3 vale 1 tenemos este término. m4, ¿qué pasa en m4? x1 vale 1 y x2 y x3 valen 0. x1 vale 1, podía ser cualquiera de estos dos y x2 y x3 valen 0, eso ocurre aquí m4 y así uno va llenando esta tabla, asegurándose que los minterms estén en la posición correcta. Vamos a ver, ¿por qué nos sirve hacer esto? Este es un ejemplo de tres variables, aquí tenemos una tabla de verdad estándar binario, tenemos los minterms que valen 0, 1 etcétera y aquí tenemos el mapa de Karnaugh que llenamos exactamente de esta forma. m0, m1, m2, m3, m4, m5, m6, m7. Entonces lo hacemos aquí, m0, m1, m2, m3, m4, m5, m6, m7. Okey llenamos el mapa y ahora agrupemos. Vamos a agrupar por ejemplo estos dos 1 que están aquí y agrupamos estos dos 1 que están aquí y no hay más, eso es todo. Entonces ahora tenemos que crear la función apartir del mapa. La función va a tener dos términos, porque tiene dos grupos. Un término por cada grupo. Este grupo me dice lo siguiente, mira hay que mirar aquí los que no cambian, los términos que no cambian, los que cambian desaparecen de la expresión. ¿Cómo es eso? Así mira, aquí x1 no cambia, entonces cuando x1 vale 1, la expresión existe, x2 cambia por lo tanto x2 no aparece en la expresión y x3 no cambia, x3 sigue siendo 0 en estos dos números, por lo tanto x3 aparece, pero como aquí es 0, x3 aparece negado, entonces los términos que cambian y son 1, aparecen directamente en la expresión, los términos que cambian y son 0 aparecen negados en la expresión, esa es la regla que vamos a usar. Y los términos que no cambian desaparecen de la expresión, perdón los términos que si cambian desaparecen de la expresión. Entonces tenemos f va a ser independientemente de cuánto vale x2, porque x2 cambió, x2 valía 1 aquí, valía 0 aquí, x2 cambia por lo tanto x2 no va en la expresión. El que no cambia es x1 y x1 vale 1 siempre que estos dos sean 1 por lo tanto pongo x1 solito y luego x3 no cambia, por lo tanto va en la expresión x3 vale 0 aca, como vale 0 pongo x3 negado en mi expresión. Voy hacer lo mismo para el otro grupo. En el otro grupo, x3 no cambia, x1 si cambia, por lo tanto x1 desaparece de mi expresión y x2 no cambia. x2 en ambos términos del grupo, x2 vale perdón aquí está, x2 vale 0, cómo x2 vale 0, pongo x2 negado aquí y x3 vale 1, por lo tanto pongo x3 sin negar y esta expresión es la misma, que me permite implementar esta función. A veces uno duda de que pongo primero, que pongo aquí, x3, x1, x2, etcétera, mientras sean consistentes no hay problema, yo les recomiendo que busquen una forma que les acomode. Por ejemplo esta forma aquí de poner x1 y x2, pensamos que este es bit más significativo y este es el menos significativo, me acomoda a mí, pero ustedes pueden buscar algo que les acomode. Las celdas de los extremos derechos e izquierdos, se ven distanciadas, están lejos pero en realidad están a distancia Hamming igual a 1 porque esto es circular, esto se, perdón esto se devuelve desde la derecha hacia la izquierda, asi que es circular por lo tanto están a distancia Hamming igual a 1. Pregunta, ¿cuál es la distancia Hamming entre el término de abajo y el de arriba? Es 1, si pero ¿será 1 también si la miro desde el otro lado? Es lo mismo es realmente lo mismo, pero es distancia Hamming 1. Muy bien, este es otro ejemplo de tres variables, tenemos otra tabla de verdad distinta, ¿sí? Es distinta, son números distintos aquí y aquí podemos agrupar de otra forma, vamos a agrupar estos 1s que están aca, y estos dos 1. A ver en estos dos 1 que están aca, ¿cuáles cambian y cuáles no cambian? Bueno, x1 y x2 ambos cambian, por lo tanto ambos desaparecen en la expresión. Y x3 no cambia, se mantiene 0 en todos estos cuatro 1. Por lo tanto pongo x3, pero como es 0 aquí, lo pongo negado aca. ¿Qué pasa con estos otros dos? Con estos otros dos x, ¿cuál cambia aquí? x3 cambia, x3 vale 0 aquí y x3 vale 1 aquí, como x3 cambia, x3 desaparece de esta expresión, x3 desaparece y esta expresión va a valer x1, porque x1 no va negado y x2 negado porque x2 vale 0 aquí. Suena un poquito como un trabalenguas, pero cuando ustedes aprendan a hacerlo, no van a tener ningún problema. Esto es fácil y hasta es entretenido. Y con eso tengo mi expresión óptima, interesante. you, esto es interesante porque mientras más grande el grupo, más pequeña es mi expresión. Entonces yo tengo un incentivo de buscar grupos grandes, tengo un incentivo de buscar y podrían haber sido grupos, podría haber elegido este grupo, este y este. Pero eso no son grupos suficientemente grandes, este grupo y este grupo, pero no son grupos lo suficientemente grandes. Podría haber elegido este grupo y este grupo, pero me habría dado más expresiones. Entonces si yo puedo hacer grupos grandes funciona muy bien, pero no puedo hacer grupos grandes con formas raras, por ejemplo si aquí yo hubiera tenido un 1, yo no puedo hacer un grupo con esta forma, porque tienen que ser grupos rectangulares donde el ancho y el alto, son potencias de 2. La forma de hacerlo en ese caso habría sido, tomar este grupo que es grande y este que está solo agruparlo de la forma que me quede un grupo grande, del que haga un grupo grande, se me simplifica. Okey, salió larga la clase, pero es una clase muy importante. Hoy día aprendimos mapas de Karnaugh de dos y tres variables, aprendimos distancia Hamming que es muy útil para hacer mapas de Karnaugh y aprendimos códigos Gray, guao. Fueron muchas cosas. Okey nos vemos en la próxima.
