Orientador: Prof. Dr. Jair Donadelli Jr. / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Ciência da Computação, 2014.

Orientador: Prof. Dr. Ronaldo Cristiano Prati / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Ciência da Computação, 2014.

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.

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.

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.

A Modelagem de Sólidos vem se estabelecendo como uma área da Computação Gráfica em pleno crescimento, sendo responsável pelo tratamento de problemas envolvendo a manipulação, análise e exibição interativa de modelos computacionais de objetos sólidos. Sistemas de CAD, CAM e CAE contribuíram para a popularização do uso de diversos conceitos dessa área. Ademais, o recente advento da Realidade Virtual mostrou a importância da aplicação de tais conceitos no projeto de mundos virtuais. A intenção inicial do presente trabalho foi a de elaborar um Sistema Modelador de Sólidos completo. Contudo, um sistema de tal monta demandaria mais tempo do que o disponível, além de exigir o trabalho em conjunto de uma equipe de analistas e programadores. Assim sendo, os esforços foram aplicados na elaboração de um sistema de suporte às Operações Booleanas Regularizadas, que são o cerne da técnica CSG. Tal sistema foi projetado de forma a garantir a portibilidade necessária para permitir sua execuçãm em diversos tipos de plataformas de hardware e software. Assim sendo, o presente trabalho propõe-se a estudar, analisar e dar suporte às Operações Booleanas Regularizadas entre primitivas CSG inseridas em mundos virtuais escritos em VRML (Virtual Reality Modeling Language), que não dá suporte a tais operadores. Apresenta-se aqui uma extensão à tal linguagem, além de métodos e algoritmos utilizados para a aproximação dos sólidos através da técnica de octrees.

Algoritmos exatos para fatoração estão limitados a funções Booleanas read-once, onde cada variável aparece uma vez na equação final. No entanto, estes algoritmos apresentam duas restrições principais: (1) eles não consideram funções Booleanas incompletamente especificadas, e (2) eles não são adequados para as funções binate. Para superar o primeiro inconveniente, é proposto um algoritmo que encontra equações read-once para funções Booleanas incompletamente especificadas, sempre que possível, é proposto. Com respeito à segunda limitação, é apresentada uma transformação de domínio que divide variáveis binate existentes em duas variáveis unate independentes. Tal transformação de domínio conduz a funções Booleanas incompletamente especificadas, que podem ser eficientemente fatoradas mediante a aplicação do algoritmo proposto. A combinação das duas contribuições dá resultados ótimos para uma nova classe de funções Booleanas chamada read-polarity-once, onde cada polaridade (positiva ou negativa) de uma variável aparece no máximo uma vez na forma fatorada da expressão Booleana. Resultados experimentais sobre circuitos ISCAS'85 mostrou que funções read-polarity-once são significativamente mais frequentes em circuitos reais quando comparado com a classe de funções read-once, a qual muitos trabalhos já foram dedicados na literatura. / Efficient exact factoring algorithms are limited to read-once functions, in which each variable appears once in the final Boolean equation. However, those algorithms present two main constraints: (1) they do not consider incompletely specified Boolean functions; and (2) they are not suitable for binate functions. To overcome the first drawback, it is proposed an algorithm that finds read-once formulas for incompletely specified Boolean functions, whenever possible. With respect to the second limitation, a domain transformation that splits existing binate variables into two independent unate variables is presented. Such domain transformation leads to incompletely specified Boolean functions, which can be efficiently factored by applying the proposed algorithm. The combination of both contributions gives optimal results for a novel broader class of Boolean functions named as read-polarity-once functions, where each polarity (positive or negative) of a variable appears at most once in the factored form. Experimental results over ISCAS'85 benchmark circuits have shown that read-polarityonce functions are significantly more frequent than read-once functions, for which many works have already been devoted in the literature.

Submitted by JULIANA DE FÁTIMA FRANCISCANI null (ifsp.juliana@gmail.com) on 2016-10-28T18:39:46Z No. of bitstreams: 1 Juliana de Fátima Franciscani.pdf: 3657600 bytes, checksum: dfdbe82d43ba74271de101385cdbbf6e (MD5) / Approved for entry into archive by Felipe Augusto Arakaki (arakaki@reitoria.unesp.br) on 2016-11-03T19:07:45Z (GMT) No. of bitstreams: 1 franciscani_jf_me_ilha.pdf: 3638504 bytes, checksum: 6ca7f15a8be8ef019afd3f8e0ecc1e52 (MD5) / Made available in DSpace on 2016-11-03T19:07:45Z (GMT). No. of bitstreams: 1 franciscani_jf_me_ilha.pdf: 3638504 bytes, checksum: 6ca7f15a8be8ef019afd3f8e0ecc1e52 (MD5) Previous issue date: 2016-08-31 / Com a evolução e difusão do desenvolvimento de equipamentos utilizando microtecnologia e nanotecnologia, circuitos cada vez menores, mais eficientes e que consomem menos energia, são necessários. Os métodos de minimização de funções booleanas tornam-se relevantes por possibilitarem a otimização de circuitos lógicos, através da geração de circuitos que possuam a mesma funcionalidade, porém, minimizados. Estudos na área de minimização de funções booleanas são realizados há muito tempo, e estão sendo adaptados às novas tecnologias. A geração de implicantes primos de uma função booleana é um dos passos para a cobertura dos mintermos da função e, consequentemente, para a obtenção da função de custo mínimo. Neste trabalho, a Primeira Fase do Método de Quine-McCluskey para Funções Booleanas com Múltiplas Saídas (QMM) foi implementada para posterior comparação com os Métodos Propostos GPMultiplo e MultiGeraPlex (baseados na filosofia do algoritmo GeraPlex). Os métodos propostos geram os implicantes primos de uma função booleana com múltiplas saídas e utilizam a operação de consenso iterativo para comparar dois termos. Os resultados obtidos, através da comparação do GPMultiplo, MultiGeraPlex e da Primeira Fase do Método de QMM, puderam comprovar que a aplicação dos métodos propostos torna-se mais viável e vantajosa por permitir menor tempo de execução e uso de memória, menor quantidade de implicantes gerados e de comparações entre os termos. / With the evolution and spread of the development of equipment using microtechnology and nanotechnology, circuits in need are smaller, more efficient and consume less power. Methods of Minimizing Boolean Functions become important as they allow optimization of logic circuits by generating circuits having the same functionality, but minimized. Studies in Minimizing Boolean Functions area are carried out long ago, and are being adapted to new technologies. The generation of prime implicants of a Boolean function is one of the steps for covering the function of the minterms, and consequently to obtain the minimum cost function. In this work, the first phase of the Quine-McCluskey Method for Booleans Functions with Multiple Output (QMM) was implemented for comparison with Proposed Methods GPMultiplo and MultiGeraPlex (based on the philosophy of GeraPlex algorithm). The proposed methods generates the prime implicants of a Boolean Function with Multiple Output and using the iterative consensus operation to compare two terms. The results obtained by comparing the GPMultiplo, MultiGeraPlex and the first phase of the QMM Method, were able to prove that the application of the proposed methods becomes more feasible and advantageous, by allowing smaller execution time, number of implicants and number of comparisons.

Orientador: Alexandre Cesar Rodrigues Silva / Resumo: Com a evolução e difusão do desenvolvimento de equipamentos utilizando microtecnologia e nanotecnologia, circuitos cada vez menores, mais eficientes e que consomem menos energia, são necessários. Os métodos de minimização de funções booleanas tornam-se relevantes por possibilitarem a otimização de circuitos lógicos, através da geração de circuitos que possuam a mesma funcionalidade, porém, minimizados. Estudos na área de minimização de funções booleanas são realizados há muito tempo, e estão sendo adaptados às novas tecnologias. A geração de implicantes primos de uma função booleana é um dos passos para a cobertura dos mintermos da função e, consequentemente, para a obtenção da função de custo mínimo. Neste trabalho, a Primeira Fase do Método de Quine-McCluskey para Funções Booleanas com Múltiplas Saídas (QMM) foi implementada para posterior comparação com os Métodos Propostos GPMultiplo e MultiGeraPlex (baseados na filosofia do algoritmo GeraPlex). Os métodos propostos geram os implicantes primos de uma função booleana com múltiplas saídas e utilizam a operação de consenso iterativo para comparar dois termos. Os resultados obtidos, através da comparação do GPMultiplo, MultiGeraPlex e da Primeira Fase do Método de QMM, puderam comprovar que a aplicação dos métodos propostos torna-se mais viável e vantajosa por permitir menor tempo de execução e uso de memória, menor quantidade de implicantes gerados e de comparações entre os termos. / Mestre

Algoritmos exatos para fatoração estão limitados a funções Booleanas read-once, onde cada variável aparece uma vez na equação final. No entanto, estes algoritmos apresentam duas restrições principais: (1) eles não consideram funções Booleanas incompletamente especificadas, e (2) eles não são adequados para as funções binate. Para superar o primeiro inconveniente, é proposto um algoritmo que encontra equações read-once para funções Booleanas incompletamente especificadas, sempre que possível, é proposto. Com respeito à segunda limitação, é apresentada uma transformação de domínio que divide variáveis binate existentes em duas variáveis unate independentes. Tal transformação de domínio conduz a funções Booleanas incompletamente especificadas, que podem ser eficientemente fatoradas mediante a aplicação do algoritmo proposto. A combinação das duas contribuições dá resultados ótimos para uma nova classe de funções Booleanas chamada read-polarity-once, onde cada polaridade (positiva ou negativa) de uma variável aparece no máximo uma vez na forma fatorada da expressão Booleana. Resultados experimentais sobre circuitos ISCAS'85 mostrou que funções read-polarity-once são significativamente mais frequentes em circuitos reais quando comparado com a classe de funções read-once, a qual muitos trabalhos já foram dedicados na literatura. / Efficient exact factoring algorithms are limited to read-once functions, in which each variable appears once in the final Boolean equation. However, those algorithms present two main constraints: (1) they do not consider incompletely specified Boolean functions; and (2) they are not suitable for binate functions. To overcome the first drawback, it is proposed an algorithm that finds read-once formulas for incompletely specified Boolean functions, whenever possible. With respect to the second limitation, a domain transformation that splits existing binate variables into two independent unate variables is presented. Such domain transformation leads to incompletely specified Boolean functions, which can be efficiently factored by applying the proposed algorithm. The combination of both contributions gives optimal results for a novel broader class of Boolean functions named as read-polarity-once functions, where each polarity (positive or negative) of a variable appears at most once in the factored form. Experimental results over ISCAS'85 benchmark circuits have shown that read-polarityonce functions are significantly more frequent than read-once functions, for which many works have already been devoted in the literature.