Mostrar registro simples

dc.contributor.advisorReis, Andre Inaciopt_BR
dc.contributor.authorCallegaro, Viniciuspt_BR
dc.date.accessioned2016-09-22T02:14:28Zpt_BR
dc.date.issued2016pt_BR
dc.identifier.urihttp://hdl.handle.net/10183/148342pt_BR
dc.description.abstractThe 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.en
dc.description.abstractO 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.pt_BR
dc.format.mimetypeapplication/pdfpt_BR
dc.language.isoengpt_BR
dc.rightsOpen Accessen
dc.subjectLogic synthesisen
dc.subjectMicroeletrônicapt_BR
dc.subjectFactoringen
dc.subjectFunções booleanaspt_BR
dc.subjectDecompositionen
dc.subjectRead-onceen
dc.subjectDisjoint-support decompositionen
dc.subjectRead-polarity-onceen
dc.titleMinimização ótima de classes especiais de funções booleanaspt_BR
dc.title.alternativeOn the optimal minimization of espcial classes of Boolean functions en
dc.typeTesept_BR
dc.identifier.nrb001002404pt_BR
dc.degree.grantorUniversidade Federal do Rio Grande do Sulpt_BR
dc.degree.departmentInstituto de Informáticapt_BR
dc.degree.programPrograma de Pós-Graduação em Computaçãopt_BR
dc.degree.localPorto Alegre, BR-RSpt_BR
dc.degree.date2016pt_BR
dc.degree.leveldoutoradopt_BR


Thumbnail
   

Este item está licenciado na Creative Commons License

Mostrar registro simples