Sistemas Digitais - 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 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˜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
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’s 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˜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.
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˜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. 9 / 65
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.
10 / 65
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.
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’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
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˜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.
25 / 65
Implicantes
Terminologia:
26 / 65
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
27 / 65
Implicantes
Exemplo:
28 / 65
Implicantes
Ce´lula 1 Distinta
Uma ce´lula 1 distinta uma combinac¸a˜o 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´ıdo na soma m´ınima (sena˜o, a
soma estaria necessariamente incompleta).
29 / 65
Implicantes
Ce´lula 1 Distinta
Uma ce´lula 1 distinta uma combinac¸a˜o 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´ıdo na soma m´ınima (sena˜o, a
soma estaria necessariamente incompleta).
29 / 65
Implicantes
Ce´lula 1 Distinta
Uma ce´lula 1 distinta uma combinac¸a˜o 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´ıdo na soma m´ınima (sena˜o, a
soma estaria necessariamente incompleta).
29 / 65
Passos para Obter a Func¸a˜o M´ınima
Logo, o primeiro passo na selec¸a˜o 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˜o
foram cobertas pelos implicantes primos essenciais (se houver).
30 / 65
Passos para Obter a Func¸a˜o M´ınima
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˜o
cobertas pelos implicantes primos
essenciais, essa e´ a soma m´ınima.
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˜o lo´gica onde nem todas
as ce´lulas 1 distintas sa˜o 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´ıdos na soma m´ınima.
Como decidir entre os demais
implicantesprimos?
34 / 65
Exemplos
Exemplos
F
WX
YZ
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1 1
00
01
11
10
00 01 11 10
Os demais implicantes primos sa˜o:
W · X · Y , X · Y · Z e W · X · Z.
Podemos observar que X · Y · Z
eclipsa os demais implicantes primos
W · X · Y e W · X · Z (i.e., ele cobre
pelo todas as ce´lulas 1s cobertas por
estes implicantes primos). Como
X · Y · Z no custa mais do que os
demais, podemos retirar os outros de
considerac¸a˜o. Logo, X · Y · Z deve
ser inclu´ıdo na soma m´ınima.
F = W ·Y · Z + W ·Y · Z + X ·Y · Z
Dizemos que X · Y · Z e´ um
implicante primo essencial
secunda´rio. 35 / 65
Exemplos
F
WX
YZ
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1 1
1
1
11
00
01
11
10
00 01 11 10
Esta func¸a˜o na˜o tem nenhum
implicante primo essencial!
Como proceder nesses casos?
36 / 65
Exemplo
Branching Method
1 Comec¸ando com uma ce´lula 1 qualquer, selecionamos um implicante
primo que cobre essa ce´lula como se ele fosse essencial, e removemos
ele do mapa.
2 Aplicamos o me´todo visto anteriormente (identificar as ce´lulas 1
distintas, identificar os implicantes primos essenciais, etc...).
3 Quando terminamos, repetimos o processo utilizando o outro
implicante primo (isto e´, aquele que deixamos de fora inicialmente),
gerando uma segunda tentativa de soma m´ınima.
4 Finalmente, comparamos o custo de todas as alternativas e
escolhemos a menor.
Pode ocorrer de ficarmos empacados (isto e´, na˜o encontrarmos nenhum
implicante primo essencial). Neste caso, podemos aplicar esse
procedimento recursivamente.
37 / 65
Exemplos
F
WX
YZ
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1 1
1
1
11
00
01
11
10
00 01 11 10
F = W ·X · Z + W ·Y · Z + X ·Y · Z
F
WX
YZ
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1 1
1
1
11
00
01
11
10
00 01 11 10
F = X ·Y · Z + W ·X · Z + W ·Y · Z
38 / 65
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
39 / 65
Produto de Somas
Exemplo:
40 / 65
Produto de Somas
Exemplo:
41 / 65
Mapas de Karnaugh
Exemplo:
42 / 65
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
43 / 65
Minimizac¸a˜o com indiferenc¸as
Exemplo:
44 / 65
Minimizac¸a˜o com indiferenc¸as
Exemplo:
45 / 65
Minimizac¸a˜o com indiferenc¸as
Exemplo:
46 / 65
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)
47 / 65
Minimizac¸a˜o com va´rias sa´ıdas
Exemplo:
48 / 65
Minimizac¸a˜o com va´rias sa´ıdas
Minimizac¸a˜o com com va´rias sa´ıdas:
49 / 65
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.
50 / 65
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
51 / 65
Va´riaveis Introduzidas
Podemos reduzir a dimensa˜o do mapa de Karnaugh introduzindo varia´veis
no mapa.
A ideia ba´sica e´ expressar F em termos de uma varia´vel V. Para func¸o˜es
de especificac¸a˜o completa (isto e´, sem don’t cares), temos quatro
possibilidades:
V F F (V)
0 0
0
1 0
V F F (V)
0 0
V
1 1
V F F (V)
0 1
1
1 1
V F F (V)
0 1
V
1 0
52 / 65
Va´riaveis Introduzidas
Considere a func¸a˜o de 4 varia´veis:
Linha W X Y Z F
0 0 0 0 0 1
1 0 0 0 1 1
2 0 0 1 0 0
3 0 0 1 1 1
4 0 1 0 0 1
5 0 1 0 1 1
6 0 1 1 0 0
7 0 1 1 1 0
8 1 0 0 0 1
9 1 0 0 1 0
10 1 0 1 0 0
11 1 0 1 1 0
12 1 1 0 0 1
13 1 1 0 1 1
14 1 1 1 0 0
15 1 1 1 1 0
F
WX
YZ
1
1
1
1
1
11
1
00
01
11
10
00 01 11 10
F = Y · Z + X · Y + W · X · Z
53 / 65
Va´riaveis Introduzidas
Podemos montar uma tabela de F (Z):
Linha W X Y Z F
0 0 0 0 0 1
1 0 0 0 1 1
2 0 0 1 0 0
3 0 0 1 1 1
4 0 1 0 0 1
5 0 1 0 1 1
6 0 1 1 0 0
7 0 1 1 1 0
8 1 0 0 0 1
9 1 0 0 1 0
10 1 0 1 0 0
11 1 0 1 1 0
12 1 1 0 0 1
13 1 1 0 1 1
14 1 1 1 0 0
15 1 1 1 1 0
Linha W X Y F (Z)
0 0 0 0 1
1 0 0 1 Z
2 0 1 0 1
3 0 1 1 0
4 1 0 0 Z
5 1 0 1 0
6 1 1 0 1
7 1 1 1 0
54 / 65
Va´riaveis Introduzidas
Podemos montar uma tabela de F (Z):
Linha W X Y F (Z)
0 0 0 0 1
1 0 0 1 Z
2 0 1 0 1
3 0 1 1 0
4 1 0 0 Z
5 1 0 1 0
6 1 1 0 1
7 1 1 1 0
E tambe´m o mapa de F (Z):
FZ
WX
Y
0
1
2
3
4
5
6
7
1
Z
1
0
Z
0
1
0
0
1
00 01 11 10
55 / 65
Va´riaveis Introduzidas
Como proceder para minimizar o mapa de Karnaugh de F (Z)?
FZ
WX
Y
0
1
2
3
4
5
6
7
1
Z
1
0
Z
0
1
0
0
1
00 01 11 10
Esta minimizac¸a˜o e´ realizada em duas etapas. Na primeira etapa, devem
ser cobertos os termos contendo Z e Z, sendo que na˜o e´ necessa´rio cobrir
os termos 1s (na˜o nessa etapa).
Os termos Z podem ser associados, em ordem de prioridade, com os
termos Z e 1 (pois 1 = Z + Z), e os termos Z podem ser associados, em
ordem de prioridade, com os termos Z e 1 (pelo mesmo motivo anterior).
56 / 65
Va´riaveis Introduzidas
Logo, podemos fazer os agrupamentos:
FZ
WX
Y
1
Z
1
0
Z
0
1
0
0
1
00 01 11 10
Note que devemos multiplicar o valor do termo gerado pelo agrupamento
pelo valor da varia´vel dentro do mapa. Logo, geramos os termos: Y · Z e
W · X · Z.
57 / 65
Va´riaveis Introduzidas
Na segunda etapa do processo, ja´ com os termos Z e Z cobertos,
redesenhamos o mapa fazendo as seguintes substituic¸o˜es:
Termo original Substitu´ıdo por
Z, Z ou 0 0
1, se foi associado com Z e Z d
1, se na˜o foi associado com Z e Z 1
E o mapa se torna:
FZ
WX
Y
d 1 10
1
00 01 11 10
O que gera o termo X · Y.
58 / 65
Va´riaveis Introduzidas
Finalmente:
Linha W X Y F (Z)
0 0 0 0 1
1 0 0 1 Z
2 0 1 0 1
3 0 1 1 0
4 1 0 0 Z
5 1 0 1 0
6 1 1 0 1
7 1 1 1 0
FZ
WX
Y
1
Z
1
0
Z
0
1
0
0
1
00 01 11 10
F = Y · Z + X · Y + W · X · Z
59 / 65