Embed Size (px)
Citation preview
Aperfeiçoamento do método Clause-Column Table para a geração eficiente
de implicantes primos para minimização de funções booleanas.
Alexandre C. R. da Silva, Caroline D. P. N. Barbieri, Depto. de Engenharia Elétrica, FEIS, UNESP
15385-000 Ilha Solteira, SP.
E-mail: [email protected] [email protected]
Resumo: A geração de implicantes primos é um fator importante na fase de cobertura dos mintermos
em métodos minimização de funções booleanas. A minimização de função booleana é utilizada na fase
de otimização de circuitos digitais em que o critério de custo é a quantidade de variáveis e portas
lógicas. Neste trabalho aperfeiçoou-se um método de geração de implicantes primos denominado
Clause-Column Table. Este novo algoritmo adiciona um novo critério de parada ao método original,
evitando dessa forma a geração de termos nulos e iterações desnecessárias. Os estudos de casos
comprovaram que o algoritmo proposto tem um desempenho superior ao algoritmo original. Foi
comprovado que não são gerados termos nulos e consequentemente foram necessárias menos
iterações.
Palavras-chave: Minimização de função booleana, Geração de implicantes primos, Cobertura de
mintermos.
1. Introdução
A simplificação de funções booleanas é parte essencial na redução dos custos para a implementação de
circuitos digitais. O método clássico [2] é dividido em duas fases a geração de todos os implicantes
primos e a cobertura dos mintermos, obtendo dessa forma a solução de custo mínimo. Apesar do
método Quine-McCluskey gerar uma solução mínima global a complexidade do algoritmo faz com
que o tempo aumente exponencialmente com o número de variáveis de entrada. Em decorrência dessa
característica a busca por métodos de minimização de funções booleanas tem sido incessante ao longo
dos anos. Recentemente foram publicados os seguintes trabalhos [ 6, 7, 8] que buscam novas soluções
ou procuram melhorar algoritmos já existentes.
Em [4] foi desenvolvido o programa chamado Espresso que minimiza funções booleanas sem a
necessidade da geração de todos os implicantes primos. Trata-se de um método heurístico que apesar
de eficiente não garante a solução mínima global.
É importante destacar que existem inúmeros métodos de minimização, cada qual aplicando
técnicas com características diferentes. Alguns trabalhos foram desenvolvidos baseados em técnicas de
programação linear, cujas soluções mínimas são obtidas, utilizando-se de algum modelo de relaxação,
na cobertura dos mintermos [1, 3].
Alguns trabalhos recentes aprimoraram o tradicional método de Quine-McCluskey. Em [6], foi
utilizado o conceito de “Máscara de Redução” a fim de reduzir a complexidade e o tempo de execução
do algoritmo desenvolvido por Quine e McCluskey.
Neste trabalho apresenta-se um algoritmo que tem como objetivo aperfeiçoar o método de [5],
denominado “Clause-Column Table”. O método proposto evita a geração de termos nulos e utiliza-se
de menos iterações para gerar os implicantes primos. Apresenta-se nas próximas seções o método de
Clause-Column Table Aprimorado e um estudo de caso.
2. Método de minimização Clause-Column Table Aprimorado
O método Clause-Column Table é um método tabular e iterativo para a geração de implicantes primos
em que os termos da função representam as colunas da tabela. Uma função booleana pode ser
representada através dos seus mintermos ou maxtermos.
Esta forma de representação torna-se muito interessante, pois facilita o processo de geração dos
implicantes primos. Trata-se do mesmo principio utilizado na geração dos implicantes primos dos
tradicionais métodos de expansão em torno de um literal, utilizado por tantos outros métodos de
496
minimização. Entretanto o método de expansão utilizado pelo método Clause-Column é um pouco
diferente dos empregados nos métodos tradicionais o que reduz a quantidade de implicantes primos
gerados.
Ao minimizar funções utilizando o método original Clause-Column Table original, constatou-se a
geração de termos nulos e uma quantidade de iterações desnecessárias. Apesar dessa deficiência do
método não foram gerados todos os implicantes como no método de Quine-McCluskey.
No método Clause-Column Table aprimorado apresentado neste trabalho, incluiu-se um critério
de parada que evita a geração dos termos nulos diminuindo assim a quantidade de iterações
desnecessárias. Incluiu-se no algoritmo original o teorema da adjacência, ou seja, + = .
Considere a função booleana: ( ) ( ) ( ) (
) ( ) O método original gera na fase inicial a matriz apresentada a seguir. Pode-se notar que esta
matriz possui quatro colunas rotuladas por , , e que representam os maxtermos da função.
Salienta-se que as colunas e podem ser simplificadas algebricamente. O mesmo ocorre para as
colunas e . O método original não realiza esta simplificação algébrica.
(
)
O método Clause-Column Table aprimorado aplica o teorema de adjacência entre as colunas:
e ; e . Gerando dessa forma uma matriz reduzida.
(
)
Além do emprego do teorema da adjacência incluiu-se no método Clause-Column Table
aprimorado o seguinte critério de parada: “quando restar apenas uma coluna na matriz, a partir da 2ª
iteração, o algoritmo deve ser interrompido”. Dessa forma as seguintes regras foram implementadas:
Um literal que aparece isolado em uma coluna é definido como um literal essencial;
Quando uma coluna estiver contida na outra, a coluna com a maior quantidade de
literais deve ser excluída e a coluna que permanece é denominada de “coluna contida”.
3. Algoritmo para a geração de implicantes primos através do método Clause-Column
Table aprimorado
A contribuição deste artigo consiste na definição de um critério de parada inexistente no algoritmo
original conforme já salientado na seção anterior. No método original são definidos somente três
critérios de parada descritos a seguir:
Todas as colunas sejam excluídas;
Um literal torne-se essencial e na próxima iteração o seu complemento também;
Dois literais, complementados ou não, tornem-se essenciais ao mesmo tempo.
Descreve-se a seguir os passos envolvidos no método proposto. O algoritmo deve ser executado
iterativamente até que uns dos critérios de parada sejam atendidos.
1º Passo: Forme uma matriz em que cada coluna é composta por um termo da função.
2º Passo: Execute o passo 2, descrito a seguir iterativamente até que todas as colunas sejam excluídas,
caso contrário vá ao passo 3:
a) Se algum critério de parada do 6º passo é atendido, interrompa o algoritmo, caso contrário vá
ao passo seguinte;
497
b) Se houver literais essenciais, selecione-os;
c) Elimine todas as colunas que contém literais essenciais;
d) Elimine o complemento do literal essencial selecionado das colunas restantes;
e) Se houver colunas contidas, elimine-as;
f) Se existir colunas redundantes elimine aleatoriamente uma delas;
g) Simplifique as colunas restantes de acordo com o teorema de adjacência;
h) Forme uma matriz denominada de “Matriz Reduzida” composta pelas colunas restantes.
3º Passo: Se houver um literal essencial for selecionado no passo anterior execute o 5º passo, caso
contrário execute o 4º passo.
4º Passo: Verifique na Matriz Reduzida a quantidade de ocorrências de cada um dos literais na forma
complementada ou não. Se houver literais com a mesma ocorrência selecione um aleatoriamente.
5º Passo: Execute os seguintes passos:
a) Todas as colunas contendo o literal selecionado no 2º passo devem ser eliminadas;
b) O complemento do literal essencial selecionado também deve ser eliminado das demais
colunas;
c) Se na Matriz Reduzida houver mais de uma coluna, então repita o 4º passo, caso contrário
multiplique o literal selecionado por cada um dos literais restantes na coluna;
d) Os termos gerados no item anterior são definidos como implicantes primos, senão existir
colunas resultantes para multiplicação, o literal selecionado no 2º passo é o implicante primo;
6º Passo: Execute o 2º passo até que algum critério de parada seja atendido. Os critérios de parada
são:
a) Todas as colunas sejam excluídas;
b) Dois literais, complementados ou não, tornem-se essenciais ao mesmo tempo;
c) Um literal torne-se essencial e na iteração seguinte o seu complemento também;
d) Reste apenas uma coluna a partir da segunda iteração.
7º Passo: Uma vez atingido algum critério de parada reúna todos os termos obtidos no 5º passo, pois
representam implicantes primos.
Para apresentar o algoritmo proposto considere a função na forma produto de soma conforme descrito:
( ) ∏ ( )
1º Passo: Forme a expressão booleana de acordo com os maxtermos da função escolhida para
minimização: ( ) ( ) ( ) ( )
(
)
2º Passo: Analisando a matriz nota-se que nenhum dos itens do 2º passo é atendido, sendo assim
execute o 3º passo.
3º Passo: Não há literal essencial na Matriz Reduzida, então execute o 4º passo.
4º Passo: Os literais e têm a mesma ocorrência na tabela. Qualquer um deles pode ser
selecionado aleatoriamente, o literal é escolhido.
5º Passo: Eliminam-se as colunas correspondentes ao literal selecionado e multiplique-o pela
coluna restante, formando assim os implicantes primos.
498
(
)
Implicantes primos obtidos: ( + ). 6º Passo: Como nenhum critério de parada é atendido, o 2º passo deve ser executado novamente.
2º Passo: O literal selecionado na iteração anterior não volta para a tabela. Nota-se na matriz que a
coluna deve ser eliminada, pois é contida pela coluna , formando assim a Matriz Reduzida.
Na Matriz Reduzida existe um literal essencial . As colunas em que ele pertence devem ser
eliminadas e o seu complemento das demais colunas.
(
) (
)
3º Passo: Há um literal essencial na Matriz Reduzida, então executar 5º passo.
5º Passo: O literal essencial selecionado deve ser multiplicado pela coluna restante, formando assim
os implicantes primos.
( )
Implicantes primos obtidos: ( )
6º Passo: Nenhum critério de parada é atendido, execute o 2º Passo.
2º Passo: O literal selecionado na iteração anterior não volta para a tabela. Sendo assim resta apenas
uma coluna, ou seja, um dos critérios de parada é atendido e o algoritmo deve ser interrompido.
(
)
Conjunto de implicantes obtidos com a execução do algoritmo Clause-Column Table aprimorado:
( + + ).
Utiliza-se dos mesmos maxtermos da função anterior para apresentar o método original Clause-
Column Table: ( ) ∏ ( )
1º Passo: Forme a expressão booleana de acordo com os maxtermos da função escolhida para
minimização: ( ) ( ) ( ) ( )
(
)
2º Passo: Analisando a matriz nota-se que nenhum dos itens do 2º passo foi atendido, sendo assim
execute o 3º passo.
3º Passo: Não há literal essencial na Matriz Reduzida, então execute o 4º passo.
4º Passo: Os literais e têm a mesma ocorrência na tabela. Qualquer um deles pode ser
selecionado aleatoriamente, o literal é escolhido.
5º Passo: Eliminam-se as colunas correspondentes ao literal selecionado e multiplique-o pela
coluna restante, formando assim os implicantes primos.
499
(
)
Implicantes primos obtidos: ( + )
6º Passo: Como nenhum critério de parada é atendido o 2º passo deve ser executado novamente.
2º Passo: O literal selecionado na iteração anterior não volta para a tabela. Nota-se na matriz que a
coluna deve ser eliminada, pois é contida pela coluna , formando assim a Matriz Reduzida.
Na Matriz Reduzida existe um literal essencial . As colunas em que ele pertence devem ser
eliminadas e o seu complemento das demais colunas.
(
) (
)
3º Passo: Há um literal essencial na Matriz Reduzida, então executar 5º passo.
5º Passo: O literal essencial selecionado deve ser multiplicado pela coluna restante, formando assim
os implicantes primos.
( )
Implicantes primos obtidos: ( )
6º Passo: Nenhum critério de parada é atendido, execute o 2º Passo.
2º Passo: O literal selecionado na iteração anterior não volta para a tabela e nenhum item do 2º passo é
atendido.
(
)
3º Passo: Não existe literal essencial selecionado no passo anterior, então execute o 4º Passo.
4º Passo: Como resta apenas uma coluna na Matriz Reduzida, todos os literais possui a mesma
ocorrência, sendo assim qualquer um deles pode ser selecionado aleatoriamente, é selecionado o literal
. 5º Passo: A coluna em que o literal selecionado se encontra deve ser eliminada. Assim não resta
nenhuma coluna para multiplicação e o literal selecionado é o próprio implicante primo.
Implicante primo obtido: 6º Passo: Nenhum critério de parada é atendido.
2ºPasso: O literal selecionado na iteração anterior não volta para a Matriz, restando apenas o literal
essencial A coluna em que ele se encontra deve ser eliminada.
( )
3º Passo: Existe um literal essencial selecionado no passo anterior, então execute o 5º Passo.
5º Passo: Não resta nenhuma coluna para multiplicação e o literal essencial selecionado é o próprio
implicante primo. Implicante primo obtido: 6º Passo: Um dos critérios de para é atendido, pois um literal não pode tornar-se essencial e na
iteração seguinte o seu complemento também; Implicantes primos obtidos com a execução do método original Clause-Column Table: ( + + ) Nota-se com a execução do método original Clause-Column Table que foram gerados os termos nulos
como implicantes primos, ou seja, termos que não fazem parte da solução final.
500
4. Conclusão
Apresentou-se neste trabalho uma versão aprimorada do método de minimização de funções booleanas
denominado Clause-Column Table. Com a inclusão de um novo critério de parada e o emprego do
teorema de adjacência o método proposto utiliza menos iterações e evita à geração de termos nulos
que ocorria no método original.
A inclusão do novo critério de parada diminui a quantidade de iterações desnecessárias tornando
o método mais rápido e evitando a obtenção de termos nulos.
A geração de termos nulos acarreta o maior consumo de memória visto que não são candidatos a
solução final do problema de cobertura, além de, algumas vezes gerar uma solução infactível.
Os vários estudos de casos comprovaram que o método apresentado aprimorou o método Clause-
Column Table proposto por Das em 1972.
Como trabalho futuro pretende-se estudar funções com don't care states e funções com múltiplas
saídas.
Agradecimentos
Os autores agradecem ao Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq,
processo: 309023/2012-2) e ao Programa de Pós-Graduação em Engenharia Elétrica (PPGEE) da
Faculdade de Engenharia de Ilha Solteira (FEIS-UNESP).
Referências
[1] Alexandre César Rodrigues da Silva. Contribuição à síntese de circuitos digitais utilizando
programação linear inteira 0 e 1, 1993.
[2] E. McCluskey. Minimization of boolean function. The Bell System Techinal Journal,
35(6):1417{1444, 1956.
[3] F. Fallah, S. Liao, and S Devadas. Solving covering problems using lpr-based lower bounds.Very
Large Scale Integration (VLSI) Systems, IEEE Transactions on, 8(1):9{17, 2000.
[4] Robert K. Brayton, Gary D. Hachtel, and Alberto L. Sangiovanni-Vincentelli. Logic Mini-mization
Algorithms for VLSI Synthesis. Higham, USA, 1984.
[5] S.R. Das and N.S. Khabra. Clause-column table approach for generating all the prime implicants of
witching functions. IEEE Transactions on Computers, 21(11):1239{1246,1972.
[6] Tarun Kumar Jain, D. S. Kushwaha, and A. K. Misra. Optimization of the quine-mccluskey
method for the minimization of the boolean expressions. In Proceedings of the Fourth International
Conference on Autonomic and Autonomous Systems, ICAS '08, pages 165{168, Washington, DC,
USA, 2008. IEEE Computer Society.
[7] V. Minzyuk. Integers sorting method for boolean functions minimization. In Modern Problems of
Radio Engineering Telecommunications and Computer Science (TCSET), 2012 International
Conference on, pages 61{61, 2012.
[8] Yuan Lin and Ruiping Geng. Mlbm: Machine-learning-based minimization algorithm for boolean
functions. In Industrial Electronics, 2009. ISIE 2009. IEEE International Symposium on, pages
1160{1165, 2009.
501
