Notas de aula 3 - Computer Vision Research Group

39
Notas de aula de MAC0329 (2004)
6
Circuitos de chaveamentos e Circuitos Lógicos
Esta seção contém uma breve introdução a circuitos digitais (lógicos), sua relação com a álgebra
booleana, e alguns problemas relacionados ao projeto de circuitos lógicos. Mais detalhes podem
ser encontrados em quaisquer livros sobre projeto de circuitos lógicos (exemplo: [Mendelson, 1977,
Hill and Peterson, 1981, Katz, 1994, Micheli, 1994]).
6.1
Circuitos de chaveamentos
Na vida diária deparamos com dispositivos fı́sicos de dois estados tais como interruptores, contatos, diodos, transistores, etc. Dependendo do dispositivo em questão, eles podem tomar os estados ligado/desligado, conduzindo/não conduzindo, fechado/aberto, carregado/descarregado, magnetizado/não magnetizado, alto-potencial/baixo-potencial, etc. Vários circuitos podem ser formados com
esses dispositivos tais como circuitos de computadores eletrônicos, sistemas de chaveamento telefônico,
dispositivos ou sistemas de controle em geral (elevador, display digital, etc), etc.
Em um circuito elétrico, uma chave é um dispositivo ligado a um ponto do circuito e que pode tomar
um dos dois estados, fechado ou aberto. No estado fechado, a chave permite que a corrente passe
através do ponto, enquanto que no estado aberto nenhuma corrente passa através do ponto. O estado
fechado (respec., aberto) pode ser referenciado por 1 (respec., 0) e as chaves podem ser representadas
por letras como x, y, z, etc.
Dois pontos P e Q (inicial e final) estão ligados por um circuito de chaveamento se estes estão ligados
por um circuito (linhas) no qual está localizado um número finito de chaves.
A disposição dos fios e das chaves no circuito determina alguns tipos de circuitos. Os possı́veis tipos
estão ilustrados a seguir:
6.1.1
Circuitos em série
A corrente flui de P a Q se e somente se todas as chaves estiverem fechadas.
a
P
b
c
Q
Figura 1: Exemplo de um circuito em série.
6.1.2
Circuitos em paralelo
A corrente flui de P a Q se pelo menos uma das chaves estiver fechada.
a
b
P
c
Q
d
Figura 2: Exemplo de um circuito em paralelo.
40
Notas de aula de MAC0329 (2004)
6.1.3
Circuitos em série-paralelo
Envolvem ligações em série e em paralelo. Em geral, pode-se trocar uma chave de um circuito por um
circuito em série ou em paralelo para se obter novos circuitos série-paralelos.
b
c
a
a
P
Q
b
d
c
Figura 3: Exemplo de um circuito em série-paralelo.
6.1.4
Circuitos ponte
São circuitos que não são série-paralelo.
a
P
d
Q
c
b
e
Figura 4: Exemplo de um circuito-ponte.
Com relação aos circuitos de chaveamento, podemos observar que:
• Duas chaves com o mesmo nome operam de forma idêntica (ou seja, se uma está aberta, a outra
está necessariamente aberta e vice-versa). Chaves com nomes complementados operam de forma
complementar (se a chave x está aberta então a chave x está fechada e vice-versa).
• Denotando os circuitos em série como o produto das chaves (por exemplo, x y se as chaves são
x e y) e os circuitos em paralelo pela soma das chaves (por exemplo, a + b + c se as chaves
são a, b e c), podemos ver que qualquer circuito em série-paralelo corresponde a uma expressão
booleana com n variáveis, onde n é a quantidade de chaves com nomes distintos (a menos de
complementação) presentes no circuito. No caso do exemplo em série-paralelo acima, a expressão
correspondente é:
a(bc + a) + bdc
As chaves (com nomes distintos) correspondem às variáveis booleanas, a posição das chaves
define o valor dessas variáveis, e o estado do circuito estar ou não conduzindo corrente de P a
Q corresponde ao valor (1 ou 0, respectivamente) da função.
Analogamente, qualquer expressão envolvendo +, · e complementação de variáveis corresponde
a um circuito em série-paralelo.
Podemos dizer que uma função representa um circuito e que um circuito realiza uma função.
• Dois circuitos envolvendo as mesmas chaves são equivalentes se para as mesmas posições das
chaves a corrente flui ou não flui de P a Q em ambos. Obviamente, as expressões correspondentes
a circuitos equivalentes são também equivalentes (e vice-versa).
41
Notas de aula de MAC0329 (2004)
• Da mesma forma que podemos simplificar expressões booleanas, podemos também simplificar os
circuitos.
• Considerando-se que as chaves podem tomar apenas dois estados, que o circuito ou está ou não
está conduzindo corrente (mas não ambos), e ignorando-se questões fı́sicas como voltagem, resistência, quantidade de corrente elétrica, os circuitos de chaveamento podem ser modelados pela
álgebra booleana. A menos das diferenças de terminologia e de significado, trata-se exatamente
da lógica proposicional (ou da álgebra booleana hB, +, ·, , 0, 1i).
• Para cada circuito-ponte também corresponde uma função. A expressão correspondente pode
ser obtida tomando-se todos os caminhos que conduzem corrente de P a Q. Porém, dada uma
função qualquer, determinar um circuito-ponte correspondente não é fácil.
No exemplo da figura 4, o circuito em série-paralelo correspondente é:
d
a
c
P
e
Q
e
b
c
6.2
d
Circuitos lógicos
Usando a convenção 1 para presença de sinal e 0 para ausência de sinal, podemos olhar circuitos
de chaveamento do ponto de vista lógico (funcional). Por exemplo, no caso de circuitos em série, a
corrente só flui com todas as portas fechadas, isto é, com sinais de entrada presentes em todas as
chaves. Então, um circuito em série com n chaves pode ser representado por um dispositivo com
n entradas (correspondendo cada uma delas a uma chave), e uma saı́da que vale 1 se há sinal em
todas as entradas e 0 se há pelo menos uma entrada sem sinal. Da mesma forma, podemos ter
dispositivos representando um circuito em paralelo, ou algum outro circuito simples. Tais dispositivos
são chamados portas lógicas.
As principais portas lógicas estão ilustradas a seguir:
Porta E
Porta OU
Inversor NÃO
Porta XOR
Porta NÃO-E
Porta NÃO-OU
Figura 5: Representação gráfica de algumas portas lógicas.
As ilustrações acima mostram portas com duas entradas, mas são usuais também as portas E, OU,
NÃO-E e NÃO-OU com mais de duas entradas. As funções representadas por estas portas (para duas
entradas x1 e x2 ) estão descritas a seguir:
42
Notas de aula de MAC0329 (2004)
x1
0
0
1
1
x2
0
1
0
1
E
x1 x2
0
0
0
1
OU
x1 + x2
0
1
1
1
NÃO
x1
1
1
0
0
XOR
x1 ⊕ x2
0
1
1
0
NÃO-E
x1 x2
1
1
1
0
NÃO-OU
x1 + x2
1
0
0
0
Circuitos lógicos são circuitos construı́dos a partir da interconexão de portas lógicas. Comparado
aos circuitos de chaveamento, as entradas das portas lógicas em um circuito lógico correspondem às
chaves enquanto uma saı́da corresponde a indicar se a corrente está passando de um ponto ao outro
no circuito de chaveamento.
Fisicamente, as entradas e a saı́da são quantidades fı́sicas (por exemplo, nı́vel de voltagem). Adotase uma convenção para distinguir dois estados (0 e 1) dependendo da quantidade fı́sica corrente. A
implementação fı́sica de portas lógicas é altamente dependente de tecnologia e não será considerada
nesta disciplina.
Uma vez que entradas e saı́das são sempre 0s ou 1s, podemos pensar em circuitos lógicos como formas
de se expressar funções booleanas de B n em B. Portanto, a álgebra booleana constitui um fundamento
teórico para o projeto de circuitos digitais (ou seja, uma das razões para se estudar álgebra booleana
é justamente para podermos entender e projetar circuitos digitais!).
6.3
Completude funcional
Conforme já vimos anteriormente, qualquer expressão booleana é obtida compondo-se subexpressões
com os operadores + (disjunção), · (conjunção) e . Em particular, vimos que qualquer função de B n
em B pode ser expressa por uma expressão booleana. Isto significa que qualquer função de B n em B
pode ser implementada com circuitos que utilizam apenas as portas E, OU e o inversor NÃO.
Mais ainda, vimos que o sistema algébrico continua completo mesmo restrito aos operadores + e (ou
· e ), pois o outro pode ser expresso em função desses dois.
No caso de portas lógicas, temos os dois casos a seguir:
6.3.1
Portas E e NÃO
a + b = a + b = (a b)
Figura 6: Realização do operador OU com E e NÃO.
6.3.2
Portas OU e NÃO
a b = a b = (a + b)
43
Notas de aula de MAC0329 (2004)
Figura 7: Realização do operador E com OU e NÃO.
6.3.3
Portas NÃO-E / Portas NÃO-OU
Além dos dois casos acima, portas NÃO-E e portas NÃO-OU sozinhas também constituem sistemas
completos. A figura 8 ilustra a expressão de NÃO, E e OU em termos de NÃO-E e em termos de
NÃO-OU.
a
a
a
a
ab
a
a
b
ab
b
a
a+b
a
b
b
a+b
Figura 8: Realização do operador NÃO, E e OU com NÃO-E e com NÃO-OU.
De fato, com respeito à porta NÃO-E temos:
a = a + a = aa
a b = a b + a b = a b + a b = ab ab
a + b = aa + bb = a a + b b = (a a)(b b)
e com respeito à porta NÃO-OU, temos
a = aa = a + a
ab = (a + a)(b + b) = (a + a)(b + b) = (a + a) + (b + b)
a + b = (a + b)(a + b) = (a + b)(a + b) = (a + b) + (a + b)
Notas de aula de MAC0329 (2004)
44
Exemplo: Dada a função f (a, b, c, d) = a+bc+cd, expresse f de forma que sua realiazação corresponda
a um circuito dois-nı́veis utilizando apenas as portas especificadas. Suponha que as entradas da portas
lógicas podem ser variáveis com ou sem complementação.
a) portas NÃO-E
b) portas OU e NÃO-E
c) portas NÃO-OU e OU
No caso (a) basta utilizarmos o fato de que f = f . Assim temos f = f = a + bc + cd = a · b c · cd
No caso (b), basta aplicarmos DeMorgan em cada um dos termos do resultado anterior. Assim temos
f = a · (b + c) · (c + b).
Finalmente, no caso (c) basta aplicarmos DeMorgan novamente. Assim temos f = a+(b + c)+(c + b).
Exercı́cio: Desenho os circuitos correspondentes a cada uma das expressões do exemplo acima.
6.4
Circuitos combinacionais e seqüenciais
Os circuitos combinacionais são aqueles nos quais as saı́das são determinadas em função apenas das
entradas atuais. Os circuitos seqüenciais são aqueles nos quais as saı́das dependem não apenas das
entradas atuais mas também de dados prévios nos instantes anteriores. Pode-se dizer que circuitos
seqüenciais envolvem realimentação, ou seja, eles possuem “memória”.
6.5
Projeto de circuitos combinacionais
Projetar um circuito consiste em especificar um circuito que implementa uma certa funcionalidade
desejada. No projeto de circuitos digitais, várias questões devem ser levadas em consideração tais
como tecnologia, custo, quantidade de portas lógicas a serem utilizadas, eficiência computacional, etc.
A seguir discorremos brevemente sobre alguns aspectos a serem considerados neste curso.
A velocidade de computação é afetada por diversos fatores. Dentre eles, o caminho mais longo (em
termos de quantidade de portas lógicas) que o sinal deve percorrer até produzir o resultado define o
número de nı́veis do circuito. Assim, podemos ter
• circuitos 2-nı́veis
• circuitos multi-nı́veis
Encontrar uma representação compacta 2-nı́veis é um problema que já foi bastante estudado e existem vários algoritmos/técnicas para este problema (Mapa de Karnaugh, método tabular de QuineMcCluskey, Espresso, etc).
Em termos funcionais, os processamentos efetuados pelo computador correspondem à realização de
várias funções (a composição das saı́das de várias funções corresponde ao resultado de um certo processamento). Em vez de especificar um circuito para cada uma das funções, muitas vezes pode-se reduzir
a quantidade de portas lógicas necessárias para implementar todas as funções compartilhando-se subcircuitos entre as várias funções. Portanto, podemos também pensar em circuitos com múltiplas
saı́das.
No caso de simplificação 2-nı́veis de funções booleanas além de algoritmos especı́ficos para simplificar (ou minimizar) funções individualmente, são também importantes os algoritmos para minimizar
Notas de aula de MAC0329 (2004)
45
uma coleção de funções (que não necessariamente resulta em minimização individual, mas resulta em
minimização coletiva). No caso de projeto multi-nı́veis, o problema de simplificação é mais complexo.
A tecnologia a ser utilizada para a realização das funções pode influenciar o tipo de otimização em
questão. Por exemplo, pode-se desejar utilizar apenas um conjunto de portas lógicas (por exemplo
NÃO-E), ou então, pode-se querer utilizar dispositivos programáveis com uma certa estrutura, ou
ainda utilizar circuitos comerciais disponı́veis no mercado.
Os passos básicos para se projetar um circuito são:
• Entender o problema: Identificar os dados de entrada, de controle e de saı́da, e de que forma
o controle age sobre os dados de entrada para produzir a saı́da desejada; assumir hipóteses
razoáveis; dar nomes aos elementos.
• Formular o problema em alguma representação padrão: descrever formalmente a relação entradasaı́da (por exemplo, através de tabelas-verdade ou expressões booleanas).
• Escolher uma implementação: na implementação, a descrição formal (abstrata) deve ser mapeada para algo concreto como portas lógicas. Assim, deve-se decidir a implementação em
termos concretos: lógica 2-nı́veis, lógica multi-nı́veis, lógica NÃO-E, lógica NÃO-OU, PLA, usar
componentes disponı́veis comercialmente, etc.
• Aplicar um procedimento de projeto: uma vez escolhida a implementação, deve-se fazer o mapeamento propriamente dito. No caso de implementação por portas lógicas, um dos objetivos
pode ser a minimização do número total de portas lógicas em uma implementação dois-nı́veis.
Neste caso pode-se aplicar técnicas de minimização dois-nı́veis.
Exemplo: Deseja-se projetar um sistema de alarme contra roubos em um banco. Este sistema será
alimentado por sinais provenientes de 4 linhas. A linha A está conectada a uma chave secreta de
controle, a linha B a um sensor sob um cofre de aço no depósito, a linha C a um relógio a bateria, e a
linha D à fechadura do depósito que abriga o cofre de aço. As seguintes situações produzem voltagem
correspondente ao valor lógico 1 em cada uma das linhas:
A: A chave secreta de controle está fechada
B: O cofre está em sua posição normal
C: O relógio está entre 10:00 e 15:00 horas (horário de atendimento do banco).
D: A porta do depósito que abriga o cofre está fechada
O alarme deve soar (saı́da igual ao valor lógico 1) se a chave secreta de controle está fechada e o cofre
foi movido, ou quando a sala é aberta após o expediente bancário, ou quando o depósito é aberto com
a chave secreta de controle aberta.
Podemos ver que as entradas consistem dos sinais provenientes das 4 linhas e a saı́da será o soar ou
o não soar do alarme. Assim, podemos expressar a saı́da através de uma função f (A, B, C, D). A
função toma valor 1 (isto é, o alarme soa) nos seguintes casos:
A chave secreta de controle está fechada e o cofre foi movido: AB
O depósito é aberta após o expediente bancário: C D
O depósito é aberto com a chave secreta de controle aberta: A D
46
Notas de aula de MAC0329 (2004)
Logo, a função pode ser escrita como f (A, B, C, D) = AB + C D + A D. Esta expressão pode ser
substituı́da por outra equivalente mais adequada à implementação escolhida.
Exercı́cio: Desenhe o circuito de chaveamento e o circuito digital correspondente à função f (a, b, c, d, e) =
(a + b)cd + e.
Exercı́cio: Qual é a função correspondente ao circuito de chaveamento a seguir ?
b
a
d
c
e
f
Exercı́cio: Desenhe circuitos de chaveamento correspondentes às seguintes expressões:
x y z + x (y + y)
x [y (z + w) + z (u + v)]
(a + b + c)(a + bc) + c d + d (b + c)
Exercı́cio: Qual é a função correspondente ao circuito lógico a seguir ?
a
d
c
f
a
b
c
Expresse a função na forma SOP e desenhe o circuito correspondente.
Exercı́cio: Em alguns casos, simplificar a expressão dual é muito mais fácil do que simplificar a
expressão original. Simplifique a função f = cb + abcd + cd + ac + abc + b c d. Dica: considere
g = cb + abcd + cd e h = ac + abc + b c d. Simplifique g ∗ e h∗ e use o fato de que g = (g ∗ )∗ e h = (h∗ )∗ .
Exercı́cio: Suponha que as entradas das portas lógicas podem ser variáveis com ou sem complementação. Dada uma função na forma produto de somas, desenhe circuitos dois-nı́veis utilizando
apenas:
a) portas OU e E
b) portas NÃO-OU
c) portas E e NÃO-OU
d) portas NÃO-E e E
Notas de aula de MAC0329 (2004)
47
Exercı́cio: Uma sala tem duas portas e ambas podem ser utilizadas tanto como entrada como saı́da.
Deseja-se instalar interruptores perto das duas salas de forma que ao entrar na sala seja possı́vel
acendermos a luz da sala e ao saı́rmos da sala seja possı́vel apagarmos as luzes, independentemente
da porta utilizada para entrar ou sair da sala. Podemos pensar nos interruptores como sendo as
entradas do sistema e a lâmpada como sendo a saı́da do sistema. O funcionamento lógico deste sistema
(acender/apagar da lâmpada) pode ser descrito por uma função. Derive a função e em seguida descreva
como implementar o circuito lógico correspondente.
Exercı́cio: No exercı́cio anterior, como ficaria a sua função se a sala fosse imensa e tivesse três portas
?
Exercı́cio: Quais dos seguintes contém circuitos combinacionais e quais contém circuitos seqüênciais?
Justifique a sua reposta.
a) Uma máquina de lavar automática com etapas de molho, lavagem, enxágue e centrifugação.
b) Um circuito de três entradas que produz saı́da 1 sempre que ao menos duas das entradas têm valor
1.
c) Um circuito que divide dois números de dois bits e devolve o quociente e o resto da divisão.
d) Uma máquina que aceita uma cédula de um real e devolve três moedas de 25 centavos, duas moedas
de 10 centavos e uma de 5 centavos.
e) Um relógio digital que toca um alarme quando um determinado horário é atingido.
Exercı́cio: Antônio e Bia têm dois filhos, Carlos e Dina. Quando comem fora, eles sempre vão ou
a um restaurante que serve hamburgueres ou então a outro que serve frangos. Antes de sair de casa,
a famı́lia vota para decidir em qual dos restaurantes irá. O restaurante que recebe maior número de
votos ganha, exceto quando Antônio e Bia votam pelo mesmo restaurante, e neste caso o restaurante
escolhido por eles ganha. Em todas as outras situações de empate, a famı́lia vai ao restaurante de
frangos. Projete um circuito lógico que automaticamente seleciona um restaurante quando a famı́lia
vota.
Notas de aula de MAC0329 (2004)
7
48
Lógica combinacional dois-nı́veis
Objetivo: encontrar expressões mı́nimas na forma soma de produtos ou produto de somas, que podem
ser implementados em circuitos com dois nı́veis de portas lógicas.
Referências para esta parte: capı́tulo 6 de [Hill and Peterson, 1981], capı́tulo 7 de [Micheli, 1994],
capı́tulo 4 de [Mendelson, 1977], etc.
7.1
Revisão
Os dados nos computadores digitais são representados em binário e os processamentos nada mais são
do que mapeamentos de dados binários em dados binários, ou seja, funções que mapeiam n dı́gitos
binários em m dı́gitos binários.
Seja A(n) o conjunto de todas as funções booleanas em A com n variáveis e seja ≤ uma relação definida
em A(n) da seguinte forma:
f ≤ g ⇐⇒ f (a) ≤ g(a), ∀a ∈ An .
Seja (f · g)(a) = f (a) · g(a), (f + g)(a) = f (a) + g(a), e f (a) = f (a), ∀a ∈ An . Fazendo 0(a) = 0 e
1(a) = 1 para todo a ∈ An , o conjunto (A(n), +, ·, , 0, 1) também é uma álgebra booleana.
Daqui em diante consideremos a álgebra booleana hB(n), +, ·, , 0, 1i.
Uma função booleana f : {0, 1}n → {0, 1} pode ser caracterizada em termos de seu conjunto-um,
f h1i = {b ∈ {0, 1}n : f (b) = 1}, bem como em termos do seu conjunto-zero, f h0i = {b ∈ {0, 1}n :
f (b) = 0}.
As funções booleanas que tomam valor 1 em exatamente um elemento de {0, 1}n são denominados
mintermos. Um mintermo em n variáveis é uma conjunção (produto) de exatamente n literais, os
quais envolvem diferentes variáveis. Uma conjunção em que uma Q
variável aparece no máximo uma
vez é usualmente denominada de produto, e expresso como p = ni=1 σi , σi ∈ {xi , xi , 0 0 }, com 0 0
denotando o caractere vazio. Por exemplo, para n = 4, x1 x3 e x2 x3 x4 são exemplos de produtos.
Mintermos (aqueles em que todas as variáveis aparecem exatamente uma vez, ou na forma barrada
ou na forma não-barrada) são também chamados de produtos canônicos.
Os átomos de hB(n), +, ·, , 0, 1i são os 2n mintermos. Portanto, toda função booleana pode ser escrita
como uma disjunção (soma) de mintermos distintos. Mais ainda, tal representação é única a menos
da ordem dos mintermos e será denominada soma canônica de produtos (SOP canônica).
7.2
Simplificação de notação
O conjunto de todas as seqüências de n bits correspondem à representação binária dos números entre 0
e 2n − 1. Com base neste fato, podemos caracterizar os produtos canônicos, e as somas canônicas (que
serão denominadas maxtermos) através da notação decimal correspondente. A tabela 1 apresenta
os mintermos e maxtermos para três variáveis e a notação associada a cada um deles.
Observe que x1 x2 x3 = 1 se e somente se x1 = 1, x2 = 0 e x3 = 1. Portanto, a SOP canônica de uma
expressão booleana pode ser diretamente obtida através da soma dos mintermos correspondentes aos
1’s da sua tabela-verdade. Analogamente, (x1 + x2 + x3 ) = 0 se e somente se x1 = 0, x2 = 1 e x3 = 0,
49
Notas de aula de MAC0329 (2004)
x1 x2 x3
000
001
010
011
100
101
110
111
maxtermos
x 1 + x 2 + x 3 = M0
x 1 + x 2 + x 3 = M1
x 1 + x 2 + x 3 = M2
x 1 + x 2 + x 3 = M3
x 1 + x 2 + x 3 = M4
x 1 + x 2 + x 3 = M5
x 1 + x 2 + x 3 = M6
x 1 + x 2 + x 3 = M7
mintermos
x 1 x 2 x 3 = m0
x 1 x 2 x 3 = m1
x 1 x 2 x 3 = m2
x 1 x 2 x 3 = m3
x 1 x 2 x 3 = m4
x 1 x 2 x 3 = m5
x 1 x 2 x 3 = m6
x 1 x 2 x 3 = m7
Tabela 1: Tabela de maxtermos e mintermos
e portanto, a POS canônica pode ser obtida pelo produto dos maxtermos correspondentes aos 0’s da
tabela-verdade.
Exemplo: Dada a tabela-verdade
x1 x2 x3
000
001
010
011
100
101
110
111
f1
1
1
0
0
1
1
1
0
a forma SOP canônica da função é
f (x1 , x2 , x3 ) = x1 x2 x3 + x1 x2 x3 + x1 x2 x3 + x1 x2 x3 + x1 x2 x3
e sua notação simplificada é dada por :
f (x1 , x2 , x3 ) =
X
m(0, 1, 4, 5, 6).
A forma POS canônica é f (x1 , x2 , x3 ) = (x1 + x2 + x3 )(x1 + x2 + x3 )(x1 + x2 + x3 ) =
7.3
Q
M (2, 3, 7).
Minimização de funções booleanas
Quando pensamos em minimização, devemos estabelecer um critério de custo que desejamos minimizar.
O seguinte critério é bastante utilizado.
Definição: Uma expressão booleana escrita como soma de produtos é minimal se (1) não existe
nenhuma outra expressão equivalente com um número menor de termos e (2) não existe nenhuma
outra expressão equivalente com igual número de termos mas com menor número de literais.
Definição: Um implicante primo (ou simplesmente primo) de uma função booleana f é um
produto p tal que p ≤ f , e não há outro produto p0 , p ≤ p0 , tal que p0 ≤ f .
50
Notas de aula de MAC0329 (2004)
Dada uma expressão minimal, se um literal de qualquer um dos produtos da expressão é removida, a
expressão resultante não mais representa a mesma função.
Teorema: Qualquer produto em uma expressão minimal do tipo soma de produtos é um implicante
primo.
7.3.1
Representação cúbica (ou via intervalos)
Um conceito utilizado com bastante freqüência no contexto de manipulação de funções booleanas é o
de cubos.
As seqüências de n bits, correspondentes a todas as possı́veis combinações de valores que as n variáveis
de uma função Booleana podem tomar, podem ser representadas por pontos no n-espaço. A coleção
de todos os 2n pontos possı́veis formam os vértices de um n-cubo. A figura 9 mostra um 3-cubo.
111
011
101
110
001
010
100
000
Figura 9: Diagrama do 3-cubo.
Os vértices de um n-cubo são denominados 0-cubos. Dois 0-cubos formam um 1-cubo se eles diferem
em apenas uma coordenada. Quatro 0-cubos formam um 2-cubo se eles são iguais a menos de duas
coordenadas. De modo geral, 2k 0-cubos formam um k-cubo se eles são exatamente iguais a menos de
k coordenadas.
Mais formalmente, um cubo é um conjunto de elementos em {0, 1}n para os quais um produto toma
valor 1, i.e., se p é um produto então o cubo correspondente é o conjunto ph1i = {b ∈ {0, 1}n : p(b) =
1}. Portanto, existem tantos cubos contidos em {0, 1}n quanto produtos envolvendo as variáveis
x1 , x 2 , . . . , x n .
Cubos não são subconjuntos arbitrários de {0, 1}n . No contexto de reticulados, cubos são subreticulados do reticulado {0, 1}n , denominados intervalos.
Um intervalo é caracterizado por dois extremos: o menor e o mair elementos contidos nele. Assim, o
intervalo de extremo inferior 100 e extremo superior 101 é denotado [100, 101] e definido por [100, 101] =
{x ∈ {0, 1}3 : 100 ≤ x ≤ 101}.
Denotamos um k-cubo colocando um X nas coordenadas que não são iguais. Assim, o 1-cubo
{000, 100}, que corresponde ao intervalo [000, 100], é representado por X00. O 2-cubo {000, 001, 100, 101},
que corresponde ao intervalo [000, 101], é representado por X0X.
NOTA: Daqui em diante utilizaremos arbitrariamente os termos produto, cubo ou intervalo
quando nos referirmos a um produto.
Uma função booleana com poucas variáveis (tipicamente 3 ou 4) pode ser graficamante ilustrada
através do diagrama de Hasse. Usaremos a convensão de desenhar elementos de f h1i como cı́rculos
preenchidos, enquanto os elementos de f h0i serão representados por cı́rculos não preenchidos. A
51
Notas de aula de MAC0329 (2004)
representação via diagrama de Hasse da função f1 (x1 , x2 , x3 ) = x1 x2 x3 + x1 x2 x3 + x1 x2 x3 + x1 x2 x3
é mostrada na figura 10.
111
011
101
001
010
110
100
000
Figura 10: Representação via diagrama de Hasse da função f1 .
Exemplo: A figura 11 mostra alguns cubos. Dizemos que o 0-cubo 000 está contido no (ou é coberto
pelo) 1-cubo X00, ou ainda, que o 1-cubo X00 cobre o 0-cubo 000. Analogamente, dizemos que o
1-cubo X00 está contido no 2-cubo X0X ou que o 2-cubo X0X cobre o cubo X00.
X00
X0X
000
a
b
c
Figura 11: Os cubos 000, X00 e X0X.
Dada uma função f e um produto p, dizemos que o conjunto ph1i é um cubo de f se p ≤ f (ou,
equivalentemente, se ph1i ⊆ f h1i). Neste sentido, mintermos são cubos de tamanho unitário e primos
são cubos maximais contidos em f h1i (i.e., um cubo de f que não é totalmente contido em outro cubo
de f ).
Os dois primeiros cubos da Fig. 12 (em negrito) são cubos da função f1 mas os dois últimos não são.
Figura 12: Exemplos de um 0-cubo (intervalo 011), um 1-cubo (intervalo 0X1), um 2-cubo (intervalo
0XX) e um 3-cubo (intervalo XXX), respectivamente (em negrito).
P
Exemplo: A função Booleana f =
m(0, 1, 4, 5, 6) é representada pelos vértices 000, 001, 100, 101
e 110. Os mintermos (ou intervalos triviais) de f e os implicantes primos (ou cubos ou intervalos
maximais) de f são mostrados respectivamente nas figura 13a e 13b.
A forma SOP canônica de f pode ser entendida como sendo a coleção de 0-cubos de f ou, equivalentemente, como a coleção de intervalos triviais (intervalos com apenas um elemento), cada um deles
correspondendo a um elemento em f h1i. Em geral, qualquer expressão na forma SOP corresponde a
uma coleção de cubos (ou intervalos) onde nenhum deles está propriamente contido em outro.
52
Notas de aula de MAC0329 (2004)
101
110
1X0
001
100
X0X
000
a
b
Figura 13: (a) Mintermos e (b) implicantes primos de f =
7.4
P
m(0, 1, 4, 5, 6).
Mapas de karnaugh
A minimização de uma expressão Booleana pode ser realizada algebricamente aplicando-se os axiomas
e leis da álgebra Booleana. Entretanto, a manipulação algébrica, além de ser uma tarefa cansativa,
pode facilmente induzir uma pessoa a cometer erros, principalmente quando o número de variáveis
envolvidas é grande. Mapas de Karnaugh são diagramas que são utilizados para auxiliar este processo.
Qualquer livro que cobre funções booleanas (funções de chaveamento), projeto de circuitos lógicos ou
minimização lógica apresenta a minimização de funções booleanas utilizando mapas de Karnaugh (ou
K-maps). Mapas de Karnaugh podem ser utilizadas para minimização (manual) de funções com até 6
variáveis. (Este tópico será coberto em sala de aula, mas não haverá notas de aula sobre este tópico1 ).
7.5
Minimização Tabular de Quine-McCluskey
Mapas de Karnaugh representam uma maneira visual e intuitiva de se minimizar funções booleanas.
No entanto, elas só se aplicam a funções com até 6 variáveis e não são sistemáticos (adequados para
programação). O algoritmo tabular de Quine-McCluskey para minimização de funções Booleanas é um
método clássico que sistematiza este processo de minimização para um número arbitrário de variáveis.
O algoritmo de Quine-McCluskey (QM) requer que a função booleana a ser minimizada esteja na
forma SOP canônica. A idéia básica deste algoritmo consiste em encarar os mintermos da SOP
canônica como pontos no n-espaço, ou seja, como vértices de um n-cubo. A partir do conjunto destes
vértices (ou 0-cubos) procura-se gerar todos os 1-cubos possı́veis combinando-se dois deles (equivale
a gerar as arestas do cubo que ligam dois 0-cubos considerados). A partir da combinação de dois
1-cubos procura-se gerar todos os possı́veis 2-cubos e assim por diante, até que nenhum cubo de
dimensão maior possa ser gerado a partir da combinação de dois cubos de dimensão menor. Os cubos
resultantes (aqueles que não foram combinados com nenhum outro) ao final de todo o processo são os
implicantes primos.
Este processo de minimização pode ser facilmente associado ao processo algébrico de simplificação. Os
mintermos da expressão na forma canônica inicial correspondem aos 0-cubos. Combinar dois 0-cubos
para gerar um 1-cubo corresponde a combinar dois mintermos para eliminar uma variável e gerar um
termo com menos literais para substituı́-los, como mostramos no seguinte exemplo :
x1 x2 x3 + x1 x2 x3 = x1 x2 (x3 + x3 ) = x1 x2 · 1 = x1 x2
Quando considerados no 3-espaço, o processo mostrado na expressão algébrica acima corresponde ao
processo de agruparmos os 0-cubos 111 e 110 para geração do 1-cubo 11X, como ilustra a figura 14.
1
A não ser que alguém se dispunha a desenhar os mapas ou digitalizar os mapas de algum livro.
53
Notas de aula de MAC0329 (2004)
111
11X
110
Figura 14: Passo elementar do algoritmo de Quine-McCluskey
7.5.1
Cálculo de implicantes primos
A primeira parte do algoritmo QM consiste de um processo para determinação de todos os implicantes
primos. A seguir descrevemos os processos queP
constituem esta parte e, ao mesmo tempo, mostramos
a sua aplicação sobre a função f (x1 , x2 , x3 ) =
m(0, 1, 4, 5, 6).
• Primeiro passo : converter os mintermos para a notação binária.
000, 001, 100, 101, 110
• Segundo passo : Separar os mintermos em grupos de acordo com o número de 1’s em sua
representação binária e ordená-los em ordem crescente, em uma coluna, separando os grupos
com uma linha horizontal.
000
001
100
101
110
• Terceiro passo : combinar todos os elementos de um grupo com todos os elementos do grupo
adjacente inferior para geração de cubos de dimensão maior. Para cada 2 grupos comparados
√
entre si, gerar um novo grupo na próxima coluna e colocar os novos cubos. Marcar com
os
cubos que foram usados para gerar novos cubos.
√
√
√
√
√
000
001
100
101
110
=⇒
00X
X00
X01
10X
1X0
Observação : o novo cubo gerado será inserido no novo conjunto se e somente se ele ainda não
estiver contido nele.
Repetir o processo para cada nova coluna formada, até que nenhuma combinação mais seja
possı́vel.
√
√
√
√
√
000
001
100
101
110
=⇒
√
√
√
√
00X
X00
X01
10X
1X0
=⇒
X0X
54
Notas de aula de MAC0329 (2004)
• Quarto passo : Listar os implicantes primos. Os implicantes primos são aqueles que não foram
√
combinados com nenhum outro, ou seja, aqueles que não estão com a marca .
1X0 e X0X
À primeira vista, poderı́amos afirmar que a soma de todos os implicantes primos corresponde à expressão minimal da função Booleana. No entanto, existem casos em que a soma de dois ou mais
implicantes primos cobre um outro. Neste caso, este último termo é redundante, no sentido de que
ele pode ser eliminado do conjunto de implicantes primos, sem que a expressão resultante deixe de ser
equivalente à expressão original. Podemos ilustrar esta situação no seguinte exemplo.
P
Exemplo: Considere a expressão Booleana f (a, b, c) =
m(0, 1, 3, 7). Pelo algoritmo QM obtemos
os seguintes implicantes primos:
00X, 0X1 e X11.
Graficamente, estes implicantes primos (ou cubos) correspondem respectivamente aos intervalos [000, 001],
[001, 011] e [011, 111] ilustrados na figura 15(a). Note, porém, que o intervalo [001, 011] é redunX11
0X1
00X
a
b
Figura 15: Os (a) implicantes primos e uma (b) cobertura mı́nima .
dante, ou seja, a mesma expressão pode ser expressa apenas pelos implicantes primos 00X e X11
(figura 15(b)).
Portanto, o ponto central da segunda parte do algoritmo QM é o cálculo de um menor subconjunto
do conjunto de implicantes primos suficientes para cobrir2 todos os mintermos da função Booleana.
Tal conjunto é denominado uma cobertura mı́nima.
7.5.2
Cálculo de uma cobertura mı́nima
Uma cobertura mı́nima pode ser calculada com a ajuda de uma tabela denominada Tabela de Implicantes
Primos, conforme descrito a seguir (com exemplos para para a função f (x1 , x2 , x3 , x4 , x5 ) =
P
(1, 2, 3, 5, 9, 10, 11, 18, 19, 20, 21, 23, 25, 26, 27)).
1. Construir a Tabela de Implicantes Primos : no topo das colunas deve-se colocar os mintermos
de f e, à esquerda de cada linha, os implicantes primos. Os implicantes primos devem ser listados
em ordem decrescente de acordo com a sua dimensão, isto é, em ordem crescente de acordo com
o número de literais. Deve-se acrescentar uma coluna à esquerda e uma linha na parte inferior.
√
Em cada linha, marcar as colunas com quando o implicante primo da linha cobre o mintermo
da coluna.
2
Um conjunto de implicantes primos (cubos maximais) cobre um mintermo (0-cubo) se este é coberto por pelo menos
um dos implicantes primos.
55
Notas de aula de MAC0329 (2004)
1
XX01X
X10X1
0X0X1
00X01
X0101
1010X
10X11
101X1
2
√
√
√
3
√
5
9
10
√
√
√
√
11
√
√
√
18
√
19
√
20
21
23
25
26
√
√
√
√
√
27
√
√
√
√
√
√
√
√
2. Selecionar os implicantes primos essenciais : deve-se procurar na tabela as colunas que contém
√
√
apenas uma marca . A linha na qual estas colunas contém a marca
corresponde a um
implicante primo essencial. Em outras palavras, este implicante primo é o único que cobre
o mintermo da coluna e, portanto, não pode ser descartado. Então, deve-se marcar com um
asterisco (*) esta linha na coluna mais à esquerda, para indicar que este é um implicante primo
essencial. A seguir, deve-se marcar, na última linha da tabela, todas as colunas cujo mintermo
é coberto pelo implicante primo selecionado.
1
*
XX01X
X10X1
0X0X1
00X01
X0101
1010X
10X11
101X1
2
√
√
√
3
√
5
9
10
√
√
√
√
11
√
√
√
18
√
19
√
20
21
√
√
√
√
26
√
27
√
√
√
√
√
√
√
√
25
√
√
√
√
23
√
√
√
√
Deve-se repetir este processo enquanto existir uma coluna cujo mintermo não está coberto pelo
conjunto de implicantes primos selecionados até o momento e que satisfaz as condições descritas.
1
*
*
*
XX01X
X10X1
0X0X1
00X01
X0101
1010X
10X11
101X1
2
√
√
√
3
√
5
9
10
√
√
√
√
11
√
√
√
18
√
19
√
20
21
√
√
√
√
√
√
√
√
√
√
√
25
26
√
27
√
√
√
√
√
√
√
√
23
√
√
√
√
√
3. Reduzir a tabela : manter apenas as colunas correspondentes aos mintermos não cobertos pelos
implicantes primos essenciais, e as linhas correspondentes aos implicantes primos que não foram
selecionados e que cobrem pelo menos um mintermo ainda não coberto.
0X0X1
00X01
X0101
10X11
101X1
1
√
√
5
23
√
√
√
√
56
Notas de aula de MAC0329 (2004)
4. Selecionar os implicantes primos secundariamente essenciais : eliminar as linhas dominadas e as
colunas dominantes e, em seguida, selecionar os essenciais.
Eliminar colunas dominantes: Diz-se que uma coluna β na Tabela de Implicantes Primos
√
√
domina uma coluna α se e somente se β tem um
em todas as linhas em que α tem . Se β
domina α, então ela pode ser removida da tabela.
Eliminar linhas dominadas: Diz-se que uma linha A na Tabela de Implicantes Primos domina
uma outra linha B se e somente se o número de literais em A é menor que o de B, e A tem
√
√
em pelo menos todas as colunas em que B tem . Se A domina B, então existe uma forma
minimal que não utiliza o termo da linha B, ou seja, a linha B pode ser removida da tabela.
A seguir, deve-se repetir o mesmo processo do passo 2, porém os implicantes primos essenciais
serão chamados secundariamente essenciais e marcados com dois asteriscos (**), e em seguida
fazer a redução da tabela (passo 3).
**
**
0X0X1
00X01
10X11
1
√
√
5
√
√
√
23
√
√
Deve-se repetir o processo descrito neste passo até que não seja mais possı́vel fazer qualquer
eliminação ou até que a tabela fique vazia. Se a tabela não ficar vazia, a tabela restante é
chamada tabela cı́clica.
5. Aplicar o método de Petrick : este método (de busca exaustiva) pode ser utilizado para resolver
a tabela cı́clica. Ele fornece todas as possı́veis combinações dos implicantes primos restantes
que são suficientes para cobrir os mintermos restantes. Deve-se escolher dentre elas, aquela que
envolve o menor número de termos. Caso existam mais de uma nestas condições, deve-se escolher
a de custo mı́nimo (aquela que envolve menor número de literais).
Exemplo: Considere a tabela cı́clica a seguir:
0
a
b
c
d
e
f
g
0X10X
011XX
01X1X
1X0X0
00X00
X1010
X0000
√
4
√
13
√
√
15
10
√
√
√
16
√
√
√
√
√
26
√
√
Para que todos os mintermos da tabela cı́clica sejam cobertos, a seguinte expressão deve ser
verdadeira.
(e + g)(a + e)(a + b)(b + c)(c + f )(d + f )(d + g) = 1
Transformando esta expressão em soma de produtos, obtemos todas as possı́veis soluções (cada
produto é uma solução viável). Dentre os produtos, deve-se escolher aquele(s) de menor custo
(menor número de implicantes primos e implicantes com menor número de literais). (Se eu não
errei nos cálculos, as soluções são {a, c, d, e}, {b, c, d, e} e {a, c, d, g} (outros tem custo maior).
Notas de aula de MAC0329 (2004)
7.5.3
57
Pontos fracos do algoritmo QM
• o algoritmo requer que a função esteja na forma SOP canônica
• o número de implicantes primos de uma função booleana com n variáveis pode ser de ordem
exponencial. Um dos pontos fracos do algoritmo de QM é que ele calcula todos os implicantes
primos explicitamente.
7.6
Funções incompletamente especificadas
Em algumas situações, o valor de uma função para algumas entradas não são relevantes (tipicamente
porque tais entradas nunca ocorrerão na prática). Em tais situações, tanto faz se a função toma valor
0 ou 1 nessas entradas, que serão denominadas de don’t cares.
Para minimizar pelo algoritmo QM uma função incompletamente especificada, é interessante considerarmos todos os don’t cares na etapa de cálculo dos implicantes primos, pois isto aumenta a chance
de eliminarmos a quantidadde de produtos.
De forma mais genérica do que a vista anteriormente, podemos então caracterizar uma função booleana
f através dos seus conjuntos um, zero e dc (de don’t care), definidos respectivamente por f h1i = {b ∈
{0, 1}n : f (b) = 1}, f h0i = {b ∈ {0, 1}n : f (b) = 0} e f h∗i = {0, 1}n \ (f h1i ∪ f h0i).
Na parte de cálculo dos implicantes primos devem ser utilizados todos os elementos de f h1i ∪ f h∗i.
Na parte de cálculo de uma cobertura mı́nima devem ser considerados apenas os elementos de f h1i.
7.7
O algoritmo ISI
Podemos dizer que o algoritmo QM utiliza uma abordagem bottom-up para gerar todos os implicantes
primos. Outra possı́vel abordagem é a top-down, utilizada pelo ISI (Inremental splitting of intervals).
O ISI inicia o processo a partir do n-cubo e, sucessivamente, elimina os zeros da função, tomando
cuidado em representar os elementos que restam após uma eliminação através do conjunto de seus
intervalos maximais. Assim, depois de eliminar todos os zeros, os elementos restantes correspondem
aos uns (mintermos) da função, os quais estarão representados pelos intervalos maximais, ou seja,
pelos implicantes primos da função.
Para fazer paralelo com algo mais concreto, podemos pensar que o QM é aquele processo em que o
fulano constrói uma parede juntando os tijolos, enquanto o ISI é aquele em que o fulano esculpe uma
tora de madeira para obter a obra desejada.
7.7.1
Passo básico do ISI
Remover um elemento de um cubo (intervalo) e representar os elementos restantes pelos subintervalos
maximais contidos neles é a chave do algoritmo ISI.
Sejam [A, B] e [C, D] dois intervalos em {0, 1}n . A diferença de [A, B] e [C, D] é o conjunto
[A, B] \ [C, D] = {x ∈ {0, 1}n : x ∈ [A, B] e x 6∈ [C, D]}
que pode também ser expresso por [A, B] \ [C, D] = [A, B] ∩ [C, D]c .
(1)
58
Notas de aula de MAC0329 (2004)
Proposição: Sejam [A, B] e [C, D] dois intervalos de {0, 1}n cuja interseção é não-vazia. Então,
[A, B] \ [C, D] =
(2)
n
o
0
0
[A, B ] : B é elemento maximal daqueles que não contém nenhum elemento de [C, D] ∪
n
o
[A0 , B] : A0 é elemento minimal daqueles que não estão contidos em nenhum elemento de [C, D] .
A equação acima mostra como a diferença de intervalos pode ser expressa em termos da coleção de
intervalos maximais contidos na diferença.
Se dim([A, B]) = k, qualquer intervalo maximal contido na diferença tem dimensão k − 1. O número
de intervalos maximais contidos na diferença é dado por dim([A, B]) − dim([A, B] ∩ [C, D]).
Exemplo: Mostramos a seguir algumas diferenças representadas pelos intervalos maximais contidos
na diferença.
Sejam [A, B] = [000, 111] e [C, D] = [001, 111]. O número de intervalos em [A, B]\[C, D] é dim([A, B])−
dim([A, B] ∩ [C, D]) = 3 − 2 = 1 e a dimensão dos intervalos resultantes é dim([A, B]) − 1 = 3 − 1 = 2.
Veja Fig. 16.
111
111
011
101
001
010
110
100
011
001
000
101
110
010
100
000
Figura 16: [000, 111] \ [001, 111] = {[000, 110]}.
Sejam [A, B] = [000, 111] e [C, D] = [001, 011]. O número de intervalos em [A, B]\[C, D] é dim([A, B])−
dim([A, B] ∩ [C, D]) = 3 − 1 = 2 e a dimensão dos intervalos resultantes é dim([A, B]) − 1 = 3 − 1 = 2.
Veja Fig. 17.
110
111
010
011
101
110
100
011
000
111
001
010
100
001
101
110
000
100
Figura 17: [000, 111] \ [001, 011] = {[000, 110], [100, 111]}.
Sejam [A, B] = [000, 111] e [C, D] = [011, 011]. Este é o caso em que apenas um ponto do cubo é
removido. O número de intervalos em [A, B] \ [C, D] é dim([A, B]) − dim([A, B] ∩ [C, D]) = 3 − 0 = 3
e a dimensão dos intervalos resultantes é dim([A, B]) − 1 = 3 − 1 = 2. Veja Fig. 18.
59
Notas de aula de MAC0329 (2004)
110
010
100
000
111
111
011
101
001
010
110
011
101
110
100
100
000
101
001
100
000
Figura 18: [000, 111] \ [011, 011] = {[000, 110], [100, 111], [000, 101]}.
7.7.2
Um exemplo completo
Consideremos a minimização da função f (x1 , x2 , x3 ) = x1 x2 x3 + x1 x2 x3 + x1 x2 x3 + x1 x2 x3 + x1 x2 x3 .
Temos f h0i = {111, 011, 010}. A figura 19 mostra os elementos que permanecem após as sucessivas
remoções dos elementos em f h0i. Cada seta indica um passo de remoção (note que não mostramos
os intervalos maximais resultantes individualmente, mostramos os elementos restantes em negrito). A
figura 20 mostra o mesmo processo em uma estrutura de árvore. Cada nı́vel da árvore corresponde ao
resultado após um passo de remoção. Note que alguns intervalos podem ser descartados por estarem
contidos em outros.
111
011
101
110
011
101
110
001
010
100
001
010
100
000
000
001
101
110
010
100
001
110
100
000
Figura 19:
Cálculo de implicantes primos de f (f h0i
{000, 001, 100, 101, 110}). Ordem de remoção: 111, 011 e 010.
7.7.3
101
000
=
{010, 011, 111} e f h1i
=
ISI: Minimização de funções incompletamente especificadas
O algoritmo ISI remove sucessivamente os zeros do cubo inicial de forma a obter, ao final do processo,
o conjunto de todos os intervalos maximais de f h1i (i.e., implicantes primos). Se a função possui don’t
cares, então ao final do processo serão obtidos os intervalos maximais de f h1i ∪ f h∗i. No entanto,
intervalos que são formados inteiramente por elementos de f h∗i não serão necessários na etapa de
cálculo de uma cobertura mı́nima. Portanto, estes podem ser descartados, assim que são detectados
durante o processo de remoção dos zeros.
Mostramos a idéia através da sua aplicação na minimização de f , com f h0i = {010, 111}, f h1i =
{000, 001, 101} e f h∗i = {100, 011, 110}, cujo processo é ilustrado nas figuras 21 and 22.
60
Notas de aula de MAC0329 (2004)
XXX
0XX
00X
a
X0X
0X0
XX0
X0X
b
XX0
X0X
c
X00
1X0
d
Figura 20:
Cálculo de implicantes primos de f (f h0i = {010, 011, 111} e f h1i =
{000, 001, 100, 101, 110}). (a) intervalo inicial; (b) após remoção de 111 ; (c) após remoção de 011; (d)
resultado final, após remoção de 010.
Os elementos que são don’t cares são representados no diagrama de Hasse como vértices sem os cı́rculos;
cı́rculos preenchidos representam elementos de f h1i enquanto os não preenchidos representam os de
f h0i. As arestas em negrito indicam que os elementos adjacentes a ela fazem parte de um intervalo.
No inı́cio do processo, todos os elementos fazem parte do intervalo XXX. Após a remoção de 111,
três intervalos são gerados: 0XX, X0X and XX0. Nenhum deles pode ser descartado pois todos eles
contém pelo menos um elemento de f h1i. Em seguida, o elemento 010 é removido dos intervalos 0XX,
and XX0, produzindo os intervalos 00X, 0X1 and X00, 1X0, respectivamente. Os intervalos 00X and
X00 podem ser descartados pois estão contidos em X0X. O intervalo 1X0 pode ser descartado pois
não cobre nenhum elemento de f h1i. Assim, os intervalos que restam são X0X and 0X1. O segundo
será eliminado no processo de cálculo de cobertura mı́nima.
Note que a função resutante é consistente com a inicial; dos elementos em f h∗i, 011 e 110 são mapeados
para 0, e somente 100 é mapeado para 1.
111
011
101
110
001
010
100
000
011
101
110
001
010
100
000
011
101
110
100
001
011
101
100
001
000
000
Figura 21: Cálculo de implicantes primos de f (f h0i = {010, 111}, f h1i = {000, 001, 101} e f h∗i =
{100, 011, 110}).
7.8
Diferença entre QM e ISI
Ambos calculam todos os implicantes primos e depois uma cobertura mı́nima. No entanto, quando a
função possui don’t cares, o ISI tem a vantagem de não manipular explicitamente os don’t cares.
7.9
Outros algoritmos de minimização lógica 2-nı́veis
Muito esforço ocorreu nas décadas de 1980 e inı́cio da década de 1990 no sentido de se desenvolver
programas para minimização de funções com várias variáveis. O algoritmo QM é um processo de-
REFERÊNCIAS
61
XXX
0XX
00X
0X1
a
X0X
X0X
XX0
X00
b
1X0
c
Figura 22: Cálculo de implicantes primos de f (f h0i = {010, 111}, f h1i = {000, 001, 101} e f h∗i =
{100, 011, 110}).
morado e além disso utiliza muita memória, o que limita sua utilidade na prática para funções com
relativamente poucas variáveis (poucas dezenas).
Os esforços realizados foram no sentido de achar alternativas nos quais os implicantes primos não
precisassem ser calculados explicitamente, formas eficientes para se calcular uma cobertura mı́nima e
heurı́sticas eficientes.
Um dos programas mais utilizados atualmente é o ESPRESSO (desenvolvido por um grupo da Universidade de Berckley) [Brayton et al., 1984, McGreer et al., 1993]. Depois do ESPRESSO, foram
propostas outras melhorias (como o uso de BDD — Binary Decision Diagrams) por Coudert e outros [Coudert, 1994, Coudert, 1995], e mais recentemente o BOOM [Fis̃er and Hlavicka, 2003].
Referências
[Brayton et al., 1984] Brayton, R. K., Hachtel, G. D., McMullen, C. T., and Sangiovanni-Vincentelli,
A. L. (1984). Logic Minimization Algorithms for VLSI Synthesis. Kluwer Academic Publishers.
[Coudert, 1994] Coudert, O. (1994). Two-level Logic Minimization: an Overview. Integration, the
VLSI Journal, 17(2):97–140.
[Coudert, 1995] Coudert, O. (1995). Doing Two-level Minimization 100 Times Faster. In Proc. of
Symposium on Discrete Algorithms (SODA), San Francisco CA.
[Fis̃er and Hlavicka, 2003] Fis̃er, P. and Hlavicka, J. (2003). Boom - a heuristic boolean minimizer.
Computers and Informatics, 22(1):19–51.
[Hill and Peterson, 1981] Hill, F. J. and Peterson, G. R. (1981). Introduction to Switching Theory and
Logical Design. John Wiley, 3rd edition.
[Katz, 1994] Katz, R. H. (1994). Contemporary Logic Design. Benjamin Cummings.
[McGreer et al., 1993] McGreer, P. C., Sanghavi, J., Brayton, R. K., and Sangiovanni-Vincentelli,
A. L. (1993). Espresso-Signature : A New Exact Minimizer for Logic Functions. IEEE trans. on
VLSI, 1(4):432–440.
[Mendelson, 1977] Mendelson, E. (1977). Álgebra Booleana e Circuitos de Chaveamento. Mcgraw-Hill.
[Micheli, 1994] Micheli, G. D. (1994). Synthesis and Optimization of Digital Circuits. McGraw-Hill.