Dissertations / Theses on the topic 'Circuit booléen'
To see the other types of publications on this topic, follow the link: Circuit booléen.
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Circuit booléen.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Soyez-Martin, Claire. "From semigroup theory to vectorization : recognizing regular languages." Electronic Thesis or Diss., Université de Lille (2022-....), 2023. http://www.theses.fr/2023ULILB052.
Abstract:
L'évaluation efficace des expressions régulières constitue un défi persistant depuis de nombreuses décennies. Au fil du temps, des progrès substantiels ont été réalisés grâce à une variété d'approches, allant de nouveaux et ingénieux algorithmes à des optimisations complexes de bas niveau.Les outils de pointe de ce domaine utilisent ces techniques d'optimisation, et repoussent constamment les limites de leur efficacité. Une avancée notoire réside dans l'intégration de la vectorisation, qui exploite une forme de parallélisme de bas niveau pour traiter l'entrée par blocs, entraînant ainsi d'importantes améliorations de performances. Malgré une recherche approfondie sur la conception d'algorithmes sur mesure pour des tâches particulières, ces solutions manquent souvent de généralisabilité, car la méthodologie sous-jacente à ces algorithmes ne peut pas être appliquée de manière indiscriminée à n'importe quelle expression régulière, ce qui rend difficile son intégration dans les outils existants.Cette thèse présente un cadre théorique permettant de générer des programmes vectorisés particuliers capables d'évaluer les expressions régulières correspondant aux expressions rationnelles appartenant à une classe logique donnée. L'intérêt de ces programmes vectorisés vient de l'utilisation de la théorie algébrique des automates, qui offre certains outils algébriques permettant de traiter les lettres en parallèle. Ces outils permettent également d'analyser les langages réguliers plus finement, offrent accès à des optimisations des programmes vectorisés basées sur les propriétés algébriques de ces langages. Cette thèse apporte des contributions dans deux domaines. D'une part, nous présentons des implémentations et des benchmarks préliminaires, afin d'étudier les possibilités offertes par l'utilisation de l'algèbre et de la vectorisation dans les algorithmes d'évaluation des expressions régulières. D'autre part, nous proposons des algorithmes capables de générer des programmes vectorisés reconnaissant les langages appartenant à deux classes d'expressions rationnelles, la logique du premier ordre et sa restriction aux formules utilisant au plus deux variablesThe pursuit of optimizing regular expression validation has been a long-standing challenge,spanning several decades. Over time, substantial progress has been made through a vast range of approaches, spanning from ingenious new algorithms to intricate low-level optimizations.Cutting-edge tools have harnessed these optimization techniques to continually push the boundaries of efficient execution. One notable advancement is the integration of vectorization, a method that leverage low-level parallelism to process data in batches, resulting in significant performance enhancements. While there has been extensive research on designing handmade tailored algorithms for particular languages, these solutions often lack generalizability, as the underlying methodology cannot be applied indiscriminately to any regular expression, which makes it difficult to integrate to existing tools.This thesis provides a theoretical framework in which it is possible to generate vectorized programs for regular expressions corresponding to rational expressions in a given class. To do so, we rely on the algebraic theory of automata, which provides tools to process letters in parallel. These tools also allow for a deeper understanding of the underlying regular language, which gives access to some properties that are useful when producing vectorized algorithms. The contribution of this thesis is twofold. First, it provides implementations and preliminary benchmarks to study the potential efficiency of algorithms using algebra and vectorization. Second, it gives algorithms that construct vectorized programs for languages in specific classes of rational expressions, namely the first order logic and its subset restricted to two variables
2
Paperman, Charles. "Circuits booléens, prédicats modulaires et langages réguliers." Paris 7, 2014. http://www.theses.fr/2014PA077258.
Abstract:
La conjecture de Straubing, énoncée dans son livre publié en 1994, suggère qu'un langage régulier définissable par un fragment logique équipé d'une signature arbitraire, est définissable par le même fragment logique mais équipé d'une signature régulière. Les fragments logiques considérés sont des classes de férmules de la logique monadique du second ordre sur les mots finis. Cette thèse est une contribution à l'étude de le conjecture de Straubing. Pour prouver une telle conjecture, il semble nécessaire pour établir cette conjecture de prouver deux résultats de natures différentes : 1. Des caractérisations algébriques de classes de langages réguliers définies par des fragments logiques équipés de prédicats réguliers, 2. Des résultats de non-définissabilité de langages réguliers dans des fragments logiques équipés de prédicats numériques arbitraires. La première partie de cette thèse est dédiée à l'ajout des prédicats réguliers à un fragment logique et en particulier, celui des prédicats modulaires lorsque les fragments logiques disposent de structures algébriques. La seconde partie de cette thèse est dédiée à des résultats de non définissablité, et en particulier l'étude du fragment à deux variables de la logique du premier ordreThe Straubing conjecture, stated in his book published in 1994, suggest that a regular language definable by a fragment of logic and equipped with an arbitrary numerical signature is definable using the same fragment of logic using only regular predicates. The considered fragments of logic are classed of formulas of monadic second order logic over finite words. This thesis is a contribution to the study of the Straubing conjecture. To prove such a conjecture, it seems necessary to obtain two results of two distinct types: 1. Algebraic characterizations of classes of regular languages defined by fragments of logics equipped with regular predicates, 2. Undefinability results of regular languages in fragments of logics equipped with arbitrary numerical predicates. The first part of this thesis is dedicated to the operation of adding regular predicates to a given fragment of logic, with a particular focus on modular predicates in the case where logical fragments have some algebraic structure. The second par of this thesis is dedicated to undefinability results with a particular focus on two-variable first order logic
3
Daitch, Samuel Isaac. "Translating alloy using Boolean circuits." Thesis, Massachusetts Institute of Technology, 2004. http://hdl.handle.net/1721.1/33129.
Abstract:
Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2004.Includes bibliographical references (p. 71-72).
Alloy is a automatically analyzable modelling language based on first-order logic. An Alloy model can be translated into a Boolean formula whose satisfying assignments correspond to instances in the model. Currently, the translation procedure mechanically converts each piece of the Alloy model individually into its most straightforward Boolean representation. This thesis proposes a more efficient approach to translating Alloy models. The key is to take advantage of the fact that an Alloy model contains patterns that are used repeatedly. This makes it natural to give a model a more structured Boolean representation, namely a Boolean circuit. Reusable pieces in the model correspond to circuit components. By identifying the most frequently used components and optimizing their corresponding Boolean formulas, the size of the overall formula for the model would be reduced without significant additional work. A smaller formula would potentially decrease the time required to determine satisfiability, resulting in faster analysis overall.
by Samuel Isaac Daitch.
M.Eng.
4
Shi, Junhao. "Boolean techniques in testing of digital circuits." [S.l.] : [s.n.], 2006. http://deposit.ddb.de/cgi-bin/dokserv?idn=98361816X.
5
Chattopadhyay, Arkadev. "Circuits, communication and polynomials." Thesis, McGill University, 2008. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=115660.
Abstract:
In this thesis, we prove unconditional lower bounds on resources needed to compute explicit functions in the following three models of computation: constant-depth boolean circuits, multivariate polynomials over commutative rings and the 'Number on the Forehead' model of multiparty communication. Apart from using tools from diverse areas, we exploit the rich interplay between these models to make progress on questions arising in the study of each of them.Boolean circuits are natural computing devices and are ubiquitous in the modern electronic age. We study the limitation of this model when the depth of circuits is fixed, independent of the length of the input. The power of such constant-depth circuits using gates computing modular counting functions remains undetermined, despite intensive efforts for nearly twenty years. We make progress on two fronts: let m be a number having r distinct prime factors none of which divides ℓ. We first show that constant depth circuits employing AND/OR/MODm gates cannot compute efficiently the MAJORITY and MODℓ function on n bits if 'few' MODm gates are allowed, i.e. they need size nW&parl0;1s&parl0;log n&parr0;1/&parl0;r-1&parr0;&parr0; if s MODm gates are allowed in the circuit. Second, we analyze circuits that comprise only MOD m gates, We show that in sub-linear size (and arbitrary depth), they cannot compute AND of n bits. Further, we establish that in that size they can only very poorly approximate MODℓ.
Our first result on circuits is derived by introducing a novel notion of computation of boolean functions by polynomials. The study of degree as a resource in polynomial representation of boolean functions is of much independent interest. Our notion, called the weak generalized representation, generalizes all previously studied notions of computation by polynomials over finite commutative rings. We prove that over the ring Zm , polynomials need Wlogn 1/r-1 degree to represent, in our sense, simple functions like MAJORITY and MODℓ. Using ideas from arguments in communication complexity, we simplify and strengthen the breakthrough work of Bourgain showing that functions computed by o(log n)-degree polynomials over Zm do not even correlate well with MODℓ.
Finally, we study the 'Number on the Forehead' model of multiparty communication that was introduced by Chandra, Furst and Lipton [CFL83]. We obtain fresh insight into this model by studying the class CCk of languages that have constant k-party deterministic communication complexity under every possible partition of input bits among parties. This study is motivated by Szegedy's [Sze93] surprising result that languages in CC2 can all be extremely efficiently recognized by very shallow boolean circuits. In contrast, we show that even CC 3 contains languages of arbitrarily large circuit complexity. On the other hand, we show that the advantage of multiple players over two players is significantly curtailed for computing two simple classes of languages: languages that have a neutral letter and those that are symmetric.
Extending the recent breakthrough works of Sherstov [She07, She08b] for two-party communication, we prove strong lower bounds on multiparty communication complexity of functions. First, we obtain a bound of n O(1) on the k-party randomized communication complexity of a function that is computable by constant-depth circuits using AND/OR gates, when k is a constant. The bound holds as long as protocols are required to have better than inverse exponential (i.e. 2-no1 ) advantage over random guessing. This is strong enough to yield lower bounds on the size of an important class of depth-three circuits: circuits having a MAJORITY gate at its output, a middle layer of gates computing arbitrary symmetric functions and a base layer of arbitrary gates of restricted fan-in.
Second, we obtain nO(1) lower bounds on the k-party randomized (bounded error) communication complexity of the Disjointness function. This resolves a major open question in multiparty communication complexity with applications to proof complexity. Our techniques in obtaining the last two bounds, exploit connections between representation by polynomials over teals of a boolean function and communication complexity of a closely related function.
6
Boyd, Mark J. "Complexity analysis of a massive parallel boolean satisfiability implication circuit /." Diss., Digital Dissertations Database. Restricted to UC campuses, 2005. http://uclibs.org/PID/11984.
7
PELADEAU, PIERRE. "Classes de circuits booleens et varietes de monoides." Paris 6, 1990. http://www.theses.fr/1990PA066265.
Abstract:
Ce travail porte sur l'etude de la complexite du calcul parallele dans le modele des circuits booleens et ses liens avec la classification algebrique des monoides finis. Barrington a montre qu'un langage est reconnu par une suite de circuits nc#1 ssi il est reconnu par une suite de programmes de longueur polynomiale sur un monoide fini. Ceci nous permet d'utiliser la classification algebrique des monoides finis, en termes de varietes, afin d'etudier la structure interne de la classe nc#1. Nous donnons des caracterisations algebriques detaillees des sous-classes de nc#1, reliant plus precisement la nature des portes et la profondeur des circuits a la complexite des varietes de monoides. Contrairement a la reconnaissance par morphismes, deux varietes distinctes de monoides peuvent, avec des programmes de longueur polynomiale, reconnaitre la meme classe de langages. Ceci nous amene, a travers une etude des proprietes du probleme du mot, a definir une nouvelle division entre monoides finis et une nouvelle notion de variete de monoides finis, adaptee a la reconnaissance par programmes. A l'aide de cette notion, nous demontrons que pour toutes les classes de circuits (sauf une) contenues dans nc#1, si deux classes sont separables, alors elles sont separees par un langage rationnel. Les classes de complexite a l'interieur de nc#1 ont egalement des caracterisations en logique, tout comme les langages rationnels. La seule difference est l'utilisation de predicats numeriques non-uniformes dans le cas des circuits, un predicat numerique etant un predicat qui definit un sous-ensemble de n#k. Nous demontrons qu'il existe une unique classe maximale de predicats numeriques telle que les langages, definis par des formules n'utilisant que des predicats numeriques de cette classe, sont rationnels. Ce resultat, avec les caracterisations algebriques, permet d'enoncer une conjecture tres forte concernant
8
Bowen, Richard Strong. "Minimal Circuits for Very Incompletely Specified Boolean Functions." Scholarship @ Claremont, 2010. https://scholarship.claremont.edu/hmc_theses/18.
Abstract:
In this report, asymptotic upper and lower bounds are given for the minimum number of gates required to compute a function which is only partially specified and for which we allow a certain amount of error. The upper and lower bounds match. Hence, the behavior of these minimum circuit sizes is completely (asymptotically) determined.
9
Barato, Matteo. "Sulla Conversione di Circuiti Booleani in Circuiti Quantistici." Bachelor's thesis, Alma Mater Studiorum - Università di Bologna, 2018.
10
Sengupta, Rimli. "Lower bounds for natural functions in restricted boolean circuits." Diss., Georgia Institute of Technology, 1995. http://hdl.handle.net/1853/8269.
11
Younes, Ahmed. "Practical search algorithms and Boolean circuits for quantum computers." Thesis, University of Birmingham, 2004. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.409283.
12
Krischer, Stefan. "Méthodes de vérification de circuits digitaux." Vandoeuvre-les-Nancy, INPL, 1994. http://www.theses.fr/1994INPL043N.
Abstract:
Cette thèse propose des outils pour la vérification formelle de la correction de circuits matériels. Pour la vérification de la correction d'un circuit combinatoire par rapport a sa spécification, une nouvelle méthode pour spécifier des fonctions booléennes est présentée, les systèmes de réécriture booléens (BTRS), puis une transformation d'un BTRS en deux expressions booléennes est décrite qui permet de vérifier la correction, la complétude et la cohérence d'une spécification par rapport a une implémentation. Pour la vérification de circuits séquentiels, deux nouveaux algorithmes qui décident l'équivalence et l'inclusion de deux machines de mealy sont introduits. Ces problèmes de décision peuvent aussi être vus comme cas spécifiques de la vérification d'un invariant d'une machine, a savoir la machine produit. Un survol uniforme et généralise sur les méthodes d'itération de point fixe décrit l'analyse de l'atteignabilité d'une machine et le test de la non-atteignabilité d'un ensemble d'états. Ces algorithmes de test d'équivalence et d'inclusion sont implémentes dans le logiciel fancy. Finalement, les applications en preuve de circuits des démonstrateurs de théorèmes généraux sont explorées. Une méthode de description et de preuve des circuits paramètres combinatoires ou séquentiels par des systèmes de réécriture est présentée. Différentes sortes de preuves qui ont besoin de telles descriptions sont montrées: par réécriture (prouveurs lp ou reve), par induction (lp), par consistance (reve), par des ensembles tests (spike)
13
Mahooti, Rabe'eh. "A CMOS circuit generator using differential pass transistors for implementing Boolean functions." PDXScholar, 1988. https://pdxscholar.library.pdx.edu/open_access_etds/3805.
Abstract:
This study uses differential pass transistor methodology for implementing and evaluating Boolean functions. The main goal is investigation of CMOS and nMOS approaches in pass transistor logic design. Pass-transistor logic is most effective in the implementation of Boolean functions when the vectors are in the same format. It has been demonstrated that nMOS pass transistor logic driven by a control signal voltage above the V dd level offers a significant improvement in speed. nMOS pass transistorsalso offer less area consumption in comparison to the CMOS approach.
The philosophy developed here has been used in the design of a program for the layout generation of pass transistor networks. This program has been applied to the design of a 4-to-1 multiplexer and an adder (sum and carry). The layout of the circuit sub-cell have been done using the program Magic, based on 3μ CMOS p-well technology.
14
Morizumi, Hiroki. "Studies on lower bounds for the size of Boolean circuits." 京都大学 (Kyoto University), 2007. http://hdl.handle.net/2433/135983.
15
Hacker, Charles Hilton, and n/a. "WinLogiLab - A Computer-Based Teaching Suite for Digital Logic Design." Griffith University. School of Engineering, 2001. http://www4.gu.edu.au:8080/adt-root/public/adt-QGU20050915.172404.
Abstract:
This thesis presents an interactive computerised teaching suite developed for the design of combinatorial and sequential logic circuits. This suite fills a perceived gap in the currently available computer-based teaching software for digital logic design. Several existing digital logic educational software are available, however these existing programs were found to be unsuitable for our use in providing alternative mode subject delivery. This prompted the development of a Microsoft Windows TM tutorial suite, called WinLogiLab. WinLogiLab comprises of a set of tutorials that uses student provided input data, to perform the initial design steps for digital Combinatorial and Sequential logic circuits. The combinatorial tutorials are designed to show the link between Boolean Algebra and Digital Logic circuits, and follows the initial design steps: from Boolean algebra, truth tables, to Exact and the Heuristic minimisation techniques, to finally produce the combinatorial circuit. Similarly, the sequential tutorials can design simple State Machine Counters, and can model more complex Finite State Automata.
16
Hacker, Charles. "WinLogiLab - A Computer-Based Teaching Suite for Digital Logic Design." Thesis, Griffith University, 2001. http://hdl.handle.net/10072/367209.
Abstract:
This thesis presents an interactive computerised teaching suite developed for the design of combinatorial and sequential logic circuits. This suite fills a perceived gap in the currently available computer-based teaching software for digital logic design. Several existing digital logic educational software are available, however these existing programs were found to be unsuitable for our use in providing alternative mode subject delivery. This prompted the development of a Microsoft Windows TM tutorial suite, called WinLogiLab. WinLogiLab comprises of a set of tutorials that uses student provided input data, to perform the initial design steps for digital Combinatorial and Sequential logic circuits. The combinatorial tutorials are designed to show the link between Boolean Algebra and Digital Logic circuits, and follows the initial design steps: from Boolean algebra, truth tables, to Exact and the Heuristic minimisation techniques, to finally produce the combinatorial circuit. Similarly, the sequential tutorials can design simple State Machine Counters, and can model more complex Finite State Automata.Thesis (Masters)
Master of Philosophy (MPhil)
School of Engineering
Science, Environment, Engineering and Technology
Full Text
17
Vora, Rohit H. "An Algorithm for multi-output Boolean logic minimization." Thesis, Virginia Tech, 1987. http://hdl.handle.net/10919/43829.
Abstract:
A new algorithm is presented for a guaranteed absolute minimal solution to the problem of Boolean Logic Minimization in its most generalized form of multi-output function with arbitrary cost criterion.
The proposed algorithm is shown to be tighter than the Quine-McCluskey method in its ability to eliminate redundant prime implicants, making it possible to simplify the cyclic tables. In its final form, the proposed algorithm is truly concurrent in generation of prime implicants and construction of minimal forms. A convenient and efficient technique is used for identifying existing prime implicants. Branch-and-bound method is employed to restrict the search tree to a cost cut-off value depending on the definition of cost function specified.
A most generalized statement of the algorithm is formulated for manual as well as computer implementation and its application is illustrated with an example. A program written in Pascal, for classical diode-gate cost function as well as PLA-area cost function, is developed and tested for an efficient computer implementation. Finally, various advantages of the proposed approach are pointed out by comparing it with the classical approach of Quine-McCluskey method.Master of Science
18
Chakrapani, Lakshmi Narasimhan. "Probabilistic boolean logic, arithmetic and architectures." Diss., Atlanta, Ga. : Georgia Institute of Technology, 2008. http://hdl.handle.net/1853/26706.
Abstract:
Thesis (Ph.D)--Computing, Georgia Institute of Technology, 2009.Committee Chair: Palem, Krishna V.; Committee Member: Lim, Sung Kyu; Committee Member: Loh, Gabriel H.; Committee Member: Mudge, Trevor; Committee Member: Yalamanchili, Sudhakar. Part of the SMARTech Electronic Thesis and Dissertation Collection.
19
Abouzeid, Pierre. "Méthodes de factorisation algébrique dédiées aux circuits intégrés complexes." Phd thesis, Grenoble INPG, 1992. http://tel.archives-ouvertes.fr/tel-00341574.
Abstract:
Cette thèse propose des méthodes de synthèse dédiées aux circuits intégrés complexes. Elle concerne l'étape de factorisation algébrique dont le but est de réduire la complexité des expressions booléennes évaluées en terme de littéraux. Les méthodes classiques proposées généralement, amènent une bonne minimisation de la surface active mais peuvent entrainer un mauvais contrôle de la connectique. Cette thèse présente d'abord un état de l'art critique sur les techniques de factorisation algébrique poussées incluant les techniques dites booléennes. Dans les chapitres suivants, deux approches alternatives de factorisation plus restreintes sont proposées. La première est réduite a une division par conoyaux et la deuxième concerne une factorisation dite lexicographique encore plus restrictive, dont le but est de préparer une connectique simplifiée. Les résultats expérimentaux ont permis de définir à partir de quel seuil de complexité, il convient d'appliquer ces deux méthodes pour obtenir une bonne surface globale ainsi qu'un bon facteur de routage
20
Vuillod, Patrick. "Optimisation et décomposition technologique de circuits intégrés à faible consommation." Grenoble INPG, 1997. http://www.theses.fr/1997INPG0096.
Abstract:
Cette these se situe dans le domaine de la synthese automatique de circuits integres. Elle se consacre a la minimisation de la puissance dissipee qui est maintenant un critere d'optimisation aussi important que la surface ou la vitesse. En effet, les appareils portatifs ont envahi le marche de la micro-electronique. Ils exigent une consommation de puissance faible tout en conservant des criteres de performance eleves. Nous proposons une methode d'optimisation au niveau des reseaux de cellules standard. Elle resout la selection et l'identification des cellules de bibliotheque par le calcul de formules booleennes. Elle est completement symbolique par opposition aux methodes structurelles utilisant des graphes. Elle generalise les methodes existantes d'identification booleenne pour des fonctions a plusieurs sorties. On l'a appelee identification generale. Nous l'avons mis en pratique dans un outil de minimisation de la puissance dissipee sous contraintes de vitesse. Cet outil prend un reseau de portes optimise pour la vitesse et reduit sa consommation en conservant la frequence originale. Notre optimisation allie les techniques de reconnexion, de redimensionnement et de permutation des connecteurs des cellules. De plus, l'identification de fonctions a plusieurs sorties permet des simplifications que les methodes classiques ne detectent pas. Nous avons obtenu de tres bons resultats sur une large gamme de circuits, en moyenne 22% de reduction, et plus de 25% pour les gros circuits. Parallelement a cet outil, nous avons egalement propose une methode originale d'optimisation du pic de courant dans les elements sequentiels des microprocesseurs qui utilise le decalage des horloges.
21
Li, Witharana Wing Kar. "Non-Boolean characterization of Homer1a intranuclear transcription foci." Thesis, Lethbridge, Alta. : University of Lethbridge, Dept. of Neuroscience, c2011, 2011. http://hdl.handle.net/10133/3402.
Abstract:
Activity-induced immediate-early gene (IEG) transcription foci can be labelled with fluorescent probes, permitting high temporal and spatial resolution in mapping neuronal circuits. Previous quantification approaches have assumed a Boolean function of transcription foci, assuming that cells are either active or inactive. Due to multiple amplification steps in the in situ hybridization process, it was thought that information relating to magnitudes of firing rates was lost. However, the current data suggest that transcription foci actually exhibit non-Boolean intensity and size values which vary according to behavioural condition. Systematic characterization of transcription foci intensity and size revealed incremental variations such that: home-cage < one-environment exposure < five-environment exposure < maximal electroconvulsive shock. Visual differences in transcription foci may result from a quantifiable relationship between spiking patterns and transcription rates. The exact stoichiometry between neuronal spiking and transcription is not yet clear, but these results suggest that Boolean applications of IEG imaging may neglect accurate neuronal activation properties.xvi, 125 leaves : ill. ; 29 cm
22
Amoura, Aadil. "Synthese logique sur reseaux programmables de type FPGA et CPLD." Grenoble INPG, 1998. http://www.theses.fr/1998INPG0158.
Abstract:
Cette these se situe dans le cadre de la synthese logique. L'objectif de ce travail est de resoudre des problemes fondamentaux de la synthese logique sur les reseaux programmables de type fpga et cpld, lies a la decomposition technologique et a la prediction temporelle sur ce type de boitiers. La premiere partie du travail s'interesse aux techniques de decomposition technologique permettant un ciblage heterogene sur les reseaux programmables de type fpga. Nous partons des techniques classiques, puis sont proposees des alternatives basees sur le principe de couverture des nuds et la decomposition de roth&karp. Nous presentons en outre des methodes de bi-decomposition booleenne en utilisant les operateurs logiques or et xor. Ces methodes sont particulierement interessantes pour permettre une meilleure exploitation des ressources des nouveaux cplds ainsi que les differentes configurations des blocs logiques des nouveaux fpgas. La derniere partie traite de la prediction temporelle sur des cibles hierarchiques. La modelisation des circuits en utilisant les structures de cones logiques, et leur classification temporelle permet d'orienter un decoupage du plan de masse, lequel guidera les outils de placement et routage.
23
Nguyen, Thiep V. "Test generation for detecting multiple stuck faults in synchronous sequential circuits using Boolean difference and transition matrix techniques." Thesis, University of Ottawa (Canada), 1993. http://hdl.handle.net/10393/6670.
Abstract:
The Boolean difference is a mathematical concept which has proved its usefulness in the study of single and multiple stuck-at faults in combinational circuits. This tool of analysis was extended to cover multiple stuck-at faults in synchronous sequential circuits as well. In this dissertation, modifications to previous work are presented, together with the development of a new method for deriving the required shortest test sequence to detect a specified multiple fault. First, the vector Boolean difference technique is utilized to determine the input vector that will produce a difference in output between the fault-free and faulty circuits with both starting in the same initial state. If that detection cannot be achieved immediately, then the state transition matrices of both circuits are combined and used to form a matrix of detecting state pairs. Each of these pairs comprises of the present states of both circuits for which an output difference will be detected by an input vector. The detecting tree is then built leading the two circuits from the same initial state to the first detecting state found to complete the search for the shortest test sequence. Besides being able to identify, at an early stage, faults that are undetectable, this algorithm guarantees the generation of a shortest test sequence, if one exists, for every multiple stuck-at fault in a synchronous sequential circuit having a synchronizing sequence or a known initial state. A computer program was also written as a tool to automatically generate test sequences for detecting single or multiple faults in both combinational and synchronous sequential circuits.
24
PALENA, MARCO. "Exploiting Boolean Satisfiability Solvers for High Performance Bit-Level Model Checking." Doctoral thesis, Politecnico di Torino, 2017. http://hdl.handle.net/11583/2680997.
Abstract:
Digital systems are nowadays ubiquitous and often comprise an extremely high level of complexity. Guaranteeing the correct behavior of such systems has become an ever more pressing need for manufacturers. Correctness of digital systems can be addressed resorting to formal verification techniques such as model checking. A major issue of model checking techniques, however, is scalability. Recent performance advances in Boolean Satisfiability (SAT) solvers, brought about a leap in the scalability of those techniques. SAT-based model checking algorithms, however, still suffer from non-negligible applicability issues when confronted with the complexity of many industrial-scale designs. In this dissertation we present several approaches to improve performance and scalability of SAT-based model checking algorithms, focusing in particular on interpolation and IC3. Each of the presented approaches addresses scalability from a different perspective. The first approach focuses on the interaction between IC3 and the underlying SAT solver. IC3, in fact, proves to be highly sensitive to the way its SAT queries are handled. We propose and compare different strategies for SAT solvers management in IC3. The second approach consists of a novel interpolation-based algorithm that specifically targets the limited flexibility and incrementality of the original interpolation method. The proposed algorithm overcomes such limitations through the use of an incremental data structure for overapproximated reachability as well as techniques to better control the precision of the computed overapproximations. The third approach addresses interpolants compaction, proposing a novel SAT-based technique that relies on proof-based abstraction to achieve considerable compaction rates. Each of the proposed approaches was experimentally evaluated and proved to increase scalability of SAT-based model checking algorithms, in particular when considered in the context of portfolio-based model checking tools.
25
Fiszer, Robert Adrian. "Synthesis of Irreversible Incompletely Specified Multi-Output Functions to Reversible EOSOPS Circuits with PSE Gates." PDXScholar, 2014. https://pdxscholar.library.pdx.edu/open_access_etds/2109.
Abstract:
As quantum computers edge closer to viability, it becomes necessary to create logic synthesis and minimization algorithms that take into account the particular aspects of quantum computers that differentiate them from classical computers. Since quantum computers can be functionally described as reversible computers with superposition and entanglement, both advances in reversible synthesis and increased utilization of superposition and entanglement in quantum algorithms will increase the power of quantum computing.
One necessary component of any practical quantum computer is the computation of irreversible functions. However, very little work has been done on algorithms that synthesize and minimize irreversible functions into a reversible form. In this thesis, we present and implement a pair of algorithms that extend the best published solution to these problems by taking advantage of Product-Sum EXOR (PSE) gates, the reversible generalization of inhibition gates, which we have introduced in previous work [1,2].
We show that these gates, combined with our novel synthesis algorithms, result in much lower quantum costs over a wide variety of functions as compared to our competitors, especially on incompletely specified functions. Furthermore, this solution has applications for milti-valued and multi-output functions.
26
Belrhiti, Alaoui Mohammed. "Nouvelles Méthodes de Synthèse Logique et Application aux Réseaux Programmables." Phd thesis, Grenoble INPG, 1996. http://tel.archives-ouvertes.fr/tel-00346229.
Abstract:
Cette thèse propose et analyse de nouvelles méthodes de synthèse logique. L'analyse concerne des outils de la "troisième génération" d'écriture de bases irrédondantes de fonctions booléennes, à savoir les minimiseurs dits symboliques. Cette génération de minimiseurs conduit à la solution optimale plus rapidement et avec moins d'espace mémoire que les heuristiques de la minimisation explicite. Elle permet également le calcul de la forme complémentée minimale sans être exposée à des problèmes d'explosion en complexité, ce qui permet d'aboutir à un choix efficace entre une fonction et son complément. Nous avons abordé ensuite les problèmes de granularité des expressions factorisées. Nous avons proposé une méthode originale de réinjection qui intègre d'une façon concurrente une phase de minimisation symbolique des expressions booléennes. Cette méthode a permis de "corriger" la granularité: d'une part, des expressions booléennes obtenues par la factorisation, d'autre part, des équations obtenues par une description de haut niveau de type VHDL. La méthode proposée peut être également appliquée en tant que minimiseur logique qui tient compte du partage de la logique entre les expressions booléennes, ce qui n'est pas possible avec un minimiseur logique local ou global. Les expériences pratiques et l'application sur les réseaux programmables de type CPLD sont concluantes. Enfin, nous avons proposé une méthode originale de l'exploration de l'espace des solutions des macro-générateurs de type additionneur. Cette méthode est fondée sur le filtrage des solutions générées et l'amélioration par dérivation d'une solution donnée. Cette approche peut être efficacement appliquée sur la macro-génération sous contraintes temporelles
27
Kochte, Michael Andreas [Verfasser], and Hans-Joachim [Akademischer Betreuer] Wunderlich. "Boolean reasoning for digital circuits in presence of unknown values : application to test automation / Michael Andreas Kochte. Betreuer: Hans-Joachim Wunderlich." Stuttgart : Universitätsbibliothek der Universität Stuttgart, 2014. http://d-nb.info/1052894089/34.
28
Bosco, Gilles. "Synthèse et décomposition technologique sur réseaux programmables et ASICs." Phd thesis, Grenoble INPG, 1996. http://tel.archives-ouvertes.fr/tel-00346210.
Abstract:
Cette thèse s'intéresse d'une part au problème de décomposition technologique orienté surface sur des réseaux programmables de type FPGAs (Field Programmable Gate Arrays) et d'autre part à la synthèse des macro-générateurs sur ASICs et plus précisément de la synthèse des additionneurs. La décomposition s'articule autour de deux axes essentiels: tout d'abord, il s'agit d'optimiser la taille de la représentation des fonctions booléennes. Les représentations de base choisies ici sont les ROBDDs (Reduced Ordered Binary Decision Diagrams) ainsi qu'une structure dérivée, les ITE (If Then Else). La deuxième étape concerne la décomposition proprement dite. Les technologies cibles sont ici des FPGAs à base de LUT-k (Look Up Table), en particulier les FPGAs XC5200 de Xilinx et Orca de AT&T. Les deux méthodes de décomposition technologique orienté surface proposées permettent une décomposition hétérogène en prenant en compte non pas une seule configuration mais un ensemble de configurations possibles de la cellule cible. La première méthode est fondée sur un parcours descendant et optimisé du ROBDD. La seconde méthode s'appuie sur une modélisation en recouvrement d'hypergraphe du problème de décomposition technologique. Dans les deux méthodes, le coût exact en terme de surface finale du circuit est pris en compte à chaque étape de la décomposition. L'étude menée dans la deuxième partie de la thèse sur la macro-génération conduit dans un premier temps à l'exploration de l'espace des solutions possibles puis à l'optimisation d'une solution sélectionnée par un algorithme de dérivation discrète. L'utilisation d'un filtre permet la restriction de l'espace des solutions à explorer et d'autre part guide le processus de dérivation en éliminant les solutions trivialement médiocres. La combinaison des processus d'exploration et de dérivations permet la génération de macros dont les caractéristiques physiques sont les plus proches possibles de celles fixées par un utilisateur potentiel. Ces méthodes ont été intégrées au sein d'un outil universitaire ASYL+ développé au laboratoire CSI
29
Poirot, Franck. "Méthodes de synthèse optimisée pour compilateurs de silicium." Phd thesis, Grenoble INPG, 1990. http://tel.archives-ouvertes.fr/tel-00338390.
Abstract:
La synthèse logique joue un rôle fondamental dans les compilateurs de silicium. Alors que l'état de l'art de la synthèse deux couches est très avance, celui de la synthèse multi-couches reste encore un sujet très ouvert. L'objet de cette thèse est de présenter des méthodes originales de synthèse de contrôleurs et de systèmes combinatoires pour une implémentation multi-couches a base de cellules de bibliothèque. Le premier chapitre définit le concept de compilation de silicium et introduit l'une de ses composantes, la synthèse logique. L'importance du marche de la synthèse logique y est clairement définie ainsi que ses implications dans la conception actuelle de circuits intégrés. Le deuxième chapitre concerne la synthèse de contrôleurs. Le probleme du codage des machines d'états fini est traite en détail et une methode basée sur la théorie d'immersion de cubes intersectant dans un hypercube booléen est proposée. Le troisième chapitre est consacre a la synthèse de circuits combinatoires et une methode d'optimisation temporelle de tels dispositifs est développée. Ces travaux ont été implémentés dans un environnement industriel
30
Garando, Lahcen. "Architecture intégrée de rétines B-codées par processeurs cellulaires." Paris 11, 1986. http://www.theses.fr/1986PA112136.
Abstract:
L'intégration sur une même puce, de capteurs optoélectroniques, de codeurs d’images binaires, et de processeurs massivement parallèles, permet la réalisation d'une rétine "intelligente", système de vision compact en temps réel. Nous définissons l'architecture du tableau de processeurs élémentaires. Chacun d'eux associe un capteur optoélectronique d'image binaire, une unité logique bit-série et des moyens de communications avec ses voisins. La machine ainsi constituée permet d'acquérir une image binaire et de lui appliquer toute itération d'opérateurs ne supportant que des calculs booléens sur les données des voisins, traitements combinatoires locaux CTCU. Par ailleurs, nous détaillons les circuits électroniques qui permettent de représenter une image en niveau de gris par la densité de pixels noirs d'une image binaire, technique appelée B-codage. Enfin, nous décrivons l'implantation en technologie NMOS, de circuits d'évaluation de ces deux architectures. Celles-ci permettent la réalisation d'une rétine intelligente à structure matricielle, dont le processeur élémentaire contient moins de 25 transistorsThe integration, on a single ship, of optoelectronic sensors, binary picture coders, and massively parallel processors, results in a compact real time vision system, a kind of « intelligent retina ». First, we define the processor array architecture: each PE combines a binary picture optoelectronic sensor, a bit serial logic unit, and neighborhood communications means. This array can acquire a binary picture and apply to it any iteration of operators, provided they require only bolean processing of neighbours datas: they are called neighborhood combinatorial logic. We detail also electronic circuits performing the coding of a grey-level picture in the black pixels density of a binary picture-this kind of half toning is called B-coding. Finally, we describe prototype chips layout in a NMOS technology: these lead to the realization of an intelligent retina, whose array structure is based on a less than 25 transistors PE
31
Sénéchaud, Pascale. "Calcul formel et parallélisme : bases de Gröbner booléennes, méthodes de calcul : applications, parallélisation." Grenoble INPG, 1990. http://tel.archives-ouvertes.fr/tel-00337227.
Abstract:
Nous présentons les bases de Grobner, leur utilisation et la parallélisation des algorithmes qui les calculent dans le cas de polynômes booléens. Une première partie est consacrée à la présentation théorique des bases de Grobner dans le cas général. Cette présentation se veut accessible a des non-spécialistes. Une étude bibliographique de la complexité est faite. Une deuxième partie concerne les applications des bases de Grobner booléennes en calcul propositionnel et en preuve de circuits combinatoires. Nous proposons un algorithme de preuve formelle de circuits combinatoires hiérarchisés. Dans la troisième partie nous adaptons l'algorithme séquentiel au cas booléen et nous étudions plus en détail la normalisation. Nous proposons deux méthodes de parallélisation a granularité différentes. Nous analysons et comparons plusieurs implantations parallèles et présentons des résultats expérimentaux. Les algorithmes sont généralisables au cas des polynômes a coefficients rationnels. Nous soulignons l'influence de la répartition des données sur le temps d'exécution. Nous présentons une methode de répartition des polynômes basée sur la recherche de chemins de longueur donnée dans un graphe oriente. Cette répartition nous permet d'obtenir des résultats interpretables et de conclure sur les différents algorithmes
32
MELE, Santino. "A SAT based test generation method for delay fault testing of macro based circuits." Doctoral thesis, Università degli studi di Ferrara, 2010. http://hdl.handle.net/11392/2388685.
Abstract:
Delay fault testing and at-speed testing are widely used to verify the
timing of synchronous digital IC’s. The importance of these techniques is
still growing because of the relevant IC’s parameters uncertainties which
characterize the current technologies.
In order to drive this process, several fault models and test generation
techniques have been developed that target different trade-offs between accuracy
and efficiency.
The largest fraction of these approaches is based upon gate level descriptions
of the circuit. In case the basic building blocks are more complex
than logic gates and their implementation is not known, functional level approaches
have been proposed. For instance, this is the case for look-up tables
based Field Programmable Gate Arrays (FPGAs) and it may be a perspective
for deep submicron circuits that exploit logic bricks as basic building
blocks. This class of circuits has been referred to as macro or module based.
In this context, the main activities performed during the tree years of
my PhD are related to the timing failures problems in module-based CMOS
VLSI circuits.
The attention to module-based (or block-based) circuits follows the current
VLSI physical design trends that attempt to limit the parametric failures
due to the scaling of technology toward nanometric feature sizes. In
such technologies, in fact, the traditional design paradigms that are based on
small (i.e gate level) cells may produce high levels of variability, thus resulting
in parametric defects. The use of highly regular cell structures, called
logic bricks has been proposed to solve these problems thus increasing the
yield of VLSI circuits. A brick comprises a logic function created from a
small set of logic primitives that are mapped on to a micro-regular fabric.
Such logic function is typically more complex that those implemented in traditional VLSI libraries.
Field Programmable Gate Array (FPGA) technology also exploits a module
based design approach. Unlike logic bricks, FPGAs are completely programmable,
because they are based on look up tables (a n-bit LUT can
accomplish every n-bit function), but the drawback is related to the implementation
of the LUT, that is unknown to designer and not optimized for
regularity.
In this scenario, the delay fault testing became a big issue, since it is
very difficult to study a circuit built using modules whose implementation
in not known, either for technological and for intellectual property reasons.
Moreover, the aggressive timing policies used in today’s ICs make the need
for delay fault testing more relevant.
The main PhD activity, that will be explained in detail in this thesis, is
related to a new method that we propose to generate test vectors for path
delay faults in circuits based on modules.
In particular, we consider the single path delay fault model in combinational
circuits or in (enhanced) full-scan ones that are composed of functional
blocks whose implementation is not known. In such circuits a path fault is
detected by suitable conditions so that a test pair is able to propagate a
transition through the path under test, in order to detect a path delay fault.
In order to identify such conditions, we introduced a new signal representation
that enables the use of boolean differential calculus. Also, additional
conditions to prevent invalidation of tests by hazards have been identified.
We suppose that the dynamic behavior of the block is modeled using
input delays such as in the timing arc delay model. We target simple combinational
blocks such as logic bricks, that are expected to present up to
8-10 inputs and a low logic depth. The used method is scalable, to generate
conditions for path delay fault tests also at gate level.
In order to assess the feasibility of the proposed approach, I realized a
software, written in C/C++, that permits to find out robust and non-robust
test pairs, starting from the BLIF description of a module based circuit. Such
a software uses a BDD description of the blocks’ functions on which we apply
Boolean Differences to obtain local sensitization conditions at module level.
Since there are circuits whose BDD structure may be very large and it may
be inefficient (in some cases also infeasible) to treat it, we translate functions
obtained at macros level to a CNF description. After that, a SAT solver generates the test pairs at circuit level starting from the conjunction of all
the CNF functions.
The software tool was used to verify the proposed approach on a set of
benchmarks (both combinational or full-scan) from ITC’99 and ISCAS’85
sets. Such benchmarks allowed to show the feasibility of the proposed approach,
although they are not fully representative of the target circuits for
which the method was developed.
Another significant work, carried out during my PhD period, also deal
with testing of macro-based circuits, but it concerns specifically logic bricks.
In particular, a method for high quality functional fault simulation and
test generation for such circuits was conceived and a software tool that
implements it was developed.
For both the approaches, results showed the feasibility of them, but also
highlighted possibilities to improve and extend the work done.
33
Mrnuštík, Michal. "Evoluční návrh využívající booleovské sítě." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2010. http://www.nusl.cz/ntk/nusl-237120.
Abstract:
This master's thesis introduces the Random Boolean Networks as a developmental model in the evolutionary design. The representation of the Random Boolean Networks is described. This representation is combined with an evolutionary algorithm. The genetic operators are described too. The Random Boolean Networks are used as the developmental model for the evolutionary design of the combinational circuits and the sorting networks. Moreover a representation of the Random Boolean Networks for the design of image filters is introduced. The proposed methods are evaluated in different case-studies. The results of the experiments are discussed together with the potential improvements and topics of the next research.
34
Aubert, Clément. "Logique linéaire et classes de complexité sous-polynominales." Paris 13, 2013. https://theses.hal.science/tel-00957653.
Abstract:
This research in Theoretical Computer Science extends the gateways between Linear Logic and Complexity Theory by introducing two innovative models of computation. It focuses on sub-polynomial classes of complexity : AC and NC —the classes of efficiently parallelizable problems— and L and NL —the deterministic and non-deterministic classes of problems efficiently solvable with low resources on space. Linear Logic is used through its Proof Net resentation to mimic with efficiency the parallel computation of Boolean Circuits, including but not restricted to their constant-depth variants. In a second moment, we investigate how operators on a von Neumann algebra can be used to model computation, thanks to the method provided by the Geometry of Interaction, a subtle reconstruction of Linear Logic. This characterization of computation in logarithmic space with matrices can naturally be understood as a wander on simple structures using pointers, parsing them without modifying them. We make this intuition formal by introducing Non Deterministic Pointer Machines and relating them to other well-known pointer-like-machines. We obtain by doing so new implicit characterizations of sub-polynomial classes of complexityCette recherche en informatique théorique construit de nouveaux ponts entre logique linéaire et théorie de la complexité. Elle propose deux modèles de machines abstraites qui permettent de capturer de nouvelles classes de complexité avec la logique linéaire, les classes des problèmes efficacement parallélisables (NC et AC) et celle des problèmes solutionnables avec peu d’espace, dans ses versions déterministes et non-déterministes (L et NL). La représentation des preuves de la logique linéaire comme réseaux de preuves est employée pour représenter efficacement le calcul parallèle des circuits booléens, y compris à profondeur constante. La seconde étude s’inspire de la géométrie de l’interaction, une délicate reconstruction de la logique linéaire à l’aide d’opérateurs d’une algèbre de von Neumann. Nous détaillons comment l’interaction d’opérateurs représentant des entiers et d’opérateurs représentant des programmes peut être reconnue nilpotente en espace logarithmique. Nous montrons ensuite comment leur itération représente un calcul effectué par des machines à pointeurs que nous définissons et que nous rattachons à d’autres modèles plus classiques. Ces deux études permettent de capturer de façon implicite de nouvelles classes de complexité, en dessous du temps polynomial
35
Predrag, Teodorović. "Dizajn i minimizacija rekurzivnih Bulovih formula za memristivna logička kola." Phd thesis, Univerzitet u Novom Sadu, Fakultet tehničkih nauka u Novom Sadu, 2014. http://www.cris.uns.ac.rs/record.jsf?recordId=86541&source=NDLTD&language=en.
Abstract:
U radu je razmatran problem dizajna i minimizacije rekurzivneBulove formule konstruisane za proizvoljnu Bulovu funkciju y:BN→B.U cilju rešavanja ovog problema, predstavljene su dve algoritamskeheuristike za minimizaciju rekurzivne Bulove formule. Minimizacijarekurzivne Bulove formule vrši se korišćenjem regularnih poredakapozitivnih proizvod termova. U disertaciji je dokazano kako je ovaregularnost poredaka zapravo potreban i dovoljan uslov da željenaBulova funcija y bude korektno predstavljena rekurzivnom Bulovomformulom konstruisanom na osnovu tih poredaka. Pokazano je i kakopredstavljeni algoritmi daju bolje rezultate za veći broj instanciproblema u poređenju sa algoritmima dostupnim u literaturi.In this thesis, the problem of design and minimization of recursive Booleanformula, based on an arbitrary Boolean function y:BN→B , is considered. As asolution of a problem, two heuristic algorithms that minimize the length ofrecursive Boolean formula, were presented. Minimization, itself, is done byusing regular orders of positive product terms. In the thesis it was proved thatthe regularity of orders represents necessary and sufficient condition forcorrect representation of Boolean function y by recursive Boolean formulabased on such regular order. Developed algorithms are compared with otherheuristic algorithms for recursive Boolean formula minimization, available inthe literature, and it is shown how algorithms proposed in this thesis providebetter results for more problem instances.
36
Aubert, Clément. "Logique linéaire et classes de complexité sous-polynomiales." Phd thesis, Université Paris-Nord - Paris XIII, 2013. http://tel.archives-ouvertes.fr/tel-00957653.
Abstract:
Cette recherche en informatique théorique construit de nouveaux ponts entre logique linéaire et théorie de la complexité. Elle propose deux modèles de machines abstraites qui permettent de capturer de nouvelles classes de complexité avec la logique linéaire, les classes des problèmes efficacement parallélisables (NC et AC) et celle des problèmes solutionnables avec peu d'espace, dans ses versions déterministes et non-déterministes (L et NL). La représentation des preuves de la logique linéaire comme réseaux de preuves est employée pour représenter efficacement le calcul parallèle des circuits booléens, y compris à profondeur constante. La seconde étude s'inspire de la géométrie de l'interaction, une délicate reconstruction de la logique linéaire à l'aide d'opérateurs d'une algèbre de von Neumann. Nous détaillons comment l'interaction d'opérateurs représentant des entiers et d'opérateurs représentant des programmes peut être reconnue nilpotente en espace logarithmique. Nous montrons ensuite comment leur itération représente un calcul effectué par des machines à pointeurs que nous définissons et que nous rattachons à d'autres modèles plus classiques. Ces deux études permettent de capturer de façon implicite de nouvelles classes de complexité, en dessous du temps polynomial.
37
Jang, Jing-Tang Keith. "The size and depth of Boolean circuits." 2013. http://hdl.handle.net/2152/21370.
Abstract:
We study the relationship between size and depth for Boolean circuits. Over four decades, very few results were obtained for either special or general Boolean circuits. Spira showed in 1971 that any Boolean formula of size s can be simulated in depth O(log s). Spira's result means that an arbitrary Boolean expression can be replaced by an equivalent "balanced" expression, that can be evaluated very efficiently in parallel. For general Boolean circuits, the strongest known result is that Boolean circuits of size s can be simulated in depth O(s / log s). We obtain significant improvements over the general bounds for the size versus depth problem for special classes of Boolean circuits. We show that every layered Boolean circuit of size s can be simulated by a layered Boolean circuit of depth O(sqrt{s log s}). For planar circuits and synchronous circuits of size s, we obtain simulations of depth O(sqrt{s}). Improving any of the above results by polylog factors would immediately improve the bounds for general circuits. We generalize Spira's theorem and show that any Boolean circuit of size s with segregators of size f(s) can be simulated in depth O(f(s)log s). This improves and generalizes a simulation of polynomial-size Boolean circuits of constant treewidth k in depth O(k² log n) by Jansen and Sarma. Since the existence of small balanced separators in a directed acyclic graph implies that the graph also has small segregators, our results also apply to circuits with small separators. Our results imply that the class of languages computed by non-uniform families of polynomial size circuits that have constant size segregators equals non-uniform NC¹. As an application of our simulation of circuits in small depth, we show that the Boolean Circuit Value problem for circuits with constant size segregators (or separators) is in deterministic SPACE (log² n). Our results also imply that the Planar Circuit Value problem, which is known to be P-Complete, is in SPACE (sqrt{n} log n). We also show that the Layered Circuit Value and Synchronous Circuit Value problems, which are both P-complete, are in SPACE(sqrt{n}). Our study of circuits with small separators and segregators led us to obtain space efficient algorithms for computing balanced graph separators. We extend this approach to obtain space efficient approximation algorithms for the search and optimization versions of the SUBSET SUM problem, which is one of the most studied NP-complete problems. Finally we study the relationship between simultaneous time and space bounds on Turing machines and Boolean circuit depth. We observe a new connection between planar circuit size and simultaneous time and space products of input-oblivious Turing machines. We use this to prove quadratic lower bounds on the product of time and space for several explicit functions for input-oblivious Turing machines.text
38
Safarpour, Sean A. "Managing circuit don't cares in Boolean satisfiability." 2005. http://link.library.utoronto.ca/eir/EIRdetail.cfm?Resources__ID=370244&T=F.
39
Liu, Tsung-Hsun, and 劉宗勳. "Efficient Construction for Quantum Boolean Circuits." Thesis, 2007. http://ndltd.ncl.edu.tw/handle/nmk283.
Abstract:
碩士國立東華大學
資訊工程學系
95
As the development of VLSI design advances, quantum computing is a possible alternative for solving the bottleneck of future computer design. Just like a classical computer, a quantum computer also has circuits and logic gates inside. Over the last few years, several quantum circuit simplification methods have been proposed. However, most methods are complex and others can not be automated. In the classical logic design, the Quine-McCluskey method (Tabulation Method) and the Karnaugh map are efficient and easy methods of minimization for conventional logic design. In this thesis, we design a grouping operation technique to classify data and another method to extract the XOR operation between two gates in the circuit. We present our grouping method and using those two simplification steps to construct the quantum circuit effectively.
40
Hsu, Tzu-Chien, and 徐子騫. "Reconstructing and Utilizing Circuit Information in Quantified Boolean Formula Solving." Thesis, 2016. http://ndltd.ncl.edu.tw/handle/17722740081935749042.
Abstract:
碩士國立臺灣大學
電子工程學研究所
104
Quantified Boolean Satisfiability (QSAT) is a powerful representation since any problem in PSPACE can be encoded naturally and compactly as QSAT. Due to its representational power, QSAT is gaining increasing research attention, and many effective quantified Boolean formula(QBF) solvers have been developed recently, yet these solvers remain premature and awaits further breakthroughs for industrial applications. There are two main procedures used for QBF solver, including solution learning and conflict learning. One of the main researches about conjunctive normal form based (CNF-based) solver focuses on how to bridge the duality gap between solution learning and conflict learning, while the duality gap results from the empty initial cube database. Recent research shows that circuit information can be used as initial cube database to bridge the gap, and such technique is implemented in two state-of-the-art QBF solvers, including OOQ and QELL. OOQ is the first QBF solver to propose the definition of usable circuit information for initial cube database, and how to utilize circuit information during solution learning in resolution-based solving style. On the other hand, QELL provides a more general characterization about usable circuit information and integrate circuit information with solution learning in an expansion-based solving style. Both solvers show how circuit information helps achieve exponential speed-up. However, the circuit information reconstruction and utilization are still incomplete in three aspects: First, the reconstructible circuit information is still restricted. Second, only circuit information can be used as initial cube database. Third, circuit information is not fully utilized in the solution learning of QELL. This thesis proposes improvement methods for these three aspects. This thesis shows how to recover more hidden circuit information in addition to Tseitin transformation pattern, and proposes a method to recover initial cubes uncovered by circuit information. This thesis also gives a modified solution learning method to utilize circuit information for QELL. The new proposed methods for reconstructing and utilizing circuit information are implemented in QELL solver, and instances are provided to evidence the contribution of this thesis.
41
Smith, Alexander D. S. "Diagnosis of combinational logic circuits using Boolean satisfiability." 2004. http://link.library.utoronto.ca/eir/EIRdetail.cfm?Resources__ID=95044&T=F.
42
Chou, Yao-Hsin, and 周耀新. "Research on the Testability of Quantum Boolean Circuits." Thesis, 2009. http://ndltd.ncl.edu.tw/handle/09789931876530670157.
Abstract:
博士國立臺灣大學
電機工程學研究所
97
Circuit testing is now over 45 years and poses many considerable challenges. The circuits of modern electrical appliances become more and more complicated and the cost of circuit testing is rapidly increasing along with the complexity of the chip. According to Inter/National Technology Roadmap for Semiconductors 2001/1997, test cost will become critical part of the total cost in ten years. It is indispensable to control these costs and provide a cost-effective solution. Therefore, it is important to develop efficient testing approaches. Testing is also the key to many fault tolerance approaches that improve product reliability. Nowadays, every electronic device/electrical appliance we use is built by Boolean circuits. In this project, a novel method is proposed to perform logic testing for Boolean circuit by utilizing the quantum computation. In the future, any Boolean circuit can be tested easily, quickly, and cost-effectively, so that reliable and inexpensive products can be acquired by everyone. It has been proved that any Boolean circuit can have its quantum version. In this project, we showed that quantum Boolean circuits can be arranged into a 1-testable quantum iterative logic array (QILA). Furthermore, with superposition, which is a nanoscale phenomenon in the quantum computation, any quantum Boolean circuit and any QILA can be tested in just a few steps for any given classical Boolean function. By utilizing nanotechnology, these methods provide a smooth migration to the next generation circuit design and may intrinsically change the IC design flow in the future. Recently, a systematic procedure was proposed to derive a minimum input quantum circuit for any given classical logic with the generalized quantum Toffoli gate, which is universal in Boolean logic. Since quantum Boolean circuits are reversible, we can apply this property to build quantum iterative logic array (QILA). QILA can be easily tested in constant time (C-testable) if stuck-at fault model is assumed. In this project, we try to use Hadamard and general CCN gates to make QILA 1-testable. That is, for any quantum Boolean circuit, the number of test patterns is independent of both the size of the array and the length of the inputs. Nanotechnology has made the semiconductor industry to keep up with the growth of consumers'' performance--capacity demands. Sophisticated semiconductor fabrication techniques are used for the production of nanoscale structures. By nanometer technologies, there are more transistors fabricated on a single chip with increasing integration scale, thus reducing the cost per transistor. However, nanometer-scale devices have much higher manufacturing fault rates and are more sensitive to failures of transistors and wires owing to many external factors. Consequently, the difficulty of testing each transistor increases as the complexity of devices increases. Testing such highly complex and dense circuits becomes very difficult and expensive. On the other hand, when devices are getting smaller and smaller, the quantum effect appears. With nanoscale phenomenon such as superposition or entanglement, we can perform quantum computation to accomplish some tasks that are classically impossible. Some of these examples are Shor''s factorization and Grover''s search algorithm. It is interesting to note that these nano-phenomena can be used to solve the circuit testing problem as well. Previous study showed that any classical circuit can be implemented by a straightforward replacement algorithm with auxiliary qubits as intermediate storage. Recently, a construction procedure of minimum input quantum Boolean circuit was proposed. The constructed quantum Boolean circuits are reversible. Such circuits are of interest for several reasons. One of the important reasons is energy saving. Reversible circuits are information lossless and hence tend to dissipate relatively little energy. According to Landauer''s principle, it is possible to construct a computer using reversible circuits that can compute with arbitrarily small amounts of energy. Another reversible circuit''s property of particular interest is that the Boolean function of a reversible circuit is bijective (one-to-one and onto); hence it can be used to form an iterative logic array (ILA), a system that consists of identical modules arranged in a geometrically regular interconnection pattern. ILA is well known to be easily testable. In this project, we study the testing properties on quantum Boolean circuit and quantum iterative logic array (QILA). QILA consists of reversible quantum circuits constructed from a library of universal reversible gates, including quantum NOT, controlled-NOT (CNOT), generalized controlled-controlled-NOT (CCN), and Hadamard gates. Under stuck-at fault and cell fault model, we show that any QILA and quantum Boolean circuits are 1-testable. That is, the circuits can be tested with only one test pattern.
43
Tsai, I.-Ming, and 蔡一鳴. "Quantum Boolean Circuits for Quantum Computing and Communications." Thesis, 2002. http://ndltd.ncl.edu.tw/handle/68727984781291695914.
Abstract:
博士國立臺灣大學
電機工程學研究所
91
Quantum information science is a multidisciplinary research area. It combines quantum mechanics, theoretical computer science, information theory, and mathematics to explore the possibilities of making efficient computing and communication. In this dissertation, we first present a historical overview of quantum mechanics and give an introduction of quantum computing and quantum communication, and then we propose some important engineering applications of quantum boolean circuits. First, we show how a classical Boolean function can be realized using quantum boolean circuits with minimum space. It is well-known that any classical combinational circuits can be implemented with Toffoli gates using the straightforward, but inefficient, replacement algorithm. In this dissertation, we propose a systematic procedure to derive a minimum space quantum circuit to implement a given classical combinational logic. Second, we explain how quantum boolean circuits can be used to search multiple targets in an unordered database. To do this, we show how quantum boolean circuits can be used to implement the oracle circuit and the inversion-about-average function in Grover's search algorithm. In addition, we also show that a slight modification of the oracle circuit can be used to search multiple targets. Finally, we present a switching architecture such that digital data can be switched in the quantum domain. This results in a quantum switch that can be used to build classical and quantum information networks. Compared with a traditional space or time domain switch, the proposed switching mechanism is much more scalable. Assuming an n-by-n quantum switch, the space consumption grows linearly, i.e. O(n), while the time complexity is O(1) for unicasting, and O(log n) for multicasting. Based on these advantages, a high throughput switching device can be built simply by increasing the number of I/O ports.
44
Dubrova, Elena Vladimirovna. "Boolean and multiple-valued functions in combinational logic synthesis." Thesis, 1997. http://hdl.handle.net/1828/8276.
Abstract:
The subject of this dissertation is the theory of Boolean and multiple-valued functions.
The main areas considered are: functional completeness, canonical forms,
minimization of functions, discrete differences and functional decomposability. The
results obtained are used as a foundation for the development of several new algorithms
for logic synthesis of combinational logic circuits. These include an efficient
algorithm for three-level AND-OR-XOR minimization for Boolean functions, an algorithm
for generating the composition trees for Boolean and multiple-valued functions
in a certain class, and an algorithm for computing a new canonical form of multiple-valued
functions. Several other problems, related to logic synthesis, such as test
generation for combinational logic circuits and synthesis of easily testable circuits are also addressed. Possible directions for future research are discussed.Graduate
45
Shi, Junhao [Verfasser]. "Boolean techniques in testing of digital circuits / von Junhao Shi." 2006. http://d-nb.info/98361816X/34.
46
Huang, Shih-Ming, and 黃世名. "Secure Boolean Computation for Electronic Medical Record using Garbled Circuits." Thesis, 2015. http://ndltd.ncl.edu.tw/handle/92212440049876000118.
Abstract:
碩士國立交通大學
網路工程研究所
103
Electronic medical record has been used for many years. The need for medical resource is not restricted to local area. Not only how integrating, managing and making good use of data at different area but also the medical service for patients are important issues. Along with cloud computing is maturing, EMRs can be stored in cloud; by doing so, it would cut down on managing cost and exchange EMRs with others more convenient; however, we should pay attention to its privacy, because that EMR including with patient's basic, biometric and medical information. As a result, we have to encrypt EMR before storing it in cloud, and make encrypted EMR accessible not only to patient but doctor with appropriate identity. To satisfy the requirement of medical database, we have to support regular functionalities, which are common in cloud services, and leak nothing to cloud service provider while executing command and returning results. Besides that, for quality of medical service, users especially need to care about correctness of EMR; verifying that cloud service stores and provides data without any mistake before using EMR. Focusing on challenges above, we propose a secure electronic medical record database, called SDEMR(Secure Distributed Electronic Medical Record), based on CryptDB [1][2][3], developed by MIT CSAIL team. CryptDB ensures data's confidentiality and supports doing operations on ciphertext in database via onion encryption. For both usability and security, we add the following three functions: 1)secure boolean computation: utilizing the concept of Yao's garbled circuit[4], allowing user to outsource computation to database without revealing plaintext information. 2)integrity check mechanism: Embedding PDP[5] into our system, verifying whether data stored in cloud is correct or not and ensuring that EMR is not modified by attackers. 3)access control mechanism: making use of MA-ABE[6], iv letting users manage their EMR elastically and make unauthorized users impossible to access EMR. Therefore, it's achievable for EMR to be securely controlled and shared with other people in cloud. In the end, we prove our architecture is practicable by implementation. Also, for manipulating our system straightforwardly, we design user interface by referencing the principle of high usability of a user interface[7]. We also make a mini medical database to simulate our system. We followed the suggested standards from the EMRs Standard Management System of the Ministry of Health and Welfare of Executive Yuan[8] to build the records, tables etc.
47
Hu, Yung-Chun, and 胡詠峻. "Energy Optimization for Probabilistic Boolean Logic Circuits and its Applications." Thesis, 2014. http://ndltd.ncl.edu.tw/handle/43435187146011868497.
48
Wu, Chi-An, and 吳濟安. "A Circuit-Based Boolean Solver and Its Application to Rewiring-Based Logic Optimization." Thesis, 2008. http://ndltd.ncl.edu.tw/handle/80099182293087476707.
Abstract:
碩士國立臺灣大學
電機工程學研究所
96
In this thesis, we proposed a SAT-based logic optimization framework which contains a robust Boolean satisfiability (SAT) solver, a powerful redundancy-addition-and- removal (RAR) engine, and a Pseudo-Boolean optimizer on the circuit netlist. It can be used for the verification and logic optimization of the VLSI circuits. The SAT solver is implemented on the FRAIG (Functionally Reduced And-Inverter Graph) structure so that it has stronger implicability on a semi-canonical circuit netlist. We further revised the FRAIG by recording more logic implications and allowing multi-input gates. Different from other FRAIG packages where the SAT engine is based on a separated Conjunctive-Normal-Form (CNF) based solver, we implemented the SAT algorithms directly on FRAIG so that the structural information can be fully utilized. Moreover, we incorporated the SAT decision making and RAR techniques so that the RAR-based logic optimization can be more flexible and efficient. Lastly, we extended our SAT solver to a Pseudo Boolean (PB) optimizer and proposed a multiple RAR technique. We applied these techniques for circuit optimization and the experimental results show that our framework can achieve significant improvement over the traditional approaches.
49
Wu, Chi-An. "A Circuit-Based Boolean Solver and Its Application to Rewiring-Based Logic Optimization." 2008. http://www.cetd.com.tw/ec/thesisdetail.aspx?etdun=U0001-0707200819433300.
50
Chang, Li-Kai, and 張立楷. "Automatic Synthesis of Sequential Quantum Boolean Circuits Based on Self-Timed Specifications." Thesis, 2004. http://ndltd.ncl.edu.tw/handle/08220424937599409877.
Abstract:
碩士大同大學
資訊工程學系(所)
92
This thesis presents a methodology to transfer self-timed circuit specifications into sequential quantum Boolean circuits (SQBCs). State graphs (SGs) are used to describe the behaviors of self-timed circuits and then are translated into SQBCs based on Toffoli gates. The concept of IP (Intellectual Property) reuse is applied to the constructed SQBCs to produce reusable and composable quantum Boolean circuits (CQBCs). Therefore, these reusable CQBCs as basic modular components can be exploited to construct more complicated quantum Boolean circuits. Based on our methodology a CAD tool written in Java to automatically synthesize SQBCs and CQBCs is designed and implemented. A universal set of self-timed components is successfully and automatically synthesized into CQBCs by using our CAD tool. These CQBCs can be used as building blocks to compose all control-path components of self-timed systems.