EA-772-AULA-12-Circuitos-combinatArios-e-mapas-de-Karnaugh--2018-xx

Prévia do material em texto

UNIVERSIDADE ESTADUAL DE CAMPINAS 
FACULDADE DE ENGENHARIA ELÉTRICA E DE COMPUTAÇÃO 
EA – 772 CIRCUITOS LÓGICOS 
2S-2018 – TURMA A 
 
 
 
Aula 12 
Circuitos combinatórios e mapas de 
Karnaugh 
 
 
 
 
 
 
 
 
 
 
 
PROF. JOSÉ W M BASSANI 
EA-772 Circuitos Lógicos – Aula 12 
Segundo Semestre de 2018, Professor: Bassani, JWM 
2 
 
 
 
AGOSTO DE 2018 
 
Aula 12. 
Funções booleanas e circuitos digitais 
Circuitos digitais 
 
 
 
 
 
 
Circuitos combinatórios 
Circuito lógico 
combinatório
a1
a2
an
.
.
.
s= f(a1, a2, a3)
 
 
Para construir o circuito combinatório partimos da especificação, que é a tabela verdade (TV). 
 
 TV 
 
 
 
 
 
 
 
linha x y z f 
0 0 0 0 1 
1 0 0 1 1 
2 0 1 0 1 
3 0 1 1 1 
4 1 0 0 0 
5 1 0 1 1 
6 1 1 0 1 
7 1 1 1 0 
Combinacionais ou combinatórios 
(sem memória) 
Seqüenciais 
(com memória) 
A saída depende apenas da 
combinação atual das entradas 
A saída depende das entradas atuais 
e do estado interno do circuito 
saída 
entradas 
Definições: 
1. Mintermo (AND): produto lógico das 
variáveis de entrada, complementadas 
se seu valor for zero; 
2. Maxtermo (OR): soma lógica das 
variáveis de entrada, complementadas 
se seu valor for 1; 
EA-772 Circuitos Lógicos – Aula 12 
Segundo Semestre de 2018, Professor: Bassani, JWM 
3 
 
Pela TV: Linha 2: mintermo= x’·y·z’ 
 maxtermo= x+ y’+ z 
 Linha 4: mintermo= x·y’·z’ 
 maxtermo= x’+ y+ z 
3. Soma canônica: soma lógica (OR) dos mintermos para as saídas iguais a 1; 
4. Produto canônico: produto lógico (AND) dos maxtermos para as saídas iguais a 0. 
 
Exemplo: Sc= fmin= x’y’z’ + x’y’z + x’yz’ + x’yz + xy’z + xyz’ 
 Pc= fmax= (x’ + y + z) · (x’ + y’ + z’) 
 fmin fmax 
 
As combinações das entradas podem ser expressas em decimal. Assim, a especificação do 
nosso exemplo fica: 
f(x, y, z)= S(0, 1, 2, 3, 5, 6) 
 = P(4, 7) 
 
Exercício: Mostre que fmin equivalente a fmax para: 
 
 
 
 
Desenvolvendo o lado direito de fmax: 
(aa + ab’ + ba + bb’) · (a’ + b) 
(a + ab’ + ba) · (a’ + b) 
aa’ + ab + aa’b’ + ab’b + baa’ + bab 
ab + ab 
ab = fmin 
 
 
a b x 
0 0 0 
0 1 0 
1 0 0 
1 1 1 
fmin= ab 
fmax= (a+b)·(a+b’)·(a’+b) 
EA-772 Circuitos Lógicos – Aula 12 
Segundo Semestre de 2018, Professor: Bassani, JWM 
4 
 
5. Especificação na presença de don’t care: 
 
 
 
 
 
 
 
Exemplo: 
 
 
 
 
fs(x, y)= x’y + xy’ ← Considerando X= 1 
fp(x, y)= (x + y) · (x’ + y’) · (x’ + y) ← Considerando X= 0 
 
Exemplo: 
 
 
 
 
Para casa: Fazer para X= 0. 
 
 
 
 
 
 x y z f 
0 0 0 0 0 
1 0 0 1 1 
2 0 1 0 0 
3 0 1 1 1 
4 1 0 0 X 
5 1 0 1 0 
6 1 1 0 X 
7 1 1 1 0 
 x y s 
0 0 0 0 
1 0 1 1 
2 1 0 X 
3 1 1 0 
a b f 
0 0 1 
0 1 X 
1 0 1 
1 1 0 
fmin(x, y, z)= S(1,3) + D(4,6) 
fmax(x, y, z)= P(0,2,5,7) · D(4,6) 
Don’t care 
fmin(x, y, z)= S(1) + D(2) 
fmax(x, y, z)= P(0,3) · D(2) 
Para X= 1: 
fmin(a, b)= a’b’+ab’+a’b= S(0,2) + D(1) 
fmax(a, b)= a’+b’= P(3) 
EA-772 Circuitos Lógicos – Aula 12 
Segundo Semestre de 2018, Professor: Bassani, JWM 
5 
 
 
6. Mapas de Veitch-Karnaugh (Mapas de Karnaugh – MK) 
Mapeamento biunívoco da TV. Criados inicialmente por Edward Veitch (1952) e aperfeiçoados 
pelo engenheiro de comunicações Maurice Karnaugh. 
 
 TV MK 
 
 
 
A organização do MK é tal que as células adjacentes (vizinhas) diferem em apenas uma 
posição binária. 
 
7. Definição: As células vizinhas podem caracterizar subcubos de ordem 2n. Uma célula do 
mapa é um subcubo de ordem 20= 1. As células dos subcubos podem ser combinadas 
formando um novo mintermo. 
 
 a b c f 
0 0 0 0 1 
1 0 0 1 1 
2 0 1 0 0 
3 0 1 1 1 
4 1 0 0 1 
5 1 0 1 0 
6 1 1 0 0 
7 1 1 1 1 
EA-772 Circuitos Lógicos – Aula 12 
Segundo Semestre de 2018, Professor: Bassani, JWM 
6 
 
 
Simplificação de funções booleanas usando MK 
1. Juntar células adjacentes em subcubos de ordem 2n= 1, 2, 4, ...; 
2. Criar tantos subcubos quantos necessários para “cobrir” toda a função; 
3. É um implicante primo da função o subcubo que não estiver contido em outro de ordem 
maior; 
4. Extrair a função canônica mínima pela soma lógica de todos os mintermos (implicantes 
primos); 
Exemplos: 
 
 
 
F = a´b´c + ab´c + abc + abc´ 
F = ab + b´c 
 
 
 
 
 
 
 
 
F= ab + b´c 
Como descobrir esta 
combinação 
“automaticamente”? 
EA-772 Circuitos Lógicos – Aula 12 
Segundo Semestre de 2018, Professor: Bassani, JWM 
7 
 
 
 
5. Fmin= ∑ implicantes primos 
Mais exemplos: 
 
 
 
 
 
 
 
 
F= bd 
F= b´c´d + bd´ 
EA-772 Circuitos Lógicos – Aula 12 
Segundo Semestre de 2018, Professor: Bassani, JWM 
8 
 
 
 
 
 
 
F= a´bd + ab´d´ 
F= b 
F= ab 
F= b´ + a’ + c 
EA-772 Circuitos Lógicos – Aula 12 
Segundo Semestre de 2018, Professor: Bassani, JWM 
9 
 
 
 
Exercícios para casa: 
1. Dada a TV, fazer o MK e obter a função mínima: 
 
 
 
 
 
 
2. Dada a TV 
 
 
 
 
 
 
a b c x 
0 0 0 0 
0 0 1 1 
0 1 0 0 
0 1 1 1 
1 0 0 1 
1 0 1 0 
1 1 0 0 
1 1 1 1 
a b c liga 
0 0 0 1 
0 0 1 1 
0 1 0 1 
0 1 1 X 
1 0 0 0 
1 0 1 0 
1 1 0 1 
1 1 1 1 
a’bc’d + bd = 
= bd(a’c’+1)= bd 
F= acd + bd + a´b´cd´ 
F= b’d’ 
EA-772 Circuitos Lógicos – Aula 12 
Segundo Semestre de 2018, Professor: Bassani, JWM 
10 
 
E se não houver o don’t care? Assuma que X= 0 e resolva novamente. No caso anterior, a 
existência do don’t care possibilitou assumir X=1 e melhorar a simplificação. 
Bibliografia 
-Bassani JWM. 
 Notas de aula – Circuitos Lógicos. 
-Veja a lista de referencias indicadas na primeira aula 
 
(Veja no site indicado para a disciplina o material didático e bibliografia indicada)