Método Tabular Quine-McCluskey
No capítulo anterior, discutimos o método K-map, que é um método conveniente para minimizar funções booleanas até 5 variáveis. Porém, é difícil simplificar as funções booleanas com mais de 5 variáveis usando este método.
O método tabular de Quine-McClukey é um método tabular baseado no conceito de implicantes primários. Nós sabemos issoprime implicant é um termo de produto (ou soma), que não pode ser reduzido ainda mais combinando com qualquer outro produto (ou soma) de termos da função booleana fornecida.
Este método tabular é útil para obter os implicantes primários usando repetidamente a seguinte identidade booleana.
xy + xy '= x (y + y') = x.1 = x
Procedimento do Método Tabular Quine-McCluskey
Siga estas etapas para simplificar as funções booleanas usando o método tabular Quine-McClukey.
Step 1 - Organize os termos mínimos fornecidos em um ascending ordere faça os grupos com base no número de unidades presentes em suas representações binárias. Então, haveráat most ‘n+1’ groups se houver 'n' variáveis booleanas em uma função booleana ou 'n' bits no equivalente binário de termos mínimos.
Step 2 - Compare os termos mínimos presentes em successive groups. Se houver uma mudança na posição de apenas um bit, considere o par desses dois termos mínimos. Coloque este símbolo '_' na posição do bit diferente e mantenha os bits restantes como estão.
Step 3 - Repita a etapa 2 com os termos recém-formados até obtermos todos prime implicants.
Step 4 - Formule o prime implicant table. Ele consiste em um conjunto de linhas e colunas. Os implicantes primários podem ser colocados em linhas e os termos mínimos podem ser colocados em colunas. Coloque '1' nas células correspondentes aos termos mínimos que são cobertos em cada implicante primo.
Step 5- Encontre os implicantes primários essenciais observando cada coluna. Se o termo mínimo é coberto apenas por um implicante primo, então ele éessential prime implicant. Esses implicantes primos essenciais farão parte da função booleana simplificada.
Step 6- Reduza a tabela do implicante primo removendo a linha de cada implicante primo essencial e as colunas correspondentes aos termos min que são cobertos naquele implicante primo essencial. Repita a etapa 5 para a tabela implicante principal reduzida. Pare este processo quando todos os termos mínimos de determinada função booleana terminarem.
Exemplo
Deixe-nos simplify a seguinte função booleana, $ f \ left (W, X, Y, Z \ right) = \ sum m \ left (2,6,8,9,10,11,14,15 \ right) $ usando Quine-McClukey método tabular.
A função booleana fornecida está em sum of min termsFormato. Ele tem 4 variáveis W, X, Y e Z. Os termos mínimos fornecidos são 2, 6, 8, 9, 10, 11, 14 e 15. A ordem crescente desses termos mínimos com base no número de uns presentes em seus equivalente binário é 2, 8, 6, 9, 10, 11, 14 e 15. A seguinte tabela mostra estesmin terms and their equivalent binary representações.
| Nome do grupo | Termos mínimos | W | X | Y | Z |
|---|---|---|---|---|---|
| GA1 | 2 | 0 | 0 | 1 | 0 |
| 8 | 1 | 0 | 0 | 0 | |
| GA2 | 6 | 0 | 1 | 1 | 0 |
| 9 | 1 | 0 | 0 | 1 | |
| 10 | 1 | 0 | 1 | 0 | |
| 11 | 1 | 0 | 1 | 1 | |
| 14 | 1 | 1 | 1 | 0 | |
| GA4 | 15 | 1 | 1 | 1 | 1 |
Os termos mínimos fornecidos são organizados em 4 grupos com base no número de uns presentes em seus equivalentes binários. A tabela a seguir mostra os possíveismerging of min terms de grupos adjacentes.
| Nome do grupo | Termos mínimos | W | X | Y | Z |
|---|---|---|---|---|---|
| GB1 | 2,6 | 0 | - | 1 | 0 |
| 2,10 | - | 0 | 1 | 0 | |
| 8,9 | 1 | 0 | 0 | - | |
| 8,10 | 1 | 0 | - | 0 | |
| GB2 | 6,14 | - | 1 | 1 | 0 |
| 9,11 | 1 | 0 | - | 1 | |
| 10,11 | 1 | 0 | 1 | - | |
| 10,14 | 1 | - | 1 | 0 | |
| 11,15 | 1 | - | 1 | 1 | |
| 14,15 | 1 | 1 | 1 | - |
Os termos mínimos, que diferem em apenas uma posição de um bit dos grupos adjacentes, são mesclados. Esse bit diferente é representado com este símbolo, '-'. Nesse caso, existem três grupos e cada grupo contém combinações de dois termos mínimos. A tabela a seguir mostra os possíveismerging of min term pairs de grupos adjacentes.
| Nome do grupo | Termos mínimos | W | X | Y | Z |
|---|---|---|---|---|---|
| GB1 | 2,6,10,14 | - | - | 1 | 0 |
| 2,10,6,14 | - | - | 1 | 0 | |
| 8,9,10,11 | 1 | 0 | - | - | |
| 8,10,9,11 | 1 | 0 | - | - | |
| GB2 | 10,11,14,15 | 1 | - | 1 | - |
| 10,14,11,15 | 1 | - | 1 | - |
Os grupos sucessivos de pares de termos mínimos, que diferem na posição de apenas um bit, são mesclados. Esse bit diferente é representado com este símbolo, '-'. Nesse caso, existem dois grupos e cada grupo contém combinações de quatro termos mínimos. Aqui, essas combinações de termos de 4 minutos estão disponíveis em duas linhas. Portanto, podemos remover as linhas repetidas. A tabela reduzida após a remoção das linhas redundantes é mostrada abaixo.
| Nome do grupo | Termos mínimos | W | X | Y | Z |
|---|---|---|---|---|---|
| GC1 | 2,6,10,14 | - | - | 1 | 0 |
| 8,9,10,11 | 1 | 0 | - | - | |
| GC2 | 10,11,14,15 | 1 | - | 1 | - |
Uma fusão adicional das combinações de termos mínimos de grupos adjacentes não é possível, uma vez que eles diferem em mais de uma posição de bit. Existem três linhas na tabela acima. Portanto, cada linha dará um implicante primo. Portanto, oprime implicants são YZ ', WX' e WY.
o prime implicant table é mostrado abaixo.
| Termos mínimos / Implicantes principais | 2 | 6 | 8 | 9 | 10 | 11 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|
| YZ’ | 1 | 1 | 1 | 1 | ||||
| WX’ | 1 | 1 | 1 | 1 | ||||
| WY | 1 | 1 | 1 | 1 |
Os implicantes primários são colocados em linhas e os termos mínimos são colocados em colunas. 1s são colocados nas células comuns das linhas implicantes principais e nas colunas de termo mínimo correspondentes.
Os termos mínimos 2 e 6 são cobertos apenas por um implicante principal YZ’. Então, é umessential prime implicant. Isso fará parte da função booleana simplificada. Agora, remova esta linha principal implicante e as colunas de termo mínimo correspondentes. A tabela de implicantes primários reduzida é mostrada abaixo.
| Termos mínimos / Implicantes principais | 8 | 9 | 11 | 15 |
|---|---|---|---|---|
| WX’ | 1 | 1 | 1 | |
| WY | 1 | 1 |
Os termos mínimos 8 e 9 são cobertos apenas por um implicante principal WX’. Então, é umessential prime implicant. Isso fará parte da função booleana simplificada. Agora, remova esta linha principal implicante e as colunas de termo mínimo correspondentes. A tabela de implicantes primários reduzida é mostrada abaixo.
| Termos mínimos / Implicantes principais | 15 |
|---|---|
| WY | 1 |
O termo mínimo 15 é coberto apenas por um implicante principal WY. Então, é umessential prime implicant. Isso fará parte da função booleana simplificada.
Neste exemplo de problema, obtivemos três implicantes primos e todos os três são essenciais. Portanto, osimplified Boolean function é
f(W,X,Y,Z) = YZ’ + WX’ + WY.