Embedded memories dominate area, power and cost of modern very large scale integrated circuits system on chips ( VLSI SoCs). Furthermore, due to process variations, it becomes challenging to design reliable energy efficient systems. Therefore, fault-tolerant designs will be area efficient, cost effective and have low power consumption. The idea of this project is to design embedded memories where reliability is intentionally compromised to increase storage density. Gain cell memories are smaller than SRAM and unlike DRAM they are logic compatible. In multilevel DRAM storage density is increased by storing two bits per cell without reducing feature size. This thesis targets multilevel read and write schemes that provide short access time, small area overhead and are highly reliable. First, timing analysis of reference design is performed for read and write operation. An analytical model of write bit line (WBL) is developed to have an estimate of write delay. Replica technique is designed to generate the delay and track variations of storage array. Design of replica technique is accomplished by designing replica column, read and write control circuits. A memory controller is designed to control the read and write operation in multilevel DRAM. A multilevel DRAM is with storage capacity of eight kilobits is designed in UMC 90 nm technology. Simulations are performed for testing and results are reported for energy and access time. Monte Carlo analysis is done for variation tolerance of replica technique. Finally, multilevel DRAM with replica technique is compared with reference design to check the improvement in access times.

We present an Intellectual Property (IP) protection technique for sequential circuits driven by embedding a decomposed signature into a Finite State Machine (FSM) through the manipulation of the arbitrary state encoding of the unprotected FSM. This technique is composed of three steps: (a) transforming the signature into a watermark graph, (b) embedding watermark graphs into the original FSM's State Transition Graph (STG) and (c) generating models for verification and extraction. In the watermark construction process watermark graphs are generated from signatures. The proposed methods for watermark construction are: (1) BSD, (2) FSD, and (3) HSD. The HSD method is shown to be advantageous for all signatures while providing sparse watermark FSMs with complexity O(n^2). The embedding process is related to the sub-graph matching problem. Due to the computational complexity of the matching problem, attempts to reverse engineer or remove the constructed watermark from the protected FSM, with only finite resources and time, are shown to be infeasible. The proposed embedding solutions are: (1) Brute Force and (2) Greedy Heuristic. The greedy heuristic has a computational complexity of O(n log n), where n is the number of states in the watermark graph. The greedy heuristic showed improvements for three of the six encoding schemes used in experimental results. Model generation and verification utilizes design automation techniques for generating multiple representations of the original, watermark, and watermarked FSMs. Analysis of the security provided by this method shows that a variety of attacks on the watermark and system including: (1) data-mining hidden functionality, (2) preimage, (3) secondary preimage, and (4) collision, can be shown to be computationally infeasible. Experimental results for the ten largest IWLS 93 benchmarks that the proposed watermarking technique is a secure, yet flexible, technique for protecting sequential circuit based IP cores.

We present a method of mitigating theft of sequential circuit Intellectual Property hardware designs through means of watermarking. Hardware watermarking can be performed by selectively embedding a watermark in the state encoding of the Finite State Machine. This form of watermarking can be achieved by matching a directed graph representation of the watermark with a sub-graph in state transition graph representation of the FSM. We experiment with three approaches: a brute force method that provides a proof of concept, a greedy algorithm that provides excellent runtime with a drawback of sub-optimal results, and finally a simulated annealing method that provides near optimal solutions with runtimes that meet our performance goals. The simulated annealing approach when applied on a ten benchmarks chosen from IWLS 93 benchmark suite, provides watermarking results with edge overhead of less than 6% on average with runtimes not exceeding five minutes.

Biological neural systems (BNS) in general and the central nervous system (CNS) specifically exhibit a strikingly efficient computational power along with an extreme flexible and adaptive basis for acquiring and integrating new knowledge. Acquiring more insights into the actual mechanisms of information processing within the BNS and their computational capabilities is a core objective of modern computer science, computational sciences and neuroscience. Among the main reasons of this tendency to understand the brain is to help in improving the quality of life of people suffer from loss (either partial or complete) of brain or spinal cord functions. Brain-computer-interfaces (BCI), neural prostheses and other similar approaches are potential solutions either to help these patients through therapy or to push the progress in rehabilitation. There is however a significant lack of knowledge regarding the basic information processing within the CNS. Without a better understanding of the fundamental operations or sequences leading to cognitive abilities, applications like BCI or neural prostheses will keep struggling to find a proper and systematic way to help patients in this regard. In order to have more insights into these basic information processing methods, this thesis presents an approach that makes a formal distinction between the essence of being intelligent (as for the brain) and the classical class of artificial intelligence, e.g. with expert systems. This approach investigates the underlying mechanisms allowing the CNS to be capable of performing a massive amount of computational tasks with a sustainable efficiency and flexibility. This is the essence of being intelligent, i.e. being able to learn, adapt and to invent. The approach used in the thesis at hands is based on the hypothesis that the brain or specifically a biological neural circuitry in the CNS is a dynamic system (network) that features emergent capabilities. These capabilities can be imported into spiking neural networks (SNN) by emulating the dynamic neural system. Emulating the dynamic system requires simulating both the inner workings of the system and the framework of performing the information processing tasks. Thus, this work comprises two main parts. The first part is concerned with introducing a proper and a novel dynamic synaptic model as a vital constitute of the inner workings of the dynamic neural system. This model represents a balanced integration between the needed biophysical details and being computationally inexpensive. Being a biophysical model is important to allow for the abilities of the target dynamic system to be inherited, and being simple is needed to allow for further implementation in large scale simulations and for hardware implementation in the future. Besides, the energy related aspects of synaptic dynamics are studied and linked to the behaviour of the networks seeking for stable states of activities. The second part of the thesis is consequently concerned with importing the processing framework of the dynamic system into the environment of SNN. This part of the study investigates the well established concept of binding by synchrony to solve the information binding problem and to proposes the concept of synchrony states within SNN. The concepts of computing with states are extended to investigate a computational model that is based on the finite-state machines and reservoir computing. Biological plausible validations of the introduced model and frameworks are performed. Results and discussions of these validations indicate that this study presents a significant advance on the way of empowering the knowledge about the mechanisms underpinning the computational power of CNS. Furthermore it shows a roadmap on how to adopt the biological computational capabilities in computation science in general and in biologically-inspired spiking neural networks in specific. Large scale simulations and the development of neuromorphic hardware are work-in-progress and future work. Among the applications of the introduced work are neural prostheses and bionic automation systems.

Máquinas de Estados Finitos, além de suas inúmeras aplicações, são amplamente utilizadas na Engenharia de Software para modelar especificações de sistemas. Nesses modelos, projetistas podem inserir, inadvertidamente, estados redundantes, ou seja, que exibem o mesmo comportamento. A eliminação desses estados traz diversos benefícios para as atividades que utilizam o modelo, como menor complexidade e menos recursos físicos para implementação. O processo de eliminação desses estados é denominado minimização, e pode ser realizado em tempo polinomial para máquinas completamente especificadas. Por outro lado, a minimização de máquinas parciais, cuja especificação não cobre todo o domínio de entrada, somente pode ser obtida em tempo polinomial com o uso de abordagens não determinísticas, ou seja, trata-se de um problema NP-Completo. Este trabalho apresenta uma estratégia para a minimização de máquinas de estados finitos parciais que faz o uso de heurísticas e otimizações para tornar o processo mais eficiente. Visando mensurar tal ganho de eficiência, foram realizados experimentos, nos quais os tempos de execução de uma implementação do método proposto foram medidos, juntamente com os tempos de implementações de dois outros métodos conhecidos. Os resultados mostraram vantagens significativas de performance para o novo método em relação aos métodos anteriores / Finite State Machines are largely used on Software Engineering to model systems specifications. In these models, designers may inadvertently include redundant states, i.e., states which exhibit the same input/output behavior. The absence of such states brings benefits to the modeling activities, reducing the complexity and taking less physical resources on implementations. The process of eliminating redundant states is known as minimization, and can be accomplished in polynomial time for completely specified machines. On the other hand, the minimization of partially specified machines, i.e., machines which have undefined behavior for some inputs, can only be done in polynomial time when non-deterministic approaches are applied. It is a known NP-Complete problem. This work presents a deterministic approach to minimize incompletely specified Finite State Machines, using heuristics and optimizations to accomplish the task more efficiently. In order to measure the performance improvements, experiments were done, observing the running time of an implementation of the proposed method, along with running times of implementations of two other known methods. The results revealed a significant performance advantage when using the proposed approach

O teste baseado em modelos tem como objetivo auxiliar a atividade de testes, gerando conjuntos de casos de teste a partir de modelos, como Máquinas de Estados Finitos (MEFs). Diversos métodos de geração de conjuntos de caso de teste têm sido propostos ao longo das últimas décadas, com algumas contribuições recentes. Dentre esses trabalhos, há os que geram seqüências de verificação que são conjuntos de caso de teste formados por uma única seqüência e que são capazes de detectar os defeitos de uma implementação cujo comportamento pode ser modelado a partir de uma MEF. Neste trabalho é proposto um algoritmo de geração de seqüências de verificação que tem a finalidade de gerar seqüências menores que as seqüências geradas pelos métodos existentes. O algoritmo, que é baseado na técnica de algoritmos genéticos e nas condições de suficiência para a completude de casos de teste, consiste basicamente em criar novas seqüências a partir de seqüências menores. Por meio de mutações, novas seqüências são geradas pelo algoritmo. As condições de suficiência são utilizadas para determinar quais seqüências geradas são seqüências de verificação. Também são apresentados neste trabalho os estudos experimentais realizados para determinar o comportamento do algoritmo diante de diferentes contextos / Model-based testing aims at aiding the testing activity, generating test cases from models such as Finite State Machines (FSM). Several test cases generation methods have been proposed along the last decades, with some recent contributions. Among these works, there are those that generate checking sequences, which are test cases formed by a single sequence and which are capable of detecting faults in an implementation whose behavior can be modeled as an FSM. This work proposes a checking sequences generation algorithm which aims at generating sequences smaller than the sequences generated by existing methods. The algorithm, which is based on the genetic algorithms technique and sufficient conditions for completeness of test cases, basically consists of creating new sequences from small sequences. Through mutations, new sequences are generated by the algorithm. The suffcient conditions are used to determine which sequences are checking sequences. Experimental studies are presented in this work to determine the behavior of the algorithm on different contexts

Developing real-time strategy game AI is a challenging task due to that an AI-player has to deal with many different decisions and actions in an ever changing complex game world. Humans have little problem when it comes to dealing with the complexity of the game genre while it is a difficult obstacle to overcome for the computer. Adapting to the opponents strategy is one of many things that players typically have to do during the course of a game in the real-time strategy genre. This report presents a finite-state machine based solution to the mentioned problem and implements it with the help of the existing Starcraft: Broodwar AI Opprimobot. The extension is experimentally compared to the original implementation of Opprimobot. The comparison shows that both manages to achieve approximately the same win ratio against the built-in AI of Starcraft: Broodwar, but the modified version provides away to model more complex strategies.

This master’s thesis deals with analysis of state machines for embedded applications. The issue of finite-state machine is described theoretically. The document also contains a proposal for funding for modeling finite state machines in Matlab/Simulink. It is designed data representation of finite automaton. Over this data representation algorithm of minimization is applied. Finally, the algorithm is implemented to generate code in C language.

Fuzzing is a test method used to automatically generate test case inputs and to executea system under test (SUT) with those inputs. The method is traditionally used to discovercrash-inducing bugs in software. Fuzzing can generate thousands of inputs per secondand many implementations use smart techniques to reach deeply into the code. Fewfuzz testing implementations, however, have the ability to explore and retain informationof state in stateful applications. We develop an extension of the fuzzer American Fuzzy Lop (AFL), building on the workof the Ijon project, and utilize its fuzzing capabilities to discover states in SUT; inparticular, applications built as finite state machines. The extension successfullyharnesses AFL’s input generation to explore the SUT’s state space. We then implement functionality that allows for the SUT to return state information tothe fuzzer, including the state path and path length. Furthermore, functionality is addedthat allows the test operator to specify the expected number of states in the SUT, andGUI extensions that provide real-time information of state discovery during fuzzing. The state information retained after a completed fuzzing session is automaticallysummarized in a structured format. We further demonstrate that the summarizedinformation can be used to generate test cases for a test operator to verify the SUT.

Les travaux de cette thèse s'inscrivent dans la théorie des automates et des langages formels. ils peuvent se diviser en deux parties qui donnent également deux visions différentes de manipuler les langages dans la théorie des automates. La première partie s'intéresse à la notion de dérivation des expressions qui permet de faire passer le formalisme des quotients de langages au niveau des expressions rationnelles. en particulier cette thèse étudie les termes dérivés cassés d'une expression rationnelle. ces termes dérivés cassés permettent, sous certaines circonstances, et à l'aide d'autres opérations, une réversibilité de la transformation d'un automate en une expression rationnelle. Dans la seconde partie, la théorie des automates est utilisée pour traiter des problèmes sur les systèmes de numération. les systèmes de numération représentent des nombres par des mots. il est possible d'utiliser des automates et des transducteurs afin d'être capable de 'compter' sur un langage rationnel représentant les entiers. plus précisément ces automates sont étudiés pour le cas des systèmes de numération abstraits qui associent à chaque entier un mot d'un langage rationnel, ordonné par l'ordre radiciel. dans un tel système, la fonction qui permet de calculer le mot suivant est une fonction co-séquentielle par morceaux, c'est-à-dire qu'il suffit de lire deux fois le mot d'entrée de la droite vers la gauche pour qu'une machine calcule son image. / The works in this thesis lies in the automata and formal languages theory. in the first part, the notion of derivation of rational expressions is studied. more precisely the broken derived terms of a rational expressions. Theses broken derived terms allow, under certain circumstances, with some other operations on automata, to have the reversibility of the transformation of an automaton into a rational expression. In the second part, automata and tranducers allow to 'count' on a numeration system, where integers are represented by words on a rational language. more precisely, this part adress the problem of counting in an abstract numeration systems, which maps to any word of a rational language, ordored by radix order, the integer corresponding to the order of the word. in such a numeration system, the function which computes the successor of a word is a piecewise co-sequential function: it can be realised by a machine which reads the input two times to give the output.