Algoritmo de Quine-McCluskey

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
NoFonti.svg
Este artigo ou se(c)ção cita fontes fiáveis e independentes, mas que não cobrem todo o conteúdo (desde Maio de 2013). Por favor, adicione mais referências e insira-as corretamente no texto ou no rodapé. Trechos sem fontes poderão ser removidos.
Encontre fontes: Googlenotícias, livros, acadêmicoYahoo!Bing.

O Algoritmo de Quine–McCluskey (ou método dos implicantes primos) é um método utilizado para minimização de funções booleanas desenvolvido por W.V. Quine e Edward J. McCluskey em 1956. É funcionalmente idêntico ao mapa de Karnaugh, mas a forma tabular o faz mais eficiente para uso em algoritmos computacionais, além de fornecer um algoritmo determinístico para checar se a forma mais simplificada de uma função booleana foi alcançada.

O procedimento consiste em 3 etapas:

  1. Encontrar todos os implicantes primos da função;
  2. Usar esses implicantes primos num mapa de implicantes primos para encontrar os implicantes primos essenciais da função;
  3. Usar os implicante primos essenciais e se necessário alguns implicantes primos para encontrar a função minimizada.

Complexidade[editar | editar código-fonte]

Embora mais prático do que o mapa de Karnaugh ao lidar com mais de 4 variáveis, o algoritmo de Quine-McCluskey também possui limitações devido ao fato de o problema resolvido por ele ser NP-difícil: o tempo de execução do algoritmo de Quine-McCluskey cresce exponencialmente em relação ao número de variáveis. Pode-se mostrar que para uma função de n variáveis o limite superior no número de implicantes primos é 3n/n. Se n = 32 haverão cerca de 5.8 * 1013 implicantes primos. Funções com grande número de variáveis têm de ser simplificadas com heurísticas não-ótimas, das quais o ESPRESSO é considerado um padrão.[1]

Exemplo[editar | editar código-fonte]

Etapa 1: Implicantes primos[editar | editar código-fonte]

Minimizando uma função arbitrária:

f(A,B,C,D) =\sum m(4,8,10,11,12,15) + d(9,14).  \,

Esta expressão diz que a saída da função f será 1 para os mintermos 4,8,10,11,12 e 15 (denotados por 'm'), além de haver saídas irrelevantes, chamados don't care, definidas pelos minitermos 9 e 14.

A 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

Obtemos facilmente a soma de produtos a partir desta tabela, simplesmente somando os mintermos e desprezando os termos don't care:

f_{A,B,C,D} = A'BC'D' + AB'C'D' + AB'CD' + AB'CD + ABC'D' + ABCD.

A fórmula acima não está em sua forma mais simplificada. Para encontrar os minitermos primos, primeiro agrupa-se todos os minitermos em uma tabela. Separando em grupos baseado na quantidade de 1's presentes.

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

Começando pelo primeiro elemento do primeiro grupo da tabela, compare-o com todos os termos do grupo seguinte. Toda vez que que a combinação for possível a menos de um dígito deve-se anotar o código resultante em uma outra tabela, substituindo o dígito divergente pelo sinal -. Toda vez que um termo não possuir combinação deve-se marcá-lo pois este representa um implicante primo. Repete-se o procedimento para cada termo do primeiro grupo. Faça o mesmo para o segundo grupo, comparando seus termos com os termos do terceiro grupo.

Depois de realizar o procedimento em toda a tabela. Repita o procedimento para a tabela gerada. O algorítimo continua até que não haja mais combinações possíveis.

Número de 1's Coluna 1 Marca Coluna 2 Marca Coluna 3 Marca
0
1 0100 ok 100- ok 10-- *
1000 ok 10-0 ok 1--0 *
10-0 ok
-100 *
2 1001 ok 10-1 ok 1-1- *
1010 ok 101- ok
1100 ok 1-10 ok
11-0 ok
3 1011 ok 1-11 ok
1110 ok 111- ok
4 1111 ok

Neste exemplo, nenhum dos termos da coluna 3 pôde ser combinado. Se não fosse o caso, o algorítimo continuaria.

Etapa 2: Implicantes primos essenciais[editar | editar código-fonte]

Usando os implicantes primos essenciais constrói-se o mapa a seguir. A primeira linha do mapa representa os minitermos envolvidos. A primeira coluna mostra os implicantes primos e quais minitermos ele pode representar. Para definir quais os minitermos cada implicante primo pode representar usa-se usa-se o código substituindo o - por 0 e por 1 de forma a gerar todas as combinações possíveis.

Implicante primo minitermos representáveis 4 8 10 11 12 15 A B C D
-100 m(4,12)* X X - 1 0 0
10-- m(8,9,10,11) X X X 1 0 - -
1--0 m(8,10,12,14) X X X 1 - - 0
1-1- m(10,11,14,15)* X X X 1 - 1 -

Olhando as colunas da tabela observa-se que os implicantes primos são aqueles que possuem apenas um X e uma das colunas. Se um implicante primo é essencial, então será necessário incluí-lo na equação booleana simplificada. Em alguns casos, os implicantes primos essenciais não cobrem todos os minitermos. Nesses casos deve-se adicionar termos não essenciais de forma a cobrir todos os minitermos. Esse procedimento deve visar a menor quantidade possível de adições. Para proceder forma mais analítica pode ser usado o método de Petrick. Neste exemplo podemos combinar os implicantes essenciais com um dos não essenciais para cobrir todos os minitermos e obter uma das equações:

f_{A,B,C,D} = BC'D' + AC + AB'\
f_{A,B,C,D} = BC'D' + AC + AD' \

Ambas as equações são mínimas e equivalentes à equação inicial:

f_{A,B,C,D} = A'BC'D' + AB'C'D' + AB'C'D + AB'CD' + AB'CD + ABC'D' + A'B'CD' + ABCD. \

Ver também[editar | editar código-fonte]

Referências

  1. V.P. Nelson e.a., Digital Circuit Analysis and Design, Prentice Hall, 1995, pag. 234