Algoritmo Quine-McCluskey - Quine–McCluskey algorithm

Diagrama de Hasse do gráfico de busca do algoritmo para 3 variáveis. Dado, por exemplo, o subconjunto dos nós de nível inferior (verde claro), o algoritmo calcula um conjunto mínimo de nós (aqui :, verde escuro) que cobre exatamente .

O algoritmo Quine-McCluskey ( QMC ), também conhecido como o método de implicantes primos , é um método utilizado para a minimização de funções booleanas que foi desenvolvido por Willard V. Quine em 1952 e estendido por Edward J. McCluskey em 1956. Em geral princípio esta abordagem já havia sido demonstrada pelo lógico Hugh McColl em 1878, foi provada por Archie Blake em 1937 e foi redescoberta por Edward W. Samson e Burton E. Mills em 1954 e por Raymond J. Nelson em 1955.Também em 1955, Paul W. Abrahams e John G. Nordahl, bem como Albert A. Mullin e Wayne G. Kellner, propuseram uma variante decimal do método.

O algoritmo Quine-McCluskey é funcionalmente idêntico ao mapeamento de Karnaugh , mas a forma tabular o torna mais eficiente para uso em algoritmos de computador e também fornece uma maneira determinística de verificar se a forma mínima de uma função booleana foi alcançada. Às vezes é chamado de método de tabulação.

O método envolve duas etapas:

  1. Encontrar todos os implicantes primários da função.
  2. Use esses implicantes primos em um gráfico de implicantes primos para encontrar os implicantes primos essenciais da função, bem como outros implicantes primos que são necessários para cobrir a função.

Complexidade

Embora mais prático do que o mapeamento de Karnaugh ao lidar com mais de quatro variáveis, o algoritmo Quine-McCluskey também tem uma gama limitada de uso, uma vez que o problema que ele resolve é NP-completo . O tempo de execução do algoritmo Quine – McCluskey cresce exponencialmente com o número de variáveis. Para uma função de n variáveis, o número de implicantes primos pode ser tão grande quanto 3 n / ln ( n ), por exemplo, para 32 variáveis, pode haver mais de 534 × 10 12 implicantes primos. Funções com um grande número de variáveis ​​devem ser minimizadas com métodos heurísticos potencialmente não ótimos , dos quais o minimizador lógico heurístico Espresso era o padrão de fato em 1995.

A segunda etapa do algoritmo consiste em resolver o problema da cobertura do conjunto ; Instâncias NP-hard desse problema podem ocorrer nesta etapa do algoritmo.

Exemplo

Entrada

Neste exemplo, a entrada é uma função booleana em quatro variáveis, que avalia para os valores e , avalia para um valor desconhecido em e , e para todos os outros lugares (onde esses inteiros são interpretados em sua forma binária para entrada para para sucinto de notação). As entradas que avaliam são chamadas de 'mintermos'. Codificamos todas essas informações por escrito

Esta expressão diz que a função de saída f será 1 para os mintermos e (denotada pelo termo 'm') e que não nos importamos com a saída de combinações e (denotada pelo termo 'd').

Etapa 1: encontrar implicantes primários

Primeiro, escrevemos a função como uma tabela (onde 'x' significa não importa):

UMA B C D f
m0 0 0 0 0 0
m1 0 0 0 1 0
m2 0 0 1 0 0
m3 0 0 1 1 0
m4 0 1 0 0 1
m5 0 1 0 1 0
m6 0 1 1 0 0
m7 0 1 1 1 0
m8 1 0 0 0 1
m9 1 0 0 1 x
m10 1 0 1 0 1
m11 1 0 1 1 1
m12 1 1 0 0 1
m13 1 1 0 1 0
m14 1 1 1 0 x
m15 1 1 1 1 1

Pode-se facilmente formar a soma canônica da expressão de produtos a partir desta tabela, simplesmente somando os mintermos (deixando de fora os termos irrelevantes ) em que a função é avaliada como um:

f A, B, C, D = A'BC'D '+ AB'C'D' + AB'CD '+ AB'CD + ABC'D' + ABCD.

o que não é mínimo. Portanto, para otimizar, todos os mintermos avaliados como um são colocados primeiro em uma tabela de mintermos. Termos irrelevantes também são adicionados a esta tabela (nomes entre parênteses), para que possam ser combinados com mintermos:

Número
de 1s		 Minterm
Representação Binária
1 m4 0100
m8 1000
2 (m9) 1001
m10 1010
m12 1100
3 m11 1011
(m14) 1110
4 m15 1111

Neste ponto, pode-se começar a combinar mintermos com outros mintermos. Se dois termos diferirem apenas por um único dígito, esse dígito pode ser substituído por um hífen indicando que o dígito não importa. Os termos que não podem mais ser combinados são marcados com um asterisco (*). Por exemplo, 1000e 1001pode ser combinado para fornecer 100-, indicando que ambos os mintermos implicam que o primeiro dígito é 1e os próximos dois são 0.

Número
de 1s		 Minterm 0-Cube Implicantes de tamanho 2
1 m4 0100 m (4,12) -100 *
m8 1000 m (8,9) 100-
- - m (8,10) 10-0
- - m (8,12) 1-00
2 m9 1001 m (9,11) 10-1
m10 1010 m (10,11) 101-
- - m (10,14) 1-10
m12 1100 m (12,14) 11-0
3 m11 1011 m (11,15) 1-11
m14 1110 m (14,15) 111-
4 m15 1111 -

Ao passar do tamanho 2 para o tamanho 4, trate -como um valor de terceiro bit. Por exemplo, -110e -100pode ser combinado para dar -1-0, como pode -110e -11-para dar -11-, mas -110e 011-não pode porque -110está implícito por 1110enquanto 011-não é. (Truque: Combine o -primeiro.)

Número
de 1s		 Minterm 0-Cube Implicantes de tamanho 2 Implicantes de tamanho 4
1 m4 0100 m (4,12) -100 * m (8,9,10,11) 10 - *
m8 1000 m (8,9) 100- m (8,10,12,14) 1--0 *
- - m (8,10) 10-0 -
- - m (8,12) 1-00 -
2 m9 1001 m (9,11) 10-1 m (10,11,14,15) 1-1- *
m10 1010 m (10,11) 101- -
- - m (10,14) 1-10 -
m12 1100 m (12,14) 11-0 -
3 m11 1011 m (11,15) 1-11 -
m14 1110 m (14,15) 111- -
4 m15 1111 - -

Nota: Neste exemplo, nenhum dos termos na tabela de implicantes tamanho 4 pode ser mais combinado. Em geral, este processo deve ser continuado (tamanhos 8, 16, etc.) até que nenhum outro termo possa ser combinado.

Etapa 2: gráfico implicante principal

Nenhum dos termos pode ser combinado mais do que isso, portanto, neste ponto, construímos uma tabela implicante primária essencial. Ao longo do lado estão os implicantes principais que acabaram de ser gerados, e ao longo do topo estão os mintermos especificados anteriormente. Os termos irrelevantes não são colocados no topo - eles são omitidos desta seção porque não são entradas necessárias.

4 8 10 11 12 15 ⇒ UMA B C D
m (4,12) * ✓ ✓ ⇒ - 1 0 0
m (8,9,10,11) ✓ ✓ ✓ ⇒ 1 0 - -
m (8,10,12,14) ✓ ✓ ✓ ⇒ 1 - - 0
m (10,11,14,15) * ✓ ✓ ✓ ⇒ 1 - 1 -

Para encontrar os implicantes primos essenciais, percorremos a linha superior. Temos que procurar colunas com apenas um "✓". Se uma coluna tiver apenas um "✓", isso significa que o mintermo só pode ser coberto por um implicante primo. Este implicante primário é essencial .

Por exemplo: na primeira coluna, com minterm 4, existe apenas um "✓". Isso significa que m (4,12) é essencial. Então colocamos uma estrela ao lado dela. Minterm 15 também tem apenas um "✓", então m (10,11,14,15) também é essencial. Agora todas as colunas com um "✓" estão cobertas.

O segundo implicante primo pode ser "coberto" pelo terceiro e pelo quarto, e o terceiro implicante primo pode ser "coberto" pelo segundo e pelo primeiro, e nenhum deles é, portanto, essencial. Se um implicante primo for essencial, então, como seria de se esperar, é necessário incluí-lo na equação booleana minimizada. Em alguns casos, os implicantes primários essenciais não cobrem todos os mintermos; nesse caso, procedimentos adicionais para redução do gráfico podem ser empregados. O "procedimento adicional" mais simples é a tentativa e erro, mas uma forma mais sistemática é o método de Petrick . No exemplo atual, os implicantes primos essenciais não lidam com todos os mintermos, então, neste caso, os implicantes essenciais podem ser combinados com um dos dois não essenciais para produzir uma equação:

f A, B, C, D = BC'D '+ AB' + AC

ou

f A, B, C, D = BC'D '+ AD' + AC

Ambas as equações finais são funcionalmente equivalentes à equação detalhada original:

f A, B, C, D = A'BC'D '+ AB'C'D' + AB'C'D + AB'CD '+ AB'CD + ABC'D' + ABCD '+ ABCD.

Veja também

Referências

Leitura adicional

links externos