Mapas de Karnaugh

Prévia do material em texto

Sistemas Digitais I
Introduc¸a˜o
Myle`ne Christine Queiroz de Farias
Departamento de Engenharia Ele´trica
Universidade de Bras´ılia (UnB)
Bras´ılia, DF 70910-900
mylene@unb.br
March 10, 2018
Aula 04: Mapas de Karnaugh
Suma´rio
Mapas de Karnaugh;
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 2 / 1
Mapas de Karnaugh
Mapas de Karnaugh
Forma de Tabela verdade ou uma extensa˜o do diagrama de Venn;
Cada ‘quadrado’ representa um mintermo da expressa˜o booleana;
Permite encontrar as redundancias das varia´veis de entrada da
expressa˜o, ajudando a reduzir a expressa˜o de sa´ıda
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
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 3 / 1
Mapas de Karnaugh
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 4 / 1
Mapas de Karnaugh
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 5 / 1
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’s nos quadrados cujos
mintermos correspondentes levam a resposta a zero.
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 6 / 1
Mapas de Karnaugh
O uso do mapa de Karnaugh e´ regido pela disposic¸a˜o de seus
elementos (quadrados);
Cada elemento difere do elemento adjacente por ter exatamente uma
varia´vel complementar em seu mintermo;
Cada expressa˜o deve ser escrita em sua forma canonica e cada termo
da expresso deve conter cada uma das varia´veis de entrada.
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 7 / 1
Mapas de Karnaugh
Exemplo:
Z = A · B · C + A · B · C + A · B · C + A · B · C
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 8 / 1
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˜o e´
numerada na sequencia usual, mas em relac¸a˜o 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.
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 9 / 1
Mapas de Karnaugh
Exemplo:
Z = A · B · C + A · B · C + A · B · C + A · B · C
Expressa˜o Mı´nima:
Z = A · B + B · C
... Pode-se incluir o terceiro c´ıculo:
Z = A · B + B · C + A · C
Mas, na˜o seria a expressa˜o m´ınima. Os dois c´ırculos cobrem a expressa˜o
m´ınima.
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 10 / 1
Mapas de Karnaugh
Exemplo:
Z = A · B · C + A · B · C + A · B · C + A · B · C
Expressa˜o Mı´nima:
Z = A · B + B · C
... Pode-se incluir o terceiro c´ıculo:
Z = A · B + B · C + A · C
Mas, na˜o seria a expressa˜o m´ınima. Os dois c´ırculos cobrem a expressa˜o
m´ınima.Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 10 / 1
Mapas de Karnaugh
Exemplo1:
F = B(A + A)
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 11 / 1
Mapas de Karnaugh
Exemplo2:
f (A,B,C ) = A · B + A · C + B · C
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 12 / 1
Mapas de Karnaugh
Exemplo3:
f (A,B,C ) = A · C + B · C + A · B
= A · C + B · C
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 13 / 1
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
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 14 / 1
Mapas de Karnaugh
Exemplo4:
f (A,B,C ) = A · B · C + A · B · C + A · B · C + A · B · C
= B · C + A · C
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 15 / 1
Mapas de Karnaugh
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 16 / 1
Mapas de Karnaugh
Pode-se combinar apenas 1’s que sejam adjacentes
Pode-se combinar 1’s apenas em grupos de poteˆncia de 2 (1,2,4,8
etc.)
Deve-se tentar formar os maiores grupos poss´ıveis
Na˜o gerar grupos ale´m do necessa´rio para cobrir todos os 1’s
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 17 / 1
Mapas de Karnaugh
Regra para agrupamento de termos (exemplos):
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 18 / 1
Mapas de Karnaugh
Regra para agrupamento de termos (exemplos):
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 19 / 1
Mapas de Karnaugh
Mapas de 4 varia´veis:
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 20 / 1
Mapas de Karnaugh
Mapas de 4 varia´veis: Exemplos
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 21 / 1
Mapas de Karnaugh
Mapas de 4 varia´veis: Exemplos
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 22 / 1
Mapas de Karnaugh
Mapas de 4 varia´veis: Exemplos
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 23 / 1
Mapas de Karnaugh
Mapas de 5 varia´veis:
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 24 / 1
Implicantes
Para um dado termo, cada aparic¸a˜o de uma varia´vel (em sua forma
natural ou complementar) e´ chamada de literal:
xyz – 3 literais
abcd – 4 literais
Qualquer ‘1’ ou grupo de ‘1’s que podem ser combinados em um
mapa de Karnaugh representa um termo implicante de uma func¸a˜o.
Um implicante e´ denominado implicante-primo se na˜o puder ser
combinado com outro implicante para que uma varia´vel seja
eliminada.
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 25 / 1
Implicantes
Terminologia:
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 26 / 1
Implicantes
Implicante primo:
Essencial: necessa´rio para formar uma soluc¸a˜o m´ınima
Na˜o-essencial: na˜o necessa´rio para formar uma soluc¸a˜o m´ınima
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 27 / 1
Implicantes
Exemplo:
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 28 / 1
Produto de Somas
Minimizac¸a˜o usando mapas de Karnaugh tambe´m pode ser feita
usando a forma produto de somas (POS)
O procedimento e´ o mesmo, entretanto, faz-se agrupamentos de 0s
Deve-se atribuir 0 no mapa para todos os maxtermos que fazem parte
da func¸a˜o
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 29 / 1
Produto de Somas
Exemplo:
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 30 / 1
Produto de Somas
Exemplo:
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 31 / 1
Mapas de Karnaugh
Exemplo:
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 32 / 1
Minimizac¸a˜o com indiferenc¸as
Frequentemente, em sistemas digitais, algumas condio˜es de entrada,
ou seja, algumas combinac¸o˜es doa valores de entrada na˜o acontecem
Uma combinac¸a˜o de entradas que pode nunca acontecer e´
denominada dont care ou indiferenc¸a
Quando um circuito e´ projetado, um dont care pode ser ignorado (a
sa´ıda pode ser tratada como ‘1’ ou ‘0’ na tabela-verdade)
Um func¸a˜o que tem dont care e´ denominada func¸a˜o de
especificac¸a˜o incompleta
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 33 / 1
Minimizac¸a˜o com indiferenc¸as
Exemplo:
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 34 / 1
Minimizac¸a˜o com indiferenc¸as
Exemplo:
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 35 / 1
Minimizac¸a˜o com indiferenc¸as
Exemplo:
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 36 / 1
Minimizac¸a˜o com va´rias sa´ıdas
Ate´ agora somente exemplos com uma u´nica sad´a foram considerados
Geralmente, na pra´tica, os sistemas possuem mais de uma sa´ıda
Circuitos podem ser combinados de forma a implementar o sistema
com o menor custo poss´ıvel (menor nmero de portas)
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 37 / 1
Minimizac¸a˜o com va´rias sa´ıdas
Exemplo:
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 38 / 1
Minimizac¸a˜o com va´rias sa´ıdas
Minimizac¸a˜o com com va´rias sa´ıdas:
Myle`ne Farias(ENE-UnB) SD1 March 10, 2018 39 / 1
Minimizac¸a˜o com va´rias sa´ıdas
Exemplo: Supor que as func¸o˜es F1 e F2 abaixo sa˜o sa´ıdas do mesmo
circuito:
F1 = A · D + B · D + A · B · C F2 = B · D + A · D + A · B · C · D
F1 possui 4 portas AND, 2 portas OR, 2 inversoras e 5 entradas. F2 possui
5 portas AND, 2 portas OR, 3 inversoras e 7 entradas.
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 40 / 1
Minimizac¸a˜o com com va´rias sa´ıdas:
F1 = A · D + A · B · D + A · B · C · D F2 = B · D + A · B · D + A · B · C · D
F1 possui 6 portas AND, 2 portas OR e 3 inversoras. F2 possui 6 portas
AND, 2 portas OR e 3 inversoras. Observe que F1 e F2 possui possuem 2
termos em comum. Logo, o sistema geral pode ser implementado com
F = A · D + B · D + A · B · D + A · B · C · D
que utiliza 7 portas AND, 3 portas OR e 3 inversoras
Myle`ne Farias (ENE-UnB) SD1 March 10, 2018 41 / 1