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

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.

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.