Circuitos lógicos combinatórios

Sumário






Álgebra de Boole
Mapas de Karnaugh
Projecto de circuitos combinatórios
Tempos de propagação
Descodificadores e multiplexers
Circuitos aritméticos
1
Álgebra de Boole
2
Lógica Binária

Como já foi visto anteriormente, existem
dois valores lógicos



0 (Falso)
1 (Verdadeiro)
Definem-se 3 operações básicas



Conjunção – “E”, “AND”, representada por ‘.’
Disjunção – “OU”, “OR”, representada por ‘+’
Negação – “NÃO”, “NOT”, representada pela
barra horizontal sobre a variável ou por ‘~’
3
Lógica Binária

Tabelas de verdade
AND
X
Y
F
0
0
1
0
1
0
0
0
0
1
1
1
F=X.Y
X
0
0
1
1
OR
Y
0
1
0
1
F
0
1
1
1
F=X+Y
NOT
X
F
0
1
1
0
F=X
4
Portas Lógicas

Cada operação lógica tem um circuito eléctrico
correspondente
AND
X
Y

OR
F
X
Y
NOT
F
X
F
Estes componentes designam-se por
portas lógicas (logic gates)
5
Portas Lógicas

Evolução temporal
X
Y
0
0
0
1
1
0
t
X
Y
F
X.Y
0
0
0
1
X
Y
F
X+Y
0
1
1
1
X
F
X
1
1
0
0
1
1
Na realidade existe um atraso temporal entre variações
à entrada e consequente variação na saída
6
Álgebra de Boole

Representação de funções lógicas por
equações


Exemplo: F X  YZ
A partir da função lógica obtém-se:


Tabela de verdade – Valores lógicos da
função para todas as combinações de
entradas
Diagrama do circuito – Esquema do circuito
com as portas lógicas e respectivas ligações
7
Álgebra de Boole

Tabela de verdade
F X  YZ
X
Y
Z
F
0
0
0
1
0
0
1
1
0
1
0
1
0
1
1
1
1
0
0
0
1
0
1
0
1
1
0
0
1
1
1
1
8
Álgebra de Boole

Diagrama do circuito
F X  YZ
X
Y
Z
F
9
Álgebra de Boole

Propriedades

AND







X.1=X
X.0=0
X.X=X
X.X=0
X.Y=Y.X
X(YZ) = (XY)Z
X+(YZ) = (X+Y).(X+Z)
(elemento neutro)
(elemento absorvente)
(comutativa)
(associativa)
(distributiva)
10
Álgebra de Boole

Propriedades

OR







X+0 = X
X+1 = 1
X+X = X
X+X = 1
X+Y = Y+X
X+(Y+Z) = (X+Y)+Z
X.(Y+Z) = (XY) + (XZ)
(elemento neutro)
(elemento absorvente)
(comutativa)
(associativa)
(distributiva)
11
Álgebra de Boole

NOT
XX

Leis de DeMorgan
X  Y  X.Y
X.Y  X  Y

Teorema do consenso
XY  XZ  YZ  XY  XZ
(X  Y)(X  Z)(Y  Z)  (X  Y)(X  Z)
12
Álgebra de Boole

Aplicação das propriedades

Simplificação de equações

Exemplo
F  XY Z  XYZ  X
 XY(Z  Z)  X
 XY 1  X
 XY  X
 XY  X 1
 X(Y 1)
 X 1
X
13
Termos Mínimos

A partir de uma tabela de verdade pode-se escrever uma
função como uma soma de produtos lógicos

Cada produto lógico que assume o valor 1 para uma
dada combinação de variáveis de entrada designa-se
Termo produto

Um produto lógico em que todas as variáveis de entrada
aparecem exactamente uma vez (complementadas ou
não) designa-se Termo mínimo
14
Termos Mínimos
X
Y Z
0
0
Termo mínimo
Símbolo
0
XYZ
m0
0
0 1
XYZ
m1
0
0
1
1
1
1 0
1 1
0 0
0 1
1 0
X
X
X
X
X
YZ
YZ
YZ
YZ
YZ
m2
m3
m4
m5
m6
1
1
XYZ
m7
1
15
Termos Mínimos

Uma função pode ser definida como uma
soma de termos mínimos

Exemplo
F   m2 , m3 , m4 , m7 
Será o mesmo que
F XYZ  XYZ  XYZ  XYZ
16
Mapas de Karnaugh

Ferramenta útil para simplificação de funções e
projecto de circuitos

Geralmente utilizados quando se pretende obter
uma função lógica a partir da tabela de verdade

Representam-se no mapa os termos mínimos da
função (com valor 1 ou 0)

Obtém-se as funções lógicas através do
agrupamento de termos mínimos com valor ‘1’
17
Mapas de Karnaugh

Os termos mínimos são organizados de modo a que
apenas mude um bit entre quadrados adjacentes (código
binário reflectido)
XY
YZ

Podem-se agrupar termos mínimos em que a função
assume o valor lógico 1. Deste modo simplifica-se a
função lógica
18
Mapas de Karnaugh

Exemplos de associação de termos
mínimos
19
Mapas de Karnaugh

Exemplo de simplificação de função
F  ( X  Y)  Z  X
X Y Z
F
0
0
0
0
1
1
1
1
1
1
1
1
1
0
1
0
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
X
X
YZ
00 01 11 10
0 1 1 1 1
1 1
0
0
1
Z
A função simplifica-se para
FXZ
20
Mapas de Karnaugh

Exemplo de obtenção dos termos produto
ZW
XY
00 01 11 10
00 1 0 1 1
01 0
0
1
1
11 0
1
1
1
10 1
0
1
1
YW
Z
XYW
F  XYW  YW  Z
21
Mapas de Karnaugh

Implicantes

Designa-se implicante de uma função a
qualquer termo produto que assume o valor
lógico 1 para todos os termos mínimos que o
compõem

Se a simplificação de uma variável num
implicante o transformar num termo produto
não implicante, então esse implicante é um
implicante primo
22
Mapas de Karnaugh

Exemplos de implicantes e implicantes
primos
YZ
X
00 01 11 10
0 1 0 1 1
1


0
0
1
1
Implicantes: Y; XZ; XY; YZ; XY; X Y Z; etc.
Implicantes primos: Y; XZ
23
Mapas de Karnaugh

Implicantes primos

Se um termo mínimo estiver incluído apenas
num implicante primo então esse implicante
primo é essencial

Os implicantes primos a que a condição
anterior não se aplica são implicantes primos
não-essenciais
24
Mapas de Karnaugh

Exemplos de implicantes primos
essenciais e não essenciais
ZW
XY
00 01 11 10
00 0 0 1 1
01 0
0
1
1
11 1
1
1
0
Implicantes primos essenciais
10 0
0
0
0
Implicantes primos não-essenciais
25
Mapas de Karnaugh

Quando uma determinada combinação de variáveis
nunca ocorre é possível definir a função como não
totalmente especificada
X
1
1
X
1
X
1
1

Os termos mínimos não especificados podem ser
agrupados ao não, consoante dê mais jeito
26
Circuitos Combinatórios

Definição

Um circuito lógico diz-se combinatório se, em cada
instante temporal, os valores das saídas dependem
apenas dos valores das entradas
n
entradas
CircuitoCombinatório
m
saídas
27
Procedimentos de Projecto
1. Determinar o nº de entradas, o nº de saídas e
atribuir-lhes designações
2. Escrever a tabela de verdade que relaciona as
entradas com as saídas
3. Obter funções simplificadas para cada saída

Mapas de Karnaugh, álgebra de Boole
4. Desenhar o esquema do circuito
5. Verificar o funcionamento do circuito
28
Ferramentas de Projecto

Ferramentas de CAD
(Computer Aided Design)
 Bibliotecas de funções e símbolos
 Ferramentas de síntese




Tabelas de verdade
Linguagens de descrição de hardware (e.g. VHDL)
Editores esquemáticos
Simulação



Nível funcional
Nível lógico
Nível eléctrico
29
Circuitos Lógicos Combinatórios
30
Portas Lógicas

Portas lógicas estudadas



AND
OR
X
Y
F
X
Y
F
NOT (Inverter)
X
F
31
Portas Lógicas

Outras portas lógicas

NAND
X
Y

X
Y
F
F  XY
NOR
F
FXY
X Y
F
0
0
1
1
0
1
0
1
1
1
1
0
X Y
F
0
0
1
1
1
0
0
0
0
1
0
1
32
Portas Lógicas
XOR
X Y
F
X
Y
0
0
1
1
0
1
0
1
0
1
1
0
X Y
F
0
0
1
1
1
0
0
1


F
XNOR
X
Y

F  X  Y  X Y  X Y
F
F  X  Y  X Y  X Y
Buffer
X
F
FX
0
1
0
1
X
F
0
1
0
1
33
Portas Lógicas

Qualquer circuito pode ser realizado utilizando
apenas portas NAND ou apenas portas NOR
X
F
X
F
X
Y
F
X
Y
F
X
Y
X
F
F
Y
34
Portas Lógicas

Exemplo:
F X YZ
Circuito directo
Circuito com NANDs
X
X
F
Y
Z
F
Y
Z
Algebricamente:
F X Y.Z X Y.Z X.Y.Z X.Y.Z
35
Tempos de Propagação

Idealmente, as portas lógicas respondem
instantaneamente a variações na entrada...
X
F
X
F
t
36
Tempos de Propagação

...mas, na realidade:


os sinais de entrada não são ondas perfeitas
as portas lógicas respondem com um atraso temporal
X
F
tpLH
tpHL
t
37
Tempos de Propagação

tpLH – Tempo de propagação LOW->HIGH


tpHL – Tempo de propagação HIGH->LOW


Tempo que a saída demora a subir após uma
variação na entrada que cause a subida
Tempo que a saída demora a descer após
uma variação na entrada que cause a descida
tpd – Tempo de propagação

tpd = Max(tpLH, tpH)
38
Tempos de Propagação

Num dado circuito, muitas vezes interessa saber
qual o pior caso de propagação


Worst-case propagation delay – impõe restrições
temporais à velocidade com que operam os circuitos
Ao pior caso de propagação, corresponde um
dado caminho do circuito – caminho crítico.

Normalmente é o caminho que atravessa mais portas
lógicas (isto se os atrasos das portas forem idênticos)
39
Tempos de Propagação

Exemplo:
Qual será o pior caso de propagação no seguinte circuito ?
Indique uma situação que ilustre o pior caso.
A
B
F
C
AND e OR: tpd = 10ns
NOT: tpd = 7ns
(Suponha tpd = tpLH = tpHL em todas as portas)
40
Tempos de Propagação

Exemplo:
Caminho crítico
A
B
F
C
Exemplo de uma situação:
passagem de A=1, B=1, C=0 -> F=0
para A=1, B=0, C=0 -> F=1 (mudou-se o sinal de B)
Tpd(Total) = tpd(NOT)+tpd(AND)+tpd(OR) = 27ns
41
Tempos de Propagação

Podem também ocorrer de picos na saída...

Exemplo:
A
F
Caso ideal
Caso real
A
A
A
A
F
F
t
tpd(NOT)
tpd(AND)
t
42
Tecnologias

Densidade de integração

SSI (Single Scale Integration)


MSI (Medium Scale Integration)



10-100 portas / CI
Ex: Circuitos aritméticos, registos, contadores
LSI (Large Scale Integration)



<10 portas lógicas por circuito integrado
100-10000 portas / CI
Microprocessadores simples, memórias pequenas, controladores
VLSI (Very Large Scale Integration)


10000 a mais de 100 Milhões de portas / CI
Processadores complexos (Pentium, Xeon, etc.)
43
Tecnologias

Principais características

Fan-in


Fan-out


Gamas de tensão correctamente interpretadas
Potência dissipada


Número de portas que se podem ligar à saída
Margem de ruído


Número de entradas
Aquecimento dos circuitos
Tempos de propagação

tpHL e tpLH
44
Tecnologias

Principais famílias lógicas

TTL (transistor-transistor logic)


ECL (emitter-coupled logic)


Baixo consumo de energia; muito utilizados actualmente
BiCMOS (bipolar complementary metal-oxide semicondutor)


Permitem uma grande densidade de integração
CMOS (complementary metal-oxide semicondutor)


Mais rápidos que TTL; dissipam muita potência
MOS (metal-oxide semiconductor)


Rápidos; dissipam muita potência; actualmente em declínio
Combinação TTL e CMOS (mais rápido que apenas CMOS)
GaAs (arseneto de gálio)

A família mais rápida, mas também a mais cara
45
Exemplos de Circuitos
Combinatórios
46
Exemplos de Projecto

Adicionador de 2 bits (Half-adder)
Pretende-se projectar um circuito que realize a adição
de 2 bits. À saída deverão ser apresentados o
resultado da adição e o bit de transporte.
Entradas:
X e Y – Bits a adicionar
Saídas:
S – Resultado da adição
C – Transporte (Carry)
47
Exemplos de Projecto

Adicionador de 2 bits (Half-adder)
Tabela de Verdade
X
Y
S
Mapas de Karnaugh
Função S
C
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1
X
Y
0
1
0
0
1
1
1
0
S  XY  XY
 XY
Função C
X
Y
0
1
0
0
0
1
0
1
C  XY
48
Exemplos de Projecto

Adicionador de 2 bits (Half-adder)
Circuito resultante
X
Y
S
C
49
Exemplos de Projecto

Adicionador de 2 bits completo (Full Adder)
Com base no circuito anterior pode ser obtido um circuito,
designado Full Adder, que adiciona dois bits (X e Y) ao bit de
transporte de uma soma anterior (Cin).
Half-adder
X
Y
Half-adder
S
Cin
Cout
50
Exemplos de Projecto

Descodificador BCD-Display 7 segmentos
Pretende-se projectar um circuito que descodifique um número
representado em código BCD (números de 0 a 9, representados
em binário), gerando à sua saída um conjunto de sinais que
permitem apresentar o número num display de 7 segmentos.
a
Número
(BCD)
f
Descodificador
b
g
e
c
d
Display de 7 segmentos
51
Exemplos de Projecto

Descodificador BCD-Display 7 segmentos
Tabela de verdade
B3 B2 B1 B0
a
b
c
d
e
f
g
0
0
0 0
1
1
1
1
1
1
0
0
0
0 1
0
1
1
0
0
0
0
0
0
0
0
1 0
1 1
1
1
1
1
0
1
1
1
1
0
0
0
1
1
0
1
0 0
0
1
1
0
0
1
1
0
1
0 1
1
0
1
1
0
1
1
0
0
1
1
1 0
1 1
1
1
0
1
1
1
1
0
1
0
1
0
1
0
1
0
0 0
1
1
1
1
1
1
1
1
0
1
0
1
0
1
0
0
0
1
0
1
0
1 0 0 1
Restantes casos
52
Exemplos de Projecto

Descodificador BCD-Display 7 segmentos
Mapas de Karnaugh
a
b
B1B0
B3B2
00 01 11 10
B1B0
B3B2
00 01 11 10
00 1
0
1
1
00 1
1
1
1
01 0
1
1
1
01 1
0
1
0
11 0
0
0
0
11 0
0
0
0
10 1
1
0
0
10 1
1
0
0
a  B B  B B B  B B B B B B
3 1 3 2 0 3 2 0 3 2 1
bB B B B B B B B B B
3 2 3 1 0 3 1 0 2 1
53
Circuitos Combinatórios Típicos
54
Descodificadores

Circuito com n entradas e 2n saídas. Apenas uma saída
virá com valor lógico diferente de todas as outras.

Exemplo: descodificador 3-para-8 (ou 1 de 8)
Entradas
A2 A1 A0
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
D 7 D6 D 5
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 1
0 1 0
1 0 0
Saídas
D4 D 3 D 2 D 1 D0
0 0 0 0 1
0 0 0 1 0
0 0 1 0 0
0 1 0 0 0
1 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
55
Descodificadores
Esquema interno:
Símbolo:
A0
3/8
D0
A1
D1
A2
D2
D3
D4
D5
D6
D7
56
Codificadores

Circuito com 2n entradas e n saídas que realiza a
operação inversa de um descodificador.

Exemplo: Codificador 4-para-2
D0
D3
0
0
0
1
Entradas
D2 D1 D0
0 0 1
0 1 0
1 0 0
0 0 0
A0 = D1+D3
Saídas
A1 A0
0 0
0 1
1 0
1 1
A1 = D2+D3
8/3
A0
D1
A1
D2
A2
D3
D4
D5
D6
D7
57
Multiplexers

Circuito combinatório cuja saída é igual a uma de m=2n
entradas, seleccionada por n linhas de controlo.

Exemplo: Multiplexer 4-para-1




4 Entradas – D0 a D3
1 Saída – Y
2 Linhas de controlo – S1 e S0
S1 S0
0 0
0 1
1 0
1 1
Y
D0
D1
D2
D3
A saída Y corresponde a uma das entradas Dm, dependendo das
linhas de controlo Sn
58
Multiplexers
Esquema interno:
Símbolo:
S0
S0
MUX 4-1
S1
S1
D0
D1
D2
D0
Y
D3
D1
Y
D2
D3
59
Desmultiplexers

Circuito que realiza a operação inversa de um
multiplexer. Direcciona a entrada para uma de 2n linhas
de saída, seleccionada por n linhas de controlo

Exemplo: Desmultiplexer 1-para-4 linhas



1 Entrada – A
4 Linhas de saída – D0 a D3
2 Linhas de controlo – S0 e S1
S1 S0
0 0
0 1
1 0
1 1
D3 D2 D1 D0
0 0 0 A
0 0 A 0
0 A 0 0
A 0 0 0
60
Desmultiplexers
Esquema interno:
Símbolo:
S0
S0
S1
DX 1-4
S1
D0
D1
D0
A
D1
D2
D3
D2
A
D3
61
Adição Binária

Adicionador de 4 bits
Relembrando a aula passada...
Half-adder
X
Y
Half-adder
S
Cin
Cout
62
Adição Binária

Adicionador de 4 bits
... é possível obter um circuito que adiciona 4 bits,
utilizando Full Adders e propagando o bit de transporte
A3
C4
B3
FA
S3
A2
C3
B2
FA
S2
A1
C2
B1
FA
S1
A0
C1
B0
FA
C0
S0
Este circuito designa-se por Ripple Carry Adder
63
Subtracção Binária

Complemento para 2




Permite uma representação coerente de números
negativos em base 2
Bit de maior peso  Bit de sinal
O complemento para 2 obtém-se complementando o
número e adicionando 1
Exemplos
 5 = 0101
 -5 = 1010 + 1 = 1011

3 = 0011

-3 = 1100 + 1 = 1101
64
Subtracção Binária

Complemento para 2

Números inteiros no intervalo [-8;7]
Complemento
Decimal
para 2
Complemento
Decimal
para 2
7
0111
-1
1111
6
5
0110
0101
-2
-3
1110
1101
4
0100
-4
1100
3
0011
-5
1011
2
1
0010
0001
-6
-7
1010
1001
0
0000
-8
1000
65
Subtracção Binária

Complemento para 2


Subtrair um número inteiro é o mesmo que
somar o seu complemento para 2
Exemplos
11000
0100
+ 1110
10010
4
-2
11000
1101
+ 1100
-3
-4
2
11001
-7
66
Subtracção Binária

Circuito que complementa (ou não) um número de
4 bits, em função de S (selecção de operação)
B3
B2
B1
B0
S


S=0 – não complementa B (para somar)
S=1 – complementa B (para subtrair)
67
Subtracção Binária

Adicionador / subtractor de 4 bits
A3
B3
A2
B2
A1
B1
A0
B0
S
FA
FA
FA
FA
Cin
Cout
S3
S2
S1
S0
68
Overflow

Resultado de uma adição/subtracção fora
do intervalo de operação  overflow

Exemplo (4 bits):


Intervalo de operação: [-8;7]
Operações em que ocorre overflow


6+3
-3-7, etc.
69
Overflow

Detecção de overflow

A ocorrência de overflow pode ser detectada
analisando os 2 últimos carrys
V
Cn-1
Adicionador /
Subtractor
de n bits

Cn
A saída V indica se há ou não overflow
70