El anterior artículo de esta serie sobre minimización de funciones lógicas terminaba con una afirmación cuanto menos sorprendente: el algoritmo de Quine-McClusky no siempre devuelve la expresión mínima correspondiente a la forma canónica original, que es la única entrada para el algoritmo.
En éste de hoy, el tercero de los cinco de que se compone la serie, se explica por qué en ocasiones (en muchas ocasiones) el algoritmo tal como está definido en la literatura no encuentra la expresión mínima, y qué se puede hacer para efectivamente encontrarla siempre.
Aquí podéis encontrar el PDF de este tercer artículo.
Hasta el próximo.
Disfrutad de la vida mientras podáis.
The Minimización de Funciones Lógicas. El algoritmo de Quine–McClusky explicado y mejorado-III by , unless otherwise expressly stated, is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 2.5 Spain License.
{ 4 } Comentarios
Hola Macluskey,
Afirmas que el algoritmo de Quine-McClusky no siempre devuelve la expresión (booleana) mínima correspondiente a la forma canónica original. Es cierto. Pero el método no fue diseñado para resolver ese problema, que en inglés se conoce como el Minimum Circuit Size Problem (MCSP). El algoritmo de Quine-McClusky resuelve un caso particular de ese problema, a saber, encontrar una suma de productos mínima correspondiente a la forma canónica original. Por tanto, es normal que exista otras expresiones mínimas correspondiente a la forma canónica original, en particular, su expresión en productos de sumas.
Por otra parte, afirmas: “puedo asegurar que si lo que se desea es optimizar el código de una expresión lógica contenida en un programa fuente da exactamente igual una u otra estructura de la expresión: lo importante es reducir al máximo el número de condiciones de la fórmula para minimizar el número de comparaciones a realizar para determinar el flujo del programa.”
No estoy totalmente de acuerdo con esta afirmación. Esta afirmación se basa en que calcular las condiciones de la fórmula puede ser computacionalmente costoso. Claramente si evitas tener que calcular una condición en una fórmula, eso es una ganancia. Sin embargo, en cuanto tienes que calcular una vez la condición (afirmada o negada), da igual cuantas veces más aparezca en la fórmula. La condición es calculada una vez. Una vez que has obtenido el bit de información, usarla una o más veces es igual de malo que usar una o más veces una puerta AND, OR, etc.
Un saludo.
Gracias, Masek, por tu comentario.
Tengo dudas en lo que comentas sobre que el algoritmo QM no fue diseñado para devolver la expresión (booleana) mínima correspondiente a la forma canónica original.
Mi primer contacto con este algoritmo fue en la Carrera, en 1973 o 1974, y entonces se presentaba como el método para minimizar funciones lógicas a partir de la forma canónica. De forma absoluta. Y yo estudiaba Informática, no Electrónica, por lo que nuestro interés era reducir en lo posible el número de condiciones a testear en los programas. En los programas fuente; la optimización en los compiladores simplemente no existía en la época, donde el lenguaje más avanzado de entonces era el ínclito Cobol…
Ciertamente en el documento de McClusky de 1956 que describe el algoritmo hace mención siempre a minimizar la “suma de productos”, pero si revisas la información en la Red, prácticamente nadie hace mención a esto que tú comentas, y que una vez que se desmenuza el algoritmo resulta obvio: descontando el número de formas canónicas en que ambos métodos (minterms/maxterms) devuelven cadenas de la misma longitud, el número de formas canónicas que obtienen un resultado óptimo tratando los minterms es exactamente el mismo que el número de formas que obtienen un resultado óptimo tratando los maxterms.
Desde el punto de vista del diseño de circuitos lógicos no tengo ni la menor idea de si es mejor una Suma de Productos que un Producto de Sumas, aunque supongo que dependerá de la tecnología a utilizar. Pero si queremos optimizar un programa fuente (no el objeto resultado de la compilación, el fuente), entonces es siempre mejor que la expresión a evaluar tenga el menor número posible de condiciones.
No acabo de comprender tus dudas sobre esta afirmación mía anterior.
Claro que con los compiladores modernos cada condición se evalúa una sola vez, pero el hecho de que la expresión sea una Suma de Productos o un Producto de Sumas poco tiene que ver con esto. Es decir, computacionalmente se evalúa cada condición una vez y luego se gestiona ese bit de información, como comentas, pero en cualquier caso hay que gestionar ese bit tantas veces como aparezca la expresión. Luego no sólo hay que evaluar la condición en sí, hay además que tomar un camino u otro dependiendo de si ese valor es 0 ó 1, y eso exige un cierto tratamiento, sea una comparación, sea un tratamiento booleano…
Cuantas menos veces aparezca una condición, afirmativa o negativa, menos esfuerzo computacional se requiere. Y eso sin tener en cuenta que, si estamos hablando de programas fuente, suelen tener un mantenimiento posterior. Es decir, algún esforzado programador deberá mirar ese programa para modificarlo en el futuro (Al menos cuando yo trabajaba, eso se hacía; ahora, vistas las cosas que pasan en los Grandes Sistemas de Información del Mundo, vaya Vd. a saber). Y cuanto más sencilla sea la codificación, más sencillo será el mantenimiento.
En fin, no sé si he captado todo lo que comentabas. En cualquier caso, gracias de nuevo por tus comentarios.
Saludos
Hola Macluskey.
Es cierto que si uno hace una búsqueda sobre el método de Quine–McCluskey en la Red (por cierto, McCluskey lleva “e”), hay muchos sitios que incorrectamente lo describen como un método para encontrar una expresión booleana mínima sin especificar que es en forma de suma de productos. No tengo ni idea por qué este error está tan extendido. Sería interesante averiguar por qué. Sin embargo, en el trabajo original o cualquier trabajo que haya pasado la revisión por pares encontrarás que el método devuelve una suma de productos mínima.
Respecto a mi otra discrepancia, me acabo de dar cuenta que interpreté incorrectamente tus frases en una lectura rápida. Por un momento había pensado que estabas diciendo que daba igual cuantos ANDs, ORs tuvieras, que lo único importante eran las condiciones. Realmente estamos de acuerdo, no hay discrepancia. Perdona.
Un saludo.
Gracias, Masek, por tu comentario.
Sí, me había extrañado tu duda sobre el número de condiciones de los programas fuente. Perdonado.
No dudo de que lo que dices es cierto, ya había avisado en todos los artículos de la serie que dudaba muchísimo que algo tan “evidente” no hubiera sido “detectado” en los casi 70 años de existencia del algoritmo.
Ya comenté cuál es mi perfil: informático de la era de los dinosaurios debidamente jubilado, y un poco friki (o mucho) de algunos temas concretos, como la minimización de expresiones lógicas. Pero, claro, estoy completamente fuera de los círculos académicos, y no voy a pagar por bajarme artículos que a priori parecían interesantes. Por eso dependo del acceso a los documentos que se pueden encontrar en la Red, siempre que sean gratis. Afortunadamente sí he conseguido acceso al documento original de McClusky, algo es algo.
Por cierto, escribo “McClusky” por dos motivos: porque así lo escribió mi profesor cuando nos contó el método hace cincuenta años y así lo he conocido toda mi vida, y para que no se confunda son mi nick. Nick que, por cierto, no tiene nada que ver con este investigador estadounidense.
Ya lo he explicado en alguna ocasión, pero el nick viene de aquellos tiempos del cuplé, cuando se estropeaba una cinta o la impresora o cualquier otro cacharro, lo que pasaba cada lunes y cada martes… y entonces alguien del Banco en que trabajaba decía “A ver si viene Macluskey desde Oklahoma y lo resuelve…”.
El nombre del tal McClusky fue tomado de la película “La batalla de Midway”, la buena, la de Charlton Heston, Henry Fonda y compañía, porque el aviador americano que descubre a la flota japonesa y al mando de su escuadrón aéreo hunde a los cuatro portaaviones japoneses se llamaba Clarence Wade McClusky… Y ése era un nombre suficientemente exótico para que se quedara en el magín colectivo como el del tipo listo que resolvía las cosas… Más adelante tomaría el relevo otro ilustre Mac: MacGiver.
En fin, perdón por la batallita.
Saludos
Escribe un comentario