Metodo de quine mccluskey resumen basico teoria PDF

Preview

Summary

Teoría muy básica de cómo funciona el método. NOTA: sin código ejemplo de programación en compilador...

Description

Método de reducción de expresiones booleanas por la técnica de QuineMcCluskey Cardona Caudillo Carlos Alberto El método de simplificación de funciones booleanas desarrollado por Willard Van Orman Quine y Edward J. McCluskey. Es funcionalmente idéntico a la utilización del mapa de Karnaugh, pero su forma tabular lo hace más eficiente para su implementación en lenguajes computacionales, y provee un método determinista de conseguir la mínima expresión de una función booleana. Antes de comenzar con la descripción del algoritmo de Quine-McCluskey debemos comprender algunos conceptos importantes para la correcta interpretación de la información presentada. Cubos-n y distancia Una cadena de n bits puede visualizarse geométricamente, como un vértice de un objeto llamado cubo n. Un cubo n tiene n 2 vértices, cada uno de los cuales está rotulado con una cadena de n bits. Las aristas se dibujan entre vértices adyacentes cuyos rótulos difieren del vértice dado en solo un bit. Más allá de n=4 , los cubos son muy complicados de dibujar. Los cubos también proporcionan una interpretación geométrica para el concepto de distancia también llamada distancia de Hamming. La distancia entre dos cadenas de n bits es el número de posiciones de bits en que difieren.

Un subcubo m de un cubo n es un conjunto de m vértices en los que n-m de los bits 2 tienen el mismo valor en cada vértice, y los restantes m bits toman todas las 2m combinaciones. Implicar Una función lógica

P ( X 1 ,… X n ) implica F ( X 1 , … X n ) si para

una función lógica implicar cada combinación de entrada tal que P=1 , entonces también F=1 . Implicante primo Un implicante primo de una función lógica F ( X 1 , … X n) es un término producto normal P ( X 1 ,… X n) que implica a F, de manera que, si cualquier variable se remueve de P, entonces el término producto resultante no implica a F. En términos de un mapa de Karnaugh, un implicante primo de F es un conjunto circundado de celdas 1 que satisfacen nuestra regla de combinación, tal que si tratamos de hacerlo más grande (cubriendo dos veces tantas celdas), cubre uno o más cero.

Ilustración 2. Implicantes primos

La suma de todos los implicantes primos de una función lógica se llama suma completa. Ilustración 1. Cubos n para n=1, 2, 3 y 4

Una celda 1 distinguida de una función lógica es una combinación de entrada cubierta por un solo implicante primo.

posibilidades para cada variable en un término producto general:

Un implicante primo esencial de una función lógica es un implicante primo que cubre una o más celdas 1 distinguidas.

0  No complementada

Ya que un implicante primo esencial es el único implicante que cubre alguna celda 1, debe incluirse en cada suma mínima de la función lógica.

Estas posibilidades se representan mediante una cadena de n de los dígitos anteriores, en la representación cúbica de un término producto.

1  Complementada

X  No aparece

Vamos a explicarlo con un ejemplo: Estamos trabajando con términos producto de 8 variables, X7, X6,…,X0, podemos escribir los siguientes términos producto y sus representaciones cúbicas: '

'

'

X 7 ∙ X 6 ∙ X 5∙ X 4 ∙ X 3 ∙ X 2 ∙ X 1 ∙ X 0 ≡ 01101110

X 3 ∙ X 2 ∙ X 1 ∙ X 0 ' ≡ xxxx 1110 Ilustración 3. (a) Mapa de Karnaugh, (b) implicantes primos y celdas 1 distinguidas, (c) mapa reducido por la acción de remover los implicantes primos esenciales y las celdas 1 cubiertas

La mayoría de las funciones lógicas combinacionales son muy grandes como para minimizarse usando el método de los mapas de Karnaugh, por lo que es importante minimizarlas de alguna manera. Para esta encomienda nos apoyaremos del algoritmo de Quine-McCluskey. Al igual que todos los algoritmos, el algoritmo de Quine-McCluskey puede traducirse a un programa de computadora. El algoritmo tiene dos pasos: 1.) Encontrar todos los implicantes primos de la función. 2.) Seleccionar un conjunto mínimo de implicantes primos que cubran la función. El punto de partida para el algoritmo de Quine-McCluskey es la tabla de verdad o, su equivalente, la lista de minitérminos de la función. Debemos representar tres

X 7 ∙ X 5 ' ∙ X 4 ∙ X 3 ∙ X 2 ' ∙ X 1≡ 1 x 01101 x

X 6 ≡ x 1 xxxxxx Para representar un término producto en un programa de computadora, podemos usar una estructura de datos con n elementos, cada uno de los cuales tiene tres valores posibles. Hay varias metodologías para desarrollar el algoritmo de Quine-McCluskey, en este documento se expondrá la metodología llamada búsqueda de implicantes primos al combinar términos producto. Bien, el primer paso en el algoritmo de Quine-McCluskey es determinar todos los implicantes primos de la función lógica. En el algoritmo computacional se debe aplicar sistemática y repetidamente el teorema , esto con el fin de X ⋅Y +X ⋅Y ' =X combinar los minitérminos, luego los cubos1, cubos-2 y así sucesivamente, creando los cubos más grandes posibles que cubren solamente los 1 de la función. Si una función de n variables tiene un término producto igual a una sola variable, entonces

son necesarios 2n−1 minitérminos para cubrir ese término producto. Para cubos más grandes la situación es en realidad peor. El número de subcubos-m posibles de un cubo- n es el coeficiente binominal

( mn ) × 2 , donde ( mn ) el número m

de maneras de elegir m variables como x y 2m es el número de maneras de asignar 0 y 1 a las variables restantes. Para funciones con 16 variables m=11 ; hay 8,945,664 posibles subcubos-11 de un cubo-16. El número total de los subcubos-m distintos de un cubo-n, para cualquier valor de m, es 3n . Aún usando un algoritmo computacional descrito, los problemas relacionados con la minimización de funciones mediante el algoritmo de Quine-McCluskey está limitado a funciones con 15 < variables< 20 , ya que usan muchísima memoria y no concluyen o no ejecutan correctamente el proceso. Bibliografía [1]Algoritmo Quine–McCluskey (2018). Recuperado el 27/09/2018 de: https://es.wikipedia.org/wiki/Algoritmo_Quin e–McCluskey [2]Wakerly, J. (1992). Diseño digital Principios y prácticas. México: PRENTICE -HALL HISPANOAMERICANA....