Aprenda › Tema 4

Mapas de Karnaugh de 2, 3 e 4 variáveis com condições X

Leitura de 7 min · Equipe bitGateLab

Simplificar com a álgebra de Boole funciona, mas depende de você "enxergar" qual lei aplicar. O mapa de Karnaugh transforma essa busca em um exercício visual: ele organiza a tabela-verdade em uma grade em que as células vizinhas diferem em uma única variável, e simplificar passa a ser circular grupos de uns. Aqui você vai aprender a construir mapas de 2, 3 e 4 variáveis, a agrupar corretamente (incluindo as bordas que "dão a volta") e a aproveitar as condições irrelevantes ("don't care").

A ideia: células vizinhas, uma variável de diferença

A lei da adjacência diz que AB + AB = A: dois termos que diferem em uma única variável se fundem e essa variável desaparece. O mapa de Karnaugh organiza os mintermos de modo que qualquer par de células que compartilham um lado atenda a essa condição. Para conseguir isso, os cabeçalhos de linhas e colunas não seguem a ordem binária 00, 01, 10, 11, e sim o código Gray: 00, 01, 11, 10. Entre dois valores consecutivos muda apenas um bit, e o mesmo acontece entre o último e o primeiro (10 e 00). Por isso o mapa se comporta como se suas bordas opostas estivessem coladas.

Mapas de 2 e 3 variáveis

O mapa de duas variáveis tem 4 células: A nas linhas e B nas colunas. O de três variáveis tem 8 células: A nas linhas e BC nas colunas, em ordem Gray. O número dentro de cada célula indica o mintermo correspondente:

Repare que m3 e m2 ficam nessa ordem: é o efeito do código Gray, e a causa de muitos erros ao preencher o mapa à mão.

Regras de agrupamento

• Os grupos só podem conter uns (ou X, como você verá mais adiante), nunca zeros.
• O tamanho de cada grupo deve ser uma potência de 2: 1, 2, 4, 8 ou 16 células.
• Os grupos são retângulos de células adjacentes, incluindo a adjacência através das bordas. As diagonais não contam.
• Faça cada grupo o maior possível: um grupo de 2^k células elimina k variáveis.
• Use a menor quantidade de grupos que cubra todos os uns. Os grupos podem se sobrepor.

Para ler um grupo, examine cada variável: se ela mantém o mesmo valor em todas as células do grupo, aparece no termo (sem barra se vale 1, com barra se vale 0); se muda, é eliminada.

Mapa de 4 variáveis e adjacência nas bordas

Com quatro variáveis o mapa tem 16 células: AB nas linhas e CD nas colunas, ambos em ordem Gray.

A coluna da esquerda é vizinha da coluna da direita, e a linha de cima é vizinha da linha de baixo. Em consequência, os quatro cantos (m0, m2, m8, m10) formam um grupo válido de 4 células: em todas elas B = 0 e D = 0, de modo que são lidas como BD.

Condições irrelevantes (X)

Às vezes certas combinações de entrada nunca ocorrem, ou a saída delas não tem consequências. Por exemplo, em um dígito BCD os códigos 1010 a 1111 não existem. Nessas linhas escreve-se um X (também chamado de don't care) e anota-se à parte como d(...). Ao agrupar, cada X pode ser tomado como 1 se ajudar a formar um grupo maior, ou ignorado caso contrário. Nunca é preciso cobrir um X.

Erros comuns

• Ordenar os cabeçalhos em binário (00, 01, 10, 11) em vez de Gray. O mapa deixa de ter vizinhos de uma única variável e os grupos saem errados.
• Formar grupos de 3 ou 6 células. Só valem potências de 2.
• Esquecer a adjacência das bordas e dos quatro cantos, o que deixa grupos menores do que o necessário.
• Acrescentar um grupo cujas células já estão todas cobertas por outros. Ele sobra e adiciona portas.
• Obrigar-se a cobrir os X. Eles só são usados quando aumentam um grupo.

Experimente no simulador

O módulo de mapas de Karnaugh organiza a função em ordem Gray, marca os grupos e escreve a expressão mínima, de modo que você pode comparar o seu agrupamento com o que a ferramenta propõe.

1. Crie uma função de quatro variáveis e insira os uns do exemplo 2.
2. Agrupe primeiro no papel e escreva o seu resultado.
3. Observe os grupos que o mapa marca e a expressão resultante; se ela for diferente da sua, veja qual grupo não era máximo.
4. Insira o exemplo 3 marcando como X as células 0, 2 e 5, e observe como a simplificação muda ao retirar esses X.
5. Converta o resultado em circuito e mude as entradas para confirmar que ele coincide com a tabela.

Exercícios

1. Simplifique F(A, B, C) = Σm(0, 2, 4, 6).
   Resposta

   As colunas BC = 00 e BC = 10 são vizinhas pela borda e estão cheias. Nas quatro células C = 0: F = C.

2. Simplifique F(A, B, C, D) = Σm(0, 2, 5, 7, 8, 10, 13, 15).
   Resposta

   Cantos: BD. Bloco central m5, m7, m13, m15: BD. F = BD + BD, que é a XNOR de B e D.

3. Simplifique F(A, B, C, D) = Σm(4, 5, 6, 7, 12, 13, 14, 15).
   Resposta

   As linhas AB = 01 e AB = 11 formam um grupo de 8; somente B se mantém em 1. F = B.

4. Um dígito BCD (A é o bit mais significativo) deve acender uma saída quando vale 5 ou mais. Simplifique F = Σm(5, 6, 7, 8, 9) + d(10, 11, 12, 13, 14, 15).
   Resposta

   Com os X, as linhas AB = 11 e AB = 10 formam um grupo de 8: A. O bloco m5, m7, m13, m15 dá BD e o bloco m6, m7, m14, m15 dá BC. F = A + BD + BC = A + B(C + D).

Quando há mais de quatro ou cinco variáveis, o mapa fica difícil de ler; para esses casos existe um procedimento tabular, o método de Quine-McCluskey.