Repositório Digital

A- A A+

Minimização ótima de classes especiais de funções booleanas

.

Minimização ótima de classes especiais de funções booleanas

Mostrar registro completo

Estatísticas

Título Minimização ótima de classes especiais de funções booleanas
Outro título On the optimal minimization of espcial classes of Boolean functions
Autor Callegaro, Vinicius
Orientador Reis, Andre Inacio
Data 2016
Nível Doutorado
Instituição Universidade Federal do Rio Grande do Sul. Instituto de Informática. Programa de Pós-Graduação em Computação.
Assunto Funções booleanas
Microeletronica
[en] Decomposition
[en] Disjoint-support decomposition
[en] Factoring
[en] Logic synthesis
[en] Read-once
[en] Read-polarity-once
Abstract The problem of factoring and decomposing Boolean functions is Σ-complete𝑃2 for general functions. Efficient and exact algorithms can be created for an existing class of functions known as read-once, disjoint-support decomposable and read-polarity-once functions. A factored form is called read-once (RO) if each variable appears only once. A Boolean function is RO if it can be represented by an RO form. For example, the function represented by 𝐹=𝑥1𝑥2+𝑥1𝑥3𝑥4+𝑥1𝑥3𝑥5 is a RO function, since it can be factored into 𝐹=𝑥1(𝑥2+𝑥3(𝑥4+𝑥5)). A Boolean function f(X) can be decomposed using simpler subfunctions g and h, such that 𝑓(𝑋)=ℎ(𝑔(𝑋1),𝑋2) being X1, X2 ≠ ∅, and X1 ∪ X2 = X. A disjoint-support decomposition (DSD) is a special case of functional decomposition, where the input sets X1 and X2 do not share any element, i.e., X1 ∩ X2 = ∅. Roughly speaking, DSD functions can be represented by a read-once expression where the exclusive-or operator (⊕) can also be used as base operation. For example, 𝐹=𝑥1(𝑥2⊕(𝑥4+𝑥5)). A read-polarity-once (RPO) form is a factored form where each polarity (positive or negative) of a variable appears at most once. A Boolean function is RPO if it can be represented by an RPO factored form. For example the function 𝐹=𝑥1̅̅̅𝑥2𝑥4+𝑥1𝑥3+𝑥2𝑥3 is RPO, since it can factored into 𝐹=(𝑥1̅̅̅𝑥4+𝑥3)(𝑥1+𝑥2). This dissertation presents four new algorithms for synthesis of Boolean functions. The first contribution is a synthesis method for read-once functions based on a divide-and-conquer strategy. The second and third contributions are two algorithms for synthesis of DSD functions: a top-down approach that checks if there is an OR, AND or XOR decomposition based on sum-of-products, product-of-sums and exclusive-sum-of-products inputs, respectively; and a method that runs in a bottom-up fashion and is based on Boolean difference and cofactor analysis. The last contribution is a new method to synthesize RPO functions which is based on the analysis of positive and negative transition sets. Results show the efficacy and efficiency of the four proposed methods.
Resumo O problema de fatorar e decompor funções Booleanas é Σ-completo𝑃2 para funções gerais. Algoritmos eficientes e exatos podem ser criados para classes de funções existentes como funções read-once, disjoint-support decomposable e read-polarity-once. Uma forma fatorada é chamada de read-once (RO) se cada variável aparece uma única vez. Uma função Booleana é RO se existe uma forma fatorada RO que a representa. Por exemplo, a função representada por 𝐹=𝑥1𝑥2+𝑥1𝑥3𝑥4+𝑥1𝑥3𝑥5 é uma função RO, pois pode ser fatorada em 𝐹=𝑥1(𝑥2+𝑥3(𝑥4+𝑥5)). Uma função Booleana f(X) pode ser decomposta usando funções mais simples g e h de forma que 𝑓(𝑋)=ℎ(𝑔(𝑋1),𝑋2) sendo X1, X2 ≠ ∅, e X1 ∪ X2 = X. Uma decomposição disjunta de suporte (disjoint-support decomposition – DSD) é um caso especial de decomposição funcional, onde o conjunto de entradas X1 e X2 não compartilham elementos, i.e., X1 ∩ X2 = ∅. Por exemplo, a função 𝐹=𝑥1𝑥2̅̅̅𝑥3+𝑥1𝑥2𝑥3̅̅̅ 𝑥4̅̅̅+𝑥1𝑥2̅̅̅𝑥4 é DSD, pois existe uma decomposição tal que 𝐹=𝑥1(𝑥2⊕(𝑥3+𝑥4)). Uma forma read-polarity-once (RPO) é uma forma fatorada onde cada polaridade (positiva ou negativa) de uma variável aparece no máximo uma vez. Uma função Booleana é RPO se existe uma forma fatorada RPO que a representa. Por exemplo, a função 𝐹=𝑥1̅̅̅𝑥2𝑥4+𝑥1𝑥3+𝑥2𝑥3 é RPO, pois pode ser fatorada em 𝐹=(𝑥1̅̅̅𝑥4+𝑥3)(𝑥1+𝑥2). Esta tese apresenta quarto novos algoritmos para síntese de funções Booleanas. A primeira contribuição é um método de síntese para funções read-once baseado em uma estratégia de divisão-e-conquista. A segunda contribuição é um algoritmo top-down para síntese de funções DSD baseado em soma-de-produtos, produto-de-somas e soma-exclusiva-de-produtos. A terceira contribuição é um método bottom-up para síntese de funções DSD baseado em diferença Booleana e cofatores. A última contribuição é um novo método para síntese de funções RPO que é baseado na análise de transições positivas e negativas.
Tipo Tese
URI http://hdl.handle.net/10183/148342
Arquivos Descrição Formato
001002404.pdf (3.370Mb) Texto completo Adobe PDF Visualizar/abrir

Este item está licenciado na Creative Commons License

Este item aparece na(s) seguinte(s) coleção(ões)


Mostrar registro completo

Percorrer



  • O autor é titular dos direitos autorais dos documentos disponíveis neste repositório e é vedada, nos termos da lei, a comercialização de qualquer espécie sem sua autorização prévia.
    Projeto gráfico elaborado pelo Caixola - Clube de Criação Fabico/UFRGS Powered by DSpace software, Version 1.8.1.