• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 2
  • 1
  • 1
  • Tagged with
  • 7
  • 3
  • 2
  • 2
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

ATPG based Preimage Computation: Efficient Search Space Pruning using ZBDD

Chandrasekar, Kameshwar 06 August 2003 (has links)
Preimage Computation is a fundamental step in Formal Verification of VLSI designs. Conventional OBDD-based methods for Formal Verification suffer from spatial explosion, since large designs can blow up in terms of memory. On the other hand, SAT/ATPG based methods are less demanding on memory. But the run-time can be huge for these methods, since they must explore an exponential search space. In order to reduce this temporal explosion of SAT/ATPG based methods, efficient learning techniques are needed. Conventional ATPG aims at computing a single solution for its objective. In preimage computation, we must enumerate all solutions for the target state during the search. Similar sub-problems often occur during preimage computation that can be identified by the internal state of the circuit. Therefore, it is highly desirable to learn from these search-states and avoid repeated search of identical solution/conflict subspaces, for better performance. In this thesis, we present a new ZBDD based method to compactly store and efficiently search previously explored search-states. We learn from these search-states and avoid repeating subsets and supersets of previously encountered search spaces. Both solution and conflict subspaces are pruned based on simple set operations using ZBDDs. We integrate our techniques into a PODEM based ATPG engine and demonstrate their efficiency on ISCAS '89 benchmark circuits. Experimental results show that upto 90% of the search-space is pruned due to the proposed techniques and we are able to compute preimages for target states where a state-of-the-art technique fails. / Master of Science
2

Towards a Theory of Recursive Function Complexity: Sigma Matrices and Inverse Complexity Measures

Fournier, Bradford M 18 December 2015 (has links)
This paper develops a data structure based on preimage sets of functions on a finite set. This structure, called the sigma matrix, is shown to be particularly well-suited for exploring the structural characteristics of recursive functions relevant to investigations of complexity. The matrix is easy to compute by hand, defined for any finite function, reflects intrinsic properties of its generating function, and the map taking functions to sigma matrices admits a simple polynomial-time algorithm . Finally, we develop a flexible measure of preimage complexity using the aforementioned matrix. This measure naturally partitions all functions on a finite set by characteristics inherent in each function's preimage structure.
3

Abstraction Guided Semi-formal Verification

Parikh, Ankur 28 June 2007 (has links)
Abstraction-guided simulation is a promising semi-formal framework for design validation in which an abstract model of the design is used to guide a logic simulator towards a target property. However, key issues still need to be addressed before this framework can truly deliver on it's promise. Concretizing, or finding a real trace from an abstract trace, remains a hard problem. Abstract traces are often spurious, for which no corresponding real trace exits. This is a direct consequence of the abstraction being an over-approximation of the real design. Further, the way in which the abstract model is constructed is an open-ended problem which has a great impact on the performance of the simulator. In this work, we propose a novel approaches to address these issues. First, we present a genetic algorithm to select sets of state variables directly from the gate-level net-list of the design, which are highly correlated to the target property. The sets of selected variables are used to build the Partition Navigation Tracks (PNTs). PNTs capture the behavior of expanded portions of the state space as they related to the target property. Moreover, the computation and storage costs of the PNTs is small, making them scale well to large designs. Our experiments show that we are able to reach many more hard-to-reach states using our proposed techniques, compared to state-of-the-art methods. Next, we propose a novel abstraction strengthening technique, where the abstract design is constrained to make it more closely resemble the concrete design. Abstraction strengthening greatly reduces the need to refine the abstract model for hard to reach properties. To achieve this, we efficiently identify sequentially unreachable partial sates in the concrete design via intelligent partitioning, resolution and cube enlargement. Then, these partial states are added as constraints in the abstract model. Our experiments show that the cost to compute these constraints is low and the abstract traces obtained from the strengthened abstract model are far easier to concretize. / Master of Science
4

A nonlinear appearance model for age progression

Bukar, Ali M., Ugail, Hassan 15 October 2017 (has links)
No / Recently, automatic age progression has gained popularity due to its nu-merous applications. Among these is the search for missing people, in the UK alone up to 300,000 people are reported missing every year. Although many algorithms have been proposed, most of the methods are affected by image noise, illumination variations, and most importantly facial expres-sions. To this end we propose to build an age progression framework that utilizes image de-noising and expression normalizing capabilities of kernel principal component analysis (Kernel PCA). Here, Kernel PCA a nonlinear form of PCA that explores higher order correlations between input varia-bles, is used to build a model that captures the shape and texture variations of the human face. The extracted facial features are then used to perform age progression via a regression procedure. To evaluate the performance of the framework, rigorous tests are conducted on the FGNET ageing data-base. Furthermore, the proposed algorithm is used to progress images of Mary Boyle; a six-year-old that went missing over 39 years ago, she is considered Ireland’s youngest missing person. The algorithm presented in this paper could potentially aid, among other applications, the search for missing people worldwide.
5

Méthodes de démélange non-linéaires pour l'imagerie hyperspectrale / Non-linear unmixing methods for hyperspectral imaging

Nguyen Hoang, Nguyen 03 December 2013 (has links)
Dans cette thèse, nous avons présenté les aspects de la technologie d'imagerie hyperspectrale en concentrant sur le problème de démélange non-linéaire. Pour cette tâche, nous avons proposé trois solutions. La première consiste à intégrer les avantages de l'apprentissage de variétés dans les méthodes de démélange classique pour concevoir leurs versions non-linéaires. Les résultats avec les données générées sur une variété bien connue - le "Swissroll"- donne des résultats prometteurs. Les méthodes fonctionnent beaucoup mieux avec l'augmentation de la non-linéarité. Cependant, l'absence de contrainte de non-négativité dans ces méthodes reste une question ouverte pour des améliorations à trouver. La deuxième proposition vise à utiliser la méthode de pré-image pour estimer une transformation inverse de l'espace de données entrées des pixels vers l'espace des abondances. L'ajout des informations spatiales sous forme "variation totale" est également introduit pour rendre l'algorithme plus robuste au bruit. Néanmoins, le problème d'obtention des données de réalité terrain nécessaires pour l'étape d'apprentissage limite l'application de ce type d'algorithmes. / In this thesis , we present several aspects of hyperspectral imaging technology , while focusing on the problem of non- linear unmixing . We have proposed three solutions for this task. The first one is integrating the advantages of manifold learning in classical unmixing methods to design their nonlinear versions . Results with data generated on a well-known manifold- the " Swissroll " - seem promising. The methods work much better with the increase in non- linearity compared with their linear version. However, the absence of constraint of non- negativity in these methods remains an open question for improvements . The second proposal is using the pre-image method for estimating an inverse transformation of the data form pixel space to abundance of space . The adoption of spatial information as " total variation " is also introduced to make the algorithm more robust to noise . However, the problem of obtaining ground truth data required for learning step limits the application of such algorithms.
6

Spline křivky s pythagorejským hodografem / Pythagorean hodograph splines

Kadlec, Kryštof January 2020 (has links)
In this thesis the main object of our concern is a Pythagorean hodograph B- spline curve. We recall notions of both Pythagorean hodograph (PH) curves and B-spline functions separately first. Then we put these fields together to generalize PH curves to their B-spline instances. We encapsulate these curves in various spaces under one algebraic structure using the formalism of Clifford algebras. We consider both Euclidean and Minkowski spaces of lower dimensions which give room for real applications and use of these curves. We support our results by giving numerous examples. 1
7

Um novo método criptográfico baseado no cálculo de pré-imagens de autômatos celulares caóticos, não-homogêneos e não-aditivos / A new cryptography method based on the pre-image calculus of chaotic, non-homogeneous and non-additive cellular automata

Macêdo, Heverton Barros de 12 September 2007 (has links)
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / A new cryptographic method based on cellular automata (CA) has been investigated. In this method, the ciphering process is performed by preimages computation while deciphering is performed by CA temporal evolution. The preimages calculus is able to be used in a cryptographic system only if any arbitrary CA lattice has at least one preimage. In a previous method proposed by Gutowitz, this guarantee of pre-image was obtained due to the toggle property of the rules used as keys and some additional bits used in the calculus. Here a new method is proposed in which two distinct types of toggle rules are used without the need of additional bits. As a consequence, the cipher text and the plain text have the same size. One of the rules has the toggle property and it is responsible for CA dynamical behavior. The other rule is responsible to guarantee preimage existence, without need of additional bits. This method also differs from other cryptographic models based on additive rules previously published. The model is resistant against an attack known as differential cryptanalysis. Besides, it is efficient considering hardware implementation due to the intrinsic parallelism of the model. / O presente trabalho investiga um novo método criptográfico baseado em autômatos celulares (ACs). Neste método o processo de cifragem é realizado através do cálculo de préimagens enquanto a decifragem é realizada através da evolução temporal dos ACs. Para que o cálculo de pré-imagem possa ser utilizado em um sistema criptográfico, é necessário que todos os reticulados possíveis de um AC possuam pelo menos uma pré-imagem. Em um método anterior, proposto por Gutowitz, essa garantia de existência de pré-imagem foi conseguida graças à propriedade de sensitividade das regras empregadas como chaves e à utilização de bits adicionais. Nessa dissertação, um novo método é proposto onde dois tipos distintos de regras fazem com que não seja necessário acrescentar bits adicionais, tornando o texto cifrado e texto original do mesmo tamanho. Uma das regras utilizadas também possui a propriedade de sensitividade e é responsável pelo comportamento dinâmico médio do AC. A outra regra é responsável por garantir que sempre exista uma pré-imagem, sem a necessidade dos bits adicionais. Esse método também difere de outros modelos criptográficos publicados anteriormente que utilizam ACs com regras aditivas. Uma das características do modelo aqui proposto é a sua resistência contra um tipo de ataque conhecido como criptoanálise diferencial, além da possibilidade de implementação eficiente em hardware, usufruindo do paralelismo do modelo. / Mestre em Ciência da Computação

Page generated in 0.0903 seconds