Arquitectura de Computadores I
Análise e Concepção de Circuito Combinacionais
António M. Gonçalves Pinheiro
Departamento de Fı́sica
Universidade da Beira Interior
Covilhã - Portugal
[email protected]
Arquitectura de Computadores I
Concepção de Sistemas Combinacionais
Sistema de controlo de Limpa Para-brisas
Pretende-se projectar um sistema digital de controlo para um Limpa Para-brisas de um automóvel.
Considere que o sistema tem disponı́vel as variáveis digitais:
• C1, C0 - Comutador que sinaliza a programação do
limpa para-brisas (ver tabela ao lado).
• I - que sinaliza (=1) que a ignição do carro está
ligada.
• S - sensor de chuva (=1) presente no vidro
para-brisas.
Pretende-se que o sistema controle o modo de funcionamento do limpa para-brisas segundo a tabela ao lado
C1
0
0
1
1
C0 Velocidade Pretendida
0
Parado
1
Automático
0
Intermitente
1
Permanente
MF1 MF0 Modo de Funcionamento
0
0
Parado
1
Intermitente
0
1
0
Permanente
Considere que quando o Comutador está em Automático o modo de funcionamento do limpa
para-brisas deve ser “permanente”, caso seja detectada chuva.
Desenhe um circuito lógico que gere MF1 e MF0.
Universidade da Beira Interior
Arquitectura de Computadores I
Concepção de Sistemas Combinacionais
Resolução
Variáveis Independentes
(Entrada)
C1, C0 - Comutador
C1 C0
0 0
Parado
0 1 Automático
1 0 Intermitente
1 1 Permanente
S - Sensor
I - Ignição
Variáveis Dependentes
(Saı́da)
MF1, MF0 - Modo de Funcionamento
MF1 MF0
0
0
Parado
0
1 Intermitente
1
0
Permanente
I
S
C
1
C
0
Sistema
Combinacional
M
1
M
0
Tabela de Verdade
I S C1 C0 MF1 MF0
0 0 0 0 0
0
0
1 0 0 0 1
0
0
2 0 0 1 0
0
0
3 0 0 1 1
0
0
4 0 1 0 0
0
0
5 0 1 0 1
0
0
6 0 1 1 0
0
0
7 0 1 1 1
0
0
8 1 0 0 0
0
0
9 1 0 0 1
0
0
10 1 0 1 0
0
1
11 1 0 1 1
1
0
12 1 1 0 0
0
0
13 1 1 0 1
1
0
14 1 1 1 0
0
1
15 1 1 1 1
1
0
Universidade da Beira Interior
Arquitectura de Computadores I
Concepção de Sistemas Combinacionais
Resolução
Tabela de Verdade
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
I
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
S
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
C1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
C0 MF1 MF0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
1
1
1
0
0
0
0
1
1
0
0
0
1
1
1
0
MF1, MF0 - Modo de Funcionamento
MF0 = I · S · C1 · C0 + I · S · C1 · C0
MF1 = I · S · C1 · C0 + I · S · C1 · C0 + I · S · C1 · C0
Nota Teórica
Primeira Fórmula Canónica da Algebra de Boole
f=
n−1
2X
fi · mi
i=0
I · S · C1 · C0
I · S · C1 · C0
I · S · C1 · C0
I · S · C1 · C0
I · S · C1 · C0
• fi - valor da função f na linha i da tabela de verdade.
• mi - mintermo de ordem i (função lógica que só é 1
na linha i da tabela de verdade).
• n - número de variáveis lógicas independentes.
Exemplo: MF0= m10 + m14;
Universidade da Beira Interior
MF1= m11 + m13 + m15
Arquitectura de Computadores I
Concepção de Sistemas Combinacionais
Resolução
Tabela de Verdade
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
I
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
S
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
C1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
C0 MF1 MF0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
1
1
1
0
0
0
0
1
1
0
0
0
1
1
1
0
MF1, MF0 - Modo de Funcionamento
MF0 = I · S · C1 · C0 + I · S · C1 · C0
MF0 = I · C1 · C0 · (S + S)
MF0 = I · C1 · C0
MF1 = I · S · C1 · C0 + I · S · C1 · C0 + I · S · C1 · C0
MF1 = I · S · C1 · C0 + I · S · C1 · C0 +
I · S · C1 · C0 + I · S · C1 · C0
MF1 = I · C1 · C0 · (S+S) + I · S · C0 · (C1 + C1)
MF1 = I · C1 · C0 + I · S · C0
I · S · C1 · C0
I · S · C1 · C0
I · S · C1 · C0
I · S · C1 · C0
I · S · C1 · C0
⇓
MAPAS DE KARNAUGH
Universidade da Beira Interior
Arquitectura de Computadores I
Concepção de Sistemas Combinacionais
Resolução
Tabela de Verdade
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
I
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
S
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
C1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
C0 MF1 MF0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
1
1
1
0
0
0
0
1
1
0
0
0
1
1
1
0
MF1, MF0 - Modo de Funcionamento
MF0 = I · C1 · C0
MF1 = I · C1 · C0 + I · S · C0
I S C C
1
0
M
0
M
1
Universidade da Beira Interior
Arquitectura de Computadores I
Mapas de Karnaugh
Mapa de Karnaugh
Representa a tabela de verdade de forma a que as simplificações fiquem adjacentes, e como tal,
sejam facilmente identificáveis.
Nota: Códigos de Gray ou Refletidos
Estes códigos têm a particularidadede de que
entre duas linhas consecutivas, só muda o
valor de um bit.
Nota: Nas simplificações efectuadas no exemplo anterior só existe também a alteração de
um bit.
10
11
12
13
14
15
I
1
1
1
1
1
1
S
0
0
1
1
1
1
C1
1
1
0
0
1
1
0
1
1
0
00
01
11
10
00
01
11
10
10
11
01
00
000
001
011
010
110
111
101
100
C0 MF0
0
1 I · S · C1 · C0
1
0
0
0
1
0
0
1 I · S · C1 · C0
1
0
MF0 = I · S · C1 · C0 + I · S · C1 · C0
MF0 = I · C1 · C0
Universidade da Beira Interior
000
001
011
010
110
111
101
100
100
101
111
110
010
011
001
000
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000
Arquitectura de Computadores I
Mapas de Karnaugh
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
A
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
B
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
C
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
D
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
F
f0
f1
f2
f3
f4
f5
f6
f7
f8
f9
f10
f11
f12
f13
f14
f15
0
0
1
1
0 0 1
0 1 1
0 f0
f7
1
1
0
1 C
0 D
f 14
f 10
A B
Universidade da Beira Interior
Arquitectura de Computadores I
Mapas de Karnaugh
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
A
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
B
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
C
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
D
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
F
f0
f1
f2
f3
f4
f5
f6
f7
f8
f9
f10
f11
f12
f13
f14
f15
0
0
1
1
0
1
1
0
0
0
f0
f4
f 12
f8
0
1
f1
f5
f 13
f9
1
1
f3
f7
f 15
f 11
1 C
0 D
f2
f6
f 14
f 10
A B
Simplificação Simbólica
D
B
f0
f4
f 12
f8
f1
f5
f 13
f9
f3
f7
f 15
f 11
f2
f6
f 14
A
f 10
C
Universidade da Beira Interior
Arquitectura de Computadores I
Mapas de Karnaugh
Exemplo do controlo do limpa para-brisas
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
I
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
S
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
C1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
C0 MF1 MF0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
1
1
1
0
0
0
0
1
1
0
0
0
1
1
1
0
C0
M0
S
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
I
C1
MF0 = I · S · C1 · C0 + I · S · C1 · C0
MF0 = I · C1 · C0 · (S + S)
MF0 = I · C1 · C0
Universidade da Beira Interior
Arquitectura de Computadores I
Mapas de Karnaugh
Exemplo do controlo do limpa para-brisas
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
I
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
S
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
C1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
C0 MF1 MF0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
1
1
1
0
0
0
0
1
1
0
0
0
1
1
1
0
C0
M1
S
0
0
0
0
0
0
1
0
0
0
1
1
0
0
0
0
I
C1
MF1 = I · S · C1 · C0 + I · S · C1 · C0 + I · S · C1 · C0
MF1 = I · S · C1 · C0 + I · S · C1 · C0 +
I · S · C1 · C0 + I · S · C1 · C0
MF1 = I · C1 · C0 · (S+S) + I · S · C0 · (C1 + C1)
MF1 = I · C1 · C0 + I · S · C0
Universidade da Beira Interior
Arquitectura de Computadores I
Mapas de Karnaugh
Exemplo da Condição de Matrı́cula
F
0
1
2
3
4
5
6
7
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
F
0
1
0
0
0
1
1
1
C
0 1 0 0
A 0 1 1 1
B
F=A· B· C + A· B·C + A·B·C + A·B·C
F=( A·B + B·C) + A·C
F=( A·B + B·C)
Universidade da Beira Interior
Arquitectura de Computadores I
Mapas de Karnaugh
Mapas de Karnaugh para diferente número de variáveis independentes
0 f0 f1
1 f2 f3
0
F 0
0 f0
1 f4
A
A
F 0 1 B
0
1
f1
f5
1
1
f3
f7
1 B
0 C
f2
f6
F
0
0
1
1
0
1
1
0
0
0
f0
f4
f12
f8
0
1
f1
f5
f13
f9
1
1
f3
f7
f15
f11
1 C
0 D
f2
f6
f14
f10
A B
F
B
f0 f1
A f2 f3
F
C
B
B
0
0
1
1
0
1
1
0
0
0
1
f1
f9
f25
f17
0
1
1
f3
f11
f27
f19
0
1
0
f2
f10
f26
f18
1
1
0
f6
f14
f30
f22
1
1
1
f7
f15
f31
f23
1
0
1
f5
f13
f29
f21
1 C
0 D
0 E
f4
f12
f28
f20
A B
D
F
f0 f1 f3 f2
A f4 f5 f7 f6
F
0
0
0
f0
f8
f24
f16
f0
f4
f12
f8
f1
f5
f13
f9
f3
f7
f15
f11
f2
f6
f14
A
f10
B
E
E
F
f0
f8
f24
f16
f1
f9
f25
f17
C
f3
f11
f27
f19
f2
f10
f26
f18
f6
f14
f30
f22
f7
f15
f31
f23
f5
f13
f29
f21
D
C
Universidade da Beira Interior
f4
f12
f28
A
f20
Arquitectura de Computadores I
Mapas de Karnaugh
Técnica de preenchimento dos Mapas de Karnaugh
F
C
D
F
f0 f1 f3 f2
A f4 f5 f7 f6
B
B
f0
f4
f12
f8
f1
f5
f13
f9
f3
f7
f15
f11
f2
f6
f14
A
f10
C
B
E
E
F
f0
f8
f24
f16
f1
f9
f25
f17
f3
f11
f27
f19
f2
f10
f26
f18
f6
f14
f30
f22
f7
f15
f31
f23
f5
f13
f29
f21
D
C
Universidade da Beira Interior
f4
f12
f28
A
f20
Arquitectura de Computadores I
Mapas de Karnaugh
Tipos de Agrupamentos
D
F
B
1
0
0
1
0
1
1
0
0
1
1
0
0
0
0
0
A
C
F=B C D + (BCD+BCD)
F=B C D + BD
Agrupamentos em Mapas de 5 Variáveis
• Fazer os agrupamentos de cada lado da linha
de simetria como se fazem num mapa de 4
variáveis.
• Sempre que possı́vel para cada agrupamento
juntar o agrupamento simétrico.
B
E
E
F
1
0
0
1
0
1
1
0
0
1
1
0
0
0
0
0
1
0
0
0
0
1
1
0
0
1
1
1
1
0
1
1
D
Simetria
C
Simetria
F=(B C E + B C E) +
(B C D E + B C D E) +
ACD+ABCE
F= BE + B D E + A C D +
+ABCE
Universidade da Beira Interior
A
Arquitectura de Computadores I
Mapas de Karnaugh
Tipos de Agrupamentos (continuação)
Dimensão de cada agrupamento
• Podem-se fazer agrupamentos de 1, 2, 4, 8, 16...
(Potências de 2)
• Os agrupamentos resultam sempre por agrupamento de
dois agrupamentos com metade da dimensão.
B
E
E
F
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
0
0
0
0
1
1
0
0
1
1
0
D
1
1
1
1
B
A
E
E
F
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
1
0
0
0
0
0
D
C
F= B C + B E + C D E
C
F= C + A B D E
Universidade da Beira Interior
0
0
0
0
A