Aula 02 - Simplificação de Circuitos Lógicos e Mapas de Karnaugh

---

1. Introdução à Minimização Lógica

O projeto de circuitos digitais combinacionais busca primordialmente a obtenção de redes lógicas ótimas que satisfaçam as especificações funcionais com:

1. Menor Custo de Silício e Contagem de Componentes: Redução drástica da quantidade de circuitos integrados e transistores;
2. Menor Consumo de Energia: Minimização das capacitâncias parasitas internas comutadas a cada ciclo;
3. Menor Atraso de Propagação ($t_{pd}$): Redução do número de níveis lógicos entre as entradas e as saídas, maximizando a frequência de operação do sistema.

Enquanto a simplificação por manipulação algébrica direta fundamentada nos postulados de Huntington exige elevada intuição matemática e não garante que a forma irredutível tenha sido alcançada, o Mapa de Karnaugh (K-Map) oferece um método gráfico sistemático, determinístico e visual para a identificação da forma mínima canônica em Soma de Produtos (SOP) ou Produto de Somas (POS).

🕹️ Simulador Dinâmico Interativo: Mapa de Karnaugh 4V, Detecção de Hazards e Síntese VHDL Concorrente

Experimente clicar em qualquer célula da grade $4\times 4$ (alternando entre 0, 1 e Don’t Care X) ou carregar circuitos clássicos (Detector de Números Primos, Decodificador BCD 7-Segmentos, Paridade XOR e Circuito com Hazard Estático-1) para visualizar o envelopamento automático dos Implicantes Primos Essenciais no toroide, a equação mínima SOP, a rede de portas lógicas AND-OR, o alerta de Hazard Estático-1 com inclusão do Termo de Consenso e o código VHDL sintetizável gerado em tempo real: 👉 ▶️ Clique para Abrir o Simulador em Tela Cheia no Navegador (Arquivo no cofre: [[simulador_mapa_karnaugh_sintese_vhdl_fsm.html]])

---

📌 Sumário da Aula

1. 2. Fundamentos Estruturais do Mapa de Karnaugh
   • 2.1 Indexação por Código Gray
   • 2.2 Estrutura para 2, 3 e 4 Variáveis
2. 3. Topologia e Envelopamento Toroidal
3. 4. Teoria e Regras Formais de Agrupamento
4. 5. Classificação Rigorosa dos Implicantes
5. 6. Condições Irrelevantes (*Don’t Care* — ‘d’ ou ‘X’)
   • Exemplo Clássico: Decodificador BCD 8421
   • Estratégia de Minimização com *Don’t Care*:
6. 7. Riscos Lógicos (*Hazards* / *Glitches*) e Termos de Consenso
   • 7.1 Risco Estático-1 (*Static-1 Hazard*)
   • 7.2 Eliminação de Hazards via Termo de Consenso
7. 8. Questões Resolvidas das Materiais Teóricos de Referência

---

2. Fundamentos Estruturais do Mapa de Karnaugh

O Mapa de Karnaugh é uma representação bidimensional da tabela-verdade em que as células são organizadas de modo que células geometricamente adjacentes diferem pelo valor de exatamente um único literal booleano.

2.1 Indexação por Código Gray

A garantia de que células vizinhas diferem por apenas 1 bit baseia-se na sequência do Código Gray:

$\text{Sequeˆncia de Gray para 2 bits:}00⟶01⟶11⟶10$

Note que, diferentemente da contagem binária natural ($00\to 01\to 10\to 11$), a transição de $01$ para $11$ altera apenas o bit mais significativo, e a transição de $11$ para $10$ altera apenas o bit menos significativo. Adicionalmente, a sequência é cíclica: o último elemento ($10$) difere do primeiro ($00$) por apenas 1 bit!

2.2 Estrutura para 2, 3 e 4 Variáveis

A. Mapa de 2 Variáveis ($2^2=4$ células)

Variáveis $A$ (linhas) e $B$ (colunas):

$A\backslash B$	$0$	$1$
0	$m_0(\overline{A}\overline{B})$	$m_1(\overline{A}B)$
1	$m_2(A\overline{B})$	$m_3(AB)$

B. Mapa de 3 Variáveis ($2^3=8$ células)

Variável $A$ nas linhas e $BC$ nas colunas:

$A\backslash BC$	$00$	$01$	$11$	$10$
0	$m_0(\overline{A}\overline{B}\overline{C})$	$m_1(\overline{A}\overline{B}C)$	$m_3(\overline{A}BC)$	$m_2(\overline{A}B\overline{C})$
1	$m_4(A\overline{B}\overline{C})$	$m_5(A\overline{B}C)$	$m_7(ABC)$	$m_6(AB\overline{C})$

Atenção: Observe a inversão de posição entre as colunas 3 e 4 ($11$ antes de $10$), necessária para manter a adjacência de Gray.

C. Mapa de 4 Variáveis ($2^4=16$ células)

Variáveis $AB$ nas linhas e $CD$ nas colunas:

$AB\backslash CD$	$00$	$01$	$11$	$10$
00	$m_0$	$m_1$	$m_3$	$m_2$
01	$m_4$	$m_5$	$m_7$	$m_6$
11	$m_{12}$	$m_{13}$	$m_{15}$	$m_{14}$
10	$m_8$	$m_9$	$m_{11}$	$m_{10}$

---

3. Topologia e Envelopamento Toroidal

O mapa de Karnaugh não deve ser interpretado como um plano rígido e isolado, mas sim como a projeção plana da superfície de um toro geométrico (uma superfície toroidal em formato de rosquinha):

1. Adjacência Horizontal: A coluna da extrema esquerda ($00$) é adjacente à coluna da extrema direita ($10$);
2. Adjacência Vertical: A linha do topo ($00$) é adjacente à linha da base ($10$);
3. Agrupamento dos Quatro Cantos: As quatro células dos vértices extremos formam um grupo adjacente válido de 4 mintermos: $\{m_0,m_2,m_8,m_{10}\}⟹\text{Termo Simplificado: }\overline{B}\cdot \overline{D}$

---

4. Teoria e Regras Formais de Agrupamento

Para que a simplificação resulte na expressão mínima estrita, as seguintes regras axiomáticas devem ser observadas:

1. Potências de 2: Todo agrupamento (enlace) deve conter exatamente $2^k$ células ($1,2,4,8,16,\dots$);
2. Formato Retangular: Os grupos devem ter conformação retangular ou quadrada no toro (dimensões $1\times 1,1\times 2,2\times 1,2\times 2,1\times 4,4\times 1,2\times 4,4\times 4$);
3. Eliminação de Literais: Um grupo de $2^k$ células em uma função de $n$ variáveis elimina exatamente $k$ variáveis, resultando em um produto de $n-k$ literais:
   • Grupo de 1 célula: termo com $n$ literais (nenhuma simplificação);
   • Grupo de 2 células: termo com $n-1$ literais (elimina 1 variável);
   • Grupo de 4 células: termo com $n-2$ literais (elimina 2 variáveis);
   • Grupo de 8 células: termo com $n-3$ literais (elimina 3 variáveis);
   • Grupo de 16 células: termo constante $1$ (função identicamente verdadeira).
4. Maximização dos Laços: Sempre priorize o maior tamanho de laço possível para maximizar a eliminação de literais;
5. Minimização da Cobertura: Utilize o menor número total de agrupamentos suficiente para cobrir todos os ‘1’s do mapa.

---

5. Classificação Rigorosa dos Implicantes

Para sistematizar a seleção dos agrupamentos, a literatura formal de comutação define:

1. Implicante: Qualquer produto de literais que, quando avaliado em $1$, força a saída da função para $1$. Graficamente, é qualquer conjunto de células de valor $1$ em formato válido de potência de 2.
2. Implicante Primo (PI - Prime Implicant): É um implicante obtido combinando o número máximo possível de células adjacentes. Um laço é primo se não puder ser englobado por nenhum outro laço de potência de 2 maior.
3. Implicante Primo Essencial (EPI - Essential Prime Implicant): É um implicante primo que cobre ao menos uma célula de valor $1$ que não é coberta por nenhum outro implicante primo.
   • Regra Cardeal: Todos os Implicantes Primos Essenciais devem obrigatoriamente figurar na expressão simplificada final!

---

6. Condições Irrelevantes (Don’t Care — ‘d’ ou ‘X’)

Em múltiplos projetos de engenharia, determinadas combinações das variáveis de entrada são fisicamente impossíveis de ocorrer ou têm saída irrelevante para a operação do sistema.

Exemplo Clássico: Decodificador BCD 8421

No código BCD (Decimal Codificado em Binário), 4 bits representam dígitos decimais de 0 a 9 ($0000_2$ a $1001_2$). As combinações de 10 a 15 ($1010_2$ a $1111_2$) são combinações proibidas.

Estratégia de Minimização com Don’t Care:

• Atribui-se valor lógico $1$ ao termo Don’t Care se e somente se ele permitir formar um grupo maior (ex.: transformar um par em quadra, ou uma quadra em octeto);
• Caso o termo Don’t Care não auxilie na expansão de nenhum laço existente, ele é assumido como $0$, evitando a criação desnecessária de novos agrupamentos.

---

7. Riscos Lógicos (Hazards / Glitches) e Termos de Consenso

Um dos problemas mais sutis e perigosos na síntese de circuitos lógicos assíncronos é o surgimento de pulsos transitórios espúrios (glitches), causados pelas assimetrias no tempo de propagação ($t_{pd}$) das portas lógicas físicas.

7.1 Risco Estático-1 (Static-1 Hazard)

Considere a função simplificada mínima:

$Y=A\cdot \overline{C}+B\cdot C$

Se as entradas forem polarizadas em $A=1$ e $B=1$, a expressão teórica reduz-se a:

$Y=1\cdot \overline{C}+1\cdot C=\overline{C}+C=1$

Entretanto, se a variável $C$ transitar de $1\to 0$:

• O inversor real introduz um atraso de propagação não-nulo $\Delta t$ para calcular $\overline{C}$;
• Durante o intervalo $\Delta t$, tanto $C=0$ quanto $\overline{C}=0$ momentaneamente;
• Consequentemente, as saídas de ambos os termos AND caem a $0$, gerando um pulso falso de nível baixo ($1\to 0\to 1$) na saída da porta OR!

7.2 Eliminação de Hazards via Termo de Consenso

No mapa de Karnaugh, o risco estático-1 manifesta-se sempre que a transição de um estado para outro adjacente exige a mudança de um agrupamento para outro grupo vizinho sem sobreposição. A solução consiste em incluir deliberadamente um implicante primo redundante (Termo de Consenso) que una os dois grupos:

$Y_{\text{robusto}}=A\cdot \overline{C}+B\cdot C+\underset{\text{Termo de Consenso}}{\underbrace{A\cdot B}}$

Quando $A=1$ e $B=1$, o termo $A\cdot B$ mantém a saída fixada em $1$ de forma incondicional, suprimindo o glitch com 100% de confiabilidade!

---

8. Questões Resolvidas das Materiais Teóricos de Referência

Questão 1 (Apostila 01 - Módulo 4)

Enunciado: Utilize a abordagem por mapa de Karnaugh para simplificar a seguinte expressão booleana de 4 variáveis: $S(A,B,C,D)=\sum m(0,2,4,5,6,7,8,10,13,15)$

A) $S=\overline{B}\overline{D}+A\overline{B}C$
B) $S=\overline{B}\overline{D}+\overline{A}B+BD$
C) $S=\overline{A}BD+C\overline{D}$
D) $S=AB+\overline{C}D$

Resolução Passo a Passo:

1. Mapeiam-se os 10 mintermos no Mapa de Karnaugh $4\times 4$:

$AB\backslash CD$	$00$	$01$	$11$	$10$
00	1 ($m_0$)	0 ($m_1$)	0 ($m_3$)	1 ($m_2$)
01	1 ($m_4$)	1 ($m_5$)	1 ($m_7$)	1 ($m_6$)
11	0 ($m_{12}$)	1 ($m_{13}$)	1 ($m_{15}$)	0 ($m_{14}$)
10	1 ($m_8$)	0 ($m_9$)	0 ($m_{11}$)	1 ($m_{10}$)

2. Identificação dos agrupamentos ótimos:
   • Grupo 1 (Envelopamento dos 4 Cantos): Células $\{m_0,m_2,m_8,m_{10}\}$.
     • Linhas $00$ e $10⟹B$ varia ($0$ e $1$), fixando $\overline{B}$;
     • Colunas $00$ e $10⟹C$ varia, fixando $\overline{D}$;
     • Termo 1: $\overline{B}\cdot \overline{D}$.
   • Grupo 2 (Linha Completa 01): Células $\{m_4,m_5,m_6,m_7\}$.
     • Cobre todos os 4 mintermos da linha $AB=01$;
     • Elimina integralmente as variáveis $C$ e $D$;
     • Termo 2: $\overline{A}\cdot B$.
   • Grupo 3 (Quadra Central): Células $\{m_5,m_7,m_{13},m_{15}\}$.
     • Linhas $01$ e $11⟹A$ varia, fixando $B$;
     • Colunas $01$ e $11⟹C$ varia, fixando $D$;
     • Termo 3: $B\cdot D$.
3. Todos os 10 mintermos foram cobertos pelos 3 implicantes primos essenciais: $S=\overline{B}\overline{D}+\overline{A}B+BD$

Resposta Correta: B

---

Questão 2 (Apostila 01 - Módulo 4)

Enunciado: Calcule a expressão simplificada na forma de soma de produtos do mapa de Karnaugh abaixo de 3 variáveis ($A\backslash BC$):

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

A) $S=\overline{C}+AB$
B) $S=\overline{C}+ABC$
C) $S=A\overline{B}+C$
D) $S=\overline{B}+\overline{A}C$

Resolução Passo a Passo:

1. Identificam-se as células com valor $1$:
   • Linha $0$: mintermos $m_0$ ($000$) e $m_2$ ($010$);
   • Linha $1$: mintermos $m_4$ ($100$), $m_7$ ($111$) e $m_6$ ($110$).
2. Formação dos agrupamentos ótimos de potências de 2:
   • Grupo 1 (Quadra por Envelopamento de Colunas Externas):
     • Células $\{m_0,m_2,m_4,m_6\}$ (Colunas $00$ e $10$ em ambas as linhas);
     • Como cobre ambas as linhas, a variável $A$ é eliminada;
     • Entre as colunas $00$ e $10$, a variável $B$ varia ($0$ e $1$), fixando $C=0⟹\overline{C}$;
     • Termo 1: $\overline{C}$.
   • Grupo 2 (Par de 1s Adjacentes):
     • Célula $m_7$ ($111$) precisa ser coberta. Sua vizinha imediata é $m_6$ ($110$);
     • Grupo $\{m_6,m_7\}$ na linha $A=1$:
       • $A$ é fixado em $1$;
       • Entre as colunas $11$ e $10$, a variável $B$ permanece $1$ e $C$ varia ($1$ e $0$);
       • Termo 2: $A\cdot B$.
3. Expressão simplificada final: $S=\overline{C}+AB$

Resposta Correta: A