Mapas de Karnaugh

As linhas ABC=001 e 011 diferem só em B. Os seus mintermos somam $\overline A\overline BC+\overline ABC=\overline AC$: B desaparece porque pode valer 0 ou 1. Um mapa de Karnaugh coloca estas combinações em células vizinhas para tornar visíveis os grupos que eliminam variáveis.

Ordem e adjacência

As etiquetas usam código Gray: 00, 01, 11, 10. Passar de uma coluna à seguinte muda um só bit, e a primeira e a última também são adjacentes; nos mapas de quatro variáveis, o mesmo acontece com as linhas, e os quatro cantos formam um grupo possível.

Não há adjacência diagonal. Os grupos são retângulos com $1,2,4,8,\ldots$ células. Um retângulo pode atravessar uma fronteira do mapa. Um grupo de três células não elimina uma quantidade inteira de variáveis e não é válido.

Exemplo de soma de produtos

Considera $F(A,B,C)=\Sigma m(1,3,5,6,7)$, representada na tabela seguinte em código Gray:

$A\backslash BC$	00	01	11	10
0	0	1	1	0
1	0	1	1	1

Observa as variáveis que ficam constantes dentro de cada contorno. Uma variável desaparece porque aparece negada numa metade do grupo e direta na outra: $AB+A\overline B=A(B+\overline B)=A\cdot 1=A$, por distributividade e complemento. É a identidade aplicada às células vizinhas, não um atalho gráfico; no contínuo, $C=1$ enquanto $A$ e $B$ variam, por isso obtemos $C$, e no tracejado, $A=B=1$ enquanto $C$ varia, por isso obtemos $AB$.

Falta a célula 6 depois de formar o grupo de quatro, por isso agrupa-a com a célula 7 na coluna 11, mesmo que esta já pertença ao grupo $C$.

Portanto $F=C+AB$. A célula 7 pertence aos dois grupos, o que é permitido. Sem essa sobreposição precisaríamos de um termo maior. Cada 1 tem de ficar coberto; cobrir uma célula 0 tornaria a expressão errada.

Implicantes essenciais

Um grupo de 1 que não pode ser alargado sem incluir um 0 é um implicante primo. Maximal não significa maior do mapa: o grupo AB tem duas células e também é primo. Um primo é essencial quando cobre algum 1 que nenhum outro primo cobre.

No exemplo, a célula 1 só pode entrar no grande grupo $C$, e a célula 6 só pode entrar no grupo $AB$. Ambos são necessários. Noutros mapas, vários grupos não essenciais podem completar a cobertura. Escolhe uma combinação que cubra os 1 restantes, preferindo menos termos e menos literais quando esse é o custo pedido.

Um grupo pequeno válido pode ser redundante. Acrescentá-lo não muda a função, mas aumenta o circuito. Não é obrigatório desenhar todos os grupos possíveis.

Produto de somas

Para obter POS, agrupa os zeros. As células 0 e 4, na coluna 00, têm $B=C=0$, por isso o fator é $(B+C)$: só fica 0 quando ambos são 0. As células 0 e 2, na linha $A=0$ e nas colunas 00,10 que se tocam pela fronteira, dão $(A+C)$.

Assim, com

$$F=(B+C)(A+C)=C+AB.$$

Nos fatores de zeros, uma variável constante em 0 fica direta e uma constante em 1 fica negada. É a regra inversa da usada nos produtos dos grupos de 1. Não negues a função inteira ao passar de SOP para POS. Confirma cada fator substituindo um zero coberto: esse zero tem de anular o fator e, por isso, toda a expressão.

Quatro variáveis

Para $F(A,B,C,D)=\Sigma m(0,2,8,10)$, usamos $AB$ nas linhas e $CD$ nas colunas, ambas em código Gray, com

$AB\backslash CD$	00	01	11	10
00	1	0	0	1
01	0	0	0	0
11	0	0	0	0
10	1	0	0	1

Os quatro cantos pertencem ao mesmo grupo, atravessando as duas fronteiras. $A$ e $C$ mudam, mas $B=D=0$ em todos os cantos. O produto é $\overline B\overline D$. Escolher a ordem binária 00,01,10,11 esconderia esta adjacência e poderia levar a grupos errados.

Condições indiferentes

Uma célula $X$ significa que a especificação permite qualquer saída nessa combinação. Podes tratá-la como 1 para alargar um grupo de 1, ou como 0 para alargar um grupo de 0, sem obrigação de usar todos os $X$.

Por exemplo, $G=\Sigma m(1,3,7)$ com indiferentes 5 e 6 permite agrupar 1,3,5,7 e obter $G=C$. No índice 5, o circuito dará 1, mas isso é permitido. Se 5 fosse um zero obrigatório, o grupo seria inválido.

Um estado não usado só pode ser indiferente se o comportamento nesse estado for realmente livre. Se o circuito tiver de recuperar de um estado inválido, essa recuperação impõe valores nas equações.

Função correta e tempo

Para além da tabela: hazards

Simplificar uma função não elimina os atrasos das portas. Num circuito $AB+\overline AC$ com $B=C=1$, mudar $A$ pode causar uma breve saída 0 se um caminho se desligar antes de o outro ligar. O termo de consenso $BC$ pode cobrir a transição e evitar este hazard estático no modelo de atrasos considerado.

A tabela de verdade descreve estados estáveis. Uma pergunta sobre impulsos transitórios exige seguir os caminhos e os atrasos, além de simplificar a expressão.