Mapas de Karnaugh e condições de don’t-care

Da tabela-verdade ao custo de implementação

A tabela-verdade^{iTabela-verdade Tabela que enumera todas as combinações possíveis de entradas e a saída de cada uma. A evolução temporal é verificada separadamente nas formas de onda. Saiba mais} define a função; a minimização decide com qual expressão implementá-la. Com três entradas, numeraremos os mintermos pelo binário ABC, com A como bit mais significativo.

Por exemplo, o mintermo 4 é ABC=100. As linhas não enumeradas, 0, 2 e 6, produzem 0. Em vez de cinco produtos, podem-se agrupar termos que diferem em apenas um bit.

Karnaugh é uma tabela com outra ordem

Coloque BC na ordem 00, 01, 11, 10. É código Gray: entre colunas adjacentes muda apenas um bit. A primeira e a última também são adjacentes.

Os grupos são retângulos com $1,2,4,8,\ldots$ células. Incluir um 0 altera a função; incluir o mesmo 1 em vários grupos é permitido.

1. Agrupe as quatro células das duas colunas com C=1. A e B variam, mas a saída continua em 1: resta C.
2. Agrupe BC=00 e 01 na linha A=1. Apenas C muda: resta $A\overline B$.
3. Uma OR dos dois grupos cobre todos os uns e evita todos os zeros.

Compare a definição inicial e a expressão simplificada para as oito entradas. Verifique separadamente que a expressão é mais curta e que a função foi preservada.

O fluxo abaixo converte grupos em expressões: no grupo C, eliminam-se A e B, que variam; no grupo de duas células, elimina-se C.

Don’t-care concede liberdade de otimização sob uma hipótese

Suponha que o contrato do sistema garanta que ABC=000 nunca ocorre. Marcar essa célula como X permite usá-la como 0 ou 1. Agrupando as quatro células com B=0, obtém-se:

A nova expressão produz 1 com ABC=000 e difere da tabela completa original. Para afirmar equivalência, deve-se acrescentar que a entrada não é 000. Se 000 ocorrer durante inicialização ou recuperação de erros, a otimização pode violar os requisitos do sistema.

Minimizar a expressão não equivale a minimizar o chip

Menos literais não garante área, atraso e potência ótimos em uma biblioteca concreta. Influem carga, fan-out, portas compostas disponíveis, fiação e pulsos espúrios. Aqui estabelecemos função e hipóteses; o custo físico é avaliado com síntese e temporização.

Leitura adicional: MIT OpenCourseWare — Combinational Logic

Prática · Sobreposição e condições de don’t-care

1. Selecione o grupo C. A e B variam dentro de suas quatro células; resta apenas C.
2. Selecione A·¬B. Cobre m4 e m5, e m5 também pertence a C. A sobreposição é permitida, mas incluir zeros não é.
3. Pressione m0 duas vezes: 0 → 1 → X. Com X, a especificação fica incompleta e inclui d(0). O grupo B=0 se amplia e resulta $C+\overline B$.
4. Pressione m0 novamente para voltar a 0. Ao recuperar o requisito original, o grupo ampliado deve desaparecer.

Selecionar um grupo não altera valores. A expressão completa que cobre todos os uns é mantida e somente o termo examinado é destacado. «Mínimo» prioriza produtos e depois literais; se houver várias soluções, uma delas é mostrada.