Con la tecnología de Blogger.

Mapas de Karnaugh

sábado, 6 de agosto de 2011

Introducción

En la actualidad y desde hace ya muchos años, el hombre en su vida diaria se expresa, se comunica, almacena información y la maneja, etc. , desde el punto de vista numérico con el sistema decimal y desde el punto de vista alfabético con un determinado idioma.

Asimismo, la computadora, debido a su construcción basada fundamentalmente en circuitos electrónicos digitales, lo hace desde ambos puntos de vista con el sistema binario, utilizando una serie de códigos que permiten su perfecto funcionamiento.

Este es el motivo que nos obliga a transformar internamente todos nuestros datos, tanto numéricos como alfanuméricos, a una representación binaria para que la maquina sea capaz de procesarlos.

Códigos Numéricos

El sistema numérico binario, es decir, el código numérico binario, tiene el merito de que sus dígitos tienen una correspondencia exacta con los valores de una variable lógica.

Sin embargo, tiene una desventaja, ya que una magnitud numérica expresada en código binario requiere más de tres veces tantos dígitos como el numero equivalente. Este inconveniente se puede resolver empleando el código octal o el hexadecimal.

Otra desventaja de este código se refiere a las conversiones, inversa y directa entre digito binario y decimal. Las conversines son relativamente complicadas, cada digito binario puede afectar a cada decimal y viceversa.

Cuando es importante poner remedio a esta situación, puede utilizarse el sistema de representación decimal codificado binario (BCD) o tendremos ocasión de utilizar un segundo código denominado código reflejado.

Código Gray y Binario Reflejado

Es un código continuo y cíclico.

Continuo: porque al pasar de una combinación válida del código a la siguiente, se cambia un único bit.

Cíclico: porque también hay un bit de diferencia entre la última y la primera combinación válida.

Código: conjunto de significado o reglas asociadas a un grupo de bits. Toda combinación de datos posee un significado determinado, basado en reglas determinadas.



Es reflejado porque al codificarlo tengo que suponer que se refleja en un espejo para formarlo

Ejemplo 1: Código Gray para tres bits y binario para tres bits




Ejemplo 2: Código Gray para cuatro bits y binario para cuatro bits


Conversión de binario a Gray                                   Conversión de Gray a binario
Si Bn = Bn + 1 => Gn = 0                                           Si Bn = Gn + 1 => Bn = 0
Si Bn Bn + 1 => Gn = 1                                           Si Bn Gn + 1 => Bn = 1

Para resolver problemas con circuitos lógicos existen dos formas:

a) Análisis: dado un circuito encontrar la función lógica que cumple a su salida.

b) Sintaxis: encontrar el circuito suponiendo que se parte de una especificación.

1º Tabular la especificación (hacer tabla de verdad)
2º Mapearla (hacer el mapa de Veitch-Karnaugh)
3º Simplificarla (hacer la expresión más simple)
4º Implementarla (o sea colocar las compuertas para realizar esa función)

Mapa de Veitch-Karnaugh

Normalmente llamado mapa K, se lo utiliza para sintetizar funciones lógicas en forma gráfica y rápida. Agrupando los “1” (unos o mintérminos) obtenemos expresiones con la suma de productos; mientras que si se agrupan los “0” (ceros o maxtérminos) se obtienen productos de la suma. Para realizar el mapa K se utiliza el código Gray.

El mapa K es muy cómodo para sintetizar problemas de más de dos variables de entrada. Permite sintetizar funciones sin aplicar las leyes del álgebra de Boole. Es decir, que permite encontrar la primera y segunda forma canónica, así como las expresiones con el mínimo número de letras y operandos. Se recorre de la siguiente manera:


Construcción del mapa K para 2, 3 y 4 variables e identificación de las zonas

a) Mapa K con 2 variables   b) Mapa K con 3 variables
c) Mapa K con 4 variables



Implicantes Primos en la Minimización

Se llama implicantes primos (IP) a las agrupaciones de máximo número posible de celdas adyacentes tales que el recuadro que las abarca no puede estar incluido en otro recuadro que permita una agrupación mayor de celdas. Los IP dan lugar a productos con el menor número de variables, objetivo de la minimización. Se llama implicantes primos no esenciales a aquellos que presentan entre las celdas que agrupan uno o más unos compartidos con otros implicantes primos. En caso contrario, se llaman esenciales. En consecuencia, el primer paso para minimizar consiste en encontrar todos los IP existentes. Esto es la base para llevar a buen fin una minimización usando el diagrama, siendo esta la principal causa de los errores que se cometen.

Una vez determinados todos los IP, se podrá decir cuáles de ellos son necesarios para cubrir todos los “unos” del diagrama, y cuáles son redundantes, amén de poder reconocer más de una solución mínima.

Así mismo, el concepto de IP apunta al objetivo de determinar y solucionar aquellos agrupamientos de celdas que permitan obtener simultáneamente una suma de productos (SP) con mínimo número de sumandos, constituidos por los productos con el menor número de variables, como se pretende.

Determinados en un diagrama la totalidad de IP posibles, hay que ver cuáles de ellos, denominados IP “no esenciales”, tienen todos los unos que agrupan enlazados por otros IP, dado que según el caso pueden aparecer o no en la SP mínima buscada, los productos correspondientes a ellos. Esta función mediante el cálculo algebraico se obtiene:



Los pasos realizados se pueden hacer sin usar álgebra, por ejemplo, los cuatro primeros sumandos son directamente los correspondientes a los cuatro unos adyacentes enlazados en la parte superior del diagrama y los dos siguientes se corresponden con los dos “unos” adyacentes enlazados en la parte inferior. En el diagrama de Karnaugh las variables coordenadas de un lazo (en la obtención de SP mínimas) con la conversión de los mintérminos 0 = -A y 1 = A (lo mismo para cualquier otra variable).

En general, enlazando dos celdas adyacentes en un diagrama se elimina una variable en el producto correspondiente a ese lazo. En el caso de enlace de cuatro celdas adyacentes en un diagrama se eliminan dos variables con el producto de ese lazo y en el caso de ocho celdas adyacentes se eliminan tres variables en el producto correspondiente a ese lazo. Dejando de lado el proceso de minimización algebraico, el diagrama permite llegar al mismo resultado, siguiendo estos pasos:

1) Se enlazan las celdas con “unos” adyacentes buscando lazos que engloben a otros.

2) Cada sumando de la expresión minimizada, es el producto que se forma con las variables que son las coordenadas de cada lazo considerado.

3) La expresión SP mínima buscada es la suma de todos los productos hallados según el paso anterior.

Una suma de productos será mínima si no existe otra suma de productos con menor número de sumandos, ni otra de igual número de sumandos pero con menor cantidad de variables lógicas.

Reglas Prácticas para Minimizar

Suponiendo que se tiene una función representada por una cierta disposición de “unos” en el diagrama, los pasos a seguir con vistas a obtener soluciones con el menor número de lazos, siendo que cada uno de estos encierra la mayor cantidad de celdas adyacentes agrupables pueden ser:

1) Encontrar todos los IP de la función para lo cual:

Procurar primero formar todos los lazos posibles que contengan ocho celdas adyacentes. Con celdas que no fueron cubiertas en el paso anterior tratar de formar todos los lazos posibles que contengan cuatro celdas adyacentes.

Si aún quedaran celdas que se pueden enlazar como dos adyacentes, formar todos los lazos posibles de este tipo.Luego del paso anterior sólo pueden quedar sin enlazar celdas aisladas, que constituirán lazos con una celda.

2) Preferiblemente indicar en punteado los lazos que tienen todos sus “unos” compartidos con otros lazos, o sea los IP no esenciales.

3) Probar si con los lazos en trazo lleno (IP esenciales) se pueden cubrir todos los unos del diagrama, teniendo siempre presente que se busca hacer con esto el menor número posible de lazos.

4) Si con los lazos en trazo lleno no se cubren todos los “unos” del diagrama realizar esto usando el menor número de lazos en punteado disponible.

5) En caso de que los lazos en punteado den lugar a más de una solución mínima, realizar preferentemente un diagrama para cada uno.

6) Para cada paso de solución mínima hallar las variables que son sus coordenadas y formar el producto correspondiente desechando las variables que no intervendrán en el mismo.

7) Cada solución mínima expresarla como suma de todos los productos hallados conforme al paso anterior.

Tener presente que cualquiera sea el número de variables de un diagrama, lazos de ocho celdas eliminan tres variables, lazos de cuatro celdas eliminan dos variables, lazos de dos celdas eliminan una variable y lazos de una celda no eliminan variables originando mintérminos. En general un lazo de 2^n permitirá eliminar n variables.

1º ¿Cuándo podemos agrupar o simplificar 2 unos?

A) Cuando estos sean adyacentes (no en diagonal)
B) Cuando estén en los extremos opuestos de una misma fila o columna



2º ¿Cómo podemos agrupar o simplificar 4 unos?


¿Como podemos agrupar o simplificar ocho unos?


El hecho de que los unos (o los ceros) de las esquinas sean adyacentes resulta de imaginar al mapa como un planisferio de la tierra.

A pesar de que éste se ve en el plano, todos tenemos en mente la idea de que cubre toda una "esfera".

Algo similar ocurre con el "mapa" de Karnaugh (la idea es que cubre todo un "toro", figura geométrica cuya forma es la de una cámara de un neumático de auto).

En resumen, dado el mapa K de una determinada función los pasos a seguir son:

- Enlazar la mayor cantidad de unos de la tabla con la menor cantidad posible de lazos.

- Indicar en punteado los lazos que tienen todos sus unos compartidos con otros lazos, o sea los implicantes primos no esenciales.

- Probar que los implicantes primos cubren todos los “unos” del diagrama con la menor cantidad posible de lazos

-Realizar un diagrama para cada solución mínima .

-Hallar las coordenadas de cada mintérmino y formar el producto correspondiente, desechando las variables que no intervendrán en el mismo. Tener presente que en general un lazo de dos permitirá eliminar “n” variables.

Cómo Simplificar los Mintérminos

1º Se simplifican los mintérminos que son adyacentes y se toman o agrupan de 2, 4, 8, 16...2n . Dos mintérminos son adyacentes cuando difieren en una letra.La suma de dos mintérminos adyacentes es igual al producto de las variables que tienen en común.



2º Los mintérminos que no son adyacentes no se pueden simplificar (A, B, C, D)

3º Si tomo dos mintérminos se elimina una variable, si tomo cuatro se eliminan dos variables.


Dos Soluciones Mínimas

Una misma función puede tener dos o más soluciones mínimas.


Lazos Redundantes

Algunas veces aunque se tenga en cuenta todos los lazos mayores posibles, un subconjunto de ellos puede cubrir todos los “unos” de esa función, en estos casos existe un lazo redundante que viola el principio de que los “unos” queden enlazados con el menor número de lazos posibles.


Esta suma de productos no es mínima, dado que si bien se han tenido en cuenta los mayores lazos posibles, en este caso con un subconjunto. El lazo dibujado en línea punteada que corresponde al producto es redundante, pues agrega un sumando innecesario.


Funciones Incompletamente Especificadas

Cuando una variable de salida no se puede definir con un cero o con un uno en la tabla de verdad se coloca una “x” que significa redundancia o “no preocuparse”. Esto sucede cuando no nos interesa la funciòn de salida o cuando se trata de estados prohibidos que no forman parte de algún código.

La redundancia se puede usar como un comodín, se puede tomar como uno o cero indicidualmente.

Ejemplo: realizar un circuito que (a la salida) encienda una lámpara cuando en su entrada viene el código del 3 y el código es el BCD natural.


Nivel de un Circuito Lógico: es el número de compuertas que atraviesa la señal para llegar a la salida. Cada nivel implica un retardo adicional de tiempo.



Riesgo de un circuito lógico: un riesgo es una breve excursión a un nivel lógico inesperado. La desigual propagación de los retardos en las compuertas puede dar lugar a riesgos. Se llama riesgo a la salida “espuria transitoria” de un circuito lógico combinacional.
Ejemplo: sabemos que


Riesgos Estáticos y Dinámicos

Un riesgo es estático cuando una señal debe permanecer constante y sin embargo toma transitoriamente un valor distinto.

En los ejemplos anteriores, en el primer gráfico es riesgo estático en los unos, y en este último gráfico, en los ceros.

Un riesgo es dinámico cuando una señal que debe cambiar, lo hace un número impar de veces mayor que uno.



Riesgo dinámico que puede importar o no según los siguientes teoremas


1º Teorema: los circuitos lógicos de menos de tres niveles están libres de riesgos dinámicos.

2º Teorema: un circuito lógico que sea la implementación de una expresión simplificada de una expresión obtenida en Mapa K por agrupamiento de unos, está libre de riesgos estáticos en los ceros.

3º Teorema: dual del anterior. Una función lógica por agrupamiento de ceros, está libre de riesgos estáticos en los unos.

Ejemplo:


El problema del riesgo existe cuando se cambia de un minitérmino adyacente a otro pasando de un “1” a otro “1” de dos grupos distintos, entonces para solucionarlo se debe unir esa separación.

Los mapas anteriores son un ejemplo de dos soluciones posibles libres de riesgo, en caso de no tomar en cuenta el riesgo, se obtendrían sólo 3 términos.

Distintas formas de Sintetizar o Simplificar Funciones con el Mapa K

a) Se pueden agrupar las “1” y la función Z será una suma de productos a la salida.

b) Si agrupamos los “0” la función Z será un produto de sumas a la salida.

La utilización de cada uno de estos agrupamientos depende de la tecnología y tipos de compuertas a utilizar.Además, se dividen en 2 grupos, obteniendo 4 expresiones booleanas y 8 circuitos con compuertas distintas; pero cada circuito cumple la tabla de verdad.



Ejemplo: Sintetizar por los cuatro métodos y realizar los ocho circuitos:



Publicar un comentario en la entrada

About Me

Mi foto
Mauricio Vistosi
Ver todo mi perfil

  © Blogger template The Professional Template II by Ourblogtemplates.com 2009

Back to TOP