Sistemas Digitais - Mapas de Karnaugh

Sistemas Digitais I
Introduc¸a\u2dco
Myle`ne Christine Queiroz de Farias
Departamento de Engenharia Ele´trica
Universidade de Bras´\u131lia (UnB)
Bras´\u131lia, DF 70910-900
mylene@unb.br
March 22, 2018
Aula 04: Mapas de Karnaugh
Suma´rio
Mapas de Karnaugh;
2 / 65
Mapas de Karnaugh
Mapas de Karnaugh
Forma de Tabela verdade ou uma extensa\u2dco do diagrama de Venn;
Cada \u2018quadrado\u2019 representa um mintermo da expressa\u2dco booleana;
Permite encontrar as redundancias das varia´veis de entrada da
expressa\u2dco, ajudando a reduzir a expressa\u2dco de sa´\u131da
Cada mapa mostra os termos-produto (mintermos) que podem ser
formados por n varia´veis, cada um em um quadrado distinto.
3 varia´veis: 8 mintermos
4 varia´veis: 16 mintermos
3 / 65
Mapas de Karnaugh
4 / 65
Mapas de Karnaugh
5 / 65
Mapas de Karnaugh
Um mapa de n varia´veis tera´ 2n quadrados, cada um representado um
mintermo;
O mintermo em cada quadrado ou elemento do mapa e´ o produto das
varia´veis listadas na linha e na coluna do elemento;
O mapa e´ preenchido colocando-se 1\u2019s nos quadrados cujos
mintermos correspondentes levam a resposta a zero.
6 / 65
Mapas de Karnaugh
O uso do mapa de Karnaugh e´ regido pela disposic¸a\u2dco de seus
elementos (quadrados);
Cada elemento difere do elemento adjacente por ter exatamente uma
varia´vel complementar em seu mintermo;
Cada expressa\u2dco deve ser escrita em sua forma canonica e cada termo
da expresso deve conter cada uma das varia´veis de entrada.
7 / 65
Mapas de Karnaugh
Exemplo:
Z = A · B · C + A · B · C + A · B · C + A · B · C
8 / 65
Mapas de Karnaugh
Exemplo:
Z = A · B · C + A · B · C + A · B · C + A · B · C
A linha BC e´ numerada de modo que somente ocorra mudana de 1
bit quando se passar de um quadrado para outro adjacente (Na\u2dco e´
numerada na sequencia usual, mas em relac¸a\u2dco a`s varia´veis.
Se elementos adjacentes tiverem o valor 1:
O produto dos termos correspondentes diferem em apenas uma varia´vel
Os termos podem ser simplificados de modo a eliminar essa varia´vel. 9 / 65
Mapas de Karnaugh
Exemplo:
Z = A · B · C + A · B · C + A · B · C + A · B · C
Expressa\u2dco M\u131´nima:
Z = A · B + B · C
... Pode-se incluir o terceiro c´\u131culo:
Z = A · B + B · C + A · C
Mas, na\u2dco seria a expressa\u2dco m´\u131nima. Os dois c´\u131rculos cobrem a expressa\u2dco
m´\u131nima.
10 / 65
Mapas de Karnaugh
Exemplo:
Z = A · B · C + A · B · C + A · B · C + A · B · C
Expressa\u2dco M\u131´nima:
Z = A · B + B · C
... Pode-se incluir o terceiro c´\u131culo:
Z = A · B + B · C + A · C
Mas, na\u2dco seria a expressa\u2dco m´\u131nima. Os dois c´\u131rculos cobrem a expressa\u2dco
m´\u131nima.
10 / 65
Mapas de Karnaugh
Exemplo1:
F = B(A + A)
11 / 65
Mapas de Karnaugh
Exemplo2:
f (A,B,C ) = A · B + A · C + B · C
12 / 65
Mapas de Karnaugh
Exemplo3:
f (A,B,C ) = A · C + B · C + A · B
= A · C + B · C
13 / 65
Mapas de Karnaugh
Exemplo4:
f (A,B,C ) = A · B · C + A · B · C + A · B · C + A · B · C
= A · C + A · C
= A
14 / 65
Mapas de Karnaugh
Exemplo4:
f (A,B,C ) = A · B · C + A · B · C + A · B · C + A · B · C
= B · C + A · C
15 / 65
Mapas de Karnaugh
16 / 65
Mapas de Karnaugh
Pode-se combinar apenas 1\u2019s que sejam adjacentes
Pode-se combinar 1\u2019s apenas em grupos de pote\u2c6ncia de 2 (1,2,4,8
etc.)
Deve-se tentar formar os maiores grupos poss´\u131veis
Na\u2dco gerar grupos ale´m do necessa´rio para cobrir todos os 1\u2019s
17 / 65
Mapas de Karnaugh
Regra para agrupamento de termos (exemplos):
18 / 65
Mapas de Karnaugh
Regra para agrupamento de termos (exemplos):
19 / 65
Mapas de Karnaugh
Mapas de 4 varia´veis:
20 / 65
Mapas de Karnaugh
Mapas de 4 varia´veis: Exemplos
21 / 65
Mapas de Karnaugh
Mapas de 4 varia´veis: Exemplos
22 / 65
Mapas de Karnaugh
Mapas de 4 varia´veis: Exemplos
23 / 65
Mapas de Karnaugh
Mapas de 5 varia´veis:
24 / 65
Implicantes
Para um dado termo, cada aparic¸a\u2dco de uma varia´vel (em sua forma
natural ou complementar) e´ chamada de literal:
xyz \u2013 3 literais
abcd \u2013 4 literais
Qualquer \u20181\u2019 ou grupo de \u20181\u2019s que podem ser combinados em um
mapa de Karnaugh representa um termo implicante de uma func¸a\u2dco.
Um implicante e´ denominado implicante-primo se na\u2dco puder ser
combinado com outro implicante para que uma varia´vel seja
eliminada.
25 / 65
Implicantes
Terminologia:
26 / 65
Implicantes
Implicante primo:
Essencial: necessa´rio para formar uma soluc¸a\u2dco m´\u131nima
Na\u2dco-essencial: na\u2dco necessa´rio para formar uma soluc¸a\u2dco m´\u131nima
27 / 65
Implicantes
Exemplo:
28 / 65
Implicantes
Ce´lula 1 Distinta
Uma ce´lula 1 distinta uma combinac¸a\u2dco de entrada que e´ coberta por
apenas um implicante primo.
Implicante Primo Essencial
Um implicante primo essencial e´ um implicante primo que cobre uma (ou
mais) ce´lula(s) 1 distinta(s).
Como um implicante primo essencial e´ o u´nico implicante primo que cobre
alguma ce´lula 1 distinta, ele deve estar inclu´\u131do na soma m´\u131nima (sena\u2dco, a
soma estaria necessariamente incompleta).
29 / 65
Implicantes
Ce´lula 1 Distinta
Uma ce´lula 1 distinta uma combinac¸a\u2dco de entrada que e´ coberta por
apenas um implicante primo.
Implicante Primo Essencial
Um implicante primo essencial e´ um implicante primo que cobre uma (ou
mais) ce´lula(s) 1 distinta(s).
Como um implicante primo essencial e´ o u´nico implicante primo que cobre
alguma ce´lula 1 distinta, ele deve estar inclu´\u131do na soma m´\u131nima (sena\u2dco, a
soma estaria necessariamente incompleta).
29 / 65
Implicantes
Ce´lula 1 Distinta
Uma ce´lula 1 distinta uma combinac¸a\u2dco de entrada que e´ coberta por
apenas um implicante primo.
Implicante Primo Essencial
Um implicante primo essencial e´ um implicante primo que cobre uma (ou
mais) ce´lula(s) 1 distinta(s).
Como um implicante primo essencial e´ o u´nico implicante primo que cobre
alguma ce´lula 1 distinta, ele deve estar inclu´\u131do na soma m´\u131nima (sena\u2dco, a
soma estaria necessariamente incompleta).
29 / 65
Passos para Obter a Func¸a\u2dco M´\u131nima
Logo, o primeiro passo na selec¸a\u2dco de implicantes primos e´ identificarmos
as ce´lulas 1 distintas e os implicantes primos essenciais correspondentes e
incluirmos esses termos na soma.
Em seguida, precisamos determinar como cobrir as ce´lulas 1 que na\u2dco
foram cobertas pelos implicantes primos essenciais (se houver).
30 / 65
Passos para Obter a Func¸a\u2dco M´\u131nima
Exemplos
F
WX
YZ
0
0
1
1
1
1
1
1
0
0
0
1
0
1
0
1
00
01
11
10
00 01 11 10
F = W · Y + W · X + X · Z + Y · Z
Como todas as ce´lulas 1 distintas sa\u2dco
cobertas pelos implicantes primos
essenciais, essa e´ a soma m´\u131nima.
31 / 65
Exemplos
F
WX
YZ
1
1
1
1
1
1
0
1
0
0
0
0
0
0
1
1
00
01
11
10
00 01 11 10
Uma func¸a\u2dco lo´gica onde nem todas
as ce´lulas 1 distintas sa\u2dco cobertas
por implicantes primos essenciais e´
mostrada ao lado.
32 / 65
Exemplos
Removendo os implicantes primos essenciais:
F
WX
YZ
1
00
01
11
10
00 01 11 10
Chegamos a apenas uma ce´lula 1 e
os implicantes primos que cobrem
esta ce´lula (W · Z e X · Y · Z).
Neste caso, a escolha e´ simples:
usamos o termo W · Z pois ele tem
menos literais.
33 / 65
Exemplos
Exemplos
F
WX
YZ
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1 1
1
11
1
00
01
11
10
00 01 11 10
Os implicantes primos que englobam
os mintermos 2 (W · Y · Z) e 9
(W · Y · Z) so implicantes primos
essenciais e, portanto, devem ser
inclu´\u131dos na soma m´\u131nima.
Como decidir entre os demais
implicantes