O problema de fatorar e decompor funções Booleanas é Σ-completo2 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 =12+134+135 é 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 =12̅̅̅3+123̅̅̅ 4̅̅̅+12̅̅̅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̅̅̅24+13+23 é 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. / The problem of factoring and decomposing Boolean functions is Σ-complete2 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 =12+134+135 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̅̅̅24+13+23 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.
| Identifer | oai:union.ndltd.org:IBICT/oai:lume.ufrgs.br:10183/148342 |
| Date | January 2016 |
| Creators | Callegaro, Vinicius |
| Contributors | Reis, Andre Inacio |
| Source Sets | IBICT Brazilian ETDs |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, instname:Universidade Federal do Rio Grande do Sul, instacron:UFRGS |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0035 seconds