3 - minimização de circuitos lógicos

Prévia do material em texto

SISTEMAS LÓGICOS
Universidade Federal da Bahia
Escola Politécnica
CURSO DE ENGENHARIA ELÉTRICA
PROF. EDSON PINTO SANTANA
edsonps@ufba.br
Sistemas Lógicos 2
SUMÁRIO
3. MINIMIZAÇÃO DE CIRCUITOS LÓGICOS
3.1. Introdução
3.2. Mapas de Karnaugh
3.3. Método de Quine-Mccluskey
Sistemas Lógicos 3
3.1. Introdução
● Redes de dois níveis: funções expressas em SOP (AND/OR) ou 
POS (OR/AND) e disponibilidade de variáveis complementadas.
Sistemas Lógicos 4
3.1. Introdução
● Redes do tipo AND/OR (OR/NAND) são facilmente convertidas 
em redes do tipo NAND/NAND (NOR/NOR).
● Redes de saída única. (redes mais complexas exigem abordagem 
hierárquica)
● Sem limitações quanto ao número de entradas de cada porta.
Sistemas Lógicos 5
3.1. Introdução
● Métodos SISTEMÁTICOS de MINIMIZAÇÃO: redes com 
número mínimo de portas, e, dentre estas, com o número mínimo 
de entradas.
● Expressões mínimas em SOP e POS devem ser comparadas.
Rede Rede
Sistemas Lógicos 6
3.2. Mapas de Karnaugh
● Representação espacial que possibilita sistematizar a 
aplicação do TEOREMA DA ADJACÊNCIA entre 
as diferentes variáveis.
● Adjacências -> vizinhança entre linhas, colunas e 
fronteira do mapa (toróide).
● Obtém-se um bom aproveitamento da simplicidade 
do método para um limite de 5 a 6 variáveis de 
entrada.
a.b+ a.b'=a
(a+ b).(a+ b ')=a
Sistemas Lógicos 7
3.2. Mapas de Karnaugh
Sistemas Lógicos 8
3.2. Mapas de Karnaugh
(e)
Sistemas Lógicos 9
3.2.1. Conceitos
● Termo mínimo/máximo.
● Representação numérica da função e preenchimento 
do mapa.
f (x2 , x1 , x0)=∑m {0,2,6 }
f (x3 , x2 , x1 , x0)=∏ M {1,3,4,6,10,11,13 }
f (x2 , x1 , x0)=∑m {1.4,5 }U∑ dc {2,3 }
Sistemas Lógicos 10
3.2.1. Conceitos
● Adjacências: retângulos com dimensões em potência 
de dois para SOP (células-1) ou POS (células-0).
Sistemas Lógicos 11
3.2.1. Conceitos
● Representação de expressões no mapa K.
Sistemas Lógicos 12
3.2.1. Conceitos
● Implicantes (Implicados).
● Implicantes (Implicados) Primos.
● Implicantes (Implicados) Primos Essenciais.
(a) Implicantes (b) Implicantes primos
Sistemas Lógicos 13
3.2.2. Algoritmo
1. Determine todos os implicantes (implicados) 
primos.
2. Obtenha os implicantes (implicados) primos 
essenciais.
3. Se restam células-1 que não estão cobertas pelos 
implicantes primos essenciais, escolha os menor 
conjunto de implicantes primos que promove a 
cobertura total de células-1.
Sistemas Lógicos 14
3.2.3. Exemplo (1)
●
● Implicantes Primos:
● Implicantes Primos Essenciais:
● Expressão mínima em SOP:
E( x1 , x2 , x3)=∑ m {0,3,4,6,7 }
x1' x0', x1 x0 , x2 x0' e x2 x1 
x1' x0' e x1 x0
x1' x0' + x1 x0 + x2 x0' e x1' x0'+ x1 x0 + x2 x1
Sistemas Lógicos 15
3.2.3. Exemplo (2)
●
● Expressão mínima em SOP:
E( x3 , x2 , x1 , x0)=∑ m{0,1,3,7,8,12 }U∑ dc {5,10,11,13,14 }
E(x3,x2,x1,x0) = x3 x0' + x3' x0+ x1 x0 + x3'x2'x1'
Sistemas Lógicos 16
3.2.3. Exemplo (3)
●
● Expressão mínima em POS:
E( x3 , x2 , x1 , x0)=∑M {2,5,7,13,15 }U∑ dc {10 }
E(x3,x2,x1,x0) =(x0'+ x2').( x0+ x2 + x1')
Sistemas Lógicos 17
3.2.3. Exemplo – Sugestões
● F(x3,x2,x1,x0) = Σm{0,2,3,5,8} U 
dc{10,11,12,13,14,15}
● F(x3,x2,x1,x0) = ΠΜ{2,4,6,8,9,10,15}
Sistemas Lógicos 18
3.3. Método de Quine-McCluskey
● Método tabular.
● Aplicação sucessiva do teorema da união para 
determinar os implicantes primos.
● Em comparação aos mapas de karnaugh:
– Mais adequado a implementação através de 
programação.
– Pode ser empregado em problemas com maior 
número de variáveis de entrada.
● Utilizado como base em ferramentas CAD para a 
minimização de redes lógicas de dois níveis.
Sistemas Lógicos 19
3.3. Método de Quine-McCluskey
● Tabelas: 1. Implicantes primos 2. Cobertura mínima
● Tabela de implicantes primos: nas colunas são 
dispostas os diferentes tamanhos de adjacências, e as 
linhas estabelecem os possíveis termos agrupados 
pelos número de 1s.
● Tabela de cobertura: nas colunas são dispostos todos 
os termos mínimos e nas linhas os diferentes 
implicantes primos.
Sistemas Lógicos 20
3.3. Método de Quine-McCluskey
● Exemplo: f(x3,x2,x1,x0)=Σm{0,1,3,5,7,11,12,13,14}
TERMOS
MÍNIMOS
ADJACÊNCIAS
3 VAR. 2 VAR. 1 VAR.
0000 N 000- 0--1
0001 N 00-1 N
0-01 N
0011 N
0101 N 0-11 N
1100 N -011
01-1 N
0111 N -101
1011 N 110-
1101 N 11-0
1110 N
Sistemas Lógicos 21
3.3. Método de Quine-McCluskey
● Exemplo: Tabela de cobertura
Implicantes 0 1 3 5 7 11 12 13 14 PE
000- x x x
-011 x x x
-101 x x
110- x x
11-0 x x x
0--1 x x x x x
x3' x2' x1' + x2' x1x0 + x2x1' x0 + x3x2x0' + x3' x0
x3' x2' x1' + x2' x1x0 + x3x2x1' + x3x2x0' + x3' x0