Reductions in the cost and size of integrated circuits are allowing more and more complex functions to be included in previously simple tools such as lawn-mowers, ovens, and thermostats. Because of this, the process of synthesizing such functions from their initial representation to an optimal VLSI implementation is rarely hand-performed; instead, automated synthesis and optimization tools are a necessity. The factors such tools must take into account are numerous, including area (size), power consumption, and timing factors, to name just a few. Existing tools have traditionally focused upon optimization of two-level representations. However, new technologies such as Field Programmable Gate Arrays (FPGAs) have generated additional interest in three-level representations and structures such as Kronecker Decision Diagrams (KDDs). The reason for this is that when implementing a circuit on an FPGA, the cost of implementing exclusive-or logic is no more than that of traditional AND or OR gates. This dissertation investigates the use of the autocorrelation coefficients in logic synthesis for these types of structures; specifically, whether it is possible to pre-process a function to produce a subset of its autocorrelation coefficients and make use of this information in the choice of a three-level decomposition or of decomposition types within a KDD. This research began as a general investigation into the properties of autocorrelation coefficients of switching functions. Much work has centered around the use of a function's spectral coefficients in logic synthesis; however, very little work has used a function's autocorrelation coefficients. Their use has been investigated in the areas of testing, optimization for Programmable Logic Arrays (PLAs), identification of types of complexity measures, and in various DD-related applications, but in a limited manner. This has likely been due to the complexity in their computation. In order to investigate the uses of these coefficients, a fast computation technique was required, as well as knowledge of their basic properties. Both areas are detailed as part of this work, which demonstrates that it is feasible to quickly compute the autocorrelation coefficients. With these investigations as a foundation we further apply the autocorrelation coefficients to the development of a classification technique. The autocorrelation classes are similar to the spectral classes, but provide significantly different information. The dissertation demonstrates that some of this information highlighted by the autocorrelation classes may allow for the identification of exclusive-or logic within the function or classes of functions. In relation to this, a major contribution of this work involves the design and implementation of algorithms based on these results. The first of these algorithms is used to identify three-level decompositions for functions, and the second to determine decomposition type lists for KDD-representations. Each of these implementations compares well with existing tools, requiring on average less than one second to complete, and performing as well as the existing tools about 70% of the time. / Graduate

Made available in DSpace on 2014-10-09T12:31:23Z (GMT). No. of bitstreams: 0 / Made available in DSpace on 2014-10-09T13:59:33Z (GMT). No. of bitstreams: 1 01433.pdf: 5221000 bytes, checksum: 2ca9fa37b9a7f292a7bd310078bceb73 (MD5) / Dissertacao (Mestrado) / IPEN/D / Instituto de Pesquisas Energeticas e Nucleares - IPEN/CNEN-SP

Made available in DSpace on 2014-10-09T12:31:30Z (GMT). No. of bitstreams: 0 / Made available in DSpace on 2014-10-09T13:59:33Z (GMT). No. of bitstreams: 1 01417.pdf: 15560137 bytes, checksum: 857fe87504571bc27557a261974b6971 (MD5) / Tese (Doutoramento) / IPEN/T / Universitaet Karlsruhe - Fakultaet fuer Maschinenbau

Made available in DSpace on 2014-10-09T12:24:18Z (GMT). No. of bitstreams: 0 / Made available in DSpace on 2014-10-09T14:04:26Z (GMT). No. of bitstreams: 1 00508.pdf: 1394827 bytes, checksum: 4841c122d3cfa0b91639516519105971 (MD5) / Dissertacao (Mestrado) / IEA/D / Instituto de Fisica, Universidade de Sao Paulo - IF/USP

Made available in DSpace on 2014-10-09T12:31:23Z (GMT). No. of bitstreams: 0 / Made available in DSpace on 2014-10-09T13:59:33Z (GMT). No. of bitstreams: 1 01433.pdf: 5221000 bytes, checksum: 2ca9fa37b9a7f292a7bd310078bceb73 (MD5) / Dissertacao (Mestrado) / IPEN/D / Instituto de Pesquisas Energeticas e Nucleares - IPEN/CNEN-SP

Made available in DSpace on 2014-10-09T12:31:30Z (GMT). No. of bitstreams: 0 / Made available in DSpace on 2014-10-09T13:59:33Z (GMT). No. of bitstreams: 1 01417.pdf: 15560137 bytes, checksum: 857fe87504571bc27557a261974b6971 (MD5) / Tese (Doutoramento) / IPEN/T / Universitaet Karlsruhe - Fakultaet fuer Maschinenbau

Made available in DSpace on 2014-10-09T12:24:18Z (GMT). No. of bitstreams: 0 / Made available in DSpace on 2014-10-09T14:04:26Z (GMT). No. of bitstreams: 1 00508.pdf: 1394827 bytes, checksum: 4841c122d3cfa0b91639516519105971 (MD5) / Dissertacao (Mestrado) / IEA/D / Instituto de Fisica, Universidade de Sao Paulo - IF/USP

In this work, we focus on two kinds of problems involving the proximity of geometric objects. The first part revolves around intersection detection problems. In this setting, we are given two (or more) geometric objects and we are allowed to preprocess them. Then, the objects are translated and rotated within a geometric space, and we need to efficiently test if they intersect in these new positions. We develop representations of convex polytopes in any (constant) dimension that allow us to perform this intersection test in logarithmic time.In the second part of this work, we turn our attention to facility location problems. In this setting, we are given a set of sites in a geometric space and we want to place a facility at a specific place in such a way that the distance between the facility and its farthest site is minimized. We study first the constrained version of the problem, in which the facility can only be place within a given geometric domain. We then study the facility location problem under the geodesic metric. In this setting, we consider a different way to measure distances: Given a simple polygon, we say that the distance between two points is the length of the shortest path that connects them while staying within the given polygon. In both cases, we present algorithms to find the optimal location of the facility.In the process of solving facility location problems, we rely heavily on geometric structures called Voronoi diagrams. These structures summarize the proximity information of a set of ``simple'' geometric objects in the plane and encode it as a decomposition of the plane into interior disjoint regions whose boundaries define a plane graph. We study the problem of constructing Voronoi diagrams incrementally by analyzing the number of edge insertions and deletions needed to maintain its combinatorial structure as new sites are added. / Option Informatique du Doctorat en Sciences / info:eu-repo/semantics/nonPublished

No abstract available. / Dissertation (MSc (Metallurgy))--University of Pretoria, 2006. / Materials Science and Metallurgical Engineering / unrestricted

The goal of this thesis is to first give an overview of the modern approach, using the paper of A. Vershik and A. Okounkov, to inductively parametrizing all irreducible representations of the symmetric groups. This theory is then used to answer questions concerning to central projections in the group algebra. We index units first by partitions, and then by so called standard tableaux. We also present a new result and discuss future research exploring the connections between this theory and Quantum Information.