View
111
Download
2
Category
Preview:
Citation preview
Circuitos Digitais CIC - UnB
Soma de ProdutosSoma de Produtos
• Soma de produtos é uma forma padrão de representação de funções Booleanas constituida pela aplicação da operação lógica OU sobre um conjunto de termos formados pela operação E:
ABACFDZ
Z = AB AC D’F
Termo produto
Soma de produtos
2 níveis lógicos
Circuitos Digitais CIC - UnB
Produto de SomasProduto de Somas
• O produto de somas é outra forma padrão de representação de funções Booleanas caracterizada pela aplicação da operação E sobre um conjunto de operações OU sobre as entradasABACFDZ
2 níveis lógicos
Z = (A B)(A C)(D’ F)
Termo soma
Produto de Somas
Circuitos Digitais CIC - UnB
MintermosMintermos
• Um mintermo é um termo produto que vale 1 em apenas um ponto do domínio de uma função Booleana• É definido por um produto (AND) onde cada variável aparece apenas uma vez, direta ou
complementada
F = A’BC 00010000
C01010101
B00110011
A00001111
Mintermo A’BC
Circuitos Digitais CIC - UnB
MaxtermosMaxtermos
• Um maxtermo é um termo soma que vale 0 (zero) em apenas um ponto do domínio da função
• É determinado por uma disjunção (OR) onde cada variável aparece apenas uma vez, direta ou complementada
F 11101111
C01010101
B00110011
A00001111
Maxtermo (A’ B C)
Circuitos Digitais CIC - UnB
Formas CanônicasFormas Canônicas
• Uma tabela verdade é uma assinatura que identifica unívocamente uma função Booleana
• Espressões Booleanas diferentes podem representar uma mesma função Booleana
F00011111
F11100000
C01010101
B00110011
A00001111
F = A C
F = A B A B’ C
F = A B C B’ C’) C
Tabela Verdade Espressões Booleanas
Circuitos Digitais CIC - UnB
Formas Canônicas Dois NíveisFormas Canônicas Dois Níveis
• Formas Canônicas são representações (assinaturas) únicas de funções Booleanas– Ex: uma soma de produtos é uma forma canônica
F = A' B C A B' C' A B' C A B C' A B C0 1 1 1 0 0 1 0 1 1 1 0 1 1 1
F' = A' B' C' A' B' C A' B C'
F00011111
F11100000
C01010101
B00110011
A00001111
OR de 1’s
Circuitos Digitais CIC - UnB
Formas Canônicas Dois NíveisFormas Canônicas Dois Níveis
• Formas Canônicas são representações (assinaturas) únicas de funções Booleanas– Ex: produto de somas é outra forma canônica
F = (A B C) (A B C’) (A B’ C)0 0 0 0 0 1 0 1 0
F' = (A B’ C’) (A B’ C’) (A B’ C) (A B C’) (A B C)
F00011111
F11100000
C01010101
B00110011
A00001111
AND de 0’s
Circuitos Digitais CIC - UnB
Formas Canônicas Dois NíveisFormas Canônicas Dois Níveis
• Notação para soma de mintermos:– F(A,B,C) = (1, 3, 5, 7)
= m1 m3 m5 m7
= A B C’ A B' C' A B’ C A B C
• Notação para produto de maxtermos:– F(A,B,C) = (0, 2, 4, 6)
= M0·M2·M4·M6
= (A B C) (A B’ C) (A’ B C) (A’ B’ C)
Circuitos Digitais CIC - UnB
Simplificação de Soma de MintermosSimplificação de Soma de Mintermos
• Usando métodos algébricos:
– F(A,B,C) = ∑(3,4,5,6,7)
= m3 m4 m5 m6 m7
= A' B C A B' C' A B' C A B C' A B C= A B' (C C') A' B C A B (C' C)= A B' A' B C A B= A (B' B) A' B C= A A' B C= A B C B
C
A
FImplementação
Circuitos Digitais CIC - UnB
Mintermos x MaxtermosMintermos x Maxtermos
• É possível obter um produto de maxtermos a partir de uma soma de mintermos e vice-versa aplicando De Morgan sobre o complemento da função
– F(A,B,C) = (1, 2, 3, 5, 7) = A’ B’ C A’ B C’ A B’ C A B C
F ’ (A,B,C) = (0, 4, 6) = A’ B’ C’ A B’ C’ A B C’
F (A,B,C) = (F ’ (A,B,C) )’ = (A’ B’ C’ A B’ C’ A B C’)’
= (A B C’)(A B’ C’)(A’ B’ C’)
= (1, 3, 7)
Circuitos Digitais CIC - UnB
Funções IncompletasFunções Incompletas
• São funções para as quais algumas combinações de valores das entradas nunca ocorrem– Ex: acionador de display de 7 segmentos para dígitos BCD
A0000000011111111
B0000111100001111
C0011001100110011
D0101010101010101
S11011011111XXXXXX
x1x2x3x4
s1
s2
s 3s4
s5
s6 s 7
• 4 entradas -> 16 combinações• apenas 10 utilizadas• 6 combinações nunca ocorrem
• são denominadas irrelevantes(don’t cares)
• podem ser utilizadas para simplificar a lógica
• 4 entradas -> 16 combinações• apenas 10 utilizadas• 6 combinações nunca ocorrem
• são denominadas irrelevantes(don’t cares)
• podem ser utilizadas para simplificar a lógica
Circuitos Digitais CIC - UnB
Funções IncompletasFunções Incompletas
• Funções incompletas mapeiam pontos do domínio da função em 3 valores possíveis:– F(A, B, C, D) { 0, 1, X }
• Os domínios de pontos onde F vale { 0, 1, X} são denominados, respectivamente, de:
F1 = {m0, m2, m3, m5, m6, m7, m8, m9 }
Fx = {i10, i11, i12, i13, i14, i15 }
F0 = {M1, M4 }
• F pode ser descrita definindo-se dois desses três conjuntos:– F (A, B, C, D) = F1 Fx ou F1 F0 ou F0 Fx
Circuitos Digitais CIC - UnB
Minimização Lógica Dois NíveisMinimização Lógica Dois Níveis
• Manipulação algébrica: – Difícil determinar a ordem e quais transformações aplicar
– Como saber se atingiu-se a melhor solução ?
• Ferramentas de auxílio:– Não conseguem tratar problemas grandes de forma exata
– Baseiam-se em heurísticas e critérios de custo
– Resultados bastante bons em lógica dois níveis
• Métodos manuais apenas para fins didáticos ou funções muito simples
Circuitos Digitais CIC - UnB
Minimização Lógica Dois NíveisMinimização Lógica Dois Níveis
• Idéia base: aplicação de distribuição e complemento
A(B A(B B’) = A B’) = A
Dentro de F1:
B varia enquanto
A não muda
Resultado: B é eliminado!Resultado: B é eliminado!
A0011
B0101
F0011
F = A B' + A B = A (B' + B) = A G = A' B' + A B' = (A' + A) B' = B'
Dentro de G1:
A varia enquanto
B não muda
Resultado: A é eliminado!Resultado: A é eliminado!
A0011
B0101
G1010
Circuitos Digitais CIC - UnB
CubosCubos
• O espaço Booleano n-dimencional pode ser visualizado espacialmente• Produtos de literais são chamados de cubos
Cubo 4
WXYZ
01110011
0010
0000
0001
0110
1010
0101
0100
1000
1011
1001
1110
1111
1101
1100
YZ
W
X
XY
X
01
00
11
10
Y
Cubo 3
XYZ
X
011
010
000
001
111
110
100
101Y Z
Cubo 1X
0 1
Cubo 2
Circuitos Digitais CIC - UnB
Visualização de CubosVisualização de Cubos
Cubo 3
XYZ
X
011
010
000
001
111
110
100
101Y Z• Pontos adjacentes diferem em 1 bit• Todos os pontos da função estão dispostos sobre uma face• Y e Z variam enquanto X permanece inalterado: Y e Z podem ser eliminados da expressão
F(X, Y, Z) = ∑(4,5,6,7) = XF(X, Y, Z) = ∑(4,5,6,7) = X
Circuitos Digitais CIC - UnB
Mapas de KarnaughMapas de Karnaugh
• Visualização do domínio de uma função na forma matricial
• Pontos do domínio estão dispostos seguindo o código Gray, pares adjacentes diferem em 1 bit
AB 0 1
0
1
0
1
2
3
0
1
2
3
6
7
4
5
ABC
0
1
3
2
4
5
7
6
12
13
15
14
8
9
11
10
A
B
AB
CD
A
00 01 11 10
0
1
00 01 11 00
00
01
11
10C
B
D
Circuitos Digitais CIC - UnB
Adjacências no Mapa de KarnaughAdjacências no Mapa de Karnaugh
000
001
010
011
110
111
100
101
00 01 11 10
0
1
ABC
A
B
011
010
000
001
100
110
101
111
B
C
A
• Os elementos nas extremidades das linhas e colunas são também adjacentes
Circuitos Digitais CIC - UnB
Adjacências no Mapa de KarnaughAdjacências no Mapa de Karnaugh
• O cubo obtido é definido pelas variáveis que não mudam de fase ao longo de seus mintermos
A
B 0 1
0 1
0 1
0
1
A
B 0 1
1 1
0 0
0
1
B é eliminadoA permanece
A é eliminadoB’ permanece
F = ?F = ?
F = ?F = ?
ABC
A
00 01 11 10
0
1
0
0
0
0
1
1
1
1
B
F = ?F = ?
Circuitos Digitais CIC - UnB
Adjacências no Mapa de KarnaughAdjacências no Mapa de Karnaugh
• O cubo obtido é definido pelas variáveis que não mudam de fase ao longo de seus mintermos
A
B 0 1
0 1
0 1
0
1
A
B 0 1
1 1
0 0
0
1
B é eliminadoA permanece
A é eliminadoB’ permanece
F = A B’ AB = AF = A B’ AB = A
F = A’ B’ AB’ = B’F = A’ B’ AB’ = B’
ABC
A
00 01 11 10
0
1
0
0
0
0
1
1
1
1
B
F = A B C’ A B C AB’C A B’ C’ = A(B(C C’) B’(C C’)) = A
F = A B C’ A B C AB’C A B’ C’ = A(B(C C’) B’(C C’)) = A
Circuitos Digitais CIC - UnB
Adjacências no Mapa-KAdjacências no Mapa-K
00C
AB01 11 10
1001
1100
A
B
0
1•Adjacência nas extremidades das linhas
00C
AB01 11 10
0101
1 10 0
A
B
0
1•Adjacência nas extremidades das colunas
Circuitos Digitais CIC - UnB
Complemento de uma FunçãoComplemento de uma Função
00C
AB01 11 10
1001
1100
A
B
0
1
00C
AB
01 11 10
0110
0011
A
B
0
1
F = ? F = ?
F’ = ?F’ = ?
Trocar 0’s por 1’s
Circuitos Digitais CIC - UnB
Complemento de uma FunçãoComplemento de uma Função
00C
AB01 11 10
1001
1100
A
B
0
1
00C
AB
01 11 10
0110
0011
A
B
0
1
F = A C B’ C’ F = A C B’ C’
F’ = A’ C B C’ F’ = A’ C B C’
Trocar 0’s por 1’s
Circuitos Digitais CIC - UnB
Karnaugh de 4 variáveisKarnaugh de 4 variáveis
AB00 01 11 10
1 0 0 1
0 1 0 0
1 1 1 1
1 1 1 1
00
01
11
10C
CD
A
D
B
F = ?F = ?
Circuitos Digitais CIC - UnB
Karnaugh de 4 variáveisKarnaugh de 4 variáveis
F = C + A' B D + B' D'F = C + A' B D + B' D'
AB00 01 11 10
1 0 0 1
0 1 0 0
1 1 1 1
1 1 1 1
00
01
11
10C
CD
A
D
B
Circuitos Digitais CIC - UnB
Minimização com IrrelevânciasMinimização com Irrelevâncias
• Os pontos irrelevantes podem ser considerados como 1 ou 0 no mapa de Karnaugh
• São utilizados para formar cubos maiores, simplificando a função
00C
AB01 11 10
1x01
x1x0
A
B
0
1
Os pontos irrelevantes deste cuboestão sendo computados como 1’s
Este ponto irrelevante é considerado como 0
Circuitos Digitais CIC - UnB
Exemplo: comparador de 2 bitsExemplo: comparador de 2 bits
F11000010000100001
F20111001100010000
F30000100011001110
D0101010101010101
C0011001100110011
B0
1
0
1
A0
0
1
1
=, >, <F1 A B = C DF2 A B < C DF3 A B > C D
AB
CD
N1
N2
• 3 funções de 4 variáveis• 3 mapas de Karnaugh• 3 funções de 4 variáveis• 3 mapas de Karnaugh
© R.H. Katz
Circuitos Digitais CIC - UnB
Exemplo: comparador de 2 bitsExemplo: comparador de 2 bits
AB00 01 11 10
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
00
01
11
10C
CD
A
D
B
K-map for F1
AB00 01 11 10
0 0 0 0
1 0 0 0
1 1 0 1
1 1 0 0
00
01
11
10C
CD
A
D
B
K-map for F2
AB00 01 11 10
0 1 1 1
0 0 1 1
0 0 0 0
0 0 1 0
00
01
11
10C
CD
A
D
B
K-map for F3
F1 = ?
F2 = ?
F3 = ?
F1 = ?
F2 = ?
F3 = ?
© R.H. Katz
Circuitos Digitais CIC - UnB
Exemplo: comparador de 2 bitsExemplo: comparador de 2 bits
F1 = A' B' C' D' + A' B C' D + A B C D + A B' C D'
F2 = A' B' D + A' C
F3 = B C' D' + A C' + A B D'
A xnor B xnor C xnor D
AB00 01 11 10
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
00
01
11
10C
CD
A
D
B
K-map for F1
AB00 01 11 10
0 0 0 0
1 0 0 0
1 1 0 1
1 1 0 0
00
01
11
10C
CD
A
D
B
K-map for F2
AB00 01 11 10
0 1 1 1
0 0 1 1
0 0 0 0
0 0 1 0
00
01
11
10C
CD
A
D
B
K-map for F3
© R.H. Katz
Recommended