To see the other types of publications on this topic, follow the link: Logical synthesis.
Dissertations / Theses on the topic 'Logical synthesis'
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 'Logical synthesis.'
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
Yang, Ting. "Evaluating development projects : exploring a synthesis model of the logical framework approach and outcome mapping." Thesis, University of Sussex, 2018. http://sro.sussex.ac.uk/id/eprint/79800/.
Full textAbstract:
Under the current results-driven development agenda, sound evaluation, and a corresponding evaluation toolkit, need to be in place to examine whether and to what extent development interventions have achieved their targeted objectives and results, and to generate lessons for further development learning and improvement. My review of the literature shows that innovative and appropriate evaluation approaches are needed to address key challenges in evaluation such as the tension between learning and accountability objectives, the need to unpack the mechanisms linking outputs and outcomes or goal, and to add an actor perspective. Irrespective of project type, the Logical Framework Approach (LFA) is often a standard requirement of major official donor agencies on projects they fund, so as to fulfil bureaucratic imperatives. However, it is often considered inadequate in addressing key challenges in development evaluation. Given the dominant status of the LFA with such strong support from donors, it is helpful to seek a ‘middle way': a combination of the LFA with other approaches in order to address some of its inadequacies, while satisfying donor agencies' requirements. A synthesis of the LFA and Outcome Mapping (OM) is one such option. This thesis explores the practical value and usefulness of a synthesis model empirically. Applying the model in two case study aid projects, I found that it serves well as a theory-based evaluation tool with a double-stranded (actor strand and results chain) theory of change. The model helps reconcile learning and accountability and add explanatory power and an explicit actor perspective. It also helps establish causation and enable attribution claims at various results levels with its different elements. The model has some limitations but my results suggest it can be usefully adopted. The choice of its application depends on project evaluation context and purpose in specific cases.
2
Teslenko, Maxim. "All Around Logic Synthesis." Doctoral thesis, Stockholm : Mikroelektronik och informationsteknik, Kungliga Tekniska högskolan, 2008. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-4700.
Full text
3
Kozlowski, Tomasz. "Application of exclusive-OR logic in technology independent logic optimisation." Thesis, University of Bristol, 1996. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.296702.
Full text
4
Berrada, Fathi Wafâa. "Influence des architectures "materiel" et "logiciel" de systemes de synthese d'image sur l'efficacite d'algorithmes de visualisation." Université Louis Pasteur (Strasbourg) (1971-2008), 1988. http://www.theses.fr/1988STR13185.
Full textAbstract:
Presentation sur le materiel existant, les logiciels de base disponibles, les normalisations operationnelles ainsi que les algorithmes diffuses actuellement. Il est montre comment ces trois parties interreagissent entre elles. Il est precise qu'elle parait etre l'architecture "materiel" et "logiciel" la plus adaptee a une exploitation avancee
5
Färm, Petra. "Advanced algorithms for logic synthesis." Licentiate thesis, KTH, Microelectronics and Information Technology, IMIT, 2004. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-1717.
Full textAbstract:
<p>In this thesis, new algorithms for logic synthesis areexplored. Our work is motivated by two observations: (1)Traditional logic synthesis applies literal count as theprimary quality metric during the technology independentoptimization phase. Thissimplistic metric often leads to badcircuit structures as it cannot foresee the impact of earlychoices on the final area, delay, power consumption, etc. (2)Although powerful, global Boolean optimization is not robustand corresponding algorithms cannot be used in practice withoutartificially restricting the application window. Othertechniques, such as algebraic methods scale well but provideweaker optimization power.</p><p>In our most recent work, both problems are addressed byapplying a simulated annealing approach that is based on asimple circuit graph representation and a complete set of localtransformations, including algebraic and Boolean optimizationsteps. The objective of the annealing process can be tuned tocomplex cost functions, combining area, timing, routability,and power. Our experimental results on benchmark functionsdemonstrate the significant potential of the simulatedannealing approach.</p><p>Earlier work includes a fast rule-based system fortechnology independent optimization. A Boolean network isoptimized by applying local structural transformations thatpreserve its functionality. NPN classes of Boolean functionsare used to identify replacement rules for localtransformations. It provides fast and roboust optimization, butuses a simplistic objective.</p><p>Decomposition is one of the important steps of logicsynthesis. It can be applied during the technology independentoptimization phase as well as during the technology mapping. Wehave extended a conjunctive decomposition of Boolean functions[1]to multiple-valued input binary-valued output functions.Our extension provides a more efficient way for decomposingmutiple-output Boolean functions, since [1]only considerssingle-output functions.</p><p>Furthermore, we address the problems of technology mappingand logic optimization for Chemically Assembled ElectronicNanotechnoloy (CAEN).CAEN is a promising alternative toCMOS-based technology, allowing construction of extremeleydense low-power computational elements with inexpensivechemical self-assembly.</p>
6
Wang, Qi. "Logic synthesis for low power." Diss., The University of Arizona, 1998. http://hdl.handle.net/10150/288924.
Full textAbstract:
The dissertation addresses several problems in the power optimization and power-delay tradeoffs in digital CMOS circuits. The work is organized according to the three main sources of power dissipation: Power dissipation due to switching (P(sc)), standby or leakage power (P(leak)) and short circuit power (P(sc)). First we present new, efficient and provably correct algorithms for minimizing the switching power in combinational and sequential CMOS logic circuits. The techniques are based on the addition and removal of redundancies at the logic level. The basic technique developed for combinational circuits is extended to sequential circuits. Results of experiments carried on large (thousands of logic gates) commerical circuits (of the PowerPC chip) will be presented. Power dissipation due to the short circuit current has received much less attention. For submicron MOSFETs, this can be comparable to the switching power. A new, and computationally tractable model for the short circuit current in CMOS inverters and more complex CMOS gates was developed. This model was verified using a commerical 0.25 μm CMOS library and device models. The problem of minimizing the standby power for deep submicron technology is also addressed. The standby power dissipation has often been ignored in the design of CMOS circuits since its contribution to the total power dissipation has been negligable. However as device dimensions and voltages are scaled down, the standby power can be of the same order of magnitude as the switching power. This is a serious problem of many portable devices as they are in standby mode for considerable periods of time. One approach to alleviate this problem is the use of dual threshold voltages. We developed several new algorithms that optimally assign one of two threshold voltages to CMOS gates so as to minimize the standby power without sacrificing performance. The new algorithms handle circuits of thousands of gates and it is shown that the standby power can be reduced by as much as an order of magnitude without any loss of performance.
7
Hadjinicolaou, M. G. "Synthesis of programmable logic arrays." Thesis, Brunel University, 1986. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.371168.
Full text
8
Pearce, Maureen. "Logic synthesis for programmable devices." Thesis, University of Bristol, 1993. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.357911.
Full text
9
Poulain, Thierry. "Contribution du génie logiciel pour la conception et l'évaluation d'applications de supervision." Valenciennes, 1994. https://ged.uphf.fr/nuxeo/site/esupversions/86faffad-3e4b-4990-b7c1-7a6b0cf7faac.
Full textAbstract:
A partir d'une démarche axée sur le génie logiciel, l'objectif de cette thèse est d'intégrer des fonctionnalités de prototypage, favorisant le cycle de développement d'applications de surveillance. Le mémoire est divisé en cinq chapitres. Dans le premier, sont abordés les systèmes de supervision. Puis, après avoir identifié un ensemble de problèmes ergonomiques résultant de leur utilisation et de leur conception, une démarche globale de conception et évaluation développée au LAIH est décrite. Une application de supervision nécessitant de nombreux développements informatiques, les principaux modèles utilisés en génie logiciel sont ensuite abordés. La conception et l'évaluation d'un système homme-machine fait intervenir de multiples méthodes et outils issus de domaines divers. Dans ce cadre, un panorama de ces méthodes et outils fait l'objet du deuxième chapitre. Ces différents points nous conduisent à proposer une démarche axée sur le prototypage dans le troisième chapitre. Celle-ci a pour objectif d'améliorer la conception des images destinées à la supervision des procédés en fournissant un cadre méthodologique aux différents intervenants impliqués dans le cycle de développement. Dans l'objectif d'appliquer cette démarche, le quatrième chapitre décrit notre contribution à l'étude et l'intégration de fonctionnalités de prototypage dans l'atelier ATLAS (atelier logiciel pour l'animation de synoptiques). Cette recherche a été menée en collaboration avec la CSEE et 3IP. ATLAS consiste, à partir d'une description graphique du procédé, à générer des prototypes d'images. Une fois les vues graphiques évaluées et validées dynamiquement, une partie des données de prototypage est ensuite récupérée pour produire l'application définitive qui sera implantée sur le site. Enfin une première validation technique ainsi que des perspectives de recherches et de développement sont présentées dans le cinquième chapitre.
10
Димко, Єгор Павлович. "Моделі та методи оптимального керування індукційним дуплекс-процесом за умов невизначеності". Thesis, Національний технічний університет "Харківський політехнічний інститут", 2018. http://repository.kpi.kharkov.ua/handle/KhPI-Press/38635.
Full textAbstract:
Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.03 – системи та процеси керування. – Національний технічний університет "Харківський політехнічний інститут", Харків, 2018. Дисертація присвячена вирішенню актуальної науково-практичної задачі – розробці методів оптимального управління в умовах невизначеності. Показана можливість побудови адекватної математичної моделі індукційного дуплекс-процесу плавки як об'єкта управління в умовах неможливості реалізації плану активного експерименту в виробничих умовах. На основі цього запропоновано для опису кінцевого стану в задачі пошуку оптимального за кінцевим станом управління використовувати результати параметричного опису за визначенням локально-оптимальних значень вхідних змінних на основі реалізації процедури рідж-аналізу. Показано, як з використанням комбінованої процедури штучної ортогоналізації за даними пасивного експерименту при довільній формі плану експерименту і центрального ортогонального планування отримати таке параметричне опис. Розв'язана задача синтезу оптимального управління індукційної плавкою в печах ІСТ1 / 0.8-М5 в умовах альтернативних стратегій і доведено, що при виборі стратегії плавлення на "болоті" фазова траєкторія буде постійно змінюватися внаслідок корекції початкового стану, що обумовлено зміною швидкості розплавлення при обраному способі управління. Показано, як оптимальне за швидкодією управління може бути отримано з використанням принципу максимуму Понтрягіна в умовах обліку невизначеності в описі початкового стану об'єкта управління. Синтезований оптимальний регулятор температурного режиму в індукційної міксері на основі мультіальтернатівного опису кінцевого стану, характерною особливістю якого є використання оптимальних рішень рідж-аналізу і параметричної класифікації температурного режиму. Показано, що такий підхід може бути застосований для блоку логічних умов при логічному синтезі комбінованої системи управління індукційним дуплекс-процесом.<br>Thesis for the degree of candidate of technical sciences in specialty 05.13.03 – systems and control processes. – National Technical University "Kharkov Polytechnic Institute", Kharkov, 2018. The thesis is devoted to the solution of an actual scientific and practical problem – the development of optimal control methods in conditions of uncertainty. The possibility of building an adequate mathematical model of an induction duplex melting process as a control object under the conditions of impossibility of implementing an active experiment plan under production conditions is shown. Based on this, it is proposed to use the results of the parametric description by definition of the local-optimal values of the input variables based on the implementation of the ridge analysis procedure to describe the final state in the problem of finding the optimal by the final state control. It is shown how using a combined procedure of artificial orthogonalization according to a passive experiment with an arbitrary form of the experiment plan and central orthogonal planning to obtain such a parametric description. The problem of synthesizing optimal control of induction melting in IST1 / 0.8-M5 furnaces in terms of alternative strategies was solved and it was proved that when choosing a melting strategy in the “bog” phase trajectory will constantly change due to the correction of the initial state, which is caused by the change in melting rate with the selected control method. It is shown how the optimal in terms of speed control can be obtained using the Pontryagin maximum principle in terms of taking into account the uncertainty in the description of the initial state of the control object. An optimal temperature regulator was synthesized in an induction mixer based on a multi-alternative description of the final state, a characteristic feature of which is the use of optimal solutions of ridge analysis and parametric classification of the temperature regime. It is shown how such an approach can be applied to a block of logical conditions in the logical synthesis of a combined control system of an induction duplex process.
11
Färm, Petra. "Integrated Logic Synthesis Using Simulated Annealing." Doctoral thesis, KTH, Mikroelektronik och Informationsteknik, IMIT, 2007. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-4257.
Full textAbstract:
A conventional logic synthesis flow is composed of three separate phases: technologyindependent optimization, technology mapping, and technology dependentoptimization. A fundamental problem with such a three-phased approach is thatthe global logic structure is decided during the first phase without any knowledge ofthe actual technology parameters considered during later phases. Although technologydependent optimization algorithms perform some limited logic restructuring,they cannot recover from fundamental mistakes made during the first phase, whichoften results in non-satisfiable solutions.We present a global optimization approach combining technology independentoptimization steps with technology dependent objectives in an annealing-basedframework. We prove that, for the presented move set and selection distribution, detailedbalance is satisfied and thus the annealing process asymptotically convergesto an optimal solution. Furthermore, we show that the presented approach cansmoothly trade-off complex, multiple-dimensional objective functions and achievecompetitive results. The combination of technology independent and technologydependent objectives is handled through dynamic weighting. Dynamic weightingreflects the sensitivity of the local graph structures with respect to the actual technologyparameters such as gate sizes, delays, and power levels. The results showthat, on average, the presented advanced annealing approach can improve the areaand delay of circuits optimized using the Boolean optimization technique providedby SIS with 11.2% and 32.5% respectively.Furthermore, we demonstrate how the developed logic synthesis framework canbe applied to two emerging technologies, chemically assembled nanotechnology andmolecule cascades. New technologies are emerging because a number of physicaland economic factors threaten the continued scaling of CMOS devices. Alternativesto silicon VLSI have been proposed, including techniques based on molecularelectronics, quantum mechanics, and biological processes. We are hoping that ourresearch in how to apply our developed logic synthesis framework to two of theemerging technologies might provide useful information for other designers movingin this direction.<br>QC 20100709
12
Kraan, H. C. "Proof planning for logic program synthesis." Thesis, University of Edinburgh, 1994. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.653555.
Full textAbstract:
The area of logic program synthesis is attracting increased interest. Most efforts have concentrated on applying techniques from functional program synthesis to logic program synthesis. This thesis investigates a new approach: Synthesizing logic programs automatically via middle-out reasoning in proof planning. [Bundy <I>et al </I>90a] suggested middle-out reasoning in proof planning. Middle-out reasoning uses variables to represent unknown details of a proof. Unification instantiates the variables in the subsequent planning, while proof planning provides the necessary search control. Middle-out reasoning is used for synthesis by planning the verification of an unknown logic program: The program body is represented with a meta-variable. The planning results both in an instantiation of the program body and a plan for the verification of that program. If the plan executes successfully, the synthesized program is partially correct and complete. Middle-out reasoning is also used to select induction schemes. Finding an appropriate induction scheme in synthesis is difficult, because the recursion in the program, which is unknown at the outset, determines the induction in the proof. In middle-out induction, we set up a schematic step case by representing the constructors applied to the induction variables with meta-variables. Once the step case is complete, the instantiated variables correspond to an induction appropriate to the recursion of the program. The results reported in this thesis are encouraging. The approach has been implemented as an extension of the proof planner CL<SUP>A</SUP>M [Bundy <I>et al</I> 90b], called <I>Periwinkle</I>, which has been used to synthesize a variety of programs fully automatically.
13
Winterstein, Felix. "Separation logic for high-level synthesis." Thesis, Imperial College London, 2016. http://hdl.handle.net/10044/1/33371.
Full textAbstract:
High-level synthesis (HLS) promises a significant shortening of the digital hardware design cycle by raising the abstraction level of the design entry to high-level languages such as C/C++. However, applications using dynamic, pointer-based data structures remain difficult to implement well, yet such constructs are widely used in software. Automated optimisations that leverage the memory bandwidth of dedicated hardware implementations by distributing the application data over separate on-chip memories and parallelise the implementation are often ineffective in the presence of dynamic data structures, due to the lack of an automated analysis that disambiguates pointer-based memory accesses. This thesis takes a step towards closing this gap. We explore recent advances in separation logic, a rigorous mathematical framework that enables formal reasoning about the memory access of heap-manipulating programs. We develop a static analysis that automatically splits heap-allocated data structures into provably disjoint regions. Our algorithm focuses on dynamic data structures accessed in loops and is accompanied by automated source-to-source transformations which enable loop parallelisation and physical memory partitioning by off-the-shelf HLS tools. We then extend the scope of our technique to pointer-based memory-intensive implementations that require access to an off-chip memory. The extended HLS design aid generates parallel on-chip multi-cache architectures. It uses the disjointness property of memory accesses to support non-overlapping memory regions by private caches. It also identifies regions which are shared after parallelisation and which are supported by parallel caches with a coherency mechanism and synchronisation, resulting in automatically specialised memory systems. We show up to 15x acceleration from heap partitioning, parallelisation and the insertion of the custom cache system in demonstrably practical applications.
14
Димко, Єгор Павлович. "Моделі та методи оптимального керування індукційним дуплекс-процесом за умов невизначеності". Thesis, НТУ "ХПІ", 2018. http://repository.kpi.kharkov.ua/handle/KhPI-Press/38290.
Full textAbstract:
Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.03 – системи та процеси керування. – Національний технічний університет "Харківський політехнічний інститут", Харків, 2018.
Дисертація присвячена вирішенню актуальної науково-практичної задачі – розробці методів оптимального управління в умовах невизначеності. Показана можливість побудови адекватної математичної моделі індукційного дуплекс-процесу плавки як об'єкта управління в умовах неможливості реалізації плану активного експерименту в виробничих умовах. На основі цього запропоновано для опису кінцевого стану в задачі пошуку оптимального за кінцевим станом управління використовувати результати параметричного опису за визначенням локально-оптимальних значень вхідних змінних на основі реалізації процедури рідж-аналізу. Показано, як з використанням комбінованої процедури штучної ортогоналізації за даними пасивного експерименту при довільній формі плану експерименту і центрального ортогонального планування отримати таке параметричне опис. Розв'язана задача синтезу оптимального управління індукційної плавкою в печах ІСТ1 / 0.8-М5 в умовах альтернативних стратегій і доведено, що при виборі стратегії плавлення на "болоті" фазова траєкторія буде постійно змінюватися внаслідок корекції початкового стану, що обумовлено зміною швидкості розплавлення при обраному способі управління. Показано, як оптимальне за швидкодією управління може бути отримано з використанням принципу максимуму Понтрягіна в умовах обліку невизначеності в описі початкового стану об'єкта управління. Синтезований оптимальний регулятор температурного режиму в індукційної міксері на основі мультіальтернатівного опису кінцевого стану, характерною особливістю якого є використання оптимальних рішень рідж-аналізу і параметричної класифікації температурного режиму. Показано, що такий підхід може бути застосований для блоку логічних умов при логічному синтезі комбінованої системи управління індукційним дуплекс-процесом.<br>Thesis for the degree of candidate of technical sciences in specialty 05.13.03 – systems and control processes. – National Technical University "Kharkov Polytechnic Institute", Kharkov, 2018. The thesis is devoted to the solution of an actual scientific and practical problem – the development of optimal control methods in conditions of uncertainty. The possibility of building an adequate mathematical model of an induction duplex melting process as a control object under the conditions of impossibility of implementing an active experiment plan under production conditions is shown. Based on this, it is proposed to use the results of the parametric description by definition of the local-optimal values of the input variables based on the implementation of the ridge analysis procedure to describe the final state in the problem of finding the optimal by the final state control. It is shown how using a combined procedure of artificial orthogonalization according to a passive experiment with an arbitrary form of the experiment plan and central orthogonal planning to obtain such a parametric description. The problem of synthesizing optimal control of induction melting in IST1 / 0.8-M5 furnaces in terms of alternative strategies was solved and it was proved that when choosing a melting strategy in the "bog" phase trajectory will constantly change due to the correction of the initial state, which is caused by the change in melting rate with the selected control method. It is shown how the optimal in terms of speed control can be obtained using the Pontryagin maximum principle in terms of taking into account the uncertainty in the description of the initial state of the control object. An optimal temperature regulator was synthesized in an induction mixer based on a multi-alternative description of the final state, a characteristic feature of which is the use of optimal solutions of ridge analysis and parametric classification of the temperature regime. It is shown how such an approach can be applied to a block of logical conditions in the logical synthesis of a combined control system of an induction duplex process.
15
Xu, Leeka. "Synthesis and optimisation of combinational logic using universal logic module networks." Thesis, Edinburgh Napier University, 1995. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.295379.
Full text
16
Matsuura, Satoshi. "Synthetic RNA-based logic computation in mammalian cells." Kyoto University, 2019. http://hdl.handle.net/2433/242426.
Full text
17
Krenz, René. "Graph dominators in logic synthesis and verification." Licentiate thesis, KTH, KTH, 2004. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-4293.
Full textAbstract:
<p>This work focuses on the usage of dominators in circuit graphs in order to reduce the complexity of synthesis and verification tasks. One of the contributions of this thesis is a new algorithm for computing multiple-vertex dominators in circuit graphs. Previous algorithms, based on single-vertex dominators suffer from their rare appearance in many circuits. The presented approach searches efficiently for multiple-vertex dominators in circuit graphs. It finds dominator relations, where algorithms for computing single-vertex dominators fail. Another contribution of this thesis is the application of dominators for combinational equivalence checking based on the arithmetic transform. Previous algorithms rely on representations providing an explicit or implicit disjoint function cover, which is usually excessive in memory requirements. The new algorithm allows a partitioned evaluation of the arithmetic transform directly on the circuit graph using dominator relations. The results show that the algorithm brings significant improvements in memory consumption for many benchmarks. Proper cuts are used in many areas of VLSI. They provide cut points, where a given problem can be split into two disjoint sub-problems. The algorithm proposed in this thesis efficiently detects proper cuts in a circuit graph and is based on a novel concept of a reduced dominator tree. The runtime of the algorithm is less than 0.4 seconds for the largest benchmark circuit. The final contribution of this thesis is the application of the proper cut algorithm as a structural method to decompose a Boolean function, represented by a circuit graph. In combination with a functional approach, it outperforms previous methods, which rely on functional decomposition only.</p>
18
Wang, Xiaojun. "An interactive, high-level logic synthesis system." Thesis, Staffordshire University, 1994. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.387386.
Full text
19
Vasilko, Milan. "Design synthesis for dynamically reconfigurable logic systems." Thesis, Bournemouth University, 2000. http://eprints.bournemouth.ac.uk/291/.
Full textAbstract:
Dynamic reconfiguration of logic circuits has been a research problem for over four decades. While applications using logic reconfiguration in practical scenarios have been demonstrated, the design of these systems has proved to be a difficult process demanding the skills of an experienced reconfigurable logic design expert. This thesis proposes an automatic synthesis method which relieves designers of some of the difficulties associated with designing partially dynamically reconfigurable systems. A new design abstraction model for reconfigurable systems is proposed in order to support design exploration using the presented method. Given an input behavioural model, a technology server and a set of design constraints, the method will generate a reconfigurable design solution in the form of a 3D floorplan and a configuration schedule. The approach makes use of genetic algorithms. It facilitates global optimisation to accommodate multiple design objectives common in reconfigurable system design, while making realistic estimates of configuration overheads and of the potential for resource sharing between configurations. A set of custom evolutionary operators has been developed to cope with a multiple-objective search space. Furthermore, the application of a simulation technique verifying the lll results of such an automatic exploration is outlined in the thesis. The qualities of the proposed method are evaluated using a set of benchmark designs taking data from a real reconfigurable logic technology. Finally, some extensions to the proposed method and possible research directions are discussed.
20
Oreifej, Rashad. "SYNTHESIS OF SELF-RESETTING STAGE LOGIC PIPELINES." Master's thesis, University of Central Florida, 2006. http://digital.library.ucf.edu/cdm/ref/collection/ETD/id/3572.
Full textAbstract:
As designers began to pack multi-million transistors onto a single chip, their reliance on a global clocking signal to orchestrate the operations of the chip has started to face almost insurmountable difficulties. As a result, designers started to explore clockless circuits to avoid the global clocking problem. Recently, self-resetting circuits implemented in dynamic logic families have been proposed as viable clockless alternatives. While these circuits can produce excellent performances, they display serious limitations in terms of area cost and power consumption. A middle-of-the-road alternative, which can provide a good performance and avoid the limitations seen in dynamic self-resetting circuits, would be to implement self-resetting behavior in static circuits. This alternative has been introduced recently as Self-Resetting Stage Logic and used to propose three types of clockless pipelines. Experimental studies show that these pipelines have the potential to produce high throughputs with a minimum area overhead if a suitable synthesis methodology is available. This thesis proposes a novel synthesis methodology to design and verify clockless pipelines implemented in SRSL by taking advantage of the maturity of current CAD tools. This methodology formulates the synthesis problem as a combinatorial analytical problem for which a run-time efficient exact solution is difficult to derive. Consequently, a two-phase algorithm is proposed to synthesize these pipelines from gate netlists subject to user-specified constraints. The first phase is a heuristic based on the as-soon-as-possible scheduling strategy in which each gate of the netlist is assigned to a single pipeline stage without violating the period constraint of each pipeline stage. On the other hand, the second phase consists of a heuristic, based on the Kernighan-Lin partitioning strategy, to minimize the number of nets crossing each pair of adjacent pipeline stages. The objective of this optimization is to reduce the number of latches separating pipeline stages since these latches tend to occupy large areas. Experiments conducted on a prototype of the synthesis algorithm reveal that these self-resetting stage logic pipelines can easily reach throughputs higher than 1 GHz. Furthermore, these experiments reveal that the area overhead needed to implement the self-resetting circuitry of these pipelines can be easily amortized over the area of the logic embedded in the pipeline stages. In the overall, the synthesis methods developed for SRSL produce low area overhead pipelines for wide and deep gate netlists while it tends to produce high throughput pipelines for wide and shallow gate netlists. This shows that these pipelines are mostly suitable for coarse-grain datapaths.<br>M.S.Cp.E.<br>School of Electrical Engineering and Computer Science<br>Engineering and Computer Science<br>Computer Engineering
21
Marshall, I. "Hardware synthesis from an interval temporal logic." Thesis, University of East Anglia, 1997. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.361488.
Full text
22
Padua, C. I. P. S. "A logic synthesis approach to silicon compilation." Thesis, University of Southampton, 1988. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.381234.
Full text
23
Lu, Aiguo. "Logic synthesis for field programmable gate arrays." Thesis, University of Bristol, 1995. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.295061.
Full text
24
Liu, Tai-hung. "Logic synthesis for high-performance digital circuits /." Digital version accessible at:, 1999. http://wwwlib.umi.com/cr/utexas/main.
Full text
25
PALANISWAMY, ASHOK KUMAR. "SYNTHESIS AND TESTING OF THRESHOLD LOGIC CIRCUITS." OpenSIUC, 2014. https://opensiuc.lib.siu.edu/dissertations/963.
Full textAbstract:
Threshold logic gates gaining more importance in recent years due to the significant development in the switching devices. This renewed the interest in synthesis and testing of circuits with threshold logic gates. Two important synthesis considerations of threshold logic circuits are addressed namely, threshold logic function identification and reducing the total number of threshold logic gates required to represent the given boolean circuit description. A fast method to identify the given Boolean function as a threshold logic function with weight assignment is introduced. It characterizes the threshold logic function based on the modified chows parameters which results in drastic reduction in time and complexity. Experiment results shown that the proposed method is at least 10 times faster for each input and around 20 times faster for 7 and 8 input, when comparing with the algorithmic based methods. Similarly, it is 100 times faster for 8 input, when comparing with asummable method. Existing threshold logic synthesis methods decompose the larger input functions into smaller input functions and perform synthesis for them. This results in increase in the number of threshold logic gates required to represent the given circuit description. The proposed implicit synthesis methods increase the size of the functions that can be handled by the synthesis algorithm, thus the number of threshold logic gates required to implement very large input function decreases. Experiment results shown that the reduction in the TLG count is 24% in the best case and 18% on average. An automatic test pattern generation approach for transition faults on a circuit consisting of current mode threshold logic gates is introduced. The generated pattern for each fault excites the maximum propagation delay at the gate (the fault site). This is a high quality ATPG. Since current mode threshold logic gate circuits are pipelined and the combinational depth at each pipeline stage is practically one. It is experimentally shown that the fault coverage for all benchmark circuits is approximately 97%. It is also shown that the proposed method is time efficient.
26
Lukac, Martin. "Quantum Inductive Learning and Quantum Logic Synthesis." PDXScholar, 2009. https://pdxscholar.library.pdx.edu/open_access_etds/2319.
Full textAbstract:
Since Quantum Computer is almost realizable on large scale and Quantum Technology is one of the main solutions to the Moore Limit, Quantum Logic Synthesis (QLS) has become a required theory and tool for designing Quantum Logic Circuits. However, despite its growth, there is no any unified aproach to QLS as Quantum Computing is still being discovered and novel applications are being identified.
The intent of this study is to experimentally explore principles of Quantum Logic Synthesis and its applications to Inductive Machine Learning. Based on algorithmic approach, I first design a Genetic Algorithm for Quantum Logic Synthesis that is used to prove and verify the methods proposed in this work.
Based on results obtained from the evolutionary experimentation, I propose a fast, structure and cost based exhaustive search that is used for the design of a novel, least expensive universal family of quantum gates.
The results form both the evolutionary and heuristic search are used to formulate an Inductive Learning Approach based on Quantum Logic Synthesis with the intended application being the humanoid behavioral robotics.
The presented approach illustrates a successful algorithmic approach, where the search algorithm was able to invent/discover novel quantum circuits as well as novel principles in Quantum Logic Synthesis.
27
Nguena-Timo, Omer. "Synthesis for a weak real-time logic." Thesis, Bordeaux 1, 2009. http://www.theses.fr/2010BOR13931/document.
Full textAbstract:
Dans cette thèse, nous nous intéressons à la spécification et à la synthèse de contrôleurs des systèmes temps-réels. Les modèles pour ces systèmes sont des Event-recording Automata. Nous supposons que les contrôleurs observent tous les évènements se produisant dans le système et qu'ils peuvent interdirent uniquement des évènements contrôlables. Tous les évènements ne sont pas nécessairement contrôlables. Une première étude est faite sur la logique Event-recording Logic (ERL). Nous proposons des nouveaux algorithmes pour les problèmes de vérification et de satisfaisabilité. Ces algorithmes présentent les similitudes entre les problèmes de décision cité ci-dessus et les problèmes de décision similaires étudiés dans le cadre du $\mu$-calcul. Nos algorithmes corrigent aussi des algorithmes présents dans la littérature. Les similitudes relevées nous permettent de prouver l'équivalence entre les formules de ERL et les formules de ERL en forme normale disjonctive. La logique ERL n'étant pas suffisamment expressive pour décrire certaines propriétés des systèmes, en particulier des propriétés des contrôleurs, nous introduisons une nouvelle logique WT$_\mu$. La logique WT$_\mu$ est une extension temps-réel faible du $\mu$-calcul. Nous proposons des algorithmes pour la vérification des systèmes lorsque les propriétés sont écrites en WT$_\mu$. Nous identifions deux fragments de WT$_\mu$ appelés WT$_\mu$ bien guardé ($WG$-WT$_\mu$) et WT$_\mu$ pour le contrôle ($C$-WT$_\mu$). La logique $WG$-WT$_\mu$ est plus expressif que $C$-WT$_\mu$. Nous proposons un algorithme qui permet de vérifier si une formule de $WG$-WT$_\mu$ possède un modèle (éventuellement déterministe). Cet algorithme nécessite de connaître les ressources (horloges et constante maximale comparée avec les horloges) des modèles. Dans le cadre de $C$-WT$_\mu$ l'algorithme que nous proposons et qui permet de décider si une formule possède un modèle n'a pas besoin de connaître les ressources des modèles. En utilisant $C$-WT$_\mu$ comme langage de spécification des systèmes, nous proposons des algorithmes de décision pour le contrôle centralisé et le $\Delta$-contrôle centralisé. Ces algorithmes permettent aussi de construire des modèles de contr\^oleurs. Lorsque les objectifs de contrôle sont décrits à l'aide des formules de $WG$-WT$_\mu$, nous montrons également comment synthétiser des contrôleurs décentralisés avec des ressources fixées à l'avance et ceci, lorsqu'au plus un contrôleur est non déterministe<br>In this dissertation, we consider the specification and the controller synthesis problem for real-time systems. Our models for systems are kinds of Event-recording automata. We assume that controllers observe all the events occurring in the system and can prevent occurrences of controllable events. We study Event-recording Logic (ERL). We propose new algorithms for the model-checking and the satisfiability problems of that logic. Our algorithms are similar to some algorithms proposed for the same problems in the setting of the standard $\mu$-calculus. They also correct earlier proposed algorithms. We define disjunctive normal form formulas and we show that every formula is equivalent to a formula in disjunctive normal form. Unfortunately, ERL is rather weak and can not describe some interesting real-time properties, in particular some important properties for controllers. We define a new logic that we call WT$_\mu$. The logic WT$_\mu$ is a weak real-time extension of the standard $\mu$-calculus. We present an algorithm for the model-checking problem of WT$_\mu$. We consider two fragments of WT$_\mu$ called well guarded WT$_\mu$ ($WG$-WT$_\mu$) and WT$_\mu$ for control ($C$-WT$_\mu$). We show that the satisfiability of $WG$-WT$_\mu$ is decidable if the maximal constants appearing in models are known a priori. Our algorithm allows to check whether a formula of $WG$-WT$_\mu$ has a deterministic model. The algorithm we propose to decide whether a formula of $C$-WT$_\mu$ has a model does not need to know the maximal constant used in models. All the algorithms for the satisfiability checking construct witness models. Using $C$-WT$_\mu$, we present algorithms for a centralised controller synthesis problem and a centralised $\Delta$-controller synthesis problems. The construction of witness controllers is effective. We also consider the decentralised controller synthesis problem with limited resources (the maximal constants used in controllers is known a priory) when the properties are described with $WG$-WT$_\mu$. We show that this problem is decidable and the computation of witness controllers is effective
28
Wist, Dominic. "Attacking complexity in logic synthesis of asynchronous circuits." Phd thesis, Universität Potsdam, 2011. http://opus.kobv.de/ubp/volltexte/2012/5970/.
Full textAbstract:
Most of the microelectronic circuits fabricated today are synchronous, i.e. they are driven by one or several clock signals. Synchronous circuit design faces several fundamental challenges such as high-speed clock distribution, integration of multiple cores operating at different clock rates, reduction of power consumption and dealing with voltage, temperature, manufacturing and runtime variations. Asynchronous or clockless design plays a key role in alleviating these challenges, however the design and test of asynchronous circuits is much more difficult in comparison to their synchronous counterparts.
A driving force for a widespread use of asynchronous technology is the availability of mature EDA (Electronic Design Automation) tools which provide an entire automated design flow starting from an HDL (Hardware Description Language) specification yielding the final circuit layout. Even though there was much progress in developing such EDA tools for asynchronous circuit design during the last two decades, the maturity level as well as the acceptance of them is still not comparable with tools for synchronous circuit design. In particular, logic synthesis (which implies the application of Boolean minimisation techniques) for the entire system's control path can significantly improve the efficiency of the resulting asynchronous implementation, e.g. in terms of chip area and performance. However, logic synthesis, in particular for asynchronous circuits, suffers from complexity problems.
Signal Transitions Graphs (STGs) are labelled Petri nets which are a widely used to specify the interface behaviour of speed independent (SI) circuits - a robust subclass of asynchronous circuits.
STG decomposition is a promising approach to tackle complexity problems like state space explosion in logic synthesis of SI circuits. The (structural) decomposition of STGs is guided by a partition of the output signals and generates a usually much smaller component STG for each partition member, i.e. a component STG with a much smaller state space than the initial specification.
However, decomposition can result in component STGs that in isolation have so-called irreducible CSC conflicts (i.e. these components are not SI synthesisable anymore) even if the specification has none of them. A new approach is presented to avoid such conflicts by introducing internal communication between the components.
So far, STG decompositions are guided by the finest output partitions, i.e. one output per component. However, this might not yield optimal circuit implementations. Efficient heuristics are presented to determine coarser partitions leading to improved circuits in terms of chip area.
For the new algorithms correctness proofs are given and their implementations are incorporated into the decomposition tool DESIJ. The presented techniques are successfully applied to some benchmarks - including 'real-life' specifications arising in the context of control resynthesis - which delivered promising results.<br>Moderner Schaltungsentwurf fokussiert hauptsächlich synchrone Schaltungstechnik mit allen inhärenten Problemen. Asynchone (d.h. ungetaktete) Schaltungen zeichnen sich jedoch nicht nur durch das Fehlen der Taktversatzproblematik gegenüber ihren synchronen Pendents aus, sondern auch insbesondere durch geringeren Energieverbrauch, günstigere EMV-Eigenschaften, hohe Performance, Modularität und Robustheit gegenüber Schwankungen in der Spannungsversorgung, im Herstellungsprozess sowie Temperaturunterschieden. Diese Vorteile werden mit höherer Integration sowie höheren Taktraten signifikanter. Jedoch ist der Entwurf und auch der Test asynchroner Schaltungen erheblich schwieriger verglichen mit synchronen Schaltungen.
Entwurfswerkzeuge zur Synthese asynchroner Schaltungen aus Hochsprachen-Spezifikationen sind zwar inzwischen verfügbar, sie sind jedoch noch nicht so ausgereift und bei weitem noch nicht so akzeptiert in der Industrie, wie ihre Äquivalente für den synchronen Schaltungsentwurf. Insbesondere fehlt es an Werkzeugunterstützung im Bereich der Logiksynthese komplexer Steuerungen („Controller“), welche kritisch für die Effizienz – z.B. in Bezug auf Chipfläche und Geschwindigkeit – der resultierenden Schaltungen oder Systeme ist.
Zur Spezifikation von Steuerungen haben sich Signalflankengraphen („signal transition graphs“, STGs) bewährt, die auch als Entwurfseinstieg für eine Logiksynthese von SI-Schaltungen („speed independent“) verwendet werden. (SI-Schaltungen gelten als sehr robuste asynchrone Schaltungen.) Aus den STGs werden zwecks Logiksynthese Automaten abgeleitet werden, deren Zustandszahl aber oft prohibitiv groß werden kann. Durch sogenannte STG-Dekomposition wird die Logiksynthese einer komplexen Schaltung ermöglicht, was bislang aufgrund von Zustandsexplosion oft nicht möglich war. Dabei wird der Spezifikations-STG laut einer gegebenen Partition von Ausgangssignalen in viele kleinere Teilnetze dekomponiert, wobei zu jedem Partitionsblock ein Teilnetz – mit normalerweise signifikant kleinerem Zustandsraum im Vergleich zur Spezifikation – erzeugt wird. Zu jedem Teilnetz wird dann eine Teilschaltung (Komponente) mittels Logiksynthese generiert.
Durch die Anwendung von STG-Dekomposition können jedoch Teilnetze erzeugt werden, die sogenannte irreduzible CSC-Konflikte aufweisen (d.h. zu diesen Teilnetzen kann keine SI-Schaltung erzeugt werden), obwohl die Spezifikation keine solchen Konflikte hatte. Diese Arbeit präsentiert einen neuen Ansatz, welcher die Entstehung solcher irreduziblen Konflikte vermeidet, und zwar durch die Einführung interner Kommunikation zwischen den (zu den Teilnetzen gehörenden) Schaltungskomponenten.
Bisher werden STG-Dekompositionen total durchgeführt, d.h. pro resultierender Komponente wird ein Ausgangssignal erzeugt. Das führt gewöhnlich nicht zu optimalen Schaltungsimplementierungen. In dieser Arbeit werden Heuristiken zur Bestimmung gröberer Ausgabepartitionen (d.h. Partitionsblöcke mit mehreren Ausgangssignalen) vorgestellt, die zu kleineren Schaltungen führen.
Die vorgestellten Algorithmen werden formal abgesichert und wurden in das bereits vorhandene Dekompositionswerkzeug DESIJ integriert. An praxisrelevanten Beispielen konnten die vorgestellten Verfahren erfolgreich erprobt werden.
29
Krenz-Bååth, René. "Dominator-based Algorithms in Logic Synthesis and Verification." Doctoral thesis, KTH, Elektronik- och datorsystem, ECS, 2007. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-4579.
Full textAbstract:
Today's EDA (Electronic Design Automation) industry faces enormous challenges. Their primary cause is the tremendous increase of the complexity of modern digital designs. Graph algorithms are widely applied to solve various EDA problems. In particular, graph dominators, which provide information about the origin and the end of reconverging paths in a circuit graph, proved to be useful in various CAD (Computer Aided Design) applications such as equivalence checking, ATPG, technology mapping, and power optimization. This thesis provides a study on graph dominators in logic synthesis and verification. The thesis contributes a set of algorithms for computing dominators in circuit graphs. An algorithm is proposed for finding absolute dominators in circuit graphs. The achieved speedup of three orders of magnitude on several designs enables the computation of absolute dominators in large industrial designs in a few seconds. Moreover, the computation of single-vertex dominators in large multiple-output circuit graphs is considerably improved. The proposed algorithm reduces the overall runtime by efficiently recognizing and re-using isomorphic structures in dominator trees rooted at different outputs of the circuit graph. Finally, common multiple-vertex dominators are introduced. The algorithm to compute them is faster and finds more multiple-vertex dominators than previous approaches. The thesis also proposes new dominator-based algorithms in the area of decomposition and combinational equivalence checking. A structural decomposition technique is introduced, which finds all simple-disjoint decompositions of a Boolean function which are reflected in the circuit graph. The experimental results demonstrate that the proposed technique outperforms state-of-the-art functional decomposition techniques. Finally, an approach to check the equivalence of two Boolean functions probabilistically is investigated. The proposed algorithm partitions the equivalence check employing dominators in the circuit graph. The experimental results confirm that, in comparison to traditional BDD-based equivalence checking methods, the memory consumption is considerably reduced by using the proposed technique.<br>QC 20100804
30
Lämmermann, Sven. "Runtime Service Composition via Logic-Based Program Synthesis." Doctoral thesis, KTH, Microelectronics and Information Technology, IMIT, 2002. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-3371.
Full text
31
Krenz-Bååth, René. "Dominator-based algorithms in logic synthesis and verification /." Stockholm : Department of Electronic, Computer, and Software Systems, School of Information and Communication Technology, Royal Institute of Technology (KTH), 2008. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-4579.
Full text
32
Zhuang, Nan. "Logic synthesis and technology mapping using genetic algorithms." Thesis, Imperial College London, 1998. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.286760.
Full text
33
Lester, Nigel L. K. "Logic synthesis using Reed-Muller and SOP expressions." Thesis, University of Bristol, 1995. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.295060.
Full text
34
Saul, Jonathan. "Logic synthesis based on the Reed-Muller representation." Thesis, University of Bristol, 1991. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.357962.
Full text
35
Cresswell, Stephen N. "Deductive synthesis of recursive plans in linear logic." Thesis, University of Edinburgh, 2001. http://hdl.handle.net/1842/1896.
Full textAbstract:
Conventionally, the problem of plan formation in Artificial Intelligence deals with the generation of plans in the form of a sequence of actions. This thesis describes an approach to extending the expressiveness of plans to include conditional branches and recursion. This allows problems to be solved at a higher level, such that a single plan in such a language is capable of solving a class of problems rather than a single problem instance. A plan of fixed size may solve arbitrarily large problem instances. To form such plans, we take a deductive planning approach, in which the formation of the plan goes hand-in-hand with the construction of the proof that the plan specification is realisable. The formalism used here for specifying and reasoning with planning problems is Girard's Institutionistic Linear Logic (ILL), which is attractive for planning problems because state change can be expressed directly as linear implication, with no need for frame axioms. We extract plans by means of the relationship between proofs in ILL and programs in the style of Abramsky. We extend the ILL proof rules to account for induction over inductively defined types, thereby allowing recursive plans to be synthesised. We also adapt Abramsky's framework to partially evaluate and execute the plans in the extended language. We give a proof search algorithm tailored towards the fragment of the ILL employed (excluding induction rule selection). A system implementation, Lino, comprises modules for proof checking, automated proof search, plan extraction and partial evaluation of plans. We demonstrate the encodings and solutions in our framework of various planning domains involving recursion. We compare the capabilities of our approach with the previous approaches of Manna and Waldinger, Ghassem-Sani and Steel, and Stephen and Biundo. We claim that our approach gives a good balance between coverage of problems that can be described and the tractability of proof search.
36
Wang, Lingli. "Automated synthesis and optimization of multilevel logic circuits." Thesis, Edinburgh Napier University, 2000. http://researchrepository.napier.ac.uk/Output/4342.
Full textAbstract:
With the increased complexity of Very Large Scaled Integrated (VLSI) circuits, multilevel logic synthesis plays an even more important role due to its flexibility and compactness. The history of symbolic logic and some typical techniques for multilevel logic synthesis are reviewed. These methods include algorithmic approach; Rule-Based approach; Binary Decision Diagram (BDD) approach; Field Programmable Gate Array(FPGA) approach and several perturbation applications. One new kind of don't cares (DCs), called functional DCs has been proposed for multilevel logic synthesis. The conventional two-level cubes are generalized to multilevel cubes. Then functional DCs are generated based on the properties of containment. The concept of containment is more general than unateness which leads to the generation of new DCs. A separate C program has been developed to utilize the functional DCs generated as a Boolean function is decomposed for both single output and multiple output functions. The program can produce better results than script.rugged of SIS, developed by UC Berkeley, both in area and speed in less CPU time for a number of testcases from MCNC and IWLS'93 benchmarks. In certain applications ANDjXOR (Reed-Muller) logic has shown some attractive advantages over the standard Boolean logic based on AND JOR operations. A bidirectional conversion algorithm between these two paradigms is presented based on the concept of polarity for sum-of-products (SOP) Boolean functions, multiple segment and multiple pointer facilities. Experimental results show that the algorithm is much faster than the previously published programs for any fixed polarity. Based on this algorithm, a new technique called redundancy-removal is applied to generalize the idea to very large multiple output Boolean functions. Results for benchmarks with up to 199 inputs and 99 outputs are presented. Applying the preceding conversion program, any Boolean functions can be expressed by fixed polarity Reed-Muller forms. There are 2n polarities for an n-variable function and the number of product terms depends on these polarities. The problem of exact polarity minimization is computationally extensive and current programs are only suitable when n :::; 15. Based on the comparison of the concepts of polarity in the standard Boolean logic and Reed-Muller logic, a fast algorithm is developed and implemented in C language which can find the best polarity for multiple output functions. Benchmark examples of up to 25 inputs and 29 outputs run on a personal computer are given. After the best polarity for a Boolean function is calculated, this function can be further simplified using mixed polarity methods by combining the adjacent product terms. Hence, an efficient program is developed based on decomposition strategy to implement mixed polarity minimization for both single output and very large multiple output Boolean functions. Experimental results show that the numbers of product terms are much less than the results produced by ESPRESSO for some categories of functions.
37
McKenzie, Lynn Mhairi. "Logic synthesis and optimisation using Reed-Muller expansions." Thesis, Edinburgh Napier University, 1995. http://researchrepository.napier.ac.uk/Output/4276.
Full textAbstract:
This thesis presents techniques and algorithms which may be employed to represent, generate and optimise particular categories of Exclusive-OR Sum- Of-Products (ESOP) forms. The work documented herein concentrates on two types of Reed-Muller (RM) expressions, namely, Fixed Polarity Reed-Muller (FPRM) expansions and KROnecker (KRO) expansions (a category of mixed polarity RM expansions). Initially, the theory of switching functions is comprehensively reviewed. This includes descriptions of various types of RM expansion and ESOP forms. The structure of Binary Decision Diagrams (BDDs) and Reed-Muller Universal Logic Module (RM-ULM) networks are also examined. Heuristic algorithms for deriving optimal (sub-optimal) FPRM expansions of Boolean functions are described. These algorithms are improved forms of an existing tabular technique [1]. Results are presented which illustrate the performance of these new minimisation methods when evaluated against selected existing techniques. An algorithm which may be employed to generate FPRM expansions from incompletely specified Boolean functions is also described. This technique introduces a means of determining the optimum allocation of the Boolean 'don't care' terms so as to derive equivalent minimal FPRM expansions. The tabular technique [1] is extended to allow the representation of KRO expansions. This new method may be employed to generate KRO expansions from either an initial incompletely specified Boolean function or a KRO expansion of different polarity. Additionally, it may be necessary to derive KRO expressions from Boolean Sum-Of-Products (SOP) forms where the product terms are not minterms. A technique is described which forms KRO expansions from disjoint SOP forms without first expanding the SOP expressions to minterm forms. Reed-Muller Binary Decision Diagrams (RMBDDs) are introduced as a graphical means of representing FPRM expansions. RMBDDs are analogous to the BDDs used to represent Boolean functions. Rules are detailed which allow the efficient representation of the initial FPRM expansions and an algorithm is presented which may be employed to determine an optimum (sub-optimum) variable ordering for the RMBDDs. The implementation of RMBDDs as RM-ULM networks is also examined. This thesis is concluded with a review of the algorithms and techniques developed during this research project. The value of these methods are discussed and suggestions are made as to how improved results could have been obtained. Additionally, areas for future work are proposed.
38
Sarabi, Andisheh. "Logic Synthesis with High Testability for Cellular Arrays." PDXScholar, 1994. https://pdxscholar.library.pdx.edu/open_access_etds/4752.
Full textAbstract:
The new Field Programmable Gate Array (FPGA) technologies and their structures have opened up new approaches to logic design and synthesis. The main feature of an FPGA is an array of logic blocks surrounded by a programmable interconnection structure. Cellular FPGAs are a special class of FPGAs which are distinguished by their fine granularity and their emphasis on local cell interconnects. While these characteristics call for specialized synthesis tools, the availability of logic gates other than Boolean AND, OR and NOT in these architectures opens up new possibilities for synthesis. Among the possible realizations of Boolean functions, XOR logic is shown to be more compact than AND/OR and also highly testable. In this dissertation, the concept of structural regularity and the advantages of XOR logic are used to investigate various synthesis approaches to cellular FPGAs, which up to now have been mostly nonexistent. Universal XOR Canonical Forms, Two-level AND/XOR, restricted factorization, as well as various Directed Acyclic Graph structures are among the proposed approaches. In addition, a new comprehensive methodology for the investigation of all possible XOR canonical forms is introduced. Additionally, a new compact class of XOR-based Decision Diagrams for the representation of Boolean functions, called Kronecker Functional Decision Diagrams (KFDD), is presented. It is shown that for the standard, hard, benchmark examples, KFDDs are on average 35% more compact than Binary Decision Diagrams, with some reductions of up to 75% being observed.
39
Silva, Augusto Neutzling. "Syhthesis of thereshold logic based circuits." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 2014. http://hdl.handle.net/10183/119435.
Full textAbstract:
Circuitos baseados em portas lógicas de limiar (threshold logic gates – TLG) vem sendo estudados como uma alternativa promissora em relação ao tradicional estilo lógico CMOS, baseado no operadores AND e OR, na construção de circuitos integrados digitais. TLGs são capazes de implementar funções Booleanas mais complexas em uma única porta lógica. Diversos novos dispositivos, candidatos a substituir o transistor MOS, não se comportam como chaves lógicas e são intrinsicamente mais adequados à implementação de TLGs. Exemplos desses dispositivos são os memristores, spintronica, diodos de tunelamento ressonante (RTD), autômatos celulares quânticos (QCA) e dispositivos de tunelamento de elétron único (SET). Para o desenvolvimento de um fluxo de projeto de circuitos integrados baseados em lógica threshold, duas etapas são fundamentais: (1) identificar se uma dada função Booleana corresponde a uma função lógica threshold (TLF), isto é, pode ser implementada em um único TLG e computar os pesos desse TLG; (2) se uma função não é identificada como TLF, outro método de síntese lógica deve construir uma rede de TLGs otimizada que implemente a função. Este trabalho propõe métodos para atacar cada um desses dois problemas, e os resultados superam os métodos do estado-da-arte. O método proposto para realizar a identificação de TLFs é o primeiro método heurístico capaz de identificar todas as funções de cinco e seis variáveis, além de identificar mais funções que os demais métodos existentes quando o número de variáveis aumenta. O método de síntese de redes de TLGs é capaz de sintetizar circuitos reduzindo o número de portas TLG utilizadas, bem como a profundidade lógica e o número de interconexões. Essa redução é demonstrada através da síntese dos circuitos de avaliação da MCNC em comparação com os métodos já propostos na literatura. Tais resultados devem impactar diretamente na área e desempenho do circuito.<br>In this work, a novel method to synthesize digital integrated circuits (ICs) based on threshold logic gates (TLG) is proposed. Synthesis considering TLGs is quite relevant, since threshold logic has been revisited as a promising alternative to conventional CMOS IC design due to its suitability to emerging technologies, such as resonant tunneling diodes, memristors and spintronics devices. Identification and synthesis of threshold logic functions (TLF) are fundamental steps for the development of an IC design flow based on threshold logic. The first contribution is a heuristic algorithm to identify if a function can be implemented as a single TLG. Furthermore, if a function is not detected as a TLF, the method uses the functional composition approach to generate an optimized TLG network that implements the target function. The identification method is able to assign optimal variable weights and optimal threshold value to implement the function. It is the first heuristic algorithm that is not based on integer linear programming (ILP) that is able to identify all threshold functions with up to six variables. Moreover, it also identifies more functions than other related heuristic methods when the number of variables is more than six. Differently from ILP based approaches, the proposed algorithm is scalable. The average execution time is less than 1 ms per function. The second major contribution is the constructive process applied to generate optimized TLG networks taking into account multiple goals and design costs, like gate count, logic depth and number of interconnections. Experiments carried out over MCNC benchmark circuits show an average gate count reduction of 32%, reaching up to 54% of reduction in some cases, when compared to related approaches.
40
Nayeem, Noor Muhammed. "Synthesis and testing of reversible Toffoli circuits." Thesis, Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science, c2012, 2012. http://hdl.handle.net/10133/3309.
Full textAbstract:
Recently, researchers have been interested in reversible computing because of its ability to
dissipate nearly zero heat and because of its applications in quantum computing and low
power VLSI design. Synthesis and testing are two important areas of reversible logic. The
thesis first presents an approach for the synthesis of reversible circuits from the exclusive-
OR sum-of-products (ESOP) representation of functions, which makes better use of shared
functionality among multiple outputs, resulting in up to 75% minimization of quantum cost
compared to the previous approach. This thesis also investigates the previous work on constructing
the online testable circuits and points out some design issues. A simple approach
for online fault detection is proposed for a particular type of ESOP-based reversible circuit,
which is also extended for any type of Toffoli circuits. The proposed online testable designs
not only address the problems of the previous designs but also achieve significant improvements
of up to 78% and 99% in terms of quantum cost and garbage outputs, respectively.<br>xii, 82 leaves : ill. ; 29 cm
41
Midde, Bharath Reddy. "Design, analysis, and synthesis of 16 bit arithmetic logic unit using reversible logic gate." Thesis, California State University, Long Beach, 2016. http://pqdtopen.proquest.com/#viewpdf?dispub=10099864.
Full textAbstract:
<p> In the modern world, an Arithmetic Logic Unit (ALU) is one of the most crucial component of an embedded system and is used in many devices like calculators, cell phones, computers, and so on. An ALU is a multi-functional circuit that conditionally performs one of several possible functions on two operands A and B depending on control inputs. It is nevertheless the main performer of any computing device. This project proposes the design of programmable reversible logic gate structures, targeted for the ALU implementation and their use in the realization of an efficient reversible ALU. This ALU consists of sixteen operations, the arithmetic operations include addition, subtraction, multiplication and the logical operations includes AND, OR, NOT and XOR. All the modules are being designed using the basic reversible gates. </p><p> Using reversible logic gates instead of traditional logic AND/OR gates, a reversible ALU is constructed whose function is the same as traditional ALU. Comparing with the number of input bits and the discarded bits of the traditional ALU, the reversible ALU significantly reduces the use and loss of information bits. The proposed reversible 16-bit ALU reuses the information bits and achieves the goal of lowering delay of logic circuits by 42% approximately. Programmable reversible logic gates are realized in Verilog HDL.</p>
42
El-Maleh, Aiman H. "Testability preservation of combinational and sequential logic synthesis transformations." Thesis, McGill University, 1995. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=29016.
Full textAbstract:
In order to reduce the test development cost and guarantee testable designs, it is essential to have synthesis transformations that are testability and test-set preserving. In this thesis, we study testability preservation of transformations that form the basis of existing state-of-the-art logic synthesis and optimization techniques.<br>We show that the concurrent decomposition and factorization transformations, except dual-extraction of multiplexor structures, preserve testablility and test-set under several testing constraints. Furthermore, we provide sufficient conditions for test-set preservation under the algebraic resubstitution with complement transformation that cover a larger class of complementary expressions than was known previously. Experimental results show that dual-extraction of multiplexor structures is utilized in only 2 out of 50 benchmark circuits. We demonstrate that while disabling this transformation has negligible effect on area, it results in an efficient test-set preserving multilevel logic synthesis algorithm.<br>Recently, it has been shown that retiming has a very strong impact on the run time of sequential, structural automatic test pattern generators (ATPGs), as well as the levels of fault coverage and fault efficiency attained. We show that retiming preserves testability with respect to a single stuck-at fault test set by adding a prefix sequence of a pre-determined number of arbitrary input vectors. Furthermore, we show that a new circuit attribute, termed density of encoding, is the main reason for high test generation time. We also propose a novel approach for reducing test pattern generation cost based on test-set preserving transformations. Experimental results show that high fault coverages can be achieved on high performance circuits optimized by retiming with a much less CPU time (a reduction of two orders of magnitude in several instances) than if ATPG is attempted directly on those circuits.
43
Rao, Jinghai. "Semantic Web Service Composition via Logic-based Program Synthesis." Doctoral thesis, Norwegian University of Science and Technology, Department of Computer and Information Science, 2004. http://urn.kb.se/resolve?urn=urn:nbn:no:ntnu:diva-344.
Full textAbstract:
<p>The ability to efficient selection and integration of inter-organizational heterogeneous Web services at runtime becomes an important requirement to the Web service provision. In an Web service application, if no single existing Web service can satisfy the functionality required by the user, there should be a program or an agent to automated combine existing services together in order to fulfill the request.</p><p>The aim of this thesis is to consider the Web service composition problem from the viewpoint of logic-based program synthesis, and to propose an agent-based framework for supporting the composition process in scalable and flexible manner. The approach described in this thesis uses Linear Logic-based theorem proving to assist and automate composition of Semantic Web services. The approach uses a Semantic Web service language (DAML-S) for external presentation of Web services, while, internally, the services are presented by extralogical axioms and proofs in Linear Logic. Linear Logic, as a resource conscious logic, enables us to capture the concurrent features of Web services formally (including parameters, states and non-functional attributes). The approach uses a process calculus to present the process model of the composite service. The process calculus is attached to the Linear Logic inference rules in the style of type theory. Thus the process model for a composite service can be generated directly from the complete proof. We introduce a set of subtyping rules that defines a valid dataflow for composite services.</p><p>The subtyping rules that are used for semantic reasoning are presented with Linear Logic inference figures. The composition system has been implemented based on a multi-agent architecture, AGORA. The agent-based design enables the different components for Web service composition system, such as the theorem prover, semantic reasoner and translator to integrated to each other in a loosely coupled manner.</p><p>We conclude with discussing how this approach has been directed to meet the main challenges in Web service composition. First, it is autonomous so that the users do not required to analyze the huge amount of available services manually. Second, it has good scalability and flexibility so that the composition is better performed in a dynamic environment. Third, it solves the heterogeneous problem because the Semantic Web information is used for matching and composing Web services.</p><p>We argue that LL theorem proving, combined with semantic reasoning offers a practical approach to the success to the composition of Web services. LL, as a logic for specifying concurrent programming, provides higher expressive powers in the modeling of Web services than classical logic. Further, the agent-based design enables the different components for Web service composition system to integrated to each other in a loosely coupled manner.</p><p>The main contributions of this thesis is summarized as follows. First, an generic framework is developed for the purpose of presenting an abstract process of the automated Semantic Web service composition. Second, a specific system based on the generic platform has been developed. The system focuses on the translation between the internal and external languages together with the process extraction from the proof. Third, applications of the subtyping inference rules that are used for semantic reasoning is discussed. Fourth, an agent architecture is developed as the platform for Web service provision and composition.</p>
44
Dubrova, Elena Vladimirovna. "Boolean and multiple-valued functions in combinational logic synthesis." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1998. http://www.collectionscanada.ca/obj/s4/f2/dsk2/ftp02/NQ34259.pdf.
Full text
45
Ngom, Alioune. "Synthesis of multiple-valued logic functions by neural networks." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1998. http://www.collectionscanada.ca/obj/s4/f2/dsk2/ftp03/NQ36787.pdf.
Full text
46
Yee, Gin Sun. "Dynamic logic design and synthesis using clock-delayed domino /." Thesis, Connect to this title online; UW restricted, 1999. http://hdl.handle.net/1773/6039.
Full text
47
Xu, Siyao M. Eng Massachusetts Institute of Technology. "Reversible logic synthesis with minimal usage of ancilla bits." Thesis, Massachusetts Institute of Technology, 2015. http://hdl.handle.net/1721.1/100615.
Full textAbstract:
Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2015.<br>This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.<br>Cataloged from student-submitted PDF version of thesis.<br>Includes bibliographical references (pages 49-50).<br>Reversible logic has attracted much research interest over the last few decades, especially due to its application in quantum computing. In the construction of reversible gates from basic gates, ancilla bits are commonly used to remove restrictions on the type of gates that a certain set of basic gates generates. With unlimited ancilla bits, many gates (such as Toffoli and Fredkin) become universal reversible gates. However, ancilla bits can be expensive to implement, thus making the problem of minimizing necessary ancilla bits a practical topic. This thesis explores the problem of reversible logic synthesis using a single base gate and a few ancilla bits. Two base gates are discussed: a variation of the 3- bit Toffoli gate and the original 3-bit Fredkin gate. There are three main results associated with these two gates: i) the variated Toffoli gate can generate all n-bit reversible gates using 1 ancilla bit, ii) the variated Toffoli can generate all n-bit reversible gates that are even permutations using no ancilla bit, iii) the Fredkin gate can generate all n-bit conservative reversible gates using 1 ancilla bit. Prior to this paper, the best known result for general universality requires three basic gates, and the best known result for conservative universality needs 5 ancilla bits. The second result is trivially optimal. For the first and the third result, we explicitly prove their optimality: the variated Toffoli cannot generate all n-bit reversible gates without using any extra input lines, and the Fredkin gate cannot generate all n-bit conservative reversible gates without using extra input lines. We also explore a stronger version of the second converse by introducing a new concept called borrowed bits, and prove that the Fredkin gate cannot generate all n-bit conservative reversible gates without ancilla bits, even with an unlimited number of borrowed bits.<br>by Siyao Xu.<br>M. Eng.
48
Yasuoka, Koichi. "Ternary Decision Diagrams and Their Applications for Logic Synthesis." Kyoto University, 1996. http://hdl.handle.net/2433/77846.
Full text
49
Al-Jassani, ban Adil. "Computer aided synthesis and optimisation of electronic logic circuits." Thesis, Edinburgh Napier University, 2011. http://researchrepository.napier.ac.uk/Output/6658.
Full textAbstract:
In this thesis, a variety of algorithms for synthesis and optimisation of combinational and sequential logic circuits are developed. These algorithms could be part of new commercial EGAD package for future VLSI digital designs. The results show that considerable saving in components can be achieved resulting in simpler designs that are smaller, cheaper, consume less power and easier to test. The purpose of generating different sets of coefficients related to Reed Muller (RM) is that they contain different number of terms; therefore the minimum one can be selected to design the circuits with reduced gate count. To widen the search space and achieve better synthesis tools, representations of Mixed Polarity Reed Muller (MPRM), Mixed Polarity Dual Reed Muller (MPDRM), and Pseduo Kronecker Reed Muller (PKRO RM) expansions are investigated. Efficient and fast combinatorial techniques and algorithms are developed for the following: â Bidirectional conversion between MPRM/ MPDRM form and Fixed Polarity Reed Muller forms (FPRM)/Fixed Polarity Dual Reed Muller forms (FPDRM) form respectively. The main advantages for these techniques are their simplicity and suitability for single and multi output Boolean functions. â Computing the coefficients of any polarity related to PKRO_RM class starting from FPRM coefficients or Canonical Sum of Products (CSOP). â Computing the coefficients of any polarity related to MPRM/or MPDRM directly from standard form of CSOP/Canonical Product of sums (CPOS) Boolean functions, respectively. The proposed algorithms are efficient in terms of CPU time and can be used for large functions. For optimisation of combinational circuits, new techniques and algorithms based on algebraic techniques are developed which can be used to generate reduced RM expressions to design circuits in RM/DRM domain starting from FPRM/FPDRM, respectively. The outcome for these techniques is expansion in Reed Muller domain with minimal terms. The search space is 3`" Exclusive OR Sum of Product (ESOP)/or Exclusive NOR Product of Sums (ENPOS) expansions. Genetic Algorithms (GAs) are also developed to optimise combinational circuits to find optimal MPRM/MPDRM among 3° different polarities without the need to do exhaustive search. These algorithms are developed for completely and incompletely specified Boolean functions. The experimental results show that GA can find optimum solutions in a short time compared with long time required running exhaustive search in all the benchmarks tested. Multi Objective Genetic Algorithm (MOGA) is developed and implemented to determine the optimal state assignment which results in less area and power dissipation for completely and incompletely specified sequential circuits. The goal is to find the best assignments which reduce the component count and switching activity simultaneously. The experimental results show that saving in components and switching activity are achieved in most of the benchmarks tested compared with recently published research. All algorithms are implemented in C++.
50
Patino, Alberto. "Reversible Logic Synthesis Using a Non-blocking Order Search." PDXScholar, 2010. https://pdxscholar.library.pdx.edu/open_access_etds/162.
Full textAbstract:
Reversible logic is an emerging area of research. With the rapid growth of markets such as mobile computing, power dissipation has become an increasing concern for designers (temperature range limitations, generating smaller transistors) as well as customers (battery life, overheating). The main benefit of utilizing reversible logic is that there exists, theoretically, zero power dissipation. The synthesis of circuits is an important part of any design cycle. The circuit used to realize any specification must meet detailed requirements for both layout and manufacturing. Quantum cost is the main metric used in reversible logic. Many algorithms have been proposed thus far which result in both low gate count and quantum cost. In this thesis the AP algorithm is introduced. The goal of the algorithm is to drive quantum cost down by using multiple non-blocking orders, a breadth first search, and a quantum cost reduction transformation. The results shown by the AP algorithm demonstrate that the resulting quantum cost for well-known benchmarks are improved by at least 9% and up to 49%.